Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

Enunciado do Problema
O artigo aborda o problema do bandit Gaussiano-linear, um cenário de tomada de decisão sequencial onde um jogador seleciona ações $A_t \in \mathcal{A} \subset \mathbb{R}^d$ para maximizar recompensas cumulativas. A recompensa no tempo $t$ é gerada por $R_{t+1} = \theta_\star^\top A_t + W_{t+1}$, onde $\theta_\star$ é um vetor de parâmetros desconhecido e $W_{t+1}$ é um ruído Gaussiano i.i.d. com variância $\sigma^2$. O objetivo é minimizar o regret bayesiano, definido como a diferença esperada entre a recompensa da ação ótima e a ação escolhida ao longo de um horizonte $T$, assumindo uma distribuição a priori $\rho$ sobre $\theta_\star$. Especificamente, os autores focam no caso em que $\theta_\star \sim \mathcal{N}(\mu_0, \Sigma_0)$ e o conjunto de ações é uma bola $\ell_2$ escalonada de raio $r$.

Metodologia
Os autores analisam o Thompson Sampling, um algoritmo de amostragem de posterior, que extrai uma estimativa de parâmetro $\hat{\theta}_t$ da distribuição posterior dada o histórico $H_t$ e seleciona a ação que maximiza a recompensa esperada sob $\hat{\theta}_t$.

Para derivar os limites de regret, os autores empregam uma decomposição do regret instantâneo em dois termos:

1. Termo (I): O regret incorrido quando o parâmetro amostrado $\hat{\theta}_t$ está próximo do parâmetro verdadeiro $\theta_\star$ (dentro de um evento de alta probabilidade definido pela matriz de precisão da posterior).
2. Termo (II): O regret incorrido quando o parâmetro amostrado está longe do parâmetro verdadeiro.

A principal inovação técnica reside na análise do Termo (I). Os autores introduzem um lema de potencial elíptico generalizado (Lema 3). Diferente dos lemas de potencial elíptico padrão usados na literatura de bandits lineares (ex: Abeille & Lazaric, 2017; Dani et al., 2008), que tipicamente exigem que a matriz de precisão inicial seja limitada de zero (ex: $V_0 \succeq I$) e limitem erros quadráticos, este novo lema:

• Permite que a matriz de precisão inicial $V_0$ seja arbitrariamente pequena (ou até zero no limite), acomodando distribuições a priori difusas.
• Introduz um expoente flexível $p \in [0, 1]$ na soma das normas.
• Separa explicitamente o limite em um termo de determinante logarítmico (capturando o ganho de informação a longo prazo) e um termo de traço envolvendo a precisão inicial (capturando o custo de "burn-in" inicial).

A análise do Termo (II) baseia-se em desigualdades de concentração padrão para distribuições Gaussianas para limitar a probabilidade de grandes desvios entre $\hat{\theta}_t$ e $\theta_\star$.

Principais Contribuições e Resultados
A contribuição primária é um novo limite de regret bayesiano para Thompson Sampling no cenário Gaussiano-linear que desacopla o termo de "burn-in" dependente da a priori da taxa de minimax de regret.

1. Limite de Regret Melhorado: Os autores provam que o Thompson Sampling alcança um regret de:
   $$\text{Reg}(T) = \tilde{O}\left( \sigma d \sqrt{T} + d r \sqrt{\text{Tr}(\Sigma_0)} \right)$$
   Aqui, $\sigma d \sqrt{T}$ representa a taxa minimax assintótica, enquanto $d r \sqrt{\text{Tr}(\Sigma_0)}$ representa o custo inicial de reduzir a incerteza da escala da a priori para a escala do ruído.

2. Desacoplamento de Termos: Limites anteriores (ex: Kalkanli & Özgür, 2020) exibiam uma dependência multiplicativa, tal como $\tilde{O}(d \sqrt{T(\sigma^2 + r^2 \text{Tr}(\Sigma_0))})$, onde a difusividade da a priori $\sqrt{\text{Tr}(\Sigma_0)}$ escalonava todo o regime minimax. O novo resultado mostra que, até fatores logarítmicos, a difusividade da a priori adiciona apenas uma constante aditiva ao regret, independente do horizonte de tempo $T$.

3. Limites Inferiores: O artigo estabelece um limite inferior para qualquer política neste cenário, demonstrando que o termo de "burn-in" $d r \sqrt{\text{Tr}(\Sigma_0)}$ é inevitável para a prioras Gaussianas. Isso confirma que a estrutura aditiva do limite superior é apertada (até fatores logarítmicos) e que a difusividade da a priori não pode ser eliminada totalmente do regret.

4. Generalização: Os autores observam que seus resultados podem ser estendidos para distribuições fortemente log-côncavas e distribuições de ruído, não se limitando estritamente ao caso Gaussiano.

Significância
O artigo afirma que seus resultados resolvem uma imprecisão (looseness) nos limites de regret existentes para Thompson Sampling. Ao provar que o termo dependente da a priori é aditivo em vez de multiplicativo, o trabalho esclarece o papel da difusividade da a priori: ela atua como um custo de "burn-in" único necessário para reduzir a incerteza ao nível do ruído de observação, após o qual o desempenho do algoritmo é governado apenas pela variância do ruído $\sigma$ e pela dimensão $d$. Isso fornece uma caracterização mais precisa da eficiência do algoritmo, particularmente em regimes onde a a priori é altamente difusa (grande $\text{Tr}(\Sigma_0)$), mostrando que tal difusividade não degrada permanentemente a taxa de convergência assintótica. A introdução do lema de potencial elíptico generalizado é apresentada como uma ferramenta que permite uma análise mais flexível de problemas de otimização estocástica onde a incerteza inicial pode ser ilimitada.