強化学習の基礎：概要とマルコフ決定過程

強化学習の基本概念を解説。MDPの構成要素からベルマン方程式の導出、価値反復法・方策反復法をPythonで実装したグリッドワールド実験、割引率γの役割まで、教科書レベルで解説します。

12 min read

機械学習の用語整理

機械学習における「モデル」とは、データから学習する数式やアルゴリズムのことで、その内部には調整可能な「パラメータ」を持っています。これらのパラメータを、与えられたデータに基づいて最適化するプロセスを「学習」または「訓練」と呼びます。

代表的なモデルとして、人間の脳の神経回路を模倣した「ニューラルネットワーク (NN)」があり、これを多層化したものが「ディープニューラルネットワーク (DNN)」です。

学習の手法は大きく分けて以下の3つがあります。

  • 教師あり学習 (Supervised Learning)
  • 教師なし学習 (Unsupervised Learning)
  • 強化学習 (Reinforcement Learning)

強化学習の概要

強化学習は、教師あり学習や教師なし学習のようにデータセットが与えられるのではなく、「環境」が与えられる点が特徴です。

  • 環境: エージェント（学習主体）が行動し、その行動に応じて状態が変化し、特定の状態に到達したり特定の行動を取ったりした際に「報酬」が与えられる空間のことです。

強化学習では、エージェントが環境と相互作用しながら、より多くの報酬を獲得できるようにモデルのパラメータを調整します。環境の開始から終了までの一連の行動と状態の遷移を「1エピソード」と呼び、この1エピソードで得られる累積報酬を最大化することが学習の目的となります。

問題設定：マルコフ決定過程 (MDP)

強化学習の問題は、多くの場合、マルコフ決定過程 (Markov Decision Process, MDP) として定式化されます。MDPは、マルコフ性（次の状態が現在の状態と行動のみに依存し、過去の履歴には依存しない性質）を持つ意思決定過程です。

MDPの主要な構成要素は以下の4つです。

  • \(S\) : 状態 (State) の集合。エージェントが現在置かれている状況を表します。
  • \(A\) : 行動 (Action) の集合。エージェントが各状態で取りうる選択肢です。
  • \(T\) : 状態遷移確率 (Transition Probability)。現在の状態 \(s\) で行動 \(a\) を取ったときに、次の状態 \(s'\) へ遷移する確率 \(P(s'|s, a)\) を表します。
  • \(R\) : 報酬関数 (Reward Function)。ある状態 \(s\) で行動 \(a\) を取り、次の状態 \(s'\) に遷移したときに得られる報酬 \(R(s, a, s')\) を表します。

強化学習における「ロボット」や「AI」は、これらの状態を受け取り、最適な行動を出力する関数とみなすことができます。この関数を「方策 (Policy)」 \(\pi(a|s)\) と呼びます。エージェントは、報酬を最大化するように方策を更新していくことで、最適な方策の発見を目指します。

実は、MDPにはもう一つ重要な要素があります。それが割引率 (Discount Factor) \(\gamma \in [0,1]\) です。前述の通り学習の目的は累積報酬の最大化ですが、遠い将来の報酬をそのまま合計すると、無限に続くタスクでは合計が発散したり、「今すぐの報酬」と「10万ステップ先の報酬」を同列に扱ってしまったりする問題が生じます。\(\gamma\) は将来の報酬を現在価値に割り引くための係数で、これを含めると MDP は \((S, A, T, R, \gamma)\) の5つ組として定式化されます。\(\gamma\) の役割は本記事の後半で具体的な数値実験を通して確認します。

なお、\(T(s'|s,a)\) （遷移確率）と \(R(s,a,s')\) （報酬関数）を別々に持つ代わりに、次状態と報酬の同時分布 \(p(s',r \mid s,a) = \Pr(S_{t+1}=s', R_{t+1}=r \mid S_t=s, A_t=a)\) としてまとめて表記することもあります。こちらは報酬が確率的に変動する場合も扱える、より一般的な書き方で、Sutton & Barto の教科書 Reinforcement Learning: An Introduction をはじめ多くの文献で採用されています。以降の導出ではこの \(p(s',r|s,a)\) 表記を使いますが、報酬が \((s,a,s')\) の決定的な関数である場合は \(p(s',r|s,a) = T(s'|s,a)\) （\(r=R(s,a,s')\) のときのみ）に一致します。

価値関数とベルマン期待方程式

強化学習の目的は累積報酬の最大化でしたが、これを数式で正確に扱うために、時刻 \(t\) 以降に得られる割引累積報酬（収益, Return） \(G_t\) を次のように定義します。

\[ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \]

この定義から、\(G_t\) は1つ先の収益 \(G_{t+1}\) を使って再帰的に書けることがすぐにわかります。

\[ G_t = R_{t+1} + \gamma \underbrace{(R_{t+2} + \gamma R_{t+3} + \cdots)}_{=\,G_{t+1}} = R_{t+1} + \gamma G_{t+1} \tag{1} \]

環境の遷移は確率的なので、収益 \(G_t\) も確率変数です。そこで方策 \(\pi\) の下での状態価値関数 (State-Value Function) を、収益の期待値として定義します。

\[ V^\pi(s) = \mathbb{E}_\pi\left[\, G_t \mid S_t = s \,\right] = \mathbb{E}_\pi\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \,\middle|\, S_t = s\right] \]

この \(V^\pi(s)\) を、\(G_t\) ではなく「その先の価値」を使って再帰的に表したものがベルマン期待方程式 (Bellman Expectation Equation) です。式(1)を代入して展開します。

\[ V^\pi(s) = \mathbb{E}_\pi\left[ R_{t+1} + \gamma G_{t+1} \mid S_t = s \right] \]

ここで期待値を、方策 \(\pi(a|s)\) に従って選ばれる行動 \(a\) と、遷移先の状態・報酬の同時分布 \(p(s',r|s,a)\) に従って生じる \((s', r)\) について分解します。

\[ V^\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \Big[\, r + \gamma\, \mathbb{E}_\pi\big[G_{t+1} \mid S_{t+1}=s'\big] \Big] \]

ここでマルコフ性が本質的に使われています。\(G_{t+1}\) は時刻 \(t+1\) 以降の遷移だけで決まるため、\(S_{t+1}=s'\) が与えられれば、それ以前の \(S_t=s\) や \(A_t=a\) の情報は不要になります。つまり

\[ \mathbb{E}_\pi\big[G_{t+1} \mid S_{t+1}=s', S_t=s, A_t=a\big] = \mathbb{E}_\pi\big[G_{t+1} \mid S_{t+1}=s'\big] = V^\pi(s') \]

が成り立ちます。これを代入すれば、ベルマン期待方程式が得られます。

\[ \boxed{\, V^\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \big[\, r + \gamma V^\pi(s') \,\big] \,} \tag{2} \]

同様に、状態 \(s\) で行動 \(a\) を取った場合の価値を表す行動価値関数 (Action-Value Function) \(Q^\pi(s,a) = \mathbb{E}_\pi[G_t \mid S_t=s, A_t=a]\) も、全く同じ手順（式(1)の代入 → マルコフ性による条件付き期待値の簡略化）で導出できます。

\[ Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a) \big[\, r + \gamma\, \mathbb{E}_\pi[G_{t+1}\mid S_{t+1}=s'] \,\big] = \sum_{s',r} p(s',r|s,a) \big[\, r + \gamma V^\pi(s') \,\big] \tag{3} \]

さらに、\(V^\pi(s)\) は「\(s\) から方策 \(\pi\) に従って行動したときの期待収益」なので、行動 \(a \sim \pi(\cdot|s)\) について \(Q^\pi\) の期待値を取るだけで書けます。

\[ V^\pi(s) = \sum_a \pi(a|s)\, Q^\pi(s,a) \tag{4} \]

式(3)・式(4)を組み合わせると、式(2)が再び得られることも確認できます。\(V^\pi\) と \(Q^\pi\) は互いに他方から再構成できる、表裏一体の量です。

ベルマン最適方程式

強化学習の目標は、あらゆる状態 \(s\) で \(V^\pi(s)\) を最大にする最適方策 \(\pi^*\) を見つけることです。最適方策の下での価値関数を、それぞれ最適状態価値関数 \(V^*(s) = \max_\pi V^\pi(s)\) 、最適行動価値関数 \(Q^*(s,a) = \max_\pi Q^\pi(s,a)\) と呼びます。

ここでベルマンの最適性原理 (Bellman’s Principle of Optimality) を使います。「最適方策に従うなら、最初の1手をどう選んでも、その後の意思決定は残りの部分問題に対して最適でなければならない」という考え方です。これはつまり、状態 \(s\) で行動 \(a\) を取った後は、必ず最適方策に従い続けるのが最善であることを意味します。したがって

\[ Q^*(s,a) = \sum_{s',r} p(s',r|s,a) \big[\, r + \gamma V^*(s') \,\big] \tag{5} \]

が成り立ちます（式(3)の \(V^\pi\) を \(V^*\) に置き換えただけです）。さらに、最適方策は各状態で \(Q^*(s,a)\) を最大にする行動を貪欲に選べばよいので、

\[ V^*(s) = \max_a Q^*(s,a) \]

が成り立ちます。式(5)を代入すると、ベルマン最適方程式 (Bellman Optimality Equation) が得られます。

\[ \boxed{\, V^*(s) = \max_a \sum_{s',r} p(s',r|s,a) \big[\, r + \gamma V^*(s') \,\big] \,} \tag{6} \]

式(2)の期待方程式との違いは、方策 \(\pi(a|s)\) による重み付き平均 \(\sum_a \pi(a|s)(\cdots)\) が、\(\max_a(\cdots)\) に置き換わっている点だけです。この一点が非常に重要で、\(V^*\) さえ計算できれば、最適方策は

\[ \pi^*(s) = \arg\max_a Q^*(s,a) = \arg\max_a \sum_{s',r} p(s',r|s,a) \big[\, r + \gamma V^*(s') \,\big] \]

という**貪欲方策（greedy policy）**として直接得られます。つまりベルマン最適方程式は、「全状態で同時に成り立つ\(|S|\) 本の連立方程式」であると同時に、\(\gamma < 1\) かつ報酬が有界であれば縮小写像（contraction mapping）となり唯一の解 \(V^*\) を持つことが保証されています。次節では、この性質を使って \(V^*\) を反復的に計算する2つのアルゴリズムを実装します。

動的計画法で解く：グリッドワールド実験

理論を具体的に確認するために、環境モデル \(p(s',r|s,a)\) が完全に既知な5x5グリッドワールドを用意し、価値反復法 (Value Iteration) と 方策反復法 (Policy Iteration) の両方をPythonで実装・実行します。

行/列    0     1     2     3     4
 0     .     .     .     .    G2(+10)
 1     .    WALL   .     .     .
 2     .     .   TRAP(-10) .   .
 3     .     .     .     .     .
 4    START  G1(+5) .    .     .
  • 各セルが状態 \(s\) 、行動は上下左右4方向（決定的に遷移し、壁や盤外にぶつかると同じマスに留まる）
  • 通常のマスへの移動は報酬 \(-1\) （生存コスト）
  • ゴール G1（近い・小さい報酬 \(+5\) ）と G2（遠い・大きい報酬 \(+10\) ）、および TRAP（\(-10\) ）は到達すると即座にエピソード終了する吸収状態（\(V=0\) で固定）
  • WALL は通行不可の障害物

この設定はまさに \(p(s',r|s,a)\) が決定的な分布（確率1でただ1つの \((s',r)\) が生じる）になる特殊ケースで、式(2)・式(6)の和がそのまま1項に潰れるため、導出した式を素直にコードへ落とし込めます。

GRID_H, GRID_W = 5, 5
G1, G2, TRAP, WALL = (4, 1), (0, 4), (2, 2), (1, 1)
TERMINALS = {G1, G2, TRAP}
REWARD = {G1: 5.0, G2: 10.0, TRAP: -10.0}
STEP_COST = -1.0
ACTIONS = ['up', 'down', 'left', 'right']
DELTA = {'up': (-1, 0), 'down': (1, 0), 'left': (0, -1), 'right': (0, 1)}

states = [(r, c) for r in range(GRID_H) for c in range(GRID_W) if (r, c) != WALL]
nonterminal_states = [s for s in states if s not in TERMINALS]

def step(s, a):
    dr, dc = DELTA[a]
    nr, nc = s[0] + dr, s[1] + dc
    if not (0 <= nr < GRID_H and 0 <= nc < GRID_W) or (nr, nc) == WALL:
        nr, nc = s  # 壁・盤外にぶつかると停止
    ns = (nr, nc)
    r = REWARD.get(ns, STEP_COST)
    return ns, r

def q_value(s, a, V, gamma):
    ns, r = step(s, a)
    v_ns = 0.0 if ns in TERMINALS else V[ns]
    return r + gamma * v_ns

価値反復法 (Value Iteration)

式(6)をそのまま更新式として使います。

\[ V_{k+1}(s) \leftarrow \max_a \sum_{s',r} p(s',r|s,a) \big[\, r + \gamma V_k(s') \,\big] \]
def value_iteration(gamma, theta=1e-8, max_iter=10000):
    V = {s: 0.0 for s in states}
    deltas = []
    for it in range(1, max_iter + 1):
        delta = 0.0
        newV = dict(V)
        for s in nonterminal_states:
            newV[s] = max(q_value(s, a, V, gamma) for a in ACTIONS)
            delta = max(delta, abs(newV[s] - V[s]))
        V = newV
        deltas.append(delta)
        if delta < theta:
            break
    policy = {s: max(ACTIONS, key=lambda a: q_value(s, a, V, gamma))
              for s in nonterminal_states}
    return V, policy, it, deltas

\(\gamma=0.9\) 、収束判定 \(\theta=10^{-8}\) （\(\max_s |V_{k+1}(s)-V_k(s)| < \theta\) ）で実行すると、次の結果が得られました。

Value Iteration: converged in 6 sweeps
delta per sweep: [10.0, 9.0, 8.1, 7.29, 2.187, 0.0]

6回のスイープで厳密収束（差分がちょうど0）に達しました。差分が幾何級数的（各ステップでおよそ \(\times \gamma\) ）に減っていく様子は、ベルマン作用素が縮小写像であることの直接的な現れです。

方策反復法 (Policy Iteration)

方策反復法は、方策評価（式(2)を固定方策の下で不動点まで反復）と方策改善（\(Q^\pi\) に関する貪欲化）を交互に繰り返します。

def policy_evaluation(policy, gamma, theta=1e-8, max_iter=10000):
    V = {s: 0.0 for s in states}
    for sweep in range(1, max_iter + 1):
        delta = 0.0
        newV = dict(V)
        for s in nonterminal_states:
            newV[s] = q_value(s, policy[s], V, gamma)
            delta = max(delta, abs(newV[s] - V[s]))
        V = newV
        if delta < theta:
            break
    return V, sweep

def policy_iteration(gamma, theta=1e-8):
    policy = {s: 'right' for s in nonterminal_states}  # 初期方策（全マス「右」）
    total_eval_sweeps, improve_iters = 0, 0
    while True:
        V, sweeps = policy_evaluation(policy, gamma, theta)
        total_eval_sweeps += sweeps
        improve_iters += 1
        new_policy, stable = {}, True
        for s in nonterminal_states:
            best_a = max(ACTIONS, key=lambda a: q_value(s, a, V, gamma))
            new_policy[s] = best_a
            if best_a != policy[s]:
                stable = False
        policy = new_policy
        if stable:
            return V, policy, improve_iters, total_eval_sweeps

同じ \(\gamma=0.9\) 、初期方策「全マス右」で実行した結果は次の通りです。

Policy Iteration: 3 回の方策改善で収束
方策評価の内訳（スイープ数）: [176, 7, 6]  (合計 189 スイープ)

方策改善のステップ数はわずか3回で済んでいますが、内訳を見ると1回目の方策評価だけで176スイープを要しています。これは初期方策「全マス右」の下では、盤面右端に何度もぶつかって \(-1\) を延々と受け取り続ける（吸収状態に到達しない）状態が存在し、その価値 \(V^\pi(s) \approx -1/(1-\gamma) = -10\) に収束するまでに \(\gamma=0.9\) の縮小率でおよそ\(176\) 回の反復が必要になるためです。方策改善後の2回目・3回目は、どの状態も高々8ステップ程度で終端に到達する「筋の良い」方策になっているため、7回・6回と急速に収束します。

Value IterationとPolicy Iterationの収束曲線比較

この結果は、価値反復法と方策反復法の典型的なトレードオフをそのまま示しています。価値反復法は1回の更新は軽い（各状態で \(\max\) を取るだけ）ものの、\(V^*\) に収束するまでスイープを繰り返す必要があります（6スイープ）。方策反復法は方策改善のステップ数自体は少ない（3回）ものの、各改善ステップの中で方策評価を収束まで解く必要があり、総計算量（189スイープ）は今回のケースでは価値反復法より大きくなりました。どちらが有利かは問題設定（状態数、初期方策の質、方策評価の打ち切り基準など）に依存します。

相互検証：同じ最適解に収束するか

2つの独立したアルゴリズムが同じ答えに辿り着くことを確認します。

V_vi, pi_vi, _, _ = value_iteration(0.9)
V_pi, pi_pi, _, _ = policy_iteration(0.9)

max_diff = max(abs(V_vi[s] - V_pi[s]) for s in nonterminal_states)
policy_match = all(pi_vi[s] == pi_pi[s] for s in nonterminal_states)
print(max_diff, policy_match)
# => 0.0  True

最大差分は厳密に0.0、全21状態で最適方策も完全一致しました。価値反復法と方策反復法はアルゴリズムとしては全く異なる手続きですが、どちらもベルマン最適方程式(6)という同一の不動点方程式を解いているため、収束すれば同じ \(V^*\) ・\(\pi^*\) に辿り着くことが理論的に保証されており、今回の実験でもそれが数値的に確認できました。

収束した \(V^*(s)\) をヒートマップとして可視化すると、ゴールに近いほど価値が高く、トラップに近いほど価値が低くなる様子が一目でわかります。

グリッドワールドの最適価値関数V*(s)のヒートマップ

割引率 γ の役割：近い報酬か、遠い報酬か

\(\gamma\) が「エージェントがどれだけ将来を気にするか」を制御することを、具体的な数値で確認します。このグリッドワールドには意図的に、近くて小さい報酬 G1（\(+5\) 、スタートから1マス） と 遠くて大きい報酬 G2（\(+10\) 、マンハッタン距離8マス） を両方配置してあります。\(\gamma\) を \(0.5\) 、\(0.9\) 、\(0.99\) と変えて価値反復法を実行し、各状態の最適方策がどちらのゴールに向かうかを集計しました。

def terminal_reached(policy, s, max_steps=100):
    cur = s
    for _ in range(max_steps):
        if cur in TERMINALS:
            return cur
        cur, _ = step(cur, policy[cur])
    return None

for g in [0.5, 0.9, 0.99]:
    _, pi_g, _, _ = value_iteration(g)
    c1 = sum(terminal_reached(pi_g, s) == G1 for s in nonterminal_states)
    c2 = sum(terminal_reached(pi_g, s) == G2 for s in nonterminal_states)
    print(f"gamma={g}: G1へ向かう状態={c1}, G2へ向かう状態={c2}")

gamma=0.5:  G1へ向かう状態=11, G2へ向かう状態=10
gamma=0.9:  G1へ向かう状態=8,  G2へ向かう状態=13
gamma=0.99: G1へ向かう状態=5,  G2へ向かう状態=16

21状態のうち、遠くの大きい報酬 G2 を選ぶ状態数が 10 → 13 → 16 と、\(\gamma\) を大きくするほど単調に増えていくことがわかります。\(\gamma\) が小さい（近視眼的な）エージェントは目先の G1 に飛びつきやすく、\(\gamma\) が1に近い（将来を重視する）エージェントは遠回りしてでも大きい G2 を狙うようになります。

割引率γによる近い報酬と遠い報酬の選択比率の変化

1つの状態に注目すると、この切り替わりがより具体的に見えます。壁の左下、状態 \((1,0)\) での最適価値と最適行動は次のように変化します。

\(\gamma\)\(V^*((1,0))\)最適行動行き先
0.5\(-1.125\)down（下）近い G1 へ
0.9\(3.122\)up（上）遠い G2 へ
0.99\(5.666\)up（上）遠い G2 へ

\(\gamma=0.5\) では G1 に向かう経路の価値の方が高いため最適行動は「下」ですが、\(\gamma=0.9\) 以上では G2 に向かう経路の割引後価値が逆転し、最適行動が「上」に切り替わります。同じ環境・同じ報酬設計でも、\(\gamma\) という1つのハイパーパラメータを変えるだけで最適方策そのものが変わりうることが、この実験から確認できます。

モデルフリー強化学習へ

ここまでの価値反復法・方策反復法は、いずれも遷移確率と報酬の同時分布 \(p(s',r|s,a)\) が既知であることを前提とした動的計画法でした。しかし実際の多くの問題では、この環境モデルは未知です。次の記事では、モデルを持たずにエージェントの実際の経験（状態・行動・報酬の系列）だけから \(Q\) を推定していく Q学習や SARSA などのモデルフリー強化学習を扱います。

関連記事

参考

この記事に関連する無料ツール

DevToolBox Moving Average Calculator SMA/EMA/WMA をブラウザで即座に計算 DevToolBox JSON Formatter JSONを整形・圧縮・バリデーション DevToolBox Regex Tester 正規表現をリアルタイムテスト

関連記事