Active Context Selection Improves Simple Regret in Contextual Bandits

Resumo Técnico: A Seleção Ativa de Contextos Melhora o Arrependimento Simples em Bandits Contextuais

Formulação do Problema
Este artigo investiga o problema do bandit multi-arma contextual dentro de um espaço de contextos finito, onde os contextos representam subpopulações distintas (por exemplo, grupos demográficos). O objetivo de aprendizado é definido pelo arrependimento simples ponderado por contexto: após um orçamento experimental fixo $T$, o agente deve recomendar um único melhor tratamento para cada subpopulação. A métrica de desempenho é a lacuna esperada entre os tratamentos ótimo e recomendado, ponderada pelo vetor de distribuição populacional $p$ sobre as $k$ subpopulações.

O estudo distingue entre dois regimes de amostragem:

1. Amostragem Passiva: Os contextos são revelados aleatoriamente de acordo com a distribuição fixa $p$, e o agente escolhe apenas o tratamento.
2. Amostragem Ativa: O agente pode escolher ativamente tanto a subpopulação (contexto) quanto o tratamento para cada rodada.

A análise assume um cenário de pior caso em relação às distribuições de recompensa, mas permanece dependente da instância em relação à distribuição de contextos $p$. O artigo foca no regime "rico em dados", onde o horizonte $T$ é significativamente maior que o número de tratamentos $n$, contextos $k$ e o inverso da probabilidade mínima de contexto.

Metodologia e Estrutura Teórica

• Alocação Ótima para $p$ Conhecido:
  Quando a distribuição de subpopulações $p$ é conhecida, os autores caracterizam a alocação ótima do orçamento experimental. Eles provam que, para o critério de arrependimento simples de pior caso, políticas livres de histórico (onde a seleção de contexto depende apenas de $p$ e não do histórico observado) são suficientes para alcançar a taxa minimax.

  • Taxa Passiva: Sob amostragem passiva, o arrependimento escala como $\Theta(\sqrt{\frac{n}{T}} \|p\|_{1/2})$.
  • Taxa Ativa: Sob amostragem ativa, a estratégia ótima aloca amostras para a subpopulação $j$ com probabilidade proporcional a $p_j^{2/3}$. Isso alcança uma taxa de arrependimento de $\Theta(\sqrt{\frac{n}{T}} \|p\|_{2/3})$.
  • A Lacuna: O fator de melhoria da amostragem ativa sobre a passiva é caracterizado pela razão $R(p) = \|p\|_{1/2} / \|p\|_{2/3}$. Os autores mostram que, para distribuições altamente não uniformes, essa lacuna pode ser tão grande quanto $\Theta(k^{1/4})$. A alocação ativa ótima desloca as probabilidades de amostragem em direção a uma distribuição mais uniforme em comparação com $p$, aumentando assim a exploração em subpopulações menores.

• Intervenções Orçamentadas:
  O artigo estende a análise para cenários onde a amostragem ativa é custosa, permitindo que o agente escolha a subpopulação em apenas uma fração $\alpha$ das rodadas. Os autores formulam um problema de otimização restrita para minimizar o arrependimento sujeito à restrição de que a alocação $q$ deve satisfazer $q_j \geq (1-\alpha)p_j$. Eles derivam uma estrutura de limiar para a alocação ótima: subpopulações com grande $p_j$ podem permanecer em sua alocação passiva se o orçamento for insuficiente para melhorá-las, enquanto outras são impulsionadas em direção à proporção $p_j^{2/3}$. Eles identificam um orçamento mínimo $\alpha_{\min}(p)$ necessário para recuperar a taxa ótima totalmente ativa.

• $p$ Desconhecido (O Algoritmo EETC):
  Quando $p$ é desconhecido, uma política totalmente ativa não pode simplesmente adotar a regra $p^{2/3}$. Os autores propõem o algoritmo Explore-Explore-Then-Commit (EETC), que equilibra três fases:

  1. Exploração Passiva Inicial: O agente atua passivamente para estimar $p$.
  2. Amostragem Passiva Contínua: O agente continua a amostragem passiva até que o orçamento restante seja suficiente para implementar a alocação ativa ótima com base na estimativa atual.
  3. Comprometimento: O agente muda para amostragem ativa usando a distribuição estimada para alocar as rodadas restantes.
     A análise teórica mostra que, para horizontes grandes, o EETC alcança a mesma taxa de arrependimento simples que a política ativa totalmente ótima com $p$ conhecido, até fatores constantes.

Resultados Chave e Experiências

• Garantias Teóricas: O artigo estabelece taxas de arrependimento rigorosas tanto para $p$ conhecido quanto desconhecido. Ele prova que a seleção ativa de contextos melhora estritamente a amostragem passiva, sendo a magnitude da melhoria dependente da heterogeneidade da distribuição de contextos.
• Experimentos Sintéticos: Experimentos em dados sintéticos confirmam que a lacuna de arrependimento entre políticas passivas e ativas se amplia à medida que o número de subpopulações $k$ aumenta, alinhando-se com o limite teórico $\Theta(k^{1/4})$. O algoritmo EETC demonstra corresponder estreitamente ao desempenho da política ativa de oráculo ($p$ conhecido).
• Dados do Mundo Real (MovieLens): Os autores avaliaram seus métodos no conjunto de dados MovieLens 1M, tratando recomendações de filmes como tratamentos e grupos demográficos como subpopulações. Os resultados indicam que políticas passivas produzem o maior arrependimento. Tanto a política ativa com $p$ conhecido quanto o EETC superam significativamente a linha de base passiva, com o EETC aproximando-se do desempenho da política ativa de oráculo à medida que o horizonte aumenta.

Significado e Afirmações
O artigo afirma quantificar o valor específico da seleção ativa de subpopulações no desenho experimental e no aprendizado de políticas. Sua principal contribuição é demonstrar que a seleção ativa de subpopulações sempre melhora o desempenho sobre a amostragem passiva, sendo o ganho substancial quando a distribuição populacional é enviesada.

Os autores enfatizam que seu trabalho preenche a lacuna entre bandits contextuais padrão (onde os contextos são ambientais) e desenho experimental (onde o experimentador controla a amostra). Ao caracterizar a regra de alocação ótima ($q_j \propto p_j^{2/3}$) e fornecer um algoritmo (EETC) que se adapta a distribuições desconhecidas sem sacrificar a optimalidade assintótica, o artigo oferece um framework rigoroso para alocação eficiente de recursos em populações heterogêneas. O trabalho sugere que, em cenários onde o recrutamento direcionado ou a amostragem controlada são viáveis, ignorar a capacidade de selecionar contextos leva a recomendações de tratamento subótimas.