动态规划
动态规划（Dynamic Programming）概述
基本概念
动态规划是解决强化学习问题的一种重要方法，它通过将复杂问题分解为子问题，并存储子问题的解来避免重复计算。 在强化学习中，动态规划主要用于计算最优策略和最优价值函数。
核心思想：通过"分而治之"的方式，将复杂问题分解为更小的子问题，并利用子问题的解来构建原问题的解。
主要算法
1. 策略评估（Policy Evaluation）
计算给定策略下的状态价值函数
2. 策略改进（Policy Improvement）
基于当前价值函数改进策略
3. 策略迭代（Policy Iteration）
交替进行策略评估和改进
4. 价值迭代（Value Iteration）
直接迭代计算最优价值函数
算法流程
策略迭代
- 初始化策略π
- 策略评估：计算Vπ
- 策略改进：基于Vπ更新策略
- 重复步骤2-3直到策略稳定
价值迭代
- 初始化价值函数V
- 对每个状态s更新V(s)
- 重复步骤2直到收敛
- 从V导出最优策略
应用场景
小型MDP问题
状态空间和动作空间较小的决策问题
最优控制
如机器人路径规划、资源分配等
游戏AI
如简单的棋盘游戏、迷宫问题等
资源调度
如任务调度、库存管理等