Formulación de estados para este problema de RL y otras cuestiones.

Question

Considere un mundo cuadriculado 100 $\times$ 100 con una posición inicial, $S$ , en la esquina inferior izquierda y una posición de gol, $G$ en algún lugar del centro. Ambos $S$ y $G$ son fijos y no se mueven.

Además, los subobjetivos existen de uno en uno. Por ejemplo, "1" aparece en una posición aleatoria. Si se alcanza "1", aparece "2" y así sucesivamente. Los números sucesivos aparecen de forma aleatoria pero tendrán una distancia cada vez más cercana al objetivo final $G$ . La probabilidad de transición no está disponible y no se aprenderá, por lo que se utilizará el aprendizaje sin modelo.

El agente puede moverse en 4 direcciones cardinales.

Tengo muchas preguntas serias:

1. ¿Cuál podría ser una buena representación del espacio de estados para esto? El hecho de que sea 100 $\times$ 100 significa que estoy evitando los habituales $(x,y)$ posición de "coordenadas" o la cardinalidad del espacio de estados será tan grande.

Mi idea sería elegir la posición "relativa" entre el agente y el objetivo. Algo así como: $(x,y)$ , $x = \{ -1, 0, 1\}$ . $-1$ si el objetivo está a la izquierda del agente, 1 si el objetivo está a la derecha, y 0 si el objetivo está en el mismo $x$ coordinar como el agente. $y = \{ -1,0,1\}$ , $-1$ si el objetivo está por debajo, $1$ si está por encima del agente. 0 si son iguales $y-$ coordinar.

Así que tal vez la formulación del espacio de estado puede seguir esta forma que se encuentra aquí:

Aprendizaje por refuerzo libre de modelos con submetas: ¿cómo reforzar el aprendizaje con una sola recompensa?

$(x,y,k)$ donde $k$ ¿se ha alcanzado el subobjetivo de número?

2. ¿Es un problema manejable? Entiendo que esto puede estar mal escrito, pero quiero compartir mi intuición. El número de submetas que tengo aquí podría no ser conocido apriori. Pero definitivamente se acercan cada vez más a la posición de la meta.

¿Hay alguna manera de escribir los estados para incluir las posiciones de los subobjetivos sin dar múltiples recompensas? He pensado en dar múltiples recompensas al agente después de conseguir cada subobjetivo, pero eso sería "hacer trampa". Creo que es estándar en RL que la recompensa se da al final de la tarea.

Me gustaría tener su valiosa opinión sobre este problema. Siéntase libre de enviar comentarios o más preguntas si hay alguna.

Answer 1

Resumen

1. El espacio de estados se desprende del problema. La "bondad" depende del método, al igual que "demasiado grande".
2. Puedes modificar la función de recompensa para acelerar el aprendizaje si sabes que la política óptima es invariable a la transformación.
3. La trazabilidad depende de algo más que del espacio de estados. La RL se ha aplicado a problemas mucho más amplios, aunque esos métodos no son exactamente los mismos.

---

Definición del espacio de estados

No está claro lo que quieres decir con "agradable". Considera lo que sabes:

• La portería está en el centro.
• El agente comienza en la parte inferior izquierda.
• El primer subobjetivo aparece en algún lugar distinto de estos dos espacios.
• A veces, al alcanzar un subobjetivo, aparece otro; otras, no.
• Mientras haya un subobjetivo, el agente debe alcanzarlo antes de llegar a la meta.

Es decir, el número de submetas no parece especialmente importante para la política óptima.

En una representación discreta, el agente puede estar en una de las siguientes situaciones $10,000$ posiciones, y si un subobjetivo está presente puede aparecer en cualquiera de $9,998$ . (Suponiendo que nunca puede estar en el estado de meta, y sabiendo que nunca puede estar en la posición inicial del agente, lo que se deduce de saber que las submetas sólo se acercan a la meta).

¿Grande? Claro. ¿Demasiado grande para el aprendizaje Q estándar? Probablemente, si quieres que tu aprendiz devuelva una política antes de la muerte por calor del universo. Pero esto parece ser la representación completa e irreductible de su problema.

Mi idea sería elegir la posición "relativa" entre el agente y el objetivo. Algo así como: $(x,y)$ , $x = \{ -1, 0, 1\}$ . $-1$ si el objetivo está a la izquierda del agente, 1 si el objetivo está a la derecha, y 0 si el objetivo está en el mismo $x$ coordinar como el agente. $y = \{ -1,0,1\}$ , $-1$ si el objetivo está por debajo, $1$ si está por encima del agente. 0 si son iguales $y-$ coordinar.

Siento lo que quieres decir aquí: Te gustaría mapear un gran espacio de estado $S$ a uno más pequeño $\hat S$ tal que $\pi^*_{S}(s) = \pi^*_{\hat S}(\hat s)$ . Esto tiene un sentido intuitivo, ya que la distancia relativa a los subobjetivos y a la meta es casi todo lo que el agente necesita para tomar decisiones óptimas.

Esto es básicamente hacer una política a mano; está bien si eso se ajusta a su problema, pero entonces uno se pregunta si necesita RL en absoluto.

¿Es esto manejable?

Bueno, es aprendible, en el sentido de que está bien dentro del estado actual de la técnica. Consideremos el espacio de estados descrito en el artículo sobre el aprendizaje de los juegos de Atari mediante redes neuronales profundas y Q-learning :

Trabajar directamente con fotogramas Atari sin procesar, que son imágenes de 210 × 160 píxeles con una paleta de 128 colores, puede ser exigente desde el punto de vista informático, por lo que aplicamos un paso básico de preprocesamiento destinado a reducir la dimensionalidad de la entrada. Los fotogramas en bruto se preprocesan convirtiendo primero su representación RGB en escala de grises y reduciendo su tamaño a una imagen de 110×84. La representación final de entrada se obtiene recortando una región de 84 × 84 de la imagen que captura aproximadamente el área de juego. [Para los experimentos de este trabajo, la función $\phi$ del algoritmo 1 aplica este preprocesamiento a los últimos 4 fotogramas de un historial y los apila para producir la entrada de la función Q.

Podría ver su espacio de estados como un subconjunto del $100 \times 100$ imágenes, y el espacio de estado de arriba empequeñece el suyo. Todo para decir que existen soluciones probables incluso para espacios de estado más grandes, pero en esto probablemente no sea necesario ponerse tan elegante.

Sobre las "trampas

Creo que lo normal en RL es que la recompensa se dé al final de la tarea.

Le ruego que se desprenda rápidamente de esta idea: Simplemente no es cierto. En primer lugar, porque la función de recompensa se deriva de la aplicación, y punto. Si una aplicación conlleva diferentes recompensas, naturalmente deben incluirse, es decir, una sola recompensa no es estándar. En segundo lugar, porque las políticas óptimas son invariables bajo ciertas transformaciones de la función de recompensa que puede acelerar el aprendizaje (el énfasis es mío):

Este trabajo investiga las condiciones bajo las cuales las modificaciones de la función de recompensa de un proceso de decisión de Markov preservan la política óptima. Se demuestra que [...] se puede añadir una recompensa para las transiciones entre estados que es expresable como la diferencia de valor de una función potencial arbitraria aplicada a esos estados. [...] En particular, se demuestra que algunos "errores" bien conocidos en los procedimientos de conformación de recompensas surgen de recompensas no basadas en el potencial, y se dan métodos para construir los potenciales de conformación correspondientes a las heurísticas basadas en la distancia y en los subobjetivos . Demostramos que estos potenciales pueden conducir a reducciones sustanciales del tiempo de aprendizaje.

Si tu problema tiene un estado objetivo, una sola recompensa es una representación natural, y tienes razón en que añadir arbitrariamente recompensas a los estados es una mala idea. Pero sólo lo es cuando no se puede demostrar la invariabilidad de la política bajo la transformación; de lo contrario, es un juego limpio.

¿Qué debe hacer? hacer ?

Como sabes, puedes esperar que cualquier acción bajo la política óptima se mueva generalmente hacia el subobjetivo o hacia el objetivo. Creo que encontrarás que puedes crear funciones de recompensa basadas en el potencial a partir de estos hechos, que acelerarían rápidamente el aprendizaje.

También se puede ver esto como un aprendizaje de opciones problema, en el que una opción era perseguir el subobjetivo y la otra perseguir el objetivo. ( Opción es un término utilizado para describir las acciones temporalmente extendidas. Se puede ver como el uso de una determinada política hasta que se alcance un determinado estado).

También se podría simplemente inicializar $Q$ de manera que la política de partida se acerque a la óptima.

Addenda

¿Hay alguna manera de escribir los estados para incluir las posiciones de los subobjetivos sin dar múltiples recompensas?

Ninguna representación del espacio de estados requiere una determinada función de recompensa. No está claro qué significa esto.

Referencias

• Jugar a Atari con el aprendizaje por refuerzo profundo por Mnih et al
• Invarianza de la política bajo transformaciones de la recompensa: Teoría y aplicación a la conformación de recompensas por Ng et al.
• Opciones de aprendizaje en el aprendizaje por refuerzo por Stolle y Precup