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