Learning Ordinal Response Policies in Rank-Based Stochastic Prize-Collecting Games

Resumo Técnico: Aprendizado de Políticas de Resposta Ordinal em Jogos de Coleta de Prêmios Estocásticos Baseados em Ranking

1. Definição do Problema

O artigo aborda as limitações do Problema de Orienteamento de Equipe (TOP - Team Orienteering Problem) em sistemas multiagentes. Embora o TOP forneça um framework unificado para roteamento cooperativo (ex: entrega de última milha, vigilância), onde agentes maximizam uma utilidade coletiva sob orçamentos de viagem, ele falha ao modelar cenários envolvendo agentes autointeressados competindo em ambientes de recursos escassos. Em tais configurações, os agentes (ex: frotas de entrega concorrentes ou motoristas de crowdsourcing) priorizam recompensas individuais em vez do ganho coletivo, e suas interações são regidas por transições estocásticas e restrições de energia.

Para preencher essa lacuna, os autores propõem o Jogo de Orienteamento de Coleta de Prêmios Estocásticos (SPCOG - Stochastic Prize-Collecting Orienteering Game). Em um SPCOG:

• Os agentes operam em um grafo ponderado com distribuições de prêmios estocásticos nos nós.
• Os agentes possuem orçamentos de viagem individuais e visam maximizar suas próprias recompensas cumulativas.
• Resolução de Conflitos: Quando múltiplos agentes visitam o mesmo nó simultaneamente, aplica-se uma regra baseada em ranking: o agente com o maior ranking global (menor índice) reivindica o prêmio integralmente; outros recebem zero.
• Objetivo: Encontrar políticas convergentes para agentes independentes para maximizar recompensas individuais, reconhecendo que a recompensa total da equipe pode ser inferior ao ótimo do TOP cooperativo devido à competição.

2. Metodologia

Análise Teórica de Equilíbrios
Os autores primeiro analisam a existência de um Equilíbrio de Nash Puro (PNE) em SPCOGs:

• Grafos Completos: Eles provam que, para grafos completos, existe um PNE único sob resolução de conflito baseada em ranking. Neste equilíbrio, o $i$-ésimo agente ranqueado seleciona o $i$-ésimo maior prêmio disponível. A recompensa total neste PNE coincide com a solução ótima de um TOP cooperativo equivalente.
• Grafos Estrela (Star Graphs): Um PNE único semelhante existe onde os agentes se movem para o $i$-ésimo maior prêmio em estágios alternados.
• Grafos Arbitrários: O artigo demonstra, via contraexemplo (um cenário específico de dois agentes), que um PNE não necessariamente existe para estruturas de grafos arbitrárias quando os agentes se movem simultaneamente, destacando a complexidade de resolver esses jogos em comparação com formulações de Stackelberg (líder-seguidor).

Conceito de Rank Ordinal (OR - Ordinal Rank)
Para enfrentar o desafio da observabilidade parcial e do espaço de estados exponencial em grafos gerais, os autores introduzem o Rank Ordinal (OR):

• Oponentes Imediatos: Os agentes são agrupados em "jogos de estágio localizados" baseados em um "grafo separador" onde as arestas conectam agentes com conjuntos alcançáveis sobrepostos.
• Definição: O OR de um agente é definido como $1 +$ o número de agentes com um ranking global superior (menor índice) dentro de seu vizinhança imediata (componente conectada).
• Significância: O OR resume a competição local mais influente. Os autores hipotetizam que condicionar as políticas ao OR, em vez do estado global ou ranking global, atua como um forte viés indutivo, permitindo que os agentes aprendam respostas ótimas aos oponentes imediatos sem a necessidade de informações globais.

Aprendizado de Resposta Fictícia Ordinal (FORL - Fictitious Ordinal Response Learning)
Os autores propõem o FORL, um algoritmo de aprendizado regulado por entropia projetado para aprendizado por reforço multiagente independente (MARL):

• Atualizações Sequenciais: Os agentes atualizam suas políticas sequencialmente com base em seu ranking. Agentes de ranking superior atualizam primeiro, assumindo que os agentes de ranking inferior seguem políticas aleatórias ou estacionárias.
• Bootstrapping: O agente de maior ranking aprende primeiro para resolver o problema estocástico de agente único subjacente. Uma vez que sua política atinge um limiar de confiança (medido pela entropia), seus parâmetros são compartilhados com os demais.
• Jogo Fictício (Fictitious Play): Agentes subsequentes atualizam suas políticas jogando contra as políticas "estacionárias" dos agentes de ranking superior.
• Regulação de Entropia: O algoritmo utiliza um limiar de entropia decrescente ($H_{stop}$) para garantir a convergência. Se um PNE existir, o algoritmo converge para uma estratégia pura (entropia $\to$ 0); caso contrário, fornece limites de confiança sobre a qualidade da política de estratégia mista.
• Arquitetura de Política: As políticas são modeladas usando uma arquitetura baseada em Transformer (TRXL-I) e são condicionadas a observações locais aumentadas com o OR. O mascaramento de ações é usado para impor restrições de grafo.

3. Principais Contribuições

1. Formulação SPCOG: Introdução de uma variante de teoria dos jogos do TOP para agentes autointeressados em ambientes estocásticos e com restrição de energia.
2. Garantias Teóricas: Prova de um PNE único em grafos completos e estrela que se alinha com a solução ótima do TOP, e um contraexemplo mostrando a não existência de PNEs em grafos arbitrários.
3. Rank Ordinal (OR): Proposta do OR como uma representação local concisa da posição competitiva de um agente, que serve como um forte viés indutivo para o aprendizado.
4. Algoritmo FORL: Desenvolvimento de um algoritmo inspirado em jogo fictício e regulado por entropia, que produz políticas convergentes em cenários de aprendizado independente.
5. Validação Empírica: Demonstração de que políticas condicionadas por OR superam políticas condicionadas por ranking global em termos de generalização, escalabilidade e eficiência de treinamento.

4. Resultados Experimentais

Experimentos foram conduzidos em redes de estradas do mundo real (Estocolmo e Manhattan) com distribuições de prêmios estáticas e dinâmicas.

• Desempenho vs. TOP: Em grafos completos, as políticas condicionadas por OR alcançaram 95% da recompensa ótima do TOP. Em grafos incompletos, o equilíbrio de pior caso alcançou 87% da solução ótima.
• Generalização: Políticas treinadas com FORL e condicionamento por OR demonstraram capacidades superiores de transferência "zero-shot" para distribuições de prêmios desbalanceadas e orientadas por demanda, comparadas ao Aprendizado de Política Independente (IPL) e métodos de compartilhamento de parâmetros condicionados ao estado global.
• Escalabilidade: Ao escalar para equipes de até 25 agentes, as políticas condicionadas por OR (PS-OR) mostraram um escalonamento linear na recompensa total com baixa variância. Em contraste, políticas condicionadas pelo ranking global (PS-GR) exibiram ganhos sublineares e variância significativamente maior.
• Eficiência: O método FORL exigiu de 1,56x a 2,2x menos tempo de treinamento para atingir perfis de recompensa comparáveis em relação às linhas de base de compartilhamento de parâmetros e aprendizado independente.

5. Significância e Alegações

O artigo afirma que o conceito de Rank Ordinal desacopla efetivamente a necessidade de informação de estado global em jogos de roteamento multiagentes. Ao focar nos "oponentes imediatos" locais e seus rankings relativos, os agentes podem aprender estratégias robustas que generalizam bem para maiores tamanhos de equipe e ambientes não vistos.

Os autores afirmam que o FORL fornece um mecanismo prático para obter políticas convergentes em jogos de roteamento competitivos e estocásticos onde as suposições cooperativas tradicionais falham. O trabalho sugere que, em cenários de conflito baseados em ranking, a informação local condicionada à posição ordinal é um sinal de aprendizado mais eficaz do que o estado global ou o ranking global, ofereando uma solução escalável para frotas robóticas heterogêneas e autointeressadas.