arXiv:2403.17247

DASA: Delay-Adaptive Multi-Agent Stochastic Approximation

Nicolò Dal Fabbro, Arman Adibi, H. Vincent Poor, Sanjeev R. Kulkarni, Aritra Mitra, George J. Pappas

제출 2024-03-25

원문 초록

We consider a setting in which $N$ agents aim to speedup a common Stochastic Approximation (SA) problem by acting in parallel and communicating with a central server. We assume that the up-link transmissions to the server are subject to asynchronous and potentially unbounded time-varying delays. To mitigate the effect of delays and stragglers while reaping the benefits of distributed computation, we propose \texttt{DASA}, a Delay-Adaptive algorithm for multi-agent Stochastic Approximation. We provide a finite-time analysis of \texttt{DASA} assuming that the agents' stochastic observation processes are independent Markov chains. Significantly advancing existing results, \texttt{DASA} is the first algorithm whose convergence rate depends only on the mixing time $\tau_{mix}$ and on the average delay $\tau_{avg}$ while jointly achieving an $N$-fold convergence speedup under Markovian sampling. Our work is relevant for various SA applications, including multi-agent and distributed temporal difference (TD) learning, Q-learning and stochastic optimization with correlated data.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.06935v1math.OC공통 태그 Stochastic Optimization, Q-Learning

강화학습의 수학적 방법론

Mathematical methods of reinforcement learning

강화학습(RL)은 확률론, 최적화, 작용소 이론의 도구들에 점점 더 깊이 기반을 두고 있다. 이 서베이는 현대 강화학습 알고리즘의 설계와 분석을 뒷받침하는 수학적 구조를 체계적으로 정리한다. 마르코프 결정 과정(MDP)과 벨만 작용소(Bellman operator)에서 출발하여, 수렴 보장과 수렴 속도를 이끌어 내는 수축 사상(contraction mapping), 단조성(monotonicity), 고정점 이론을 가치 반복(value iteration), 정책 반복(policy iteration), 시간차(temporal-difference) 방식에 걸쳐 강조한다. 이어서 최적화 관점을 전개하는데, 확률적 근사(stochastic approximation)와 마팅게일(martingale) 방법, 볼록 쌍대성(convex duality), 그리고 미러/근위(mirror/proximal) 방법과 정규화의 연결 관계를 다룬다. 함수 근사(function approximation)는 선형 및 비선형 설정 모두를 다루며, 안정화(stabilization), 오차 분해(error decomposition), 그리고 종속 데이터 및 혼합 과정에 대한 집중 부등식(concentration inequality)을 통한 샘플 복잡도(sample complexity)를 포함한다. 나아가 오프-정책 평가/학습, 제약 강화학습과 제약 MDP(CMDP)를 다룬다. 전반에 걸쳐 공통된 작용소 및 변분적 관점 하에 알고리즘 템플릿을 통합하고, 유한 샘플 경계와 점근적 결과를 함께 조명한다. 이 논문은 강화학습에 관심 있는 확률론, 최적화, 통계학 연구자들에게 통합된 수학적 진입점을 제공하고자 한다.

arXiv:2606.20356v1math.OC공통 태그 Stochastic Optimization, Q-Learning

공통 노이즈의 바서슈타인 불확실성 하의 평균장 제어를 위한 강건한 $Q$-학습

Robust $Q$-learning for mean-field control under Wasserstein uncertainty in common noise

본 논문에서는 공통 노이즈 법칙의 바서슈타인 불확실성 하의 이산 시간 평균장 제어 문제를 위한 강건한 $Q$-학습 알고리즘을 제시합니다. 이 알고리즘은 양자화 및 투영 기법을 공통 노이즈 공간에서의 바서슈타인 쌍대 재정식화와 결합합니다. 우리는 동기식 및 비동기식 학습 방식 모두에 대해 수렴성과 유한 시간 반복 경계를 확립합니다. 시스템 리스크 및 전염병 모델에 대한 수치 실험은 비동기식 구현을 이상적인 벨만 반복과 비교하고, 공통 노이즈 오지정 하에서의 강건성-성능 트레이드오프를 보여주며, 비동기식 $Q$-학습 알고리즘의 관찰된 수렴 거동을 보고합니다.

arXiv:2606.18183v1stat.ML공통 태그 Stochastic Optimization, Q-Learning

마르코프 노이즈 하에서 선형 특징을 갖는 시간차 학습을 위한 확산 근사

A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noise

선형 함수 근사를 사용한 시간차(TD) 학습은 정책 평가의 핵심 방법입니다. 이에 대한 고전적인 연속 시간 기술은 상미분 방정식(ODE)으로, 점근적 평균 역학은 포착하지만 오차 바닥을 결정하는 확률적 변동은 무시합니다. 우리는 마르코프 노이즈 하에서 선형 TD(0)에 대한 확률 미분 방정식(SDE) 근사를 소개합니다. 결과 모델은 사영된 벨만 연산자에 의해 지배되는 수축 역학을 마르코프 샘플링의 영향과 구별합니다. 그 결과, 이 모델은 마르코프 장기 공분산과 사영된 벨만 연산자의 수축 기하학 사이의 상호작용을 통해 고정 스텝 사이즈 오차 바닥을 설명합니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.