理解马尔可夫决策过程的值迭代算法

Question

在学习MDP's 我遇到了麻烦value iteration。从概念上讲，此示例非常简单且有意义：

如果您有一个6双面骰子，并且您掷出 a4或 a5或 a，则6您保留该金额，$但如果您掷出 a1或 a2或 a，则3您将失去资金并结束游戏。

一开始你有$0滚动和不滚动之间的选择是：

k = 1
If I roll : 1/6*0 + 1/6*0 + 1/6*0 + 1/6*4 + 1/6*5 + 1/6*6 = 2.5 
I I don't roll : 0
since 2.5 > 0 I should roll

k = 2:
If I roll and get a 4:
    If I roll again: 4 + 1/6*(-4) + 1/6*(-4) + 1/6*(-4) + 1/6*4 + 1/6*5 + 1/6*6 = 4.5
    If I don't roll: 4
    since 4.5 is greater than 4 I should roll

If I roll and get a 5:
    If I roll again: 5 + 1/6*(-5) + 1/6*(-5) + 1/6*(-5) + 1/6*4 + 1/6*5 + 1/6*6 = 5
    If I don't roll: 5
    Since the difference is 0 I should not roll

If I roll and get a 6:
    If I roll again: 6 + 1/6*(-6) + 1/6*(-5) + 1/6*(-5) + 1/6*4 + 1/6*5 + 1/6*6 = 5.5
    If I don't roll: 6
    Since the difference is -0.5 I should not roll

我遇到的问题是将其转换为 python 代码。不是因为我不擅长python，而是我对伪代码的理解是错误的。尽管贝尔曼方程对我来说确实有意义。

我borrowed将伯克利代码value iteration修改为：

isBadSide = [1,1,1,0,0,0]

def R(s):
    if isBadSide[s-1]:
        return -s
    return s

def T(s, a, N):
    return [(1./N, s)]

def value_iteration(N, epsilon=0.001):
    "Solving an MDP by value iteration. [Fig. 17.4]"
    U1 = dict([(s, 0) for s in range(1, N+1)])
    while True:
        U = U1.copy()
        delta = 0
        for s in range(1, N+1):
            U1[s] = R(s) + max([sum([p * U[s1] for (p, s1) in T(s, a, N)])
                                        for a in ('s', 'g',)])

            delta = max(delta, abs(U1[s] - U[s]))

        if delta < epsilon:
             return U

    print(value_iteration(6))
    # {1: -1.1998456790123457, 2: -2.3996913580246915, 3: -3.599537037037037, 4: 4.799382716049383, 5: 5.999228395061729, 6: 7.199074074074074}

这是错误的答案。这段代码的错误在哪里？还是我对算法的理解有问题？

Answer 1

让B为您当前的余额。

\n\n

如果您选择滚动，则预期奖励为2.5 - B * 0.5。

\n\n

如果您选择不滚动，则预期奖励为0。

\n\n

所以，政策是这样的：如果B < 5，则滚动。否则，不要。

\n\n

遵循该政策时每一步的预期奖励是V = max(0, 2.5 - B * 0.5)。

\n\n\n\n

现在，如果你想用贝尔曼方程来表达它，你需要将平衡纳入状态。

\n\n

让状态<Balance, GameIsOver>由当前余额和定义游戏是否结束的标志组成。

\n\n

\n
• 操作stop：\n\n
  \n
  • 将状态<B, false>变为<B, true>
  \n
\n
• 操作roll：\n\n
  \n
  • 变成\n<B, false>概率<0, true>1/2
  \n
  • 变成\n<B, false>概率<B + 4, false>1/6
  \n
  • 变成\n<B, false>概率<B + 5, false>1/6
  \n
  • 变成\n<B, false>概率<B + 6, false>1/6
  \n
\n
• 任何行动都不能<B1, true>变成<B2, false>
\n

\n\n

使用这里的符号：

\n\n

\xcf\x80(<B, false>) = "roll", if B < 5

\n\n

\xcf\x80(<B, false>) = "stop", if B >= 5

\n\n

V(<B, false>) = 2.5 - B * 0.5, if B < 5

\n\n

V(<B, false>) = 0, if B >= 5

\n