Report
Change Detection-Based Procedures for Piecewise Stationary MABs: A Modular Approach
| العنوان: | Change Detection-Based Procedures for Piecewise Stationary MABs: A Modular Approach |
|---|---|
| المؤلفون: | Huang, Yu-Han, Gerogiannis, Argyrios, Bose, Subhonmesh, Veeravalli, Venugopal V. |
| سنة النشر: | 2025 |
| المجموعة: | Computer Science Statistics |
| مصطلحات موضوعية: | Computer Science - Artificial Intelligence, Computer Science - Machine Learning, Electrical Engineering and Systems Science - Systems and Control, Statistics - Machine Learning |
| الوصف: | 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 nonstationary. 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 (CD) have been previously proposed. Our goal is to modularize the design and analysis of such CD-based Bandit (CDB) procedures. To this end, we identify the requirements for stationary bandit algorithms and change detectors in a CDB 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 CDB procedures can indeed be modularized, so that 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 CDB procedures that are order-optimal. We compare the performance of our modular CDB procedures with various other methods in simulations. Comment: 34 pages, 2 figures, 1 table, submitted to JMLR |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2501.01291 |
| رقم الانضمام: | edsarx.2501.01291 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |