artificial-intelligence - 马尔可夫决策过程的问题

Question

替代文字 http://img693.imageshack.us/img693/724/markov.png

我对这里的一些观点有点困惑：

70% 的时间他尝试一个给定的动作都会成功是什么意思？这是否意味着每次他尝试执行动作 A 时，70% 的时间会执行该动作 A，而另外 30% 的时间会执行导致相同状态的动作，或者只是好像他总是这样做动作 A，但只有 30% 的时间他不这样做？我希望我让自己清楚:(
怎么可能有几个具有相同效用的连续状态？从理论上讲，效用不应该总是减少，你离奖励的州越远？
只知道我上面给出的信息，是否可以推断出折扣因子（gamma）是多少？如果是，如何？
是否可以计算各州的奖励？如何？

score 4 · Accepted Answer

处理大多数 MDP 问题都有一种模式，但我认为您可能在问题描述中遗漏了一些信息，很可能与您尝试达到的状态或情节结束的方式有关（什么如果您跑出网格边缘，就会发生这种情况）。我已尽我所能回答您的问题，但我已经附加了我用来处理这些类型问题的过程的入门。

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

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

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

什么是状态？有多少个州？
什么是动作？有多少个动作？
如果你从状态 u 开始，并应用一个动作 a，那么到达新状态 v 的概率是多少？

那么问题的答案呢？

状态是一个向量 (x,y)。网格是 5 x 5，所以有 25 个州。
有四种可能的动作，{E,N,S,W}
应用适当动作后成功到达相邻状态的概率为 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) 瓦 (3,4) 0.7
(4,4) 瓦 (4,4) 0.3

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

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

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

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