4.1. MADDPG
Multi-Agent Deep Deterministic Policy Gradient(MADDPG)는 2017년 발표된 Lowe et al. 의 Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments에서 소개된 알고리즘으로 기존 DDPG 알고리즘을 Multi-Agent의 영역으로 확장하였습니다. MA 세팅은 이론적인 면에서나 실용적인 측면에서나 매력적이지만 여러 Agent가 게임 내에 존재함으로 생기는 env의 non-stationarity 때문에 기존 single-agent의 접근방식으로는 학습이 어려웠습니다. MADDPG는 Centralized training과 Decentralized execution을 이용해 이 문제를 해결하였고 여러 multi-agent 환경에서 다양한 task를 수행하며 agent간의 competition과 cooperation, 그리고 이 둘의 mixed strategy까지 학습하는 데 성공했습니다. 뿐만아니라 explicit한 communication 구조 없이도 여러 agent간의 communication 통한 coordination이 가능함을 보여주었습니다.
Multi-Agent 환경에서 non-stationarity의 원인은 env의 역학이 한 agent의 action에만 의존하지 않는다는데 있습니다. 이는 action에 따른 reward 및 state transition이 여러 agent의 joint action에 따라 달라지기 때문입니다. 단순히 다른 agent의 존재 또는 action을 모른채 observation을 받아 state-action-value 혹은 policy 네트워크를 학습시키면, 독립적인 학습을 하는 single agent의 입장에서는 환경의 변화가 오로지 자신의 action에 따른 것인지 아니면 다른 agent들의 action이나 policy 변화에 따른것인지 구별하기 어렵게 됩니다.
이러한 환경의 non-stationarity는 joint action을 알고있는 경우 비교적 간단한 아이디어를 통해 해결하는 것이 가능합니다. State transition이 일어나는 매 step마다 여러 agent의 policy 변화에 관계 없이 state의 stationarity를 유지할 수 있기 때문입니다. 이는 환경 자체의 stochasticity를 제외하면 state의 transition이 agent들의 현재 state와 joint action에만 의존하기 때문입니다. 그리고 MADDPG의 핵심은 이 아이디어에 기반을 두고 있습니다.
그런데 말입니다, 여기서 joint action을 모두 아는것은 너무 강한 가정이 아닌가 하는 의구심을 가질 수 있습니다. Snake game과 같이 agent간의 simultaneous한 action choice가 이루어지는 게임의 경우 이러한 가정이 충분히 가능하지만 POMDP를 고려한다면 multiplayer game에서 한 agent가 다른 모든 agent들의 joint action을 모두 알고있는 것은 비현실적인 경우가 많습니다. 하지만 actor와 critic을 별도의 network로 학습시키는 Actor-Critic Framework을 고려한다면 훈련과정에서 critic만 모든 agent의 joint action을 알게하고 actor는 자신의 local observation을 사용하도록 제한하는 것이 가능합니다. 이후 실제 test에서는 actor만을 사용하여 test 상황에서 발생할 수 있는 정보부족의 문제를 해결 할 수 있습니다. 또한, 훈련과정에서 critic이 모든 joint action을 알 수 있다는 가정은 필요에 따라 다른 agent의 action를 직접 추론하는 것으로 가정을 완화할 수 있습니다.
실제 경기를 뛰는 N명의 선수(actor)와 이들을 1대1로 훈련시키는 N명의 코치(critic)들을 상상해 봅시다. 선수들은 자신이 보고 듣는 영역의 정보만 알 수 있지만 코치들은 경기장 전체를 내려다보며 다른 선수들을 관찰할 수 있습니다. 또한, 코치들은 다른 코치들과 선수의 전략에 대한 정보를 공유하며 자신의 선수를 훈련시킵니다. 코치들간의 공유되는 정보를 이용해 자신의 선수들에게 적절한 피드백을 줄 수 있으며 자신이 생각하는 훈련방식을 개별 선수에 맞게 적용 가능하기 때문에 각 선수들이 경기에 나갔을 때 자신의 포지션에 맞는 역할을 잘 수행하도록 이끌 수 있습니다.
Fig 1. Overview of MA-AC approach. (Image source: Lowe, et al., 2017)
그러면 multi-agent policy gradient의 수식을 통해 MADDPG의 아이디어를 조금 더 깊이 들여다 보겠습니다.
N명의 player가 있는 게임을 고려합니다.
: set of all agent policies : policy parameters : state distribution under : expected return for agent : state information; obs of all agents(can include additional state info) : centralized action-value function learned separately for each agent
MADDPG를 이해하기 위해서는 Centralized-Decentralized Scheme을 알아야합니다. 동일한 수의 policy
위 구조를 Deterministic policy로 옮기면 다음 수식으로 표현할 수 있습니다.
: continuous policy w.r.t. parameters : set of continuous polices : experience replay buffer contains the tuples : centralized action-value function updated as:
먼저 달라진 점을 살펴보겠습니다. 위의 vanilla PG와 달리 policy
Mulit-Agent Actor Critic Framework는 model에 대한 가정과 communication 방식의 제한 없이 localized agent와 centralized critic만을 이용해 다양한 multi-agent task에서 agent간의 경쟁적, 협동적, 혼합적 행동을 학습시키는데 성공했습니다. 단순히 agent간의 물리적 action으로 인한 상호작용 이외에도 agent간의 signaling을 통한 역할 수행도 가능함을 보여주었습니다. Multi-Agent Snake Game에서 이와 같은 communication을 다룰 기회는 없지만 agent간의 복잡한 competitive strategy를 이끌어내기에 적합한 알고리즘입니다. 원 논문에서는 초기에 설명한 가정을 완화하기 위해 타 agent의 action을 추정하는 방식이나 ensemble policy를 통해 stability를 보완하는 테크닉들을 보여주기도 했습니다.
