Hay un patrón para manejar la mayoría de los problemas MDP, pero creo que probablemente haya omitido alguna información de la descripción del problema, lo más probable es que tenga que ver con el estado al que intenta llegar o la forma en que el episodio termina (lo que sucede si te escapas del borde de la cuadrícula). Hice todo lo posible por responder a sus preguntas, pero agregué una introducción al proceso que utilizo para tratar este tipo de problemas.
En primer lugar, la utilidad es una medida bastante abstracta de cuánto desea estar en un estado determinado. Definitivamente es posible tener dos estados con la misma utilidad, incluso cuando se mide la utilidad con heurística simple (distancia euclidiana o de Manhattan). En este caso, supongo que el valor de la utilidad y la recompensa son intercambiables.
A largo plazo, el objetivo en este tipo de problemas suele ser ¿cómo se maximiza la recompensa esperada (a largo plazo)? La tasa de aprendizaje, gamma, controla cuánto énfasis pone en el estado actual frente a dónde le gustaría terminar; efectivamente, puede pensar en gamma como un espectro que va desde 'hacer lo que más me beneficia en este intervalo de tiempo ' en el otro extremo ' explorar todas mis opciones, y volver a la mejor '. Sutton y Barto en el libro allí en reinforcement learning tienen algunos muy buenos explanations de cómo funciona esto.
Antes de empezar, repase la pregunta y asegúrese de que puede responder con confianza a las siguientes preguntas.
- ¿Qué es un estado? ¿Cuántos estados hay?
- ¿Qué es una acción? ¿Cuántas acciones hay?
- Si comienza en el estado u, y aplica una acción a, ¿cuál es la probabilidad de alcanzar un nuevo estado v?
¿Entonces las respuestas a las preguntas?
- Un estado es un vector (x, y). La cuadrícula es 5 por 5, por lo que hay 25 estados.
- Hay cuatro acciones posibles, {E, N, S, W}
- La probabilidad de alcanzar con éxito un estado adyacente después de aplicar una acción adecuada es 0,7, la probabilidad de no moverse (permanecer en el mismo estado es 0,3) Asumiendo (0,0) es la celda superior izquierda y (4,4) es la celda inferior derecha, la siguiente tabla muestra un pequeño subconjunto de todas las transiciones posibles.
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?
- Compruebe que la tabla tenga un número apropiado de entradas. En una cuadrícula de 5 por 5 hay 25 estados y 4 acciones, por lo que la tabla debe tener 100 entradas.
- Compruebe para asegurarse de que para un par de estado/acción de inicio, solo dos entradas tienen probabilidad de ocurrencia distinta de cero.
Editar. respondiendo 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
¿Cómo definiría la función de transición al estado seleccionado (en negrita)? –
He editado mi publicación original para incluir una respuesta a esta pregunta –
Lo que usted llama tasa de aprendizaje/gamma es conocido por mí con el nombre de factor de descuento/lambda. – ziggystar