Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems
원문 초록
Regret analysis is challenging in Multi-Agent Reinforcement Learning (MARL) primarily due to the dynamical environments and the decentralized information among agents. We attempt to solve this challenge in the context of decentralized learning in multi-agent linear-quadratic (LQ) dynamical systems. We begin with a simple setup consisting of two agents and two dynamically decoupled stochastic linear systems, each system controlled by an agent. The systems are coupled through a quadratic cost function. When both systems' dynamics are unknown and there is no communication among the agents, we show that no learning policy can generate sub-linear in $T$ regret, where $T$ is the time horizon. When only one system's dynamics are unknown and there is one-directional communication from the agent controlling the unknown system to the other agent, we propose a MARL algorithm based on the construction of an auxiliary single-agent LQ problem. The auxiliary single-agent problem in the proposed MARL algorithm serves as an implicit coordination mechanism among the two learning agents. This allows the agents to achieve a regret within $O(\sqrt{T})$ of the regret of the auxiliary single-agent problem. Consequently, using existing results for single-agent LQ regret, our algorithm provides a $\tilde{O}(\sqrt{T})$ regret bound. (Here $\tilde{O}(\cdot)$ hides constants and logarithmic factors). Our numerical experiments indicate that this bound is matched in practice. From the two-agent problem, we extend our results to multi-agent LQ systems with certain communication patterns.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
판매 학습: 다중 제품 시장에서 전략적 대규모 언어 모델 에이전트를 위한 강화학습
Learning to Sell: Reinforcement Learning for Strategic Large Language Model Agents in Multi-Product Markets
다중 제품 시장에서 작동하는 자율 대규모 언어 모델(LLM) 에이전트는 정보 비대칭과 자원 제약 조건 하에서 순차적 의사결정을 내려야 합니다. 본 연구에서는 판매자가 독립적인 구매자 풀을 대상으로 대체 가능한 자산 카탈로그를 동시에 협상하는 다중 품목 협상 환경에서 에이전트가 판매자로서 효과적으로 활동하도록 학습시키는 머신러닝 접근 방식을 개발합니다. 구매자들은 제품 전반에 걸쳐 비공개적이고 이질적인 가치 평가를 지니며, 각 구매자는 최대 하나의 품목만 구매할 수 있습니다. 판매자는 전체 통신 턴 수의 제한에 직면하여 구매자의 비공개 가치 평가를 고려해 가장 수익성이 높은 제품과 동적으로 매칭하는 동시에, 더 큰 잠재 가치를 지닌 조합을 향해 제한된 상호작용 예산을 전략적으로 할당해야 합니다. 본 논문에서는 자연어를 파싱 가능하고 규제된 의사결정 공간으로 매핑하는 정형화된 4단계 메시지 프로토콜을 사용하여 이 문제를 부분 관측 마르코프 결정 과정(POMDP)으로 정형화합니다. 이러한 정형화를 바탕으로 검증 가능한 보상 기반 강화학습(RLVR)을 사용하는 사후 학습(post-training) 방법을 설계합니다. 이 프레임워크를 평가하기 위해 제약 준수, 판매자 잉여 추출, 할당 품질을 정량화하는 다차원 메트릭 스위트를 구축합니다. 학습된 판매자 에이전트는 제한된 재고를 구매자에게 더 효과적으로 매칭하는 법을 학습하며, 판매자 잉여 추출 및 구매자-제품 할당 품질 모두에서 조 단위 매개변수를 지닌 프론티어 모델과 대등하거나 이를 능가하는 성능을 보입니다. 마지막으로, 이렇게 학습된 전략은 학습 중 접하지 않은 새로운 시장 구조, 상관관계가 있는 가치 평가 분포, 가격 범위로도 견고하게 일반화됩니다.
안전성을 경쟁력으로 전환하기: 안전 필터링 강화학습을 통한 최소 착취성 로봇 정책
Turning Safety into Competence: Minimally Exploitable Robot Policies via Safety-Filtered Reinforcement Learning
경쟁적인 작업에 배치된 로봇은 안전성(safety)을 저해하지 않으면서 상대를 제압할 수 있어야 합니다. 안전 강화학습(safe RL)을 포함한 기존 접근 방식들은 작업 성공을 달성함과 동시에 실패를 피하도록 단일 정책을 학습(training)합니다. 이러한 결합은 학습을 복잡하게 만들고, 의도적인 공격에 의해 학습된 정책이 악용(exploitable)될 수 있는 여지를 남깁니다. 본 논문에서는 안전성 통합과 경쟁 작업 학습을 분리하는 2단계 강화학습 프레임워크인 Safety to Competence(S2C)를 제안합니다. 경쟁적인 상호작용을 안전 필수 마르코프 게임(safety-critical Markov games)으로 정형화하고, 모든 플레이어가 안전한 기동을 준수할 때 완벽한 필터링이 정책의 비착취성(non-exploitability)을 보존함을 증명합니다. S2C는 적대적 강화학습을 통해 강건한 안전 필터를 학습하고, 작업 정책 학습 중 이를 환경(environment)에 포함시키며, 실제 배치 시에도 동일한 필터를 유지합니다. 시뮬레이션된 터치다운 게임에서 S2C는 8가지 안전 강화학습 베이스라인을 능가하여 가장 높은 승률과 Elo 레이팅, 그리고 가장 낮은 착취성을 달성했습니다. 인간 상대를 대상으로 한 하드웨어 스트레스 테스트에서도 S2C의 뛰어난 역량이 입증되었습니다.
지연된 정보 공유를 활용한 탈중앙화 부분 관측 팀 의사결정 방법론
A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharing
본 논문에서는 저순위 잠재 동역학(low-rank latent dynamics)과 미지의 시스템 모델을 갖는 탈중앙화 부분 관측 팀 의사결정 문제를 연구합니다. 제안된 프레임워크는 전이 모델(transition model)에 대한 사전 지식 없이도 부분 관측 마르코프 결정 과정(POMDP)에서의 협력적 의사결정을 다루기 위해 팀 이론적 동치성(team-theoretic equivalence)과 저순위 모델 표현을 결합합니다. 각 팀 구성원은 로컬의 개별 정보와 팀 전체에 공유되는 지연된 공통 정보를 기반으로 의사결정을 내립니다. 사용 가능한 정보만을 활용하여, 각 구성원은 근사 저순위 마르코프 결정 과정을 학습하고 최소제곱 가치 반복(least-squares value iteration)을 적용하여 정책을 계산합니다. 이를 통해 중앙 조정자나 중앙 집중식 학습이 모두 필요하지 않은 완전 탈중앙화 학습 및 계획 알고리즘을 도출합니다. 우리는 결과로 도출된 구성원 측 해가 중앙 집중식 팀 해를 근사함을 보입니다. 즉, 부분 관측 가능성, 미지의 동역학, 지연된 공통 정보에도 불구하고 각 구성원은 근사 팀 최적 정책의 해당 구성 요소를 복원합니다. 나아가 제안된 알고리즘에 대한 유한 표본 성능 보장(finite-sample performance guarantees)을 확립하고 이에 대응하는 표본 복잡도 한계(sample-complexity bound)를 유도합니다.
프로그래밍 정책 탐색을 통한 연속 게임용 반응형 캐릭터 행동 합성
Synthesizing Reactive Character Behaviors for Continuous Games via Programmatic Policy Search
본 논문은 연속 게임에서 반응형 캐릭터 행동을 간결하고 사람이 읽을 수 있는 프로그램 형태로 합성하는 방법을 제시한다. 게임 AI 실무는 여전히 수작업으로 작성한 행동 트리, 상태 기계, 스크립트에 크게 의존하는 반면, 학계의 강화학습은 학습 비용이 크고 수정하기 어려운 불투명한 신경망 제어기를 주로 만든다. 우리 접근은 연속 공간 게임 정책을 위한 도메인 특화 언어 위에서 직접 탐색함으로써 이 간극을 메운다. 이 언어는 반응형 기하학적 의사결정을 중심으로 설계되었으며 방향 최대화(direction maximization)와 같은 고차(higher-order) 구성을 포함한다. 이러한 구성은 연속 행동 공간을 열거 가능한 프로그램 구조로 이산화하는 데 도움이 된다. 프로그램 탐색을 실용적으로 만들기 위해, 행동적 커버리지는 유지하면서 중복 프로그램 형태를 제거하는 대규모 합성 안티패턴(synthesis antipatterns) 집합을 도입한다. 또한 하향식(bottom-up) 기호 열거와 코딩 에이전트의 하향식(top-down) 안내를 결합한다. 그 결과 방법인 agentic sketching은 에이전트가 고수준 정책 구조를 제안하고 열거기를 호출해 지역 프로그램 슬롯을 채우도록 한다. 14개의 연속 게임으로 구성된 벤치마크에서 방법을 평가했으며, 고전 제어 과제부터 다중 에이전트 축구까지 범위에 걸친다. 순수 열거만 사용하는 것이 코딩 에이전트 단독 사용보다 종종 더 효율적이며, 결합 방법은 둘 모두를 크게 능가한다. 결과는 프로그래밍 정책 탐색이 게임 AI를 위한 실용적인 저작 도구가 될 수 있음을 시사한다. 디자이너가 보상 함수를 지정하면 시스템이 효과적이고 이식 가능하며 종종 놀라운 수준의 편집 가능한 행동을 발견한다.
정적 및 시변 네트워크에서의 분산 감소 Q-학습
Variance-Reduced Q-Learning over Static and Time-Varying Networks
동일한 마르코프 결정 과정(MDP)과 상호작용하는 여러 에이전트가 포함된 분산형 강화학습 문제를 조사한다. 에이전트는 네트워크를 통해 정보를 교환하여 최적 상태-행동 가치 함수를 공동으로 학습할 수 있다. 이 설정을 위해, 각 에포크 내에서 에이전트가 벨만 최적성 연산자를 국소적으로 추정하고 합의 기반 프로토콜을 사용하여 정보를 확산하는 VRDQ라는 새로운 에포크 기반 분산 $Q$-학습 알고리즘을 제안한다. 정적 및 시변 네트워크 모두에 대해, 협력으로부터 선형 속도 향상(linear speedups)을 누리는 VRDQ의 고확률 유한 시간 수렴률을 확립한다. 중요하게도, 표본 복잡도(sample-complexity)에서의 이러한 속도 향상이 $\tilde{O}(1)$의 통신만을 필요로 함을 증명하며, 이는 기존 연구의 통신 비용을 크게 개선한다.
신호등 없는 교차로에서 자율주행 차량을 위한 압축 잠재 조율
Compact Latent Coordination for Autonomous Vehicles at Unsignalized Intersections
신호등 없는 교차로에서 자율주행 차량을 조율하는 것은 다중 에이전트 강화학습(MARL) 시스템에 있어 여전히 중요한 과제이며, 이러한 시스템은 일반적으로 조합적 행동 공간, 특권 정보에 대한 의존, 또는 경직된 에이전트 설계로 어려움을 겪는다. 우리는 중앙집중식 Master 에이전트가 전역 조율 전략을 인코딩하는 proto-plan이라고 부르는 압축된 연속 임베딩을 생성하는 계층적 심층 강화학습(DRL) 아키텍처인 Master-Agent Proto-plan System(MAPS)을 제안한다. 분산 Worker 에이전트는 이 임베딩을 지역 관측과 통합하여 차량별 제어를 수행하며, 전략적 의도와 전술적 실행을 분리하고 각 모듈의 독립적 최적화를 가능하게 한다. 이 조율 메커니즘에 대한 개념 증명 평가로, HighwayEnv에서 72가지 교차로 구성에 걸쳐 MAPS를 테스트한다. MAPS는 최신 베이스라인을 능가하며 평균 이동 시간을 크게 줄이면서 충돌 없는 주행을 달성한다. 학습된 proto-plan은 또한 견고한 일반화를 보인다: 3개 에이전트로 학습된 시스템이 5개 에이전트 시나리오에 제로샷(zero-shot)으로 배포될 때 94%의 성공률을 달성하여, proto-plan 기반 계층적 학습이 다중 차량 조율을 위한 유망한 프레임워크임을 확인한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.