【Agentic RL】2.6 资格迹与TD(λ)算法

一、从n步TD的困境说起在上一章中我们学习了n步TD学习它通过调整n的大小在MC和TD(0)之间取得平衡n1TD(0)n∞MC问题n步TD虽然理论上优美但实现上有个致命缺陷——需要存储过去n步的信息。# n步TD需要的内存memory_buffer[]# 存储过去n步fortinrange(len(episode)):memory_buffer.append((state_t,action_t,reward_t))iflen(memory_buffer)n:memory_buffer.pop(0)# 丢弃超过n步的# 需要等待n步才能更新iflen(memory_buffer)n:calculate_n_step_return()当n很大时这个存储开销是相当可观的。而且如果我们在不同的时间步长之间连续插值混合使用多个n值实现会更加复杂。资格迹Eligibility Traces提供了一种优雅的解决方案。二、资格迹的核心思想2.1 什么是资格迹资格迹是一个与权重向量同维度的记忆向量它记录了哪些权重最近被激活过当某个状态被激活时对应的资格迹增加随着时间推移资格迹衰减# 资格迹的直观理解enp.zeros(num_features)# 资格迹向量forstepinepisode:# 状态激活featuresget_features(current_state)# 资格迹更新被激活的特征迹1其他特征衰减egamma*lambda_*efeatures# 计算TD误差td_errorrewardgamma*V(next_state)-V(current_state)# 更新权重所有特征都根据其资格迹被更新weightsalpha*td_error*e2.2 与短期/长期记忆的类比记忆类型强化学习对应作用短期记忆资格迹ete_tet​记录最近哪些状态被访问长期记忆权重向量wtw_twt​存储状态价值的真实估计核心思想最近的激活对当前奖励的功劳更大值得获得更多的信用credit。三、前向视图 vs 后向视图TD(λ)有两种等价的理解视角3.1 前向视图Forward View理论视角向前看所有未来的n步回报用λ加权平均。λ-回报λ-returnGtλ(1−λ)∑n1∞λn−1Gt(n)G_t^\lambda (1-\lambda) \sum_{n1}^{\infty} \lambda^{n-1} G_t^{(n)}Gtλ​(1−λ)n1∑∞​λn−1Gt(n)​权重分配示意λ0.5 ┌──────────────────────────────────────────────────┐ │ 权重 │ │ │ 1-λ │ │ │ ╲ │ │ │ ╲ (1-λ)λ │ │ │ ╲___ │ │ │ ╲ (1-λ)λ² │ │ │ ╲__ │ │ │ ... │ │ └──┼────┼────┼────┼─────────────────────────→│ │ t t1 t2 t3 时间 │ └──────────────────────────────────────────────────┘特点适合理论分析需要等待Episode结束才能计算本质上等价于更复杂的n步TD3.2 后向视图Backward View实现视角在每一步根据TD误差更新所有状态根据其对当前奖励的资格分配信用。# 后向视图的核心伪代码fortinepisode:# 1. 计算TD误差td_errorrewardgamma*V(s)-V(s)# 2. 更新所有状态的资格迹forall_sinstates:ifscurrent_state:e[s]e[s]1# 当前状态1else:e[s]gamma*lambda_*e[s]# 衰减# 3. 更新所有状态的价值forall_sinstates:V[s]V[s]alpha*td_error*e[s]关键洞察虽然从数学上可以证明后向视图等价于前向视图但实现上更高效——不需要存储过去的信息3.3 等价性证明概要前向视图Δwα∑t0T−1δt∑k0t(γλ)k∇v^(St−k,w)\Delta w \alpha \sum_{t0}^{T-1} \delta_t \sum_{k0}^{t} (\gamma\lambda)^k \nabla \hat{v}(S_{t-k}, w)Δwαt0∑T−1​δt​k0∑t​(γλ)k∇v^(St−k​,w)后向视图Δwα∑t0T−1δtet\Delta w \alpha \sum_{t0}^{T-1} \delta_t e_tΔwαt0∑T−1​δt​et​可以证明当λ\lambdaλ和γ\gammaγ满足一定条件时两者是等价的。四、TD(λ)算法详解4.1 状态价值函数的TD(λ)算法参数α\alphaα学习率γ\gammaγ折扣因子λ\lambdaλ迹衰减参数0 ≤ λ ≤ 1算法流程deftd_lambda(env,num_episodes10000,alpha0.1,gamma0.9,lambda_0.8): TD(λ) 策略评估 参数: - alpha: 学习率 - gamma: 折扣因子 - lambda_: 迹衰减参数 Vnp.zeros(env.observation_space.n)forepisodeinrange(num_episodes):# 初始化资格迹Enp.zeros(env.observation_space.n)state,_env.reset()doneFalsewhilenotdone:# 执行动作使用随机策略actionnp.random.randint(env.action_space.n)next_state,reward,done,_,_env.step(action)# 1. 计算TD误差td_errorrewardgamma*V[next_state]-V[state]# 2. 更新资格迹E[state]gamma*lambda_*E[state]1# 3. 更新所有状态的价值函数Valpha*td_error*E# 4. 衰减所有资格的折扣E*gamma*lambda_ statenext_statereturnV4.2 λ参数的直观理解λ 0TD(0)行为 - 资格迹 当前状态的特征 - 只更新当前状态 λ 1MC行为 - 资格迹持续累积不衰减 - 最终将所有信用分配给Episode中的所有状态 0 λ 1介于两者之间 - 信用根据时间距离衰减 - 离当前状态越近获得越多信用4.3 不同λ值的经验表现Random Walk实验结果不同λ的学习曲线 ┌────────────────────────────────────────────┐ │ RMS Error │ │ 0.4 │ │ │ 0.3 │ λ0 │ │ 0.2 │ ╲ │ │ 0.1 │ ╲ λ0.9 │ │ 0.0 │ ╲─●───●──●─ λ1 (MC) │ │ └──┬───┬───┬───┬───┬───┬───┬──────→ │ │ 0 100 200 300 400 Episodes │ └────────────────────────────────────────────┘ 结论λ0.9 通常是最优选择五、Sarsa(λ)控制算法5.1 从策略评估到控制之前讨论的是策略评估估计给定策略的价值。现在讨论控制找到最优策略。动作价值函数的TD(λ)Q(s,a)←Q(s,a)αδte(s,a)Q(s,a) \leftarrow Q(s,a) \alpha \delta_t e(s,a)Q(s,a)←Q(s,a)αδt​e(s,a)其中e(s,a)e(s,a)e(s,a)是状态-动作对的资格迹。5.2 Sarsa(λ)算法Sarsa State-Action-Reward-State-Actiondefsarsa_lambda(env,num_episodes10000,alpha0.1,gamma0.9,lambda_0.9,epsilon0.1): Sarsa(λ) 控制算法 n_statesenv.observation_space.n n_actionsenv.action_space.n# 初始化Q函数和资格迹Qnp.zeros((n_states,n_actions))Enp.zeros((n_states,n_actions))defepsilon_greedy(state,Q,epsilon):ifnp.random.random()epsilon:returnnp.random.randint(n_actions)returnnp.argmax(Q[state])forepisodeinrange(num_episodes):# 初始化资格迹E.fill(0)# 选择初始动作state,_env.reset()actionepsilon_greedy(state,Q,epsilon)doneFalsewhilenotdone:# 执行动作next_state,reward,done,_,_env.step(action)# 选择下一个动作ε-贪心next_actionepsilon_greedy(next_state,Q,epsilon)# TD误差ifdone:td_errorreward-Q[state,action]else:td_errorrewardgamma*Q[next_state,next_action]-Q[state,action]# 更新资格迹E[state,action]1# 更新Q函数和资格迹Qalpha*td_error*E E*gamma*lambda_ statenext_state actionnext_actionreturnQ5.3 Sarsa vs Q-learning维度Sarsa (On-policy)Q-learning (Off-policy)策略使用ε-贪心选择动作使用贪心选择最大化Q收敛更保守更激进悬崖行走安全避开悬崖边冒险可能踏入悬崖悬崖行走Cliff Walking实验Grid World with Cliff: S . . . . . . . . T ▓▓▓▓▓▓▓▓▓▓ (▓ 悬崖踩到-100) Sarsa学习路径绕过悬崖安全但不是最短 Q-learning学习路径贴着悬崖走最短但危险六、Watkins’s Q(λ)6.1 Off-policy的挑战标准TD(λ)是On-policy算法只能用当前策略采样的数据更新。Off-policy方法如Q-learning面临一个特殊问题探索动作被计入资格迹吗如果一个探索动作导致了好的结果这个功劳应该分配给之前的贪心动作还是探索动作6.2 解决方案Watkins’s Q(λ)的思想只要执行了非贪心动作就清零资格迹。defwatkins_q_lambda(...):...fortinrange(T):ifis_greedy(action):E[s,a]gamma*lambda_*E[s,a]else:E[s,a]0# 清零ifdone:td_errorreward-Q[s,a]else:td_errorrewardgamma*max(Q[s])-Q[s,a]Qalpha*td_error*E注意这意味着Watkins’s Q(λ)不完全等价于前向视图但实际效果通常很好。七、累积迹 vs 替换迹7.1 累积迹Aaccumulating Tracese[s]gamma*lambda_*e[s]1# 如果s被访问问题频繁访问的状态迹可能超过1。7.2 替换迹Replacing Tracese[s]1# 如果s被访问直接设为1优势迹值始终在[0,1]范围内更稳定。对比 状态访问序列: A, B, A, B, A 累积迹: 1.0 → 0.5 → 1.0 → 0.5 → 1.0 → ... 替换迹: 1.0 → 0.0 → 1.0 → 0.0 → 1.0 → ...八、True Online TD(λ)8.1 标准TD(λ)的问题标准TD(λ)使用后向视图更新但在某些情况下与前向视图有微小差异。8.2 True Online TD(λ)为了与前向视图精确等价需要使用True Online版本deftrue_online_td_lambda(env,alpha0.1,gamma0.9,lambda_0.9): True Online TD(λ) - 精确等价于前向视图 Vnp.zeros(env.observation_space.n)v0# old value estimateforepisodeinrange(num_episodes):state,_env.reset()xget_features(state)qnp.dot(V,x)# 当前估计enp.zeros_like(V)doneFalsewhilenotdone:actionnp.random.randint(env.action_space.n)next_state,reward,done,_,_env.step(action)x_nextget_features(next_state)q_nextnp.dot(V,x_next)# TD误差deltarewardgamma*q_next-q# 资格迹更新更精确的公式egamma*lambda_*e(1-alpha*gamma*lambda_*np.dot(e,x))*x# 权重更新Valpha*(deltaq-v)*e-alpha*(q-v)*x vq_next xx_next qq_nextreturnV九、总结9.1 知识回顾概念说明资格迹记录哪些权重最近被激活的向量前向视图理论视角向前看加权回报后向视图实现视角根据资格分配信用TD(λ)用λ参数连接TD(0)和MCSarsa(λ)On-policy控制算法Watkins’s Q(λ)Off-policy控制算法9.2 λ参数选择指南λ值特点适用场景λ0TD(0)低方差高偏差在线学习快速收敛λ0.9最佳平衡点大多数场景推荐λ1MC高方差无偏差Episodic任务样本效率低9.3 实践建议作为起点使用λ0.9调参在0.8-0.99范围内微调考虑任务Episodic任务可尝试更高的λ使用替换迹实际效果更稳定9.4 展望资格迹是强化学习中时间差分的核心机制之一。理解了这一机制后我们可以更好地理解人脑如何进行信用分配多巴胺系统的类似机制如何设计更高效的学习算法如何处理长期依赖问题下一章我们将探讨深度强化学习看看如何用神经网络来近似价值函数和策略函数。