Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits

贝叶斯赌博算法在近似贝叶斯推断方面已被广泛应用于实际应用中。然而，文献中对其理论基础的探讨较少，尤其是对于情境赌博问题。为了填补这一空白，我们提出了一个通用的理论框架，以分析在近似推断存在的情况下随机线性赌博问题，并对两种贝叶斯赌博算法——线性汤普森采样（LinTS）和贝叶斯上限置信度的扩展，即线性贝叶斯上限置信度（LinBUCB）进行后悔分析。我们证明，当应用于近似推断时，LinTS和LinBUCB均能保持其原有的后悔上限率，但代价是更大的常数项。这些结果适用于一般的贝叶斯推断方法，在假设由两个不同的α-散度测量的推断误差被限制的情况下成立。此外，通过引入新的“表现良好的分布”定义，我们展示了LinBUCB将LinTS的后悔率从$\tilde{O}(d^{3/2}\sqrt{T})$改进到了$\tilde{O}(d\sqrt{T})$，达到了极小化最优率的水平。据我们所知，这项工作为具有有限近似推断误差的随机线性赌博设置提供了第一篇后悔界。

论文试图在近似贝叶斯推断下分析随机线性Bandit问题的后悔率，并验证两种贝叶斯Bandit算法的理论正确性。

论文提出了一个通用的理论框架，以分析近似推断下的随机线性Bandit问题，并在此基础上对两种贝叶斯Bandit算法进行了后悔率分析。

论文提出的理论框架适用于一般的贝叶斯推断方法，并且假设推断误差通过两种不同的α-散度有界。此外，论文还提出了一个新的“well-behaved”分布定义，用于改进LinTS算法的后悔率。实验结果表明，LinBUCB算法的后悔率可以达到minimax最优率。

最近的相关研究包括：'A Contextual-Bandit Approach to Personalized News Article Recommendation'，'Bayesian Bandits with Expanding Horizon'等。