Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

Declaração do Problema

O artigo aborda a eficiência estatística da aprendizagem offline em Bandits Contextuais (BCs) quando o objetivo de aprendizagem envolve regularização Forward-Kullback-Leibler (Forward-KL). A função objetivo é definida como:
$$J_{FKL}(\pi) := \mathbb{E}[r] - \eta^{-1} \text{KL}(\pi_{\text{ref}} \| \pi)$$
onde $r$ é a recompensa, $\eta$ é a intensidade inversa de regularização e $\pi_{\text{ref}}$ é uma política de referência (comportamental).

Enquanto a regularização reverse-KL ($\text{KL}(\pi \| \pi_{\text{ref}})$) foi extensivamente estudada e demonstrou admitir complexidade amostral $\tilde{O}(\epsilon^{-1})$ (taxas rápidas) sob concentrabilidade de política única (onde a política comportamental cobre apenas a política ótima), o caso Forward-KL permanece um problema em aberto. Análises existentes para Forward-KL ou falham em se aplicar ou resultam em taxas lentas $\tilde{O}(\epsilon^{-2})$. Além disso, não está claro se a concentrabilidade de política única é suficiente para Forward-KL, dado que Forward-KL é "cobertura de massa" (penalizando $\pi \to 0$ onde $\pi_{\text{ref}} > 0$) em vez de "busca de modo", potencialmente exigindo suposições de cobertura mais fortes.

O artigo busca responder a duas questões centrais:

1. Qual é a taxa estatística de tomada de decisão para objetivos regularizados por Forward-KL?
2. A concentrabilidade de política única é suficiente para aprendizagem offline ótima em taxa neste cenário?

Metodologia

Os autores propõem uma análise simplificada para Bandits Contextuais Pessimistas Regularizados por Forward-KL (FKL-PCB). A metodologia diverge significativamente de trabalhos anteriores que dependem de expansões de Taylor e do Teorema do Valor Médio (TVM).

1. Rejeição da Análise Tradicional Baseada em TVM:
Trabalhos anteriores que analisam objetivos regularizados frequentemente usam uma expansão de Taylor em torno de um ponto intermediário $\bar{u}$ (via Teorema do Valor Médio) para decompor a lacuna de subotimalidade. Para reverse-KL, os termos resultantes exibem uma propriedade de monotonicidade sob pessimismo que permite limitar o erro usando concentrabilidade de política única.
No entanto, os autores demonstram (via Lema 5.3) que, para Forward-KL, a derivada do termo de decomposição da subotimalidade envolve uma "assimetria inclinada" de uma variável aleatória centrada. O sinal dessa derivada é indefinido, o que significa que o argumento de monotonicidade falha. Consequentemente, rotinas padrão baseadas em TVM não podem alcançar taxas rápidas sem recorrer a suposições de concentrabilidade mais fortes (todas as políticas).

2. Pipeline Analítico Convexo:
Para contornar as limitações do TVM, os autores introduzem uma técnica de prova inovadora baseada em conjugados convexos e divergências de Bregman:

• Perspectiva Dual: Eles caracterizam o objetivo regularizado através de seu conjugado convexo sobre o simplex de probabilidade.
• Argumento de Auto-Limitação: Eles derivam uma identidade para a lacuna de subotimalidade (Lema 5.5) que expressa o erro diretamente em termos da diferença quadrada entre a recompensa verdadeira e a estimativa pessimista, ponderada pela razão da política ótima para a política de referência.
• Identidade Chave: A contribuição técnica central é a desigualdade:
  $$\text{SubOpt}_{FKL}(\hat{\pi}) \leq 2\eta \sum_{a} \frac{(\pi^*_{FKL}(a))^2}{\pi_{\text{ref}}(a)} (r(a) - \hat{r}(a))^2$$
  Este limite depende apenas do coeficiente de concentrabilidade de política única $C_{\pi^*} = \sup \frac{\pi^*}{\pi_{\text{ref}}}$, evitando a necessidade de concentrabilidade de todas as políticas.

3. Design do Algoritmo:
O artigo apresenta o FKL-PCB, um algoritmo pessimista para ambos os cenários tabular e de aproximação de função:

• Estimação: Usa mínimos quadrados para estimar a função de recompensa.
• Pessimismo: Subtrai um termo de penalidade (limite de confiança) para garantir que a recompensa estimada $\hat{r}$ seja limitada inferiormente pela recompensa verdadeira $r$ com alta probabilidade.
• Otimização: Retorna a política que maximiza o objetivo regularizado pessimista.

Contribuições e Resultados Principais

1. Limites Superiores de Complexidade Amostrais Rápidos:
O artigo estabelece os primeiros limites de complexidade amostral $\tilde{O}(\epsilon^{-1})$ para BCs offline regularizados por Forward-KL sob concentrabilidade de política única:

• Cenário Tabular: $\tilde{O}\left( \eta (C_{\pi^*})^2 |S||A| \epsilon^{-1} \right)$.
• Aproximação de Função: $\tilde{O}\left( \eta C_{\pi^*} D^2_{\pi^*} \log N_G \epsilon^{-1} \right)$, onde $D^2_{\pi^*}$ é um coeficiente de concentrabilidade do tipo $D^2$ e $N_G$ é o número de cobertura da classe de funções.
• Estes resultados melhoram o limite anterior de estado da arte $\tilde{O}(\epsilon^{-2})$ de Aminian et al. (2025) e relaxam o requisito de concentrabilidade de todas as políticas para concentrabilidade de política única.

2. Limites Inferiores Minimax:
Os autores fornecem limites inferiores correspondentes para demonstrar a precisão de seus limites superiores:

• Limite Inferior Tabular: $\Omega(\eta |S||A| \epsilon^{-1})$ no regime de alta regularização. Isso confirma que a dependência linear em $\eta$ e a taxa $1/\epsilon$ são ótimas.
• Transição de Fase: Os limites inferiores revelam uma "transição de fase" semelhante ao reverse-KL. No regime de baixa regularização (grande $\eta$), a complexidade amostral reverte para a taxa lenta $\tilde{O}(\epsilon^{-2})$, indicando que a regularização é necessária para alcançar taxas rápidas.

3. Novidade Técnica:
O artigo afirma que o "pipeline analítico convexo" unifica os cenários tabular e de aproximação de função e contorna completamente as rotinas de prova baseadas no Teorema do Valor Médio. Esta abordagem é apresentada como sendo de interesse independente para analisar outros problemas de tomada de decisão regularizados por divergência.

Significado e Afirmações

O artigo posiciona-se como o primeiro trabalho a caracterizar exatamente as taxas estatísticas para regularização Forward-KL em aprendizagem offline. Seu significado principal reside em:

• Resolução de um Problema Aberto: Ele resolve a questão de se a concentrabilidade de política única é suficiente para Forward-KL, respondendo afirmativamente com taxas rápidas.
• Teoria Unificada: Demonstra que a natureza de "cobertura de massa" do Forward-KL não inerentemente requer suposições de cobertura mais fortes do que o reverse-KL de "busca de modo", desde que uma abordagem analítica inovadora seja utilizada.
• Simplicidade Algorítmica: Mostra que um algoritmo minimalista baseado em pessimismo (FKL-PCB) é suficiente para alcançar essas taxas ótimas, sem necessidade de modificações algorítmicas complexas.

Os autores permanecem modestos quanto a direções futuras, observando que, embora estabeleçam a suficiência, a necessidade da concentrabilidade de política única para Forward-KL (mesmo em bandits de braço múltiplo) permanece uma questão em aberto. Além disso, derivar um limite inferior que corresponda ao limite superior especificamente para o coeficiente de concentrabilidade do tipo $D^2$ em aproximação de função é deixado para trabalhos futuros.