Mastering Snake Game with Multi-agent RL

본 포스트는 MARL 방법론을 다룹니다.

0. Introduction

하나의 agent와 환경 간의 상호 작용을 기본으로 하는 Single Reinforcement Learning(RL)과 달리, 여러 agent들이 공존하는 환경에서 인공지능을 학습시키는 데에는 다양한 어려움이 존재합니다. 대표적으로 environment의 non-stationarity [1], joint state-action space로 인한 curse of dimensionality [2], 그리고 이에 따른 학습 알고리즘의 scalability [3] 문제를 들 수 있습니다. Multi-Agent Reinforcement Learning(MARL)팀은 Multi-Agent 환경에서 생기는 여러 문제점과 이를 해결하기 위한 다양한 알고리즘을 공부하고 두 가지 게임 환경을 이용해 실험을 진행했습니다. 각 agent가 모두 독립적으로 경쟁하는 구도보다는 Team Markov Game과 같이 Cooperative한 특성과 Competitive한 특성이 혼재되어 있는 Mixed 게임을 염두에 두었고, 여러 agent들의 상호작용을 통한 협력을 유도하기 위해 적절한 environment를 위주로 학습을 진행했습니다.

1. Environments

1.1. Snake Game

DIYA의 활동을 지원해주시는 KC-ML2에서 개발한 Snake Game Environment [4] 는 Single-player 뱀 게임을 Multi-Player 게임으로 변형한 강화학습 환경입니다. 뱀 게임은 2차원 grid 맵 안에서 뱀이 사과를 먹을 때 마다 몸의 길이가 늘어나는 게임입니다. 이를 multi-agent 버전으로 확장하면 동시에 뱀 여러 마리가 하나의 맵 안에 공존하며 사과를 먹으러 다니는 게임이 됩니다. 이동 중인 뱀이 벽이나 다른 뱀의 몸에 부딪히게 되면 부딪힌 뱀은 죽게 되고 최후에 남는 한 마리의 뱀이 게임의 승자가 되는 경쟁적인 개인전 게임 구조입니다. 사과를 많이 먹을수록 몸의 길이가 늘어나기 때문에 하나의 episode 안에서도 게임의 후반부로 갈수록 난이도가 올라가며 정확한 조작과 장기적인 경로계획을 필요로 한다는 특징이 있습니다.

snake_gif
image source: kc-ml2/marlenv/README.md

MARL 팀은 환경에서 나오는 리워드 구조와 게임 종료 조건을 변경하여 경쟁적인 게임 룰을 협력적인 게임 환경으로 변형하여 학습을 진행했습니다.

urteam

기존의 경쟁구도를 유도하기 위한 리워드를 다음과 같이 협력적 리워드 구조로 변경하게 되면 모든 뱀들은 한 팀이 되어 최대한 많은 사과를 먹기위해 행동하도록 학습시킬 수 있습니다. 이 경우 두 마리 뱀이 함께 어느정도 몸집을 키운 뒤, 한 마리가 먼저 죽고 나머지 한 마리가 마저 맵을 가득 채우는 현상을 발견할 수 있었습니다. 게임의 한 스텝이 진행될 때마다 주어지는 Time penalty를 피하기 위해 복잡한 경로 계획을 하며 사과를 더 먹으러 다니는 것보다 차라리 빨리 죽어버리는 전략을 학습한 것입니다. 저희는 두 마리 뱀이 모두 살아남아 서로의 경로를 방해하지 않고 맵을 가득채우는 모습을 원했기 때문에 이 목표를 위해 불필요한 state는 학습에서 사용하지 않도록 두마리 중 한마리라도 죽을 경우 게임이 끝나도록 변경해 Cooperative snake game rule을 구성했습니다.

	Competitive	Cooperative
Fruit	1.0	1.0
Kill	1.0	-1.0
Time Penalty	0.0	-0.01
Terminal Condition	if all snakes are dead	if any of snakes is dead

1.2. Pommerman

Pommerman [5] 은 봄버맨을 벤치마킹한 게임 환경으로, 2차원 공간에서 에이전트들이 폭탄을 놓으면서 서로를 제거하고 이기는 게임입니다. 환경의 설정에 따라서 맵을 바꿀 수도 있고 팀전 혹은 개인전과 같은 다양한 게임을 시작할 수 있습니다. 게임의 구성요소는 1) 봄버맨, 2) 폭탄, 3) 깰 수 있는 상자, 4) 깰 수 없는 벽돌, 5) 아이템 으로 구성되어 있습니다. 아이템은 1) 폭탄 추가, 2) 화력 추가, 3) 발차기 가능 의 세 가지로 이루어져 있습니다.

에이전트가 취할 수 있는 행동은 6가지로 이루어져 있는데, 각각은 다음과 같습니다:
1) 정지(pass), 2) 위, 3) 왼쪽, 4) 아래, 5)오른쪽, 6) 폭탄 놓기.

매 턴마다 에이전트는 다음과 같은 observation을 얻습니다.

1) board: 11x11 게임판 전체의 정보. POMDP 설정을 한 경우 에이전트를 둘러싼 5x5 픽셀을 제외하고 모르는(fog) 상태가 됩니다.

2) position: [0,10] 범위의 두 정수 (x, y)로 위치를 나타냅니다.

3) Ammo: 1개의 정수. 해당 에이전트의 폭탄의 수를 나타냅니다.

4) Blast Strength: 1개의 정수. 해당 에이전트의 화력을 나타냅니다.

5) Can Kick: 1 또는 0의 값을 가지는 1개의 정수. 발로 찰 수 있는지를 나타냅니다.

6) Teammate: [-1, 3] 범위의 1개의 정수. 어떤 에이전트가 해당 에이전트와 같은 팀인지를 나타냅니다.

7) Enemies: [-1, 3] 범위의 3개의 정수들. 어떤 에이전트가 해당 에이전트와 적임을 나타냅니다.

8) Bomb Blast Strength: 정수의 리스트. 각각 에이전트가 가진 화력을 나타냅니다.

9) Bomb Life: 정수의 리스트. 각 에이전트의 관점에서 폭탄이 터지기까지 남은 시간을 나타냅니다.

10) Message: [0, 8] 범위의 두 정수. 팀메이트로부터 받는 정보입니다. 팀메이트가 죽거나 게임이 막 시작했으면 두 정수 모두 0입니다.

렌더링에서 ‘human’ mode rendering 시 위와 같은 이미지가 나오고, ‘rgb array’ mode rendering을 하면 다음과 같은 그리드 기반 이미지가 나옵니다.

pomme pomme

1.3. Sparse and Delayed Rewards

Snake game은 competitive setting에서도 상대방을 죽여 이기는 것 이외의 objective가 존재합니다. 하나의 episode 내에서 게임의 제한 시간이 끝날 때까지 여러 마리의 뱀이 살아있을 경우 최종 순위는 뱀의 몸길이에 따라 정해지기 때문에 사과를 많이 먹어서 몸을 키우도록 reward가 주어집니다. 뱀이 사과를 먹는 즉시 positive reward가 주어지기 때문에 action의 피드백이 즉각적으로 이루어지며 사과를 먹는 행위는 한 에피소드 내에서 상당히 많이 일어나기 때문에 agent가 쉽게 자주 경험할 수 있습니다. 때문에 snake game을 학습하는 agent는 상대적으로 dense한 reward를 통해 학습할 수 있습니다.

반면 pommerman은 게임이 완전히 종료되기 전까진 아무런 리워드가 주어지지 않습니다. 게임의 승패가 결정되는 순간까지 모든 action들에 대한 직접적인 피드백이 이루어지지 않습니다. 게다가 individual agent들의 행동에 대해 분리되어 reward가 주어지는 snake game과 달리 pommerman은 Team Markov Game의 형식에 따라 같은 팀 agent는 동일한 reward를 부여받기 때문에 주어지는 reward가 본인의 행동에 대한 보상인지, 팀원의 행동 때문에 주어지는 것인지 학습하는 데 어려움이 있습니다. 이 문제를 해결하기 위해 게임이 종료되기 전 먼저 죽는 agent를 찾아 개별적으로 penalty를 주는 방식으로도 학습시켜 봤지만, 죽지 않기 위해 숨어서 아무런 행동을 하지 않는 방향으로 학습이 될 뿐 근본적인 문제를 해결하진 못했습니다. snake env에서는 뱀이 사과를 먹는 행위를 env 내에서 쉽게 파악할 수 있는 반면 pommerman env에서는 폭탄을 설치하고 잠시 시간이 흐른 뒤에야 터지며 환경에 영향을 주기 때문에 각 agent의 행동을 추적하는 것이 상대적으로 어려웠습니다.

2. Algorithms

2.1. Single RL Approach

여러 Agent가 동시에 참여하는 게임이라도 학습과정에서는 Single RL의 접근 방식을 택할 수 있습니다. 독립된 개별 agent 들이 나머지 모든 참여자들의 행동을 environment의 일부로 인식한다면 Single RL 알고리즘을 그대로 적용할 수 있습니다. 이렇게 multi-agent 게임의 특성을 별도로 반영하지 않고 Single RL방식을 적용하는 것을 Independent RL이라고 부르며 흔히 MARL의 baseline으로 사용되곤 합니다. 저희는 이 Ind. RL 방식으로 Soft Actor Critic(SAC)과 Proximal Policy Gradient(PPO) 두 알고리즘을 사용해보았습니다.

2.1.1. SAC

Soft-Actor-Critic (SAC)는 굉장히 널리 알려진 off-policy RL 알고리즘입니다. Actor-critic 방식을 사용하기 때문에 value-based 방식에 비해 훨씬 안정적으로 학습이 가능하고, off-policy 방식을 사용하기 때문에 replay buffer에 쌓아둔 데이터를 사용함으로써 on-policy 방식에 비해 훨씬 빠르게 수렴합니다.

SAC의 가장 큰 특징은 entropy maximization을 통해 exploration을 극대화시킨다는 점입니다.

Optimal policy in SAC

$\pi^{*}=\arg \max_{\pi} \mathbb{E}_{\tau \sim \pi} \sum_{k=0}^{\infty} \gamma^{k}\left(R_{k}+\alpha H\left(\pi\left(\cdot \mid \mathbf{s}_{k}\right)\right)\right)$

Optimal policy in original RL

$\pi^{*}=\arg \max_{\pi} \mathbb{E}_{\tau \sim \pi} \sum_{k=0}^{\infty} \gamma^{k}(R_{k})$

기존의 RL과 다른 점이 한눈에 들어오죠? Return을 maximize함과 동시에, 다양한 action을 뽑아내어 trajectory의 다양성을 추구할 수 있는 entropy를 극대화 하는 것입니다. 이 때 entropy 극대화로 인해 optimal한 action이 선택되지 않을 가능성이 있는데, $\alpha$ 값을 학습함으로써 이를 방지할 수 있습니다.

다만 SAC는 continuous action space를 가정하고 만들어진 알고리즘입니다. 물론 discrete setting에서도 동작할 수 있는 Discrete SAC 논문이 제출된 바 있습니다. 사실 discrete action space 에서는 action space의 크기가 무한하지 않기 때문에 entropy의 max값 (target entropy)을 이론적으로 구할 수 있습니다. 즉, entropy maximization을 단순 policy loss update에서만 update 하는 것이 아니라, maximum entropy에 수렴하도록 update 하는 loss term을 추가할 수 있다는 것이죠. 다만! action space가 고정된 discrete 환경에서는 value-based 방식이 더 나은 성능을 보이는 경우도 많다는 점을 알아두세요.

여기서 잠깐! 혹시 Soft-Actor-Critic에서 Soft가 무엇을 의미하는지 아시나요?

바로 Bellman equation에서 argmax 대신 softmax를 사용한다는 뜻입니다.
기존의 Bellman equation은 아래와 같습니다.

$\pi_{V}(s)=\underset{a}{\operatorname{argmax}} \sum_{s^{\prime}} P\left(s^{\prime} \mid s, a\right)\left[R\left(s, a, s^{\prime}\right)+\gamma V\left(s^{\prime}\right)\right]$

원래 argmax를 사용하여 greedy action을 선택하고, 이를 바탕으로 policy를 얻는 것인데, Soft-actor-critic은 argmax 대신 softmax를 사용합니다. 즉, 각 action이 선택될 확률을 포함시켜서 RL update를 한다는 것입니다.

$\pi_{V}(s)=\mathbb{E}[\underset{a}{\operatorname{softmax}} \sum_{s^{\prime}} P(s^{\prime} \mid s, a)[R(s, a, s^{\prime})+\gamma V(s^{\prime})]]$

2.1.2. PPO

PPO는 clipping이라는 방법을 통해 안전한 범위 내에서 정책을 업데이트하는 방법으로 디야의 PPO 포스트에 자세히 정리되어 있습니다.

ppo

2.2. Imitation learning

강화학습에서 일반적으로 환경을 구성하는 요소로 정의하는 MDP는 다음과 같은 구성요소로 이루어져 있습니다.

$\text{MDP} := (\mathcal{S}, \mathcal{A}, P, R, \gamma)$

이 중 ‘reward’ $R ={r_t}$는 ‘에이전트가 얼마나 잘하냐’의 기준으로 환경에서 주는 신호로 생각할 수 있습니다. 하지만 환경에서 reward를 주지 않는 경우가 가끔 있습니다. 또한 몇몇 문제들에서는 reward를 정의하기 어려운 경우가 있습니다. 예를 들어 운전을 하는 에이전트에게 어떻게 하면 일반적으로 운전을 잘하는 것인지, 즉 reward를 explicit하게 정의해주기는 쉽지 않습니다. 해당 경우에 사람이 reward engineering을 통해 정의한 값을 부여할 수는 있습니다. 하지만 해당 reward가 충분한 의미를 담지 못한다면 에이전트가 통제 불가능한 행동을 할 수도 있습니다. 이럴 때에 어떠한 행동이 얼마나 좋은지에 대해 어떻게 에이전트에게 학습을 시킬 수 있을까요?

Supervised Learning 분야에서 수많은 딥러닝 문제는 ‘올바른’ 데이터가 있다면 놀라운 성능으로 학습을 한다는 것을 보였습니다. 만약 우리에게 ‘모범 답안’이 주어진다면 아마도 우리는 reward를 explicit하게 얻지 않고서도 유익한 행동을 ‘따라할’ 수 있을 것입니다. 이러한 아이디어에서 나온 것이 바로 imitation learning 입니다. 즉, 만약에 우리에게 ‘전문가(expert)’ agent가 주어지고 그 전문가가 어떻게 하는지를 배운다면 유의미한 학습을 하지 않을까 하는 방법론이라고 할 수 있습니다. imitation learning은 다른 말로 learning by demonstration 혹은 apprenticeship learning이라고 불립니다.

2.2.1. Behavior Cloning

$D ={(s_t,a^*_t)}$가 주어질 때 이를 바탕으로 Agent의 policy를 supervised learning setting으로 학습시키는 방법을 Behavior cloning이라고 합니다. 이를 위해서 Expert라고 여겨지는 agent의 action과 state을 버퍼에 쌓고 이를 바탕으로 다음 Loss function에 대해서 optimization을 진행합니다.

$\arg\min_{\theta} \mathbb{E}_{(s,a^*)\sim P^*} L(a^*, \pi_\theta(s))$

이는 결국에 agent의 policy를 학습시키는 것입니다. 여기서 Value Function을 학습시키는 방법에 대해서 고민해 볼 수 있습니다. 이러한 의문은 이후에 imitation learning setting에서 value function을 학습시키는 Reverse RL 을 통해 해결할 수 있게 됩니다.

imitation

GAIL은 expert의 trajectory를 사용하여 cost function(reward function)을 알아내고 이후에 policy를 학습하는 방식입니다. Cost function을 배운다는 점에서 IRL(Inverse Reinforcement Learning)과 결을 같이 한다고 이해해도 무방합니다. IRL과 비교하였을 때 GAIL 만의 두드러지는 특징은 GAN(Generative Adversarial Network)를 사용하여 expert의 trajectory와 학습된 policy가 만들어낸 trajectory를 구분한다는 점입니다.

이번 분기에는 Reverse RL 을 이용한 실험까지는 진행하지 못하였습니다. Actor-Critic 모델측면에서 보자면 저희의 실험은 Actor model의 training에서 실마리를 찾은 것이었습니다.

2.3. Human in the Loop

Human-in-the-Loop Reinforcement Learning (HiL-RL)은 기본적인 RL loop에 사람이 직접적으로 개입하여 효율적이고, 더 효과적인 behavior를 만들어내는 알고리즘들을 통칭하는 것입니다. 그 중에서도 Human preference 를 사용하여 reward function을 예측하는 Preference-based reinforcement learning (PbRL)은 두 가지 특징을 가집니다.

Trajectory pair 사이의 preference만을 이용하기 때문에 Non-expert human 도 특정 policy를 학습시킬 수 있다.
reward engineering 하기 어려운 trade-off 관계가 많은 복잡한 task를 해결하는 reward function을 찾아낼 수 있다.

Human-in-the-Loop

Human-in-the-Loop RL

PbRL이 어떻게 동작하는지 자세히 한 번 알아보도록 하겠습니다. PbRL은 총 4가지 step으로 이루어지는데요,
1) trajectory query 추출
2) Human preference labeling
3) Reward function learning
4) Reinforcement learning 으로 이루어집니다.

Step 1. 두 개의 trajectory query 추출하기

H 길이의 state-action sequence로 이루어진 두 개의 trajectory를 replay buffer로부터 추출합니다.

$\sigma^{1}=\lbrace\mathbf{s}_{k}^{1}, \mathbf{a}_{k}^{1}, \ldots, \mathbf{s}_{k+H}^{1}, \mathbf{a}_{k+H}^{1}\rbrace$

$\sigma^2=\lbrace\mathbf{s}_{k}^2, \mathbf{a}_{k}^2, \ldots, \mathbf{s}_{k+H}^2, \mathbf{a}_{k+H}^2\rbrace$

각 trajectory는 독립적으로 추출됩니다. 각 trajectory 는 gif, video 등 시각적 방식으로 non-expert human에게 제공되어, 둘을 직관적으로 비교할 수 있도록 합니다.

pbrl

Step 2. Human preference (feedback) 으로 labeling 하기

추출된 trajectory pair에 아래와 같이 human preference label을 제공합니다. 둘 중 더 나은 trajectory에 1, 별로인 trajectory에 0을 부여합니다. 다만, 우열을 가리기 힘든 경우 0.5의 라벨을 각각 부여합니다.

$y=(1,0)\ \text{if}\ \sigma^1\succ\sigma^2$

$y=(0,1)\ \text{if}\ \sigma^1\prec\sigma^2$

$y=(0.5,0.5)\ \text{if}\ \sigma^1=\sigma^2$

Step 3. Reward function 학습하기

Preference label을 바탕으로 reward function을 학습합니다. 두 trajectory의 reward sum이 더 높은 쪽이 사람에게 선호될 것(preferable)이라는 가정이 깔려 있습니다. reward sum의 softmax값이 trajectory가 선호될 확률이라고 본 것입니다. 즉 preference prediction을 binary classification 문제로 볼 수 있고, cross entropy를 이용하여 loss function을 정의함으로써 reward function $\widehat{r}_{\psi}$를 구할 수 있습니다.

$P_{\psi}[\sigma^{1} \succ \sigma^{0}]=\frac{\exp \sum_{t} \widehat{r}_{\psi}(\mathbf{s}_{t}^{1}, \mathbf{a}_{t}^{1})}{ \sum_{i \in \{0,1\} } \exp \sum_{t} \widehat{r}_{\psi}(\mathbf{s}_{t}^{i}, \mathbf{a}_{t}^{i})}$

$\begin{aligned}\mathcal{L}^{\text {Reward }}=-\underset{(\sigma^{0}, \sigma^{1}, y) \sim \mathcal{D}}{\mathbb{E}}[[&y(0) \log P_{\psi}[\sigma^{0} \succ \sigma^{1}] \\+\ &y(1) \log P_{\psi}[\sigma^{1} \succ \sigma^{0}]]\end{aligned}$

Step 4. 학습된 reward function을 바탕으로 RL 알고리즘 돌리기

학습된 reward function을 가지고 RL 알고리즘을 수행함으로써 human preferable policy를 얻어낼 수 있습니다. 기본적으로 on-policy 기반에서 제안된 알고리즘이기 때문에 PPO나 TRPO를 이용하여 학습합니다. Off-policy로 학습하기 위해서는 몇가지 트릭을 사용하면 되는데요, 아래 논문 [6] 을 참고해 주시면 되겠습니다.

PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training

이 과정을 통해 non-expert human이 RL에 대한 지식 없이도, 원하는 대로 agent를 학습시킬 수 있습니다. 다만 이 방법의 가장 큰 문제는, 사람이 주기적으로 개입해야 하기 때문에 누군가가 컴퓨터 앞에 계속 앉아 있어야 한다는 점인데요. 알고리즘 디버깅을 하기에는 정말 귀찮은 일이 아닐 수 없었습니다. 그래서 만들어 낸 것이 Synthetic human 입니다. PbRL은 기본적으로 reward engineering이 어려운 task에서 큰 힘을 발휘하는 알고리즘입니다. Snake 게임은 reward engineering이 상대적으로 매우 간단하죠. 그렇다면 reward engineering을 해 두고, trajectory queries 중 reward sum이 높은 녀석에게 preference를 부여한다면, 사람이 앉아 있지 않아도 학습이 가능합니다. 이를 Synthetic human PbRL이라고 합니다.

2.4. Multi-Agent RL Approach

MARL 알고리즘은 Indpendent RL과 달리 explicit 하게 multi-agent 구조를 염두에 두고 이를 학습에 활용하도록 설계되어 있습니다. Discrete action space에 적용할 수 있는 MARL의 대표적인 알고리즘으로는 COMA와 QMIX가 있습니다.

2.4.1. COMA

Counterfactual Multi Agent Policy Gradient [7] 알고리즘은 기존 PG의 Advantage 항을 Counterfactual Advantage로 대체하여 다른 agent들의 행동이 동일하고 나의 행동만 변경되었을 경우의 Q value를 반영해 Advantage를 계산합니다.

where Counterfactual Advantage $A^a(s, \boldsymbol{u})$ is defined as follows,

Centralized critic을 통해 계산한 Advantage 값은 각 agent들의 policy를 학습하는 단계에서만 사용하기 때문에 학습이 끝난 뒤 Execution 단계에서는 모든 agent은 decentralized되어 작동할 수 있습니다.

2.4.2. QMIX

QMIX [8] 는 cooperative multi-agent system 문제를 해결하기 위한 알고리즘입니다. 두 가지 전제조건을 가지고 있는데요.

Decentralized agent: 각각의 agent들은 test 단계에서 서로 communication 없이 각자의 policy 대로 움직입니다.
Total reward: reward는 개별적인 agent에 제공되지 않고, 전체 팀에 하나의 reward로 제공됩니다.

이를 해결하기 위한 QMIX의 알고리즘 모식도는 다음과 같습니다. 각각의 agent는 DRQN으로 구성된 policy network를 가지고 있습니다. 각 agent의 Q value 결과값은 mixing network를 통과하여 total Q value 결과값을 내놓게 됩니다. Total reward를 알고 있기 때문에 total Q value에 대한 학습이 가능하죠.

Untitled

중요한 것은 mixing network를 어떻게 구성하느냐는 것입니다. 여기서 QMIX는 cooperative setting에 대한 중요한 수식을 사용합니다.

$\frac{\partial Q_{total}}{\partial Q_i}\geq0$

이 수식을 만족한다면, decentralized agent가 communication 없이 greedy action을 선택하더라도, total Q value를 최대화 하는 action을 선택하는 것과 같아진다는 것입니다. 이 조건을 만족하기 위해 mixing network에 $W_1, W_2 \geq0$ 을 사용하였습니다.

2.4.3. Graph Convolution PPO

graph convolutional actor critic은 위에서 설명한 COMA와 QMIX의 핵심을 동시에 표현할 수 있는 자유도를 지닙니다. 각 agent에 graph(lower-lever graph)를 부여하고 그 graph로 하여금 local observation을 적당한 forward step동안 encoding 하게합니다. training phase에서 $Q$를 계산할 때, input을 encoding 하는 동안 lower graph끼리의 연결선(higher-level graph)을 통해 message passing이 일어나게 요구하는 것이 중요합니다. 이는 centralized critic spirit에서 벗어나지 않게 하기 위함이지요. 반대로 decentralized actor는 higher-level graph를 고려하지 않는 것으로 표현합니다.

각 agent $n$의 lower-graph에서 구해지는 $Q_n$은 전체 agent의 $Q_{\mathrm{tot}}$를 다음과 같이 표현합니다.

$Q_{\mathrm{tot}} = Q_{\mathrm{tot}}(Q_1, \dots, Q_n)$

$\frac{\partial Q_{\mathrm {tot}}}{\partial Q_n}>0$

$Q_{\mathrm {tot}}$를 표현하는 다양한 방법을 고안하는 것이 model capacity를 높이는 데 지대한 역할을 할 것임이 분명합니다. 하지만 이러한 논의는 다음 단계에서 진행하는 것으로 하고, 우리는 여기에서 매우 단순한 형태인 $Q_{\mathrm {tot}} = \sum_n Q_n$를 요구했습니다. 또한 joint action을 표현하는 분포에 대하여도 가장 간단한 형태인 $\Pi_{\mathrm {tot}} = \prod_n \pi_n$을 요구했습니다. 이렇게 하면 문제는 상당히 간단해집니다. 단순히 각 agent의 sampled path로부터 구한 loss를 average하여 gradient를 구하는 것으로 학습하게 할 수 있습니다. REINFORCE loss 혹은 surrogate loss를 구할 때 주로 쓰이는 advantage 또한 다음과 같이 single agent 환경에서와 같은 꼴로 표현할 수 있는데요,

$A_n(s, a_n) = Q(s, a_n) - Q_n(s)$

이러한 단순한 형태는 counterfactual advantage에 $Q_{\mathrm{tot}} = \sum_n Q_n$을 요구하는 것으로 얻을 수 있기도 합니다.

3. Results

3.1 Immitation Learning

아래 그림은 실제 Expert(Skynet 모델, 2019 년 Neurlips contest 5위) 와 이에 대해서 behavior cloning을 진행한 결과입니다.


expert	10 episodes with 2 epoch	50 episodes with 1000 epoch

포머맨 env는 게임의 Dynamics 자체가 toytask RL env에 비해 상당히 높은 복잡도를 갖고 있으면서 동시에 극단적으로 sparse한 reward setting 이라는 점에서 RL을 이용해 학습하기 굉장히 까다로웠습니다. 또한 에이전트의 exploration을 장려하는 것이 특히 어려운 과제였는데, 위 결과에서도 확인할 수 있듯 Expert model을 이용한 behavior cloning으로도 폭탄에 대한 회피 기제는 학습할 수 있었습니다.

실험 결과에서 흥미로웠던 점은 생각보다 많은 에피소드가 필요하지 않았다는 점입니다. 실험을 진행하는 동안 가장 큰 병목은 episode를 쌓는데서 발생했습니다. 데이터를 쌓는 데 시간이 오래걸리긴 하지만 상당히 적은 episode로도 어느정도 policy가 학습되는 것을 보면 차라리 사람이 직접 플레이를 해서 episode를 쌓는게 나을 것 같다는 생각이 들었습니다. (그래서 사람이 플레이를 하고 해당 episode를 저장하는 스크립트도 만들어 두었습니다).

3.2. Cooperative Snakes


Reward Engineering	RE + Terminal Condition


RE + Terminal Condition	Finder logo from mac os X

3.3. Graph Convolution Snakes


Reward Engineering	RE + Terminal Condition

3.4. Preference based RL

아쉽게도 이런저런 여건 상 사람이 직접 preference RL을 수행하지는 못했습니다. Synthetic human PbRL의 결과를 보시죠


PbRL (with SAC)

References

[1] Yang, Yaodong, et al. “Mean field multi-agent reinforcement learning.” International Conference on Machine Learning. PMLR, 2018.
[2] OroojlooyJadid, Afshin, and Davood Hajinezhad. “A review of cooperative multi-agent deep reinforcement learning.” arXiv preprint arXiv:1908.03963 (2019).
[3] Lowe, Ryan, et al. “Multi-agent actor-critic for mixed cooperative-competitive environments.” Advances in neural information processing systems 30 (2017).
[4] ML2, “Marlenv, Multi-agent Reinforcement Learning Environment”, 2021. (link)
[5] Resnick, Cinjon, et al. “Pommerman: A multi-agent playground.” arXiv preprint arXiv:1809.07124 (2018).
[6] Lee, Kimin, Laura Smith, and Pieter Abbeel. “Pebble: Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training.” arXiv preprint arXiv:2106.05091 (2021).
[7] Foerster, Jakob, et al. “Counterfactual multi-agent policy gradients.” Proceedings of the AAAI conference on artificial intelligence. Vol. 32. No. 1. 2018.
[8] Rashid, Tabish, et al. “Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning.” International Conference on Machine Learning. PMLR, 2018.

Written by 정은기, 조재경, 이용선, 엄의섭, 서동진

모든 실험에 사용한 코드는 DIYA 동아리 저장소에서 확인하실 수 있습니다.

DIYA는 동아리 활동 및 GitLab 운영에 머신러닝 연구조직 KC-ML2의 지원을 받고 있습니다.
본 프로젝트는 AI 전문기업 Surromind에서 지원받은 연산자원을 이용해 실험을 진행했습니다.