arXiv:2011.10915

Multi-Agent Reinforcement Learning for Markov Routing Games: A New Modeling Paradigm For Dynamic Traffic Assignment

Zhenyu Shou, Xu Chen, Yongjie Fu, Xuan Di

제출 2020-11-22

원문 초록

This paper aims to develop a paradigm that models the learning behavior of intelligent agents (including but not limited to autonomous vehicles, connected and automated vehicles, or human-driven vehicles with intelligent navigation systems where human drivers follow the navigation instructions completely) with a utility-optimizing goal and the system's equilibrating processes in a routing game among atomic selfish agents. Such a paradigm can assist policymakers in devising optimal operational and planning countermeasures under both normal and abnormal circumstances. To this end, we develop a Markov routing game (MRG) in which each agent learns and updates her own en-route path choice policy while interacting with others in transportation networks. To efficiently solve MRG, we formulate it as multi-agent reinforcement learning (MARL) and devise a mean field multi-agent deep Q learning (MF-MA-DQL) approach that captures the competition among agents. The linkage between the classical DUE paradigm and our proposed Markov routing game (MRG) is discussed. We show that the routing behavior of intelligent agents is shown to converge to the classical notion of predictive dynamic user equilibrium (DUE) when traffic environments are simulated using dynamic loading models (DNL). In other words, the MRG depicts DUEs assuming perfect information and deterministic environments propagated by DNL models. Four examples are solved to illustrate the algorithm efficiency and consistency between DUE and the MRG equilibrium, on a simple network without and with spillback, the Ortuzar Willumsen (OW) Network, and a real-world network near Columbia University's campus in Manhattan of New York City.

함께 살펴볼 논문

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

arXiv:2607.01525v2math.OC공통 태그 Q-Learning, Multi-agent Reinforcement Learning

평균장 강화학습: 평균장 제어를 위한 이론과 알고리즘

Mean Field Reinforcement Learning: Theory and Algorithms for Mean Field Control

이 모노그래프는 평균장 상호작용과 공통 잡음을 갖는 대규모 개체군 확률 제어에서 발생하는 마르코프 결정 과정의 관점에서 평균장 강화학습을 소개한다. 다중 에이전트 강화학습과 평균장 제어 사이의 연결에서 출발하여, 대표 에이전트 학습 문제를 정식화하고, 이것이 유한 개체군 시스템과 맺는 관계를 분석하며, 일반 모형과 선형-이차 모형을 모두 연구하는 데 필요한 확률론적, 수학적, 제어이론적 틀을 전개한다. 서술에는 동적 계획법 원리, 혼돈 전파 극한, 그리고 표 기반 Q-러닝과 정책 경사 방법에 대한 이론적 분석이 포함된다. 또한 표 기반 기법과 심층 결정론적 정책 경사(deep deterministic policy gradient)와 같은 심층 강화학습 방법을 포함한 수치적 구현도 논의한다. 이 책의 목표는 독자에게 평균장 제어 이론과 강화학습 방법론 사이의 일관된 가교를 제공하는 것이며, 문제의 수학적 구조와 대규모 확률적 개체군을 위한 다루기 쉬운 학습 접근법의 설계를 강조한다.

arXiv:2610.13439v1cs.MA공통 태그 Autonomous Vehicles, Multi-agent Reinforcement Learning

자율주행차의 집합적 경로 선택에는 인간 운전자와의 공존을 위한 사회적 인식이 필요하다

Collective Autonomous Vehicle Routing Needs Social Awareness for Coexistence with Human Drivers

실제 교통 네트워크에서 자율주행차(AV)의 집합적 경로 선택은 인간 운전 차량(HDV)에 외부효과를 유발할 수 있는데, AV에게 유리한 경로가 다른 도로 이용자의 통행 시간을 증가시킬 수 있기 때문이다. 이를 해결하기 위해 우리는 이기적인 통행 시간 기반 AV 보상에 사회적 요소인 한계 비용(marginal cost)을 도입한다. 한계 비용은 해당 AV를 제거한 반사실적(counterfactual) 시뮬레이션에서의 통행 시간과 비교하여, 해당 AV가 다른 도로 이용자에게 미치는 영향을 포착한다. 우리는 다중 에이전트 강화학습(Multi-Agent Reinforcement Learning, MARL)을 사용하여 혼합 자율주행(mixed-autonomy) 교통 환경에서 AV의 경로 선택을 연구하며, 여기서 AV는 교통 환경과의 반복적인 상호작용을 통해 경로 선택 정책을 학습한다. Ingolstadt와 Provins의 실제 네트워크에 대한 실험 결과, 한계 비용을 AV 보상에 포함하면 이기적인 AV 경로 선택에 비해 HDV 통행 시간 증가를 제한하고 AV 통행 시간을 단축할 뿐만 아니라, 전체 시스템 성능도 향상되는 것으로 나타났다. Ingolstadt에서 AV 40%의 이기적인 경로 선택은 다른 차량의 통행 시간을 1.7% 증가시키지만, 사회적 보상을 포함하면 이 수치는 1.1%로 감소한다. 흥미롭게도 전체 시스템 성능이 향상될 뿐만 아니라, AV 자신도 사회적으로 행동할 때 더 나은 결과를 얻는다. 이러한 효과는 실험 대상 도시, 보급률(penetration rate), 반복 실험 전반에 걸쳐 일관되게 나타나지만, 보상에서 사회적 요소의 가중치가 증가하면 시스템이 원하는 성능에 도달하지 못한다. 혼합 자율주행 교통에서 사회적 AV 경로 선택을 보다 확장 가능하게 만들기 위해, 우리는 교통 시스템에 가장 큰 영향을 미치는 경로 선택을 하는 AV에 대해서만 한계 비용을 계산한다. 이를 통해 반사실적 시뮬레이션의 횟수를 줄이면서도 훨씬 낮은 계산 비용으로 유사한 성능을 달성한다. 우리의 결과는 AV 경로 선택이 이기적인 보상을 넘어, 모든 교통 참여자의 이익을 위해 목적 함수에 사회적 요소를 포함해야 함을 시사한다.

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:2609.22967v1cs.CV공통 태그 Autonomous Vehicles, Multi-agent Reinforcement Learning

범용 협력 지능: 회복력 있는 다중 에이전트 생태계를 위한 인지 아키텍처

General Collaborative Intelligence: Architecting Cognition for Resilient Multi-Agent Ecosystems

다중 에이전트 무인 시스템은 고립된 자기 중심적 sensing에서 협력 지능으로 이동하고 있으며, 분산 에이전트들이 압축된 특징(feature)을 교환하여 어떤 단일 에이전트도 벗어날 수 없는 국소 관측의 함정—가림(occlusion), 유한한 센서 범위, 환경 열화—to overcome. 해당 분야는 아키텍처, 통신, embodied, 회복력(resilience), 신뢰 차원에서 성숙해 왔지만, 기존 서베이는 이러한 차원을 각각 따로 다루며 그 의존 관계를 거의 드러내지 않는다. 본 리뷰는 두 가지 상보적 렌즈를 통해 통합적 종합을 제시한다. 첫째는 협력 단계, 통신 패러다임, 융합 아키텍처, 학습 전략, 응용 도메인에 걸친 5차원 분류체계이다. 둘째는 인지적 시너지를 운영 기준으로 전환하는 세 가지 인지적 시너지 조건—의미적 모호성 해소(Semantic Disambiguation), 화용론적 정보 교환(Pragmatic Information Exchange), 선제적 정보 탐색(Proactive Informational Foraging)—이다. 이러한 렌즈를 통해 협력 아키텍처와 토폴로지, 채널을 미분 가능한 파이프라인 구성요소로 다루는 신경-통신 공동 설계(neural-communication co-design), 다중 에이전트 강화학습을 통한 embodied 행동-지각 루프, 동기화·불확실성 정량화·라벨 효율적 학습을 위한 회복력 메커니즘을 조망한다. 이어 이러한 진전을 V2X, 무인 항공, 산업 물류, 스마트 시티의 네 가지 운영 도메인과 안전-프라이버시-유용성(safety-privacy-utility) 삼각 관계에 대응시킨다. 벤치마크 포화와 평가 파편화에 대응하기 위해, 본문은 협력 방법의 트레이드오프를 연구 간 비교 가능하게 만드는 성숙도 모델을 갖춘 5기둥 scoring 프로토콜 GCI-Bench를 제안한다. 재현성, sim-to-real 격차, 협력이 성능을 저하시키는 조건에 대한 비판적 성찰을 통해 미해결 과제를 밝히고, 실세계 불확실성 하에서 범용 협력 지능을 향한 방향을 제시한다.

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)$의 통신만을 필요로 함을 증명하며, 이는 기존 연구의 통신 비용을 크게 개선한다.

토론

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