【强化学习与最优控制】笔记（十四）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函数：

$Q^*\left( i,u \right) =\sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +\alpha J^*\left( j \right) \right)}$ (1.1)

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

$Q^*\left( i,u \right) =\sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +\alpha \underset{v\in U\left( j \right)}{\min}Q^*\left( j,v \right) \right)} \;\;\;\;\forall (u,i)$ (1.2)

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

$\left( FQ \right) \left( i,u \right) =\sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +\alpha \underset{v\in U\left( j \right)}{\min}Q\left( j,v \right) \right)}\;\;\;\;\forall (u,i)$ (1.3)

采用Q函数的值迭代算法可以简单表示为： $Q_{k+1}=FQ_k$

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

$Q_{k+1}\left( i,u \right) =\left( 1-\gamma ^k \right) Q_k\left( i,u \right) +\gamma ^k\left( F_kQ_k \right) \left( i,u \right) \;\;\;\;\forall (u,i)$ （1.4）

其中

$\left( F_kQ_k \right) \left( i,u \right) =\left\{ \begin{array}{l} g\left( i_k,u_k,j_k \right) +\alpha \underset{v\in U\left( j_k \right)}{\min}Q_k\left( j_k,v \right) \,\,\,\,if\ \left( i,u \right) \in \left( i_k,u_k \right)\\ Q_k\left( i,u \right) \,\,\,\,if\ \left( i,u \right) \notin \left( i_k,u_k \right)\\ \end{array} \right.$ （1.5）

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

想要保住式（1.4）（1.5）的算法收敛一般需要两方面的条件：1是所有的 $(i,u)$ 对可以产生无限长的样本序列 $\left\{ (i_k,u_k)\right\}$ ，2是迭代步长 $\gamma^k$ 需满足一下条件：

$\gamma^k>0, \;\;\sum_{k=0}^{\infty}{\gamma^k}=\infty,\;\;\sum_{k=0}^{\infty}\left({\gamma^k}\right)^2=\infty$ (1.6)

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

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

1.2 Approximation Q-Learning 之 SARSA

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

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

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

Step 1: 运行仿真环境当前状态转移到下一个状态 $\left( i_k,i_{k+1} \right)$

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

$u^{k+1}\in arg\underset{u\in U\left( i^{k+1} \right)}{\min}\tilde{Q}\left( i^{k+1},u,r^k \right)$

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

$r^{k+1}=r^k-\gamma ^k\nabla \tilde{Q}\left( i^k,u^k,r^k \right) \left( g\left( i^k,u^k,i^{k+1} \right) -\alpha \tilde{Q}\left( i^{k+1},u^{k+!},j^k \right) \right)$

Step 4： $i^{k+1},u^{k+1},r^{k+1}$ 都已经得到了，同时令 $k=k+1$ 跳转Step1继续。

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

2.1 Projection by Monte Carlo Simulation

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

首先定义一个子空间 $M=\left\{ \Phi r |r\in R^m \right\}$

其中 $\Phi$ 是一个 $n\times m$ 的矩阵，我们用 $\phi(i)$ 表示 $\Phi$ 矩阵第 $i$ 列。

我们将 Value function $J\left( i \right)$ 投影到子空间 $M$ 上，相当于是在子空间 $M$ 上找到一个对 Value function 的最好的近似。有如下表达式：

$r^*\in arg\underset{r\in R^m}{\min}\sum_{i=1}^n{\xi _i\left( \phi \left( i \right) 'r-J\left( i \right) \right) ^2}$ （2.1）

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

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

$r^*=\left( \sum_{i=1}^n{\xi _i\phi \left( i \right) \phi \left( i \right) '} \right) ^{-1}\sum_{i=1}^n{\xi _i\phi \left( i \right) J\left( i \right)}$ （2.2）

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

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

$\sum_{i=1}^n{\xi _i\phi \left( i \right) \phi \left( i \right) '} \approx \frac{1}{q}\sum_{s=1}^q{\phi \left( s \right) \phi \left( s\right) '}$ (2.3)

$\sum_{i=1}^n{\xi _i\phi \left( i \right) J\left( i \right)}\approx\frac{1}{q}\sum_{s=1}^q{\phi \left( s \right) \beta^s}$ (2.4)

其中 $\beta^s$ 是通过仿真实验对 $J(i^s)$ 的近似。

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

$\bar{r}=\left(\sum_{s=1}^q{\phi \left( s \right) \phi \left( s\right) '}\right)^{-1}\sum_{s=1}^q{\phi \left( s \right) \beta^s}$ (2.5)

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

2.2 Temporal differences (TD)

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

$\tilde{J}_{\mu}\approx\prod_{}^{}(T^N_\mu \hat{J})$ (2.6)

进一步采用线性函数对 $\tilde{J_{\mu}}$ 和 $\hat{J}$ 进行近似带入到上式可得：

$\Phi r=\prod_{}^{}(T^\lambda_\mu \Phi r)$ （2.7）

其中 $T_{\mu}^\lambda$ 有如下定义：

$\left( T_{\mu}^{\lambda}J \right) \left( i \right) =\left( 1-\lambda \right) \sum_{l=0}^{\infty}{\lambda ^l\left( T_{\mu}^{l+1}J \right) \left( i \right) ,\,\,\,\,i=1,...,n}$ （2.8）

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

$\bar{r}\in arg\underset{r}{\min}\left( \phi \left( i^s \right) 'r-sample\ of\ \left( T_{\mu}^{\lambda}\Phi r \right) \left( i^s \right) \right) ^2$ （2.9）

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

3 Exact and Approximate Linear Programming

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

$J^*\left( i \right) =\sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +\alpha J^*\left( j \right) \right)}$ （3.1）

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

$\max \sum_{i=1}^n{J\left( i \right)}$ (3.2)

s.t. $J\left( i \right) \le \sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +\alpha J\left( j \right) \right)},\ \forall i=1,..,n\,\ u\in U(i)$ (3.3）

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

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

$\tilde{J}\left( i,r \right) =\sum_{l=1}^m{r_l\phi _l\left( i \right)}$ （3.4）

其中 $\phi_l$ 是函数， $r$ 为参数。

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

$\underset{r}{\max}\sum_{i\in I}{\tilde{J}\left( i,r \right)}$ （3.5）

s.t. ${\tilde{J}\left( i,r \right)}\le \sum_{j=1}^n{p_{ij}\left( u \right) \left( g\left( i,u,j \right) +\alpha {\tilde{J}\left( i,r \right)} \right)},\ \forall i \in I,u\in U(i)$ （3.6）

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