Contextual Thompson Sampling via Generation of Missing Data
Kelly W. Zhang, Tiffany Tianhui Cai, Hongseok Namkoong, Daniel Russo
我们引入了Thompson采样(TS)上下文匪徒算法的框架,其中算法量化不确定性和决策的能力取决于离线学习的生成模型的质量。 我们的算法没有将环境中的不确定性视为由不可观察的潜在参数引起的,而是将不确定性视为缺失,但可能可观察到的结果(包括未来和反事实结果)。 如果这些结果都被观察到,人们只需使用完整数据集上的“神谕”策略来做出决定。 受这种概念化的启发,在每个决策时间,我们的算法使用生成模型来概率推断缺失的结果,使用被计算的完整数据集来拟合策略,并使用该策略来选择下一个操作。 我们正式表明,这种算法是TS的生成式公式,并建立了一个最先进的后悔绑定。 值得注意的是,我们的遗憾约束仅通过其离线预测损失的质量依赖于生成模型,并适用于任何拟合“神谕”策略的方法。
We introduce a framework for Thompson sampling (TS) contextual bandit algorithms, in which the algorithm's ability to quantify uncertainty and make decisions depends on the quality of a generative model that is learned offline. Instead of viewing uncertainty in the environment as arising from unobservable latent parameters, our algorithm treats uncertainty as stemming from missing, but potentially observable outcomes (including both future and counterfactual outcomes). If these outcomes were all...
