盐城市亭湖区建设局网站,手机网站设计与实现是什么,韩城建设公司网站,制作小程序的方法如何自己制作小程序【强化学习的数学原理-赵世钰】课程笔记#xff08;二#xff09;贝尔曼公式
一. 内容概述
1. 第二章主要有两个内容
#xff08;1#xff09;一个核心概念#xff1a;状态值#xff08;state value#xff09;#xff1a;从一个状态出发#xff0c;沿着一个策略我…【强化学习的数学原理-赵世钰】课程笔记二贝尔曼公式
一. 内容概述
1. 第二章主要有两个内容
1一个核心概念状态值state value从一个状态出发沿着一个策略我所得到的奖励回报的平均值。状态值越高说明对应的策略越好。之所以关注状态值是因为它能评价一个策略的好坏。
2基本工具贝尔曼公式the Bellman equation
用于分析状态值描述所有状态和状态值之间的关系这个关系就是一个方程一个等式。通过求解这个方程就可以求解出来一个给定策略的状态值因此就可以评价这个策略的好坏。求解贝尔曼公式进而得到一个策略所对应的状态值这样的一个过程被称为策略评价policy evaluationpolicy evaluation 在强化学习中是非常基础的一个概念我评价了一个策略得到它的值然后基于它的值再改进策略然后循环下去最后就能得到一个最优的策略。
2. 第二章大纲
激励性实例Motivating examples状态值state value贝尔曼公式 Bellman equation推导贝尔曼公式 Bellman equation矩阵向量形式贝尔曼公式 Bellman equation求解状态值state value动作值从 state value 过渡到 action value
二. 激励性实例Motivating examples
1. 例子1为什么回报/收益return很重要
1什么是回报return
沿着轨迹获得的奖励reward的折扣discounted总和。
What is return? The (discounted) sum of the rewards obtained along a trajectory.
2为什么回报return很重要
下图的第三个表示这个策略在 s1 状态有百分之 50 的概率向右有百分之 50 的概率向下。 问题 从起点 s 1 s_1 s1 出发哪项策略policy是 “最好的”哪项 “最差”
直觉 第一个最好第二个最差因为第二个进入了forbidden area。第三个策略是不好也不差它有一定的概率进入forbidden area。
数学 我们能用数学来描述这种直觉吗
回报return可以用来评估策略policyreturn 可以告诉我们哪个策略好哪个策略坏这样才能不断地改进策略。请参阅下文。
根据策略 1左图从 s 1 s_1 s1 开始折扣回报discounted return为 r e t u r n 1 0 γ 1 γ 2 1 … , γ ( 1 γ γ 2 … ) , γ 1 − γ \begin{align} return_1 0 \gamma 1 \gamma^2 1 \dots, \\ \gamma(1 \gamma \gamma^2 \dots), \\ \frac{\gamma}{1 - \gamma} \end{align} return10γ1γ21…,γ(1γγ2…),1−γγ
根据策略 2中图从 s 1 s_1 s1 开始折扣回报discounted return为 r e t u r n 2 − 1 γ 1 γ 2 1 … , − 1 γ ( 1 γ γ 2 … ) , − 1 γ 1 − γ \begin{align} return_2 -1 \gamma 1 \gamma^2 1 \dots, \\ -1 \gamma(1 \gamma \gamma^2 \dots), \\ -1 \frac{\gamma}{1 - \gamma} \end{align} return2−1γ1γ21…,−1γ(1γγ2…),−11−γγ
根据策略 3右图从 s 1 s_1 s1 开始折扣回报discounted return为策略3是随机性的Policy 3 is stochastic! r e t u r n 3 0.5 ( − 1 γ 1 − γ ) 0.5 ( γ 1 − γ ) − 0.5 γ 1 − γ \begin{align} return_3 0.5 (-1 \frac{\gamma}{1 - \gamma}) 0.5(\frac{\gamma}{1-\gamma}) \\ -0.5 \frac{\gamma}{1-\gamma} \end{align} return30.5(−11−γγ)0.5(1−γγ)−0.51−γγ
策略 3 这里其实是在计算期望。这里已经不是 return 的概念了return 的概念是针对一个轨迹定义的现在有两个轨迹我们在做的是求平均值即求期望。其实这里求的是状态值state value。
总之从 s 1 s_1 s1 开始 r e t u r n 1 r e t u r n 3 r e t u r n 2 return_1 return_3 return_2 return1return3return2 上述不等式表明第一种策略是最好的第二种策略是最差的这与我们的直觉完全相同。
计算回报return对于评估一项策略非常重要。
2. 例子2如何计算回报return 上图中四个状态state是 s 1 , s 2 , s 3 , s 4 s_1,s_2,s_3,s_4 s1,s2,s3,s4策略policy是绿色的箭头奖励reward是 r 1 , r 2 , r 3 , r 4 r_1,r_2,r_3,r_4 r1,r2,r3,r4。
1方法1通过定义
让 v i v_i vi 表示从 s i ( i 1 , 2 , 3 , 4 ) s_i(i 1,2,3,4) si(i1,2,3,4)出发得到的回报return。
注意轨迹是无穷的例如从 s 1 s_1 s1 出发 s 1 → s 2 → s 3 → s 4 → s 1 → s 2 … . s_1 \rightarrow s_2 \rightarrow s_3 \rightarrow s_4 \rightarrow s_1 \rightarrow s_2\dots. s1→s2→s3→s4→s1→s2….会一直走下去 v 1 r 1 γ r 2 γ 2 r 3 … v 2 r 2 γ r 3 γ 2 r 4 … v 3 r 3 γ r 4 γ 2 r 1 … v 4 r 4 γ r 1 γ 2 r 2 … \begin{align} v_1 r_1 \gamma r_2 \gamma^2 r_3 \dots \\ v_2 r_2 \gamma r_3 \gamma^2 r_4 \dots \\ v_3 r_3 \gamma r_4 \gamma^2 r_1 \dots \\ v_4 r_4 \gamma r_1 \gamma^2 r_2 \dots \\ \end{align} v1v2v3v4r1γr2γ2r3…r2γr3γ2r4…r3γr4γ2r1…r4γr1γ2r2…
2方法2 v 1 r 1 γ ( r 2 γ r 3 … ) r 1 γ v 2 v 2 r 2 γ ( r 3 γ r 4 … ) r 2 γ v 3 v 3 r 3 γ ( r 4 γ r 1 … ) r 3 γ v 4 v 4 r 4 γ ( r 1 γ r 2 … ) r 4 γ v 1 \begin{align} v_1 r_1 \gamma (r_2 \gamma r_3 \dots) r_1 \gamma v_2 \\ v_2 r_2 \gamma (r_3 \gamma r_4 \dots) r_2 \gamma v_3 \\ v_3 r_3 \gamma (r_4 \gamma r_1 \dots) r_3 \gamma v_4 \\ v_4 r_4 \gamma (r_1 \gamma r_2 \dots) r_4 \gamma v_1 \\ \end{align} v1v2v3v4r1γ(r2γr3…)r1γv2r2γ(r3γr4…)r2γv3r3γ(r4γr1…)r3γv4r4γ(r1γr2…)r4γv1
上面这一组式子告诉我们从不同状态出发得到的 return 依赖于从其他状态出发得到的 return回报return相互依赖。 这一思想在强化学习中被称为 Bootstrapping ! 现代的意思就是引申出来我从自己出发然后不断地迭代所得到的一些结果。 如何使用这些方程把上面的一组式子写成矩阵向量的形式matrix-vector form 可被重写成一种更简化的形式 v r γ P v v r \gamma Pv vrγPv I I I (identity matrix)减去 γ \gamma γ 然后乘以P 矩阵然后乘以 v v v 就等于 γ \gamma γ 把 ( I − v P ) (I - vP) (I−vP)这个矩阵求逆然后乘以 γ \gamma γ 就得到了 v v v 。
从上面的方程可以解出从不同状态出发的价值value v 这就是贝尔曼公式针对这个特定的确定性 deterministic 问题
虽然简单但它展示了核心概念一个状态state的价值value依赖于其他状态state的价值value矩阵向量形式更容易理解如何求解状态值state value。
练习
考虑图中所示的策略policy。请写出回报return之间的关系即写出贝尔曼方程 答案从 s 1 s_1 s1 出发以奖励 0 到状态 s 3 s_3 s3 从状态 s 3 s_3 s3 出发得到的 return 是 v 3 v_3 v3从 s 2 s_2 s2 出发以奖励 1 到状态 s 4 s_4 s4 从状态 s 4 s_4 s4 出发 得到的 return 是 v 4 v_4 v4… v 1 0 γ v 3 v 2 1 γ v 4 v 3 1 γ v 4 v 4 1 γ v 4 \begin{align} v_1 0 \gamma v_3 \\ v_2 1 \gamma v_4 \\ v_3 1 \gamma v_4 \\ v_4 1 \gamma v_4 \\ \end{align} v10γv3v21γv4v31γv4v41γv4 如何求解这是一个线性方程组很好求解。 我们可以先计算 v 4 v_4 v4然后计算 v 3 , v 2 , v 1 v_3,v_2,v_1 v3,v2,v1。
三. 状态值state value
单步
单步single-step流程 b S t → A t R t 1 , S t 1 S_t \xrightarrow{A_t} R_{t1},S_{t1} StAt Rt1,St1 t , t 1 t,t 1 t,t1离散时间实例 t t t 指当前的时刻 t 1 t1 t1 指下一个时刻 S t t S_tt Stt 时刻的状态 A t A_t At在状态 S t S_t St 采取的动作 R t 1 R_{t1} Rt1在状态 S t S_t St 采取动作 A t A_t At 之后获得的奖励reward有时也写成 R t R_t Rt写成什么都没有区别只是一个习惯但是一般都写成 R t 1 R_{t1} Rt1 S t 1 S_{t1} St1采取动作 A t A_t At 后转换到的状态
注意 S t 、 A t 、 R t 1 S_t、A_t、R_{t1} St、At、Rt1 都是大写的代表随机变量random variables就是我们可以对它进行一系列的操作比如求期望expectation。
每一步的所有跳跃step都由以下概率分布probability distributions所决定
在 S t S_t St 要采取什么样的动作action由 策略 π \pi π 来决定在 S t S_t St 采取动作take action A t A_t At要得到什么样的奖励Reward由奖励概率reward probability 决定在 S t S_t St 采取动作take action A t A_t At要跳到下一个什么状态State由状态转移概率 state transition probability 决定 governed受约束的所规管的
多步
考虑以下多步骤轨迹multi-step trajectory S t → A t R t 1 , S t 1 → A t 1 R t 2 , S t 2 → A t 2 R t 3 , … S_t \xrightarrow{A_t} R_{t1},S_{t1} \xrightarrow{A_{t1}} R_{t2},S_{t2} \xrightarrow{A_{t2}} R_{t3},\dots StAt Rt1,St1At1 Rt2,St2At2 Rt3,… 折扣回报discounted returnGt 是所有瞬时回报immediate reward与折扣因子discount rate乘积相加 G t R t 1 γ R t 2 γ 2 R t 3 … G_t R_{t1} \gamma R_{t2} \gamma^2 R_{t3} \dots GtRt1γRt2γ2Rt3… γ ∈ [ 0 , 1 ) \gamma \in [0,1) γ∈[0,1) 是折扣率discount rate。 G t G_t Gt 也是一个随机变量random variables因为 R t 1 , R t 2 R_{t1},R_{t2} Rt1,Rt2都是随机变量random variables。
正式定义状态值state value
折扣回报discounted return G t G_t Gt 的期望值或称为期望值 expectation 或平均值 mean被定义为状态值函数state-value function或简称为状态值state value 注意
状态值state value它是 s 的函数 是一种条件期望conditional expectation条件是状态从 s 开始。从不同的状态 s 出发得到的轨迹不同得到的折扣回报discounted return G t G_t Gt 也不同状态值state value它是策略 π \pi π 的函数 对于不同的策略policy 会得到不同的轨迹不同的轨迹会得到不同的折扣回报discounted returnGt就会得到不同的状态值state value它代表一个状态的 “价值”。如果状态值state value越大那么从这个状态出发的策略policy就更好因为可以获得更大的累积回报return。
问 回报return与状态值state value之间的关系是什么
答
回报return是针对单个轨迹trajectory求的 return
状态值state value针对多个轨迹trajectory得到的 return 再求平均值。
如果从一个状态出发有可能得到多个轨迹trajectory这时候回报return与状态值state value显然有区别
但假如从一个状态出发一切都是确定性的只能得到一条轨迹trajectory这时候那个状态的回报return与那个状态的状态值state value是一样的。 例子 这三个例子分别对应三个策略 π 1 , π 2 , π 3 \pi_1,\pi_2,\pi_3 π1,π2,π3三个策略导致了三个轨迹trajectory 理解为根据策略可能走出的轨迹要计算在这三个不同策略下同一个状态 s 1 s_1 s1 的状态值state value 策略 1 和 2 从 s 1 s_1 s1 出发能得到唯一的一个 trajectory这个 trajectory 的 return 就是它们分别的 state value
策略 3 有两条轨迹状态值state value是这两条轨迹分别得到的回报return的平均值。就是把 probability 乘到前面去这实际上就是期望expectation的求法。
比较三个策略导致的状态值state value的大小可知第一种策略是最好的第二种策略是最差的这与我们的直觉完全相同。
四. 贝尔曼公式推导
1. 推导
状态值state value固然重要但如何计算呢答案就在贝尔曼公式Bellman equation中。总之贝尔曼公式Bellman equation描述了不同状态的状态值state value之间的关系。
考虑一个随机轨迹 S t → A t R t 1 , S t 1 → A t 1 R t 2 , S t 2 → A t 2 R t 3 , … S_t \xrightarrow{A_t} R_{t1},S_{t1} \xrightarrow{A_{t1}} R_{t2},S_{t2} \xrightarrow{A_{t2}} R_{t3},\dots StAt Rt1,St1At1 Rt2,St2At2 Rt3,… 折扣回报discounted return G t G_t Gt 可写成 G t R t 1 γ R t 2 γ 2 R t 3 … R t 1 γ ( R t 2 γ R t 3 … ) R t 1 γ G t 1 \begin{align} G_t R_{t1} \gamma R_{t2} \gamma^2 R_{t3} \dots \\ R_{t1} \gamma(R_{t2} \gamma R_{t3} \dots) \\ R_{t1} \gamma G_{t1} \end{align} GtRt1γRt2γ2Rt3…Rt1γ(Rt2γRt3…)Rt1γGt1 所以这个时刻我所得到的 return 等于我能立即得到的奖励immediate reward R t 1 R_{t1} Rt1 加上到下一时刻从那出发能得到的 return futrue reward乘以 discount rate
那么根据状态值state value的定义可以得出 v π ( s ) E [ G t ∣ S t s ] E [ R t 1 γ G t 1 ∣ S t s ] E [ R t 1 ∣ S t s ] γ E [ G t 1 ∣ S t s ] \begin{align} v_{\pi}(s) \mathbb{E}[G_t|S_t s]\\ \mathbb{E}[R_{t1} \gamma G_{t1} | S_t s] \\ {\color{blue} \mathbb{E}[R_{t1}|S_t s]} \gamma {\color{blue} \mathbb{E}[G_{t1}|S_t s]} \end{align} vπ(s)E[Gt∣Sts]E[Rt1γGt1∣Sts]E[Rt1∣Sts]γE[Gt1∣Sts] 接下来分别计算这两个项求出他们的形式就得到了贝尔曼公式
首先计算第一项 E [ R t 1 ∣ S t s ] \mathbb{E}[R_{t1}|S_t s] E[Rt1∣Sts]当前时刻我在状态 s 我得到的立即奖励immediate reward是 R t 1 R_{t1} Rt1 E [ R t 1 ∣ S t s ] ∑ a π ( a ∣ s ) E [ R t 1 ∣ S t s , A t a ] ∑ a π ( a ∣ s ) ∑ r p ( r ∣ s , a ) r \begin{align} \mathbb{E}[R_{t1}|S_t s] \sum_a \pi(a|s) \mathbb{E} [R_{t1}|S_t s,A_t a] \\ \sum_a \pi(a|s) \sum_r p(r|s,a)r \end{align} E[Rt1∣Sts]a∑π(a∣s)E[Rt1∣Sts,Ata]a∑π(a∣s)r∑p(r∣s,a)r 理解
在状态 s 我有多个 action 可以去选择take action a 的概率是 π ( a ∣ s ) \pi(a|s) π(a∣s)当我 take action a 我所得到的 value 是 E [ R t 1 ∣ S t s , A t a ] \mathbb{E}[R_{t1}|S_t s, A_t a] E[Rt1∣Sts,Ata]。 E [ R t 1 ∣ S t s , A t a ] \mathbb{E}[R_{t1}|S_t s, A_t a] E[Rt1∣Sts,Ata] 可以写成 ∑ r p ( r ∣ s , a ) r \sum\limits_r p(r|s,a)r r∑p(r∣s,a)r
意思是从 s s s 出发take action a a a得到的奖励reward是 r r r 的概率是 p ( r ∣ s , a ) p(r|s,a) p(r∣s,a)根据期望的定义取值为 r r r 的概率乘以 r r r 本身就是期望。 注意 第一项其实就是我能得到的立即奖励immediate reward的期望/平均 大写的 S 不确定小写的 s 是确定的。在前面的 state value 定义时已说明S、R 表示随机变量。这里的大写 StAtRt1都是集合所以对于任意时刻 tS 是确定的A 可能有几种不同选择。 而之前的例子是确定性奖励所以对于 R 是一个集合变量印象不深。最简单的就是抽奖你每次执行同样的行为得到的奖励却不同这里 Πa|s) 是采取动作 a 的概率后面一项是采取这个动作之后到下一个不同状态的概率比如我有 0.5 概率pai撞到墙但是撞到墙之后有 0.1 概率原地不动也有 0.9 概率后退一步这部分内容就是后面的 p这里就是枚举了所有动作下的概率和收益的成绩加起来算了期望就是两次离散型随机变量计算期望
其次计算第二项 E [ G t 1 ∣ S t s ] \mathbb{E}[G_{t1}|S_t s] E[Gt1∣Sts]第二项是我从当前状态 s s s 出发得到的下一个时刻的回报return的期望mean 第一行从当前 s s s 出发有多个选择可以跳到不同 s ′ s s′ 跳到不同 s ′ s s′ 的概率是 p ( s ′ ∣ s ) p(s | s) p(s′∣s)跳到不同 s ′ s s′ 所得到的值是 E [ G t 1 ∣ S t s , S t 1 s ’ ] \mathbb{E}[G_{t1}|S_t s,S_{t1} s’ ] E[Gt1∣Sts,St1s’]一相加就是 (expectation) E [ G t 1 ∣ S t s ] \mathbb{E}[G_{t1}|S_t s] E[Gt1∣Sts]从第一行到第二行 E [ G t 1 ∣ S t s , S t 1 s ′ ] \mathbb{E}[G_{t1}|S_t s,S_{t1} s ] E[Gt1∣Sts,St1s′] 意思是当前状态是 s s s下一个状态是 s ′ s s′计算从下一个状态出发所得到回报return的期望mean第二行 E [ G t 1 ∣ S t 1 s ′ ] \mathbb{E}[G_{t1}|S_{t1} s ] E[Gt1∣St1s′] 把第一行中那一项的 S t s S_t s Sts 去掉了因为我已经知道了下一个状态是 s ′ s s′就不用关心我之前究竟是在什么状态了这其实就是马尔可夫的性质是无记忆的memoryless Markov property从第二行到第三行 E [ G t 1 ∣ S t 1 s ′ ] \mathbb{E}[G_{t1} | S_{t1} s ] E[Gt1∣St1s′] 意思是从下一个状态 s’ 出发计算我所能得到的回报return的平均值mean这个就是第三行写的一个状态值state value v π ( s ′ ) v_{\pi}(s) vπ(s′)只不过是针对 s ′ s s′ 的状态值state value v π ( s ′ ) v_{\pi}(s) vπ(s′)。——最开始的状态值state value的定义从第三行到第四行从 s s s 到 s ′ s s′ 的概率 p ( s ′ ∣ s ) p(s | s) p(s′∣s)从 s s s 出发我有多种选择可以选择不同的动作action选择 action a 的概率是 π ( a ∣ s ) \pi (a|s) π(a∣s) 选择这个 action 我跳到 s ′ s s′ 的概率是 p ( s ′ ∣ s , a ) p(s |s, a) p(s′∣s,a)通过两者相乘相加可以得到 p ( s ′ ∣ s ) p(s | s) p(s′∣s)。
注意
第二项是 future reward 的平均mean E [ G t 1 ∣ S t s , S t 1 s ′ ] E [ G t 1 ∣ S t 1 s ′ ] \mathbb{E}[G_{t1}|S_t s,S_{t1} s] \mathbb{E}[G_{t1}|S_{t1} s] E[Gt1∣Sts,St1s′]E[Gt1∣St1s′] 是由于由于无记忆马尔可夫特性memoryless Markov property
贝尔曼公式Bellman equation此处 σ \sigma σ 后面应该加一个左大括号 {右大括号在式子的最后面 } 强调由方程中的符号可以得出以下重点
上述方程称为贝尔曼方程Bellman equation它描述了不同状态states的状态值函数state-value functions之间的关系因为看上面式子标红的地方上面式子等式左边是 s s s 的状态值state value等式右边是 s ′ s s′ 的状态值state value他们的关系可以通过这样的一个式子表达出来。它由两个项组成即时奖励项immediate reward term和未来奖励项future reward term。这是一组等式每个状态state都有这样的等式这不是一个式子这个式子对状态空间中的所有状态都成立等式后面的取值范围是 ∀ s ∈ S \forall s \in S ∀s∈S所以如果有 n 个状态就有 n 个这样的式子通过这 n 个式子可以求解出状态值state value。 v π ( s ) v_{\pi}(s) vπ(s) 和 v π ( s ′ ) v_{\pi}(s) vπ(s′) 是我们要计算的状态值计算的思想就是 Bootstrapping ! 直观上来讲等式左边的状态值state value v π ( s ) v_{\pi}(s) vπ(s))依赖于等式右边的状态值state value v π ( s ′ ) v_{\pi}(s) vπ(s′)看起来好像没法计算其实我们有一组这样的式子把这些式子连立就可以算出来。公式中的 π ( a ∣ s ) \pi (a|s) π(a∣s) 是给定的策略 policy是一种概率 probability。解方程称为策略评估policy evaluation贝尔曼公式依赖于策略policy如果我们能计算出状态值state value其实我们在做的一件事就是评估这个策略policy evaluation究竟是好是坏 。奖励概率 Reward probability p ( r ∣ s , a ) p(r|s,a) p(r∣s,a) 和状态转换概率State transition probability p ( s ′ ∣ s , a ) p(s|s,a) p(s′∣s,a) 代表的是动态模型dynamic model或称为环境模型environment model 分两种情况一种是我们知道这个模型model在本节和下节当中我们都会假设知道这个 model给出来相应的算法一种是不知道模型model这种情况下我们仍然可以求出 state value这就是 model free reinforcement learning 的算法。 2. 例子
1例子1
图中的策略 π \pi π 由绿色的箭头表示 根据一般表达式general expression写出贝尔曼方程 v π ( s ) ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] v_{\pi}(s) \sum_a \pi(a|s)\left[\sum_r p(r|s,a)r \gamma \sum_{s}p(s|s,a)v_{\pi}(s)\right] vπ(s)a∑π(a∣s)[r∑p(r∣s,a)rγs′∑p(s′∣s,a)vπ(s′)] 这个例子很简单因为策略policy是确定的deterministic。
首先考虑 s 1 s_1 s1 的状态值state value π ( a a 3 ∣ s 1 ) 1 a n d π ( a ≠ a 3 ∣ s 1 ) 0 p ( s ′ s 3 ∣ s 1 , a 3 ) 1 a n d p ( s ′ ≠ s 3 ∣ s 1 , a 3 ) 0 p ( r 0 ∣ s 1 , a 3 ) 1 a n d p ( r ≠ 0 ∣ s 1 , a 3 ) 0 \pi(a a_3|s_1) 1 \ \ and \ \ \pi(a \ne a_3 | s_1) 0 \\ p(s s_3|s_1,a_3)1 \ \ and p(s \ne s_3 | s_1,a_3) 0 \\ p(r0|s_1,a_3)1 \ \ and p(r \ne 0 | s_1,a_3) 0 π(aa3∣s1)1 and π(aa3∣s1)0p(s′s3∣s1,a3)1 andp(s′s3∣s1,a3)0p(r0∣s1,a3)1 andp(r0∣s1,a3)0 将上面这些概率和值代入贝尔曼方程得出下面这个式子和上面在 二.2 那部分用激励性例子 2 介绍的方法计算出的结果一样即与上面直观计算出的结果是一样的虽然此时是用复杂贝尔曼公式得到的但从直观上来讲很容易理解 v π ( s 1 ) 0 γ v π ( s 3 ) v_{\pi}(s_1) 0 \gamma v_{\pi}(s_3) vπ(s1)0γvπ(s3) 类似地可以得出 v π ( s 1 ) 0 γ v π ( s 3 ) v π ( s 2 ) 1 γ v π ( s 4 ) v π ( s 3 ) 1 γ v π ( s 4 ) v π ( s 4 ) 1 γ v π ( s 4 ) v_{\pi}(s_1) 0 \gamma v_{\pi}(s_3) \\ v_{\pi}(s_2) 1 \gamma v_{\pi}(s_4) \\ v_{\pi}(s_3) 1 \gamma v_{\pi}(s_4) \\ v_{\pi}(s_4) 1 \gamma v_{\pi}(s_4) vπ(s1)0γvπ(s3)vπ(s2)1γvπ(s4)vπ(s3)1γvπ(s4)vπ(s4)1γvπ(s4) 从最后一个方程到第一个方程逐一求解上述方程得到 v π ( s 4 ) 1 1 − γ v π ( s 3 ) 1 1 − γ v π ( s 2 ) 1 1 − γ v π ( s 1 ) γ 1 − γ v_{\pi}(s_4) \frac{1}{1-\gamma} \\ v_{\pi}(s_3) \frac{1}{1-\gamma} \\ v_{\pi}(s_2) \frac{1}{1-\gamma} \\ v_{\pi}(s_1) \frac{\gamma}{1-\gamma} \\ vπ(s4)1−γ1vπ(s3)1−γ1vπ(s2)1−γ1vπ(s1)1−γγ 如果 γ 0.9 \gamma 0.9 γ0.9那么 v π ( s 4 ) 1 1 − 0.9 10 v π ( s 3 ) 1 1 − 0.9 10 v π ( s 2 ) 1 1 − 0.9 10 v π ( s 1 ) 0.9 1 − 0.9 9 v_{\pi}(s_4) \frac{1}{1-0.9} 10 \\ v_{\pi}(s_3) \frac{1}{1-0.9} 10\\ v_{\pi}(s_2) \frac{1}{1-0.9} 10\\ v_{\pi}(s_1) \frac{0.9}{1-0.9} 9\\ vπ(s4)1−0.9110vπ(s3)1−0.9110vπ(s2)1−0.9110vπ(s1)1−0.90.99 计算出 s 1 s_1 s1 的状态值是 9 s 2 , s 3 , s 4 s_2,s_3,s_4 s2,s3,s4 的状态值是 10。状态值state values代表这个状态的价值如果一个状态的价值高说明这个状态是值得我们往那个方向走的之所以 s 2 , s 3 , s 4 s_2,s_3,s_4 s2,s3,s4 的价值高是因为它们距离 target area 比较近。 计算出状态值state values后干什么
耐心等待计算行动值action value并改进策略improve policy慢慢的就会得到最优策略。
s 2 s_2 s2 不是陷阱吗为什么状态值那么高
前面提到过reward 是给动作打分现在的 v v v 是状态的得分所以虽然 s 2 s_2 s2 是陷阱但是进入陷阱的惩罚是不体现在陷阱这个状态里面的陷阱的负价值体现在 s 1 s_1 s1 的 value 是最小的上面因为只有 s 1 s_1 s1 有可能往陷阱走 s 2 s_2 s2 的策略是走向 s 4 s_4 s4这个是高价值的如果 s 1 s_1 s1 还有一个策略是走向 s 2 s_2 s2那么 s 1 s_1 s1 的 value 还会进一步降低
2例子2 v π ( s ) ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] v_{\pi}(s) \sum_a \pi(a|s)\left[\sum_r p(r|s,a)r \gamma \sum_{s}p(s|s,a)v_{\pi}(s)\right] vπ(s)a∑π(a∣s)[r∑p(r∣s,a)rγs′∑p(s′∣s,a)vπ(s′)]
写出每个状态的贝尔曼方程。求解贝尔曼方程中的状态值。与上一个示例中的策略进行比较。 在这个策略policy下计算出 s 1 s_1 s1 的状态值state value是 8.5 s 2 , s 3 , s 4 s_2,s_3,s_4 s2,s3,s4 的状态值state value是 10。而在上一个策略policy下 s 1 s_1 s1 的状态值state value是 9。
所以这个策略没有刚才的策略好。
五.贝尔曼公式 Bellman equation矩阵向量形式Matrix-vector form
为什么要考虑矩阵向量形式因为我们需要从中求解状态值state value
一个未知数依赖于另一个未知数。如何解决这些未知数 v π ( s ) ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] {\color{red}v_{\pi}(s)} \sum_a \pi(a|s)\left[ \sum_r p(r|s,a)\gamma \sum_{s} p(s|s,a) {\color{red}v_{\pi}(s)} \right] vπ(s)a∑π(a∣s)[r∑p(r∣s,a)γs′∑p(s′∣s,a)vπ(s′)]
元素形式Elementwise form 上述元素形式的方程对每个状态 s ∈ S s \in S s∈S 都成立如果有 n n n 个状态就有 n n n 个这样的方程。这意味着有这样的 ∣ S ∣ |S| ∣S∣ 方程矩阵向量形式Matrix-vector form 如果我们把所有方程放在一起就会得到一组线性方程可以简洁地写成矩阵向量形式。矩阵向量形式非常优雅也非常重要。
1. 推导出矩阵向量形式
回顾一下 v π ( s ) ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] v_{\pi}(s) \sum_a \pi(a|s)\left[ \sum_r p(r|s,a)\gamma \sum_{s} p(s|s,a) v_{\pi}(s) \right] vπ(s)a∑π(a∣s)[r∑p(r∣s,a)γs′∑p(s′∣s,a)vπ(s′)] 将贝尔曼方程改写为括号外的项往括号里面分配 v π ( s ) γ π ( s ) γ ∑ s ′ p π ( s ′ ∣ s ) v π ( s ′ ) v_{\pi}(s) \gamma_{\pi}(s)\gamma \sum_{s} p_{\pi}(s|s)v_{\pi}(s) vπ(s)γπ(s)γs′∑pπ(s′∣s)vπ(s′) 其中 r π ( s ) r_{\pi}(s) rπ(s) 代表从当前状态出发我所能得到的即时奖励immediate reward的平均值这个式子其实与推导贝尔曼公式的时候计算第一项和第二项的时候写的中间过程的公式是一样的是即时奖励加未来奖励从当前 s s s 出发有多个选择可以跳到不同 s ′ s s′ 跳到不同 s ′ s s′ 的概率是 p ( s ′ ∣ s ) p(s | s) p(s′∣s)
假设状态states可以索引为 s i ( i 1 , . . . , n ) s_i (i 1, ... , n) si(i1,...,n)。
对于状态 s i s_i si贝尔曼方程为从 s i s_i si 跳到 s j s_j sj 的概率是 p π ( s j ∣ s i ) p_{\pi}(s_j|s_i) pπ(sj∣si)从 s i s_i si 跳到 s j s_j sj 所取的 state value 是 v π ( s j ) v_{\pi}(s_j) vπ(sj) v π ( s ) γ π ( s ) γ ∑ s j p π ( s j ∣ s i ) v π ( s j ) v_{\pi}(s) \gamma_{\pi}(s)\gamma \sum_{s_j} p_{\pi}(s_j|s_i)v_{\pi}(s_j) vπ(s)γπ(s)γsj∑pπ(sj∣si)vπ(sj) 将所有这些状态方程放在一起改写成矩阵向量形式 v π v_{\pi} vπ 是一个向量 v π ( s ) γ π ( s ) γ P π v π v_{\pi}(s) \gamma_{\pi}(s)\gamma P_{\pi}v_{\pi} vπ(s)γπ(s)γPπvπ 其中 P π P_{\pi} Pπ 是状态转换矩阵state transition matrix p π ( s j ∣ s i ) p_{\pi}(s_j|s_i) pπ(sj∣si) 意思是状态从 s i s_i si 跳到 s j s_j sj 的概率
代表第 i i i行第 j j j列的元素从 s i s_i si 跳到 s j s_j sj 的这样一个概率
2. 例子
1例子1
有四个状态即 n 4 的时候的矩阵向量形式 考虑下图策略policy用绿色的箭头表示
2例子2 六.贝尔曼公式 Bellman equation求解状态值state value
1.求解
用刚才推导的贝尔曼公式的矩阵和向量的形式求解状态值state value
为什么要求解状态值state value
给定一个策略policy我们会列出来它的贝尔曼公式 Bellman equation再进一步求解这个贝尔曼公式得到状态值state value求出相应的状态值这样的一个过程state value称为策略评估policy evaluation这是 RL 中的一个基本问题。它是找到更好策略的基础。策略评估policy evaluation是强化学习中的关键因为只有能够去评价一个策略好或者不好我们才能进一步改进它最后再找到最优的策略。
矩阵向量形式的贝尔曼方程为 v π v_π vπ 是一个向量 v π r π γ P π v π v_{\pi} r_{\pi} \gamma P_{\pi}v_{\pi} vπrπγPπvπ 下面给出两种求解贝尔曼公式的方法
1闭式解为The closed-form solution is即状态值state value的解析表达式为 v π ( I − γ P π ) − 1 r π v_{\pi} (I - \gamma P_{\pi})^{-1}r_{\pi} vπ(I−γPπ)−1rπ 实际上我们仍然需要使用数值工具来计算矩阵逆实际中并不会使用。我们能避免矩阵逆运算吗可以通过迭代算法iterative algorithms。
2迭代解决iterative solution方案是 v k v_k vk 和 v k 1 v_{k1} vk1 都是向量包含了不同时刻的所有状态值 v k 1 r π γ P π v k v_{k1} r_{\pi}\gamma P_{\pi}v_k vk1rπγPπvk 首先可以随便猜一个 v 0 v_0 v0 等于什么比如全为0然后带入到等式右边得到等式左边的 v 1 v_1 v1 然后把 v 1 v_1 v1 再带到等式右边得到等式左边的 v 2 v_2 v2 然后把 v 2 v_2 v2 再带到等式右边得到等式左边的 v 3 v_3 v3如此循环计算下去就会得到一个序列 { v 0 , v 1 , v 2 , } \{v0, v1, v2,\} {v0,v1,v2,}。我们可以证明当 k k k 趋向于 ∞ ∞ ∞的时候 v k v_k vk 就收敛到了 v π v_{\pi} vπ这个 v π v_{\pi} vπ 就是真实的状态值state value v k → v π ( I − γ P π ) − 1 r π , k → ∞ v_k \rightarrow v_{\pi} (I- \gamma P_{\pi})^{-1}r_{\pi}, \ \ \ \ k \rightarrow \infty vk→vπ(I−γPπ)−1rπ, k→∞ 证明 2.例子 r b o u n d a r y r f o r b i d d e n − 1 , r t a r g e t 1 , γ 0.9 r_{boundary} r_{forbidden} -1, r_{target} 1,\gamma 0.9 rboundaryrforbidden−1,rtarget1,γ0.9
以下是两项 好 的策略绿色箭头是策略和状态值state value。在第四列中前两个状态的两项策略是不同的。 用刚才讲的解析表达式或者迭代算法都可以求出状态值state value。
可以看出状态值state value全为正数。
靠近目标 target area 的状态值state value都比较大距离目标 target area 越远它的状态值state value越小。
以下是两项 不好的策略绿色箭头是策略和状态值state value。状态值state value比好策略的状态值小。 上面两个策略很明显会撞墙或进入禁区从直觉上讲这是不好的策略
而计算出的状态值state value有负数通过状态值state value也可以判断出这是不好的策略这与我们的直觉一致。 可以看出我们可以通过计算状态值state value来评价一个策略policy的好坏 七.动作值action value
从状态值state value到动作值action value
状态值state valueagent智能体从某一状态state开始所能获得的平均回报average return。动作值action valueagent智能体从某一状态state出发并采取某项动作taking an action之后所能获得的平均回报average return。
我们为什么关心动作值action value
策略指的是在一个状态我要选择什么样的 action有一些 action 我们如何做选择呢就要根据 action value 来做判断action value 大的意味着我选择那个 action 会得到更多的 reward那我就会去选择那个。因为我们想知道哪个动作更好。这一点在下面的讲解中会更加清楚。我们将经常使用动作值。
1.动作值定义
动作值定义我们从当前状态 s 出发选择动作 a 之后我所得到的回报return的一个平均average就是动作值action value q π ( s , a ) E [ G t ∣ S t s , A t a ] q_{\pi}(s,a) \mathbb{E}[G_t|S_ts,A_ta] qπ(s,a)E[Gt∣Sts,Ata] q π ( s , a ) q_{\pi}(s,a) qπ(s,a)是状态-动作对 ( s , a ) (s,a) (s,a)的函数依赖于从哪个状态出发从哪个状态的 action 出发。 q π ( s , a ) q_{\pi}(s,a) qπ(s,a)依赖于 π \pi π不同的策略会得到不同的 action value
不确定对确定了action的话reward不也是确定的吗为啥还要求期望
确定了actionaction的reward确定但结果状态不确定所以期望是给结果状态 v ( s ′ ) v(s) v(s′)的就比如之前老师讲的被风吹歪的例子现态采取同个策略可能会掉到不同的次态
2.动作值与状态值的联系
根据条件期望的性质可以得出等式右边意思是我有很多个 a a a我选择一个 a a a 的概率是 π ( a ∣ s ) \pi(a | s) π(a∣s)选择 a a a 后所得到的 average return 是 q π ( s , a ) q_{\pi}(s,a) qπ(s,a) 因此 v π ( s ) ∑ a π ( a ∣ s ) q π ( s , a ) ( 2 ) {\color{red}v_{\pi}(s)} \sum_a \pi(a|s) {\color{red}q_{\pi}(s,a)} \quad \quad \quad (2) vπ(s)a∑π(a∣s)qπ(s,a)(2) 等式左边是从一个状态出发的 state value 等于右边我选择不同 action 得到的 action value 的平均值权重就是策略 π \pi π。 action value其实可以理解为state value的一个action下的值 回想一下状态值state value由以下公式给出 比较 (2) 和 (3)我们可以得出动作值函数action-value function的表达式为 (2) 和 (4) 是一枚硬币的两面
(2) 说明了如何从动作值action value中获取状态值state value。(4) 则说明了如何从状态值state value中获取动作值action value。 在概率论范畴下研究对象都是随机变量是没有常规意义的平均的。所说的平均都是概率意义平均即期望。 3.例子 写出状态 s 1 s_1 s1 的动作值 q π ( s 1 , a 2 ) − 1 γ v π ( s 2 ) q_{\pi}(s_1,a_2) -1\gamma v_{\pi}(s_2) qπ(s1,a2)−1γvπ(s2) 问题下面这些不等于0 q π ( s 1 , a 2 ) , q π ( s 1 , a 3 ) , q π ( s 1 , a 4 ) , q π ( s 1 , a 5 ) ? B e c a r e f u l ! ! q_{\pi}(s_1,a_2),q_{\pi}(s_1,a_3),q_{\pi}(s_1,a_4),q_{\pi}(s_1,a_5)? \ Be careful \ !! qπ(s1,a2),qπ(s1,a3),qπ(s1,a4),qπ(s1,a5)? Becareful !! 至于其他动作所有的 action 都可以计算 q π ( s 1 , a 2 ) − 1 γ v π ( s 2 ) q π ( s 1 , a 3 ) 0 γ v π ( s 3 ) q π ( s 1 , a 4 ) − 1 γ v π ( s 1 ) q π ( s 1 , a 5 ) 0 γ v π ( s 2 1 \begin{align} q_{\pi}(s_1,a_2) -1\gamma v_{\pi}(s_2) \\ q_{\pi}(s_1,a_3) 0\gamma v_{\pi}(s_3) \\ q_{\pi}(s_1,a_4) -1\gamma v_{\pi}(s_1) \\ q_{\pi}(s_1,a_5) 0\gamma v_{\pi}(s_21 \\ \end{align} qπ(s1,a2)qπ(s1,a3)qπ(s1,a4)qπ(s1,a5)−1γvπ(s2)0γvπ(s3)−1γvπ(s1)0γvπ(s21 强调
动作值action value很重要因为我们未来会关注在某个状态它不同的 action 它们之间会相互比较我们会选一个动作值action value最大的那个。因为我们关心的是采取哪种动作。我们可以先求解贝尔曼公式计算所有状态值state value然后再计算动作值action value。我们也可以不计算状态值state value使用或不使用模型直接计算动作值action value。
八.总结
