arXiv:2604.10177cs.ITcs.LG2026-04

提出模块化框架,让多臂赌博机自动适应奖励变化。

A Modularized Framework for Piecewise-Stationary Restless Bandits

  • 分段设计:用检测+衰减探索机制应对未知变化点。
  • 理论证明:在T期内后悔值逼近最优,受马尔可夫混和时间影响。
  • 适合研究者:想提升自适应强化学习性能的人可直接套用。

我们研究分段平稳的非平稳多臂赌博机(PS-RMAB)问题,其中每个臂以马尔可夫链演化,但均值奖励在未知区间内发生变化。为缓解探索与检测延迟之间的权衡,提出一个模块化框架,将任意RMAB基础算法与变化检测及新型衰减探索机制结合。该设计支持现有求解器与检测器的灵活插拔,无需预先知道变化次数即可高效适应均值突变。为评估性能,引入一种细化的后悔度量,衡量因探索与检测导致的额外后悔,基准为在真实变化点重启基础算法的虚拟先知。理论上证明后悔上界为$ ilde{O}( oot{2}{LMKT})$,其中$L$为所有臂与区间的最大混和时间,$M$为段数,$K$为臂数,$T$为总时间跨度。仿真表明,本框架的后悔接近段先知水平,且持续优于未考虑环境变化的基础求解器。

原文摘要 · Abstract (English)

We study the piecewise-stationary restless multi-armed bandit (PS-RMAB) problem, where each arm evolves as a Markov chain but \emph{mean rewards may change across unknown segments}. To address the resulting exploration--detection delay trade-off, we propose a modular framework that integrates arbitrary RMAB base algorithms with change detection and a novel diminishing exploration mechanism. This design enables flexible plug-and-play use of existing solvers and detectors, while efficiently adapting to mean changes without prior knowledge of their number. To evaluate performance, we introduce a refined regret notion that measures the \emph{excess regret due to exploration and detection}, benchmarked against an oracle that restarts the base algorithm at the true change points. Under this metric, we prove a regret bound of $\tilde{O}(\sqrt{LMKT})$, where $L$ denotes the maximum mixing time of the Markov chains across all arms and segments, $M$ the number of segments, $K$ the number of arms, and $T$ the horizon. Simulations confirm that our framework achieves regret close to that of the segment oracle and consistently outperforms base solvers that do not incorporate any mechanism to handle environmental changes.

强化学习多臂赌博机自适应后悔分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。