Slate / Combinatorial Bandit

A Slate Bandit (combinatorial bandit) extends actions from single items to a whole page-level list: each round pick $K$ items out of $N$ candidates to form a slate $S$ with $|S| = K$, i.e. $\binom{N}{K}$ combinations; rewards may be item-level (per-item clicks) or slate-level (e.g., at least one click, dwell time). The typical solution is Top-K combinatorial exploration: apply UCB/TS-style confidence scores at the item level — sort by $\hat{\mu}_a + \sqrt{\frac{2\ln t}{n_a}}$ and take the top $K$, guaranteeing each candidate gets explored, then adjust for position/diversity.

home feed, search result pages, email recommendations, ad layout combinations; interviews contrast "one action vs a set of actions" with MAB, hitting combinatorial complexity $\binom{N}{K}$ and greedy approximation.

enumerating $\binom{N}{K}$ super-arms explodes combinatorially and cannot be estimated individually; slate bandits exploit the combinatorial structure (per-item contribution + position effects) to reduce the estimation dimension from combinations to items, keeping $O(\ln T)$-scale regret over large candidate pools while explicitly modeling item dependencies (diversity penalties, mutual exclusions).

Combinatorics: how many slates for $N=10, K=3$? Why can't we estimate every super-arm individually?

Top-K combinatorial exploration: how do item-level UCB/TS scores with top-K selection guarantee exploration?

Difference between item-level and slate-level reward modeling, and when to use each?

How does position bias distort estimates, and how do you correct for it?

Modeling dependencies within a slate: diversity, mutual exclusion, and click co-occurrence constraints?