A single algorithm for both restless and rested rotting bandits

Título: Um único algoritmo para bandits rotativos (rotting) descansados (rested) e inquietos (restless)

Autores: Julien Seznec, Pierre Menard, Alessandro Lazaric, Michal Valko.
Publicação: AISTATS 2020.

1. Problema e Contexto

O artigo aborda o problema dos Bandits Multi-Armed (MAB) em ambientes não estacionários onde as recompensas dos braços (ações) tendem a decair (rotting) ao longo do tempo. Esse cenário é comum em aplicações como sistemas de recomendação (onde o usuário se cansa de recomendações repetidas) ou tutoria inteligente (onde o conteúdo se torna obsoleto).

O trabalho distingue dois tipos fundamentais de não-estacionariedade:

1. Rested (Descansado): A recompensa de um braço decai apenas quando ele é selecionado (puxado). Se não for escolhido, seu valor permanece constante.
2. Restless (Inquieto): A recompensa decai independentemente das ações do agente, apenas com o passar do tempo (ex: notícias que perdem valor com o tempo).

O Desafio:
Anteriormente, acreditava-se que esses dois cenários exigiam abordagens fundamentalmente diferentes. Algoritmos de ponta para bandits restless (como aqueles baseados em detecção de mudança ou esquecimento passivo) performavam mal no cenário rested. Além disso, o artigo demonstra que, se as recompensas pudessem aumentar além de diminuir, seria impossível aprender com uma taxa de arrependimento sublinear ($o(T)$) em um cenário misto. No entanto, a restrição de que as recompensas são não-crescentes (apenas decaem) permite uma solução unificada.

2. Metodologia: RAW-UCB

Os autores propõem um novo algoritmo chamado RAW-UCB (Rotting Adaptive Window Upper Confidence Bound).

• Mecanismo Central: O RAW-UCB é uma política de índice (index policy) que calcula um limite superior de confiança (UCB) para cada braço.
• Janela Adaptativa: Diferente do UCB clássico que usa todos os dados históricos, o RAW-UCB calcula a média das últimas $h$ observações de cada braço para vários tamanhos de janela $h$.
• Seleção de Janela: Para cada braço, o algoritmo seleciona a janela $h$ que minimiza o índice UCB (o limite inferior mais apertado). A lógica é que, como as recompensas decaem, médias baseadas em janelas muito longas introduzem viés (incluem dados antigos e altos), enquanto janelas muito curtas introduzem alta variância. O algoritmo adapta-se automaticamente para encontrar o equilíbrio ideal (trade-off viés-variância) sem conhecimento prévio da taxa de decaimento.
• Versão Eficiente: O artigo também apresenta o EFF-RAW-UCB, que utiliza uma atualização eficiente baseada em uma grade geométrica de janelas, reduzindo a complexidade computacional de $O(t)$ para $O(\log t)$ por rodada, mantendo as garantias teóricas.

3. Contribuições Principais

1. Impossibilidade no Caso Geral Misto: Os autores provam que, se um ambiente contiver simultaneamente braços rested e restless com decaimento, nenhuma estratégia de aprendizado pode atingir uma taxa de arrependimento sublinear ($o(T)$) no pior caso. Isso justifica a necessidade de tratar os cenários separadamente ou assumir que o ambiente é estritamente um ou outro.
2. Algoritmo Unificado: O RAW-UCB é o primeiro algoritmo a atingir taxas de arrependimento minimax quase ótimas em ambos os cenários (rested e restless) sem precisar saber a priori qual é o tipo de não-estacionariedade, a taxa de decaimento, o orçamento de variação ou o horizonte temporal $T$.
3. Garantias Teóricas:
   • Restless (Orçamento de Variação e Estacionariedade por Partes): O algoritmo atinge a taxa minimax $O((VT K T^2)^{1/3})$ para orçamento de variação e $O(\sqrt{\Upsilon_T K T})$ para estacionariedade por partes (onde $\Upsilon_T$ é o número de mudanças), sem depender de parâmetros desconhecidos.
   • Rested: O algoritmo atinge a taxa minimax $O(\sqrt{KT})$ e também recupera limites dependentes do problema da ordem $O(\log T)$, algo que não é possível em bandits não-rotativos onde as recompensas podem aumentar.
4. Superioridade sobre FEWA: O RAW-UCB melhora a constante teórica do algoritmo anterior FEWA (o estado da arte para rested) por um fator de 4 e é mais simples de implementar e executar.

4. Resultados Experimentais

Os autores validaram o RAW-UCB em dois tipos de experimentos:

• Dados Sintéticos (Rested): Comparação com FEWA, GLR-UCB e Exp3.S. O RAW-UCB superou consistentemente o FEWA em todos os níveis de decaimento, tanto com ajuste teórico quanto empírico. O Exp3.S e o GLR-UCB (sem exploração ativa) tiveram desempenho inferior ou inconsistente no cenário rested.
• Dados Reais (Restless - Yahoo! Front Page): Utilizando o conjunto de dados de cliques do Yahoo! (que exibe um decaimento natural de interesse ao longo do dia), o RAW-UCB (na versão eficiente EFF-RAW-UCB) demonstrou o menor arrependimento acumulado em comparação com FEWA, Exp3.S e GLR-UCB.
  • Em cenários "difíceis" (muitas mudanças de braço ótimo), o RAW-UCB rastreou o melhor braço com mais eficiência.
  • Em cenários "fáceis" (um braço dominante), o algoritmo atingiu uma taxa de arrependimento logarítmica, superando significativamente o Exp3.S.
  • Eficiência Computacional: A versão eficiente (EFF-RAW-UCB) foi cerca de 10 vezes mais rápida que o GLR-UCB.

5. Significado e Conclusão

Este trabalho é significativo porque desafia a noção de que bandits rested e restless rotativos exigem algoritmos fundamentalmente distintos. Ao explorar a propriedade de que as recompensas são não-crescentes, os autores conseguiram unificar o tratamento desses problemas sob uma única estrutura de índice adaptativo.

O RAW-UCB oferece uma solução robusta, teoricamente fundamentada e computacionalmente eficiente para sistemas de recomendação e outros domínios onde a "fadiga" ou a "obsolescência" são fatores críticos, eliminando a necessidade de ajustar parâmetros específicos para o tipo de não-estacionariedade do ambiente.