Bounded Regret for Finite-Armed Structured Bandits

Tor Lattimore, Rémi Munos

Abstract

We study a new type of K-armed bandit problem where the expected return of one arm may depend on the returns of other arms. We present a new algorithm for this general class of problems and show that under certain circumstances it is possible to achieve finite expected cumulative regret. We also give problem-dependent lower bounds on the cumulative regret showing that at least in special cases the new algorithm is nearly optimal.

Introduction

In the classic Multi-Armed Bandit (MAB) framework, an agent must balance exploration (trying new arms) with exploitation (pulling the best-known arm). Standard theory assumes arms are independent, leading to the well-known result by Lai and Robbins (1985): any consistent strategy must suffer at least logarithmic cumulative regret, $O(\log n)$, as the number of trials $n$ grows.

However, many real-world problems exhibit structure. For instance, in online advertising, the click-through rates of different ad variants are often mathematically related. This paper explores whether such structures can be exploited to break the logarithmic barrier and achieve finite regret—a state where the agent eventually identifies the optimal arm with such high confidence that it stops making sub-optimal choices entirely.

The UCB-S Algorithm

The authors propose UCB-S (Structured Upper Confidence Bound), an algorithm designed to leverage known functional relationships between arms.

The Model

The reward of each arm $i$ is assumed to be a known function $\mu_i(\theta)$ of an underlying, unknown parameter $\theta^*$. Instead of estimating each arm's mean independently, UCB-S maintains a confidence set $\tilde{\Theta}_t$ of possible parameters consistent with all observed data across all arms.

Examples of structured reward functions $\mu_i(\theta)$ across various settings, including linear and piecewise-linear models.

Optimism under Structure

At each step, the algorithm selects the arm $i$ that maximizes the potential reward for any parameter in the current confidence set. This approach allows the agent to "learn for free." Pulling the optimal arm provides information about $\theta^*$, which in turn shrinks the confidence intervals for all other arms, even those not recently pulled.

Achieving Finite Regret

The core theoretical contribution is identifying the conditions under which UCB-S achieves finite regret. Theorem 3 establishes that if the problem structure is "identifiable"—meaning the optimal arm's mean reward uniquely distinguishes it as the best across the parameter space—the algorithm's expected cumulative regret remains bounded by a constant. In these cases, the information gained from the optimal arm is sufficient to eventually "disprove" all sub-optimal arms forever.

The Challenge of Ambiguity

Finite regret is not guaranteed for all structures. The authors identify "Ambiguous Cases" where two different parameters $\theta_1$ and $\theta_2$ might yield the same mean reward for the optimal arm but point to different arms as being optimal. In such scenarios, the agent is forced to continue pulling sub-optimal arms to distinguish between the parameters, reverting to the classic $O(\log n)$ regret.

Counter-examples illustrating structures where the identifiability condition fails, leading to potential ambiguity.

Conclusion

This work demonstrates that logarithmic regret is not an inescapable law for all bandit problems. By exploiting problem structure, UCB-S can achieve significantly better performance, reaching a steady state of zero additional regret in many practical scenarios. Future work involves addressing the computational complexity of optimizing over high-dimensional parameter spaces and extending these guarantees to continuous action sets.

Summary updated

Abstract

We study a new type of K-armed bandit problem where the expected return of one arm may depend on the returns of other arms. We present a new algorithm for this general class of problems and show that under certain circumstances it is possible to achieve finite expected cumulative regret. We also give problem-dependent lower bounds on the cumulative regret showing that at least in special cases the new algorithm is nearly optimal.
BibTeX
@inproceedings{lattimore2014bounded,
  author = {Tor Lattimore and Rémi Munos},
  title = {{Bounded Regret for Finite-Armed Structured Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=S14RlwZuZB},
}
Figure