目录
系列笔记:
【强化学习的数学原理】课程笔记–1(基本概念,贝尔曼公式)
【强化学习的数学原理】课程笔记–2(贝尔曼最优公式,值迭代与策略迭代)
【强化学习的数学原理】课程笔记–3(蒙特卡洛方法)
随机近似与随机梯度下降
这个部分主要是为了下一章 时序差分方法 做铺垫,其内容也适用于机器学习等方向。
Mean estimation
上一节 中我们已经讨论过,在 model-free 的情况下,为了求解
q π k ( s , a ) = E [ G t ∣ S t = s , A t = a ] q_{\pi_k}(s,a) = E[G_t | S_t = s, A_t =a] qπk(s,a)=E[Gt∣St=s,At=a]
我们需要利用 大数定律 的结论,通过大量的采样 g π k ( i ) ( s , a ) , i = 1 , 2 , 3... g^{(i)}_{\pi_k}(s,a), i = 1,2,3... gπk(i)(s,a),i=1,2,3...,来估计 q π k ( s , a ) q_{\pi_k}(s,a) qπk(s,a):
q π k ( s , a ) = 1 n ∑ i = 1 n g π k ( i ) ( s , a ) q_{\pi_k}(s,a) = \frac{1}{n} \sum_{i=1}^n g^{(i)}_{\pi_k}(s,a) qπk(s,a)=n1i=1∑ngπk(i)(s,a)
我们将上述问题简记为:
E ( X ) ≈ x ˉ = 1 n ∑ i = 1 n x i E(X) \approx \bar{x} = \frac{1}{n} \sum_{i=1}^n x_i E(X)≈xˉ=n1i=1∑nxi
上述式子在实际中有一个效率的问题:需要等到所有的样本 x i x_i xi 全都采集完毕才能计算。而上述式子有一个 等价 的迭代式子:
w k + 1 = w k − 1 k ( w k − x k ) w_{k+1} = w_k - \frac{1}{k} (w_k -x_k) wk+1=wk−k1(wk−xk)
其中 w k = 1 k − 1 ∑ i = 1 k − 1 x i w_k = \frac{1}{k-1} \sum_{i=1}^{k-1} x_i wk=k−11∑i=1k−1xi 。证明也很容易:
w k + 1 = 1 k ∑ i = 1 k x i = 1 k ( ∑ i = 1 k − 1 x i + x k ) = 1 k ( ( k − 1 ) w k + x k ) = w k − 1 k ( w k − x k ) w_{k+1} = \frac{1}{k} \sum_{i=1}^{k} x_i = \frac{1}{k} (\sum_{i=1}^{k-1} x_i + x_k) = \frac{1}{k} ((k-1)w_k + x_k) = w_k - \frac{1}{k} (w_k -x_k) wk+1=k1i=1∑kxi=k1(i=1∑k−1xi+xk)=k1((k−1)wk+xk)=wk−k1(wk−xk)
作为上式的延展,我们提出一个更广泛使用的迭代式:
w k + 1 = w k − α k ( w k − x k ) w_{k+1} = w_k - \alpha_k (w_k -x_k) wk+1=wk−αk(wk−xk)
在下面的 Robbins-Monro 算法 中,我们会展示:在满足一定条件时,上式依然满足 lim k → ∞ w k = E [ X ] \lim_{k \rightarrow \infin} w_k = E[X] limk→∞wk=E[X]
Robbins-Monro 算法
Robbins-Monro 算法提出了以下框架:
要求解 g ( w ) = 0 g(w) = 0 g(w)=0
如果不知道 g g g 的具体形式,但可以拿到足够多的采样 g ( w k ) , k = 1 , 2 , 3... g(w_k), k = 1,2,3... g(wk),k=1,2,3...,那么可以用迭代式:
w k + 1 = w k − a k ( g ( w k ) + η k ) , a k > 0 w_{k+1} = w_k - a_k (g(w_k) + \eta_k), \quad a_k > 0 wk+1=wk−ak(g(wk)+ηk),ak>0
来求解,其中随机变量 η ∈ R \eta \in \mathbb{R} η∈R 是观测误差。当以下条件满足时,可以保证 w k w_k wk 收敛到 w ∗ w^* w∗ ( w ∗ w^* w∗ 满足 g ( w ∗ ) = 0 g(w^*) = 0 g(w∗)=0):
\quad
- 0 < c 1 ≤ ∇ w g ( w ) ≤ c 2 , ∀ w 0 < c_1 \leq \nabla_w g(w) \leq c_2,\forall w 0<c1≤∇wg(w)≤c2,∀w
\quad- ∑ k = 1 ∞ a k = ∞ \sum_{k=1}^{\infin} a_k = \infin ∑k=1∞ak=∞ 并且 ∑ k = 1 ∞ a k 2 < ∞ \sum_{k=1}^{\infin} a_k^2 < \infin ∑k=1∞ak2<∞
\quad- E [ η k ∣ H k ] = 0 E[\eta_k|\mathcal{H}_k] = 0 E[ηk∣Hk]=0 并且 E [ η k 2 ∣ H k ] < ∞ E[\eta_k^2|\mathcal{H}_k] < \infin E[ηk2∣Hk]<∞,其中 H k = { w k , w k − 1 , . . . } \mathcal{H}_k = \{w_k, w_{k-1}, ...\} Hk={wk,wk−1,...}
下面我们依次来直观理解一下每个条件:
- 0 < c 1 ≤ ∇ w g ( w ) ≤ c 2 , ∀ w 0 < c_1 \leq \nabla_w g(w) \leq c_2,\forall w 0<c1≤∇wg(w)≤c2,∀w:前半部分 0 < c 1 ≤ ∇ w g ( w ) 0 < c_1 \leq \nabla_w g(w) 0<c1≤∇wg(w) 是要求 g ( w ) g(w) g(w) 是单调递增函数,而由于常用的场景是求解 min w J ( w ) \min_w J(w) minwJ(w) 时,转化为求解 ∇ w J ( w ) = 0 \nabla_w J(w) = 0 ∇wJ(w)=0,因此 0 < c 1 ≤ ∇ w 2 J ( w ) ≤ c 2 0 < c_1 \leq \nabla_w^2 J(w) \leq c_2 0<c1≤∇w2J(w)≤c2 即要求 J ( w ) J(w) J(w) 是 凸函数。而后半部分 ∇ w g ( w ) ≤ c 2 \nabla_w g(w) \leq c_2 ∇wg(w)≤c2 则限制了 g ( w ) g(w) g(w) 的增长率不会发散,否则会影响 w k w_k wk 的收敛性。
\quad
\quad - ∑ k = 1 ∞ a k = ∞ \sum_{k=1}^{\infin} a_k = \infin ∑k=1∞ak=∞ 并且 ∑ k = 1 ∞ a k 2 < ∞ \sum_{k=1}^{\infin} a_k^2 < \infin ∑k=1∞ak2<∞:这其实是希望 a k a_k ak 是一个趋于 0,但又不会过快趋于 0 的序列。要求 a k a_k ak 趋于 0 很好理解,因为 w k + 1 − w k = a k ( g ( w k ) + η k ) w_{k+1} - w_k = a_k (g(w_k) + \eta_k) wk+1−wk=ak(g(wk)+ηk) 因此 a k a_k ak 趋于 0 才能保证 w k w_k wk 能收敛。那 a k a_k ak 不会过快趋于 0 有什么作用呢?由于 w k + 1 − w k = − a k ( g ( w k ) + η k ) w_{k+1} - w_k = - a_k (g(w_k) + \eta_k) wk+1−wk=−ak(g(wk)+ηk),因此 w 1 − w ∞ = ∑ k = 1 ∞ a k ( g ( w k ) + η k ) w_1 - w_{\infin} = \sum_{k=1}^{\infin} a_k (g(w_k) + \eta_k) w1−w∞=k=1∑∞ak(g(wk)+ηk),如果 a k a_k ak 很快就趋于 0 了,由于 ∇ w g ( w ) ≤ c 2 \nabla_w g(w) \leq c_2 ∇wg(w)≤c2 ,因此 ∑ k = 1 ∞ a k ( g ( w k ) + η k ) \sum_{k=1}^{\infin} a_k (g(w_k) + \eta_k) ∑k=1∞ak(g(wk)+ηk) 有上界,即 ∣ w 1 − w ∞ ∣ ≤ b |w_1 - w_{\infin}| \leq b ∣w1−w∞∣≤b 由此带来的问题是 w 1 w_1 w1 不能任意选择,因为若选的 w 1 w_1 w1 离 w ∗ w^* w∗ 太远,那么 ∣ w 1 − w ∞ ∣ ≤ b |w_1 - w_{\infin}| \leq b ∣w1−w∞∣≤b 就不成立了,因而是否能收敛到 w ∗ w^* w∗ 也无法保证 (NOTE: a k = 1 k a_k = \frac{1}{k} ak=k1 就是一个满足条件的例子)
\quad
\quad - E [ η k ∣ H k ] = 0 E[\eta_k|\mathcal{H}_k] = 0 E[ηk∣Hk]=0 并且 E [ η k 2 ∣ H k ] < ∞ E[\eta_k^2|\mathcal{H}_k] < \infin E[ηk2∣Hk]<∞:这个条件比较弱,甚至不要求 η \eta η 满足高斯分布,只要 { η k } \{\eta_k\} {ηk} 独立同分布,且满足 E [ η k ] = 0 , E [ η k 2 ] < ∞ E[\eta_k] = 0, E[\eta_k^2] < \infin E[ηk]=0,E[ηk2]<∞ 即可。本质是希望 η \eta η 中不要包含有效信息,有效的信息应该都包含在 g ( w ) g(w) g(w) 中。
抛开上述条件,Robbins-Monro 算法的想法也很简单,就是:对于一个单调递增函数,随便取一个点 w 1 w_1 w1,如果 g ( w 1 ) + η 1 < 0 g(w_1) + \eta_1 < 0 g(w1)+η1<0,说明 w ∗ w^* w∗ 在 w 1 w_1 w1的右边,那么下一步应该往右走,而 w 2 = w 1 − a 1 ( g ( w 1 ) + η 1 ) w_{2} = w_1 - a_1 (g(w_1) + \eta_1) w2=w1−a1(g(w1)+η1)
由于 g ( w 1 ) + η 1 < 0 g(w_1) + \eta_1 < 0 g(w1)+η1<0,因此 − a 1 ( g ( w 1 ) + η 1 ) > 0 - a_1 (g(w_1) + \eta_1) > 0 −a1(g(w1)+η1)>0,即方向向右。同理,如果 g ( w 1 ) + η 1 > 0 g(w_1) + \eta_1 > 0 g(w1)+η1>0,则下一步会往左走一点
图示:
用 Robbins-Monro 算法解释 Mean estimation
为了能将 Mean estimation 囊括到 Robbins-Monro 的框架下,我们需要定义: g ( w ) = w − E [ X ] g(w) = w - E[X] g(w)=w−E[X]
这样求解 g ( w ∗ ) = 0 g(w^*) = 0 g(w∗)=0 就等价于求解 w ∗ = E [ X ] w^* = E[X] w∗=E[X]。由此 Robbins-Monro 中的迭代式 w k + 1 = w k − a k ( g ( w k ) + η k ) w_{k+1} = w_k - a_k (g(w_k) + \eta_k) wk+1=wk−ak(g(wk)+ηk)
其中 g ( w k ) = w k − E [ X ] g(w_k) = w_k - E[X] g(wk)=wk−E[X], η k \eta_k ηk 是样本 x k x_k xk 的观测误差 E [ X ] − x k E[X] - x_k E[X]−xk(易证 E [ η k ] = 0 E[\eta_k] = 0 E[ηk]=0 且 E [ η k 2 ] < ∞ E[\eta_k^2] < \infin E[ηk2]<∞),再取 a k = 1 k a_k = \frac{1}{k} ak=k1,因此有
w k + 1 = w k − a k ( g ( w k ) + η k ) = w k − 1 k ( w k − E [ X ] + E [ X ] − x k ) = w k − 1 k ( w k − x k ) \begin{aligned} w_{k+1} &= w_k - a_k (g(w_k) + \eta_k)\\ &= w_k - \frac{1}{k} (w_k - E[X] + E[X] - x_k)\\ &= w_k - \frac{1}{k} (w_k - x_k) \end{aligned} wk+1=wk−ak(g(wk)+ηk)=wk−k1(wk−E[X]+E[X]−xk)=wk−k1(wk−xk)
即 Mean estimation
用 Robbins-Monro 算法解释 Batch Gradient descent
机器学习中常用的 Gradient descent 算法描述如下:
min w J ( w ) = E [ f ( w , X ) ] \min_w J(w) = E[f(w,X)] wminJ(w)=E[f(w,X)]
其中 f f f 即损失函数, w w w 是模型中的待优化参数。求解的迭代式是:
w k + 1 = w k − α k ∇ w J ( w ) = w k − α k E [ ∇ w f ( w k , X ) ] = w k − α k ⋅ 1 n ∑ i = 1 n ∇ w f ( w k , x i ) \begin{aligned} w_{k+1} =& w_k - \alpha_k \nabla_w J(w)\\ =& w_k - \alpha_k E[\nabla_w f(w_k,X)] \\ =& w_k - \alpha_k \cdot \frac{1}{n} \sum_{i=1}^n \nabla_w f(w_k,x_i) \end{aligned} wk+1===wk−αk∇wJ(w)wk−αkE[∇wf(wk,X)]wk−αk⋅n1i=1∑n∇wf(wk,xi)
其中 ( x i , f ( w k , x i ) ) (x_i, f(w_k,x_i)) (xi,f(wk,xi)) 即一对样本。由于每次更新 w w w 都需要将所有的样本都计算到,因此也叫 Batch Gradient descent。 但跟 Mean estimation 类似,Batch Gradient descent 要求所有样本采样完毕才能计算,效率比较低。因此提出了每次只使用一个样本来更新参数的算法:Stochastic Gradient Descent (SGD)
w k + 1 = w k − α k ∇ w f ( w k , x k ) w_{k+1} = w_k - \alpha_k \nabla_w f(w_k,x_k) wk+1=wk−αk∇wf(wk,xk)
为了将 SGD 囊括到Robbins-Monro 的框架下,只需要定义 g ( w ) = ∇ w J ( w ) g(w) = \nabla_w J(w) g(w)=∇wJ(w)
那么求解 g ( w ∗ ) = ∇ w J ( w ∗ ) = 0 g(w^*) = \nabla_w J(w^*) = 0 g(w∗)=∇wJ(w∗)=0 就等价于求解 min w J ( w ) \min_w J(w) minwJ(w) (当 J ( w ) J(w) J(w) 是凸函数时),可以推导:
w k + 1 = w k − a k ( g ( w k ) + η k ) = w k − α k ( E [ ∇ w f ( w k , X ) ] + ( ∇ w f ( w k , x k ) − E [ ∇ w f ( w k , X ) ] ) ) = w k − α k ⋅ ∇ w f ( w k , x k ) \begin{aligned} w_{k+1} =& w_k - a_k (g(w_k) + \eta_k)\\ =& w_k - \alpha_k (E[\nabla_w f(w_k,X)] + (\nabla_w f(w_k,x_k) - E[\nabla_w f(w_k,X)])) \\ =& w_k - \alpha_k \cdot \nabla_w f(w_k,x_k) \end{aligned} wk+1===wk−ak(g(wk)+ηk)wk−αk(E[∇wf(wk,X)]+(∇wf(wk,xk)−E[∇wf(wk,X)]))wk−αk⋅∇wf(wk,xk)
即 SGD。上式中 η k = ∇ w f ( w k , x k ) − E [ ∇ w f ( w k , X ) ] \eta_k = \nabla_w f(w_k,x_k) - E[\nabla_w f(w_k,X)] ηk=∇wf(wk,xk)−E[∇wf(wk,X)],同样易证 E [ η k ] = 0 E[\eta_k] = 0 E[ηk]=0 且 E [ η k 2 ] < ∞ E[\eta_k^2] < \infin E[ηk2]<∞。这里同时也说明了 SGD的收敛性,跟随 Robbins-Monro 框架的收敛性而成立
用 SGD 解释 Mean estimation
注意到如果想将 Mean estimation 套入 SGD 的框架,需要找到一个 f ( w , X ) f(w,X) f(w,X) 使得满足:
∇ w f ( w , X ) = w − X \nabla_w f(w,X) = w - X ∇wf(w,X)=w−X
因为这样就有:
w k + 1 = w k − α k ⋅ ∇ w f ( w k , x k ) = w k − α k ( w k − x k ) w_{k+1} = w_k - \alpha_k \cdot \nabla_w f(w_k,x_k) = w_k - \alpha_k (w_k - x_k) wk+1=wk−αk⋅∇wf(wk,xk)=wk−αk(wk−xk)
上式即 Mean estimation 的迭代式。因此我们可以构造:
min w J ( w ) = E [ 1 2 ∣ ∣ w − X ∣ ∣ 2 ] \min_w J(w) = E[\frac{1}{2}||w-X||^2] wminJ(w)=E[21∣∣w−X∣∣2]
这个从直观也比较好理解, 即求解 w = E [ X ] w = E[X] w=E[X] 等价于求解 min w E [ 1 2 ∣ ∣ w − X ∣ ∣ 2 ] \min_w E[\frac{1}{2}||w-X||^2] minwE[21∣∣w−X∣∣2]
SGD 的一个有趣的性质
尽管上面我们说明了 SGD 的收敛性,但它的收敛速度呢?是否也足够快呢?这里有一个有趣的结论:
当 w k w_k wk 距离 w ∗ w^* w∗ 较远时,SGD 向 w ∗ w^* w∗ 靠近的速度与一般的 GD 差不多,但是当 w k w_k wk 离 w ∗ w^* w∗ 比较近时,其收敛会呈现一定的 随机性
定义 δ k = ∣ ∇ w f ( w k , x k ) − E [ ∇ w f ( w k , X ) ] ∣ ∣ E [ ∇ w f ( w k , X ) ] ∣ \delta_k = \frac{|\nabla_wf(w_k,x_k) - E[\nabla_w f(w_k,X)]|}{|E[\nabla_w f(w_k,X)]|} δk=∣E[∇wf(wk,X)]∣∣∇wf(wk,xk)−E[∇wf(wk,X)]∣
来描述 SGD 和 GD 算法的相对误差, δ k \delta_k δk 越小,表明 SGD 与 GD 的收敛速度越接近。
由于 g ( w ∗ ) = ∇ w J ( w ∗ ) = E [ ∇ w f ( w ∗ , X ) ] = 0 g(w^*) = \nabla_w J(w^*) = E[\nabla_w f(w^*,X)] = 0 g(w∗)=∇wJ(w∗)=E[∇wf(w∗,X)]=0,因此
δ k = ∣ ∇ w f ( w k , x k ) − E [ ∇ w f ( w k , X ) ] ∣ ∣ E [ ∇ w f ( w k , X ) ] − E [ ∇ w f ( w ∗ , X ) ] ∣ = ∣ ∇ w f ( w k , x k ) − E [ ∇ w f ( w k , X ) ] ∣ E [ ∇ w 2 f ( w k ^ , X ) ( w k − w ∗ ) ] \delta_k = \frac{|\nabla_wf(w_k,x_k) - E[\nabla_w f(w_k,X)]|}{|E[\nabla_w f(w_k,X)] - E[\nabla_w f(w^*,X)]|} = \frac{|\nabla_wf(w_k,x_k) - E[\nabla_w f(w_k,X)]|}{E[\nabla^2_w f(\hat{w_k},X)(w_k - w^*)]} δk=∣E[∇wf(wk,X)]−E[∇wf(w∗,X)]∣∣∇wf(wk,xk)−E[∇wf(wk,X)]∣=E[∇w2f(wk^,X)(wk−w∗)]∣∇wf(wk,xk)−E[∇wf(wk,X)]∣
其中总存在 w k ^ ∈ ( w k , w ∗ ) \hat{w_k} \in (w_k,w^*) wk^∈(wk,w∗) ,使得 E [ ∇ w f ( w k , X ) ] − E [ ∇ w f ( w ∗ , X ) ] = E [ ∇ w 2 f ( w k ^ , X ) ( w k − w ∗ ) ] E[\nabla_w f(w_k,X)] - E[\nabla_w f(w^*,X)] = E[\nabla^2_w f(\hat{w_k},X)(w_k - w^*)] E[∇wf(wk,X)]−E[∇wf(w∗,X)]=E[∇w2f(wk^,X)(wk−w∗)] 是 中值定理 的结论。
由于 w k − w ∗ w_k - w^* wk−w∗ 不是随机变量,且由 Robbins-Monro 框架的收敛性条件, 0 < c ≤ ∇ w 2 f 0 < c \leq \nabla^2_w f 0<c≤∇w2f,可得:
∣ E [ ∇ w 2 f ( w k ^ , X ) ( w k − w ∗ ) ] ∣ = E [ ∇ w 2 f ( w k ^ , X ) ] ∣ ∣ w k − w ∗ ∣ ≥ c ∣ w k − w ∗ ∣ |E[\nabla^2_w f(\hat{w_k},X)(w_k - w^*)]| = E[\nabla^2_w f(\hat{w_k},X)]||w_k - w^*| \geq c |w_k - w^*| ∣E[∇w2f(wk^,X)(wk−w∗)]∣=E[∇w2f(wk^,X)]∣∣wk−w∗∣≥c∣wk−w∗∣
⇒ δ k ≤ ∣ ∇ w f ( w k , x k ) − E [ ∇ w f ( w k , X ) ] ∣ c ∣ w k − w ∗ ∣ \Rightarrow \delta_k \leq \frac{|\nabla_wf(w_k,x_k) - E[\nabla_w f(w_k,X)]|}{c |w_k - w^*|} ⇒δk≤c∣wk−w∗∣∣∇wf(wk,xk)−E[∇wf(wk,X)]∣
因此我们可以发现:
- 当 ∣ w k − w ∗ ∣ |w_k - w^*| ∣wk−w∗∣ 比较大时, δ k \delta_k δk 的上界比较小,即此时 SGD 与 GD 的收敛速度比较接近
- 当 ∣ w k − w ∗ ∣ |w_k - w^*| ∣wk−w∗∣ 比较小时, δ k \delta_k δk 的上界比较大,即此时 SGD 的收敛速度不太能保证,有较强的 随机性
时序差分方法
时序差分方法也是一种 model-free 方法,类似 蒙特卡洛方法,我们有一个足够长的 trajectory ( s 0 , r 1 , s 1 , . . . , s t , r t + 1 , s t + 1 , . . . ) (s_0, r_1, s_1, ..., s_t, r_{t+1}, s_{t+1},...) (s0,r1,s1,...,st,rt+1,st+1,...) 来作为样本集。回忆求解贝尔曼最优公式时的 策略迭代 过程
已知 π k → ( v π k ( 0 ) → v π k ( 1 ) → . . . → v π k ( ∞ ) = v π k ) → 求解 q π k ( s , a ) → π k + 1 = { 1 , a = a ∗ ( s ) 0 , a ≠ a ∗ ( s ) → . . . 已知 \pi_k \rightarrow (v_{\pi_k}^{(0)} \rightarrow v_{\pi_k}^{(1)} \rightarrow ... \rightarrow v_{\pi_k}^{(\infin)} = v_{\pi_k}) \rightarrow 求解 q_{\pi_k}(s,a) \rightarrow \pi_{k+1}= \begin{cases} 1, \quad a = a^*(s)\\ 0, \quad a \neq a^*(s) \end{cases} \rightarrow ... 已知πk→(vπk(0)→vπk(1)→...→vπk(∞)=vπk)→求解qπk(s,a)→πk+1={1,a=a∗(s)0,a=a∗(s)→...
其中 ( v π k ( 0 ) → v π k ( 1 ) → . . . → v π k ( ∞ ) = v π k ) (v_{\pi_k}^{(0)} \rightarrow v_{\pi_k}^{(1)} \rightarrow ... \rightarrow v_{\pi_k}^{(\infin)} = v_{\pi_k}) (vπk(0)→vπk(1)→...→vπk(∞)=vπk) 即是通过迭代求解一个求解一个贝尔曼公式:
v π k ( 1 ) = r π k + γ P π k v π k ( 0 ) v π k ( 2 ) = r π k + γ P π k v π k ( 1 ) … 贝尔曼公式 ⟵ v π k ( ∞ ) = r π k + γ P π k v π k ( ∞ ) \begin{aligned} v_{\pi_k}^{(1)} &= r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(0)}\\ v_{\pi_k}^{(2)} &= r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(1)}\\ & \dots \\ \text{贝尔曼公式} \quad \longleftarrow \quad v_{\pi_k}^{(\infin)} &= r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(\infin)}\\ \end{aligned} vπk(1)vπk(2)贝尔曼公式⟵vπk(∞)=rπk+γPπkvπk(0)=rπk+γPπkvπk(1)…=rπk+γPπkvπk(∞)
但现在由于是 model-free 了,我们只能通过样本来求解 v π k v_{\pi_k} vπk。在 第一节 中, v π k v_{\pi_k} vπk 的原始定义是在 Policy 为 π k {\pi_k} πk, 从状态 s 出发时,所有可能的 trajectory 的 discounted return G t G_t Gt 的期望值: v π ( s ) = E [ G t ∣ S t = s ] = E [ R t + 1 + γ G t + 1 ∣ S t = s ] v_{\pi}(s) = E[G_t|S_t=s] = E[R_{t+1} + \gamma G_{t+1}|S_t = s] vπ(s)=E[Gt∣St=s]=E[Rt+1+γGt+1∣St=s]
又由于 E [ G t + 1 ∣ S t = s ] = v π ( S t + 1 ) E[G_{t+1}|S_t = s] = v_{\pi}(S_{t+1}) E[Gt+1∣St=s]=vπ(St+1)
因此:
v π ( s ) = E [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s ] v_{\pi}(s) = E[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t = s] vπ(s)=E[Rt+1+γvπ(St+1)∣St=s]
上式可以用 Robbins-Monro 框架来迭代求解:
记 g ( v π ( s t ) ) = v π ( s t ) − E [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s t ] g(v_{\pi}(s_t)) = v_{\pi}(s_t) - E[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t = s_t] g(vπ(st))=vπ(st)−E[Rt+1+γvπ(St+1)∣St=st]
目标是求解: g ( v π ( s t ) ) = 0 g(v_{\pi}(s_t)) = 0 g(vπ(st))=0
上式就是我们前面讨论的 Mean estimation,每来一个样本 ( s t , r t + 1 , s t + 1 ) (s_t, r_{t+1}, s_{t+1}) (st,rt+1,st+1),其更新式为:
v t + 1 ( s t ) = v t ( s t ) − α t ( s t ) ( v t ( s t ) − [ r t + 1 + γ v t ( s t + 1 ) ] ) v_{t+1}(s_t) = v_t(s_t) - \alpha_t(s_t) (v_t(s_t) - [r_{t+1} + \gamma v_t(s_{t+1})]) vt+1(st)=vt(st)−αt(st)(vt(st)−[rt+1+γvt(st+1)])
其中 v t ˉ = r t + 1 + γ v t ( s t + 1 ) \bar{v_t} = r_{t+1} + \gamma v_t(s_{t+1}) vtˉ=rt+1+γvt(st+1) 称为 TD target, δ t = v t ( s t ) − v t ˉ \delta_t = v_t(s_t) - \bar{v_t} δt=vt(st)−vtˉ 则称为 TD error。注意这里: v t + 1 ( s ) = v t ( s ) , if s ≠ s t v_{t+1}(s) = v_t(s), \text { if } s \neq s_t vt+1(s)=vt(s), if s=st
即,每学习一个样本, v t + 1 v_{t+1} vt+1 相比 v t v_t vt 只会更新当前样本涉及到的 state 的 state value(这是当然的)。
如前面 Robbins-Monro 所讨论的,迭代的目标是减小 TD error,由于 g ( v π ( s t ) ) g(v_{\pi}(s_t)) g(vπ(st)) 是单调递增函数:
- 当 v t ( s t ) − v t ˉ < 0 v_t(s_t) - \bar{v_t} < 0 vt(st)−vtˉ<0 时, v t + 1 ( s t ) v_{t+1}(s_t) vt+1(st) 往 v t ( s t ) v_t(s_t) vt(st) 右边移一点
- 当 v t ( s t ) − v t ˉ > 0 v_t(s_t) - \bar{v_t} > 0 vt(st)−vtˉ>0 时, v t + 1 ( s t ) v_{t+1}(s_t) vt+1(st) 往 v t ( s t ) v_t(s_t) vt(st) 左边移一点
从数学上来说,因为当 v t = v π v_t = v_{\pi} vt=vπ 时:
E [ δ t ∣ S t = s t ] = E [ v π ( S t ) − ( R t + 1 + γ v π ( S t + 1 ) ) ∣ S t = s t ] = v π ( s t ) − E [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s t ] = 0 \begin{align} E[\delta_t | S_t=s_t] &= E[v_{\pi}(S_t) - (R_{t+1} + \gamma v_{\pi}(S_{t+1})) | S_t=s_t] \\ &= v_{\pi}(s_t) - E[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t=s_t] \\ &= 0 \end{align} E[δt∣St=st]=E[vπ(St)−(Rt+1+γvπ(St+1))∣St=st]=vπ(st)−E[Rt+1+γvπ(St+1)∣St=st]=0
因此减小 TD error 即使得 v t v_t vt 向 v π v_{\pi} vπ 靠近。
与蒙特卡洛算法的区别
- 首先最主要的区别:TD 算法摆脱了蒙特卡洛算法中 需要等到所有的样本都采完,才能进行一轮更新。TD 算法中,每增加一个样本就可以进行一次 value state 更新
- TD 算法由于每次只更新了一个样本,所以其开始的时候,是对 R t + 1 + γ G t + 1 R_{t+1} + \gamma G_{t+1} Rt+1+γGt+1 的有偏估计,当学习的样本量足够多时,才逐渐变成无偏估计;而蒙特卡洛算法一条 trajectory 就采到足够多的样本,且一次迭代就全部使用,因此直接就是无偏估计
- TD 算法估计的 state value,而蒙特卡洛方法是直接估计 action value
Sarsa 算法
上述 TD 算法只是求解了贝尔曼方程,但这不足以找到最优的 Policy,要找最优 Policy,需要知道所有 state 的 action value,回忆蒙特卡洛算法:
已知 π k → 从 ( s , a ) 出发,做 n 次实验,有 n 个结果 g π k ( i ) ( s , a ) → 估计 q π k ( s , a ) = 1 n ∑ i g π k ( i ) ( s , a ) → π k + 1 = { 1 , a = a π k ( s ) 0 , a ≠ a π k ( s ) → . . . 已知 \pi_k \rightarrow 从 (s,a) 出发,做n次实验,有n个结果 g_{\pi_k}^{(i)}(s,a) \rightarrow 估计 q_{\pi_k}(s,a) = \frac{1}{n}\sum_i g_{\pi_k}^{(i)}(s,a) \rightarrow \pi_{k+1}= \begin{cases} 1, \quad a = a_{\pi_k}(s)\\ 0, \quad a \neq a_{\pi_k}(s) \end{cases} \rightarrow ... 已知πk→从(s,a)出发,做n次实验,有n个结果gπk(i)(s,a)→估计qπk(s,a)=n1i∑gπk(i)(s,a)→πk+1={1,a=aπk(s)0,a=aπk(s)→...
这里我们也是想估计 q π k ( s , a ) q_{\pi_k}(s,a) qπk(s,a),但类似 TD 算法的想法,Sarsa 算法也是来一个样本就学一点,而不是像蒙特卡洛算法一样等所有的样本都生成完了,再一起学。
第一节 当中,我们推到过 action value 形式的贝尔曼公式,首先看常见的 state value 的贝尔曼公式:
v π ( s ) = ∑ a π ( a ∣ s ) [ ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ P ( s ′ ∣ s , a ) v π ( s ′ ) ] , ∀ s \begin{aligned} v_{\pi}(s) = \sum_{a} \pi(a|s) [\sum_{r} P(r|s,a)r + \gamma \sum_{s'} P(s'|s,a) v_{\pi}(s')], \quad \forall s \end{aligned} vπ(s)=a∑π(a∣s)[r∑P(r∣s,a)r+γs′∑P(s′∣s,a)vπ(s′)],∀s
由于
v π ( s ) = ∑ a π ( a ∣ s ) q π ( s , a ) v_{\pi}(s) = \sum_a \pi(a|s) q_{\pi}(s,a) vπ(s)=a∑π(a∣s)qπ(s,a)
因此上式等价于
q π ( s , a ) = ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ P ( s ′ ∣ s , a ) v π ( s ′ ) = ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ P ( s ′ ∣ s , a ) ∑ a ′ q π ( s ′ , a ′ ) π ( a ′ ∣ s ′ ) = ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ ∑ a ′ q π ( s ′ , a ′ ) P ( s ′ ∣ s , a ) P ( a ′ ∣ s ′ ) = ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ ∑ a ′ q π ( s ′ , a ′ ) P ( s ′ ∣ s , a ) P ( a ′ ∣ s ′ , s , a ) = ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ ∑ a ′ q π ( s ′ , a ′ ) P ( s ′ , a ′ ∣ s , a ) = E [ R + γ q π ( S ′ , A ′ ) ∣ s , a ] \begin{aligned} q_{\pi}(s,a) &= \sum_{r} P(r|s,a)r + \gamma \sum_{s'} P(s'|s,a) v_{\pi}(s')\\ &= \sum_{r} P(r|s,a)r + \gamma \sum_{s'} P(s'|s,a) \sum_{a'} q_{\pi}(s',a') \pi(a'|s')\\ &= \sum_{r} P(r|s,a)r + \gamma \sum_{s'}\sum_{a'} q_{\pi}(s',a') P(s'|s,a) P(a'|s')\\ &= \sum_{r} P(r|s,a)r + \gamma \sum_{s'}\sum_{a'} q_{\pi}(s',a') P(s'|s,a) P(a'|s',s,a)\\ &= \sum_{r} P(r|s,a)r + \gamma \sum_{s'}\sum_{a'} q_{\pi}(s',a') P(s',a'|s,a)\\ &= E[R + \gamma q_{\pi}(S',A')|s,a] \end{aligned} qπ(s,a)=r∑P(r∣s,a)r+γs′∑P(s′∣s,a)vπ(s′)=r∑P(r∣s,a)r+γs′∑P(s′∣s,a)a′∑qπ(s′,a′)π(a′∣s′)=r∑P(r∣s,a)r+γs′∑a′∑qπ(s′,a′)P(s′∣s,a)P(a′∣s′)=r∑P(r∣s,a)r+γs′∑a′∑qπ(s′,a′)P(s′∣s,a)P(a′∣s′,s,a)=r∑P(r∣s,a)r+γs′∑a′∑qπ(s′,a′)P(s′,a′∣s,a)=E[R+γqπ(S′,A′)∣s,a]
因此 Sarsa 算法的 Robbins-Monro 框架为:
记 g ( q π ( s t , a t ) ) = q π ( s t , a t ) − E [ R t + 1 + γ q π ( S t + 1 , A t + 1 ) ∣ S t = s t , A t = a t ] g(q_{\pi}(s_t,a_t)) = q_{\pi}(s_t,a_t) - E[R_{t+1} + \gamma q_{\pi}(S_{t+1},A_{t+1})|S_t = s_t, A_t = a_t] g(qπ(st,at))=qπ(st,at)−E[Rt+1+γqπ(St+1,At+1)∣St=st,At=at]
目标是求解: g ( q π ( s t , a t ) ) = 0 g(q_{\pi}(s_t,a_t)) = 0 g(qπ(st,at))=0
\quad
每来一个样本 { s t , a t , r t + 1 , s t + 1 , a t + 1 } \{s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}\} {st,at,rt+1,st+1,at+1},更新式为: q t + 1 ( s t , a t ) = q t ( s t , a t ) − α t ( s t , a t ) [ q t ( s t , a t ) − ( r t + 1 + γ q t ( s t + 1 , a t + 1 ) ) ] q_{t+1}(s_t,a_t) = q_t(s_t,a_t) - \alpha_t(s_t,a_t) [q_t(s_t,a_t) - (r_{t+1} + \gamma q_t(s_{t+1},a_{t+1}))] qt+1(st,at)=qt(st,at)−αt(st,at)[qt(st,at)−(rt+1+γqt(st+1,at+1))]
同样有: q t + 1 ( s , a ) = q t ( s , a ) , ∀ ( s , a ) ≠ ( s t , a t ) q_{t+1}(s,a) = q_t(s,a), \qquad \forall (s,a) \neq (s_t,a_t) qt+1(s,a)=qt(s,a),∀(s,a)=(st,at)
Sarsa 算法的完整实现为:
这里面有一点需要注意,我们每采到一个样本 ( s t , a t , r t + 1 , s t + 1 , a t + 1 ) (s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}) (st,at,rt+1,st+1,at+1),就会立即更新 q t + 1 ( s t , a t ) q_{t+1}(s_t,a_t) qt+1(st,at) 然后立马就更新 Policy π t + 1 \pi_{t+1} πt+1,并且由这个 Policy 来采下一个样本,这里采用 ϵ \epsilon ϵ-greedy 方法来更新策略也是这个原因(即 Sarsa 是 on-policy 的,迭代中的策略同时也要用来生成下一步的样本)。
另外不难看出 Sarsa 找的 仅仅是从某一个 state 出发,到 target state 的最优路线,而不是求所有 state 的最优路线。因此 Sarsa 往往会主要在 start state 和 target state 附近寻找,因为一般情况下,最优路线也不会绕路。但理论上来说,不把所有的 state 都“走”足够多次,是 不能保证 Sarsa 找到的路径是 “全局最优” 的,有时也会出现只找到局部最优的情况。
一个例子
![](https://i-blog.csdnimg.cn/direct/531f19e966f24877bf8a25da1b1e4eec.png)
左边展示了 Sarsa 的结果,可以看出,它只是找到了从 start state 开始的一个最优路径,但是其他 state 的 policy 很多并不是最优的。右图显示了随着算法迭代,一个 episode 的长度和 reward,可以看到,随着迭代步数增加,episode 的长度减少,reward 增加,这些都说明,Policy 在不断变好。
Expected Sarsa 算法
Expected Sarsa 算法的迭代式与 Sarsa 非常接近:
q t + 1 ( s t , a t ) = q t ( s t , a t ) − α t ( s t , a t ) [ q t ( s t , a t ) − ( r t + 1 + γ E [ q t ( s t + 1 , A ) ] ) ] q t + 1 ( s , a ) = q t ( s , a ) , ∀ ( s , a ) ≠ ( s t , a t ) \begin{align} q_{t+1}(s_t,a_t) &= q_t(s_t,a_t) - \alpha_t(s_t,a_t) [q_t(s_t,a_t) - (r_{t+1} + \gamma E[q_t(s_{t+1},A)])]\\ q_{t+1}(s,a) &= q_t(s,a), \qquad \forall (s,a) \neq (s_t,a_t) \end{align} qt+1(st,at)qt+1(s,a)=qt(st,at)−αt(st,at)[qt(st,at)−(rt+1+γE[qt(st+1,A)])]=qt(s,a),∀(s,a)=(st,at)
其中 E [ q t ( s t + 1 , A ) ] = ∑ a π t ( a ∣ s t + 1 ) q t ( s t + 1 , a ) = v t ( s t + 1 ) E[q_t(s_{t+1},A)] = \sum_{a} \pi_t(a|s_{t+1})q_t(s_{t+1},a) = v_t(s_{t+1}) E[qt(st+1,A)]=∑aπt(a∣st+1)qt(st+1,a)=vt(st+1)
上述迭代式也是基于求解贝尔曼公式:
q π ( s , a ) = E [ R t + 1 + γ E [ q π ( S t + 1 , A t + 1 ) ∣ S t + 1 ] ∣ S t = s , A t = a ] = E [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s , A t = a ] \begin{align} q_{\pi}(s,a) &= E[R_{t+1} + \gamma E[q_{\pi}(S_{t+1},A_{t+1})|S_{t+1}] | S_t = s, A_t = a]\\ &= E[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s, A_t = a]\\ \end{align} qπ(s,a)=E[Rt+1+γE[qπ(St+1,At+1)∣St+1]∣St=s,At=a]=E[Rt+1+γvπ(St+1)∣St=s,At=a]
上式等价于贝尔曼公式的原因是:
v π ( s ) = E [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s ] = ∑ a π ( a ∣ s ) E [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s , A t = a ] = ∑ a π ( a ∣ s ) q π ( s , a ) \begin{align} v_{\pi}(s) &= E[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t = s]\\ &= \sum_{a} \pi(a|s) E[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t = s, A_t = a]\\ &= \sum_{a} \pi(a|s) q_{\pi}(s,a) \end{align} vπ(s)=E[Rt+1+γvπ(St+1)∣St=s]=a∑π(a∣s)E[Rt+1+γvπ(St+1)∣St=s,At=a]=a∑π(a∣s)qπ(s,a)
Expected Sarsa 跟 Sarsa 相比:
- TD target 计算更复杂了
- 采样样本从 { s t , a t , r t + 1 , s t + 1 , a t + 1 } \{s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}\} {st,at,rt+1,st+1,at+1} 变成了 { s t , a t , r t + 1 , s t + 1 } \{s_t, a_t, r_{t+1}, s_{t+1}\} {st,at,rt+1,st+1},estimation variance 变小了
n-step Sarsa 算法
n-step Sarsa 是 Sarsa 的另一个重要变体,回忆 action value 的原始定义: q π ( s , a ) = E [ G t ∣ S t = s , A t = a ] q_{\pi}(s,a) = E[G_t | S_t = s, A_t = a] qπ(s,a)=E[Gt∣St=s,At=a]
G t G_t Gt 可以分解成 G t = R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... Gt=Rt+1+γRt+2+γ2Rt+3+...
或者更细的拆分:
Sarsa ← G t ( 1 ) = R t + 1 + γ q π ( S t + 1 , A t + 1 ) G t ( 2 ) = R t + 1 + γ R t + 2 + γ 2 q π ( S t + 2 , A t + 2 ) … n-step Sarsa ← G t ( n ) = R t + 1 + γ R t + 2 + . . . + γ n q π ( S t + n , A t + n ) … 蒙特卡洛算法 ← G t ( ∞ ) = R t + 1 + γ R t + 2 + γ 2 R t + 3 + γ 3 R t + 4 + . . . \begin{aligned} \text{Sarsa} \leftarrow \quad G_t^{(1)} &= R_{t+1} + \gamma q_{\pi}(S_{t+1},A_{t+1})\\ G_t^{(2)} &= R_{t+1} + \gamma R_{t+2} + \gamma^2 q_{\pi}(S_{t+2},A_{t+2})\\ \dots\\ \text{n-step Sarsa} \leftarrow \quad G_t^{(n)} &= R_{t+1} + \gamma R_{t+2} + ... + \gamma^n q_{\pi}(S_{t+n},A_{t+n})\\ \dots\\ \text{蒙特卡洛算法} \leftarrow \quad G_t^{(\infin)} &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + ... \end{aligned} Sarsa←Gt(1)Gt(2)…n-step Sarsa←Gt(n)…蒙特卡洛算法←Gt(∞)=Rt+1+γqπ(St+1,At+1)=Rt+1+γRt+2+γ2qπ(St+2,At+2)=Rt+1+γRt+2+...+γnqπ(St+n,At+n)=Rt+1+γRt+2+γ2Rt+3+γ3Rt+4+...
即 Sarsa 是每拿到一个样本就更新,蒙特卡洛算法 是拿到所有样本再更新,而 n-step Sarsa 是拿到 n 个样本再更新
因此 n-step Sarsa 的效果也介于 Sarsa 和蒙特卡洛算法之间:
- 当 n 比较大时,更接近蒙特卡洛算法,此时其 bias 比较小,但 estimate variance 比较大
- 当 n 比较小时,更接近 Sarsa,此时其 bias 比较大,但 estimate variance 比较小
Q-learning 算法
Q-learning 跟上述 Sarsa 算法及其变种最主要的区别是:它是直接求的 optimal action value,这就意味着,它不需要像 Sarsa 一样,在每一步迭代后,专门再更新一下 Policy π \pi π ,而是每次迭代直接就可得本次迭代后的最优的 Policy 了
直接给出 Q-learning 的迭代式:
q t + 1 ( s t , a t ) = q t ( s t , a t ) − α t ( s t , a t ) [ q t ( s t , a t ) − ( r t + 1 + γ max a q t ( s t + 1 , a ) ) ] q t + 1 ( s , a ) = q t ( s , a ) , ∀ ( s , a ) ≠ ( s t , a t ) \begin{align} q_{t+1}(s_t,a_t) &= q_t(s_t,a_t) - \alpha_t(s_t,a_t) [q_t(s_t,a_t) - (r_{t+1} + \gamma \max_{a} q_t(s_{t+1},a))]\\ q_{t+1}(s,a) &= q_t(s,a), \qquad \forall (s,a) \neq (s_t,a_t) \end{align} qt+1(st,at)qt+1(s,a)=qt(st,at)−αt(st,at)[qt(st,at)−(rt+1+γamaxqt(st+1,a))]=qt(s,a),∀(s,a)=(st,at)
Q-learning 的本质是 贝尔曼最优公式,这是因为:
q ( s , a ) = E [ R t + 1 + γ max a q ( S t + 1 , a ) ∣ S t = s , A t = a ] = ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ P ( s ′ ∣ s , a ) max a q ( s ′ , a ) \begin{aligned} q(s,a) &= E[R_{t+1} + \gamma \max_{a} q(S_{t+1},a) |S_t = s, A_t=a ]\\ &= \sum_r P(r|s,a)r + \gamma \sum_{s'} P(s'|s,a) \max_{a} q(s',a)\\ \end{aligned} q(s,a)=E[Rt+1+γamaxq(St+1,a)∣St=s,At=a]=r∑P(r∣s,a)r+γs′∑P(s′∣s,a)amaxq(s′,a)
由于 贝尔曼最优公式 : v ∗ ( s ) = max a q ( s , a ) v^*(s) = \max_a q(s,a) v∗(s)=maxaq(s,a),因此上式等价于
v ∗ ( s ) = max a [ ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ P ( s ′ ∣ s , a ) v ∗ ( s ′ ) ] = max π ∑ a π ( a ∣ s ) [ ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ P ( s ′ ∣ s , a ) v ∗ ( s ′ ) ] \begin{aligned} v^*(s) &= \max_a [\sum_r P(r|s,a)r + \gamma \sum_{s'} P(s'|s,a) v^*(s')]\\ &= \max_{\pi} \sum_a \pi(a|s) [\sum_r P(r|s,a)r + \gamma \sum_{s'} P(s'|s,a) v^*(s')] \end{aligned} v∗(s)=amax[r∑P(r∣s,a)r+γs′∑P(s′∣s,a)v∗(s′)]=πmaxa∑π(a∣s)[r∑P(r∣s,a)r+γs′∑P(s′∣s,a)v∗(s′)]
即为 第二节 中讨论的贝尔曼最优公式。
off-policy 和 on-policy
这是强化学习中一个比较基础而重要的概念。与深度学习不同,强化学习中其实有两种 Policy:
- behavior policy:用于生成样本的 Policy
- target policy:实际优化的 Policy
\quadoff-policy 和 on-policy 分别指:
- off-policy:behavior policy 和 target policy 不同
- on-policy:behavior policy 和 target policy 是同一 Policy(我们前面讨论的绝大部分算法都是这种,这也是这些算法要用 ϵ \epsilon ϵ-greedy 而不是直接 greedy 算法更新策略的原因)
Q-learning 是目前为止的第一个 off-policy 算法,核心原因就是因为它求解的是贝尔曼 最优 公式 ,而其他算法求解的只是贝尔曼公式,对比 Q-learning 和 Sarsa 的迭代式
Q-learning : q t + 1 ( s t , a t ) = q t ( s t , a t ) − α t ( s t , a t ) [ q t ( s t , a t ) − ( r t + 1 + γ max a q t ( s t + 1 , a ) ) ] Sarsa : q t + 1 ( s t , a t ) = q t ( s t , a t ) − α t ( s t , a t ) [ q t ( s t , a t ) − ( r t + 1 + γ q t ( s t + 1 , a t + 1 ) ) ] \begin{aligned} \text{Q-learning : } q_{t+1}(s_t,a_t) &= q_t(s_t,a_t) - \alpha_t(s_t,a_t) [q_t(s_t,a_t) - (r_{t+1} + \gamma \max_{a} q_t(s_{t+1},a))]\\ \text{Sarsa : } q_{t+1}(s_t,a_t) &= q_t(s_t,a_t) - \alpha_t(s_t,a_t) [q_t(s_t,a_t) - (r_{t+1} + \gamma q_t(s_{t+1},a_{t+1}))] \end{aligned} Q-learning : qt+1(st,at)Sarsa : qt+1(st,at)=qt(st,at)−αt(st,at)[qt(st,at)−(rt+1+γamaxqt(st+1,a))]=qt(st,at)−αt(st,at)[qt(st,at)−(rt+1+γqt(st+1,at+1))]
Sarsa 的一个样本是 { s t , a t , r t + 1 , s t + 1 , a t + 1 } \{s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}\} {st,at,rt+1,st+1,at+1},其中 s t , a t s_t, a_t st,at 是当前步给定的,而 r t + 1 , s t + 1 r_{t+1}, s_{t+1} rt+1,st+1 是仅依赖于 model: P ( R ∣ s , a ) P(R|s,a) P(R∣s,a) 和 P ( S ′ ∣ s , a ) P(S'|s,a) P(S′∣s,a),与 Policy 无关。重点在于 a t + 1 a_{t+1} at+1 ,一方面它依赖 behavior policy 生成,另一方面,它又用来更新了 target policy 的 action value,这就要求 a t + 1 a_{t+1} at+1 实际也是 target policy 在给定 s t , a t s_t, a_t st,at 的选择(否则定义就不对了)
反观 Q-learning,由于它求解的是贝尔曼最优公式,所以它需要的样本为 { s t , a t , r t + 1 , s t + 1 } \{s_t, a_t, r_{t+1}, s_{t+1}\} {st,at,rt+1,st+1},在给定 s t , a t s_t, a_t st,at 时是不依赖 Policy 的,因此这里 target policy 可以和 behavior policy 解耦。因此它的 behavior policy 可以取得非常 exploration,这样可以使得取到的样本对每一个 state 都充分访问,也更有利于 target policy 的效果,以下是一个例子:
![](https://i-blog.csdnimg.cn/direct/70c5049df2a2481bb7e7ae96dad72217.png)
左边一列是 behavior policy,中间是生成的 episodes,右边一列是用于看 target policy 随着迭代的效果,可以看到,当 ϵ \epsilon ϵ 比较大时, behavior policy 探索性较强,对各个 state 的访问比较充分,其找到的 target policy 效果也更好。
下面再看一个例子,这个例子里,直接将 ϵ \epsilon ϵ 取为了1 (因此各个 action 概率均等):
![](https://i-blog.csdnimg.cn/direct/2d90be4c9d3b416a877c749085871b97.png)
可以看到,此时 behavior policy 生成的 episodes 覆盖性更好,这使得 target policy 也能很快收敛
总结
下面我们给上述的各种时序差分算法一个综合的框架,并在这框架下看下每个算法的核心差别是什么:
q t + 1 ( s t , a t ) = q t ( s t , a t ) − α ( s t , a t ) [ q t ( s t , a t ) − q ˉ t ] q_{t+1}(s_t,a_t) = q_t(s_t,a_t) - \alpha(s_t,a_t) [q_t(s_t,a_t) - \bar{q}_t] qt+1(st,at)=qt(st,at)−α(st,at)[qt(st,at)−qˉt]
不难总结上述时序差分算法的迭代式都满足上述情况,具体来看:
![](https://i-blog.csdnimg.cn/direct/7615175934b8413c9a2f63317d1ca736.png)
Reference:
1.强化学习的数学原理