赞
踩
【强化学习的数学原理-赵世钰】课程笔记(四)值迭代与策略迭代
本节课讲的是 model base 的算法,下节课将会介绍 model-free 算法。值迭代和策略迭代和截断策略迭代都是求解最优状态值和最优策略的办法
值迭代算法和策略算法是截断策略迭代算法的极端情况
这是上一节课由收缩映射定理(Contraction mapping theorem)给出的一个算法,这节课给它一个名字,给它两个步骤,正式的介绍出来:
贝尔曼最优公式(矩阵向量形式):
v
=
f
(
v
)
=
max
π
(
r
π
+
γ
P
π
v
)
v = f(v) = \max \limits_{\pi}(r_{\pi} + \gamma P_{\pi} v)
v=f(v)=πmax(rπ+γPπv)
如何求解贝尔曼最优公式? 在上一讲中,我们知道收缩映射定理提出了一种迭代算法:只要用下面这个算法就可以求出它的最优策略(optimal policy)和最优的状态值(optimal state value)
v
k
+
1
=
f
(
v
k
)
=
max
π
(
r
π
+
γ
P
π
v
k
)
,
k
=
1
,
2
,
3
…
v_{k+1} = f(v_k) = \max \limits_{\pi}(r_{\pi} + \gamma P_{\pi} v_k), \qquad k = 1,2,3 \dots
vk+1=f(vk)=πmax(rπ+γPπvk),k=1,2,3…
其中
v
0
v_0
v0 可以是任意值。
算法的矩阵向量形式如下:
v
k
+
1
=
f
(
v
k
)
=
max
π
(
r
π
+
γ
P
π
v
k
)
,
k
=
1
,
2
,
3
…
v_{k+1} = f(v_k) = \max \limits_{\pi}(r_{\pi} + \gamma P_{\pi} v_k), \qquad k = 1,2,3 \dots
vk+1=f(vk)=πmax(rπ+γPπvk),k=1,2,3…
可以分解为(be decomposed)两个步骤:
其中 v k v_k vk 是给定的。
问题: v k v_k vk 是状态值(state value)吗?
不是,因为不能确保 v k v_k vk 满足贝尔曼方程。如果上式中,左边是 v k v_k vk,那它确实是一个贝尔曼公式,那么 v k v_k vk 就是一个状态值(state value),但是左边并不是 v k v_k vk,而是 v k + 1 v_{k+1} vk+1。所以这里的 v k v_k vk 就是一个向量,就是一个值,可以是任意的值,并不是状态值(state value)
理解:
接下来,我们需要研究元素形式(elementwise form),以便实现算法。
对每一个 s,一开始有个
v
k
(
s
)
v_k(s)
vk(s),
v
k
v_k
vk 最开始可以从
v
0
v_0
v0 或者
v
1
v_1
v1 开始——>从
v
k
v_k
vk 可以计算得到
q
k
q_k
qk——>得到
q
k
q_k
qk 后我知道哪个
q
k
q_k
qk 是最大的,然后知道它对应的 action 是什么,就可以得到贪婪策略(greedy policy)
π
k
+
1
πk+1
πk+1——>然后得到
v
k
+
1
v_{k+1}
vk+1,
v
k
+
1
v_{k+1}
vk+1就对应最大的
q
k
q_k
qk
这个过程可以写成下面的伪代码:
用值迭代算法(value iteration algorithm)为下面的 a 图求解出一个最优的策略,图 b,c 是我们在使用算法进行迭代的过程中,每次我们都会得到一个策略 π k + 1 \pi_{k+1} πk+1,图 b,c 就是得到的策略 π k + 1 \pi_{k+1} πk+1,把它画在图中。
q 表(q-table): q ( s , a ) q(s,a) q(s,a) 的表达式(当给出 v v v 的时候,能求出 q q q)
k = 0 k=0 k=0,先选取 v 0 v_0 v0,可以任意选取,简单起见全选0,然后把 v 0 v_0 v0 带入刚才的 q-table 当中去:
先进行策略更新,针对每一个状态,我们去看哪个 q k q_k qk 是最大的,那么它对应的新的策略就可以求出。对 s 1 s_1 s1 而言,选取动作 a 3 a_3 a3 和 a 5 a_5 a5 对应的 q q q 最大,所以 policy 可以在最大的 q q q 里面随便选一个(第 k k k 步是对所有 s s s 进行更新)
再进行价值更新,上面选出的最大的 q k q_k qk,作为新的 v 1 v_1 v1 进行下一步的使用
这个策略绘制出图片就是上面的 b 图,可以看出在 s 2 s_2 s2 , s 3 s_3 s3 和 s 4 s_4 s4 上都已经达到了最优,可以到达目标。但是在 s 1 s_1 s1 上还没有达到最优,因为当前策略是原地不动,但是最优策略需要到达目标。再进行下一步迭代:
k = 1 k=1 k=1,把上次迭代得到的 v 1 v_1 v1 带入刚才的 q-table 当中去:
这个策略绘制出图片就是上面的 c 图,可以看出在 s 1 , s 2 , s 3 和 s 4 s_1,s_2 ,s_3 和 s_4 s1,s2,s3和s4 上都已经达到了最优,可以到达目标,已经求出来了最优策略。还可以进行下一步迭代,直到达到迭代终止条件:
这是这节课新介绍的一个算法,下节课会在这个算法的基础上,得到一个 model free 的 reinforcement learning 的算法
算法描述:
给定随机初始策略 π 0 π_0 π0(任意给定,可能是不好的策略,之后会迭代找到好的策略)
每次迭代分为两个步骤:
之前提过,policy evaluation 就是我给定一个策略 π k π_k πk(最开始是 π 0 π_0 π0),可以求解它对应的贝尔曼公式,得到 π k π_k πk 对应的 state value v π k v_{π_k} vπk,这样的过程就叫策略评估(policy evaluation)
上一步求出来了 v π k v_{π_k} vπk,我求解优化问题得到一个新的策略 π k + 1 π_{k+1} πk+1, π k + 1 π_{k+1} πk+1 比 π k π_k πk 更好
最大化是分量式的!
理解:
该算法可以得到一个序列,用下面的过程来表示:最开始猜的 π 0 π_0 π0 肯定是不好的,然后我做 policy evaluation 得到 v π 0 v_{π_0} vπ0,然后做 policy improvement 得到 π 1 π_1 π1…
问题
问题 1: 在策略评估(policy evaluation)步骤中,如何通过求解贝尔曼方程得到状态值(state value) v π k v_{π_k} vπk?
假设给定一个策略(policy)
π
k
π_k
πk,我们可以列出来它的贝尔曼公式( Bellman equation)如下:
v
π
k
=
r
π
k
+
γ
P
π
k
v
π
k
v_{\pi_k} = r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}
vπk=rπk+γPπkvπk
有两种方法可以求解这个贝尔曼公式得到状态值(state value):
(1)闭式解为(The closed-form solution is),即状态值(state value)的解析表达式为:
v
π
k
=
(
I
−
γ
P
π
k
)
−
1
r
π
k
v_{\pi_k} = (I - \gamma P_{\pi_k})^{-1}r_{\pi_k}
vπk=(I−γPπk)−1rπk
这个方法我们不太用,因为要求逆矩阵,经常用的是下面的方法
(2)迭代解决(iterative solution)方案是:(
v
π
k
v_{π_k}
vπk 和
v
π
k
+
1
v_{π_{k+1}}
vπk+1 都是向量,包含了不同时刻的所有状态值)最开始对
v
π
k
v_{π_k}
vπk 有一个猜测,不断迭代就可以得到
v
π
k
v_{π_k}
vπk
v
π
k
(
j
+
1
)
=
r
π
k
+
γ
P
π
k
v
π
k
j
,
j
=
0
,
1
,
2
,
…
v_{\pi_k}^{(j+1)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{j}, \qquad j = 0,1,2,\dots
vπk(j+1)=rπk+γPπkvπkj,j=0,1,2,…
问题 2: 在策略改进(policy improvement)步骤中,为什么新策略 π k + 1 π_{k+1} πk+1 比 π k π_k πk 更好?
π k + 1 π_{k+1} πk+1 是求解下面这个( v π k v_{π_k} vπk给定的)式子所得到的,可以证明 v π k + 1 v_{π_{k+1}} vπk+1 一定大于等于 v π k v_{π_k} vπk,所以 π k + 1 π_{k+1} πk+1 比 π k π_k πk 更好
问题 3: 为什么这种迭代算法能最终找到最优的策略?
由于每次迭代都会改进策略,我们知道:最优的状态值(state value)是
v
∗
v^*
v∗
v
π
0
≤
v
π
1
≤
v
π
2
≤
⋯
≤
v
π
k
≤
⋯
≤
v
∗
v_{\pi_0} \le v_{\pi_1} \le v_{\pi_2} \le \dots \le v_{\pi_k} \le \dots \le v^*
vπ0≤vπ1≤vπ2≤⋯≤vπk≤⋯≤v∗
因此,
v
π
k
v_{π_k}
vπk 会不断增加并收敛(keeps increasing and will converge)。仍需证明它收敛于 v*:
问题 4: 这种策略迭代算法(policy iteration algorithm)与前一种值迭代算法(value iteration algorithm)之间的关系是什么?
问题 3 给出的那个定理的证明(就是上面那个定理),即若要证明 policy iteration 的算法是收敛的,实际上用到了 value iteration 算法是收敛的这样的一个结果,所以它是基于 value iteration 算法的一个结果。
另外 policy iteration 和 value iteration 实际上是两个极端,是一个更 general 的截断策略迭代算法(Truncated policy iteration algorithm)的两个极端,稍后会介绍。
为了实现,我们要研究它的元素形式(Elementwise form)
步骤 1:策略评估(PE)(Step 1: policy evaluation (PE))
步骤 2:策略改进 (PI)(Step 2: policy improvement (PI))
流程伪代码:
值迭代和策略迭代的区别:
图 b 是最优策略,在 s1 的时候往右走,在 s2 的时候静止不动。图 a 是初始策略,都往左走是不合适的,我们用 policy iteration 的算法得到图 b 这样一个最优策略
k=0
该例子比较简单,该策略在一次迭代后达到最优!在您的程序设计中,应该继续运行,直到满足停止标准为止。
现在你知道了另一种搜索最优策略(optimal policies)的强大算法!现在,让我们应用它,看看能发现什么。
例子的基本设置:
现在要做的是对这样一个 5×5 的网格,求一个最优策略。下面这些图画的是,我从最开始随便给定的一个策略 π 0 π_0 π0,求出 v π 0 v_{π_0} vπ0,policy improvement 得到 π 0 π_0 π0,然后policy evaluation 得到 v π 1 v_{π_1} vπ1,一直下去直到得到 π 10 π_{10} π10 和 v π 10 v_{π_{10}} vπ10
让我们来看看中间策略和状态值。
策略和状态值的有趣模式
这是前两个值迭代算法(value iteration algorithm)和策略迭代算法(policy iteration algorithm)的一般化推广;值迭代算法(value iteration algorithm)和策略迭代算法(policy iteration algorithm)是截断策略迭代算法(Truncated policy iteration algorithm)的特殊情况
针对Policy iteration ,它是从一个初始的策略 π 0 \pi_0 π0 出发,这个策略可能是非常不好的,任意猜测的这样一个策略,然后在第 k 个 iteration 当中,它包含两个步骤:
针对Value iteration ,它不是从一个初始的策略 π 0 \pi_0 π0 出发 ,它是从一个值 v 0 v_0 v0 出发,这个值 v 0 v_0 v0 可以是任意的一个值,然后通过值迭代算法它最后能收敛到 v ∗ v^* v∗ (最优状态值:Optimal state value),然后在第 k 个 iteration 当中,它包含两个步骤:
这两种算法非常相似:
理解:
让我们仔细比较一下这些步骤:
理解:
伪代码:
收敛的意思就是,收敛到一个怎么迭代都不太会改变的值
因为没有计算无穷多步,所以此时的 v k ≠ v π k v_k \ne v_{\pi_k} vk=vπk,那么此时的截断是否会带来一些问题呢?比如是否会使整个算法不再收敛?
截断是否会削弱收敛性?下面给出一个定理:
考虑Policy iteration在策略评估步骤(PE)求解贝尔曼公式时的迭代算法
如果这个迭代算法的初始值比较特殊如 v π k − 1 v_{\pi_{k-1}} vπk−1,可以证明在这个迭代算法中, v π k + 1 v_{\pi_{k+1}} vπk+1 一定是 比 v π k v_{\pi_k} vπk 大的,所以计算1 次也会增大,计算 j 次也会增大,计算 ∞ \infty ∞ 也会增大 ( ∞ \infty ∞ 次 代价太大,用有限步即可)
刚才这个结果可以通过下图比较好的展示出来,这个图的横轴是 k k k,即 policy iteration 算法中的迭代次数 iteration 的索引(index) ,纵轴是值,简单起见,state value 只有一维。红线 v ∗ v^* v∗ 代表最优状态值(optimal state value),其他曲线是上面三种算法,通过迭代都最终收敛到 v ∗ v^* v∗
PI 的收敛证明基于 VI 的收敛证明。既然 VI 收敛,我们就知道 PI 收敛。
例子:
设置: 与上一示例相同。以下是初始策略,目标是找一个最优策略
结论:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。