Finding the Time to Think: Learning Planning Budgets in Real-Time RL

Resumen Técnico: Encontrar el tiempo para pensar: Presupuestos de planificación de aprendizaje en RL en tiempo real

Definición del problema: RL en tiempo real con retardo variable

El Aprendizaje por Refuerzo (RL) estándar y los Procesos de Decisión de Markov (MDP) operan bajo la suposición de que el entorno espera indefinidamente a que el agente compute una acción; por lo tanto, la deliberación no conlleva un coste. En entornos de tiempo real, esta suposición falla: el entorno progresa continuamente independientemente del tiempo de computación del agente. Una acción perfecta ejecutada demasiado tarde es a menudo inferior a una acción subóptima pero oportuna.

Mientras que el trabajo previo (Ramstedt & Pal, 2019) formalizó el RL en tiempo real con un retardo fijo (por ejemplo, exactamente un paso de tiempo para computar), este artículo introduce el RL en tiempo real con retardo variable. En este marco, el agente no es una función estática, sino un procedimiento que se ejecuta en el tiempo. El agente debe decidir cuánto tiempo deliberar en cada punto de decisión. El coste de la deliberación se "paga" como progreso ambiental (o agotamiento del reloj en juegos de tablero) mientras el agente computa. Esto crea un desafío de meta-razonamiento: el agente debe equilibrar la calidad de la acción planificada frente a la degradación del estado causada por el tiempo dedicado a la planificación. Planificar ingenuamente cuánto planificar conlleva el riesgo de una paradoja donde la propia meta-decisión incurre en los mismos costes de tiempo real que la planificación que busca optimizar.

Metodología

Los autores proponen una solución basada en un Proceso de Decisión de Markov Semi-marcoviano (SMDP) sobre opciones presupuestadas, desacoplando el algoritmo de planificación de la decisión de cuánto planificar.

1. Componentes de la arquitectura:

   • Política de reflejo ($\pi_{reflex}$): Una política rápida y ligera (por ejemplo, la cabeza de política de un modelo AlphaZero sin MCTS) que se ejecuta en mucho menos de un fotograma. Provee acciones inmediatas para el entorno mientras el planificador se ejecuta en segundo plano.
   • Computaciones de refinamiento de acción de tiempo continuo ($\{c_k\}$): Un conjunto finito de computaciones indexadas por una duración discreta $k$. En este trabajo, se instancian como ejecuciones de Monte Carlo Tree Search (MCTS) durante $k$ fotogramas. Las ejecuciones más largas ($c_k$) producen acciones de mayor calidad pero requieren más tiempo.
   • Opciones presupuestadas ($o_k$): Cada opción $o_k$ envuelve una computación $c_k$. Al iniciarse, el agente se compromete a ejecutar $k-1$ acciones extraídas de $\pi_{reflex}$ mientras $c_k$ se ejecuta. En el $k$-ésimo fotograma, se ejecuta la acción refinada de $c_k$.
   • Política de compuerta ($\pi_{gate}$): Una red neuronal ligera entrenada mediante Proximal Policy Optimization (PPO) que actúa como una meta-política. Observa el estado actual (observación del juego, características del planificador y estimaciones de valor) y selecciona el presupuesto $k$ (la duración de la opción) para el siguiente meta-paso.

2. Protocolo de entrenamiento:

   • Entrenamiento en dos fases: Primero, se entrenan planificadores base estilo AlphaZero para entornos específicos. Estos planificadores son luego congelados. Segundo, la política de compuerta se entrena sobre el planificador congelado.
   • Formulación de Meta-MDP: La política de compuerta resuelve un problema de control discreto donde las acciones son la selección de opciones presupuestadas. La recompensa es el retorno acumulado sobre los $k$ fotogramas de la opción, descontado por $\gamma^k$.
   • GAE adaptado: Debido a que los meta-pasos tienen duraciones variables ($k$), los autores adaptan la Estimación de Ventaja Generalizada (GAE) para transportar el descuento por meta-paso $\gamma^k$ a través del cálculo de la ventaja.

3. Instanciaciones de entornos:

   • Entornos de acción comprometida (Pac-Man, Tetris en tiempo real, Snake): El entorno progresa continuamente. El agente ejecuta $k-1$ acciones de reflejo mientras planifica. El coste de la planificación es el cambio del estado del mundo durante la computación.
   • Entornos de reloj (Speed Hex, Speed Go): El tablero es estático, pero un reloj compartido se agota con el tiempo de pensamiento. La política de reflejo emite "no-ops" durante la ventana de planificación. El coste es la reducción del presupuesto de tiempo restante.

Contribuciones clave

1. Marco de RL en tiempo real con retardo variable: Una generalización de los marcos de retardo fijo donde el agente elige su propio tiempo de deliberación, tratando la selección del retardo como un problema aprendible en lugar de una restricción impuesta por el sistema.
2. Caracterización empírica de los compromisos de planificación: Los autores establecen que la calidad de la planificación y la latencia de inferencia escalan conjuntamente con el número de simulaciones de MCTS. Este escalado conjunto motiva la necesidad de una asignación adaptativa en lugar de presupuestos fijos.
3. Compuerta adaptativa sobre planificadores congelados: Un método para aprender presupuestos de planificación dependientes del estado utilizando una política de compuerta ligera entrenada sobre un planificador AlphaZero congelado. Esto evita la paradoja de "planificar sobre la planificación", ya que un solo pase hacia adelante de la compuerta es órdenes de magnitud más barato que una ejecución de MCTS.
4. Validación de hardware en el mundo real: El método se valida en un despliegue asíncrono de dos GPUs (una GPU para el entorno/reflejo, otra para MCTS) sin cambios arquitectónicos ni reentrenamiento, demostrando que la política entrenada en simulación se transfiere efectivamente a la ejecución separada por hardware.

Resultados

La política de compuerta fue evaluada en cinco entornos: Pac-Man, Real-Time Tetris, Snake, Speed Hex y Speed Go.

• Rendimiento frente a baselines: La política de compuerta adaptativa superó consistentemente a:
  • Políticas de presupuesto fijo: Agentes restringidos a un solo $k$ (por ejemplo, siempre planificando para 1, 2, 3 o 4 fotogramas).
  • Baselines heurísticos: Incluyendo "Greedy" (siempre máximas simulaciones) y "Midpeak" (asignación de campana de Gauss común en motores de juegos).
  • Baselines aleatorios: La selección aleatoria de presupuestos fue significativamente peor, confirmando que cuándo asignar computación es tan crítico como cuánta se asigna.
• Ganancias específicas:
  • Pac-Man: +10.3% de mejora sobre el mejor presupuesto fijo.
  • Real-Time Tetris: +65% de mejora sobre el mejor presupuesto fijo.
  • Snake: +10.9% de mejora.
  • Speed Hex/Go: La política de compuerta logró puntuaciones esperadas más altas que tanto los presupuestos fijos como las heurísticas bajo diversas restricciones de reloj.
• Análisis de comportamiento: La política de compuerta aprendió a asignar una planificación más profunda (mayor $k$) en estados de alto riesgo o limitados (por ejemplo, fantasmas cerca en Pac-Man, tableros densos en Tetris, baja alcanzabilidad en Snake) y reaccionó rápidamente (bajo $k$) en estados seguros o abiertos. También demostró generalización a diferentes presupuestos de reloj en Speed Hex/Go sin reentrenamiento.
• Transferencia de hardware: En una configuración asíncrona de dos GPUs (H100, A100, A40), las políticas se transfirieron limpiamente de la simulación al hardware real. La latencia se mantuvo dentro del presupuesto en H100 y A100, y los retornos coincidieron estrechamente con sus contrapartes de simulación.

Significancia y afirmaciones

El artículo afirma abordar un desajuste fundamental entre el RL estándar y la interacción en tiempo real al formalizar el tiempo de deliberación como un recurso que debe gestionarse dinámicamente. La significancia reside en:

• Escapar de la paradoja del meta-razonamiento: Al usar una compuerta ligera sobre un planificador congelado, el sistema evita la sobrecarga computacional de planificar cómo planificar, haciendo que el enfoque sea práctico para el despliegue en tiempo real.
• Asignación de recursos dependiente del estado: Los resultados demuestran que un presupuesto de planificación fijo es subóptimo; el valor de la computación es altamente dependiente del estado.
• Escalabilidad al hardware asíncrono: El protocolo de entrenamiento de "acción comprometida" modela con éxito la dinámica de la ejecución asíncrona, permitiendo que las políticas entrenadas en simulación se desplieguen en hardware separado (entorno vs. planificador) sin modificaciones.

Limitaciones reconocidas:

• El marco asume un simulador de entorno perfecto para los pasos comprometidos (MCTS debe predecir con precisión las $k-1$ acciones de reflejo).
• La política de compuerta se entrena sobre un planificador congelado; la optimización conjunta del planificador y la compuerta queda como trabajo futuro.
• El conjunto de presupuestos $\mathcal{K}$ está calibrado manualmente y es discreto; se sugieren extensiones futuras hacia vocabularios de computación continuos o más ricos.