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.
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) = maxa[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 st, ejecuta una acción at, el entorno responde devolviendo un nuevo estado st+1 y una recompensa rt+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 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 maxa’ Q(s’, a’). El Q-Learning es 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ás información
Para complementar es recomendable consultar otros documentos.
- …
Esta página está licenciada bajo CC BY-NC-SA 4.0 por Laboratorios Narratech.