Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

Sintesi Tecnica: Apprendimento per Rinforzo con Preferenze a Coppie in Problemi Decisionali a Lungo Termine

Definizione del Problema
L'apprendimento per rinforzo (RL) tradizionale formula gli obiettivi come la massimizzazione del valore atteso di una funzione di ricompensa scalare all'interno di un Processo Decisionale di Markov (MDP). Tuttavia, in molte applicazioni, come l'affinamento (fine-tuning) di grandi modelli linguistici (LLM), definire preferenze a coppie (ad esempio, "la traiettoria A è migliore della traiettoria B") è spesso più naturale e fattibile rispetto alla definizione di una ricompensa scalare. I metodi esistenti per l'RL con preferenze a coppie, che inferiscono una funzione di ricompensa o ottimizzano direttamente le preferenze, soffrono tipicamente di due critiche limitazioni:

1. Si basano su orizzonti temporali finiti e fissi, il che è impraticabile per problemi decisionali a lungo termine dove gli agenti non terminano a un passo prestabilito.
2. Mancano di garanzie teoriche che le politiche di Markov stazionarie siano ottimali rispetto alle politiche dipendenti dalla storia, un pilico fondamentale della teoria standard degli MDP.

Inoltre, gli approcci standard spesso non riescono a catturare le preferenze non transitive (ad esempio, il paradosso di Condorcet), in cui l'aggregazione delle preferenze di un gruppo o una valutazione multi-caratteristica non forma un ordinamento transitivo.

Metodologia: Markov Decision Contests (MDC)
Gli autori propongono un nuovo modello di problema chiamato Markov Decision Contest (MDC) per colmare queste lacune. Un MDC è definito da un ambiente finito $(S, A, P, \mu)$ e da un margine di preferenza di Markov $M: (S \times A) \times (S \times A) \to \mathbb{R}$. L'obiettivo è trovare una politica $\pi$ che massimizzi il margine di preferenza medio contro qualsiasi altra politica $\pi'$, formulato come un gioco a somma zero:
$$\max_{\pi} \min_{\pi'} \sum_{s,a} \sum_{s',a'} x_\pi(s,a) x_{\pi'}(s',a') M((s,a), (s',a'))$$
dove $x_\pi$ rappresenta la frequenza media degli stati-azione limite (misura di occupazione).

Per garantire la trattabilità teorica in contesti a orizzonte infinito, gli autori assumono che la funzione di probabilità di transizione sia unichain e aperiodica. Sotto queste condizioni, stabiliscono che l'insieme delle misure di occupazione per le politiche dipendenti dalla storia è equivalente all'involucro convesso delle misure di occupazione per le politiche deterministiche stazionarie.

Contributi Chiave

1. Ottimalità delle Politiche Stazionarie: Il documento dimostra che, all'interno dei MDC unichain finiti, una politica stazionaria randomizzata è ottimale tra tutte le politiche dipendenti dalla storia. Ciò giustifica la restrizione dello spazio di ricerca alle politiche di Markov, colmando un divario tra teoria e pratica per l'RL basato sulle preferenze.
2. Complessità Computazionale: Gli autori dimostrano che risolvere un MDC esattamente appartiene alla classe P (tempo polinomiale). Nello specifico, costruiscono un programma lineare con $|S||A| + |S| + 1$ variabili e $2|S||A| + |S| + 1$ vincoli. Questa complessità è paragonabile agli standard MDP a ricompensa media, nonostante gli MDC siano una generalizzazione stretta che supporta preferenze non transitive.
3. Hedged Policy Iteration (HPI): Viene introdotto un algoritmo iterativo approssimato, l'Hedged Policy Iteration (HPI). Esso utilizza l'algoritmo Hedge per aggiornare le regole decisionali basandosi sui "margini di valore marginali" (margini di preferenza cumulativi).
   • Convergenza: HPI converge a una politica ottimale con un tasso sublineare di $O(1/\sqrt{K})$, dove $K$ è il numero di iterazioni.
   • Scalabilità: Gli autori derivano una forma di gradiente di politica per l'HPI e un'implementazione di deep learning (Algoritmo 3) che utilizza buffer e approssimazioni della funzione di valore, rendendolo adatto ad ambienti ad alta dimensionalità.

Risultati Sperimentali
Gli autori hanno valutato HPI e una variante troncata (HPI-Clip) contro Self-Play Preference Optimization (SPPO) (Swamy et al., 2024) su 13 compiti ad alta dimensionalità con lunghi orizzonti temporali (2048 passi) utilizzando la suite Mujoco-v5.

• Configurazione: I compiti includevano problemi standard di controllo continuo (dove le preferenze derivavano dalle differenze di ricompensa) e compiti "Mujoco-NT" caratterizzati da margini di preferenza esplicitamente non transitivi (ad esempio, regole del tipo "il migliore di tre").
• Prestazioni: In 12 dei 13 compiti, HPI e HPI-Clip hanno dimostrato un'efficienza di apprendimento significativamente superiore (misurata come l'Area Sotto la Curva del ritorno episodico o l'inverso del gap di ottimalità) rispetto a SPPO.
• Ablazione: I risultati sono rimasti validi anche quando i modelli di preferenza venivano appresi da dati offline.

Significato e Rivendicazioni
Il documento afferma che l'apprendimento per rinforzo con preferenze a coppie in problemi decisionali a lungo termine è più trattabile di quanto precedentemente ipotizzato. Introducendo il modello MDC, gli autori forniscono un quadro in cui:

• Le politiche stazionarie sono teoricamente sufficienti, eliminando la necessità di complesse strategie dipendenti dalla storia.
• Il problema rimane computazionalmente efficiente (in P), anche con preferenze non transitive.
• Algoritmi pratici (HPI) scalano a problemi ad alta dimensionalità e lungo orizzonte, superando i metodi allo stato dell'arte esistenti.

Gli autori osservano che, sebbene questi risultati siano promettenti per applicazioni come gli LLM in compiti a lungo orizzonte, è necessaria un'ulteriore investigazione per determinare quando l'apprendimento del margine di preferenza superi l'apprendimento basato sulla ricompensa e quanto efficacemente questi metodi possano allineare i modelli linguistici nella pratica. Il lavoro mira a far convergere la teoria e la pratica dell'RL con preferenze a coppie.