定义#

1. 回报（Return）和价值（Value）

我们定义回报 (Return) 。这是 Agent 从时刻 开始，一直持续到未来所能获得的折扣累计奖励：

• ：执行动作后的即时奖励（reward）。
• ：折扣因子（Discount Factor）。
• 注：奖励（reward）是即时的，回报（return）是累计的。

这里面可以用递归的技巧写出：

2. 状态价值函数（State Value）

状态价值函数 定义为：在状态 下，遵循策略 能获得期望回报（average return）。

• 这里是回报（全局概念）而不是奖励（reward）

3. 动作价值函数（Action Value）

在状态 下，遵循策略 采取动作 ，能获得期望回报（average return）。

• 和 State Value 的差异就是它选择了一个 action

因此：

‍

推导#

基于上述定义，我们将 的递归形式代入价值函数的定义，进行展开。

这里分出来两个期望，分别是下一步的即时 reward 和未来的 return

1.

• 第一步：由于 是个策略函数，输出多个动作，而每个动作都是一个可能性，因此 需要拆成对每个动作进行求和， 是在状态 下，选择动作 的概率

• 第二步： 是一个环境反馈项

  • 是状态 和动作 下，环境给予的奖励（reward）
  • 自不必说，是这个奖励 的概率

‍

2.

这里的遍历性（期望如何展开）在于，在 下还能去哪些状态 ，和 1 一样，我们自然而然的对下一状态 进行展开：

这里还存在期望项没有展开完，我们还需要继续进行，而由于 RL 算法一般假设马尔可夫过程，因此在求 期望时， 是不必要的，因此又可写成：

这里面有个容易注意到的事实（但我来说难以注意）， 恰好是我们刚刚定义的 ，其意义是站在 状态下的期望回报，只需换成 ，于是我们写成（又一递归形式）：

但这并非我们想要的项，因为 包含 ，而对于一个站在状态 的智能体来说，是只能通过某个动作 转换到 ，因而我们需要把 转成如此形式：

分别是状态 下，采取动作 能够到 的概率，以及状态 下，策略 能够生成动作 的概率，其实就是 到 的所有路径概率之和，最后代回得到：

‍

3. 贝尔曼方程

上面求的所有中间结果代回：

我们发现里面都有 ，直接提出（求和）：

这就是贝尔曼方程

‍

注意这是个递推式，只描述了状态 下如何求价值函数，要求解需要对每个状态列出方程组成方程组求解。

‍

‍

其次，把 提出写成这样的形式是有一定的妙处的，可以发现 是一个策略，而方括号里面都是价值，包括了即时和未来两项，我们回到动作价值的定义，后面就是 Action Value：

‍

矩阵表示#

由于我们上面求出的是个递推式，为了全局求解，我们实际上需要列出方程组，因此先推导矩阵表示，我们回到提出 之前，引入记号代表两项

1. 即时奖励部分

2. 未来回报部分

有了这两个记号原来的方程可以简化为：

再写成向量表示：

价值向量 ()：

奖励向量 ()：

转移矩阵 ()：第 行第 列的元素

于是直接写成：

由于 和 都是已知的（假设我们知道环境），上面又是线性方程组，可以直接推导解析解：

但实际中解析解通常求不出来，原因如下：

1. 如果 很大，矩阵求逆会非常困难，复杂度 ，而实际问题中， 一般都很大
2. 有时我们不知道 和 是什么，或者难以模拟，被称为 Model-Free 场景

‍

于是我们需要一种迭代求解方法

‍

贝尔曼最优方程 bellman optimal equation#

首先我们定义何为最优 ， 这和博弈论的优势策略是一样的：

我们就说策略 优于或等于

基于此，我们要寻找的最优状态价值函数 定义为所有可能策略下的最大值：

这就引出几个问题：

1. 这样的策略是否存在？
2. 这样的策略是否唯一？
3. 这样的策略是随机策略还是确定性策略？
4. 如何达到这样的策略？

‍

我们继续用上面矩阵表示的记号，对于任意固定策略 ，价值函数满足线性方程：

观察上式，实际上的未知变量只有 ，我们可以看作是：

其中：

这个形式可以用不动点定理，需证明 是个收缩映射：

对于任意两个价值向量 和 ，满足：

详细证明略

‍

由此，我们可知解存在，并可以采用迭代方法求解：只需要随机初始化一个 ，不断应用函数 ，足够多步后我们能够得到最优的