Bellman Equation反向传播：从原理到实践的强化学习入门指南

1次阅读

没有评论

共计 2004 个字符，预计需要花费 6 分钟才能阅读完成。

考虑一个 4 ×4 的网格世界（Grid World），智能体从起点 (0,0) 出发，目标是到达终点(3,3)。每次移动会获得 - 1 的即时奖励，碰到边界则保持原位。这个简单环境揭示了强化学习的核心挑战：

如何评估状态的价值？
如何平衡探索（exploration）和利用（exploitation）？
如何在延迟奖励和即时奖励间做权衡？

这些问题的数学基础正是 Bellman Equation，它通过递归形式将长期回报与即时奖励联系起来。

动态规划（Dynamic Programming）
需要完整环境模型（$p(s’|s,a)$ 已知）
时间复杂度：$O(|S|^2|A|)$
适合小规模离散状态空间
蒙特卡洛（Monte Carlo）
通过完整回合采样估计价值
无偏估计但方差高
适合回合制任务
时序差分（Temporal Difference）
结合动态规划和蒙特卡洛优点
在线学习，方差较低
TD($\lambda$)可调整偏差 - 方差权衡

定义状态价值函数：
$$V^\pi(s) = \mathbb{E}\pi[\sum | s_t = s]$$}^\infty \gamma^k r_{t+k

根据马尔可夫性质，可得 Bellman 方程：
$$V^\pi(s) = \sum_a \pi(a|s) \sum_{s’} p(s’|s,a)[r + \gamma V^\pi(s’)]$$

当策略为最优策略 $\pi^$ 时，Bellman 最优方程成立：
$$V^(s) = \max_a \sum_{s’} p(s’|s,a)[r + \gamma V^*(s’)]$$

其中：
– $\gamma$：折扣因子（0≤γ<1）
– $p(s’|s,a)$：状态转移概率
– $r$：即时奖励

import numpy as np

# 环境参数
GRID_SIZE = 4
ACTIONS = ['up', 'down', 'left', 'right']
GAMMA = 0.9
THETA = 1e-4

# 初始化值函数
V = np.zeros((GRID_SIZE, GRID_SIZE))

def transition(s, a):
    """状态转移函数"""
    i, j = s
    if a == 'up': ni, nj = max(i-1,0), j
    elif a == 'down': ni, nj = min(i+1,GRID_SIZE-1), j
    elif a == 'left': ni, nj = i, max(j-1,0)
    else: ni, nj = i, min(j+1,GRID_SIZE-1)
    return (ni, nj), -1  # 固定奖励 -1

def value_iteration():
    while True:
        delta = 0
        for i in range(GRID_SIZE):
            for j in range(GRID_SIZE):
                if (i,j) == (GRID_SIZE-1, GRID_SIZE-1):
                    continue  # 终止状态

                v_old = V[i,j]
                max_v = -np.inf
                for a in ACTIONS:
                    (ni, nj), r = transition((i,j), a)
                    max_v = max(max_v, r + GAMMA * V[ni,nj])
                V[i,j] = max_v
                delta = max(delta, abs(v_old - V[i,j]))

        if delta < THETA:
            break

通过调整学习率 $\alpha$ 观察收敛速度：

import matplotlib.pyplot as plt

alphas = [0.1, 0.3, 0.5, 0.7, 0.9]
converge_steps = []

for alpha in alphas:
    V = np.zeros((GRID_SIZE, GRID_SIZE))
    steps = 0
    while True:
        # 带学习率的更新规则
        delta = value_iteration_step(alpha)
        steps += 1
        if delta < THETA:
            break
    converge_steps.append(steps)

plt.plot(alphas, converge_steps)
plt.xlabel('Learning Rate (α)')
plt.ylabel('Convergence Steps')