什么是强化学习？（贝尔曼方程）

3.贝尔曼方程(Bellman equation)

贝尔曼方程表示上述状态价值函数与状态-行为价值函数之间的关系。贝尔曼方程有贝尔曼期望方程和贝尔曼最佳方程。

3.1贝尔曼期望方程(Bellman expectation equation)

贝明期望方程可将状态价值函数和状态-行为价值函数表示为期望值 $E$。状态价值函数的贝尔曼期望方程表示如下：
$$V_{\pi }(s)=\mathbb{E}\left[R_{t+1}+\gamma V_{\pi }\left(S_{t+1}\right)\mid S_t=s\right]$$当前状态 $S_t$ 的价值减价到下一状态 $S_{t+1}$的价值 $\gamma$ 乘以的期望值。
状态-行为价值函数的贝尔曼期望方程如下：
$$Q_{\pi }(s,a)=\mathbb{E}\left[R_{t+1}+\gamma Q_{\pi }\left(S_{t+1},A_{t+1}\right)\mid S_t=s,A_t=a\right]$$在当前状态 $S_t$上执行动作 $A_t$，这意味着期望补偿$R_{t+1}$加上下一个状态 $S_{t+1}$ 和动作 $A_{t+1}$的状态-动作价值乘以折扣率。
在状态价值函数中，可以将此期望值转换为遵循策略 $\pi$ 的状态-行为价值函数，如下所示：$$V_{\pi }(s)=\sum _{a\in A}\pi (a\mid s)Q_{\pi }(s,a)$$状态 $s$ 根据策略 $\pi$ 选择行为 $a$ 的概率乘以状态 $s$ 根据 $\pi$ 执行行为 $a$ 的价值。在此公式中，状态-行为价值函数也可以用状态价值函数重新求解。
$$Q_{\pi }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s,s^{\prime }}^a{V}_{\pi }\left(s^{\prime }\right)$$在当前状态 $s$ 中执行行为 $a$ 时，期望补偿和对下一状态 $s$ 的期望值乘以状态转移概率，并加上加上折扣。
将此公式代入上面的状态值函数：
$$V_{\pi }(s)=\sum _{a\in A}\pi (a\mid s)\left(R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s,s^{\prime }}^a{V}_{\pi }\left(s^{\prime }\right)\right)$$这样，在价值函数表达式中，模糊期望值表达式 $E$ 被减去并递归地表示。
类似地，状态-行为价值函数也可以递归地表示：
$$Q_{\pi }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s,s^{\prime }}^a\sum _{a^{\prime }\in A}\pi \left(a^{\prime }\mid s^{\prime }\right)Q_{\pi }\left(s^{\prime },a^{\prime }\right)$$
我们通过贝尔曼方程对状态价值函数和状态-行为价值函数进行了递归求解。

3.2 贝尔曼最优方程(Bellman optimality equation)

最佳状态价值和最佳状态-行动价值可以表述为：最佳价值是指在遵循可获得最大总回报的政策时所获得的价值。
$$\begin{array}{rl}{V}_{\ast }(s)& =\underset{\pi }{\max }{V}_{\pi }(s)\\ Q_{\ast }(s,a)& =\underset{\pi }{\max }{Q}_{\pi }(s,a)\end{array}$$在 $V$ 和 $Q$ 上加上星星（*）表示最佳价值。
用贝尔曼最佳方程表示最佳价值和最佳行动价值：
$$\begin{array}{c}{V}_{\ast }(s)=\underset{a}{\max }{R}_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s,s^{\prime }}^a{V}_{\ast }\left(s^{\prime }\right)\\ Q_{\ast }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s,s^{\prime }}^a{V}_{\ast }\left(s^{\prime }\right)\end{array}$$

4. $MDP$ 的动态编程(dynamic programming)

4.1 $MDP$

让我们看一下使用达伦贝尔曼方程求解 $MDP$ 的动态编程。动态编程（Dynamic Programming，DP）是一种解决递归优化问题的方法，DP由策略迭代和价值迭代组成。
重复策略（policy iteration）
重复策略将重复刷新状态价值函数，如下所示：
$$V_{k+1}(s)=\sum _{a\in A}\pi (a\mid s)\left(R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s,s^{\prime }}^a{V}_k\left(s^{\prime }\right)\right)$$
其中 $k$ 表示重复过程。重复 $N$ 次更新价值函数V以创建$V_1、V_2、\dots 和V_N$。这与贝尔曼期望方程的形式相同。
我们将重新导入上面的 $MDP$ 示例。以下是3x3网格区域中的策略
最初，我们允许在所有状态下以相同的0.25概率执行所有操作。未应用折扣。即，即 $\gamma$=1。
到达陷阱时-0.1，到达目的地时奖励1。现在，让我们看一下重复刷新状态价值函数会发生什么。
下面显示了状态价值函数在策略重复过程中的变化

策略迭代中的状态值函数变化。当 k=8 时，策略可以更新为

基于状态价值函数的策略更新
如果下一个状态具有与基于状态价值函数的策略更新相同的价值，则可以赋予相同的概率，使其移动到具有最高价值的状态。价值重复（value iteration）价值重复类似于策略重复。区别在于，我们首先来看一下价值重复的公式
$$V_{k+1}(s)=\max a\in A{R}_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s,s^{\prime }}^a{V}_k\left(s^{\prime }\right)$$在策略重复中，我们将以下状态的价值乘以策略函数的概率相加，而在策略重复中，我们贪婪地选择最大的下一个价值。从公式可以看出，只有贝尔是最佳方程。在策略重复中，我们更新了状态价值函数，随后又更新了策略；而在价值重复中，我们没有单独更新策略的步骤。价值循环假定当前的策略是最佳的，并获得最大的补偿。

下面的示例显示了重复值状态价值函数在上述相同示例中的变化情况：

4.2.动态规划的局限性以及为什么需要强化学习

动态规划很难应用于大多数现实世界的问题，其中状态转移概率和奖励函数在现实中无法提前知道，因为必须给出 MDP 的状态转移概率和奖励函数。

这个问题定义得非常好，即使状态转移概率和奖励函数是已知的，随着状态数量的增加，也很难实际求解贝尔曼方程。
这使得很难将动态规划应用于大多数实际问题，其中状态转移概率和奖励函数事先不知道并且状态是无限的。这些缺点可以通过处理强化学习的问题来克服。