Contextual Bandits with Similarity Information

Aleksandrs Slivkins

Abstract

In a multi-armed bandit (MAB) problem, an online algorithm makes a sequence of choices. In each round it chooses from a time-invariant set of alternatives and receives the payoff associated with this alternative. While the case of small strategy sets is by now well-understood, a lot of recent work has focused on MAB problems with exponentially or infinitely large strategy sets, where one needs to assume extra structure in order to make the problem tractable. In particular, recent literature considered information on similarity between arms. We consider similarity information in the setting of "contextual bandits", a natural extension of the basic MAB problem where before each round an algorithm is given the "context" -- a hint about the payoffs in this round. Contextual bandits are directly motivated by placing advertisements on webpages, one of the crucial problems in sponsored search. A particularly simple way to represent similarity information in the contextual bandit setting is via a "similarity distance" between the context-arm pairs which gives an upper bound on the difference between the respective expected payoffs. Prior work on contextual bandits with similarity uses "uniform" partitions of the similarity space, which is potentially wasteful. We design more efficient algorithms that are based on adaptive partitions adjusted to "popular" context and "high-payoff" arms.

Introduction

The Multi-Armed Bandit (MAB) framework is a cornerstone of online machine learning, modeling the trade-off between exploring new actions and exploiting known high-reward actions. However, traditional MAB models often struggle with the scale of modern applications, such as sponsored search or personalized recommendations, where the number of possible actions (arms) and environments (contexts) can be infinite.

To address this, researchers have turned to "similarity information." By assuming that similar context-arm pairs yield similar rewards, we can make these infinite problems tractable. This paper introduces the Contextual Zooming algorithm, which moves beyond the rigid, uniform partitioning of previous methods to provide a more efficient, adaptive approach to the contextual bandit problem.

The Problem of Uniform Partitioning

In a contextual bandit setting, the agent receives a "context" (e.g., a user's profile or a webpage's content) before selecting an arm (e.g., an advertisement). The challenge lies in the sheer volume of possible context-arm pairs. Previous solutions typically relied on uniform partitions, effectively dividing the entire similarity space into equal-sized chunks.

This approach is inherently wasteful. It spends the same amount of exploratory effort on low-reward "dead zones" as it does on high-reward regions. In real-world scenarios, rewards are often concentrated in specific areas, and certain contexts appear far more frequently than others. A more efficient algorithm should be able to ignore the "boring" parts of the space and focus its refinement where the potential payoffs are highest.

The Contextual Zooming Algorithm

The core contribution of this research is the Contextual Zooming algorithm. It operates on a similarity space $(\mathcal{P}, D)$, where the distance $D$ between two context-arm pairs provides a Lipschitz bound on the difference in their expected payoffs.

Adaptive Partitioning and Selection

Unlike static grids, Contextual Zooming uses an adaptive partitioning strategy. It begins with a single, coarse "ball" covering the entire space. As data is gathered, the algorithm employs an index-based selection rule—similar to the Upper Confidence Bound (UCB) approach—to balance the exploration of uncertain regions with the exploitation of known high-reward areas.

The Activation Rule

The algorithm "zooms in" on specific regions through an activation rule. When a region has been sampled enough times that its "confidence radius" (the uncertainty of its reward) becomes smaller than its actual geometric radius, the algorithm creates a new, smaller ball centered at the current context-arm pair. This allows the algorithm to treat contexts and arms as a single, unified similarity space, refining its knowledge of high-potential regions with increasing precision.

Theoretical Insights: The Zooming Dimension

A key theoretical innovation in this paper is the definition of the contextual zooming dimension ($d_c$). While standard complexity measures like the covering dimension account for the entire space, the zooming dimension is more "optimistic." It measures the complexity of only the "relevant" parts of the space—those near the optimal rewards or those containing frequently occurring contexts.

This allows the algorithm to take advantage of "benign" problem instances. If high payoffs are concentrated in small regions, $d_c$ will be small, and the algorithm will perform significantly better than a uniform partitioning approach.

Key Results and Performance

The paper validates the Contextual Zooming algorithm through rigorous mathematical proofs of regret bounds:

  • Optimal Regret: The algorithm achieves a regret bound of $\tilde{O}(T^{1 - 1/(2+d_c)})$, where $T$ is the time horizon. This bound is instance-dependent, meaning it improves when the problem structure is benign.
  • Worst-Case Robustness: In the worst-case scenario where no benign structure exists, the algorithm matches the performance of the best known uniform partitioning algorithms.
  • Lower Bounds: The authors provide nearly matching lower bounds, proving that for any given similarity space, no algorithm can significantly outperform Contextual Zooming in the long run.

Conclusion and Future Directions

Contextual Zooming represents a significant advancement in making large-scale bandit problems tractable by adaptively focusing on high-value regions of the search space. While the algorithm currently requires a well-defined metric and explicit numeric bounds on payoff differences, it provides a robust framework for handling complex, real-world decision-making.

Future work may explore "ordinal" similarity, where explicit numeric distances are replaced by tree-based taxonomies, and extending the zooming logic to handle adversarial payoffs more effectively. By moving away from uniform partitions, this research paves the way for more nuanced and efficient online learning systems.

Summary updated

Abstract

In a multi-armed bandit (MAB) problem, an online algorithm makes a sequence of choices. In each round it chooses from a time-invariant set of alternatives and receives the payoff associated with this alternative. While the case of small strategy sets is by now well-understood, a lot of recent work has focused on MAB problems with exponentially or infinitely large strategy sets, where one needs to assume extra structure in order to make the problem tractable. In particular, recent literature considered information on similarity between arms. We consider similarity information in the setting of "contextual bandits", a natural extension of the basic MAB problem where before each round an algorithm is given the "context" -- a hint about the payoffs in this round. Contextual bandits are directly motivated by placing advertisements on webpages, one of the crucial problems in sponsored search. A particularly simple way to represent similarity information in the contextual bandit setting is via a "similarity distance" between the context-arm pairs which gives an upper bound on the difference between the respective expected payoffs. Prior work on contextual bandits with similarity uses "uniform" partitions of the similarity space, which is potentially wasteful. We design more efficient algorithms that are based on adaptive partitions adjusted to "popular" context and "high-payoff" arms.
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