구간별 정적 MAB를 위한 탐지 증강 밴딧 절차: 모듈식 접근법

Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approach

기존의 다중 팔 밴딧(MAB) 알고리즘은 팔(arm)과 연관된 보상 분포가 시간에 따라 변하지 않는 정적 환경을 위해 설계되었다. 그러나 많은 응용 분야에서 환경은 비정적인 것으로 모델링하는 것이 더 정확하다. 본 연구에서는 팔의 부분 집합과 연관된 보상 분포가 특정 변경점(change-points)에서 변하고 변경점 사이에서는 정적으로 유지되는 구간별 정적 MAB(PS-MAB) 환경을 조사한다. 우리의 초점은 PS-MAB의 점근적 분석에 있으며, 이를 위해 변경 탐지 기반의 실용적인 알고리즘들이 이전에 제안된 바 있다. 우리의 목표는 이러한 탐지 증강 밴딧(DAB) 절차의 설계 및 분석을 모듈화하는 것이다. 이를 위해, 먼저 PS-MAB에 대한 새롭고 개선된 성능 하한(lower bounds)을 제공한다. 그 후, 모듈화에 필요한 DAB 절차 내의 정적 밴딧 알고리즘과 변경 탐지기에 대한 요구 사항을 식별한다. 우리는 보상이 서브-가우시안(sub-Gaussian) 분포를 따른다고 가정한다. 이 가정과 변경점 분리에 대한 조건 하에서, 우리는 DAB 절차의 분석이 실제로 모듈화될 수 있음을 보여주며, 이를 통해 다양한 변경 탐지기와 밴딧 알고리즘의 조합에 대해 통일된 방식으로 후회(regret) 한계를 얻을 수 있음을 보인다. 이러한 분석을 통해, 우리는 오더-최적(order-optimal)인 새로운 모듈식 DAB 절차를 개발한다. 마지막으로, 실험을 통해 다른 방법들과 후회 성능을 비교하고 탐지 능력을 조사함으로써 모듈식 DAB 접근법의 실질적인 유효성을 입증한다.

Conventional Multi-Armed Bandit (MAB) algorithms are designed for stationary environments, where the reward distributions associated with the arms do not change with time. In many applications, however, the environment is more accurately modeled as being non-stationary. In this work, piecewise stationary MAB (PS-MAB) environments are investigated, in which the reward distributions associated with a subset of the arms change at some change-points and remain stationary between change-points. Our focus is on the asymptotic analysis of PS-MABs, for which practical algorithms based on change detection have been previously proposed. Our goal is to modularize the design and analysis of such Detection Augmented Bandit (DAB) procedures. To this end, we first provide novel, improved performance lower bounds for PS-MABs. Then, we identify the requirements for stationary bandit algorithms and change detectors in a DAB procedure that are needed for the modularization. We assume that the rewards are sub-Gaussian. Under this assumption and a condition on the separation of the change-points, we show that the analysis of DAB procedures can indeed be modularized, so that the regret bounds can be obtained in a unified manner for various combinations of change detectors and bandit algorithms. Through this analysis, we develop new modular DAB procedures that are order-optimal. Finally, we showcase the practical effectiveness of our modular DAB approach in our experiments, studying its regret performance compared to other methods and investigating its detection capabilities.