Best-Arm Identification in Correlated Multi-Armed Bandits

In this paper we consider the problem of best-arm identification in multi-armed bandits in the fixed confidence setting, where the goal is to identify, with probability <inline-formula> <tex-math notation="LaTeX">$1-\delta $ </tex-math></inline-formula> for some <inline-formula> <tex-math notation="LaTeX">$\delta >0$ </tex-math></inline-formula>, the arm with the highest mean reward in minimum possible samples from the set of arms <inline-formula> <tex-math notation="LaTeX">$\mathcal {K}$ </tex-math></inline-formula>. Most existing best-arm identification algorithms and analyses operate under the assumption that the rewards corresponding to different arms are independent of each other. We propose a novel correlated bandit framework that captures domain knowledge about correlation between arms in the form of upper bounds on expected conditional reward of an arm, given a reward realization from another arm. Our proposed algorithm C-LUCB, which generalizes the LUCB algorithm utilizes this partial knowledge of correlations to sharply reduce the sample complexity of best-arm identification. More interestingly, we show that the total samples obtained by C-LUCB are of the form <inline-formula> <tex-math notation="LaTeX">$\mathrm {O}\left({\sum _{k \in \mathcal {C}} \log \left({\frac {1}{\delta }}\right)}\right)$ </tex-math></inline-formula> as opposed to the typical <inline-formula> <tex-math notation="LaTeX">$\mathrm {O}\left({\sum _{k \in \mathcal {K}} \log \left({\frac {1}{\delta }}\right)}\right)$ </tex-math></inline-formula> samples required in the independent reward setting. The improvement comes, as the <inline-formula> <tex-math notation="LaTeX">$\mathrm {O}(\log (1/\delta))$ </tex-math></inline-formula> term is summed only for the set of <italic>competitive</italic> arms <inline-formula> <tex-math notation="LaTeX">$\mathcal {C}$ </tex-math></inline-formula>, which is a subset of the original set of arms <inline-formula> <tex-math notation="LaTeX">$\mathcal {K}$ </tex-math></inline-formula>. The size of the set <inline-formula> <tex-math notation="LaTeX">$\mathcal {C}$ </tex-math></inline-formula>, depending on the problem setting, can be as small as 2, and hence using C-LUCB in the correlated bandits setting can lead to significant performance improvements. Our theoretical findings are supported by experiments on the Movielens and Goodreads recommendation datasets.

Paper

Similar papers

© 2026 NYSGPT2525 LLC