Characterizing Bias in Post-Bandit Inference under Index Algorithms

Resumo Técnico: Caracterização do Viés na Inferência Pós-Bandido sob Algoritmos de Índice

Problema
O artigo aborda o desafio estatístico de realizar inferência em dados gerados por algoritmos de Multi-Armed Bandit (MAB). Diferente dos dados convencionais e independentes e identicamente distribuídos (i.i.d.), os dados de bandit são coletados de forma adaptativa, criando um ciclo de feedback onde as decisões de alocação dependem de observações passadas. Essa adaptatividade induz um viés de seleção sistemático no estimador da média amostral, $\bar{X}_a(N_a(T))$, o que pode distorcer intervalos de confiança e testes de hipótese. Embora a literatura prévia tenha estabelecido que tal viés existe (ex: Nie et al., 2018) e fornecido limites assintóticos gerais (ex: Shin et al., 2019a,b; Russo e Zou, 2016), há uma carência de caracterizações precisas de primeira ordem para este viés em algoritmos de índice totalmente adaptativos e amplamente utilizados, como o UCB1. A questão central de pesquisa é determinar a magnitude precisa do viés da média amostral e o viés associado à estatística Z sob algoritmos de índice canônicos, e compreender como as escolhas de design algorítmico influenciam esse viés.

Metodologia
Os autores focam em algoritmos de índice estáveis, uma classe que inclui o canônico Upper Confidence Bound (UCB1) e suas generalizações. A inovação metodológica central é uma nova aproximação fluida empírica da dinâmica de amostragem do algoritmo.

1. Aproximação Fluida: Os autores primeiro definem uma aproximação fluida determinística, $n_T$, substituindo as médias amostrais empíricas pelas médias populacionais ($\mu$) nas equações de equalização de índices. Isso captura o comportamento de alocação de primeira ordem, mas ignora flutuações estocásticas.
2. Aproximação Fluida Empírica: Para capturar a correlação crítica entre as contagens de extrações (pull counts) e as flutuações de recompensa que impulsionam o viés, os autores introduzem uma aproximação de segunda ordem, $\tilde{n}_T$. Esta é construída reintroduzindo as médias amostrais avaliadas nas contagens de alocação fluida ($\bar{X}_a(n_{a,T})$) nas equações de equalização de índices.
3. Quantidade Chave: A análise identifica uma quantidade crítica dependente do algoritmo, denominada taxa de exploração efetiva, denotada por $\Gamma_{a,T}$. Para uma função de índice $I_t(x, n)$, esta é definida como $\Gamma_t(x, n) := -2n^{3/2} \frac{\partial_n I_t(x, n)}{\partial_x I_t(x, n)}$. Esta taxa quantifica o quão responsiva é a alocação a perturbações na média amostral; uma taxa mais alta implica menor responsividade e, portanto, menor viés.
4. Condições de Estabilidade: Os resultados teóricos dependem de três condições: regularidade da função de índice (suavidade e monotonicidade), condições de escala fluida (garantindo que braços subótimos sejam extraídos o suficiente para concentração) e condições de estabilidade (garantindo que as contagens de extrações reais se concentrem em torno da aproximação fluida empírica).

Principais Contribuições e Resultados

• Caracterização Precisa do Viés: O artigo deriva expressões explícitas de primeira ordem para o viés da média amostral e da estatística Z conforme $T \to \infty$.

  • Para qualquer braço $a$ que não seja o braço ótimo único, o viés padronizado da estatística Z, $E[Z_{a,T}]$, converge para:
    $$E[Z_{a,T}] \approx -\left(1 - \frac{1}{|O|}\mathbb{1}\{a \in O\}\right) \frac{\sigma_a}{\Gamma_{a,T}}$$
    onde $O$ é o conjunto de braços ótimos e $\sigma_a$ é o desvio padrão da recompensa.
  • Para o braço ótimo único, o viés é de uma ordem muito menor, decaindo polinomialmente rápido (ex: $O(f_T/T)$ para UCB generalizado), enquanto braços ótimos não únicos exibem um viza que decai à taxa de $1/\Gamma_{a,T}$.

• Aplicação ao UCB Generalizado: Especializando para algoritmos de UCB generalizado com índice $I_t(x, n) = x + f_t/\sqrt{n}$, a taxa de exploração efetiva é $\Gamma_{a,T} = f_T$.

  • Caso UCB1: Para o UCB1 padrão, $f_T = \sqrt{2 \log T}$. Consequentemente, o viés padronizado decai à taxa extremamente lenta de $1/\sqrt{\log T}$. Isso implica que, mesmo para $T$ grande, o viés permanece substancial na escala inferencial.
  • Caso Generalizado: O viés escala como $1/f_T$.

• Trade-off Regret-Viés: Os autores estabelecem um trade-off fundamental entre a minimização do regret (arrependimento) e o viés de inferência.

  • O regret para o UCB generalizado escala como $f_T^2$.
  • O viés escala como $1/f_T$.
  • Portanto, o viés escala como $1/\sqrt{\text{Regret}}$. Algoritmos projetados para minimizar o regret agressivamente (como o UCB1 com $f_T$ de crescimento lento) incorrem em maior viés. Inversamente, algoritmos mais exploratórios (com $f_T$ de crescimento mais rápido) reduzem o viés, mas aumentam o regret.

• Origem Algorítmica do Viés: Os resultados revelam que o viés é impulsionado pela "taxa de exploração efetiva". O viés surge porque o algoritmo ajusta as alocações para equalizar os índices; quando a média amostral de um braço flutua para cima, o algoritmo o extrai com mais frequência, criando uma correlação positiva entre o número de extrações e a média amostral. Essa correlação positiva resulta em um viés negativo (para baixo) no estimador em relação à média real, como refletido no sinal negativo da expressão de primeira ordem.

Significância e Alegações
O artigo afirma fornecer a primeira caracterização precisa de primeira ordem do viés para algoritmos de índice estáveis e totalmente adaptativos. Sua significância reside em:

1. Quantificar o Custo Inferencial: Demonstra que, para algoritmos padrão como o UCB1, o viés decai tão lentamente ($1/\sqrt{\log T}$) que pode dominar o erro padrão em configurações de inferência prática, desafiando a validade da inferência pós-bandido padrão sem correção.
2. Insight Algorítmico: Esclarece que o viés não é meramente uma função da adaptatividade, mas é estruturalmente determinado pela forma específica da função de índice (via taxa de exploração efetiva).
3. Implicações de Design: Destaca uma distinção qualitativa entre instâncias com um braço ótimo único (baixo viés) e aquelas com múltiplos braços ótimos (alto viés), e mapeia explicitamente o trade-off entre minimizar o regret e minimizar o viés.
4. Contribuição Metodológica: A estrutura de aproximação fluida empírica é apresentada como uma ferramenta tratável para analisar as complexas dependências temporais na amostragem adaptativa, potencialmente aplicável a outras propriedades inferenciais de algoritmos de bandit.

Os autores observam que seus resultados são específicos para algoritmos de índice estáveis e não se aplicam diretamente a algoritmos instáveis (como Thompson Sampling ou $\epsilon$-greedy) ou métodos de não-índice, sugerindo estes como direções para trabalhos futuros. Eles também enfatizam que, embora a fórmula do viés sugira correções naturais, construir intervalos de confiança práticos com desempenho de amostra finita melhorado continua sendo uma tarefa em aberto.