Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems

arXiv:2403.03361v1 Announce Type: cross
Abstract: This paper studies the Bayesian regret of a variant of the Thompson-Sampling algorithm for bandit problems. It builds upon the information-theoretic framework of [Russo and Van Roy, 2015] and, more specifically, on the rate-distortion analysis from [Dong and Van Roy, 2020], where they proved a bound with regret rate of $O(d\sqrt{T \log(T)})$ for the $d$-dimensional linear bandit setting. We focus on bandit problems with a metric action space and, using a chaining argument, we establish …

abstract algorithm analysis arxiv bayesian cs.lg framework information linear paper rate sampling stat.ml studies the information type van