马尔可夫决策过程的问题

Question

alt text http://img693.imageshack.us/img693/724/markov.png

关于这里的一些观点,我有点困惑:

1. 说70%的时间他会尝试某项行动会成功是什么意思？这是否意味着每次他尝试执行动作A时,70%的时间会执行该动作A而另外30%执行导致相同状态的动作,或者就像他总是这样做行动A,但只有30%的时间他没有做到这一点？我希望我能让自己清楚:(
2. 如何使用相同的实用程序连续几个状态？理论上,效用不应该总是减少,你离奖励的国家越远？
3. 只知道我上面给出的信息,是否有可能推断出什么是折扣因子(gamma)？如果有,怎么样？
4. 是否可以计算各州的奖励？怎么样？

Answer 1

处理大多数 MDP 问题都有一个模式，但我认为您可能在问题描述中省略了一些信息，很可能它与您试图达到的状态或情节结束的方式有关（什么）如果您跑出网格边缘就会发生）。我已尽力回答您的问题，但我还附加了关于我用来处理此类问题的过程的入门知识。

首先，效用是一个相当抽象的衡量标准，衡量你想要处于给定状态的程度。即使您使用简单的启发式方法（欧几里得距离或曼哈顿距离）来衡量效用，也绝对有可能拥有两个具有相同效用的状态。在这种情况下，我假设效用价值和奖励是可以互换的。

从长远来看，此类问题的目标往往是，如何最大化预期（长期）回报？学习率，伽玛，控制着你对当前状态与你想要的最终状态的重视程度 - 实际上，你可以将伽玛视为一个范围，从“在这个时间步中做对我最有利的事情”到在另一个极端“探索我所有的选择，然后回到最好的”。Sutton 和 Barto 在关于强化学习的书中对它的工作原理有一些非常好的解释。

在开始之前，请回顾一下问题并确保您可以自信地回答以下问题。

1. 什么是国家？有多少个州？
2. 什么是行动？有多少个动作？
3. 如果从状态 u 开始，并应用操作 a，达到新状态 v 的概率是多少？

那么问题的答案呢？

1. 状态是一个向量 (x,y)。网格是 5 x 5，因此有 25 个状态。
2. 有四种可能的动作，{E,N,S,W}
3. 应用适当的动作后成功到达相邻状态的概率为 0.7，不移动（保持相同状态的概率为 0.3）。假设 (0,0) 是左上角的单元格，(4,4) 是右下角的单元格，下表显示了所有可能转换的一小部分。

开始状态 动作 最终状态 概率
-------------------------------------------------- -
(0,0) E (0,0) 0.3
(0,0) E (1,0) 0.7
(0,0) E (2,0) 0
...
(0,0) E (0,1) 0
...
(0,0) E (4,4) 0
(0,0) N (0,0) 0.3
...
(4,4) W (3,4) 0.7
(4,4) W (4,4) 0.3

我们如何检查这对于这个问题是否有意义？

1. 检查表中是否有适当数量的条目。在 5 x 5 网格上有 25 个状态和 4 个操作，因此该表应有 100 个条目。
2. 检查以确保对于开始状态/操作对，只有两个条目的发生概率非零。

编辑。回答对目标状态的转移概率的请求。下面的符号假设

• v 是最终状态
• u 是源状态
• a 是操作，如果未提及，则暗示所应用的操作不相关。

P( v=(3,3) | u =(2,3), a=E ) = 0.7
P( v=(3,3) | u =(4,3), a=W ) = 0.7
P( v=(3,3) | u =(3,2), a=N ) = 0.7
P( v=(3,3) | u =(3,4), a=S ) = 0.7
P( v=(3,3) | u =(3,3) ) = 0.3