Posts 2. (Foerster 2017 AAAI) Counterfactual Multi-Agent Policy Gradients
Post
Cancel

2. (Foerster 2017 AAAI) Counterfactual Multi-Agent Policy Gradients

목차

1. Main ideas
2. Notation
3. Indepedent Actor-Critic
4. Counterfactual Multi-Agent Policy Gradients
5. COMA Lemma 1
6. Algorithm
7. Reference

Main ideas

  • Centralised critic 사용
  • Counterfactual baseline 사용
  • Critic representation 사용

Notation

  • Stochastic game \(G = <S,U,P,r,Z,O,n, \gamma >\)
    • n agents identified by \(a \in A \equiv \{1, \cdots, n\}\)
    • \(s \in S\)
    • each agent simultaneously chooses an action \(u^a \in U\)
    • Joint action \(u \in U \equiv U^n\)
    • State transition function \(P(s' \mid s,u): S \times U \times S \to [0,1]\)
    • Reward runction \(r(s,u) : S \times U \to R\) and \(\gamma \in [0,1)\)
    • Observation \(z \in Z\)
    • Observation function \(O(s,a) : S \times A \to Z\)
    • Each agent has an action-observation history \(\tau \in T \equiv (Z \times U) ^*\) with conditions a stochastic policy \(\pi^a(u^a \mid \tau^a): T \times U \to [0,1]\)

Indepedent Actor-Critic

  • 가장 간단하게 Multi-agent를 사용하는 방법은 agent 마다 독립된 actor와 critic을 두어 학습하게하는 방법이다.
  • 이를 이 논문에서는 IAC라고 칭한다.
  • 하지만 각 agent는 다른 상태 관측을 하기 때문에 agent끼리 서로 협동하는 것이 아닌 따로 행동한다.
  • 이는 정보 공유가 없어서 학습하는 동안 공동의 목표로 학습하지 못한다는 결과를 보여준다.

Counterfactual Multi-Agent Policy Gradients

  • 제일 처음 말했던 main idea 세 가지를 사용한 방법이다.
  • Centralised critic
    • IAC와 달리 centralisation of the ciritic을 사용한다.
    • 이를 적용하는 방법으로 TD error를 이용하여 Update하는 방식이다.
      \(g = \bigtriangledown_{\theta^{\pi}} log\pi(u \mid \tau_t^a) (r + \gamma V(s_{t+1}) + V(s_t))\)
    • 하지만 global reward만을 고려하기 때문에 각각의 agent가 global reward에 얼마나 기여했는 지를 몰라 학습하기 위한 TD error를 만들기가 어렵다.
  • Counterfactual baseline
    • 각 agent들이 shaped reward를 통해서 학습한다.
      \(D^a = r(s,u) - r(s,(u^{-a},c^a))\)
    • agent a의 action을 \(c^a\)로 대체하여 reward를 얻을 후 이를 global reward를 빼서 해당 agent의 reward를 구하는 방식이다.
    • 이 방식은 agent a의 action을 \(c^a\) default action으로 대체하여 해당 agent의 원래 action과 상관 없는 reward를 생성하여 이를 이용하는 것이 핵심이다.
    • 하지만 \(r(s,(u^{-a}, c^a))\)를 측정하기 위해서 시뮬레이터를 모든 agent에 대해서 계속 사용해야한다는 문제가 있다. 또한 \(c^a\)를 각 환경마다 선정하는 데 어려움이 있다.
    • 이렇게 구한 Q 값을 이용하여 advantage fuction을 구할 수 있다. \(A^a(s,u) = Q(s,u) - \sum_{u'^a} \pi^a(u'^a \mid \tau^a)Q(s,(u^{-a}, u'^a))\)
    • joint action을 고정시켜두고 agent a의 action의 경우의 수를 모두 구하여 value function을 구하여 advantage function을 구하는 방법이다.
  • Critic representation
    • DNN을 사용할 경우 이러한 advantage function을 구하는 것이 오랜 시간(비용)이 든다.
    • 기존에는 advantage fucntion을 구하기 위해 여러번의 DNN inference를 통하여 구하였다.
    • 그래서 advantage function의 만들기 위한 정보를 입력한 후 single forward pass만으로 근사화하여 구할 수 있도록하였다.

Architecture

COMA Lemma 1

  • 알고리즘이 최적의 policy를 찾는 것을 보여주기 위해서는 해당 수식이 convergence를 보여주면 된다.
    \(g_k = E_\pi [\sum_a \bigtriangledown_\theta log\pi^a(u^a \mid \tau^a) A^a(s,u) ]\)
    \(A^a(s,u) = Q(s,u) - b(s,u^{-a})\)
  • 우선 \(g_b\)만을 고려
    \(g_b = -E_\pi [\sum_a \bigtriangledown_\theta log\pi^a(u^a \mid \tau^a)b(s,u^{-a})]\) \(g_b = - \sum_sd^\pi(s) \sum_a\pi(u \mid \tau) \bigtriangledown_\theta log\pi^a(u^a \mid \tau^a)b(s,u^{-a})\) \(= - \sum_sd^\pi(s) \sum_a\sum_{u^{-a}}\pi(u^{-a} \mid \tau -a) \sum_{u^a}\pi^a(u^a\mid \tau^a) \bigtriangledown_\theta log\pi^a(u^a \mid \tau^a)b(s,u^{-a})\) \(= - \sum_sd^\pi(s) \sum_a\sum_{u^{-a}}\pi(u^{-a} \mid \tau -a) \sum_{u^a}\pi^a(u^a\mid \tau^a) \frac{\bigtriangledown_\theta \pi^a(u^a \mid \tau^a)}{\pi^a(u^a \mid \tau^a)} b(s,u^{-a})\)
    \(= - \sum_sd^\pi(s) \sum_a\sum_{u^{-a}}\pi(u^{-a} \mid \tau -a) \sum_{u^a} \bigtriangledown_\theta \pi^a(u^a \mid \tau^a)b(s,u^{-a})\)
    \(= - \sum_sd^\pi(s) \sum_a\sum_{u^{-a}}\pi(u^{-a} \mid \tau -a) \bigtriangledown_\theta \sum_{u^a} \pi^a(u^a \mid \tau^a)b(s,u^{-a})\)
    \(= - \sum_sd^\pi(s) \sum_a\sum_{u^{-a}}\pi(u^{-a} \mid \tau -a) \bigtriangledown_\theta b(s,u^{-a})\)
    \(= - \sum_sd^\pi(s) \sum_a\sum_{u^{-a}}\pi(u^{-a} \mid \tau -a) b(s,u^{-a}) \bigtriangledown_\theta 1\)
    \(=0\)

  • \(g_b\)는 0의 값을 가지므로 variacne를 낮춰주긴하지만 expected gradient에는 영향이 없다.
  • 그렇다면 \(g\)의 앞쪽의 Q function만 있는 부분을 보자.
    \(g= E_\pi [\sum_a \bigtriangledown_\theta log\pi^a (u^a \mid \tau^a) Q(s,u)]\)
    \(= E_\pi [\bigtriangledown_\theta \sum_a log\pi^a (u^a \mid \tau^a) Q(s,u)]\)
    \(= E_\pi [\bigtriangledown_\theta log \prod_a \pi^a (u^a \mid \tau^a) Q(s,u)]\)
    \(\pi(u \mid s) = \prod_a \pi^a(u^a \mid \tau^a)\)
    \(g = E_\pi[\bigtriangledown_\theta log \pi(u \mid s) Q(s,u)]\)
  • 해당 공식은 single action에서 actor-critic 알고리즘에서 convergence를 증명한 공식이다.
  • 그러므로 COMA의 \(g\)는 convergence하고 local optimal policy를 찾을 수 있다.

Algorithm

Algorithm

Reference

1. Foerster, Jakob, et al. “Counterfactual multi-agent policy gradients.” Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 32. No. 1. 2018.

This post is licensed under CC BY 4.0 by the author.