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

通信制約下の分散Thompson採样法

基本情報

論文ID: 2410.15543
タイトル: Distributed Thompson sampling under constrained communication
著者: Saba Zerefa, Zhaolin Ren, Haitong Ma, Na Li (ハーバード工学応用科学大学院)
分類: 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)などの情報論的概念を利用してアルゴリズム性能を限定

実験設定

テスト関数

2つの標準最適化テスト関数を使用：

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$
- 特性：多くの局所最大値と1つのグローバル最小値を有する

通信ネットワーク

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を計算

実験結果

主要結果

実験結果は理論予測を強く支持している：

接続性の影響：Rosenbrocおよび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|}}$

系3.4： $G_{max}$ を最大完全部分グラフとして選択すると： $R_{SB}(t) = \tilde{O}\left(\sqrt{\frac{1}{t|V_{max}|}}\right)$

収束性分析

順序単一エージェントThompson採样の $\tilde{O}(\sqrt{1/t})$ 後悔と比較して：

平均後悔改善係数： $\sqrt{\theta(G)/M}$
単純後悔改善係数： $\sqrt{1/|V_{max}|}$

結論と考察

主要結論

アルゴリズムの有効性：提案された分散Thompson採样アルゴリズムは、通信制約下の多エージェントベイズ最適化問題を効果的に解決できる
理論保証：通信グラフ構造に依存する後悔界限を確立し、連結グラフ下の収束優位性を証明
グラフ構造の重要性：通信グラフの接続性はアルゴリズム性能に顕著な影響を与える

限界

同期仮定：アルゴリズムは全体的な同期クロックを仮定しており、実際のアプリケーションでは非現実的である可能性がある
計算複雑性：高次元空間におけるargmax計算の効率問題は完全には解決されていない
カーネル関数選択：理論分析は特定のカーネル関数仮定に依存している

今後の方向性

非同期版：全体的な同期を必要としないアルゴリズム変体の開発
効率的な最適化：高次元Thompson採样におけるargmaxの効率的計算方法の研究
より厳密な界限：より厳密な後悔界限の探索
実際のアプリケーション：実際のマルチロボットまたはセンサネットワークシステムでのアルゴリズム検証

深層的評価

利点

理論的貢献が顕著：通信制約のある分散ベイズ最適化に初めて理論保証を提供
問題設定が実際的：現実における通信制約という重要な問題を考慮
分析が厳密：理論証明の構造が明確で、情報論的ツールを用いた深い分析
実験が十分に支持：数値実験は理論予測をよく検証している

不足点

実験規模が限定的：2次元テスト関数と比較的小規模なネットワークでのみ検証
実用性の考慮が不十分：同期仮定とargmax計算効率の問題は実際のアプリケーションを制限
比較実験の欠如：他の分散最適化手法との直接比較がない

影響力

理論的価値が高い：分散ベイズ最適化理論に重要な貢献
応用前景が広い：マルチロボット、IoTなどの分野で潜在的応用価値
拡張性が強い：後続研究のための堅実な理論基盤を提供

適用シナリオ

マルチロボット協調最適化タスク
分散センサネットワークパラメータ調整
エッジコンピューティング環境での協調学習
通信帯域幅が制限される並列最適化問題

総合評価：これは分散ベイズ最適化分野における重要な理論的貢献を有する高品質な論文である。著者らは巧妙にグラフ理論、情報論、ベイズ最適化を組み合わせ、実際に一般的な通信制約シナリオに対する理論保証を提供している。実用性の面ではまだ改善の余地があるが、その理論的価値と今後の研究への指導的意義は顕著である。