Offline-to-Online Learning in Linear Bandits

Resumo Técnico: Aprendizado Offline-para-Online em Bandidos Lineares

Enunciado do Problema
Este artigo aborda o problema do aprendizado offline-para-online no cenário de bandido linear estocástico. O cenário envolve um aprendiz que seleciona sequencialmente ações de um conjunto $\mathcal{A} \subset \mathbb{R}^d$ para maximizar recompensas cumulativas ao longo de um horizonte $n$, enquanto possui acesso a um conjunto de dados offline pré-existente $\mathcal{D}$. Os dados offline são coletados via um design fixo e não adaptativo (contagens de ações determinísticas) e seguem um modelo de recompensa linear com ruído subgaussiano.

O desafio central reside no equilíbrio entre dois objetivos concorrentes:

1. Regret Online ($R_n$): Minimizar o regret em relação à ação ótima $\mu^*$. Algoritmos online padrão (ex: LinUCB) dependem de otimismo para explorar, alcançando regret sublinear, mas podem sofrer com alto regret inicial se os dados offline forem ignorados.
2. Regret Offline ($R_n^{off}$): Minimizar o regret em relação à média da recompensa do conjunto de dados offline ($\mu_{off}$). Algoritmos offline padrão (ex: LinLCB) dependem de pessimismo para explorar os dados conhecidos, garantindo um desempenho próximo a $\mu_{off}$, mas falham em explorar, o que leva a um regret linear se o conjunto offline for subótimo ou se o horizonte for longo.

Trabalhos existentes têm tratado esses regimes separadamente ou focado em bandidos de múltiplas braços (MAB), onde o regret escala com o número de ações. Este artigo busca preencher a lacuna em ambientes estruturados (lineares), onde o regret deve escalar com a dimensão $d$ em vez do tamanho do espaço de ações.

Metodologia: O Algoritmo LinOtO
Os autores propõem o LinOtO (Linear Offline-to-Online), um algoritmo que equilibra dinamicamente exploração e explotação ao gerenciar um orçamento de exploração. O algoritmo opera alternando entre duas estratégias baseadas em um conjunto de confiança $C_t$ construído a partir de dados tanto offline quanto online:

1. Conjuntos de Confiança: O algoritmo mantém um estimador de mínimos quadrados $\hat{\theta}_t$ e um elipsoide de confiança $C_t$ em torno do parâmetro real $\theta^*$. O raio deste conjunto incorpora a incerteza proveniente tanto dos dados offline ($\beta_{off}$) quanto das interações online ($\beta_t$).
2. Ações de UCB vs. LCB:
   • Ação UCB ($U_t$): A ação que maximiza o Limite Superior de Confiança (Upper Confidence Bound) dentro de $C_t$. Isso promove a exploração e reduz $R_n$, mas corre o risco de aumentar $R_n^{off}$.
   • Ação LCB ($L_t$): A ação que maximiza o Limite Inferior de Confiança (Lower Confidence Bound) (especificamente, o máximo dos limites inferiores de confiança ao longo do tempo). Isso promove a explotação dos dados offline, reduzindo $R_n^{off}$, mas potencialmente aumentando $R_n$.
3. Mecanismo de Orçamento:
   • O algoritmo define uma recompensa de linha de base segura $r_b$, derivada de um limite inferior na recompensa de uma ação "segura" específica $L_{off}$ (a ação LCB calculada puramente a partir dos dados offline). A Proposição 2 garante que $L_{off}$ é próximo de $\mu_{off}$ com alta probabilidade.
   • Um orçamento de exploração $B(t)$ é mantido, representando a recompensa excedente cumulativa do algoritmo sobre a linha de base $r_b$.
   • Regra de Decisão: Se $B(t) > 0$, o algoritmo seleciona a ação otimista $U_t$ (exploração). Se $B(t) \le 0$, ele seleciona a ação pessimista $L_t$ (explotação) para acumular orçamento.
   • Este mecanismo garante que o algoritmo só explore quando tiver "conquistado" o direito de fazê-lo ao permanecer seguro em relação à linha de base offline.

Principais Contribuições

1. Design de Algoritmo: O artigo apresenta o LinOtO, o primeiro algoritmo especificamente desenhado para o cenário de bandido linear offline-para-online que equilibra simultaneamente as estratégias UCB e LCB via um mecanismo de alternância baseado em orçamento.
2. Garantias Teóricas: Os autores estabelecem limites de regret de alta probabilidade para ambos os métricas:
   • Regret Online ($R_n$): O Teorema 1 mostra que o LinOtO alcança regret sublinear em relação à ação ótima. O limite consiste em um termo dependente do horizonte $n$ (semelhante ao LinUCB) e uma constante aditiva dependente da qualidade dos dados offline. Se os dados offline cobrirem bem o espaço, o limite melhora.
   • Regret Offline ($R_n^{off}$): O Teorema 2 demonstra que o regret em relação à referência offline escala linearmente com $n$, mas diminui como $O(1/\sqrt{m})$ com o número de amostras offline $m$. Isso condiz com o desempenho de uma solução puramente offline (pessimista).
3. Análise de Tradeoff de Pareto: A análise revela um tradeoff ajustável controlado por um parâmetro $\alpha$. Aumentar $\alpha$ favorece o desempenho online (mais próximo do LinUCB), enquanto diminuir $\alpha$ favorece o desempenho offline (mais próximo do LinLCB).

Resultados Experimentais
Avaliações empíricas em tarefas sintéticas de bandido linear (dimensão $d=20$, $|A|=100$) demonstram:

• Sensibilidade ao Horizonte: Para horizontes curtos, o LinOtO acompanha a linha de base conservadora do LinLCB. Para horizontes longos, ele transiciona para a exploração, alcançando um regret sublinear comparável ao LinUCB.
• Qualidade dos Dados Offline:
  • Quando o conjunto de dados offline exclui a ação ótima, o LinOtO desvia-se com sucesso do prior offline subótimo para explorar, eventualmente superando o LinLCB (que sofre regret linear) e aproximando-se do desempenho do LinUCB conforme o tamanho dos dados offline $m$ aumenta.
  • Quando o conjunto de dados offline inclui a ação ótima, o LinOtO converge rapidamente, performando comparavelmente ao LinUCB e LinLCB.
• Robustez: O algoritmo performa consistentemente entre os extremos da exploração pura (LinUCB) e da explotação pura (LinLCB), adaptando-se aos parâmetros do problema.

Significância e Alegações
O artigo alega que o LinOtO resolve efetivamente o tradeoff "pouco compreendido" de offline-para-online em ambientes estruturados. Diferente de trabalhos anteriores em configurações de MAB (ex: Sentenac et al., 2025), esta abordagem aproveita a estrutura linear para garantir que o regret escale com a dimensão $d$ em vez do número de ações, tornando-o escalável para problemas de alta dimensão.

Os autores observam modestamente que seu framework atualmente assume dados offline de design fixo e não considera mudanças de distribuição entre os dados offline e online ou políticas de registro adaptativas. Eles identificam o endereçamento dessas limitações, juntamente com a extensão do framework para configurações não lineares, como direções importantes para pesquisas futuras. O trabalho contribui para a literatura mais ampla de aproveitamento de conhecimento prévio (dicas, dados offline) para guiar os tradeoffs de exploração-explotação no aprendizado online.