Abstract
Multi-armed bandit models are widely studied sequential decision-making problems that exemplify the exploration-exploitation trade-off. We study a novel correlated multi-armed bandit model where the rewards obtained from the arms are functions of a common latent random variable. We propose and analyze the performance of the C-UCB algorithm that leverages the correlations between arms to reduce the cumulative regret. Unlike the standard UCB algorithm that pulls all sub-optimal arms $O(\log T)$ times, the C-UCB algorithm takes only $O(1)$ times to identify that some arms, which we refer to as non-competitive arms, are sub-optimal. Thus, we effectively reduce a $K$-armed bandit problem to a $(C + 1)$-armed bandit problem with $C < K$ denoting the number of competitive arms. A key consequence is that when $C = 0$, our algorithm achieves a constant (i.e., $O(1)$) regret. Establishing lower bounds for the regret, we show that the C-UCB algorithm is order-wise optimal and demonstrate its superiority against other algorithms via numerical simulations.
Introduction: Exploiting the "Hidden Link"
In the classic Multi-Armed Bandit (MAB) framework, a decision-maker must choose between $K$ different actions (arms) to maximize a cumulative reward. The core challenge is the exploration-exploitation trade-off: deciding whether to stick with the best arm found so far or explore others. Traditional models, such as the UCB1 algorithm, assume that rewards from different arms are independent. This assumption forces algorithms to pull every sub-optimal arm at least $O(\log T)$ times to ensure they are not the best.
However, in many real-world scenarios, rewards are correlated. For example, different advertisements shown to the same demographic (a latent variable) likely have linked performance. This paper introduces a framework where rewards are functions of a common latent random source, allowing for significantly more efficient exploration.
Methods: The C-UCB Algorithm
The authors propose the Correlated-UCB (C-UCB) algorithm. The framework assumes the reward of each arm $k$ is a known function $g_k(X)$ of a common latent random variable $X$. While the distribution of $X$ is unknown, the functions $g_k$ are assumed to be known from prior studies.
C-UCB utilizes two primary mechanisms:
- Pseudo-Rewards: By observing a reward from arm $k$, the algorithm infers possible values of $X$ and calculates a "pseudo-reward" for other arms—the maximum possible reward they could have yielded given that $X$.
- Competitive vs. Non-Competitive Arms: Arms are classified based on their potential to be optimal. Non-competitive arms are those proven sub-optimal through the rewards of the current best arm, while competitive arms require direct exploration to distinguish.
Key Results and Insights
The theoretical analysis of C-UCB reveals several major advantages over traditional MAB approaches:
- Regret Reduction: C-UCB effectively transforms a $K$-armed bandit problem into a $(C+1)$-armed problem. The expected regret is proven to be $C \cdot O(\log T) + O(1)$.
- Constant Regret ($O(1)$): In cases where $C=0$ (no competitive arms), the algorithm achieves constant regret. This occurs when the information "leaked" by pulling the optimal arm is sufficient to rule out all others without ever pulling them directly.
- Information Leakage and Invertibility: If the reward function of the optimal arm is invertible, the latent variable $X$ can be perfectly deduced, leading to immediate identification of sub-optimal arms.
- Optimality: The authors provide new lower bounds for correlated bandits, proving that C-UCB is order-wise optimal.
Conclusion and Future Work
C-UCB demonstrates that structural knowledge of arm correlations can break the logarithmic regret barrier. While the current model assumes known reward functions $g_k(X)$, future research aims to extend this to scenarios where these functions must be learned online. Additionally, the authors suggest applying these correlation-exploiting principles to other strategies like Thompson Sampling to further enhance performance in complex decision-making environments.
Summary updated