On Pareto Optimality for Parametric Choice Bandits

Resumo Técnico: Otimalidade de Pareto para Bandidos de Escolha Paramétricos

1. O Problema

O artigo aborda o problema de otimização de sortimento online sob modelos de escolha estocástica. Em sistemas de decisão modernos, existe uma tensão fundamental entre dois objetivos conflitantes:

1. Desempenho Online (Regret): Maximizar a receita cumulativa ao longo de um horizonte $T$, escolhendo os melhores conjuntos de itens (sortimentos) com base no conhecimento atual.
2. Precisão Inferencial (Inference): Garantir que os dados coletados permitam realizar inferências estatísticas confiáveis (como contrastes de receita entre dois produtos) após o experimento ter terminado.

Políticas focadas apenas em maximizar a receita tendem a explorar pouco as variações necessárias para uma boa inferência, enquanto políticas puramente exploratórias sacrificam a receita. O objetivo é encontrar o equilíbrio de Pareto entre esses dois critérios.

2. Metodologia

Os autores propõem uma arquitetura de Exploração Forçada baseada em Otimismo diante da Incerteza (OFU - Optimism-in-the-Face-of-Uncertainty). A estratégia utiliza dois estimadores de Máxima Verossimilhança Regularizada (MLE):

• Estimador de Decisão ($\hat{\theta}_t$): Baseado em todas as observações até o tempo $t$, usado para construir conjuntos de confiança e guiar a escolha de sortimentos otimistas.
• Estimador de Inferência ($\hat{e}_{\theta_T}$): Baseado apenas nas rodadas de exploração forçada, preservando uma estrutura de informação limpa para estimar contrastes de receita post-hoc.

Base Teórica: O trabalho desenvolve uma teoria geral baseada em proxies de score e curvatura previsíveis. Em vez de assumir uma curvatura global constante, a teoria rastreia a acumulação de proxies de Hessiana (curvatura) ao longo da trajetória de ações escolhidas. Isso permite derivar desigualdades de concentração autonormalizadas e conjuntos de confiança elipsoidais.

3. Principais Contribuições

1. Teoria Geral de Confiança e Regret: Estabelecem garantias de erro de regret e erro de inferência que dependem da acumulação de informação (matrizes de curvatura e score), permitindo inclusive erros de otimização aproximada ($\epsilon_t$).
2. Instanciação para o Modelo MNL (Multinomial Logit): Demonstram que, para o modelo MNL, um cronograma de exploração de singletons espaçados e balanceados (oferecer um item por vez de forma cíclica) garante a cobertura necessária para obter taxas de erro explícitas.
3. Análise de Pareto e Limites (Bounds): Provam que, dentro de uma família de cronogramas polinomiais ($n_T \asymp T^\alpha$), existe um intervalo de otimalidade de Pareto.
4. Extensibilidade: Fornecem condições suficientes para estender o framework para modelos mais complexos, como o Exponomial Choice e o Nested Logit.

4. Resultados Principais

Ao aplicar o modelo ao MNL com um orçamento de exploração $n_T$, os autores obtêm:

• Regret (Arrependimento): $\tilde{O}(n_T + T/\sqrt{n_T})$.
• Erro de Contraste de Receita: $\tilde{O}(1/\sqrt{n_T})$.

A Fronteira de Pareto:
Ao analisar o tradeoff através de um cronograma polinomial $n_T \asymp T^\alpha$:

• O intervalo $\alpha \in [2/3, 1)$ é considerado Pareto-não-dominado em termos de taxa (rate-wise).
• O ponto $\alpha = 2/3$ é o ponto de equilíbrio único que minimiza o expoente do regret, resultando em um regret de $\tilde{O}(T^{2/3})$ e erro de inferência de $\tilde{O}(T^{-1/3})$.
• O artigo prova um limite inferior (lower bound) que mostra que o produto entre o erro de inferência e a raiz quadrada do regret é constante, confirmando que não é possível melhorar ambos simultaneamente além de um certo limite.

5. Significância

Este trabalho é significativo por fornecer uma base matemática rigorosa para o design de experimentos adaptativos em gestão de receita. Ele move a discussão de "apenas maximizar lucro" para um framework de "aprendizado estatístico útil", permitendo que empresas tomem decisões de marketing ou precificação que sejam, ao mesmo tempo, lucrativas no curto prazo e cientificamente válidas para análises de longo prazo. A distinção entre o estimador de decisão e o de inferência resolve o problema de viés que ocorre quando se usa dados de exploração greedily para inferência estatística.