2025-11-24T22:28:17.253920

Exploration-free Algorithms for Multi-group Mean Estimation

Wei, Zhong, Li

We address the problem of multi-group mean estimation, which seeks to allocate a finite sampling budget across multiple groups to obtain uniformly accurate estimates of their means. Unlike classical multi-armed bandits, whose objective is to minimize regret by identifying and exploiting the best arm, the optimal allocation in this setting requires sampling every group on the order of $Î(T)$ times. This fundamental distinction makes exploration-free algorithms both natural and effective. Our work makes three contributions. First, we strengthen the existing results on subgaussian variance concentration using the Hanson-Wright inequality and identify a class of strictly subgaussian distributions that yield sharper guarantees. Second, we design exploration-free non-adaptive and adaptive algorithms, and we establish tighter regret bounds than the existing results. Third, we extend the framework to contextual bandit settings, an underexplored direction, and propose algorithms that leverage side information with provable guarantees. Overall, these results position exploration-free allocation as a principled and efficient approach to multi-group mean estimation, with potential applications in experimental design, personalization, and other domains requiring accurate multi-group inference.

academic

탐색-자유 다중군집 평균 추정 알고리즘

기본 정보

논문 ID: 2510.10374
제목: Exploration-free Algorithms for Multi-group Mean Estimation
저자: Ziyi Wei (Virginia Tech), Huaiyang Zhong (Virginia Tech), Xiaocheng Li (Imperial College London)
분류: cs.LG, stat.ML
발표 시간: 2025년 10월 12일
논문 링크: https://arxiv.org/abs/2510.10374

초록

본 논문은 다중군집 평균 추정 문제를 연구하며, 제한된 표본 예산을 여러 군집에 배분하여 각 군집의 평균에 대한 일관되게 정확한 추정을 얻는 것을 목표로 한다. 전통적인 다중팔 밴딧과 달리(최적 팔을 식별하고 활용하여 후회를 최소화하는 것이 목표), 이 설정에서의 최적 배분은 각 군집을 Θ(T)번 표본화해야 한다. 이러한 근본적인 차이로 인해 탐색-자유 알고리즘이 자연스럽고 효과적이다. 본 논문은 세 가지 주요 기여를 한다: 첫째, Hanson-Wright 부등식을 사용하여 준가우시안 분산 집중의 기존 결과를 강화하고, 더 날카로운 보장을 생성할 수 있는 엄격한 준가우시안 분포 클래스를 식별한다. 둘째, 탐색-자유의 비적응형 및 적응형 알고리즘을 설계하여 기존 결과보다 더 타이트한 후회 경계를 확립한다. 셋째, 프레임워크를 문맥적 밴딧 설정으로 확장하며, 이는 탐색이 부족한 방향이고, 보조 정보를 활용하는 알고리즘을 제안하고 증명 가능한 보장을 제공한다.

연구 배경 및 동기

문제 정의

다중군집 평균 추정 문제는 제한된 시간 범위 T 내에서 K개 군집에 표본 예산을 배분하여 모든 군집의 평균 추정이 일관된 정확도에 도달하도록 요구한다. 구체적으로, 제k 군집에 대해 보상 분포가 Pk이고 평균이 μk, 분산이 σk²일 때, 목표는 p-노름 목적함수를 최소화하는 것이다:

$R_p(n) = \left\|\left\{\frac{\sigma_k^2}{n_k}\right\}_{k=1}^K\right\|_p$

여기서 nk는 제k 군집에 대한 표본 수이다.

연구 동기

실제 응용 필요성: 여론조사, 실험 설계, 개인화 추천 등의 분야에서 최적 군집만이 아닌 모든 군집에 대해 정확하고 공정한 추정이 필요하다.
이론적 과제: 전통적인 다중팔 밴딧과 달리, 최적 배분 방안은 각 팔이 Θ(T)번 표본화되도록 요구하므로 전통적인 탐색-활용 트레이드오프가 불필요하다.
기존 방법의 한계: 기존의 UCB 클래스 알고리즘은 불필요한 탐색 오버헤드를 도입하며 문제의 구조적 특성을 충분히 활용하지 못한다.

핵심 기여

이론적 개선: Hanson-Wright 부등식을 기반으로 준가우시안 분산 집중 부등식을 개선하고, 엄격한 준가우시안 분포 범주를 식별하여 더 날카로운 이론적 보장을 획득한다.
알고리즘 설계: 두 가지 탐색-자유 알고리즘을 제안한다:
- 비적응형 알고리즘(분산 하한에 대한 사전 지식 필요)
- 적응형 알고리즘(사전 지식 불필요, 신뢰 구간 사용)
프레임워크 확장: 다중군집 평균 추정을 문맥적 밴딧 설정으로 처음 확장하고, 해당 알고리즘을 제안하며 이론적 분석을 제공한다.
성능 향상: 기존 최고 결과 대비 후회 경계에서 log T 인수를 제거하여 더 타이트한 이론적 경계를 달성한다.

방법 상세 설명

작업 정의

K개 군집이 주어지고, 각 군집 k의 보상 분포 Pk는 미지의 평균 μk와 분산 σk²를 갖는다. 시간 범위 T 내에서 각 시점에 한 군집을 선택하여 표본화하며, 목표는 모든 군집의 추정 오차의 p-노름을 최소화하는 것이다.

최적 배분 방안

명제 2.1은 이론적 최적 배분을 제시한다: $n_k^* = \frac{\sigma_k^q}{\sum_{j=1}^K \sigma_j^q} \cdot T$

여기서 q = 2p/(p+1)(p가 유한할 때) 또는 q = 2(p = ∞일 때)이다.

알고리즘 1: 비적응형 배분

핵심 아이디어: 두 단계로 진행

첫 번째 단계: 각 군집을 균등하게 τ라운드 표본화하여 분산 추정
두 번째 단계: 추정된 분산에 따라 최적 비율로 남은 예산 배분

주요 매개변수:

초기 길이: $\tau = \frac{\sigma^q}{\sigma^q + (K-1)\underline{\sigma}^q} \cdot T$
배분 가중치: $\lambda_{k,\tau} = \frac{\hat{\sigma}_{k,\tau}^q}{\sum_{j=1}^K \hat{\sigma}_{j,\tau}^q}$

알고리즘 2: 적응형 알고리즘

개선점: 분산 하한에 대한 사전 지식이 불필요하며, 신뢰 구간을 통해 적응적으로 조정한다.

핵심 메커니즘:

신뢰 구간 구성: 개선된 분산 집중 부등식을 기반으로 LCB 및 UCB 구성
적응형 중지: 각 군집의 중지 시간을 동적으로 계산
팔 제거 전략: 최적 팔 식별의 제거 기법과 유사

신뢰 구간:

$LCB_{k,n} = \max\{\hat{\sigma}_{k,n}^2 - \varepsilon_{k,n}^+, 0\}$
$UCB_{k,n} = \hat{\sigma}_{k,n}^2 + \varepsilon_{k,n}^-$

알고리즘 3: 문맥적 확장

문제 설정: 각 군집 k는 매개변수 벡터 βk와 연관되며, 문맥 ct를 관찰할 때 보상은: $X_{k,n} = \beta_k^T c_n + \eta_{k,n}$

목적함수: $\min \mathbb{E}\left[\sum_{k=1}^K \|\hat{\beta}_{k,n_k} - \beta_k\|^2\right]$

주요 혁신:

릿지 회귀 추정기 사용
선결정 후관찰 표본화 전략
문맥 벡터의 독립성 유지

실험 설정

데이터셋

가우시안 분포: K=4개 군집, 평균은 U(-1,1)에서 표본화, 분산은 {1, 1.5, 2, 2.5}
Rademacher + 가우시안: Carpentier 등의 실험 설정 재현
대칭 베타 분포: 엄격한 준가우시안 성질의 장점 검증
문맥적 설정: K∈{5,10,20}, 차원 d=4, 문맥은 초입방체에서 균등 표본화

평가 지표

경험적 후회: $R_p(n^{\pi}) - R_p(n^*)$
이론적 상한의 타이트함
알고리즘의 수렴 속도

비교 방법

일반 준가우시안(GSG) 설정 vs 엄격한 준가우시안(SSG) 설정
분산 하한 알려짐 vs 미지
다양한 p값의 성능 비교

실험 결과

주요 결과

이론적 경계의 타이트함: 엄격한 준가우시안 설정에서의 이론적 상한이 경험적 결과와 더 가깝게 나타나며, 특히 p=∞일 때 두드러진다.
분산 하한의 영향: 분산 하한이 미지일 때 알고리즘 성능이 현저히 저하되며, 이러한 저하는 GSG와 SSG 설정에서 다른 시점에 나타난다.
시간 복잡도: SSG 설정에서 첫 번째 단계의 길이가 현저히 감소하여, σ²와 관련된 것에서 log T에만 의존하는 상수로 변한다.

구체적 수치 결과

가우시안 실험에서 T > 2×10⁴일 때 알고리즘이 이론적 예상 성능을 보이기 시작
SSG 설정의 이론적 경계가 GSG 설정보다 약 한 자릿수 타이트함
문맥적 실험에서 경험적 후회의 기울기가 -2에 근접하여 이론적 예측과 일치

소거 실험

엄격한 준가우시안 vs 일반 준가우시안: 엄격한 준가우시안 분포가 더 나은 상수 인수와 더 간단한 알고리즘 구현을 제공한다.
다양한 p값의 비교: p=∞일 때 가장 타이트한 이론적 경계를 제공한다.
문맥적 차원의 영향: 팔의 수가 증가함에 따라 성능이 안정적인 스케일링 관계를 유지한다.

이론적 분석

주요 이론적 결과

정리 3.1(비적응형 알고리즘, p=∞): $\mathbb{E}[R_p(n^{\pi_1}) - R_p(n^*)] \leq 4\sqrt{2}\sigma^2 F_{Alg1,\infty}(\lambda, \sigma^2) T^{-3/2}\sqrt{\log T} + o(T^{-3/2})$

정리 3.2(비적응형 알고리즘, p<∞): $\mathbb{E}[R_p(n^{\pi_1}) - R_p(n^*)] \leq 24\sigma^4 F_{Alg1,p}(\lambda, \sigma^2) T^{-2}\log T + o(T^{-2})$

정리 4.1(적응형 알고리즘): 동일한 차수의 경계를 제공하나 상수 인수는 약간 다르다.

주요 개선사항

분산 집중: Hanson-Wright 부등식을 사용하여 분산 추정의 집중 부등식을 개선하고, $\sqrt{\log(1/\delta)}$ 인수를 제거한다.
엄격한 준가우시안: 분산 매개변수가 실제 분산과 같은 엄격한 준가우시안 분포 범주를 식별하여 더 날카로운 경계를 제공한다.
탐색-자유 설계: UCB 클래스 탐색이 이 문제에서 불필요함을 증명하며, 최적해 자체가 각 팔을 Θ(T)번 표본화하도록 요구하기 때문이다.