arXiv:2607.22935cs.LG2026-07

解决推荐系统中动态曝光下限的公平性问题,实现零违规与低后悔。

Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors

论文配图:Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors
图 1 · 摘自论文原文
  • 将公平调度建模为整数取样中的分歧问题,通过分块处理动态下限。
  • 提出BDQ-UCB算法,后悔上界仅依赖非强制预算R,达Θ(√KR)最优率。
  • 适用于重叠群体场景,可避免传统方法因分组冲突导致的曝光偏差。

在推荐、内容筛选和受监管分配中,每个提供方、臂或群体需在特定周期内获得保证的曝光量,而非仅总体满足。本文研究带有精确曝光下限的随机多臂老虎机问题,发现关键在于一个舍入问题:分数公平调度通过整数拉取实现,曝光误差即为分歧向量。主要贡献是提出一种带时变下限的分块模型。BDQ-UCB算法在每块内确定性满足下限,高概率后悔界为O(√KR log(KT)),其中非强制预算R取代时间跨度T主导后悔;其MOSS残差变体达到O(√KR),且存在匹配下界Θ(√KR),即使有正强制曝光亦成立;引入kl-UCB++残差规则实现实例相关最优性。对于重叠群体下限,单臂舍入可能导致组约束违反Ω(s),而Beck-Fiala零空间舍入在块预算内满足所有组下限,违反度低于臂度t,且与UCB兼容于同一R参数后悔。针对学习到的组计划,封闭不相交系统达~Θ(√KT),提出双账本分解解释朴素索引规则失败原因,并证明一种路径可行的计划采样规则,在初始覆盖松弛条件下实现条件~O(√KT)保证,条件无关的重叠率仍开放。合成数据、MovieLens-100k类型曝光及部署压力测试显示,该方法在无需调参情况下实现精确可行性,且后悔表现媲美调优后的拉格朗日基线。

原文摘要 · Abstract (English)

Minimum-exposure constraints arise in recommendation, content curation, and regulated allocation when each provider, arm, or group must receive guaranteed exposure inside a period rather than only in aggregate. We study stochastic bandits with exact exposure floors and show that the right object is a rounding problem: a fractional fair schedule is realized as integral pulls, and the exposure error is exactly a discrepancy vector. The main contribution is a blockwise model with time-varying floors. BDQ-UCB satisfies every block floor deterministically and has fair regret governed by the nonmandatory budget $R$, not the horizon $T$, with high-probability regret $O(\sqrt{KR\log(KT)})$. A MOSS residual variant attains $O(\sqrt{KR})$, and a matching lower bound gives the minimax rate $Θ(\sqrt{KR})$, even with positive mandatory exposure; a kl-UCB$^{++}$ residual rule adds instance-dependent optimality. The formulation becomes essential for overlapping group floors: per-arm rounding can violate a group constraint by $Ω(s)$ in the group size, whereas Beck--Fiala null-space rounding meets every group floor within the block budget with violation below the arm degree $t$, and composes with UCB at the same $R$-parametrized regret. For learned group plans, we close disjoint systems at $\widetildeΘ(\sqrt{KT})$, give a dual-ledger decomposition explaining why naive index rules fail under overlap, and prove a plan-sampling rule that is pathwise feasible under an initial cover-slack condition and attains a conditional $\widetilde O(\sqrt{KT})$ guarantee, leaving the condition-free overlap rate open. Experiments on synthetic floors, MovieLens-100k genre exposure, and deployment stress tests show exact feasibility without penalty tuning and regret competitive with tuned Lagrangian baselines.

公平推荐多臂老虎机曝光控制算法优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。