Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems
<|reference_start|>Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems: 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 new bounds that depend on the metric entropy of the action space for a variant of Thompson-Sampling.   Under suitable continuity assumption of the rewards, our bound offers a tight rate of $O(d\sqrt{T})$ for $d$-dimensional linear bandit problems.<|reference_end|>
@article{gouverneur2024chained,
    title={Chained Information-Theoretic bounds and Tight Regret Rate for Linear
  Bandit Problems},
    author={Amaury Gouverneur, Borja Rodr'iguez-G'alvez, Tobias J. Oechtering,
  Mikael Skoglund},
    journal={arXiv preprint arXiv:2403.03361},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.03361},
    primaryClass={stat.ML cs.LG}
}