差异舍入法下的静态与时变曝光下限公平赌博机

# 基于静态与时变曝光下限的差异舍入公平赌博机 来源：https://arxiv.org/html/2607.22935 ###### 摘要 最小曝光约束出现在推荐、内容策展和受监管分配中，此时每个提供者、臂或组必须在某个时间段内获得保证的曝光，而不仅仅是总体上的聚合。我们研究带有精确曝光下限的随机赌博机，并表明核心问题是一个舍入问题：一个分数公平调度被实现为整数拉取，而曝光误差恰好是一个差异向量。主要贡献是一个具有时变下限的分块模型。BDQ-UCB 确定性地满足每个分块的下限，其公平遗憾由非强制预算 \(R\) 而非时间范围 \(T\) 决定，高概率遗憾为 \(O(\sqrt{KR\log(KT)})\)。一个 MOSS 残差变体达到 \(O(\sqrt{KR})\)，并且一个匹配的下界给出了极小极大速率 \(\Theta(\sqrt{KR})\)，即使存在正强制曝光；一个 kl-UCB++ 残差规则添加了实例依赖的最优性。该公式对于重叠组下限变得必不可少：逐臂舍入可能违反组约束达 \(O(s)\)（其中 \(s\) 为组大小），而 Beck–Fiala 零空间舍入在分块预算内满足每个组下限，违反程度低于臂度 \(t\)，并与 UCB 组合，得到相同参数化遗憾 \(R\)。对于学习的组计划，我们在 \(\tilde{\Theta}(\sqrt{KT})\) 处封闭了不相交系统，给出一个双账本分解，解释了为什么朴素指数规则在重叠下会失败，并证明了一个计划采样规则，该规则在初始覆盖松弛条件下是路径可行的，并达到条件性的 \(\tilde{O}(\sqrt{KT})\) 保证，将无条件重叠速率问题留为开放。在合成下限、MovieLens-100k 类型曝光和部署压力测试上的实验显示，无需惩罚调优即可实现精确可行性，且遗憾与调优的拉格朗日基线相当。 ## 引言 公平约束赌博机出现在臂是提供者、卖家、内容源、治疗或必须获得最低曝光的受保护群体时。经典随机赌博机会将几乎所有拉取集中在经验最佳臂上，但在许多分配系统中，即使奖励较低的臂也出于合同、法律或伦理原因有权获得最小数量的机会。对于固定的全局曝光下限，有一个简单且经过充分研究的解决方案：给每个臂其所需的拉取次数，然后运行标准赌博机算法，如 Fair-MAB（Patil et al. 2020, 2021）所形式化的。我们的起点不同：我们将公平层视为一个*舍入*层，其中学习器通过整数拉取实现一个分数曝光计划，由此产生的曝光差距恰好是一个差异向量。这对于单个全局下限几乎是平凡的，但当下限随时间变化时变得结构上有用，并且当下限重叠时（此时单次拉取可以同时满足多个约束）变得真正必要。图1显示了流程：在每个周期内，将一个分数公平计划舍入为恰好满足下限的整数拉取，然后将剩余轮次用于学习奖励。留下的差异舍入决定了可行性；非强制轮次的数量决定了遗憾。 参阅图注 图1：公平赌博机的差异舍入视图。每个周期将一个分数公平计划舍入为整数拉取（曝光差距是一个差异向量），并将剩余轮次用于残差 UCB。逐臂下限仅需循环配额舍入；重叠组下限需要真正的集合差异舍入，其中这种简化本身成为算法而不仅仅是描述性语言。 这个视角组织了整篇论文。我们的核心对象是*分块*模型，其中时间范围被分割成若干周期，每个周期带有自己的整数下限向量，必须在该周期内满足，而不仅仅是总体上的聚合。分块算法 BDQ-UCB（分块差异配额上置信界）精确执行每个分块的配额，并且仅在下限释放的轮次上运行 UCB，因此其公平遗憾由总非强制预算 \(R = \sum_{b=1}^{B} \left( H_b - \sum_i m_{b,i} \right)\) 决定，而不是由时间范围 \(T\) 决定。在强意义上，这是正确的复杂度参数：一个匹配的下界和一个基于 MOSS 的残差规则将极小极大速率定为 \(\Theta(\sqrt{KR})\)，即使强制曝光占时间范围的恒定比例，并且一个 kl-UCB++ 残差规则恢复了精确的实例依赖常数。强制拉取对于每个公平策略都是共有的，因此是免费的；所有不可避免的探索都存在于残差预算中。算法命名是系统的：后缀是残差索引规则（UCB、MOSS 或 kl-UCB++）；DQ-UCB 是静态基础，B 前缀标记分块版本，Group-、D-、OG- 和 P- 前缀分别标记固定、不相交、一次性采样和采样计划组算法。 当下限放置在重叠组上时，这种简化变得必要。使用逐臂规则舍入一个组可行的分数计划可能会在组大小上错过一个组下限达 \(O(s)\)，而 Beck–Fiala 零空间舍入，一种真正的差异算法，使用严格低于臂度 \(t\)（与组大小和组数量无关）的组松弛度，在预留的分块预算内满足每个组下限。与 UCB 组合，这产生了 Group-BDQ-UCB，对于固定组计划具有相同的残差预算遗憾。最后一个问题是计划本身是否可以学习，从而使基准变为最佳组公平计划而非给定计划。在这里，对于不相交组，答案是尖锐的：一个逐次拉取覆盖规则以 \(\tilde{\Theta}(\sqrt{KT})\) 封闭了计划适应性的代价，匹配一个下界，并且在任意重叠下部分地封闭，其中线性规划对偶性识别了确切障碍，一个计划采样规则达到了条件性的 \(\tilde{O}(\sqrt{KT})\) 保证，其一个开放假设我们明确陈述。跨设置的全部复杂度总结在表3（附录B）。 我们明确校准这些论断。静态结果是对固定下限曝光公平性的重新推导，并非相对于 Fair-MAB 的新速率；建模贡献在于分块下限模型，其下限是周期特定的，在每个周期前揭示，并在该周期内满足。分离结果排除了最终计数和块独立替代方案，但不排除具有截止期限意识的动态惩罚，我们将其包含为基线。该框架的价值在于无需惩罚调优即可实现精确可行性，且遗憾由非强制预算 \(R\) 决定。 ## 相关工作 最接近的先前工作是 Fair-MAB 框架（Patil et al. 2020, 2021），该框架要求每个臂在每轮中接收规定比例的拉取（允许加性容差），并相对于公平感知比较器测量遗憾。我们的静态结果是基于差异对该保证的重新推导，而非速率改进，并且由于配额是预先加载的，DQ-UCB 以容差 1 满足相同的任意时刻下限（注13），但其目的是使舍入层明确，并将其推广到 Fair-MAB 未捕获的分块时变下限。 其他公平标准是互补而非直接可比的：任人唯贤（Joseph et al. 2016）、基于功绩的曝光（Wang et al. 2021）、Nash 社会福利（Barman et al. 2022）、最大最小公平性（Harada et al. 2025）、不确定性下的公平性（Lee et al. 2026）以及公平-性能前沿（Wilms and Heitz 2026），后者的帕累托观点与我们的封闭形式分析平行。更接近精确曝光的是具有显式组或上下文约束的工作（公平上下文赌博机（Chen et al. 2020）、具有组内功绩的双层组曝光（Pokhriyal et al. 2024）、超几何有限池排名下限（Cartier van Dissel et al. 2025）和图结构多正则化器公平性（Zhou et al. 2025）），以及通过交互代理（Manupriya et al. 2025; Xu et al. 2025; Krishnamurthy et al. 2026）或缓慢非平稳性（Shaarad and Dukkipati 2020）放松单个平稳学习器的工作，后者与我们的分块模型相邻。 另一条线通过预算、队列或对偶性强制执行约束（带背包的赌博机（Badanidiyuru et al. 2013）、凹奖励凸约束扩展（Agrawal and Devanur 2014）、组合睡眠赌博机中的虚拟队列公平性（Li et al. 2019）、修正索引最小速率公平性（Claure et al. 2020）以及用于在线分配的对偶镜像下降（Balseiro et al. 2020）），但这些仅保证渐近或平均可行性，而精确的每周期可行性正是我们模型作为原始假设的内容；一个具有截止期限意识的拉格朗日量代表了实验中基于惩罚的家族。这些工作均无法在无需惩罚调优的情况下确定性地强制执行时变分块级下限；精确的分块可行性、无调优设计以及匹配的极小极大下界的组合是本文特有的。 分析借鉴了标准赌博机工具：有限时间上置信界（UCB）（Auer et al. 2002; Han et al. 2024）；通过 KL 链式法则和 Pinsker 不等式的极小极大构造（Bubeck and Cesa-Bianchi 2012; Lattimore and Szepesvári 2020）；用于实例依赖下界的 Bretagnolle–Huber 形式；以及我们速率最优残差规则背后的 MOSS（Audibert and Bubeck 2009）和 kl-UCB++（Ménard and Garivier 2017）索引。时变需求下的分配是互补的（那里的下限未知，我们的是每个分块揭示的（Lyu and Cheung 2023）），多目标和偏好/风险混合（Davoodi and Maghsudi 2025; Tatlı et al. 2025a, b）共享我们帕累托曲线的混合结构。最后，舍入引擎是经典差异理论（Spencer 定理（Spencer 1985）、Banaszczyk 平衡（Banaszczyk 1998）、Bansal 的构造方法（Bansal 2010）、依赖舍入（Gandhi et al. 2006）、拟阵友好舍入（Bansal and Nagarajan 2016）以及在线向量平衡（Bansal et al. 2020; Altschuler and Tikhomirov 2025; Bednorz and Godlewski 2024）），其中我们使用 Beck–Fiala 定理作为重叠下限的核心工具，并将更难的在开放自适应规划问题中的在线结果与之关联。 ## 问题设置与差异简化 我们研究一个随机 \(K\) 臂赌博机，时间范围为 \(T\)。臂 \(i\) 产生 \([0,1]\) 中的独立奖励，均值为 \(\mu_i\)。令 \[ i^\star \in \operatorname{arg\,max}_{i \in [K]} \mu_i, \quad \mu_\star = \mu_{i^\star}, \quad \Delta_i = \mu_\star - \mu_i, \] 因此 \(\Delta_{i^\star} = 0\) 且对每个臂 \(i\)，\(\Delta_i \geq 0\)。符号总结在表2（附录A）中，所有证明推迟到技术附录。 对于目标曝光分数 \(\delta \in [0, 1/K]\)，整数下限为 \(m = \lfloor \delta T \rfloor\)，一个策略是 \(m\)-公平的，如果其最终拉取次数满足对每个臂 \(i \in [K]\) 有 \(N_i(T) \geq m\)（等价地，每个臂的经验曝光至少为 \(m/T \geq \delta - 1/T\)）。最优 \(m\)-公平分配、诱导的公平伪遗憾以及公平遗憾恒等式 \[ \widehat{\mathrm{Reg}}_m(T) = \sum_{i \neq i^\star} \Delta_i \bigl( N_i(T) - m \bigr), \] 表明公平遗憾是配额之外拉取的差距加权计数，这是下一节中分块对象的静态（\(B=1\)）特化；我们将其正式陈述推迟到附录C（引理10）。这个差距加权计数正是差异视图将使其可行的。 ### 曝光-差异恒等式 我们首先记录一个分数公平调度与一个整数拉取序列之间的差恰好是一个差异向量。在时间 \(t\) 的分数分配是一个向量 \(x_t \in \mathbb{R}^K\)，满足 \(x_{t,i} \geq 0\) 且 \(\sum_i x_{t,i} = 1\)，臂 \(i\) 的意图累积分数曝光为 \(S_i(T) = \sum_{t=1}^T x_{t,i}\)，一个确定性拉取 \(A_t\) 对应于标准基向量 \(e_{A_t}\)。定义差异向量 \[ D_T = \sum_{t=1}^T \bigl( e_{A_t} - x_t \bigr) = N(T) - S(T), \] 其中 \(N(T) = (N_1(T), \dots, N_K(T))\) 且 \(S(T) = (S_1(T), \dots, S_K(T))\)。 ###### 命题 1（曝光-差异恒等式） 固定任意分数调度 \(x_1, \dots, x_T\)。对于任意拉取序列 \(A_1, \dots, A_T\)，以下成立。 1. (i) 每个臂的曝光误差恰好是差异向量中相应坐标：\(N_i(T) - S_i(T) = D_{T,i}\)。因此，如果对每个 \(i\) 有 \(S_i(T) \geq m + B\) 且 \(\|D_T\|_\infty \leq B\)，则整数拉取序列是 \(m\)-公平的。 2. (ii) 相对于分数调度的奖励差距是一个加权差异：\(\sum_{t=1}^T \mu^\top x_t - \sum_{t=1}^T \mu_{A_t} = -\mu^\top D_T\)。 3. (iii) 因此，在公平下限约束下最小化奖励损失等价于... （原文在此处被截断，但根据上下文，应继续描述优化等价性。）