強化学習その4: 2.3 Value-based Methods

この記事は articles/reinforce-finance.pdf の Section 2.3: Value-based Methods の要点を、式の意味とアルゴリズム差分が追える形で整理したものです。

1. 2.3 の設定

Section 2.3 は次の設定を置いています。

無限ホライズン
割引報酬
有限状態・有限行動（tabular）
定常方策

この設定で、未知の $P,r$ の下でもサンプル

(s,a,r,s')

を使って $V$ や $Q$ を更新するのが value-based の基本アイデアです。

2. TD(0)（式 (2.21), (2.22)）

方策 $\pi$ 固定での価値関数推定を

V^{\pi,(n+1)}(s) \leftarrow (1-\beta_n(s,a))V^{\pi,(n)}(s) +\beta_n(s,a)\bigl[r+\gamma V^{\pi,(n)}(s')\bigr]

と更新します（式 (2.21)）。

同値な形として

V^{\pi,(n+1)}(s) \leftarrow V^{\pi,(n)}(s) +\beta_n(s,a)\,\delta_n

\delta_n = \underbrace{r+\gamma V^{\pi,(n)}(s')}_{\text{TD target}} -V^{\pi,(n)}(s)

（式 (2.22)）が使われます。

3. Q-learning（式 (2.23), (2.24)）

Q-learning はベルマン最適方程式のサンプル近似です。

Q^{(n+1)}(s,a) \leftarrow (1-\beta_n(s,a))Q^{(n)}(s,a) +\beta_n(s,a)\left[r+\gamma\max_{a'}Q^{(n)}(s',a')\right]

（式 (2.23)）。

3.1 収束条件（Theorem 2.2）

典型的には学習率が Robbins-Monro 条件

\sum_{i=1}^{\infty}\beta_{n_i(s,a)}=\infty,\qquad \sum_{i=1}^{\infty}\beta_{n_i(s,a)}^2<\infty

を満たし、報酬が有界なら

Q^{(n)}(s,a)\to Q^*(s,a)\quad(n\to\infty)

が成り立ちます（式 (2.24) と Theorem 2.2 の要旨）。

4. SARSA（式 (2.25), (2.26)）

SARSA は on-policy TD 学習です。更新式は

Q^{(n+1)}(s,a) \leftarrow (1-\beta)Q^{(n)}(s,a) +\beta\bigl(r+\gamma Q^{(n)}(s',a')\bigr)

で、次行動 $a'$ を現在の方策（例: $\varepsilon$ -greedy）で選びます（式 (2.25)）。

4.1 $\varepsilon$ -greedy（式 (2.26)）

\begin{cases} \text{確率 }1-\varepsilon\text{ で } \arg\max_{a'}Q^{(n)}(s,a') \text{ から選ぶ}\\ \text{確率 }\varepsilon\text{ で } A \text{ から一様ランダムに選ぶ} \end{cases}

4.2 Q-learning との違い

Q-learning: 更新に $\max_{a'}Q(s',a')$ を使う（off-policy）
SARSA: 実際に選んだ $a'$ の $Q(s',a')$ を使う（on-policy）

5. サンプル効率の議論（2.3.4 の要約）

Section 2.3.4 では、非漸近解析とサンプル複雑度の結果が整理されています。
細部は論文依存ですが、流れは次です。

TD(0) の非漸近解析は主に線形近似で進展
Q-learning は simulator あり/なしでオーダーが変わる
線形MDP仮定では、特徴次元 $d$ に依存するより良いオーダーが得られる

代表的な形として、Q-learning 系では

\tilde O\!\left( \frac{|S||A|}{(1-\gamma)^5\varepsilon^{5/2}} \right)

のような評価、線形MDPでは

\tilde O\!\left( \frac{d}{(1-\gamma)^3\varepsilon^2} \right)

のような評価が報告されています（定数・仮定・ログ因子は論文ごとに異なります）。

6. 金融タスクでの解釈

執行やマーケットメイクでは、状態・行動が高次元で tabular 前提は破れやすい
それでも TD/Q-learning/SARSA の更新構造は、DQNやActor-Criticの基礎になる
まず tabular で収束直観を掴んでから関数近似へ進むのが実装上有効

7. まとめ

TD(0): 価値関数を1ステップ誤差で更新
Q-learning: ベルマン最適方程式の off-policy 近似
SARSA: 実行方策に沿う on-policy 更新
理論比較は sample complexity と convergence rate で読む

Python実装ミニ例（TD(0), Q-learning, SARSA）

5状態の簡単な line-world で、3手法の更新式を比較する最小実装です。

import numpy as np

rng = np.random.default_rng(0)
gamma = 0.95
alpha = 0.1
eps = 0.1
S, A = 5, 2
START = 2


def step(s: int, a: int):
    ns = max(0, min(S - 1, s + (-1 if a == 0 else 1)))
    done = ns in (0, S - 1)
    r = -1.0 if ns == 0 else (1.0 if ns == S - 1 else 0.0)
    return ns, r, done


def eps_greedy(Q: np.ndarray, s: int, e: float):
    if rng.random() < e:
        return int(rng.integers(A))
    return int(np.argmax(Q[s]))


# TD(0): 固定方策（ここでは一様ランダム）で V を評価
V = np.zeros(S)
for _ in range(5000):
    s = START
    done = False
    while not done:
        a = int(rng.integers(A))
        ns, r, done = step(s, a)
        target = r if done else r + gamma * V[ns]
        V[s] += alpha * (target - V[s])
        s = ns
print("TD(0) V =", np.round(V, 3))

# Q-learning: off-policy
Q_q = np.zeros((S, A))
for _ in range(4000):
    s = START
    done = False
    while not done:
        a = eps_greedy(Q_q, s, eps)
        ns, r, done = step(s, a)
        best_next = 0.0 if done else np.max(Q_q[ns])
        Q_q[s, a] += alpha * (r + gamma * best_next - Q_q[s, a])
        s = ns
print("Q-learning pi =", np.argmax(Q_q, axis=1))

# SARSA: on-policy
Q_s = np.zeros((S, A))
for _ in range(4000):
    s = START
    a = eps_greedy(Q_s, s, eps)
    done = False
    while not done:
        ns, r, done = step(s, a)
        if done:
            target = r
        else:
            na = eps_greedy(Q_s, ns, eps)
            target = r + gamma * Q_s[ns, na]
        Q_s[s, a] += alpha * (target - Q_s[s, a])
        s = ns
        if not done:
            a = na
print("SARSA pi =", np.argmax(Q_s, axis=1))

参考

Ben Hambly, Renyuan Xu, Huining Yang, Recent Advances in Reinforcement Learning in Finance, 2023.
元メモ: articles/reinforce-finance.pdf
Sutton and Barto, Reinforcement Learning: An Introduction