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 (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 샘플링 알고리즘을 제안한다. 이 구현에서 각 에이전트는 이웃으로부터 샘플 포인트를 수신하며, 통신 네트워크는 그래프 구조로 인코딩되고, 각 에이전트는 자신의 가우스 과정을 이용하여 목적 함수를 모델링한다. 논문은 베이지안 평균 후회(regret)와 베이지안 단순 후회의 이론적 경계를 증명하며, 이 경계는 통신 그래프의 구조에 의존한다. 배치 베이지안 최적화와 달리, 이 경계는 에이전트 간 통신 그래프가 제한된 경우에 적용된다. 순차적 단일 에이전트 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|}}$

따름정리 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의 효율적 계산 방법 연구
더 타이트한 경계: 더 타이트한 후회 경계 탐색
실제 응용: 실제 다중 로봇 또는 센서 네트워크 시스템에서 알고리즘 검증

심층 평가

장점

이론적 기여의 중요성: 통신 제약이 있는 분산 베이지안 최적화에 대한 이론적 보장을 처음으로 제공
현실적 문제 설정: 실제 통신 제약의 중요한 문제를 고려
엄밀한 분석: 이론적 증명이 구조적으로 명확하며, 정보 이론적 도구를 활용한 심층 분석
충분한 실험 지원: 수치 실험이 이론적 예측을 잘 검증

부족한 점

제한된 실험 규모: 2D 테스트 함수와 소규모 네트워크에서만 검증
실용성 고려 부족: 동기화 가정과 argmax 계산 효율성 문제가 실제 응용을 제한
비교 실험 부재: 다른 분산 최적화 방법과의 직접적 비교 실험 부족

영향력

높은 이론적 가치: 분산 베이지안 최적화 이론에 중요한 기여
광범위한 응용 전망: 다중 로봇, IoT 등 분야에서 잠재적 응용 가치
강한 확장성: 후속 연구를 위한 견고한 이론적 기초 제공

적용 시나리오

다중 로봇 협력 최적화 작업
분산 센서 네트워크 파라미터 튜닝
엣지 컴퓨팅 환경에서의 협력 학습
통신 대역폭이 제한된 병렬 최적화 문제

종합 평가: 이는 분산 베이지안 최적화 분야에서 중요한 이론적 기여를 하는 고품질 논문이다. 저자들은 그래프 이론, 정보 이론, 베이지안 최적화를 교묘하게 결합하여 실제에서 흔히 마주치는 통신 제약 시나리오에 대한 이론적 보장을 제공한다. 실용성 측면에서는 개선의 여지가 있지만, 이론적 가치와 향후 연구에 대한 지도적 의미는 상당하다.