Stochastic Linear Bandits with Parameter Noise

Resumo Técnico: Bandits Lineares Estocásticos com Ruído de Parâmetro

Definição do Problema
Este trabalho investiga o modelo de bandits lineares estocásticos com ruído de parâmetro. Neste cenário, um agente interage com um ambiente ao longo de um horizonte temporal $T$ selecionando ações $a_t$ de um conjunto de ações $\mathcal{A} \subseteq \mathbb{R}^d$. Diferentemente do modelo padrão de ruído aditivo, onde a recompensa é $X_t = a_t^\top \theta^\star + \eta_t$ (com $\theta^\star$ fixo e ruído $\eta_t$), o modelo de ruído de parâmetro assume que a recompensa é dada por $X_t = a_t^\top \theta_t$, onde $\theta_t$ é amostrado i.i.d. de uma distribuição fixa e desconhecida $\nu$ com média $\theta^\star$ e matriz de covariância $\Sigma$.

O artigo destaca uma distinção fundamental: no modelo de ruído de parâmetro, o agente pode influenciar a variância da recompensa. Especificamente, $\text{Var}(X_t) = a_t^\top \Sigma a_t$, whereas no modelo de ruído aditivo, a variância é determinada exclusivamente pelo ambiente. Os autores observam que, embora o modelo de ruído de parâmetro seja um relaxamento do modelo de bandits lineares adversariais (onde $\theta_t$ é escolhido por um adversário), ele apresenta propriedades estruturais únicas que permitem limites de arrependimento potencialmente mais apertados do que no modelo de ruído aditivo em certos contextos geométricos.

Metodologia e Algoritmos
Os autores propõem dois algoritmos adaptados a diferentes geometrias de conjuntos de ações:

1. VASE (Eliminação Sucessiva de Design Ótimo Consciente de Variância):

   • Alvo: Conjuntos de ações finitos gerais (e conjuntos infinitos via argumentos de cobertura).
   • Mecanismo: Um algoritmo de eliminação sucessiva que aproveita informações de variância. Em cada fase, ele calcula um design G-ótimo $\pi_\ell$ para selecionar ações. Ele estima explicitamente a variância das ações no suporte do design usando um algoritmo de regra de parada (SR).
   • Inovação Chave: O algoritmo utiliza variâncias estimadas de duas maneiras: para reduzir o número de amostras necessárias para exploração e como pesos em um estimador de mínimos quadrados ponderados. Esse ponderamento garante que a covariância do estimador permaneça controlada mesmo com menos amostras, levando a limites de arrependimento dependentes da variância.

2. VALEE (Explorar-Explorar Linear Consciente de Variância):

   • Alvo: Esferas unitárias $\ell_p$ onde $p \in (1, 2]$ (e suas normas duais $q \ge 2$).
   • Mecanismo: Um algoritmo simples de explorar-explorar.
     • Exploração: O algoritmo joga vetores da base padrão $e_i$. Ele estima o vetor médio $\theta^\star$ coordenada a coordenada usando a técnica Média-das-Médias (MoM). Se a matriz de covariância $\Sigma$ for desconhecida, ele primeiro estima as variâncias dos vetores da base.
     • Exploração: Uma vez que o erro de estimativa seja suficientemente pequeno em relação à variância e ao horizonte temporal, o algoritmo compromete-se com uma ação $\hat{a}$ derivada da média estimada $\hat{\theta}$, especificamente $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$.
   • Inovação Chave: A análise explora a geometria da bola $\ell_p$ e a estrutura do ruído de parâmetro. Os autores mostram que explorar vetores da base produz um erro de estimativa proporcional a $\sqrt{\sigma^2(e_i)}$, o que é mais apertado do que o limite padrão $\epsilon$ em modelos de ruído aditivo. Isso permite que o algoritmo alcance limites de arrependimento ótimos que dependem da estrutura de variância da distribuição de recompensas.

Resultados Chave
O artigo estabelece limites superiores e inferiores, demonstrando que os algoritmos propostos são minimax ótimos (até fatores logarítmicos) para configurações específicas.

• Conjuntos de Ações Finitos Gerais ($K$ ações):

  • Limite Superior: O VASE alcança um arrependimento de $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$, onde $M_\sigma$ é uma quantidade dependente da variância limitada por $\max_a \sigma^2(a)$.
  • Limite Inferior: Um limite inferior de $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ é provado, mostrando que o limite superior é apertado até fatores logarítmicos quando $\log(K) \approx d$.

• Esferas Unitárias $\ell_p$ ($p \le 2$):

  • Covariância Conhecida: O VALEE alcança um arrependimento de $\tilde{O}(d + \sqrt{dT \sigma^2_q})$, onde $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$. Isso é mostrado como ótimo via um limite inferior correspondente de $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$.
  • Covariância Desconhecida: O VALEE incorre em um termo aditivo adicional, resultando em um arrependimento de $\tilde{O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$. Os autores observam que este termo aditivo surge da fase de estimativa de variância.

• Esferas Unitárias $\ell_p$ ($p > 2$):

  • O artigo fornece um limite inferior de $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$, correspondendo aos limites inferiores conhecidos para o cenário adversarial nessas geometrias.

Significado e Afirmações
O artigo afirma resolver um "caso curioso" sobre bandits lineares onde o modelo de ruído aditivo frequentemente produz limites de arrependimento piores ($d\sqrt{T}$) do que o modelo adversarial ($\sqrt{dT}$) para conjuntos de ações específicos como a bola unitária $\ell_2$. Os autores demonstram que o modelo de ruído de parâmetro alinha-se mais de perto com a intuição de que modelos estocásticos devem ser mais fáceis do que os adversariais.

• Limites Mais Apertados: Para bolas $\ell_p$ com $p \le 2$, o modelo de ruído de parâmetro permite limites de arrependimento da ordem $\sqrt{dT \sigma^2_q}$, que podem ser significativamente menores do que o limite $d\sqrt{T}$ típico de modelos de ruído aditivo quando a variância é pequena.
• Vantagem Estrutural: Os resultados destacam que a linearidade da realização (não apenas da expectativa) e a capacidade do agente de influenciar a variância são cruciais para alcançar esses limites aprimorados.
• Simplicidade: Surpreendentemente, o arrependimento ótimo para bolas $\ell_p$ ($p \le 2$) é alcançável usando um algoritmo de explorar-explorar muito simples (VALEE), contrastando com os algoritmos complexos de design ótimo frequentemente necessários em configurações de ruído aditivo.

Os autores concluem que, embora seus resultados para $p \le 2$ sejam ótimos (até logs) quando a covariância é conhecida, o caso de covariância desconhecida deixa uma lacuna aberta (o termo $T^{1/3}$) que trabalhos futuros podem abordar. Eles também deixam o projeto de um algoritmo que corresponda ao limite inferior para $p > 2$ como uma questão em aberto.