如何找出策略迭代的值?
How to find out values of Policy Iteration?
我的老师给出了以下问题:
考虑以下具有 3 个状态和奖励的 MDP。有两种可能的动作——红色和蓝色。状态转移概率在边上给出,S2 是终端状态。假设初始策略为:π(S0) = B; π(S1) = R。
我们被问及最佳策略的 γ 值 (0<γ<1) 是什么:
(a) π∗(S0) = R; π*(S1) = B;
(b) π∗(S0) = B; π*(S1) = R;
(c) π∗(S0) = R; π*(S1) = R;
我已经证明 (a) 的答案是 γ = 0.1,但找不到 (b) 和 (c) 的 γ 值。老师说对于 (b) 任何 γ > 0.98 都可以,而对于 (c) γ = 0.5。我认为他错了,并且写了 the following python script ,它遵循教科书(Russell 和 Norvig AIMA)中的算法,实际上对于任何 γ 值,我得到的唯一策略是 (a)。但是老师说他没有错,我的剧本肯定有问题。我怎样才能明确地证明这样的政策是不可能的?
S0 = "S0"
S1 = "S1"
S2 = "S2"
BLUE = "blue"
RED = "red"
gamma = 0.5 # TODO MODIFY GAMMA HERE
# P(s'|s,a)
P_destination_start_action = \
{
(S0,S0, BLUE):0.5,(S0,S0,RED):0.9, (S0,S1,BLUE):0.8,(S0,S1,RED):0, (S0,S2, BLUE):0,(S0,S2,RED):0,
(S1,S0, BLUE):0.5,(S1,S0,RED):0, (S1,S1,BLUE):0.2,(S1,S1,RED):0.6, (S1,S2, BLUE):0,(S1,S2,RED):0,
(S2,S0, BLUE):0, (S2,S0,RED):0.1, (S2,S1,BLUE):0 ,(S2,S1,RED):0.4,(S2,S2, BLUE):1,(S2,S2,RED):1
}
class MDP:
def __init__(self):
self.states = [S0, S1, S2]
self.actions = [BLUE, RED]
self.P_dest_start_action = P_destination_start_action
self.rewards = {S0: -2, S1: -5, S2: 0}
def POLICY_EVALUATION(policy_vec, utility_vec, mdp):
new_utility_vector = {}
for s in mdp.states:
to_sum = [(mdp.P_dest_start_action[(s_tag, s, policy_vec[s])] * utility_vec[s_tag])
for s_tag in mdp.states]
new_utility_vector[s] = mdp.rewards[s] + gamma * sum(to_sum)
return new_utility_vector
def POLICY_ITERATION(mdp):
utility_vector = {state: 0 for state in mdp.states}
policy_vector = {S0: BLUE, S1: RED, S2: RED}
unchanged = False
while not unchanged:
utility_vector = POLICY_EVALUATION(policy_vector, utility_vector, mdp)
unchanged = True
for s in mdp.states:
BLUE_sum = sum([(mdp.P_dest_start_action[(s_tag, s, BLUE)] * utility_vector[s_tag])
for s_tag in mdp.states])
RED_sum = sum([(mdp.P_dest_start_action[(s_tag, s, RED)] * utility_vector[s_tag])
for s_tag in mdp.states])
if policy_vector[s] == RED and BLUE_sum > RED_sum:
policy_vector[s] = BLUE
unchanged = False
elif policy_vector[s] == BLUE and RED_sum > BLUE_sum:
policy_vector[s] = RED
unchanged = False
return policy_vector
if __name__ == "__main__":
Q2_mdp = MDP()
new_policy_vec = POLICY_ITERATION(Q2_mdp)
print("===========================END===============================")
print("S_O policy =", new_policy_vec[S0], " ,S_1 Policy =", new_policy_vec[S1])
你的老师似乎(大部分)是对的。
这看起来不一定是必须以编程方式解决的问题,它也可以通过数学方式解决(这可能是您的老师所做的,以及为什么他可以说您的代码必须在不看代码的情况下被窃听)。
基于数学的解决方案
让 V(S, C)
表示在状态 S
中选择颜色 C
的值。对于所有颜色 C
.
,我们通常有 V(S2, C) = 0
在S0
或S1
中选择红色动作的真实值V(S0, R)
和V(S1, R)
很容易写下来,因为它们不依赖于任何其他状态的值(从技术上讲,它们确实取决于 S2
的值,但那些是 0
,因此我们可以将它们排除在外):
V(S0, R) = 0.9 * (-2 + gamma * V(S0, R))
V(S1, R) = 0.6 * (-5 + gamma * V(S1, R))
用一点算术,这些可以重写为:
V(S0, R) = -1.8 / (1 - 0.9 * gamma)
V(S1, R) = -3 / (1 - 0.6 * gamma)
观察到在 S0
和 S1
两种状态下都选择 B
(蓝色)的策略永远不会是最优的,这一点也很有用。这样的政策永远不会达到 S2
并且只会继续收集无限数量的负面奖励。
知道了这一点,我们可以很容易地用V(S0, B)
和V(S1, R)
来写V(S0, B)
。我们不必考虑值 V(S0, B)
中的 V(S1, B)
项,因为当我们考虑以下情况时,在 S1
中播放 B
永远不是最佳选择也已经在 S0
中播放 B
:
V(S0, B) = 0.5 * (-2 + gamma * V(S0, B)) + 0.5 * (-5 + gamma * V(S1, R))
简化为:
V(S0, B) = -3.5 + 0.5 * gamma * V(S0, B) + 0.5 * gamma * (-3 / (1 - 0.6 * gamma))
现在我们有了 V(S0, R)
和 V(S0, B)
的漂亮表达式,我们可以从另一个减去一个:如果表达式 V(S0, B) - V(S0, R)
为正,则最优策略将发挥 B
在 S0
。如果为负数,则播放R
。
有了更多的算术运算,现在应该可以解决像 V(S0, B) > V(S0, R)
这样的不等式了。一个更简单的解决方案(尽管您的老师可能不希望您参加考试)是将两个值 (= (-3.5 + (-1.5x / (1 - 0.6x))) / (1 - 0.5x) + (1.8 / (1 - 0.9x))
) 的推导代入 google 并查看绘图相交的位置x
轴:这是在 x = 0.96
处(例如 gamma = 0.96
)。因此,您的老师似乎在该解决方案中犯了一个小错误 (b) 实际上适用于任何 gamma > 0.96
,而不是任何 gamma > 0.98
.
当然,同样的推理和算术也适用于我还没有考虑过的其他价值函数,比如V(S1, B)
。
基于编程的解决方案
至于为什么您的基于编程的解决方案不起作用,确实存在一个小错误;在 Policy Evaluation 步骤中,您只循环遍历所有状态一次。可能需要连续多个这样的循环。看看 Russel 和 Norvig 的书确实提到了 Value Iteration 的修改版本可以用于这个函数,它本身一直循环直到实用程序几乎没有变化。
根据 Sutton 和 Barto 的强化学习书中的伪代码,Policy Evaluation 函数可以固定如下:
def POLICY_EVALUATION(policy_vec, utility_vec, mdp):
new_utility_vector = utility_vec
delta = 100000.0
while delta > 0.00001:
delta = 0.0
for s in mdp.states:
old_vs = {s: new_utility_vector[s] for s in new_utility_vector}
to_sum = [(mdp.P_dest_start_action[(s_tag, s, policy_vec[s])] * new_utility_vector[s_tag])
for s_tag in mdp.states]
new_utility_vector[s] = mdp.rewards[s] + gamma * sum(to_sum)
delta = max(delta, max([abs(new_utility_vector[s] - old_vs[s]) for s in old_vs]))
return new_utility_vector
经过这次改动,你确实会,比如,得到
===========================END===============================
('S_O policy =', 'blue', ' ,S_1 Policy =', 'red')
作为 gamma = 0.97
的输出(不仅仅是 gamma > 0.98
),正如基于数学的解决方案所预期的那样。
我的老师给出了以下问题:
考虑以下具有 3 个状态和奖励的 MDP。有两种可能的动作——红色和蓝色。状态转移概率在边上给出,S2 是终端状态。假设初始策略为:π(S0) = B; π(S1) = R。
我们被问及最佳策略的 γ 值 (0<γ<1) 是什么:
(a) π∗(S0) = R; π*(S1) = B;
(b) π∗(S0) = B; π*(S1) = R;
(c) π∗(S0) = R; π*(S1) = R;
我已经证明 (a) 的答案是 γ = 0.1,但找不到 (b) 和 (c) 的 γ 值。老师说对于 (b) 任何 γ > 0.98 都可以,而对于 (c) γ = 0.5。我认为他错了,并且写了 the following python script ,它遵循教科书(Russell 和 Norvig AIMA)中的算法,实际上对于任何 γ 值,我得到的唯一策略是 (a)。但是老师说他没有错,我的剧本肯定有问题。我怎样才能明确地证明这样的政策是不可能的?
S0 = "S0"
S1 = "S1"
S2 = "S2"
BLUE = "blue"
RED = "red"
gamma = 0.5 # TODO MODIFY GAMMA HERE
# P(s'|s,a)
P_destination_start_action = \
{
(S0,S0, BLUE):0.5,(S0,S0,RED):0.9, (S0,S1,BLUE):0.8,(S0,S1,RED):0, (S0,S2, BLUE):0,(S0,S2,RED):0,
(S1,S0, BLUE):0.5,(S1,S0,RED):0, (S1,S1,BLUE):0.2,(S1,S1,RED):0.6, (S1,S2, BLUE):0,(S1,S2,RED):0,
(S2,S0, BLUE):0, (S2,S0,RED):0.1, (S2,S1,BLUE):0 ,(S2,S1,RED):0.4,(S2,S2, BLUE):1,(S2,S2,RED):1
}
class MDP:
def __init__(self):
self.states = [S0, S1, S2]
self.actions = [BLUE, RED]
self.P_dest_start_action = P_destination_start_action
self.rewards = {S0: -2, S1: -5, S2: 0}
def POLICY_EVALUATION(policy_vec, utility_vec, mdp):
new_utility_vector = {}
for s in mdp.states:
to_sum = [(mdp.P_dest_start_action[(s_tag, s, policy_vec[s])] * utility_vec[s_tag])
for s_tag in mdp.states]
new_utility_vector[s] = mdp.rewards[s] + gamma * sum(to_sum)
return new_utility_vector
def POLICY_ITERATION(mdp):
utility_vector = {state: 0 for state in mdp.states}
policy_vector = {S0: BLUE, S1: RED, S2: RED}
unchanged = False
while not unchanged:
utility_vector = POLICY_EVALUATION(policy_vector, utility_vector, mdp)
unchanged = True
for s in mdp.states:
BLUE_sum = sum([(mdp.P_dest_start_action[(s_tag, s, BLUE)] * utility_vector[s_tag])
for s_tag in mdp.states])
RED_sum = sum([(mdp.P_dest_start_action[(s_tag, s, RED)] * utility_vector[s_tag])
for s_tag in mdp.states])
if policy_vector[s] == RED and BLUE_sum > RED_sum:
policy_vector[s] = BLUE
unchanged = False
elif policy_vector[s] == BLUE and RED_sum > BLUE_sum:
policy_vector[s] = RED
unchanged = False
return policy_vector
if __name__ == "__main__":
Q2_mdp = MDP()
new_policy_vec = POLICY_ITERATION(Q2_mdp)
print("===========================END===============================")
print("S_O policy =", new_policy_vec[S0], " ,S_1 Policy =", new_policy_vec[S1])
你的老师似乎(大部分)是对的。
这看起来不一定是必须以编程方式解决的问题,它也可以通过数学方式解决(这可能是您的老师所做的,以及为什么他可以说您的代码必须在不看代码的情况下被窃听)。
基于数学的解决方案
让 V(S, C)
表示在状态 S
中选择颜色 C
的值。对于所有颜色 C
.
V(S2, C) = 0
在S0
或S1
中选择红色动作的真实值V(S0, R)
和V(S1, R)
很容易写下来,因为它们不依赖于任何其他状态的值(从技术上讲,它们确实取决于 S2
的值,但那些是 0
,因此我们可以将它们排除在外):
V(S0, R) = 0.9 * (-2 + gamma * V(S0, R))
V(S1, R) = 0.6 * (-5 + gamma * V(S1, R))
用一点算术,这些可以重写为:
V(S0, R) = -1.8 / (1 - 0.9 * gamma)
V(S1, R) = -3 / (1 - 0.6 * gamma)
观察到在 S0
和 S1
两种状态下都选择 B
(蓝色)的策略永远不会是最优的,这一点也很有用。这样的政策永远不会达到 S2
并且只会继续收集无限数量的负面奖励。
知道了这一点,我们可以很容易地用V(S0, B)
和V(S1, R)
来写V(S0, B)
。我们不必考虑值 V(S0, B)
中的 V(S1, B)
项,因为当我们考虑以下情况时,在 S1
中播放 B
永远不是最佳选择也已经在 S0
中播放 B
:
V(S0, B) = 0.5 * (-2 + gamma * V(S0, B)) + 0.5 * (-5 + gamma * V(S1, R))
简化为:
V(S0, B) = -3.5 + 0.5 * gamma * V(S0, B) + 0.5 * gamma * (-3 / (1 - 0.6 * gamma))
现在我们有了 V(S0, R)
和 V(S0, B)
的漂亮表达式,我们可以从另一个减去一个:如果表达式 V(S0, B) - V(S0, R)
为正,则最优策略将发挥 B
在 S0
。如果为负数,则播放R
。
有了更多的算术运算,现在应该可以解决像 V(S0, B) > V(S0, R)
这样的不等式了。一个更简单的解决方案(尽管您的老师可能不希望您参加考试)是将两个值 (= (-3.5 + (-1.5x / (1 - 0.6x))) / (1 - 0.5x) + (1.8 / (1 - 0.9x))
) 的推导代入 google 并查看绘图相交的位置x
轴:这是在 x = 0.96
处(例如 gamma = 0.96
)。因此,您的老师似乎在该解决方案中犯了一个小错误 (b) 实际上适用于任何 gamma > 0.96
,而不是任何 gamma > 0.98
.
当然,同样的推理和算术也适用于我还没有考虑过的其他价值函数,比如V(S1, B)
。
基于编程的解决方案
至于为什么您的基于编程的解决方案不起作用,确实存在一个小错误;在 Policy Evaluation 步骤中,您只循环遍历所有状态一次。可能需要连续多个这样的循环。看看 Russel 和 Norvig 的书确实提到了 Value Iteration 的修改版本可以用于这个函数,它本身一直循环直到实用程序几乎没有变化。
根据 Sutton 和 Barto 的强化学习书中的伪代码,Policy Evaluation 函数可以固定如下:
def POLICY_EVALUATION(policy_vec, utility_vec, mdp):
new_utility_vector = utility_vec
delta = 100000.0
while delta > 0.00001:
delta = 0.0
for s in mdp.states:
old_vs = {s: new_utility_vector[s] for s in new_utility_vector}
to_sum = [(mdp.P_dest_start_action[(s_tag, s, policy_vec[s])] * new_utility_vector[s_tag])
for s_tag in mdp.states]
new_utility_vector[s] = mdp.rewards[s] + gamma * sum(to_sum)
delta = max(delta, max([abs(new_utility_vector[s] - old_vs[s]) for s in old_vs]))
return new_utility_vector
经过这次改动,你确实会,比如,得到
===========================END===============================
('S_O policy =', 'blue', ' ,S_1 Policy =', 'red')
作为 gamma = 0.97
的输出(不仅仅是 gamma > 0.98
),正如基于数学的解决方案所预期的那样。