提出滑动窗口贝叶斯算法,有效应对奖励随时间突变或平滑变化的强化学习场景。
Sliding-Window Thompson Sampling for Non-Stationary Settings
- 基于滑动窗口的贝叶斯推断,动态调整对各动作收益的估计
- 在突变与平滑变化环境下,达到当前最优的累计后悔上界
- 适用于需要实时适应环境变化的推荐系统、广告投放等场景
非平稳多臂老虎机(NS-MAB)建模了随时间演化的序列决策问题。本文填补了该领域空白,首次对基于滑动窗口的汤普森采样(TS)算法进行统一分析,涵盖使用不同先验的两种方法:Beta-SWTS 和 γ-SWGTS。我们推导出适用于任意非平稳环境(含伯努利或次高斯奖励)的统一后悔上界,引入新指标刻画学习复杂度。进一步将结果特化至最常见两类场景:突变型与平滑变化型环境,性能匹配现有最优水平。通过模拟实验验证算法有效性,并与当前先进方法对比,展现出优越的适应性与稳定性。
原文摘要 · Abstract (English)
Non-stationary multi-armed bandits (NS-MABs) model sequential decision-making problems in which the expected rewards of a set of actions, a.k.a.~arms, evolve over time. In this paper, we fill a gap in the literature by providing a novel analysis of Thompson sampling-inspired (TS) algorithms for NS-MABs that both corrects and generalizes existing work. Specifically, we study the cumulative frequentist regret of two algorithms based on sliding-window TS approaches with different priors, namely $\textit{Beta-SWTS}$ and $\textit{$γ$-SWGTS}$. We derive a unifying regret upper bound for these algorithms that applies to any arbitrary NS-MAB (with either Bernoulli or subgaussian rewards). Our result introduces new indices that capture the inherent sources of complexity in the learning problem. Then, we specialize our general result to two of the most common NS-MAB settings: the $\textit{abruptly changing}$ and the $\textit{smoothly changing}$ environments, showing that it matches state-of-the-art results. Finally, we evaluate the performance of the analyzed algorithms in simulated environments and compare them with state-of-the-art approaches for NS-MABs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。