Correlated Multi-Armed Bandits with A Latent Random Source

Samarth Gupta, Gauri Joshi, Osman Yagan

TL;DR

Standard multi-armed bandit algorithms waste time exploring sub-optimal arms because they assume every arm is independent. This paper introduces C-UCB, an algorithm that exploits correlations between arms linked by a common latent random source to identify "non-competitive" arms, potentially achieving constant regret ($O(1)$) rather than the traditional logarithmic growth ($O(\log T)$).

What Problem Does This Paper Address?

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: do you stick with the best arm you've found so far, or try others to see if they are better?

Traditional models (like the famous UCB1 algorithm) assume that the reward from one arm tells you absolutely nothing about the others. Because of this "independence assumption," these algorithms are mathematically forced to pull every sub-optimal arm at least $O(\log T)$ times to be sure they aren't the best.

However, in the real world, rewards are often correlated. For example, if two different advertisements are shown to the same demographic (a latent variable), their performance is likely linked. If we know how these rewards are structurally related, can we stop exploring obviously bad arms much sooner?

Methods

The authors propose a framework where 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 (perhaps from prior controlled studies).

The C-UCB Algorithm

The "Correlated-UCB" (C-UCB) algorithm introduces two clever concepts:

  1. Pseudo-Rewards: When you pull arm $k$ and see a reward $r$, you can infer which values of $X$ could have produced that reward. The "pseudo-reward" for another arm $\ell$ is the maximum possible reward arm $\ell$ could have given for those specific values of $X$.
  2. Competitive vs. Non-Competitive Arms:
    • Non-competitive arms are those that can be proven sub-optimal just by looking at the rewards of the current best arm.
  3. Competitive arms are those that are "too close to call" without pulling them directly.

C-UCB identifies the arm pulled most often ($k_{max}$) and uses its data to calculate empirical pseudo-rewards for all other arms. If an arm's pseudo-reward is lower than the average reward of $k_{max}$, it is labeled "non-competitive" and removed from the exploration pool. The algorithm then runs standard UCB only on the remaining "competitive" set.

Datasets

The paper relies on synthetic simulations to validate the theory. They tested three primary scenarios:

  • Discrete Latent Source: $X$ takes values from a finite set, with rewards defined by specific vectors.
  • Continuous Latent Source: $X$ follows various Beta distributions, with reward functions including Gaussian, exponential, and uniform mappings.
  • Latent Random Vector: $X$ is a multi-dimensional vector $(X_1, X_2)$, showing the algorithm's extensibility.

No real-world datasets were used for benchmarking in this specific paper.

Key Insights and Ideas

  • The Power of Invertibility: If the reward function of the optimal arm is invertible, we can perfectly deduce the value of the latent variable $X$ every time we pull it. This allows us to calculate the exact rewards of all other arms without ever pulling them, leading to $O(1)$ regret.
  • Reducing the Problem Space: C-UCB effectively transforms a $K$-armed bandit problem into a $(C+1)$-armed problem, where $C$ is the number of competitive arms. If $C=0$, the algorithm stops exploring sub-optimal arms entirely after a finite number of steps.
  • Information Leakage: The paper formalizes the idea that pulling one arm "leaks" information about others. Even if the functions aren't perfectly invertible, the "upper bound" provided by pseudo-rewards is often enough to rule out bad arms.

Key Results

  • Regret Analysis: The authors prove that C-UCB achieves an expected regret of $C \cdot O(\log T) + O(1)$.
  • Constant Regret: In regimes where $C=0$ (no competitive arms), the algorithm achieves $O(1)$ regret. This is a significant theoretical improvement over the $O(\log T)$ regret of standard UCB.
  • Lower Bounds: The authors provide a new lower bound for correlated bandits, proving that C-UCB is order-wise optimal—meaning no algorithm can do better than $O(1)$ regret when $C=0$.
  • Simulation Performance: In tests where only one arm was competitive, C-UCB's regret curve flattened significantly compared to the linear-looking logarithmic growth of vanilla UCB.

Limitations and Future Work

  • Known Reward Functions: The biggest limitation is the assumption that the functions $g_k(X)$ are known. In many applications, these mappings are just as mysterious as the distribution of $X$ itself.
  • Static Functions: The model assumes the relationship between $X$ and the rewards doesn't change over time.
  • Future Directions: The authors suggest extending this logic to other bandit strategies like Thompson Sampling. They also aim to investigate how to handle cases where the reward functions $g_k$ must be learned alongside the latent distribution.

Summary updated

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 (i.e., to increase the total reward obtained after T rounds). 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 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, where C can be computed from the reward functions. A key consequence is that when C = 0, our algorithm achieves a constant (i.e., O(1)) regret instead of the standard O(log T) scaling with the number of rounds T . 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.
BibTeX
@inproceedings{gupta2020correlated,
  author = {Samarth Gupta and Gauri Joshi and Osman Yagan},
  title = {{Correlated Multi-Armed Bandits with A Latent Random Source}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=pq9kO973JSq},
}

Loading related content...

Figure