强化学习数学基础（4）

写在前面

该系列是作者学习西湖大学赵世钰老师的《强化学习的数学原理》这一课程所总结的知识点，通过记录课程笔记加深印象，以及建立起自己的知识框架。

回顾

在上一章节中，我们第一次进入了model-free的世界。如何求解最优贝尔曼等式呢？在model-based中，我们知道环境的概率分布，因此可以求解state-value（在policy iteration算法中）；在model-free中，我们回归到action value的定义，即 ，本质是估计期望。

由此引入model-free estimation工具，Monte carlo估计方法。其理论基础为大数定律，进一步的，将该方法应用于RL中求解bellman optimality equation，介绍了MC basic算法。在其基础上，为了充分利用数据，引入MC explore starts算法和MC 算法。

在本章节介绍随机近似理论和随机梯度下降，介绍该章是为了介绍接下来RL中重要的时间差分理论埋下基础；同时它也衔接上一章，Monte carlo estimation可以看作是本章随机近似理论的一个特例。

Stochastic Approximation

回顾mean estimation问题，使用Monte carlo方法：

这是monte carlo算法的核心，但其有个劣势在于，如果样本是序列产生的，那么只能等到序列结束才会估计。怎么解决这个问题呢？

所以， 能够由 表示：

这样，我们就可以用 去增量的计算 的均值。即使在刚开始的时候数据不会很准确，但随着过程的进行，其会逐渐变得更加准确。

上式作为一个例子，考虑一个更通用的表达：

其中 被替换为 ；那么其是否还会得到准确的估计呢？其实这正是一种我们接下来所要介绍的一种特殊的SA算法，也是一个特别的stochastic gradient descent算法。

Robbins-Monro algorithm

SA算法表示一类随机迭代解决求根问题（root-finding）或者优化问题的算法；本节所介绍的Robbins-Monro（RM）算法是SA中的开创性工作，著名的随机梯度下降算法本质是RM的一种特殊形式。

求根问题即：

其中 是待求解的变量， 表示函数。

• 求根问题在实际中应用广泛，很多问题最终都能转化为求根问题，例如， 是需要最小化的目标函数，则优化问题可被转化为
• 常见的等式问题如 也可通过 转化为root finding问题;

那么如何求解上述问题呢？

• 如果我们知道函数形式，我们可以通过求解closed-form solution或者通过gradient descent方法求解；

如果函数形式不知道怎么办？Robbins-Monro算法适用于解决该问题。具体形式为：

其中：

• 表示根的第 次估计；

• 表示第 次带噪声的观察；

• 表示正系数

• 表示黑盒模型，RM算法依赖：

  • Input sequence：
  • Noisy output sequence:

  再次验证了数据科学的信条，没模型就需要数据，没数据就需要模型，至少有一个。

收敛分析

Theorem（Robbins-Monro Theorem）

In the Robbins-Monro algorithm, if

1. for all ；

   • 表示 函数单调递增，这保证了根的存在性和唯一性；
   • 梯度 有界；
2. And

   • 表示 ,
   • 条件 表示 收敛速度较慢；
3. and

   • 如果 是iid序列，满足 并且 ，即方差有界

where , then converges with probability 1 (w.p.1) to the root satisfying

回顾在mean estimation问题中，迭代式算法 中的 满足关于 的条件2；接下来介绍该迭代式算法正是RM算法的应用。

1、考虑函数 ；目标为求解求根问题 ，则得到的 自然为所估计的 。

2、对于上述函数，因为我们只能得到 的观察，即

上式可写为

3、应用RM算法求解上述问题，迭代式为

Stochastic gradient descent

SGD广泛应用于深度学习中，是一种梯度更新算法，从SA的视角，SGD其实是一种特殊的RM算法。

假设我们要求解如下优化问题：

应用梯度下降来求解该问题，有三种方式：

1、Gradient descent（GD）

它的缺陷在于期望值很难求取，因为我们不知道分布的具体形式；

2、batch gradient descent（BGD）

用monte carlo思想，进行近似；其缺陷在于在每次迭代 时，需要大量样本。

3、stochastic gradient descent（SGD）

相比于BGD，SGD就是令 。所以SGD从形式上看就是mean estimation 算法，或者mean estimation algorithm本质就是一种特殊的SGD algorithm。

那么SGD每次只用一个样本，如何证明当 时， 呢？我们只需要证明SGD是一种RM算法，因为RM能够收敛，则SGD也会收敛。

回顾SGD的目标是要最小化： ，这个问题也可以转化为求根问题，即

令 ，那么我们对:

其中：

那么，按照RM算法解求根问题的迭代式，即：

Theorem(Convergence of SGD)

In the SGD theorem, if:

1、 （对应RM中的条件1）

2、 And （对应RM条件2）

3、 is iid（只有 是iid，才有 ）

总结

在本章节中，我们引入了随机近似理论。这是承上启下的章节，上一章节的monte carlo算法，是我们介绍的model-free的估计方法，可以用于估计期望，如policy iteration中估计action value 。但monte-carlo方法有个问题，即每次需要在序列结束才能计算，因此为了解决这个问题，我们给出迭代式的mean estimation方法：

进一步的，我们引入SA理论中开创性工作Robbins-monro算法，mean estimation是其中一个特例，即求解 这样的一个求根问题；我们证明在满足一些约束的情况，RM可以通过以下方式来解决求根问题：

其最大的好处是：1、求根问题在实际中比较常见，一些其他问题通常也可以通过一些转换变化成求根问题；2、RM算法不需要知道函数的具体形式，就可以进行求解；

进一步的，我们介绍SGD本质上也是RM算法的一个特例，最小化目标函数的优化问题也可以转化为求根问题，即令一阶导为0；当满足RM算法的约束条件，SGD可以通过下式进行求解：

以上，可以看出RM算法应用广泛，事实上这是在很多领域都得到应用的重要优化技术。