ベルマン方程式と動的計画法

前の notebook で価値関数が「将来の期待値」だと見えたら、次にやることは、その期待値をどう計算するかです。ここではベルマン期待方程式と最適方程式を並べ、その上に方策反復法と価値反復法がどう乗っているかをまとめて読みます。

参考動画（外部）

授業本編ではなく、別の説明で見直したいときの参考材料です。

ベルマン方程式は「長期最適化を局所更新へ崩す式」

強化学習が扱いたいのは長い将来ですが、そのままでは計算しづらいので、1 ステップ先の価値に押し込み直します。方策が固定されているなら期待値を取り、最適化したいなら max を取る。この切り替えだけで、評価の式と制御の式が分かれます。

Vπ(s)=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)[r+γVπ(s′)]V^{\pi}(s) = \sum_a \pi(a\mid s)\sum_{s',r} p(s',r\mid s,a)[r + \gamma V^{\pi}(s')] V∗(s)=max⁡a∑s′,rp(s′,r∣s,a)[r+γV∗(s′)]V^*(s) = \max_a \sum_{s',r} p(s',r\mid s,a)[r + \gamma V^*(s')] 
gamma = 0.92
Q_next = {("s1", "left"): 0.5, ("s1", "right"): 0.7}
pi = {"left": 0.4, "right": 0.6}
expected_backup = sum(pi[a] * (1.0 + gamma * Q_next[("s1", a)]) for a in ["left", "right"])
optimal_backup = max(1.0 + gamma * Q_next[("s1", a)] for a in ["left", "right"])
print("Bellman expectation backup =", round(expected_backup, 6))
print("Bellman optimality backup =", round(optimal_backup, 6))

この差分は見た目には小さくても、アルゴリズムの役割を決めます。期待方程式を何度も回すと「今の方策の評価」になり、最適方程式を何度も回すと「最善行動を前提にした価値」へ近づきます。

方策反復法は「評価」と「改善」を交互に行う

方策反復法では、まず現在の方策で価値関数を評価し、その価値を使って方策を greedy に改善します。何がよいかを一度しっかり評価してから行動を変えるので、責務分離が明快です。

states = ["s0", "s1"]
actions = ["left", "right"]
gamma = 0.9
P = {
    "s0": {
        "left": [("s0", 0.2), ("s1", 1.0)],
        "right": [("s1", 0.4), ("s1", 0.4)],
    },
    "s1": {
        "left": [("s0", 0.0), ("s0", 0.0)],
        "right": [("s1", 0.3), ("s1", 0.3)],
    },
}

def action_value(s, a, V):
    ns1, r1 = P[s][a][0]
    ns2, r2 = P[s][a][1]
    return 0.5 * (r1 + gamma * V[ns1]) + 0.5 * (r2 + gamma * V[ns2])

def eval_policy(policy, V):
    newV = {}
    for s in states:
        a = policy[s]
        newV[s] = action_value(s, a, V)
    return newV

def improve_policy(V):
    return {s: max(actions, key=lambda a: action_value(s, a, V)) for s in states}
V = {"s0": 0.0, "s1": 0.0}
policy = {"s0": "left", "s1": "left"}
for k in range(8):
    V = eval_policy(policy, V)
    new_policy = improve_policy(V)
    print(f"iter={k}: policy={policy}, V={{s0:{V['s0']:.4f}, s1:{V['s1']:.4f}}}")
    if new_policy == policy:
        print("policy stable -> stop")
        break
    policy = new_policy

評価と改善がはっきり分かれているので、どこで詰まっているかが追いやすいのが方策反復法の利点です。その代わり、毎回の反復で評価をある程度回す必要があります。

価値反復法は「最適ベルマン更新」へ一本化する

価値反復法では、方策評価を明示的に分けず、毎回 max を取った最適ベルマン更新を直接回します。価値が収束してから、最後に greedy に方策を取り出します。

states = ["s0", "s1"]
actions = ["left", "right"]
gamma = 0.9
P = {
    "s0": {
        "left": [("s0", 0.2), ("s1", 1.0)],
        "right": [("s1", 0.4), ("s1", 0.4)],
    },
    "s1": {
        "left": [("s0", 0.0), ("s0", 0.0)],
        "right": [("s1", 0.3), ("s1", 0.3)],
    },
}

def action_value(s, a, V):
    ns1, r1 = P[s][a][0]
    ns2, r2 = P[s][a][1]
    return 0.5 * (r1 + gamma * V[ns1]) + 0.5 * (r2 + gamma * V[ns2])
V = {"s0": 0.0, "s1": 0.0}
for it in range(40):
    newV = {}
    for s in states:
        newV[s] = max(action_value(s, a, V) for a in actions)
    diff = max(abs(newV[s] - V[s]) for s in states)
    V = newV
    print(f"iter={it}: diff={diff:.6f}, V={{s0:{V['s0']:.4f}, s1:{V['s1']:.4f}}}")
    if diff < 1e-6:
        break
policy_star = {s: max(actions, key=lambda a: action_value(s, a, V)) for s in states}
print("optimal V =", V)
print("greedy policy from V =", policy_star)

方策反復法と比べると、価値反復法はループが短く、そのぶん「評価を十分やったか」を考えずに済みます。一方で、どちらもベルマン方程式から出てくる動的計画法であり、違うのは反復の切り方です。

ここまでで掴みたいこと

  1. ベルマン期待方程式は方策評価、ベルマン最適方程式は最適制御の式である。
  2. 方策反復法は評価と改善を分ける。
  3. 価値反復法は最適ベルマン更新を直接回す。
  4. 後半の TD 法や Q 学習は、このベルマン更新を「モデルなし・データから」近似する方法だと見るとつながりやすい。