【强化学习与最优控制】笔记（十四）Q-Learning，TD 与 近似线性规划

上一期笔记，忘记的童鞋可以复习一下：

王源：【强化学习与最优控制】笔记（十三）Actor-Critic Methods

如需获取电子版教材的同学可以从如下链接中获取：

Dimitri P. Bertsekas 强化学习2021版教材和视频课程推荐

这期笔记是我们这个系列最后一期，教材第6章主要是讲Aggregation，我不准备再写笔记了。另外第五章还有一点小尾巴也不准备更新了，主要原因在于进入第五章之后我对强化学习部分的理解十分有限，自然也写不出新东西了。后边有时间的话 我会先小补一下随机过程的内容，然后开始读 正经的强化学习圣经教材：Reinforcement learning: An introduction，就是Sutton那本教材了。相信接触过强化学习的童鞋都知道这本书的分量了。这本教材和我们现在笔记的教材虽然都是讲强化学习，但是看待问题的角度有着很大的不同。我目前还不能把这两个不同角度完全融会贯通，期待在下一系列的笔记中能有所进展。

本笔记对应教材中第5章5.4-5.6的内容。如需购买教材的童鞋请点击：

强化学习与最优控制（英文版）

本节笔记三个主题：1 Q-Learning；2 Temporal differences (TD)；3 近似线性规划。

1.1 Exact Q-Learning

先回顾一下 对于discount的问题最优的Q函数：

(1.1)

教材4.3节中给出了Q函数满足如下表达式：

(1.2)

为了简便起见我们为Q函数 定义 为 Bellman operator

(1.3)

采用Q函数的值迭代算法可以简单表示为：

和值函数迭代类似，我们在每次从 到 对Q函数进行迭代的过程也可以采样一部分状态和控制变量来进行迭代，也就是对式（1.3）的迭代公式进行一个改进：

（1.4）

其中

（1.5）

从上式可知每次迭代仅仅是更新一个采样点即可。

想要保住式（1.4）（1.5）的算法收敛一般需要两方面的条件：1是所有的 对可以产生无限长的样本序列 ，2是迭代步长 需满足一下条件：

(1.6)

式（1.6）的步长条件经常会在优化问题步长中出现，直观上的意思是步长既不能太大也不能太小。

在实际问题中Exact Q-Learning的算法缺点也是非常明显的，状态变量和控制变量 的数量往往是非常大的，这会导致计算量过大。下面我们介绍Approximation Q-Learning 算法。

1.2 Approximation Q-Learning 之 SARSA

在上一节的笔记中我们实际上通过Model-Free Critic-Only Method 里已经介绍了 关于Q函数的参数化近似。忘记的同学可以复习一下：

王源：【强化学习与最优控制】笔记（十三）Actor-Critic Methods

那我们这里的 Approximation Q-Learning 除了上面提到的 通过参数化来近似Q函数以外，还要通过采样的方法来近似优化问题的迭代求解。下面直接给出算法流程：

Step 1: 运行仿真环境 当前状态转移到下一个状态

Step 2：极小化当前近似Q函数得到下一拍的控制变量，如下所示：

Step 3：更新近似Q函数的参数：

Step 4： 都已经得到了，同时令 跳转Step1继续。

由于上面这个算法首先会得到下一个state，然后得到下一个action，接着通过对reward函数采样的极小化来更新Q函数的参数。所以这个算法也被称为 SARSA (State-Action-Reward-State-Action)

2.1 Projection by Monte Carlo Simulation

在这一小章节里我们将问题聚焦于采样线性函数来参数化近似 Policy evaluation 的过程。

首先定义一个子空间

其中 是一个 的矩阵，我们用 表示 矩阵第 列。

我们将 Value function 投影到子空间 上，相当于是在子空间 上找到一个对 Value function 的最好的近似。有如下表达式：

（2.1）

上式中之所以有 可以理解为加权的二范数。式（2.1）实际上就是在做投影，为了后边简便起见我们也用 表示将函数 投影到子空间 上。

式（2.1）所构成的问题是一个二次凸优化问题，直接通过求导就可以得到最优解：

（2.2）

从上式中可以看出 如果 比较大的话就很花费很多计算时间，那么通过上式直接求最优的方式就可能会很慢。

因此我们可以采用蒙特卡洛实验的方式来做一个近似：

(2.3)

(2.4)

其中 是通过仿真实验对 的近似。

通过式（2.3）（2.4）的蒙特卡洛实验的近似之后，我们将式（2.2）重新改写为：

(2.5)

将上式和式（2.1）对比就会发现实际上，上式也可以理解为对式（2.1）中 个求和中采样出一个 个样本的子集。

2.2 Temporal differences (TD)

在2.1小节中我们实际上还是近似的是Value function，进一步我们也可以考虑直接近似 Policy Evaluation之后的函数，也就是 ，用投影的方式简便表达如下：

(2.6)

进一步采用线性函数对 和 进行近似 带入到上式可得：

（2.7）

其中有如下定义：

（2.8）

上式可以理解为 mulitstep 的 Bellman equation，当 的时候上式退化为 Bellman equation。那么接下来的关键问题在于如何求解方程（2.7），很明显由于 这一项的存在导致方程（2.7）是一个非线性方程，一般情况下很难有解析解。因此首先通过采样的方式来近似 ，然后构造出如下的优化问题：

（2.9）

上式的优化问题是一个最小二乘问题，易知该优化问题有解析解。对该优化问题的求解大致有2个思路，1是直接采用解析解的形式该方法称之为 LSTD 方法，2是采用迭代算法，每次只从多个样本中选取一个出来更新参数 称之为 TD方法。这一思想在前面已经出现过好几次了，详细过程就不赘述了，可参考教材5.5小节。

3 Exact and Approximate Linear Programming

让我们的目光再次回答动态规划的问题中，在动态规划中我们关键的问题在于求解 Value function，而 最优的 Value function满足 Bellman equation:

（3.1）

通过 Bellman equation的启发，我们构造如下线性规划问题，这个线性规划问题的解和 Bellman equation的解是一样的：

(3.2)

s.t. (3.3）

首先我们先说明上面这个线性规划问题的解就是Bellman equation的解。从约束（3.3）可以看出线性规划的解是原来 Bellman equation 解的下界，同时从目标函数（3.2）可知我们是要在下界中找到一个最大的。易知这个最大的下界就是让约束（3.3）都取等号。由此可知上面（3.2）和（3.3）的线性规划的解就是 Bellman equation （3.1）的解。

分析上面的线性规划问题可以看出，线性规划约束的数量就是状态变量乘以控制变量的数量 ，若状态变量数量很大，这就会导致该线性规划问题约束过多 求解比较困难。若我们采用如下函数近似 Value function：

（3.4）

其中 是函数， 为参数。

将式（3.4）带入到（3.2）和（3.3）的线性规划，得到新的线性规划问题：

（3.5）

s.t. （3.6）

线性规划问题的决策变量为 ，一般来说参数 的维数是远小于状态变量数量 。其中集合 可以选择为状态变量的子集。相比原来的线性规划问题（3.2）和（3.3），也可以在一定程度上减少约束的数量。