평균 이동이 존재하는 밴딧에서의 최적 팔 식별
Best Arm Identification for Bandits with Shifting Means
한국어 초록
본 논문에서는 '평균 이동(Shifting Means)'이라고 명명한 새로운 형태의 적대적 섭동(adversarial perturbation)이 존재하는 확률적 환경(environment)에서의 최적 팔 식별(best arm identification) 문제를 연구합니다. 고전적으로는 $K$개 팔의 평균 보상이 시간에 따라 안정적이었던 반면, 평균 이동 환경에서는 평균 보상 간의 간격 $\boldsymbolΔ$만 안정적으로 유지되고 이들의 공통 이동(shift)은 매 라운드마다 적대적으로 결정될 수 있습니다. 학습자의 목표는 표본 복잡도(sample complexity)를 최소화하면서 높은 확률로 최적 팔을 식별하는 것입니다(고정 신뢰도 설정). 이러한 이동을 다루기 위해서는 새로운 도구가 필요합니다. 널리 사용되는 Track-and-Stop을 포함하여 일반화 우도비 검정(GLRT, Generalized Likelihood Ratio Test) 정지 규칙을 사용하는 알고리즘들이 시간에 따라 변하는 이동 하에서 실패함을 보입니다. 대신, 우리는 '평균 이동을 위한 중요도 가중치($\mathsf{ISM}$, Importance Weights for Shifting Means)'를 제안합니다. 평균이 $U$로 유계이고 보상이 $σ^2$-서브 가우시안(sub-Gaussian)이라는 가정 하에, $\mathsf{ISM}$이 $δ$-정확함을 증명하고 $K (σ^2 + U^2) Δ_{\min}^{-2} \ln \frac{1}δ$ 차수의 표본 복잡도 상한을 가짐을 보입니다. 또한 상수 인자 범위 내에서 일치하는 최악 조건 하한(worst-case lower bound)을 제시하고 결과를 실험적으로 평가합니다.
원문 초록
We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the $K$ arms are stable in time, in Shifting Means only the gaps $\boldsymbolΔ$ between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means ($\mathsf{ISM}$). Assuming means bounded by $U$ and $σ^2$-sub-Gaussian rewards, we show $\mathsf{ISM}$ to be $δ$-correct and to enjoy a sample complexity bound of order $K (σ^2 + U^2) Δ_{\min}^{-2} \ln \frac{1}δ$. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
Accepted at NeurIPS 2026