強化学習その3: 2.2 From MDP to Learning

この記事は articles/reinforce-finance.pdf の Section 2.2: From MDP to Learning を、前提なしで読めるように整理したメモです。

1. 何が「Learning」なのか

Section 2.1 では MDP の遷移 $P$ と報酬 $r$ が既知である前提でした。
Section 2.2 の出発点は、 $P,r$ が未知という現実的な設定です。

このとき目標は:

\text{未知の }P,r\text{ のもとで、最適方策 }\pi^*\text{（またはそれに近い方策）を学習する}

です。

2. Agent-Environment Interface

時刻 $t$ で

エージェントが状態 $s_t$ を観測
行動 $a_t$ を選択
環境から報酬 $r_t$ と次状態 $s_{t+1}$ を受け取る

というループを繰り返します。

1ステップの観測は

(s_t,a_t,r_t,s_{t+1})

で、履歴（experience）は

h_t=\{(s_u,a_u,r_u,s_{u+1})\}_{u=0}^{t}

です。

3. Exploration と Exploitation

Exploitation: 現在わかっている「良い行動」を選ぶ
Exploration: 未知の行動を試して情報を増やす

探索が弱すぎると局所最適に留まり、探索が強すぎると学習が遅くなるため、2つのバランスが中心課題になります。

4. オンライン相互作用と Simulator（Generative Model）

通常はオンライン設定で、 $t+1$ の初期状態は実際の遷移結果 $s_{t+1}$ です。
一方、Simulator（Generative Model）にアクセスできる設定では、任意の $(s,a)$ をクエリしてサンプルを得られます。

これは

\text{探索の自由度を上げて、理論的サンプル効率を改善しやすくする}

という意味を持ちます。

5. 2.2.1 Performance Evaluation

Section 2.2.1 の要点は、RLアルゴリズムの性能評価指標を揃えることです。

5.1 Sample Complexity（エピソード型）

有限ホライズン（エピソード長 $T$ ）で、各エピソード後に方策 $\pi_k$ を返すとき、
ある $K$ 以降で

\mathbb{P}\!\left(V_0^{\pi_k}\ge V_0^*-\varepsilon\right)\ge 1-\delta,\qquad k\ge K

を満たす最小サンプル数を Sample Complexity とみなします（式 (2.15) の趣旨）。

5.2 Discounted 設定での Q/V Sample Complexity

割引無限ホライズンでは、 $Q$ と $V$ の誤差で評価することが多いです。

\|Q^{(n)}-Q^*\|_\infty \coloneqq \sup_{s\in S,a\in A}|Q^{(n)}(s,a)-Q^*(s,a)| \le \varepsilon

\|V^{(n)}-V^*\|_\infty \coloneqq \sup_{s\in S}|V^{(n)}(s)-V^*(s)| \le \varepsilon

（式 (2.16), (2.17) の整理）。

5.3 Sample Complexity of Exploration

「現在状態 $s_n$ で方策 $\pi_n$ がどれだけ最適に近いか」を直接見る指標:

\mathbb{P}\!\left(|V^{\pi_n}(s_n)-V^*(s_n)|\le \varepsilon\right)\ge 1-\delta,\qquad n\ge N

（式 (2.18)）。

5.4 Mean-square Sample Complexity

状態分布 $\mu$ に関する平均二乗誤差:

\|V^{\pi_n}-V^*\|_{\mu} \coloneqq \left( \int_S (V^{\pi_n}(s)-V^*(s))^2\,\mu(ds) \right)^{1/2} \le \varepsilon

（式 (2.19)）。

5.5 Rate of Convergence

$N$ ステップで誤差 $\varepsilon$ を達成する関係で速度を定義します。典型例:

線形収束: $N=\tilde O(\log(1/\varepsilon))$
劣線形収束: $N=\tilde O(1/\varepsilon^p)$ （ $p\ge1$ ）

5.6 Regret（主にエピソード型）

エピソード型では、最適方策との差を累積した

\mathcal{R}(M)=K\,V_0^*-\sum_{k=1}^K \mathbb{E}[V_0^{\pi_k}]

を使います（式 (2.20) の形）。
無限ホライズン割引では累積割引報酬が有界なので、同じ形の regret は解釈が難しい点に注意です。

6. 2.2.2 RLアルゴリズムの分類

Section 2.2.2 の分類は次です。

Model-based RL
遷移 $P$ と報酬 $r$ を推定し、計画（planning）で方策を改善する
Model-free RL
$P,r$ の明示推定なしで直接学習する
Value-based（Model-free の一種）
$V,Q$ を学習して方策を暗黙的に導く
Policy-based（Model-free の一種）
方策そのものをパラメータ化して学習する

この分類が、次節 2.3（Value-based）と 2.4（Policy-based）の入り口になります。

7. 金融応用での読み替え

最適執行: 有限ホライズン・強い制約・オンライン探索が難しい
ポートフォリオ: 非定常環境で評価分布 $\mu$ の選び方が重要
ヘッジ: サンプル効率とリスク制約を同時に見る必要がある

そのため、Section 2.2 の評価指標（Sample Complexity / Regret / MSE）は、金融タスクで「何を良い学習とみなすか」を定義する土台になります。

Python実装ミニ例（評価指標の計算）

未知環境で学習誤差が減っていく状況を模擬し、Section 2.2 の指標を計算する最小例です。

import numpy as np

rng = np.random.default_rng(42)
T = 2000
n = np.arange(1, T + 1)

# 学習ギャップ |V^{pi_n}(s_n)-V*(s_n)| のトイデータ
gap = 0.8 * np.exp(-n / 350.0) + 0.02 + rng.normal(0.0, 0.02, size=T)
gap = np.clip(gap, 0.0, None)

eps = 0.05
delta = 0.05

# sample complexity: 初めて eps 以下になった時刻
idx = np.where(gap <= eps)[0]
N_eps = int(idx[0] + 1) if idx.size else None

# high-probability 条件の近似: 移動窓で P(gap <= eps) を推定
window = 200
ok = (gap <= eps).astype(float)
p_hat = np.convolve(ok, np.ones(window) / window, mode="valid")
idx_prob = np.where(p_hat >= 1.0 - delta)[0]
N_prob = int(idx_prob[0] + window) if idx_prob.size else None

# mean-square 指標
rmse = float(np.sqrt(np.mean(gap**2)))

# regret のトイ計算
regret = np.cumsum(gap)

print("N_eps =", N_eps)
print("N_prob =", N_prob)
print("RMSE =", rmse)
print("Regret(T) =", float(regret[-1]))

参考

Ben Hambly, Renyuan Xu, Huining Yang, Recent Advances in Reinforcement Learning in Finance, 2023.
元メモ: articles/reinforce-finance.pdf
MIT 6.390 notes: Markov Decision Processes