4

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

考虑一个有数字的 3 面骰子的问题1, 2, 3。如果您掷出 a1或 a 2，您将获得该值，$但如果您掷出 a 3，您将失去所有钱，游戏结束 ( finite horizon problem)

从概念上讲，我了解如何使用以下论坛完成此操作：

在此处输入图像描述

所以让我们分解一下：

由于这是一个finite horizon我们可以忽略的问题gamma。

如果我observe 1，我可以go要么stop。那utility/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)如果它的解决方案中有自己的定义，我不确定如何解决。这可能是由于糟糕的数学背景。

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

具体来说，如果滚动三给了您$3而滚动一结束了游戏，那将影响您的决定，因为实用程序已更改。

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

有人可以解释动态编程是如何工作的吗？我该如何解决Q(1,g)或Q(1,s)当它在自己的定义中？

4

1 回答 1

3

特殊解决方案：

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

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

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

于 2017-08-26T18:22:17.413 回答