Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning
Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning
复制标题
用于上下文强盗和强化学习的感觉良好的汤普森采样
DOI：
--
复制
发表时间：
2021
影响因子：
3.6
通讯作者：
Tong Zhang
中科院分区：
文献类型：
--
作者：
Tong Zhang
汤普森采样由于其建模能力的灵活性而被广泛用于上下文老虎机问题。然而，在频率论背景下仍然缺乏此类方法的一般理论。在本文中，我们提出了汤普森采样的理论分析，重点关注频率后悔界限。在这种情况下，我们表明标准汤普森采样在探索新行动方面不够积极，导致在某些悲观情况下出现次优。为了解决这个问题，提出了一种称为“感觉良好的汤普森采样”的简单修改，它比标准汤普森采样更积极地支持高奖励模型。我们证明，该理论框架可用于推导标准汤普森采样的贝叶斯后悔界限，以及感觉良好汤普森采样的频繁后悔界限。结果表明，在这两种情况下，我们都可以将老虎后悔问题减少到在线最小二乘回归估计。对于频率分析，可以使用已被充分研究的在线聚合技术直接获得在线最小二乘回归界。所得到的老虎机后悔界限与有限动作情况下的极小极大下界相匹配。此外，该分析可以推广到处理一类线性可嵌入上下文强盗问题（它概括了流行的线性上下文强盗模型）。获得的结果再次与极小极大下界匹配。最后我们说明该分析可以扩展到处理一些 MDP 问题。
Thompson Sampling has been widely used for contextual bandit problems due to the flexibility of its modeling power. However, a general theory for this class of methods in the frequentist setting is still lacking. In this paper, we present a theoretical analysis of Thompson Sampling, with a focus on frequentist regret bounds. In this setting, we show that the standard Thompson Sampling is not aggressive enough in exploring new actions, leading to suboptimality in some pessimistic situations. A simple modification called Feel-Good Thompson Sampling, which favors high reward models more aggressively than the standard Thompson Sampling, is proposed to remedy this problem. We show that the theoretical framework can be used to derive Bayesian regret bounds for standard Thompson Sampling, and frequentist regret bounds for Feel-Good Thompson Sampling. It is shown that in both cases, we can reduce the bandit regret problem to online least squares regression estimation. For the frequentist analysis, the online least squares regression bound can be directly obtained using online aggregation techniques which have been well studied. The resulting bandit regret bound matches the minimax lower bound in the finite action case. Moreover, the analysis can be generalized to handle a class of linearly embeddable contextual bandit problems (which generalizes the popular linear contextual bandit model). The obtained result again matches the minimax lower bound. Finally we illustrate that the analysis can be extended to handle some MDP problems.