强化学习笔记（一）
一、强化学习的基本范式与概念
1.1 强化学习的基本范式
- 强化学习的目标：最大化未来累计奖励
- 某次行动可能会产生长期后果
- 奖励可能会延迟
- 牺牲眼前的回报来获得更多可能会更好的长期奖励
- 在强化学习中，时间步$t$发生的事情
- Agent
- 执行动作$A_t$
- 接收到观察$O_t$
- 接收到奖励$R_t$
- 环境
- 接收到动作$A_t$
- 给出观察$O_t$
- 给出奖励$R_t$
- 下一个时间步
- 历史序列$H_t=O_1,R_1,A_1,\cdots,A_{t-1},O_t,R_t$
- 状态$S_t=f(H_t)$
- 环境的状态$S_t^e$
- Agent的状态$S_t^a$
- Agent
- 强化学习Agent具有的组件
- 策略
- Agent的行为函数，从状态到行动的映射
- 确定性：$a=\pi(s)$
- 概率分布：$\pi(a|s)=P[A_t=a|S_t=s]$
- 价值函数
- 对未来价值的预测，衡量状态/行动的好坏
- $v_{\pi}(s)=E_{\pi}[R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\dots|S_t=s]$
- 模型
- Agent对环境的表示，预测环境下一步会做什么
- $\mathcal{P}$预测下一个状态：$\mathcal{P}{ss^{\prime}}^a =\mathbb{P}[S{t+1}=s^{\prime}\mid S_t=s,A_t=a]$
- $\mathcal{R}$预测下一个即时奖励：$\mathcal{R}s^a =\mathbb{E}\left[R{t+1}\mid S_t=s,A_t=a\right]$
- 策略
- 强化学习的Agent分类
- 基于价值函数：隐式策略，有价值函数
- Q-Learning、Sarsa
- 投资顾问：假如你想理财，不知道具体怎么投资，投资顾问帮你分析每种投资方式的「回报潜力」（即价值）。然后，你选择回报潜力最高的投资方式。顾问的目标是不断提高其估算价值的准确性
- 基于策略：有策略，无价值函数
- 策略梯度（Policy Gradients）
- PPO
- 厨师学徒：假如你想成为厨师，最好的办法是直接模仿和优化你的烹饪方法，而不是先学理论（价值函数）再去试验。通过尝试，你会直接调整策略，例如切菜快一点、火候控制得更精准，从而做出更好的菜
- Actor-Critic：有策略，有价值函数
- 团队合作的过程：Actor 是厨师学徒，试着做菜（决策）；Critic 是美食评论家，评价菜的好坏并给出建议（价值评估）
- Model-Free：策略/价值函数，无模型
- 不对环境进行建模，直接与真实环境进行交互来学习到最优策略
- 泛化性优于Model-Based
- 盲目尝试的冒险家： 假设你第一次去一个迷宫探险，不熟悉地形，也没有地图，你只能靠反复尝试不同的路径，逐步摸索出哪条路是最好的。你不关心迷宫的结构，只关注行动的效果，例如「向左」可以减少时间，「向右」会遇到障碍
- Model-Based：策略/价值函数，有模型
- 根据环境中的经验，构建一个虚拟世界，同时真实环境和虚拟世界中学习
- 构建环境模型：学会一个函数，能够预测当前状态下的环境动态，即 状态转移 和 奖励函数
- 理性计划的探险家： 假设你去迷宫探险，但这次你拿到了一张迷宫的地图（即环境模型）。在出发前，你可以先研究地图，推测出最短路径或者避开障碍的路线，然后按计划行动。即使还没进入迷宫，你就能做出不错的决策
- 基于价值函数：隐式策略，有价值函数
- 学习和规划（Learning和Planning）
- 学习
- 环境初始是未知的
- Agent与环境交互后改进策略
- 规划
- 环境模型是已知的
- Agent基于模型执行行动（没有任何外部交互）后改进策略
- 又名深思熟虑、推理、内省、沉思、思考、寻找
- 学习
- 探索和利用（Exploration和Exploitation）
- 探索
- 尝试新的动作，找到关于环境的更多信息
- 可能带来更高长期回报的策略、动作或状态，帮助智能体避免陷入局部最优解
- 过度探索：智能体会浪费大量时间尝试不太可能带来高回报的动作，无法充分利用已知的信息
- 利用
- 基于已有知识选择最优动作，以最大化当前的即时回报
- 过度利用：智能体可能停留在次优的策略上（局部最优解），无法发现更高回报的选择
- 采用$\epsilon-$贪心
- 以$\epsilon$的概率进行探索（随机选择动作）
- 以$1-\epsilon$的概率进行利用（选择当前最优动作）
- 一般设置初始$\epsilon$较大（偏向探索），然后逐渐减小（偏向利用）
- 采用上置信界（Upper Confidence Bound, UCB）
- 同时考虑动作的预期回报和不确定性（置信区间）。
- 高不确定性和高回报的动作会被优先选择，特别适用于多臂赌博机（Multi-Armed Bandit）问题
- 探索
- 预测和控制（Prediction和Control）
- 预测：评估未来
- 给定一个策略（policy），评估该策略在未来的表现
- 目标：计算每个状态的价值（Value），即该策略从当前状态开始执行后，期望获得的累计回报
- 输入：已知的策略 $\pi(s, a)$，表示在每个状态下选择某动作的概率
- 输出：状态值函数 $V^\pi(s)$ 或状态-动作值函数 $Q^\pi(s, a)$
- $V^\pi(s)$：遵循策略 $\pi$ 时，从状态 $s$ 开始的期望总回报
- $Q^\pi(s, a)$：遵循策略 $\pi$ 时，在状态 $s$ 执行动作 $a$ 后的期望总回报
- 这是一个评估任务，因为策略已经固定
- 假设你有一个固定的策略（比如在迷宫中选择路径的方法），Prediction 的任务是告诉你如果执行这个策略，每个状态的长期收益会是多少
- 给定一个策略（policy），评估该策略在未来的表现
- 控制：优化未来
- 寻找一个最优策略，使得未来的累计回报最大化
- 目标：找到最佳策略 $\pi^{\star}$，使得每个状态的价值 $V^{\pi^{\star}}(s)$ 或 $Q^{\pi^{\star}}(s, a)$ 达到最大
- 核心问题：需要探索状态和动作的组合，确定哪个策略可以实现最优回报
- 假设你不知道在迷宫中最优的行走策略，Control 的任务是通过试验和学习找到最短路径策略，从而最大化你的目标（如最快到达出口）
- 寻找一个最优策略，使得未来的累计回报最大化
- 预测：评估未来
1.2 在线学习与离线学习
- 在线学习
- 在在线学习中，策略网络会实时与环境进行交互，采集新的数据（状态、动作、奖励等），然后利用这些新数据进行策略更新。
- 每次更新策略后，下一轮的数据采集会基于当前的更新后的策略进行，这种交互是动态的。
- 离线学习
- 在离线学习中，数据已经预先采集好，存储在固定的数据集中。
- 策略更新时不再与环境交互，而是基于静态数据集进行训练。
- 这种方式类似于监督学习，目标是最小化策略和标签之间的差异。
1.3 On-Policy与Off-Policy
| 类别 | On-policy Learning | Off-policy Learning |
|---|---|---|
| 学习目标 | 直接学习当前执行的策略 $\pi$ 的价值或改进 $\pi$ | 学习目标策略 $\pi$ 的价值，但经验来自另一个行为策略 $\mu$ |
| 行为策略 | 行为策略和目标策略一致 $\mu = \pi$ | 行为策略和目标策略可能不同 $\mu \neq \pi$，也可能是$\pi_{old}$ |
| 数据来源 | 从当前策略 $\pi$ 采样的交互经验（行动和状态） | 从其他策略 $\mu$ 或环境采样的经验数据 |
| 形象描述 | 在岗位上工作时学习技能 | 通过观察别人工作而学习技能 |
| 优点 | 学习和执行策略一致，简单直观 | 可以探索最优策略 $\pi^{\star}$，学习灵活 |
| 缺点 | 受限于当前策略 $\pi$，可能收敛到次优策略 | 需要重要性采样或其他机制解决策略差异引发的偏差 |
| 例子 | SARSA | Q-learning |
1.4 逆向强化学习
- 逆向强化学习（Inverse Reinforcement Learning, IRL） ：核心目标是从专家的行为中推断潜在的奖励函数
- 传统强化学习的逆过程，传统强化学习的目标是根据已知的奖励函数找到最优策略，而逆向强化学习则是通过观察专家的最优策略或行为来推断背后的奖励函数
1.5 强化学习的应用
- 游戏中的策略制定
- 自动驾驶中的决策系统
- 自动化机器学习中的神经网络架构搜索
- 自然语言处理中的对话系统
- 广告投放中的广告主竞价策略
二、经典强化学习
2.1 马尔可夫链
2.1.1 马尔可夫过程
- 马尔可夫状态
- $P[S_{t+1}|S_t]=P[S_{t+1}|S_1,\cdots,S_t]$
- 基于现在，未来独立于过去：$H_{1:t}\rightarrow S_t\rightarrow H_{t+1:\infty}$
- 一旦有了当前状态，历史可以被抛弃
- 当前状态是未来的充分统计数据
- 马尔可夫随机过程（Markov Processes）
- 马尔可夫随机过程由二元组$(\mathcal{S},\mathcal{P})$组成
- $\mathcal{S}$：状态空间（所有可能状态的集合）
- $\mathcal{P}$：状态转移概率矩阵，定义从当前状态$s_t$转移到下一个额状态$s_{t+1}$的概率$P(s_{t+1}|s_t)$
$$
\mathcal{P}{ss^{\prime}}=P[S{t+1}=S^{\prime}|S_t=s]
$$
- 马尔可夫随机过程由二元组$(\mathcal{S},\mathcal{P})$组成
2.1.2 马尔可夫奖励过程
马尔可夫奖励过程（Markov Reward Processes）由二元组$(\mathcal{S},\mathcal{P},\mathcal{R},\gamma)$组成
- $\mathcal{S}$：状态空间（所有可能状态的集合）
- $\mathcal{P}$：状态转移概率矩阵，定义从当前状态$s_t$转移到下一个额状态$s_{t+1}$的概率$P(s_{t+1}|s_t)$
- $\mathcal{R}$：奖励函数，$\mathcal{R}s=E[R{t+1}|S_t=s]$
- $\gamma$：折扣因子，$\gamma\in[0,1]$，用于衡量未来奖励的当前价值
- 当前获得的奖励$R$在$k+1$个时间步后的价值为$\gamma^{k}R$
- $\gamma\rightarrow0$时，趋近于”近视“评估（Mypoic）
- $\gamma\rightarrow1$时，趋近于”远视“评估（Far-Sighted）
- 采用折扣因子的原因
- 便于数学上的收敛计算
- 折扣因子限制了回报的累积，确保问题可解并且奖励是有限的
- 折扣因子通过对未来奖励进行加权，隐式表达了这种不确定性
- 在金融或经济领域，折扣因子反映了时间价值的概念，即立即获得的奖励比未来的同样奖励更有价值
- 人类和动物普遍更倾向于即时奖励而非延迟奖励，即“即时满足倾向”
- 在某些特殊情况下，可以使用不折扣的马尔可夫过程，例如：
- 所有序列都终止：如果问题设计保证智能体的每条路径最终都会结束，例如迷宫求解任务，回报的总和是有限的，无需引入折扣因子
- 特定目标任务：例如以目标状态为重点的问题，可能不关注时间步长
- 未折扣的过程更适用于有界问题，而在无界问题中通常会引入折扣因子
值函数$V(s)$
- 从时间步$t$开始的总折扣奖励值/回报（Return）：$G_t=R_{t+1}+\gamma R_{t+2}+\dots=\displaystyle\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1}$
- 值函数则表示从当前状态$s$开始的期望累计回报，评估状态的长期价值
$$
V(s)=E[G_t|S_t=s]
$$ - 据此，值函数可以划分为两部分：即时奖励$R_{t+1}$与折扣后的$\gamma V(S_{t+1})$
$$
V(s)=E[G_t|S_t=s]=E[R_{t+1}+\gamma V(S_{t+1})|S_t=s]
$$
贝尔曼方程（Bellman Equation）
定义策略$\pi$下价值函数和动作值函数的递归关系
$v=\mathcal{R}+\gamma\mathcal{P}v$，其中
$$
\begin{bmatrix}v(1) \ \vdots \ v(n)\end{bmatrix}=\begin{bmatrix}\mathcal{R}{1} \ \vdots \ \mathcal{R}{n}\end{bmatrix}+\gamma\begin{bmatrix}\mathcal{P}{11} & \ldots & \mathcal{P}{1n} \ \vdots \ \mathcal{P}{11} & \ldots & \mathcal{P}{nn}\end{bmatrix}\cdot \begin{bmatrix}v(1) \ \vdots \ v(n)\end{bmatrix}
$$$v=\mathcal{R}+\gamma\mathcal{P}v\Rightarrow (I-\gamma\mathcal{P})v=\mathcal{R}\Rightarrow v=(I-\gamma\mathcal{P})^{-1}\mathcal{R}$
贝尔曼方程的计算复杂度
- 对于$n$个状态，该方程的计算复杂度是$O(n^3)$
- 对于小的马尔科夫链，可以利用该公式计算
- 对于较大的马尔科夫链，则需要使用一些迭代的方法，如动态规划、蒙特卡洛方法、时间差分学习
2.1.2 马尔可夫决策过程
马尔可夫决策过程（Markov Decision Process）是具有动作的马尔可夫奖励过程
马尔可夫奖励过程由二元组$(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$组成
- $\mathcal{S}$：状态空间（所有可能状态的集合）
- $\mathcal{A}$：动作空间（所有可能动作的集合）
- $\mathcal{P}$：状态转移概率矩阵，定义从当前状态$s_t$**执行动作$a$**转移到下一个额状态$s_{t+1}$的概率
$$
\mathcal{P}{ss^{\prime}}^{a}=P[S{t+1}=S^{\prime}|S_t=s,A_t=a]
$$ - $\mathcal{R}$：奖励函数，$\mathcal{R}s^a=E[R{t+1}|S_t=s,A_t=a]$
- $\gamma$：折扣因子，$\gamma\in[0,1]$，用于衡量未来奖励的当前价值
策略：给定状态时，动作的概率分布
- $\pi(a|s)=P[A_t=a|S_t=s]$
- 策略完整定义了Agent的行动，智能体在每个时间步会依据它选择动作
- 在标准MDP中，策略是时间无关的，不会随着时间变化，只要状态相同，选择的行动均相同
- $A_t\sim \pi(\cdot|S_t),\forall t>0$，即在任何时间步$t > 0$，动作$A_t$都是根据相同的策略$\pi$从状态$S_t$中抽样的
给定$\mathcal{M}=(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$和策略$\pi$
马尔可夫过程：$(\mathcal{S},\mathcal{P}^{\pi})$
马尔科夫奖励过程：$(\mathcal{S},\mathcal{P}^{\pi},\mathcal{R}^{\pi},\gamma)$
$$
\mathcal{P}{s,s^{\prime}}^{\pi}=\displaystyle\sum{a\in\mathcal{A}}\pi(a|s)\mathcal{P}{ss^{\prime}}^{a}\
\mathcal{R}{s}^{\pi}=\displaystyle\sum_{a\in\mathcal{A}}\pi(a|s)\mathcal{R}_{s}^{a}
$$
给定策略$\pi$，值函数$V_\pi(s)$
- $V_{\pi}(s)=E_{\pi}[G_t|S_t=s]=E_{\pi}[R_{t+1}+\gamma V_{\pi}(S_{t+1})|S_t=s]$
- 贝尔曼期望方程的矩阵形式：$v_\pi=\mathcal{R}^\pi+\gamma\mathcal{P}^\pi v_\pi$，则$v_\pi=(I-\gamma\mathcal{P}^\pi)^{-1}\mathcal{R}^\pi$
动作值函数$q_{\pi}(s,a)$
- $q_{\pi}(s,a)=E_{\pi}[G_t|S_t=s,A_t=a]=E_{\pi}[R_{t+1}+\gamma q_{\pi}(S_{t+1},A_{t+1})|S_t=s,A_t=a]$
- 表示从当前状态$s$开始选择动作$a$的期望累计回报，即评估Agent在状态$s$下选择特定动作$a$的价值
- 在选择动作$a$后，Agent会按照策略$\pi$来选择后续动作
$$
\begin{aligned}
V_{\pi}(s)&=\displaystyle\sum_{a\in\mathcal{A}}\pi(a|s)q_{\pi}(s,a)\
q_\pi(s,a)&=\mathcal{R}s^a+\gamma\displaystyle\sum{s^{\prime}\in\mathcal{S}}\mathcal{P}{ss^{\prime}}^aV_\pi(s^{\prime})\
V{\pi}(s)&=\displaystyle\sum_{a\in\mathcal{A}}\pi(a|s)\left(\mathcal{R}s^a+\gamma\displaystyle\sum{s^{\prime}\in\mathcal{S}}\mathcal{P}{ss^{\prime}}^aV_\pi(s^{\prime})\right)\
q_\pi(s,a)&=\mathcal{R}s^a+\gamma\displaystyle\sum{s^{\prime}\in\mathcal{S}}\mathcal{P}{ss^{\prime}}^a\displaystyle\sum_{a^{\prime}\in\mathcal{A}}\pi(a^{\prime}|s^{\prime})q_\pi(s^{\prime},a^{\prime})
\end{aligned}
$$ - 贝尔曼期望方程：$q_\pi(s, a) = \mathbb{E}[R_t + \gamma \displaystyle\sum_{a’} \pi(a’|S_{t+1}) q_\pi(S_{t+1}, a’) ,|, S_t = s, A_t = a]$
最优化问题
- 最优值函数
- $v_{*}(s)=\displaystyle\max_{\pi}v_{\pi}(s)$
- $q_{*}(s,a)=\displaystyle\max_{\pi}q_{\pi}(s,a)$
- 当求得最优值函数时，即称MDP问题被解决
- 最优策略
- 称$\pi \geq \pi^\prime \iff v_\pi(s) \geq v_{\pi^\prime}(s), , \forall s$，来定义策略的优劣
- 对于任何MDP，均存在最优策略$\pi_{*}$，使得$\pi^{\star} \geq \pi, , \forall \pi$
- $v_{\pi_*}(s) = v_*(s), , \forall s$且$q_{\pi_*}(s,a) = q_*(s,a), , \forall s$
- 根据最优动作值函数得到最优策略：
$$
\pi^*(a|s) =
\begin{cases}
1, & \text{如果 } a = \arg\displaystyle\max_{a \in A} q^*(s, a), \
0, & \text{否则}.
\end{cases}
$$ - 最优值函数与最优动作值函数
$$
\begin{aligned}
v_*(s)&=\displaystyle\max_a q_*(s,a)\
q_*(s)&=\mathcal{R}s^a+\gamma\displaystyle\sum{s^{\prime}\in\mathcal{S}}\mathcal{P}{ss^{\prime}}^aV(s^{\prime})\
v_(s)&=\displaystyle\max_a \mathcal{R}s^a+\gamma\displaystyle\sum{s^{\prime}\in\mathcal{S}}\mathcal{P}{ss^{\prime}}^aV(s^{\prime})\
q_(s,a)&=\mathcal{R}s^a+\gamma\displaystyle\sum{s^{\prime}\in\mathcal{S}}\mathcal{P}{ss^{\prime}}^a\displaystyle\max{a^\prime}q_*(s^{\prime},a^{\prime})
\end{aligned}
$$ - 最优化问题的贝尔曼方程没有封闭解，考虑迭代解方法
- 值迭代
- 策略迭代
- Q-Learning
- SARSA
- 最优值函数
马尔可夫过程的扩展
- （完全可观察）马尔可夫决策过程MDP：$O_t=S_t^a=S_t^e$，Agent直接观察环境的状态
- 部分可观察马尔可夫决策过程（POMDP, Partially Observable MDP）：Agent无法直接观察到完整的环境状态，而是通过观测$o_t$获取部分信息，必须构造自己的状态表示
- 连续状态和动作空间：状态和动作空间是连续的，可以使用函数逼近方法（如深度强化学习）解决
2.2 动态规划
2.2.1 动态规划定义
引入动态规划
- 假设MDP已知，即状态转移和奖励已知
- 利用Dynamic Programming解决已知的MDP问题
动态规划的特点
- 具有最优子结构和重叠子问题两个重要性质
- Model-based：动态规划假设 MDP 的转移概率 $P(s’|s, a)$ 和奖励函数 $R(s, a)$ 是完全已知的；而我们需要解决的是Planning，如何解决MDP问题
- 确定性：值函数和策略的更新是基于精确的数学计算，不依赖于采样数据
- 对于Prediction：预测策略的价值函数——策略评估
- 对于Control：在给定MDP中，能做到的最好事情是什么；可获得最大回报是什么；最好的策略是什么；最优价值函数
动态规划的目标
动态规划的目标是求解最优策略 $\pi^{\star}$，即找到一种策略使得累积期望奖励（或价值）最大化
价值函数（Value Function）：
- 状态价值函数 $V^\pi(s)$：在策略 $\pi$ 下，从状态 $s$ 开始的累积期望奖励
$$
V^\pi(s) = \mathbb{E}^\pi \left[ \displaystyle\sum_{t=0}^\infty \gamma^t R(s_t, a_t) \big| s_0 = s \right]
$$ - 状态-动作价值函数 $Q^\pi(s, a)$：在策略 $\pi$ 下，从状态 $s$ 执行动作 $a$ 开始的累积期望奖励
$$
Q^\pi(s, a) = \mathbb{E}^\pi \left[ R(s, a) + \gamma V^\pi(s’) \big| s, a \right]
$$- 状态价值函数 $V^\pi(s)$：在策略 $\pi$ 下，从状态 $s$ 开始的累积期望奖励
设$V^{\star}(s)$ 是最优价值函数，最优策略$\pi^{\star}$满足：
$$
V^*(s) = \displaystyle\max_a \mathbb{E}_{\pi^*} \left[ R(s, a) + \gamma V^*(s’) \right]
$$
2.2.2 策略评估与策略改进
策略评估（Policy Evaluation）
目标：给定一个策略 $\pi$，计算其对应的状态价值函数 $V^\pi(s)$
方法：通过贝尔曼期望方程（Bellman Expectation Equation）迭代计算：
$$
V_\pi(s) = \displaystyle\sum_{a} \pi(a|s) \displaystyle\sum_{s’} P(s’|s, a) \big[ R(s, a) + \gamma V_\pi(s’) \big]
$$迭代方式:
- 初始 $V_0(s) = 0$（或任意值）
- 逐步更新（其中$s^{\prime}$是$s$的后继状态）
$$
V_{k+1}(s) = \displaystyle\sum_{a} \pi(a|s) \displaystyle\sum_{s’} P(s’|s, a) \big[ R(s, a) + \gamma V_k(s’) \big]
$$
Synchronous备份：每次更新时，对于所有状态$s\in S$，使用$v_k(s^{\prime})$更新$v_{k+1}(s)$
改进
- In-Place Dynamic Programming
- Prioritised sweeping
- Real-time dynamic programming
- Full-Width Backups
- Sample Backups
策略评估过程中，虽然能够利用当前价值函数和贪婪原则得到好的策略，但是策略评估的策略始终是初始被评估策略，不会更新
即更好的策略并不会对价值函数的迭代造成反馈，所以称为策略评估
2.2.3 策略迭代
策略改进（Policy Improvement）
- 目标：基于当前策略的价值函数 $V^\pi(s)$，改进策略 $\pi$
- 实际上，不必等到价值函数收敛，即可得到最优策略
- 方法：利用贪婪原则（Greedy Principle）更新策略：
$$
\begin{align}
\pi’(s) &= \arg\displaystyle\max_a q_{\pi}(s,a) = \arg\displaystyle\max_a \displaystyle\sum_{s’} P(s’|s, a) \big[ R(s, a) + \gamma V_\pi(s’) \big]\
q_{\pi}(s,\pi^{\prime}(s))&=\displaystyle\max_a q_{\pi}(s,a)\ge q_{\pi}(s,\pi(s))=v_{\pi}(s)\
v_{\pi}(s)& \leq q_\pi(s,\pi^{\prime}(s))=\mathbb{E}{\pi^{\prime}}\left[R{t+1}+\gamma v_\pi(S_{t+1})\mid S_t=s\right] \
&\leq\mathbb{E}{\pi^{\prime}}\left[R{t+1}+\gamma q_\pi(S_{t+1},\pi^{\prime}(S_{t+1}))\mid S_t=s\right] \
&\leq\mathbb{E}{\pi^{\prime}}\left[R{t+1}+\gamma R_{t+2}+\gamma^2q_\pi(S_{t+2},\pi^{\prime}(S_{t+2}))\mid S_t=s\right] \
&\leq\mathbb{E}{\pi^{\prime}}\left[R{t+1}+\gamma R_{t+2}+…\mid S_t=s\right]=v_{\pi^{\prime}}(s)
\end{align}
$$
策略迭代（Policy Iteration）
目标：反复进行“策略评估”和“策略改进”，直至收敛到最优策略 $\pi^{\star}$。
过程：
- 初始随机策略 $\pi_0$
- 策略评估：计算 $V_{\pi_k}(s)$
- 策略改进：得到新策略 $\pi_{k+1}$
- 重复，直至策略不再变化
与简单的策略评估不同，策略迭代会在更新后的新策略上进行策略评估
最终达到最优策略
$$
q_{\pi}(s,\pi^{\prime}(s))=\displaystyle\max_a q_{\pi}(s,a)= q_{\pi}(s,\pi(s))=v_{\pi}(s)\
\text{Bellman Optimality Equation: }v_{\pi}(s)=\displaystyle\max_a q_{\pi}(s,a)\rightarrow v_{\pi}(s)=v_{*}(s)
$$策略评估得到的价值函数不一定需要收敛，可以提前停止吗
- 迭代K步
- 价值迭代
2.2.4 价值迭代
- 价值迭代（Value Iteration）
目标：直接通过更新价值函数来找到最优值函数 $V_*(s)$，进而推导出最优策略
方法：基于贝尔曼最优方程（Bellman Optimality Equation）迭代：
$$
V_{k+1}(s) = \displaystyle\max_{a\in\mathcal{A}} \displaystyle\sum_{s’\in\mathcal{S}} P(s’|s, a) \big[ R(s, a) + \gamma V_k(s’) \big]=\max_{a\in\mathcal{A}} R(s,a)+\gamma\displaystyle\sum_{s’\in\mathcal{S}} P(s’|s, a)V_k(s’)\
v_{k+1}=\max_{a\in\mathcal{A}}\mathcal^a+\gamma\mathcal{P}^av_k
$$终止条件：当 $V_{k+1}(s)$ 与 $V_k(s)$ 的变化小于阈值 $\epsilon$ 时停止
与策略迭代不同，没有显式策略
中间价值函数可能并没有对应的策略；而策略迭代中价值函数是根据特定策略计算得到的
| 问题类型 | 贝尔曼方程 | 算法 | 功能 | 算法复杂度 |
|---|---|---|---|---|
| 预测问题 | 贝尔曼期望方程 | 策略评估 | 计算给定策略的状态价值函数 $v_\pi(s)$ | 每次迭代$O(mn^2)$，其中$n$是状态数，$m$是动作数 |
| 控制问题（期望） | 贝尔曼期望方程 | 策略迭代 | 求解最优策略 $\pi^{\star}$ 和 $v_*(s)$ | 每次策略评估$O(mn^2)$，策略改进$O(mn)$ |
| 控制问题（最优） | 贝尔曼最优方程 | 价值迭代 | 求解最优策略 $\pi^{\star}$ 和 $v_*(s)$ | 每次迭代$O(mn^2)$，基于动作值函数时，每次迭代$O(m^2n^2)$ |
