algorithm - 马尔可夫决策过程：价值迭代，它是如何工作的？

Question

最近我读了很多关于马尔可夫决策过程（使用价值迭代）的文章，但我根本无法理解它们。我在互联网/书籍上找到了很多资源，但它们都使用了对我的能力来说太复杂的数学公式。

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

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

据我了解，MDP的粗鲁简化是它们可以创建一个网格，该网格保持我们需要去的方向（一种“箭头”网格，指向我们需要去的地方，从网格上的某个位置开始) 达到某些目标并避免某些障碍。具体到我的情况，这意味着它可以让玩家知道往哪个方向去收集硬币并避开敌人。

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

这个对吗？还是我完全走错了路？

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

（摘自 Russell & Norvig 的《人工智能 - 一种现代方法》一书）

我知道这s将是网格中所有方块的列表，a将是一个特定的动作（上/下/右/左），但其余的呢？

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

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

感谢您的宝贵时间。

（注意：随时添加/删除标签或在评论中告诉我是否应该提供有关某事或类似内容的更多详细信息。）

Answer 1

是的，数学符号可以使它看起来比实际复杂得多。真的，这是一个非常简单的想法。我已经实现了一个值迭代演示小程序，您可以使用它来获得更好的想法。

基本上，假设您有一个带有机器人的 2D 网格。机器人可以尝试向北、向南、向东、向西移动（这些是动作 a），但是因为它的左轮很滑，所以当它试图向北移动时，它最终到达正方形的概率只有 0.9在它的北边，而它有 0.1 的概率最终会在它的西边的方格处（与其他 3 个动作类似）。这些概率由 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 

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

价值迭代所做的是它首先给目标状态的效用 100 和所有其他状态的效用 0。然后在第一次迭代中，这 100 个效用从目标开始向后分配 1 步，因此所有可以在 1 步内到达目标状态的状态（紧邻它的所有 4 个方格）都将获得一些效用。也就是说，他们将获得一个效用，该效用等于从该状态我们可以达到所述目标的概率。然后我们继续迭代，在每一步我们将实用程序从目标移回 1 步。

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

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

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

因为在 5,6 上，如果你向北走，有 0.9 的概率最终到达 5,5，而如果你向西走，有 0.1 的概率最终到达 5,5。

(5,4)、(4,5)、(6,5) 也是如此。

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

Answer 2

我建议您使用 Q-learning 进行实施。

也许你可以用我写的这篇文章作为灵感。这是一个带有 Java 源代码的 Q-learning 演示。这个演示是一个包含 6 个字段的地图，AI 学习它应该从每个状态到哪里去获得奖励。

Q-learning是一种通过给予奖励或惩罚让人工智能自行学习的技术。

这个例子展示了用于路径查找的 Q 学习。机器人从任何状态学习它应该去哪里。

机器人从一个随机的地方开始，它在探索该区域时会记住分数，每当它到达目标时，我们都会重复一个新的随机开始。在足够的重复之后，得分值将是固定的（收敛）。

在这个例子中，动作结果是确定性的（转移概率为 1），动作选择是随机的。分数值由 Q 学习算法 Q(s,a) 计算。
该图显示了状态（A、B、C、D、E、F）、来自这些状态的可能动作和给予的奖励。

结果 Q*(s,a)

政策 Π*(s)

Qlearning.java

import java.text.DecimalFormat;
import java.util.Random;

/**
 * @author Kunuk Nykjaer
 */
public class Qlearning {
    final DecimalFormat df = new DecimalFormat("#.##");

    // path finding
    final double alpha = 0.1;
    final double gamma = 0.9;


// states A,B,C,D,E,F
// e.g. from A we can go to B or D
// from C we can only go to C
// C is goal state, reward 100 when B->C or F->C
//
// _______
// |A|B|C|
// |_____|
// |D|E|F|
// |_____|
//

    final int stateA = 0;
    final int stateB = 1;
    final int stateC = 2;
    final int stateD = 3;
    final int stateE = 4;
    final int stateF = 5;

    final int statesCount = 6;
    final int[] states = new int[]{stateA,stateB,stateC,stateD,stateE,stateF};

    // http://en.wikipedia.org/wiki/Q-learning
    // http://people.revoledu.com/kardi/tutorial/ReinforcementLearning/Q-Learning.htm

    // Q(s,a)= Q(s,a) + alpha * (R(s,a) + gamma * Max(next state, all actions) - Q(s,a))

    int[][] R = new int[statesCount][statesCount]; // reward lookup
    double[][] Q = new double[statesCount][statesCount]; // Q learning

    int[] actionsFromA = new int[] { stateB, stateD };
    int[] actionsFromB = new int[] { stateA, stateC, stateE };
    int[] actionsFromC = new int[] { stateC };
    int[] actionsFromD = new int[] { stateA, stateE };
    int[] actionsFromE = new int[] { stateB, stateD, stateF };
    int[] actionsFromF = new int[] { stateC, stateE };
    int[][] actions = new int[][] { actionsFromA, actionsFromB, actionsFromC,
            actionsFromD, actionsFromE, actionsFromF };

    String[] stateNames = new String[] { "A", "B", "C", "D", "E", "F" };

    public Qlearning() {
        init();
    }

    public void init() {       
        R[stateB][stateC] = 100; // from b to c
        R[stateF][stateC] = 100; // from f to c    
    }

    public static void main(String[] args) {
        long BEGIN = System.currentTimeMillis();

        Qlearning obj = new Qlearning();

        obj.run();
        obj.printResult();
        obj.showPolicy();

        long END = System.currentTimeMillis();
        System.out.println("Time: " + (END - BEGIN) / 1000.0 + " sec.");
    }

    void run() {
        /*
         1. Set parameter , and environment reward matrix R
         2. Initialize matrix Q as zero matrix
         3. For each episode: Select random initial state
            Do while not reach goal state o
                Select one among all possible actions for the current state o
                Using this possible action, consider to go to the next state o
                Get maximum Q value of this next state based on all possible actions o
                Compute o Set the next state as the current state
         */

        // For each episode
        Random rand = new Random();
        for (int i = 0; i < 1000; i++) { // train episodes
            // Select random initial state
            int state = rand.nextInt(statesCount);
            while (state != stateC) // goal state
            {
                // Select one among all possible actions for the current state
                int[] actionsFromState = actions[state];

                // Selection strategy is random in this example
                int index = rand.nextInt(actionsFromState.length);
                int action = actionsFromState[index];

                // Action outcome is set to deterministic in this example
                // Transition probability is 1
                int nextState = action; // data structure

                // Using this possible action, consider to go to the next state
                double q = Q(state, action);
                double maxQ = maxQ(nextState);
                int r = R(state, action);

                double value = q + alpha * (r + gamma * maxQ - q);
                setQ(state, action, value);

                // Set the next state as the current state
                state = nextState;
            }
        }
    }

    double maxQ(int s) {
        int[] actionsFromState = actions[s];
        double maxValue = Double.MIN_VALUE;
        for (int i = 0; i < actionsFromState.length; i++) {
            int nextState = actionsFromState[i];
            double value = Q[s][nextState];

            if (value > maxValue)
                maxValue = value;
        }
        return maxValue;
    }

    // get policy from state
    int policy(int state) {
        int[] actionsFromState = actions[state];
        double maxValue = Double.MIN_VALUE;
        int policyGotoState = state; // default goto self if not found
        for (int i = 0; i < actionsFromState.length; i++) {
            int nextState = actionsFromState[i];
            double value = Q[state][nextState];

            if (value > maxValue) {
                maxValue = value;
                policyGotoState = nextState;
            }
        }
        return policyGotoState;
    }

    double Q(int s, int a) {
        return Q[s][a];
    }

    void setQ(int s, int a, double value) {
        Q[s][a] = value;
    }

    int R(int s, int a) {
        return R[s][a];
    }

    void printResult() {
        System.out.println("Print result");
        for (int i = 0; i < Q.length; i++) {
            System.out.print("out from " + stateNames[i] + ":  ");
            for (int j = 0; j < Q[i].length; j++) {
                System.out.print(df.format(Q[i][j]) + " ");
            }
            System.out.println();
        }
    }

    // policy is maxQ(states)
    void showPolicy() {
        System.out.println("\nshowPolicy");
        for (int i = 0; i < states.length; i++) {
            int from = states[i];
            int to =  policy(from);
            System.out.println("from "+stateNames[from]+" goto "+stateNames[to]);
        }          
    }
}

打印结果

out from A:  0 90 0 72,9 0 0
out from B:  81 0 100 0 81 0
out from C:  0 0 0 0 0 0
out from D:  81 0 0 0 81 0
out from E:  0 90 0 72,9 0 90
out from F:  0 0 100 0 81 0

showPolicy
from a goto B
from b goto C
from c goto C
from d goto A
from e goto B
from f goto C
Time: 0.025 sec.

Answer 3

不是一个完整的答案，而是一个澄清的评论。

状态不是单个单元格。状态包含所有相关单元格的每个单元格中的信息。这意味着一个状态元素包含哪些单元格是实心的，哪些是空的；哪些包含怪物；硬币在哪里；玩家在哪里。

也许您可以使用从每个单元格到其内容的地图作为状态。这确实忽略了怪物和玩家的移动，这可能也很重要。

细节取决于你想如何建模你的问题（决定什么属于状态以及以何种形式）。

然后策略将每个状态映射到左、右、跳跃等动作。

首先，您必须先了解 MDP 所表达的问题，然后再考虑诸如值迭代之类的算法是如何工作的。

Answer 4

我知道这是一篇相当老的帖子，但我在寻找与 MDP 相关的问题时遇到了它，我确实想指出（对于来到这里的人）关于你何时说出“s”和“a”是什么的更多评论.

我认为你是绝对正确的，这是你的[上、下、左、右]列表。

但是对于 s 来说，它实际上是网格中的位置，而 s' 是您可以去的位置。这意味着你选择一个状态，然后你选择一个特定的 s' 并执行所有可以带你到那个 sprime 的操作，你用它来计算这些值。（从中挑选一个最大值）。最后你去寻找下一个 s' 并做同样的事情，当你用尽所有 s' 值时，你会找到你刚刚完成搜索的最大值。

假设您在角落选择了一个网格单元，您只有 2 个可以移动到的状态（假设左下角），这取决于您选择如何“命名”您的状态，在这种情况下，我们可以假设一个状态是一个 x,y 坐标，因此您当前的状态 s 是 1,1 并且您的 s' （或 s 素数）列表是 x+1,y 和 x,y+1 （在本例中没有对角线）（求和部分在所有 s')

你也没有在你的方程中列出它，但是最大值是 a 或给你最大值的动作，所以首先你选择给你最大值的 s' 然后在其中你选择动作（至少这是我对算法的理解）。

所以如果你有

x,y+1 left = 10 
x,y+1 right = 5 

x+1,y left = 3
x+1,y right 2

您将选择 x,y+1 作为您的 s'，但随后您需要选择一个最大化的动作，在这种情况下留给 x,y+1。我不确定仅找到最大数量和找到状态然后找到最大数量之间是否存在细微差别，所以也许有一天有人可以为我澄清这一点。

如果你的动作是确定性的（意思是如果你说前进，你会 100% 确定地前进），那么你很容易有一个动作，但是如果它们是非确定性的，你有 80% 的确定性，那么你应该考虑其他可以让你到达那里的行动。这是何塞上面提到的滑轮的背景。

我不想贬低其他人所说的话，而只是提供一些额外的信息。