Marginal Posterior Sampling for Slate Bandits

Maria Dimakopoulou, Nikos Vlassis, Tony JebaraIJCAI 2019 · DOI

Abstract

Recommendation systems often present users with a "slate" of items rather than a single recommendation. This introduces a combinatorial explosion of possible slates and a difficult credit assignment problem when only a single reward is observed for the entire collection. We present Marginal Posterior Sampling (MPS), a Thompson sampling-based algorithm that optimizes at the individual slot level. By assuming monotonicity in item quality and using reward imputation, MPS achieves significant reductions in cumulative regret while operating up to 70 times faster than traditional generalized linear bandit approaches.

Introduction

In modern recommendation engines, items are rarely presented in isolation. Instead, they are organized into slates—grids of movies, lists of articles, or multi-component emails. This "slate bandit" problem is challenging due to two primary factors:

  1. Combinatorial Complexity: With $l$ slots and $m$ actions per slot, the number of possible slates is $m^l$. Treating each combination as an independent arm is computationally and statistically infeasible.
  2. Credit Assignment: Systems typically observe a single binary reward (e.g., a click anywhere on the page) for the entire slate, making it unclear which specific item drove the user's engagement.

Existing Generalized Linear Bandit (GLM) models attempt to address this by modeling interactions, but they often rely on rigid functional assumptions and require expensive optimization over the slate space.

Methodology: Marginal Posterior Sampling (MPS)

MPS simplifies the slate bandit problem through three core principles:

Monotonicity Assumption

Rather than modeling complex item interactions, MPS assumes that the total reward is a non-decreasing function of the "quality" of individual items in their respective slots. This "monotonicity" implies that improving any single slot will not decrease the overall slate's expected reward.

Marginal Posteriors and Reward Imputation

MPS maintains independent Beta distributions for every (slot, action) pair. When a slate is presented and a reward $r \in \{0, 1\}$ is observed, the algorithm "imputes" this reward to every item in the slate. If the user interacts with the slate ($r=1$), every item in that specific configuration receives a "success" in its local statistics. While noisy, this approach allows marginal distributions to converge to the optimal items for each position over time.

Slot-Level Optimization

To select a new slate, MPS samples from the marginal posteriors of each slot and independently chooses the best item for each. This reduces the search complexity from $O(m^l)$ to $O(m \cdot l)$, enabling near-instantaneous decision-making.

Experimental Evaluation

The algorithm was evaluated in simulated environments designed to mimic recommendation dynamics, including additive reward functions and complex sigmoid models with random positive interactions (synergy). Simulations spanned 50,000 time steps with varying slate sizes ($l=2$ to $4$) and action counts ($m=2$ to $5$).

Cumulative regret across different action counts (m=2 to 5) for a 2-slot slate. MPS (orange) consistently achieves lower regret than GLM (blue) and Bernoulli (green) baselines.

Results and Discussion

MPS demonstrated superior performance and efficiency across all tested scenarios:

  • Regret Reduction: In sigmoid interaction tests, MPS improved cumulative reward by 15% to 30% compared to the GLM baseline.
  • Computational Speed: MPS is significantly faster than traditional methods. For a configuration with 4 slots and 5 actions, MPS made decisions in 0.20 ms, a 70x speedup over the 14.25 ms required by the GLM.
  • Scalability: The linear growth in computational cost relative to slots and actions makes MPS highly suitable for large-scale production environments.

Limitations and Future Work

The primary limitation of MPS is its reliance on the monotonicity assumption. In cases of strong negative interactions—where two individually high-quality items create a poor user experience when paired—MPS may struggle to find the optimal combination. Future work includes extending the model to handle high-dimensional contextual features and validating performance in live A/B testing environments.

Summary updated

BibTeX
@inproceedings{dimakopoulou2019marginal,
  author = {Maria Dimakopoulou and Nikos Vlassis and Tony Jebara},
  title = {{Marginal Posterior Sampling for Slate Bandits}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/308},
}
Figure