An Information-Theoretic Analysis for Thompson Sampling with Many Actions

2018/05/30 by Dong, Shi, Benjamin Van Roy, Van Roy, Benjamin · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Decision-Making and Behavioral Economics #FOS: Computer and information sciences #Gaussian Processes and Bayesian Inference #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.1805.11845

openalex publication_date 2018/05/30 · openalex created_date 2018/06/13 · openalex updated_date 2026/07/28

Abstract

Information-theoretic Bayesian regret bounds of Russo and Van Roy capture the dependence of regret on prior uncertainty. However, this dependence is through entropy, which can become arbitrarily large as the number of actions increases. We establish new bounds that depend instead on a notion of rate-distortion. Among other things, this allows us to recover through information-theoretic arguments a near-optimal bound for the linear bandit. We also offer a bound for the logistic bandit that dramatically improves on the best previously available, though this bound depends on an information-theoretic statistic that we have only been able to quantify via computation.

Cited by

• Order Optimal Regret Bounds for Sharpe Ratio Optimization under Thompson Sampling
• Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts

Related

• Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits
• First-Order Bayesian Regret Analysis of Thompson Sampling
• An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces
• Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems
• An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandits