前面的一篇博客:Model-free control:如何从经验中学习一个好的策略 到目前为止,我们都假设了可以将价值函数或state-action价值(即Q函数)表示成向量或者矩阵
表格表示法很多现实世界的问题会有巨大的状态空间 和/或 动作空间 表格表示法是不够用(insufficient)的
使用一个参数化的函数来表示一个(state-action/state)价值函数而不是一张表格 w可以是一个网络或者多项式。
不希望对每一个状态a都要显式的学习或储存
动态模型或回报模型价值state-action价值(Q值)策略希望有更完备的表示,能在状态和状态之间或者状态-动作和状态-动作之间泛化
可能不是非常好的近似,可能不会使得你能够表示一个好的策略。这会是一个bias-variance的权衡(trade-off)在加上一个函数近似权衡。你有一个非常小的表示,不需要大量数据来拟合,但它同样不会有好的容量去表示复杂的价值或策略。
在函数近似这方面,有大量可选的函数近似器,我们该选择哪一个?
大量可能的函数近似器包括
特征的线性组合神经网络决策树近邻算法Fourier / wavelet bases在这篇博文里我们关注可微的函数近似器(想想看,为什么)
两类非常流行的可微函数近似器(in RL)
线性特征表示(here)神经网络(可能会写到下一篇博文)线性特征表示是前几年研究的最多的近似器。
∇ w J ( w ) = E π [ 2 ( V π ( s ) − V ~ ( s , w ) ) ] ∇ w V \nabla_w J(w)=E_\pi[2(V^\pi(s)-\tilde{V}(s,w))] \nabla_w V ∇wJ(w)=Eπ[2(Vπ(s)−V~(s,w))]∇wV Δ w = α ( V π ( s ) − V ~ ( s , w ) ) ∇ w V ( s ) \Delta w=\alpha(V^\pi(s)-\tilde{V}(s,w)) \nabla_w V(s) Δw=α(Vπ(s)−V~(s,w))∇wV(s) updating w
当然,现实中我们没有能力去分辨任何状态s的 V π ( s ) V^\pi(s) Vπ(s)
现在考虑如何做model-free的价值函数近似用于在没有模型的条件下进行预测/评估/策略评估
回顾不依赖模型的策略评估
遵循一个固定的策略(或者能够访问之前的数据)目标是估计 V π V^\pi Vπ和/或 Q π Q^\pi Qπ维护一张可查表来存储 V π V^\pi Vπ和/或 Q π Q^\pi Qπ的估计 在每一个周期结束之后更新这些估计(蒙特·卡罗尔方法)或每一步之后(TD方法)
现在:在价值函数近似,更改估计更新的步骤把拟合函数近似器包括进去
使用一个特征向量来表示一个状态s x ( s ) = { x 1 ( s ) x 1 ( s ) . . . x n ( s ) x(s)= \begin{cases} x_1(s) \\ x_1(s) \\ ... \\ x_n(s) \\ \end{cases} x(s)=⎩⎪⎪⎪⎨⎪⎪⎪⎧x1(s)x1(s)...xn(s)
这个特征向量非常原始,非常简单,可能不是马尔科夫的,但是合理的。
特征表示的选择非常重要。
用一个加权的线性组合来表示一个特定策略的价值函数(或者state-action价值函数) V ^ ( s : w ) = ∑ j = 1 n x j ( s ) w j = x ( s ) T w \hat{V}(s:w)=\sum_{j=1}^nx_j(s)w_j=x(s)^{\Tau} \bf{w} V^(s:w)=j=1∑nxj(s)wj=x(s)Tw
目标函数是 J ( w ) = E π [ ( V π ( s ) − V ^ ( s ; w ) ) 2 ] J(\textbf{w})=\mathbb{E}_\pi[(V^\pi(s)-\hat{V}(s;\textbf{w}))^2] J(w)=Eπ[(Vπ(s)−V^(s;w))2]
权重更新是 Δ w = − 1 2 α ∇ 2 J ( w ) \Delta \textbf{w} = -\frac{1}{2}\alpha \nabla_{\textbf{2}}J(\textbf{w}) Δw=−21α∇2J(w)
即 Δ w = − 1 2 α ( 2 ( V π ( s ) − V π ( a ; w ) ^ ) ) x ( s ) \Delta \textbf{w} =-\frac{1}{2}\alpha(2(V^\pi(s)-\hat{V^\pi(a;w)}))x(s) Δw=−21α(2(Vπ(s)−Vπ(a;w)^))x(s)
线性函数近似有一个优点,可以清晰直观地理解为 Update = step-size * prediction * feature value 三部分对应上面公式的三部分
回报 G t G_t Gt是一个无偏但含有噪点的真实回报 V π ( s t ) V^\pi(s_t) Vπ(st)的期望的采样 因此可以约减MC VFA到在一系列(state,return)对: < s 1 , G 1 > , < s 2 , G 2 > , . . . , < s T , G T > <s_1,G_1>,<s_2,G_2>,...,<s_\Tau,G_\Tau> <s1,G1>,<s2,G2>,...,<sT,GT>上执行监督学习
而在拟合函数近似器时用 G t G_t Gt替代真实 V π ( s t ) V^\pi(s_t) Vπ(st) 具体而言当使用线性VFA进行策略评估时: Δ w = α ( G t − V ^ ( s t ; w ) ) ∇ w V ^ ( s t ; w ) = α ( G t − V ^ ( s t ; w ) ) x ( s t ) = α ( G t − x ( s t ) T w ) x ( s t ) \begin{aligned} \Delta \textbf{w} = \alpha(G_t-\hat{V}(s_t;\textbf{w})) \nabla_{\textbf{w}}\hat{V}(s_t;\textbf{w}) \\ = \alpha(G_t-\hat{V}(s_t;\textbf{w})) \textbf{x}(s_t) \\ = \alpha(G_t-\textbf{x}(s_t)^\Tau \textbf{w})x(s_t) \\ \end{aligned} Δw=α(Gt−V^(st;w))∇wV^(st;w)=α(Gt−V^(st;w))x(st)=α(Gt−x(st)Tw)x(st) 注意: G t G_t Gt可能是一个噪声非常大的真实回报估计1 : I n i t i a l i z e w = 0 , k = 1 1:\ Initialize \ \textbf{w}=0, k =1 1: Initialize w=0,k=1 2 : l o o p 2:\ loop 2: loop 3 : S a m p l e k 3:\ \quad Sample \ k 3: Sample k-th episode ( s k , 1 , a k , 1 , r k , 1 , s k , 2 , . . . , s k , L k ) (s_{k,1},a_{k,1},r_{k,1},s_{k,2},...,s_{k,L_k}) (sk,1,ak,1,rk,1,sk,2,...,sk,Lk) given π \pi π 4 : f o r t = 1 , . . . . , L k d o 4:\ \quad for \ t=1,....,L_k \ do 4: for t=1,....,Lk do 5 : i f 5:\ \quad \quad if 5: if First visit to (s) in episode k t h e n k \ then k then 6 : G t ( s ) = ∑ j = t L k r k , j 6:\ \quad \quad \quad G_t(s)=\sum_{j=t}^{L_k} r_{k,j} 6: Gt(s)=∑j=tLkrk,j 7 : U p d a t e w e i g h t s : 7:\ \quad \quad \quad Update weights: 7: Updateweights: 8 : w = w + α ( G t ( s ) − V ^ ( s , w ) ) x ( s ) 8:\ \quad \quad \quad \quad \textbf{w} = \textbf{w} + \alpha(G_t(s)-\hat{V}(s,\textbf{w}))\textbf{x}(s) 8: w=w+α(Gt(s)−V^(s,w))x(s) 9 : e n d i f 9:\ \quad \quad end if 9: endif 10 : e n d f o r 10: \quad end for 10:endfor 11 : k = k + 1 11: \quad k=k+1 11:k=k+1 11 : e n d l o o p 11: end loop 11:endloop
算法同样可以改成every-visit。
第六行业可以加入 γ \gamma γ,变成 G t ( s ) = ∑ j = t L k r k , j γ j G_t(s)=\sum_{j=t}^{L_k} r_{k,j}\gamma^j Gt(s)=∑j=tLkrk,jγj,但在周期性的RL里,基本都是bounded的,所有 γ = 1 \gamma=1 γ=1也没关系。
基于一个特定策略的MDP所定义的马尔科夫链将会最终收敛到一个在状态之上的概率分布 d ( s ) d(s) d(s)
d ( s ) d(s) d(s)被称作策略 π \pi π上的驻点分布
∑ s d ( s ) = 1 \sum_sd(s)=1 ∑sd(s)=1
d ( s ) d(s) d(s)满足下列平衡方程:
d ( s ) = ∑ s ′ ∑ a π ( s ′ ∣ a ) p ( s ′ ∣ s , a ) d ( s ′ ) d(s)=\sum_{s'}\sum_a\pi(s'|a)p(s'|s,a)d(s') d(s)=∑s′∑aπ(s′∣a)p(s′∣s,a)d(s′) d ( s ′ ) = ∑ s ∑ a π ( a ∣ s ) p ( s ′ ∣ s , a ) d ( s ) d(s')=\sum_{s}\sum_a\pi(a|s)p(s'|s,a)d(s) d(s′)=∑s∑aπ(a∣s)p(s′∣s,a)d(s) 当马尔科夫链运行了足够长的时间,上述平衡方程都成立,这意味着,你在上一个状态的概率分布与下一个状态的概率分布完全一致。它告诉了你停留在一个特定状态的概率,但没有说明整个过程发生的时间。
1 ^1 1Tsitsiklis and Van Roy. An Analysis of Temporal-Difference Learning with Function Approximation. 1997. https:// web.standford.edu/bvr/pubs/td.pdf
设使用VFA的蒙特·卡罗尔策略评估收敛到权重 w M C \textbf{w}_{MC} wMC,那么该权重有可能有最小的均方误差: M S V E ( w M C ) = m i n w ∑ s ∈ S d ( s ) ( V π ( s ) − V ^ π ( s ; w ) ) 2 MSVE(\textbf{w}_{MC})=min_\textbf{w}\sum_{s \in S}d(s)(V^\pi(s)-\hat{V}^\pi(s;\textbf{w}))^2 MSVE(wMC)=minw∑s∈Sd(s)(Vπ(s)−V^π(s;w))2可能有一系列从策略 π \pi π(采样)而来的周期(episode)
能解析式地求解最小化在数据集上的最小均方误差的最佳线性近似
记 G ( s i ) G(s_i) G(si)是一个真实期望回报 V π ( s i ) V^\pi(s_i) Vπ(si)的无偏采样 a r g m i n w ∑ i = 1 N ( G ( s i ) − x ( s i ) T w ) 2 argmin_w \sum_{i=1}^{N}(G(s_i)-\textbf{x}(s_i)^\Tau \textbf{w})^2 argminwi=1∑N(G(si)−x(si)Tw)2
求导并设置为0: w = ( X τ X ) − 1 X T G \textbf{w}=(X^\tau X)^{-1}X^\Tau \textbf{G} w=(XτX)−1XTG
其中 G \textbf{G} G是一个向量全部N个回报组成的向量, X X X是每N个状态集中的每一个特征 x ( s i ) \textbf{x}(s_i) x(si)组成的矩阵
注意:因为是蒙特·卡罗尔方法,所有不做任何马尔科夫假设
但仍然是on policy的。
这样能利用函数价值近似约简TD(0) learning为在一系列数据对上执行监督学习
< s 1 , r 1 + γ V ^ π ( s 2 ; w ) > , < s 2 , r 2 + γ V ^ ( s 3 ; w ) > <s_1,r_1+\gamma \hat{V}^\pi(s_2;\textbf{w})>,<s_2,r_2+\gamma \hat{V}(s_3; \textbf{w})> <s1,r1+γV^π(s2;w)>,<s2,r2+γV^(s3;w)>寻求最小化均方误差的权重: J ( w ) = E π [ ( r j + r V ^ π ( s j + 1 , w ) ) − V ^ ( s j ; w ) ] 2 \textbf{J}(w)=\mathbb{E}_\pi[(r_j+r\hat{V}^\pi(s_{j+1},\textbf{w}))-\hat{V}(s_j;\textbf{w})]^2 J(w)=Eπ[(rj+rV^π(sj+1,w))−V^(sj;w)]2
在线性TD(0)中:
Δ w = α ( r + γ V ^ ( s ′ ; w ) − V ^ π ( s ; w ) ) ∇ w V ^ π ( s ; w ) = α ( r + γ V ^ ( s ′ ; w ) − V ^ π ( s ; w ) ) x ( s ) = α ( r + γ V ^ ( s ′ ; w ) − x ( s ) T w ) ) x ( s ) \begin{aligned} \Delta \textbf{w} = & \alpha(r+\gamma \hat{V}(s';\textbf{w})-\hat{V}^\pi(s;\textbf{w}))\nabla_\textbf{w}\hat{V}^\pi(s;\textbf{w}) \\ = &\alpha (r+\gamma \hat{V}(s';\textbf{w})-\hat{V}^\pi(s;\textbf{w}))\textbf{x}(s) \\ = & \alpha (r+\gamma \hat{V}(s';\textbf{w})-\textbf{x}(s)^\Tau\textbf{w}))\textbf{x}(s) \end{aligned} Δw===α(r+γV^(s′;w)−V^π(s;w))∇wV^π(s;w)α(r+γV^(s′;w)−V^π(s;w))x(s)α(r+γV^(s′;w)−x(s)Tw))x(s) 这篇博客以及之前的介绍的都是TD(0),事实上,它有非常多的变种,称为TD lambda。TD(0)是最流行的,也有其他的扩展,为了便于理解,我们暂时只关注TD(0)。
看起来非常像蒙特•卡罗尔,除了我们现在做的是bootstrapping。
1 : I n i t i a l i z e w = 0 , k = 1 1: Initialize \ \textbf{w}=0, \ k=1 1:Initialize w=0, k=1 2 : l o o p 2: loop 2:loop 3 : 3: \qquad 3: Sample tuple ( s k , a k , r k , s k + 1 ) (s_k,a_k,r_k,s_{k+1}) (sk,ak,rk,sk+1) given π \pi π 4 : 4: \qquad 4: Update weights: 5 : w = w + α ( r + γ x ( s ′ ) T w − x ( s ) T w ) x ( s ) 5: \qquad\qquad \textbf{w} = \textbf{w}+\alpha(r+\gamma\textbf{x}(s')^\Tau\textbf{w}-\textbf{x}(s)^\Tau\textbf{w})\textbf{x}(s) 5:w=w+α(r+γx(s′)Tw−x(s)Tw)x(s) 6 : k = k + 1 6: \qquad k = k+1 6:k=k+1 7 : e n d l o o p 7: end loop 7:endloop
对比一下前面蒙特•卡罗尔的例子,和蒙特•卡罗尔计算的结果一致。 但TD learning仅仅更新那些小的局部变化,比如一个状态-动作回报或者下一个;蒙特•卡罗尔更新一整个周期的回报。所以TD更新比蒙特•卡罗尔小,与之前看到的没有函数近似器的版本类似。
定义一个特定策略 π \pi π的线性价值方程相对于真实值的均方误差为 M S V E ( w ) = ∑ s ∈ S d ( s ) ( V π ( s ) − V ^ π ( s ; w ) ) 2 MSVE(\textbf{w})=\sum_{s\in S}d(s)(V^\pi(s)-\hat{V}^\pi(s;\textbf{w}))^2 MSVE(w)=s∈S∑d(s)(Vπ(s)−V^π(s;w))2
其中
d(s): π \pi π在真实决策过程的驻点分布 V ^ π ( s ; w ) = x ( s ) T w \hat{V}^\pi(s;\textbf{w})=\textbf{x}(s)^\Tau \textbf{w} V^π(s;w)=x(s)Tw,一个线性价值函数近似使用VFA的TD(0) 策略评估收敛到权重 w T D \textbf{w}_{TD} wTD,它是可能的最小均方误差的常数倍。 M S V E ( w T D ) ≤ 1 1 − γ m i n w ∑ s ∈ S d ( s ) ( V π ( s ) − V ^ π ( s ; w ) ) 2 MSVE(\textbf{w}_{TD})\leq\frac{1}{1-\gamma}min_{\textbf{w}}\sum_{s\in S}d(s)(V^\pi(s)-\hat{V}^\pi(s;w))^2 MSVE(wTD)≤1−γ1minw∑s∈Sd(s)(Vπ(s)−V^π(s;w))2
虽不像Monte Carlo那样好,但也相当好了。
定义一个特定策略的线性价值函数近似相对于真实值的均方误差为: M S V E ( w ) = ∑ s ∈ S d ( s ) ( V π ( s ) − V ^ π ( s ; w ) ) MSVE(\textbf{w})=\sum_{s\in S}d(s)(V^\pi(s)-\hat{V}^\pi(s;\textbf{w})) MSVE(w)=s∈S∑d(s)(Vπ(s)−V^π(s;w))
使用VFA的TD(0) 策略评估收敛到权重 w T D \textbf{w}_{TD} wTD,它是可能的最小均方误差的常因子。 M S V E ( w T D ) ≤ 1 1 − γ m i n w ∑ s ∈ S d ( s ) ( V π ( s ) − V ^ π ( s ; w ) ) 2 MSVE(\textbf{w}_{TD})\leq\frac{1}{1-\gamma}min_{\textbf{w}}\sum_{s\in S}d(s)(V^\pi(s)-\hat{V}^\pi(s;w))^2 MSVE(wTD)≤1−γ1minw∑s∈Sd(s)(Vπ(s)−V^π(s;w))2
如果VFA是一个表格表示(tabular representation) (一个状态有一个特征),那么MC和TD的MSVE是? MC是0,因为能精确表示,所以没有误差。 因为MC是zero,TD是MC的常数倍,所以TD也是0。
实验上通常TD会更好,实际操作时boostrapping通常有提升。
TD或者MC能更快地收敛到固定点吗?
没有被确定地理解(据我所知)
实践时TD learning通常能更快收敛到它函数近似点的固定值
使用价值函数近似来表示状态-动作价值 Q ^ π ( s , a ; w ) ≈ Q π \hat{Q}^\pi(s,a;\textbf{w})\approx Q^\pi Q^π(s,a;w)≈Qπ
交替
使用价值函数近似来近似策略评估执行 ϵ − \epsilon- ϵ−greedy策略提升可能是不稳定的。通常包含以下过程的交叉:
函数近似BootstrappingOff-policy learnnig(离线学习) (其实也有Sampling)不稳定最大的影响因素是Off-policy learning.
这通常被称作The Deadly Triad(死亡三件套),一旦组合这三样,可能会收敛失败或者收敛到不太好的地方。
使用特征来同时表示状态和动作 x ( s , a ) = ( x 1 ( s , a ) x 2 ( s , a ) . . . x n ( s , a ) ) \textbf{x}(s,a)=\begin{pmatrix} x_1(s,a) \\ x_2(s,a) \\ ... \\ x_n(s,a) \end{pmatrix} x(s,a)=⎝⎜⎜⎛x1(s,a)x2(s,a)...xn(s,a)⎠⎟⎟⎞
使用一个加权的特征线性组合来表示状态-动作价值函数 Q ^ ( s , a ; w ) = x ( s , a ) T w = ∑ j = 1 n x j ( s , a ) w j \hat{Q}(s,a;\textbf{w})=\textbf{x}(s,a)^\Tau\textbf{w}=\sum_{j=1}^nx_j(s,a)w_j Q^(s,a;w)=x(s,a)Tw=∑j=1nxj(s,a)wj
随机梯度下降更新: ∇ w J ( w ) = ∇ w E π [ ( Q π ( s , a ) − Q ^ π ( s , a ; w ) 2 ] \nabla_\textbf{w}J(\textbf{w})=\nabla_{\textbf{w}}\mathbb{E}_\pi[(Q^\pi(s,a)-\hat{Q}^\pi(s,a;\textbf{w})^2] ∇wJ(w)=∇wEπ[(Qπ(s,a)−Q^π(s,a;w)2]
综上,我们不会对每个状态使用单独的权重向量,而是使用有能包含状态和动作的特征。可以在此基础之上做SGD。
以下公式本质上是使用做近似价值函数值对之前博文里的公式的价值函做对换得到的。
类似于策略迭代,一个状态的真实状态-动作价值函数是未知的,所以用一个目标值做替代
在蒙特·卡罗尔方法,使用一个回报 G t G_t Gt作为一个替代的目标 Δ w = α ( G t − Q ^ ( s t , a t ; w ) ) ∇ w Q ^ ( s t , a t ; w ) \Delta\textbf{w}=\alpha(G_t-\hat{Q}(s_t,a_t;\textbf{w}))\nabla_{\textbf{w}}\hat{Q}(s_t,a_t;\textbf{w}) Δw=α(Gt−Q^(st,at;w))∇wQ^(st,at;w)
对于SARSA,不使用TD目标 r + γ Q ^ ( s ′ , a ′ ; w ) r+\gamma\hat{Q}(s',a';\textbf{w}) r+γQ^(s′,a′;w),而是利用当前的函数近似价值 Δ w = α ( r + γ Q ^ ( s ′ , a ′ ; w ) − Q ^ ( s , a ; w ) ) ∇ w Q ^ ( s , a ; w ) \Delta\textbf{w}=\alpha(r + \gamma \hat{Q}(s',a'; \textbf{w})-\hat{Q}(s,a;\textbf{w}))\nabla_{\textbf{w}}\hat{Q}(s,a;\textbf{w}) Δw=α(r+γQ^(s′,a′;w)−Q^(s,a;w))∇wQ^(s,a;w)
(TD目标参见之前的博文,这里的形式可能会让你产生疑惑,但博主还是原样誊写下来了,下同)
对于Q-learning,相对于使用一个TD目标 r + γ m a x a ′ Q ^ ( s ′ , a ′ ; w ) r+\gamma max_{a'}\hat{Q}(s',a';\textbf{w}) r+γmaxa′Q^(s′,a′;w),采用了当前函数近似值的max Δ w = α ( r + γ m a x Q ^ ( s ′ , a ′ ; w ) − Q ^ ( s , a ; w ) ) ∇ w Q ^ ( s , a ; w ) \Delta\textbf{w}=\alpha(r + \gamma max \hat{Q}(s',a'; \textbf{w})-\hat{Q}(s,a;\textbf{w}))\nabla_{\textbf{w}}\hat{Q}(s,a;\textbf{w}) Δw=α(r+γmaxQ^(s′,a′;w)−Q^(s,a;w))∇wQ^(s,a;w)使用VFA的TD会有一些不好的地方,为什么?
使用价值函数近似的TD不遵循目标函数的梯度非正式的,更新包括了执行一次遵循最能拟合一个特定特征表示的潜在的价值函数的(近似)Bellman backup。Bellman operators 是收缩,但是价值函是近似是扩张。 以前Bellman Operator是让操作的价值越来越接近于真实值,从而使得它们之间的差距变小,而每一次使用函数近似拟合则会让操作的近似价值偏离近似函数的所在的空间,因此又需要不断映射回近似函数所在的空间。✔表示会收敛,(✔)表示会震荡,×表示会发散。
这张图是说,你的近似函数的Bellman误差可能不在你的价值函数所在的平面,你可以投影来把它映射到其所在的平面。 另外,在实践中,你有其他可选的loss函数,而且loss最小的函数不一定对你所要解决的问题是最好的。