Notas sobre aprendizaje por refuerzo (III): recompensas, trazas y valores

Pues vamos a por otro post sobre aprendizaje por refuerzo ('reinforcement learning') , un post que, como los dos anteriores, de momento se centra en fijar conceptos, vocabularios y notaciones, más que en el mecanismo de aprendizaje por refuerzo propiamente dicho.

En este artículo, en efecto, vamos a introducir dos conceptos: traza y valor. Las trazas nos ayudarán a entender un poco más el modelo de procesos de decisión de Markov y el valor va a ser una forma de concretar la idea de recompensa, tan central del aprendizaje por refuerzo.

Como en lo visto hasta ahora, y como en gran parte de lo que vendrá en esta serie de artículos, me sigo apoyando en el libro 'Deep reinforcement learning' de Aske Plaat

Vamos allá

Recordando conceptos

Como ya hemos visto, los procesos de decisión de Markov son procesos de decisión en que un agente, por ejemplo un robot, interactúa con un entorno, y va adoptando, de manera secuencial decisiones que se traducen en la adopción de acciones sobre el entorno. El entorno, que se encuentra en un momento dado en un estado (s) puede, como consecuencia de esa acción, cambiar a otro estado (s'), teniendo lugar, en ese caso, una transición (t). Y cuando se produce esa transición, el agente recibe una recompensa (r).

En los procesos de decisión de Markov, además, la eventual transición depende, únicamente, del estado del entorno y de la acción aplicada, por lo que no exhiben memoria ni tampoco ninguna dependencia externa.

El agente, toma sus decisión usando una política (π). Y el aprendizaje por refuerzo busca optimizar esa política de forma que se maximice la recompensa acumulada que obtiene el agente. 

Podemos visualizar la relación de estados y acciones como un grafo que, en el caso de entornos deterministas (en un estado dado, la aplicación de una acción sólo puede conducir a otro estado concreto), se convierte en un árbol.

Habiendo recordado esto, ya podemos ir a por los dos conceptos que son objetivo de este post: trazas y valores.

Trazas

Aunque hasta ahora hemos visualizado sólo una transición de estados, en la realidad, lógicamente, cuando el proceso de decisión secuencial se desarrolla (cuando, por ejemplo, el robot interacciona con su entorno), se van realizando, de forma secuencial acciones, seguidas de eventuales cambios de estado del entorno y su recompensa asociada, a las que siguen nuevas acciones con sus consiguientes cambios de estado y así sucesivamente hasta alcanzar un objetivo final.

Durante ese proceso, en cada instante temporal t, el entorno se encontrará en un estado s_t, el agente aplicará una acción a_t, obtendrá una recompensa r_t y provocará la transición al estado s_t+1 con el que se inicia un nuevo paso, y así sucesivamente, hasta conseguir un objetivo final o hasta el infinito.

Pues bien, una traza (τ) no es más que la entidad que recoge esa sucesión de estados, acciones y recompensas. Podemos, formalmente, expresar que una traza con n pasos como:

τ = { s_t, a_t, r_t, s_t+1,  ..., s_t+n, a_t+n, r_t+n, s_t+n+1 }

Con frecuencia, n se convierte en infinito (∞). Además, y aunque no lo voy a representar aquí formalmente (porque sale una fórmula bastante compleja), en el caso de entornos estocásticos, no tendremos trazas cerradas, por decirlo de alguna manera, sino una distribución de probabilidad sobre trazas.

Las trazas también reciben a veces el nombre de trayectoria, episodio o secuencia. 

Retorno

Un concepto muy relacionado con el traza y el de recompensa, es el de retorno (R).

En el fondo, el retorno no es más que la recompensa futura de una traza, es decir, la acumulación de recompensas que se obtienen a lo largo de la ejecución de la traza, aunque con un pequeño matiz que ahora apuntaremos. La formulación del retorno de una traza τ_t sería:

R (τ_t) = r_t + γ*r_t+1 + γ²*r_t+2 + ... =  r_t + ∑_i=1^∞ γⁱ*r_t+i

Vemos que el retorno es una función que para una traza dada, nos devuelve la recompensa acumulada. Y vemos también en la fórmula que no sumamos directamente las recompensas presentes en la traza, sino que lo hacemos multiplicándolo por un factor γ elevado a una potencia que va aumentando. Bien, ese factor γ es lo que denominamos factor de descuento cuando presentamos los modelos de Markov. Y ahora vemos su uso. El factor de descuento es un número comprendido entre 0 y 1 que se utiliza para, a la hora de calcular el retorno, dar más peso a las recompensas recientes que a las lejanas.

Recompensa esperada: valores de estado y de estado-acción

El concepto de retorno nos deja ya cerca de saber con qué recompensa suelen trabajar los algoritmos de aprendizaje por refuerzo. Y ello es debido a la existencia de entornos estocásticos. En casos estocásticos, para una política dada (π), y partiendo de un estado s, no se producirá siempre una misma traza y por tanto no siempre el mismo retorno o recompensa acumulada.

Por ello, lo que queremos es la recompensa acumulada esperada (incluyendo descuentos). Pues bien, esa recompensa acumulada y descontada esperada, es lo que se denomina el valor V, de un estado s. Para una política (π) dada, existirá esa función V, que representamos como V^π(s) que nos proporciona el valor del estado (es decir, su recompensa acumulada esperada).

Adicionalmente, se suele trabajar con la función valor de estado-acción (Q^π(s,a)) cuya idea básica es la misma que el valor de un estado, pero en que ahora condicionamos, no sólo el estado, sino también la acción, es decir, se trata de una función que nos proporciona la recompensa acumulada esperada cuando, estando en un estado s, y siguiendo una política π, aplicamos una acción a.

Inciso: consideraciones sobre la lectura y el entendimiento

No se me oculta que los conceptos expuestos en este post y en los dos anteriores, pueden acabar desbordando al lector que no los conozca a priori, pero hago notar que, a despecho de lo que pueda parecer en una primera lectura no profunda, y a despecho también de lo dificultosas que nos pueden resultar las formulaciones matemáticas, en el fondo los conceptos que hay detrás son bastante sencillos, lógicos y diría que intuitivos.

Así que sugiero al lector que no se desanime, que los lea despacio varias veces y verá cómo al final le parecen lógicos y casi sencillos.

Conclusiones

Con este post casi cerramos la exposición de los conceptos básicos. Hemos visto lo que son los procesos de decisión secuenciales y en concreto los de Markov. Hemos hablado de agentes y entornos (deterministas y estocásticos). Sabemos lo que son los estados, las acciones, las recompensas y las políticas. 

Y hemos aprendido lo que son las trazas y cómo, de cara a la obtención de recompensas acumuladas, aplicamos el factor de descuento y computamos valores de estados o de acciones-estado que, en el fondo, nos proporcionan esas recompensas acumuladas esperadas que luego utilizan los algoritmos de aprendizaje por refuerzo.

Hemos fijado conceptos, pero aún nos queda mucho que ver...

Artículos de este blog relacionados

• Notas sobre aprendizaje por refuerzo (II): Visualizando el aprendizaje en procesos de Markov
• Notas sobre aprendizaje por refuerzo (I): Procesos de decisión de Markov