Source-linked AI summary
Off-Policy Multi-Agent Decomposed Policy Gradients
Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, Chongjie Zhang
TL;DR
MAPG 방법은 value-based 접근법보다 성능이 낮은 경우가 많고, off-policy 학습, centralized-decentralized 불일치, credit assignment가 여전히 난제로 남아 있다. DOP는 actor-critic 학습에서 centralized critic을 factorize하며, discrete 및 continuous benchmark 전반에서 다른 MAPG 방법을 능가하고, discrete task에서는 state-of-the-art value-based 방법도 앞선다.
문제
MAPG 방법은 value-based 방법보다 성능이 낮은 경우가 많으며, off-policy 학습과 centralized-decentralized 불일치가 multi-agent policy-gradient 학습을 제약한다.
방법
DOP는 centralized critic을 가중치가 부여된 local critic들로 factorize하여 off-policy 학습을 가능하게 하고 centralized-decentralized 불일치와 credit assignment를 해결한다.
결과
DOP는 StarCraft II와 particle environment 전반에서 안정적이며 다른 MAPG algorithm을 능가하고, discrete benchmark에서 state-of-the-art value-based 방법을 능가한 최초의 stochastic MAPG 방법으로 보고되었다.
시사점 및 한계
Value decomposition은 multi-agent actor-critic 방법이 discrete 및 continuous action setting 전반에서 선도적인 value-based 방법과 경쟁할 수 있도록 한다.
시사점 및 한계
수렴 분석은 tabular policy와 value function을 가정하며, continuous-action representation 결과는 Lipschitz-smooth action gradient를 가정한다.
Abstract
from arXiv · showhide
Multi-agent policy gradient (MAPG) methods recently witness vigorous progress. However, there is a significant performance discrepancy between MAPG methods and state-of-the-art multi-agent value-based approaches. In this paper, we investigate causes that hinder the performance of MAPG algorithms and present a multi-agent decomposed policy gradient method (DOP). This method introduces the idea of value function decomposition into the multi-agent actor-critic framework. Based on this idea, DOP supports efficient off-policy learning and addresses the issue of centralized-decentralized mismatch and credit assignment in both discrete and continuous action spaces. We formally show that DOP critics have sufficient representational capability to guarantee convergence. In addition, empirical evaluations on the StarCraft II micromanagement benchmark and multi-agent particle environments demonstrate that DOP significantly outperforms both state-of-the-art value-based and policy-based multi-agent reinforcement learning algorithms. Demonstrative videos are available at https://sites.google.com/view/dop-mapg/.
1 서론
이 논문은 centralized actor-critic framework에 value decomposition을 도입해 multi-agent policy-gradient methods와 state-of-the-art value-based MARL 간 성능 격차를 다룬다. DOP는 factorized critic을 사용해 확장 가능한 off-policy learning을 지원하면서 estimation bias와 policy-update variance의 균형을 맞추며, discrete 및 continuous-action benchmark 전반에서 우수한 결과를 달성한다.
- 동기: DOP는 MAPG와 value-based methods 간 성능 격차를 다루며, 후자는 StarCraft II micromanagement와 같은 어려운 과제에서 state-of-the-art 결과를 달성한다는 장점이 있다.논문은 MAPG의 낮은 성능을 초래하는 원인을 분석하고 이러한 방법을 저해하는 세 가지 주요 문제를 식별한다.
- 기여: DOP는 local actions를 조건으로 하는 개별 critic들의 weighted linear sum으로 value estimation을 분해하는 centralized but factorized critic을 도입한다.이 구조는 확장 가능한 critic learning과 stochastic policies의 tractable off-policy evaluation을 가능하게 한다.
- 방법: Linearly decomposed critic은 value-estimation bias를 유발할 수 있지만, policy-improvement guarantees를 유지하면서 policy-update variance를 크게 줄인다.이러한 bias-variance trade-off는 제한된 representational capacity에도 불구하고 decomposed critic을 사용할 근거를 제공한다.
- 실험 결과: DOP는 실행 간 안정적이며, 다른 MAPG algorithms를 큰 폭으로 능가하고, StarCraft II와 multi-agent particle environments 전반에서 state-of-the-art value-based methods를 크게 능가한다.평가는 StarCraft II의 discrete action spaces와 multi-agent particle environments의 continuous action spaces를 포함한다. 또한 stochastic DOP는 후자의 비교에서 성과를 달성한 최초의 MAPG method로 제시된다.
- 관련 연구: Value-based MARL의 value-decomposition methods는 각 agent의 local Q-functions를 학습하고 learnable mixing function을 통해 결합하며, VDN의 arithmetic summation부터 QMIX의 nonlinear monotonic factorization까지 다양한 형태를 취한다.QTRAN 및 관련 methods는 이러한 구조를 넘어 value-decomposition 계열을 확장한다.
2 배경
이 논문은 완전 협력형 multi-agent task를 Dec-POMDP로 정식화하고, decentralized policy를 사용하는 discrete 및 continuous action space를 모두 다룬다. 또한 MADDPG와 COMA 같은 centralized-critic method를 포함해 centralized training with decentralized execution의 틀 안에 제안 방법을 위치시킨다.
- Dec-POMDP 정식화: 완전 협력형 task는 Dec-POMDPs로 모델링되며, agent는 observation을 받고 joint action을 선택한 뒤 state 사이를 전이하고 discount factor γ하에서 reward를 받는다.이 정식화에는 유한한 agent, environment state, observation, action, transition dynamics, reward, discounting이 포함된다.
- Dec-POMDP 정식화: 이 framework는 discrete 및 continuous action space를 다루며, 전자에는 stochastic policy를, 후자에는 deterministic policy µ를 학습한다.Deterministic joint policy는 µ = ⟨µ1, · · ·, µn⟩으로 표기된다.
- Multi-Agent Policy Gradient: Centralized training with decentralized execution은 decentralized execution을 유지하면서 non-stationarity에 대응하며, 일반적으로 centralized critic과 decentralized actor를 사용한다.MADDPG와 COMA는 대표적인 centralized-critic, decentralized-actor method로 제시된다.
- Multi-Agent Policy Gradient: COMA는 agent i를 제외한 joint action에 기반한 counterfactual advantage를 사용해 credit assignment를 처리하고 variance를 줄인다.제외된 agent를 기준으로 한 joint action은 a_-i로 표기된다.
3 분석
분석에서는 multi-agent policy-gradient 성능을 제한하는 세 가지 장애물, 즉 어려운 off-policy stochastic learning, centralized-decentralized mismatch, 그리고 cooperative setting에서 해결되지 않은 credit assignment를 식별한다. 이러한 문제는 지수적으로 증가하는 variance, 다루기 어려운 계산량, 그리고 다른 agent의 action에서 비롯되는 간섭 때문에 발생한다.
- 3.1 Off-Policy Learning: off-policy stochastic MAPG가 어려운 이유는 importance-sampling variance가 agent 수에 따라 지수적으로 증가하는 반면, multi-agent tree-backup target에는 O(|A|^n)의 계산이 필요하기 때문이다.기존 stochastic MAPG method는 off-policy data를 지원하지 않으며, agent 수가 증가할수록 tree-backup evaluation은 계산 불가능해진다.
- 3.2 Centralized-Decentralized Mismatch: centralized critic은 각 agent의 update가 다른 agent의 action에 의존하기 때문에 high-variance policy-gradient estimate를 생성하며, 다른 agent의 exploration이나 suboptimality가 learning을 잘못된 방향으로 이끌 수 있다.이러한 상호작용은 한 agent의 suboptimality가 critic을 교란하고 다른 agent의 update를 방해하는 negative feedback loop를 만들 수 있으며, 이를 centralized-decentralized mismatch (CDM)라고 한다.
- 3.4 Empirical Evidence: 한 case study에 따르면 DOP는 COMA 및 MADDPG보다 gradient variance가 significantly lower하여 결과적으로 이들을 능가하는 반면, CDM은 sequential setting에서 divergence를 일으킬 수 있다.해당 passage는 variance와 performance 비교를 위해 Fig. 2를 참조하며, 이후 section에서 악화된 CDM과 divergence를 검토한다고 설명한다.
- 3.3 Credit Assignment: MADDPG와 MAAC는 continuous action에서 효율적인 off-policy learning을 가능하게 하지만, single global reward를 사용하는 fully cooperative setting에서는 credit assignment 문제를 대체로 해결하지 못한다.제공된 passage는 이를 deterministic policy-gradient method를 multi-agent setting으로 확장할 때의 한계로 제시한다.
4 분해된 Off-Policy Policy Gradients
DOP는 multi-agent actor-critic 학습에 value-decomposed centralized critic을 도입해 다루기 쉬운 off-policy 평가와 decentralized policy 업데이트를 가능하게 한다. Stochastic DOP는 critic approximation이 존재해도 단조로운 policy improvement를 제공하며, deterministic DOP는 bounded approximation errors 하에서 continuous actions를 지원한다.
- Critic decomposition: DOP는 centralized critic을 개별 agent critic의 nonnegative weighted sum으로 분해하며, 가중치와 bias는 global observation-action history로부터 생성된다.개별 critic은 agent별 reward가 아니라 joint reward를 사용한 global TD update로 학습된다.
- Stochastic DOP: 분해된 critic은 tree-backup expectation의 복잡도를 O(|A|^n)에서 O(n|A|)로 줄여 multi-agent off-policy evaluation을 다루기 쉽게 만든다.DOP는 sample efficiency와 training efficiency 사이의 절충을 위해 off-policy tree-backup과 on-policy TD(λ) update도 결합한다.
- Stochastic DOP: 각 stochastic DOP policy update는 자신의 individual critic에만 의존해 암묵적으로 credit을 할당하고, 다른 agent의 action으로 발생하는 centralized-decentralized mismatch를 완화한다.논문은 DOP가 policy-gradient variance를 줄이고 복잡한 task에서 centralized-decentralized mismatch를 완화한다고 보고한다.
- Policy improvement guarantee: 온건한 가정하에서 stochastic DOP update는 joint objective를 단조롭게 개선하며, 부정확한 decomposed Q estimate가 있어도 J(π) ≥ J(πo)를 만족한다.수렴 분석은 tabular policy와 value function을 사용하며 value evaluation을 mean-squared-error 문제로 단순화한다.
5 실험
실험은 decomposed critic이 centralized-decentralized mismatch를 완화하고, off-policy 효율을 높이며, credit assignment를 가능하게 하고, discrete 및 continuous task 전반에서 기존 MARL 방법을 능가하는지 검증한다. 결과는 12개 무작위 seed에 대한 평균이다.
- CDM 이슈: DOP는 local Q-value 순서를 보존하며, linear decomposition이 추가적인 estimation error를 유발함에도 다른 알고리즘보다 policy-gradient variance가 훨씬 낮다.실험에서는 경쟁 방법의 variance가 undecomposed critic이 모든 agent의 action에 영향을 받기 때문이라고 설명한다.
- Benchmark 평가: 평가는 SMAC에서 stochastic DOP를 COMA, VDN, QMIX와 비교하고, continuous-action MPE task에서 deterministic DOP를 MADDPG, MAAC와 비교한다.DOP는 실험 전반에서 고정된 hyperparameter와 network structure를 사용하는 반면, SMAC baseline은 benchmark에 맞게 조정된 default를 사용한다.
- Off-Policy Learning: DOP와 off-policy DOP는 on-policy version을 능가하는 반면, 순수한 off-policy learning은 일반적으로 유사한 성능에 도달하기 위해 더 많은 sample을 필요로 한다.ablation에서는 κ를 0, 0.5, 1로 변화시키며, DOP에는 κ=0.5를 사용한다.
- CDM 이슈: On-Policy DOP는 COMA가 더 expressive한 critic을 사용함에도 COMA를 능가하며, COMA는 불안정하고 near-optimal policy를 학습한 뒤 발산할 수 있다.이 비교는 두 방법이 주로 critic decomposition에서 다르므로 centralized-decentralized mismatch의 효과를 분리한다.
- Decomposed Multi-Agent Tree Backup: Decomposed tree backup은 agent 수가 증가해도 빠르고 안정적으로 수렴하는 반면, sampled common tree backup은 비효율적이 되고 On-Policy DOP보다 낮은 성능을 보일 수 있다.Common tree backup은 200개의 joint action을 sampling하여 expectation을 추정하는 반면, 직접 계산에는 map MMM에서 20^10개의 summation이 필요할 수 있다.
- Credit Assignment: Deterministic DOP는 clockwise pushing에 대해 더 큰 Q-value를 학습하고, 그 결과 Mill task에서 이전 state-of-the-art deterministic MAPG method를 능가한다.학습된 credit assignment는 training 중 점차 합리적인 수준이 된다.
6 마무리 발언 · A 확률적 DOP를 위한 수학적 세부사항
이 논문은 최신 MAPG 알고리즘의 성능을 제한하는 세 가지 단점을 규명하고, 이를 해결하기 위해 분해된 actor-critic 방법(DOP)을 제안한다. 이론적·실증적 결과는 DOP가 안정적이고 효율적인 multi-agent off-policy learning을 가능하게 함을 보여준다.
- 6 마무리 발언: DOP는 stochastic policy-gradient 방법에서의 on-policy learning, centralized-decentralized mismatch, 그리고 deterministic policy learning에서의 credit assignment 문제를 해결한다.
- 6 마무리 발언: 이 논문은 규명된 MAPG 성능 한계를 극복하기 위해 분해된 actor-critic 방법(DOP)을 제안한다.
- 6 마무리 발언: 이론적 분석은 DOP가 안정적이고 효율적인 multi-agent off-policy learning을 달성할 수 있음을 뒷받침한다.
- 6 마무리 발언: 실증적 평가는 DOP가 안정적이고 효율적인 multi-agent off-policy learning을 달성할 수 있음을 보여준다.
A.1 분해된 critic은 tractable한 multi-agent tree backup을 가능하게 함 … B Deterministic DOP의 수학적 세부사항
DOP의 선형 분해 critic은 multi-agent tree backup을 tractable하게 만들고 on-policy 및 off-policy stochastic policy-gradient 유도를 지원한다. 또한 이론은 명시적 가정하에서 variance reduction을 설명하지만, 해당 가정이 강하다는 점도 지적한다.
- A.1 분해된 critic은 tractable한 multi-agent tree backup을 가능하게 함: Tree-backup expectation complexity는 joint critic을 사용할 때의 O(|A|^n)에서 DOP의 선형 분해 critic을 사용하면 O(n|A|)로 감소한다.이 분해를 통해 tractable한 multi-agent off-policy policy evaluation이 가능해진다.
- B Deterministic DOP의 수학적 세부사항: 수학적 부록은 on-policy 및 off-policy learning 모두에 대한 stochastic DOP policy gradient를 유도하고 deterministic-DOP framework를 뒷받침하는 이론을 분석한다.제공된 본문은 stochastic 유도와 이론적 variance analysis를 구체적으로 다룬다.
- A.2.1 On-policy 버전: On-policy stochastic DOP policy gradient는 credit assignment에 aristocrat utility를 사용하며, 각 agent의 utility는 다른 agent의 action과 독립적이다.부록은 stochastic multi-agent policy를 업데이트하기 위한 gradient를 유도한다.
- A.2.2 Off-policy 버전: Off-policy stochastic gradient는 DOP의 선형 분해 critic을 사용하므로, off-policy data를 통한 policy improvement로 sample efficiency를 높일 수 있다.이 유도는 on-policy stochastic policy gradient에 대응하는 off-policy 버전으로 제시된다.
- A.3 CDM 이슈: Stochastic DOP는 policy-gradient variance를 줄일 수 있으며, 부록은 bounded policy gradient와 agent별 random variable에 대한 가정을 통해 이 효과를 이론적으로 분석한다.분석에서는 X1, X2, . . . , Xn이 평균 µ, variance σ2를 갖는 i.i.d. 변수라고 가정한다.
- A.3 CDM 이슈: 제시된 가정하에서는 variance 결과가 임의의 τ에 대해 성립하지만, 해당 가정은 quite strong하다고 인정된다.결론은 bounded-gradient 및 i.i.d. 가정에 명시적으로 조건부이다.
B.1 결정론적 DOP 정책 그래디언트 정리
이 절에서는 결정론적 DOP 정책 그래디언트 업데이트를 제시하고, 단일 에이전트 정책 그래디언트 결과에서 착안해 이를 유도한다.
- B.1 결정론적 DOP 정책 그래디언트 정리: 결정론적 DOP 정책 그래디언트 업데이트를 Section 4.2.1의 초점으로 제시한다.
- B.1 결정론적 DOP 정책 그래디언트 정리: 이 절에서는 결정론적 DOP 정책 그래디언트 업데이트 규칙의 유도를 제공한다.
- B.1 결정론적 DOP 정책 그래디언트 정리: 증명은 단일 에이전트 정책 그래디언트 사례에서 착안한다.
C 확률적 DOP 정책 개선 정리의 증명
확률적 DOP 정책 개선 정리는 완만한 단조성 가정하에서 정확한 Q_tot 추정치가 없어도 충분히 작은 업데이트가 J(π)를 개선함을 보인다. 분석은 MSE critic 정식화와 양의 선형 분해 가중치에 기반하며, neural critic과 target-network TD learning에 대한 한계도 지적한다.
- 증명 메커니즘: Critic learning을 MSE 문제로 분석하면 projection error가 있어도, Q_tot^π의 정확한 추정치를 요구하지 않고 π를 개선할 수 있다.저자들은 decomposed critic이 부정확하더라도 여전히 π를 개선할 수 있다고 설명한다.
- 증명 메커니즘: 이 증명은 monotone decomposition이 local action value의 순서를 보존하며, linearly decomposed critic이 k_i(τ) > 0을 만족함을 확립한다.이 순서 결과는 정책 개선 증명의 토대가 되는 Fact 1을 도출한다.
- 정책 개선 정리: 완만한 가정과 충분히 작은 δ > 0하에서 stochastic DOP 업데이트는 J(π) ≥ J(π_o)를 보장하여 joint policy를 개선한다.이 정리는 업데이트 π_i(a_i|τ_i) = π_i^o(a_i|τ_i) + β_{a_i,τ}δ에 적용된다.
- 한계: neural-network policy와 critic은 MONOTONE을 위반할 수 있고 target-network TD-error minimization은 가정된 MSE 문제와 다르므로, 이론적 분석이 이들에 직접 성립하지 않을 수 있다.이러한 한계에도 불구하고 linearly decomposed critic 구조는 상당히 안정적인 경험적 성능을 보이는 것으로 보고된다.
D 결정론적 DOP critic의 표현 능력 · E 알고리즘 · F 관련 연구
이 논문은 결정론적 DOP critic이 국소 평활성하에서 유계 근사 오차를 달성할 수 있음을 보인 뒤, stochastic 및 deterministic 학습 절차를 제시하고 이를 확장 가능한 cooperative MARL 및 centralized-critic policy-gradient 연구 맥락에 위치시킨다.
- D 결정론적 DOP critic의 표현 능력: 주어진 Lipschitz-gradient 가정하에서 결정론적 DOP critic의 추정 오차는 Oδ(τ) 내의 action에 대해 O(Lδ2)로 유계다.이 결과는 모든 τ와 인접한 action 쌍 a, a′ ∈ Oδ(τ)에 적용된다.
- D 결정론적 DOP critic의 표현력: DOP critic의 일차 구조는 인접 행동에 대한 임의의 sampling distribution에서 최적 MSE 근사 오차가 O(Lδ2) 미만이 되도록 한다.이 논증은 전체 Q-function의 일차 Taylor 형식을 사용하며, 정확하게 추정된 인접 Q-value를 전제로 δ ≪ 1이라고 가정한다.
- E 알고리즘: Stochastic DOP는 critic, decentralized actor, mixer, target network, 그리고 별도의 off-policy 및 on-policy replay buffer를 초기화한다.학습 루프는 trajectory를 두 buffer에 수집하고 target network를 주기적으로 업데이트한다.
- E 알고리즘: Stochastic DOP는 on-policy trajectory에서 policy를 업데이트하면서 off-policy replay를 사용해 on-policy 및 DOP target 기반 critic loss를 결합한다.알고리즘은 critic을 업데이트하기 전에 N1개의 on-policy trajectory와 N2개의 off-policy trajectory를 샘플링한다.
- E 알고리즘: Deterministic DOP는 noisy decentralized action으로 탐색하고, transition을 하나의 replay buffer에 저장하며, 샘플링한 transition으로 critic과 policy를 업데이트한다.Target critic, actor, mixer network는 α로 제어되는 soft update를 사용해 주기적으로 업데이트된다.
- F 관련 연구: Centralized joint-action learning은 coordination을 개선하고 non-stationarity를 피하지만, joint action space는 agent 수에 따라 지수적으로 증가한다.Coordination graph는 coordination independency를 활용하고 global reward를 local term으로 분해해 확장성 문제를 다룬다.
- F 관련 연구: Multi-agent policy gradient는 안정적인 수렴과 continuous control 적용 가능성을 제공하며, COMA와 MADDPG는 centralized critic과 decentralized actor를 사용해 non-stationarity를 다룬다.관련 연구 논의는 이러한 방법을 centralized training with decentralized execution 맥락에 위치시킨다.
G 인프라, 아키텍처 및 하이퍼파라미터 · G.1 확률적 DOP · G.2 결정론적 DOP
실험은 NVIDIA P100 GPU에서 고정된 하이퍼파라미터를 사용한다. 확률적 및 결정론적 DOP는 state-conditioned decomposed critic을 사용하지만, actor 아키텍처와 replay 기반 학습 설정은 서로 다르다.
- G 인프라, 아키텍처 및 하이퍼파라미터: 실험은 다음 절에 명시된 고정 하이퍼파라미터 설정으로 NVIDIA P100 GPU에서 수행된다.
- G.1 확률적 DOP: 확률적 DOP는 두 개의 256차원 ReLU fully connected layer로 구성된 에이전트별 local utility network를 사용하며, critic은 실행 중 사용되지 않으므로 global state를 조건으로 한다.각 network는 가능한 모든 local action에 대해 Qφi를 출력한다.
- G.1 확률적 DOP: 확률적 DOP는 state-conditioned weight와 bias를 사용해 local utility를 global Q 추정치로 선형 결합하며, 음이 아닌 weight를 [0, 1]로 정규화한다.weight는 합으로 정규화하기 전에 activation의 절댓값을 사용한다.
- G.1 확률적 DOP: local policy network는 64-bit GRU를 중심으로 fully connected layer를 구성하며 local action에 대한 확률 분포를 출력한다.첫 번째 fully connected layer 다음에 ReLU activation을 적용한다.
- G.1 확률적 DOP: 확률적 DOP는 κ = 0.5, 5000 episodes와 32개의 on-policy item으로 구성된 replay buffer, 네 개의 병렬 environment를 사용하며, learning rate 5 × 10^-4 및 α = 0.99인 RMSprop을 사용한다.Exploration은 500k time step 동안 ϵ를 1.0에서 0.05로 anneal한 뒤 일정하게 유지하며, optimization에는 momentum이나 weight decay를 사용하지 않는다.
- G.2 결정론적 DOP: 결정론적 DOP는 유사한 critic 구조를 유지하지만 local action을 입력으로 포함하며, 두 개의 64차원 ReLU hidden layer를 사용하고 local action을 출력하는 actor를 사용한다.critic 아키텍처는 입력에 local action을 포함한다는 점에서 확률적 DOP와 다르다.
- G.2 결정론적 DOP: 결정론적 DOP는 최신 10000 transitions를 포함하는 replay buffer에서 학습하며, critic 및 actor 학습을 위해 update마다 1250 transitions를 샘플링한다.