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

Ответ 1

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

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

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

На первой итерации положим

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

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

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

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

Ответ 2

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

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

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

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

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

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

Ответ 3

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

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

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.

Ответ 4

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

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

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

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

Также вы не указали его в своем уравнении, но max имеет значение или действие, которое дает вам максимальное значение, поэтому сначала вы выбираете s ', который дает вам max, а затем внутри, что вы выбираете действие (по крайней мере, это мое понимание алгоритма).

Итак, если у вас

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

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