arXiv:2402.11800

Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling

Arman Adibi, Nicolo Dal Fabbro, Luca Schenato, Sanjeev Kulkarni, H. Vincent Poor, George J. Pappas, Hamed Hassani, Aritra Mitra

제출 2024-02-19

원문 초록

Motivated by applications in large-scale and multi-agent reinforcement learning, we study the non-asymptotic performance of stochastic approximation (SA) schemes with delayed updates under Markovian sampling. While the effect of delays has been extensively studied for optimization, the manner in which they interact with the underlying Markov process to shape the finite-time performance of SA remains poorly understood. In this context, our first main contribution is to show that under time-varying bounded delays, the delayed SA update rule guarantees exponentially fast convergence of the \emph{last iterate} to a ball around the SA operator's fixed point. Notably, our bound is \emph{tight} in its dependence on both the maximum delay $\tau_{max}$, and the mixing time $\tau_{mix}$. To achieve this tight bound, we develop a novel inductive proof technique that, unlike various existing delayed-optimization analyses, relies on establishing uniform boundedness of the iterates. As such, our proof may be of independent interest. Next, to mitigate the impact of the maximum delay on the convergence rate, we provide the first finite-time analysis of a delay-adaptive SA scheme under Markovian sampling. In particular, we show that the exponent of convergence of this scheme gets scaled down by $\tau_{avg}$, as opposed to $\tau_{max}$ for the vanilla delayed SA rule; here, $\tau_{avg}$ denotes the average delay across all iterations. Moreover, the adaptive scheme requires no prior knowledge of the delay sequence for step-size tuning. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms, including TD learning, Q-learning, and stochastic gradient descent under Markovian sampling.

함께 살펴볼 논문

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

arXiv:2609.27664v1cs.AI공통 태그 Q-Learning, Multi-agent Reinforcement Learning

진화적 안정성이 학습 도달 가능성을 보장하지는 않는다: 협력 창발에 대한 다중 에이전트 강화학습 관점

Evolutionary Stability Does Not Guarantee Learning Accessibility: A Multi-Agent Reinforcement Learning Perspective on Cooperation Emergence

협력의 창발(cooperation emergence)은 탈중앙화된 에이전트(decentralized agent)들이 다른 에이전트들의 변화하는 행동에 적응하면서 동시에 조정을 이루어야 하므로 다중 에이전트 시스템에서 핵심적인 문제입니다. 진화 게임 이론(evolutionary game theory)은 전략적으로 안정한 결과를 규명하지만, 집단 조정 동역학 하에서의 안정성이 유한 샘플 학습 에이전트들이 국소적 보상(reward) 피드백을 통해 동일한 결과에 도달할 수 있음을 반드시 의미하지는 않습니다. 본 연구에서는 정부, 플랫폼 기업, 사용자가 참여하는 투명한 거버넌스 동기 기반의 3인 에이전트 게임에서 이러한 차이를 탐구합니다. 고정된 스테이지 게임 유인에 대한 복제자 동역학(replicator dynamics)을 도출하고, 대칭적인 초기 조건 그리드에서 협력적 진화 유역(evolutionary basin)을 평가하며, 이를 세 가지 탈중앙화 가치 기반 학습자에 대한 학습 유역 추정치와 비교합니다. 학습 분석에서는 동일한 보수 환경(payoff environment) 및 결과 기준 하에서 $\varepsilon$-탐욕적(greedy) 행동 선택을 사용하는 독립 Q-학습(independent Q-learning), 스케일링된 볼츠만 탐험(scaled Boltzmann exploration), 그리고 SA--EA BQL을 활용합니다. 샘플링된 그리드에서 진화 유역의 체적은 $V_E=1.00$입니다. 실증적 학습 유역은 $\varepsilon$-IQL의 경우 $0.88$인 반면, 스케일링된 볼츠만 및 SA--EA BQL의 경우 모두 $0.00$입니다. 진단 추적 결과는 이 고정된 구성에서 더 넓은 행동 다양성과 0이 아닌 가치 분리가 협력적 결합 행동을 유지하지 못하는 실패와 공존할 수 있음을 보여줍니다. 이러한 결과는 진화적 안정성과 학습 도달 가능성(learning accessibility)이 결합된 게임-학습 시스템의 구별되는 속성임을 나타냅니다. 공유 자전거 환경은 동기 부여를 위한 적용 사례이며, 더 광범위한 기여는 명시된 다중 에이전트 학습 동역학 하에서 집단 수준의 안정성과 협력의 유한 샘플 도달 가능성을 비교하기 위한 프레임워크를 제공하는 것입니다.

arXiv:2607.21876v1cs.LG공통 태그 Q-Learning, Multi-agent Reinforcement Learning

정적 및 시변 네트워크에서의 분산 감소 Q-학습

Variance-Reduced Q-Learning over Static and Time-Varying Networks

동일한 마르코프 결정 과정(MDP)과 상호작용하는 여러 에이전트가 포함된 분산형 강화학습 문제를 조사한다. 에이전트는 네트워크를 통해 정보를 교환하여 최적 상태-행동 가치 함수를 공동으로 학습할 수 있다. 이 설정을 위해, 각 에포크 내에서 에이전트가 벨만 최적성 연산자를 국소적으로 추정하고 합의 기반 프로토콜을 사용하여 정보를 확산하는 VRDQ라는 새로운 에포크 기반 분산 $Q$-학습 알고리즘을 제안한다. 정적 및 시변 네트워크 모두에 대해, 협력으로부터 선형 속도 향상(linear speedups)을 누리는 VRDQ의 고확률 유한 시간 수렴률을 확립한다. 중요하게도, 표본 복잡도(sample-complexity)에서의 이러한 속도 향상이 $\tilde{O}(1)$의 통신만을 필요로 함을 증명하며, 이는 기존 연구의 통신 비용을 크게 개선한다.

arXiv:2601.17454v2cs.MA공통 태그 Q-Learning, Multi-agent Reinforcement Learning

표 형식 다중 에이전트 Q-러닝에서 체화에 의해 유도되는 협조 체제

Embodiment-Induced Coordination Regimes in Tabular Multi-Agent Q-Learning

중앙화된 가치 학습은 다중 에이전트 강화학습(MARL) 방법의 넓은 범위를 기반으로 하지만, 그 주장된 이점은 일반적으로 협조 구조를 함수 근사와 부분 관측성과 혼동하는 설정에서 평가된다. 우리는 명시적인 속도 및 스태미나(stamina) 제약이 있는 완전 표 형식(tabular) 8×8 포식자-먹이 그리드월드에서 협조 구조를 분리하여, 10개 시드에 걸쳐 세 가지 운동학적 체제에서 독립 Q-러닝과 중앙화 Q-러닝의 네 가지 조합을 모두 비교한다. 완전 독립 학습(IQL-IQL)은 모든 체제와 모든 시드에서 완전 중앙화 구성(CQL-CQL)보다 더 짧은 에피소드와 더 높은 포식자 보상을 산출한다(Wilcoxon p = 0.00195, Cliff's delta = 1.0). 비대칭 IQL-CQL 조합은 일시적 불안정으로 해소되기보다 40,000 에피소드 학습 예산 전체에 걸쳐 지속되는 협조 붕괴를 유발한다. 고정된 IQL-IQL 포식자에 대한 최적 반응(best-response) 테스트는 가장 강한 구성조차 40k 에피소드에서 균형(equilibrium)에 수렴하지 않았음을 보여주므로, 구성 간 차이는 종국 성능이 아니라 공유 예산 하의 학습 역학을 반영한다. 우리는 시간적 동기화 잠금(temporal synchronization lock)이라 부르는 메커니즘을 제안한다: 공유 가치 함수가 모든 에이전트 결정을 결합하므로, 한 에이전트가 스태미나 제한을 받을 때 공동 Q-값이 능력 있는 파트너를 차선의 대기로 강제하는 반면, 독립 학습자는 비동기 추적을 계속한다. 이 병리는 함수 근사가 아니라 크레딧 할당(credit assignment)에서 기인하므로, 학습 중 크레딧을 중앙화하는 딥 MARL 방법에서도 유사한 효과가 나타날 수 있다고 추측한다. 중앙화된 협조는 균일하게 유익하지 않다; 독립 학습에 대한 그 이점은 체화(embodiment) 제약 하에서 축소되거나 사라지며, 중앙화-독립 혼합 조합은 균일한 선택 어느 쪽보다 성능이 나쁠 수 있다.

arXiv:2607.20547v1cs.LG공통 태그 Q-Learning, Multi-agent Reinforcement Learning

다중 에이전트 강화학습을 이용한 항공 회랑 내 저하된 감시 환경에서의 충돌 해소

Conflict Resolution under Degraded Surveillance in Air Corridors Using Multi-Agent Reinforcement Learning

안전한 고급 항공 이동성(Advanced Air Mobility, AAM) 운용은 감시 정보가 노이즈가 있거나, 지연되거나, 불완전하거나, 일시적으로 이용 불가능할 때 항공기가 분리(separation)를 유지해야 한다. 본 연구는 구조화된 3차원 회랑 내에서 운용되는 이질적인 소형 무인 항공기와 전기 수직 이착륙(eVTOL) 항공기 간 분산형 충돌 해소를 위한 심층 Q 네트워크 기반 다중 에이전트 강화학습 프레임워크를 개발한다. 두 항공기 유형에 대해 각각 국부 관측과 항로 유지, 선회, 수직 기동, 착륙, 속도 제어를 포함하는 14개 행동 공간을 사용하여 별도의 정책을 학습한다. 시뮬레이션에는 항공기별 동역학, 에너지 사용, 회랑 제약, 관측 노이즈, 통신 지연, 정보 드롭아웃, 바람 교란, 액추에이터 불확실성, 모델 불확실성이 포함된다. 학습된 정책은 교통 밀도와 최소 분리 임계값의 90가지 조합에 걸쳐 평가된다. 분리 상실(loss-of-separation) 빈도와 지속 시간은 일반적으로 교통 밀도와 분리 요구사항이 증가함에 따라 증가하지만, 대부분의 사건은 1초 이내에 해소된다. 안전한 조건 하에서 에이전트는 시간의 약 79% 동안 운동을 유지한다. 충돌 상황에서는 선회가 행동의 33%를 차지하며, 운동 유지 29%, 속도 제어 25%, 수직 기동 13%가 뒤를 잇는다. 6개의 파레토 최적 구성은 안전성과 회랑 용량 간의 트레이드오프를 보여준다. 이 프레임워크는 저하된 감시 조건 하에서 더 안전한 AAM 충돌 해소 전략의 시뮬레이션 기반 평가를 지원한다.

arXiv:2607.06935v1math.OC공통 태그 Q-Learning, Multi-agent Reinforcement 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)를 다룬다. 전반에 걸쳐 공통된 작용소 및 변분적 관점 하에 알고리즘 템플릿을 통합하고, 유한 샘플 경계와 점근적 결과를 함께 조명한다. 이 논문은 강화학습에 관심 있는 확률론, 최적화, 통계학 연구자들에게 통합된 수학적 진입점을 제공하고자 한다.

토론

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