动态规划求解强化学习任务——使用策略改进定理迭代求解策略π
- 目录
- 回顾
- 策略改进定理
- 贝尔曼最优方程
- 迭代求解过程
- 总结和答疑
目录
上一节介绍了策略改进定理的推导过程，本节使用策略改进定理介绍迭代求解策略 π \pi π的算法过程。
回顾
策略改进定理
为了避免在每次迭代过程中都计算关于
π
\pi
π和
π
′
\pi'
π′的最优价值函数——介绍了策略改进定理：
假设从新的策略中产生的动作记作
π
′
(
s
)
\pi'(s)
π′(s)，
∀
s
∈
S
\forall s \in \mathcal S
∀s∈S，若满足：
V
π
(
s
)
≤
q
π
(
s
,
π
′
(
s
)
)
V_\pi(s) \leq q_\pi(s,\pi'(s))
Vπ(s)≤qπ(s,π′(s))
那么则有：
∀
s
∈
S
,
V
π
(
s
)
≤
V
π
′
(
s
)
\forall s \in \mathcal S,V_\pi(s) \leq V_{\pi'}(s)
∀s∈S,Vπ(s)≤Vπ′(s)
贝尔曼最优方程
在贝尔曼最优方程的介绍中，我们提到
V
π
(
s
)
V_\pi(s)
Vπ(s)可以理解成 满足
a
∈
A
(
s
)
a \in \mathcal A(s)
a∈A(s)的动作
a
a
a对应状态-动作价值函数
q
π
(
s
,
a
)
q_\pi(s,a)
qπ(s,a)的加权平均；
并且介绍了期望(加权平均)值与最大值之间的关系
→
\to
→ 我们得到如下结果：
V
π
(
s
)
≤
max
a
q
π
(
s
,
a
)
V_\pi(s) \leq \mathop{\max}\limits_{a}q_\pi(s,a)
Vπ(s)≤amaxqπ(s,a)
与此同时还介绍了基于贪心算法(Greedy Policy)得到的最优策略内部权重分布：
也就是说，基于贪心算法产生的策略必然将所有权重分配给使价值函数产生最大结果对应的动作。
π
∗
(
a
∣
s
)
=
{
1
i
f
a
=
arg
max
a
∈
A
q
π
∗
(
s
,
a
)
0
e
l
s
e
\pi_*(a \mid s) = \left\{ \begin{array}{ll} 1\quad if \quad a= \mathop{\arg\max}\limits_{a \in \mathcal A}q_{\pi^*}(s,a)\\ 0\quad else \end{array} \right.
π∗(a∣s)={1ifa=a∈Aargmaxqπ∗(s,a)0else
迭代求解过程
基于策略改进定理，我们尝试对策略改进过程进行设计：
-
假设给定了当前策略 π \pi π,通过策略评估计算当前策略的状态动作价值函数 q π ( s , a ) q_\pi(s,a) qπ(s,a)，在状态 s s s给定的条件下， q π ( s , a ) q_\pi(s,a) qπ(s,a)可看作成向量形式。设 A ( s ) = { a 1 , a 2 , a 3 , . . . , a n } \mathcal A(s) =\{a_1,a_2,a_3,...,a_n\} A(s)={a1,a2,a3,...,an}是 s s s状态下有意义的动作集合，数学表达如下：
q π ( s , a ) = ( q π ( s , a 1 ) q π ( s , a 2 ) q π ( s , a 3 ) . . . q π ( s , a n ) ) ( a 1 , a 2 , a 3 , . . . , a n ∈ A ( s ) ) q_\pi(s,a) = \begin{pmatrix} q_\pi(s,a_1) \\ q_\pi(s,a_2) \\ q_\pi(s,a_3)\\ ...\\ q_\pi(s,a_n) \end{pmatrix}(a_1,a_2,a_3,...,a_n \in \mathcal A(s)) qπ(s,a)=⎝⎜⎜⎜⎜⎛qπ(s,a1)qπ(s,a2)qπ(s,a3)...qπ(s,an)⎠⎟⎟⎟⎟⎞(a1,a2,a3,...,an∈A(s)) -
从上述 q π ( s , a ) q_\pi(s,a) qπ(s,a)各元素中选择一个最大值，该值对应的动作我们称它为贪心策略下的最优策略，记做 π ′ ( s ) \pi'(s) π′(s)。
π ′ ( s ) = arg max a ∈ A ( s ) q π ( s , a ) \pi'(s) = \mathop{\arg\max}\limits_{a \in \mathcal A(s)} q_\pi(s,a) π′(s)=a∈A(s)argmaxqπ(s,a)
它同样可以理解成：
q π ( s , π ′ ( s ) ) = max a ∈ A ( s ) q π ( s , a ) = q ∗ ( s , a ) q_\pi(s,\pi'(s)) = \mathop{\max}\limits_{a \in \mathcal A(s)}q_\pi(s,a) = q_*(s,a) qπ(s,π′(s))=a∈A(s)maxqπ(s,a)=q∗(s,a)
是的，你没有看错，这个动作就是策略，它的策略概率分布和上述贝尔曼最优方程介绍的一样，将全部权重分配给该动作，其余动作分配权重均为0 -
根据上述步骤，我们得到了一个新的策略 π ′ ( s ) \pi'(s) π′(s)。已知了策略 π \pi π和 π ′ \pi' π′，要如何比较哪个策略更优：回到本节回顾部分 → \to → 使用策略改进定理对策略优劣的比较过程进行优化。
继续观察：这个特殊的策略 π ′ ( s ) \pi'(s) π′(s)是否满足策略改进定理呢？即：
V π ( s ) ≤ q π ( s , π ′ ( s ) ) V_\pi(s) \leq q_\pi(s,\pi'(s)) Vπ(s)≤qπ(s,π′(s))
答案是肯定的。简单推导：
根据 π ′ ( s ) \pi'(s) π′(s)产生定义，可以得到：
q π ( s , π ′ ( s ) ) = max a q π ( s , a ) q_\pi(s,\pi'(s)) = \mathop{\max}\limits_{a}q_\pi(s,a) qπ(s,π′(s))=amaxqπ(s,a)
在上面贝尔曼最优方程回顾部分，我们得到最大值和期望(加权平均)值之间的关系：
V π ( s ) ≤ max a q π ( s , a ) V_\pi(s) \leq \mathop{\max}\limits_{a}q_\pi(s,a) Vπ(s)≤amaxqπ(s,a)
因此：
V π ( s ) ≤ q π ( s , π ′ ( s ) ) V_\pi(s) \leq q_\pi(s,\pi'(s)) Vπ(s)≤qπ(s,π′(s)) -
根据策略改进定理 → \to → 验证了我们通过贪心算法产生的策略 π ′ ( s ) \pi'(s) π′(s)是更优的(至少不亚于策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s))：
∀ s ∈ S , V π ( s ) ≤ V π ′ ( s ) \forall s \in \mathcal S, V_{\pi}(s) \leq V_{\pi'}(s) ∀s∈S,Vπ(s)≤Vπ′(s)
终上，我们对上述迭代步骤进行归纳整理：
- 给定策略 π → \pi \to π→ 计算 q π ( s , a ) q_\pi(s,a) qπ(s,a);
- 使用贪心算法找出最优策略 π ′ ( s ) \pi'(s) π′(s),并重新执行步骤1的操作；
策略优化部分已经结束，我们具体达到什么样的情况就可以 认定策略
π
\pi
π是最优策略
→
\to
→ 停止迭代 呢？
仔细观察，上述步骤还有一个情况没有讨论，即：
V
π
(
s
)
=
V
π
′
(
s
)
V_\pi(s) = V_{\pi'}(s)
Vπ(s)=Vπ′(s)
如果在迭代过程中出现这种情况
→
\to
→ 策略
π
′
\pi'
π′没有办法更优了，此时的
π
,
π
′
\pi,\pi'
π,π′都已经达到了最优状态。即：
V
π
(
s
)
=
V
π
′
(
s
)
=
V
∗
(
s
)
V_\pi(s) = V_{\pi'}(s) = V_*(s)
Vπ(s)=Vπ′(s)=V∗(s)
其中
V
∗
(
s
)
V_*(s)
V∗(s)表示关于状态
s
s
s的最优价值函数(详见贝尔曼最优方程)。
注意：这里并没有说策略
π
,
π
′
\pi,\pi'
π,π′是相同的(这种情况只是其中的一种可能)，换句话说，这两种策略使用贪心策略产生的
a
,
a
′
a,a'
a,a′并不一定是相同的，只是说它们对应的价值函数是最优的。
对这个情况进行证明：
求证问题描述：
如果在策略
π
\pi
π迭代过程中产生如下情况：
V
π
(
s
)
=
V
π
′
(
s
)
V_\pi(s) = V_{\pi'}(s)
Vπ(s)=Vπ′(s)
那么则有：
V
π
(
s
)
=
V
π
′
(
s
)
=
V
∗
(
s
)
V_\pi(s) = V_{\pi'}(s) = V_*(s)
Vπ(s)=Vπ′(s)=V∗(s)
证明如下：
根据条件，对等式两侧进行展开：
∑
a
′
∈
A
π
′
(
a
′
∣
s
)
q
π
′
(
s
,
a
′
)
=
∑
a
∈
A
π
(
a
∣
s
)
q
π
(
s
,
a
)
\begin{aligned} \sum_{a' \in \mathcal A}\pi'(a' \mid s)q_{\pi'}(s,a') = \sum_{a \in \mathcal A}\pi(a \mid s)q_\pi(s,a) \\ \end{aligned}
a′∈A∑π′(a′∣s)qπ′(s,a′)=a∈A∑π(a∣s)qπ(s,a)
由于
π
′
(
a
′
∣
s
)
\pi'(a' \mid s)
π′(a′∣s)和
π
(
a
∣
s
)
\pi(a \mid s)
π(a∣s)均通过贪心算法选择出的策略结果
→
\to
→ 两种策略必然满足如下形式：
π
′
(
a
′
∣
s
)
=
{
1
i
f
a
′
=
arg
max
a
′
∈
A
q
π
′
(
s
,
a
′
)
0
e
l
s
e
\pi'(a' \mid s) = \left\{ \begin{array}{ll} 1\quad if \quad a' = \mathop{\arg\max}\limits_{a' \in \mathcal A}q_{\pi'}(s,a')\\ 0\quad else \end{array} \right.
π′(a′∣s)={1ifa′=a′∈Aargmaxqπ′(s,a′)0else
π
(
a
∣
s
)
=
{
1
i
f
a
=
arg
max
a
∈
A
q
π
(
s
,
a
)
0
e
l
s
e
\pi(a \mid s) = \left\{ \begin{array}{ll} 1\quad if \quad a= \mathop{\arg\max}\limits_{a \in \mathcal A}q_{\pi}(s,a)\\ 0\quad else \end{array} \right.
π(a∣s)={1ifa=a∈Aargmaxqπ(s,a)0else
因此，等式左右两侧的展开结果分别
→
\to
→ 只有一个非零结果，其余所有结果均为零值。则有：
max
a
′
q
π
′
(
s
,
a
′
)
=
max
a
q
π
(
s
,
a
)
=
q
π
(
s
,
π
′
(
s
)
)
\mathop{\max}\limits_{a'}q_{\pi'}(s,a') = \mathop{\max}\limits_{a}q_{\pi}(s,a) = q_\pi(s,\pi'(s))
a′maxqπ′(s,a′)=amaxqπ(s,a)=qπ(s,π′(s))
根据上面红色字的说法，并没有说
a
,
a
′
a,a'
a,a′是同一个动作，但是选择这两个动作(姑且认为两种动作是不同的)之后的状态-动作价值函数都指向了相同的结果
→
\to
→ 当前迭代步骤的最优状态-动作价值函数。则有：
i
f
V
π
(
s
)
=
V
π
′
(
s
)
→
q
π
′
(
s
,
a
′
)
=
q
π
(
s
,
a
)
if \quad V_\pi(s) = V_{\pi'}(s) \to q_{\pi'}(s,a') = q_{\pi}(s,a)
ifVπ(s)=Vπ′(s)→qπ′(s,a′)=qπ(s,a)
继续推导，对
V
π
′
(
s
)
V_{\pi'}(s)
Vπ′(s)重新展开,并使用
q
π
(
s
,
a
)
q_{\pi}(s,a)
qπ(s,a)对
q
π
′
(
s
,
a
′
)
q_{\pi'}(s,a')
qπ′(s,a′)进行替换：
∀
s
∈
S
,
V
π
′
(
s
)
=
∑
a
′
∈
A
π
′
(
a
′
∣
s
)
q
π
′
(
s
,
a
′
)
=
∑
a
‘
∈
A
π
′
(
a
′
∣
s
)
q
π
(
s
,
a
)
=
q
π
(
s
,
π
′
(
s
)
)
\begin{aligned} \forall s \in \mathcal S, V_{\pi'}(s) & = \sum_{a' \in \mathcal A}\pi'(a' \mid s)q_{\pi'}(s,a') \\ & = \sum_{a‘ \in \mathcal A}\pi'(a' \mid s)q_\pi(s,a) \\ & = q_\pi(s,\pi'(s)) \\ \end{aligned}
∀s∈S,Vπ′(s)=a′∈A∑π′(a′∣s)qπ′(s,a′)=a‘∈A∑π′(a′∣s)qπ(s,a)=qπ(s,π′(s))
继续对
q
π
(
s
,
π
′
(
s
)
)
q_\pi(s,\pi'(s))
qπ(s,π′(s))进行替换，并将
V
π
(
s
′
)
V_{\pi}(s')
Vπ(s′)替换为
V
π
′
(
s
′
)
V_{\pi'}(s')
Vπ′(s′)(根据条件)：
q
π
(
s
,
π
′
(
s
)
)
=
max
a
q
π
(
s
,
a
)
=
max
a
∑
s
′
,
r
p
(
s
′
,
r
∣
s
,
a
)
[
r
+
γ
V
π
(
s
′
)
]
=
max
a
∑
s
′
,
r
p
(
s
′
,
r
∣
s
,
a
)
[
r
+
γ
V
π
′
(
s
′
)
]
\begin{aligned} q_\pi(s,\pi'(s)) & = \mathop{\max}\limits_{a}q_{\pi}(s,a) \\ & = \mathop{\max}\limits_{a}\sum_{s',r}p(s',r \mid s,a)[r + \gamma V_{\pi}(s')] \\ & = \mathop{\max}\limits_{a}\sum_{s',r}p(s',r \mid s,a)[r + \gamma V_{\pi'}(s')] \end{aligned}
qπ(s,π′(s))=amaxqπ(s,a)=amaxs′,r∑p(s′,r∣s,a)[r+γVπ(s′)]=amaxs′,r∑p(s′,r∣s,a)[r+γVπ′(s′)]
经过整理得到下式，它就是状态价值函数贝尔曼最优方程的标准形式：
V
π
′
(
s
)
=
max
a
∑
s
′
,
r
p
(
s
′
,
r
∣
s
,
a
)
[
r
+
γ
V
π
′
(
s
′
)
]
V
∗
(
s
)
=
max
a
∑
s
′
,
r
p
(
s
′
,
r
∣
s
,
a
)
[
r
+
γ
V
∗
(
s
′
)
]
\begin{aligned} V_{\pi'}(s) = \mathop{\max}\limits_{a}\sum_{s',r}p(s',r \mid s,a)[r + \gamma V_{\pi'}(s')] \\ V_*(s) = \mathop{\max}\limits_{a}\sum_{s',r}p(s',r \mid s,a)[r + \gamma V_*(s')] \end{aligned}
Vπ′(s)=amaxs′,r∑p(s′,r∣s,a)[r+γVπ′(s′)]V∗(s)=amaxs′,r∑p(s′,r∣s,a)[r+γV∗(s′)]
结合条件，则有：
V
π
′
(
s
)
=
V
∗
(
s
)
=
V
π
(
s
)
V_{\pi'}(s) = V_*(s) = V_{\pi}(s)
Vπ′(s)=V∗(s)=Vπ(s)
因此，在迭代过程中满足上述情况，即可停止迭代。
总结和答疑
从整个迭代过程中，由于贪心策略的原因，我们从始至终一直都在计算
q
π
(
s
,
a
)
q_\pi(s,a)
qπ(s,a)。
回顾一下整个迭代流程:
- 在 S t = s S_t = s St=s状态下，我们使用贪心算法(人为指定)初始一个策略 π ( s ) \pi(s) π(s)；(在贪心算法下策略和动作没有区别)
- 基于确定的动作 π ( s ) → \pi(s) \to π(s)→ 计算对应的 q π ( s , π ( s ) ) q_\pi(s,\pi(s)) qπ(s,π(s));
- 针对 q π ( s , π ( s ) ) q_\pi(s,\pi(s)) qπ(s,π(s))产生的向量，选择一个状态-动作价值函数最大对应的动作作为新的策略；
- 重复执行2，3步骤 → \to → 直到 q π ( s , π ( s ) ) q_\pi(s,\pi(s)) qπ(s,π(s))不再变化为止。
有些人可能存在疑问/误区：
如果我们的策略是贪心的
→
\to
→ 只有一个动作被赋予了全部权重，其他动作还能求出状态-动作价值函数吗？
自然是可以的。
示例：
假设
S
t
=
s
S_t=s
St=s状态下存在3种动作：
A
(
s
)
=
{
a
1
,
a
2
,
a
3
}
\mathcal A(s) = \{a_1,a_2,a_3\}
A(s)={a1,a2,a3}
假设初始化策略如下
→
a
3
\to a_3
→a3被赋予了全部权重 ：
π
i
n
i
t
=
(
0
,
0
,
1
)
\pi_{init} = (0,0,1)
πinit=(0,0,1)
观察一下当前策略
π
i
n
i
t
\pi_{init}
πinit的
q
π
i
n
i
t
(
s
,
A
(
s
)
)
q_{\pi_{init}}(s,\mathcal A(s))
qπinit(s,A(s))是什么样子的；
q
π
i
n
i
t
(
s
,
A
(
s
)
)
=
(
q
π
i
n
i
t
(
s
,
a
1
)
q
π
i
n
i
t
(
s
,
a
2
)
q
π
i
n
i
t
(
s
,
a
3
)
)
q_{\pi_{init}}(s,\mathcal A(s)) = \begin{pmatrix} q_{\pi_{init}}(s,a_1) \\ q_{\pi_{init}}(s,a_2) \\ q_{\pi_{init}}(s,a_3) \end{pmatrix}
qπinit(s,A(s))=⎝⎛qπinit(s,a1)qπinit(s,a2)qπinit(s,a3)⎠⎞
由于
a
1
a_1
a1被赋予了权重0
→
\to
→ 观察一下
q
π
i
n
i
t
(
s
,
a
1
)
q_{\pi_{init}}(s,a_1)
qπinit(s,a1)：
q
π
i
n
i
t
(
s
,
a
1
)
=
∑
s
′
,
r
p
(
s
′
,
r
∣
s
,
a
)
[
r
+
γ
V
π
i
n
i
t
(
s
′
)
]
q_{\pi_{init}}(s,a_1) = \sum_{s',r}p(s',r \mid s,a)[r + \gamma V_{\pi_{init}}(s')]
qπinit(s,a1)=s′,r∑p(s′,r∣s,a)[r+γVπinit(s′)]
- 首先动态特性函数只和系统内部相关，并且我们在上一节策略改进定理中提到过策略和奖励之间没有必然联系，因此 p ( s ′ , r ∣ s , a ) p(s',r \mid s,a) p(s′,r∣s,a)和 r r r都是有值的；
-
γ
\gamma
γ是人为设定的
∈
(
0
,
1
)
\in(0,1)
∈(0,1)的常数；
V
π
i
n
i
t
(
s
′
)
V_{\pi_{init}}(s')
Vπinit(s′)是加权结果，在该示例中如下：
V π i n i t ( s ′ ) = ∑ a ∈ A π i n i t ( a ∣ s ′ ) q π i n i t ( s ′ , a ) = 0 + 0 + π i n i t ( a 3 ∣ s ′ ) q π i n i t ( s ′ , a 3 ) \begin{aligned} V_{\pi_{init}}(s') & = \sum_{a \in \mathcal A}\pi_{init}(a \mid s')q_{\pi_{init}}(s',a) \\ & = 0 + 0 + \pi_{init}(a_3 \mid s')q_{\pi_{init}}(s',a_3) \end{aligned} Vπinit(s′)=a∈A∑πinit(a∣s′)qπinit(s′,a)=0+0+πinit(a3∣s′)qπinit(s′,a3)
因此， V π i n i t ( s ′ ) V_{\pi_{init}}(s') Vπinit(s′)也可能是有值的。 - 综上，即便策略中某个动作没有被赋予权重 → \to → 并不影响状态-动作价值函数结果的产生，从而不影响我们对最优状态-动作价值函数的选择；
下一节将介绍动态规划求解强化学习任务最后一个部分——价值迭代(Value Iteration)
相关参考：
P4 强化学习-DP-4-策略改进-贪心策略
强化学习（三）用动态规划（DP）求解
