Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actions

Sintesi Tecnica: Politica di Flusso Sferico Latente per il Reinforcement Learning con Azioni Combinatorie

1. Definizione del Problema

Il documento affronta la sfida di applicare il Reinforcement Learning (RL) ad ambienti con spazi di azione combinatori. In questi contesti, le azioni sono decisioni strutturate (ad es. selezione di sottoinsiemi, routing, scheduling) governate da vincoli di fattibilità rigidi. L'insieme delle azioni ammissibili, $\mathcal{A}(s)$, tipicamente cresce esponenzialmente con la dimensione del problema, rendendo intrattabile la parametrizzazione diretta della politica su tutte le azioni valide.

Gli approcci esistenti affrontano un compromesso:

• Ottimizzazione del valore basata su solver: Incorpora reti di valore all'interno di Programmi Lineari Interi Misti (MIP) per estrarre azioni greedy. Ciò richiede spesso architetture di valore specifiche e scala scarsamente con la complessità della rete.
• Livelli decisionali indotti dall'ottimizzazione: Apprende politiche strutturate end-to-end ma tipicamente produce politiche deterministiche, limitando l'espressività e l'esplorazione in paesaggi complessi.

Sebbene i modelli generativi moderni (diffusion e flow-based) abbiano mostrato successo nel controllo continuo rappresentando distribuzioni stocastiche ricche e multimodali, non possono essere applicati direttamente al RL combinatorio perché non impongono intrinsecamente vincoli di fattibilità discreti. L'adattamento ingenuo porta ad azioni non ammissibili.

2. Metodologia: LSFLOW

Gli autori propongono LSFLOW (Latent Spherical Flow Policy), un framework che scinde l'espressività della politica dall'imposizione della fattibilità. L'idea centrale è quella di apprendere una politica stocastica in uno spazio latente continuo compatto e delegare la fattibilità a un solver di ottimizzazione combinatoria (CO).

A. Politica di Flusso Sferico Indotta dal Solver

• Rappresentazione Latente: Inveve di produrre direttamente le azioni, la politica apprende una distribuzione su vettori di costo $\mathbf{c} \in \mathbb{R}^m$.
• Mappatura del Solver: Un solver CO mappa un vettore di costo campionato in un'azione ammissibile tramite un obiettivo lineare: $\mathbf{a}^*(s, \mathbf{c}) = \arg\min_{\mathbf{a} \in \mathcal{A}(s)} \mathbf{c}^\top \mathbf{a}$.
• Vincolo Sferico: A causa dell'invarianza di scala positiva del solver (l'azione ottimale dipende solo dalla direzione di $\mathbf{c}$, non dalla sua magnitudo), lo spazio latente è ristretto alla sfera unitaria $\mathbb{S}^{m-1}$.
• Modello Generativo: La politica $\pi_\theta(\mathbf{c} | s)$ è modellata utilizzando il flusso sferico (spherical flow matching). Essa apprende un campo vettoriale dipendente dal tempo sulla sfera per trasportare una distribuzione di base verso una distribuzione target di direzioni di costo. Ciò consente alla politica di rappresentare qualsiasi distribuzione stocastica su azioni ammissibili senza enumerarle esplicitamente.

B. Addestramento Efficiente nello Spazio Latente
Per evitare l'ostacolo computazionale di chiamare ripetutamente il solver CO durante gli aggiornamenti della politica, LSFLOW addestra sia l'attore che il critico direttamente nello spazio dei costi latenti.

• Critico: Una rete di valore $\tilde{Q}_\phi(s, \mathbf{c})$ è addestrata per approssimare $Q(s, \mathbf{a}^*(s, \mathbf{c}))$. Questo ammortizza i costi del solver, richiedendo solo una chiamata al solver per ogni passo dell'ambiente invece di una per ogni proposta di politica.
• Aggiornamento della Politica: La politica viene aggiornata utilizzando un obiettivo di flow-matching sferico pesato. Le proposte vengono ricalibrate in base al valore stimato dal critico, spostando la distribuzione verso direzioni di costo che producono azioni ammissibili di valore superiore.

C. Operatore di Bellman Smussato
Una sfida critica è che la mappatura dalla direzione del costo all'azione è a tratti costante e discontinua (a causa del solver), portando a un apprendimento del valore instabile.

• Smoothing vMF: Gli autori introducono un kernel von Mises–Fisher (vMF) per smussare l'operatore di Bellman. Invece di valutare il valore in una singola direzione $\mathbf{c}$, l'obiettivo è calcolato mediando su un vicinato di direzioni campionate dal kernel vMF.
• Garanzie Teoriche: Gli autori dimostrano che questo operatore smussato è una mappatura di contrazione con un punto fisso unico che è infinitamente differenziabile ($C^\infty$) rispetto alla direzione del costo. Ciò garantisce obiettivi di apprendimento stabili e a bassa varianza. Dimostrano inoltre che, al tendere il parametro di concentrazione del kernel $\kappa \to \infty$, il valore smussato converge alla vera funzione di valore quasi ovunque.

3. Contributi Chiave

1. Primo Framework Flow/Diffusion per il RL Combinatorio: LSFLOW è il primo framework di politica che trasferisce l'espressività dei modelli generativi basati su flow allo spazio di azione combinatorio garantendo la fattibilità tramite un solver.
2. Ottimizzazione Efficiente nello Spazio Latente: Il metodo introduce un paradigma di addestramento in cui sia l'attore che il critico operano nello spazio dei costi latenti, evitando ripetute chiamate al solver durante l'ottimizzazione.
3. Apprendimento Stabilizzato tramite Smoothing: Il documento propone un operatore di Bellman smussato utilizzando kernel vMF per mitigare l'instabilità causata dalle discontinuità indotte dal solver, fornendo prove teoriche di contrazione e regolarità (smoothness).

4. Risultati Sperimentali

Gli autori valutano LSFLOW su benchmark pubblici e un'applicazione del mondo reale:

• Benchmark Pubblici: Testato su quattro compiti dinamici (Scheduling, Routing, Assignment, Intervention) di Xu et al. (2025). LSFLOW ha superato i baseline allo stato dell'arte (inclusi SEQUOIA e SRL) con una media del 20,6% in termini di reward.
• Applicazione nel Mondo Reale: Applicato a un compito di test per Infezioni Sessualmente Trasmesse (IST) che coinvolge lo screening basato sulla rete per Gonorrea, HIV, Sifilide e Clamidia. LSFLOW ha dimostrato un'efficienza di rilevamento superiore (frazione di casi positivi trovati) rispetto ai baseline, particolarmente nei regimi di budget medio-bassi.
• Efficienza: LSFLOW è stato circa 3,0 volte più veloce nel tempo di addestramento rispetto al baseline di Structured RL (SRL) deterministico, poiché evita la differenziazione attraverso il solver o la risoluzione di MIP incorporati durante l'addestramento.

5. Significato e Rivendicazioni

Il documento afferma che LSFLOW offre una via principesca e scalabile al RL con azioni combinatorie. Spostando l'onere della fattibilità sul solver e apprendendo una politica stocastica espressiva in uno spazio sferico latente, il metodo supera i limiti degli approcci precedenti che sacrificano o la generalità (metodi basati su solver) o l'espressività (metodi deterministici).

Gli autori sottolineano che il loro approccio trasferisce con successo i benefici delle moderne politiche generative (multimodalità, esplorazione ricca) a domini vincolati. Riconoscono i limiti, notando che lo smoothing introduce un compromesso bias-varianza e che l'inferenza richiede ancora chiamate al solver, suggerendo lavori futuri su smoothing adattivo e guida appresa per ridurre ulteriormente i tempi di esecuzione.