Efficient and Adaptive Posterior Sampling Algorithms for Bandits

arXiv:2405.01010v1 Announce Type: new
Abstract: We study Thompson Sampling-based algorithms for stochastic bandits with bounded rewards. As the existing problem-dependent regret bound for Thompson Sampling with Gaussian priors [Agrawal and Goyal, 2017] is vacuous when $T \le 288 e^{64}$, we derive a more practical bound that tightens the coefficient of the leading term %from $288 e^{64}$ to $1270$. Additionally, motivated by large-scale real-world applications that require scalability, adaptive computational resource allocation, and a balance in utility and computation, we propose …

abstract algorithms arxiv cs.lg posterior practical sampling stat.ml stochastic study type