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

Question

关闭。这个问题需要debugging details .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

7年前关闭。




Improve this question




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

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

说他尝试给定 Action 的 70% 的时间都会成功是什么意思？这是否意味着每次他尝试执行 Action A 时，70% 的时间都会执行该 Action A，而另外 30% 的时间会执行导致相同状态的 Action ，或者就好像他一直都在做行动 A，但只有 30% 的时候他不这样做？我希望我说清楚:(

怎么可能有多个具有相同效用的连续状态？理论上，效用不应该总是减少，你离有奖励的状态越远？

只知道我上面提供的信息，
是否有可能推断出什么是
折扣因子( Gamma )？如果是，如何？

是否可以计算
国家的奖励？如何？

Answer 1

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

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

从长远来看，这些类型问题的目标往往是，您如何最大化您的预期(长期)返回？学习率 gamma 控制您对当前状态的重视程度与您希望结束的位置 - 实际上，您可以将 gamma 视为一个范围，从“在此时间步中做对我最有利的事情”到在另一个极端“探索我所有的选择，然后回到最好的选择”。萨顿和巴托在那里预订 reinforcement learning有一些非常好的explanations这是如何工作的。

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

什么是状态？有多少个州？

什么是 Action ？有多少 Action ？

如果您从状态 u 开始，并应用一个 Action a，那么到达新状态 v 的概率是多少？

那么问题的答案呢？

状态是向量 (x,y)。网格是 5 x 5，所以有 25 个状态。

有四种可能的操作，{E,N,S,W}

应用合适的 Action 后成功到达相邻状态的概率为0.7，不动的概率(保持在同一状态为0.3)。假设 (0,0) 是左上角的单元格，(4,4) 是右下角的单元格，下表显示了所有可能转换的一小部分。

开始状态 Action 最终状态概率
-------------------------------------------------- ——
(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 个 Action ，因此该表应该有 100 个条目。

检查以确保对于开始状态/ Action 对，只有两个条目具有非零发生概率。

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

v 是最终状态

u 是源状态

a 是 Action ，如果没有提及，则暗示所应用的 Action 不相关。

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