Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization

Resumo Técnico: Seleção de Episódios Inspirada em Computação Quântica para Aprendizado por Reforço de Monte Carlo via Otimização QUBO

Declaração do Problema
O aprendizado por reforço de Monte Carlo (MC) enfrenta desafios significativos em relação à eficiência de amostragem, particularmente em ambientes caracterizados por recompensas esparsas, grandes espaços de estados e trajetórias temporalmente correlacionadas. Métodos MC padrão baseiam-se na premissa de que as amostras de dados são independentes e identicamente distribuídas (i.i.d.), uma premissa violada pela natureza Markoviana das trajetórias de RL. Consequentemente, os estimadores de MC sofrem de:

1. Propagação de Variância: Os retornos exibem variância cumulativa, exigindo um número de episódios ($N_s$) que escala como $O(\epsilon^{-2})$ para reduzir o erro de estimativa.
2. Diluição Subótima de Trajetória: Em domínios de recompensa esparsa, o estimador é diluído por trajetórias de baixa recompensa, necessitando de um crescimento exponencial no tamanho da amostra para garantir cobertura suficiente dos caminhos ótimos.
3. Explosão Combinatória: Teoricamente, selecionar um subconjunto ideal de $m$ episódios de $N$ candidatos para maximizar a precisão da estimativa de valor é um problema NP-difícil, isomorfo à seleção de características e cobertura de conjuntos, com um espaço de solução de $\binom{N}{m}$.

Metodologia
Os autores propõem o MC+QUBO, um framework que reformula o processo de seleção de episódios como um problema de Otimização Binária Quadrática Não Restrita (QUBO). Em vez de usar todos os episódios amostrados para atualizações de política, o método filtra um lote de trajetórias para selecionar um subconjeto que maximize a recompensa cumulativa enquanto promove a cobertura do espaço de estados (diversidade).

• Formulação QUBO: O problema de seleção é codificado como:
  $$\min_{x \in \{0,1\}^n} \left( -\alpha \sum_{i=1}^n R_i x_i + \gamma \sum_{i<j} w_{ij} x_i x_j \right)$$
  Onde:

  • $x_i = 1$ indica a seleção do episódio $\tau_i$.
  • $R_i$ é a recompensa cumulativa do episódio $i$.
  • $w_{ij}$ representa a similaridade pareada entre episódios (ex: similaridade de Jaccard dos conjuntos de estados visitados).
  • $\alpha$ é um multiplicador de escala de recompensa, e $\gamma$ pondera a penalidade de similaridade.
  • O termo linear ($-\alpha R_i$) favorece episódios de alta recompensa, enquanto o termo quadrático ($\gamma w_{ij}$) penaliza a redundância, incentivando a seleção de trajetórias diversas.

• Solvers Inspirados em Computação Quântica: O problema QUBO é resolvido usando samplers de caixa-preta inspirados em computação quântica, especificamente Recozimento Quântico Simulado (SQA) e Bifurcação Simulada (SB).

  • SQA mimetiza o recozimento quântico usando atualizações estocásticas clássicas e Monte Carlo de integral de caminho para simular o tunelamento quântico entre mínimos de energia.
  • SB utiliza uma abordagem de sistema dinâmico clássico onde variáveis contínuas evoluem em direção a estados binários via fenômenos de bifurcação.
  • Os autores tratam esses solvers como oráculos que fornecem soluções aproximadas de alta qualidade dentro de orçamentos computacionais práticos.

• Integração: O fluxo de trabalho envolve gerar um lote de episódios, computar recompensas e similaridades, formular o QUBO, despachar o problema para o solver e usar a melhor solução observada (o vetor binário $x^*$) para determinar quais episódios serão usados para atualizar a tabela de valor de ação $Q(s, a)$ via MC de primeira visita.

Principais Contribuições

1. Reformulação da Seleção de Episódios: O artigo estabelece um elo formal entre a seleção de episódios de MC e a otimização combinatória, demonstrando que o problema de seleção pode ser mapeado para uma formulação QUBO.
2. Integração Algorítmica: Introduz um pipeline concreto (Algoritmo 2) que insere uma etapa de filtragem baseada em QUBO entre a amostragem de trajetória e a avaliação de política no aprendizado MC padrão.
3. Validação Empírica: O estudo avalia o método em ambientes GridWorld de horizonte finito de vários tamanhos ($3\times3$ a $20\times20$), comparando o MC+QUBO contra um baseline de MC vanilla.

Resultados
Experimentos conduzidos em ambientes GridWorld demonstram que o MC+QUBO supera consistentemente o MC vanilla em termos de velocidade de convergência e qualidade da política final.

• Escalabilidade: A lacuna de desempenho aumenta em ambientes maiores ($\ge 10\times10$), onde recompensas esparsas e o crescimento exponencial do espaço de estados tipicamente dificultam a avaliação MC padrão.
• Convergência: O MC+QUBO converge em menos lotes ao focar o aprendizado em trajetórias informativas e diversas, filtrando efetivamente episódios redundantes.
• Insight de Design: Os autores observam que priorizar a cobertura do espaço de estados (definindo a influência do peso da recompensa próximo de zero) resultou em um aprendizado mais equilibrado e melhor generalização do que a seleção impulsionada por recompensa, que tendia a causar uma convergência mais rápida, porém menos estável.
• Desempenho do Solver: Solvers inspirados em computação quântica (SQA e SB) superaram heurísticas clássicas (como Tabu Search e Simulated Annealing) neste contexto. A latência computacional foi dominada pela comunicação em nuvem, e não pelo tempo do solver em si (que foi negligenciável para $n \le 200$).

Significância e Alegações
O artigo alega que integrar a otimização inspirada em computação quântica como uma subrotina de tomada de decisão no aprendizado por reforço oferece um aprimoramento prático para métodos de MC, particularmente para problemas com recompensas esparsas e trajetórias correlacionadas. Ao unir RL com otimização combinatória, o estudo sugere um caminho para algoritmos onde métodos quânticos e inspirados em computação quântica guiam ativamente o processo de aprendizado para superar a ineficiência de amostragem.

Os autores mantêm a modéstia quanto ao escopo, observando que, embora o framework mostre promessa em GridWorld, trabalhos futuros são necessários para explorar extensões para controle contínuo, RL hierárquico e sistemas multiagentes, bem como o deployment em hardware quântico real. O presente trabalho serve como uma prova de conceito para o uso de solvers inspirados em física para otimizar a fase de seleção de dados do aprendizado por reforço.