De Markov, Processus de prise de Décision: la valeur de l'itération, comment ça fonctionne?

Je recommande l'utilisation de Q-learning pour votre mise en œuvre.

Peut-être vous pouvez utiliser ce post que j'ai écrit comme une source d'inspiration. C'est un Q-l'apprentissage de la démo avec le code source Java. Cette démo est une carte avec 6 champs et l'IA apprend d'où il devrait aller de chaque etat pour obtenir la récompense.

Q-learning est une technique pour laisser l'IA apprendre par lui-même en lui donnant la récompense ou le châtiment.

Cet exemple illustre le Q-learning utilisé pour la découverte de parcours. Un robot apprend d'où il devrait aller de n'importe quel état.

Le robot commence à un endroit aléatoire, il garde la mémoire de la partition, tout en explorant la région, chaque fois qu'il atteint l'objectif, nous le répétons avec un nouveau départ aléatoire. Après un nombre suffisant de répétitions, les valeurs de score sera stationnaire (convergence).

Dans cet exemple, les conséquences de l'action est déterministe (probabilité de transition est de 1) et de la sélection de l'action est aléatoire. Le score valeurs sont calculées par le Q-learning de l'algorithme de Q(s,a).

L'image montre les états (A,B,C,D,E,F), les actions possibles de la part des états et de la récompense donnée.

Résultat Q*(s,a)

Politique Π*(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]);
        }          
    }
}

Résultat d'impression

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.

Je sais que c'est un assez vieux post, mais je suis tombé sur elle lors de la recherche pour les MDP des questions, je ne veux noter (pour les gens à venir ici) un peu plus de commentaires sur lorsque vous avez déclaré que "s" et "a" ont été.

Je pense que pour un vous avez absolument raison, c'est votre liste de [haut,bas,gauche,droite].

Cependant, pour s c'est vraiment l'emplacement de la grille et de s' agit de l'emplacement, vous pouvez aller à.
Ce que cela signifie est que vous chercher un etat, et ensuite, vous choisissez un particulier s' et passer par toutes les actions que vous pouvez prendre pour que sprime, que vous utilisez pour déterminer ces valeurs. (ramasser un max de personnes). Enfin, vous allez pour la prochaine s' et faire la même chose, lorsque vous avez épuisé toutes le s' valeurs alors vous trouver le max de ce que vous venez de terminer la recherche.

Supposons que vous avez choisi une cellule de la grille dans le coin, vous voudriez en avoir seulement 2 états, vous pourrait éventuellement passer à (en supposant coin en bas à gauche), en fonction de la façon dont vous choisissez de le "nom" de votre état, nous pourrions, dans ce cas, supposons qu'un état est une coordonnée x,y, de sorte que votre état actuel s est de 1,1 et votre s' (ou s le premier) de la liste est x+1,y et x,y+1 (pas de diagonale dans cet exemple) (La Somme de la partie qui va sur tous les s')

Aussi vous ne l'avez indiqué dans votre équation, mais le max est de l'un ou de l'action qui vous donne le max, donc tout d'abord à vous de choisir le s " qui vous donne le maximum et puis à l'intérieur de vous de choisir l'action (au moins c'est ma compréhension de l'algorithme).

Donc, si vous aviez

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

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

Vous allez choisir x,y+1 comme s', mais alors vous aurez besoin de choisir une action qui est maximisée, ce qui est dans ce cas gauche pour x,y+1. Je ne sais pas si il y a une subtile différence entre juste de trouver le nombre maximum et de trouver de l'état, puis le nombre maximum mais peut-être quelqu'un un jour peut préciser que pour moi.

Si vos mouvements sont déterministes (sens si vous dire d'aller de l'avant, vous aller de l'avant avec 100% de certitude), alors il est assez facile, vous avez une action, mais s'ils sont non déterministes, vous avez un mot à dire 80% de certitude, alors vous devriez envisager d'autres actions qui pourrait vous y arrivez. C'est le contexte de glissement de la roue que Jose mentionnés ci-dessus.

Je ne veux pas porter atteinte à ce que les autres ont dit, mais juste pour donner quelques informations supplémentaires.