Non-Stochastic Bandit Slate Problems

Satyen Kale, Lev Reyzin, Robert E. SchapireNeurIPS 2010 · OpenReview

In classic "multi-armed bandit" problems, a learner selects a single action (an "arm") out of $K$ possibilities and receives a reward. However, real-world recommendation systems—like those used by Google or Netflix—rarely show just one ad or movie. Instead, they present a slate: a subset or a ranked list of items.

This paper introduces efficient algorithms for non-stochastic "slate" bandit problems. By combining multiplicative weight updates with relative entropy projections, the authors achieve optimal $O(\sqrt{T})$ regret bounds for both ordered and unordered lists, even when competing against complex external policies.

The Slate Bandit Problem

Transitioning from single items to slates introduces two primary challenges:

  1. Combinatorial Explosion: If a system has 1,000 items and needs to pick a slate of 10, the number of possible combinations is astronomical. Standard bandit algorithms that treat every combination as a unique "arm" would be computationally intractable.
  2. Bandit Feedback: The learner only observes the rewards (e.g., clicks or revenue) for the items actually displayed. There is no counterfactual feedback for how unselected items would have performed.

The authors tackle two distinct versions of this problem:

  • Unordered Slates: The learner selects $s$ items, and the total reward is simply the sum of their individual rewards.
  • Ordered Slates: Position matters. An ad placed at the top of a page typically has a different reward profile than the same ad placed at the bottom.

Algorithmic Approach: Projections and Embeddings

To solve this efficiently, the authors build on a specialized version of the Multiplicative Weights (MW) algorithm. The core technical innovation avoids maintaining a probability distribution over every possible slate. Instead, the algorithm maintains a distribution over individual actions but constrains it to a convex set representing the "average" behavior of a valid slate.

To keep the algorithm's "beliefs" within the bounds of a valid slate, they utilize Bregman Projections. After each update, the new distribution is projected back onto the set of valid slate representations using relative entropy as the distance metric.

The geometric embeddings differ based on the problem type:

  • For unordered slates, a slate is represented as an indicator vector within a specific polytope.
  • For ordered slates, the authors use subpermutation matrices to capture both the item and its specific position in the ranking.

Unlike general-purpose online linear optimization tools that require complex "self-concordant barriers," these algorithms rely on simple matrix/vector operations and sorting, making them highly practical for real-time systems.

Key Results and Regret Bounds

The authors provide the first efficient algorithms for these slate problems that achieve $O(\sqrt{T})$ regret. The framework is also flexible enough to handle competition against external "experts" or policies. If there are $N$ different black-box strategies recommending slates, these algorithms can learn to perform almost as well as the best single strategy in hindsight.

Summary of regret bounds for unordered and ordered slates.

As shown in the bounds, ordered slates are fundamentally harder to optimize. The regret bound for ordered slates scales linearly with the slate size $s$, whereas the unordered version scales with $\sqrt{s}$. These results are significant because they improve upon general combinatorial bandit bounds by factors of $\sqrt{s}$ or more, while running in polynomial time relative to the number of items.

Limitations and Future Directions

Because this is a theoretical work focused on algorithmic design, no empirical experiments on real-world datasets were conducted. The authors note several areas for future refinement:

  • Independence Assumption: The current model assumes the reward of one item in a slate is independent of the others. In reality, showing two very similar news stories might decrease the value of the second one due to redundancy. Modeling these interactions is a critical next step.
  • High-Probability Bounds: The bounds provided are for expected regret. While high-probability bounds are possible for the "no-policy" setting, extending them to scenarios where the learner competes against multiple policies remains open.
  • User Modeling: The ordered model assumes a fixed reward for an (item, position) pair but does not account for complex user behaviors, such as "cascading" models where a user scans from top to bottom and stops after the first click.

Summary updated

Abstract

We consider bandit problems, motivated by applications in online advertising and news story selection, in which the learner must repeatedly select a slate, that is, a subset of size s from K possible actions, and then receives rewards for just the selected actions. The goal is to minimize the regret with respect to total reward of the best slate computed in hindsight. We consider unordered and ordered versions of the problem, and give efficient algorithms which have regret O(sqrt(T)), where the constant depends on the specific nature of the problem. We also consider versions of the problem where we have access to a number of policies which make recommendations for slates in every round, and give algorithms with O(sqrt(T)) regret for competing with the best such policy as well. We make use of the technique of relative entropy projections combined with the usual multiplicative weight update algorithm to obtain our algorithms.
BibTeX
@inproceedings{kale2010non,
  author = {Satyen Kale and Lev Reyzin and Robert E. Schapire},
  title = {{Non-Stochastic Bandit Slate Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=H1ZyWPbdWH},
}
Figure