procesos de decisión de Markov preguntas [cerrada]

Question

alt text http://img693.imageshack.us/img693/724/markov .png

Estoy un poco confundido acerca de algunos puntos aquí:

1. ¿Qué significa decir que va a ser un éxito del 70% de las veces se trata de una acción determinada? ¿Quiere decir que cada vez que intenta llevar a cabo una acción A, que será el 70% del tiempo hacer que la acción A y el otro 30% no la acción que lleva al mismo estado, o simplemente que es como si siempre lo hicieron A la acción, pero sólo el 30% de las veces que simplemente no lo hace? Espero que estoy siendo claro: (
2. ¿Cómo es posible tener varios estados consecutivos con la misma utilidad? En la teoría de la utilidad no siempre debe disminuir, cuanto más lejos se está de estados con una recompensa?
3. conociendo sólo la info me dio anteriormente, es posible inferir cuál es la factor de descuento (gamma)? En caso afirmativo, ¿cómo?
4. ¿Es posible calcular el Recompensa por los estados? ¿Cómo?

Answer 1

Hay un patrón para hacer frente a la mayoría de los problemas de MDP, pero creo que probablemente ha omitido alguna información de la descripción del problema, lo más probable es que tiene que ver con el estado que está tratando de alcanzar, o la forma en un episodio extremos (lo que ocurre si se ejecuta fuera del borde de la red). He hecho todo lo posible para responder a sus preguntas, pero he anexado una cartilla sobre el proceso que utilizo para hacer frente a este tipo de problemas.

En primer lugar utilidad es una medida bastante abstracta de la cantidad que desea estar en un estado determinado. Definitivamente es posible tener dos estados con la misma utilidad, incluso cuando se mide con la utilidad heurística simple (euclidiana o la distancia de Manhattan). En este caso, supongo que el valor de utilidad y la recompensa son intercambiables.

A largo plazo, el objetivo de este tipo de problemas tiende a ser, ¿Cómo maximizar su recompensa esperada (a largo plazo)? La tasa de aprendizaje, gamma, controla la cantidad de énfasis que el lugar sobre el estado actual frente a donde le gustaría terminar - con eficacia que se pueda imaginar gamma como un espectro que va desde, 'Haz lo que los beneficios que más me en este paso de tiempo' a en el otro extremo < em> 'explorar todas mis opciones, y volver a la mejor' . Sutton y Barto allí libro sobre aprendizaje por refuerzo tener algún realmente agradables explicaciones de cómo funciona este.

---

Antes de empezar, volver a través de la pregunta y asegúrese de que se puede responder con seguridad a las siguientes preguntas.

1. ¿Qué es un estado? ¿Cuántos estados hay?
2. ¿Qué es una acción? Cuántas acciones hay?
3. Si se inicia en u estado, y se aplica una acción a, ¿cuál es la probabilidad de alcanzar un nuevo estado v?

Así que las respuestas a las preguntas?

1. Un estado es un vector (x, y). La rejilla es de 5 por 5, por lo que hay 25 estados.
2. Hay cuatro acciones posibles, {E, N, S, W}
3. La probabilidad de alcanzar con éxito un estado adyacente después de aplicar una acción adecuada es 0,7, la probabilidad de no se mueve (permanecer en el mismo estado es 0,3). Suponiendo (0,0) es la celda superior izquierda y (4,4) es la célula inferior derecha, muestra la siguiente tabla un pequeño subconjunto de todas las posibles transiciones.

Start State Action           Final State    Probability
---------------------------------------------------
(0,0)           E               (0,0)          0.3
(0,0)           E               (1,0)          0.7
(0,0)           E               (2,0)          0
...
(0,0)           E               (0,1)          0
... 
(0,0)           E               (4,4)          0
(0,0)           N               (0,0)          0.3
...
(4,4)           W               (3,4)          0.7
(4,4)           W               (4,4)          0.3

¿Cómo podemos comprobar que esto tiene sentido para este problema?

1. Compruebe que la tabla tiene un número apropiado de entradas. En una cuadrícula de 5 x 5 hay 25 estados y 4 acciones, por lo que la tabla debe tener 100 entradas.
2. Asegúrese de que para un par estado de inicio / acción, sólo dos entradas tienen probabilidad no nula de occuring.

---

Editar. responder a la solicitud de las probabilidades de transición a el estado objetivo. La notación siguiente se supone

• v es el estado final
• u es el Estado de la fuente
• a es la acción, en el que no se menciona, se da a entender que la acción aplicada no es relevante.

P( v=(3,3) | u =(2,3), a=E ) = 0.7
P( v=(3,3) | u =(4,3), a=W ) = 0.7
P( v=(3,3) | u =(3,2), a=N ) = 0.7
P( v=(3,3) | u =(3,4), a=S ) = 0.7
P( v=(3,3) | u =(3,3) ) = 0.3

Answer 2

AD.1) probablemente no es que siempre robot tiene que mover - es decir, los 30% son "ah, ahora descansar un poco" o "no había poder moverse en absoluto ".

Answer 3

he formulado este problema como un proceso finito Decisión-Horizonte Markov y lo resolvió mediante la Directiva de la iteración. A la derecha de cada iteración, hay una representación cuadrícula con código de color de las acciones recomendadas para cada estado así como la red de recompensa / matriz original.

Revisar la política / estrategia final en la Etapa 4. ¿Está de acuerdo con su intuición?