将汤普森采样重看为在线优化，揭示其探索与利用的平衡机制。
A Broader View of Thompson Sampling
- 把汤普森采样视为在线优化算法，用不确定度正则化贪婪性。
- 提出不变时间的损失定义，导出平稳贝尔曼最优策略。
- 为改进策略提供理论依据，适合强化学习研究者阅读。
汤普森采样是应用最广泛、研究最深入的强化学习算法之一，具有结构简单、后悔值低和理论保证稳固等优点。然而，与大多数其他强化学习算法不同，其后验采样如何实现探索与利用的恰当平衡，至今仍是一个未解之谜。本文提出，理解该问题的核心在于将汤普森采样重新诠释为一种在线优化算法。为此，我们引入一种时间不变的损失概念，从而导出一个平稳的带约束问题及对应的平稳贝尔曼最优策略。进一步证明，汤普森采样可被表达为一种在线优化形式，其结构模仿了该最优策略：贪婪行为受到剩余不确定性的正则化。这一新视角不仅深化了对汤普森采样动态行为的理解，还为基于贝尔曼最优基准的策略改进提供了原则性方法。
原文摘要 · Abstract (English)
Thompson Sampling is one of the most widely used and studied bandit algorithms, known for its simple structure, low regret performance, and solid theoretical guarantees. Yet, in stark contrast to most other families of bandit algorithms, the exact mechanism through which posterior sampling (as introduced by Thompson) is able to "properly" balance exploration and exploitation, remains a mystery. In this paper, we show that the core insight to address this question stems from recasting Thompson Sampling as an online optimization algorithm. To distill this, we introduce a suitable time invariant notion of regret that leads to a stationarized bandit problem, and a stationary Bellman-optimal policy. We then show that Thompson Sampling admits an online optimization form that mimics the structure of the aforementioned Bellman-optimal policy, where "greediness" is regularized by a measure of residual uncertainty. This new lens of online optimization allows both a better understanding of Thompson Sampling dynamics, as well as a principled manner for policy improvement that mimics the Bellman-optimal benchmark.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。