Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learning

Resumen Técnico: Transporte Inteligente sin Neuronas – Expansión de la Red de Metro con Aprendizaje por Refuerzo Tabular

Definición del Problema
El artículo aborda el Problema de Expansión de la Red de Metro (MNEP, por sus siglas en inglés), un subconjunto específico del Problema de Diseño de Redes de Transporte (TNDP). El objetivo es diseñar una nueva línea de metro dentro de una red urbana existente para maximizar la demanda de viajes capturada, sujeto a restricciones de presupuesto de construcción ($B$) y al número máximo de estaciones ($T$). Tradicionalmente, el MNEP se modela como un problema de optimización combinatoria donde la ciudad se representa como una cuadrícula, y el objetivo es encontrar una secuencia de celdas adyacentes que formen una línea para maximizar la suma de la demanda de Origen-Destino (OD) satisfecha.

Se identifica una brecha crítica en la literatura relacionada con la dependencia del Aprendizaje por Refuerzo Profundo (Deep RL) para estos problemas. Aunque el Deep RL ha mostrado éxito en la toma de decisiones secuenciales complejas, es computacionalmente costoso, ambientalmente costoso y, a menudo, funciona como una "caja negra", careciendo de interpretabilidad. Los autores argumentan que el MNEP es fundamentalmente un problema de optimización estática con características de entrada limitadas y restricciones de escalabilidad inherentes (por ejemplo, espaciado fijo entre estaciones), lo que sugiere que las redes neuronales complejas pueden ser innecesarias. Además, los enfoques existentes suelen priorizar la eficiencia (utilitarismo) sobre la equidad social, fallando en abordar adecuadamente la distribución justa de los beneficios de transporte entre diferentes grupos socioeconómicos.

Metodología
Los autores proponen un marco novedoso que combina una reformulación del problema con un enfoque de Aprendizaje por Refuerzo Tabular (Tabular RL), incorporando explícitamente criterios de equidad social.

1. Reformulación del Problema (NMRDP):
   El MNEP se reformula como un Proceso de Decisión de Recompensa No Markoviano (NMRDP). A diferencia de los enfoques previos de Deep RL que tratan cada celda de la cuadrícula como una acción potencial (lo que resulta en un espacio de acciones que escala linealmente con el tamaño de la cuadrícula, $O(n \times m)$), el método propuesto desacopla el proceso en dos etapas:

• Selección del Estado Inicial: El agente selecciona una celda de inicio para la línea de metro.
• Navegación Secuencial: El agente se mueve a través de la cuadrícula eligiendo una de ocho direcciones discretas (Norte, Sur, Este, Oeste y cuatro diagonales).
  Esto reduce el espacio de acciones a un tamaño constante de 8 (independientemente de las dimensiones de la cuadrícula) para todos los pasos después de la selección inicial, reduciendo la complejidad temporal a $O(1)$ por paso. El estado se simplifica a la ubicación actual del agente. Debido a que la recompensa depende de la historia de las estaciones visitadas (para calcular la demanda directa y de transferencia), el proceso viola la propiedad de Markov estricta, de ahí la formulación NMRDP.

2. Algoritmo (Aprendizaje por Refuerzo Tabular de Monte Carlo):
   Los autores emplean un algoritmo de Aprendizaje por Refuerzo Tabular basado en Monte Carlo. El agente mantiene dos tablas:

• $V_{start}(S_0)$: Estima el retorno esperado para seleccionar una celda específica como punto de partida.
• $Q(S, A)$: Estima el valor de tomar una acción direccional específica desde un estado actual.
  El agente utiliza una estrategia $\epsilon$-greedy para la exploración y explotación. Las actualizaciones se realizan al final de cada episodio mediante la estimación de Monte Carlo del retorno total $J$, ajustando los valores $V$ y $Q$ basándose en la diferencia entre los retornos estimados y los reales.

3. Integración de la Equidad Social:
   La función de recompensa se extiende más allá de la simple maximización de la demanda para incluir la equidad social. Los autores definen grupos ($G$) basados en indicadores socioeconómicos (específicamente, índices de precios de la vivienda como indicador de desarrollo). Se prueban tres formulaciones de recompensa:

• Utilitarista (Máxima Eficiencia): Maximiza la demanda total satisfecha.
• Reparto Igualitario (Equidad Horizontal): Utiliza el Índice de Gini Generalizado (GGI) para minimizar las disparidades en los beneficios entre grupos.
• Justicia Rawlsiana (Equidad Vertical): Maximiza el beneficio para el grupo más desfavorecido (el quintil más bajo de precios de vivienda).

Contribuciones Clave

• Reformulación del Problema: El artículo demuestra que reformular el MNEP como un NMRDP con un espacio de acciones desacoplado permite el uso de métodos tabulares simples, reduciendo drásticamente la complejidad del espacio de búsqueda sin restringir el espacio de soluciones.
• Eficiencia Algorítmica: La propuesta de un algoritmo de Aprendiaje por Refuerzo Tabular de Monte Carlo que logra un rendimiento competitivo con significativamente menos episodios de entrenamiento en comparación con el Deep RL.
• Marco Consciente de la Equidad: La integración de diversos objetivos de bien social (utilitarista, igualitario y rawlsiano) en el marco de RL, proporcionando un mecanismo flexible para equilibrar la eficiencia y la justicia en la planificación del transporte.
• Interpretabilidad: El uso de métodos tabulares proporciona una interpretabilidad inherente, permitiendo a los tomadores de decisiones visualizar políticas óptimas, distribuciones de recompensa y valores Q directamente, a diferencia de las representaciones latentes del Deep RL.

Resultados Experimentales
El método fue evaluado en dos entornos del mundo real: Xi'an, China, y Ámsterdam, Países Bajos.

• Desempeño: El TabularMNEP logró un rendimiento comparable con los métodos de vanguardia de Deep RL en todas las funciones de recompensa (Eficiencia, GGI(2), GGI(4) y Rawls). En algunos casos, fue ligeramente inferior al Deep RL pero se mantuvo dentro de los intervalos de confianza, superando significativamente a los modelos base de Algoritmos Genéticos y Búsqueda Voraz (Greedy Search).
• Eficiencia: El enfoque Tabular requirió solo 25,000 episodios de entrenamiento, una reducción de 18 veces en comparación con los 448,000 episodios requeridos por el modelo base de Deep RL.
• Impacto Ambiental: Debido a la reducción en el tiempo de entrenamiento y la falta de dependencia de GPU (aunque se probó en nodos GPU para asegurar la equidad en la comparación), el método Tabular redujo las emisiones de carbono estimadas en un factor de 12 en promedio.
• Resultados de Equidad: Los experimentos confirmaron que las diferentes funciones de recompensa lograron desplazar el diseño de la red. La Máxima Eficiencia favoreció las zonas de alta demanda (a menudo más ricas), mientras que las recompensas GGI y Rawlsianas lograron redistribuir los beneficios hacia los grupos de menores ingresos, aunque con costos variables para la eficiencia general.

Significancia y Reivindicaciones
El artículo sostiene que los modelos complejos de Aprendizaje Profundo de "caja negra" no siempre son necesarios para problemas de optimización combinatoria como el MNEP. Al reformular cuidadosamente el problema para reducir el espacio de acciones, los métodos tabulares más simples, eficientes en recursos e interpretables pueden ofrecer resultados de vanguardia. Los autores enfatizan que este enfoque ofrece una solución "replicable, modular, interpretable y eficiente en recursos".

El trabajo destaca la importancia de considerar la equidad social en la planificación automatizada del transporte, demostando que el RL puede ajustarse para optimizar la justicia sin sacrificar demasiado la eficiencia. Sin embargo, los autores mantienen una postura modesta respecto a la escalabilidad, reconociendo que, si bien los métodos tabulares funcionan bien para el MNEP debido a los espacios de estados restringidos, pueden no generalizarse a problemas con representaciones de estado inherentemente masivas. También advierten que, sin un diseño cuidadoso de la recompensa y supervisión humana, la toma de decisiones automatizada en la planificación urbana corre el riesgo de reforzar los sesgos existentes.