Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actions

Resumo Técnico: Política de Fluxo Esférico Latente para Aprendizado por Reforço com Ações Combinatórias

1. Definição do Problema

O artigo aborda o desafio de aplicar Aprendizado por Reforço (RL) em ambientes com espaços de ação combinatórios. Nesses cenários, as ações são decisões estruturadas (ex: seleção de subconjuntos, roteamento, escalonamento) governadas por restrições de viabilidade rígidas. O conjunto viável de ações, $\mathcal{A}(s)$, tipicamente cresce exponencialmente com o tamanho do problema, tornando a parametrização direta da política sobre todas as ações válidas intratável.

As abordagens existentes enfrentam um compromisso (trade-off):

• Otimização de valor baseada em solver: Incorpora redes de valor em Programas Inteiros Mistos (MIPs) para extrair ações gananciosas (greedy). Isso frequentemente exige arquiteturas de valor específicas e escala mal com a complexidade da rede.
• Camadas de decisão induzidas por otimização: Aprende políticas estruturadas de ponta a ponta, mas tipicamente gera políticas determinísticas, limitando a expressividade e a exploração em paisagens complexas.

Embora modelos generativos modernos (difusão e baseados em fluxo) tenham demonstrado sucesso em controle contínuo ao representar distribuições estocásticas multimodais ricas, eles não podem ser aplicados diretamente ao RL combinatório porque não impõem inerentemente restrições de viabilidade discretas. A adaptação ingênua leva a ações inviáveis.

2. Metodologia: LSFLOW

Os autores propõem o LSFLOW (Política de Fluxo Esférico Latente), um framework que desacopla a expressividade da política da imposição de viabilidade. A ideia central é aprender uma política estocástica em um espaço latente contínuo compacto e delegar a viabilidade a um solver de otimização combinatória (CO).

A. Política de Fluxo Esférico Induzida por Solver

• Representação Latente: Em vez de produzir ações diretamente, a política aprende uma distribuição sobre vetores de custo $\mathbf{c} \in \mathbb{R}^m$.
• Mapeamento do Solver: Um solver de CO mapeia um vetor de custo amostrado para uma ação viável via um objetivo linear: $\mathbf{a}^*(s, \mathbf{c}) = \arg\min_{\mathbf{a} \in \mathcal{A}(s)} \mathbf{c}^\top \mathbf{a}$.
• Restrição Esférica: Devido à invariância de escala positiva do solver (a ação ótima depende apenas da direção de $\mathbf{c}$, não de sua magnitude), o espaço latente é restrito à esfera unitária $\mathbb{S}^{m-1}$.
• Modelo Generativo: A política $\pi_\theta(\mathbf{c} | s)$ é modelada usando correspondência de fluxo esférico (spherical flow matching). Ela aprende um campo vetorial dependente do tempo na esfera para transportar uma distribuição base para uma distribuição alvo de direções de custo. Isso permite que a política represente qualquer distribuição estocástica sobre ações viáveis sem enumerá-las explicitamente.

B. Treinamento Eficiente no Espaço Latente
Para evitar o gargalo computacional de chamar o solver de CO repetidamente durante as atualizações da política, o LSFLOW treina tanto o ator quanto o crítico diretamente no espaço de custo latente.

• Crítico: Uma rede de valor $\tilde{Q}_\phi(s, \mathbf{c})$ é treinada para aproximar $Q(s, \mathbf{a}^*(s, \mathbf{c}))$. Isso amortiza os custos do solver, exigindo apenas uma chamada de solver por passo do ambiente, em vez de por cada proposta de política.
• Atualização da Política: A política é atualizada usando um objetivo de correspondência de fluxo esférico ponderado. As propostas são reponderadas com base no valor estimado pelo crítico, deslocando a distribuição para direções de custo que resultam em ações viáveis de maior valor.

C. Operador de Bellman Suavizado
Um desafio crítico é que o mapeamento de direção de custo para ação é constante por partes e descontínuo (devido ao solver), levando a uma aprendizagem de valor instável.

• Suavização vMF: Os autores introduzem um kernel von Mises–Fisher (vMF) para suavizar o operador de Bellman. Em vez de avaliar o valor em uma única direção $\mathbf{ c}$, o alvo é computado pela média sobre uma vizinhança de direções amostradas do kernel vMF.
• Garantias Teóricas: Os autores provam que este operador suavizado é um mapeamento de contração com um ponto fixo único que é infinitamente diferenciável ($C^\infty$) em relação à direção do custo. Isso garante uma aprendizagem de alvos estável e de baixa variância. Eles demonstram ainda que, conforme o parâmetro de concentração do kernel $\kappa \to \infty$, o valor suavizado converge para a verdadeira função de valor quase em toda parte.

3. Principais Contribuições

1. Primeiro Framework de Fluxo/Difusão para RL Combinatório: O LSFLOW é o primeiro framework de política que transfere a expressividade dos modelos generativos baseados em fluxo para espaços de ação combinatórios enquanto garante a viabilidade via um solver.
2. Otimização Eficiente no Espaço Latente: O método introduz um paradigma de treinamento onde tanto o ator quanto o crítico operam no espaço de custo latente, evitando chamadas repetidas ao solver durante a otimização.
3. Aprendizagem Estabilizada via Suavização: O artigo propõe um operador de Bellman suavizado usando kernels vMF para mitigar a instabilidade causada pelas descontinuidades induzidas pelo solver, fornecendo provas teóricas de contração e suavidade.

4. Resultados Experimentais

Os autores avaliam o LSFLOW em benchmarks públicos e uma aplicação do mundo real:

• Benchmarks Públicos: Testado em quatro tarefas dinâmicas (Escalonamento, Roteamento, Atribuição, Intervenção) de Xu et al. (2025). O LSFLOW superou as linhas de base de última geração (incluindo SEQUOIA e SRL) em uma média de 20,6% em recompensa.
• Aplicação no Mundo Real: Aplicado a uma tarefa de testagem de Infecções Sexualmente Transmissíveis (IST) envolvendo triagem baseada em rede para Gonorreia, HIV, Sífilis e Clamídia. O LSFLOW demonstrou maior eficiência de detecção (fração de casos positivos encontrados) comparado às linhas de base, particularmente em regimes de orçamento baixo a médio.
• Eficiência: O LSFLOW foi aproximadamente 3,0× mais rápido no tempo de treinamento do que a linha de base de RL Estruturado (SRL) determinística, pois evita a diferenciação através do solver ou a resolução de MIPs incorporados durante o treinamento.

5. Significância e Alegações

O artigo afirma que o LSFLOW oferece um caminho fundamentado e escalável para RL com ações combinatórias. Ao transferir o fardo da viabilidade para um solver e aprender uma política estocástica expressiva em um espaço esférico latente, o método supera as limitações de abordagens anteriores que sacrificam ou a generalidade (métodos baseados em solver) ou a expressividade (métodos determinísticos).

Os autores enfatizam que sua abordagem transfere com sucesso os benefícios das políticas generativas modernas (multimodalidade, exploração rica) para domínios restritos. Eles reconhecem limitações, observando que a suavização introduz um compromisso entre viés e variância e que a inferência ainda requer chamadas de solver, sugerindo trabalhos futuros sobre suavização adaptativa e orientação aprendida para reduzir ainda mais o tempo de execução.