An Information-Theoretic Analysis for Thompson Sampling with Many Actions

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 in corpus (14)

• Improved Optimistic Algorithms for Logistic Bandits
• Mirror Descent and the Information Ratio
• Reinforcement Learning, Bit by Bit
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• On the Performance of Thompson Sampling on Logistic Bandits
• A Bit Better? Quantifying Information for Bandit Learning
• Combining Offline Causal Inference and Online Bandit Learning for Data Driven Decision
• Information Directed Sampling for Sparse Linear Bandits
• Regret Bounds for Generalized Linear Bandits under Parameter Drift
• Deciding What to Learn: A Rate-Distortion Approach
• UCB-based Algorithms for Multinomial Logistic Regression Bandits
• The Value of Information When Deciding What to Learn
• Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification
• Metalearning Linear Bandits by Prior Update