agosto 22, 2021

~ 16 MIN

AxR - Procesos de Decisión Finitos de Markov

< Blog RSS

Open In Colab

Procesos de Decisión Finitos de Markov

Vamos a introducir la formulación de los procesos de decisión finitos de Markov (MDPs), la resolución de los cuales abarca el conjunto de algoritmos de AxR. Los MDPs describen procesos de decisión secuencial en los que las acciones tomadas en diferentes situaciones no solo influen en las recompensas inmediatas, sino también en las futuras. A diferencia del ejemplo que vimos en el post anterior, en el que estimamos q_*(a) para cada acción a , el uso de MDPs nos va a permitir estimar q_*(s,a) como el valor para cada par estado-acción, s y a respectivamente.

La interface Agente-Entorno

El objetivo de los MDPs es la representación del problema de aprendizaje a través de la interacción con el entorno para conseguir un objetivo. El agente es el encargado de aprender y tomar decisiones, mientras que el entorno es todo con lo que interacciona y sobre lo que no tiene un control directo. El entrono presenta diferentes situaciones al agente en función de sus acciones, y provee recompensas que el agente intenta maximizar.

El agente interacciona con el entrono de manera secuencial en pasos discretos, t=0,1,2,... . Para cada instante t el agente recibe una representación del estado S_t , la cual usa para definir una acción A_t que a su vez produce un nuevo estado S_{t+1} . En ese momento el entorno emite la recompensa R_{t+1} . En un MDP finito, el conjunto de estados, acciones y recompensas tienen un número finito de elementos. En este caso, las variables aleatorias R_t y S_t tienen distribuciones de probabilidad bien definidas, y que dependen únicamente del estado anterior y la acción tomada. Estas funciones de probabilidad definen la dinámica del MDP.

Definimos las probabilidades de transición de estado como

p(s^\prime|s,a) = \sum_r p(s^\prime,r|s,a)

donde s^\prime es el nuevo estado. Podemos encontrar las recompensa esperada para un par estado-acción con la expresión

r(s,a) = \sum_r r \sum_{s^\prime} p(s^\prime,r|s,a)

y las recompensa esperada para tríos de estado-acción-estado siguiente con

r(s,a,s^\prime) = \sum_r r \frac{p(s^\prime,r|s,a)}{p(s^\prime|s,a)}

Los MDPs son flexibles y abstractos, y se pueden aplicar a multitud de problemas de forma distinta. Los instantes temporales no tienen porque estar referidos a intervalos de tiempor real, sino que pueden interpretarse como etapas sucesivas arbitrarias en cualquier proceso de toma de decisión. Las acciones pueden ser desde controles tales como voltajes aplicados en motores robóticos hasta decisiones de alto nivel. Del mismo modo, los estados pueden representarse utilizando desde sensaciones básicas hasta conceptos abstractos y representaciones simbólicas. Ejemplos:

  • Imaginemos que aplicamos axr al control de temperatura de un bioreactor. Las diferentes acciones podrían ser la activación de elementos de calefacción y motores para mantener una temperatura objetivo. Los estados vendrían determinados por sensores de temperatura y otros sensores además de representaciones simbólicas sobre los ingredientes químicos. Las recompensas serían las medidas del ratio al cual los productos químicos se producen en el bioreactor. Mientras que las recompensas son siempre valores numéricos escalares, las acciones y estados pueden representarse mediante listas, vectores, símbolos, etc.

  • Imaginemos que aplicamos axr al control de un brazo robótico para manipular objetos. En este caso, las acciones serían los voltajes eléctricos necesarios para mover los diferentes motores, los estados se definirían con el conjunto de ángulos y posiciones de los diferentes elementos del brazo y la recompensa sería de +1 si el objeto es cogido mientras que una recompensa negativa podría aplicarse por cada instante en el que el brazo no ha logrado coger el objeto.

Vamos a aplicar los conceptos vistos en el siguiente MDP dónde tenemos 3 estados (representadas por círculos) y 3 posibles acciones (representada por diamantes).

Empezando por el estado s_0 el agente puede elegir entre las acciones a_0 , a_1 y a_2 . Si elige la acción a_1 , siempre se queda en el estado s_0 y no recibe recompensa. Si elige la acción a_0 , tiene un 70% de probabilidades de quedarse en s_0 recibiendo +10 de recomensa. Podría quedarse en s_0 recibiendo recompensa una y otra vez, pero eventualmente (con un 30% de probabilidad) acabaría en el estado s_1 . En el nuevo estado, podría llevar a cabo las acciones a_0 o a_2 . Si elige a_0 se quedará en el mismo estado sin recibir recompensa, mientras que con a_2 transiciona al estado s_2 recibiendo una recompensa de -50. Por último, en el estado s_2 , el agente sólo puede llevar a cabo una acción, a_1 , que la mayoría de las veces le llevará al estado inicial, recibiendo una recompensa de +40, pero que eventualmente podría llevarle al estados s_1 o a quedarse en el mismo estado.

probas_transiciones = [
    [[0.7, 0.3, 0.0], [1.0, 0.0, 0.0], [0.8, 0.2, 0.0]], # p(s0| s0, a0), p(s0| s0, a1), p(s0| s0, a2)
    [[0.0, 1.0, 0.0], None, [0.0, 0.0, 1.0]           ], # p(s1| s1, a0), p(s1| s1, a1), p(s1| s1, a2)
    [None,            [0.8, 0.1, 0.1], None           ]  # p(s2| s2, a0), p(s2| s2, a1), p(s2| s2, a2)
]

recompensas = [
    [[+10, 0, 0], [0, 0, 0],   [0, 0, 0]],   # r(s0, s0, a0), r(s0, s0, a1), r(s0, s0, a2)
    [[0, 0, 0],   [0, 0, 0],   [0, 0, -50]], # r(s1, s1, a0), r(s1, s1, a1), r(s1, s1, a2)
    [[0, 0, 0],   [+40, 0, 0], [0, 0, 0]]    # r(s2, s2, a0), r(s2, s2, a1), r(s2, s2, a2)
]

acciones = [
    [0, 1, 2],
    [0, 2],
    [1]
]

Objetivos y Recompensas

En el AxR el objetivo de un agente está determinado por la recompensa que le proporciona el entorno. En cada instante, la recompensa es un valor numérico, y el agente tiene que maximizar la recompensa total recibida a largo plazo. Esta es una de las propiedades más distintivas del AxR en comparación a otras técnicas de aprendizaje. Por ejemplo: un agente aprendiendo a andar tendrá una recompensa positiva cada vez que se mueva hacia adelante. Un robot aprendiendo a recoger basura del suelo tendrá una recompensa positiva cada vez que recoga basura, mientras que recibirá recompensas negativas cuando recoga cosas que no son basura. En definitiva, el agente aprende mediante el proceso de maximización de la recompensa, por lo tanto es crítico que las recompensas reflejen el objetivo que queremos lograr. Un agente aprendiendo a jugar a ajedrez recibirá una recompensa positiva sólo cuando gane y no cada vez que se coma una pieza ya que de hacerlo así podría aprender a comer el máximo de piezas posibles incluso si eso le lleva a perder la partida.

La recompensa es nuestra manera de comunicarnos con el agente y tiene que reflejar qué queremos conseguir, no el cómo.

Retornos y Episodios

Definimos el retorno como una función de todas las recomensas recibidas después de el instante t . En el caso más simple

G_t = R_{t+1} + R_{t+2} + ... + R_T

donde T es el último instante temporal. Formalmente, el objetivo del agente es el de maximizar el retorno esperado. Un episodio concluye cuando el agente llega al instante T , como por ejemplo cuando termina una partida de ajedrez. Algunas tareas, sin embargo, no son episódicas y continuan en el tiempo sin fin (por ejemplo, tareas de control de procesos). Esto implica que el retorno de una tarea continua podría ser infinito, dificultando su maximización.

Para unificar ambos casos se introduce el concepto de descuento, por lo que ahora el objetivo del agente será el de maximizar el retorno descontado esperado.

G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... = \sum_{k=0}^\infty \gamma^k R_{t+k+1}

donde 0 \leq \gamma \leq 1 es el ratio de descuento, el cual determina el valor presente de las recompensas futuras. Un valor de \gamma=0 hará que el agente se focalice únicamente en recompensas inmediatas, mientras que a medida que \gamma se acerca a 1 el agente tendrá en cuenta las recompensas a largo plazo con mayor intensidad.

Políticas y Funciones de Valor

Prácticamente todos los algoritmos de AxR se basan en la estimación de funciones de valor, que indican lo bueno que es un estado o un par estado-acción. Formalmente, esta medida de bondad viene dada por las recompensas futuras esperadas, o el retorno esperado. Las funciones de valor están definidas con respecto a formas particulares de actuar, llamdas políticas.

Una política es una relación entre estados y probabilidades de seleccionar cada acción posible. Si el agente está siguiendo la política \pi en el instante t , entonces \pi_t(a|s) es la probilidad de ejecutar la acción a en el instante t para el estado s . Los diferentes métodos y algoritmos de AxR especifican cómo evoluciona \pi como resultado de la experiencia del agente a través de la interacción con el entorno.

La función de valor de un estado s dada una política \pi se denota como v_\pi(s) y equivale al retorno esperado desde el estado s si nuesto agente siguiese la política \pi hasta el final del episodio.

v_\pi(s) = \mathbb{E}_\pi [G_t | S_t=s] = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t=s \right]

donde \mathbb{E}_\pi [\cdot] es el valor esperado de una variable aleatoria asumiendo que el agente está siguiendo la política \pi .

De manera similar definimos el valor de una acción a en el estado s bajo la política \pi como el retorno esperado empezando en s , llevando a cabo la acción a y siguiendo en adelante la política \pi

q_\pi(s,a) = \mathbb{E}_\pi [G_t | S_t=s, A_t = a] = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t=s , A_t = a \right]

Ambas funciones de valor se estiman a través de la experiencia. Por ejemplo, los métodos Monte Carlo mantienen un registro por cada estado visitado de la recompensa media obtenida desde ese estado en adelante. Si el número de veces que cada estados es visitado se aproxima a infito, estos valores promedios convergen a v_\pi(s) . Lo mismo se puede hacer con q_\pi(s,a) si se mantiene un registro por cada acción tomada. Esta metodología es problemática si hay muchos estados o acciones. En estos casos las funciones v_\pi(s) y q_\pi(s,a) son funciones paramétricas (con menos parámteros que estados, obviamente) y estos parámetros se van ajustando en función de las recompensas obtenidas.

La ecuación de Bellman

Una de las propiedades fundamentales de las funciones de valor utilizadas ampliamente en AxR y programación dinámica es que satisfacen relaciones recursivas: dada una política \pi y un estado s , la siguiente relación se establece entre el valor de s y el valor de los posibles estados sucesores

v_\pi(s) = \sum_a \pi(a|s) \sum_{s^\prime,r} p(s^\prime,r|s,a) [r + \gamma v_\pi(s^\prime)]

Esta expresión se conoce como la ecuación de Bellman para v_\pi . Expresa la relación entre el valor de una estado y el valor de los estados sucesivos. Empezando por el estado s un agente podría tomar una acción de entre varias basada en una política \pi . Para cada una de estas acciones, el entorno podría responder con uno de los varios posibles estados sucesivos s^\prime junto a una recompensa r depenendiendo de la dinámica del entorno dada por la función de probabilidad p . La ecuación de Bellman calcula el promedio de todas estas posibilidades, ponderando cada una por su probabilidad de ocurrir. Determina que el valor de una estado es igual al valor del estado sucesivo esperado (descontado) más la recompensa obtenida por el camino.

Políticas óptimas y Funciones de Valor óptimas

Resolver un problema de AxR significa, a grandes rasgos, encontrar una política que consiga mucha recompensa a largo plazo. Para MDPs finitos podemos definir la política óptima, \pi_* , como aquella con mayor función de valor para cualquier estado

v_*(s) = \max_\pi v_\pi(s)

Del mismo modo,

q_*(s,a) = \max_\pi q_\pi(s,a) = \mathbb{E} [R_{t+1} + \gamma v_*(S_{t+1}) | S_t=s, A_t=a]

La ecuación de Bellman puede reescribirse asumiendo una política óptima dando lugar a

v_*(s) = \max_a \sum_{s^\prime,r} p(s^\prime,r|s,a) [r + \gamma v_*(s^\prime)] q_*(s,a) = \sum_{s^\prime,r} p(s^\prime,r|s,a) [r + \gamma \max_{a^\prime} q_*(s^\prime,a^\prime)]

Para MDPs finitos, la ecuación de Bellman de optimidad para v_* tiene solución única. Se trata de un sistema de ecuaciones, con una ecuación e incóginta por estado. Si la dinámica del entorno, p , es conocida entonces podemos resolver el problema con cualquier método de resolución de sistemas de ecuacions no lineales. Lo mismo se puede hacer con q_*(s,a) . Una vez encontrada esta solución, un agente seguirá la política óptima escogiendo aquella acción en cada estado que maximice q_*(s,a) .

Sin embargo, esta aproximación no es la utilizada generalmente ya que rara vez conocemos al 100% la dinámica de un entorno, o disponemos del suficiente poder computacional como para resolver el sistema de ecuaciones. Es por este motivo que muchos métodos de toma de decision se basan en la aproximación de la solución de la ecuación de Bellman de optimidad.

Vamos a ver un ejemplo de aproximación de q_*(s,a) utilizando programación dinámica, un algoritmo de AxR que veremos en detalle más adelante, para el MDP visto anteriormente.

probas_transiciones = [
    [[0.7, 0.3, 0.0], [1.0, 0.0, 0.0], [0.8, 0.2, 0.0]], # p(s0| s0, a0), p(s0| s0, a1), p(s0| s0, a2)
    [[0.0, 1.0, 0.0], None, [0.0, 0.0, 1.0]           ], # p(s1| s1, a0), p(s1| s1, a1), p(s1| s1, a2)
    [None,            [0.8, 0.1, 0.1], None           ]  # p(s2| s2, a0), p(s2| s2, a1), p(s2| s2, a2)
]

recompensas = [
    [[+10, 0, 0], [0, 0, 0],   [0, 0, 0]],   # r(s0, s0, a0), r(s0, s0, a1), r(s0, s0, a2)
    [[0, 0, 0],   [0, 0, 0],   [0, 0, -50]], # r(s1, s1, a0), r(s1, s1, a1), r(s1, s1, a2)
    [[0, 0, 0],   [+40, 0, 0], [0, 0, 0]]    # r(s2, s2, a0), r(s2, s2, a1), r(s2, s2, a2)
]

acciones = [
    [0, 1, 2],
    [0, 2],
    [1]
]


import numpy as np

# inicializamos q(s, a)

q = np.full((3, 3), -np.inf) # -np.inf para acciones imposibles
for estado, accion in enumerate(acciones):
    q[estado, accion] = 0.0

q


array([[  0.,   0.,   0.],
       [  0., -inf,   0.],
       [-inf,   0., -inf]])


gamma = 0.90  # factor de descuento

# estimamos q* aplicando la eq. de Bellman de optimalidad

for iteration in range(100):
    q_prev = q.copy()
    for s in range(3):
        for a in acciones[s]:
            q[s, a] = np.sum([probas_transiciones[s][a][sp]*(recompensas[s][a][sp] + gamma*np.max(q_prev[sp])) for sp in range(3)])

q


array([[18.91891892, 17.02702703, 13.62162162],
       [ 0.        ,        -inf, -4.87971488],
       [       -inf, 50.13365013,        -inf]])


# política óptima

pi = np.argmax(q, axis=1)

pi


array([0, 0, 1], dtype=int64)

La política óptima encontrada nos dice que en el estado s_0 tomar la acción a_0 es lo mejor, efectivamente nos da +10 de recompensa. En el estado s_1 los mejor es tomar la acción a_0 , ya que la altrenativa nos dará una recompensa negativa. En el estado s_2 lo mejor es tomar la acción a_1 , que en la mayoría de ocasiones nos dará una recompensa de +40. Un factor de descuento distinto dará como resultado otra política en función de cuánto valoremos recompensas a largo plazo.

gamma = 0.95  # factor de descuento

for iteration in range(50):
    q_prev = q.copy()
    for s in range(3):
        for a in acciones[s]:
            q[s, a] = np.sum([probas_transiciones[s][a][sp]*(recompensas[s][a][sp] + gamma*np.max(q_prev[sp])) for sp in range(3)])

# política óptima

np.argmax(q, axis=1)


array([0, 2, 1], dtype=int64)

En esta nueva política la acción óptima del estado s_1 ahora ha cambiado a a_2 , lo cual dará como resultado una recompensa negativa de -50 pero que nos lleva al estado s_2 , desde donde podemos conseguir la recompensa de +40.

Resolviendo MDPs

Existen multitud de métodos y algoritmos que pueden ser utlizados para resolver MDPs. En el campo del AxR puedes ser clasificados en base a sus propiedades. Los grupos de métodos más comunes se dividen en:

  • tabulares vs aproximados: Hablamos de métodos tabulares para referirnos a aquellos métodos capaces de encontrar de manera exacta funciones de valor y políticas óptimas, para los cuales podemos representar las funciones de acción-valor como una lista o una tabla. Estos casos suelen estar limitados a entornos con un pequeño conjunto de estados y acciones (como los que hemos visto en los posts anteriores). Cuando este conjunto es tan grande que no es posible representarlo de manera exacta, recurrimos a los métodos aproximados que, como su nombre indica, nos darán una solución aproximada. Por ejemplo, un método tabular es suficiente para entrenar un agente que juegue al tres en raya de manera óptima, ya que podemos representar en una tabla todas las posibles configuraciones del juego y, para cada una, su valor. Sin embargo, intentar hacer lo mismo para juegos como el ajedrez o el go resultaría imposible ya que el número de posibles estados y acciones es astronómico. En estos casos, recurrimos a métodos aproximados.
  • model-free vs model-based: Los métodos basasdos en modelos son capaces de predecir la recompensa que obtendrán en el futuro, para lo cual necesitan de un modelo del entorno que puede ser dado o aprendido. Por otro lado, los modelos no basados en el entorno aprender directamente de las recompensas obtenidas, relacionando observaciones y acciones.
  • value-based vs policy-based: Los métodos de AxR basados en política nos darán una distribución de probabilidad sobre el conjunto de acciones dado un estado determinado, es decir, aproximan directamente la política del agente. Por el contrario, los métodos basados en valores, asignan un valor a cada acción (o par estado-acción), el cual es usado por el agente para definir su política (por ejemplo, escoger la acción con mayor valor).
  • On-policy vs off-policy: Un método on-policy basa su aprendizaje en la interacción del agente con el entorno en tiempo real, mientras que un método off-policy es capaz de aprender de interacciones de otros agentes, ejemplos humanos o del mismo agente en versiones pasadas.

En este post vamos a introducir la primera clase de métodos, los tabulares, los cuales podemos usar para asentar los conceptos claves del AxR.

Resumen

El AxR consiste en aprender un comportamiento a través de la interacción para conseguir un objetivo. El agente, mediante la realización de acciones, interactúa con el entorno, que define un estado y una recompensa. El objetivo del agente es maximizar la recompensa recibida a lo largo del tiempo. Cuando esta configuración está formulada con probabilidades de transición definidas constituye un proceso de decisión de Markov (MDP). Un MDP finito es un MDP con estados, acciones y recompensas finitas.

El retorno es la función de recompensas futuras que el agente tiene que maximizar. Las funciones de valor de una politica asignan a cada estado (o par estado-acción) el retorno esperado. Las funciones de valor óptimas asignan el máximo retorno esperado para la política determinada. Una política cuyas funciones de valor sean óptimas, es una política óptima.

La ecuación de Bellman especifica condiciones de consistencia que una política óptima debe cumplir, y puede (en principio) resolverse para encontrar las funciones de valor óptimas. Sin embargo, debido a las limitaciones que entornos complejos pueden acarrear, la mayoría de métodos se basan en encontrar aproximaciones a estas funciones.

< Blog RSS