liferay做网站好吗,前端静态页面接单,网站描述范例,wordpress文章发布时间强化学习笔记 主要基于b站西湖大学赵世钰老师的【强化学习的数学原理】课程#xff0c;个人觉得赵老师的课件深入浅出#xff0c;很适合入门.
第一章 强化学习基本概念 第二章 贝尔曼方程 第三章 贝尔曼最优方程 第四章 值迭代和策略迭代 第五章 强化学习实例分析:GridWorld…强化学习笔记 主要基于b站西湖大学赵世钰老师的【强化学习的数学原理】课程个人觉得赵老师的课件深入浅出很适合入门.
第一章 强化学习基本概念 第二章 贝尔曼方程 第三章 贝尔曼最优方程 第四章 值迭代和策略迭代 第五章 强化学习实例分析:GridWorld 第六章 蒙特卡洛方法 第七章 Robbins-Monro算法 第八章 多臂老虎机 第九章 强化学习实例分析:CartPole 文章目录 强化学习笔记一、on-policy vs off-policy二、TD learning of state values1 迭代格式2 推导3 分析4 TD(0)与蒙特卡洛方法的对比 三、Sarsa四、Expected Sarsa五、Q-learning六、参考资料 在强化学习实例分析:CartPole中我们通过实验发现了蒙特卡洛方法的一些缺点
每次更新需要等到一个episode结束越到后面的episode耗时越长效率低.
本节介绍强化学习中经典的时序差分方法Temporal Difference MethodsTD。与蒙特卡洛(MC)学习类似TD学习也是Model-free的但由于其增量形式在效率上相较于MC方法具有一定的优势。
一、on-policy vs off-policy
在介绍时序差分算法之前首先介绍一下on-policy 和 off-policy的概念
On-policy我们把用于产生采样样本的策略称为behavior-policy在policy-improvement步骤进行改进的策略称为target-policy.如果这两个策略相同我们称之为On-policy算法。Off-policy如果behavior-policy和target-policy不同我们称之为Off-policy算法。
比如在Monte-Carlo算法中我可以用一个给定策略 π a \pi_a πa来产生样本这个策略可以是 ϵ \epsilon ϵ-greedy策略以保证能够访问所有的 s s s和 a a a。而我们目标策略可以是greedy策略 π b \pi_b πb在policy-imporvement阶段我们不断改进 π b \pi_b πb最终得到一个最优的策略。这样我们最后得到的最优策略 π b ∗ \pi_b^* πb∗就是一个贪婪策略不用去探索不是最优的动作这样我们用 π b ∗ \pi_b^* πb∗可以得到更高的回报。
二、TD learning of state values
1 迭代格式
和蒙特卡洛方法一样用TD learning来估计状态值 v ( s ) v(s) v(s)我们也需要采样的数据假设给定策略 π \pi π某个episode采样得到的序列如下 ( s 0 , r 1 , s 1 , . . . , s t , r t 1 , s t 1 , . . . ) (s_0, r_1, s_1, . . . , s_t , r_{t1}, s_{t1}, . . .) (s0,r1,s1,...,st,rt1,st1,...) 那么TD learning给出在第 t t t步状态值 v ( s ) v(s) v(s)的更新如下 v ( s t ) v ( s t ) α t ( s t ) [ r t 1 γ v ( s t 1 ) − v ( s t ) ] ( 1 ) v(s_t)v(s_t)\alpha_t(s_t)[r_{t1}\gamma v(s_{t1})-v(s_t)]\qquad(1) v(st)v(st)αt(st)[rt1γv(st1)−v(st)](1) Note: s t s_t st是当前状态 s t 1 s_{t1} st1是跳转到的下一个状态这里需要用到 v ( s t 1 ) v(s_{t1}) v(st1)(本身也是一个估计值)我们可以看到TD方法在每个时间步都会进行更新不需要得到整个episode结束才更新;这个算法被称为TD(0)。
当 a t ( s t ) a_t(s_t) at(st)取常量 α \alpha α时下面给出 v π ( s ) v_{\pi}(s) vπ(s)估计的伪代码 2 推导
TD(0)的迭代格式为什么是这样的呢和前面介绍随机近似中的RM算法似乎有点像事实上它可以看作是求解Bellman方程的一种特殊的随机近似算法。我们回顾贝尔曼方程中介绍的 v π ( s ) E [ G t ∣ S t s ] E [ R t γ G t 1 ∣ S t s ] E [ R t γ v π ( S t 1 ) ∣ S t s ] ( 2 ) \begin{aligned} v_{\pi}(s)\mathbb{E}[G_t|S_ts]\\ \mathbb{E}[R_t\gamma G_{t1}|S_ts]\\ \mathbb{E}[R_t\gamma v_{\pi}(S_{t1})|S_ts]\\ \end{aligned} \qquad(2) vπ(s)E[Gt∣Sts]E[RtγGt1∣Sts]E[Rtγvπ(St1)∣Sts](2) 下面我们用Robbins-Monro算法来求解方程2,对于状态$s_t, $我们定义一个函数为 g ( v π ( s t ) ) ≐ v π ( s t ) − E [ R t 1 γ v π ( S t 1 ) ∣ S t s t ] . g(v_\pi(s_t))\doteq v_\pi(s_t)-\mathbb{E}\big[R_{t1}\gamma v_\pi(S_{t1})|S_ts_t\big]. g(vπ(st))≐vπ(st)−E[Rt1γvπ(St1)∣Stst]. 那么方程2等价于 g ( v π ( s t ) ) 0. g(v_\pi(s_t))0. g(vπ(st))0. 显然我们可以用RM算法来求解上述方程的根就能得到 v π ( s t ) v_{\pi}(s_t) vπ(st)。因为我们可以通过采样获得 r t 1 r_{t1} rt1和 s t 1 s_{t1} st1它们是 R t 1 R_{t1} Rt1和 S t 1 S_{t 1} St1的样本我们可以获得的$g( v_\pi ( s_{t}) ) $的噪声观测是 g ~ ( v π ( s t ) ) v π ( s t ) − [ r t 1 γ v π ( s t 1 ) ] ( v π ( s t ) − E [ R t 1 γ v π ( S t 1 ) ∣ S t s t ] ) ⏟ g ( v π ( s t ) ) ( E [ R t 1 γ v π ( S t 1 ) ∣ S t s t ] − [ r t 1 γ v π ( s t 1 ) ] ) ⏟ η . \begin{aligned}\tilde{g}(v_{\pi}(s_{t}))v_\pi(s_t)-\begin{bmatrix}r_{t1}\gamma v_\pi(s_{t1})\end{bmatrix}\\\underbrace{\left(v_\pi(s_t)-\mathbb{E}\big[R_{t1}\gamma v_\pi(S_{t1})|S_ts_t\big]\right)}_{g(v_\pi(s_t))}\\\underbrace{\left(\mathbb{E}\big[R_{t1}\gamma v_\pi(S_{t1})|S_ts_t\big]-\big[r_{t1}\gamma v_\pi(s_{t1})\big]\right)}_{\eta}.\end{aligned} g~(vπ(st))vπ(st)−[rt1γvπ(st1)]g(vπ(st)) (vπ(st)−E[Rt1γvπ(St1)∣Stst])η (E[Rt1γvπ(St1)∣Stst]−[rt1γvπ(st1)]). 因此求解 g ( v π ( s t ) ) 0 g(v_{\pi}(s_{t}))0 g(vπ(st))0的RM算法为 v t 1 ( s t ) v t ( s t ) − α t ( s t ) g ~ ( v t ( s t ) ) v t ( s t ) − α t ( s t ) ( v t ( s t ) − [ r t 1 γ v π ( s t 1 ) ] ) , ( 3 ) \begin{aligned}v_{t1}(s_{t})v_t(s_t)-\alpha_t(s_t)\tilde{g}(v_t(s_t))\\v_t(s_t)-\alpha_t(s_t)\Big(v_t(s_t)-\big[r_{t1}\gamma v_\pi(s_{t1})\big]\Big),\end{aligned}\qquad(3) vt1(st)vt(st)−αt(st)g~(vt(st))vt(st)−αt(st)(vt(st)−[rt1γvπ(st1)]),(3) 其中 v t ( s t ) v_t(s_t) vt(st)是 v π ( s t ) v_\pi(s_t) vπ(st)在$t, 时间点的估计 时间点的估计 时间点的估计\alpha _t( s_t) $是学习率。
Note:
(3)中的算法与(1)中的TD(0)具有相似的表达式唯一的区别是(3)的右侧包含 v π ( s t 1 ) v_{\pi}(s_{t1}) vπ(st1)而(1)包含 v t ( s t 1 ) v_t(s_{t1}) vt(st1)这是因为(3)的设计是通过假设其他状态值已知来估计 s t s_t st的动作值。如果我们想估计所有状态的状态值则右侧的 v π ( s t 1 ) v_{\pi}(s_{t1}) vπ(st1)应替换为 v t ( s t 1 ) v_t(s_{t1}) vt(st1)那么(3)与(1)完全相同。并且我们可以证明这样的替换能保证所有 v t ( s ) v_t(s) vt(s)都收敛到 v π ( s ) v_{\pi}(s) vπ(s)这里就不再展开。
3 分析
我们再来看一下TD(0)的迭代格式 v t 1 ( s t ) ⏟ new estimate v t ( s t ) ⏟ current estimate − α t ( s t ) [ v t ( s t ) − ( r t 1 γ v t ( s t 1 ) ⏟ TD target v ˉ t ) ⏞ TD error δ t ] , ( 4 ) \underbrace{v_{t1}(s_t)}_{\text{new estimate}}\underbrace{v_t(s_t)}_{\text{current estimate}}-\alpha_t(s_t)\Big[\overbrace{v_t(s_t)-\Big(\underbrace{r_{t1}\gamma v_t(s_{t1})}_{\text{TD target }\bar{v}_t}\Big)}^{\text{TD error }\delta_t}\Big],\qquad (4) new estimate vt1(st)current estimate vt(st)−αt(st)[vt(st)−(TD target vˉt rt1γvt(st1)) TD error δt],(4) 其中 v ˉ t ≐ r t 1 γ v t ( s t 1 ) ( 5 ) \bar{v}_t\doteq r_{t1}\gamma v_t(s_{t1})\qquad(5) vˉt≐rt1γvt(st1)(5) 被称为TD target δ t ≐ v ( s t ) − v ˉ t v t ( s t ) − ( r t 1 γ v t ( s t 1 ) ) ( 6 ) \delta_t\doteq v(s_t)-\bar{v}_tv_t(s_t)-(r_{t1}\gamma v_t(s_{t1}))\qquad(6) δt≐v(st)−vˉtvt(st)−(rt1γvt(st1))(6) 被称为TD-error.
为什么5被称为TD target因为迭代格式4是让 v t 1 v_{t1} vt1朝着 v ˉ t \bar{v}_t vˉt更新的我们考察 ∣ v t 1 ( s t ) − v ˉ t ∣ ∣ [ v t ( s t ) − v ˉ t ] − α t ( s t ) [ v t ( s t ) − v ˉ t ] ∣ ∣ [ 1 − α t ( s t ) ] ∣ ∣ [ v t ( s t ) − v ˉ t ] ∣ ≤ ∣ [ v t ( s t ) − v ˉ t ] ∣ \begin{aligned} |v_{t1}(s_t)-\bar{v}_t||\begin{bmatrix}v_t(s_t)-\bar{v}_t\end{bmatrix}-\alpha_t(s_t)\big[v_t(s_t)-\bar{v}_t\big]|\\ |[1-\alpha_t(s_t)]||\big[v_t(s_t)-\bar{v}_t\big]|\\ \leq|\big[v_t(s_t)-\bar{v}_t\big]| \end{aligned} ∣vt1(st)−vˉt∣∣[vt(st)−vˉt]−αt(st)[vt(st)−vˉt]∣∣[1−αt(st)]∣∣[vt(st)−vˉt]∣≤∣[vt(st)−vˉt]∣ 显然当 0 α t ( s t ) 2 0\alpha_t(s_t)2 0αt(st)2时上式的不等式成立这意味着 v t 1 v_{t1} vt1比 v t v_t vt离 v ˉ t \bar{v}_t vˉt更近所以 v ˉ t \bar{v}_t vˉt被称为TD target。
TD-error则衡量了在 t t t时间步估计值 v t v_t vt与 v ˉ t \bar{v}_t vˉt 的差异显然我们可以想象当 v t v_t vt估计值是准确的 v π v_{\pi} vπ时TD-error的期望值应该为0事实上确实如此 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 ] v π ( s t ) − v π ( s t ) 0. \begin{aligned} \mathbb{E}[\delta_t|S_ts_t] \mathbb{E}\big[v_\pi(S_t)-(R_{t1}\gamma v_\pi(S_{t1}))|S_ts_t\big] \\ v_\pi(s_t)-\mathbb{E}\big[R_{t1}\gamma v_\pi(S_{t1})|S_ts_t\big] \\ v_\pi(s_t)-v_\pi(s_t)\\ 0. \end{aligned} E[δt∣Stst]E[vπ(St)−(Rt1γvπ(St1))∣Stst]vπ(st)−E[Rt1γvπ(St1)∣Stst]vπ(st)−vπ(st)0. 当TD-error趋于0时 那么(1)也得到不到什么新的信息了迭代也就收敛了。
4 TD(0)与蒙特卡洛方法的对比
TD learningMonte Carlo MethodsTD learning每得到一个样本就能更新 v ( s ) v(s) v(s)或者 q ( s , a ) q(s,a) q(s,a)这种算法被称为online的.MC每次更新必须等到一个epsisode结束这种算法被称为offline的.TD可以处理连续性任务和episodic任务.MC只能处理episodic任务.TD被称为bootstraping方法因为 v ( s ) v(s) v(s)/ q ( s , a ) q(s,a) q(s,a)动作的更新依赖于其他状态值先前的估计值.因此TD需要给定一个初始值.MC是Non-Bootstraping的.
三、Sarsa
如果我们要得到最优策略无论是用策略迭代还是值迭代算法我们都需要 q ( s , a ) q(s,a) q(s,a)所以我们可以用TD learning直接来估计 q ( s , a ) q(s,a) q(s,a)给定策略 π \pi π假设某个episode采样得到如下序列 ( s 0 , a 0 , r 1 , s 1 , a 1 , . . . , s t , a t , r t 1 , s t 1 , a t 1 , . . . ) . (s_0, a_0, r_1, s_1, a_1, . . . , s_t , a_t , r_{t1}, s_{t1}, a_{t1}, . . .). (s0,a0,r1,s1,a1,...,st,at,rt1,st1,at1,...). 那么TD learning对 q ( s , a ) q(s,a) q(s,a)的估计如下 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 ) ) ] , ( 7 ) q_{t1}(s_t,a_t)q_t(s_t,a_t)-\alpha_t(s_t,a_t)\Big[q_t(s_t,a_t)-(r_{t1}\gamma q_t(s_{t1},a_{t1}))\Big],\qquad(7) qt1(st,at)qt(st,at)−αt(st,at)[qt(st,at)−(rt1γqt(st1,at1))],(7) Note:
和对状态值的估计1对比我们发现7就是把1中的 v ( s ) v(s) v(s)替换为 q ( s , a ) q(s,a) q(s,a)其实就是用RM算法求解关于 q ( s , a ) q(s,a) q(s,a)的贝尔曼方程所以得到的迭代格式类似.其中 s t 1 s_{t1} st1为转移的下一个状态 a t 1 a_{t1} at1是在状态 s t 1 s_{t1} st1下采取的动作这里是根据策略 π \pi π得到.因为我们采样的序列就是根据 π \pi π得到的所以如果 s t 1 s_{t1} st1是终止状态显然就没有 a t 1 a_{t1} at1此时我们定义 q ( s t 1 , a t 1 ) 0 q(s_{t1},a_{t1})0 q(st1,at1)0.这个算法每次更新会用到 ( s t , a t , r t 1 , s t 1 , a t 1 ) (s_t, a_t, r_{t1}, s_{t1}, a_{t1}) (st,at,rt1,st1,at1)(SARSA)所以这个算法被称为SARSA.当我们有 q ( s , a ) q(s,a) q(s,a)的估计值后我们可以使用greedy或者 ε \varepsilon ε-greedy来更新策略。可以证明如果步长 a t ( s t , a t ) a_t(s_t,a_t) at(st,at)满足RM算法收敛的条件要求只要所有的状态-动作对被访问无限次Sarsa以概率1收敛到最优的策略 π ∗ \pi^* π∗和最优的动作-价值函数 q ∗ ( s , a ) q^*(s,a) q∗(s,a).
同TD(0)类似Sarsa可以看作是用RM算法求解如下贝尔曼方程得到的迭代格式 q π ( s , a ) E [ R γ q π ( S ′ , A ′ ) ∣ s , a ] , for all ( s , a ) . q_\pi(s,a)\mathbb{E}\left[R\gamma q_\pi(S,A)|s,a\right],\quad\text{for all }(s,a). qπ(s,a)E[Rγqπ(S′,A′)∣s,a],for all (s,a).
下面给出Sarsa完整的伪代码 Sarsa是一种on-policy算法因为在估计 q t q_t qt值时会用到依据 π t \pi_t πt产生的样本更新 q t q_t qt后我们又会依据新的 q t q_t qt来更新策略得到 π t 1 \pi_{t1} πt1然后用 π t 1 \pi_{t1} πt1产生样本继续更新 q t 1 q_{t1} qt1这样交替进行最后得到最优策略。在这个过程中我们发现产生样本的策略和得到的最优策略是同一个策略所以是on-policy算法。
四、Expected Sarsa
给定策略 π \pi π其动作值可以用Sarsa的一种变体Expected-Sarsa来估计。Expected-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 ( s t , a t ) − α t ( s t , a t ) [ q t ( s t , a t ) − ( r t 1 γ ∑ a π ( a ∣ s t 1 ) q t ( s t 1 ) , a ) ] \begin{aligned} q_{t1}(s_t,a_t)q_t(s_t,a_t)-\alpha_t(s_t,a_t)\Big[q_t(s_t,a_t)-(r_{t1}\gamma\mathbb{E}[q_t(s_{t1},A)])\Big]\\ q_t(s_t,a_t)-\alpha_t(s_t,a_t)\Big[q_t(s_t,a_t)-(r_{t1}\gamma\sum_a\pi(a|s_{t1})q_t(s_{t1}),a)\Big] \end{aligned} qt1(st,at)qt(st,at)−αt(st,at)[qt(st,at)−(rt1γE[qt(st1,A)])]qt(st,at)−αt(st,at)[qt(st,at)−(rt1γa∑π(a∣st1)qt(st1),a)] 同Sarsa类似Expected-Sarsa可以看作是用RM算法求解如下贝尔曼方程得到的迭代格式 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{aligned} q_\pi(s,a)\mathbb{E}\Big[R_{t1}\gamma\mathbb{E}[q_\pi(S_{t1},A_{t1})|S_{t1}]\Big|S_ts,A_ta\Big]\\ \mathbb{E}\Big[R_{t1}\gamma v_\pi(S_{t1})|S_ts,A_ta\Big]. \end{aligned} qπ(s,a)E[Rt1γE[qπ(St1,At1)∣St1] Sts,Ata]E[Rt1γvπ(St1)∣Sts,Ata]. 虽然Expected Sarsa的计算复杂度比Sarsa高但它消除了随机选择 a t 1 a_{t1} at1所带来的方差。在相同的采样样本条件下Expected Sarsa的表现通常比Sarsa更好。
五、Q-learning
接下来我们介绍强化学习中经典的Q-learning算法Sarsa算法和Expected-Sarsa都是估计 q ( s , a ) q(s,a) q(s,a)如果我们想要得到最优策略还需要policy-improvement而Q-learning算法则是直接估计 q ∗ ( s , a ) q^*(s,a) q∗(s,a)如果我们能得到 q ∗ ( s , a ) q^*(s,a) q∗(s,a)就不用每一步还执行policy-improvement了。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 ∈ A ( s t 1 ) q t ( s t 1 , a ) ) ] , ( 7.18 ) q_{t1}(s_t,a_t)q_t(s_t,a_t)-\alpha_t(s_t,a_t)\left[q_t(s_t,a_t)-\left(r_{t1}\gamma\max_{a\in\mathcal{A}(s_{t1})}q_t(s_{t1},a)\right)\right],\quad(7.18) qt1(st,at)qt(st,at)−αt(st,at)[qt(st,at)−(rt1γa∈A(st1)maxqt(st1,a))],(7.18) Q-learning也是一种随机近似算法用于求解以下方程: q ( s , a ) E [ R t 1 γ max a q ( S t 1 , a ) ∣ S t s , A t a ] . q(s,a)\mathbb{E}\left[R_{t1}\gamma\max_aq(S_{t1},a)\Big|S_ts,A_ta\right]. q(s,a)E[Rt1γamaxq(St1,a) Sts,Ata]. 这是 q ( s , a ) q(s,a) q(s,a)贝尔曼最优方程所以Q-learning本质就是求解贝尔曼最优方程的随机近似算法其伪代码如下 显然Q-learning是一种Off-policy算法因为 q t ( s , a ) q_t(s,a) qt(s,a)在更新的时候用的数据可以是一个给定 ϵ \epsilon ϵ-greedy策略 π a \pi_a πa产生的但是直接学习到 q ∗ ( s , a ) q^*(s,a) q∗(s,a)我们可以通过 q ∗ ( s , a ) q^*(s,a) q∗(s,a)得到一个greedy策略 π b ∗ \pi_b^* πb∗.
即使Q-learning是off-policy的但我们也可以按on-policy的方式来实现下面给出这两种实现我们可以更清楚地看到off-policy和on-policy的区别 六、参考资料
Zhao, S… Mathematical Foundations of Reinforcement Learning. Springer Nature Press and Tsinghua University Press.Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
