Mathematics foundation of reinforcement learning - Part 3 强化学习笔记3

Syllabus

Chapter 6 Stochastic Approximation

这一章节主要是为了后续介绍Temporal-difference（TD）算法做准备

Robbins-Monro algorithm

先上一个直观的表现如下

可以看到通过迭代，从w1收敛到了w使得g(w)=0，那也就求得了E[W]的值

假设我们要求一个方程 g(w) = 0 的解，由于是model free，我们只能根据观察值来求解

将g(w)写为

• w_k 为 第k个估计值
• g(w_k, η_k)为噪音值，而这个噪音值也可以写作一个关于w_k的函数

可以看到，这个算法最关键的就是这个a_k的值，即每一次往目标值w*靠近多少

下面给出这个算法的成立条件是

• 条件(a) 这个说明的是函数g(w)的梯度是正的，即单调增的，保证g(w)=0一定有解，且小于c2，表示函数不是发散的
• 条件(b) 这个ak可以理解为步长
  • a_k^2趋向于0，这个比较好理解，即a_k最终会趋向于0，也就是说w_{k+1} → w_k
  • a_k 的和不趋向于0，通过如下式子，如果a_k累积和是有界的，那么最终点到初始点点距离也是有界的，而初始点是随机值，所以如果这个累积和有界，那说明当初始点选择不够优秀的时候，无法得到正确的w*。

• 条件(c)
  • 第一部分表示噪声 η 的期望是 0，即算法不会像错误方向收敛。
  • 第二部分，表示噪声幅度不会太大，即不会对更新方向造成干扰

Stochastic gradient descent 随机梯度下降 以及 BGD，mini-batch GD, SGD

我们使用一个例子来理解这个，假设我们有如下函数

我们希望求这个w，使得函数J(w)为最小值

Method 1: Gradient Descent (GD)

一个直接的办法就是直接对函数求导，当然这个必须是在有模型即有函数的情况下才能完成。

Method 2: Batch Gradient Descent

这个与蒙特卡洛算法思想类似，当没有模型model free的情况下，对于期望值，可以使用求平均的办法求得，这个的主要缺点是每次计算都需要采集n个样本效率较低。

Method 3: Mini-batch GD

这个相较于BGD的优势就在于，他取m个样例取平均作为估计的期望值，算是介于BGD和SGD中间的一个算法

Method 4: Stochastic Gradient Descent

而SGD算法，则直接取样例wk，xk，通过不断迭代逼近最终值wk

⚠️注意，这里的ak需要满足平方和收敛为0，但和发散