哪怕轻微非平稳，满足型后悔仍随时间增长
On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization
- 提出基于后交互参考的新型Fano分析框架
- 非平稳段数L≥2时，最优后悔为Θ(L log T)
- 适用于关注策略鲁棒性的强化学习研究者
受决策中满足原则启发，本文研究非平稳K臂老虎机下的满足型后悔保证。在具有L个平稳段的一般可实现分段平稳设置中，当L≥2时，最优后悔为Θ(L log T)。这与L=1（即平稳情形）形成鲜明对比：此时在可实现条件下可达到与T无关的Θ(1)满足型后悔。换言之，即使存在极轻微的非平稳性，最优后悔也必须随时间增长。分析中的关键工具是一种新颖的基于Fano的框架，通过引入后交互参考构造专门适配非平稳老虎机。该框架严格扩展了经典Fano方法及近期针对平稳老虎机的交互式Fano技术。此外，我们还讨论了一种特殊情形，在此情形下常数级满足型后悔仍可实现。
原文摘要 · Abstract (English)
Motivated by the principle of satisficing in decision-making, we study satisficing regret guarantees for nonstationary $K$-armed bandits. We show that in the general realizable, piecewise-stationary setting with $L$ stationary segments, the optimal regret is $Θ(L\log T)$ as long as $L\geq 2$. This stands in sharp contrast to the case of $L=1$ (i.e., the stationary setting), where a $T$-independent $Θ(1)$ satisficing regret is achievable under realizability. In other words, the optimal regret has to scale with $T$ even if just a little nonstationarity presents. A key ingredient in our analysis is a novel Fano-based framework tailored to nonstationary bandits via a \emph{post-interaction reference} construction. This framework strictly extends the classical Fano method for passive estimation as well as recent interactive Fano techniques for stationary bandits. As a complement, we also discuss a special regime in which constant satisficing regret is again possible.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。