提出模块化方法，让带变化检测的老虎机算法更高效可靠。
Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approach
- 将变化检测与老虎机算法解耦，实现可组合设计。
- 在子高斯奖励下，证明了新算法达到最优渐近性能。
- 适合需要动态适应环境的在线决策场景。
传统多臂老虎机（MAB）算法假设环境静态，但现实中常为非平稳。本文研究分段平稳多臂老虎机（PS-MAB），其中部分臂的回报分布在某些变化点发生改变，变化点之间保持平稳。针对此类环境的渐近分析，现有方法依赖变化检测技术。本文旨在模块化设计与分析这类检测增强型老虎机（DAB）算法。首先，给出改进的性能下界；其次，识别出使模块化可行的静止型老虎机算法与变化检测器所需条件。在子高斯奖励假设和变化点间距足够条件下，证明了分析可模块化，能统一推导不同组合下的后悔上界。基于此，设计出新的、阶次最优的模块化DAB算法。实验验证了其在后悔性能和检测能力上的实际有效性，优于多种基准方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。