An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

Resumo Técnico: Um Algoritmo Melhorado para Bandidos Contextuais Lineares Adversários via Redução

Definição do Problema

O artigo aborda o problema do bandido contextual linear adversário. Neste cenário, um adversário oblíquo seleciona uma sequência de vetores de perda ocultos $\theta_t \in \mathbb{R}^d$ antes do início da interação. Em cada rodada $t$, um conjunto de ações $A_t \subset \mathbb{R}^d$ é extraído i.i.d. de uma distribuição fixa, porém desconhecida $\mathcal{D}$, e revelado ao aprendiz. O aprendiz deve selecionar uma ação $a_t \in A_t$ e incorre em uma perda $\ell_t$ com esperança $\mathbb{E}[\ell_t] = a_t^\top \theta_t$. O objetivo é minimizar o regret contra a melhor política fixa $\pi$, onde uma política mapeia qualquer conjunto de ações observado $A$ para um ponto em seu casco convexo $\text{conv}(A)$.

Este cenário generaliza os bandidos lineares clássicos ao permitir que os conjuntos de ações (contextos) variem estocasticamente ao longo do tempo, enquanto as perdas permanecem adversárias. Um desafio crítico é que a distribuição $\mathcal{D}$ é desconhecida, e o aprendiz não tem acesso a um simulador que possa gerar amostras gratuitas de $\mathcal{D}$. Além disso, o número de ações possíveis $K$ pode ser exponencialmente grande em relação à dimensão $d$ (por exemplo, em problemas combinatórios como caminho mais curto), tornando inviáveis algoritmos com complexidade polinomial em $K$.

Metodologia

A contribuição central é uma redução computacionalmente eficiente que transforma o problema do bandido contextual linear adversário em um problema de bandido linear adversário robusto à especificação incorreta com um conjunto de ações fixo.

1. Redução para Conjuntos de Ações Fixos:
   Os autores definem um mapeamento $\Psi(\pi) = \mathbb{E}_{A \sim \mathcal{D}}[\pi(A)]$, que mapeia uma política $\pi$ para sua ação média. Como $\mathcal{D}$ é desconhecida, o verdadeiro conjunto de ações médias $\Omega = \{\Psi(\pi) \mid \pi \in \Pi\}$ não pode ser acessado diretamente. Em vez disso, o algoritmo constrói uma aproximação empírica $\hat{\Omega}$ usando $N$ amostras i.i.d. de conjuntos de ações extraídos de $\mathcal{D}$.

   • $\hat{\Omega}$ é definido como a soma de Minkowski dos cascos convexos dos conjuntos de ações amostrados: $\hat{\Omega} = \frac{1}{N} \sum_{i=1}^N \text{conv}(A_i)$.
   • A redução baseia-se no fato de que, para políticas de classificador linear, a diferença entre a perda esperada na distribuição real e na distribuição empírica é pequena (convergência uniforme), desde que $N$ seja suficientemente grande.

2. Lidando com a Discrepância via Robustez à Especificação Incorreta:
   Como o aprendiz opera sobre $\hat{\Omega}$ em vez de $\Omega$, o feedback recebido pelo algoritmo de bandido linear subjacente é "mal especificado". Especificamente, a perda esperada observada pelo algoritmo de bandido linear difere da verdadeira perda esperada por um termo de erro limitado $\epsilon$.

   • Os autores utilizam um algoritmo de bandido linear adversário $\alpha$-robusto à especificação incorreta como uma caixa preta. Este algoritmo garante baixo regret mesmo quando o feedback satisfaz $|\mathbb{E}[c_t] - \langle y_t, \theta_t \rangle| \le \epsilon$.
   • Para executar um ponto $y_t \in \hat{\Omega}$ sugerido pelo algoritmo de bandido linear, o aprendiz utiliza uma decomposição baseada em Frank-Wolfe (Algoritmo 2) para expressar $y_t$ como uma combinação convexa de pontos na fronteira de $\hat{\Omega}$. Esses pontos de fronteira correspondem a políticas de classificador linear $\pi_\phi$, que podem ser executadas usando um oráculo de otimização linear para os conjuntos de ações individuais $A_t$.

3. Componentes Algorítmicos:

   • Algoritmo 1: A estrutura principal que interage com o ambiente, decompõe a sugestão do bandido linear em uma mistura de políticas lineares e fornece a perda resultante de volta ao algoritmo de bandido linear.
   • Algoritmo 3 (Pesos Exponenciais Contínuos com Especificação Incorreta Robusta): Uma instanciação específica do algoritmo de bandido linear robusto. Ele adapta o método de pesos exponenciais contínuos com corte (Ito et al., 2020) adicionando um "termo de bônus" $b_t$ ao estimador de perda. Este bônus incentiva a exploração e compensa o overhead de regret causado pela especificação incorreta.
   • Truque de Dobramento (Doubling Trick): Para lidar com o tamanho de amostra $N$ desconhecido, o algoritmo emprega um truque de dobramento, reiniciando o processo em épocas $2, 4, 8, \dots$ e utilizando todas as amostras de contexto acumuladas para refinar $\hat{\Omega}$.

Principais Contribuições

• Algoritmo Eficiente em Oráculo: O artigo apresenta o primeiro algoritmo para bandidos contextuais lineares adversários com conjuntos de ações estocásticos que alcança limites de regret independentes do número de ações $K$ em sua complexidade computacional. Ele requer apenas um oráculo de otimização linear para os conjuntos de ações individuais em cada rodada.
• Aplicabilidade Combinatória: O método é o primeiro a alcançar regret $\text{poly}(d)\sqrt{T}$ em tempo polinomial para bandidos combinatórios com conjuntos de ações estocásticos e perdas adversárias. Algoritmos anteriores ou exigiam feedback de semi-bandido ou tinham complexidade computacional escalando polinomialmente com $K$ (que é exponencial em $d$ para muitos problemas).
• Redução Inovadora: O trabalho estabelece uma redução de tempo polinomial de bandidos contextuais lineares adversários para bandidos lineares robustos à especificação incorreta. Diferente de reduções anteriores (ex: Hanna et al., 2023) que focavam em cenários estocásticos ou careciam de implementações de tempo polinomial, esta redução opera sob perdas adversárias e é computacionalmente eficiente.

Resultados

O algoritmo alcança os seguintes limites de regret (ignorando fatores logarítmicos):

• Sem Simulador: $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3 T \log K}\})$.
  • Isso resolve uma questão em aberto de Liu et al. (2023) sobre se o regret $\text{poly}(d)\sqrt{T}$ é alcançável em tempo polinomial independente de $K$.
  • A complexidade computacional é $\text{poly}(d, T)$ mais $\text{poly}(d, T)$ chamadas ao oráculo de otimização linear.
• Com Simulador: Se o aprendiz tiver acesso a um simulador que possa gerar contextos gratuitos, o limite de regret melhora para $\tilde{O}(d\sqrt{L^*})$, onde $L^*$ é a perda cumulativa da melhor política. Este é um limite de primeira ordem que se adapta à dificuldade da instância do problema.

Significância e Alegações

Os autores afirmam que este trabalho fornece um framework geral que amplia significativamente a aplicabilidade dos bandidos contextuais lineares adversários para problemas com espaços de ações exponencialmente grandes (ex: caminho mais curto, fluxo, emparelhamento bipartido) sem exigir conhecimento da distribuição do contexto ou um simulador.

O artigo observa explicitamente que, embora o limite $\tilde{O}(d^2\sqrt{T})$ seja uma melhoria sobre resultados anteriores de tempo polinomial dependentes de $K$, permanece uma questão em aberto se o limite quase ideal $\tilde{O}(d\sqrt{T})$ pode ser alcançado sem um simulador em tempo polinomial. Os autores também destacam que sua abordagem remove a suposição irreal de distribuições de contexto log-côncavas exigida por alguns trabalhos anteriores (Olkhovskaya et al., 2023) quando especializada para certas formulações. Finalmente, eles sugerem que o framework de redução pode ser aplicável a outros cenários, como MDPs lineares com transições fixas e perdas adversárias.