Resumo Técnico: Bandidos Multi-Braços com Cintilação (Flickering Multi-Armed Bandits)

1. Formulação do Problema

O artigo introduz o framework de Bandidos Multi-Braços com Cintilação (FMAB) para abordar a tomada de decisão sequencial em ambientes onde a disponibilidade de ações é dinâmica, restrita e dependente do estado atual do agente. Ao contrário dos problemas clássicos de Bandidos Multi-Braços (MAB), que assumem acesso irrestrito a um conjunto fixo de braços, o FMAB modela cenários onde um agente pode selecionar apenas um subconjunto de braços definido pela sua localização atual em um grafo que evolui estocasticamente.

Restrições Principais:

• Acessibilidade Local: Em qualquer rodada $t$, o agente reside no braço $a_{t-1}$. O conjunto de braços disponíveis $L_t(a_{t-1})$ é restrito à vizinhança de $a_{t-1}$ no grafo atual $G_t$, além do próprio braço atual.
• Evolução Estocástica: O grafo $G_t$ evolui ao longo do tempo. O agente não pode saltar arbitrariamente para qualquer braço; ele deve navegar através da estrutura do grafo para alcançar braços não visitados ou promissores.
• Desafio Dual: O agente enfrenta uma tensão entre a aquisição de informação estatística (explorar braços para identificar o ideal) e o custo de navegação física (o custo de se mover através do grafo para alcançar esses braços).

Modelos de Grafo:
Os autores formalizam a evolução da disponibilidade de ações através de dois processos principais de grafos aleatórios:

1. Erdős–Rényi (ER) i.i.d.: Em cada rodada, um novo grafo é amostrado independentemente. As arestas existem com probabilidade $p$ (homogêneo) ou probabilidades específicas de cada aresta $p_{ij}$ (heterogêneo).
2. Edge-Markoviano (Aresta-Markoviano): O grafo evolui a partir do estado anterior. As arestas aparecem com probabilidade $\alpha$ e desaparecem com probabilidade $\beta$. Isso modela uma conectividade "pegajosa" onde a topologia muda gradualmente em vez de resetar completamente.

O objetivo é minimizar o regret cumulativo $R(T) = \sum_{t=1}^T (\mu(a^*) - r_t(a_t))$, onde $a^*$ é o braço ótimo, sujeito a estas restrições de movimento local.

2. Metodologia

A solução proposta é um Algoritmo de Aprendizado de Duas Fases que utiliza um Passeio Aleatório Preguiçoso (Lazy Random Walk) para exploração.

Fase I: Identificação do Melhor Braço (Exploração)

• Política: O agente realiza um passeio aleatório preguiçoso. Em cada passo, dado o braço atual $a_{t-1}$ e o grafo realizado $G_t$, o agente seleciona o próximo braço $a_t$ uniformemente ao acaso do conjunto disponível $L_t(a_{t-1})$.
• Duração: Esta fase dura por um tempo pré-determinado $T_0$.
• Objetivo: Coletar amostras suficientes de todos os braços para estimar seus valores médios de recompensa $\hat{\mu}(a)$ com precisão.
• Terminação: Ao final da Fase I, o agente identifica o braço candidato ótimo $\hat{a}^* = \arg\max_a \hat{\mu}(a)$.

Fase II: Navegação e Compromisso (Explotação)

• Política: O agente continua o passeio aleatório preguiçoso até que alcance com sucesso o alvo identificado $\hat{a}^*$.
• Compromisso: Uma vez que o agente chega em $\hat{a}^*$, ele se compromete com este braço para todas as rodadas subsequentes. Como o agente pode sempre permanecer em seu braço atual (auto-loop), ele permanece em $\hat{a}^*$ indefinidamente.

Técnicas de Análise Teórica

A análise faz a ponte entre técnicas espectrais para cadeias de Markov evolutivas e desigualdades de concentração para grafos variantes no tempo:

• Para Grafos ER i.i.d.:
  • Caso Homogêneo: O kernel de transição esperado é simétrico e duplamente estocástico, resultando em uma distribuição estacionária uniforme. Os autores utilizam um argumento de regeneração para mostrar que o passeio se mistura eficientemente.
  • Caso Heterogêneo: O kernel não é simétrico. Os autores empregam um argumento de tipicidade uniforme, provando que as propriedades do grafo realizado (graus, cortes) concentram-se fortemente em torno de seus valores esperados, permitindo limites uniformes sobre o gap espectral e a distribuição estacionária.
• Para Grafos Edge-Markovianos:
  • A análise aborda o acoplamento entre o passeio do agente e a evolução do grafo.
  • Uma condição de "Duas Velocidades" é estabelecida: o grafo deve evoluir suficientemente devagar (condição de viscosidade/stickiness $\beta \le O(1/n)$) em relação à velocidade de mistura do passeio aleatório.
  • O algoritmo requer um período de aquecimento (burn-in period) ($T_{burn}$) para que o processo do grafo atinja sua distribuição estacionária antes que a fase de exploração padrão comece.

3. Resultados Principais

Limites de Regret

O artigo estabelece limites de regret sublineares de alta probabilidade para ambos os modelos de grafo.

Teorema 1 (Grafos ER i.i.d.):
Para o modelo ER heterogêneo, o regret $R(T)$ satisfaz com probabilidade $1-\delta$:
$$R(T) \le \underbrace{O\left(n \log(nT/\delta) + \frac{n \log(n/\delta)}{\Delta_{\min}^2}\right)}_{\text{Custo de Exploração}} + \underbrace{O\left(n \log(n/\delta)\right)}_{\text{Custo de Navegação}}$$
onde $\Delta_{\min}$ é o gap de subotimalidade mínimo. O custo de exploração escala linearmente com o número de braços $n$, e o custo de navegação contabiliza o tempo para alcançar o braço ótimo.

Teorema 3 (Grafos Edge-Markovianos):
Sob condições de tipicidade e viscosidade, o regret inclui um termo de burn-in adicional:
$$R(T) \le \underbrace{O\left(\frac{\log(nT/\delta)}{\alpha+\beta}\right)}_{\text{Burn-in}} + \underbrace{O\left(n \log(nT/\delta) + \frac{n \log(n/\delta)}{\Delta_{\min}^2}\right)}_{\text{Exploração}} + \underbrace{O\left(n \log(n/\delta)\right)}_{\text{Navegação}}$$

Regret Esperado e Quase-Otimalidade

Ao definir a probabilidade de falha $\delta = 1/T$, os autores derivam o limite de regret esperado:
$$E[R(T)] = O\left(\frac{n \log(nT)}{\Delta_{\min}^2}\right)$$
O artigo prova que este limite é quase-ótimo ao derivar um limite inferior informacional. O limite inferior mostra que qualquer algoritmo deve incorrer em um tempo de identificação de $\Omega(n \log(T)/\Delta_{\min}^2)$. A abordagem de duas fases proposta iguala este limite inferior até fatores logarítmicos, demonstrando que o "custo de navegação" não aumenta fundamentalmente a dificuldade estatística do problema além do requisito de identificação.

Simulações

As descobertas teóricas são validadas através de:

1. Experimentos Controlados: Simulações em grafos ER i.i.d. e Edge-Markovianos confirmam que o regret médio converge para zero e que o tempo de navegação escala inversamente com a probabilidade de aresta $p$ (ou seja, $O(1/p)$).
2. Cenário de Resposta a Desastres Robóticos: Uma simulação de um veículo terrestre buscando locais de relé de comunicação em uma zona de desastre. O veículo opera com sensores locais (sem mapa global) e navega em uma rede de ruas que muda dinamicamente (Edge-Markovian). Os resultados mostram que o algoritmo identifica com sucesso a localização ideal e converge para ela, validando a aplicabilidade prática do modelo FMAB.

4. Significância e Contribuições

O artigo reivindica as seguintes contribuições:

• Framework Inovador: Introduz o modelo FMAB, que é o primeiro a acoplar explicitamente restrições de movimento local (navegação) com tomada de decisão sequencial sob incerteza. Isso aborda uma lacuna na literatura existente, onde bandidos "Dorminhocos" (Sleeping) ou "Voláteis" (Volatile) assumem que a disponibilidade é independente das ações do agente ou é globalmente conhecida.
• Análise Unificada: Fornece uma análise de regret unificada para aprendizado em grafos aleatórios evolutivos, lidando tanto com dinâmicas i.i.d. quanto Markovianas.
• Robustez Algorítmica: A estratégia de passeio aleatório preguiçoso proposta mostra-se robusta através de diversos regimes de conectividade (homogêneo, heterogêneo e tempo-correlacionado).
• Limites Fundamentais: Ao estabelecer um limite inferior correspondente, o trabalho caracteriza o custo intrínseco de aprender sob restrições de movimento local, provando que o overhead físico de navegação não degrada a taxa estatística fundamental de aprendizado (até fatores logarítmicos).
• Relevância Prática: O trabalho une o aprendizado online teórico com restrições físicas, oferecendo uma base rigorosa para aplicações em robótica, resposta a desastres e sistemas em rede onde os agentes não podem teletransportar entre as opções.

Os autores concluem que, embora a análise de alta probabilidade dependa de parâmetros específicos do grafo, o regret esperado final depende apenas de parâmetros fundamentais do problema ($n, T, \Delta_{\min}$), sugerindo que as restrições estruturais do ambiente são efetivamente gerenciadas pela estratégia de exploração proposta.