algorithm - 带值迭代的马尔可夫决策过程动态规划

Question

我正在自学学习MDP和value iteration，希望有人能提高我的理解。

考虑具有数字 1, 2, 3 的 3 面骰子的问题。如果您掷出 1 或 2，您将在 $ 中获得该值，但如果您掷出 3，您将输掉你所有的钱和游戏结束(finite horizo​​n problem)

从概念上讲，我理解这是如何通过以下论坛完成的:

那么让我们分解一下:

由于这是一个finite horizo​​n 问题，我们可以忽略gamma。

如果我观察到 1，我可以go 或 stop。它的效用/值(value)是:

V(1) = max(Q(1, g), Q(1, s))
Q(1, g) = r + SUM( P( 2 | 1,g) * V(2) + P( 3 | 1,g) * V(3))
Q(1, s) = r + SUM( P( 2 | 1,s) * V(2) + P( 3 | 1,s) * V(3))

where r = 1

我observe 2，我可以go或stop:

V(2) = max(Q(2, g), Q(2, s))
Q(2, g) = r + SUM( P( 1 | 2,g) * V(1) + P( 3 | 1,g) * V(3))
Q(2, s) = r + SUM( P( 1 | 2,s) * V(1) + P( 3 | 1,s) * V(3))

where r = 2

我观察到3，游戏结束。

直觉上 V(3) 是 0 因为游戏已经结束，所以我们可以从 Q(1, g)。我们在上面也定义了 V(2)，所以我们可以将其替换为:

Q(1, g) = r + SUM( P( 2 | 1,g) *     
    MAX ((P( 1 | 2,g) * V(1)) , (P( 1 | 2,s) * V(1))))

这是事情变得糟糕的地方。如果 Q(1, g) 在其解决方案中有自己的定义，我不确定如何解决。这可能是因为数学背景差。

我所理解的是，效用或状态的值(value)会根据奖励而改变，因此决策也会改变。

具体来说，如果掷三给你 $3 而掷一结束游戏，那会影响你的决定，因为效用已经改变。

但我不确定如何编写代码来计算它。

有人可以解释一下动态规划是如何工作的吗？当 Q(1,g) 或 Q(1,s) 在其自己的定义中时，如何求解？

Answer 1

特殊解决方案:

对于您的示例，很容易知道应该选择“go”还是“stop”:有一个货币值 X，无论您是“go”还是“go”都一样或“停止”，对于所有较小的值，您应该“去”，对于所有较大的值，您应该停止。所以唯一的问题是，这个值是多少:

X=E("stop"|X)=E("go"|X)=1/3(1+X)+1/3(2+x) =>
1/3X=1 =>
X=3

我已经在第一行中使用了即使我选择“走”并赢了我也会在下一轮选择停止。所以知道应该做出什么决定，很容易计算出完美策略的预期胜利，在 python 中:

def calc(money):
    PROB=1.0/3.0
    if money<3:#go
       return  PROB*calc(money+1)+PROB*calc(money+2)-PROB*0
    else:#stop
       return money 

print "Expected win:", calc(0)

>>> Expected win: 1.37037037037

---

一般解决方案:

我不确定上述操作过程是否可以推广到任意场景。然而，还有另一种可能来解决此类问题。

让我们稍微改变一下游戏规则:不再有无限多的回合，而是最多 N 回合。然后你的递归变成:

E(money, N)=max(money, 1/3*E(money+1, N-1)+1/3*E(money+1, N-1))

如您所见，E(money, N) 的值不再取决于自身，而是取决于回合数较少的游戏的结果。

在没有证据的情况下，我声明，您正在寻找的值是 E(money)=lim_{N->infinity} E(money, N)。

对于您的特殊问题，python 代码如下所示:

PROB=1.0/3.0

MAX_GOS=20#neglect all possibilities with more than 1000 decisions "GO"

LENGTH=2*MAX_GOS+1#per go 2$ are possible

#What is expected value if the game ended now?
expected=range(LENGTH)

for gos_left in range(1,MAX_GOS+1):
   next=[0]*len(expected)
   for money in range(LENGTH-gos_left*2):
       next[money]=max(expected[money], PROB*expected[money+1]+PROB*expected[money+2])#decision stop or go
   expected=next

print "Expected win:", expected[0]

>>> Expected win: 1.37037037037

我很高兴这两种方法产生了相同的结果!