Correlated Multiarmed Bandit Problem: Bayesian Algorithms and Regret Analysis
This work addresses the correlated multiarmed bandit problem for sequential decision-making applications, presenting incremental improvements through Bayesian analysis.
The paper tackled the correlated multiarmed bandit problem by analyzing Bayesian algorithms, specifically the UCL algorithm and a new correlated UCL algorithm, under multivariate Gaussian rewards, and showed how priors and correlation structure can improve performance, with rigorous characterization of accuracy, confidence, and correlation scale.
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.