具有有界采样违规的分布式在线赌博机子模最大化

# 分布式在线赌博机次模最大化：具有有界采样违规  
来源：https://arxiv.org/html/2607.00680  
Bin Du  
College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China;\{iniesdu, liuch, zdq\.bpz\}@nuaa\.edu\.cn  
Dingqi Zhu  
11footnotemark:1  
Lintao Ye  
School of Artificial Intelligence and Automation at the Huazhong University of Science and Technology, Wuhan, China;yelintao93@hust\.edu\.cn  
Dengfeng Sun  
School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47906, USA;dsun@purdue\.edu  

###### 摘要  
我们研究了带有划分拟阵约束的分布式在线次模最大化问题，其中多个智能体依次从其各自子集中选择有限数量的动作，以最大化一系列目标函数的累积值。我们开发了一个统一的算法框架，能够适应全信息和赌博机反馈模型。对于这两种反馈模型，我们证明了所提算法实现了次线性 \(1-1/e\) 遗憾保证，这与现有集中式算法达到的结果相当。此外，为了解决由连续松弛和舍入引起的采样违规问题，我们提出了一种有界随机管道舍入方案，并证明采样违规的概率逐渐消失。因此，累积采样违规在 \(T\) 上保持次线性，并且我们进一步证明在某些条件下该结果无法改进。数值结果验证了本文的理论发现。  

## 1 引言  
次模最大化是广泛应用中的一个基本问题，例如传感器选择 [3 (https://arxiv.org/html/2607.00680#bib.bib2)]、资源分配 [22 (https://arxiv.org/html/2607.00680#bib.bib21)] 以及多智能体系统中的任务协调 [36 (https://arxiv.org/html/2607.00680#bib.bib22)]。在其一般形式中，该问题旨在在满足特定组合约束（如基数约束或拟阵约束）的条件下最大化一个集合函数。尽管具有广泛适用性，但这类问题已知为 NP 难 [10 (https://arxiv.org/html/2607.00680#bib.bib23)]，因此其精确解通常在计算上难以处理。为此，大量研究致力于开发具有可证明性能保证的高效近似算法。已有大量工作表明，通过基于贪心的方法或其连续变体，可以实现常数因子近似比，例如 \(1/2\) 或 \(1-1/e\) [20 (https://arxiv.org/html/2607.00680#bib.bib24), 11 (https://arxiv.org/html/2607.00680#bib.bib25), 26 (https://arxiv.org/html/2607.00680#bib.bib45)]。此外，除非 P=NP，否则这些保证被进一步证明是最优的 [10 (https://arxiv.org/html/2607.00680#bib.bib23)]。这一结果为设计算法提供了坚实的理论基础，使其能够在保持计算可行性的同时实现近乎最优的性能保证。

除了经典的集中式问题外，受多智能体网络大规模决策场景的推动，分布式次模最大化也引起了越来越多的关注（参见 e.g. [13 (https://arxiv.org/html/2607.00680#bib.bib19), 27 (https://arxiv.org/html/2607.00680#bib.bib44), 18 (https://arxiv.org/html/2607.00680#bib.bib26), 9 (https://arxiv.org/html/2607.00680#bib.bib20)]）。一类典型的分布式问题产生于智能体拥有分布式动作子集，且可行性通过耦合所有智能体决策的组合约束来强制执行（例如 [24 (https://arxiv.org/html/2607.00680#bib.bib29), 9 (https://arxiv.org/html/2607.00680#bib.bib20)]）。一个典型的例子是划分拟阵约束 [23 (https://arxiv.org/html/2607.00680#bib.bib12)]，其中全局动作集被划分给多个智能体，每个智能体只能从其局部集合中选择一个或少量动作。为了解决此类约束下的分布式次模最大化，文献 [24 (https://arxiv.org/html/2607.00680#bib.bib29)] 的作者提出了一种结合经典连续贪心算法（也称为 Frank-Wolfe 算法）与基于共识的协调方案的求解方法。然而，该方法依赖于次模目标函数多线性扩展的精确梯度评估，导致计算复杂度随动作集大小呈指数增长。为了解决这一问题，文献 [23 (https://arxiv.org/html/2607.00680#bib.bib12)] 的作者遵循相同的 Frank-Wolfe 框架，但利用梯度信息的经验估计，开发了一种分布式算法。结果表明，随着梯度估计样本数量的增加，近似比可以任意接近最优值 \(1-1/e\)。此外，我们之前的工作 [9 (https://arxiv.org/html/2607.00680#bib.bib20)] 提出了一种基于随机梯度的分布式算法，也显著降低了梯度评估的计算复杂度。然而，由于 [9 (https://arxiv.org/html/2607.00680#bib.bib20)] 中的算法完全在离散域中开发，其近似比仅能保证为 \(1/2\)，与在连续域中开发的算法相比是次优的。

另一类关于次模最大化的相关工作集中在在线设置上，其中一系列次模目标函数随时间逐步揭示，决策必须顺序做出，且无法访问未来信息。在此设置下，目标是设计一种在线算法，生成一系列决策以最大化时变目标函数的累积值。具体地，累积 \(\alpha\)-遗憾的概念（例如 \(\alpha=1/2\) 或 \(1-1/e\)）被用来刻画这类在线算法的性能。如果累积 \(\alpha\)-遗憾相对于时间范围 \(T\) 是次线性的，那么算法的时间平均性能渐近地匹配事后选择的 \(\alpha\)-次优解的性能。为此，文献 [25 (https://arxiv.org/html/2607.00680#bib.bib30)] 的作者通过在离散域中使用 *元动作* 技术，提出了第一个在线次模最大化算法。结果表明，该算法在基数约束下实现了 \(O(\sqrt{T})\) 的 \(1-1/e\) 遗憾。这一结果进一步被 [15 (https://arxiv.org/html/2607.00680#bib.bib31)] 扩展到具有划分拟阵约束的问题中。通过使用标准的提升技术，即将离散问题提升到连续域，然后进行适当的舍入方案，建立了相同的遗憾保证。事实上，文献 [25 (https://arxiv.org/html/2607.00680#bib.bib30)] 引入的元动作思想也已应用于在线连续次模最大化问题（参见 e.g. [6 (https://arxiv.org/html/2607.00680#bib.bib33), 5 (https://arxiv.org/html/2607.00680#bib.bib32), 33 (https://arxiv.org/html/2607.00680#bib.bib11)]）。特别是，Meta-Frank-Wolfe 算法首次在 [6 (https://arxiv.org/html/2607.00680#bib.bib33)] 中提出，并证明在一般凸集约束下能够重现 \(O(\sqrt{T})\) 的 \(1-1/e\) 遗憾。然而，这种方法的一个关键限制是它在每个时间步 \(t\) 需要 \(\sqrt{T}\) 次精确梯度评估，这在实际场景中可能代价过高。为了缓解这一问题，文献 [5 (https://arxiv.org/html/2607.00680#bib.bib32)] 使用随机梯度估计增强了 Meta-Frank-Wolfe 算法，并证明在温和条件下可以实现相同的遗憾结果。尽管如此，梯度评估的数量仍然为 \(O(\sqrt{T})\)，对于大规模问题可能仍然昂贵。受此挑战的启发，文献 [33 (https://arxiv.org/html/2607.00680#bib.bib11)] 开发了一种单次版本的在线算法，称为 Mono-Frank-Wolfe。结果表明，该算法将每个函数的梯度评估次数从 \(\sqrt{T}\) 减少到 1，并实现了 \(O(T^{4/5})\) 的 \(1-1/e\) 遗憾。此外，通过应用单点梯度估计器 [16 (https://arxiv.org/html/2607.00680#bib.bib17)]，文献 [33 (https://arxiv.org/html/2607.00680#bib.bib11)] 进一步将算法开发适应于赌博机反馈模型，并提出了第一种赌博机次模最大化方法，实现了 \(O(T^{8/9})\) 的 \(1-1/e\) 遗憾。更多相关工作可在 [34 (https://arxiv.org/html/2607.00680#bib.bib42), 21 (https://arxiv.org/html/2607.00680#bib.bib41), 30 (https://arxiv.org/html/2607.00680#bib.bib36)] 中找到。值得注意的是，通过使用标准的提升技术，上述连续算法都可以用于解决离散在线次模最大化问题。然而，这类方法的一个关键限制是它们可能需要评估在违反原始集合约束（例如划分拟阵或基数约束）的采样点处的函数值。事实上，文献 [33 (https://arxiv.org/html/2607.00680#bib.bib11)] 表明，不存在一种合适的舍入方案能够同时保证无偏梯度估计和所得离散样本的可行性。因此，文献 [33 (https://arxiv.org/html/2607.00680#bib.bib11)] 提出了响应式赌博机算法，该算法将零奖励分配给不可行样本，但仍然需要查询这些违规点的函数值。本文旨在解决采样违规问题。

最近，一些研究尝试同时处理分布式和在线设置下的次模最大化问题（参见 e.g. [35 (https://arxiv.org/html/2607.00680#bib.bib35), 31 (https://arxiv.org/html/2607.00680#bib.bib43), 32 (https://arxiv.org/html/2607.00680#bib.bib34)]）。文献 [35 (https://arxiv.org/html/2607.00680#bib.bib35)] 的作者考虑了分布式在线连续次模最大化问题，其中每个智能体观察一个局部目标函数序列，并且所有智能体受到一个共同的凸集约束。然后提出了两种分布式在线算法，并证明它们的 \(1-1/e\) 遗憾分别被上界为 \(O(T^{4/5})\) 和 \(O(\sqrt{T})\)。为了解决智能体间具有分离动作子集的分布式设置，我们之前的工作 [32 (https://arxiv.org/html/2607.00680#bib.bib34)] 在纯离散域中开发了一种在线分布式贪心算法，该算法本质上是实现 \(O(\sqrt{T})\) 的 \(1/2\) 遗憾。据作者所知，现有工作尚未解决在划分拟阵约束下实现最优 \(1-1/e\) 遗憾的分布式在线次模最大化问题。填补这一空白，正如我们下面详述的，需要比组合现有技术更多的工作。

本文的贡献总结如下：  
1. (i) 我们首先建立了在划分拟阵约束下的分布式在线次模最大化问题公式，然后提出了一种统一的算法框架，结合了提升技术与 Meta-Frank-Wolfe 算法，同时适应全信息和赌博机反馈模型。据作者所知，这是第一个针对该问题实现最优 \(1-1/e\) 遗憾的框架。  
2. (ii) 对于全信息和赌博机模型，我们分别建立了 \(O(T^{4/5})\) 和 \(O(T^{8/9})\) 的 \(1-1/e\) 遗憾界，这与已知的集中式速率相匹配，同时以完全分布式的方式在网络中运行。  
3. (iii) 为了解决由集合约束下的在线舍入导致的采样违规问题，我们引入了 *有界随机管道舍入* (B-SPR)，它将管道舍入推广到任意分数界，同时保留其和与单调性保证。将 B-SPR 嵌入到渐进有界方案 (PB-SPR) 中，然后驱动迭代点向拟阵顶点移动。我们证明每步违规概率为 \(O(T^{-1/9})\)，因此累积违规仅次线性增长为 \(O(T^{7/9})\)。匹配的 \(\Omega(T^{7/9})\) 下界证明该速率在某些条件下不可改进。  

记号：整数集和实数集分别记为 \(\mathbb{Z}\) 和 \(\mathbb{R}\)。对于任意给定整数 \(n\in \mathbb{Z}_{\geq 1}\)，令 \([n]:=\{1,2,\cdots,n\}\)，并用 \(\mathbf{1}_n\) 表示 \(n\) 维全1向量。对于集合 \(S\)，令 \(|S|\) 表示集合的基数。对于两个向量 \(\mathbf{x},\mathbf{y}\in \mathbb{R}^n\)，不等式 \(\mathbf{x}\preceq \mathbf{y}\) 按元素定义。\(\mathbbm{1}\{\cdot\}\) 表示指示函数。  

## 2 问题陈述与预备知识  
### 2.1 分布式在线次模最大化  
考虑一个由 \(I\) 个智能体组成的网络，每个智能体 \(i\in [I]\) 维护一个局部动作子集 \(\mathcal{A}_i \subseteq \mathcal{A}:=\cup_{i=1}^{I} \mathcal{A}_i\)，其中 \(|\mathcal{A}_i|=N_i\) 且 \(|\mathcal{A}|=N\)。每个智能体的目标是从 \(\mathcal{A}_i\) 中选择最多 \(\kappa_i \in \mathbb{Z}_{\geq 1}\) 个动作，使得一系列时变甚至 *对抗性* 的目标函数 \(f^1(\mathcal{S}), f^2(\mathcal{S}), \cdots, f^T(\mathcal{S})\) 在时间范围 \(T\in \mathbb{Z}_{\geq 1}\) 上被合作最大化。该问题可以表述为分布式最大化问题：  
\[
\max_{\mathcal{S}} f^t(\mathcal{S}) \quad \text{(1a)}  
\text{subject to } \mathcal{S} \in \mathcal{I}:=\{\mathcal{S} \mid |\mathcal{S}\cap \mathcal{A}_i| \leq \kappa_i, \; i\in [I]\}. \tag{1b}
\]  
注意，通过假设 \(\mathcal{A}_i \cap \mathcal{A}_j = \emptyset, \; \forall i\neq j\)，式 (1b) 中的集合 \(\mathcal{I}\) 被称为 *划分拟阵* [24 (https://arxiv.org/html/2607.00680#bib.bib29)]。此外，我们假设每个函数 \(f^t(\cdot): 2^{\mathcal{A}} \to \mathbb{R}_{\geq 0}\) 是 *单调*、*次模* 和 *归一化* 的，其定义如下。  

###### 定义 1 (单调性). 一个集合函数 \(f(\cdot)\) 是单调非减的，如果对于 \(\forall \mathcal{S}_1 \subseteq \mathcal{S}_2 \subseteq \mathcal{A}\)，有 \(f(\mathcal{S}_1) \leq f(\mathcal{S}_2)\)。  

###### 定义 2 (次模性). 一个集合函数 \(f(\cdot)\) 是次模的，如果对于 \(\forall \mathcal{S}_1 \subseteq \mathcal{S}_2 \subseteq \mathcal{A}\) 和 \(\forall a \in \mathcal{A}\setminus \mathcal{S}_2\)，有 \(f(\{a\}\cup \mathcal{S}_1) - f(\mathcal{S}_1) \geq f(\{a\}\cup \mathcal{S}_2) - f(\mathcal{S}_2)\)。  

除了单调性和次模性外，集合函数通常是 *归一化* 的，即 \(f(\emptyset)=0\)。