2025-11-25T01:19:18.327955

Distributed Thompson sampling under constrained communication

Zerefa, Ren, Ma et al.

In Bayesian optimization, a black-box function is maximized via the use of a surrogate model. We apply distributed Thompson sampling, using a Gaussian process as a surrogate model, to approach the multi-agent Bayesian optimization problem. In our distributed Thompson sampling implementation, each agent receives sampled points from neighbors, where the communication network is encoded in a graph; each agent utilizes their own Gaussian process to model the objective function. We demonstrate theoretical bounds on Bayesian average regret and Bayesian simple regret, where the bound depends on the structure of the communication graph. Unlike in batch Bayesian optimization, this bound is applicable in cases where the communication graph amongst agents is constrained. When compared to sequential single-agent Thompson sampling, our bound guarantees faster convergence with respect to time as long as the communication graph is connected. We confirm the efficacy of our algorithm with numerical simulations on traditional optimization test functions, demonstrating the significance of graph connectivity on improving regret convergence.

academic

Distributed Thompson sampling under constrained communication

基本信息

论文ID: 2410.15543
标题: Distributed Thompson sampling under constrained communication
作者: Saba Zerefa, Zhaolin Ren, Haitong Ma, Na Li (Harvard School of Engineering and Applied Sciences)
分类: cs.LG cs.SY eess.SY math.OC stat.ML
发表时间: 2025年1月1日 (arXiv v3)
论文链接: https://arxiv.org/abs/2410.15543

摘要

本文研究在通信受限条件下的多智能体贝叶斯优化问题。作者提出了一种分布式Thompson采样算法，使用高斯过程作为代理模型。在该实现中，每个智能体从邻居接收采样点，通信网络用图结构编码；每个智能体利用自己的高斯过程来建模目标函数。论文证明了贝叶斯平均后悔和贝叶斯简单后悔的理论界限，该界限依赖于通信图的结构。与批量贝叶斯优化不同，该界限适用于智能体间通信图受限的情况。与顺序单智能体Thompson采样相比，只要通信图连通，该算法保证了更快的时间收敛性。

研究背景与动机

问题定义

本文要解决的核心问题是在通信受限的多智能体系统中进行黑盒函数优化。具体来说：

黑盒随机优化挑战：在目标函数不显式已知且只能通过噪声评估访问的情况下，需要找到函数的最大值
多智能体协作需求：多个智能体可以并行采样目标函数，但彼此间的通信可能受到限制
通信约束现实性：在实际应用中（如多机器人源搜索、传感器网络），智能体可能无法访问所有其他智能体的信息

研究重要性

该问题在多个重要领域有广泛应用：

机器学习中的超参数调优
基于仿真的优化
实验设计
多机器人系统
传感器网络优化

现有方法局限性

集中式方法不适用：需要中央协调器管理所有智能体数据，在分布式场景中不现实
批量贝叶斯优化假设过强：假设所有智能体都能访问相同信息，不符合通信受限的实际情况
现有理论保证要求苛刻：先前提供理论保证的分布式贝叶斯优化文献要求完全连通的通信图

研究动机

作者的出发点是开发一种能够在任意通信图结构下工作的分布式贝叶斯优化算法，并提供相应的理论保证。

核心贡献

提出分布式Thompson采样算法：针对通信受限的多智能体贝叶斯优化问题设计了新算法
建立理论界限：
- 贝叶斯平均后悔界限： $\tilde{O}\left(\sqrt{\frac{\theta(G)}{\sqrt{Mt}}}\right)$
- 贝叶斯简单后悔界限： $\tilde{O}\left(\sqrt{\frac{1}{t|V_{max}|}}\right)$
图结构依赖分析：界限依赖于通信图的团覆盖数 $\theta(G)$ 和最大完全子图大小 $|V_{max}|$
收敛性保证：证明了在连通通信图下比顺序单智能体方法收敛更快
数值验证：在标准优化测试函数上验证了算法有效性

方法详解

任务定义

对于紧集 $X \subset \mathbb{R}^d$ ，考虑未知连续函数 $f: X \rightarrow \mathbb{R}$ ，目标是找到其最大值。设有 $M$ 个智能体，每个都可以查询 $f$ 并接收噪声观测 $y = f(x) + \epsilon$ ，其中 $\epsilon \sim \mathcal{N}(0, \sigma_\epsilon^2)$ 。

通信网络用图 $G = (V,E)$ 描述，其中 $|V| = M$ ，边 $(i,j) \in E$ 表示智能体 $i$ 和 $j$ 可以通信。智能体 $i$ 在时间 $t$ 可访问的数据为 $D_{t,i} = \{(x_{\tau,j}, y_{\tau,j})\}_{j \in \mathcal{N}(i) \cup \{i\}, \tau < t}$ 。

模型架构

高斯过程建模

每个智能体 $i$ 使用独立的高斯过程 $GP_{t,i}$ 来建模目标函数： $f | \mathcal{F}_{D_{t,i}} \sim GP_{t,i}(\mu_{D_{t,i}}(x), k_{D_{t,i}}(x,x'))$

其中：

$\mu_{D_t}(x) = k_t(x)^T(K_{D_t} + \sigma_n^2 I)^{-1}y_{D_t}$
$k_{D_t}(x,x') = k(x,x') - k_{D_t}(x)^T(K_{D_t} + \sigma_n^2 I)^{-1}k_{D_t}(x')$

分布式Thompson采样算法

算法1：分布式Thompson采样

1. 对f设置GP先验
2. 初始化：对i=1,...,M，设置初始数据D_{1,i}和GP_{0,i}
3. 对t=1,...,T：
   对i=1,...,M：
   a) 基于D_{t,i}更新后验GP_{t,i}
   b) 从GP_{t,i}采样函数实现：f̂_{t,i} ~ GP_{t,i}
   c) 选择查询点：x_{t,i} = argmax_x f̂_{t,i}(x)
   d) 观测y_{t,i}
   e) 向邻居广播(x_{t,i}, y_{t,i})
   f) 从邻居收集评估C_{t,i}
   g) 更新数据历史：D_{t+1,i} = D_{t,i} ∪ C_{t,i} ∪ {(x_{t,i}, y_{t,i})}

技术创新点

无中央协调器设计：每个智能体独立维护自己的GP模型，避免了集中式方法的瓶颈
通信图结构利用：理论分析巧妙地将通信图分解为不相交的完全子图，并分别分析每个子图的性能
信息论分析框架：利用最大信息增益(MIG)等信息论概念来界定算法性能

实验设置

测试函数

使用两个标准优化测试函数：

Rosenbrock函数： $f(x,y) = (1-x)^2 + 100(y-x^2)^2$ $f (x, y) = (1 - x)^{2} + 100 (y - x^{2})^{2}$
- 特点：包含一个大的山谷，全局最小值位于其中
Ackley函数： $f(x,y) = -20\exp(-0.2\sqrt{\frac{x^2+y^2}{2}}) - \exp(\frac{1}{2}(\cos(2\pi x) + \cos(2\pi y))) + 20 + e$ $f (x, y) = - 20 exp (- 0.2 \frac{x ^{2} + y ^{2}}{2}) - exp (\frac{1}{2} (cos (2 π x) + cos (2 π y))) + 20 + e$
- 特点：有许多局部最大值和一个全局最小值

通信网络

使用Erdős-Rényi随机图，包含20个智能体，连接概率分别为0.2、0.4和0.6。

评价指标

瞬时平均后悔： $R^A(t) = \frac{1}{M}\sum_{i=1}^M (f^* - f(x_{t,i}))$
瞬时简单后悔： $R^S(t) = f^* - \max_{i,\tau} f(x_{t,i})$
累积后悔：上述指标的时间累积

实现细节

使用BOTorch包实现
高斯过程使用Matérn核（ $\nu = 5/2$ ）
运行50个时间步
通过网格搜索计算argmax

实验结果

主要结果

实验结果强烈支持理论预测：

连接性影响：在Rosenbrock和Ackley函数上，连接概率越高的图（0.6 > 0.4 > 0.2）获得更好的后悔收敛性能
一致性表现：该趋势在瞬时简单后悔和平均后悔指标上都得到验证
算法有效性：分布式Thompson采样成功找到了两个测试函数的极值

理论验证

数值结果验证了理论分析的核心预测：

高连接性通信图带来更好的性能
图结构对算法收敛速度有显著影响

理论分析

主要定理

定理3.1（贝叶斯平均后悔界限）：设 $\{G_k\}_{k \in \{1,...,n\}}$ 为通信图 $G$ 的 $n$ 个不相交完全子图的集合，则 $t$ 步后的贝叶斯平均后悔满足： $R_{AB}(t) \leq \frac{1}{M}\sum_{k=1}^n |V_k|\left(\frac{C_1}{t|V_k|} + \sqrt{\frac{C_2\xi_{|V_k|}\beta_t\Psi_{t|V_k|}}{t|V_k|}}\right)$

推论3.2：选择 $n$ 为图 $G$ 的团覆盖数 $\theta(G)$ ，得到： $R_{AB}(t) = \tilde{O}\left(\sqrt{\frac{\theta(G)}{\sqrt{Mt}}}\right)$

定理3.3（贝叶斯简单后悔界限）：设 $G_s = (V_s, E_s)$ 为 $G$ 的完全子图，则： $R_{SB}(t) \leq \frac{C_1}{t|V_s|} + \sqrt{\frac{C_2\xi_{|V_s|}\beta_t\Psi_{t|V_s|}}{t|V_s|}}$