在 $4\times 4$ 的网格情形中：

• 状态空间表示智能体在网格中的位置，从左下到右上依次编号二维坐标为 $(0,0)$ 到 $(3,3)$；
• 动作空间包括向上、向右、向下和向左移动（数值表示依次为 $\{0, 1, 2, 3\}$）；
• 状态转移概率 $P(s'|s, a)$ 满足边界条件，即限制智能体不能移动出网格边界。这样的边界条件确保智能体在现有的状态空间内进行决策和学习；
• 终态为右上角位置 $(3,3)$，一旦智能体到达该位置，当前回合结束；
• 奖励函数 $R(s,a,s')$ 定义为：当智能体到达终态 $s'=(3,3)$ 时，奖励 $+10$，此外带有每步移动的惩罚 $-1$，鼓励智能体以最短路径到达终态，这平衡智能体的探索 (exploration) 和利用 (exploitation) 的行为，后者是指智能体在已知信息基础上选择最优动作以最大化奖励，前者是指智能体尝试新的动作以发现潜在的更优策略。需要注意的是，奖励是稀疏奖励 (sparse reward)，只有在到达特殊情形时才会获得奖励，不是每一个格点上都有奖励。奖励函数还关注到达奖励格的方式和决策路径。

为了调整智能体在探索和利用之间的权衡，可以

• 引入 $\varepsilon$ - 贪婪策略 (epsilon-greedy policy)，即智能体以概率 $1-\varepsilon$ 选择当前估计的最优动作，以概率 $\varepsilon$ 随机选择一个动作进行探索。通过调整 $\varepsilon$ 的值，可以控制智能体的探索程度，从而影响学习效果和收敛速度。
• 使用软最大化策略 (softmax policy)，根据动作的估计值分配选择概率，使得高估计值的动作被选择的概率更大，但仍然保留一定的探索空间。
• 采用上置信界 (Upper Confidence Bound, UCB) 方法，结合动作的估计值和不确定性，选择具有最高上置信界的动作，从而在探索和利用之间取得平衡。

比如，智能体在状态 $s$（面对冰箱）时，可以选择动作 $a$（打开冰箱门），然后根据状态转移概率 $P(s'|s,a)$ 转移到下一个状态 $s'$（冰箱门打开），并获得即时奖励 $R(s,a,s')$（找到食物，奖励 $+10$），但也有可能什么都没找到（奖励 $-1$）。这就是 $r$ 的随机性体现。而 $\pi_*$ 就是希望能找到一个最优策略，使得在任何状态下，选择的动作都能最大化未来的累积奖励。（期望意义下的最优）

现在给出 $Q_\pi$ 的 Bellman 期望方程的推导过程。从起始点 $Q_{\pi}(s,a)=\mathbb E_{\pi} \left[ G_t | S_t = s, A_t = a \right]$ 出发，将回报拆解成即时奖励和未来奖励的折扣和：

$$\begin{array}{ll} Q_{\pi}(s,a)&=\displaystyle \mathbb{E}_{\pi} \left[ \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s, A_t = a \right]\\\\ &=\displaystyle \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma \sum_{k=0}^{\infty} \gamma^k R_{t+k+2} | S_t = s, A_t = a \right]\\\\ &=\displaystyle \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a \right]\\\\ &=\displaystyle \mathbb{E}_{\pi} \left[ R_{t+1} |s,a \right] + \gamma \mathbb{E}_{\pi} \left[ G_{t+1} | s,a \right]\\ \\ &=\displaystyle \sum_{s',r} P(s',r|s,a) \cdot r +\sum_{s'}P(s'|s,a) \cdot \gamma \mathbb{E}_{\pi} \left[ G_{t+1} | s',a' \right]\\\\ &=\displaystyle \sum_{s',r} P(s',r|s,a) \left[ r + \gamma \sum_{a'} \pi(a'|s') Q_{\pi}(s',a') \right]\end{array}$$

简言之，$Q$ 是一个递归定义的函数，通过对 $Q$ 的期望计算，可以逐步逼近最优动作值函数 $Q_*$，从而找到最优策略 $\pi_*$。寻找最优策略主要有两种方法：

• 动态规划：分为值迭代和策略迭代，需要已知完整的环境模型（状态转移概率和奖励函数）；
• 强化学习：不需要已知环境模型，通过与环境交互来学习最优策略，主要包括值函数方法（如 $Q$ 学习）和策略方法（如策略梯度方法）。

同步评估的例子是，想要评估一个城市各小区的房价（状态价值），但房价相互影响，小区和邻近小区的房价会互相影响，因此需要同时一轮轮地更新所有小区的房价估计。而就地评估则是逐个小区地更新房价估计，利用最新的估计值进行计算，依次评估各小区的房价。

策略改进定理是在说，如果我们能找到一个新策略 $\pi'$，使得在每个状态 $s$ 下，按照新策略选择的动作在旧策略下的动作值函数 $Q_{\pi}(s, \pi'(s))$ 至少不低于旧策略的状态值函数 $V_{\pi}(s)$，那么新策略 $\pi'$ 在所有状态下的表现至少不会比旧策略 $\pi$ 差，写成公式推导就是

$$V_{\pi}(s) = Q_{\pi}(s, \pi(s)) \leq Q_{\pi}(s, \pi'(s)) = V_{\pi'}(s)$$

这是不过是用 $V,Q$ 表示同一件事。

策略迭代的局限性也是显而易见的，比如在博弈环境中，环境的动态性和不确定性使得状态转移概率和奖励函数难以准确建模，因此无法直接应用策略迭代方法。此外，策略迭代需要维护整个状态空间的值函数，对于大规模状态空间的问题，计算和存储开销较大，难以实际应用。

Bellman 最优方程告诉我们，在最优情形下，最优状态值函数和最优动作值函数之间的关系为

$$V_{*}(s) = \max_{a \in A} Q_{*}(s,a)$$

所以，通过反复选取预期回报最大的动作，作为状态值函数的更新依据，意思就是说希望在此处决策是采用最大预期回报的动作，自然当前状态下的预期回报就是最大回报（最大动作值函数）。

冻酸奶超市问题 (Frozen Yogurt Shop Problem) 是一个经典的强化学习问题。在这个问题中，智能体需要管理一个冻酸奶超市的库存和定价策略，以最大化利润。具体情形如下：

• 状态空间 $S$：表示超市的库存水平，其中 $s\in \{0,1,2,3,4,5\}$；
• 动作空间 $A$：表示智能体可以采取补货决策，其中 $a\in \{0,1,2\}$，分别对应不同补货数量；
• 最大库存限制为 $5$ 单位；
• 需求 $d$ 服从分布 $\{0,1,2,3\}$，表示每天的顾客需求量；
• 开销为
  • 售价为每单位 $20$；
  • 补货成本为每单位 $12$；
  • 库存持有成本为每单位 $2$；
  • 缺货惩罚为每单位 $5$；

目标是找到最优的补货策略 $\pi^*$，使得在长期内最大化超市的利润。可以列出方程：

• 库存更新方程：$s' = \max(0,\min(5, s + a - d))$；
• 奖励函数：

$$r(s,a,d)=20 \min (s+a,d) - 12 a - 2 s - 5 \max(0,d - (s + a))$$

• 需求分布：

$$P(d=0)=0.1, \quad P(d=1)=0.3, \quad P(d=2)=0.4, \quad P(d=3)=0.2$$

• MDP 参数：$\gamma=0.9,\ \theta=0.001$。

$Q$ - 学习的更新公式推导如下。从当前的 $Q$ - 表出发，在 $t$ 时刻，智能体处于状态 $s_t$，采取动作 $a_t$，获得即时奖励 $r_t$，并转移到下一个状态 $s_{t+1}$。我们希望做出最大化未来回报的决策，因为决策是一个概率过程（动态过程），因此选取总是存在误差：

$$\Delta =(r_t+\gamma \max_{a} Q(s_{t+1},a)) - Q(s_t,a_t)$$

这里的 $\Delta$ 就是时序差分误差 (Temporal Difference Error)，表示当前估计与目标值之间的差异。通过调整当前的 $Q(s_t,a_t)$，使其更接近目标值 $r_t + \gamma \max_{a} Q(s_{t+1},a)$，从而逐步逼近最优动作值函数 $Q_*(s,a)$。具体地，设置学习率 $\alpha$，控制每次更新的步长，最终得到 $Q$ - 学习的更新公式：

$$Q(s_t,a_t)\leftarrow Q(s_t,a_t) + \alpha\left[ r_{t} + \gamma \max_{a} Q(s_{t+1},a) - Q(s_t,a_t) \right]$$

$Q$ - 学习通过当前的估计值更新另一个估计值，看似可能会导致自举偏差 (self-fulfilling bias)，即估计值受到自身误差的影响，从而导致估计值偏离真实值。但 $Q$ - 学习的映射是一个收缩映射，不同的 $Q$，或者说 $Q$ 表格之间的距离会逐步缩小，最终收敛到唯一的最优动作值函数 $Q_*$。具体地，定义 $Q$ - 学习的更新算子如上。

此外，学习率应该保持适当的衰减，以确保收敛性。通常要求满足以下条件：

• $\sum_{t=0}^{\infty} \alpha_t(s,a) = \infty$，确保每个状态 - 动作对被充分更新；
• $\sum_{t=0}^{\infty} \alpha_t^2(s,a) < \infty$，防止更新过度震荡。

$Q$ - 学习的局限性是：

• 离散的状态和动作空间，不利于计算，并且高维度还会带来维度灾难问题；
• 对复杂的环境建模能力有限；
• 需要处理每一对状态 - 动作对，存储开销大；
• 不能归纳未见过的状态（泛化能力差）。

一般而言，深度学习辅助 $Q$ - 学习的实现也十分困难，因为

• 神经网络是非线性函数逼近器，可能会引入不稳定性和发散问题；
• 观测的数据具有序列相关性，违反了独立同分布 (i.i.d.) 假设，影响训练效果；
• $Q$ - 值估计会变得不稳定，目标值随着网络参数的更新而变化，导致训练过程不稳定。

为此，DQN 引入了经验回放和目标网络等技术来缓解这些问题，从而提高训练的稳定性和效果：

• 经验回放 (Experience Replay)：将智能体与环境交互的经验存储在一个缓冲区中，随机采样小批量数据进行训练，打破数据之间的相关性，提高训练的稳定性。
• 目标网络 (Target Network)：引入一个独立的目标网络，用于计算目标值 $r + \gamma \max_{a'} Q(s',a';\theta^-)$，并定期将当前网络的参数 $\theta$ 复制到目标网络 $\theta^-$，从而稳定目标值的计算。
• 梯度裁剪 (Gradient Clipping)：限制梯度的最大值，防止梯度爆炸，提高训练的稳定性。

目标网络综合了当前网络的学习成果，也兼顾历史稳定性，当目标网络更新比主网络慢时，在一段时间内，主网络 $Q(s,a;\theta)$ 就会有一个稳定的学习目标，减少了由于网络参数频繁变化带来的不稳定性。

如果不加目标网络，更新就是硬更新，即每次都用最新的网络参数来计算目标值：

$$\theta^-\leftarrow \theta$$

而有了目标网络后，更新变成软更新，即每次只更新一小部分：

$$\theta^- \leftarrow \tau \theta + (1-\tau) \theta^-$$

其中 $\tau$ 是一个小的正数，通常取值在 $0.001$ 到 $0.01$ 之间。

使用参数化有以下优点：

• 通用性：可以表示复杂的策略，适用于大规模状态空间；
• 紧凑性：通过参数化减少存储需求；
• 可微性：便于使用梯度下降等优化方法进行训练。

Monte Carlo 策略梯度方法 (Monte Carlo Policy Gradient Methods) 是一种基于策略梯度定理的强化学习算法。它通过采样完整的轨迹来估计梯度，从而更新策略参数 $\theta$。具体步骤如下：

• 采样轨迹：根据当前策略 $\pi_\theta$ 与环境交互，生成一条完整的轨迹

$$\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots, s_T)$$

• 计算累积奖励：对于每个时间步 $t$，计算从时间步 $t$ 开始的累积奖励

$$G_t = \sum_{k=t}^{T} \gamma^{k-t} r_k$$

• 对数概率梯度：计算每个时间步 $t$ 的对数概率梯度 $\nabla_{\theta} \log \pi_\theta(a_t|s_t)$：

  • 对于离散型，使用 softmax 函数来参数化策略：

  $$\pi_\theta(a|s) = \frac{e^{\theta^T\phi(s,a)}}{\sum_{a'} e^{\theta^T\phi(s,a')}}\implies \nabla_{\theta} \log \pi_\theta(a|s) = \phi(s,a) - \sum_{a'} \pi_\theta(a'|s) \phi(s,a')$$

  • 对于连续型，使用 Gaussian 分布来参数化策略：

  $$\pi_\theta(a|s) = \mathcal N(\mu_\theta(s),\sigma^2)\implies \nabla_{\theta} \log \pi_\theta(a|s) = \frac{a - \mu_\theta(s)}{\sigma^2} \nabla_{\theta} \mu_\theta(s)$$

• 估计梯度：使用采样的轨迹来估计目标函数的梯度：

  • 对于单个轨迹 $\tau$，梯度估计为：

  $$\nabla_{\theta} J(\theta) \approx g=g(\tau)= \sum_{t=0}^{T} \nabla_{\theta} \log \pi_\theta(a_t|s_t) G_t$$

  • 对于多个轨迹 $\{\tau_i\}_{i=1}^N$，梯度估计为：

  $$\nabla_{\theta} J(\theta) \approx g=\frac{1}{N} \sum_{i=1}^{N} g(\tau_i)= \frac{1}{N} \sum_{i=1}^{N} \sum_{t=0}^{T} \nabla_{\theta} \log \pi_\theta(a_t^i|s_t^i) G_t^i$$

• 更新参数：初始化梯度 $g_0=0$，用上述计算好的 $g$ 累加到 $g_0$ 上，然后使用梯度上升法更新策略参数，其中 $\alpha$ 是学习率：

$$\theta \leftarrow \theta + \alpha g$$

• 重复上述步骤，不断采样，计算梯度并更新参数，直到策略收敛或达到预定的训练轮数。

下面给出梯度定理的证明推导。

• 对 Bellman 期望方程两边对 $\theta$ 求导，展开：

$$\begin{array}{ll} \displaystyle \nabla_{\theta} V_{\pi_\theta}(s)&=\displaystyle \nabla_{\theta} \sum_{a} \pi_\theta(a|s) Q_{\pi_\theta}(s,a)\\\\ &=\displaystyle \sum_{a} \left[ \nabla_{\theta} \pi_\theta(a|s) Q_{\pi_\theta}(s,a) + \pi_\theta(a|s) \nabla_{\theta} Q_{\pi_\theta}(s,a) \right] \\ \\ &=\displaystyle \sum_{a} \nabla_{\theta} \pi_\theta(a|s) Q_{\pi_\theta}(s,a) + \gamma \sum_{a} \pi_\theta(a|s) \sum_{s'} P(s'|s,a) \nabla_{\theta} V_{\pi_\theta}(s')\end{array}$$

• 定义在策略 $\pi_\theta$ 下的转移概率：

$$P(s\to s';1,\pi_\theta) = \sum_{a} \pi_\theta(a|s) P(s'|s,a)$$

• 代入上式，得到：

$$\nabla_{\theta} V_{\pi_\theta}(s) = \sum_{a} \nabla_{\theta} \pi_\theta(a|s) Q_{\pi_\theta}(s,a) + \gamma \sum_{s'} P(s\to s';1,\pi_\theta) \nabla_{\theta} V_{\pi_\theta}(s')$$

• 递归展开上式，得到：

$$\nabla_{\theta} V_{\pi_\theta}(s) = \sum_{k=0}^{\infty} \gamma^k \sum_{s'} P(s\to s';k,\pi_\theta) \sum_{a} \nabla_{\theta} \pi_\theta(a|s') Q_{\pi_\theta}(s',a)$$

其中， $P(s\to s';k,\pi_\theta)$ 表示在策略 $\pi_\theta$ 下，从状态 $s$ 出发经过 $k$ 步转移到状态 $s'$ 的概率，定义为

$$P(s\to s';k,\pi_\theta) = \sum_{s_1,\ldots,s_{k-1}} \prod_{i=0}^{k-1} P(s_{i+1}|s_i,a_i) \pi_\theta(a_i|s_i)$$

• 定义折扣状态访问分布 (Discounted State Visitation Distribution)：

$$d_{\pi_\theta}(s) = \sum_{s_0}p(s_0) \sum_{k=0}^{\infty} \gamma^k P(s_0 \to s;k,\pi_\theta)$$

其中，$p(s_0)$ 是初始状态分布。折扣状态访问分布表示在策略 $\pi_\theta$ 下，状态 $s$ 在整个轨迹中被访问的频率，考虑了折扣因子 $\gamma$ 的影响。回忆目标函数的定义，我们可以从轨迹的开头进行分类：

$$\begin{array}{ll} \nabla_{\theta} J(\theta) &= \displaystyle \nabla_{\theta} \sum_{s} p(s_0=s) V_{\pi_\theta}(s)\\\\ &= \displaystyle \sum_{s} p(s_0=s) \nabla_{\theta} V_{\pi_\theta}(s)\\\\ &= \displaystyle \sum_{s} p(s_0=s) \sum_{k=0}^{\infty} \gamma^k \sum_{s'} P(s\to s';k,\pi_\theta) \sum_{a} \nabla_{\theta} \pi_\theta(a|s') Q_{\pi_\theta}(s',a)\\\\ &= \displaystyle \sum_{s'} \left[ \sum_{s} p(s_0=s) \sum_{k=0}^{\infty} \gamma^k P(s\to s';k,\pi_\theta) \right] \sum_{a} \nabla_{\theta} \pi_\theta(a|s') Q_{\pi_\theta}(s',a)\\\\ &= \displaystyle \sum_{s'} d_{\pi_\theta}(s') \sum_{a} \nabla_{\theta} \pi_\theta(a|s') Q_{\pi_\theta}(s',a)\\ \\&= \displaystyle \mathbb{E}_{s \sim d_{\pi_\theta}, a \sim \pi_\theta} \left[ \nabla_{\theta} \log \pi_\theta(a|s) Q_{\pi_\theta}(s,a) \right]\end{array}$$

这是状态 - 动作对的期望形式。如果按轨迹进行分类，可以得到轨迹的期望形式：

$$\begin{array}{ll}\displaystyle \nabla_{\theta} J(\theta) &= \displaystyle \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{\infty} \gamma^t\nabla_{\theta} \log \pi_\theta(a_t|s_t) Q_{\pi_\theta}(s_t,a_t) \right]\\\\ &= \displaystyle \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{\infty} \nabla_{\theta} \log \pi_\theta(a_t|s_t) G_t \right]\end{array}$$

这是在说，每条轨迹的第 $t$ 步，处于状态 $s_t$，采取动作 $a_t$，其对数概率的梯度贡献为第一行式子，而另一方面

$$\begin{array}{ll}\mathbb E_{\tau}[\nabla_{\theta} \log \pi_\theta(a_t|s_t) Q_{\pi_\theta}(s_t,a_t)]&=\mathbb E_{\tau}[\nabla_{\theta} \log \pi_\theta(a_t|s_t) \mathbb E_{s_t,a_t}[G_t|s_t,a_t]]\\\\ &=\mathbb E_{s_t,a_t}[\mathbb E_{s_t,a_t}[\nabla_{\theta} \log \pi_\theta(a_t|s_t) G_t|s_t,a_t]]\\\\ &=\mathbb E_{s_t,a_t}[\nabla_{\theta} \log \pi_\theta(a_t|s_t) G_t]\\ \\ &=\mathbb E_{\tau}[\nabla_{\theta} \log \pi_\theta(a_t|s_t) G_t]\end{array}$$

这用到了重期望原理 (Law of Total Expectation)，即条件期望的期望等于总体期望。