【RL】Value Function Approximation(值函数逼近)

Lecture 8: Value Function Approximation

Algorithm for state value estimation

Objective function

v π ( s ) v_{\pi}(s) vπ(s) v ^ ( s , w ) \hat{v}(s, w) v^(s,w)是真实state value和近似函数。

算法的目标是找到一个最优的 w w w,使得 v ^ ( s , w ) \hat{v}(s, w) v^(s,w)能够最好地逼近每个 s s s v π ( s ) v_{\pi}(s) vπ(s)

这是一个policy evaluation问题。

为了找到最优的 w w w,需要两个步骤:

  • 第一步是定义目标函数
  • 第二步是推导优化目标函数的算法

目标函数为:
J ( w ) = E [ ( v π ( S ) − v ^ ( S , w ) ) 2 ] . J(w)=\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))^2]. J(w)=E[(vπ(S)v^(S,w))2].
目标是寻找可以最小化 j ( w ) j(w) j(w) w w w

期望是关于随机变量 S ∈ S S \in \mathbf{S} SS的。关于 S S S 的概率分布有以下几种方式:

第一种方式是使用均匀分布(uniform distribution)

即通过将每个state的概率设置为 1 / ∣ S ∣ 1/|\mathbf{S}| 1/∣S,将所有state态视为同等重要。

在这种情况下,目标函数变为:
J ( w ) = E [ ( v π ( S ) − v ^ ( S , w ) ) 2 ] = 1 ∣ S ∣ ∑ s ∈ S ( v π ( s ) − v ^ ( s , w ) ) 2 . J(w)=\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))^2]=\frac1{|\mathcal{S}|}\sum_{s\in\mathcal{S}}(v_\pi(s)-\hat{v}(s,w))^2. J(w)=E[(vπ(S)v^(S,w))2]=S1sS(vπ(s)v^(s,w))2.
缺点:每个state可能并不同样重要。 例如,某些state可能很少被policy访问。 因此,这种方法没有考虑给定policy下Markov过程的真实动态。

第一种方式是使用稳态分布(stationary distribution)

稳态分布是经常使用的一个重要概念。 简而言之,它描述了Markov过程的长期行为。

{ d π ( s ) } s ∈ S \{d_\pi(s)\}_{s\in S} {dπ(s)}sS 表示policy π \pi π 下马尔可夫过程的平稳分布。 根据定义, d π ( s ) ≥ 0 d_{\pi}(s)\geq0 dπ(s)0 ∑ s ∈ S d π ( s ) = 1 \sum_{s\in\mathcal{S}}d_\pi(s)=1 sSdπ(s)=1

目标函数可以重写为:
J ( w ) = E [ ( v π ( S ) − v ^ ( S , w ) ) 2 ] = ∑ s ∈ S d π ( s ) ( v π ( s ) − v ^ ( s , w ) ) 2 . J(w)=\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))^2]=\sum_{s\in\mathcal{S}}d_\pi(s)(v_\pi(s)-\hat{v}(s,w))^2. J(w)=E[(vπ(S)v^(S,w))2]=sSdπ(s)(vπ(s)v^(s,w))2.
该函数是加权平方误差。

由于更频繁访问的state具有更高的 d π ( s ) d_{\pi}(s) dπ(s) 值,因此它们在目标函数中的权重也高于那些很少访问的state。

Example

n π ( s ) n_{\pi}(s) nπ(s) 表示在由 π \pi π 生成的很长的episode中 s s s 被访问的次数。

那么, d π ( s ) d_{\pi}(s) dπ(s) 可以近似为:
d π ( s ) ≈ n π ( s ) ∑ s ′ ∈ S n π ( s ′ ) d_\pi(s)\approx\frac{n_\pi(s)}{\sum_{s^{\prime}\in\mathcal{S}}n_\pi(s^{\prime})} dπ(s)sSnπ(s)nπ(s)
在这里插入图片描述

收敛值是可以预测的,因为它们是 d π d_{\pi} dπ 的条目:
d π T = d π T P π d_\pi^T=d_\pi^TP_\pi dπT=dπTPπ
对于这个例子,有 P π P_{\pi} Pπ 作为:
P π = [ 0.3 0.1 0.6 0 0.1 0.3 0 0.6 0.1 0 0.3 0.6 0 0.1 0.1 0.8 ] \left.P_\pi=\left[\begin{array}{cccc}0.3&0.1&0.6&0\\0.1&0.3&0&0.6\\0.1&0&0.3&0.6\\0&0.1&0.1&0.8\end{array}\right.\right] Pπ= 0.30.10.100.10.300.10.600.30.100.60.60.8
可以计算出1的特征值的左特征向量为:
d π = [ 0.0345 , 0.1084 , 0.1330 , 0.7241 ] T d_\pi=\begin{bmatrix}0.0345,0.1084,0.1330,0.7241\end{bmatrix}^T dπ=[0.0345,0.1084,0.1330,0.7241]T

Optimization algorithms

当有了目标函数后,下一步就是优化它。

为了最小化目标函数 J ( w ) J(w) J(w),可以使用梯度下降算法:
w k + 1 = w k − α k ∇ w J ( w k ) w_{k+1}=w_k-\alpha_k\nabla_wJ(w_k) wk+1=wkαkwJ(wk)
真实梯度为:
∇ w J ( w ) = ∇ w E [ ( v π ( S ) − v ^ ( S , w ) ) 2 ] = E [ ∇ w ( v π ( S ) − v ^ ( S , w ) ) 2 ] = 2 E [ ( v π ( S ) − v ^ ( S , w ) ) ( − ∇ w v ^ ( S , w ) ) ] = − 2 E [ ( v π ( S ) − v ^ ( S , w ) ) ∇ w v ^ ( S , w ) ] \begin{aligned} \nabla_wJ(w)& =\nabla_w\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))^2] \\ &=\mathbb{E}[\nabla_w(v_\pi(S)-\hat{v}(S,w))^2] \\ &=2\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))(-\nabla_w\hat{v}(S,w))] \\ &=-2\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))\nabla_w\hat{v}(S,w)] \end{aligned} wJ(w)=wE[(vπ(S)v^(S,w))2]=E[w(vπ(S)v^(S,w))2]=2E[(vπ(S)v^(S,w))(wv^(S,w))]=2E[(vπ(S)v^(S,w))wv^(S,w)]
真实梯度涉及期望的计算。

可以使用随机梯度来代替真实梯度:
w t + 1 = w t + α t ( v π ( s t ) − v ^ ( s t , w t ) ) ∇ w v ^ ( s t , w t ) , w_{t+1}=w_t+\alpha_t(v_\pi(s_t)-\hat{v}(s_t,w_t))\nabla_w\hat{v}(s_t,w_t), wt+1=wt+αt(vπ(st)v^(st,wt))wv^(st,wt),
其中 s t s_t st S S S的样本。这里, 2 α k 2\alpha_k 2αk被合并到 α k \alpha_k αk

该算法无法实现,因为它需要真实的state value v π v_{\pi} vπ,而 v π v_{\pi} vπ是待估计的未知数。

为了保证算法的可行性,可以用近似值替换 v π ( s t ) v_{\pi}(s_t) vπ(st)

特定来说:

一、使用函数逼近的Monte Carlo learning

g t g_t gt 为该episode中从 s t s_t st开始的discounted return。 然后, g t g_t gt可以用来近似 v π ( s t ) v_{\pi}(s_t) vπ(st)。 算法变为:
w t + 1 = w t + α t ( g t − v ^ ( s t , w t ) ) ∇ w v ^ ( s t , w t ) . w_{t+1}=w_t+\alpha_t(g_t-\hat{v}(s_t,w_t))\nabla_w\hat{v}(s_t,w_t). wt+1=wt+αt(gtv^(st,wt))wv^(st,wt).
二、函数逼近的TD learning
根据TD learning的理念, r t + 1 + γ v ^ ( s t + 1 , w t ) r_{t+1}+\gamma\hat{v}(s_{t+1},w_t) rt+1+γv^(st+1,wt)可以被视为 v π ( s t ) v_{\pi}(s_t) vπ(st)的近似。 那么算法就变成了:
w t + 1 = w t + α t [ r t + 1 + γ v ^ ( s t + 1 , w t ) − v ^ ( s t , w t ) ] ∇ w v ^ ( s t , w t ) . w_{t+1}=w_t+\alpha_t\left[r_{t+1}+\gamma\hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)\right]\nabla_w\hat{v}(s_t,w_t). wt+1=wt+αt[rt+1+γv^(st+1,wt)v^(st,wt)]wv^(st,wt).
在这里插入图片描述

它只能估计给定policy的state value。

Selection of function approximators

如何选择函数 v ^ ( s , w ) \hat{v}(s,w) v^(s,w)

第一种方法是以前广泛使用的,使用线性函数:
v ^ ( s , w ) = ϕ T ( s ) w \hat{v}(s,w)=\phi^T(s)w v^(s,w)=ϕT(s)w
这里, ϕ ( s \phi (s ϕ(s)是特征向量,可以是多项式基、傅立叶基等。

第二种是现在广泛使用的以神经网络作为非线性函数逼近器。

神经网络的输入是state,输出是 v ^ ( s , w ) \hat{v}(s,w) v^(s,w),网络参数是 w w w

v ^ ( s , w ) = ϕ T ( s ) w \hat{v}(s,w)=\phi^T(s)w v^(s,w)=ϕT(s)w 的线性情况下,有:
∇ w v ^ ( s , w ) = ϕ ( s ) . \nabla_w\hat{v}(s,w)=\phi(s). wv^(s,w)=ϕ(s).
将梯度代入TD算法:
w t + 1 = w t + α t [ r t + 1 + γ v ^ ( s t + 1 , w t ) − v ^ ( s t , w t ) ] ∇ w v ^ ( s t , w t ) w_{t+1}=w_t+\alpha_t\left[r_{t+1}+\gamma\hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)\right]\nabla_w\hat{v}(s_t,w_t) wt+1=wt+αt[rt+1+γv^(st+1,wt)v^(st,wt)]wv^(st,wt)
可得:
w t + 1 = w t + α t [ r t + 1 + γ ϕ T ( s t + 1 ) w t − ϕ T ( s t ) w t ] ϕ ( s t ) w_{t+1}=w_t+\alpha_t\big[r_{t+1}+\gamma\phi^T(s_{t+1})w_t-\phi^T(s_t)w_t\big]\phi(s_t) wt+1=wt+αt[rt+1+γϕT(st+1)wtϕT(st)wt]ϕ(st)
这是线性函数逼近的TD learning算法。 简称为 TD-Linear。

线性函数近似的缺点:很难选择合适的特征向量。

线性函数近似的优点:

  • TD 算法在线性情况下的理论特性比在非线性情况下更容易理解。
  • 线性函数逼近仍然很强大,因为表格表示只是线性函数逼近的一个特例。

表格表示是线性函数近似的特例

首先,考虑state s s s 的特殊特征向量:
ϕ ( s ) = e s ∈ R ∣ S ∣ , \phi(s)=e_s\in\mathbb{R}^{|\mathcal{S}|}, ϕ(s)=esRS,
其中 e s e_s es 是一个向量,第 s s s 个条目为 1,其他条目为 0。

在这种情况下,
v ^ ( s , w ) = e s T w = w ( s ) , \hat{v}(s,w)=e_s^Tw=w(s), v^(s,w)=esTw=w(s),
其中 w ( s ) w(s) w(s) w w w 的第 s s s 个条目。

TD 线性算法是:
w t + 1 = w t + α t [ r t + 1 + γ ϕ T ( s t + 1 ) w t − ϕ T ( s t ) w t ] ϕ ( s t ) , w_{t+1}=w_t+\alpha_t\big[r_{t+1}+\gamma\phi^T(s_{t+1})w_t-\phi^T(s_t)w_t\big]\phi(s_t), wt+1=wt+αt[rt+1+γϕT(st+1)wtϕT(st)wt]ϕ(st),
ϕ ( s t ) = e s \phi (s_t) = e_s ϕ(st)=es 时,上述算法变为:
w t + 1 = w t + α t ( r t + 1 + γ w t ( s t + 1 ) − w t ( s t ) ) e s t . w_{t+1}=w_t+\alpha_t\left(r_{t+1}+\gamma w_t(s_{t+1})-w_t(s_t)\right)e_{s_t}. wt+1=wt+αt(rt+1+γwt(st+1)wt(st))est.
这是一个向量方程,仅更新 w t w_t wt 的第 t t t 个条目。

e s t T e^T_{s_t} estT 等式两边相乘得到:
w t + 1 ( s t ) = w t ( s t ) + α t ( r t + 1 + γ w t ( s t + 1 ) − w t ( s t ) ) , w_{t+1}(s_t)=w_t(s_t)+\alpha_t\left(r_{t+1}+\gamma w_t(s_{t+1})-w_t(s_t)\right), wt+1(st)=wt(st)+αt(rt+1+γwt(st+1)wt(st)),
这正是表格TD算法。

Illustrative examples

给定一个policy:对于任何 s s s a a a π ( a ∣ s ) = 0.2 \pi(a|s) = 0.2 π(as)=0.2

目标是估计该policy的state value(policy evaluation问题)。

总共有 25 个state value。 接下来将展示如何使用少于 25 个参数来近似这些state value。

设置: r f o r b i d d e n = r b o u n d a r y = − 1 , r t a r g e t = 1 r_{\mathrm{forbidden}}=r_{\mathrm{boundary}}=-1,r_{\mathrm{target}}=1 rforbidden=rboundary=1,rtarget=1, γ = 0.9. \gamma=0.9. γ=0.9.

在这里插入图片描述

Ground truth:

真实状态值和 3D 可视化:

在这里插入图片描述

Experience 样本:

  • 按照给定的policy生成 500 个episode。
  • 每episode有 500 步,从遵循均匀分布的随机选择的state-action对开始。

为了进行比较,tabular TD算法(简称TD-Table)给出的结果:

在这里插入图片描述

接下来展示 TD-Linear 算法的结果:

特征向量选择:
ϕ ( s ) = [ 1 x y ] ∈ R 3 . \left.\phi(s)=\left[\begin{array}{c}1\\x\\y\end{array}\right.\right]\in\mathbb{R}^3. ϕ(s)= 1xy R3.
在这种情况下,近似state value为:
v ^ ( s , w ) = ϕ T ( s ) w = [ 1 , x , y ] [ w 1 w 2 w 3 ] = w 1 + w 2 x + w 3 y . \left.\hat{v}(s,w)=\phi^T(s)w=[1,x,y]\left[\begin{array}{c}w_1\\w_2\\w_3\end{array}\right.\right]=w_1+w_2x+w_3y. v^(s,w)=ϕT(s)w=[1,x,y] w1w2w3 =w1+w2x+w3y.
值得注意的是, ϕ ( s ) \phi (s) ϕ(s) 也可以定义为 ϕ ( s ) = [ x , y , 1 ] T \phi (s) = [x, y, 1]^T ϕ(s)=[x,y,1]T ,其中元素的顺序并不重要。

TD-Linear 算法的结果:

在这里插入图片描述

趋势是对的,但由于逼近能力有限,存在误差。

为了增强逼近能力,可以使用高阶特征向量,从而使用更多参数。

例如,可以考虑:
ϕ ( s ) = [ 1 , x , y , x 2 , y 2 , x y ] T ∈ R 6 . \phi(s)=[1,x,y,x^2,y^2,xy]^T\in\mathbb{R}^6. ϕ(s)=[1,x,y,x2,y2,xy]TR6.
在这种情况下:
v ^ ( s , w ) = ϕ T ( s ) w = w 1 + w 2 x + w 3 y + w 4 x 2 + w 5 y 2 + w 6 x y \hat{v}(s,w)=\phi^T(s)w=w_1+w_2x+w_3y+w_4x^2+w_5y^2+w_6xy v^(s,w)=ϕT(s)w=w1+w2x+w3y+w4x2+w5y2+w6xy
其对应于二次曲面。

可以进一步增加特征向量的维度:
ϕ ( s ) = [ 1 , x , y , x 2 , y 2 , x y , x 3 , y 3 , x 2 y , x y 2 ] T ∈ R 10 . \begin{aligned}\phi(s)=[1,x,y,x^2,y^2,xy,x^3,y^3,x^2y,xy^2]^T\in\mathbb{R}^{10}.\end{aligned} ϕ(s)=[1,x,y,x2,y2,xy,x3,y3,x2y,xy2]TR10.
具有高阶特征向量的 TD-Linear 算法的结果:

在这里插入图片描述

上图对应: ϕ ( s ) ∈ R 6 \phi(s) \in \mathbb{R}^6 ϕ(s)R6

在这里插入图片描述

上图对应: ϕ ( s ) ∈ R 1 0 \phi(s) \in \mathbb{R}^10 ϕ(s)R10

Summary of the story

至此,完成了价值函数逼近TD learning的过程。

  • 这个过程从目标函数开始:
    J ( w ) = E [ ( v π ( S ) − v ^ ( S , w ) ) 2 ] . J(w)=\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))^2]. J(w)=E[(vπ(S)v^(S,w))2].
    目标函数表明这是一个policy evaluation问题。

  • 梯度下降算法为:
    w t + 1 = w t + α t ( v π ( s t ) − v ^ ( s t , w t ) ) ∇ w v ^ ( s t , w t ) , w_{t+1}=w_t+\alpha_t(v_\pi(s_t)-\hat{v}(s_t,w_t))\nabla_w\hat{v}(s_t,w_t), wt+1=wt+αt(vπ(st)v^(st,wt))wv^(st,wt),

  • 将算法中未知的真值函数替换为近似值,得到算法:
    w t + 1 = w t + α t [ r t + 1 + γ v ^ ( s t + 1 , w t ) − v ^ ( s t , w t ) ] ∇ w v ^ ( s t , w t ) . w_{t+1}=w_t+\alpha_t\left[r_{t+1}+\gamma\hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)\right]\nabla_w\hat{v}(s_t,w_t). wt+1=wt+αt[rt+1+γv^(st+1,wt)v^(st,wt)]wv^(st,wt).

Theoretical analysis

算法:
w t + 1 = w t + α t [ r t + 1 + γ v ^ ( s t + 1 , w t ) − v ^ ( s t , w t ) ] ∇ w v ^ ( s t , w t ) w_{t+1}=w_t+\alpha_t\left[r_{t+1}+\gamma\hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)\right]\nabla_w\hat{v}(s_t,w_t) wt+1=wt+αt[rt+1+γv^(st+1,wt)v^(st,wt)]wv^(st,wt)
不最小化以下目标函数:
J ( w ) = E [ ( v π ( S ) − v ^ ( S , w ) ) 2 ] J(w)=\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))^2] J(w)=E[(vπ(S)v^(S,w))2]
不同的目标函数:

  • 目标函数1:真值误差
    J E ( w ) = E [ ( v π ( S ) − v ^ ( S , w ) ) 2 ] = ∥ v ^ ( w ) − v π ∥ D 2 J_E(w)=\mathbb{E}[(v_\pi(S)-\hat{v}(S,w))^2]=\|\hat{v}(w)-v_\pi\|_D^2 JE(w)=E[(vπ(S)v^(S,w))2]=v^(w)vπD2

  • 目标函数2:Bellman误差
    J B E ( w ) = ∥ v ^ ( w ) − ( r π + γ P π v ^ ( w ) ) ∥ D 2 ≐ ∥ v ^ ( w ) − T π ( v ^ ( w ) ) ∥ D 2 , J_{BE}(w)=\|\hat{v}(w)-(r_\pi+\gamma P_\pi\hat{v}(w))\|_D^2\doteq\|\hat{v}(w)-T_\pi(\hat{v}(w))\|_D^2, JBE(w)=v^(w)(rπ+γPπv^(w))D2v^(w)Tπ(v^(w))D2,
    其中, T π ( x ) ≐ r π + γ P π x T_\pi(x)\doteq r_\pi+\gamma P_\pi x Tπ(x)rπ+γPπx

  • 目标函数 3:预计Bellman误差(Projected Bellman error)
    J P B E ( w ) = ∥ v ^ ( w ) − M T π ( v ^ ( w ) ) ∥ D 2 , \begin{aligned}J_{PBE}(w)&=\|\hat{v}(w)-MT_\pi(\hat{v}(w))\|_D^2,\end{aligned} JPBE(w)=v^(w)MTπ(v^(w))D2,
    其中 M M M 是投影矩阵。

TD-Linear算法最大限度地减少了Projected Bellman error。

Sarsa with function approximation

到目前为止,只考虑了state value估计的问题。
v ^ ≈ v π \hat{v}\approx v_\pi v^vπ
为了寻找最佳policy,需要估计action values。

价值函数近似的 Sarsa 算法为:
w t + 1 = w t + α t [ r t + 1 + γ q ^ ( s t + 1 , a t + 1 , w t ) − q ^ ( s t , a t , w t ) ] ∇ w q ^ ( s t , a t , w t ) . w_{t+1}=w_t+\alpha_t\left[r_{t+1}+\gamma\hat{q}(s_{t+1},a_{t+1},w_t)-\hat{q}(s_t,a_t,w_t)\right]\nabla_w\hat{q}(s_t,a_t,w_t). wt+1=wt+αt[rt+1+γq^(st+1,at+1,wt)q^(st,at,wt)]wq^(st,at,wt).
为了寻找最优policy,可以将policy evaluation和policy improvement结合起来。

在这里插入图片描述

Q-learning with function approximation

与 Sarsa 类似,tabular Q-learning也可以扩展到价值函数逼近的情况。

q-value更新规则为:
w t + 1 = w t + α t [ r t + 1 + γ max ⁡ a ∈ A ( s t + 1 ) q ^ ( s t + 1 , a , w t ) − q ^ ( s t , a t , w t ) ] ∇ w q ^ ( s t , a t , w t ) , w_{t+1}=w_t+\alpha_t\Big[r_{t+1}+\gamma\max_{a\in\mathcal{A}(s_{t+1})}\hat{q}(s_{t+1},a,w_t)-\hat{q}(s_t,a_t,w_t)\Big]\nabla_w\hat{q}(s_t,a_t,w_t), wt+1=wt+αt[rt+1+γaA(st+1)maxq^(st+1,a,wt)q^(st,at,wt)]wq^(st,at,wt),
与 Sarsa 相同,只是将 q ^ ( s t + 1 , a t + 1 , w t ) \hat{q}(s_{t+1},a_{t+1},w_t) q^(st+1,at+1,wt) 替换为 max ⁡ a ∈ A ( s t + 1 ) q ^ ( s t + 1 , a , w t ) \max_{a\in\mathcal{A}(s_{t+1})}\hat{q}(s_{t+1},a,w_t) maxaA(st+1)q^(st+1,a,wt)

在这里插入图片描述

Deep Q-learning

Deep Q-learning 或 deep Q-network (DQN):

将深度神经网络引入强化学习的最早、最成功的算法之一。

神经网络的作用是成为非线性函数逼近器。

与以下算法不同:
w t + 1 = w t + α t [ r t + 1 + γ max ⁡ a ∈ A ( s t + 1 ) q ^ ( s t + 1 , a , w t ) − q ^ ( s t , a t , w t ) ] ∇ w q ^ ( s t , a t , w t ) w_{t+1}=w_t+\alpha_t\Big[r_{t+1}+\gamma\max_{a\in\mathcal{A}(s_{t+1})}\hat{q}(s_{t+1},a,w_t)-\hat{q}(s_t,a_t,w_t)\Big]\nabla_w\hat{q}(s_t,a_t,w_t) wt+1=wt+αt[rt+1+γaA(st+1)maxq^(st+1,a,wt)q^(st,at,wt)]wq^(st,at,wt)
因为训练网络的方式。

Deep Q-learning旨在最小化目标函数/损失函数:
J ( w ) = E [ ( R + γ max ⁡ a ∈ A ( S ′ ) q ^ ( S ′ , a , w ) − q ^ ( S , A , w ) ) 2 ] , J(w)=\mathbb{E}\left[\left(R+\gamma\max_{a\in\mathcal{A}(S^{\prime})}\hat{q}(S^{\prime},a,w)-\hat{q}(S,A,w)\right)^2\right], J(w)=E[(R+γaA(S)maxq^(S,a,w)q^(S,A,w))2],
其中 ( S , A , R , S ′ ) (S, A, R, S') (S,A,R,S) 是随机变量。

这实际上是贝尔曼最优误差(Bellman optimality error):
q ( s , a ) = E [ R t + 1 + γ max ⁡ a ∈ A ( S t + 1 ) q ( S t + 1 , a ) ∣ S t = s , A t = a ] , ∀ s , a q(s,a)=\mathbb{E}\left[R_{t+1}+\gamma\max_{a\in\mathcal{A}(S_{t+1})}\left.q(S_{t+1},a)\right|S_t=s,A_t=a\right],\quad\forall s,a q(s,a)=E[Rt+1+γaA(St+1)maxq(St+1,a)St=s,At=a],s,a
R + γ max ⁡ a ∈ A ( S ′ ) q ^ ( S ′ , a , w ) − q ^ ( S , A , w ) R+\gamma\max_{a\in\mathcal{A}(S^{\prime})}\hat{q}(S^{\prime},a,w)-\hat{q}(S,A,w) R+γmaxaA(S)q^(S,a,w)q^(S,A,w)的值在期望意义上应该为0。

使用梯度下降最小化目标函数。

在目标函数中:
J ( w ) = E [ ( R + γ max ⁡ a ∈ A ( S ′ ) q ^ ( S ′ , a , w ) − q ^ ( S , A , w ) ) 2 ] , J(w)=\mathbb{E}\left[\left(R+\gamma\max_{a\in\mathcal{A}(S^{\prime})}\hat{q}(S^{\prime},a,w)-\hat{q}(S,A,w)\right)^2\right], J(w)=E[(R+γaA(S)maxq^(S,a,w)q^(S,A,w))2],
参数 w w w 不仅出现在 q ^ ( S , A , w ) \hat{q}(S, A, w) q^(S,A,w) 中,而且还出现在:
y ≐ R + γ max ⁡ a ∈ A ( S ′ ) q ^ ( S ′ , a , w ) y\doteq R+\gamma\max_{a\in\mathcal{A}(S^{\prime})}\hat{q}(S^{\prime},a,w) yR+γaA(S)maxq^(S,a,w)
为了简单起见,可以假设在计算梯度时, y y y 中的 w w w 是固定的(至少在一段时间内)。

为此,可以引入两个网络。

  • 一个是代表 q ^ ( s , a , w ) \hat{q}(s, a, w) q^(s,a,w) 的主网络
  • 另一个是目标网络 q ^ ( s , a , w T ) \hat{q}(s, a, w_T) q^(s,a,wT)

在这种情况下,目标函数退化为:
J = E [ ( R + γ max ⁡ a ∈ A ( S ′ ) q ^ ( S ′ , a , w T ) − q ^ ( S , A , w ) ) 2 ] , J=\mathbb{E}\left[\left(R+\gamma\max_{a\in\mathcal{A}(S^{\prime})}{\hat{q}(S^{\prime},a,w_T)-\hat{q}(S,A,w)}\right)^2\right], J=E[(R+γaA(S)maxq^(S,a,wT)q^(S,A,w))2],
其中 w T w_T wT 是目标网络参数。

w T w_T wT 固定时, J J J 的梯度可以很容易地得到:
∇ w J = E [ ( R + γ max ⁡ a ∈ A ( S ′ ) q ^ ( S ′ , a , w T ) − q ^ ( S , A , w ) ) ∇ w q ^ ( S , A , w ) ] . \nabla_wJ=\mathbb{E}\left[\left(R+\gamma\max_{a\in\mathcal{A}(S^{\prime})}{\hat{q}(S^{\prime},a,w_T)-\hat{q}(S,A,w)}\right)\nabla_w\hat{q}(S,A,w)\right]. wJ=E[(R+γaA(S)maxq^(S,a,wT)q^(S,A,w))wq^(S,A,w)].

  • deep Q-learning 的基本思想是利用梯度下降算法来最小化目标函数。
  • 然而,这样的优化过程发展了一些值得特别关注的重要技术。

第一个技术:

两个网络,一个主网络和一个目标网络。

实施细节:

  • w w w w T w_T wT 分别表示主网络和目标网络的参数。 它们最初设置为相同。
  • 在每次迭代中,从重放缓冲区(replay buffer)中抽取一小批样本 { ( s , a , r , s ′ ) } \{(s, a, r, s' )\} {(s,a,r,s)}
  • 网络的输入包括state s s s 和action a。 目标输出为 y T ≐ r + γ max ⁡ a ∈ A ( s ′ ) q ^ ( s ′ , a , w T ) \begin{aligned}y_T\doteq r+\gamma\max_{a\in\mathcal{A}(s')}\hat{q}(s',a,w_T)\end{aligned} yTr+γaA(s)maxq^(s,a,wT)。 然后,直接最小化小批量 { ( s , a , y T ) } \{(s, a, y_T )\} {(s,a,yT)} 上的 TD 误差或称为损失函数 ( y T − q ^ ( s , a , w ) ) 2 (y_T − \hat{q}(s, a, w))^2 (yTq^(s,a,w))2

第二个技术

Experience replay

当收集了一些经验样本后,不会按照收集的顺序使用这些样本。

相反,我们将它们存储在一个集合中,称为重播缓冲区(replay buffer) B ≐ { ( s , a , r , s ′ ) } \mathcal{B}\doteq\{(s,a,r,s^{\prime})\} B{(s,a,r,s)}

每次训练神经网络时,都可以从replay buffer中抽取 mini-batch 随机样本。

样本的抽取,或者称为experience replay,应该遵循均匀分布。

Why is experience replay necessary in deep Q-learning? Why does the replay must follow a uniform distribution?

答案在目标函数中:
J ( w ) = E [ ( R + γ max ⁡ a ∈ A ( S ′ ) q ^ ( S ′ , a , w ) − q ^ ( S , A , w ) ) 2 ] , J(w)=\mathbb{E}\left[\left(R+\gamma\max_{a\in\mathcal{A}(S^{\prime})}\hat{q}(S^{\prime},a,w)-\hat{q}(S,A,w)\right)^2\right], J(w)=E[(R+γaA(S)maxq^(S,a,w)q^(S,A,w))2],
( S , A ) ∼ d (S,A)\sim d (S,A)d ( S , A ) (S, A) (S,A)是一个索引并被视为单个随机变量。

R ∼ p ( R ∣ S , A ) , S ′ ∼ p ( S ′ ∣ S , A ) \begin{aligned}R&\sim p(R|S,A),S'\sim p(S'|S,A)\end{aligned} Rp(RS,A),Sp(SS,A) R R R S S S由系统模型决定。

假设state-action对 ( S , A ) (S, A) (S,A) 的分布是均匀的。

然而,样本并不是统一收集的,因为它们是由某些policy产生的。

为了打破后续样本之间的相关性,可以使用经验回放(experience replay)技术,从replay buffer中统一抽取样本。

这就是为什么经验回放(experience replay)是必要的以及为什么经验回放必须统一的数学原因。

tabular Q-learning vs. deep Q-learning:

为什么tabular Q-learning不需要经验回放(experience replay)?

tabular Q-learning无均匀分布要求。

为什么deep Q-learning涉及分布?

深层情况下目标函数是所有 ( S , A ) (S, A) (S,A) 的标量平均值。 表格情况不涉及 S S S A A A的任何分布。表格情况下的算法旨在求解所有 ( s , a ) (s,a) (s,a)的一组方程(Bellman最优方程)。

可以在tabular Q-learning中使用经验回放吗?

可以。tabular Q-learning既可以是on-policy的也可以是off-policy的。在其是off-policy情况时,可以受用经验回放。

在这里插入图片描述

Example:

此示例旨在学习每个state-action 对的最佳action value。

一旦获得最优action value,就可以立即得到最优贪心policy。

设置:

  • 使用一个单独的episode来训练网络。
  • 这一episode是由图(a)所示的探索性行为policy生成的
  • episode只有 1,000 步。 tabular Q-learning 需要 100,000 个步。
  • 具有一个隐藏层的浅层神经网络被用作 q ^ ( s , a , w ) \hat{q}(s, a, w) q^(s,a,w)的非线性逼近器。 隐藏层有 100 个神经元。

在这里插入图片描述

在这里插入图片描述

仅使用 100 步的episode:

在这里插入图片描述

请添加图片描述

Summary

This lecture introduces the method of value function approximation.

  • First, understand the basic idea.
  • Second, understand the basic algorithms.




以上内容为B站西湖大学智能无人系统 强化学习的数学原理 公开课笔记。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/397535.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

重铸安卓荣光——上传图片组件

痛点: 公司打算做安卓软件,最近在研究安卓,打算先绘制样式 研究发现安卓并不像前端有那么多组件库,甚至有些基础的组件都需要自己实现,记录一下自己实现的组件 成品展示 一个上传图片的组件 可以选择拍照或者从相册中…

RSA之前端加密后端解密

RSA之前端加密后端解密 RSA加密解密方式有: (1)公钥加密,私钥解密; (2)私钥加密,公钥解密; 此文章中以下我使用的是前端公钥加密,后端私钥解密; …

提升竞争力!攻读在职硕士为职业发展加冕——社科院与杜兰大学金融管理硕士

在现如今竞争激烈的职场环境中,不断提升自身的竞争力是每个职场人士都面临的重要任务。攻读在职硕士学位成为越来越多人实现个人职业发展目标的首选方式之一。特别是社科院与杜兰大学合作开设的金融管理硕士项目,为那些希望在金融行业取得突破的职业人士…

欢迎来到IT时代----盘点曾经爆火全网的计算机电影

计算机专业必看的几部电影 计算机专业必看的几部电影,就像一场精彩的编程盛宴!《黑客帝国》让你穿越虚拟世界,感受高科技的魅力;《社交网络》揭示了互联网巨头的创业之路,《源代码》带你穿越时间解救世界,这…

智慧驿站_智慧文旅驿站_轻松的驿站智慧公厕_5G智慧公厕驿站_5G模块化智慧公厕

多功能城市智慧驿站是在智慧城市建设背景下,所涌现的一种创新型社会配套设施。其中,智慧公厕作为城市智慧驿站的重要功能基础,具备社会配套不可缺少的特点,所以在应用场景上,拥有广泛的需求和要求。那么,城…

java-kotlin踩坑:错误:找不到符号(点击能跳转到对应类中)

问题描述: 在android用java调用一个kotlin定义的类时,导包正常,点击也能跳转到对应类中,但是在编译运行时会报错,提示找不到符号 解决方法: 第一步:在app级别的build.gradle中添加kotlin-and…

HarmonyOS4.0系统性深入开发35 弹性布局(Flex)

弹性布局(Flex) 概述 弹性布局(Flex)提供更加有效的方式对容器中的子元素进行排列、对齐和分配剩余空间。容器默认存在主轴与交叉轴,子元素默认沿主轴排列,子元素在主轴方向的尺寸称为主轴尺寸&#xff0…

【动态规划专栏】专题一:斐波那契数列模型--------4.解码方法

本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小…

blasterswap明牌空投

空投要点 明牌空投,blaster生态第一个swap,应该不会寒酸交互简单,仅需3步,零gas费仅仅要求加密钱包在eth链有过交易需要有x和discord账号 blasterswap空投简介 BlasterSwap 是Blast生态里面第一个SWAP项目,近期启动…

国开电大计算机科学与技术网络技术与应用试题及答案,分享几个实用搜题和学习工具 #媒体#其他#知识分享

这些软件以其强大的搜索引擎和智能化的算法,为广大大学生提供了便捷、高效的解题方式。下面,让我们一起来了解几款备受大学生欢迎的搜题软件吧! 1.三羊搜题 这个是公众号 支持文字和语音查题!!! 学习通,知到,mooc等等平台的网课题目答案都…

OpenCV 4基础篇| 色彩空间类型转换

目录 1. 色彩空间基础2. 色彩空间类型2.1 GRAY 色彩空间2.2 BGR 色彩空间2.3 CMY(K) 色彩空间2.4 XYZ 色彩空间2.5 HSV 色彩空间2.6 HLS 色彩空间2.7 CIEL*a*b* 色彩空间2.8 CIEL*u*v* 色彩空间2.9 YCrCb 色彩空间 3. 类型转换函数3.1 cv2.cvtColor3.2 cv2.inRange 1. 色彩空间…

Fiddler与wireshark使用

Fiddler解决三个问题 1、SSL证书打勾,解析https请求 2、响应回来乱码,不是中文 3、想及时中止一下,查看实时的日志 4、搜索对应的关键字 问题1解决方案: 标签栏Tools下 找到https,全部打勾 Actions里面 第一个 t…

怎么在电脑上做工作笔记?电脑桌面电子笔记软件

在繁忙的职场中,随时随地记录工作笔记是许多职场人士的日常需求。这不仅包括了会议记录、项目进展,还有一些灵感、规划和工作要点,都需要随手记下,以便随时查看和回顾。那么我们如何在电脑上做工作笔记更高效、便捷呢?…

文献学习-1-Continuum Robots for Medical Interventions

Chapt 5. 连续体机构分析 5.1 文献学习 5.1.1 Continuum Robots for Medical Interventions Authors: PIERRE E. DUPONT , Fellow IEEE, NABIL SIMAAN , Fellow IEEE, HOWIE CHOSET , Fellow IEEE, AND CALEB RUCKER , Member IEEE 连续体机器人在医学上得到了广泛的应用&a…

爱校对软件——清华大学研发的全能文字处理助手

随着数字化和信息化的深入发展,高效、准确的文字处理工具成为了各行各业的迫切需求。清华大学人机交互实验室推出的“爱校对”软件,作为一款先进的文字处理工具,正逐渐成为专业编辑、写作者、学生、法律从业者、政府工作人员、商业从业者、出…

计算机视觉学习指南(划分为20个大类)

计算机视觉的知识领域广泛而庞杂,涵盖了众多重要的方向和技术。为了更好地组织这些知识,我们需要遵循无交叉无重复(Mutually Exclusive Collectively Exhaustive,MECE)的原则,并采用循序渐进的方式进行分类…

开发一款招聘小程序需要具备哪些功能?

随着时代的发展,找工作的方式也在不断变得简单,去劳务市场、人才市场的方式早就已经过时了,现在大多数年轻人都是直接通过手机来找工作。图片 找工作类的平台不但能扩大企业的招聘渠道,还能节省招聘的成本,方便求职者进…

Solidworks:钣金的折弯系数、K因子、折弯扣除

在SolidWorks的钣金件设计中,“折弯系数”、“K因子”和“折弯扣除”都是与折弯加工相关的重要参数。 “折弯系数”是一个用于描述金属材料在折弯过程中应力分布非均匀性的指标。它反映了金属板材在弯曲时内外表面应力的分布情况,是判断材料是否适合进行…

音乐与步伐同行:南卡、韶音和墨觉的骨传导耳机深度评测

在快节奏的现代生活中,音乐成为了许多人精神慰藉的方式之一。特别是对于那些热爱运动的人来说,音乐不仅是他们运动过程中的最佳伴侣,更是激发潜力,突破极限的源动力。但是在运动的过程中如何享受到最佳的音乐体验呢?这…

DAY20 结构和其他数据形式(上)【一万六千字超详细】

文章目录 前言14.1 示例问题:创建图书目录14.2建立结构声明14.3定义结构变量14.3.1 初始化结构14.3.2 访问结构成员14.3.2 结构的初始化器 14.4 结构数组14.4.1 声明结构数组14.4.2 标识结构数组的成员 14.3 嵌套结构14.6 指向结构的指针14.6.1 声明和初始化结构指针…