5.3.1 Multi-Agent Importance Sampling

이 section에서는 IQL의 non-stationarity 문제를 importance sampling 기법을 사용하여 해결하는 것을 보입니다. 보통 RL에서 agent가 off-policy를 배우기 위해 target policy가 만든 분포와 모은 데이터의 분포가 다를때 Importance sampling을 진행합니다. 이런 방식을 응용해, 현재 환경에서 만들 분포와 모은 다른환경에서의 분포에 차이를 importance sampling을 통해 해결할 수 있다는 것이 off-environment의 기본 아이디어입니다. 우리는 각 학습할 때마다 다른 agent들의 policies가 바뀌어 환경 분포가 바뀔 것을 알고 있습니다. 그러므로 off-environment를 이용하여 이 문제를 해결할 수 있습니다.

In Fully-observable MARL environment

Q-function이 실제 state $s$를 볼 수 있다면, 주어진 다른 agent의 policy에 대해 한 agent의 Bellman optimality equation을 다음과 같이 쓸 수 있습니다.

$Q^*_a(s,u^a|\bm{\pi}^{-a}) = \sum_{\bold{u}^{-a}}{\bm{\pi}^{-a}(\bold{u}^{-a}|s)\begin{bmatrix} r(s,u^a,\bold{u}^{-a})+\gamma \sum_{s'}{P(s'|s,u^a,\bold{u}^{-a})\max_{u^{'a}}{Q^*_a(s',u^{'a})}} \end{bmatrix}}$

이 때, 시간이 지남에 따라, agent의 policy가 변하므로 이를 기록하기 위한 시간을 넣은 tuple을 만들면 다음과 같이 표기 가능합니다.

$<s,u^ar,\pi(\bold{u}^{-a}|s),s'>^{(t_c)}$

그렇다면 loss는 replay time $t_r$에 대해 다음과 같이 구할 수 있습니다.

$\mathcal{L}(\theta) = \sum_{i=1}^b\frac{\bm{\pi}^{-a}_{t_r}(\bold{u}^{-a}|s)}{\bm{\pi}_{t_i}^{-a}(\bold{u}^{-a}|s)}[(y_i^{\mathrm{DQN}}-Q(s,u;\theta))^2]$

In Partially-observable MARL environment

partially observable상황에서는 action-observation histories가 agent의 policies뿐만아니라, transition과 observation function과도 연관되어 있기 때문에 좀더 식이 복잡해집니다. 이를 정의하기 위해서 이전의 정의들을 확장해보겠습니다.

state space$\hat{s} = \{s,\bold{\tau}^{-a} \} \in \hat{S} = S \times T^{n-1}$이는 다른 agent들의 이전 history를 포함하여 정의됩니다. 그리고, 그에 상응하는 observation function $\hat{O}(\hat{s},a) = O(s,a)$입니다. reward function은 $\hat{r}(\hat{s},u) = \sum_{\bold{u}^{-a}}{\bm{\pi}^{-a}(\bold{u}^{-a}|\bm{\tau}^{-a})r(s,\bold{u})}$로 joint action에 대해 정의됩니다. 마지막으로 transition probability function $\hat{P}$를 정의하면,

$\hat{P}(\hat{s}'|\hat{s},u) = P(s',\tau'|s,\tau,u) = \sum_{\bold{u}^{-a}}{\bm{\pi}^{-a}(\bold{u}^{-a}|\bm{\tau}^{-a})P(s'|s,\bold{u})P(\tau^{'-a}|\bm{\tau}^{-a},\bold{u}^{-a},s')}$

로 정의할 수 있습니다. 바뀐 정의를 가지고 다시 Bellman Equation를 나타내보겠습니다.

$Q(\tau,u) = \sum_{\hat{s}}{p(\hat{s}|\tau)[\hat{r}(\hat{s},u)+\gamma \sum_{\tau',\hat{s}',u'}\hat{P}(\hat{s}'|\hat{s},u)\pi(u',\tau')p(\tau'|\tau,\hat{s}',u)Q(\tau',u')]}$

다음과 같이 action-observation histories $\tau$에 따른 state $\hat{s}$로 갈확률에 따른 값으로 나타납니다. 이때 양변에 $\sum_{\bold{u}^{-a}}{\bm{\pi}^{-a}(\bold{u}^{-a}|\bm{\tau}^{-a})}$ 를 곱해주면, 정의들에 의해 다음 처럼 정의 가능합니다.

$Q^*_a(s,u^a|\bm{\pi}^{-a}) = \sum_s{p(\hat{s}|\tau) \sum_{\bm{u}^{-a}}\bm{\pi}^{-a}(\bold{u}^{-a}|\bm{\tau}^{-a})[r(s,\bold{u})+\gamma \sum_{r',\hat{s}',u'}P(s'|s,\bold{u})p(\bm{\tau}^{'-a}|\bm{\tau},\bold{u}^{-a},s')\pi(u',\tau')p(\tau'|\tau,\hat{s}',u)Q(\tau',u')}$이 때, 이전엔 $\bm{\pi}^{-a}(\bm{u}^{-a}|s)$이었지만 이번엔 $\bm{\pi}^{-a}(\bold{u}^{-a}|\bm{\tau}^{-a})$에 의존하기 때문에 importance weights $\frac{\bm{\pi}^{-a}{t_r}(\bold{u}^{-a}|s)}{\bm{\pi}{t_i}^{-a}(\bold{u}^{-a}|s)}$는 근사값으로 구해짐을 알 수 있습니다.