提出无需知道突变点数的极简探索机制，提升多臂老虎机应对环境突变的性能。
Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits
- 设计递减探索机制，不依赖突变点数量信息
- 在不增加计算复杂度前提下实现近最优后悔值
- 适用于现有检测算法，实测效果优于传统均匀探索
分段平稳多臂老虎机问题考虑奖励分布的突发变化，核心挑战在于探索以检测环境变化与传统利用之间的权衡。现有方法或需知晓突变点数 $M$，或计算开销极高。本文从极简视角重审该问题，提出一种新型通用探索机制——递减探索，无需 $M$ 的先验知识，可与现有基于变化检测的算法结合，实现近最优的后悔值增长。仿真结果表明，尽管对 $M$ 无感，该机制使现有算法的累积后悔显著低于传统均匀探索。
原文摘要 · Abstract (English)
The piecewise-stationary bandit problem is an important variant of the multi-armed bandit problem that further considers abrupt changes in the reward distributions. The main theme of the problem is the trade-off between exploration for detecting environment changes and exploitation of traditional bandit algorithms. While this problem has been extensively investigated, existing works either assume knowledge about the number of change points $M$ or require extremely high computational complexity. In this work, we revisit the piecewise-stationary bandit problem from a minimalist perspective. We propose a novel and generic exploration mechanism, called diminishing exploration, which eliminates the need for knowledge about $M$ and can be used in conjunction with an existing change detection-based algorithm to achieve near-optimal regret scaling. Simulation results show that despite oblivious of $M$, equipping existing algorithms with the proposed diminishing exploration generally achieves better empirical regret than the traditional uniform exploration.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。