怎么把网站上传到空间,自己做背景的网站,wordpress焦点图插件,天津设计网站强化学习-数学理论
强化学习-基本概念强化学习-贝尔曼公式强化学习-贝尔曼最优公式强化学习-值迭代与策略迭代强化学习-蒙特卡洛方法 文章目录 强化学习-数学理论一、蒙特卡洛方法理论(Monte Carlo, MC)二、MC Basic2.1 算法拆解2.2 MC Basic算法 三、MC Exploring Starts3.1 …强化学习-数学理论
强化学习-基本概念强化学习-贝尔曼公式强化学习-贝尔曼最优公式强化学习-值迭代与策略迭代强化学习-蒙特卡洛方法 文章目录 强化学习-数学理论一、蒙特卡洛方法理论(Monte Carlo, MC)二、MC Basic2.1 算法拆解2.2 MC Basic算法 三、MC Exploring Starts3.1 算法拆解3.1.1 高效利用数据3.1.2 高效更新策略 3.2 MC Exploring Starts算法3.3 为什么必须要有exploring starts这个条件呢 四、MC Epsilon-Greedly4.1 soft policy理论4.2 ε \varepsilon ε-greedy policysoft policy的一种4.3 MC Epsilon-Greedly算法4.3.1 如何将 ε \varepsilon ε-greedy policy引入MC Basic4.3.2 MC Epsilon-Greedly算法伪代码 总结内容小结参考资料 一、蒙特卡洛方法理论(Monte Carlo, MC) 上一篇博客介绍的是model-base的方法本篇博客开始介绍model-free的方法model-free的核心思想是基于数据来估计出一个模型。 如何在没有模型的情况下去进行估计有一个重要的思想Monte Carlo estimation。下面以抛硬币的例子为大家讲解该思想。 假设我们正在进行抛硬币游戏将其结果用 X X X来表示结果是正面时 X 1 X1 X1;结果是反面时 X − 1 X-1 X−1我们的目的是去求解 E [ X ] \mathbb E[X] E[X]有如下两种方法 方法一model-base 假设我们知道有一个概率模型 p ( X 1 ) 0.5 , p ( X − 1 ) 0.5 p(X1)0.5, p(X-1)0.5 p(X1)0.5,p(X−1)0.5那么 E [ X ] Σ x x p ( x ) 1 × 0.5 ( − 1 ) × 0.5 0 \mathbb E[X] \underset{x}\Sigma xp(x)1\times0.5 (-1)\times0.50 E[X]xΣxp(x)1×0.5(−1)×0.50然而事实上我们可能没有办法获取这么精确的概率模型。 方法二model-freeMonte Carlo estimation 投掷硬币很多次做多次试验得到很多采样结果把所有的采样结果求平均。具体如下假如做了N次实验这N次实验的结果是${x_1,x_2,x_3,…,x_N}$把结果相加再除于N得到 x ‾ \overline{\text{x}} x当N足够大时 x ‾ \overline{\text{x}} x 近似等于 E [ X ] \mathbb E[X] E[X]等式为 E [ X ] ≈ x ‾ 1 N Σ N j 1 x j \mathbb E[X]\approx\overline{\text{x}}\frac{1}{N}\underset{j1}{\overset{N}\Sigma}x_j E[X]≈xN1j1ΣNxj。这个思想就是 Monte Carlo estimation。 Monte Carlo estimation思想的数学理论支撑如下图所示相关证明这里不再给出感兴趣的朋友可以查阅相关参考资料。 二、MC Basic
2.1 算法拆解 上一篇博客我们讲过policy iteration这个算法在上一篇中它是模型确定的本篇的核心是如何将policy iteration转变成model-free的方法。 policy iteration算法有如下两部分 { p o l i c y e v a l u a t i o n : v π k r π k γ P π k v π k v a l u e i m p r o v e m e n t : π k 1 a r g m a x π ( r π γ P π v k ) \begin{cases} policy\ evaluation:\ v_{\pi_k}r_{\pi_k} \gamma P_{\pi_k} v_{\pi_k}\\ value\ improvement:\ \pi_{k1}argmax_\pi(r_\pi\gamma P_\pi v_k) \end{cases} {policy evaluation: vπkrπkγPπkvπkvalue improvement: πk1argmaxπ(rπγPπvk) policy improvement的elementwise form如下 π k 1 ( s ) a r g m a x π Σ a π ( a ∣ s ) [ Σ r p ( r ∣ s , a ) r γ Σ s ′ p ( s ′ ∣ s , a ) v k ( s ′ ) ] ⏟ q π k ( s , a ) , s ∈ S \begin{aligned} \pi_{k1}(s)\underset{\pi}{argmax}\underset{a}\Sigma\pi(a|s)\underbrace{[\underset{r}\Sigma p(r|s,a)r\gamma\underset{s}\Sigma p(s|s,a)\textcolor{red}{v_k(s)}]}_{\textcolor{red}{q_{\pi_k}(s,a)}}, \quad s\in S \end{aligned} πk1(s)πargmaxaΣπ(a∣s)qπk(s,a) [rΣp(r∣s,a)rγs′Σp(s′∣s,a)vk(s′)],s∈S 算法的关键在于如何计算 q π k ( s , a ) \textcolor{red}{q_{\pi_k}(s,a)} qπk(s,a)! 同样求解 q k ( s , a ) \textcolor{red}{q_k(s,a)} qk(s,a)有如下两种方式 方案一model-base q π k ( s , a ) Σ r p ( r ∣ s , a ) r γ p s ′ ( s ′ ∣ s , a ) v π k ( s ′ ) q_{\pi_k}(s,a) \underset{r}\Sigma p(r|s,a)r\gamma\underset{s}p(s|s,a)v_{\pi_k}(s) qπk(s,a)rΣp(r∣s,a)rγs′p(s′∣s,a)vπk(s′) 方案二model-free【本篇博客的方法】 q π k ( s , a ) E [ G t ∣ S t a , A t a ] q_{\pi_k}(s,a) \mathbb E[G_t|S_ta,A_ta] qπk(s,a)E[Gt∣Sta,Ata] 如何基于数据去求解 q k ( s , a ) \textcolor{red}{q_k(s,a)} qk(s,a)答案采用章节一中提到的 Monte Carlo estimation具体步骤如下所示 首先我们从任意的一个s和a的一个组合出发然后根据当前的策略得到一个episode并计算出该episode对应的discounted return 为 g ( s , a ) g(s,a) g(s,a)这里的 g ( s , a ) g(s,a) g(s,a)是 G t G_t Gt的一个采样。假设我们有很多这样的词啊样集合 { g ( j ) ( s , a ) } \{g^{(j)}(s,a)\} {g(j)(s,a)}那么根据Monte Carlo estimation思想我们可以得到 q k ( s , a ) E [ G t ∣ S t a , A t a ] ≈ 1 N Σ N i 1 g i ( s , a ) q_k(s,a) \mathbb E[G_t|S_ta,A_ta] \approx\frac{1}{N}\underset{i1}{\overset{N}\Sigma}g^{i}(s,a) qk(s,a)E[Gt∣Sta,Ata]≈N1i1ΣNgi(s,a) 总之没有数据时得有模型没有模型时得有数据 2.2 MC Basic算法 给定一个初始策略 π 0 \pi_0 π0这个策略可能是不好的慢慢地对其进行改进然后在第k个iteration它包含两个步骤 1️⃣ policy evaluation计算出所有 ( s , a ) (s,a) (s,a)对应的 q π k q_{\pi_k} qπk其计算方法是从 ( s , a ) (s,a) (s,a)出发得到很多的episode求得episode的return并求平均 2️⃣ policy improvement在步骤一中我们得到了 q π k q_{\pi_k} qπk这个步骤主要求解一个最优化问题得到一个新的策略。 伪代码如下图所示 三、MC Exploring Starts
3.1 算法拆解 该算法是MC Basic算法的一个推广使得MC Basic算法更加高效下面通过一个例子为大家讲解。
3.1.1 高效利用数据 在一个网格世界里假如有一个策略 π \pi π我们可以得到一个episode如下所示 s 1 → a 2 s 2 → a 4 s 1 → a 2 s 2 → a 3 s 5 → a 1 . . . s_1\overset{a_2}\rightarrow s_2\overset{a_4}\rightarrow s_1\overset{a_2}\rightarrow s_2\overset{a_3}\rightarrow s_5\overset{a_1}\rightarrow ... s1→a2s2→a4s1→a2s2→a3s5→a1... 这里引入一个新的概念visit每出现一次state-action pair我们就认为有了一次访问。前面所讲到的MC Basic算法也叫Initial-visit method即对于某个episode我们只考虑 ( s 1 , a 2 ) (s_1,a_2) (s1,a2)然后利用该episode剩下所得到的return来估计 ( s 1 , a 2 ) (s_1,a_2) (s1,a2)的action value。因此我们可以清楚的知道MC Basic算法的问题在于它没有充分利用这个episode因为里面有很多的数据被浪费掉了。 如下图所示我们可以利用episode所得的return去估计前一个 q π ( s 2 , a 4 ) q_\pi(s_2,a_4) qπ(s2,a4)如此依赖就可以充分利用该episode中的数据。这里也有两种方法 first-visit method如下图所示在第三次的时候又出现了一次 ( s 1 , a 2 ) (s_1,a_2) (s1,a2)该方法的意思是只要出现过一次的state-action pair 后面再次出现就不在进行估计了。every-visit method与上面的方案截然相反出现第二次时就用第二次后面的进行估计出现第三次时就用第三次后面的值进行估计如此类推。 3.1.2 高效更新策略 上面所提到的方案是如何让数据利用更加高效下面将为大家讲解如何让策略更新的更高效这里也有两种方案。 第一种【原始法】MC Basic算法在进行策略更新的时候其原理是收集从 state-action pair 开始的所有episode然后使用return的平均值来近似action value。原始方案的缺点在于“要等”要等所有的episode这就造成了性能的低效。 第二种【改进法】针对上述方案的缺点该方法的核心是我得了一个episode时就用这个episode的return立刻去估计action value然后就直接开始改进策略后面都采用这样及时的方法从而提高性能。该方案的支撑理论见truncated policy iteration 3.2 MC Exploring Starts算法 MC Exploring Starts方法的伪代码如下
3.3 为什么必须要有exploring starts这个条件呢
exploring代表指的是从每一个 ( s , a ) (s,a) (s,a)出发都要有episode只有这样才能用后面生成的这些return去计算 q π ( s , a ) q_\pi(s,a) qπ(s,a)假设有一个state action没有被访问到就无法确保所选的action是最优的了。 starts代表要访问每一个 ( s , a ) (s,a) (s,a)从它后面能够生成reward的这些数据有两种方案1 从 ( s , a ) (s,a) (s,a)开始一个episode就是start2visit方法即我从其他状态出发得到的episode经过了 ( s , a ) (s,a) (s,a)这个状态但目前来说visit这个方法无法确保一定能够经过剩下的这些 ( s , a ) (s,a) (s,a)。 理论上只有对每个状态的每个 action value 都进行了很好的探索我们才能正确地选择最优 action。否则如果未探索某个操作则此操作可能恰好是最佳操作因此会错过。在实践中exploring starts很难实现。对于许多应用程序尤其是那些涉及与环境物理交互的应用程序很难从每个state-action pair 对开始收集episode。 四、MC Epsilon-Greedly MC Epsilon-Greedly算法通过soft policy的方式对MC Exploring Starts算法进行改进从而拿掉MC Exploring Starts算法中的硬性条件exploring starts。
4.1 soft policy理论 前几章提到的greedy policy是deterministic的而soft policy是stochastic的。如果我从一个state-action pair如 ( s , a ) (s,a) (s,a)出发假设后面的episode特别特别长因为它是探索性的因此就能够确保任何一个s和a被这个episode访问到。基于这个理论我们就可以去掉exploring starts这个条件了。
4.2 ε \varepsilon ε-greedy policysoft policy的一种 π ( a ∣ s ) { 1 − ε ∣ A ( s ) ∣ ( ∣ A ( s ) ∣ − 1 ) , f o r t h e g r e e d y a c t i o n ε ∣ A ( s ) ∣ , f o r t h e o t h e r ∣ A ( s ) ∣ − 1 a c t i o n \pi(a|s) \begin{cases}1-\frac{\varepsilon}{|\mathcal A(s)|}(|\mathcal A(s)|-1), for\,the\,greedy\,action \\ \frac{\varepsilon}{|\mathcal A(s)|}, for\,the\,other\,|\mathcal A(s)|-1\,action \end{cases} π(a∣s){1−∣A(s)∣ε(∣A(s)∣−1),∣A(s)∣ε,forthegreedyactionfortheother∣A(s)∣−1action 其中 ε ∈ [ 0 , 1 ] \varepsilon \in [0,1] ε∈[0,1] ∣ A ( s ) ∣ |\mathcal A(s)| ∣A(s)∣为状态 s 的动作数量。 ε \varepsilon ε-greedy policy可以平衡 exploitation 和 exploration。从上式也可得出当 ε 0 \varepsilon 0 ε0时, policy 就是 greedy的充分利用性强探索性弱; 当 ε 1 \varepsilon 1 ε1时, 此时策略就是随机的且其探索性就很强。 4.3 MC Epsilon-Greedly算法
4.3.1 如何将 ε \varepsilon ε-greedy policy引入MC Basic 先前MC Basic和MC Exploring Starts算法在解决policy improvement时计算公式如下 π k 1 ( s ) a r g m a x π ∈ Π Σ a π ( a ∣ s ) q π k ( s , a ) \pi_{k1}(s)\underset{\pi \in \Pi}{argmax}\underset{a}\Sigma\pi(a|s)q_{\pi_k}(s,a) πk1(s)π∈ΠargmaxaΣπ(a∣s)qπk(s,a) 这里的 Π \Pi Π代表了所有可能的policy。最大策略计算方式如下 π ( a ∣ s ) { 1 a a k ∗ 0 , a ≠ a k ∗ \pi(a|s) \begin{cases}1aa_k^*\\ 0, a \neq a_k^* \end{cases} π(a∣s){10,aak∗aak∗ 这里 a k ∗ a r g m a x a q π k ( s , a ) a_k^*argmax_a q_{\pi_k}(s,a) ak∗argmaxaqπk(s,a). 现在只需要把原来的 π ∈ Π \pi \in \Pi π∈Π用 ε \varepsilon ε-greedy policy替代即可即 π ∈ Π ε \pi \in \Pi_\varepsilon π∈Πε具体公式如下所示 π k 1 ( s ) a r g m a x π ∈ Π ε Σ a π ( a ∣ s ) q π k ( s , a ) \pi_{k1}(s)\underset{\pi \in \Pi_\varepsilon}{argmax}\underset{a}\Sigma\pi(a|s)q_{\pi_k}(s,a) πk1(s)π∈ΠεargmaxaΣπ(a∣s)qπk(s,a) 这里的 Π \Pi Π只包含一部分的策略最大策略计算如下 π ( a ∣ s ) { 1 − ∣ A ( s ) ∣ − 1 ∣ A ( s ) ∣ ε , a a k ∗ 1 ∣ A ( s ) ∣ ε , a ≠ a k ∗ \pi(a|s) \begin{cases}1-\frac{|\mathcal A(s)|-1}{|\mathcal A(s)|}\varepsilon, aa_k^* \\ \frac{1}{|\mathcal A(s)|}\varepsilon, a\neq a_k^* \end{cases} π(a∣s){1−∣A(s)∣∣A(s)∣−1ε,∣A(s)∣1ε,aak∗aak∗ 4.3.2 MC Epsilon-Greedly算法伪代码 总结
内容小结 Monte Carlo estimation将大量的数据采样求平均进行估计MC Basic基于Monte Carlo estimation思想将policy iteration算法从model-base的方法转为model-free的方法MC Exploring Starts是对MC Basic算法的优化从数据和策略两个方面进行优化MC Epsilon-Greedly通过soft policy的方式对MC Exploring Starts算法进行改进拿掉了硬性条件exploring starts。 参考资料
蒙特卡洛方法视频版
