Anytime-valid Optimal Policy Identification

Resumo Técnico: Identificação de Política Ótima com Validade em Tempo Real (Anytime-Valid)

1. Definição do Problema

O artigo aborda o desafio de identificar uma política ótima ($\pi^\star$) a partir de uma classe finita de candidatas $\Pi = \{\pi_1, \dots, \pi_m\}$ utilizando dados de bandit contextual registrados (logged). Em muitos cenários práticos, os dados são gerados por uma política de registro (logging policy) ($h_t$) externa, determinada externamente e que o analista não controla. Esta política de registro pode ser uma randomização fixa ou um algoritmo adaptativo ajustado para objetivos diferentes dos do analista (por exemplo, maximizar o engajamento do usuário em vez de minimizar a desinformação).

A dificuldade central reside em duas restrições:

1. Configuração Off-Policy: O analista deve inferir o valor das políticas alvo $\nu(\pi)$ usando dados coletados sob uma política diferente $h_t$, sem a capacidade de direcionar a coleta de dados para o objetivo de identificação.
2. Monitoramento Sequencial: Profissionais frequentemente desejam monitorar evidências continuamente, eliminar políticas claramente subótimas à medida que os dados se acumulam e interromper a coleta de dados assim que a política ótima for identificada, em vez de se comprometer com um tamanho de amostra fixo ($N$) antecipadamente.

A literatura existente sobre identificação de política ótima geralmente assume que o analista controla a coleta de dados (amostragem adaptativa) ou fornece garantias de inferência apenas para um tamanho de amostra pré-especificado e fixo. Este artigo busca preencher essa lacuna ao fornecer garantias de validade em tempo real (anytime-valid) para a identificação de políticas ótimas em configurações off-policy.

2. Metodologia

O framework proposto constrói um conjunto de políticas candidatas ótimas indexado pelo tempo, $S_t$, que evolui conforme os dados chegam. A metodologia baseia-se em três componentes principais:

A. Pseudo-Resultados Duplamente Robustos (Doubly Robust Pseudo-Outcomes)
Para estimar os valores das políticas $\nu(\pi)$ a partir de dados registrados, o método utiliza pesos de importância $w_t(\pi) = \pi(A_t|X_t) / h_t(A_t|X_t)$. Para melhorar a eficiência e a estabilidade, estes são combinados com um modelo de recompensa $b_{rt}(x,a)$ para construir pseudo-resultados duplamente robustos (DR). Especificamente, pseudo-resultados inferiores e superiores ($\phi^{DRL}_t$ e $\phi^{DRU}_t$) são definidos de tal forma que suas expectativas condicionais sejam iguais ao valor real da política $\nu(\pi)$ e $1-\nu(\pi)$, respectivamente. Crucialmente, a validade não depende da especificação correta do modelo de recompensa, apenas das probabilidades de registro conhecidas.

B. Sequências de Confiança (CS) com Validade em Tempo Real
Baseando-se no trabalho de Waudby-Smith et al. (2024), o artigo constrói sequências de confiança para os valores das políticas. Uma sequência de intervalos $[L_t(\pi), U_t(\pi)]$ é uma CS $(1-\alpha)$ se o valor real $\nu(\pi)$ permanecer dentro do intervalo para todo $t \geq 1$ com probabilidade de pelo menos $1-\alpha$. Estes intervalos são construídos usando os pseudo-resultados DR e um processo de variância $V_t(\pi)$ que contabiliza o acúmulo de evidências. A largura destes intervalos diminui a uma taxa de $O(\sqrt{(\log \log t + \log m)/t})$.

C. Eliminação Sequencial e Regra de Parada
Utilizando um limite superior (union bound) sobre a classe de políticas $\Pi$, o método constrói sequências de confiança simultâneas para todas as políticas. O conjunto candidato $S_t$ é definido como:
$$S_t := \left\{ \pi \in \Pi : U_t\left(\pi; \frac{\alpha}{m}\right) \geq \max_{\pi' \in \Pi} L_t\left(\pi'; \frac{\alpha}{m}\right) \right\}$$
Uma política é eliminada de $S_t$ se o seu limite superior de confiança cair abaixo do limite inferior de confiança máximo de qualquer política concorrente. O procedimento para em um tempo dependente dos dados $\tau$ quando $S_\tau$ torna-se um singleton (contendo apenas uma política).

3. Principais Contribuições

O artigo apresenta duas contribuições teóricas primordiais:

1. Garantia de Cobertura com Validade em Tempo Real: Os autores provam que o conjunto $S_t$ construído satisfaz uma garantia de cobertura uniforme:
   $$P(\Pi^\star \subseteq S_t \text{ para todo } t \geq 1) \geq 1 - \alpha$$
   onde $\Pi^\star$ é o conjunto das verdadeiras políticas ótimas. Isso garante que, com alta probabilidade, nenhuma política ótima seja jamais eliminada, independentemente de quando o analista decidir parar.

2. Limites de Complexidade de Amostra: Quando a política ótima $\pi^\star$ é única, o artigo define um tempo de parada $\tau$ para sua identificação. Sob uma condição de regularidade de crescimento de variância linear (Assunção 1), a complexidade de amostra é derivada como:
   $$\tau = O\left( \frac{\log m + \log \log(1/\Delta_{\min})}{\Delta_{\min}^2} \right)$$
   onde $\Delta_{\min}$ é o hiato (gap) entre o valor da melhor política e o da segunda melhor. Este limite indica que o número de amostras necessárias escala logaritmicamente com o tamanho da classe de políticas e inversamente com o quadrado do hiato de subotimalidade.

4. Resultados Empíricos

O artigo valida o framework através de três demonstrações empíricas:

• Ilustração Sintética: Em um cenário simulado de bandit contextual com seis políticas, o framework conseguiu eliminar políticas claramente subótimas precocemente no fluxo de dados, enquanto manteve a política ótima até que ela fosse identificada de forma única. As sequências de confiança para os valores das políticas convergiram para os valores reais, conforme esperado.
• Eficiência de Amostra: Comparando o procedimento com validade em tempo real contra um delineamento de $N$ fixo (onde $N$ é calculado com base em um $\Delta$ alvo), os autores encontraram economias substanciais de amostra quando o verdadeiro hiato de subotimalidade era maior que o hiato alvo. Por exemplo, se o verdadeiro hiato fosse o dobro do alvo, o método com validade em tempo real economizou, em média, 60–80% do tamanho de amostra planejado.
• Aplicação no Mundo Real: O método foi aplicado a um grande experimento adaptativo (Offer-Westort et al., 2024) envolvendo 15.292 usuários no Quênia e na Nigéria, visando reduzir o compartilhamento de desinformação. O framework replicou a conclusão do estudo original (identificando "nudge de precisão" e "dicas do Facebook" como os melhores desempenhos), mas forneceu uma visão dinâmica do acúmulo de evidências. Mostrou que as piores políticas puderam ser eliminadas com apenas uma fração dos dados finais, enquanto as principais candidatas permaneceram no conjunto de candidatos durante todo o processo.

5. Significância e Limitações

Significância:
O artigo fornece um framework inferencial rigoroso para o monitoramento sequencial em configurações off-policy. Ele permite que analistas tomem decisões de parada dependentes dos dados sem invalidar as garantias estatísticas, abordando uma limitação fundamental das abordagens de $N$ fixo. Isso é particularmente valioso em aplicações do mundo real onde a coleta de dados é limitada por políticas de registro externas e os recursos são limitados.

Limitações:
Os autores explicitamente apontam duas limitações:

1. Invariância Temporal: O framework assume que os valores das políticas são constantes ao longo do tempo. Ele não lida atualmente com ambientes não estacionários onde os efeitos do tratamento evoluem (por exemplo, devido à novidade ou fadiga).
2. Requisito de Sobreposição (Overlap): O método exige que toda política alvo seja absolutamente contínua em relação à política de registro (sobreposição estrita). Isso exclui cenários onde a política de registro atribui deterministicamente probabilidade zero a ações que uma política alvo tomaria, o que pode ocorrer em algoritmos adaptativos altamente concentrados (ex: estilo UCB).

O artigo conclui que, embora essas limitações existam, o framework oferece uma solução robusta para uma ampla classe de políticas de registro estocásticas comumentes encontradas na prática.