电脑做系统ppt下载网站好,wordpress吐槽源码,开发个网站开票名称是什么意思,苏州婚庆公司网站建设案例文章目录 1. 什么是马尔科夫过程2. 强化学习与MDP的关系3. 价值函数的贝尔曼方程3.1 状态价值函数的贝尔曼方程3.2 动作价值函数的贝尔曼方程3.3 价值函数递推关系的转换 4. 最优价值函数5. MDP计算最优值函数实例 1. 什么是马尔科夫过程
马尔科夫过程#xff08;Markov Deci… 文章目录 1. 什么是马尔科夫过程2. 强化学习与MDP的关系3. 价值函数的贝尔曼方程3.1 状态价值函数的贝尔曼方程3.2 动作价值函数的贝尔曼方程3.3 价值函数递推关系的转换 4. 最优价值函数5. MDP计算最优值函数实例 1. 什么是马尔科夫过程
马尔科夫过程Markov Decision Process, MDP也称为马尔科夫链Markov Chain是指具有马尔科夫性质的过程而马尔科夫性质指的是该过程中的未来状态仅依赖于当前的状态和行动与过去的状态序列无关。具体来说马尔科夫过程满足以下两个性质
无记忆性Markov Property给定当前时刻的状态未来时刻的状态只依赖于当前时刻的状态而与过去的状态序列无关。这意味着过程中的状态转移概率只与当前状态有关与之前的历史状态无关。状态空间可数马尔科夫过程的状态空间是可数的即状态集合中的状态数量是有限或可列无穷的。
马尔科夫过程在许多领域都有应用例如在统计学、信号处理、自然语言处理、金融等领域中都有广泛的应用。
2. 强化学习与MDP的关系
在强化学习中马尔科夫决策过程是用于建立智能体与环境之间交互过程的重要数学框架具体而言强化学习解决的问题就是在一个MDP中找到一个最优的策略使得智能体在这个策略下获得的累积奖励最大化。
可以将强化学习过程定义为马尔科夫过程的标准数学形式用一个五元组 ( S , A , R , P , π ) (S,A,R,P,\pi) (S,A,R,P,π) 表示其中 S S S 是状态空间集合包含了所有可能的有效状态 A A A 是动作空间集合 R R R 是奖励函数阶段 t t t 采取动作的奖励 r t R ( s t , a t , s t 1 ) r_t R(s_t, a_t, s_{t1}) rtR(st,at,st1) P P P 状态转移概率矩阵其中 P ( s ′ ∣ s , a ) P(s|s,a) P(s′∣s,a) 是在状态 s s s 下 采取动作 a a a 转移到状态 s ′ s s′ 的概率 π \pi π 是智能体在每个状态下采取动作的策略。
其中对应用强化学习的系统的如下元素做马尔科夫假设
环境的状态转移即未来的环境状态只与当前的环境状态和当前智能体所采取的动作有关与过去的状态序列无关智能体的策略即智能体在状态 s s s 处所采取的动作 a a a 的概率仅与当前状态有关与其他要素无关即如下的策略函数 π ( a ∣ s ) P ( A t a ∣ S t s ) \pi(a|s)P(A_ta|S_ts) π(a∣s)P(Ata∣Sts)状态价值函数即对一个状态的价值估计只基于当前的状态而不考虑过去的状态情况仅评估当前状态下基于已有策略 π \pi π 还能获得的累积奖励具体公式如下 v π ( s ) E π ( G t ∣ S t s ) E π ( R t γ R t 1 γ 2 R t 2 … ∣ S t s ) v_\pi(s)\mathrm{E}_\pi\left(G_t \mid S_ts\right)\mathrm{E}_\pi\left(R_{t}\gamma R_{t1}\gamma^2 R_{t2}\ldots \mid S_ts\right) vπ(s)Eπ(Gt∣Sts)Eπ(RtγRt1γ2Rt2…∣Sts)动作价值函数同理评估一个状态 s s s 下采取动作 a a a 的价值只依赖于当前的状态和动作与过去的状态和动作无关。 以上部分概念可以通过前文《强化学习基础概念入门》了解。 3. 价值函数的贝尔曼方程
在提到马尔科夫决策过程时经常也会提到贝尔曼方程Bellman Equation1这是描述马尔科夫决策过程中最优值函数的重要方程。前面提到不论是状态价值函数还是动作价值函数都是只与当前状态有关估计的累积价值包括当前阶段的价值和未来阶段的价值而贝尔曼方程的核心思想就是将基于当前状态的价值估计和基于下一个状态的价值估计联系起来形成一个递归方程作为求解最优价值函数或者动作价值函数的基础。
3.1 状态价值函数的贝尔曼方程
根据上面提到的状态价值函数的表达式进行如下推导 v π ( s ) E π ( R t γ R t 1 γ 2 R t 2 … ∣ S t s ) E π ( R t γ ( R t 1 γ R t 2 … ) ∣ S t s ) E π ( R t γ G t 1 ∣ S t s ) E π ( R t γ v π ( S t 1 ) ∣ S t s ) \begin{aligned} v_\pi(s) \mathrm{E}_\pi\left(R_{t}\gamma R_{t1}\gamma^2 R_{t2}\ldots \mid S_ts\right) \\ \mathrm{E}_\pi\left(R_{t}\gamma\left(R_{t1}\gamma R_{t2}\ldots\right) \mid S_ts\right) \\ \mathrm{E}_\pi\left(R_{t}\gamma G_{t1} \mid S_ts\right) \\ \mathrm{E}_\pi\left(R_{t}\gamma v_\pi\left(S_{t1}\right) \mid S_ts\right)\end{aligned} vπ(s)Eπ(RtγRt1γ2Rt2…∣Sts)Eπ(Rtγ(Rt1γRt2…)∣Sts)Eπ(RtγGt1∣Sts)Eπ(Rtγvπ(St1)∣Sts)
即在 t t t 时刻的状态估计价值和在 t 1 t1 t1 时刻的状态估计价值满足如下的递推关系贝尔曼方程 v π ( s ) E π ( R t γ v π ( S t 1 ) ∣ S t s ) v_{\pi}(s)\mathrm{E}_{\pi}(R_{t}\gamma v_{\pi}(S_{t1})|S_ts) vπ(s)Eπ(Rtγvπ(St1)∣Sts)
其中 R t R_t Rt 是在状态 s s s 下采取动作后的即时奖励 γ \gamma γ 是奖励衰减因子。
3.2 动作价值函数的贝尔曼方程
除了状态价值估计函数 v π ( s ) v_{\pi}(s) vπ(s)还有一个动作价值函数 q π ( s , a ) q_{\pi}(s,a) qπ(s,a)该估计函数考虑了所采取的动作 a a a 对回报的影响公式与状态价值函数相似如下 q π ( s , a ) E π ( G t ∣ S t s , A t a ) E π ( R t γ R t 1 γ 2 R t 2 … ∣ S t s , A t a ) q_\pi(s,a)\mathrm{E}_\pi\left(G_t \mid S_ts, A_ta \right)\mathrm{E}_\pi\left(R_{t}\gamma R_{t1}\gamma^2 R_{t2}\ldots \mid S_ts,A_ta \right) qπ(s,a)Eπ(Gt∣Sts,Ata)Eπ(RtγRt1γ2Rt2…∣Sts,Ata)
同理可得 q π ( s , a ) q_{\pi}(s,a) qπ(s,a) 的贝尔曼方程如下 q π ( s , a ) E π ( R t γ q π ( S t 1 , A t 1 ) ∣ S t s ) q_{\pi}(s,a)\mathrm{E}_{\pi}(R_{t}\gamma q_{\pi}(S_{t1},A_{t1})|S_ts) qπ(s,a)Eπ(Rtγqπ(St1,At1)∣Sts)
3.3 价值函数递推关系的转换
前面的两种价值函数的贝尔曼方程尽管呈现了前后阶段的估计价值的递推关系但是仍是期望表达式为了最优化动作策略需要将动作策略 π ( a ∣ s ) \pi(a|s) π(a∣s) 纳入到递推关系当中。
根据动作价值函数 q π ( s , a ) q_{\pi}(s,a) qπ(s,a) 和状态价值函数 v π ( s ) v_{\pi}(s) vπ(s) 的定义可以得到如下的关系 v π ( s ) ∑ a ∈ A π ( a ∣ s ) q π ( s , a ) v_{\pi}(s)\sum_{a\in A} \pi(a|s)q_{\pi}(s,a) vπ(s)a∈A∑π(a∣s)qπ(s,a)
即当前状态的估计价值是所有动作的估计价值基于策略概率分布函数 π ( a ∣ s ) \pi(a|s) π(a∣s) 的期望值即在当前状态和当前策略下所有动作的估计价值乘以动作的选择概率求和后得到当前状态的估计价值。
同理在一个状态 s s s 下估计动作 a a a 的价值即采取了该动作之后状态转移到下一阶段状态的期望价值关系如下 q π ( s , a ) R t γ ∑ s ′ ∈ S ( P s s ′ a v π ( s ′ ) ) q_{\pi}(s,a)R_t\gamma \sum_{s\in S}(P^a_{ss}v_{\pi}(s)) qπ(s,a)Rtγs′∈S∑(Pss′avπ(s′))
即在状态 s s s 下采取动作 a a a由于环境的随机因素状态可能转移到其他的多种状态 s ′ s s′因此评估状态 s s s 下动作 a a a 的价值计算的是下一阶段的状态估计价值的期望再乘以下一阶段价值奖励的衰减因子 γ \gamma γ。
将上述两个式子彼此代入得到新的贝尔曼递推关系式如下 v π ( s ) ∑ a ∈ A π ( a ∣ s ) ( R t a γ ∑ s ′ ∈ S ( P s s ′ a v π ( s ′ ) ) ) v_{\pi}(s)\sum_{a\in A} \pi(a|s)(R_t^a\gamma \sum_{s\in S}(P^a_{ss}v_{\pi}(s))) vπ(s)a∈A∑π(a∣s)(Rtaγs′∈S∑(Pss′avπ(s′))) q π ( s , a ) R t a γ ∑ s ′ ∈ S ( P s s ′ a ∑ a ′ ∈ A π ( a ′ ∣ s ′ ) q π ( s ′ , a ′ ) ) q_{\pi}(s,a)R_t^a\gamma \sum_{s\in S}(P^a_{ss} \sum_{a\in A} \pi(a|s)q_{\pi}(s,a)) qπ(s,a)Rtaγs′∈S∑(Pss′aa′∈A∑π(a′∣s′)qπ(s′,a′))
4. 最优价值函数
当我们对价值函数的估计越准确即策略越有效则我们决策过程的累积奖励值越大。前面提到贝尔曼方程是作为求解最优价值函数的基础通过贝尔曼方程的递推关系我们可以迭代地求解出最优价值函数直到算法收敛。
假设在马尔可夫决策过程当中我们所采取的策略是最优的表示为 π ∗ \pi^* π∗它能使得我们在每个阶段的回报都比其他的策略所获回报要高得到这么一个策略就是强化学习问题所要求的解。但我们很难直接地找到这样地策略只能在不断的训练中去比较和学习更优的策略且对于复杂问题几乎不可能穷举所有的策略因此比较得到的最优策略是局部最优的。
比较策略的优劣最直接的方式就是通过比较策略在不同状态下的期望累积奖励大小其中使得期望累积奖励值达到最大的策略即为最优策略如下 v ∗ ( s ) max π v π ( s ) v_*(s)\max_{\pi}v_{\pi}(s) v∗(s)πmaxvπ(s)
同理最优动作价值函数的最优策略如下 q ∗ ( s , a ) max π q π ( s , a ) q_*(s,a)\max_{\pi}q_{\pi}(s,a) q∗(s,a)πmaxqπ(s,a)
假设动作 a a a 是最优策略所选出的最优动作这里暂不考虑策略的随机性则最优状态价值函数和最优动作价值函数之间的关系为 v ∗ ( s ) max a q ∗ ( s , a ) v_{*}(s)\max_{a}q_{*}(s,a) v∗(s)amaxq∗(s,a) q ∗ ( s , a ) R t a γ ∑ s ′ ∈ S ( P s s ′ a v ∗ ( s ′ ) ) q_{*}(s,a)R_t^a\gamma \sum_{s\in S}(P^a_{ss}v_{*}(s)) q∗(s,a)Rtaγs′∈S∑(Pss′av∗(s′))
同理将上述两个式子代入彼此可以得到最优价值函数如下 v ∗ ( s ) max a ( R t a γ ∑ s ′ ∈ S ( P s s ′ a v ∗ ( s ′ ) ) ) v_{*}(s)\max_{a} (R_t^a\gamma \sum_{s\in S}(P^a_{ss}v_{*}(s))) v∗(s)amax(Rtaγs′∈S∑(Pss′av∗(s′))) q ∗ ( s , a ) R t a γ ∑ s ′ ∈ S ( P s s ′ a max a ‘ q ∗ ( s ′ , a ′ ) ) q_{*}(s,a)R_t^a\gamma \sum_{s\in S}(P^a_{ss} \max_{a‘}q_{*}(s,a)) q∗(s,a)Rtaγs′∈S∑(Pss′aa‘maxq∗(s′,a′))
上述的最优价值函数是在强化学习的迭代训练中不断更新得到的随着训练场景增多价值函数不断逼近最优价值函数。
5. MDP计算最优值函数实例
现有一个关于学生开始的马尔科夫决策过程2左上角的圆圈是当前的起始位置状态右上角的方框是终点位置状态。学生可以采取的动作为下图弧线上的红色字符串有 S t u d y , F a c e b o o k , Q u i t , S l e e p , P u b Study,Facebook,Quit,Sleep,Pub Study,Facebook,Quit,Sleep,Pub各个状态下采取动作对应的即时奖励 R R R 的值在相关弧线上。现需要找到最优的状态价值或动作价值函数以期能够达成最优策略。 每个非结束状态都有两种可选择的动作因此为了方便我们令初始策略选择每个动作的概率 π ( a ∣ s ) \pi(a|s) π(a∣s) 均为 0.5 0.5 0.5同时假设奖励衰减因子为 1 1 1即初始策略下会考虑当前及未来全量的累积奖励。
这里我们将终点状态的价值设为 0 0 0即不论由什么状态通过什么动作直接到达终点都不增加奖励。接着定义左上 s 1 s_1 s1、左下 s 2 s_2 s2、中下 s 3 s_3 s3、右下 s 4 s_4 s4 四个圆圈的状态价值为 v 1 , v 2 , v 3 , v 4 v_1,v_2,v_3,v_4 v1,v2,v3,v4通过以下公式计算各个状态的估计价值状态价值函数 v π ( s ) ∑ a ∈ A π ( a ∣ s ) ( R t a γ ∑ s ′ ∈ S ( P s s ′ a v π ( s ′ ) ) ) v_{\pi}(s)\sum_{a\in A} \pi(a|s)(R_t^a\gamma \sum_{s\in S}(P^a_{ss}v_{\pi}(s))) vπ(s)a∈A∑π(a∣s)(Rtaγs′∈S∑(Pss′avπ(s′)))
先从起始状态出发可得如下的方程组 v 1 0.5 × ( 0 v 2 ) 0.5 × ( − 1 v 1 ) v 2 0.5 × ( − 1 v 1 ) 0.5 × ( − 2 v 3 ) v 3 0.5 × ( − 2 v 4 ) 0.5 × ( 0 0 ) v 4 0.5 × ( 10 0 ) 0.5 × ( 1 0.2 × v 2 0.4 × v 3 0.4 × v 4 ) v_10.5\times (0v_2) 0.5\times (-1v_1)\\ v_20.5\times (-1v_1) 0.5\times (-2v_3)\\ v_30.5\times (-2v_4) 0.5\times (00)\\ v_40.5\times (100) 0.5\times (10.2\times v_2 0.4\times v_3 0.4\times v_4) v10.5×(0v2)0.5×(−1v1)v20.5×(−1v1)0.5×(−2v3)v30.5×(−2v4)0.5×(00)v40.5×(100)0.5×(10.2×v20.4×v30.4×v4)
通过解方程得到 v 1 − 2.3 , v 2 − 1.3 , v 3 2.7 , v 4 7.4 v_1-2.3,v_2-1.3,v_32.7,v_47.4 v1−2.3,v2−1.3,v32.7,v47.4这是在我们规定好价值函数之后求得的状态估计价值但这不一定是最优价值函数。求最优价值函数的关键在于求出各个状态的价值以及每个状态可以采取的动作的估计价值
假设终点的状态价值仍为 0 0 0系统的奖励衰减因子 γ 1 \gamma1 γ1可得在未知最优策略 π ( a ∣ s ) \pi(a|s) π(a∣s) 下 q ∗ ( s 3 , s l e e p ) 0 , q ∗ ( s 4 , s t u d y ) 10 q_*(s_3, sleep)0, q_*(s_4,study)10 q∗(s3,sleep)0,q∗(s4,study)10。接着利用如下公式 q ∗ ( s , a ) R t a γ ∑ s ′ ∈ S ( P s s ′ a max a ’ q ∗ ( s ′ , a ′ ) ) q_{*}(s,a)R_t^a\gamma \sum_{s\in S}(P^a_{ss} \max_{a’}q_{*}(s,a)) q∗(s,a)Rtaγs′∈S∑(Pss′aa’maxq∗(s′,a′))
得到 q ∗ ( s 3 , s t u d y ) − 2 max ( q ∗ ( s 4 , s t u d y ) , q ∗ ( s 4 , p u b ) ) q ∗ ( s 4 , p u b ) 1 0.2 × max ( q ∗ ( s 2 , f a c e b o o k ) , q ∗ ( s 2 , s t u d y ) ) 0.4 × max ( q ∗ ( s 3 , s t u d y ) , q ∗ ( s 3 , s l e e p ) ) 0.4 × max ( q ∗ ( s 4 , s t u d y ) , q ∗ ( s 4 , p u b ) ) q ∗ ( s 2 , s t u d y ) − 2 max ( q ∗ ( s 3 , s t u d y ) , q ∗ ( s 3 , s l l e p ) ) q ∗ ( s 2 , f a c e b o o k ) − 1 max ( q ∗ ( s 1 , f a c e b o o k ) , q ∗ ( s 1 , q u i t ) ) q ∗ ( s 1 , f a c e b o o k ) − 1 max ( q ∗ ( s 1 , f a c e b o o k ) , q ∗ ( s 1 , q u i t ) ) q ∗ ( s 1 , q u i t ) − 1 max ( q ∗ ( s 2 , s t u d y ) , q ∗ ( s 2 , f a c e b o o k ) ) q_*(s_3,study)-2\max(q_*(s_4,study), q_*(s_4,pub))\\ q_*(s_4,pub)10.2\times \max(q_*(s_2,facebook), q_*(s_2,study)) 0.4\times \max(q_*(s_3,study), q_*(s_3,sleep)) 0.4\times\max(q_*(s_4,study), q_*(s_4,pub))\\ q_*(s_2,study)-2\max(q_*(s_3,study), q_*(s_3,sllep))\\ q_*(s_2,facebook)-1\max(q_*(s_1,facebook), q_*(s_1,quit))\\ q_*(s_1,facebook)-1\max(q_*(s_1,facebook), q_*(s_1,quit))\\ q_*(s_1,quit)-1\max(q_*(s_2,study), q_*(s_2,facebook)) q∗(s3,study)−2max(q∗(s4,study),q∗(s4,pub))q∗(s4,pub)10.2×max(q∗(s2,facebook),q∗(s2,study))0.4×max(q∗(s3,study),q∗(s3,sleep))0.4×max(q∗(s4,study),q∗(s4,pub))q∗(s2,study)−2max(q∗(s3,study),q∗(s3,sllep))q∗(s2,facebook)−1max(q∗(s1,facebook),q∗(s1,quit))q∗(s1,facebook)−1max(q∗(s1,facebook),q∗(s1,quit))q∗(s1,quit)−1max(q∗(s2,study),q∗(s2,facebook))
根据上述方程组求解得到各个状态下的动作价值 q ∗ ( s 3 , s t u d y ) 8 q ∗ ( s 4 , p u b ) 8.4 q ∗ ( s 2 , s t u d y ) 6 q ∗ ( s 2 , f a c e b o o k ) 5 q ∗ ( s 1 , f a c e b o o k ) 5 q ∗ ( s 1 , q u i t ) 6 q_*(s_3,study) 8\\ q_*(s_4,pub)8.4\\ q_*(s_2,study)6\\ q_*(s_2,facebook)5\\ q_*(s_1,facebook)5\\ q_*(s_1,quit)6 q∗(s3,study)8q∗(s4,pub)8.4q∗(s2,study)6q∗(s2,facebook)5q∗(s1,facebook)5q∗(s1,quit)6
接着根据如下公式计算各个状态的估计价值 v ∗ ( s ) max a q ∗ ( s , a ) v_{*}(s)\max_{a}q_{*}(s,a) v∗(s)amaxq∗(s,a)
可得 v 1 6 , v 2 6 , v 3 8 , v 4 10 v_16,v_26,v_38,v_410 v16,v26,v38,v410即为最终的最优价值估计基于这些价值估计的策略可得最优的学习路线为 s 1 → s 2 → s 3 → s 4 → s_1\rightarrow s_2\rightarrow s_3\rightarrow s_4\rightarrow s1→s2→s3→s4→ 终点。 马尔科夫决策过程(MDP) https://www.cnblogs.com/pinard/p/9426283.html ↩︎ UCL 强化学习第二章节讲义 https://www.davidsilver.uk/wp-content/uploads/2020/03/MDP.pdf ↩︎
