マルコフゲーム入門
強化学習若手の会 Advent Calendar 2021 20日目
1. マルコフゲームって？
通常の強化学習では、エージェントは一人しかおらず、世界は固定されています。 遷移確率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$との差1が(最大ノルムにおいて)$\gamma$ずつ縮まるという性質を持っているので、 これを繰り返し適用すると$V^\pi$を得ることができます。 少しやってみましょう。
$V$を$|\mathcal{S}|$次元のベクトルだとみなすと、最大ノルムの差が縮まります。↩