Notas sobre aprendizaje por refuerzo (II): Visualizando el aprendizaje en procesos de Markov

Este es el segundo post de la serie que inicié la semana pasada dedicada al aprendizaje por refuerzo ('reinforcement learning'). En el anterior, presenté los procesos de decisión de Markov. En este segundo post, en realidad voy a avanzar poco en cuanto a aportación de nuevos conceptos, aunque algunas nueva idea sí que habrá. Sin embargo, el objetivo principal es aportar, usando incluso ciertos recursos gráficos (figuras), una mejor visualización de a qué nos referimos con esos procesos de decisión de Markov y cómo funcionan a alto nivel. 

Y, como en el caso del post anterior (y muchos de los que vendrán en esta serie), me apoyo en las explicación del libro 'Deep reinforcement learning' de Aske Plaat.

Recordando los procesos de decisión de Markov

Antes, un primer recordatorio. Recordemos que hablábamos de situaciones en que un agente (por ejemplo, un robot) interactúa con su entorno, tomando decisiones que se concretan en acciones que el agente aplica al entorno y que pueden conducir a que ese entorno cambie de estado.

Hablamos en primer lugar de procesos de decisión secuencial, es decir, aquellos en que el agente va adoptando decisiones una detrás de otra. Esas decisiones se concretan en acciones que el agente aplica a su entorno y que eventualmente, conducen a un cambio de estado del mismo. 

Los procesos de decisión de Markov, añaden sobre esta idea una restricción, a saber, que el estado siguiente del entorno sólo depende del estado de partida y las acciones disponibles para ese estado. 

Recordando los elementos de los procesos de decisión de Markov

En esos procesos de Markov, identificábamos cinco elementos, a saber, 

• El conjunto de estados legales del entorno, conjunto al que vamos a denominar S y a cada estado individual, s.
• El conjunto de acciones aplicables en cada estado, y que vamos a denominar A, denominando cada acción individual como a.
• Las transiciones, que indican la probabilidad de que la aplicación de una acción a, en un estado s, conduzca a un estado s'. A ese conjunto lo vamos a denominar T_a(s,s') y a cada transición concreta, la denominaremos t.
• Las recompensas que obtiene el agente cuando, tras aplicar una acción a en un estado s, se produce la transición al estado s'. Al conjunto lo denominaremos R_a(s,s') y cada recompensa individual la denominaremos r.
• Un factor de descuento, del que todavía no hablaremos más y que denominamos γ.

Respecto al post anterior he añadido la notación más frecuente para esos elementos, que me encuentro en el libro mencionado, y que usaré en las figuras.

Además, recordar que el agente, y de cara a seleccionar la acción, aplica lo que se denomina unos criterios o política, que vamos a representar como π y que, en el fondo, es justamente lo que queremos optimizar o aprender en el entrenamiento bajo aprendizaje por refuerzo.

Visualizando los elementos en acción

Bueno, y ya podemos empezar con la visualización. En la siguiente figura, representamos la interacción agente entorno.

La figura nos esquematiza los que hemos dicho. Tenemos un agente y un entorno con el que interactúa nuestro agente. El agente aplica al entorno (de forma secuencial) acciones (a) y recibe recompensas (r).

Para decidir las acciones, el agente aplica una política (π)

El entorno, en un momento dado, se encuentra en un estado s. Al recibir el entorno la acción, y según lo que marquen sus transiciones (T_a(s,s')), se podrá producir una transición t que signifique el paso del estado inicial s al estado siguiente s'.

Ligada a ese eventual cambio de estado, se genera la recompensa r que obtiene el agente.

Y esto se produce de manera secuencial, hasta que el agente alcanza su objetivo.

Entornos deterministas y entornos estocásticos

Añado un pequeño concepto nuevo. 

En algunos casos, las aplicación de una acción a, cuando el entorno se encuentra en un estado s, conduce directamente a un estado s'. En este caso, decimos que estamos ante un entorno determinista. 

Si por el contrario, ante un mismo estado s, puede transitarse a diferentes estados s', s'', etc con un cierto nivel de probabilidad cada uno, estaremos en el caso de un entorno estocástico.

Grafos y árboles. 

Una forma de representar la evolución del conjunto es usando grafos, tal y como se muestra en la siguiente figura:

En la figura mostramos grafos simples con una sola transición de estado. 

Representamos mediante círculos los nodos del grafo, los círculos en azul claro son los estados y los círculos oscuros las acciones. Las decisiones y las transiciones vienen representadas por los arcos (las flechas del dibujo).Se entiende que, a medida que se van contemplando las acciones en cada estado, el grafo va creciendo, añadiendo nuevos niveles, hasta llegar a estados finales que serían los nodos hoja.

Aunque es menos claro visualmente, podríamos haber eliminado de la representación las acciones y dejar solo los estados. En la etiqueta de los arcos, que representarían las transiciones, se explicitaría la acción. Pero, como digo, creo que visualmente es menos claro (aunque quizá fuese un grafo más puro), así que dejo la representación como se ve más arriba.

Es interesante notar la diferenciación entre el entorno estocástico y el determinista. Observe el lector, que en el caso del estocástico, a partir de las acciones podemos obtener varios estados resultantes (en la figura, dos por cada acción). Sin embargo, en el determinista, sólo se obtiene un estado resultante por acción.

Finalmente, decir que el grafo del caso estocástico en que no existen probabilidades, se denomina árbol.

Ensayo y error. Visualizando el aprendizaje

Una última visualización, y que tiene que ver con el aprendizaje que se realiza por refuerzo.

En el aprendizaje por refuerzo se funciona un poco mediante ensayo y error: el agente aplica una acción (ensayo)  y lo que obtiene es una recompensa (error). Cuando trabajamos con grafos, y en concreto con un árbol (entorno determinista), tenemos lo que se muestra en la figura:

Es decir, existe una especie de doble recorrido hacia delante y hacia atrás ('backpropagation').

A medida que el agente va seleccionando acciones, va recorriendo o construyendo el árbol hacia abajo. Normalmente, la verdadera recompensa se obtiene al llegar a un estado final, un estado hoja. Ahí se produce una retropropagación, una propagación hacia arriba, de la recompensa y del aprendizaje que el agente obtiene de la recompensa obtenida.

Conclusiones

Como decía al principio de este post, realmente no he añadido muchos más conceptos a los que ya vimos en el primero. Hemos añadido, eso sí, una notación más formal, que seguramente sigamos usando, y hemos explicado qué son entornos deterministas y qué estocásticos.

Más allá de eso, este post lo que pretende es, sobre todo, dejar mucho más claros los elementos de un proceso de decisión de Markov y una visión, bien que de muy alto nivel y exenta de detalle, de cómo se produce el aprendizaje. Espero que le sirva, en efecto, al lector, para clarificar conceptos.

En breve, seguiremos avanzando en este campo del aprendizaje por refuerzo mediante nuevos posts.

Artículos de este blog relacionados

• Notas sobre aprendizaje por refuerzo (I): Procesos de decisión de Markov