Марковский процесс принятия решений: итерация значений, как это работает?

Да, из-за математической записи это может показаться намного сложнее, чем оно есть на самом деле. На самом деле, это очень простая идея. Я реализовал демонстрационный апплет итерации значений, с которым вы можете поиграть, чтобы получить лучшее представление.

По сути, допустим, у вас есть 2D-сетка с роботом в ней. Робот может попытаться двигаться на север, юг, восток, запад (это действия а), но, поскольку его левое колесо скользкое, когда он пытается двигаться на север, вероятность того, что он окажется на квадрате, равна всего 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 

Затем вы устанавливаете вознаграждение равным 0 для всех состояний и 100 для целевого состояния, то есть места, в которое вы хотите, чтобы робот попал.

Что делает итерация ценности, так это то, что она начинается с придания полезности 100 целевому состоянию и 0 всем остальным состояниям. Затем на первой итерации эти 100 единиц полезности распределяются обратно на 1 шаг от цели, поэтому все состояния, которые могут достичь целевого состояния за 1 шаг (все 4 квадрата рядом с ним), получат некоторую полезность. А именно, они получат Полезность, равную вероятности того, что из этого состояния мы сможем добраться до заявленной цели. Затем мы продолжаем итерацию, на каждом шаге отодвигая утилиту еще на 1 шаг от цели.

Предположим, что в приведенном выше примере вы начинаете с R(5,5)=100 и R(.)=0 для всех остальных состояний. Так что цель - дойти до 5,5.

На первой итерации мы установили

R(5,6) = гамма * (0,9 * 100) + гамма * (0,1 * 100)

потому что на 5,6, если вы пойдете на север, есть вероятность 0,9 оказаться в 5,5, а если вы пойдете на запад, есть вероятность 0,1 оказаться в 5,5.

Аналогично для (5,4), (4,5), (6,5).

Все остальные состояния остаются с U = 0 после первой итерации итерации значения.

Не полный ответ, а уточняющее замечание.

состояние — это не отдельная ячейка. Состояние содержит информацию о том, что находится в каждой ячейке сразу для всех заинтересованных ячеек. Это означает, что один элемент состояния содержит информацию о том, какие ячейки сплошные, а какие пустые; какие из них содержат монстров; где монеты; где игрок.

Возможно, вы могли бы использовать карту каждой ячейки с ее содержимым в качестве состояния. Это игнорирует движение монстров и игрока, что, вероятно, тоже очень важно.

Детали зависят от того, как вы хотите смоделировать свою проблему (решив, что относится к состоянию и в какой форме).

Затем политика сопоставляет каждое состояние с действием, например влево, вправо, прыжок и т. д.

Сначала вы должны понять проблему, которую выражает MDP, прежде чем думать о том, как работают алгоритмы, такие как итерация значений.

Я бы рекомендовал использовать Q-learning для вашей реализации.

Может быть, вы можете использовать этот пост, который я написал, как источник вдохновения. Это демонстрация Q-learning с исходным кодом Java. Эта демонстрация представляет собой карту с 6 полями, и ИИ узнает, куда он должен идти из каждого состояния, чтобы получить награду.

Q-обучение — это метод, позволяющий ИИ учиться самому, вознаграждая его или наказывая.

В этом примере показано 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.

Я знаю, что это довольно старый пост, но я наткнулся на него, когда искал вопросы, связанные с MDP, я хотел отметить (для людей, заходящих сюда) еще несколько комментариев о том, когда вы указали, что такое «s» и «a». .

Я думаю, что вы абсолютно правы, это ваш список [вверх, вниз, влево, вправо].

Однако для s это действительно место в сетке, а s' — это место, куда вы можете попасть. Это означает, что вы выбираете состояние, а затем выбираете конкретное s и выполняете все действия, которые могут привести вас к этому спрайму, который вы используете для определения этих значений. (выберите максимальное из них). Наконец, вы переходите к следующему s и делаете то же самое, когда вы исчерпали все значения s, вы найдете максимум того, что вы только что закончили искать.

Предположим, вы выбрали ячейку сетки в углу, у вас было бы только 2 состояния, в которые вы могли бы перейти (при условии, что нижний левый угол), в зависимости от того, как вы решите «назвать» свои состояния, мы могли бы в этом случае предположить, что состояние координата x, y, поэтому ваше текущее состояние s равно 1,1, а ваш список s (или простое число s) равен x + 1, y и x, y + 1 (в этом примере нет диагонали) (часть суммирования, которая идет над всем)

Кроме того, вы не указали это в своем уравнении, но максимум представляет собой действие, которое дает вам максимум, поэтому сначала вы выбираете 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% уверенность, другие действия, которые могут привести вас к этому. Это контекст скользкого колеса, о котором упоминал Хосе выше.

Я не хочу умалять то, что сказали другие, а просто хочу дать некоторую дополнительную информацию.