Asymptotically Optimal Information-Directed Sampling
arXiv:2011.05944
Abstract
We introduce a simple and efficient algorithm for stochastic linear bandits with finitely many actions that is asymptotically optimal and (nearly) worst-case optimal in finite time. The approach is based on the frequentist information-directed sampling (IDS) framework, with a surrogate for the information gain that is informed by the optimization problem that defines the asymptotic lower bound. Our analysis sheds light on how IDS balances the trade-off between regret and information and uncovers a surprising connection between the recently proposed primal-dual methods and the IDS algorithm. We demonstrate empirically that IDS is competitive with UCB in finite-time, and can be significantly better in the asymptotic regime.
arXiv commentAccepted at COLT 2021
References in corpus (7)
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Online Learning: A Modern Introduction Using Convex Optimization
- Best-Arm Identification in Linear Bandits
- Information Directed Sampling and Bandits with Heteroscedastic Noise
- Information Directed Sampling for Linear Partial Monitoring
- Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality
- An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits
Cited by in corpus (8)
- An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
- Reinforcement Learning, Bit by Bit
- A Bit Better? Quantifying Information for Bandit Learning
- Risk-aware linear bandits with convex loss
- Experimental Design for Regret Minimization in Linear Bandits
- Bias-Robust Bayesian Optimization via Dueling Bandits
- Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification
- The Value of Information When Deciding What to Learn