1. マルコフゲームって？

Note: このブログは強化学習若手の会 Advent Calendar 2021 20日目の記事として書かれました。遅れてすみません。

通常の強化学習では、エージェントは一人しかおらず、世界は固定されています。遷移確率Pは変化しません。この設定では、エージェントは例えば期待割引報酬和 $\mathbb{E}_{\pi}[ \sum_{t=0}^\infty \gamma^t r(s_t)]$ を最大化するような方策を学習します。

一方で、学習するエージェントがいくつかいる場合はどうでしょうか？すると、エージェントがもらえる期待報酬和は他のエージェントの方策 $\pi_0, \pi_1, ..., \pi_k$ に依存してしまいます。では、 $\mathbb{E}_{\pi_0, \pi_1, ..., \pi_k}[ \sum_{t=0}^\infty \gamma^t r(s_t)]$ を最大化すればいいのかというと、必ずしもそうではありません。 利害関係が対立する場合があるからです。このような場合に対し、どのように学習の目標を設計し、また実際に学習することができるのでしょうか？

このブログでは、このようなマルチエージェント設定での学習を扱うフレームワークの一つであるマルコフゲームに注目し、その性質について概観します。特に、

MDPにおける価値関数の基本定理のナッシュ均衡解への拡張
Hannan consistent
協力ゲームの一般化であるMarkov Potential GameとそのMDPへの帰着について扱います。論文については適宜ポインタを示しますが、以下の2つの論文/ブログ記事については広範に参照しています。
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms
Recent Progresses in Multi-Agent RL Theory

MDPについての説明はアルバータ大学の講義資料およびその日本語訳を参照しています。

なお、このブログは自分が勉強用に書いたものなので、やや不親切な記述があるかと思いますが、ご了承願います。

2. マルコフ決定過程と基本定理

マルコフゲームの説明に入る前に、一人で学習する設定であるマルコフ決定過程 (Markov Decision Process, 以後MDPと呼ぶ)を使って、少しウォーミングアップしましょう。

定義1: MDP

MDP $\mathcal{M}$ は、以下から成る。

(有限)状態集合 $\mathcal{S}$
(有限)行動集合 $\mathcal{A}$
状態遷移確率 $P: \mathcal{S} \times \mathcal{A} \rightarrow \Delta(\mathcal{S})$
- $\Delta(\mathcal{S})$ は $\mathcal{S}$ 上の確率分布の空間（確率単体）
- 状態 $s$ で行動 $a$ をとったとき $s'$ に遷移する確率を $P(s'|s, a)$ と書く
報酬関数 $r: \mathcal{S} \times \mathcal{A} \rightarrow [0, 1]$
- 状態 $s$ で行動 $a$ をもらえる即時報酬を $r(s, a)$ と書く
割引報酬率 $0 \leq \gamma < 1$
初期状態分布 $\mu \in \Delta(\mathcal{S})$

いま、エージェントとして、「記憶のない」方策 $\pi: \mathcal{S} \rightarrow \Delta(\mathcal{A})$ を考え、 $\pi(a|s)$ により状態 $s$ で行動 $a$ をとる確率を表記します。ある方策 $\pi$ を固定したとき、エージェントがもらう報酬の期待値を以下のように書きます。

定義2: 状態価値関数 $V^\pi$ ・状態行動価値関数 $Q^\pi(s, a)$ ・期待リターン $G^\pi$

$$ \begin{align*} V^\pi(s) &= \mathbb{E}_{\pi} \left[\sum_{t = 0} ^\infty \gamma^t r(S_t, A_t)\right] \\ &= \sum_{a \in \mathcal{A}} \pi(a|s)\left(r(s, a) + \gamma \sum_{s'\in\mathcal{S}} P(s'|s,a) V^\pi(s)\right) \\ Q^\pi(s, a) &= r(s, a) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s,a) V^\pi(s) \\ G^\pi &= \sum_{s \in \mathcal{S}} \mu(s) V^\pi(s) \end{align*} $$

ここで、 $S_t, A_t$ は時刻 $t$ での状態・行動に対応する確率変数です。このとき、(割引)報酬和の期待値 $G^\pi$ を最大化することがエージェントの目標であり、その目標を達成する方策を最適方策 $\pi^*$ と書きます。

$\pi^*$ を求めるための非常に強力な道具がベルマン作用素(Bellman operator)と呼ばれる一連のオペレーターです。

定義3: 方策 $\pi$ についてのベルマン演算子

$V$ を任意の価値関数とする。このとき、方策 $\pi$ に付随するベルマン演算子 $\mathcal{T}^\pi$ は $V$ を $\mathcal{T}^\pi V$ に写像する。 $\mathcal{T}^\pi V$ は以下のように与えられる。

$(\mathcal{T}^\pi V)(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \left( r(s, a) + \sum_{s' \in \mathcal{S}} P(s'|s,a) V(s') \right)$

これだけだとだから何?という感じがしますが、この演算子は一回の適用で真の $V^\pi$ との差¹が(最大ノルムにおいて) $\gamma$ ずつ縮まるという性質を持っているので、これを繰り返し適用すると $V^\pi$ を得ることができます。少しやってみましょう。

$V$ を $|\mathcal{S}|$ 次元のベクトルだとみなすと、最大ノルムの差が縮まります。↩