强化学习数学基础（6）

写在前面

该系列是作者学习西湖大学赵世钰老师的《强化学习的数学原理》这一课程所总结的知识点。

回顾

在上一章节，我们介绍了Temporal-Difference算法，其建立在stochastic approximation的基础上，用于在policy evaluation步骤中对action value进行model-free地估计，以搜索optimal policy。从最常见的Sarsa算法到其各种变体，如Expected Sarsa、N-step Sarsa以及Q-learning，其本质是TD target的不同；但在之前，我们接触的state-action pairs都是tabular型，如果state或者action空间很大呢？我们就没法用tabular去表示，怎么办？本章将从tabular representation转变为function representation，以解决该问题；目标同样还是对估计action/state value，所以本章节主题是value function approximation。

Algorithm for state value estimation

在之前的章节，我们估计 ，是怎么表示的呢？横轴表示不同的state ，纵轴表示不同的action ，表格内代表action value。其优点在于比较直观且便于分析，缺点在于如果状态或者动作空间很大，这种表达形式则会受限，并且我们也很难对每一个state-action pairs都会有visit。怎么办？

我们采用function的表达形式，例如定义函数 ，学习函数令 。这样的好处有两点：1）能够表达大空间，甚至连续值；2）具有泛化能力，比如更我们逼近 时，函数中参数改变，从而也会影响其他state-action的估计，即具有泛化性。

Objective function

令 和 分别表示state value的真实值和函数近似值，其中 表示函数参数；目标是找到最优的 能使 最好地近似 。

首先，需要定义一个目标函数；然后，寻找算法解决该目标函数。

目标函数如下：

上式是期望的形式，其中随机变量是 ，有几种方式去定义它的分布：

• Uniform distribution：假设均匀分布，相当于认为状态空间中的所有状态同等重要，这种情况下，上式变为：

  其劣势正在于将所有状态同等看待，例如，存在一些状态很少会被visit，那么这些状态是否可以适当降低权重，转而关心函数对于那些经常被visit的状态的近似呢？

• Stationary distribution：引入这个概念，stationary意味着稳定的、收敛的，本质上它是描述一个markov process的长期行为（long-run behavior）。定义 表示markov process在policy 下的stationary distribution。根据定义，有 且 。

  这种情况下，目标函数为如下形式：

  它解决了uniform distribution情况下存在的问题，采用加权平均的形式，对于经常visit的state，其权重 更高。

  关于stationary distribution，其与系统的转移概率分布满足： 。

Optimization algorithms

介绍过了目标函数，下一步就是给出优化算法以逼近目标。为了优化 ，很自然可以想到gradient-descent方法：

而：

借助在SA章节中所介绍的stochastic gradient算法，可通过下式迭代求解：

其中： 是 中的一个样本；

但由于我们并不知道 ，所以上述迭代式仍不可实现。怎么办？我们在前些章节介绍了评估state/action value，总结下来可以分为两大类，四种方法：

• model-based情况

  • Closed-form solution： ，在model-based的情况下，我们知道immediate reward的概率分布 和状态转移概率分布 ，因此我们可以求解该bellman equation的闭式解，即 ；
  • Iteration solution：由于求解闭式解需要求解矩阵的逆，因此计算量很大；还有一种迭代式的求解方案，即 ，这种方法为何会收敛？具体证明请看我们前面的章节，关键在于构造序列，并证明序列的收敛性。

• model-free情况

  • Monte Carlo learning：令 为从状态 开始出发的discounted return，那么 就可以用于近似 ，上式就变为：

  • TD learning：由于Monte Carlo learning只有等episode结束才能计算，效率很低；在上一章节，我们介绍了TD算法，可以用于估计state value：

Selection of function approximators

关于近似函数有多张选择，以linear function为例：

其中： 表示特征提取器，例如可以是多项式的、Fourier basis等；

那么： ，则TD算法即为：

但Linear function的近似能力毕竟较弱，而且难点在于feature vector 很难选择，除非对有足够坚定的先验和领域知识。

相比之下，我们更通常使用NN来进行函数近似，后面会详细介绍；

回顾我们上面的内容，第一步选择objective function；第二步给出合适的optimization algorithm去优化它。整体比较好懂，但其实理论上并不严密。下面介绍几种不同的目标函数：

• True value error

• Bellman error

• Projected Bellman error

  其中: 为映射矩阵

Sarsa with function approximation

前面我们介绍了，用函数去近似state value，即从tabular representation转变为function representation。并基于目标函数去优化函数的参数，现在我们思考如何将其嵌入到policy iteration中的进行policy evaluation以实现搜索最优策略呢？

以Sarsa为例，但Sarsa算法内是需要计算action value，我们类比一下，也可以使用函数近似action value:

给出pseudocode如下（详看：https://github.com/MathFoundationRL/Book-Mathmatical-Foundation-of-Reinforcement-Learning/blob/main/Lecture%20slides/L8_Value%20function%20approximation.pdf，）：

Q-learning with function approximation

如何把函数近似和Q-learning结合呢？我们知道Q-learning相比于Sarsa，主要在于TD target的区别，Q-learning是直接学习贝尔曼最优等式，以得到最优策略，是off-policy的，当然，它也可以on-policy的形式进行学习。

在Q-learning中，函数参数更新规则如下：

其pseudocode如下：

Deep Q-learning

Deep Q-learning or Deep Q-network (DQN)是最早将深度神经网络引入到RL中，利用深度神经网络优秀的你和能力；

DQN的目标函数为：

其中： 表示随机变量

其本质是Bellman optimality error，这是因为：

如何优化以上目标函数？还是使用gradient densecent

我们可以发现在目标函数中，参数 不仅出现在 中，还出现在 ，即target中；这样求导会很复杂，为了简化，这二者采取异步更新的措施，这也是DQN中的tricky之处。

为了实现异步更新，DQN中引入两个网络：

• main network：用于表征
• target network：用于表征

这种情况下，目标函数可以写为：

在具体更新中，main netwotk一直更新，而target network中的 是固定的；一段周期 后，将main network中的参数再赋予给target network。

两个网络是DQN的第一个tricky，此外还有经验重放（experience replay）技巧。即当我们收集到experience sample后，我们并不会按照收集时候的order去使用这些样本，替代的是，将它们放在一个集合中，叫做replay buffer 表示样本的组织形式，每次训练NN，我们从其中随机采样出mini-batch进行更新。

从experience replay进行采样必须是均匀的吗？ 中随机变量有 ，按照期望的定义，我们是需要进行均匀采样，除非有很强的先验知识；

DQN的pesudocode如下：

Summary

在本章中，我们将state/action value的表征由tabluar转变为function；如何用function去近似估计呢？首先需要定义一个目标函数，其次对目标函数进行求解。对目标函数求解的方法还是基于我们在SA章节中介绍的SGD方法，近似后，我们可以继续将得到的action value嵌入到寻找最优策略的算法中，如Sarsa、Q-learning、Deep Q-learning；DQN是最早将深度神经网络引入到RL算法中的工作，其包含两个技巧：1、main network and target network，2、experience replay。