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

Resumo Técnico: Transporte Inteligente Sem Neurônios – Expansão de Rede Metro Justa com Aprendizado por Reforço Tabular

Definição do Problema
O artigo aborda o Problema de Expansão de Rede Metro (MNEP - Metro Network Expansion Problem), um subconjunto específico do Problema de Design de Rede de Transporte (TNDP). O objetivo é projetar uma nova linha de metrô dentro de uma rede urbana existente para maximizar a demanda de viagens capturada, sujeito a restrições de orçamento de construção ($B$) e ao número máximo de estações ($T$). Tradicionalmente, o MNEP é modelado como um problema de otimização combinatória onde a cidade é representada como uma grade, e o objetivo é encontrar uma sequência de células adjacentes que formem uma linha para maximizar a soma da demanda de Origem-Destino (OD) satisfeita.

Uma lacuna crítica identificada na literatura é a dependência de Aprendizado por Reforço Profundo (Deep Reinforcement Learning - Deep RL) para esses problemas. Embora o Deep RL tenha demonstrado sucesso em processos de decisão sequencial complexos, ele é computacionalmente caro, ambientalmente custoso e frequentemente funciona como uma "caixa preta", carecendo de interpretabilidade. Os autores argumentam que o MNEP é fundamentalmente um problema de otimização estática com recursos de entrada limitados e restrições de escalabilidade inerentes (por exemplo, espaçamento fixo entre estações), sugerindo que redes neurais complexas podem ser desnecessárias. Além disso, as abordagens existentes frequentemente priorizam a eficiência (utilitarismo) em detrimento da equidade social, falhando em abordar adequadamente a distribuição justa dos benefícios de transporte entre diferentes grupos socioeconômicos.

Metodologia
Os autores propõem um novo framework que combina uma reformulação do problema com uma abordagem de Aprendizado por Reforço Tabular (Tabular RL), incorporando explicitamente critérios de equidade social.

1. Reformulação do Problema (NMRDP):
   O MNEP é reformulado como um Processo de Decisão de Recompensa Não-Markoviano (NMRDP). Diferente das abordagens anteriores de Deep RL que tratam cada célula da grade como uma potencial ação (resultando em um espaço de ação que escala linearmente com o tamanho da grade, $O(n \times m)$), o método proposto desacopla o processo em duas etapas:

• Seleção do Estado Inicial: O agente seleciona uma célula inicial para a linha de metrô.
• Navegação Sequencial: O agente move-se através da grade escolhendo uma de oito direções discretas (N, S, L, O e quatro diagonais).
  Isso reduz o espaço de ação para um tamanho constante de 8 (independentemente das dimensões da grade) para todos os passos após a seleção inicial, reduzindo a complexidade de tempo para $O(1)$ por passo. O estado é simplificado para a localização atual do agente. Como a recompensa depende do histórico de estações visitadas (para calcular a demanda direta e de transferência), o processo viola a propriedade estrita de Markov, daí a formulação NMRDP.

2. Algoritmo (Monte Carlo Tabular RL):
   Os autores utilizam um algoritmo de Aprendizado por Reforço Tabular baseado em Monte Carlo. O agente mantém duas tabelas:

• $V_{start}(S_0)$: Estima o retorno esperado para selecionar uma célula específica como ponto de partida.
• $Q(S, A)$: Estima o valor de realizar uma ação direcional específica a partir de um estado atual.
  O agente utiliza uma estratégia $\epsilon$-greedy para exploração e explotação. As atualizações são realizadas ao final de cada episódio usando a estimativa de Monte Carlo do retorno total $J$, ajustando os valores $V$ e $Q$ com base na diferença entre o retorno estimado e o real.

3. Integração de Equidade Social:
   A função de recompensa é estendida além da simples maximização de demanda para incluir a equidade social. Os autores definem grupos ($G$) baseados em indicadores socioeconômicos (especificamente índices de preços de imóveis como um proxy para desenvolvimento). Três formulações de recompensa são testadas:

• Utilitarista (Máxima Eficiência): Maximiza a demanda total satisfeita.
• Compartilhamento Igualitário (Equidade Horizontal): Utiliza o Índice de Gini Generalizado (GGI) para minimizar disparidades nos benefícios entre os grupos.
• Justiça Rawlsiana (Equidade Vertical): Maximiza o benefício para o grupo mais desfavorecido (quintil mais baixo de preço de imóveis).

Principais Contribuições

• Reformulação do Problema: O artigo demonstra que reformular o MNEP como um NMRDP com um espaço de ação desacoplado permite o uso de métodos tabulares simples, reduzindo drasticamente a complexidade do espaço de busca sem restringir o espaço de solução.
• Eficiência Algorítmica: A proposta de um algoritmo de Aprendizado por Reforço Tabular de Monte Carlo que alcança um desempenho competitivo com significativamente menos episódios de treinamento do que o Deep RL.
• Framework Consciente de Equidade: A integração de diversos objetivos de bem social (utilitário, igualitário e Rawlsiano) no framework de RL, fornecendo um mecanismo flexível para equilibrar eficiência e justiça no planejamento de transportes.
• Interpretabilidade: O uso de métodos tabulares proporciona interpretabilidade inerente, permitindo que os tomadores de decisão visualizem políticas ótimas, distribuições de recompensa e valores Q diretamente, ao contrário das representações latentes do Deep RL.

Resultados Experimentais
O método foi avaliado em dois ambientes do mundo real: Xi'an, China, e Amsterdã, Holanda.

• Desempenho: O TabularMNEP alcançou desempenho comparável aos métodos de ponta de Deep RL em todas as funções de recompensa (Eficiência, GGI(2), GGI(4) e Rawls). Em alguns casos, subperformou ligeiramente o Deep RL, mas permaneceu dentro dos intervalos de confiança, superando significativamente as linhas de base de Algoritmos Genéticos e Busca Gananciosa (Greedy Search).
• Eficiência: O método Tabular exigiu apenas 25.000 episódios de treinamento, uma redução de 18 vezes em comparação com os 448.000 episódios exigidos pela linha de base de Deep RL.
• Impacto Ambiental: Devido à redução no tempo de treinamento e à ausência de dependência de GPU (embora testado em nós de GPU para fins de comparação justa), o método Tabular reduziu as emissões de carbono estimadas por um fator de 12 em média.
• Resultos de Equidade: Os experimentos confirmaram que diferentes funções de recompensa conseguiram alterar o design da rede. A Máxima Eficiência favoreceu áreas de alta demanda (frequentemente mais ricas), enquanto as recompensas GGI e Rawlsiana redistribuíram com sucesso os benefícios para os grupos de menor renda, embora com custos variados para a eficiência global.

Significância e Alegações
O artigo afirma que modelos complexos de Deep Learning, de caixa preta, nem sempre são necessários para problemas de otimização combinatória como o MNEP. Ao reformular cuidadosamente o problema para reduzir o espaço de ação, métodos tabulares mais simples, eficientes em recursos e interpretáveis podem produzir resultados de ponta. Os autores enfatizam que esta abordagem oferece uma "solução replicável, modular, interpretável e eficiente em recursos".

O trabalho destaca a importância de considerar a equidade social no planejamento automatizado de transportes, demonstrando que o RL pode ser ajustado para otimizar a justiça sem sacrificar excessivamente a eficiência. No entanto, os autores mantêm uma postura modesta quanto à escalabilidade, reconhecendo que, embora os métodos tabulares funcionem bem para o MNEP devido aos espaços de estado restritos, eles podem não se generalizar para problemas com representações de estado inerentemente massivas. Eles também alertam que, sem um design de recompensa cuidadoso e supervisão humana, a tomada de decisão automatizada no planejamento urbano corre o risco de reforçar preconceitos existentes.