A Unified Approach to Translate Classical Bandit Algorithms to the\n Structured Bandit Setting

Samarth Gupta, Shreyas Chaudhari, Subhojyoti Mukherjee, Gauri Joshi, Osman Yağan

Introduction

In the classical Multi-Armed Bandit (MAB) problem, an agent must choose between $K$ independent arms to maximize cumulative rewards. However, real-world scenarios often feature "structured" arms where rewards are correlated through a shared underlying factor. For instance, a recommendation system suggesting movies to an anonymous user must infer the user's latent preferences (the "context") to make optimal choices. While previous research has explored structured bandits, many solutions rely on restrictive assumptions like linear reward functions. This paper introduces Algorithm-C, a unified framework that generalizes classical bandit algorithms—such as Upper Confidence Bound (UCB) and Thompson Sampling (TS)—to the structured setting with arbitrary reward functions.

The Structured Bandit Problem

The authors consider a finite-armed bandit problem where the mean reward of each arm $i$ is a known function $\mu_i(\theta^*)$ of a common hidden parameter $\theta^*$. Unlike traditional models, this setting does not assume linearity or invertibility of the reward functions.

Figure 1: Movie recommendation as a structured bandit problem where user preferences depend on a hidden context.

As illustrated in Figure 1, a user's preference (the context $\theta^*$) determines the expected reward for different movies. If the user is not signed in, $\theta^*$ is unknown, but historical data provides the mapping between user types and movie ratings. The goal is to learn $\theta^*$ efficiently by observing rewards from selected arms.

The Algorithm-C Framework

The core contribution is a meta-algorithm that wraps around existing bandit strategies. Algorithm-C operates in three primary stages:

  1. Confidence Set Construction: The algorithm maintains a confidence set $\hat{\Theta}_t$ of possible values for the hidden parameter $\theta^*$, updated as new rewards are observed.
  2. Identifying Competitive Arms: It filters the set of arms to include only those that are "competitive"—arms that could potentially be optimal for some $\theta$ within the current confidence set.
  3. Classical Execution: A standard bandit algorithm (e.g., UCB or TS) is then applied exclusively to this reduced set of competitive arms.
Figure 2: Reward functions $\mu_i(\theta)$ for different arms as a function of the hidden parameter $\theta$.

Figure 2 demonstrates how different arms have varying reward profiles across the parameter space. By identifying regions where certain arms are strictly dominated by others, the algorithm can prune "non-competitive" arms early in the learning process. The authors also propose Informative Algorithm-C, which occasionally pulls non-competitive arms if they provide significant information to shrink the confidence set $\hat{\Theta}_t$ faster.

Key Insights: Bounded Regret

A significant theoretical finding is the distinction between competitive and non-competitive sub-optimal arms. In classical MAB, all sub-optimal arms are typically pulled $O(\log T)$ times. In the structured setting, Algorithm-C ensures that:

  • Competitive sub-optimal arms are pulled $O(\log T)$ times.
  • Non-competitive arms are pulled only $O(1)$ times.

In many practical cases where the optimal arm is distinct, all sub-optimal arms may eventually become non-competitive, leading to bounded regret. This means the total cost of exploration does not grow indefinitely, a major improvement over the logarithmic regret of standard methods.

Empirical Validation

The researchers validated their approach using synthetic simulations and the MovieLens 1M dataset. In the MovieLens experiments, users were grouped into "meta-users" based on age and occupation (representing the hidden parameter $\theta$), while movie genres served as the arms.

The results showed that UCB-C and TS-C significantly outperformed their classical counterparts. By leveraging the structure of the reward functions, the algorithms converged to the optimal choice much faster, reducing the number of sub-optimal pulls from thousands to nearly zero after the initial learning phase. Furthermore, Algorithm-C proved more robust than previous specialized structured algorithms like UCB-S, particularly when the true parameter $\theta^*$ was near the boundary of different optimal regions.

Conclusion

Algorithm-C provides a powerful, modular way to adapt well-known bandit strategies to complex, structured environments. By focusing exploration on competitive arms, it achieves superior performance and, in some cases, bounded regret. While computational challenges remain for large parameter spaces, the framework offers a significant step toward more efficient real-world recommendation and decision-making systems.

Summary updated

Abstract

We consider a finite-armed structured bandit problem in which mean rewards of\ndifferent arms are known functions of a common hidden parameter $\\theta^*$.\nSince we do not place any restrictions of these functions, the problem setting\nsubsumes several previously studied frameworks that assume linear or invertible\nreward functions. We propose a novel approach to gradually estimate the hidden\n$\\theta^*$ and use the estimate together with the mean reward functions to\nsubstantially reduce exploration of sub-optimal arms. This approach enables us\nto fundamentally generalize any classic bandit algorithm including UCB and\nThompson Sampling to the structured bandit setting. We prove via regret\nanalysis that our proposed UCB-C algorithm (structured bandit versions of UCB)\npulls only a subset of the sub-optimal arms $O(\\log T)$ times while the other\nsub-optimal arms (referred to as non-competitive arms) are pulled $O(1)$ times.\nAs a result, in cases where all sub-optimal arms are non-competitive, which can\nhappen in many practical scenarios, the proposed algorithms achieve bounded\nregret. We also conduct simulations on the Movielens recommendations dataset to\ndemonstrate the improvement of the proposed algorithms over existing structured\nbandit algorithms.\n
BibTeX
@misc{gupta2018unified,
  author = {Samarth Gupta and Shreyas Chaudhari and Subhojyoti Mukherjee and Gauri Joshi and Osman Yağan},
  title = {{A Unified Approach to Translate Classical Bandit Algorithms to the\textbackslash\{\}n Structured Bandit Setting}},
  year = {2018},
  eprint = {1810.08164},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.08164},
}
Figure