时序差分算法与Sarsa实现详解

1. 时序差分算法核心思想解析

时序差分（Temporal Difference, TD）算法作为强化学习中的核心方法，巧妙结合了动态规划与蒙特卡洛采样的优势。其核心公式V(S_t) ← V(S_t) + α[R_{t+1} + γV(S_{t+1}) - V(S_t)]体现了"用未来状态的价值估计来修正当前估计"的思想，这种自举（bootstrapping）机制使其具有独特的优势：

• 在线学习能力：无需等待回合结束即可更新，适合持续交互场景
• 方差控制：相比蒙特卡洛的完整回报，TD目标方差更小
• 偏差-方差权衡：通过γ参数调节长期视野与短期准确性

关键理解：TD误差δ = R + γV(S') - V(S)实际上衡量了"当前估计的意外程度"，这个信号驱动着价值函数的持续优化

2. Sarsa算法实现细节

2.1 算法流程剖析

Sarsa作为on-policy TD控制算法，其更新规则为：

python复制Q(s,a) ← Q(s,a) + α[r + γQ(s',a') - Q(s,a)]

具体实现时需要关注：

1. ε-greedy策略的平衡：初始ε建议设为0.1-0.3，可线性衰减
2. 学习率α的设置：从0.1开始随训练逐步减小
3. 折扣因子γ：长期任务建议0.9-0.99

2.2 Cliff Walking环境实现

python复制class CliffWalkingEnv:
    def __init__(self, width=12, height=4):
        self.w = width
        self.h = height
        self.x = 0  # 智能体水平位置
        self.y = height - 1  # 垂直位置(原点在左上角)

    def step(self, action):
        moves = [[0,-1],[0,1],[-1,0],[1,0]]  # 上,下,左,右
        self.x = np.clip(self.x + moves[action][0], 0, self.w-1)
        self.y = np.clip(self.y + moves[action][1], 0, self.h-1)
        
        reward = -1
        done = (self.y == self.h-1) and (0 < self.x < self.w-1)
        if done: reward = -100
        return self.y * self.w + self.x, reward, done

3. Q-learning与Sarsa的关键差异

3.1 更新规则对比

3.2 悬崖漫步中的表现差异

• Sarsa会学习到远离悬崖的安全路径
• Q-learning会找到理论最优但风险较高的路径
• 实际训练曲线显示Q-learning初期回报波动更大

4. 多步TD算法实现

4.1 n-step Sarsa原理

平衡MC和TD的优势：

math复制G_t^{(n)} = R_{t+1} + γR_{t+2} + ... + γ^{n-1}R_{t+n} + γ^nQ(S_{t+n})

4.2 代码实现关键

python复制class NStepSarsa:
    def __init__(self, n=5, ...):
        self.n = n
        self.state_buffer = []
        self.action_buffer = []
        self.reward_buffer = []

    def update(self, s, a, r, s_next, done):
        self.buffers.append((s,a,r))
        if len(self.buffers) >= self.n:
            G = sum([(γ**i)*r for i,r in enumerate(self.reward_buffer)])
            if not done:
                G += (γ**self.n) * self.Q[s_next][self.policy(s_next)]
            # 更新n步前的状态
            old_s, old_a = self.state_buffer.pop(0), self.action_buffer.pop(0)
            self.Q[old_s][old_a] += α*(G - self.Q[old_s][old_a])

5. 工程实践建议

1. 参数调优经验：

   • 学习率α采用余弦退火：α = α_min + 0.5*(α_max-α_min)*(1+cos(t/T))
   • ε衰减策略：ε = ε_end + (ε_start-ε_end)*exp(-t/ε_decay)

2. 收敛性判断：

   • 滑动窗口平均回报率变化<1%持续100episode
   • Q值变化量二范数<1e-4

3. 性能优化技巧：

   • 使用优先扫描(Prioritized Sweeping)
   • 实现Experience Replay缓冲池
   • 对离散状态使用哈希表存储Q值

6. 理论收敛性证明要点

1. 基本假设：

   • MDP满足遍历性
   • 所有状态-动作对被无限次访问
   • 步长满足Robbins-Monro条件：∑α=∞, ∑α²<∞

2. 关键引理：
   Q-learning可以表示为随机近似过程：

   math复制Q_{k+1} = (1-α_k)Q_k + α_k[TQ_k + w_k]
   

   其中T是压缩映射算子，w_k为噪声项

3. 收敛路线：
   证明过程需建立：

   • 随机噪声的均方有界性
   • 伪收缩不等式成立
   • 应用随机近似理论中的ODEs方法

实际应用中，当采用线性函数近似时，需要满足兼容性条件才能保证收敛，这是后续DQN等算法需要解决的问题。