A Federated Online Restless Bandit Framework for Cooperative Resource Allocation
원문 초록
Restless multi-armed bandits (RMABs) have been widely utilized to address resource allocation problems with Markov reward processes (MRPs). Existing works often assume that the dynamics of MRPs are known prior, which makes the RMAB problem solvable from an optimization perspective. Nevertheless, an efficient learning-based solution for RMABs with unknown system dynamics remains an open problem. In this paper, we study the cooperative resource allocation problem with unknown system dynamics of MRPs. This problem can be modeled as a multi-agent online RMAB problem, where multiple agents collaboratively learn the system dynamics while maximizing their accumulated rewards. We devise a federated online RMAB framework to mitigate the communication overhead and data privacy issue by adopting the federated learning paradigm. Based on this framework, we put forth a Federated Thompson Sampling-enabled Whittle Index (FedTSWI) algorithm to solve this multi-agent online RMAB problem. The FedTSWI algorithm enjoys a high communication and computation efficiency, and a privacy guarantee. Moreover, we derive a regret upper bound for the FedTSWI algorithm. Finally, we demonstrate the effectiveness of the proposed algorithm on the case of online multi-user multi-channel access. Numerical results show that the proposed algorithm achieves a fast convergence rate of $\mathcal{O}(\sqrt{T\log(T)})$ and better performance compared with baselines. More importantly, its sample complexity decreases with the number of agents.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem
낮은 자기상관 이진 수열 문제(LABS)는 통신, 신호 처리, 위성 항법 분야에서 중요한 응용을 갖는 어려운 조합 최적화 과제이다. 본 논문은 LABS 탐색 공간의 제한 클래스에 걸쳐 계산 노력을 적응적으로 배분하기 위해 Thompson 샘플링과 병렬 자기회피 보행(self-avoiding walk)을 결합한 하이브리드 탐색 프레임워크를 제안한다. 파티션을 다중 팔 밴딧(multi-armed bandit) 설정의 팔(arm)로 모델링함으로써, 제안된 방법은 덜 샘플링된 영역의 탐험(exploration)을 유지하면서도 경험적으로 더 높은 성능 지수(merit factor)를 산출하는 파티션 쪽으로 탐색 자원을 동적으로 전환한다. 이 접근법은 GPU 병렬 실행, 공유 사후 업데이트, 효율적인 이웃 평가, 그리고 사이클 방지를 위한 블룸 필터(Bloom filter)를 통해 추가로 가속된다. 또한 제약된 분할 비대칭 공간(partitioned skew-symmetric space)을 먼저 탐색한 후 비제약 공간에서 최적 후보를 정제하는 2단계 최적화 전략을 사용한다. 긴 이진 수열에 대한 실험 결과, 제안된 방법은 $450 \le L \le 527$ 범위의 35개 수열 길이와 $L=573$에 대해 이전에 알려진 최선의 결과를 개선하였다. 특히 $L=451$에서 성능 지수 8.0을 초과하는 새로운 최장 수열을 보고한다. 결과는 또한 Thompson 샘플링이 더 나은 관측 성능을 보이는 파티션을 효과적으로 우선시함을 보여주며, LABS 최적화에서 온라인 데이터 기반 자원 배분의 가치를 확인한다. 전반적으로 제안된 프레임워크는 고성능 성능 지수 최대화를 위한 확장 가능하고 효과적인 전략을 제공한다.
Link Adaptation Using Joint-Thompson Sampling
Class-Grouped Normalized Momentum and Faster Hyperparameter Exploration to Tackle Class Imbalance in Federated Learning
Revisiting Decentralized Online Convex Optimization with Compressed Communication
절댓값 섭동을 통한 선형 밴딧의 무작위 탐험
Randomized Exploration for Linear Bandits via Absolute Perturbations
확률적 선형 밴딧(stochastic linear bandits)에서 표준적인 상한 신뢰 구간(UCB) 알고리즘은 간단한 빈도주의 후회(regret) 분석을 허용하지만 계산 비용이 클 수 있는 반면, 톰슨 샘플링(Thompson Sampling, TS)은 계산 효율이 높지만 낙관적이지 않은 특성으로 인해 분석이 일반적으로 더 어렵다. 본 논문에서는 부호 있는 탐험(exploration) 노이즈를 절댓값으로 대체함으로써 기댓값 측면에서 낙관성을 보장하는 TS의 간단한 변형인 절댓값 톰슨 샘플링(Absolute Thompson Sampling, ATS)을 제안한다. 이는 TS의 계산 효율성을 유지하면서 TS 분석에서 흔히 요구되는 기술적으로 복잡한 반집중(anti-concentration) 논증을 피할 수 있어, UCB 방식의 단순한 후회 분석이 가능하다. ATS가 $\tilde{O}(d^{3/2}\sqrt{K})$의 후회를 달성함을 보이며, 이는 선형 밴딧에서 TS에 대한 기존 경계와 일치한다. 나아가 앙상블(ensemble) 크기로 정규화(normalization)하여 여러 절댓값 섭동에 대한 최댓값을 취하는 앙상블 절댓값 톰슨 샘플링(Ensemble Absolute Thompson Sampling, EATS)을 도입한다. 앙상블 크기가 커질수록 EATS는 UCB 목적함수로 수렴하여 극한에서 UCB 동작을 회복한다. 실험 결과, 중간 크기의 앙상블만으로도 이미 강력한 성능을 발휘함을 보인다. 본 결과는 이론과 실제 모두에서 무작위 탐험과 결정론적 낙관주의 사이의 가교를 제시한다.
AdaPrivate-TS: Private Thompson Sampling for Contextual Bandits with Privacy Amplification
우리는 Thompson Sampling과 배치 zCDP 합성을 결합한 차등 프라이버시(differentially private) 문맥적 밴딧 알고리즘인 AdaPrivate-TS를 제안한다. 핵심 통찰은 차등 프라이버시 노이즈가 사후 공분산을 구조적인 방식으로 팽창시킨다는 점이다. 즉, $b$에 가우시안 노이즈 $N(0,σ^2 I)$를 추가하면 샘플링 공분산이 $v^2 A^{-1} + σ^2 A^{-2}$가 되며, Thompson Sampling은 이를 순수한 손상이 아닌 불확실성 증가로 해석한다. 확률적 문맥 하에서의 이벤트 수준 프라이버시(개별 상호작용 보호)의 경우, 병렬 합성이 배치 전반에 걸쳐 노이즈를 분산시키기 때문에 프라이버시 비용이 $T$에 대해 로그 스케일인 $O(\sqrt{d}\,\log T/\sqrt{ρ})$에 불과함을 증명한다. 또한, 엄격한 프라이버시 예산에서 유효 노이즈를 줄일 수 있는 푸아송 서브샘플링을 통한 프라이버시 증폭을 탐구한다. 합성 및 실세계 데이터셋에 대한 실험 결과는 다음을 보여준다. (1) AdaPrivate-TS는 $\varepsilon \in [0.5, 5]$에서 비공개 성능의 93-99%를 달성하며, UCB 대비 0.5-3.7%, 극단적인 $\varepsilon$에서 적응형 탐험 튜닝 시 최대 18%까지 성능을 능가한다. (2) 프라이버시 증폭은 낮은 $\varepsilon$에서 추가적으로 2-5%의 성능 향상을 제공한다. (3) MovieLens 및 Jester에서 AdaPrivate-TS는 이벤트 수준 기준 모델 중 전반적으로 최고 성능을 달성하며 $\varepsilon \geq 2$에서 지배적이다. (4) DP-SVD 비공개 특징 하에서 UCB 대비 Thompson Sampling의 우위가 +11%까지 증가하며, 이는 노이즈-불확실성 해석이 보상 프라이버시에만 국한되지 않음을 확인한다. 우리는 인터랙티브 zCDP 합성 하에서의 프라이버시 보장에 대한 엄밀한 증명과 수렴 곡선, 12-시드 신뢰구간, DP-SVD 특징 절제 실험을 포함한 포괄적인 평가를 제공한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.