強化学習その2: 2.1 Setup: Markov Decision Processes

この記事では articles/reinforce-finance.pdf の 2.1 Setup: Markov Decision Processes にある式を、導出過程が追えるように整理します。

MDPの全体像を先に掴みたい場合は、MIT 6.390 notes: Markov Decision Processes が短くまとまっていて読みやすいです。

全体像（1枚図）

読むときは、まず Section 1-3 でベルマン方程式の核を押さえ、次に Section 6 で線形近似とDeep RLへの接続を見ると流れが追いやすいです。

0. 設定と記号

状態空間: $S$
行動空間: $A$
割引率: $\gamma\in(0,1)$
遷移カーネル: $P(\cdot\mid s,a)$
報酬（確率変数）: $r(s,a)$
方策: $\Pi=\{\pi_t\}_{t\ge0}$ （時刻依存も許す）

状態遷移は

s_{t+1}\sim P(\cdot\mid s_t,a_t),\qquad a_t\sim \pi_t(\cdot\mid s_t)

で与えます。

1. 無限ホライズン割引MDPの目的関数

1.1 方策 $\Pi$ の価値関数

時刻 $0$ に状態 $s_0=s$ から始めたとき、方策 $\Pi$ の価値関数を

V^{\Pi}(s) \coloneqq \mathbb{E}^{\Pi}\!\left[ \sum_{t=0}^{\infty}\gamma^t r(s_t,a_t) \;\middle|\; s_0=s \right]

と定義します。

1.2 最適価値関数（式 (2.1)）

最適価値関数は全方策で上限を取って

V^*(s) = \sup_{\Pi}V^{\Pi}(s) = \sup_{\Pi} \mathbb{E}^{\Pi}\!\left[ \sum_{t=0}^{\infty}\gamma^t r(s_t,a_t) \;\middle|\; s_0=s \right]

となります。これが Section 2.1 の式 (2.1) に対応します。

2. ベルマン方程式（無限ホライズン）

2.1 1ステップ先で分解

任意の方策 $\Pi$ に対して

\sum_{t=0}^{\infty}\gamma^t r(s_t,a_t) = r(s_0,a_0)+\gamma\sum_{t=1}^{\infty}\gamma^{t-1}r(s_t,a_t)

なので

V^{\Pi}(s) = \mathbb{E}^{\Pi}\!\left[r(s_0,a_0)+\gamma V^{\Pi}(s_1)\mid s_0=s\right].

ここで期待値を「最初の行動 $a$ と次状態 $s'$ 」で展開すると

V^{\Pi}(s) = \mathbb{E}_{a\sim \pi_0(\cdot\mid s)} \left[ \mathbb{E}[r(s,a)] +\gamma\, \mathbb{E}_{s'\sim P(\cdot\mid s,a)}[V^{\Pi^+}(s')] \right]

（ $\Pi^+$ は1期先以降の方策列）。

2.2 最適化して式 (2.3)

最適方策では「今の1手を最適化し、次状態以降も最適化」する（DPP）ので

V^*(s)= \sup_{a\in A} \left\{ \mathbb{E}[r(s,a)] +\gamma\, \mathbb{E}_{s'\sim P(\cdot\mid s,a)}[V^*(s')] \right\}.

これが式 (2.3) です。

Bellman方程式の背景（動的計画法）の講義ノートとしては、MIT OCW Lecture 1 が導入、Lecture 2 が価値反復の見通し、Lecture 3 が政策反復との関係整理に対応します。

3. $Q^*$ の定義とベルマン方程式

3.1 $Q^*$ の定義（式 (2.4)）

状態 $s$ でまず行動 $a$ を固定し、その後最適に行動するときの価値を

Q^*(s,a) \coloneqq \mathbb{E}[r(s,a)] +\gamma\, \mathbb{E}_{s'\sim P(\cdot\mid s,a)}[V^*(s')]

と定義します（式 (2.4)）。

また

V^*(s)=\sup_{a\in A}Q^*(s,a)

が成り立ちます。

3.2 $Q^*$ のベルマン最適方程式（式 (2.5)）

$V^*(s')=\sup_{a'}Q^*(s',a')$ を上式に代入すると

Q^*(s,a) = \mathbb{E}[r(s,a)] +\gamma\, \mathbb{E}_{s'\sim P(\cdot\mid s,a)} \left[ \sup_{a'\in A}Q^*(s',a') \right]

となり、これが式 (2.5) です。

4. 有限ホライズンMDPの導出

金融の短期執行問題のように「満期 $T$ 」がある場合は有限ホライズンで書きます。

4.1 目的関数（式 (2.6), (2.7)）

V_t^{\Pi}(s) \coloneqq \mathbb{E}^{\Pi}\!\left[ \sum_{u=t}^{T-1}r_u(s_u,a_u)+r_T(s_T) \;\middle|\; s_t=s \right]

最適価値は

V_t^*(s)=\sup_{\Pi}V_t^{\Pi}(s)

で、遷移は時刻依存で

s_{u+1}\sim P_u(\cdot\mid s_u,a_u),\qquad a_u\sim \pi_u(\cdot\mid s_u),\quad t\le u\le T-1.

4.2 ベルマン方程式（式 (2.8)）

1ステップ分離により

V_t^*(s) = \sup_{a\in A} \Big\{ \mathbb{E}[r_t(s,a)] +\mathbb{E}_{s'\sim P_t(\cdot\mid s,a)}[V_{t+1}^*(s')] \Big\}

終端条件は

V_T^*(s)=\mathbb{E}[r_T(s)].

4.3 有限ホライズンの $Q_t^*$ （式 (2.9), (2.10)）

Q_t^*(s,a) \coloneqq \mathbb{E}[r_t(s,a)] +\mathbb{E}_{s'\sim P_t(\cdot\mid s,a)}[V_{t+1}^*(s')]

より

V_t^*(s)=\sup_{a\in A}Q_t^*(s,a),

さらに代入して

Q_t^*(s,a)= \mathbb{E}[r_t(s,a)] +\mathbb{E}_{s'\sim P_t(\cdot\mid s,a)} \left[ \sup_{a'}Q_{t+1}^*(s',a') \right]

終端条件は

Q_T^*(s,a)=\mathbb{E}[r_T(s)].

5. 2.1 の残り: 方策クラスと理論的補足

5.1 決定論的方策と確率的方策

Section 2.1 では方策を次の2種類で整理しています。

決定論的方策: $\pi_t:S\to A$
確率的方策: $\pi_t:S\to\mathcal{P}(A)$

確率的方策は探索（exploration）を自然に組み込めるため、実装上よく使われます。
一方、最適性の理論では「最適方策が決定論的に取れる」条件が重要になります。

5.2 定常最適方策の存在（Theorem 2.1 の位置づけ）

PDFの Theorem 2.1（有限状態・有限行動・報酬有界）では、無限ホライズン割引MDPに対して決定論的な定常最適方策の存在が述べられています。

要点だけ書くと次の流れです。

Step 1. ベルマン最適作用素を定義する:

(\mathcal{T}v)(s)\coloneqq \sup_{a\in A}\left\{\bar r(s,a)+\gamma \sum_{s'}P(s'|s,a)\,v(s')\right\}

（ $\bar r(s,a)=\mathbb{E}[r(s,a)]$ ）。

Step 2. $\mathcal{T}$ は $\|\cdot\|_\infty$ で $\gamma$ -縮小写像。
Step 3. よって不動点 $V^*$ は一意（Banach不動点定理）。

Step 4. 各状態で次を選ぶ:

\pi^*(s)\in\operatorname*{arg\,max}_{a\in A}\left\{\bar r(s,a)+\gamma \mathbb{E}_{s'\sim P(\cdot\mid s,a)}[V^*(s')]\right\}

この選び方は決定論的かつ定常。

Step 5. この $\pi^*$ は $V^{\pi^*}=V^*$ を満たし最適。

つまり「時刻ごとに方策を変える必要がない」ことが保証され、探索対象を定常方策に絞れるのが実務上も理論上も大きい点です。

5.3 平均報酬型との違い

Section 2.1 では平均報酬（ergodic reward）型にも言及していますが、金融応用では割引報酬または有限ホライズンの設定が中心のため、本文は割引報酬を主軸にしています。

6. 2.1 の残り: Linear MDP と関数近似

6.1 Linear MDP（式 (2.11), (2.12)）

無限ホライズンで特徴量写像 $\phi:S\times A\to\mathbb{R}^d$ を固定し、

P(\cdot\mid s,a)=\langle \phi(s,a),\mu(\cdot)\rangle,\qquad r(s,a)=\langle \phi(s,a),\theta\rangle

と表せるとき Linear MDP と呼びます。
ここで $\mu=(\mu^{(1)},\dots,\mu^{(d)})$ は符号付き測度、 $\theta\in\mathbb{R}^d$ は未知パラメータです。

有限ホライズン版は時刻依存で

P_t(\cdot\mid s,a)=\langle \phi(s,a),\mu_t(\cdot)\rangle,\qquad r_t(s,a)=\langle \phi(s,a),\theta_t\rangle.

導出上の利点

任意の次状態価値関数 $V$ に対し

Q_V(s,a)=\mathbb{E}[r(s,a)]+\gamma\mathbb{E}_{s'\sim P(\cdot\mid s,a)}[V(s')]

は

Q_V(s,a) = \left\langle \phi(s,a), \theta+\gamma\int V(s')\,\mu(ds') \right\rangle

となり、 $Q_V$ が特徴量に関して線形のまま保たれます。
この構造が、サンプル効率のよい理論解析やアルゴリズム設計を可能にします。

6.2 線形関数近似（式 (2.13), (2.14)）

別の見方として、価値関数側を直接

Q(s,a)=\langle \psi(s,a),\omega\rangle,\qquad V(s)=\langle \xi(s),\eta\rangle

と近似する設定があります。有限ホライズンでは

Q_t(s,a)=\langle \psi(s,a),\omega_t\rangle,\qquad V_t(s)=\langle \xi(s),\eta_t\rangle.

PDFでは、緩い条件下で「Linear MDP の仮定」と「線形関数近似の仮定」が本質的に対応することに触れています。

6.3 非線形関数近似（Deep RL への接続）

線形仮定を外すと、ニューラルネットで $Q$ や $\pi$ を近似する Deep RL に接続します。
金融データの高次元性・非線形性を扱いやすい一方、理論保証は線形の場合より難しくなります。

関数近似を含むDP/RLの広い景色は、Bertsekas (free PDF): Abstract Dynamic Programming (3rd ed.) が体系的です。

7. なぜ金融で重要か

最適執行: 有限ホライズンのベルマン方程式を直接使う
長期運用: 無限ホライズン割引モデルが使いやすい
Q-learning/DQN: $Q^*$ の不動点方程式をサンプル近似している
線形/非線形近似: 実務データに合わせて理論と実装を接続できる

付録A: 定常最適方策の存在（詳細導出）

ここでは、有限状態・有限行動・有界報酬の割引MDPで
「決定論的かつ定常な最適方策が存在する」
ことを、ベルマン作用素から順に示します。

A.1 仮定

$|S|<\infty,\; |A|<\infty$
割引率 $\gamma\in(0,1)$
期待1ステップ報酬 $\bar r(s,a)=\mathbb{E}[r(s,a)]$ は有界
遷移確率 $P(s'|s,a)$ は各 $(s,a)$ で $\sum_{s'}P(s'|s,a)=1$

値関数の空間を

\mathcal{B}(S)\coloneqq\{J:S\to\mathbb{R}\}

とし、ノルムは

\|J\|_\infty \coloneqq \max_{s\in S}|J(s)|

を使います（有限集合なので完備）。

A.2 最適ベルマン作用素

(TJ)(s) \coloneqq \max_{a\in A} \left\{ \bar r(s,a)+\gamma\sum_{s'}P(s'|s,a)J(s') \right\}

を定義します。

補題1（単調性）

$J\le K$ （各状態で）なら $TJ\le TK$ 。

理由: 任意の行動 $a\in A$ について

\bar r(s,a)+\gamma\sum_{s'}P(s'|s,a)J(s') \le \bar r(s,a)+\gamma\sum_{s'}P(s'|s,a)K(s')

なので、両辺で $\max_{a}$ を取ればよい。

補題2（ $\gamma$ -縮小性）

\|TJ-TK\|_\infty \le \gamma\|J-K\|_\infty.

証明スケッチ: 任意の状態 $s$ について

\begin{aligned} |(TJ)(s)-(TK)(s)| &\le \max_{a} \gamma\left| \sum_{s'}P(s'|s,a)\bigl(J(s')-K(s')\bigr) \right| \\ &\le \max_a \gamma\sum_{s'}P(s'|s,a)\,|J(s')-K(s')| \\ &\le \gamma\|J-K\|_\infty\sum_{s'}P(s'|s,a) =\gamma\|J-K\|_\infty. \end{aligned}

状態 $s$ の最大を取れば主張が従います。

A.3 不動点の存在と一意性（Banach不動点定理）

補題2より、 $T$ は完備距離空間 $(\mathcal{B}(S),\|\cdot\|_\infty)$ 上の縮小写像。
したがって Banach 不動点定理より、 $T$ は一意な不動点 $J^*$ を持ち、

T J^* = J^*, \qquad J_{k+1}=TJ_k \Rightarrow J_k\to J^*

が成立します。

Banach不動点定理自体の復習には、数学補助（不動点定理）: バナッハの不動点定理（数学の景色）がコンパクトです。

A.4 greedy 方策の構成（定常・決定論的）

各状態で

\pi^*(s)\in \operatorname*{arg\,max}_{a\in A} \left\{ \bar r(s,a)+\gamma\sum_{s'}P(s'|s,a)J^*(s') \right\}

と定義します。 $A$ が有限なので argmax は空でなく、 $\pi^*$ は定義可能です。
また $\pi^*$ は時刻に依存しないため定常方策です。

このとき方策固定ベルマン作用素

(T_{\pi}J)(s) = \bar r\bigl(s,\pi(s)\bigr) +\gamma\sum_{s'}P\bigl(s'|s,\pi(s)\bigr)J(s')

を使うと

T_{\pi^*}J^* = TJ^* = J^*

が成り立ちます。

A.5 $\pi^*$ が最適であること

まず $T_{\pi^*}$ も同様に $\gamma$ -縮小なので不動点は一意。
一方 $J^{\pi^*}$ （方策 $\pi^*$ の価値関数）は定義より

J^{\pi^*}=T_{\pi^*}J^{\pi^*}

を満たすため、一意性より

J^{\pi^*}=J^*.

次に任意の方策 $\pi$ について、定義から $T_\pi J \le TJ$ 。よって反復で

T_\pi^k J \le T^k J \quad (\forall k)

が成り立ち、 $k\to\infty$ を取ると

J^\pi \le J^*.

以上より、 $\pi^*$ は全方策の中で最適。
すなわち「決定論的・定常な最適方策が存在」します。

A.6 どこまで一般化できるか

上の証明は有限 $S,A$ を使っています。連続状態・連続行動へ拡張する場合は、可測性や選択定理（measurable selection）などの追加条件が必要です。
この点は Puterman や Bertsekas の教科書・講義ノートが詳しいです。

Python実装ミニ例（縮小性と value iteration）

Section 2.1 の核である「ベルマン作用素の縮小性」と「反復での不動点到達」を数値で確認する最小例です。

import numpy as np

rng = np.random.default_rng(0)
gamma = 0.9
S, A = 4, 2

P = rng.random((S, A, S))
P /= P.sum(axis=2, keepdims=True)
R = rng.normal(size=(S, A))


def T(V: np.ndarray) -> np.ndarray:
    q = R + gamma * np.einsum("sat,t->sa", P, V)
    return q.max(axis=1)


J = rng.normal(size=S)
K = rng.normal(size=S)
lhs = np.max(np.abs(T(J) - T(K)))
rhs = gamma * np.max(np.abs(J - K))
print("contraction check:", lhs <= rhs + 1e-12, "lhs=", lhs, "rhs=", rhs)

V = np.zeros(S)
for _ in range(300):
    V_next = T(V)
    if np.max(np.abs(V_next - V)) < 1e-10:
        break
    V = V_next

Q = R + gamma * np.einsum("sat,t->sa", P, V)
pi_star = Q.argmax(axis=1)
print("V* =", np.round(V, 4))
print("greedy pi* =", pi_star)

参考

Ben Hambly, Renyuan Xu, Huining Yang, Recent Advances in Reinforcement Learning in Finance, 2023.
元メモ: articles/reinforce-finance.pdf
MIT OCW (PDF): Lecture 1, Lecture 2, Lecture 3
MIT 6.390 notes: Markov Decision Processes
Bertsekas (free PDF): Abstract Dynamic Programming (3rd ed.)
数学補助（不動点定理）: バナッハの不動点定理（数学の景色）