Pythonで〇×ゲームのAIを一から作成する その240 マルコフ性を満たす強化学習の定式化

目次と前回の記事

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 の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

今回の記事の内容

前回の記事では原始モンテカルロ法の妥当性について大数の法則を用いて証明しました。そのことからわかるように、強化学習の手法は数学の理論に基づいています。そのため、強化学習についてより深く理解するためには、強化学習の手法を式と記号を用いて数学的に表現するという「定式化」を行う必要があります。

また、強化学習の手法の多くは、環境と方策が「マルコフ性」という性質を持つことを前提とした「マルコフ決定過程」として定式化されます。そこで、今回の記事ではマルコフ性の説明と、マルコフ性を満たす強化学習の定式化を行うことにします。

なお、「マルコフ決定過程」の具体的な意味については次回の記事で説明します。

記号の表記の使い分け

機械学習では様々な用語をアルファベットやギリシャ文字などの記号で表します。本記事では標準的な機械学習での記法に倣い、下記のように記号の表記を使い分けます。なお、下記の説明では行動（action）を表す a という記号を具体例としました。

• 行動の「集合」を大文字の飾り文字の $\mathcal{A}$ で表記する
• 具体的な値が確率によって定まる、「確率変数」としての行動を大文字の $A$ で表記する
• 確率変数の実現値としての行動のような、何らかの「具体的な行動」を表す行動を小文字の $a$ で表記する

本記事では以後は原則として上記のルールに従って記号を表記することにします。

なお、強化学習で用いられる記号には様々な流儀があり、文献によっては本記事で紹介する記号と異なる記号を用いる場合がある点に注意が必要です。本記事では別の記号が使われる場合はノートや脚注などでそのことを示すことにしました。

集合を表す記号に飾り文字を使う理由は、その記号が集合を表すことを明確にするためです。そのため、集合であることが明らかである場合などでは $A$ のような通常の大文字の記号を用いる場合があります。

条件付き確率

強化学習の定式化を行う際に必要となる「条件付き確率」について説明します。なお、強化学習の手法には連続型確率変数を扱うものもありますが、〇× ゲームの状態や行動は離散的であるため本記事で扱う確率変数は 離散型確率変数 であるものとします。

これまでの記事では離散型確率変数 $X$ が $x$ という実現値を取るという事象が発生する確率を、確率質量関数 $P$ を用いて下記のように表記しました。

$P(X=x)$

これに対して、特定の事象が発生したという条件のもとで別の事象が発生する確率を「条件付き確率」と呼び、$P$ の括弧の中を $|$ で区切って $|$ の右に条件となる事象を記述します。

例えば、「確率変数 $Y$ の実現値が $y$」という条件のもとで「確率変数 $X$ の実現値が $x$」となる確率を表す条件付き確率は下記のように記述します。

$P(X=x \mid Y=y)$

また、$x$ と $y$ が確率変数 $X$ と $Y$ の実現値であることが明確な場合は、下記のように確率変数を省略して実現値だけを記述する場合があります。

$P(x \mid y)$

参考までに Wikipedia の条件付き確率の項目のリンクを下記に示します。

上記のリンク先の Wikipedia の説明では事象を大文字の $A$ や $B$ のように表記し、事象 $B$ が発生するという条件の下で事象 $A$ が発生する条件付き確率を下記のように表記しています。

$P(A \mid B)$

本記事で上記の式で条件付き確率を説明しなかった理由は、上記の $A$ と $B$ が確率変数ではない「事象」を表す記号であるため、今回の記事の最初で大文字の記号を確率変数として用いると説明したことへの矛盾による混乱を避けるためです。

下記は $A$ と $B$ の事象をベン図で表したものです。なお、$A \cap B$ は $A$ と $B$ に共通する事象を表します。

図から、事象 $B$ が発生したという条件のもとで事象 $A$ が発生する確率は、「事象 $B$ が発生する確率である $P(B)$」の中の、「事象 $A$ と $B$ に共通する事象が発生する確率である $P(A \cap B)$」の割合を表します。従って、$P(B) ≠ 0$ の場合は $P(A \mid B)$ は下記の式で定義されます。

$P(A \mid B) = \frac{P(A \cap B)}{P(B)}$

参考までに Wikipedia のベン図の項目のリンクを下記に示します。

環境に関する定式化とマルコフ性

最初に、強化学習の環境に関する定式化とマルコフ性について説明します。強化学習の用語については以前の記事を参照して下さい。

状態、行動

強化学習では状態（state）をアルファベットの s、行動（action）を a という記号で表記します。また、今回の記事の最初で説明したように、環境と行動を表す記号を以下のように区別して表記します。

• $\mathcal{S}$、$\mathcal{A}$：環境がとりうる状態の集合と、環境でとることができる行動の集合
• $S$、$A$：状態と行動を表す確率変数
• $s$、$a$：状態と行動の具体的な値（実現値）

〇× ゲームの状態は局面を表すので $\mathcal{S}$ は 〇× ゲームで出現するすべての局面の集合です。従って、以前の記事から局面の種類である 5478 個の要素を持つ集合になります¹。

〇× ゲームの行動は着手を表します。着手はゲーム盤の特定のマスに対して行うので、着手するマスの座標である (x, y) を行動として表記すると、$\mathcal{A}$ は以下のように定義されます。

$\mathcal{A} = \{ (0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)\}$

以後の説明では原則として具体的な状態と行動を表す $s$ と $a$ はそれぞれ $\mathcal{S}$ と $\mathcal{A}$ の要素、すなわち $s \in \mathcal{S}$、$a \in \mathcal{A}$ であるものとします。また、〇× ゲームの環境と状態がそうであることから、$\mathcal{S}$ と $\mathcal{A}$ は有限の要素を持つ有限集合であるものとします。

本記事では扱いませんが、環境によっては、行動や状態の数が有限でない（無限）である場合があります。例えば状態の中に「気温」のような連続的な情報が含まれる場合や、行動が「時速 0 ~ 10 km の範囲で歩く」のような連続的な値である場合は、状態と行動の種類が無限になります。

特定の状態でとることができる行動の集合

状態によってとることができる行動が異なる場合があります。例えば、〇× ゲームの場合は着手済のマスに対する着手を行うことはできません。そこで、状態 $s$ でとることができる行動の集合のことを $\mathcal{A}(s)$ のように表記することにします。 〇× ゲームの場合の $\mathcal{A}(s)$ は状態 $s$ の局面での合法手の一覧になります。

集合の要素の個数の表記方法

集合の要素の個数を表記する方法の一つに、集合を表す記号を絶対値と同じ $|$ で囲うという記法があります[^2]。例えば 〇× ゲームの場合は局面の種類が 5478、行動の種類は 9 なので下記の式が成り立ちます。

$|\mathcal{S}| = 5478$

$|\mathcal{A}| = 9$

また、$s$ が 5 手進んだ局面の場合の合法手の数は 9 - 5 = 4 なので下記の式が成り立ちます。

$|\mathcal{A}(s)| = 4$

参考までに Wikipedia の集合の要素の個数に関する項目のリンクを下記に示します。

状態遷移とマルコフ性

強化学習では、エージェントが行動を起こすことで環境の状態が変化します。例えば、〇× ゲームの場合は「ゲーム開始時の局面」という状態に対して「(1, 1) に着手する」という行動を起こした結果、「 (1, 1) に 〇 が配置された局面」という状態に変化します。このような、行動を起こすことによって状態が変化することを状態遷移（state transition）と呼びます。

本記事が扱う題材である 〇× ゲームでは、同じ状態に対して同じ行動を起こすと必ず同じ状態に遷移し、このような性質を決定論的（determinisitic）と呼びます。

一方、同じ状態で同じ行動を行った結果が異なる場合があります。例えば「サイコロを振るという行動に対する出目が異なる」場合などが相当します。この場合はサイコロの出目が次の状態を表し、どの出目がでるかを確率的に扱います。そのため、そのような性質を持つ状態遷移を確率的（stochastic）な状態遷移と呼びます。

さらに、現在の状態と行動だけでなく、過去の状態が影響するような状態遷移を考えることもできますが、そのような状態遷移は次回の記事で詳しく説明するように非常に複雑になるため、強化学習を行うことが困難になるという問題があります。そこで、一般的な強化学習の手法は状態遷移が「現在の状態によってのみ影響される」（過去の状態に影響されない）という制約を持つという仮定のもとで行います。このような制約を持つ性質の事を「マルコフ性（markov property）」²と呼び、その性質については次回の記事で詳しく説明します。

〇× ゲームの状態遷移は同じ局面で同じ着手を行った結果が常に同じになるため決定論的です。また、着手を行った結果が過去の局面に影響されないためマルコフ性を満たします。

参考までにマルコフ性の Wikipedia の項目を下記に示します。

状態遷移関数

マルコフ性を持つ決定論的な状態遷移の場合は、状態 $s$ に対して行動 $a$ を行った場合に遷移する状態を下記の状態遷移関数 $f$ で表現します³。

$f(s, a)$

ただし、行動 $a$ が状態 $s$ で取れる行動の集合である $\mathcal{A}(s)$ に含まれない場合の状態遷移は存在しないので、上記の関数には行動 $a$ が $\mathcal{A}(s)$ に含まれることを表す $a \in \mathcal{A}(s)$ という条件が付きます。

マルコフ性を持つ確率的な状態遷移の場合は、状態 $s$ に対して行動 $a$ を行った場合に状態 $s'$ になる確率を、条件付き確率を用いて下記のように表記します。

$P(s' \mid s, a)$

なお、決定論的な場合と異なり $a \notin \mathcal{A}(s)$ の場合は $P(s' \mid s, a) = 0$ とすれば良いので $a \in \mathcal{A}(s)$ という条件は必要ありません。

上記の式では確率変数を省略しています。確率変数を省略しない場合の式は、現在の状態、行動、次の状態を表す確率変数を $S$、$A$、$S'$ とすると下記のようになりますが、式が長くなるため上記のように確率変数を省略することが良くあります。

$P(S' = s' \mid S=s, A=a)$

決定論的な状態遷移は、下記のように状態 $s$ に対して行動 $a$ を行った場合に状態 $f(s, a)$ になる確率を 1、そうでない場合の確率を 0 とした確率的な状態遷移の一種であると考えることができます。

$P(s' \mid s, a) = \begin{cases}
1 & a \in \mathcal{A}(s) \text{ かつ } s' = f(s, a)\\
0 & a \notin \mathcal{A}(s) \text{ または } s' ≠ f(s, a)
\end{cases}$

ただし、本記事が題材とする 〇×ゲームの状態遷移は決定論的で、決定論的な環境では上記の確率ではなく、状態遷移を表す $f(s, a)$ を用いたほうが式が簡潔になるため、以後の説明では原則として状態遷移関数 $f(s, a)$ を用いて説明を行うことにします。

即時報酬と報酬関数

以前の記事で説明したように、強化学習ではエージェントの行動の結果によって即座に得られる、目標に対してどれほどの成果が得られたかを表す数値データのことを即時報酬（immediate reward）と呼び、r という記号で表記します。

即時報酬にも状態遷移と同様に「決定論的」と「確率的」の区別や「マルコフ性」の有無があり、〇× ゲームの即時報酬はゲームの決着が付いていない場合は 0、ゲームの決着が付いたときは勝敗結果に応じた値となるため、明らかに決定論的でマルコフ性を満たします。

マルコフ性を持つ決定論的な即時報酬は、状態 $s$ で行動 $a$ を行った結果、状態 $s'$ に状態遷移した場合に得られる即時報酬を表す下記の報酬関数（reward function）で表記します⁴。

$r(s, a, s')$

ただし、状態遷移の場合と同様の理由から $a \in \mathcal{A}(s)$ という条件が付きます。

状態遷移が決定論的な場合は $s'$ を省略して $r(s, a)$ のように報酬関数表記する場合があります。

マルコフ性を持つ確率的な即時報酬の場合は、「状態 $s$ で行動 $a$ を行った結果、状態 $s'$ に状態遷移した」という条件で $r$ の即時報酬が得られる確率を、条件付き確率を用いて下記のように表記します。

$P(r \mid s, a, s')$

状態遷移が決定論的な場合は $s'$ を省略して $P(r \mid s, a)$ のように報酬関数表記する場合があります。

また、状態遷移と同様の理由から決定論的な即時報酬を下記の式のように確率的な即時報酬として考えることができます。

$P(r \mid s, a, s') = \begin{cases}
1 & r = r(s, a, s')\\
0 & r ≠ r(s, a, s')
\end{cases}$

ただし、本記事が題材とする 〇×ゲームの状態遷移と即時報酬は決定論的であるため、先程と同様の理由で以後の説明では原則として $s'$ を省略した報酬関数 $r(s, a)$ を用いて説明を行うことにします。

まとめ

上記で紹介した環境に関連する記号と用語を表にまとめます。ただし、状態遷移と即時報酬は決定論的であり、マルコフ性を満たすものとします。

記号	意味
$\mathcal{S}$	状態の集合
$\mathcal{A}$	行動の集合
$s$	特定の 1 つの状態（$s \in \mathcal{S}$）
$a$	特定の 1 つの行動（$a \in \mathcal{A}(s)$）
$f(s, a)$	状態 $s$ で行動 $a$ を取った時に遷移する状態を表す状態遷移関数
$r(s, a)$	状態 $s$ で行動 $a$ を取った時に得られる即時報酬を表す報酬関数

強化学習において「環境を定義する」という事は、状態を表す集合 $\mathcal{S}$ と行動を表す集合 $\mathcal{A}$ を定義し、すべての状態 $s \in \mathcal{S}$ と、状態 $s$ で取りうる行動 $a \in \mathcal{A}(s)$ の組み合わせに対して状態遷移関数 $f(s, a)$ と報酬関数 $r(s, a)$ の値を定義することを表します。

〇× ゲームの場合は以下のようになります。

• 5478 種類の局面を要素とする $\mathcal{S}$ を定義する
• 9 種類の行動を要素とする $\mathcal{A}$ を定義する
• すべての状態とその状態でとりうる行動の組み合わせに対して $f(s, a)$ と $r(s, a)$ の値を定義する

〇× ゲームの状態は 5478 で行動の種類は 9 なので、定義する必要がある組み合わせの種類は最大で 5478 × 9 = 49302 通りです。もちろん、ゲーム開始時以外の局面ではとることのできる行動の種類が 9 未満になるのでその組み合わせはもっと少なくなります。

〇× ゲームの環境を表す Marubatsu クラスでは以下のように対応します。

• board 属性よって $\mathcal{S}$ の各要素（局面）を定義する
• ゲーム盤を表すクラスの座標のデータ構造で $\mathcal{A}$ の各要素（行動）を定義する
• move メソッドで任意の状態（局面）に対する行動（着手）による状態遷移に対応する $f(s, a)$ の処理を行い、status 属性に状態遷移の結果得られた報酬を表す $r(s, a)$ が計算される

なお、非常に重要な点としてエージェントは環境が管理するこれらの状態の集合や、関数の厳密な定義を知らされていないということが挙げられます。エージェントが行えることは、環境に対して行動を行うことで得られた状態遷移と即時報酬の情報（経験）から、環境に関するこれらの情報を推測することです。

また、環境によって定義された状態や関数は原則として後から変化することはありません。それに対してエージェント側で定義した「方策」は強化学習を進めていくことでエージェントが最適な方策になるように変化（学習）させていきます。本記事で「環境」に対する用語と、この後で説明する「エージェント」に対する用語を分けて説明したのは、そのことを明確にしたかったからです。

エージェントに関する定式化

次にエージェントに関する用語の定式化の説明を行います。

方策

以前の記事で説明したように、強化学習における方策（policy）は「各状態」での「各行動を選択する確率」によって表現されます。強化学習ではこの「各状態で各行動を選択する方針」を表す集合である方策を $Π$ という記号で表します。この $Π$ は数学で円周率を表すギリシャ文字 $π$ の大文字ですが、強化学習においては大文字の $Π$ とこの後で説明する小文字の $π$ はいずれも円周率とは全く異なる意味を持つ点に注意して下さい。

方策を表す記号に $Π$ や $π$ が利用される理由は以下の通りです。

• 方策（policy）の頭文字である $P$ が確率を表す記号として既に用いられている
• $Π$ の読み方がパイ（pi）であることからわかるように、$Π$ はアルファベットの P に対応するギリシャ文字である

方策の定式化

方策にも状態遷移などと同様に、状態 $s$ で特定の行動を必ず取るという決定論的な方策と、確率で行動を選択する確率的な方策があります。また、方策にも現在の状態 $s$ のみから決まるマルコフ性を持つ方策とそうでない方策があり、マルコフ性を持つ方策の事をマルコフ方策と呼びます。

決定論的なマルコフ方策は、状態 $s$ に対して必ず取る 1 つの行動をギリシャ文字の小文字の $μ$（ミュー）を用いた下記の方策関数で表記します⁵。

$μ(s)$

$μ(s)$ は状態 $s$ でとることができる行動である必要があるため $μ(s) \in \mathcal{A}(s)$ となります。

確率的な方策の場合は状態 $s$ に対して $a$ という行動を取る確率を、ギリシャ文字の小文字の $π$ を用いた下記の方策関数で表記します。

$π(a \mid s)$

なお、 $a \notin \mathcal{A}(s)$ の場合は必ず $π(a \mid s) = 0$ となります。

原始モンテカルロ法の場合は、合法手である $a \in \mathcal{A}(s)$ に対して均等な確率を割り当て、その要素数は $|\mathcal{A}(s)|$ なので、すべての状態 $s$ に対する方策は下記のように定式化できます。

$π(a \mid s) = \begin{cases}
\frac{1}{|\mathcal{A}(s)|} & a \in \mathcal{A}(s)\\
0 & a \notin \mathcal{A}(s)
\end{cases}$

方策関数 $π$ は確率質量関数ですが、確率的な状態遷移や報酬を定式化する際に用いられる確率質量関数 $P$ とは異なる記号を用います。その理由は、確率的な状態遷移や報酬の確率分布は環境によって決められた固定的なものであるのに対して、方策の確率分布はエージェントが学習によってより良いものへと更新していく流動的なものであることを異なる記号を用いることで明確にするためです。

また、$|$ が用いられていることから $π(a \mid s)$ は条件付確率であり、省略している確率変数を記述すると下記のようになります。

$π(A=a \mid S=s)$

エピソードのステップを表す添字

以前の記事で説明したように、強化学習では目的を達成するために行った一連の行動の集まりのことをエピソード（episode）と呼び、エピソードの中で行われた一つ一つの行動のことをステップ（step）と呼びます。強化学習では一つ一つのステップを離散的な時間の経過と捉え、それぞれのステップを区別するために 0 から順番に整数の番号を割り当てます。また、各ステップにおける状態、行動、報酬を表す確率変数と実現値を $S_1$、$A_1$、$R_1$、$s_1$、$a_1$、$r_1$ のようにステップの番号を右下に添字として記述することで区別します。

ステップは 0 から数えるため、最初の状態は $s_0$ となります。また、任意のステップ $t$ ⁶における状態遷移を記号で表すと下記のようになります。

• 状態 $s_t$ で $a_t$ という行動を起こす
• その結果即時報酬 $r_t$ が得られ、状態が $s_{t+1}$ に遷移する

先程は確率的な状態遷移を $P(s' \mid s, a)$ のように表記しましたが、これは任意のステップ $t$ における状態 $s$ と行動 $a$ によってステップ $t + 1$ の状態が $s'$ に遷移する確率を表すので、確率変数を省略しない場合は下記のように記述します。

$P(S_{t+1}=s' \mid S_t=s, A_t=a)$

1 つのエピソードで得られる経験の定式化

以前の記事で説明したように、エピソードの各ステップ $t$ では下記のエージェントと環境の相互作用を行います。

• エージェントが現在の状態 $s_t$ を観測し、自身の持つ方策 $Π$ に従って行動 $a_t$ を選択して環境に報告する
• 環境が報告された行動に従って状態遷移を行い、即時報酬 $r_t$ と遷移した次の状態 $s_{t+1}$ をエージェントに伝える

下記は $n$ 回のステップによるエピソードで開始から終了までに得られる経験を時系列に沿って記号で表したもので、最初の $s_0$ がエピソードを開始した時点での最初の状態を表します。また、以降は特に説明がない限りエピソードのステップ数を $n$ とします。

$s_0$、$a_0$、$r_0$、$s_1$、$a_1$、$r_1$、$s_2$、・・・、$s_{n-1}$、$a_{n-1}$、$r_{n-1}$、$s_n$

強化学習ではこの一連の「各ステップでの状態、行動、即時報酬を集めた集合」のことを履歴（history）または軌跡（trajectory）と呼び、強化学習はエピソードによって得られた上記の履歴という経験を元に学習を行います。

累積報酬（収益）

以前の記事で説明したように、強化学習の目的は、エピソードによって得られた経験（履歴）を元に、累積報酬（収益）の期待値を最大化する方策を求めることで、強化学習では累積報酬（収益）はアルファベットの g で表記します⁷。

累積報酬（収益）を表す g は「利益」を表す gain の頭文字です。収益を表す return が報酬を表す reward と同じ頭文字であるため、収益と意味が近い gain が採用されました。

これまでの記事では累積報酬と収益を同じ意味で用いてきましたが、ここでその違いについて説明します。

累積報酬

累積報酬は単純に即時報酬の合計を計算したものです。これまでの記事のように累積報酬を初期状態から得られた即時報酬の合計として計算する場合の $g$ の計算式は下記のようになります。なお、ステップは 0 から数えるので、ステップ数が $n$ の場合の最後のステップは $n -1$ となる点に注意して下さい。

$g = r_0 + r_1 + ．．．+ r_{n-1} = \sum_{i=0}^{n-1}r_i$

累積報酬も状態などと同様に、ステップごとに計算することができます。具体的には下記の式のように、$g_t$ をエピソードの中で状態 $s_{t}$ からステップ $t$ 以降に得られた即時報酬の合計と定義します。

$g_t = r_t + r_{t+1} + ．．．+ r_{n-1} = \sum_{i=t}^{n-1}r_i$

この記法を用いた場合は $g=g_0$ となります。

本記事では、具体的なエピソードから得られた累積報酬（収益）の「実現値」を小文字の $g_t$、この後で説明する「確率変数」を大文字の $G_t$ としました。なお、文献によっては累積報酬（収益）の実現値に $q_t$ などの別の記号を用いる場合があります。

割引累積報酬と収益

多くの強化学習の手法では、ステップ数が大きな即時報酬を小さく計算するという割引累積報酬（discounted cumulative reward）を用いて強化学習を行います。なお、今回の記事では割引累積報酬の定義だけを紹介することにし、その具体的な意味や、割引累積報酬を用いた強化学習の手法については今後の記事で紹介することにします。

ステップ $t$ からの割引累積報酬 $g_t$ は下記のようにステップ $t$ 以降の「ステップ $i$ で得られる即時報酬 $r_i$」に対して「割引率」と呼ばれるギリシャ文字の小文字のガンマ $γ$ で表される「$γ^{i-t}$ を乗算したものの合計」を計算します。

$g_t = r_t + γ^1r_{t+1} + γ^2r_{t+2} + ．．．+ γ^{n-1-t}r_{n-1} = \sum_{i=t}^{n-1}γ^{i-t}r_i$

割引累積報酬では割引率 $γ$ に 0 以上 1 未満の値を設定し、その値の累乗を計算することでステップ数が $t$ から大きくなればなるほど即時報酬が小さく計算されます。

$1$ の実数のべき乗は必ず 1 になるので、割引率を $γ=1$ とした場合の上記の式は累積報酬の計算式と同じになります。これは、割引率が 1 であるということが「何も割り引かない」ことを表すからです。

強化学習では一般的にこの割引累積報酬を「収益」と呼ぶことで累積報酬と区別しますが、両者を区別せずに累積報酬を収益と呼ぶ場合があります。本記事では以降は累積報酬をそのまま「累積報酬」、割引累積報酬を「収益」と表記して区別することにします。

両者の使い分け

強化学習では学習対象の性質に応じて「累積報酬」と「収益」のどちらの期待値を最大化するかを使い分けます。例えば 〇× ゲームのような途中のステップで報酬が得られず、最後のステップでのみ報酬が得られるような場合は「累積報酬」を用いた強化学習を行うのが一般的です。そのため、今回の記事の後半では「累積報酬」の期待値を最大化する場合について説明します。

価値と価値関数

強化学習では方策に従って行動を行った場合に得られる「累積報酬の期待値」のことを価値（value）と呼び、以下の 2 種類があります。

• 状態価値（state value）：状態 $s$ から方策 $Π$ に従って行動を取り続けた場合に得られる累積報酬の期待値
• 行動価値（action value）：状態 $s$ で行動 $a$ を取り、その後方策 $Π$ に従って行動を取り続けた場合に得られる累積報酬の期待値

状態価値関数

状態 $s$ での状態価値を表す関数のことを状態価値関数と呼び、下記のように $V_Π$ という記号を用いて表記します。なお、$V$ の添字に方策を表す $Π$ を記述する理由は、状態価値が方策 $Π$ によって選択された行動の結果計算されることを明確にするためです⁸。

$V_Π(s)$

累積報酬を表す確率変数を $G$ と表記すると、状態価値は「状態 $s$ から方策 $Π$ に従って行動を取りづ付ける」という条件のもとで得られる累積報酬 $G$ の期待値なので、期待値を表す $E$ の括弧の中に条件付き確率と同様の条件を表す $|$ という記号を用いた下記の式で定式化できます。

$V_Π(s) = E[G \mid s, Π]$

行動価値関数

行動価値を表す関数のことを行動価値関数と呼び、下記のように $Q$ という記号を用いて表記します。

$Q_Π(s, a)$

マルコフ性を持つ決定論的な状態遷移の場合は、状態 $s$ で行動 $a$ を取った場合に遷移する状態 $s'$ は状態遷移関数を用いて $s' = f(s, a)$ という状態に必ず遷移します。また、マルコフ性を持つ決定論的な即時報酬の場合はその際に $r(s, a)$ という即時報酬を得るので、行動価値関数は報酬関数と状態価値関数の合計による下記の式で定式化できます。

$Q_Π(s, a) = r(s, a) + V_Π(f(s, a))$

今回の記事では紹介しませんが、確率的な状態遷移や即事報酬が得られる場合も $Q_Π(s, a)$ を報酬関数と状態価値関数を用いて定式化できます。

状態価値と行動価値の定義からわかるように、この 2 種類の価値は「将来に得られる累積報酬の期待値」という同じものを「この状態がどのくらいの価値を持つか」と「この状態でこの行動をとることがどのくらいの価値を持つか」という 2 つの異なる側面で表したものです。また、2 種類の価値を定義した理由は、強化学習の手法の中で状況に応じてこの 2 種類の価値を使い分けることができると便利なことがあるからです。具体的な使い分けについては今後の記事で紹介します。

行動価値関数は品質を表す quality の頭文字で、ある状態 $s$ における行動 $a$ の品質（quality）の高さを表す指標となることが由来です。また、他の機械学習で用いられる記号と頭文字が被らないように quality を選択したという理由もあるようです。

強化学習の定式化

強化学習の目的は累積報酬の期待値を最大化する方策を求めることで、この累積報酬の期待値は初期状態を $s_0$ とした場合の下記の状態価値関数で表されます。

$V_Π(s_0)$

このような最適化を求める問題において、最大化（または最小化）の対象となる関数のことを「目的関数（objective function）」と呼びます。

目的関数 $V_Π(s_0)$ を最大化する方策のことを「最適方策（optimal policy）」と呼び、数学において最適な値や関数であることを表す * を $Π$ の右肩につけた $Π^*$⁹ と表記します。

また、上記の最適方策を表す $Π^*$ は下記の式で定式化できます。

$Π^* = \operatorname{argmax}_{Π} V_Π(s_0)$

上記の式の argmax の arg は関数の引数を表す argument の略で、$V_Π(s_0)$ の最大値を計算する「$\max V_Π(s_0)$」の max の前に arg と添字¹⁰に $Π$ をつけた「$\operatorname{argmax}_{Π} V_Π(s_0)$」は $V_Π(s_0)$ を最大化する argument である $Π$ を計算するという意味の式になります。

従って、今回の記事での定義を用いて強化学習を下記のように定式化することができます。ただし下記の定式化は、状態遷移と即時報酬と方策がマルコフ性を持ち、状態遷移と即時報酬が決定論的であるものとします。

強化学習の目的は、環境によって下記が定義された場合に、エージェントと環境の相互作用によって得られた経験を元に、目的関数 $V_Π(s_0)$ を最大化する下記の式で定式化される最適方策 $Π^*$ を見つけることである。

$Π^* = \operatorname{argmax}_{Π} V_Π(s_0)$

• 状態の集合を表す $\mathcal{S}$
• 行動の集合を表す $\mathcal{A}$
• 「任意の状態 $s \in \mathcal{S}$」と「その状態 $s$ で取りうる任意の行動 $a \in \mathcal{A}(s)$」のすべての組み合わせに対する「状態遷移関数 $f(s, a)$」と「報酬関数 $r(s, a)$」
• エピソードの開始時の初期状態を表す $s_0$
• エピソードの終了条件（特定の状態への遷移、一定時間の経過など）

状態遷移と即時報酬が確率的な場合は、上記の状態遷移関数と報酬関数を確率的な $P(s' \mid s, a)$ と $P(r \mid s, a, s')$ に置き換えるだけでそのまま成り立ちます。

〇× ゲームには当てはまらないので本記事では取り扱いませんが、環境によっては初期状態が複数あり、その中から確率的に初期状態が選択される場合があります。例えば最初にカードをシャフルしてから手札を配るようなトランプのゲームは、最初の手札（初期状態）が毎回異なります。

初期状態が確率的に選択される場合は、初期状態 $S_0$ が $s$ となる確率を下記の確率質量関数で表します。

$P(S_0 = s)$

エピソードの終了条件が設定されなかったり、特定の状態が繰り返し行われ続けるような場合などでは、エピソードのステップが無限に続く（$n \to \infty$）ことになります。そのような場合に単純に即時報酬の合計を計算する累積報酬の期待値を目的関数として強化学習を行うと、累積報酬が無限大に発散する可能性が生じるため、どの方策が優れているかを数学的に比較できなくなる場合があります。

そのような場合は、先ほど説明した収益（割引累積報酬）を用いることで収益が一定の値に収束する（無限大に発散しない）ように工夫します。詳しくは今後の記事で紹介する予定です。

今回の記事のまとめ

今回の記事では強化学習の基礎となる様々な概念を、式と記号を用いて数学的に表現するという「定式化」を行いました。また、状態遷移、即時報酬、方策が「マルコフ性」という重要な性質を持つ場合に、強化学習がどのような問題として定義されるかを整理しました。

また、次回の記事では、今回定式化した下記の「目的関数（状態価値関数）を最大化する最適方策 $\Pi^*$（パイスター）」を効率よく求めるために、マルコフ性が極めて重要な役割を果たす理由について詳しく解説します。

$Π^* = \operatorname{argmax}_{Π} V_Π(s_0)$

さらに、前回の記事でプログラムを実装した「原始モンテカルロ法」による強化学習の手法を、今回定義した数式と記号のルールを使って数学的に読み解いていく予定です。

本記事で入力したプログラム

今回の記事で入力したプログラムはありません。

次回の記事

1. 以前の記事で計算したように、同一局面を考慮した場合の 〇× | ai.py | 本記事で更新した ai_new.py |
   \mathcal{A})$、$card(\mathcal{A})$ などの表記法があります ↩

2. この名前はマルコフ性に関する研究を行ったロシア人数学者のアンドレイ・マルコフが由来です ↩

3. 状態遷移関数を表す記号として遷移を表す transision の頭文字から $T(s, a)$ のように表記する場合があります。また、この後で説明する確率的な状態遷移を $P$ とは異なる $T(s, a, s')$ と表記することがあります ↩

4. 報酬関数を大文字で $R(s, a, s')$ のように表記する場合があります ↩

5. 決定論的な方策においても方策関数を $π(s)$ と表記する場合があります ↩

6. $t$ という記号を用いるのは、この記号がエピソード内の時間（time）経過を表すからです ↩

7. 累積報酬（cumulative reward）の頭文字をとって $c$ や $c_t$ で表記する場合があります ↩

8. $Π$ を関数の引数として $V(s, Π)$ のように表記する場合があります。なお、環境を表す状態遷移関数 $f$ や報酬関数 $r$ はエージェントの方策に影響を受けないため、添字や引数に $Π$ を記述することはありません ↩

9. 「*」 は「スター」と読み、$Π^*$ は「パイスター」と読みます ↩

10. argmax の下に記述する場合があります ↩