Resumo Técnico: Exploração Pura para uma Boa Política em Aprendizado por Reforço com Feedback de Bandit

1. Formulação do Problema

Este artigo aborda o problema de Identificação de Boa Política (GPI) no âmbito da Exploração Pura em Aprendizado por Reforço (RL). Diferentemente do objetivo tradicional de Identificação da Melhor Política (BPI), que busca identificar uma política (quase) ótima com alta confiança, o GPI foca em encontrar uma política que satisfaça um limiar de desempenho específico.

Formalmente, dado um Processo de Decisão de Markov (MDP) episódico com dinâmicas de transição desconhecidas $P$ e distribuição inicial $p$, um espaço de estados finito $S$, espaço de ações $A$ e horizonte $H$, o agente recebe um limiar de recompensa $\mu_0$. O objetivo é projetar um algoritmo $\delta$-Provavelmente Aproximadamente Correto ($\delta$-PAC) que:

• Instância Positiva: Se existir uma política $\pi$ tal que sua recompensa total esperada $V^\pi_0(s_0) \ge \mu_0$, o algoritmo deve outputar tal política com probabilidade de pelo menos $1-\delta$.
• Instância Negativa: Se o valor da política ótima $V^*_0(s_0) < \mu_0$, o algoritmo deve outputar "Nenhum" com probabilidade de pelo menos $1-\delta$.

A métrica de desempenho é a complexidade de amostra esperada (o número esperado de episódios explorados, denotado como $\tau$) necessária para alcançar uma decisão correta. O artigo exclui explicitamente o caso onde $V^*_0(s_0) = \mu_0$, pois trabalhos anteriores (Degenne e Koolen [2019]) estabeleceram que qualquer algoritmo $\delta$-PAC exigiria amostras infinitas neste caso limite.

2. Metodologia: BEE-GPI

Os autores propõem um novo algoritmo denominado BEE-GPI (Exploração-Exploração Balanceada para Identificação de Boa Política). O algoritmo opera em fases $k=1, 2, \dots$, onde cada fase consiste em uma etapa de exploração adaptativa seguida por um mecanismo de ramificação de decisão.

Componentes Chave:

1. Etapa de Exploração (ES-BPI-UCRL):

   • Esta etapa utiliza um oráculo BPI-UCRL com Parada Antecipada. Emprega uma estratégia de amostragem otimista (semelhante ao BPI-UCRL) para estimar os kernels de transição e as funções de valor.
   • Crucialmente, introduz um novo mecanismo de parada antecipada. O oráculo verifica duas condições em cada passo:
     • Condição (3): Um limite inferior de confiança sobre o valor da política otimista atual excede $\mu_0$ (ajustado por um fator $C$). Se atendido, uma política candidata é identificada.
     • Condição (4): Um limite superior de confiança sobre a função de valor ótima está abaixo de $\mu_0$. Se atendido, a instância é declarada negativa.
   • Se nenhuma das condições for atendida e o orçamento de exploração $T^{ee}_k$ não for excedido, o algoritmo continua amostrando.

2. Ramificação de Decisão:

   • Se o oráculo retornar "Não Concluído", o algoritmo prossegue para a próxima fase com uma tolerância de erro mais estrita $\delta_k$ e orçamento aumentado.
   • Se o oráculo retornar "Nenhum" mas a confiança for insuficiente ($\delta_k \ge \delta/10$), o algoritmo continua para a próxima fase para garantir a garantia $\delta$-PAC.
   • Se o oráculo retornar uma política candidata $\hat{\pi}_k$, o algoritmo entra na Etapa de Exploração (Exploitation).

3. Exploração e Verificação:

   • Nesta etapa, a política candidata $\hat{\pi}_k$ é executada repetidamente para estimar seu valor real.
   • O algoritmo constrói um intervalo de confiança para a recompensa média empírica. Se o limite inferior de confiança exceder $\mu_0$ dentro de um orçamento de amostra específico, a política é outputada como a solução.
   • Se o orçamento for esgotado sem verificação, o algoritmo retorna à fase de exploração da próxima iteração.

3. Contribuições Principais

O artigo faz três contribuições teóricas primárias:

1. Formalização do GPI: Os autores definem formalmente o problema de Identificação de Boa Política no cenário de confiança fixa, distinguindo-o do $\epsilon$-BPI. Eles destacam que reduções padrão de $\epsilon$-BPI são subótimas para o GPI porque o gap $V^*_0(s_0) - \mu_0$ é desconhecido a priori, tornando a escolha de $\epsilon$ difícil.
2. Projeto de Algoritmo e Limites Superiores: Eles propõem o BEE-GPI e derivam limites superiores fundamentados teoricamente sobre sua complexidade de amostra para instâncias positivas e negativas.
   • Instâncias Positivas: A complexidade de amostra é limitada por $O\left(\frac{H^2 \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right) + O\left(\frac{\text{poly}(S, A, H)}{(V^*_0(s_0) - \mu_0)^2}\right)$.
   • Instâncias Negativas: O limite envolve termos acoplados com os tamanhos dos espaços de estado e ação, especificamente $O\left(\frac{(H+1)^4 SA \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right)$.
3. Limites Inferiores e Near-Optimalidade: Os autores estabelecem limites inferiores para o problema GPI usando "Instâncias Uniformes" construídas (para casos positivos) e "Instâncias em Árvore" (para casos negativos).
   • Eles provam que, para instâncias positivas, qualquer algoritmo $\delta$-PAC deve incorrer em uma complexidade de amostra de $\Omega\left(\frac{H \log(1/\delta)}{(V^*_0 - \mu_0)^2} + \frac{H^2 SA}{(V^*_0 - \mu_0)^2}\right)$.
   • Para instâncias negativas, o limite inferior é $\Omega\left(\frac{HSA \log(1/\delta)}{(\mu_0 - V^*_0)^2}\right)$.
   • Esses resultados demonstram que o BEE-GPI é near-optimal, com a lacuna entre os limites superior e inferior limitada a fatores polinomiais de $S, A, H$.

4. Resultados e Análise

Insights Teóricos

• Desacoplamento de Termos Logarítmicos: Uma descoberta significativa é que, para instâncias positivas, o coeficiente do termo $\log(1/\delta)$ na complexidade de amostra é $O(H^2)$ e é independente do tamanho do espaço de estados $S$ e do tamanho do espaço de ações $A$. Isso contrasta fortemente com reduções padrão de BPI, onde o coeficiente tipicamente escala polinomialmente com $S$ e $A$.
• Assimetria: Há uma assimetria inerente entre instâncias positivas e negativas. Enquanto instâncias positivas permitem a identificação eficiente de uma boa política sem explorar todo o espaço estado-ação, instâncias negativas exigem exploração global para certificar que nenhuma política atende ao limiar, daí a dependência de $S$ e $A$ no termo $\log(1/\delta)$.

Experimentos Numéricos

Os autores validam sua abordagem usando dois ambientes clássicos: MDPs de Cadeia Única e Cadeia Dupla.

• Configuração: Eles comparam o BEE-GPI contra o algoritmo BPI-UCRL de última geração (Kaufmann et al. [2021]). Para garantir uma comparação justa, o BPI-UCRL recebe o parâmetro oráculo $\epsilon = V^*_0 - \mu_0$, fornecendo-lhe conhecimento prévio significativo.
• Descobertas: Em vários limiares $\mu_0$, o BEE-GPI consistentemente requer significativamente menos episódios para identificar uma política qualificada em comparação com o BPI-UCRL. Os resultados empíricos confirmam a vantagem teórica de desacoplar o termo $\log(1/\delta)$ dos tamanhos dos espaços de estado e ação.

5. Significado e Alegações

O artigo alega que o BEE-GPI oferece uma solução mais eficiente para cenários práticos de RL onde encontrar a política absolutamente ótima é desnecessário ou computacionalmente proibitivo, mas encontrar uma política "suficientemente boa" (excedendo um benchmark) é crítico.

• Relevância Prática: Os autores citam aplicações em informática médica (identificação de tratamentos que excedem um padrão de cuidado), computação em nuvem (atendimento a Acordos de Nível de Serviço) e finanças (atendimento a benchmarks de ROI), onde o objetivo é a satisfação do limiar e não a otimalidade.
• Avanço Teórico: Ao formalizar o GPI e fornecer limites near-optimal, o trabalho preenche a lacuna entre a exploração pura teórica e requisitos práticos baseados em limiares. Demonstra que a complexidade de amostra pode ser significativamente reduzida quando o objetivo é relaxado de otimalidade para satisfação de limiar, particularmente no caso de instância positiva.
• Direções Futuras: Os autores modestamente sugerem que trabalhos futuros poderiam envolver a derivação de limites dependentes de instância mais apertados e a extensão deste framework para MDPs em grande escala usando aproximação de função.

Em resumo, o artigo estabelece que identificar uma política que atende a um limiar de recompensa é fundamentalmente diferente de identificar a melhor política, e propõe um algoritmo que aproveita essa distinção para alcançar eficiência de amostra superior, particularmente quando o gap entre o valor ótimo e o limiar é o principal motor da dificuldade.