Learning from Local Walks on Dynamic Graphs with Bandit Feedback

Resumo Técnico: Aprendizado por Caminhadas Locais em Grafos Dinâmicos com Feedback de Bandidos

Formulação do Problema
Este artigo aborda o problema estocástico de multi-armas de bandido (MAB) em um cenário onde o aprendiz está restrito ao movimento local em um grafo dinâmico. Diferente dos modelos clássicos de MAB onde qualquer braço está disponível em cada rodada, ou modelos de feedback-grafo onde observações laterais estão disponíveis, aqui o aprendiz pode selecionar apenas seu nó atual ou um vizinho imediato com base na conectividade do grafo em cada passo de tempo específico.

• Configuração: Os braços correspondem aos vértices $A = \{1, \dots, n\}$ de um grafo não direcionado variante no tempo $G_t = (A, E_t)$.
• Restrições: No tempo $t$, o aprendiz observa apenas a vizinhança local $L_t(a_{t-1})$ e deve escolher $a_t \in L_t(a_{t-1})$. O processo do grafo é oblívio (independente das ações do aprendiz).
• Desafio Central: Esta configuração desacopla a identificação do melhor braço da explotação. Nos bandidos clássicos, identificar o braço ótimo $a^\star$ permite a explotação imediata. Neste cenário dinâmico, mesmo após $a^\star$ ser identificado, o aprendiz pode estar estruturalmente isolado dele devido à topologia evolutiva. A aprendibilidade exige que o ambiente forneça consistentemente caminhos navegáveis, não apenas que a união de todos os grafos ao longo do horizonte seja conectada.

Metodologia e Condições Estruturais
Os autores adotam uma estrutura de exploração-então-compromisso (explore-then-commit), separando o problema em exploração (coleta de amostras) e navegação (alcançar o alvo identificado). Para garantir a aprendibilidade, eles introduzem uma condição estrutural agnóstica ao processo baseada na caminhada canônica (uma caminhada aleatória simples onde o aprendiz permanece ou move-se uniformemente para um vizinho).

• Mistura de Janela Deslizante com Distribuição Estacionária Comum (Definição 1): O artigo rejeita condições de conectividade de todo o horizonte (ex: a união de todos os grafos sendo conectada) como insuficientes, pois falham em garantir a alcançabilidade em tempos de parada arbitrários. Em vez disso, impõem uma condição sobre a caminhada aleatória induzida:
  1. Distribuição Estacionária Comum: Cada instantâneo do grafo $G_t$ induz um kernel reversível $U_t$ com uma distribuição estacionária comum $\pi$ (ex: alcançada por sequências de graus fixos).
  2. Mistura de Janela Deslizante: Em cada janela de tempo de comprimento $W$, pelo menos uma fração $\rho$ das rodadas deve possuir um spectral gap $\ge \gamma$.
     Esta condição garante que a caminhada se misture em direção a $\pi$ uniformemente ao longo do tempo, impedindo que o aprendiz fique preso em subgrafos locais indefinidamente, independentemente de quando a exploração termina.

Algoritmos
O artigo analisa uma família de algoritmos operando sob este regime:

1. LEX (Exploração Preguiçosa de Orçamento Fixo): Utiliza a caminhada canônica para exploração por um orçamento fixo $T_{exp}$ determinado pelos parâmetros de mistura e lacunas de recompensa (reward gaps). Ela se compromete com o líder empírico e navega usando a caminhada canônica se o alvo não for imediatamente alcançável.
2. CB-LEX (Parada Baseada em Confiança): Substitui o orçamento fixo por uma regra de parada dependente de dados. Ela termina quando o Limite Inferior de Confiança (LCB) do líder empírico domina os Limites Superiores de Confiança (UCBs) de todos os outros braços (não apenas o segundo colocado), garantindo robustez contra amostragem desigual.
3. RALEX (Exploração Consciente da Recompensa): Introduz um kernel enviesado pela recompensa que mistura a caminhada canônica com uma proposta otimista (softmax sobre recompensas estimadas). Crucialmente, mantém um "piso canônico" ($\epsilon_0$) para garantir que as propriedades de mistura estrutural da caminhada canônica sejam preservadas, garantindo a segurança no pior caso.

Resultos Principais e Limites de Regret
Sob a condição de mistura $(W, \rho, \gamma, \pi)$, os autores estabelecem regret esperado sublinear ($o(T)$) para todos os algoritmos propostos. Os limites de regret decompõem-se em dois componentes distintos:

1. Regret de Aprendizado: Escala com a dificuldade estatística (inverso das lacunas $\Delta^{-2}$) e o overhead de mistura ($\tau_0$), representando o custo de identificar o melhor braço.
2. Regret de Navegação: Um custo estrutural independente do horizonte $T$, representando o tempo esperado para alcançar o braço ótimo identificado a partir do ponto de parada.

• LEX/CB-LEX: Alcançam um regret de ordem $O(\tau_0 \cdot \Psi \cdot \log T)$, onde $\Psi$ captura a complexidade das lacunas e massas estacionárias.
• RALEX: Prova que o viés consciente da recompensa é compatível com regret sublinear. Embora o limite de pior caso seja conservador (devido ao piso canônico), o artigo fornece um teorema separado (Teorema 4) mostrando que, se o viés consciente da recompensa aumentar com sucesso a probabilidade de visitação de braços de "quase-gargalo", um ganho de desempenho provável (melhoria multiplicativa no termo de aprendizado) é alcançado.

Significância e Alegações
O artigo posiciona-se como uma caracterização estrutural da aprendibilidade para bandidos localmente restritos em grafos dinâmicos, em vez de uma proposta de minimização de regret quase-ótimo para famílias de grafos específicas (como grafos completos).

• Invariância de Deslocamento: A principal contribuição é a condição de mistura de janela deslizante invariante ao deslocamento. Isso garante que as suposições estruturais necessárias para a navegação se mantensem após o tempo de parada aleatório da exploração, um requisito que as condições de todo o horizonte não atendem.
• Desacoplamento: O trabalho separa explicitamente o custo estatístico do aprendizado do custo estrutural da navegação, fornecendo um arcabouço teórico limpo para ambientes dinâmicos.
• Agnosticismo de Processo: Ao contrário de trabalhos anteriores que dependem de processos de grafos específicos (ex: i.i.d. Erdős–Rényi ou Markoviano de arestas), este artigo fornece um teorema que é válido para qualquer sequência de grafos que satisfaça a condição de mistura centrada na caminhada, cobrindo processos naturais como sobreposições regulares rotativas e reconfigurações de preservação de grau.
• Segurança vs. Ganho: A análise do RALEX distingue entre um "teorema de segurança" (garantindo regret sublinear com qualquer parâmetro de viés) e um "teorema de ganho" (certificando a melhoria de desempenho sob condições específicas na proposta consciente da recompensa).

Os autores concluem que seu trabalho estabelece um "regime positivo" onde a caminhada canônica intrínseca é suficiente para o aprendizado, oferecendo uma base para extensões futuras para kernels mais complexos, como caminhadas do tipo Metropolis.