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} S∈S的。关于 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]=∣S∣1s∈S∑(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)}s∈S 表示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 ∑s∈Sdπ(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]=s∈S∑dπ(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)≈∑s′∈Snπ(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−αk∇wJ(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(gt−v^(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)=es∈R∣S∣,
其中
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 π(a∣s)=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]T∈R6.
在这种情况下:
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]T∈R10.
具有高阶特征向量的 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))∥D2≐∥v^(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+γa∈A(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)
maxa∈A(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+γa∈A(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+γa∈A(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+γa∈A(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+γmaxa∈A(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+γa∈A(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)
y≐R+γa∈A(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+γa∈A(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+γa∈A(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} yT≐r+γa∈A(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 (yT−q^(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+γa∈A(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} R∼p(R∣S,A),S′∼p(S′∣S,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站西湖大学智能无人系统 强化学习的数学原理 公开课笔记。