根据策略评估阶段得到的策略
π
\pi
π下的行为值函数
Q
(
s
,
a
)
Q(s,a)
Q(s,a)，使用贪心算法改进策略的过程.
2. 基于贪心算法的策略改进的基本描述
不考虑数值计算误差的贪心算法
{
a
m
a
x
=
arg?max
?
a
∈
A
(
Q
(
s
,
a
)
)
π
(
a
∣
s
)
=
{
1
a
=
a
m
a
x
0
a
≠
a
m
a
x
s
∈
S
\begin{cases} a_{max} = \argmax_{a\in A}\left(Q(s,a) \right)\\ \pi(a|s) = \begin{cases} 1\qquad a=a_{max}\\ 0\qquad a\ne a_{max} \end{cases} \end{cases}\qquad s\in S
????amax?=argmaxa∈A?(Q(s,a))π(a∣s)={1a=amax?0a=amax???s∈S 不考虑数值计算误差的贪心算法，求得的最优行为只有1个(
a
m
a
x
a_{max}
amax?)，实际中，可能有两个不同的a的值，都使得Q(s,a)取最大值，甚至由于计算误差，原本有两个最优a，最后变成了一个，这可能会导致最优动作的选取不全面。
考虑数值计算误差的贪心算法
这一算法考虑了数值计算误差
设定一个较小的数值计算误差阈值
?
>
0
\epsilon>0
?>0
则：
a
=
b
?
∣
a
?
b
∣
<
?
a=b\Leftrightarrow |a-b|<\epsilon
a=b?∣a?b∣<?
则实际编程中按如下表达式更新策略
{
Q
m
a
x
(
s
)
=
max
?
a
∈
A
Q
(
s
,
a
)
A
m
a
x
(
s
)
=
{
a
∣
a
∈
A
且
Q
m
a
x
?
Q
(
s
,
a
)
<
?
}
π
?
(
a
∣
s
)
=
{
1
/
l
e
n
g
t
h
(
A
m
a
x
(
s
)
)
a
∈
A
m
a
x
(
s
)
0
a
?
A
m
a
x
(
s
)
s
∈
S
\begin{cases} Q_{max}(s)&=\max_{a\in A} Q(s,a)\\ A_{max}(s)&=\{a|a\in A且Q_{max}-Q(s,a)<\epsilon \}\\ \pi^*(a|s)&=\begin{cases} 1/\mathrm{length}\left(A_{max}(s)\right) \quad a\in A_{max}(s)\\ 0 \qquad a\notin A_{max}(s) \end{cases} \end{cases}\qquad s\in S
????Qmax?(s)Amax?(s)π?(a∣s)?=maxa∈A?Q(s,a)={a∣a∈A且Qmax??Q(s,a)<?}={1/length(Amax?(s))a∈Amax?(s)0a∈/Amax?(s)??s∈S
输入：
?
\epsilon
?，策略
π
(
a
∣
s
)
\pi(a|s)
π(a∣s)，行为值函数
Q
(
s
,
a
)
Q(s,a)
Q(s,a)
输出：更新后的策略
π
(
a
∣
s
)
\pi(a|s)
π(a∣s)
过程：
f
o
r
s
i
n
S
:
a
m
a
x
=
arg?max
?
a
∈
A
(
Q
(
s
,
a
)
)
f
o
r
a
i
n
A
:
π
(
a
∣
s
)
=
?
n
A
i
f
a
=
a
m
a
x
:
π
(
a
∣
s
)
=
π
(
a
∣
s
)
+
(
1
?
?
)
\begin{align*} &for \quad s \quad in \quad S:\\ &\qquad a_{max}=\argmax_{a\in A}(Q(s,a))\\ &\qquad for \quad a \quad in \quad A:\\ &\qquad\qquad \pi(a|s)=\frac{\epsilon}{nA}\\ &\qquad\qquad if \quad a=a_{max}:\\ &\qquad\qquad\qquad \pi(a|s)=\pi(a|s)+(1-\epsilon) \end{align*}
?forsinS:amax?=a∈Aargmax?(Q(s,a))forainA:π(a∣s)=nA??ifa=amax?:π(a∣s)=π(a∣s)+(1??)? 注：这里采用了不考虑计算误差的贪心策略，也可以考虑使用带计算误差的贪心策略。具体请读者实践。