Learning Kernel-Based MDPs from Episodic Preferential Feedback

Riepilogo Tecnico: Apprendimento di MDP Basati su Kernel da Feedback Preferenziale Episodico

Formulazione del Problema
Questo lavoro affronta il problema dell'Apprendimento per Rinforzo da Feedback Umano (RLHF) nel contesto dei Processi Decisionali di Markov (MDP) episodici. A differenza dell'RL standard, in cui gli agenti ricevono ricompense scalari, qui l'apprenditore riceve solo feedback preferenziale binario. In ogni episodio $k$, l'apprenditore dispiega due politiche, $\pi$ e $\pi'$, da uno stato di partenza comune per generare due traiettorie, $\tau_k$ e $\tau'_k$. Il feedback consiste in un'unica etichetta binaria $y_k \in \{0, 1\}$ che indica quale traiettoria è preferita. Questa preferenza è modellata tramite una funzione di collegamento Bradley–Terry–Luce (BTL) applicata alla differenza delle ricompense cumulative (non osservate):
$$y_k \sim \text{Ber}\left(\sigma\left(\sum_{h=1}^H r_h(z^k_h) - \sum_{h=1}^H r_h(z'^k_h)\right)\right)$$
dove $\sigma$ è la funzione sigmoide. L'obiettivo è apprendere una politica che massimizzi la funzione valore $V^\pi_1$ minimizzando al contempo il rimorso cumulativo, definito come la differenza tra il valore ottimale e il valore medio delle politiche dispiegate.

L'impostazione assume una struttura di MDP a Kernel, in cui la funzione di ricompensa $r_h$ e l'operatore di transizione $P_h$ sono elementi di uno Spazio di Hilbert a Kernel Riproduttivo (RKHS) $\mathcal{H}_k$ indotto da un kernel noto $k$. Nello specifico, gli autori si concentrano sulla famiglia di kernel Matérn, che cattura strutture non lineari ed è norm-equivalente agli spazi di Sobolev, offrendo una generalizzazione oltre gli MDP lineari.

Metodologia: Algoritmo PROSTO
Gli autori propongono PROSTO (Ottimizzazione Regularizzata Basata su Preferenze tramite Ottimismo Indotto da Traiettorie Campionate). L'algoritmo opera in episodi e utilizza un approccio di iterazione del valore adattato per il feedback preferenziale e l'approssimazione di funzioni a kernel.

1. Stima della Ricompensa tramite Regressione Logistica a Kernel Regularizzata (KLRR):
   Poiché il feedback è a livello di traiettoria e binario, il vettore di ricompensa $\theta$ è stimato utilizzando la massima verosimiglianza con una penalità pesata dalla norma. Lo stimatore $\hat{\theta}_k$ minimizza la log-verosimiglianza negativa delle preferenze osservate più un termine di regolarizzazione $\tau \|\theta\|^2_{\mathcal{H}_k}$. Le covariate per questa regressione sono le caratteristiche di differenza delle traiettorie $\phi_i = \sum_{h=1}^H \phi(z^i_h) - \phi(z'^i_h)$.

2. Esplorazione tramite Perturbazione GP Randomizzata:
   Per garantire un'adeguata esplorazione a livello di traiettoria senza conoscere a priori le dinamiche di transizione (il che impedisce bonus ellittici deterministici), PROSTO impiega un'esplorazione randomizzata. Un vettore di rumore di esplorazione $\epsilon_k$ è campionato da un Processo Gaussiano (GP) con una struttura di covarianza dipendente dalla covarianza empirica delle differenze delle traiettorie. Questo rumore viene aggiunto alla stima della ricompensa per indurre ottimismo.

3. Stima della Funzione Valore tramite Regressione Ridge a Kernel (KRR):
   La funzione valore è stimata in modo ricorsivo. Il valore atteso dello stato successivo è approssimato utilizzando la regressione ridge a kernel standard sui campioni di transizione. La stima finale della funzione Q, $\hat{Q}^k_h$, combina la stima della ricompensa (KLRR + rumore GP) e la stima della transizione (KRR), soggetta a clipping per garantire la limitatezza.

4. Esecuzione della Politica:
   L'apprenditore seleziona due politiche, $\pi$ e $\pi'$, che sono greedy rispetto alle rispettive stime ottimistiche della funzione Q. Queste politiche vengono eseguite per generare le traiettorie e il feedback preferenziale del prossimo episodio.

Contributi Tecnici Chiave e Sfide
Il documento identifica tre sfide tecniche primarie specifiche per la combinazione di MDP a kernel con feedback preferenziale a livello di traiettoria e fornisce soluzioni innovative:

• Controllo dei Numeri di Copertura Logaritmici: Negli MDP a kernel, il numero di copertura logaritmico della classe di funzioni valore scala polinomialmente con l'inverso della maglia di copertura $\epsilon$ e dipende dalle norme RKHS degli stimatori. A differenza degli MDP lineari, dove i numeri di copertura sono logaritmici nel numero di episodi, le impostazioni a kernel possono portare a limiti di rimorso vuoti se le norme degli stimatori crescono troppo.

  • Soluzione: Gli autori sintonizzano attentamente il parametro di regolarizzazione $\tau$ nella KLRR per controllare esplicitamente la norma RKHS dello stimatore della ricompensa. Ciò mantiene piccolo il numero di copertura della classe di funzioni indotta, consentendo limiti di confidenza significativi.

• Esplorazione a Livello di Traiettoria con Rumore Non Liscio: I bonus di esplorazione standard (bonus ellittici) richiedono la conoscenza dell'intera traiettoria, che non è disponibile al momento della decisione. Viene utilizzata un'esplorazione randomizzata tramite campionamento GP, ma i percorsi campionati da un GP con kernel Matérn generalmente non appartengono al corrispondente RKHS (sono meno lisci). Ciò rende inapplicabili i limiti di copertura standard.

  • Soluzione: Gli autori derivano nuovi limiti di copertura Gaussiana ad alta probabilità per i percorsi campionati posteriori del GP. Sfruttano i risultati di van der Vaart e van Zanten [2008] per dimostrare che, sebbene i percorsi GP giacciano fuori dalla sfera RKHS, giacciono entro un $\epsilon$-intorno (nella norma $\ell_\infty$) di una sfera RKHS opportunamente ampliata con alta probabilità. Ciò permette la derivazione dei limiti di copertura necessari per l'analisi del rimorso.

• Bilanciamento dei Parametri di Regularizzazione e Copertura: La sintonizzazione dei parametri di regolarizzazione ($\tau$ per la ricompensa, $\lambda$ per la transizione) e della maglia di copertura $\epsilon$ non è banale. Un $\epsilon$ piccolo riduce l'errore di specificazione ma gonfia il numero di copertura; un $\epsilon$ grande fa l'opposto.

  • Soluzione: Gli autori ottimizzano congiuntamente $\tau$, $\lambda$ ed $\epsilon$ come funzioni del numero di episodi $K$ e del parametro di regolarità del kernel $\beta_p$. Questo bilanciamento garantisce che le larghezze di confidenza rimangano sufficientemente strette per un rimorso sublineare, controllando al contempo la complessità della classe di funzioni.

Risultati e Limiti di Rimorso
Il documento dimostra che PROSTO raggiunge un limite di rimorso cumulativo sublineare per tutti i kernel della famiglia Matérn. Nello specifico, il rimorso $R(K)$ scala come:
$$R(K) \leq \tilde{O}\left( \kappa_Z \max\left( H^{2.5} K^{1 - \frac{(\beta_p-1)^2}{2\beta_p(\beta_p+1)}}, H^3 K^{1 - \frac{\beta_p-1}{2(\beta_p+1)}} \right) \right)$$
dove $\beta_p > 1$ è il parametro di decadimento degli autovalori del kernel, $H$ è l'orizzonte e $\kappa_Z$ è il massimo gradiente della funzione di collegamento inversa. L'esponente di $K$ è strettamente inferiore a 1, implicando la convergenza verso la politica ottimale quando $K \to \infty$.

Inoltre, l'algoritmo è computazionalmente efficiente, con un tempo di esecuzione polinomiale nel numero di episodi $K$. Ciò lo distingue dai lavori precedenti sugli MDP a kernel con ricompense standard (ad es. Maran et al. [2024b]) che, pur raggiungendo un rimorso sublineare, si affidano alla partizione del dominio o a oracoli di ottimizzazione che non sono noti per essere computazionalmente trattabili in tempo polinomiale per impostazioni di kernel generali.

Significato e Affermazioni
Gli autori affermano che questo lavoro fornisce il primo algoritmo per l'RL basato su preferenze in MDP a kernel che raggiunge un rimorso sublineare dimostrabile per l'intera famiglia di kernel Matérn, pur essendo computazionalmente efficiente.

• Novità Teorica: Il lavoro colma il divario tra l'RL basato su preferenze (che tipicamente gestisce impostazioni tabellari o lineari) e l'approssimazione di funzioni basata su kernel (che gestisce impostazioni non lineari). Introduce nuove tecniche per gestire la mancanza di regolarità nel rumore di esplorazione GP nel contesto dell'iterazione del valore.
• Efficienza Computazionale: A differenza dei precedenti algoritmi senza rimorso per MDP lisci che potrebbero richiedere ottimizzazioni intrattabili, PROSTO offre un'implementazione in tempo polinomiale.
• Limitazioni: Gli autori riconoscono che il limite di rimorso potrebbe non essere ottimale in ordine. Notano che gli approcci di partizione del dominio, che attualmente offrono limiti ottimali in ordine in alcune impostazioni a kernel, sono incompatibili con il feedback a livello di traiettoria a causa della stocasticità delle transizioni che impedisce la stima localizzata dell'operatore di Bellman.

Il documento conclude che, sebbene il limite di rimorso derivato sia sublineare, raggiungere un limite ottimale in ordine rimane una questione aperta, richiedendo probabilmente tecniche fondamentalmente diverse oltre le attuali metodologie di partizione del dominio o copertura uniforme.