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

Question

在了解MDP的问题时，我遇到了value iteration问题。从概念上讲这个例子很简单，是有道理的：

如果你有一个6面的骰子，你滚4或5或6您保持$这一数额，但如果你滚1或2或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不太好，但也许我对pseudocode的理解是错误的。尽管Bellman equation确实对我有意义。

我borrowed为value iteration的Berkley代码，并将其修改为：

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.199845679, 2: -2.3996913580246915, 3: -3.599537037037037, 4: 4.799382716049383, 5: 5.999228395061729, 6: 7.199074074074074} 

这是错误的答案。这段代码中的错误在哪里？或者，这是我对算法的理解问题？

Answer 1

让B成为您当前的余额。

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

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

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

当遵循该政策时，每一步的预期回报为V = max(0, 2.5 - B * 0.5)。

---

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

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

• 行动stop：
  • 接通状态<B, false>到<B, true>
• 行动roll：
  • 变成<B, false>到<0, true>与 概率1/2
  • 变成<B, false>到<B + 4, false>与 概率1/6
  • 变成<B, false>到<B + 5, false>与 概率1/6
  • 变成<B, false>到<B + 6, false>与 概率1/6
• 无动作可以把<B1, true>成<B2, false>

使用符号从here：

π(<B, false>) = "roll", if B < 5

π(<B, false>) = "stop", if B >= 5

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

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