目次と前回の記事
Python のバージョンとこれまでに作成したモジュール
本記事のプログラムは Python のバージョン 3.13 で実行しています。また、numpy のバージョンは 2.3.5 です。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| mbtest.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義 |
| tree.py | ゲーム木に関する Node、Mbtree クラスなどの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
今回の記事の内容
前回の記事では最適化問題の定義と性質について説明し、以下の事を示しました。
- 強化学習は、大規模な多変数の最適化問題を解くものである
- 最適化問題には、「目的関数の表現力を高くすると、一般的に最適解を見つけることが困難になる」というトレードオフがある
- そのため、適度な表現力と解きやすさを兼ね備えた、バランスの良い目的関数を設定することが重要である
今回の記事では「マルコフ性」という概念を導入することで、強化学習の目的関数にこのようなバランスの良い性質を持たせることができる仕組みについて解説します。
強化学習の用語や記号については以前の記事と前回の記事を参照して下さい。
確率過程と強化学習の履歴
マルコフ性（markov property）は 確率過程が持つ性質の一種 です。そのため最初に確率過程について説明します。その後で強化学習の履歴が確率過程であることを示し、強化学習の目的関数の最適化するためには、確率過程の確率分布（確率質量関数）を求める必要がある ことを示します。
確率過程
「確率過程（stochastic process）」とは、「状態が確率的に変化していく様子と解釈できる、確率変数の集まりで表現された数学的対象（データの集まり）」1の事を表します。
例えば、「サイコロを何度も振って出目を記録していく」という作業において「出目」を「状態」と考えると、サイコロの出目が確率的であることから「状態」がサイコロを振ることによって「確率的に変化」していきます。このサイコロを振るたびに変化する「状態」を表す確率変数を $X_1$、$X_2$、$X_3$、・・・ のように並べると、これらの値は状態が確率的に変化していく様子を表します。このような確率変数の集まり（数列）で表されるもののことを確率過程と呼びます。
参考までに Wikipedia の確率過程の項目のリンクを下記に示します。
強化学習の履歴と確率過程
強化学習の 1 エピソードは初期状態 $s_0$ から始まり、各ステップで「行動」、「即時報酬」、「次の状態」という 3 種類の情報が得られます。前回の記事で説明したように、これらの情報の集まりのことを「履歴」と呼び、ステップ $t$ の状態、行動、即時報酬を $s_t$、$a_t$、$r_t$ と表記した下記の数列で表します。なお、以降はエピソードのステップ数が $n$ であるものとして説明を行います。
$s_0$、$a_0$、$r_0$、$s_1$、$a_1$、$r_1$、・・・、$s_{n-1}$、$a_{n-1}$、$r_{n-1}$、$s_n$
強化学習の 1 つのエピソードでは、環境の初期状態 $s_0$ からそれぞれのステップ $t$ で下記の行動を取り続けます。なお、決定論的な状態遷移は特定の状態へ遷移する確率を 100 % とした確率的な状態遷移の一種であると考えることができるので、下記では状態遷移を確率的であるものとして説明しました。即時報酬に関しても同様です。
- 確率的な方策 $π(a_t \mid s_t)$ によって、行動 $a_t$ を 確率的に選択 する
- 選択した行動によって、状態遷移関数 $P(s_{t+1} \mid s_t, a_t)$ に基づいて環境の状態が $s_t$ から $s_{t+1}$ に 確率的に遷移 する
- 選択した行動と遷移した環境の状態によって、報酬関数 $P(r_t \mid s_t, a_t, s_{t+1})$ に基づいて 確率的な即時報酬 $r_t$ が得られる
上記から、「履歴」を表す数列の要素はすべて確率的な値であるため、何らかの確率分布から抽出された実現値 であると考えることができます。従って、$S_t$、$A_t$、$R_t$ をそれぞれ $s_t$、$a_t$、$r_t$ が従う確率分布を表す確率変数とすると、強化学習の 1 エピソードで得られた履歴 は下記の確率変数の数列で表現された、各ステップでの「状態」、「行動」、「即時報酬」が確率的に変化していく 確率過程そのものである ことがわかりました。
$S_0$、$A_0$、$R_0$、$S_1$、$A_1$、$R_1$、・・・、$S_{n-1}$、$A_{n-1}$、$R_{n-1}$、$S_n$
上記の方策関数、状態遷移関数、報酬関数は現在の状態のみに依存する「マルコフ性」を満たす場合のものですが、それらが過去の状態にも依存するようなマルコフ性を満たさない関数であっても「履歴」が確率過程であることに変わりはありません。
目的関数を表す式とその性質
前回の記事で説明したように、強化学習の目的はエピソードの環境の初期状態 $s_0$ における状態価値 $V_Π(s_0)$ を最大化する最適方策 $Π^*$ を求めることです。
また、前回の記事で説明したように、状態価値 $V_Π(s)$ は状態 $s$ から方策 $Π$ に従って行動を取り続けた場合に得られる累積報酬の期待値であることから、累積報酬を表す確率変数を $G$ と表記すると下記の式で定義されます。
$V_Π(s) = E[G \mid s, Π]$
ステップ $t$ 以降の累積報酬の実現値 $g_t$ は、即時報酬の和として下記ので表されます。
$g_t = r_t + r_{t+1} + ．．．+ r_n = \sum_{i=t}^{n-1}r_i$
従って、累積報酬を表す確率変数 $G_t$ は、下記のように各ステップの即時報酬を表す確率変数 $R_i$ の和として定義できます。
$G_t = R_t + R_{t+1} + ．．．+ R_n = \sum_{i=t}^{n-1}R_i$
この式を $V_Π(s) = E[G \mid s, Π]$ に適用することで、下記の式が導かれます。最後の式の変形は以前の記事で説明した期待値の和の公式 $E[X + Y] = E[X] + E[Y]$ を用いました。
$V_Π(s_0) = E[G_0 \mid s_0, Π]$
$= E[\sum_{i=0}^{n-1}R_i \mid s_0, Π]$
$= \sum_{i=0}^{n-1}E[R_i \mid s_0, Π]$
確率変数 $X$ の期待値は、その確率分布を表す確率質量関数を用いた下記の計算されます。
$E[X] = \sum_{x}P(X=x)$
このことから、各ステップの即時報酬の期待値 $E[R_i \mid s_0, Π]$ を求めるには、確率変数 $R_i$ の確率分布（確率質量関数）を特定する必要があることがわかります。
ここで、各ステップでの即時報酬 $r_t$ は状態 $s_t$、行動 $a_t$、次の状態 $s_{t+1}$ に依存する $P(r_t \mid s_t, a_t, s_{t+1})$ によって確率的に決定されます。さらに、行動 $a_i$ は方策 $π(a_i \mid s_i)$ に、次の状態 $s_{i+1}$ は状態遷移関数 $P(s_{i+1} \mid s_i, a_i)$ に依存します。
従って、任意のステップにおける $R_t$ の確率質量関数を特定するためには $S_i$、$A_i$ の確率質量関数を特定する必要があります。
このことから、強化学習の最適化問題には下記の本質的な課題があることがわかります。
「目的関数 $V_Π(s)$ の具体的な数式を決定するためには、履歴を表す確率過程のすべての確率変数に対する確率質量関数を求める必要がある」。
確率過程の確率質量関数の定式化とマルコフ性の重要性
最初に一般論として、下記の確率変数の数列で表される確率過程の確率質量関数の定式化について説明します。
$X_1$、$X_2$、・・・、$X_{n-1}$、$X_n$
強化学習が対象とする下記の「履歴を」表す確率過程についてはその後で説明します。
$S_0$、$A_0$、$R_0$、$S_1$、$A_1$、$R_1$、・・・、$S_{n-1}$、$A_{n-1}$、$R_{n-1}$、$S_n$
なお、以降の説明では強化学習の慣習にならって $t$ 番目の確率変数を $X_t$ を「ステップ $t$ の確率変数」と表記することにします。ただし、確率過程では一般的に最初の状態の番号を 1 とすることが多いため、本記事の一般論ではステップ数を 1 から数える自然数としました。
確率質量関数の求め方
すべての $X_t$ の確率質量関数を求めるということは「すべてのステップ $t$」と「各変数がとりうるすべての状態 $x_t$」の組み合わせに対して $P(X_t=x_t)$ の具体的な値を特定することを意味します。
確率過程の各確率変数が共通してとりうる状態の集合（状態空間）を $\mathcal{X}$ と表記すると、この問題は数学的に以下のように定式化されます。
$\text{すべての } t \in {1, 2, \dots, n} \text{ および } x_t \in \mathcal{X} \text{ に対して } P(X_t=x_t) \text{ を求めよ}$
また、全称記号（$\forall$）を用いた定式化は以下のようになります。
$\forall t \in {1, 2, \dots, n}, \forall x_t \in \mathcal{X},\text{ に対して } \quad P(X_t=x_t) \text{ を求めよ}$
状態遷移関数の定式化
確率過程を表す確率変数の数列が「状態が確率的に変化していく様子と解釈できる確率変数の集まり」と定義されることから、この確率変数の数列を「時間の経過によって変化する状態」とみなすことができます。
まだ起きていない 未来の状態が現在の状態に影響を及ぼすことはない ため、下記のステップ $t$ までの具体的な状態（実現値）が得られた場合に次の未来のステップ $t+1$ の状態が $x_{t+1}$ となる確率は、現在と過去の状態に影響を受ける可能性はありますが、未来の状態に影響を受けることはありません。
$x_1$、$x_2$、・・・、$x_t$
従って、上記の場合に次のステップ $t +1$ で状態 $x_{t+1}$ に推移する確率は下記の 条件付き確率 によって定式化できます。
$P(X_{t+1}=x_{t+1} \mid X_1=x_1, X_2=x_2, ．．．, X_t=x_t)$
これは「ステップ 1 からステップ $t$ までの状態が $x_1$、$x_2$、・・・、$x_t$ である」という条件のもとで「ステップ $t+1$ の状態が $x_{t+1}$」という条件付き確率を表します。
この関数は「現在までのすべての履歴」から「次の状態への遷移」の確率を表す、強化学習における 状態遷移関数 と同じ役割を果たすので、本記事では以後はこの関数を「状態遷移関数」と表記することにします。
また、強化学習では「状態遷移関数」が環境によって定義されているので、以後の説明ではこの状態遷移関数があらかじめ定義されており、過去の状態 $x_1$、$x_2$、・・・、$x_t$ と次の状態 $x_{t+1}$ を与えれば必ず具体的な値が求まるものとします。
なお、この状態遷移関数と、通常の確率質量関数を区別できるように、以後は状態遷移関数を下記のように遷移（transition）の頭文字を取って $P_T$ と表記することにします。
$P_T(X_{t+1}=x_{t+1} \mid X_1=x_1, X_2=x_2, ．．．, X_t=x_t)$
確率過程の確率質量関数の定式化の手順
確率過程における各ステップの確率質量関数は、以下の手順によって順番に定式化（計算）することができます。
初期状態（ステップ 1）の場合
ステップ 1 ではそれ以前の状態が存在しないので、ステップ 1 の状態が $x_1$ となる確率は、条件が存在しない「状態遷移関数」$P_T(X_1=x_1)$ と等しくなります。
これは、ステップ 1 での確率質量関数 $P(X_1=x_1)$ そのものであるので、ステップ 1 の確率質量関数は下記の式で表されます。
$P(X_1=x_1) = P_T(X_1=x_1)$
ステップ 2 以降の場合
ステップ 2 以降の確率質量関数は、以下の手順を繰り返すことで機械的に求めることができます。なお、手順 2 の具体的な計算方法についてはこの後で詳しく解説します。
- 次に計算を行うステップ数を表す $t$ を 2 とする
- これまでに計算した「ステップ $t-1$ までの確率質量関数」と、「ステップ $t$ への遷移を表す状態遷移関数」を用いて、ステップ $t$ のすべての状態 $x_t$ に対する確率質量関数 $P(X_t=x_t)$ 計算する
- $t$ が最後のステップである $n$ の場合は処理を終了し、そうでない場合は $t$ に 1 を加えて手順 2 に戻る
状態遷移関数がどれだけ複雑であるか によって、手順 2 の具体的な計算の難易度が劇的に変わります。そこで、具体例を挙げながらその複雑さと計算量の違いについて説明します。
独立同分布における確率質量関数の定式化
最初の具体例として、今回の記事の最初に例示した「サイコロを振った出目を次の状態とする」という確率過程の確率質量関数を定式化します。
この確率過程では、各ステップの状態を決める「サイコロ振る」という試行は「互いに独立」しており、何回目であっても各出目の出現確率は同一（1/6）です。従って、各ステップの状態を表す確率変数 $X_1$、$X_2$、$X_3$、・・・ は独立同分布に従います。そのため、この場合の状態遷移関数は常に条件が存在しない $P_T(X_t=x_t)$ となります。
独立同分布の場合は、次の状態の確率は過去の履歴に一切依存しません。そのため、状態遷移関数は常に条件のない $P_T(X_t=x_t)$ と等しくなります。その結果、すべてのステップにおける確率質量関数は、状態遷移関数そのものと一致します。
この例での状態遷移は、ステップ数やそれまでの状態に関わらず、常に 1 から 6 のそれぞれの状態に 1/6 の確率で遷移します。従って任意のステップ $t$ の確率変数 $X_t$ の確率質量関数は下記のように状態遷移関数と同一になります。
$P(X_t=x) = P_T(X_t=x) = \begin{cases}
1/6 & x \in {1, 2, 3, 4, 5, 6}\\
0 & \text{それ以外の場合}
\end{cases}$
このように、確率過程が 独立同分布という非常に強い制約を持つ 場合は、各ステップの確率質量関数が状態遷移関数と同じになるため容易に求めることができます。しかしその反面、過去の経緯が未来に一切影響を与えないため、確率過程としての 表現力が著しく低い という致命的な欠点があります。
例えば、強化学習の履歴の確率過程にこの独立同分布の制約をそのまま当てはめると、以下のような極端な設定になってしまいます。
- 状態、行動、即時報酬がそれぞれ 6 種類あり、いずれも 1 ~ 6 の整数で表現される
- すべてのステップでどの状態、行動、即時報酬も常に均等な 1/6 で発生する
現実の環境では、〇× ゲームのように現在の状態（現在の局面）が未来の状態（次の局面）に影響を及ぼすという、時間的な因果関係を持つことが一般的です。そのため、すべてのステップで「状態遷移、行動、即時報酬の発生確率が過去と無関係に常に一定」という非常に強い制約を満たすような実用的な強化学習の題材はほどんど存在ません。
従って、一般的な強化学習では履歴に独立同分布という制約を用いることはできません。
マルコフ連鎖における確率質量関数の定式化
独立同分布よりも制約が弱く、強化学習で極めて重要な役割を果たすのが マルコフ性 です。
マルコフ性の厳密な定義とマルコフ連鎖
前回の記事ではマルコフ性を『状態遷移、即時報酬、方策が「現在の状態のみに依存する性質』と説明しましたが、確率過程においては数学的に以下のように定義されます。
「現在状態が明らかなら、未来状態は過去履歴から独立して予測される」
これはWikipedia のマルコフ性の項目に記載された口語的な定義です。確率過程において未来の状態は確定的な値ではなく確率的に決定されるため、ここでは「予測」という用語が用いられています。
この定義をより分かりやすく言い換えると、以下のようになります。
- 現在の状態さえ分かれば、それより過去の履歴をすべて無視して未来を予測できる
- 未来の状態への状態遷移を表す状態遷移関数（条件付き確率分布）が、現在の状態のみに依存し、過去のいかなる状態にも依存しない
下記は、マルコフ性を確率論の数式で厳密に定式化したものです。
$P_T(X_{t+h}=x_{t+h} \mid X_1=x_1, X_2=x_2, \dots, X_t=x_t) = P_T(X_{t+h}=x_{t+h} \mid X_t=x_t)$
左辺は「ステップ $t$ までの全履歴が与えられた」という条件のもとで、それより先の未来のステップ $t+h$ （ただし $h \ge 1$）で状態が $x_{t+h}$ となる確率を表す状態遷移関数です。
左辺は「過去の全履歴」を条件にしていますが、マルコフ性が成り立つ場合は、右辺のように「現在の状態 $X_t$」だけを条件としたシンプルな状態遷移関数で表すことができます。
このようなマルコフ性を持つ確率過程を「マルコフ過程（Markov process）」と呼び、特に状態空間 $\mathcal{X}$ が離散的であるものを「マルコフ連鎖（Markov chain）」と呼びます。
未来へのステップ幅を最も小さい $h=1$ とすると、上記の式は「次のステップ $t+1$ の状態が、現在のステップ $t$ の状態のみに依存する」という状態遷移関数になります。
$\forall t \in {1, 2, \dots, n-1}, \quad P_T(X_{t+1}=x_{t+1} \mid X_t=x_t)$
マルコフ連鎖では、この「1ステップ先の状態遷移関数」をベースにして、任意のステップにおける確率質量関数を定式化することができます。
「1ステップ先（$h=1$）の状態が現在の状態のみに依存する」という性質が満たされていれば、「任意の未来（$h \ge 1$）の状態が現在の状態のみに依存する」という性質も自動的に満たされます。
厳密な証明は、以下のような数学的帰納法によって導くことができます。
- $h=1$ のとき：
前提条件より、「$X_{t+1}$ は $X_t$ のみに依存する」が成り立つ - $h=k$ で成り立つと仮定する：
「$X_{t+k}$ は $X_t$ のみに依存する」と仮定する。このとき、$1$ステップ先の関係から「$X_{t+k+1}$ は $X_{t+k}$ のみに依存する」ため、これらを結合すると「$X_{t+k+1}$ は $X_t$ のみに依存する」となり、$h=k+1$ でも成り立つことが示される
マルコフ連鎖の具体例
マルコフ連鎖の確率質量関数を求める具体的な手順を説明するために、以下のようなサイコロを使った確率過程を考えます。
- 毎回サイコロを 1 個振る。ただし、サイコロは以下の性質を持つものとする
- サイコロの出目は 0 ~ 5 までの整数をとる
- サイコロの出目を表す確率変数を $D$、その実現値を $d$ とした確率質量関数 $P(D=d)$ があらかじめ定義されている（各出目の確率が一様とは限らない）
- 次のステップの「状態」を、これまでに振ったサイコロの出目の合計を 6 で割った余り とする
上記のような設定にした理由は以下の通りです。
- サイコロの出目を 0 ~ 5 とした理由：この後で行う余りの計算を簡潔にするため
- 出目の確率を均等（すべて 1/6）にしない理由：均等にするとこの後の計算の途中で $P(D=d) = 1/6$ が代入されて式が単純になりすぎ、定式化の構造が見えなくなってしまうため
- 状態を「6 で割った余り」とした理由：状態の種類を 6 個にする限定することで計算を簡潔にするため2
一見るするとステップ $t$ の状態 $x_t$ は、過去に振ったすべての出目（過去のすべての履歴）によって決まるため、マルコフ性を持たないように思えるかもしれません。
しかし、次のステップ $t+1$ の状態 $x_{t+1}$ は、現在の状態 $x_t$ と、新しく振ったサイコロの出目 $d$ だけを使って、以下のように完全に決定できます。なお、mod は余り（modulo）を計算する演算子です。
$x_{t+1} = (x_t + d) \mod 6$
この式が示す通り「過去にどういう順番で出目が出たか」という 詳細な履歴は一切必要なく、現在の状態 $x_t$ さえわかれば次の状態の確率を完全に予測できます。従って、この確率過程はマルコフ性（マルコフ連鎖）を満たしていると言えます。
他のサイコロを用いたマルコフ連鎖の例をいくつか紹介します。
- 次の状態をこれまでに振ったサイコロの出目の合計とする
- 次の状態をこれまでに振ったサイコロの最大値（または最小値）とする
状態遷移関数の定式化
前述した確率質量関数を求めるアルゴリズムを実行するために、このマルコフ連鎖における具体的な「状態遷移関数」を定式化します。
初期状態（ステップ 1）の状態遷移関数
ステップ $1$ ではそれ以前の状態が存在しません。また、サイコロの出目を 0 ~ 5 までの整数としたので、それを 6 で割った余りはサイコロの出目の値そのものになります。従って、下記のようにサイコロの出目の確率分布がそのままステップ 1 の状態遷移関数となります。
$P_T(X_1=x) = P(D=x)$
ステップ 2 以降の状態遷移関数
ステップ 2 以降（$t \gt 1$）の状態が $x_t$ の場合に、次のステップ $t + 1$ の状態 $x_{t+1}$ は新しく振ったサイコロの出目を $d$ として、以下の表の条件で決まります。
| $x_{t+1}$ | 遷移の条件 |
|---|---|
| 0 | $(x_t + d) \mod 6 = 0$ |
| 1 | $(x_t + d) \mod 6 = 1$ |
| 2 | $(x_t + d) \mod 6 = 2$ |
| 3 | $(x_t + d) \mod 6 = 3$ |
| 4 | $(x_t + d) \mod 6 = 4$ |
| 5 | $(x_t + d) \mod 6 = 5$ |
この表から状態遷移のルールは $(x_t + d) \mod 6 = x_{t+1}$ と表されることがわかります。
この式から「現在の状態 $x_t$ と次の状態 $x_{t+1}$ が与えられた場合」に、それを満たすための「サイコロの出目 $d$ がいくつになるか」を計算する式を逆算することを考えます。
最初に、次の状態が $x_{t + 1} = 0$ である以下の場合について考えます。
$(x_t + d) \mod 6 = 0$
具体的な導出方法はこの後のノートで解説しますが、上記の方程式を $d$ について解くと下記のようになります。
$d = (6 - x_t) \bmod 6$
上記の式が正しいことを下記の $(x_t + d) \mod 6 = 0$ となる $x_t$ と $d$ の組み合わせの一覧表表から確認して下さい。
| $x_t$ | $d$ |
|---|---|
| 0 | 0 |
| 1 | 5 |
| 2 | 4 |
| 3 | 3 |
| 4 | 2 |
| 5 | 1 |
従って、ステップ $t+1$ で状態が $x_{t+1} = 0$ に遷移する条件付き確率は、下記のようにサイコロの出目が $(6 - x_t) \bmod 6$ になる確率に等しくなります。
$P_T(X_{t+1}=0 \mid X_t=x_t) = P(D=(6 - x_t) \mod 6)$
この考え方を一般化して、任意の次の状態 $x_{t+1}$ に対して、方程式 $(x_t + d) \bmod 6 = x_{t+1}$ を $d$ について解くと、下記の式が得られます。
$d = (6 - x_t + x_{t+1}) \mod 6$
これより、このマルコフ連鎖における 状態遷移関数 の一般式（式 1）が定式化されました。
$P_T(X_{t+1}=x_{t+1} \mid X_t=x_t) = P(D=(6 - x_t + x_{t+1}) \bmod 6) \quad \text{--- (1)}$
参考までに $(x_t + d) \mod 6 = 0$ から $d = (6 - x_t) \bmod 6$ を導出する方法について説明します。
最初に $d$ と $x_t$ が自然数の場合について考えることにします。
$(x_t + d) \mod 6 = 0$ から $x_t + d$ が 6 の倍数であることがわかるので、下記の式が任意の整数 $n$ について成り立ちます。
$x_t + d = 6n$
この式を $d$ について解くと下記の式になります。
$d = 6n - x_t$
上記の式の両辺を 6 で割った余りを計算しても等式は成り立つので、下記の式が成り立ちます。
$d \mod 6 = (6n - x_t) \mod 6$
$d$ は 0 以上 5 以下の整数であることから $d \mod 6 = d$ となるため、下記の式が成り立ちます。
$d = (6n - x_t) \mod 6$
上記の式は任意の整数 $n$ において成り立つので、$n = 1$ とした下記の式が成り立ち、求める式が導出されました。
$d = (6 - x_t) \bmod 6$
確率質量関数の計算
次に、定式化した状態遷移関数を用いて、マルコフ連鎖における各ステップの確率質量関数を具体的に計算していきます。
初期状態（ステップ 1）の確率質量関数
$t=1$ の場合は、先程説明したように過去の履歴が存在しないため、確率質量関数がそのまま初期の状態遷移関数となります（式 2）。
$P(X_1=x_1) = P_T(X_1=x_1) = P(D=x_1) \quad \text{--- (2)}$
ステップ 2 以降の確率質量関数
先程説明したように、ステップ 2 以降の確率質量関数は、前述した以下のアルゴリズムに従って、前のステップの情報をベースにしながら順番（再帰的）に特定していきます。
- 次に計算を行うステップ数を表す $t$ を 2 とする
- これまでに計算した「ステップ $t-1$ までの確率質量関数」と、「ステップ $t$ への遷移を表す状態遷移関数」を用いて、ステップ $t$ のすべての状態 $x_t$ に対する確率質量関数 $P(X_t=x_t)$ 計算する
- $t$ が最後のステップである $n$ の場合は処理を終了し、そうでない場合は $t$ に 1 を加えて手順 2 に戻る
マルコフ連鎖における上記の手順 2 の具体的な計算方法について解説します。
マルコフ性から、ステップ $t+1$ の状態を予測する際は、現在のステップ $t$ の状態だけを考慮に入れれば十分です。従って、ステップ $t+1$ の状態が $x_{t+1}$ となる確率 $P(X_{t+1}=x_{t+1})$ は、以下のように計算できます。
- ステップ $t$ で取りうるすべての状態 $x_t$ について、「ステップ $t$ の状態が $x_t$ であり、なおかつ、そこから次の状態 $x_{t+1}$ へ遷移する」という 2 つの事象が同時に発生する 同時確率 $P(X_{t+1}=x_{t+1}, X_t=x_t)$ を計算する
- その確率を、ステップ $t$ のすべての状態 $x_t \in \mathcal{X}$ において足し合わせる
手順 1 の同時確率は、確率の乗法定理 より「ステップ $t$ の状態が $x_t$」となる確率を表す$P(X_t=x_t)$ と「$x_t$ の状態から次の状態 $x_{t+1}$ へ遷移する確率」を表す $P_T(X_{t+1}=x_{t+1} \mid X_t=x_t)$ を掛け合わせた以下の式で表されます。
$P(X_{t+1}=x_{t+1}, X_t=x_t) = P(X_t=x_t) P_T(X_{t+1}=x_{t+1} \mid X_t=x_t)$
手順 2 でこれらをすべて足し合わせることで、下記のように $P(X_{t+1}=x_{t+1})$ 一般式が定式化されます。
$P(X_{t+1}=x_{t+1}) = \sum_{x_t \in \mathcal{X}} P(X_t=x_t) P_T(X_{t+1}=x_{t+1} \mid X_t=x_t)$
上記の式は「全確率の法則」から導くことができます。参考までに全確率の法則の項目の Wikipedia のリンクを下記に示します。
すでにステップ $t$ までの確率質量関数 $P(X_t=x_t)$ は計算済みであり、状態遷移関数 $P_T$ も定義されているため、この右辺はすべて既知の値となり、実際に具体的な確率値を求めることができます。
具体例におけるステップ 2 の計算
この一般式を、先ほどのサイコロの具体例に当てはめてみることにします。ステップ 2 の確率質量関数 $P(X_2=x_2)$ は、以下のように展開できます。
$P(X_2=x_2) = \sum_{x_1 \in \mathcal{X}}P(X_1=x_1)P_T(X_2=x_2|X_1=x_1)$
上記の式に、ステップ 1 の分布 (式 2) と状態遷移関数 (式 1) を当てはめると、サイコロの出目の確率分布 $P(D)$ だけで表現された下記の式が得られます。
$P(X_2=x_2) = \sum_{x_1 \in \mathcal{X}}P(D=x_1)P(D=(6 - x_1 + x_2) \mod 6)$
同様に、上記で求めたステップ 2 の確率質量関数を用いて、次のステップ 3 の確率質量関数 $P(X_3=x_3)$ を求めることができ、その作業を繰り返すことで最終ステップ $n$ までのすべての確率質量関数を具体的に求めることができます。
サイコロの出目の確率が均一な場合は、すべての $d$ について $P(D=d) = 1/6$ となります。状態空間の要素の数は 6 種類（$\mathcal{X} = {0, 1, 2, 3, 4, 5}$）なので、ステップ 2 の確率は以下のように一定の値になります。
$P(X_2=x_2) = \sum_{x_1 \in \mathcal{X}}\frac{1}{6}\cdot\frac{1}{6}$
$= 6 \cdot\frac{1}{6}\cdot\frac{1}{6}$
$= \frac{1}{6}$
これはステップ 1 の確率質量関数と完全に一致するので、ステップ 3 以降の確率質量関数も同じになります。従って、任意のステップ $t$ においても確率は変化せず、下記のように常に均等な分布になります。
$P(X_t=x_t) = \frac{1}{6}$、$x_t \in {0, 1, 2, 3, 4, 5}$
確率質量関数の計算量
次に、マルコフ連鎖において全ステップの確率質量関数を求めるために、どれほどの「計算量」が必要になるかを評価することにします。
下記は先程導出したステップ $t+1$ の確率質量関数を求める一般式です。
$P(X_{t+1}=x_{t+1}) = \sum_{x_t \in \mathcal{X}}P(X_t=x_t)P_T(X_{t+1}=x_{t+1}|X_t=x_t)$
この数式を実行する際の計算回数は、以下のように切り分けて考えることができます。
-
次の状態（左辺）のループ：
この計算は、ステップ $t+1$ がとりうるすべての状態 $x_{t+1} \in \mathcal{X}$ に対して行う必要があります。従って、状態空間の大きさを $|\mathcal{X}|$ とすると $|\mathcal{X}|$ 回 の繰り返しが発生します。 -
現在の状態（右辺の $\sum$）のループ：
それぞれの $x_{t+1}$ に対して、右辺の同時確率 $P(X_t=x_t) P_T(X_{t+1}=x_{t+1} \mid X_t=x_t)$ を、ステップ $t$ のすべての状態 $x_t \in \mathcal{X}$ にわたって足し合わせる必要があります。従って、1 つの $x_{t+1}$ の計算にさらに $|\mathcal{X}|$ 回 の掛け算と足し算が発生します。
これらを掛け合わせることで、ステップ $t+1$ の確率質量関数を求めるために必要な計算回数は、ステップ数に関わらず 状態の種類の 2 乗である $|\mathcal{X}|^2$ 回 になることがわかります。
この作業は、初期状態を除くすべてのステップに対して順番に行う必要があるため、全ステップ（ステップ数 $n$）の確率質量関数をすべて特定するために必要な総計算回数は $(n -1)|\mathcal{X}|^2$ 回となります。
なお、$n$ が大きくなると $(n -1)|\mathcal{X}|^2$ は $n|\mathcal{X}|^2$ で近似できるので、必要な総計算回数を近似を表す $\approx$ を用いた以下の近似式で表すことにします。
$\text{総計算回数} \approx n|\mathcal{X}|^2$
サイコロの具体例での計算量
先ほどのサイコロの例では、状態の種類が $6$ 種類（$|\mathcal{X}| = 6$）であるため、具体的な計算回数の近似値は以下のようになります。
$6^2 \times n = 36n \text{ 回}$
これは、ステップ数 $n$（時間）に対して計算量が 比例 て増えていくという、コンピュータにとっても非常に現実的で軽い計算量です。
次に、比較対象として「マルコフ性を満たさない（過去の履歴に依存する）場合」の計算量を算出し、このマルコフ連鎖の計算量（$n |\mathcal{X}|^2$）がいかに優れているを示します。
マルコフ性を満たさない場合
次に、マルコフ性を満たさない（非マルコフ的な）確率過程について説明します。最初に次の状態が現在と一つ前のステップという 2 つの状態に依存する場合を説明し、その後で過去のすべての状態に依存する場合を説明します。
次の状態が 2 つの状態に依存する場合
マルコフ性を満たさない具体例として以下のような、次のステップの状態が現在と一つ前のステップという、「2 つの状態に依存」するという確率過程の例を取り上げます。なお、サイコロに関する条件は先ほどの例と同じで、「状態」に関する条件だけが異なります。
- 毎回サイコロを 1 個振る。ただし、サイコロは以下の性質を持つものとする
- サイコロの出目は 0 ~ 5 までの整数をとる
- サイコロの出目を表す確率変数を $D$、その実現値を $d$ とした確率質量関数 $P(D=d)$ があらかじめ定義されている（各出目の確率が一様とは限らない）
- 次の「状態」を「サイコロの出目」と「現在の状態」と「一つ前の状態」の合計を 6 で割った余りとする
この状態遷移のルールを数式で表すと、以下のようになります（ただし、サイコロの出目を $d$ とします）。
$x_{t+1} = (x_t + x_{t-1} + d) \pmod 6$
ステップ 2 までの確率質量関数
このモデルはマルコフ性を満たしませんが、以下の理由から ステップ 2 までの確率質量関数に限っては、マルコフ連鎖と全く同じ方法で計算することができます。
- ステップ 1 の初期状態：
それ以前の状態が存在せず、過去の履歴に依存しようがないため - ステップ 2 への状態遷移：
直前であるステップ 1 の状態しか存在せず、マルコフ連鎖と条件が等しくなるため
なお、上記の性質は明らかに任意の確率過程でも満たされます。
ステップ 3 以降の確率質量関数
次のステップの状態が「現在」と「一つ前」の状態に依存することから、ステップ 3 以降（$t \ge 2$）のステップ $t+1$ への状態遷移関数は下記の条件付き確率で表されます。（この状態遷移関数の具体的な計算式の導出は省略しますが、マルコフ連鎖の場合と同様の方法で求めることができます。興味のある方はぜひチャレンジしてみてください）。
$P_T(X_{t+1}=x_{t+1} \mid X_{t-1}=x_{t-1}, X_{t}= x_t)$
このとき、ステップ $t+1$ の状態が $x_{t+1}$ となる確率 $P(X_{t+1}=x_{t+1})$ は、全確率の公式を用いて以下のように計算できます。
- ステップ $t-1$ と $t$ で取りうるすべての状態の組み合わせについて、「ステップ $t-1$ で $x_{t-1}$、ステップ $t$ で $x_t$ となり、なおかつ、次の状態 $x_{t+1}$ へ遷移する」という3つの事象の 同時確率 $P(X_{t+1}=x_{t+1}, X_t=x_t, X_{t-1}=x_{t-1})$ を計算する
- その確率を、すべての $x_{t-1} \in \mathcal{X}$ と $x_t \in \mathcal{X}$ の組み合わせにおいて足し合わせる
手順 1 の同時確率は、確率の乗法定理より、2変数の同時確率 $P(X_{t-1}=x_{t-1}, X_t=x_t)$ を用いて以下の式で表されます。
$P(X_{t-1}=x_{t-1}, X_t=x_t) P_T(X_{t+1}=x_{t+1} \mid X_{t-1}=x_{t-1}, X_t=x_t)$
手順 2 でこれらをすべて足し合わせることで、下記のように $P(X_{t+1}=x_{t+1})$ を求める一般式が定式化されます。なお、下記で必要となる 2 変数の同時確率 $P(X_{t-1}=x_{t-1}, X_t=x_t)$ も、1つ前のステップまでの情報から同様に計算しておく必要があります。
$P(X_{t+1}= x_{t+1}) =$
$\sum_{x_{t-1} \in \mathcal{X}} \sum_{x_t \in \mathcal{X}} P(X_{t-1}=x_{t-1}, X_t=x_t) P_T(X_{t+1}=x_{t+1} \mid X_{t-1}=x_{t-1}, X_t=x_t)$
計算量の評価
この数式を実行する際の計算回数は、以下のように切り分けて考えることができます。
-
次の状態（左辺）のループ：
マルコフ連鎖の場合と同じ理由から $|\mathcal{X}|$ 回 の繰り返しが発生します。 -
現在の状態（右辺の $\sum\sum$）のループ：
それぞれの $x_{t+1}$ に対して、右辺の同時確率をすべての $x_{t-1} \in \mathcal{X}$ と $x_t \in \mathcal{X}$ の組み合わせにわたって足し合わせる必要があります。その組み合わせの数は $|\mathcal{X}|^2$ 回 です。
これらを掛け合わせることで、ステップ $t+1$ の確率質量関数を求めるために必要な計算回数は、ステップ数に関わらず 状態の種類の 3 乗である $|\mathcal{X}|^3$ 回 になることがわかります。
この作業は、ステップ 1 と 2 を除くすべてのステップに対して順番に行う必要がありますが、$n$ が大きい場合は全ステップで $|\mathcal{X}|^3$ 回 の計算を行う場合で近似できるため、確率質量関数をすべて特定するために必要な総計算回数の近似値は下記のようになります。
$\text{総計算回数} \approx n|\mathcal{X}|^3$
サイコロの具体例での計算量
今回のサイコロの例に当てはめると、具体的な計算回数は以下のようになります。
$6^3 \times n = 216n \text{ 回}$
マルコフ連鎖の場合の回数である $36n$ 回と比較すると、依存する過去の状態が 1 つ増えただけで、計算量が 6 倍 に膨れ上がることがわかります。
次の状態が 3 つ以上の状態に依存する場合
次のステップの状態が「3 つ以上の状態に依存」にする場合は、依存する状態の数に応じて必要な計算量が指数関数的に増大します。一般的に、次の状態が過去の $m$ 個の状態に依存する場合の確率質量関数を特定するための計算回数は $|\mathcal{X}|^{m+1}$ 回となります。
次の状態が「過去のすべての状態に依存」するという、最も多くの状態に依存する場合は、ステップ $t+1$ ではそれ以前に $t$ 個の状態が存在するため、そのステップの確率質量関数を特定するだけでも $|\mathcal{X}|^{t+1}$ 回の計算が必要となります。
従って、初期状態を除く全ステップの確率質量関数をすべて特定するために必要な総計算回数は下記の等比数列の和で表されます。
$\sum_{t=1}^{n-1}|\mathcal{X}|^{t+1} \approx \sum_{t=1}^{n}|\mathcal{X}|^{t}$
状態空間の大きさ $|\mathcal{X}|$ が大きくなると、この総和の大部分を最終項が占めるようになるため、上記の式はシンプルに $|\mathcal{X}|^n$ で近似できるようになります。
たとえば、状態の数 $|\mathcal{X}| = 10$、ステップ数 $n = 5$ の場合は、下記のように実際の総和と近似値の差は約 10% にまで縮まります。
-
実際の総和：
$\sum_{t=1}^{5} 10^t = 10 + 100 + 1,000 + 10,000 + 100,000 = 111,110 \text{ 回}$ -
近似値（$|\mathcal{X}|^n$）：
$10^5 = 100,000 \text{ 回}$
上記の性質から、次の状態が過去のすべての状態に依存する確率過程における総計算回数は、以下の指数関数で近似されます。
$\text{総計算回数} \approx |\mathcal{X}|^n$
このようにマルコフ性を持たない確率過程では、ステップ数 $n$（エピソードの時間）が長くなればなるほど必要な計算量が指数関数的に爆発するという致命的な問題が生じます。
下記は、依存する状態の数 $m$ と、全ステップの確率質量関数を計算するために必要な総計算量の関係をまとめた表です。具体例として、状態の数$|\mathcal{X}| = 10$ の場合を記載しました。
| 依存する状態の数 $m$ | 総計算量の近似値 | 状態数が 10 の場合 |
|---|---|---|
| 0（独立同分布） | $n|\mathcal{X}|^1$ | $10n$ |
| 1（マルコフ連鎖） | $n|\mathcal{X}|^2$ | $100n$ |
| 2（1 つ前まで依存） | $n|\mathcal{X}|^3$ | $1,000n$ |
| 3 | $n|\mathcal{X}|^4$ | $10,000n$ |
| 5 | $n|\mathcal{X}|^6$ | $1,000,000n$ |
| 10 | $n|\mathcal{X}|^{11}$ | $100,000,000,000n$ |
| 全履歴依存（$m = n - 1$) | $|\mathcal{X}|^{n}$ | $10^n$（指数爆発） |
この対比表から、依存する過去の状態 $m$ が増えるにつれて、計算量が文字通り桁違いに爆発していくことが視覚的にも一目瞭然にわかります。
また、このことから確率過程に 「マルコフ性（$m=1$）」という制約を課すこと が、現実的な時間内で確率質量関数（ひいては強化学習の目的関数）を計算・最適化するために極めて重要であると言えます。
サイコロを用いたマルコフ性を満たさない確率過程の例としては、「次の状態をこれまでに振ったサイコロの中央値とする」というものがあります。
なお、中央値とは数値を小さい順に並べ直した時の真ん中に位置する数値の事を表します。中央値を求めるためには、それまでに振ったすべてのサイコロの出目が必要となるためマルコフ性を満たしません。
マルコフ決定過程による強化学習の性質
ここまでは（ステップが 1 から開始する）一般的な確率過程をベースに、マルコフ性がもたらす計算量の利点を解説しました。ここからは、（初期状態をステップ 0 とする表記する）強化学習に話を戻し、強化学習の「履歴」の本質である マルコフ決定過程（MDP） の定義とその性質について説明します。
マルコフ決定過程（MDP）
これまでの記事では、環境の「状態遷移」、「即時報酬」、「方策」のすべてが、現在の状態にのみ依存するというマルコフ性を前提として議論を進めてきました。また、実用的な強化学習の多くでは、状態空間の要素数を有限（離散的）として扱います。
このような条件を満たす強化学習の履歴から、「状態」だけを表す確率変数 を抜き出して並べた下記の確率変数の数列は、今回の記事で説明した マルコフ連鎖 そのものとなります。
$S_0$、$S_1$、$S_2$、・・・、$S_{n-1}$、$S_n$
この状態の推移がマルコフ連鎖となる理由は、以下の 2 つのステップがいずれも「現在の状態 $S_t$」のみに依存して確率的に計算されるからです。
- 行動の選択：現在の状態 $S_t$ のみに依存して、方策 $\pi(a_t \mid s_t)$ により行動 $A_t$ が確率的に決定される
- 状態の遷移：現在の状態 $S_t$ と選択された行動 $A_t$ のみに依存して、状態遷移関数 $P(s_{t+1} \mid s_t, a_t)$ により次の状態 $S_{t+1}$ が確率的に決定される
このような「環境の状態の推移」を表すマルコフ連鎖に対して、下記の全履歴のように「方策による意思決定を表す行動 $A_t$」と「行動の価値（良し悪し）の判断基準となる報酬 $R_t$」を表す確率変数を組み入れた確率過程のことを「マルコフ決定過程（Markov decision process、MDP）」と呼びます。
$S_0$、$A_0$、$R_0$、$S_1$、$A_1$、$R_1$、・・・、$S_{n-1}$、$A_{n-1}$、$R_{n-1}$、$S_n$
一般的な強化学習の手法のほとんどは、このマルコフ決定過程という数学的な枠組みの上で、「累積報酬を最大化するような最適方策 $\Pi^*$ を見つけ出す」という最適化問題として定式化されています。
マルコフ決定過程の性質
ここで一つ、注意点があります。状態・行動・報酬が交互に並んだマルコフ決定過程の数列（ $S_0, A_0, R_0, S_1, A_1, R_1, \dots$ ）は、生の要素をそのまま並べた状態では、下記の理由から厳密にはマルコフ連鎖の定義を満たしません。
- 報酬の予測の問題：報酬関数が $P(r_t \mid s_t, a_t, s_{t+1})$ で定義されることから、マルコフ決定過程の要素の並び順で $A_t$ の右隣にある $R_t$ を予測するためには、直前の $A_t$ だけでなく、さらにその前にある状態 $S_t$ の情報が必要となり、「次の状態が直前の状態だけに依存する」というマルコフ連鎖のルールから外れてしまう
- 状態の予測の問題：状態遷移関数が $P(s_{t+1} \mid s_t, s_t)$ で定義されることから、左隣にある $R_t$ の情報だけから、その右隣の $S_{t+1}$ を予測することができない
しかし、この問題は 複数の状態をまとめて扱う（パッケージ化）ことで解決できます。具体的には、各ステップにおける「状態」「行動」「即時報酬」を一つの集合として扱い、それを新しいステップの状態 $X_t = \{S_t, A_t, R_t\}$ として再定義します。この $X_t$ を並べた下記の確率変数の数列は、完全にマルコフ連鎖の性質を満たすようになります（ただし、最終ステップ $n$ には行動と報酬がないため $X_n = \{S_n\}$ とします）。
$X_0$、$X_1$、・・・、$X_{n-1}$、$X_{n}$
$= \{S_0、A_0、R_0\}$、$\{S_1、A_1、R_1\}$、・・・、$\{S_{n-1}、A_{n-1}、R_{n-1}\}$、$\{S_n\}$
この新しい数列 $X_t$ がマルコフ連鎖になる（＝ $X_t$ の情報だけから、次の $X_{t+1}$ を予測できる）理由は、以下の連鎖的な因果関係によって説明できます。
- 状態の予測：次の状態 $S_{t+1}$ は、現在の状態 $S_t$ と行動 $A_t$ のみに依存して決まる。これらはすべて $X_t$ の中に含まれているため、$X_t$ から $S_{t+1}$ を直接予測できる
- 行動と報酬の予測：次の状態 $S_{t+1}$ が定まれば、そこから次の方策によって行動 $A_{t+1}$ が決まり、報酬関数によって報酬 $R_{t+1}$ も求まる。
- 従って、現在の $X_t$ の情報さえあれば、次の $X_{t+1}$ に含まれるすべての要素である ${S_{t+1}, A_{t+1}, R_{t+1}}$ をすべて連鎖的に予測できるため、過去の全履歴（ $X_0 \dots X_{t-1}$ ）に依存しないマルコフ性が完全に満たされる
この性質があるからこそ、マルコフ決定過程は先ほど証明した総計算量が $n|\mathcal{X}|^2$ に抑えられるという マルコフ連鎖の強力な計算量削減の恩恵 が受けられます。
マルコフ決定過程の表現力
マルコフ決定過程での「方策」、「状態遷移」、「即時報酬」は下記の性質を持ちます。なお、以後は状態遷移関数を表す確率質量関数を $P_T$、報酬関数を表す確率質量関数を報酬（reward）の頭文字から $P_R$ と表記して区別することにします。
- 確率的な方策：現在の状態 $s_t$ のみに基づき、方策 $\pi(a_t \mid s_t)$ によって行動 $a_t$ を確率的に選択する
- 確率的な状態遷移：選択された行動により、状態遷移関数 $P_T(s_{t+1} \mid s_t, a_t)$ に基づいて、環境の状態が $s_t$ から $s_{t+1}$ へ確率的に遷移する
- 確率的な即時報酬：選択された行動と遷移先に応じて、報酬関数 $P_R(r_t \mid s_t, a_t, s_{t+1})$ に基づいて確率的な即時報酬 $r_t$ が得られる
一見すると、「現在の状態だけを基準にする」というマルコフ性の制約は、表現力を狭めすぎるように感じられるかもしれません。しかし、マルコフ決定過程は、現実世界の広範な強化学習のタスクを扱うのに十分な高い表現力を備えています。
例えば、本記事が題材とする 〇× ゲームでは、ある局面に至るまでに「どういう順番で着手が行われたか」という過去の履歴は、現局面で着手したときの「次の局面（状態遷移）」や「勝敗の決定（即時報酬）」に対して一切影響を与えません。重要なのは、「現在の局面（ゲーム盤）がどういう状態にあるか」 という現在の情報だけです。従って、〇×ゲームの強化学習で過去の履歴をすべて切り捨て、現在の状態のみを判断材料として意思決定を行うマルコフ方策を採用することは、理にかなっているだけでなく数学的にも完全に正しいと言えます。このことは状態遷移関数と報酬関数に関しても同様です。
マルコフ性を満たさない題材とその対処法
現実世界の多くの問題や複雑なゲームでは、生の観測データをそのまま「状態」とみなすと、マルコフ性を満たさない（非マルコフ的な）ケースが多々あります。しかし、それらの問題の多くは「状態の定義を拡張する」などの工夫を行うことで、マルコフ性を満たすようにすることができます。
具体的な問題例と、その対処法について解説します。
隠れた内部パラメータ（アクションゲームの例）
キャラクターがアイテムを拾うことでジャンプ力が向上するリアルタイムアクションゲームを考えます。ただし、アイテムを取ることによるキャラクターの外見上の変化や画面の変化は起きないものとします。ディスプレイの画像（現フレーム）だけを「状態」として観測して強化学習を行う場合は、状態遷移はマルコフ性を満たしません。
その理由は、「ジャンプボタンを押す」という行動の結果（どれだけ高く飛べるか）が、画面上の情報からは判別できない「過去にアイテムを取ったか否か」という過去の履歴に依存してしまうためです。
この問題を対処する方法として、環境がエージェントに渡す「状態」のデータの中に、画面画像だけでなく「アイテムの所持」という情報を直接付け加えるというものがあります。
2. 動的な物理量（シューティングゲームの例）
シューティングゲームで、直線的に飛んでくる敵の弾を避けるという問題を考えます。現時点のディスプレイの画像 1 枚だけを「状態」とすると、マルコフ性を満たしません。
その理由は、画像 1 枚に写った弾は静止しているため、弾の「移動方向」や「速度」が計算できないからです。弾の動きを予測して避ける（未来の状態を予測する）ためには、弾の現在の位置と過去の位置との比較が必要になります。
この問題を対処する方法として、状態の情報として現在の画像だけでなく 過去数フレーム分の画像 をセットにするというものがあります。画像の変化（差分）から弾の速度や方向を現在の 1 つの状態で判断できるようになり、マルコフ性が満たされるようになります3。
3. ルールの制約（将棋や囲碁の例）
将棋や囲碁などの一部のボードゲームでは、現在の「盤面上の駒の配置」だけを状態として観測した場合にマルコフ性が満たされない場合があります。
その理由は、将棋には同じ局面が 4 回現れると引き分けになる「千日手」、囲碁には直前の着手と全く同じ盤面に戻すことを禁じる「コウ」というルールがあるからです。現在の盤面だけからは、「過去にその局面が何回出現したか」や「直前にどこに打たれたか」という履歴が判断できないためマルコフ性を満たしません。
この問題を対処する方法としては、状態の情報に「過去の同一局面の出現回数」や「直前の着手位置」といった履歴の情報を埋め込むというものがあります。
実は将棋や囲碁は、盤面を見ただけではどちらの手番であるかを判断することができないという点でもマルコフ性を満たしません。そのため、状態に現在の手番を表す情報を加える必要があります。
なお、〇× ゲームの場合は着手されているマスの数が偶数か奇数かで手番を求めることができるので、盤面の情報だけでマルコフ性が満たされます。ただし、盤面のマスの数える作業を省略できるように状態に手番の情報を含めるのが一般的で、筆者も Marubatsu クラスを turn 属性で手番がわかるように実装しました。
部分的観測マルコフ決定過程（POMDP）と近似
このように、環境自体はマルコフ性（因果関係）を持って動いているものの、エージェントが観測できる情報が不足しているためにマルコフ性が崩れてしまう問題を、専門用語で 部分的観測マルコフ決定過程（Partially Observable MDP（POMDP）） と呼びます。
強化学習のタスクを解く際は、上記の例のように「不足している情報を状態に加える」ことで、マルコフ決定過程を満たすようにへと変換して解くのが一般的なアプローチです。
また、厳密にはマルコフ性を満たさない場合であっても、実用上そのことが結果に影響する確率が十分に低い（無視できる）と判断できる場合は、あえて履歴を無視し、「マルコフ性を満たす」と仮定して近似的に解くというアプローチも非常によく用いられます。
今回の記事のまとめ
この記事の冒頭で、目的関数の設定には 「目的関数の表現力を高くすると、最適解を見つけることが困難になる」というトレードオフがある と説明しました。
強化学習におけるこのトレードオフは以下のようになります。
-
独立同一分布を課す場合：
計算量は極めて低くなるが、表現力が低すぎてほとんどの問題を扱うことができない -
マルコフ決定過程（MDP）を採用した場合：
〇×ゲームをはじめとする多くの複雑な問題を扱える高い表現力を維持したまま、計算量を $n|\mathcal{X}|^2$ という 線形時間（ステップ数 $n$ に比例する軽さ） にまで劇的に抑え込むことができる -
マルコフ性を課さない場合（全履歴依存）：
表現力は最大になるが、計算量がエピソードの長さに応じて $|\mathcal{X}|^n$ という指数爆発を起こし、事実上ゲームを解くことが不可能になる
このことから、「マルコフ性」という概念を導入することで、目的関数を求めるための計算量を低く抑えつつ、多くの強化学習の題材に適した表現力を持つバランスの良い性質を持たせることができることがわかります。
本記事で入力したプログラム
今回の記事で入力したプログラムはありません。
次回の記事
近日公開予定です。
-
Wikipedia では「確率要素の族で表現された数学的対象」と説明されており、「確率要素」とは「確率変数」を一般化した用語、「族」とは「集まり」の事を表します。本記事の内容の範囲では「確率要素の族」を「確率変数の集まり」と考えて問題はありません ↩
-
「$6$ で割った余り」にせず、単純な合計値を状態とすると、ステップ $t$ における状態の種類は $5t + 1$ 種類となり、時間が経つにつれて状態空間が無限に膨れ上がってしまいます。状態空間を有限に保つことは、強化学習の計算を現実的に解くために非常に重要なアプローチです ↩
-
実際に、Deep Mind社が開発した「DQN（Deep Q-Network）」という有名な強化学習のアルゴリズムでは、アタリ社のビデオゲームを解く際に、直近の 4 フレームの画面をまとめて1つの「状態」とすることで、ゲームのマルコフ性を担保しています。 ↩