dirkvanderhoeven.com

이 이메일 도메인이 관측된 논문 1건

arXiv:2610.10488v1stat.ML

평균 이동이 존재하는 밴딧에서의 최적 팔 식별

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)을 제시하고 결과를 실험적으로 평가합니다.