Thompson sampling: an asymptotically optimal finite-time analysis
From MaRDI portal
Abstract: The question of the optimality of Thompson Sampling for solving the stochastic multi-armed bandit problem had been open since 1933. In this paper we answer it positively for the case of Bernoulli rewards by providing the first finite-time analysis that matches the asymptotic rate given in the Lai and Robbins lower bound for the cumulative regret. The proof is accompanied by a numerical comparison with other optimal policies, experiments that have been lacking in the literature until now for the Bernoulli case.
Recommendations
Cited in
(60)- Improving multi-armed bandit algorithms in online pricing settings
- Linear Thompson sampling revisited
- On Bayesian index policies for sequential resource allocation
- Dismemberment and design for controlling the replication variance of regret for the multi-armed bandit
- Ballooning multi-armed bandits
- Adaptive policies for perimeter surveillance problems
- Asymptotically optimal algorithms for budgeted multiple play bandits
- Multi-armed bandits based on a variant of simulated annealing
- Mechanisms with learning for stochastic multi-armed bandit problems
- Maximizing revenue for publishers using header bidding and ad exchange auctions
- An information-theoretic analysis of Thompson sampling
- On the Prior Sensitivity of Thompson Sampling
- Thompson Sampling for Bayesian Bandits with Resets
- Modification of improved upper confidence bounds for regulating exploration in Monte-Carlo tree search
- Infomax strategies for an optimal balance between exploration and exploitation
- Kullback-Leibler upper confidence bounds for optimal sequential allocation
- Practical Bayesian support vector regression for financial time series prediction and market condition change detection
- A Tutorial on Thompson Sampling
- Profile-based bandit with unknown profiles
- Learning the distribution with largest mean: two bandit frameworks
- Thompson sampling guided stochastic searching on the line for deceptive environments with applications to root-finding problems
- Near-optimal regret bounds for Thompson sampling
- Multi-armed bandit for species discovery: a Bayesian nonparametric approach
- Learning to optimize via information-directed sampling
- Learning unknown service rates in queues: a multiarmed bandit approach
- Regulating greed over time in multi-armed bandits
- Preference-based online learning with dueling bandits: a survey
- On multi-armed bandit designs for dose-finding trials
- Tsallis-INF: an optimal algorithm for stochastic and adversarial bandits
- scientific article; zbMATH DE number 7626733 (Why is no real title available?)
- Optimistic Gittins Indices
- Bandit Theory: Applications to Learning Healthcare Systems and Clinical Trials
- Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning
- Sliding-Window Thompson Sampling for Non-Stationary Settings
- Online Network Revenue Management Using Thompson Sampling
- Simple Bayesian algorithms for best-arm identification
- Learning to optimize via posterior sampling
- Satisficing in Time-Sensitive Bandit Learning
- Robust sequential design for piecewise-stationary multi-armed bandit problem in the presence of outliers
- Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems
- Online learning of network bottlenecks via minimax paths
- Multi-armed bandit problem with online clustering as side information
- Variable Selection Via Thompson Sampling
- Online learning of energy consumption for navigation of electric vehicles
- Response-adaptive randomization in clinical trials: from myths to practical considerations
- Semi-parametric contextual bandits with graph-Laplacian regularization
- Thompson sampling for networked control over unknown channels
- Multi-armed bandit experiments in the online service economy
- Deep spatial Q-learning for infectious disease control
- TSPINN: Thompson sampling-based adaptive training for physics-informed neural networks
- On the limitations and possibilities of Nash regret minimization in zero-sum matrix games under noisy feedback
- Simple fixes that accommodate switching costs in multi-armed bandits
- Output-weighted sampling for multi-armed bandits with extreme payoffs
- CRIMED: lower and upper bounds on regret for bandits with unbounded stochastic corruption
- Follow-the-perturbed-leader achieves best-of-both-worlds for bandit problems
- Solving Bernoulli rank-one bandits with unimodal Thompson sampling
- Bandit algorithms based on Thompson sampling for bounded reward distributions
- Thompson sampling for adversarial bit prediction
- Optimal learning policies for differential privacy in multi-armed bandits
- Efficient multiobjective optimization employing Gaussian processes, spectral sampling and a genetic algorithm
This page was built for publication: Thompson sampling: an asymptotically optimal finite-time analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3164821)
