효율적인 실험을 위한 밴딧 (Bandits): 대조군, 선호도 및 컨텍스트 드리프트에 대한 적응

우리는 학습자가 각기 다른 개인화된 선호도 벡터 (preference vector)를 가진 사용자 그룹에게 추천을 제공해야 하며, 시간이 지남에 따라 드리프트 (drift)가 발생하는 컨텍스트 분포 (context distributions)가 존재하는 상황에서의 선형 컨텍스츄얼 확률적 멀티 암드 밴딧 (linear contextual stochastic multi-armed bandits) 변형 모델을 고려합니다. 실무자 친화적인 가정 하에, 우리는 이 설정을 평균은 정적(stationary)이지만 이분산성(heteroskedastic) 및 비정적(non-stationary) 노이즈를 갖는 선형 밴딧 (linear bandit) 문제로 축소합니다. 나아가 우리는 학습자가 매 결정 단계마다 각 결정의 평균 보상이 베이스라인 전략 $\boldsymbol\pi_0$의 보상을 초과하도록 보장해야 하는 경우를 연구합니다. 우리는 MED 전략의 선형 버전에 영감을 얻고, 비정적 이분산 노이즈를 처리할 수 있도록 정교하게 조정된 알고리즘인 Dri-MED를 소개합니다. 우리는 인스턴스 의존적 후회 (instance-dependent regret)가 $\tilde{\mathcal{O}}\left(\frac{\kappa}{\tilde{\Delta}}d^2(\log(T)\right)$로 확장됨을 보여주며, 여기서 $\tilde{\Delta}$는 정책 $\pi_0$에 따른 제약 조건 인지 하의 하위 최적성 격차 (constraint-aware sub-optimality gap)이며, $\kappa$는 이분산 회귀 (heteroskedastic regression)를 사용하여 정교하게 처리하는 분산 인지 곱셈 항 (variance-aware multiplicative term)입니다. 또한 Dri-MED가 $\tilde{\mathcal{O}}(d)$의 기대 제약 조건 위반 (expected constraint violations)을 누린다는 것을 보여줍니다. 우리의 수치적 결과는 Dri-MED가 드리프트와 선호도 구조를 무시하는 보수적인 베이스라인 모델들보다 성능이 현저히 뛰어남을 시사합니다.