MLエンジニアへの道 #37 - マルコフ決定過程

このブログ記事では、強化学習におけるマルコフ決定過程について紹介します。

これまで、私たちはラベルを与えてモデルに学習させる教師あり学習と、ラベルを与えずにモデルにパターンを学習させる教師なし学習（例：主成分分析（PCA））を扱ってきました。本記事では、新しい機械学習のパラダイムである強化学習について紹介します。

注: 本記事の内容は、Sutton, S. R. & Barto, G. A. (2015)による Reinforcement Learning: An Introduction を元にしたものです。ぜひチェックしてみてください。

強化学習とは？

強化学習は、環境と相互作用しながら報酬を最大化するエージェントを研究する、非常にユニークな機械学習のパラダイムです。教師あり学習とは異なり、教師が存在せず、エージェントが自ら世界を探索して行動を形成しなければなりません。また、教師なし学習とも異なり、エージェントは報酬を最大化するために一連の行動を実行する必要があります。

このパラダイムのユニークさは、特有の課題をもたらします。その最大の課題が、探索と活用のトレードオフです。エージェントは、経験を通じて得た知識を活用し、報酬をもたらした行動を実行する必要がありますが、同時に、より高い報酬をもたらす可能性のある未経験の行動を探索する必要もあります。このトレードオフは、環境全体ではなく限定的な課題にのみ焦点を当てる教師あり学習や教師なし学習には存在しない課題です。

強化学習エージェントは、環境全体における最適な行動を考慮するため、環境を厳密に制御する必要がある他の2つのアプローチ（教師あり・教師なし学習）と比較して、よりロバストで現実世界に適用可能です。現代の強化学習は、多くの分野からの知見を取り入れており、そのロバスト性と適用性をさらに向上させています。このため、強化学習はAIや機械学習における非常に興味深い研究分野であり、強化学習の応用がLLMを含む多くの分野で見られる理由でもあります。

問題定義

強化学習タスクは以下の図のように単純に表現できます。環境が現在の状態と報酬をエージェントに送り、エージェントが現在の状態と報酬に基づいて利用可能な行動を選択します。

各離散的な時刻 $t = 1, 2, 3...$ において、エージェントは環境の現在の状態 $S_t=s$ を受け取り、前回の行動に対応する報酬 $R_t=r$ を得て、状態 $S_t$ における行動の確率を表すポリシー $\pi_t(a|S_t = s)$ に基づいて行動 $A_t=a$ を選択します。その後、1ステップ後に環境は状態 $S_{t+1}=s'$ に遷移し、状態 $s$ で行動 $a$ を取った結果として報酬 $R_t+1=r'$ が与えられます。このプロセスは、最大のタイムステップに達するか、エージェントがゴール状態に到達するまで続きます。エージェントの目的は、複数のエピソードを経験することによって、1サイクルまたはエピソード内で報酬の合計を最大化する最適なポリシー $\pi$ を学習することです。

次の状態 $s'$ への遷移確率が現在の状態 $s$ と行動 $a$ のみに依存する場合、この遷移は マルコフ性 を持つと言います。この性質があると、各行動に対する期待報酬を容易に計算し、期待報酬が最も高い行動を選択できるため望ましいとされています。すべての状態遷移がマルコフ性を満たす場合、そのプロセスを マルコフ決定過程 （Markov Decision Process, MDP）と呼びます。強化学習の分野では、ほとんどのタスクがMDPとして定義できるという仮定の下でMDPを主に扱います。（この仮定の妥当性についての議論は記事の最後で行います。）

有限マルコフ決定過程

すべての可能な状態と行動の集合はそれぞれ状態空間と行動空間と呼ばれます。強化学習は、有限の状態空間と行動空間を持つMDPに主に焦点を当て、これを有限マルコフ決定過程と呼びます。有限MDPは、次の4つの要素で定義されます：有限状態空間 $S$ 、有限行動空間 $A$ 、状態 $s$ から次の状態 $s'$ への行動 $a$ に基づく遷移確率 $P_{ss'}^{a}$ 、およびその遷移から得られる即時報酬 $R_{ss'}^a$ 。ここでの目標は、エピソードの期待報酬（または累積報酬）を最大化するポリシーを学習することです。MDPは以下のようなグラフで表現することがよくあります。

上図は有限MDPの例です。状態空間はすべての都市で、行動空間はは選択できるすべての乗り物です。状態遷移はそれぞれの都市間での行動によって行われ、その遷移には確率（異なる交通渋滞レベルにより到達する都市が変わる可能性、アクシデントの可能性など）と報酬（費やした時間の負の報酬）が関連付けられています。ここでは、City AからCity Dへの移動において、最高の報酬（または最短時間）を得るための最適なポリシーを見つけることを課題とすることができます。マルコフ性に基づき、次の状態と報酬の各可能なペアの確率は次のように表されます。

p(s', r | s, a) = \text{Pr}\{S_{t+1} = s', R_{t+1} = r | S_t = s, A_t = a\}

これらの変数は有限MDPの全ダイナミクスを捉えており、次のような興味のある値を計算することができます：状態-行動ペアの期待報酬、

r(s, a) = \text{E}[R_{t+1} | S_t = s, A_t = a] = \sum_{r \in R} r \sum_{s' in S}p(s', r | s, a),

報酬に対して積分を行うことで得られる状態遷移確率、

p(s' | s, a) = \text{Pr}\{S_{t+1} = s' | S_t = s, A_t = a\} = \sum_{r \in R} p(s', r | s, a),

および状態、行動、次の状態の組み合わせに対する期待報酬

r(s' | s, a) = \text{E}[R_{t+1} | S_t = s, A_t = a, S_{t+1} = s'] = \frac{\sum_{r \in R} rp(s', r | s, a)}{p(s'|s, a)}.

状態遷移確率と期待報酬にはそれぞれ $P_{ss'}^a$ と $R_{ss'}^a$ を用いました。しかし、以前の期待報酬の表記は期待値しか与えず、報酬のダイナミクスを完全には表現しません。また、添字や上付き文字が多すぎるため、今後有限MDPに関する数学を議論する際には $p(s', r | s, a)$ 、 $p(s' | s, a)$ 、および $r(s' | s, a)$ を使用します（ただし、問題定義では引き続き $P_{ss'}^a$ や $R_{ss'}^a$ を使用する場合があります）。

ベルマン方程式

エージェントの目的は、行動の結果として次の状態がどれだけ良いか、つまり将来の期待報酬に基づいて増分的な行動を取ることです。この状態の価値を計算するために、ポリシーの下で将来の期待報酬を計算する関数を 価値関数 と呼びます。

v_{\pi}(s) = \text{E}_{\pi}[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s]

ここで、 $\gamma$ は将来の報酬に対する割引率です。同様に、ポリシーの下で状態 $s$ における行動 $a$ を取った場合の価値を計算する 行動価値関数 も定義できます。

q_{\pi}(s, a) = \text{E}_{\pi}[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s, A_t = a]

価値関数は将来の報酬の合計を取るため、本質的に再帰的な性質を持っています。価値関数を展開すると、現在の状態と次の状態の価値の間の再帰的な関係を次のように表現できます：

v_{\pi}(s) = \text{E}_{\pi}[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s] \\ = \text{E}_{\pi}[R_{t+1} + \gamma\sum_{k=0}^{\infty} \gamma^k R_{t+k+2} | S_t = s] \\ = \sum_a \pi(a|s) \sum_{s'}\sum_r p(s', r | s, a) [r + \gamma\text{E}_{\pi}[\sum_{k=0}^{\infty} \gamma^k R_{t+k+2} | S_{t+1} = s']] \\ - \sum_a \pi(a|s) \sum_{s'}\sum_r p(s', r | s, a) [r + \gamma v_{\pi}(s')]

この式を展開する際、すべての可能な次の状態と報酬を合計して現在の状態と行動に基づいた期待報酬を計算しなければなりません。その後、現在の状態のみの価値を得るためにさらに行動について和を取ります。上記の式は、ポリシー $\pi$ の下で行動を取る場合の期待報酬を再帰的に表現した ベルマン方程式 です。

ベルマン最適方程式

期待される将来の報酬を最大化できる最適なポリシーの下では、ある状態の価値はその状態から最適な行動に対する期待される将来の報酬と等しくなければなりません。この理由は直感的に理解できます。価値が一貫性なく計算され、報酬を最大化しない行動が選択されると、結果として最適でないなポリシーが選ばれる可能性があるためです。これに基づき、最適なポリシーによって次に移動するべき最適な状態を選択するために使用できる ベルマン最適方程式 $v_*$ を次のように定義できます。

v_{*}(s) = \max_{a \in A(s)} q_{\pi_*}(s, a) \\ = \max_{a} \text{E}_{\pi^*}[\sum_{k=0}^{\infty} R_{t+k+1} | S_t=s, A_t=a] \\ = \max_{a} \text{E}_{\pi^*}[R_{t+1}+\gamma\sum_{k=0}^{\infty} R_{t+k+2} | S_t=s, A_t=a] \\ = \max_{a} \sum_{s'}\sum_r p(s', r | s, a) [r + \gamma v_{*}(s')]

同様に、 $q_*$ のベルマン最適方程式を次のように定義できます。

q_{*}(s, a) = \text{E}[R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') | S_t=s, A+t=a] \\ = \sum_{s'}\sum_r p(s', r | s, a) [r + \gamma \max_{a'} q_*(s', a')]

ベルマン最適方程式は、全ての値 ( $p(s', r | s, a)$ ) が既知である場合、実際には方程式系であり、すべての状態 $s$ に対する $v_*(s)$ を求めることができ、これを使用して、最高の値を持つ隣接する状態に遷移する行動にのみ非ゼロの確率を割り当てる最適なポリシーを導出できます。しかし、この解法を適用することはほぼ確実に不可能です。なぜなら、これには全ての値の完全な知識、完全なマルコフ性、そして合理的な時間内に方程式系を解くための計算リソースが必要であり、いずれも現実的には得るのが困難だからです。

例えば、チェスのボード配置は $10^{111}$ から $10^{123}$ に達すると推定されており、これをすべて管理するのは不可能です。私たちは状態遷移確率や期待報酬を単純に知ることができず、ボード配置だけが次の状態の確率に影響を与える観測可能な要因ではありません。たとえば、相手の態度や残り時間などが影響するため、完全にマルコフ性を満たしているとは言えません。このような膨大な問題について方程式系を解くのは非現実的です。この様な理由から、強化学習は、利用可能な合理的なリソース内で最適なポリシーの近似を生成することに焦点を当てています。

結論

この記事では、強化学習のパラダイム、マルコフ決定過程、ベルマン方程式、ベルマン最適方程式を紹介し、強化学習タスクの本質を直感的かつ数学的に理解しました。次の記事では、最適なポリシーを近似するアルゴリズムについて深く掘り下げる前に、強化学習タスクをプログラム的にどのように表現するかを学びます。

[後書き] マルコフ性の仮定の妥当性

現実には、すべての状態遷移が完全にマルコフ性を満たすような閉じたシステムを見つけることは難しいです。むしろ、次の状態に影響を与える可能性のあるすべての関連情報を含むような状態を定義すること自体が難しいです。例えば、ポーカーのゲームをモデル化する際、エージェントの手札、プレイヤーのベット額、公開されたカードの数を状態に含めることができます。しかし、状態遷移はプレイヤーの顔つきや声の大きさ、時間帯などの観測可能な他の要因に依存する可能性もあります。これらをすべて定量化し、状態に含めることは事実上、実用上不可能ですが、だからといってポーカーの学習にMDPを使用することが不適切だと言えるのでしょうか？

一般にMDPの使用は適切であるとされます。なぜなら、上記の他の要因は確率にわずかしか影響を与えないからです。状態遷移が完全にマルコフ性を満たさなくても、エージェントの手札、プレイヤーのベット額、公開されたカードの数が次の状態の確率を主に決定するはずです。例えば、他のプレイヤーのベット額が高い場合、エージェントはその手札に自信があると評価し、顔を見て自信があるかどうか確認することなくフォールドすることができます。すべての状態が完全にマルコフである問題を定義することはほとんど不可能ですが、状態が大部分でマルコフ性を持っていればMDPを仮定するには十分です。したがって、 (マルコフ性の仮定と他の要因に基づいて強化学習が最適なポリシーの近似に焦点を当てる一方で)多くのタスクはMDPとしてモデル化できると安心して考えることができます。

リソース

Sutton, S. R. & Barto, G. A. 2015. Reinforcement Learning: An Introduction. Stanford.