Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context

Resumo Técnico: Exploração Pura Além do Feedback de Recompensa: O Papel do Contexto Pós-Ação

Formulação do Problema
Este artigo introduz uma nova variante do problema de Identificação do Melhor Braço (BAI) no cenário de confiança fixa de banditos multi-braço estocásticos (MAB). Neste cenário, denominado "BAI com contexto pós-ação", o agente seleciona uma ação (braço) $X$ e observa não apenas a recompensa $Y$, mas também um contexto intermediário pós-ação $Z$. O contexto $Z$ é gerado como consequência da ação escolhida, distinguindo este problema dos banditos contextuais padrão, onde o contexto precede a ação.

Os autores analisam dois regimes estruturais definidos pela relação causal entre ação, contexto e recompensa:

1. Contexto Separador: A recompensa $Y$ depende exclusivamente do contexto $Z$, tornando $X$ e $Y$ condicionalmente independentes dado $Z$ ($P(Y|X, Z) = P(Y|Z)$). Neste caso, a distribuição de recompensa é determinada inteiramente pelo contexto observado.
2. Contexto Não-Separador: A recompensa $Y$ depende tanto da ação $X$ quanto do contexto $Z$ ($P(Y|X, Z) \neq P(Y|Z)$). Aqui, o contexto fornece informações adicionais, mas não é uma estatística suficiente para a recompensa.

O objetivo é identificar o braço com a maior recompensa esperada com uma probabilidade de erro de no máximo $\delta$, minimizando a complexidade de amostragem (o número de rodadas necessárias).

Metodologia e Algoritmos
O artigo deriva limites inferiores dependentes da instância para a complexidade de amostragem em ambos os cenários e propõe algoritmos que alcançam assintoticamente esses limites.

• Cenário Separador:

  • Limite Inferior: Os autores derivam um limite inferior que depende das frequências de contextos observados, e não das frequências de braços puxados. Isso ocorre porque, no cenário separador, qualquer observação de um contexto específico $Z=j$ fornece informações sobre a recompensa média daquele contexto, independentemente de qual braço a gerou.
  • Algoritmo (STS): O algoritmo proposto "Separator Track and Stop" (STS) utiliza uma regra de amostragem inovadora chamada G-tracking. Diferentemente dos métodos tradicionais que rastreiam as frequências ótimas de puxada de braços, o G-tracking rastreia as frequências ótimas de observação de contextos. Ele trata o problema como uma tarefa de aprendizado off-policy ativo, onde o agente seleciona uma distribuição sobre os braços para alcançar uma distribuição-alvo sobre os contextos. O algoritmo resolve um problema de otimização convexa para encontrar as frequências ótimas de contexto e utiliza uma projeção geométrica para selecionar a próxima distribuição de braços, garantindo que as frequências de contexto observadas convirjam para o alvo ótimo.

• Cenário Não-Separador:

  • Limite Inferior: O limite inferior derivado considera a distribuição conjunta de ações e contextos.
  • Algoritmo (NSTS): O algoritmo "Non-Separator Track and Stop" (NSTS) estende o framework clássico Track-and-Stop. Ele emprega D-tracking para estimar e rastrear as proporções ótimas de puxar braços específicos, utilizando a informação conjunta das ações e seus contextos resultantes para refinar as estimativas das médias de recompensa.

Principais Contribuições

1. Definição do Problema: Formalização do BAI com contexto pós-ação, distinguindo entre regimes estruturais separadores e não-separadores.
2. Limites Teóricos: Derivação de limites inferiores dependentes da instância para a complexidade de amostragem em ambos os regimes. O limite separador é mostrado como estritamente mais apertado do que limites derivados da ignorância do contexto.
3. Design de Algoritmos:
   • Introdução do G-tracking, uma regra de amostragem que otimiza diretamente as frequências de observação de contexto no cenário separador, aproveitando a geometria do espaço de contexto.
   • Extensão do framework Track-and-Stop para o cenário não-separador (NSTS).
4. Análise de Sub-otimalidade: Demonstração teórica e empírica de que algoritmos que ignoram o contexto pós-ação (como o Track-and-Stop padrão) são estritamente sub-ótimos. No cenário separador, ignorar o contexto pode levar a aumentos arbitrariamente grandes na complexidade de amostragem, mesmo quando as lacunas de recompensa são pequenas, pois falha em utilizar a estrutura de independência condicional.
5. Análise de Redução: O artigo analisa a redução do problema separador para banditos lineares, mostrando que tais reduções aumentam o limite inferior da complexidade de amostragem em comparação com a abordagem direta proposta.

Resultados

• Teóricos: Os algoritmos propostos (STS e NSTS) são provados ser $\delta-corretos$ e alcançam otimalidade assintótica, correspondendo aos limites inferiores derivados quando $\delta \to 0$.
• Empíricos: Experimentos em dados sintéticos e dados do mundo real (logs de recomendação KuaiSAR) demonstram ganhos significativos de desempenho.
  • No cenário separador, o STS supera drasticamente as linhas de base (Track-and-Stop e Lazy Track-and-Stop), que frequentemente falham em parar dentro de horizontes de tempo razoáveis.
  • No cenário não-separador, o NSTS reduz significativamente o número de amostras necessárias em comparação com o Track-and-Stop, que ignora informações de contexto.
  • Gráficos de rastreamento confirmam que o STS converge para as frequências ótimas de contexto, enquanto as linhas de base falham em alinhar-se com a estratégia ótima.

Significado e Alegações
O artigo alega que aproveitar o contexto pós-ação altera fundamentalmente a estratégia ótima para exploração pura. Os autores enfatizam que, em cenários onde observações intermediárias (mediadores) estão disponíveis, ignorá-las leva a uma ineficiência substancial. Especificamente, no cenário separador, a capacidade de agrupar informações entre diferentes braços que geram o mesmo contexto permite uma identificação muito mais rápida do melhor braço. O trabalho destaca que os algoritmos BAI padrão não são meramente sub-ótimos, mas podem ser arbitrariamente ineficientes nesses ambientes estruturados. O artigo conclui que trabalhos futuros poderiam abordar o caso em que a matriz de probabilidade de contexto é desconhecida, observando que isso introduz desafios de não-convexidade que tornam o design de algoritmos eficientes difícil.