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:
- 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.
- 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.
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