Diffusion Approximations for Thompson Sampling in the Small Gap Regime

Abstract

We study the process-level dynamics of Thompson sampling and related sampling-based bandit algorithms in the ``small gap'' regime, where the gaps between the arm means are of order $\sqrt{\gamma }$ or smaller and the time horizon is of order $1/\gamma$, with $\gamma \downarrow 0$. In this regime, as $\gamma \downarrow 0$, we show that the process-level dynamics of such algorithms converge weakly to the solutions to certain stochastic differential equations and stochastic ordinary differential equations. Our weak convergence theory is developed using the Continuous Mapping Theorem, which provides a direct and modular theoretical approach that can be adapted to analyze a variety of sampling-based bandit algorithms and handle weakly dependent reward processes. A central finding is an algorithmic invariance principle: in the small gap regime, the limit dynamics of a broad class of sampling-based algorithms -- including Thompson sampling with general single-parameter exponential family likelihoods, as well as non-parametric bandit algorithms based on bootstrap re-sampling -- all coincide with those of Thompson sampling with Gaussian likelihoods. Moreover, in the small gap regime, the regret performance of these algorithms is generally insensitive to model mis-specification, changing continuously with increasing degrees of mis-specification.

References in corpus (14)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Batched bandit problems
• Proofs of the martingale FCLT
• Bootstrapped Thompson Sampling and Deep Exploration
• Online Learning with Switching Costs and Other Adaptive Adversaries
• Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
• Batched Multi-armed Bandits Problem
• Thompson sampling with the online bootstrap
• New Insights into Bootstrapping for Bandits
• A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms
• Sub-sampling for Efficient Non-Parametric Bandit Exploration
• Weak Signal Asymptotics for Sequentially Randomized Experiments

Cited by in corpus (5)

• A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms
• Weak Signal Asymptotics for Sequentially Randomized Experiments
• The Fragility of Optimized Bandit Algorithms
• Understanding the stochastic dynamics of sequential decision-making processes: A path-integral analysis of multi-armed bandits
• Diffusion Approximations for a Class of Sequential Testing Problems