Exploiting Correlation in Finite-Armed Structured Bandits

Samarth Gupta, Gauri Joshi, Osman Yagan

Abstract

We consider a finite-armed structured bandit problem in which mean rewards of different arms are known functions of a common hidden parameter $\theta^*$. Since we do not place any restrictions of these functions, the problem setting subsumes several previously studied frameworks that assume linear or invertible reward functions. We propose a novel approach to gradually estimate the hidden $\theta^*$ and use the estimate together with the mean reward functions to substantially reduce exploration of sub-optimal arms. This approach enables us to fundamentally generalize any classic bandit algorithm including UCB and Thompson Sampling to the structured bandit setting. We prove via regret analysis that our proposed UCB-C algorithm pulls only a subset of the sub-optimal arms $O(\log T)$ times while the other sub-optimal arms (referred to as non-competitive arms) are pulled $O(1)$ times. As a result, in cases where all sub-optimal arms are non-competitive, the proposed algorithms achieve bounded regret. We also conduct simulations on the Movielens recommendations dataset to demonstrate the improvement of the proposed algorithms over existing structured bandit algorithms.

Introduction: The Structured Bandit Problem

In the classic Multi-Armed Bandit (MAB) problem, an agent pulls different arms to maximize cumulative reward, balancing exploration (trying new arms) and exploitation (pulling the best-known arm). Standard MAB algorithms assume the rewards of different arms are completely independent. However, in many real-world scenarios, arm rewards are correlated via a shared, hidden context.

The structured bandit framework illustrated via a movie recommendation system where user context is unknown but reward mappings are known.

This is the structured bandit problem. It is the mirror image of contextual bandits: in contextual bandits, the context is known but the reward mapping is unknown; here, the context is hidden but the reward mapping is known. For example, when recommending movies to an anonymous user, the user's demographic (the hidden parameter $\theta^*$) is unknown, but historical data provides the reward functions (how different demographics rate different genres).

Methodology: The Algorithm-C Framework

The authors propose a meta-algorithm called Algorithm-C (Algorithm-Competitive), which acts as a universal wrapper around any classical bandit algorithm. By leveraging the known structure of reward functions, it identifies which arms are truly "competitive" for the current estimate of the hidden parameter.

Reward functions $\mu_i(\theta)$ for different arms as a function of the shared hidden parameter $\theta^*$.

At each time step, the algorithm performs three key steps:

  1. Construct a Confidence Set: Using observed rewards, it calculates a confidence interval ($\hat{\Theta}_t$) that contains the true hidden parameter $\theta^*$ with high probability.
  2. Filter for "Competitive" Arms: It evaluates all arms against this set. If an arm cannot possibly be optimal for any parameter value still inside $\hat{\Theta}_t$, it is labeled "non-competitive" and eliminated from the current round.
  3. Execute Classical Bandit Algorithm: The surviving arms are fed into a standard MAB algorithm (like UCB or Thompson Sampling) to decide the next pull.

Key Insights and Theoretical Results

The primary theoretical breakthrough is the proof that Algorithm-C pulls non-competitive arms only a constant $O(1)$ number of times. Standard algorithms pull all sub-optimal arms $O(\log T)$ times. By leveraging structure, Algorithm-C stops exploring arms once the hidden parameter is constrained enough to prove they are sub-optimal.

  • Bounded Regret: In scenarios where the optimal arm's reward uniquely identifies the hidden parameter, the algorithm achieves $O(1)$ bounded regret over infinite time, effectively solving the exploration-exploitation tradeoff.
  • Universal Applicability: Because the framework can wrap any strategy, practitioners can deploy structured versions of Thompson Sampling (TS-C) without needing to derive complex Bayesian posterior updates for non-linear reward functions.

Empirical Evaluation

The researchers tested the framework using both synthetic data and the MovieLens 1M Dataset. In the MovieLens simulation, 18 movie genres served as "arms" and 106 user demographic profiles acted as the hidden parameter $\theta^*$.

  • Performance: TS-C and UCB-C consistently outperformed standard versions and prior state-of-the-art structured algorithms like UCB-S.
  • Efficiency: On MovieLens, the algorithm successfully reduced the 18-arm problem to an effective problem size of just 1 to 9 competitive arms, depending on the user profile, significantly lowering cumulative regret.

Limitations and Future Work

Currently, the algorithm assumes perfect knowledge of the reward mappings (the functions from $\theta$ to mean rewards). While the framework is robust to some uncertainty, it is primarily designed for environments where these mappings are well-understood. Future research may extend this to "best-arm identification" tasks, where the goal is to find the optimal arm in the minimum number of steps regardless of intermediate rewards.

Summary updated

Abstract

We consider a finite-armed structured bandit problem in which mean rewards of different arms are known functions of a common hidden parameter $\theta^*$. Since we do not place any restrictions of these functions, the problem setting subsumes several previously studied frameworks that assume linear or invertible reward functions. We propose a novel approach to gradually estimate the hidden $\theta^*$ and use the estimate together with the mean reward functions to substantially reduce exploration of sub-optimal arms. This approach enables us to fundamentally generalize any classic bandit algorithm including UCB and Thompson Sampling to the structured bandit setting. We prove via regret analysis that our proposed UCB-C algorithm (structured bandit versions of UCB) pulls only a subset of the sub-optimal arms $O(\log T)$ times while the other sub-optimal arms (referred to as non-competitive arms) are pulled $O(1)$ times. As a result, in cases where all sub-optimal arms are non-competitive, which can happen in many practical scenarios, the proposed algorithms achieve bounded regret. We also conduct simulations on the Movielens recommendations dataset to demonstrate the improvement of the proposed algorithms over existing structured bandit algorithms.
BibTeX
@misc{gupta2018exploiting,
  author = {Samarth Gupta and Gauri Joshi and Osman Yagan},
  title = {{Exploiting Correlation in Finite-Armed Structured Bandits}},
  year = {2018},
  eprint = {1810.08164},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.08164},
}
Figure