贝尔曼算子(Bellman Operators)与动态规划

Posted on Edited on In Views:

这篇博客介绍了强化学习中的Bellman算子以及使用Bellman算子来解释动态规划的迭代过程。

原本内容来自Stanford大学Ashwin Rao老师的lecture ：Understanding (Exact) Dynamic Programming through Bellman Operators，本篇博客是这个lecture的翻译/整理/学习笔记，包括以下七个部分

  1. 值函数的向量描述
  2. Bellman算子
  3. 算子的收缩性的单调性
  4. 策略评估
  5. 策略迭代
  6. 值迭代
  7. 策略最优性

值函数的向量描述

假设：状态空间由个状态构成：；动作空间由个动作构成：

我们将一个随机策略记为，表示状态时执行动作的概率；确定性策略可以记为.

考虑一个维的空间，每个维度对应中的一个状态，考虑任意一个值函数（Value Function,VF），是这个空间中的一个向量，其坐标为.

对于策略，其VF可以记为.

最优的VF，记作，满足：

此外还有以下一些记号：

​ ：状态时执行动作时所获得的期望reward

​ ：动作时，状态转换

​ 定义记号：

​ ，表示状态下的期望reward

​ ，表示状态转移的概率

​ 记为向量

​ 记为矩阵

​ 记为MDP的折扣因子

Bellman算子和

定义表示一个VF向量到另一个VF向量的算子，贝尔曼策略算子（Bellman Policy Operator for policy ） ，作用在一个VF向量上：

​

是一个线性算子，有不动点（fixed point），即

作用在VF向量的贝尔曼最优算子（Bellman Optimality Operator）：

​

是一个非线性算子，有不动点，即

定义一个函数，按照如下规则将一个VF向量映射到一个确定性的“贪婪”策略：

​

对于任意的VF，有，也即：策略达到了的最大值。这实际上就是贝尔曼最优方程（Bellman Optimality Equation）使用Bellman算子的简洁表示。证明如下：

由于为确定性策略，则对于任意

​

算子的收缩性和单调性

在范数下，和都是收缩的算子，即：对于任意两个VF向量和，

​

​

这说明了和都是压缩映射，因此我们可以使用压缩映像原理来求不动点。

我们使用记号来表示： .在此之上，我们得到：和都是单调的，也即：对于任意两个VF向量和，有

​

​

策略评估

满足压缩映像原理的条件，那么其有唯一的不动点.

这个不动点式子事实上就是贝尔曼期望方程（Bellman Expectation Equation）使用Bellman算子的简洁表达。

那么，对于任意VF向量，我们重复应用，就会得到，完成策略评估。也即：

上面这个式子就是策略评估算法（Policy Evaluation Algorithm）使用Bellman算子的简洁表示

策略迭代

策略改进

首先规定记号：,表示第次策略迭代得到的策略和VF向量

策略改进的步骤为：，得到的是一个确定性策略（对于当前值函数的贪心策略）。

根据之前的讨论，我们知道：

再由Bellman算子的定义：，有

由以上两个式子，可以得到

由算子的单调性：

因此：. 这说明了策略改进的可行性

策略迭代

我们已经说明了在第次策略迭代后，有：

如果，这意味着，而算子有唯一不动点，则说明.

这说明了，在每次迭代的过程中，要么能够改进VF，要么能够达到最优的VF

值迭代

满足压缩映像原理的条件，其有唯一不动点，这是贝尔曼最优方程的一个简洁表达（Bellman Optimality Equation）

因此，从任意的VF向量开始，重复使用算子，就会得到

​

这就是值迭代算法（Value Iteration Algorithm）的一个简洁表示。

贪心策略最优性

已知：

其中是的不动点，则

再由的不动点，得

上式说明了，按照最优值函数得到的贪心策略，能够实现最优的值函数

换句话讲，也就是：是最优的（确定性）策略