[COMA] Counterfactual Multi-Agent Policy Gradients

[Submitted on 24 May 2017 (v1), last revised 14 Dec 2017 (this version, v2)]

Abstract

: Decentralized actor's policy와 centralized critic's Q-function을 최적화하기 위한 COMA를 제안한다. multi-agent의 credit assignment를 해결하기 위해 다른 agent's action은 고정된 상태로 유지하면서 single agent's action을 marginalises하는 counterfactual baseline을 사용한다. 추가로 single forward pass에서 counterfactual baseline이 효율적으로 계산될 수 있도록 하는 critic representation을 사용한다. 

 

 

---

Introduction

: Cooperative setting에서 joint action은 일반적으로 global reward만 생성하므로 각 agent가 team's success에서 자신의 기여도를 추론하기 어렵게 만든다. 때때로 각 agent에 대한 individual reward function를 설계할 수도 있지만 일반적으로 사용이 불가능하다. 기존 RL의 scalability와 같은 고질적인 problem과 더불어 이를 해결할 수 있는 approach가 존재한다. 

 

1. COMA는 centralised critic을 사용한다. 

: Critic은 학습 중에만 사용되는 반면, actors는 실행 중에 필요하다. 학습이 centralized 되어 있으므로 각 agent의 policy condition은 own action-observation history에만 의존하는 반면, ciric condition은 joint action과 available state information을 사용 가능하다. 

 

2. COMA는 counterfactual baseline을 사용한다. 

: 이는 각 agent가 own action이 default action으로 대체될 때 받는 reward와 global reward를 비교하는 형태의 reward에서 학습하는 과거 paper에서 motivate된다. difference reward는 multi-agent credit assignment를 수행하는 method이지만, estimated reward function에 대한 access를 필요로하며 default action을 선택하는 방법이 명확하지 않다. 

 

- centralized critic를 사용하여 current joint action에 대한 estimated return를 다른 agent's action을 고정된 상태로 유지하면서 single agent's action을 marlinalise하는 counterfacutal baseline과 비교하는 agent 별 advantage function 계산을 통해 이를 해결한다. 

 

따라 적절한 default action에 관한 approximations 혹은 assumptions에 의존하는 대신, COMA는 각 agent에 대해 centralized critic에 의존하여 해당 agent의 action만 변경되는 counterfactuals에 대해 추론하는 별도의 baseline을 계산한다. 

 

3. counterfactual baseline을 효율적으로 계산할 수 있는 critic representation을 사용한다. 

: single forward pass에서 다른 모든 agents' action에 따라 주어진 agent의 모든 다른 action에 대한 Q-value를 계산한다. single centralized cirtic이 모든 agent에 사용되기 때문에 모든 agents에 대한 모든 Q-values는 single batched forward pass에서 계산 가능하다. 

 

 

---

Background

: stochastic game G = ⟨S, U, P, r, Z, O, n, γ⟩의 fully cooperative multi-agent task에서 수행된다.

 

 

: agent

 

: env's true state

 

: 각 time-step에서 agent가 선택하는 action

 

: joint action

 

: 모든 agent가 공유하는 reward function

 

: state transition function

 

: observation

 

: observation function

 

: 아래의 조건에 의해 각 agent가 가지는 action-observation history

 

: stochastic policy 

 

 

 

---

Counterfactual Multi-Agent Policy Gradients

Centralized critic 

: 학습이 centralized 되어 있기 때문에 true global state s를 사용할 수 있고, 그렇지 않을 경우 joint action observation histories τ를 사용할 수 있다. 즉, 각 agent's actor는 partial observation O를 사용하여 action을 수행하고, critic은 state 정보와 reward, policy 및 action의 모든 정보를 받아서 각 agent에게 advantage를 부여한다.아래는 이러한 setting을 나타낸다. 

 

 

TD error estimated from this critic which is used in actor

 

→ 각 agent가 partial observable하고 interaction이 불가능한 상황에서, 모든 정보를 볼 수 있는 critic의 역할로 효율적인 cooperative action을 생성할 수 있다. 

 

 

Counterfactual baseline

: TD error는 global reward만 고려하기 때문에 각 actor에 대해 계산된 기울기는 특정 agent's action이 global reward에 얼마나 기여하는지 알 수 없고, agent가 많은 경우 gradient는 더욱 noisy하다. 

 

- 기존의 agent a's action이 default action C^a로 대체될 때 받는 reward와 global reward와 비교하는 shaped reward D^a로 학습하는 method가 있다. 즉, state와 joint-action의 team reward에서 자기 자신 agent의 default action에 따른 보상값 차이로 추정한다. 

 

 

- second term은 agent a's action에 의존하지 않기 때문에, D^a를 향상시키는 agent a의 모든 action은 true global function r(s, u)도 향상시킨다. 

 

shaped reward

 

→ 그러나 이런 approach는 second term을 추정하기 위해 own action과 다른 agents' action을 모두 고려하기 위해 simulator를 추가로 사용하고, default action을 선택하기 모호하다는 단점이 존재한다. 

 

- COMA는 해결을 위해 centralized critic을 사용하여 difference reward를 계산 가능하다. central state s에 대한 joint action u에 대한 Q-value를 추정하는 Q-function을 학습한다. 각 agent에 대해 다른 agent's action을 고정된 상태로 유지하면서, current action u^a에 대한 Q-value를 marginalise하는 counterfactual baseline과 비교하는 advantage function 계산이 가능하다. 

 

 

→ advantage function은 centralized critic을 사용하여 추가 simulation이 아닌 agent's experience에서 직접 학습된 action만 변하는 조건부 counterfactual에 대해 추론하는 각 agent에 대해 별도의 baseline을 계산한다. 

 

- 따라서 COMA에서 policy gradient는 아래와 같다. 

 

 

 

 

Critic representation

: advantage function에서 potential extra simulation을 critic으로 대체하지만 이는 평가 자체가 비용이 많이 들 수 있다. 또한 network의 output node 수는 joint action space 크기와 같으므로 비실용적이다. 해결을 위해 COMA는 baseline 평가를 효과적으로 하기 위한 critic representation을 사용한다. 

 

architectures of the actor and critic

 

- 다른 agent s' action u^-a는 network input의 일부이며 agent a's action Q-value를 output한다. 결과적으로, 각 agent에 대해 actor과 critic의 single forward pass에 의해 counterfactual advantage가 효과적으로 계산된다. 또한 output size는, |U^n|이 아닌 joint action |U|와 동일하다. 

 

→ counterfactual advantage computation 부하 감소를 위해서, 모든 정보를 critic에 삽입하여 advantage function을 근사하게 산출시키는 architecture를 사용한다. 

 

- 해당 논문에서는 discrete action setting에서 실험했지만, Monte Carlo sample로 expectation을 추정하거나 functional forms를 사용하여 continuous action으로 쉽게 확장 가능하다. 

 

 

---

COMA results

- StarCraft scenario에 대한 episode 별 평균 승률을 비교한 결과 모든 실험에서 IAC baseline보다 COMA가 우수했다. 또한 centralized critic은 decentralized critic보다 성능이 뛰어남을 알 수 있다. 

 

 

 

---

Conclusion

: 해당 논문은 decentralized policy에 대한 counterfactual advantage를 추정하기 위해, centralized critic 사용을 제안했다. COMA는 다른 agents' action을 고정된 상태로 유지하면서 single agent's action을 marginalise하는 counterfactual baseline을 사용하여 multi-agent credit assignment problem을 해결한다. 즉, 모든 정보를 볼 수 있는 centralized critic을 도입하여 각 agent의 policy에 따른 advantage를 부여하는 기법이다. team reward만 제공되는 환경에서 advantage 산출을 위해 reward shape를 도입하였고, 효율적 연산을 위해 counterfactual baseline과 critic representation을 도입하였다. 

 

 

https://m.blog.naver.com/jk96491/222018277094

Multi-Agent 강화학습 시리즈 1 - COMA(feat. 게임)