Contextual Bandits with Similarity Information

Aleksandrs Slivkins

Introduction

In the landscape of machine learning, the Multi-Armed Bandit (MAB) problem serves as a fundamental model for decision-making under uncertainty. In its standard form, an agent selects an action (an "arm") and receives a reward, aiming to maximize cumulative gain over time. However, real-world scenarios—such as personalized advertising or clinical trials—often involve "contextual" information. In contextual bandits, the agent observes a context (e.g., user demographics or search queries) before choosing an arm. The challenge intensifies when the context or arm spaces are massive or infinite, rendering traditional tabular methods obsolete.

This paper introduces contextual zooming, a framework that leverages similarity information to navigate these infinite spaces. By adaptively partitioning the similarity space, the algorithm focuses its exploration on high-payoff regions, achieving regret bounds that scale with the inherent complexity of the problem instance rather than the raw dimensionality of the space.

The Problem: Beyond Uniform Partitions

To handle infinite context-arm spaces, researchers typically assume a similarity condition: if two context-arm pairs are close in a metric space, their expected payoffs are also close (the Lipschitz condition). Traditional approaches to this problem relied on "uniform partitions," which involve overlaying a fixed grid across the entire space.

Uniform partitioning is inherently inefficient. It allocates the same amount of exploration to low-payoff or rarely occurring regions as it does to high-payoff, frequent ones. This "one-size-fits-all" approach leads to suboptimal regret in practice, especially when the payoff function is "benign"—meaning it is relatively smooth or has a structure that can be exploited.

The Contextual Zooming Framework

The paper proposes two primary algorithmic solutions to address these inefficiencies.

1. Contextual Zooming for Stochastic Payoffs

For environments where payoffs are drawn from a stable distribution, the Contextual Zooming algorithm treats the context-arm pair $(x, y)$ as a single point in a joint metric space. The algorithm maintains a set of "active balls" within this space and operates via two key rules:

  • Selection Rule: Using an index-based approach similar to the Upper Confidence Bound (UCB) algorithm, the agent selects the active ball that maximizes the potential reward for the current context. This balances the exploitation of known high-reward areas with the exploration of uncertain ones.
  • Activation Rule: As a specific ball is sampled more frequently, the algorithm's confidence in the reward estimate for that region increases. Once the confidence radius becomes smaller than the ball's actual radius, the algorithm "zooms in" by creating smaller, more refined balls around that point. This allows for increasingly granular exploration of promising regions.

2. Meta-Algorithm for Adversarial Payoffs

In scenarios where payoffs are chosen by an adversary (non-stochastic), the paper introduces a meta-algorithm. This approach adaptively partitions the context space and runs a separate "black-box" adversarial bandit algorithm (such as EXP3) within each partition. This modularity allows the framework to handle highly volatile environments while still benefiting from adaptive partitioning.

Theoretical Contributions: The Zooming Dimension

A central contribution of this work is the introduction of the contextual zooming dimension ($d_c$). This metric is a refined version of the standard covering dimension and captures the effective dimensionality of the "relevant" parts of the space.

If the optimal regions of the space are low-dimensional or if the context distribution is concentrated, $d_c$ will be small. The algorithm’s regret is shown to be $O(T^{1 - 1/(d_c+2)} \log T)$. This result is significant because it matches the best possible worst-case performance while allowing the algorithm to perform significantly better on "benign" instances where the zooming dimension is low.

Key Results and Applications

The paper provides rigorous mathematical proofs demonstrating the optimality of the proposed algorithms:

  • Optimality: The author provides a general lower bound, proving that for any product similarity space, the upper bounds achieved by contextual zooming are nearly optimal (up to logarithmic factors).
  • Unified Framework: Contextual zooming acts as a "Swiss Army knife" for bandit theory, providing a unified approach to several distinct problems. It can be used to recover or improve results for drifting bandits (where payoffs change slowly over time), sleeping bandits (where certain arms may be unavailable in specific rounds), and bandit learning-to-rank.
  • Drifting Payoffs: For the "drifting MAB" problem, where payoffs evolve like a random walk, the algorithm achieves an average dynamic regret of $O(k \sigma \log^2 T_0)$, where $\sigma$ represents the volatility of the environment.

Limitations and Future Directions

While theoretically robust, the framework has practical considerations:

  1. Oracle Access: The algorithm assumes the ability to efficiently find the "best" active ball or partition. In high-dimensional spaces, the computational overhead of managing these partitions could be substantial.
  2. Known Lipschitz Constant: The model assumes the Lipschitz constant (the rate at which payoffs change) is known. In real-world applications, estimating this constant is non-trivial.
  3. Metric Dependency: The performance is strictly tied to the quality of the metric space. If the chosen similarity measure does not accurately reflect payoff similarities, the theoretical guarantees no longer hold. Future research could explore methods for learning the metric space dynamically alongside the bandit problem.

Conclusion

By shifting from fixed to adaptive partitions, the contextual zooming framework provides a powerful and flexible approach to contextual bandits in infinite spaces. Its ability to adapt to the inherent structure of the problem instance—formalized through the zooming dimension—marks a significant step forward in making bandit algorithms both theoretically optimal and practically efficient.

Summary updated

BibTeX
@article{slivkins2014contextual,
  author = {Aleksandrs Slivkins},
  title = {{Contextual Bandits with Similarity Information}},
  journal = {J. Mach. Learn. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=k5M84_GPRa2},
}
Figure