python - 如何找出策略迭代的值？

Question

我的老师提出了以下问题:
考虑以下具有 3 个状态和奖励的 MDP。有两种可能的 Action - 红色和蓝色。状态转换概率在边上给出，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])

Answer 1

你的老师似乎(大部分)是对的。

这似乎不一定是必须以编程方式解决的问题，它也可以通过数学方式解决(这可能是您的老师所做的，以及为什么他会说您的代码必须在不查看代码的情况下被窃听)。

基于数学的解决方案

让 V(S, C)表示选择颜色的值C处于状态S .我们有 V(S2, C) = 0所有颜色C .

写下真实值很容易V(S0, R)和 V(S1, R)用于选择 S0 中的红色操作或 S1 ，因为它们不依赖于任何其他状态的值(从技术上讲，它们确实依赖于 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)

观察选择 B 的策略也很有用。 (蓝色)在两个州S0以及 S1永远不会是最优的。这样的政策永远不会达到S2并简单地继续收集无限数量的负面奖励。

知道了，我们就可以轻松写出V(S0, B)根据 V(S0, B)和 V(S1, R) .我们不必考虑 V(S1, B)值中的术语 V(S0, B)因为播放 B 永远不会是最佳选择在 S1当我们考虑我们也玩B的情况时在 S0已经:
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)))的扣除插入谷歌并查看情节与 x 相交的位置。 -轴:这是x = 0.96 (例如 gamma = 0.96 )。因此，您的老师似乎在该解决方案中犯了一个小错误 (b) 实际上适用于任何 gamma > 0.96 ，而不是任何 gamma > 0.98 .

当然，同样的推理和算术也适用于我还没有考虑过的其他值函数，例如 V(S1, B) .

基于编程的解决方案

至于为什么您的基于编程的解决方案不起作用，确实似乎存在一个小错误；在 政策评估步骤，您只需遍历所有状态一次。可能需要连续多个这样的循环。看看 Russel 和 Norvig 的书确实提到了 的修改版本。值(value)迭代 可用于此功能，它本身会一直循环，直到实用程序几乎没有变化。

根据 Sutton 和 Barto 的 Reinforcement Learning 书中的伪代码，可以将 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 )，正如基于基于数学的解决方案所预期的那样。