algorithm - Markov Decision Process : value iteration, 它是如何工作的？

Question

我已经阅读了很多关于 Markov Decision Processes (using value iteration) 的内容最近，但我根本无法理解它们。我在互联网/书籍上找到了很多资源，但它们都使用了对我的能力来说太复杂的数学公式。

由于这是我上大学的第一年，我发现网上提供的解释和公式使用的概念/术语对我来说太复杂了，而且他们假设读者知道某些我只是简单了解的事情没听说过。

我想在 2D 网格上使用它(充满墙壁(无法到达)、硬币(理想)和移动的敌人(必须不惜一切代价避免))。整个目标是在不接触敌人的情况下收集所有硬币，我想使用马尔可夫决策过程 (MDP) 为主要玩家创建一个 AI。下面是它的部分样子(请注意，与游戏相关的方面在这里并不是一个很重要的问题。我真的很想总体上了解 MDP):

据我所知，MDP 的粗略简化是它们可以创建一个网格，该网格包含我们需要前进的方向(类似于“箭头”网格，指向我们需要去的地方走，从网格上的特定位置开始)以达到特定目标并避开特定障碍。具体到我的情况，这意味着它可以让玩家知道去哪个方向收集硬币并避开敌人。

现在，使用 MDP 术语，这意味着它创建了一个状态集合(网格)，其中包含某些策略(要采取的操作 -> 上、下、右、左)对于某个状态(网格上的一个位置)。这些政策由每个州的“效用”值决定，这些值本身是通过评估到达那里在短期和长期内会带来多少好处来计算的。

这是正确的吗？还是我完全走错了路？

我至少想知道以下等式中的变量在我的情况下代表什么:

(摘自 Russell & Norvig 的《人工智能——现代方法》一书)

我知道 s 将是网格中所有方 block 的列表，a 将是一个特定的 Action (上/下/右/左)，但是剩下的呢？

如何实现奖励和效用函数？

如果有人知道一个简单的链接，它显示伪代码以非常缓慢的方式实现与我的情况相似的基本版本，那就太好了，因为我什至不知道从哪里开始。

感谢您抽出宝贵的时间。

(注意:请随意添加/删除标签或在评论中告诉我是否应该提供有关某事或类似事情的更多详细信息。)

Answer 1

是的，数学符号可以让它看起来比实际上复杂得多。真的，这是一个非常简单的想法。我有一个实现 value iteration demo applet你可以玩玩以获得更好的想法。

基本上，假设您有一个二维网格，其中有一个机器人。机器人可以尝试向北、向南、向东、向西移动(这些是 Action a)但是，因为它的左轮很滑，当它向北移动时，它最终到达正方形的概率只有 0.9在它的北边，而它有 0.1 的概率会在它的西边的方格处结束(对于其他 3 个 Action 也是如此)。这些概率由 T() 函数捕获。也就是说，T(s,A,s') 看起来像:

s    A      s'     T    //x=0,y=0 is at the top-left of the screen
x,y  North  x,y+1  .9   //we do move north
x,y  North  x-1,y  .1   //wheels slipped, so we move West
x,y  East   x+1,y  .9
x,y  East   x,y-1  .1
x,y  South  x,y+1  .9
x,y  South  x-1,y  .1 
x,y  West   x-1,y  .9
x,y  West   x,y+1  .1 

然后，您将所有状态的奖励设置为 0，但目标状态(即您希望机器人到达的位置)设置为 100。

值迭代的作用是首先为目标状态提供 100 的效用，为所有其他状态提供 0。然后在第一次迭代中，这 100 个效用会从目标返回 1 步，因此所有可以在 1 步内到达目标状态的状态(紧邻它的所有 4 个方 block )都将获得一些效用。即，他们将获得一个效用，该效用等于从该状态我们可以达到所述目标的概率。然后我们继续迭代，在每一步我们将实用程序从目标移回 1 步。

在上面的示例中，假设您从 R(5,5)= 100 开始，对于所有其他状态，R(.) = 0。所以目标是达到 5,5。

在我们设置的第一次迭代中

R(5,6) = Gamma * (.9 * 100) + Gamma * (.1 * 100)

因为在 5,6 上，如果您向北走，则有 0.9 的概率以 5,5 结束，而如果您向西走，则以 0.1 的概率以 5,5 结束。

与 (5,4)、(4,5)、(6,5) 类似。

所有其他状态在值迭代的第一次迭代后保持 U = 0。