Resumo Técnico: Exploração Adaptativa para Bandidos de Estado Latente

1. Formulação do Problema

O artigo aborda um problema de bandido multi-braços não estacionário onde as distribuições de recompensa dependem de um estado de Markov latente (não observado) que evolui autonomamente ao longo do tempo. Diferente dos bandidos contextuais padrão, o aprendiz não consegue observar o estado $s_t$ diretamente; ele apenas observa a ação selecionada $a_t$ e a recompensa estocástica resultante $r_t$.

O desafio central é que o braço ótimo muda conforme os estados ocultos transitam, mas o aprendiz deve inferir o estado atual apenas através do histórico de ações e recompensas. Este cenário introduz três dificuldades técnicas específicas:

1. Estimação de Recompensa Confundida: Algoritmos padrão fazem a média das recompensas sobre a distribuição de estados, o que leva a um viés sistemático quando o braço ótimo varia entre os estados.
2. Atribuição Temporal de Recompensa: É difícil distinguir se uma mudança no desempenho da recompensa se deve ao progresso do aprendizado ou a uma transição no estado oculto.
3. Informação de Estado Limitada: O algoritmo não pode condicionar diretamente em características do estado e deve depender de sinais indiretos, uma tarefa que se torna mais difícil à medida que o espaço de estados cresce.

O objetivo é minimizar o regrete dinâmico contra um oráculo ciente do estado, definido como a diferença cumulativa entre a recompensa do braço ótimo para o estado oculto atual e o braço efetivamente selecionado.

2. Metodologia

Os autores propõem uma família de algoritmos que integram Contexto Retardado (Lagged Context) e Estratégias de Sondagem (Probing Strategies) à estrutura do LinUCB. A abordagem evita a estimação explícita do modelo de transição de Markov latente, baseando-se, em vez disso, em estatísticas de baixa dimensão para separar os estados.

2.1 Contexto Retardado (LC-UCB)

O primeiro componente, Lagged-Context UCB (LC-UCB), trata o par ação-recompensa anterior $(a_{t-1}, r_{t-1})$ como um vetor de características de contexto $\phi_t$.

• Intuição: Sob a dinâmica de estados de Markov lentos, a recompensa anterior fornece informações sobre o estado anterior $s_{t-1}$, que está altamente correlacionado com o estado atual $s_t$.
• Mecanismo: O algoritmo aprende um mapeamento de $(a_{t-1}, r_{t-1})$ para a recompensa atual $r_t$. Isso permite que o aprendiz rastreie implicitamente o estado e selecione o braço ótimo para o estado recente inferido, em vez de uma média sobre todos os estados.
• Limitação: O LC-UCB pode falhar se múltiplos estados produzirem recompensas semelhantes para a mesma ação (não-identificabilidade), levando à ambiguidade na inferência do estado.

2.2 Sondagem para Impressões Digitais de Estado (Probing for State Fingerprints)

Para resolver a ambiguidade, os autores introduzem estratégias de sondagem que geram "impressões digitais de estado" — observações conjuntas de recompensas de múltiplos braços que identificam unicamente o estado oculto. Dois paradigmas são propostos:

1. Randomized Probing UCB (RP-UCB): Aplicável quando múltiplas unidades experimentais (ex: usuários) podem receber diferentes braços simultaneamente. Ele coleta observações conjuntas reais $(r_0, r_1)$ do mesmo passo de tempo.
2. Sequential Probing UCB (SP-UCB): Aplicável para configurações de unidade única. Ele amostra braços consecutivamente (ex: braço 0 em $t$, braço 1 em $t+1$) e trata o par $(r_t, r_{t+1})$ como uma impressão digital sintética. Isso depende da premissa de que o estado é "pegajoso" (alta probabilidade de auto-transição), de modo que o estado não mude entre as duas sondagens.

2.3 Exploração Adaptativa (AdaRP-UCB / AdaSP-UCB)

O agendamento fixo de sondagem gera regrete mesmo quando o modelo está confiante. Os autores propõem variantes de Sondagem Adaptativa que atualizam as impressões digitais apenas quando necessário, utilizando três mecanismos de controle (gates):

• Portão de Resíduo (Residual Gate): Dispara uma sondagem se o erro de predição (resíduo studentizado) exceder um limite, indicando deriva do modelo ou uma transição de estado.
• Portão de Incerteza (Uncertainty Gate): Dispara uma sondagem se a margem entre os dois melhores escores UCB for pequena, indicando alta incerteza na seleção de braços.
• Portão de Obsolescência/Perigo (Staleness/Hazard Gate): Dispara uma sondagem se a impressão digital não for atualizada por um período definido por uma função de risco exponencial, evitando o uso de informações desatualizadas.

Esses portões estão sujeitos a um intervalo mínimo entre sondagens ($\tau_{min}$) para evitar comportamentos oscilatórios.

3. Principais Contribuições

1. Estrutura Algorítmica: O desenvolvimento de LC-UCB, RP-UCB, SP-UCB e suas variantes adaptativas (AdaRP-UCB, AdaSP-UCB) que combinam contexto retardado com sondagem coordenada para lidar com bandidos de estado latente sem a necessidade de estimar o modelo completo de transição de Markov.
2. Análise Teórica: Uma decomposição do regrete dinâmico em três componentes: ambiguidade de representação (erro de aproximação), custo de sondagem e deriva após uma impressão digital tornar-se obsoleta. O artigo fornece limites que mostram que a sondagem adaptativa minimiza o regrete ao equilibrar esses fatores.
3. Validação Empírica: Avaliação sistemática através de variações no número de estados ocultos ($S$), taxas de transição (probabilidade de permanência $p_{stay}$), ruído de recompensa ($\sigma$) e horizontes temporais ($T$).

4. Resultados Experimentais

Os algoritmos foram avaliados contra baselines clássicos (UCB1, Thompson Sampling), métodos adversariais (EXP3) e métodos não estacionários (Sliding Window UCB, Discounted UCB).

• Desempenho: Os métodos de sondagem adaptativa (especificamente AdaRP-UCB e AdaSP-UCB) superaram consistentemente todos os baselines em ambientes onde os resumos (impressões digitais) podiam distinguir os estados e eram atualizados com frequência suficiente.
  • AdaRP-UCB alcançou o menor regrete em 12 de 13 configurações randomizadas, mostrando ganhos significativos em ambientes voláteis.
  • AdaSP-UCB teve o melhor desempenho em configurações de unidade única com baixo ruído, mistura lenta ou grandes espaços de estados.
• Modos de Falha: O artigo identifica condições específicas onde os métodos degradam:
  • Ruído Elevado: Quando o ruído ($\sigma$) é alto em relação ao diferencial entre braços (arm gap), as impressões digitais tornam-se fracas, e baselines não estacionários (como D-UCB) podem performar melhor.
  • Separação Fraca de Impressão Digital: Se diferentes estados produzem distribuições de recompensa conjunta semelhantes, a estratégia de sondagem não consegue desambiguar os estados.
  • Troca Rápida (Fast Switching): A sondagem sequencial (SP-UCB) falha quando o estado muda frequentemente dentro da janela de sondagem (baixo $p_{stay}$), tornando a impressão digital sintética inválida.
• Estudos de Ablação: Remover a característica de impressão digital ($\phi_{fp}$) aumentou significativamente o regrete em ambientes de estado pegajoso, confirmando o valor das observações conjuntas. Remover o contexto retardado ($\phi_{lag}$) teve um impacto menor em algumas configurações randomizadas, sugerindo que o tempo adaptativo foi o principal motor de melhoria nesses casos.

5. Significância e Alegações

O artigo alega que sua principal contribuição é uma abordagem prática para não-estacionariedade estruturada, onde o ambiente evolui via um processo de Markov autônomo. Ao contrário dos bandidos não estacionários padrão que tratam mudanças como deriva arbitrária, ou POMDPs que exigem observabilidade total ou decodificação complexa, esta abordagem utiliza resumos de histórico leves e sondagens para manter uma estimativa atual do braço ótimo.

Os autores enfatizam que seus métodos são mais eficazes em regimes onde:

1. O estado latente é previsível em horizontes curtos (mistura lenta).
2. A estratégia de sondagem pode gerar estatísticas suficientes (impressões digitais) que separam os estados relevantes.
3. Os mecanismos de controle adaptativos podem manter esses resumos atuais sem incorrer em excesso de custo de sondagem.

O trabalho faz a ponte entre bandidos contextuais e aprendizado por reforço de estado latente ao oferecer uma solução computacionalmente eficiente (baseada em LinUCB) que não requer o aprendizado da dinâmica completa de transição do estado oculto.