Reinforcement Learning in Super Mario Bros: Curriculum, Pedagogy, and Optimal Level Design in World 1-1

Resumen Técnico: Aprendizaje por Refuerzo en Super Mario Bros

Planteamiento del Problema
El nivel Mundo 1-1 de Super Mario Bros. es ampliamente celebrado en la literatura de diseño de juegos como una clase magistral de enseñanza progresiva, donde la estructura del nivel introduce mecánicas (tuberías, huecos, enemigos) en un orden seguro y de bajo riesgo antes de exigir su integración. Sin embargo, si esta estructura constituye un currículo pedagógico genuino y mensurable empíricamente o simplemente una narrativa convincente, nunca ha sido probado formalmente. Este artículo busca validar la eficacia pedagógica del diseño canónico del Mundo 1-1 utilizando el Aprendizaje por Refuerzo (RL, por sus siglas en inglés) como una lente empírica. Específicamente, los autores investigan dos preguntas: (1) qué algoritmo de RL aprende el nivel de manera más efectiva y si esto depende de la complejidad, y (2) si el ordenamiento de los segmentos canónicos acelera el aprendizaje en comparación con permutaciones aleatorias.

Metodología
Los autores implementaron el Mundo 1-1 desde cero como un entorno totalmente discreto, evitando librerías estándar de juegos o de RL para asegurar una representación fiel basada en teselas (tiles).

• Entorno: El nivel es una cuadrícula de 212 × 14 teselas. Se crearon tres versiones de complejidad creciente:
  • v1 (Estático): Suelo, tuberías, huecos y escaleras.
  • v2 (+Bloques): Añade ladrillos quebrables y bloques de interrogación.
  • v3 (+Enemigos): Añade 17 enemigos (Goombas y un Koopa) con física precisa de la NES, incluyendo la mecánica de pisotón.
• Espacio de Estados: Representado como tuplas que incluyen columna, fila, fase de salto y un "visor" (una tupla de códigos de tesela dentro de la ventana de la pantalla). El espacio de estados crece de 3 dimensiones en v1 a 115 dimensiones en v3.
• Algoritmos: Se compararon cuatro algoritmos: Q-Learning, SARSA, Monte Carlo (MC) y Deep Q-Network (DQN). Todos utilizaron exploración $\epsilon$-greedy con un esquema de decaimiento compartido.
  • Los métodos tabulares (Q-Learning, SARSA, MC) utilizaron tablas Q exactas (defaultdict), registrando los valores de los estados visitados sin aproximación.
  • DQN utilizó un MLP de PyTorch (128-128-3) con memoria de experiencia (experience replay) de 50k y sincronización de red objetivo.
• Experimento de Currículo: El nivel se partió en seis segmentos canónicos (A–F). Se probaron doce condiciones: el orden canónico (A→F), el orden inverso (F→A) y diez permutaciones aleatorias. Se seleccionó el agente de Monte Carlo para este experimento debido a su sensibilidad a las trayectorias a nivel de episodio.

Contribuciones Clave

1. Implementación Personalizada: Un entorno discreto basado en Python y fiel a la NES del Mundo 1-1 con tres niveles de complejidad, construido sin motores de juego externos.
2. Benchmarking de Algoritmos: Una comparación exhaustiva de 60 ejecuciones de entrenamiento (4 agentes × 3 niveles × 5 semillas) evaluando métodos tabulares frente a métodos de aproximación de funciones.
3. Validación del Currículo: Un experimento sistemático (60 ejecuciones adicionales) muestreando el espacio de permutaciones de los segmentos del nivel para probar la hipótesis de la estructura pedagógica.

Result Resultados

• Rendimiento de los Algoritmos:
  • Monte Carlo (MC) emergió como el agente más fuerte, logrando una tasa de victoria del 94.9% ± 1.5% en el nivel completo (v3). MC superó a DQN (76.4%) y a los métodos TD tabulares al aprender a maximizar las recompensas intermedias (romper bloques, golpear bloques de interrogación) a lo largo de las rutas ganadoras en lugar de tomar la ruta más directa.
  • DQN exhibió una dependencia de la "densidad de recompensa". Sufrió un fallo catastrófico en v1 (tasa de victoria del 10.6%) porque el replay buffer se inundó de penalizaciones por muerte (−50) en relación con las señales positivas dispersas. Sin embargo, se recuperó en v2 (93.4%) cuando las recompensas intermedias (bloques de interrogación) diversificaron la señal. En v3, DQN logró la tasa de victoria más baja (76.4%) debido a la sobregeneralización, aprendiendo a evitar los enemigos por completo en lugar de arriesgarse por las recompensas de pisotón (+5).
  • Los Métodos Tabulares convergieron en todos los niveles. MC convergió más rápido en v1 y v2, mientras que SARSA y Q-Learning mostraron una convergencia ligeramente más lenta en v1 debido al conservadurismo en la exploración.
• Aprendizaje de Currículo:
  • Orden Canónico (A→F) fue la condición más rápida y robusta, logrando una tasa de victoria del 94.7% con cero fallos catastróficos en 10 semillas. Convergió a una tasa de victoria del 50% en aproximadamente 2,771 episodios.
  • Orden Inverso (F→A) fue severamente penalizado, con una tasa de victoria del 48.5% y 4 de cada 10 semillas fallando por completo.
  • Permutaciones Aleatorias se agruparon entre ambos extremos (media de 89.0% de tasa de victoria) pero exhibieron alta varianza; ninguna permutación aleatoria individual igualó los tres criterios de la condición canónica (mayor tasa de victoria, convergencia más rápida, cero fallos).
• Mecanismo de Sensibilidad: El efecto del currículo fue específico al mecanismo de actualización. DQN mostró un efecto de currículo nulo (sin diferencia significativa entre órdenes canónico, inverso y aleatorio) porque su experience replay buffer muestrea uniformemente las transiciones, borrando el orden temporal de los segmentos de fácil a difícil. MC, que actualiza solo después de episodios completos, es altamente sensible al orden de los segmentos.

Significancia y Reivindicaciones
El artículo proporciona la primera validación empírica de que el diseño canónico del Mundo 1-1 codifica una estructura pedagógica genuina que acelera y optimiza el aprendizaje de manera medible y no puede ser replicada por azar. Los resultados demuestran que:

1. La Estructura Pedagógica es Real: El orden específico de los segmentos en el Mundo 1-1 no es arbitrario; optimiza la eficiencia del aprendizaje y la robustez para agentes que dependen de señales basadas en trayectorias.
2. Criterios de Selección de Algoritmos: La elección entre métodos tabulares y DQN no debe basarse únicamente en el tamaño del espacio de estados. En entornos discretos y no uniformes con recompensas dispersas, los métodos tabulares (específicamente MC) pueden superar a DQN. El éxito de DQN está supeditado a la densidad de recompensa para estabilizar su experience replay buffer.
3. Sensibilidad del Mecanismo de Actualización: La sensibilidad al orden del currículo es impulsada por el mecanismo de actualización. Los aprendices a nivel de episodio (MC) se benefician de la dificultad progresiva, mientras que los aprendices basados en replay (DQN) son insensibles al orden temporal debido al muestreo uniforme.

Los autores concluyen que el diseño del Mundo 1-1 es un currículo funcional, no solo una narrativa, y que su efectividad depende de la capacidad del agente para utilizar la estructura temporal de la señal de aprendizaje.