Robust Multi-Agent Reinforcement Learning via Minimax Deep Deterministic Policy Gradient

2019년

[Abstract]

이 논문에서는 멀티에이전트 환경에서 상대방의 정책이 바뀌더라도 여전히 일반화에 강인한 deep reinforcement learning (DRL) 에이전트를 만드는 것에 중점을 두었다. 또한 이를 위해 새로운 MiniMax Multi-agent Deep Deterministic Policy Gradient (M3DDPG)를 제안한다. 그리고 제안된 식을 효율적으로 풀기 위해 이들은 Multi-Agent Adversarial Learning (MAAL)을 제안한다.

[1] Introduction

agent 각각의 RL 훈련은 여러 연구를 통해 연구되었지만, 클래식 단일 에이전트가 multi-agent환경에 놓이게 되면 각 에이전트 입장에서 볼때 환경이 non-stationary가 된다. 이런 환경에서는 에이전트의 수가 늘어남에 따라 policy gradient의 분산이 지수적으로 늘어난다. 기존 방법에서는 이미 학습된 에이전트의 테스트 환경에서 상대가 갑자기 행동을 바꾼다면 해당 에이전트의 policy가 굉장히 나쁜 방법일 수 있다. M3DDPG는 클래식 MADDPG의 minimax 확장 버전이며, 이 알고리즘을 이용하면 상대가 갑자기 행동을 바꾸는 상황에서도 잘 작동할 수 있다. 또한 이 새로운 minimax learning objective를 효율적으로 최적화하기 위한 end-to-end approach인 MAAL도 제안한다.

이 논문에서의 주요 개념들은 Multi-agent RL, MiniMax, Robust RL이다. Multi-agent RL 개념에서는 기존 MADDPG 알고리즘에서 사용되었던 decentralized policy와 centralized critic framework가 사용된다. 또한 강인한 policy 학습을 위해 minimax를 사용하였다. 제안된 MAAL은 adversarial learning에서 영감을 받았으며, 이는 GD를 사용해 minimax objective를 최소화하는 방법이다.

[3] Background and Preliminary

RL에서 정의되어야 하는 것은 Q함수, objective, loss이다. 이때 Q함수 $Q(s,a|\theta)$는 $\theta$를 파라미터로 갖는 policy를 따랐을 때 해당 state에서 해당 action을 했을 때 얻을 수 있는 현재 보상 + 예측 보상이고, objective $J(\theta)$는 파라미터를 $ \theta$로 갖는 policy를 따랐을 때의 기대 보상이며, loss $\mathcal{L}(\theta)$는 네트워크에서 줄여야 할 대상으로, 실제 보상과 예측 보상의 MSE이다. $\mathcal{L}$은 Q함수 자체를 학습하는데 사용되고, $J$는 $\theta$를 학습하는데 사용된다.

Markov Games

Markov Game은 $N$개의 에이전트가 있고, state set $\mathcal{S}$가 있을 때 각 에이전트가 각자의 리워드를 최대로 하는 목표를 가지는 게임이다.

Q-Learning and Deep Q-Networks(DQN)

Q-Learning은 policy $\pi$에 대한 action-value 함수를 사용하는데, 이 Q함수는 $t$시간에서 상태가 $s$이고 행동 $a$를 취할 때 얻을 수 있는 리워드의 기댓값($Q^\pi(s, a)=\mathbb{E}[R|s^t=s, a^t=a]$)이다. DQN에서는 loss를 최소화하는 최적의 policy를 찾아 $Q^* $를 학습한다. Q-Learning은 discrete한 action space를 갖는 DRL 에이전트에 가장 적합하다.

Policy Gradient (PG) Algorithms

PG의 주 아이디어는 objective $J(\theta)=\mathbb{E}{s\sim\rho^\pi,a\sim\pi\theta}[R]$ 를 최대화하는 방향의 gradient를 이용해 policy의 파라미터 $\theta$를 바로 찾는 것이다. 이때의 gradient는

$\triangledown_\theta J(\theta)=\mathbb{E}_{s\sim \rho^\pi,a\sim\pi_\theta}[\triangledown_\theta \log\pi_\theta(a\mid s)Q^\pi(s,a)]$

라고 표현될 수 있다.

Deterministic Policy Gradient (DPG) Algorithms

DPG는 PG알고리즘에 deterministic policy $\mu_\theta:\mathcal{S}\rightarrow \mathcal{A}$를 적용한 것이다. 이때 특정 조건 하에서는 gradient를

$\triangledown_\theta J(\theta)=\mathbb{E}_{s\sim \mathcal{D}}[\triangledown_\theta \mu_\theta(s)\triangledown_aQ^\mu(s,a)\mid_{a=\mu_\theta(s)}]$

라고 쓸 수 있다. 이때 $\mathcal{D}$는 replay buffer이다. $\triangledown_aQ^\mu(s,a)$가 존재해야 하기 때문에 actio space $\mathcal{A}$는 연속이어야 한다. Deep deterministic policy gradient(DDPG)는 policy $\mu$와 critic $Q^\mu$를 딥러닝 네트워크로 근사하는 방법이다.

Multi-Agent Deep Deterministic Policy Gradient (MADDPG)

단일 에이전트 RL을 그대로 multi-agent 환경으로 옮기는 것은, 각 agent의 입장에서 수렴에 필요한 Markov assumption을 위배하기 때문에 문제가 된다. 따라서 MADDPG에서는 각 에이전트가 중앙 Q함수를 학습한다. 이때 objective는

$\triangledown_{\theta_i}J(\theta_i)=\mathbb{E}_{x, a\sim\mathcal{D}}[\triangledown_{\theta_i}\mu_i(o_i)\triangledown_{a_i}Q_i^\mu(x, a_1, \cdots, a_N)\mid_{a_i=\mu_i(o_i)}]$

가 되고, $Q_i^\mu$는 각 에이전트 $i$의 Q값을 알려주는 중앙 Q함수이고, $x$는 state information이다. replay buffer $\mathcal{D}$는 튜플 $(x, x’,a_i,\cdots,a_N,r_1,\cdots,r_N)$을 이용해 모든 에이전트에 대한 경험을 저장한다. 중앙 Q함수는 학습할 때만 사용된다.

[4] Minimax Multi-Agent Deep Deterministic Policy Gradient (M3DDPG)

Minimax Optimization

robust한 policy를 학습하기 위해 이 논문에서는 최악의 상황을 항상 고려하도록 policy를 업데이트 하기로 했다. 모든 다른 에이전트가 반대로 행동한다고 가정하는 것이다. 이 논문에서는 새로운 Q함수를 정의했는데,

$Q_{M,i}^\mu(s, a_1,\cdots,a_N)=r_i(s,a_1,\cdots,a_N)+\gamma\mathbb{E}_{s'}\left[\min_{a_{j\not{=}i}}Q_{M,i}^\mu(s',a_1',\cdots,a_N')]\mid_{a_i'=\mu_i(s')}\right]$

로 쓸 수 있다. 다시 말하면, 현재 리워드와 다음 state $s’$에서 얻는 최악 리워드의 기댓값인데, 이는 policy 없이 $Q_M^\mu$를 업데이트 하는 것을 도와준다.

Multi-Agent Adversarial Learning

action space $\mathcal{A}$가 연속적이고 Q함수가 비선형이기 때문에 M3DDPG를 최적화하는 것은 매우 많은 계산이 필요하다. 따라서 이 논문에서는 효율적이고 end-to-end인 방법인 MAAL을 제안한다. 이 방법은

비선형 Q함수를 부분 선형 함수로 근사한다.
최소화의 inner-loop를 한 단계의 GD로 만든다.

위 두 단계를 거친다. 이전 update rule에서 Q함수를 최소화시키는 다른 에이전트의 행동인 $\epsilon$을 이용해 식을 간소화하고, 이를 step size $\alpha$를 갖는 GD로 표현할 수 있다.

Discussion

Connection to Adversarial Training - Adversarial Training에서 학습을 빠르게 할 수 있었던 핵심은 loss 함수를 부분 선형 함수로 근사하고, $\epsilon^* $를 scaled gradient로 근사하는 것이었는데, 모든 에이전트의 action을 input으로 받는 중앙 Q함수 덕분에 M3DDPG에서도 같은 방법을 사용하여 빠르게 할 수 있었다.

Connection to Single Agent Robust RL - 이전에 연구된 robust reinforcement learning (RRL)은 시뮬레이션으로 한 training과 현실세계 testing의 gap을 training 중에 adversarial perturbation $\epsilon$을 넣음으로써 이어주는 방법을 사용했다. MAAL에서는 multi-agent 환경에서 다른 에이전트들의 worst case perturbation $\epsilon$을 넣어주는 방법을 사용했다. 단일 에이전트 입장에서 보면 RRL의 특별 케이스라고 볼 수 있다.

Choice of $\alpha$ - $\alpha=0$이면 M3DDPG는 MADDPG와 같아진다. $\alpha$가 커지면 더 robust하게 학습할 수 있지만 최적화가 어려워진다. 일정한 $\alpha$를 사용하는 것도 unstable한데, gradient의 scale이 매번 달라지기 때문이다. 이전 연구에서는 gradient를 정규화하는 방법을 사용했는데, M3DDPG에서는 일반 감독학습과는 다르게 input의 scale도 매번 달라지기 때문에 이 논문에서는 정규화한 gradient에 input (action) $a_j$의 norm도 곱해준다.

[5] Experiments

이 논문에서는 $N$개의 협력 에이전트와 $M$개의 대적 에이전트, 그리고 $L$개의 랜드마크로 구성된 환경으로 실험한다. 서로 다른 네개의 환경에서 실험을 진행한다.

Comparison to MADDPG

실험에서는 $0\sim1$로 정규화한 리워드를 평가 지표로 삼았는데, M3DDPG가 협력 에이전트이고 MADDPG가 대적 에이전트일 때가 점수가 가장 높았고, MADDPG가 협력 에이전트이고 M3DDPG가 대적 에이전트일 때가 점수가 가장 낮았다. 이로써 M3DDPG가 MADDPG보다 더 좋은 성능을 가졌음을 확인할 수 있다.

Evaluation with Disruptive Adversaries

이들을 서로 대적시키면 서로가 상대의 눈치를 보며 내 리워드를 최대로 하는 행동만을 하기 때문에 최악의 행동만을 하는 대적 에이전트의 상황도 봐야 한다. 이 논문에서는 문제를 제로섬으로 바꾸고 대적 에이전트를 DDPG를 이용해 협력 에이전트의 반대 리워드로 학습시켰다. 이 상황에서도 M3DDPG가 MADDPG보다 나은 성능을 보였다.

[6] Conclusion

많은 장점들에도 불구하고 M3DDPG에는 단점이 있는데, 계산량을 줄이려고 MAAL에서 한 단계의 GD만을 사용하기 때문에 지역적인 worst 상황만을 고려한다.