通过信息松弛改进预算多臂赌博机中的汤普森采样
内容提要
本文探讨了Thompson Sampling算法在序贯决策中的应用，尤其是在多臂赌博机问题中的表现。该算法通过贝叶斯方法实现了对数级别的预期遗憾，并在不同环境下进行了多种改进和扩展，展示了其在探索与开发权衡中的有效性和鲁棒性。
延伸解读
理论保证的演进
文章梳理了Thompson Sampling理论保证的逐步完善。2011年首次证明多臂赌博机中可实现对数级预期遗憾，2012年将理论保证扩展到线性收益的上下文老虎机，2013年进一步量化先验分布对遗憾界的影响。这些工作逐步填补了该算法理论认识有限的空白，为后续应用提供了基础。
面向实际约束的扩展
针对现实场景中的预算限制和非平稳环境，文章介绍了相应的Thompson Sampling变体。2015年提出的预算限制MAB算法在伯努利臂下实现对数复杂度遗憾界；2017年针对非平稳环境，通过降低先前观测效果并优化功利值来适应变化。这些扩展增强了算法在动态和资源受限场景下的实用性。
可扩展性与计算效率的改进
为应对大规模bandit问题，2014年提出的bootstrap Thompson sampling用bootstrap分布替换后验分布，提高了可扩展性和对误分布的鲁棒性。2021年基于多级Thompson抽样的方案利用聚类结构显著改善遗憾并降低计算成本。这些改进使算法更适用于高维和计算资源有限的环境。
遗憾界实用化的最新进展
2024年的研究针对有界奖励随机赌博算法，解决了高斯先验下遗憾界在T≤288e^64时虚无的问题，导出了更实用的界限，将主要项系数从288e^64缩小到1270。同时提出参数化算法TS-MA-α和TS-TD-α，通过α控制效用与计算权衡，实现O(Kln^(α+1)(T)/Δ)的遗憾界，提升了理论保证的实用性。
Q&A
Thompson Sampling算法的主要优点是什么？
Thompson Sampling算法通过贝叶斯方法实现了对数级别的预期遗憾，表现接近最优，展现了理想特性。
如何提高Thompson Sampling在大规模问题中的可扩展性？
通过引入bootstrap分布替换后验分布，bootstrap Thompson sampling方法提高了在大规模bandit问题中的可扩展性和鲁棒性。
Thompson Sampling算法在预算限制的多臂赌博问题中表现如何？
该算法在伯努利臂下实现了对数复杂度的遗憾界，证明了其在预算限制下的有效性。
在非平稳环境中，Thompson Sampling的变体如何优化算法？
提出的变体通过增加贝叶斯采样的功利值，优化了算法的功利值，并进行了广泛的实证分析。
多级Thompson抽样方案的优势是什么？
基于多级Thompson抽样方案的算法显著改善了遗憾并降低了计算成本。
Thompson Sampling算法如何平衡探索与利用的权衡？
提出的在线顺序决策支持方法利用Thompson抽样来平衡探索与利用的权衡，并在现实世界的数据集上表现有效。
