Correlated Multiarmed Bandit Problem: Bayesian Algorithms and Regret\n Analysis

2015/07/04 by Vaibhav Srivastava, Srivastava, Vaibhav, Paul Reverdy +3
Computer Science · Decision Sciences · #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

paper · pdf · doi:10.48550/arxiv.1507.01160

openalex publication_date 2015/07/04 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28

Abstract

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

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