策略迭代——贝尔曼期望不动点贪心问题
- 贝尔曼期望方程
- 不动点问题引发的策略评估算法
- 确定性策略的策略提升算法
-
- 策略提升定理
- 策略迭代算法
- 代码解析
贝尔曼期望方程
∀
s
∈
S
，
V
π
(
s
)
=
∑
a
∈
A
π
(
a
∣
s
)
(
r
(
s
,
a
)
+
γ
∑
s
′
∈
S
p
(
s
′
∣
s
,
a
)
V
π
(
s
′
)
)
\\forall s\\in S，V^{\\pi}(s)=\\sum_{a\\in A}\\pi(a\\mid s)(r(s,a)+\\gamma \\sum_{s^{'}\\in S}p(s^{'}\\mid s,a)V^{\\pi}(s^{'}))
∀s∈S，Vπ(s)=a∈A∑π(a∣s)(r(s,a)+γs′∈S∑p(s′∣s,a)Vπ(s′))
不动点问题引发的策略评估算法
一、 认出“变换规则” 你仔细看这个公式：它接收一个函数
V
(右侧的
V
π
)
V\\text{(右侧的}V^{\\pi})
V(右侧的Vπ)，乘以转换矩阵
P
(
s
,
a
)
,
s
′
=
p
(
s
′
∣
s
,
a
)
P_{(s,a),s^{'}}=p(s^{'}\\mid s,a)
P(s,a),s′=p(s′∣s,a)，再乘以
γ
\\gamma
γ加上状态s下施加动作a的奖励。最后对动作a求期望得到在策略
π
\\pi
π下的状态s的价值
V
π
(
s
)
V^{\\pi}(s)
Vπ(s)。由于这种变换对所有状态s都成立，则综上所述，贝尔曼期望可以视为
V
→
V
V\\rightarrow V
V→V的变换。
二、 给变换命名 我们给这个特定的变换规则取个名字，就叫贝尔曼算子，记作
T
π
T^{\\pi}
Tπ。这样，对于任何一个状态 s，这个算子的操作就可以定义为：
(
T
π
V
)
(
s
)
≜
∑
a
∈
A
π
(
a
∣
s
)
(
r
(
s
,
a
)
+
γ
∑
s
′
∈
S
P
(
s
′
∣
s
,
a
)
V
(
s
′
)
)
(2.1)
(T^{\\pi}V)(s)\\triangleq \\sum_{a\\in A}\\pi(a|s)(r(s,a)+\\gamma \\sum_{s^{'}\\in S}P(s^{'}|s,a)V(s^{'}))\\text{(2.1)}
(TπV)(s)≜a∈A∑π(a∣s)(r(s,a)+γs′∈S∑P(s′∣s,a)V(s′))(2.1)
三、贝尔曼算子是压缩映射 对于任意状态s，两个价值函数经过贝尔曼算子作用后的差距：
∣
(
T
π
V
k
+
1
)
(
s
)
−
(
T
π
V
k
)
(
s
)
∣
=
∣
∑
a
∈
A
π
(
a
∣
s
)
γ
∑
s
′
∈
S
P
(
s
′
∣
s
,
a
)
[
V
k
+
1
(
s
′
)
−
V
k
(
s
′
)
]
∣
(2.2)
|(T^{\\pi}V_{k+1})(s)-(T^{\\pi}V_k)(s)|=|\\sum_{a\\in A} \\pi(a|s)\\gamma \\sum_{s^{'}\\in S}P(s^{'}|s,a)[V_{k+1}(s^{'})-V_k(s^{'})]|\\text{(2.2)}
∣(TπVk+1)(s)−(TπVk)(s)∣=∣a∈A∑π(a∣s)γs′∈S∑P(s′∣s,a)[Vk+1(s′)−Vk(s′)]∣(2.2)
≤
∑
a
∈
A
π
(
a
∣
s
)
γ
∑
s
′
∈
S
P
(
s
′
∣
s
,
a
)
∣
V
k
+
1
(
s
′
)
−
V
k
(
s
′
)
∣
(2.3)
\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\text{ }\\le \\sum_{a\\in A} \\pi(a|s)\\gamma \\sum_{s^{'}\\in S}P(s^{'}|s,a)|V_{k+1}(s^{'})-V_k(s^{'})|\\text{(2.3)}
≤a∈A∑π(a∣s)γs′∈S∑P(s′∣s,a)∣Vk+1(s′)−Vk(s′)∣(2.3)
=
γ
∣
V
k
+
1
−
V
k
∣
(2.4)
=\\gamma |V_{k+1}-V_k|\\text{(2.4)}
=γ∣Vk+1−Vk∣(2.4) 综上所述：
∣
(
T
π
V
k
+
1
)
(
s
)
−
(
T
π
V
k
)
(
s
)
∣
≤
γ
∣
V
k
+
1
−
V
k
∣
(2.5)
|(T^{\\pi}V_{k+1})(s)-(T^{\\pi}V_k)(s)|\\le \\gamma |V_{k+1}-V_k|\\text{(2.5)}
∣(TπVk+1)(s)−(TπVk)(s)∣≤γ∣Vk+1−Vk∣(2.5) 由于经过贝尔曼算子的转化之后
V
k
+
1
和
V
k
V_{k+1}\\text{和}V_k
Vk+1和Vk之间的差距小于未转化之前的。因此，贝尔曼算子有一个关键性质：它是压缩映射。巴拿赫定理指出，在完备的度量空间里（我们的价值函数空间就是），任何压缩映射都有唯一的不动点。即当n足够大时，
V
n
+
1
π
=
T
π
V
n
π
V^{\\pi}_{n+1}=T^{\\pi}V^{\\pi}_n
Vn+1π=TπVnπ。此时，策略
π
\\pi
π下满足贝尔曼期望的价值向量
V
π
=
V
n
+
1
π
V^{\\pi }=V^{\\pi}_{n+1}
Vπ=Vn+1π。经此启发，我们可以设计一个价值评估函数来得到在一个策略下的价值函数。
确定性策略的策略提升算法
在策略评估算法中，一般设置初始的策略未任意状态的所有可能动作的可能性为动作个数的导数。即在任何状态动作的可能性相等。因此，首次运行策略评估出来的策略虽然并非确定性策略，但是，我们设置策略提升算法返回一个确定策略。这是因为策略提升算法的目的是在已知价值函数的条件下输出最优策略。因此，在策略迭代过程中，除了首次策略评估，策略提升算法接收到非确定性策略外，其余迭代接受的都是确定性策略。
策略提升定理
假设对于所有的状态s，经过新策略修改后的动作状态价值大于或等于原确定性策略下的动作状态价值。由于愿策略为确定性策略，因此，原策略下的动作状态价值策略等于原策略下的价值策略，数学表示为：
∀
s
∈
S
，
V
π
(
s
)
≤
Q
π
(
s
,
π
′
(
s
)
)
(3.1)
\\forall s\\in S，V^{\\pi}(s)\\le Q^{\\pi}(s,\\pi^{'}(s))\\text{(3.1)}
∀s∈S，Vπ(s)≤Qπ(s,π′(s))(3.1) 之所以用
Q
π
Q^{\\pi}
Qπ是因为用于计算的动作状态价值函数是利用在原策略下利用策略评估算法计算处的价值函数计算而来。
∀
s
，
Q
π
(
s
,
π
′
(
s
)
)
=
E
[
R
t
+
γ
V
π
(
S
t
+
1
)
∣
S
t
=
s
]
(3.2)
\\forall s，Q^{\\pi}(s,\\pi^{'}(s))=\\mathbb{E}[R_t+\\gamma V^{\\pi}(S_{t+1})|S_t=s]\\text{(3.2)}
∀s，Qπ(s,π′(s))=E[Rt+γVπ(St+1)∣St=s](3.2) 步骤一：将（3.1）代入（3.2）可得：
E
[
R
t
+
γ
V
π
(
S
t
+
1
)
∣
S
t
=
s
]
≤
E
[
R
t
+
γ
Q
π
(
S
t
+
1
)
,
π
′
(
S
t
+
1
π
)
∣
S
t
=
s
]
(3.3)
\\mathbb{E}[R_t+\\gamma V^{\\pi}(S_{t+1})|S_t=s]\\le \\mathbb{E}[R_t+\\gamma Q^{\\pi}(S_{t+1}),\\pi^{'}(S_{t+1}^{\\pi})|S_t=s]\\text{(3.3)}
E[Rt+γVπ(St+1)∣St=s]≤E[Rt+γQπ(St+1),π′(St+1π)∣St=s](3.3) 步骤二：由（3.2）代入（3.3）可得：
E
[
R
t
+
γ
Q
π
(
S
t
+
1
)
,
π
′
(
S
t
+
1
π
)
∣
S
t
=
s
]
=
E
[
R
t
+
γ
R
t
+
1
+
γ
2
V
π
(
S
t
+
2
)
∣
S
t
=
s
]
(3.4)
\\mathbb{E}[R_t+\\gamma Q^{\\pi}(S_{t+1}),\\pi^{'}(S_{t+1}^{\\pi})|S_t=s]=\\mathbb{E}[R_t+\\gamma R_{t+1}+\\gamma^{2}V^{\\pi}(S_{t+2})|S_t=s]\\text{(3.4)}
E[Rt+γQπ(St+1),π′(St+1π)∣St=s]=E[Rt+γRt+1+γ2Vπ(St+2)∣St=s](3.4) 不断重复步骤一、二，最终可得：
V
π
(
s
)
≤
E
[
R
t
+
γ
R
t
+
1
+
γ
2
R
t
+
2
+
.
.
.
∣
S
t
=
s
]
(3.5)
V^{\\pi}(s)\\le \\mathbb{E}[R_t+\\gamma R_{t+1}+\\gamma^{2}R_{t+2}+…|S_t=s]\\text{(3.5)}
Vπ(s)≤E[Rt+γRt+1+γ2Rt+2+…∣St=s](3.5) 由于除了
R
t
R_t
Rt，其余所有的
R
t
+
k
，
k
>
0
R_{t+k}，k>0
Rt+k，k>0都是在修改原确定性策略动作的基础上的，因此，（3.5）不等式右侧的
E
[
R
t
+
γ
R
t
+
1
+
γ
2
R
t
+
2
+
.
.
.
∣
S
t
=
s
]
(3.5)
=
V
π
′
(
s
)
\\mathbb{E}[R_t+\\gamma R_{t+1}+\\gamma^{2}R_{t+2}+…|S_t=s]\\text{(3.5)}=V^{\\pi^{'}}(s)
E[Rt+γRt+1+γ2Rt+2+…∣St=s](3.5)=Vπ′(s) (3.5)可改造成：
∀
s
，
V
π
(
s
)
≤
V
π
′
(
s
)
(3.6)
\\forall s ，V^{\\pi}(s)\\le V^{\\pi^{'}}(s)\\text{ (3.6)}
∀s，Vπ(s)≤Vπ′(s) (3.6) 综上所述： 现在假设存在一个确定性策略
π
′
\\pi^{'}
π′，在任意一个状态
s
s
s下，都满足
V
π
(
s
)
≤
Q
π
(
s
,
π
′
(
s
)
)
V^{\\pi}(s)\\le Q^{\\pi}(s,\\pi^{'}(s))
Vπ(s)≤Qπ(s,π′(s)) 于是在任意状态s下，我们有
V
π
(
s
)
≤
V
π
′
(
s
)
V^{\\pi}(s)\\le V^{\\pi^{'}}(s)
Vπ(s)≤Vπ′(s) 这给了我们一个启示：可以利用原策略的价值函数来计算新策略下的动作状态函数。只要计算任意状态下所有动作的价值后取最大的价值数所对应的动作定为新策略的该状态下的动作，即可得到在某价值函数下的最优策略。当我们提取了
Q
(
s
,
a
)
Q(s,a)
Q(s,a)中最大价值后得到最优策略后可进一步利用策略评估算法构造新策略的价值函数，价值函数中每个状态对应的价值为
a
r
g
max
a
∈
A
Q
π
(
s
,
a
)
arg \\max_{a\\in A}Q^{\\pi}(s,a)
argmaxa∈AQπ(s,a)。 数学表示为：
π
′
(
s
)
=
a
r
g
max
a
∈
A
Q
π
(
s
,
a
)
\\pi^{'}(s)=arg \\max_{a\\in A}Q^{\\pi}(s,a)
π′(s)=arga∈AmaxQπ(s,a)
V
π
′
(
s
)
=
max
a
∈
A
Q
π
(
s
,
a
)
V^{\\pi^{'}}(s)= \\max_{a\\in A}Q^{\\pi}(s,a)
Vπ′(s)=a∈AmaxQπ(s,a) (注：arg max 返回的是最优动作本身；max 返回的才是最大价值。)
策略迭代算法
由前文我们可知，策略评估算法可以计算固定策略下的价值函数，策略提升算法可以算出在固定价值函数的基础上，计算最优策略。我们自然联想到可以不断地迭代策略评估算法和策略提升算法最终收敛到最优策略。每一次迭代本质上是在计算某一价值函数地最优策略。现在问题是迭代何时停止呢？ 如果某一步得到了最优确定性策略后进入下一步迭代，此时策略评估算法得到的即是最优策略的价值函数。根据最优策略的价值函数再经过策略提升返回仍然是最优策略。因此，我们可以根据在迭代前后策略是否发生改变判断是否已经计算出最优策略。 重新审视策略迭代的全流程可以发现，每一次迭代最后都是返回在某一价值函数下的最优策略。这种算法在不断寻求局部最优解最终得到全局最优解的算法称为贪心算法。而策略迭代的终止条件是策略不再改变。最优策略是策略提升算子的不动点，因此一旦达到最优，策略提升将不再产生变化。 因此，策略迭代是一种基于完全信息的贪心算法，其“局部贪心”恰好是全局最优——这是贝尔曼最优方程赋予动态规划的独特优势。
代码解析
一、构建环境 
import copy
class CliffWalkingEnv:
""" 悬崖漫步环境"""
def __init__(self, ncol=12, nrow=4):
self.ncol = ncol # 定义网格世界的列
self.nrow = nrow # 定义网格世界的行
# 转移矩阵P[state][action] = [(p, next_state, reward, done)]包含下一个状态和奖励
self.P = self.createP()
def createP(self):
# 初始化
P = [[[] for j in range(4)] for i in range(self.nrow * self.ncol)]
#for i in range(self.nrow * self.ncol)：每个状态一个[[] for j in range(4)]列表
#[] for j in range(4)：每个动作一个[]
#每个状态都有四种可能动作
#转移矩阵P[i][a]状态i动作a下的元素是一个列表[]
# 4种动作, change[0]:上,change[1]:下, change[2]:左, change[3]:右。坐标系原点(0,0)
# 定义在左上角
change = [[0, –1], [0, 1], [–1, 0], [1, 0]]
#change[0~3][0/1]:最外层的0~3表示动作0~3；最里层的0代表左右列变化【左：-1/右：1】，1代表上下行变化【上：-1/下：1】
for i in range(self.nrow):
#当前状态的行i
for j in range(self.ncol):
#当前状态的列j
for a in range(4):
#在状态(i,j)是进行动作a
# 位置在悬崖或者目标状态,因为无法继续交互,任何动作奖励都为0
if i == self.nrow – 1 and j > 0:
# 此时处于终点/悬崖(1, i * self.ncol + j, 0,True)：1：概率（一定发生）；i * self.ncol + j：下一个状态（此时意味着保持不变）；0：奖励；True：进入保持状态时刻
P[i * self.ncol + j][a] = [(1, i * self.ncol + j, 0,
True)]
continue
#continue: 跳过本次动作的剩余计算，直接处理下一个动作。因为悬崖/目标状态的所有四个动作转移都相同（留在原地、终止）。
# 其他位置
#next_x ：下一列；next_y ：下一行
next_x = min(self.ncol – 1, max(0, j + change[a][0]))
next_y = min(self.nrow – 1, max(0, i + change[a][1]))
next_state = next_y * self.ncol + next_x
#只要是正常情况下的有效转移奖励都是-1既保证了尽可能少跳越到达终点，又和终点时候的保持不变形成差异。这意味着智能体到达终点时不会获得额外正奖励，唯一的好处是回合结束不再有后续惩罚。
reward = –1
done = False
# 下一个位置在悬崖或者终点
if next_y == self.nrow – 1 and next_x > 0:
done = True
if next_x != self.ncol – 1: # 下一个位置在悬崖
reward = –100
P[i * self.ncol + j][a] = [(1, next_state, reward, done)]
return P
二、策略迭代
class PolicyIteration:
""" 策略迭代算法 """
def __init__(self, env, theta, gamma):
#env：传入CliffWalkingEnv构造的环境。
self.env = env
#self.v = [0] * self.env.ncol * self.env.nrow：初始化所有状态的价值都为0
self.v = [0] * self.env.ncol * self.env.nrow
#初始化所有状态的策略为所有动作都以1/4概率
self.pi = [[0.25, 0.25, 0.25, 0.25]
for i in range(self.env.ncol * self.env.nrow)] # 初始化为均匀随机策略
self.theta = theta # 策略评估收敛阈值
self.gamma = gamma # 折扣因子
def policy_evaluation(self): # 策略评估
cnt = 1 # 计数迭代次数得到价值函数
while 1:
#初始化所有状态中相邻的迭代价值中的最大差值
max_diff = 0
#初始化新的价值函数，全0
new_v = [0] * self.env.ncol * self.env.nrow
for s in range(self.env.ncol * self.env.nrow):
#遍历所有状态s
qsa_list = [] # 开始计算状态s下的所有动作的Q(s,a)价值
for a in range(4):
qsa = 0
for res in self.env.P[s][a]:
p, next_state, r, done = res
#由于self.env.P[s][a]中所有策略的概率之和为1：因此p*r之和为r
#qsa：Q（s,a）
qsa += p * (r + self.gamma * self.v[next_state] * (1 – done))
#“(1 – done) 确保当下一状态为终止状态时，未来价值为 0，符合回报定义的截断性质。
# 本章环境比较特殊,奖励和下一个状态有关,所以需要和状态转移概率相乘
qsa_list.append(self.pi[s][a] * qsa)
#由于V(s)=\\sum_{a}\\pi(a|s)Q(s,a)所以qsa_list.append(self.pi[s][a] * qsa)
new_v[s] = sum(qsa_list) # 状态价值函数和动作价值函数之间的关系
#取上一次差值和这次差值最大的
max_diff = max(max_diff, abs(new_v[s] – self.v[s]))
#迭代新的V
self.v = new_v
if max_diff < self.theta: break # 满足收敛条件,退出评估迭代
cnt += 1
print("策略评估进行%d轮后完成" % cnt)
def policy_improvement(self): # 策略提升
for s in range(self.env.nrow * self.env.ncol):
#对于状态s
qsa_list = []
for a in range(4):
qsa = 0
for res in self.env.P[s][a]:
p, next_state, r, done = res
qsa += p * (r + self.gamma * self.v[next_state] * (1 – done))
qsa_list.append(qsa)
#取状态s下的四个动作的Q(s,a)中最大的一个
maxq = max(qsa_list)
cntq = qsa_list.count(maxq) # 计算有几个动作得到了最大的Q值
# 让这些动作均分概率
#状态s在新策略的安排下只进行能取得最大动作价值的操作
self.pi[s] = [1 / cntq if q == maxq else 0 for q in qsa_list]
print("策略提升完成")
return self.pi
def policy_iteration(self): # 策略迭代
while 1:
self.policy_evaluation()
old_pi = copy.deepcopy(self.pi) # 将列表进行深拷贝,方便接下来进行比较
#self.pi 通常是一个嵌套结构（例如 list 或 dict 或 numpy 数组），如果直接赋值。
#old_pi = self.pi，那么 old_pi 和 self.pi 会指向同一个对象。后续修改 self.pi 会同步改变 old_pi，导致无法保留旧策略的值。
#使用 copy.deepcopy 会递归地复制所有层级的内容，使得 old_pi 成为完全独立的副本，与 self.pi 互不影响
#保留旧策略的完整副本，以便在策略提升后判断策略是否发生变化。如果新旧策略完全相同，说明已收敛到最优策略，迭代终止。
new_pi = self.policy_improvement()
if old_pi == new_pi: break
三、输出
def print_agent(agent, action_meaning, disaster=[], end=[]):
print("状态价值：")
for i in range(agent.env.nrow):
for j in range(agent.env.ncol):
# 为了输出美观,保持输出6个字符
print('%6.6s' % ('%.3f' % agent.v[i * agent.env.ncol + j]), end=' ')
print()
print("策略：")
for i in range(agent.env.nrow):
for j in range(agent.env.ncol):
# 一些特殊的状态,例如悬崖漫步中的悬崖
if (i * agent.env.ncol + j) in disaster:
print('****', end=' ')
elif (i * agent.env.ncol + j) in end: # 目标状态
print('EEEE', end=' ')
else:
a = agent.pi[i * agent.env.ncol + j]
pi_str = ''
for k in range(len(action_meaning)):
pi_str += action_meaning[k] if a[k] > 0 else 'o'
print(pi_str, end=' ')
print()
env = CliffWalkingEnv()
action_meaning = ['^', 'v', '<', '>']
theta = 0.001
gamma = 0.9
agent = PolicyIteration(env, theta, gamma)
agent.policy_iteration()
print_agent(agent, action_meaning, list(range(37, 47)), [47])
策略评估进行60轮后完成 策略提升完成 策略评估进行72轮后完成 策略提升完成 策略评估进行44轮后完成 策略提升完成 策略评估进行12轮后完成 策略提升完成 策略评估进行1轮后完成 策略提升完成 状态价值： -7.712 -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -7.458 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 -7.176 -6.862 -6.513 -6.126 -5.695 -5.217 -4.686 -4.095 -3.439 -2.710 -1.900 -1.000 -7.458 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 策略： ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovo> ovoo ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ovoo ^ooo **** **** **** **** **** **** **** **** **** **** EEEE
![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)