Resumo Técnico: Algoritmos de GNEP Distribuídos sem Compartilhamento de Multiplicadores e Aplicações à Coordenação Multi-Robô e Aprendizado Ativo Baseado em Bandidos Contextuais

1. Definição do Problema

A tese aborda dois desafios distintos, porém significativos, na otimização distribuída e no aprendizado de máquina:

Parte I: Problemas de Equilíbrio de Nash Generalizado (GNEPs)
Em muitos sistemas multiagentes (ex: redes elétricas, roteamento de tráfego, coordenação multi-robô), os agentes devem minimizar funções de custo locais sujeitas tanto a restrições individuais quanto a restrições de acoplamento compartilhadas. Esta formulação leva ao Problema de Equilíbrio de Nash Generalizado (GNEP). Os algoritmos distribuídos existentes para resolver GNEPs normalmente dependem da imposição de consenso entre os multiplicadores de Lagrange associados às restrições compartilhadas. Esse requisito exige a troca de variáveis auxiliares e multiplicadores entre os agentes, aumentando a sobrecarga de comunicação e potencialmente comprometendo a privacidade. Além disso, a maioria dos métodos existentes é restrita ao cálculo de Equilíbrios de Nash Generalizados variacionais (v-GNEs), uma subclasse específica de equilíbrios, em vez do conjunto completo de Equilíbrios de Nash Generalizados (GNEs).

**Parte II: Aprendizado Ativo Baseado em Bandidos Contextuais
O aprendizado ativo visa reduzir o custo de rotulagem no aprendizado supervisionado ao selecionar de forma criteriosa os pontos de dados mais informativos. Embora existam inúmeras estratégias manuais (ex: amostragem de incerteza, amostragem de diversidade), seu desempenho é altamente dependente da distribuição subjacente dos dados, que é frequentemente desconhecida. Estruturas adaptativas existentes que combinam essas estratégias frequentemente utilizam algoritmos de bandidos adversários. Esses métodos são excessivamente conservadores, mantendo uma exploração persistente sem aproveitar o contexto ambiental, o que frequentemente resulta em um desempenho semelhante à seleção aleatória.

2. Metodologia

Parte I: Algoritmos Totalmente Distribuídos para GNEPs

O autor propõe um algoritmo continuamente distribuído baseado em dinâmica primal-dual que elimina a necessidade de compartilhamento de multiplicadores.

• Dinâmica Primal-Dual: O algoritmo modela o sistema como um Sistema Dinâmico Projetado (PDS). Os agentes atualizam suas variáveis de decisão ($z_v$) e multiplicadores locais ($\lambda_v, \mu_v$) usando apenas informações locais e dados trocados com vizinhos através de grafos de interação específicos (grafo de função de custo e grafo de restrição compartilhada).
• Transformação de Multiplicadores: Uma inovação teórica fundamental é a transformação dos multiplicadores compartilhados. Em vez de impor o consenso ($\lambda_v = \lambda_u$), o método decompõe os multiplicadores em um estado de referência comum e um termo de desvio ($\Delta_v$). Demonstra-se que a dinâmica dos termos de desvio é constante ou não crescente ao longo do tempo, dependendo do tipo de restrição (igualdade vs. desigualdade).
• Análise de Convergência:
  • Restrições de Igualdade: Para jogos com mapeamentos de custo fortemente monotônicos e restrições de igualdade lineares compartilhadas, o autor prova a estabilidade assintótica global. As variáveis primais convergem para um GNE único, enquanto as variáveis duais convergem para um conjunto de multiplicadores válidos. O equilíbrio limite depende da inicialização dos termos de desvio.
  • Restrições de Desigualdade: Para restrições de desigualdade compartilhadas com custos convexos quadráticos, a análise utiliza argumentos de entrada limitada saída limitada (BIBO) e limitação de trajetória para provar a convergência para um GNE, mesmo quando a dinâmica primal-dual induzida não é monotônica.
• Discretização: Para permitir a implementação prática, a tese desenvolve três esquemas de discretização:
  1. Passo Diminuinte (Diminishing Step Size): Mimetiza a dinâmica contínua assintoticamente, mas converge lentamente ($O(1/\sqrt{k})$).
  2. Euler Reverso (Resolvente): Utiliza um passo fixo e requer a resolução de um Problema de Equilíbrio de Nash (NEP) interno em cada etapa. Ele alcança uma taxa de convergência de $o(1/k)$.
  3. Splitting Forward-Backward: Um esquema híbrido que evita a necessidade de um solver interno ao tratar partes do operador de forma explícita e outras de forma implícita. Requer um passo globalmente acordado, mas oferece um equilíbrio entre custo computacional e taxa de convergência.

Parte II: Aprendizado Ativo Adaptativo Contextual (CAAL)

A segunda parte introduz o Aprendizado Ativo Adaptativo Contextual (CAAL), uma estrutura de meta-estratégia que utiliza bandidos contextuais para selecionar dinamicamente a melhor estratégia de aprendizado ativo manual.

• Estrutura: O problema é modelado como um bandido contextual onde os "braços" são diferentes estratégias de aprendizado ativo manuais (ex: K-Center, Diversidade Informativa).
• Contexto e Recompensa: Ao contrário das abordagens de bandidos adversários, o CAAL incorpora o contexto externo (ex: o tamanho atual do conjunto de dados rotulado) para prever recompensas. A recompensa é definida como a melhoria relativa no desempenho do modelo (ex: mudança na ROC-AUC) entre as iterações, em vez do desempenho absoluto, para lidar com a não-estacionariedade.
• Algoritmo: O método emprega um algoritmo de Upper Confidence Bound linear não-estacionário (especificamente, Sliding Window LinUCB) para estimar a função de recompensa $\theta_a^\top c_k$. Isso permite que o agente explore a previsibilidade das recompensas baseada no contexto, reduzindo o conservadorismo inerente aos métodos de bandidos adversários.

3. Principais Contribuições

Para GNEPs:

1. Primeiro Algoritmo Distribuído Sem Multiplicadores: Tanto quanto o autor sabe, este é o primeiro algoritmo distribuído que computa GNEs sem exigir consenso ou troca de multiplicadores de Lagrange. Isso reduz significativamente a sobrecarga de comunicação (em aproximadamente um terço em configurações de grafos específicas) e aumenta a privacidade.
2. Convergência de GNE Geral: O método proposto não é restrito aos v-GNEs. Ele converge para GNEs gerais, sendo que o equilíbrio específico alcançado depende da inicialização. Isso aborda a limitação dos métodos existentes que visam apenas o v-GNE único.
3. Novas Técnicas de Prova: A tese desenvolve técnicas de prova para lidar com dinâmicas induzidas não-monotônicas e equilíbrios não-únicos, utilizando análise de estabilidade de Lyapunov e argumentos de trajetória limitada.

Para Aprendizado Ativo:

1. Adaptação Contextual: O trabalho propõe incorporar informações contextuais no aprendizado ativo baseado em bandidos para reduzir o conservadorismo das estruturas de bandidos adversários.
2. Foco na Seleção de Lotes (Batch Selection): Diferente de muitos trabalhos anteriores focados na seleção de amostra única, esta abordagem enfatiza a robustez entre diferentes tamanhos de lote, o que é mais alinhado com aplicações industriais.
3. Abordagem de Meta-Aprendizado: O método foca na seleção baseada em meta-aprendizado em vez de aprendizado profundo, tornando-o mais adequado para dados tabulares, que dominam os conjuntos de dados industriais.

4. Resultados

Simulações de GNEP:

• Coordenação Multi-Robô: O algoritmo foi testado em problemas de posicionamento multi-robô e cobertura de semi-espaço. Os resultados demonstraram convergência para GNEs a partir de várias inicializações, destacando a não-unicidade das soluções. A discretização forward-backward (Algoritmo 4.10) mostrou taxas de convergência comparáveis aos métodos baseados em consenso, mas com comunicação significativamente reduzida por iteração.
• Competição de Cournot: O método foi aplicado a um jogo de Cournot com 20 agentes e 7 mercados. O algoritmo convergiu com sucesso para um GNE para qualquer inicialização, preservando a privacidade dos agentes e demonstrando escalabilidade.

Experimentos de Aprendizado Ativo:

• Conjuntos de Dados: Experimentos foram conduzidos em conjuntos de dados públicos (ILPD, I vs J, Australian Credit, German Credit) usando regressão logística como classificador base.
• Desempenho: O CAAL foi comparado contra a linha de base adaptativa de última geração (ALBL) e estratégias manuais (K-Center, Diversidade Informativa).
  • O CAAL superou o ALBL e as estratégias individuais na maioria dos conjuntos de dados, particularmente para tamanhos de lote maiores que 5.
  • A análise de "Previsão de Recompensa" mostrou que o modelo de regressão linear pôde prever com precisão as tendências de recompensa com base no contexto, validando a suposição de linearidade local.
  • A análise de "Histórico de Puxada" (Pull History) indicou que o CAAL identificou e explorou com sucesso a estratégia ideal após uma fase inicial de exploração, enquanto o ALBL tendia a selecionar braços com probabilidade quase igual devido à sua natureza conservadora.
• Implantação: A estrutura foi implantada nos sistemas de produção internos da Amazon, embora os resultados de conjuntos de dados internos tenham sido omitidos devido à confidencialidade.

5. Significância e Alegações

A tese afirma preencher lacunas críticas tanto na teoria de jogos distribuídos quanto no aprendizado de máquina adaptativo:

• Em Otimização Distribuída: Ao remover o requisito de compartilhamento de multiplicadores, a estrutura proposta oferece uma solução mais escalável e que preserva a privacidade para sistemas multiagentes de larga escala. A capacidade de convergir para GNEs gerais, em vez de apenas v-GNEs, expande a aplicabilidade do cálculo de equilíbrio distribuído para cenários onde o preço uniforme ou a coordenação centralizada não são viáveis.
• Em Aprendizado Ativo: O trabalho demonstra que o aproveitamento de informações contextuais pode melhorar significativamente a adaptabilidade das estratégias de aprendizado ativo em comparação com abordagens puramente adversárias. A estrutura CAAL proposta fornece uma solução prática e amigável para a indústria de aprendizado ativo em modo de lote, que se adapta a distribuições de dados desconhecidas sem exigir arquiteturas de aprendizado profundo.

O autor observa que, embora a análise de tempo contínuo forneça garantias teóricas fortes, os esquemas de discretização introduzem suposições específicas (ex: continuidade de Lipschitz, compacidade) necessárias para a convergência. Da mesma forma, para o componente de aprendizado ativo, a complexidade de exploração depende do número de estratégias candidatas (braços), e a estrutura atualmente depende do conhecimento de domínio para definir o conjunto inicial de estratégias manuais. É proposto como trabalho futuro estender os algoritmos de GNEP para restrições convexas mais gerais e refinar a análise teórica da estrutura de bandidos contextuais.