从马尔可夫决策过程到贝尔曼方程理解强化学习的核心算法开头怎么让机器「学会」决策上一篇我们学习了玻尔兹曼机用能量函数建模概率分布。今天我们学习动态规划——强化学习的数学基础。监督学习 输入 → 正确答案标签 强化学习 状态 → 动作 → 奖励没有正确答案 问题 机器怎么知道哪个动作是「好」的 答案 最大化累积奖励 动态规划提供了解决这个问题的数学框架一、马尔可夫决策过程MDP1.1 MDP 的定义马尔可夫决策过程MDP ═══════════════════════════════════════════════════════════════════ 五元组(S, A, P, R, γ) S状态空间所有可能的状态 A动作空间所有可能的动作 P转移概率 P(s|s, a) R奖励函数 R(s, a, s) γ折扣因子 γ ∈ [0, 1) 马尔可夫性 P(s_{t1} | s_t, a_t, s_{t-1}, a_{t-1}, ...) P(s_{t1} | s_t, a_t) → 未来只依赖于当前状态与历史无关1.2 例子网格世界网格世界示例 ═══════════════════════════════════════════════════════════════════ 状态网格位置 (i, j) 动作上、下、左、右 转移移动到相邻格子可能有随机性 奖励到达目标 100撞墙 -1每步 -1 ┌───┬───┬───┬───┐ │ │ │ │ G │ G 目标100 ├───┼───┼───┼───┤ │ │ X │ │ │ X 障碍物-100 ├───┼───┼───┼───┤ │ S │ │ │ │ S 起点 └───┴───┴───┴───┘ 目标找到从 S 到 G 的最优路径二、贝尔曼方程2.1 值函数值函数Value Function ═══════════════════════════════════════════════════════════════════ 状态值函数 V^π(s) 在状态 s 下遵循策略 π 的期望累积奖励 V^π(s) E[Σ_{t0}^∞ γ^t r_t | s_0 s] 动作值函数 Q^π(s, a) 在状态 s 下执行动作 a然后遵循策略 π 的期望累积奖励 Q^π(s, a) E[Σ_{t0}^∞ γ^t r_t | s_0 s, a_0 a] 关系 V^π(s) Σ_a π(a|s) Q^π(s, a)2.2 贝尔曼期望方程贝尔曼期望方程 ═══════════════════════════════════════════════════════════════════ V^π(s) Σ_a π(a|s) Σ_{s} P(s|s,a) [R(s,a,s) γ V^π(s)] Q^π(s,a) Σ_{s} P(s|s,a) [R(s,a,s) γ Σ_{a} π(a|s) Q^π(s,a)] 直觉 当前值 即时奖励 折扣的未来值2.3 贝尔曼最优方程贝尔曼最优方程 ═══════════════════════════════════════════════════════════════════ V*(s) max_a Σ_{s} P(s|s,a) [R(s,a,s) γ V*(s)] Q*(s,a) Σ_{s} P(s|s,a) [R(s,a,s) γ max_{a} Q*(s,a)] 最优策略 π*(s) argmax_a Q*(s, a) 意义 最优值满足贝尔曼最优方程 求解这个方程就能得到最优策略三、值迭代3.1 算法值迭代算法 ═══════════════════════════════════════════════════════════════════ 输入 MDP (S, A, P, R, γ) 收敛阈值 θ 步骤 1. 初始化 V(s) 0 for all s 2. 重复直到收敛 for each state s: V_old(s) V(s) V(s) max_a Σ_{s} P(s|s,a) [R(s,a,s) γ V(s)] if max_s |V(s) - V_old(s)| θ: break 3. 提取最优策略 π*(s) argmax_a Σ_{s} P(s|s,a) [R(s,a,s) γ V(s)] 输出 最优值函数 V* 最优策略 π*3.2 收敛性值迭代的收敛性 ═══════════════════════════════════════════════════════════════════ 定理 值迭代算法收敛到唯一的最优值函数 V* 收敛速度 |V_k - V*| ≤ γ^k |V_0 - V*| → 几何级数收敛 条件 - 0 ≤ γ 1 - 状态空间有限四、策略迭代4.1 算法策略迭代算法 ═══════════════════════════════════════════════════════════════════ 输入 MDP (S, A, P, R, γ) 步骤 1. 初始化策略 π随机或贪心 2. 重复直到收敛 a. 策略评估计算 V^π 重复直到收敛 for each state s: V(s) Σ_a π(a|s) Σ_{s} P(s|s,a) [R(s,a,s) γ V(s)] b. 策略改进更新 π for each state s: π(s) argmax_a Σ_{s} P(s|s,a) [R(s,a,s) γ V(s)] if π 没有变化 break 输出 最优策略 π*4.2 值迭代 vs 策略迭代特性值迭代策略迭代每次迭代更新值函数评估 改进策略收敛速度慢快计算量小大实现难度简单复杂五、Python 实现5.1 网格世界环境importnumpyasnpimportmatplotlib.pyplotaspltclassGridWorld:网格世界环境def__init__(self,rows4,cols4,goal_pos(0,3),obstacle_pos(1,1)):self.rowsrows self.colscols self.goal_posgoal_pos self.obstacle_posobstacle_pos# 动作上、下、左、右self.actions[(-1,0),(1,0),(0,-1),(0,1)]self.n_actionslen(self.actions)# 状态数self.n_statesrows*colsdefstate_to_pos(self,state):状态编号转坐标return(state//self.cols,state%self.cols)defpos_to_state(self,pos):坐标转状态编号returnpos[0]*self.colspos[1]defstep(self,state,action):执行动作返回 (next_state, reward, done)posself.state_to_pos(state)new_pos(pos[0]self.actions[action][0],pos[1]self.actions[action][1])# 边界检查ifnew_pos[0]0ornew_pos[0]self.rowsor\ new_pos[1]0ornew_pos[1]self.cols:new_pospos# 撞墙不动# 障碍物检查ifnew_posself.obstacle_pos:new_pospos# 撞障碍物不动next_stateself.pos_to_state(new_pos)# 奖励ifnew_posself.goal_pos:reward100doneTrueelse:reward-1doneFalsereturnnext_state,reward,donedefget_transitions(self,state,action):获取转移概率确定性环境next_state,reward,doneself.step(state,action)return[(1.0,next_state,reward)]5.2 值迭代实现defvalue_iteration(env,gamma0.99,theta1e-6):值迭代算法Vnp.zeros(env.n_states)policynp.zeros(env.n_states,dtypeint)iteration0whileTrue:V_oldV.copy()forsinrange(env.n_states):q_values[]forainrange(env.n_actions):q0forprob,next_state,rewardinenv.get_transitions(s,a):qprob*(rewardgamma*V[next_state])q_values.append(q)V[s]max(q_values)policy[s]np.argmax(q_values)iteration1ifnp.max(np.abs(V-V_old))theta:breakprint(f值迭代收敛于{iteration}轮)returnV,policy5.3 策略迭代实现defpolicy_evaluation(env,policy,gamma0.99,theta1e-6):策略评估Vnp.zeros(env.n_states)whileTrue:V_oldV.copy()forsinrange(env.n_states):apolicy[s]q0forprob,next_state,rewardinenv.get_transitions(s,a):qprob*(rewardgamma*V[next_state])V[s]qifnp.max(np.abs(V-V_old))theta:breakreturnVdefpolicy_iteration(env,gamma0.99):策略迭代算法policynp.random.randint(0,env.n_actions,env.n_states)iteration0whileTrue:# 策略评估Vpolicy_evaluation(env,policy,gamma)# 策略改进new_policynp.zeros(env.n_states,dtypeint)forsinrange(env.n_states):q_values[]forainrange(env.n_actions):q0forprob,next_state,rewardinenv.get_transitions(s,a):qprob*(rewardgamma*V[next_state])q_values.append(q)new_policy[s]np.argmax(q_values)iteration1ifnp.array_equal(new_policy,policy):breakpolicynew_policyprint(f策略迭代收敛于{iteration}轮)returnV,policy5.4 测试# 创建环境envGridWorld(rows4,cols4,goal_pos(0,3),obstacle_pos(1,1))# 值迭代V_vi,policy_vivalue_iteration(env,gamma0.99)# 策略迭代V_pi,policy_pipolicy_iteration(env,gamma0.99)# 可视化值函数fig,axesplt.subplots(1,2,figsize(12,5))# 值迭代结果ax1axes[0]ax1.imshow(V_vi.reshape(4,4),cmapviridis)ax1.set_title(Value Iteration)foriinrange(4):forjinrange(4):ax1.text(j,i,f{V_vi[i*4j]:.1f},hacenter,vacenter)# 策略迭代结果ax2axes[1]ax2.imshow(V_pi.reshape(4,4),cmapviridis)ax2.set_title(Policy Iteration)foriinrange(4):forjinrange(4):ax2.text(j,i,f{V_pi[i*4j]:.1f},hacenter,vacenter)plt.tight_layout()plt.show()# 可视化策略action_symbols[↑,↓,←,→]policy_gridnp.array([action_symbols[policy_vi[i]]foriinrange(16)]).reshape(4,4)print(最优策略值迭代:)print(policy_grid)六、工业应用6.1 机器人控制机器人控制 ═══════════════════════════════════════════════════════════════════ 状态机器人的位置、速度、姿态 动作电机控制信号 奖励到达目标 100碰撞 -100 应用 - 路径规划 - 运动控制 - 自主导航6.2 游戏 AI游戏 AI ═══════════════════════════════════════════════════════════════════ AlphaGo 状态棋盘局面 动作落子位置 奖励赢 1输 -1平 0 方法 - 蒙特卡洛树搜索MCTS - 深度强化学习6.3 推荐系统推荐系统 ═══════════════════════════════════════════════════════════════════ 状态用户历史行为 动作推荐物品 奖励用户点击/购买 1忽略 0 应用 - 个性化推荐 - 广告投放 - 内容分发七、避坑指南使用动态规划的 3 个陷阱坑 1γ 太大 → 收敛慢错误做法gamma0.9999# ❌ γ 太大V,policyvalue_iteration(env,gamma0.9999)# 需要很多轮才能收敛正确做法根据问题选择合适的 γ# ✅ 通常 γ 0.9 ~ 0.99V,policyvalue_iteration(env,gamma0.99)坑 2γ 太小 → 只考虑短期奖励错误做法gamma0.1# ❌ γ 太小V,policyvalue_iteration(env,gamma0.1)# 只考虑下一步的奖励忽略长期目标正确做法需要平衡短期和长期奖励# ✅ γ 0.9 可以看到较远的未来V,policyvalue_iteration(env,gamma0.9)坑 3状态空间太大 → 计算量爆炸错误做法100×100 网格# ❌ 状态空间太大envGridWorld(rows100,cols100)# 10000 个状态每个状态要计算 4 个动作# 计算量太大正确做法用函数逼近如深度强化学习# ✅ 用神经网络逼近值函数# Deep Q-Network (DQN)importtorchimporttorch.nnasnnclassDQN(nn.Module):def__init__(self,state_dim,action_dim):super().__init__()self.fc1nn.Linear(state_dim,128)self.fc2nn.Linear(128,128)self.fc3nn.Linear(128,action_dim)defforward(self,x):xtorch.relu(self.fc1(x))xtorch.relu(self.fc2(x))returnself.fc3(x)八、本篇总结核心要点回顾MDP状态、动作、转移概率、奖励、折扣因子值函数V(s) 状态值Q(s,a) 动作值贝尔曼方程当前值 即时奖励 折扣的未来值值迭代迭代更新值函数直到收敛策略迭代交替进行策略评估和策略改进γ 的作用平衡短期和长期奖励下篇预告下一篇我们学习Hopfield 网络。动态规划解决的是「决策」问题Hopfield 网络解决的是「记忆」问题。下一篇你将学到Hopfield 网络的结构联想记忆的原理能量函数与稳定性用 Python 手写 Hopfield 网络本期互动你对动态规划有什么看法你用过强化学习吗在什么场景下你觉得 DQN 和传统动态规划有什么区别你知道强化学习的哪些应用欢迎在评论区留言。系列目录篇标题状态01Haykin 精讲开篇从「只会调参」到「理解神经网络的灵魂」✅ 完成02感知器神经网络的「鼻祖」为什么它能「学会」分类✅ 完成03LMS 算法从最小二乘到随机梯度下降工业自适应滤波的核心✅ 完成04反向传播神经网络为什么能「学习」用 NumPy 手写 BP✅ 完成05核方法为什么 SVM 能处理非线性问题理解「升维」的本质✅ 完成06支持向量机最大间隔的「艺术」为什么它是「小数据之王」✅ 完成07正则化为什么模型越复杂越容易过拟合L1/L2/Dropout✅ 完成08PCA为什么降维能「去噪」从特征值分解到核 PCA✅ 完成09SOM无监督学习的「聚类之王」为什么它能「自组织」✅ 完成10信息论为什么「信息最大化」能学特征从熵到 ICA✅ 完成11玻尔兹曼机深度学习的「前世」从统计力学到 RBM✅ 完成12动态规划强化学习的「数学基础」从 MDP 到值迭代✅ 当前13Hopfield 网络联想记忆的「鼻祖」为什么它能「回忆」⏳ 下一篇14卡尔曼滤波为什么它能「预测」从贝叶斯推断到粒子滤波⏳ 待写15Haykin 精讲终篇从感知器到深度学习——一部神经网络的「进化史」⏳ 待写点赞收藏转发是我持续更新的动力