Slate/组合老虎机

Slate Bandit (组合老虎机) 把动作从单个 item 扩展到整页推荐列表:每轮从 $N$ 个候选中选出 $K$ 个组成 slate $S$,要求 $|S| = K$,共 $\binom{N}{K}$ 种组合;奖励既可以是 item 级(逐条点击),也可以是 slate 级(如"至少一次点击"、页面停留时长)。典型解法是 Top-K 组合探索:把 UCB/TS 的置信公式作用到 item 级别——按 $\hat{\mu}_a + \sqrt{\frac{2\ln t}{n_a}}$ 排序取前 $K$,保证每个候选都有被探索的机会,再结合位置/多样性修正。

首页信息流、搜索结果页、邮件推荐、广告组合样式;面试从"一个动作 vs 一组动作"的维度对比 MAB,引出组合复杂度 $\binom{N}{K}$ 与贪心近似。

直接枚举 $\binom{N}{K}$ 个超臂 (super-arm) 会组合爆炸、无法逐一估计;slate bandit 利用组合结构(每个 item 的独立贡献 + 位置效应)把估计维度从组合级降到 item 级,在大候选池下保持 $O(\ln T)$ 量级的 regret,同时能显式建模 item 间依赖(多样性惩罚、互斥内容)。

组合复杂度: $N=10, K=3$ 时有多少种 slate?为什么不能逐一估计每个超臂?

Top-K 组合探索的公式: 如何在 item 级做 UCB/TS 并取前 K, 探索如何保证?

item 级奖励与 slate 级奖励建模的差别?各自适用场景?

位置偏差 (position bias) 如何影响估计?如何修正?

slate 内 item 间的依赖如何建模: 多样性/互斥/协同点击的约束?