強化学習の基礎

私たちは日常生活の中で、常に「どう行動すべきか」という判断を迫られています。朝の通勤ルートを選ぶとき、投資先を決めるとき、新しいスキルを身つけるとき——これらすべては、不確実な環境の中で試行錯誤を重ねながら、より良い結果を得ようとする学習プロセスという共通点を持ちます。

強化学習は、まさにこの人間的な学習過程を数学的に定式化し、コンピュータに実装する機械学習の分野です。従来の機械学習が「正解を教えて覚えさせる」アプローチだとすれば、強化学習は「自分で試してみて学ばせる」アプローチと言えるでしょう。

この記事では、強化学習の基本的な考え方から始まり、その数学的基盤であるマルコフ決定過程、そして理論の核心であるベルマン方程式までを段階的に解説していきます。一見複雑に見える数式も、その背後にある直感的なアイデアを理解すれば、実は非常に自然で美しい理論体系であることが分かるでしょう。

1. 強化学習とは

なぜ強化学習が必要なのか

従来の機械学習手法である教師あり学習や教師なし学習では解決が困難な問題があります。

教師あり学習の限界
教師あり学習は正解ラベルが事前に用意されたデータセットを用いて学習しますが、多くの実世界の問題では正解が明確ではありません。また、静的なデータセットに基づく学習であるため、動的に変化する環境に対応することが困難です。例えば、チェスや囲碁において「この局面での最適な手」を事前に全て用意することは現実的に不可能です。局面の組み合わせが天文学的な数になるためです。
教師なし学習の限界
教師なし学習はデータの中からパターンや構造を見つけることは得意ですが、「何をすべきか」という具体的な行動指針は提供できません。データの背後にある構造を理解できても、目標達成のための戦略的な意思決定には不向きです。
強化学習が扱う状況
強化学習は、これらの従来手法では扱えない以下のような状況を扱えます。

• 逐次意思決定
• 遅延報酬
• 探索と活用のトレードオフ
• 動的環境

逐次意思決定とは、現在の選択が将来の選択肢や結果に影響を与える問題のことです。例えば、チェスで今の一手が後の局面を決定したり、投資で今日の判断が明日のポートフォリオに影響したりする状況です。強化学習は、こうした長期的な影響を考慮して最適な行動系列を学習できます。

遅延報酬とは、行動を取ってから結果（良いか悪いか）が分かるまでに時間がかかる問題です。例えば、新薬の開発では今の研究方針の良し悪しが数年後に判明したり、教育では今日の指導法の効果が学期末にならないと分からなかったりします。強化学習は、このような将来の報酬を現在の行動選択に反映できます。

探索と活用のトレードオフとは、未知の可能性を探るか既知の良い選択肢を選ぶかのジレンマです。レストラン選びで例えると、いつものお気に入りの店に行く（活用）か、新しい店を試してみる（探索）かという判断です。強化学習アルゴリズムは、この探索と活用のバランスを自動的に調整します。

動的環境とは、時間とともに状況が変化する環境のことです。株式市場のように市況が刻々と変わったり、自動運転で交通状況が常に変化したりする状況です。強化学習は、こうした変化に応じて戦略を継続的に更新し、適応的な行動選択を実現できます。

強化学習の応用例

強化学習は理論的な枠組みにとどまらず、現実世界で革新的な成果を生み出しています。

ゲームAI
AlphaGoが囲碁でプロ棋士を破り、AI研究の転換点となりました。囲碁の可能な局面数は10^170と膨大ですが、強化学習により人間を超える戦略を獲得。OpenAI FiveはDota 2でチーム協調行動を実現し、プロゲーマーに勝利しています。

ロボティクス
歩行ロボットは強化学習により、不整地での安定歩行や転倒からの復帰を学習。産業用ロボットでは、多様な物体の把持・操作タスクで人間のような器用さを実現しています。

自動運転
交差点での判断、合流タイミング、歩行者との相互作用など、ルールベースでは困難な状況での意思決定に活用。Waymoはシミュレーションで数十億マイル相当の経験を蓄積し、稀な危険シナリオへの対処も学習しています。

ビジネス応用
推薦システムではNetflixやYouTubeが長期的なユーザーエンゲージメントを最大化。金融取引ではJPMorgan ChaseのLOXMが市場影響を最小化しながら大量注文を執行。広告配信ではGoogleやFacebookが短期的クリック率と長期的顧客価値のバランスを最適化しています。

強化学習の特徴

強化学習は、エージェントが環境との相互作用を通じて最適な行動を学習する機械学習の一分野です。人間が試行錯誤を通じて学習するのと同様に、エージェントは報酬というフィードバックを受けながら、より良い行動戦略を獲得していきます。強化学習には以下のような特徴があります。

• 試行錯誤による学習：正解データがない状況での学習
• 遅延した報酬：行動の結果がすぐに分からない場合がある
• 探索と活用のトレードオフ：新しい行動を試すか、既知の良い行動を選ぶかの判断
• 環境との相互作用：静的なデータではなく、動的な環境との対話を通じた学習

2. 強化学習の基本要素

強化学習のフレームワークは、以下の5つの基本要素から構成されます。これらの要素が相互に作用することで、学習プロセスが進行します。

エージェント（Agent）

学習する主体であり、意思決定を行う存在です。人間のプレイヤー、ロボット、ソフトウェアプログラムなど、環境に対して能動的に働きかけることができるものを指します。

環境（Environment）

エージェントが存在し相互作用する世界全体を表します。ゲームのルールと盤面、物理的な空間、市場の仕組みなど、エージェントの外部にあるすべてが環境に含まれます。

状態（State）

ある時点における環境の情況を表現する情報です。チェスの盤面配置、ロボットのセンサー情報、株価のチャートなど、エージェントが意思決定を行うために必要な情報が含まれます。完全に観測可能な場合と部分的にしか観測できない場合があります。

行動（Action）

エージェントが各状態において選択可能な選択肢です。離散的な行動（上下左右の移動、買う・売る・待つ）と連続的な行動（ロボットの関節角度、車のステアリング角度）があります。

報酬（Reward）

エージェントの行動に対する即時的な評価です。正の報酬は望ましい結果を、負の報酬（ペナルティ）は望ましくない結果を示します。ゴールに到達した時の大きな報酬、壁にぶつかった時の小さなペナルティなど、タスクの目的を報酬関数として設計することが強化学習の重要な要素となります。

3. マルコフ決定過程（MDP）

強化学習の数学的基盤となるのがマルコフ決定過程（Markov Decision Process, MDP）です。MDPは、不確実性のある環境での逐次意思決定問題を定式化する数学的フレームワークです。

MDPの定義

定義：マルコフ決定過程（MDP）

MDPは以下の4つ組$(S, A, P, R)$で定義される：

• $S$：状態集合（State space）- すべての可能な状態の集合
• $A$：行動集合（Action space）- すべての可能な行動の集合
• $P: S \times A \to \mathcal{P}(S)$：遷移確率関数 - 状態$s$で行動$a$を取った時の次状態の確率分布
• $R: S \times A \times S \to \mathcal{P}(\mathbb{R})$：報酬関数 - 状態$s$で行動$a$を取り状態$s'$に遷移した時の報酬の確率分布

ここで、$\mathcal{P}(X)$は集合$X$上の確率分布の集合を表す。
決定的な場合、$P(s,a)$は単一の状態に確率1を割り当てる分布、$R(s,a,s')$は単一の実数値に確率1を割り当てる分布となる。

強化学習では、このMDPに対して割引率$\gamma \in (0,1]$を導入し、割引累積報酬を最大化する問題を考えます。

定義：割引累積報酬（Discounted Cumulative Reward）

エージェントが環境と相互作用する際、時刻$t$における状態を$s_t \in S$、行動を$a_t \in A$と表記する（小文字は集合の要素を表す）。時刻$t$から始まる割引累積報酬$G_t$は、将来得られる報酬の割引和として定義される。

$$G_t = \sum_{k=0}^{\infty} \gamma^k R(s_{t+k}, a_{t+k}, s_{t+k+1})$$

ここで$R(s_{t+k}, a_{t+k}, s_{t+k+1})$は時刻$t+k$で得られる即時報酬である。これを$r_{t+k+1}$と表記すると、

$$G_t = \sum_{k=0}^{\infty}\gamma^kr_{t+k+1}$$

と書ける。

割引率$\gamma$の値により、エージェントの行動戦略が大きく変わります：

• $\gamma$が1に近い場合：将来の報酬も現在の報酬とほぼ同等に重視する長期的視点での最適化
• $\gamma$が0に近い場合：即座の報酬を重視し、将来の報酬をほとんど考慮しない近視眼的な最適化

通常は$0.9 \leq \gamma < 1$の範囲で設定されることが多い印象です。

マルコフ性：MDPのM

MDPが有効な数学的フレームワークとして機能するためには、重要な仮定があります。それがマルコフ性です。

定義：(一次)マルコフ性（Markov Property）

状態遷移確率関数$P$が1つ前の時間の状態(と行動)のみに依存し、それより過去の状態と行動には依存しないという性質。

$$P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, \ldots, s_0, a_0) = P(s_{t+1} | s_t, a_t)$$

現実世界の多くの問題では、次に起こることは過去の複雑な履歴に依存するように思えます。例えば、株価の予測では過去数日や数週間のトレンドが重要に見えますし、医療診断では患者の病歴全体が判断材料となります。しかし、強化学習でこのような複雑な依存関係をすべて考慮すると、問題が数学的に扱いにくくなってしまいます。そこで、MDPではマルコフ性を仮定します。

マルコフ性により、現在の状態さえ分かれば、そこに至るまでの経緯に関わらず、最適な行動を決定できます。例えばチェスでは、現在の盤面さえ分かれば、その局面に至るまでの手順に関わらず最善手を考えることができます。

マルコフ性は制約のように見えますが、実際には状態の定義を適切に行うことで多くの問題に適用可能です。過去の情報が重要な場合は、それらを現在の状態に含めることで対処することが可能です。

状態遷移と報酬の仕組み

MDPにおけるエージェントと環境の相互作用は、時間を離散的なステップに分けて考えます。各時刻$t = 0, 1, 2, \ldots$において、以下のプロセスが順次実行されます：

基本的な相互作用サイクル

1. 状態観測：エージェントが現在の状態$s_t \in S$を観測
2. 行動選択：観測した状態に基づいて行動$a_t \in A$を選択
3. 状態遷移：環境が確率$P(s_{t+1}|s_t,a_t)$に従って次の状態$s_{t+1}$に遷移
4. 報酬受領：遷移の結果として報酬$r_{t+1} = R(s_t,a_t,s_{t+1})$を受け取る

このプロセスが無限に（または終了条件に達するまで）繰り返されることで、軌道（trajectory） $\tau$と呼ばれる状態・行動の系列が生成されます：

$$\tau = s_0, a_0, s_1, a_1, s_2, a_2, \ldots$$

報酬は軌道に沿って得られる情報として扱われます。

状態遷移の確率的性質
重要な点は、状態遷移が確率的であることです。同じ状態で同じ行動を取っても、必ずしも同じ次状態に遷移するとは限りません。この不確実性により：

• 環境の予測不可能性（風の影響でロボットの動きがぶれる、など）
• 情報の不完全性（すべての要因を状態に含められない）
• 本質的なランダム性（量子力学的な現象、など）

を表現できます。

報酬の役割
報酬$R(s,a,s')$は、エージェントに「何が望ましい行動か」を教える唯一の手段です。

MDPの定義において、報酬関数$R: S \times A \times S \to \mathcal{P}(\mathbb{R})$は確率分布を返しますが、実際の問題では：

• 決定的報酬：単一の値に確率1を割り当てる退化分布（例：ゴール到達で確実に+10）
• 確率的報酬：複数の値に正の確率を割り当てる分布（例：ガチャの報酬、ノイズのある評価）

のいずれかのパターンが使われます。

報酬関数の設計方法には主に2つのアプローチがあります：

• 密な報酬（Dense Reward）：各ステップで小さな報酬を与える（歩行ロボットで前進した距離に比例した報酬）
• 疎な報酬（Sparse Reward）：目標達成時のみ大きな報酬を与える（ゴール到達時に+1、それ以外は0）

報酬関数の設計は学習の効率や最終的な行動に大きく影響するため、問題設定において慎重に検討する必要があります。

4. 方策(Policy)と価値関数

なぜ価値を定量化する必要があるのか

MDPの枠組みで強化学習問題を定式化できましたが、実際にエージェントが最適な行動を選択するためには、「どの状態が良いのか」「どの行動が有効なのか」を判断する基準が必要です。

人間が意思決定を行う際も、無意識のうちに選択肢を評価しています：

• チェスで「この局面は有利だ」と感じる
• 投資で「この銘柄は将来性がある」と判断する
• 料理で「この手順だと美味しくできそう」と予想する

強化学習でも同様に、エージェントが賢明な選択をするためには、状態や行動の「良さ」を数値化して比較できる仕組みが不可欠です。

即座の報酬だけでは不十分

単純に考えると、「報酬が高い行動を選べば良い」と思えるかもしれません。しかし、強化学習では遅延報酬の問題があります：

• チェスで今の一手が数手先の勝利につながる
• 勉強という即座には報酬のない行動が将来の成功をもたらす
• 投資で短期的な損失が長期的な利益につながる

割引累積報酬から価値関数へ

先ほど定義した割引累積報酬$G_t$は、時刻$t$から得られる将来の報酬の総和でした：

$$G_t = \sum_{k=0}^{\infty} \gamma^k R(s_{t+k}, a_{t+k}, s_{t+k+1})$$

しかし、この$G_t$は実際に経験した軌道に依存する値です。同じ状態$s_t$からスタートしても、その後の行動選択や確率的な状態遷移により、$G_t$の値は変わります。

エージェントが意思決定を行う際に本当に知りたいのは：

• 「状態$s$にいる時、方策$\pi$に従って行動すれば、平均的にどれだけの累積報酬が期待できるか？」
• 「状態$s$で行動$a$を取り、その後方策$\pi$に従えば、平均的にどれだけの累積報酬が期待できるか？」

この「期待される割引累積報酬」が価値関数の正体です。価値関数は確率的な環境における累積報酬の期待値として定義されます。

方策（Policy）の概念

価値関数を定義する前に、方策(Policy) という重要な概念を理解する必要があります。

方策とは、エージェントの「行動選択の規則」です。各状態において、どの行動を選ぶべきかを決める指針を表します。人間の例で言えば：

• チェスで「この盤面ではこの手を打つ」という判断基準
• 投資で「この市況では買い・売り・様子見のうちどれを選ぶか」という戦略
• 運転で「この交通状況では加速・減速・車線変更のうちどれを選ぶか」という判断

定義：方策（Policy）

方策$\pi: S \times A \to [0,1]$は、各状態$s \in S$において各行動$a \in A$を選択する確率を表す関数である：

$$\pi(a|s) = P(A_t = a | S_t = s)$$

ここで$\sum_{a \in A} \pi(a|s) = 1$が成り立つ。

• 決定的方策：各状態で一つの行動に確率1を割り当てる
• 確率的方策：各状態で複数の行動に正の確率を割り当てる

方策があることで初めて、「この方策に従って行動した場合の期待価値」を計算することができます。

価値関数の定義

強化学習の目標は、割引累積報酬を最大化する最適方策$\pi^*$を見つけることです。価値関数は、この最適方策を見つけるための評価指標として機能します。

強化学習では、方策$\pi$の良さを以下の2つの価値関数で評価します。

定義：状態価値関数（State Value Function）

方策$\pi$の下での状態価値関数$V_t^{\pi}: S \to \mathbb{R}$は、時刻$t$において状態$s$から方策$\pi$に従って行動した場合に得られる期待割引累積報酬として定義される：

$$V_t^{\pi}(s) = \mathbb{E}_{\pi}\left[G_t \mid S_t = s\right] = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^k R(S_{t+k}, A_{t+k}, S_{t+k+1}) \mid S_t = s\right]$$

MDPのマルコフ性と時不変性（状態遷移確率と報酬関数が時刻によらず一定）により、価値関数は時刻$t$に依存せず、状態$s$のみの関数となるため、$V^{\pi}(s)$と表記する。

定義：行動価値関数（Action Value Function）

方策$\pi$の下での行動価値関数$Q_t^{\pi}: S \times A \to \mathbb{R}$は、時刻$t$において状態$s$で行動$a$を取り、その後方策$\pi$に従って行動した場合に得られる期待割引累積報酬として定義される：

$$Q_t^{\pi}(s,a) = \mathbb{E}_{\pi}\left[G_t \mid S_t = s, A_t = a\right] = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^k R(S_{t+k}, A_{t+k}, S_{t+k+1}) \mid S_t = s, A_t = a\right]$$

MDPのマルコフ性と時不変性（状態遷移確率と報酬関数が時刻によらず一定）により、価値関数は時刻$t$に依存せず、状態$s$と行動$a$のみの関数となるため、$Q^{\pi}(s,a)$と表記する。

2つの価値関数の関係と使い分け

状態価値関数$V^{\pi}(s)$の役割
状態価値関数は「この状態にいることの価値」を表します。チェスで言えば「この盤面は有利か不利か」という評価に相当します。状態価値関数は：

• 環境の設計や分析に有用（どの状態が本質的に良いか）
• 方策の全体的な評価に適している
• 計算が比較的シンプル

行動価値関数$Q^{\pi}(s,a)$の役割
行動価値関数は「この状態でこの行動を取ることの価値」を表します。「この盤面でこの手を打つとどうなるか」という評価に相当します。行動価値関数は：

• 行動選択に直接活用できる（$Q$値が最大の行動を選択）
• 多くの強化学習アルゴリズム（Q学習など）の基盤
• 実際の経験を通じて学習できる

2つの価値関数の関係
状態価値関数と行動価値関数には以下の関係があります：

$$V^{\pi}(s) = \sum_a \pi(a|s) Q^{\pi}(s,a)$$

これは「状態の価値は、その状態で可能な全ての行動の価値を方策に従って重み付け平均したもの」という意味です。

逆に、行動価値関数は状態価値関数を用いて以下のように表現できます：

$$Q^{\pi}(s,a) = \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V^{\pi}(s')\right]$$

これは「行動の価値は、その行動により得られる即座の報酬と、遷移先の状態の価値の和」という意味です。

5. ベルマン方程式

なぜベルマン方程式が必要なのか

価値関数を定義できましたが、実際に$V^{\pi}(s)$や$Q^{\pi}(s,a)$を計算するにはどうすればよいでしょうか？定義に従って無限級数を直接計算するのは現実的ではありません。

ここで重要な洞察があります。価値は現在の選択と将来の価値の組み合わせとして表現できるということです。

例えば、チェスを考えてみましょう：

• 現在の局面の価値 = 次の一手による即座の利得 + その後の局面の価値
• 投資の場合：現在の投資判断の価値 = 今期の収益 + 来期以降の期待価値

この直感を数学的に厳密に表現したものがベルマン方程式です。

ベルマン方程式の基本的なアイデア

ベルマン方程式の核心は「価値の再帰的分解」にあります：

「今の価値 = 即座の報酬 + 将来の価値」

これにより、無限の未来を考える必要がなく、「今」と「次の時刻」の関係だけで価値を表現できます。この分解により：

• 価値関数の計算が可能になる
• 動的プログラミングによる最適化が可能になる
• 効率的な学習アルゴリズムの設計が可能になる

ベルマン方程式は、価値関数の再帰的関係を表す基本的な方程式です。

ベルマン期待方程式の導出

前節で示した価値関数の関係を思い出しましょう：

$$V^{\pi}(s) = \sum_a \pi(a|s) Q^{\pi}(s,a)$$

$$Q^{\pi}(s,a) = \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V^{\pi}(s')\right]$$

第2式を第1式に代入すると：

$$V^{\pi}(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V^{\pi}(s')\right]$$

これがベルマン期待方程式（状態価値関数）です。

同様に、第1式を第2式に代入すると：

$$Q^{\pi}(s,a) = \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma\sum_{a'} \pi(a'|s')Q^{\pi}(s',a')\right]$$

これがベルマン期待方程式（行動価値関数）です。

定義：ベルマン期待方程式（Bellman Expectation Equations）

方策$\pi$に対する状態価値関数と行動価値関数は、以下の再帰的関係を満たす：

状態価値関数：

$$V^{\pi}(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V^{\pi}(s')\right]$$

行動価値関数：

$$Q^{\pi}(s,a) = \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma\sum_{a'} \pi(a'|s')Q^{\pi}(s',a')\right]$$

これらの方程式は「現在の価値 = 即座の報酬 + 将来の割引価値」という価値の分解を表している。

最適方策と最適価値関数

これまでは与えられた方策$\pi$に対する価値関数を考えてきました。しかし、強化学習の最終的な目標は最も良い方策、つまり最適方策を見つけることです。

最適方策の定義
方策$\pi^*$が最適方策であるとは、すべての状態$s$において、他のどの方策よりも高い価値を実現する方策のことです：

$$V^{\pi^*}(s) \geq V^{\pi}(s) \quad \forall \pi, \forall s \in S$$

最適価値関数
最適方策による価値関数を最適価値関数と呼びます：

• 最適状態価値関数: $V^*(s) = V^{\pi^*}(s) = \max_{\pi} V^{\pi}(s) \quad \forall s \in S$
• 最適行動価値関数: $Q^*(s,a) = Q^{\pi^*}(s,a) = \max_{\pi} Q^{\pi}(s,a) \quad \forall s \in S, \forall a \in A$

最適方策の性質

最適方策には重要な性質があります。これらは定理として厳密に証明でき、ベルマン最適方程式の理論的基盤となります。

定理1（貪欲性）

最適方策$\pi^*$は以下を満たす：

$$\pi^*(a|s) = \begin{cases} 1 & \text{if } a \in \arg\max_{a'} Q^*(s,a') \\ 0 & \text{otherwise} \end{cases}$$

すなわち、最適方策は各状態で最適行動価値関数を最大化する行動のみを選択する。

証明
背理法で証明する。最適方策$\pi^*$が状態$s$で$Q^*$値が最大でない行動$a'$を正の確率で選ぶと仮定する：

$$\pi^*(a'|s) > 0 \quad \text{かつ} \quad Q^*(s,a') < \max_{a''} Q^*(s,a'')$$

このとき、状態$s$で最大$Q^*$値を持つ行動$a^* = \arg\max_{a''} Q^*(s,a'')$のみを選択する方策$\tilde{\pi}$を考える：

$$\tilde{\pi}(a|s) = \begin{cases} 1 & \text{if } a = a^* \\ 0 & \text{otherwise} \end{cases}$$

他の状態では$\pi^*$と同じとする。

価値関数の関係より：

$$V^{\pi}(s) = \sum_a \pi(a|s) Q^{\pi}(s,a)$$

最適方策$\pi^*$については：

$$V^{\pi^*}(s) = V^*(s) = \sum_a \pi^*(a|s) Q^*(s,a)$$

仮定により、$\pi^*$は状態$s$で行動$a'$を正の確率$\pi^*(a'|s) > 0$で選び、かつ$Q^*(s,a') < Q^*(s,a^*)$である。

一方、方策$\tilde{\pi}$は状態$s$で行動$a^*$のみを選択するので：

$$V^{\tilde{\pi}}(s) = Q^*(s,a^*)$$

$\pi^*$の価値を詳しく見ると：

$$V^{\pi^*}(s) = \pi^*(a'|s) Q^*(s,a') + \pi^*(a^*|s) Q^*(s,a^*) + \sum_{a \neq a', a^*} \pi^*(a|s) Q^*(s,a)$$

$\pi^*(a'|s) > 0$かつ$Q^*(s,a') < Q^*(s,a^*)$なので、$\pi^*(a'|s)$の確率を$\pi^*(a^*|s)$に移すことで価値が向上する。

したがって：

$$V^{\tilde{\pi}}(s) = Q^*(s,a^*) > V^{\pi^*}(s)$$

これは$V^*(s) = V^{\pi^*}(s) = \max_{\pi} V^{\pi}(s)$という最適性と矛盾する。

したがって、最適方策は各状態で$Q^*$値を最大化する行動のみを選択する。$\square$

定理2（最適性の原理）

方策$\pi^*$が最適方策であるならば、任意の時刻$t$以降の部分方策も最適である。すなわち、$\forall t \geq 0, \forall s_t$に対して、$\pi^*$の時刻$t$以降の部分は状態$s_t$からの最適方策である。

証明
背理法で証明する。最適方策$\pi^*$の時刻$t$以降の部分方策が最適でないと仮定する。すなわち、状態$s_t$から時刻$t$以降により良い方策$\pi'$が存在するとする：

$$V^{\pi'}(s_t) > V^{\pi^*}(s_t)$$

このとき、以下のハイブリッド方策$\tilde{\pi}$を構成する：

• 時刻$0$から$t-1$まで：$\pi^*$に従う
• 時刻$t$以降：$\pi'$に従う

この方策の価値は：

$$V^{\tilde{\pi}}(s_0) = \mathbb{E}\left[\sum_{k=0}^{t-1} \gamma^k r_{k+1} + \gamma^t V^{\pi'}(s_t)\right] > \mathbb{E}\left[\sum_{k=0}^{t-1} \gamma^k r_{k+1} + \gamma^t V^{\pi^*}(s_t)\right] = V^{\pi^*}(s_0)$$

これは$\pi^*$が最適方策であることと矛盾する。したがって、最適方策の任意の部分方策も最適である。$\square$

ベルマン最適方程式の導出

最適価値関数は、最適方策による価値なので、ベルマン期待方程式が成り立ちます。しかし、最適方策では各状態で最良の行動を選択するため、期待値ではなく最大値を取ることになります。

状態価値関数の場合：

$$V^*(s) = \max_a Q^*(s,a) = \max_a \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V^*(s')\right]$$

行動価値関数の場合：

$$Q^*(s,a) = \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V^*(s')\right] = \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma\max_{a'} Q^*(s',a')\right]$$

定義：ベルマン最適方程式（Bellman Optimality Equations）

最適価値関数は以下の再帰的関係を満たす：

最適状態価値関数：

$$V^*(s) = \max_a \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V^*(s')\right]$$

最適行動価値関数：

$$Q^*(s,a) = \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma\max_{a'} Q^*(s',a')\right]$$

これらの方程式は「最適価値 = 最良の選択による即座の報酬 + 将来の最適価値」を表している。

6. ベルマン方程式の意味と重要性

ベルマン方程式は強化学習において極めて重要な役割を果たします。その理由を、これまで学んだ概念を使って説明します。

複雑な計算を簡単にする仕組み

問題：価値関数の計算が困難
価値関数の定義を思い出しましょう。

$$V^{\pi}(s) = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^k R(S_k, A_k, S_{k+1}) \mid S_0 = s\right]$$

この式は「未来永劫にわたる全ての報酬を足し上げる」ことを意味します。計算しようとすると、

• 無限に続く計算が必要
• 全ての可能な軌道を考慮する必要
• 確率的な環境では期待値の計算が複雑

解決：ベルマン方程式による分解
ベルマン方程式は、この複雑な計算を「今の一歩」と「将来の価値」に分解します。

$$V^{\pi}(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V^{\pi}(s')\right]$$

これにより：

• 無限の計算が有限の計算に変換される
• 「次の状態の価値さえ分かれば、現在の価値が計算できる」
• 複雑な問題が単純な関係式で表現される

最適方策を見つける道筋

ベルマン最適方程式の活用
最適価値関数は以下を満たします：

$$V^*(s) = \max_a \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V^*(s')\right]$$

この方程式を解けば：

1. 最適価値関数$V^*(s)$が求まる：各状態の最大可能価値が分かる
2. 最適方策$\pi^*$が導出できる：$V^*$を使って最良の行動を選択
   
   $$\pi^*(s) = \arg\max_a \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V^*(s')\right]$$

学習アルゴリズムの基盤

ベルマン方程式は、実際に価値関数を学習するアルゴリズムの基礎となります。

反復による解法の考え方
ベルマン方程式を直接解くのは困難ですが、反復的に近似解を求めることができます：

1. 初期値の設定：適当な価値関数$V_0(s)$から開始
2. ベルマン方程式の適用：
   
   $$V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a)\left[R(s,a,s') + \gamma V_k(s')\right]$$
3. 収束まで反復：$V_k$が変化しなくなるまで続ける

この方法により、実際にコンピュータで最適価値関数を計算できます。

実際の学習への応用

経験からの学習
実際の環境では、状態遷移確率$P(s'|s,a)$や報酬関数$R(s,a,s')$が事前に分からないことがあります。しかし、ベルマン方程式の考え方は経験的な学習でも活用できます。

例えば、状態$s$で行動$a$を取って状態$s'$に遷移し、報酬$r$を得た経験があるとき：

• 理想的には：$Q^*(s,a) = r + \gamma \max_{a'} Q^*(s',a')$
• 実際の学習では：現在の推定値$Q(s,a)$をこの理想値に近づける

この考え方が、強化学習の多くの実用的アルゴリズムの基盤となっています。

マルコフ性との相性

ベルマン方程式が成立するのは、MDPのマルコフ性があるからです：

• 過去に依存しない：現在の状態さえ分かれば、最適な判断ができる
• 再帰的構造：同じ状態なら、時刻に関わらず同じ価値を持つ
• 部分問題への分解：大きな問題を小さな問題の組み合わせとして扱える

このように、ベルマン方程式はMDPの性質を活かして、複雑な強化学習問題を解決可能な形に変換する重要な道具なのです。

7. 具体例：グリッドワールドでベルマン方程式を動かす

4×4のグリッドワールドを例に、ベルマン方程式がどのように動作し、最適な価値関数と方策を導出するかを具体的に見てみましょう。

環境の設定

[S][ ][ ][ ]
[ ][ ][X][ ]
[ ][ ][ ][ ]
[ ][ ][ ][G]

• S: スタート地点（座標(0,0)）
• G: ゴール（座標(3,3)、報酬 +10）
• X: 障害物（座標(1,2)、侵入可能だが報酬 -10）
• 各ステップでの基本報酬: -1
• 行動：上下左右の移動（壁にぶつかると移動しない）

価値反復法による実装

import numpy as np

class GridWorld:
    def __init__(self):
        self.size = 4
        self.actions = ['up', 'down', 'left', 'right']
        self.action_effects = {
            'up': (-1, 0),
            'down': (1, 0), 
            'left': (0, -1),
            'right': (0, 1)
        }
        
        # 報酬の設定
        self.rewards = np.full((4, 4), -1.0)  # 基本報酬
        self.rewards[3, 3] = 10.0  # ゴール
        self.rewards[1, 2] = -10.0  # 障害物（侵入可能）
        
        # 終端状態の設定
        self.terminal_states = [(3, 3)]
        
    def get_next_state(self, state, action):
        """行動による次の状態を返す"""
        row, col = state
        d_row, d_col = self.action_effects[action]
        
        new_row = max(0, min(self.size - 1, row + d_row))
        new_col = max(0, min(self.size - 1, col + d_col))
        
        return (new_row, new_col)
    
    def get_reward(self, state, action, next_state):
        """報酬を返す"""
        return self.rewards[next_state[0], next_state[1]]

def value_iteration(grid_world, gamma=0.9, theta=1e-6):
    """価値反復法でベルマン最適方程式を解く"""
    
    # 価値関数の初期化
    V = np.zeros((grid_world.size, grid_world.size))
    
    # 終端状態の価値を0に設定（ゲーム終了後は価値なし）
    for terminal in grid_world.terminal_states:
        V[terminal[0], terminal[1]] = 0.0
    
    iteration = 0
    while True:
        delta = 0
        new_V = V.copy()
        
        # 各状態について価値を更新
        for row in range(grid_world.size):
            for col in range(grid_world.size):
                state = (row, col)
                
                # 終端状態はスキップ
                if state in grid_world.terminal_states:
                    continue
                
                # ベルマン最適方程式を適用
                action_values = []
                for action in grid_world.actions:
                    next_state = grid_world.get_next_state(state, action)
                    reward = grid_world.get_reward(state, action, next_state)
                    
                    # V*(s) = max_a [R(s,a,s') + γV*(s')]
                    value = reward + gamma * V[next_state[0], next_state[1]]
                    action_values.append(value)
                
                new_V[row, col] = max(action_values)
                delta = max(delta, abs(new_V[row, col] - V[row, col]))
        
        V = new_V
        iteration += 1
        
        print(f"反復 {iteration}:")
        print(f"価値関数の変化量: {delta:.6f}")
        print("現在の価値関数:")
        print(np.round(V, 2))
        print()
        
        # 収束判定
        if delta < theta:
            break
    
    return V

def extract_policy(grid_world, V, gamma=0.9):
    """最適価値関数から最適方策を導出"""
    
    policy = {}
    
    for row in range(grid_world.size):
        for col in range(grid_world.size):
            state = (row, col)
            
            if state in grid_world.terminal_states:
                continue
            
            best_action = None
            best_value = float('-inf')
            
            # 各行動の価値を計算（ベルマン方程式の右辺）
            for action in grid_world.actions:
                next_state = grid_world.get_next_state(state, action)
                reward = grid_world.get_reward(state, action, next_state)
                
                # π*(s) = argmax_a [R(s,a,s') + γV*(s')]
                action_value = reward + gamma * V[next_state[0], next_state[1]]
                
                if action_value > best_value:
                    best_value = action_value
                    best_action = action
            
            policy[state] = best_action
    
    return policy

def analyze_policy_extraction(grid_world, V, gamma=0.9):
    """方策導出過程の詳細分析"""
    print("\n=== 方策導出の詳細分析 ===")
    
    # 注目する状態での分析
    focus_states = [(0, 0), (1, 1), (2, 3)]
    
    for state in focus_states:
        row, col = state
        print(f"\n状態 {state} での行動価値計算:")
        print(f"現在のV({state}) = {V[row, col]:.2f}")
        
        action_values = {}
        for action in grid_world.actions:
            next_state = grid_world.get_next_state(state, action)
            reward = grid_world.get_reward(state, action, next_state)
            action_value = reward + gamma * V[next_state[0], next_state[1]]
            action_values[action] = action_value
            
            print(f"  {action:>5}: {next_state} → {reward:+4.1f} + 0.9×{V[next_state[0], next_state[1]]:5.2f} = {action_value:6.2f}")
        
        # 最適行動
        best_action = max(action_values, key=action_values.get)
        best_value = action_values[best_action]
        print(f"  → 最適行動: {best_action} (価値: {best_value:.2f})")
        
        # 整合性チェック
        if abs(best_value - V[row, col]) < 1e-10:
            print(f"  ✓ 整合性確認: max action value = V({state})")
        else:
            print(f"  ✗ 警告: max action value {best_value:.2f} ≠ V({state}) {V[row, col]:.2f}")

def compare_obstacle_strategies(grid_world, V, gamma=0.9):
    """障害物周辺での戦略分析"""
    print("\n=== 障害物回避戦略の分析 ===")
    
    # (1,1)からの行動選択
    state = (1, 1)
    row, col = state
    print(f"状態 {state} からの選択肢:")
    
    for action in grid_world.actions:
        next_state = grid_world.get_next_state(state, action)
        reward = grid_world.get_reward(state, action, next_state)
        action_value = reward + gamma * V[next_state[0], next_state[1]]
        
        if next_state == (1, 2):  # 障害物への移動
            print(f"  {action:>5}: 障害物へ → {action_value:6.2f} ⚠️")
        else:
            print(f"  {action:>5}: 安全ルート → {action_value:6.2f}")
    
    # V関数とQ関数的思考の比較
    print(f"\nV関数での思考:")
    print(f"- V(1,2) = {V[1,2]:.2f} (障害物セルの価値)")
    print(f"- 「障害物セルにいても、そこから最適に行動すれば価値がある」")
    
    print(f"\n行動価値での思考:")
    right_value = -10 + gamma * V[1,2]
    down_value = -1 + gamma * V[2,1] 
    print(f"- right(障害物へ): {right_value:.2f}")
    print(f"- down(安全): {down_value:.2f}")
    print(f"- 「障害物への移動は明確に悪い選択」")

# 実行例
if __name__ == "__main__":
    print("=== グリッドワールドでの価値反復法 ===")
    
    env = GridWorld()
    
    print("環境設定:")
    print("- 基本報酬: -1")
    print("- ゴール(3,3)報酬: +10") 
    print("- 障害物(1,2)報酬: -10")
    print("- 割引率γ: 0.9")
    print()
    
    # 価値反復法の実行
    optimal_V = value_iteration(env, gamma=0.9)
    
    # 最適方策の導出
    optimal_policy = extract_policy(env, optimal_V, gamma=0.9)
    
    print("=== 最終結果 ===")
    print("最適価値関数:")
    print(np.round(optimal_V, 2))
    print()
    
    print("最適方策:")
    policy_grid = np.full((4, 4), '  ', dtype='<U2')
    action_symbols = {'up': '↑', 'down': '↓', 'left': '←', 'right': '→'}
    
    for (row, col), action in optimal_policy.items():
        policy_grid[row, col] = action_symbols[action]
    
    policy_grid[0, 0] = 'S'  # スタート
    policy_grid[3, 3] = 'G'  # ゴール
    policy_grid[1, 2] = 'X'  # 障害物
    
    for row in policy_grid:
        print(' '.join(row))
    
    # 詳細分析
    analyze_policy_extraction(env, optimal_V)
    compare_obstacle_strategies(env, optimal_V)

実行結果

=== グリッドワールドでの価値反復法 ===
環境設定:
- 基本報酬: -1
- ゴール(3,3)報酬: +10
- 障害物(1,2)報酬: -10
- 割引率γ: 0.9

反復 1:
価値関数の変化量: 10.000000
現在の価値関数:
[[-1. -1. -1. -1.]
 [-1. -1. -1. -1.]
 [-1. -1. -1. 10.]
 [-1. -1. 10.  0.]]

反復 2:
価値関数の変化量: 9.000000
現在の価値関数:
[[-1.9 -1.9 -1.9 -1.9]
 [-1.9 -1.9 -1.9  8. ]
 [-1.9 -1.9  8.  10. ]
 [-1.9  8.  10.   0. ]]

... (数回の反復後) ...

反復 7:
価値関数の変化量: 0.000000

=== 最終結果 ===
最適価値関数:
[[ 1.81  3.12  4.58  6.2 ]
 [ 3.12  4.58  6.2   8.  ]
 [ 4.58  6.2   8.   10.  ]
 [ 6.2   8.   10.    0.  ]]

最適方策:
S ↓ → ↓
↓ ↓ X ↓
↓ ↓ ↓ ↓
→ → → G

=== 方策導出の詳細分析 ===

状態 (0, 0) での行動価値計算:
現在のV((0, 0)) = 1.81
     up: (0, 0) → -1.0 + 0.9× 1.81 =   0.63
   down: (1, 0) → -1.0 + 0.9× 3.12 =   1.81
   left: (0, 0) → -1.0 + 0.9× 1.81 =   0.63
  right: (0, 1) → -1.0 + 0.9× 3.12 =   1.81
  → 最適行動: down (価値: 1.81)
  ✓ 整合性確認: max action value = V((0, 0))

状態 (1, 1) での行動価値計算:
現在のV((1, 1)) = 4.58
     up: (0, 1) → -1.0 + 0.9× 3.12 =   1.81
   down: (2, 1) → -1.0 + 0.9× 6.20 =   4.58
   left: (1, 0) → -1.0 + 0.9× 3.12 =   1.81
  right: (1, 2) → -10.0 + 0.9× 6.20 =  -4.42
  → 最適行動: down (価値: 4.58)
  ✓ 整合性確認: max action value = V((1, 1))

状態 (2, 3) での行動価値計算:
現在のV((2, 3)) = 10.00
     up: (1, 3) → -1.0 + 0.9× 8.00 =   6.20
   down: (3, 3) → +10.0 + 0.9× 0.00 =  10.00
   left: (2, 2) → -1.0 + 0.9× 8.00 =   6.20
  right: (2, 3) → -1.0 + 0.9×10.00 =   8.00
  → 最適行動: down (価値: 10.00)
  ✓ 整合性確認: max action value = V((2, 3))

=== 障害物回避戦略の分析 ===
状態 (1, 1) からの選択肢:
     up: 安全ルート →   1.81
   down: 安全ルート →   4.58
   left: 安全ルート →   1.81
  right: 障害物へ →  -4.42 ⚠️

V関数での思考:
- V(1,2) = 6.20 (障害物セルの価値)
- 「障害物セルにいても、そこから最適に行動すれば価値がある」

行動価値での思考:
- right(障害物へ): -4.42
- down(安全): 4.58
- 「障害物への移動は明確に悪い選択」

ベルマン方程式の動作原理

1. 価値の伝播過程
価値反復の過程で、ゴールからの価値が周囲に段階的に伝播していく様子が確認できます：

• 初期：ゴール(3,3)のみが価値10を持つ
• 反復1：ゴール隣接セルが価値を獲得
• 反復7：全体に価値が伝播し収束

2. 最適方策の導出
各状態で数式 $\pi^*(s) = \arg\max_a [R(s,a,s') + \gamma V^*(s')]$ を適用：

• 状態(1,1)では4つの行動を評価
• 障害物への移動(right)は-4.42と明確に低い価値
• 安全な移動(down)が4.58で最適と判定

行動価値行列の構築
方策導出において、各状態$s$で行動$a$を取る価値 $R(s,a,s') + \gamma V^*(s')$ を行列として整理すると：

行動価値行列 Q(s,a) = R(s,a,s') + γV*(s'):

     up   down  left  right
(0,0) 0.63  1.81  0.63  1.81  ← 最適: down/right
(0,1) 1.81  3.12  0.63  3.12  ← 最適: down/right  
(0,2) 3.12  3.12  1.81  4.58  ← 最適: right
(1,1) 1.81  4.58  1.81 -4.42  ← 最適: down
(2,3) 6.20 10.00  6.20  8.00  ← 最適: down (ゴールへ)

この行列により、V*関数から最適方策 $\pi^*(s) = \arg\max_a Q(s,a)$ を導出可能。

3. V関数と行動価値の関係
重要な洞察：

• V(1,2) = 6.2: 障害物セルにいる場合の最適価値
• Q(1,1, right) = -4.42: 障害物セルへ移動する行動の価値
• 障害物への移動は-10の報酬ペナルティを受ける
• V関数だけでは行動選択が困難だが、ベルマン方程式の右辺を計算することで正しい行動選択が可能

4. 理論と実装の一致
方策導出の詳細分析により、実装が数学的理論と完全に一致していることが確認できます：

• 各行動価値の計算過程が透明
• V関数との整合性が保たれている
• ベルマン最適方程式の理論通りに動作

この例により、ベルマン方程式が単なる数学的定理ではなく、実際に動作する強力なアルゴリズムの基盤であることが具体的に理解できます。

まとめ

強化学習の基礎フレームワークでは：

1. MDPによって問題を数学的に定式化
2. 価値関数によって状態や行動の良さを定量化
3. 方策によって行動選択戦略を表現
4. ベルマン方程式によって価値関数の関係性を記述

この記事で学んだこと

本記事では、強化学習の基礎的な枠組みを体系的に学びました：

1. マルコフ決定過程（MDP） による問題の定式化
2. 価値関数 の概念と、状態価値関数V(s)・行動価値関数Q(s,a)の違い
3. ベルマン方程式 による価値関数の再帰的関係の記述
4. 価値反復法 による最適価値関数の計算
5. グリッドワールド での具体的な実装と動作確認

特に重要な実装上の知見：

• 終端状態の価値は0に設定（ゲーム終了後の価値なし）
• 報酬設計が学習結果に与える影響の大きさ
• V関数から最適方策を導出する際の計算：$\pi^*(s) = \arg\max_a [R(s,a,s') + \gamma V^*(s')]$

次に学ぶべきトピック

本記事では環境の状態遷移確率Pが既知の場合を扱いましたが、実際の問題では環境について完全な知識がない場合がほとんどです。次のステップとして、以下のような手法を学ぶことをお勧めします：

• モンテカルロ法：実際の経験から価値関数を推定
• TD学習：Q学習やSARSAなど、経験から逐次的に学習
• Eligibility Traces：TD(λ)による効率的な学習
• 関数近似：大規模な状態空間への対応
• 方策勾配法：価値関数を介さない直接的な方策の最適化
• 深層強化学習：DQN、A3Cなどの現代的手法

これらの手法は、本記事で学んだベルマン方程式の考え方を基礎として発展したものです。強化学習の理論的な美しさと実用性を、さらに深く探求していくことができるでしょう。