Correlated Multiarmed Bandit Problem: Bayesian Algorithms and Regret Analysis

2015/07/04 by Vaibhav Srivastava, Srivastava, Vaibhav, Paul Reverdy +3
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Optimization and Search Problems #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1507.01160

openalex publication_date 2015/07/04 · arxiv created 2015/07/07 · arxiv updated 2015/07/09 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28

Abstract

We consider the correlated multiarmed bandit (MAB) problem in which the rewards associated with each arm are modeled by a multivariate Gaussian random variable, and we investigate the influence of the assumptions in the Bayesian prior on the performance of the upper credible limit (UCL) algorithm and a new correlated UCL algorithm. We rigorously characterize the influence of accuracy, confidence, and correlation scale in the prior on the decision-making performance of the algorithms. Our results show how priors and correlation structure can be leveraged to improve performance.

Citations

• On the Prior Sensitivity of Thompson Sampling
• Humans use directed and random exploration to solve the explore–exploit dilemma.

Related

• Correlated Multi-armed Bandits with a Latent Random Source
• Adaptive KL-UCB based Bandit Algorithms for Markovian and i.i.d. Settings
• Stochastic Multi-Armed Bandits with Control Variates
• A General Framework for Bandit Problems Beyond Cumulative Objectives
• Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards