Métodos basados en valor y política

El Aprendizaje por Refuerzo asume que el sistema es un agente que aprende por ensayo y error, interactuando con su entorno. Por eso es especialmente útil para utilizar en videojuegos, por ejemplo para modelar el comportamiento de personajes no jugadores. Los métodos basados en valor s métodos basados en política consiguen superar las limitaciones de los métodos basados en valor para hacer Aprendizaje por Refuerzo cuando los espacios de acciones son continuos o la dinámica del sistema requiere acciones estocásticas.

Propiedades y cadenas de Markov

Para empezar, debemos dominar el marco formal que sostiene todo este edificio del Aprendizaje por Refuerzo. Y ello supone inevitablemente hablar de Andréi Márkov (1856–1922), un matemático ruso que estudiaba secuencias de sucesos aleatorios en los que cada suceso puede depender del anterior; de hecho estudiaba la dependencia entre letras consecutivas de tipo vocal o consonante en algunas obras literarias.

Su tesis viene a decir que «si defines correctamente lo que es un ESTADO, el estado actual del sistema debe contener TODA la información del pasado necesaria para describir probabilísticamente el futuro, pudiéndose ignorar toda la historia anterior». Esta es la llamada propiedad de Markov, y una secuencia de sucesos que cumple esta propiedad se denomina cadena de Markov. Cuando el estado se define utilizando los últimos k elementos de una secuencia, hablamos de un modelo de Markov de orden k.

Ecuación de Bellman

Años después de la muerte de Markov, en los años 50, Richard Bellman desarrolló un trabajo muy interesante. Según el principio de optimalidad de Bellman «Si una solución es óptima, cualquier parte de esa solución que empiece en un estado intermedio también debe ser óptima para el problema que queda desde ese estado». Es una idea sorprendentemente simple y antigua pero que él aplicó sistemáticamente a los problemas de decisión secuencial y optimización, aprovechando la estructura de estado que había permitido formalizar la teoría de Markov. De este modo, sentó las bases de la programación dinámica, basada en el principio de que una solución óptima puede construirse a partir de soluciones óptimas de los subproblemas que la componen.

Como la mejor solución desde el estado actual puede calcularse con las mejores soluciones de los estados siguientes, Bellman propuso su famosa ecuación, una herramienta matemática central. Se trata de descomponer el valor de un estado en dos partes: la recompensa inmediata más el valor del estado siguiente descontado: V(s) = R + gamma V(s’), lo que permite calcular valores futuros de forma recursiva.

La ecuación de Bellman dice así: V(s) = max_a[R(s,a)+V(s1)] donde:

• s es el estado actual
• a es la decisión posible
• R(s,a) es el beneficio o coste inmediato
• s’ es el estado al que llegamos
• V(s’) es la función de valor de estado… el mejor resultado que podemos conseguir a partir de ahí. A diferencia de la recompensa inmediata (que es cortoplacista), la función de valor de estado (o la función de valor de acción, Q(s,a), que es parecida) mide lo «bueno» que es estar en un estado s (o estar en un estado s y además tomar una acción a) pensando en las recompensas futuras.

Proceso de decisión de Markov

Entre los años 50 y 60, Ronald Howard y otros (apoyándose en las ideas de Markov y de Bellman) desarrollaron la teoría y los métodos de lo que se llamó procesos de decisión de Markov (Markov Decision Process o MDP).

En este proceso el agente observa un estado s_t, ejecuta una acción a_t, el entorno responde devolviendo un nuevo estado s_t+1 y una recompensa r_t+1, y el ciclo se repite. El objetivo es maximizar el retorno acumulado a largo plazo (la suma de recompensas descontadas por un factor gamma). Esto ya sí que es trabajar con un paradigma claramente agencial.

Métodos tabulares

Se le llama la tabla Q a la representación matricial donde las filas son estados del juego y las columnas son las acciones. La celda Q(s,a) almacena la calidad esperada de esa decisión. En términos de Teoría de la Decisión, la función Q puede interpretarse como una función de utilidad esperada sobre pares estado–acción, aprendida a partir de experiencia en un entorno estocástico.

El Aprendizaje Q (Q-Learning) es un algoritmo que aprende la política óptima independientemente de la acción que el agente elija realizar en cada momento, asumiendo siempre que en el futuro elegirá la mejor opción posible, es decir max_a’ Q(s’, a’). Este tipo de algoritmo de aprendizaje constituye un ejemplo de off-policy, ya que aprendo una política que NO tiene porque ser la misma que uso para actuar.

El SARSA por el contrario actualiza el valor Q basándose en la acción que el agente realmente ejecuta en el siguiente paso. Es más «prudente» o conservador ante entornos con penalizaciones graves. El SARSA es un ejemplo de off-policy, ya que aprendo una política que NO tiene porque ser la misma que uso para actuar.

Dilema de exploración vs. explotación

¿Debo elegir la acción que sé que da buena puntuación (explotar) o probar acciones desconocidas que podrían ser aún mejores (explorar)? Este es el conflicto fundamental de exploración frente a explotación que se da en este tipo de aprendizaje.

La solución clásica es seguir una estrategia epsilon-voraz (epsilon-greedy). Con probabilidad 1 – epsilon el agente toma la mejor acción conocida, y con probabilidad epsilon toma una acción completamente aleatoria.

También es interesante añadirle a esto un cierto decaimiento de epsilon. Se comienza explorando agresivamente al inicio del entrenamiento y luego se va reduciendo el epsilon conforme el agente domina el juego.

Escalando a entornos complejos

En problemas de la vida real (o de los videojuegos modernos) el número de estados posibles es astronómico y no cabe en ninguna tabla… se produciría un colapso en esa supuesta tabla Q.

¿Qué podemos hacer entonces? Sustituir la tabla por una red neuronal artificial que recibe el estado y predice los valores Q para cada acción.

Para conseguir la estabilidad en videojuegos se usan técnicas como el experience relay (guardar transacciones pasadas en un buffer y entrenar con muestras aleatorias para romper la correlación temporal entre fotogramas) o el target network (usar una red secundaria congelada temporalmente para calcular los objetivos de actualización y evitar la inestabilidad de un «objetivo móvil»).

En cualquier caso la red neuronal artificial que hace falta sería muy grande y con muchas capas, con lo que ya entraríamos en el terreno del Aprendizaje Profundo, las Deep Q-Networks.

Métodos basados en valor

Los métodos basados en valor constituyen una de las principales aproximaciones dentro del aprendizaje por refuerzo y se centran en estimar el valor esperado de los estados o de las acciones, generalmente mediante funciones como lo que hemos visto de la función de valor, V(s), o la función de valor-acción, Q(s,a).

A partir de estas estimaciones, el agente puede seleccionar las acciones que maximizan la recompensa esperada, sin necesidad de aprender directamente una política. Algoritmos como Q-Learning o SARSA siguen este enfoque y han demostrado ser eficaces en numerosos problemas de toma de decisiones. Sin embargo, estos métodos pueden presentar ciertas limitaciones cuando el espacio de acciones es grande o continuo, lo que ha motivado el desarrollo de otros enfoques que aprenden la política de manera directa. Entre ellos se encuentran los métodos basados en política, que constituyen la siguiente familia de técnicas a considerar.

Métodos basados en política

En lugar de aprender indirectamente una función de valor de acción Q(s, a) y seleccionar la acción con el valor máximo, parametrizamos directamente la política pi_theta(a|s) mediante una función (como puede ser una red neuronal artificial con pesos theta) que devuelve una distribución de probabilidad sobre las acciones. Es un cambio conceptual en el que pasamos de evaluar estados a optimizar acciones (se llama policy search).

Las ventajas estructurales de estos métodos son, en primer lugar, que manejan estados de acciones continuas de forma natural (ej. cuantos grados debe girar un volante, cuanta aceleración hay que meterle a un motor… cosas que no se hacen bien con Q-Learning). En segundo lugar estos métodos pueden aprender políticas estocásticas (óptimas en juegos de información imperfecta como el póker, donde ser predecible te hace vulnerable). Y en tercer lugar presenta mejores propiedades de convergencia en espacios de alta dimensión.

El Aprendizaje por Imitación -sobre el que quizá comentemos algo más adelante, en Cuestiones avanzadas- suele funcionar con este tipo de métodos basados en políticas.

Teorema del gradiente de la política

Es un teorema que demuestra cómo podemos calcular analíticamente el gradiente del rendimiento esperado respecto a los parámetros de la red nabla_theta J(theta), incluso sin conocer la dinámica de transición del entorno.

El algoritmo REINFORCE, que también se llama Monte Carlo Policy Gradient funciona de la siguiente manera:

1. El agente juega un episodio completo recopilando una trayectoria de estados, acciones y recompensas.
2. Evalúa el retorno real obtenido al final de la partida.
3. Aumenta la probabilidad de las acciones que llevaron a retornos altos y reduce la de aquellas que acabaron en derrota.

El inconveniente de esto es que presenta una varianza muy alta en la estimación del gradiente, lo que hace que el entrenamiento sea lento e inestable.

Arquitecturas Actor-Crítico

A estas arquitecturas Actor-Critic algunas las consideran la combinación perfecta porque unen lo mejor de los métodos basados en política y los métodos basados en valor para reducir la varianza.

Se trata de hacer una división de roles. El actor modela y actualiza la política pi_theta(a|s), de manera que decide qué acción tomar. El crítico estima la función de valor de estado V_w(s), de manera que evalúa si el estado alcanzado es bueno o malo.

La clave es que el actor se actualiza basándose en el valor de la ventaja o advantage function: A(s, a) = Q(s, a) – V(s), que mide cuánto mejor fue la acción elegida comparada con la acción promedio en ese estado.

Algoritmos de estado del arte

Actualmente los que más se están usando son estos dos:

• Proximal Policy Optimization (PPO). Es el estándar actual de la industria (utilizado por OpenAI para entrenar bots en Dota 2 y por Unity ML-Agents). Restringe el tamaño de la actualización de la política mediante un recorte (clipping) en la función de pérdida para evitar que la red sufra «colapsos catastróficos» de rendimiento en un solo paso de optimización. El algoritmo por defecto en Unity ML-Agents es precisamente este, por ser uno de los algoritmos más avanzados.
• Soft Actor-Critic (SAC). Es un algoritmo off-policy para acciones continuas que maximiza tanto la recompensa acumulada como la entropía de la política. Esto fomenta una exploración muy agresiva y evita que la IA se quede estancada en mínimos locales.

En cualquier caso es importante entender que estos algoritmos ya no se programan desde cero en C++, es muy raro hacerlo… lo habitual es entrenarlos conectando marcos de trabajo como Python (en particular bibliotecas como PyTorch) con motores de juego como Unity o Unreal Engine a través de APIs de comunicación en tiempo real. Un Aprendizaje por Refuerzo podría tener sentido para la locomoción física de bípedos generados procedimentalmente, conducción autónoma en simuladores de vehículos como coches de carreras o aviones de combate.

Más información

Para complementar es recomendable consultar otros documentos.

• …