Learning Kernel-Based MDPs from Episodic Preferential Feedback

Technische Samenvatting: Leren van Kernel-gebaseerde MDP's uit Epische Preferentiële Feedback

Probleemformulering
Dit werk adresseert het probleem van Reinforcement Learning uit Menselijke Feedback (RLHF) binnen de setting van epische Markov Beslissingsprocessen (MDP's). In tegenstelling tot standaard RL, waar agenten scalare beloningen ontvangen, ontvangt de leerling hier uitsluitend binaire preferentiële feedback. In elke episode $k$ implementeert de leerling twee beleidsplannen, $\pi$ en $\pi'$, vanuit een gemeenschappelijke starttoestand om twee trajecten, $\tau_k$ en $\tau'_k$, te genereren. De feedback bestaat uit een enkel binair label $y_k \in \{0, 1\}$ dat aangeeft welk traject de voorkeur heeft. Deze voorkeur wordt gemodelleerd via een Bradley–Terry–Luce (BTL) linkfunctie toegepast op het verschil van cumulatieve (niet-geobserveerde) beloningen:
$$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)$$
waarbij $\sigma$ de sigmoidfunctie is. Het doel is om een beleidsplan te leren dat de waardenfunctie $V^\pi_1$ maximaliseert, terwijl de cumulatieve regret wordt geminimaliseerd, gedefinieerd als het verschil tussen de optimale waarde en de gemiddelde waarde van de geïmplementeerde beleidsplannen.

De setting veronderstelt een Kernel MDP-structuur, waarbij de beloningsfunctie $r_h$ en de overgangsoperator $P_h$ elementen zijn van een Reproducing Kernel Hilbert Ruimte (RKHS) $\mathcal{H}_k$ geïnduceerd door een bekende kernel $k$. Specifiek focussen de auteurs op de Matérn-kernelfamilie, die niet-lineaire structuren vastlegt en norm-equivalent is aan Sobolev-ruimten, waardoor een generalisatie wordt geboden die verder gaat dan lineaire MDP's.

Methodologie: PROSTO-algoritme
De auteurs stellen PROSTO voor (Preference based Regularized Optimization via Sampled Trajectory induced Optimism). Het algoritme werkt in episodes en maakt gebruik van een waarde-iteratiebenadering die is aangepast voor preferentiële feedback en kernel-functieapproximatie.

1. Beloningschatting via Geregulariseerde Kernel Logistische Regressie (KLRR):
   Aangezien feedback op trajectniveau en binair is, wordt de beloningsvector $\theta$ geschat via maximum likelihood-schatting met een op normen gebaseerde straf. De schatter $\hat{\theta}_k$ minimaliseert de negatieve log-likelihood van de waargenomen voorkeuren plus een regularisatieterm $\tau \|\theta\|^2_{\mathcal{H}_k}$. De covariaten voor deze regressie zijn de trajectverschil-kenmerken $\phi_i = \sum_{h=1}^H \phi(z^i_h) - \phi(z'^i_h)$.

2. Exploratie via Geredrandomiseerde GP-storing:
   Om voldoende exploratie op trajectniveau te garanderen zonder de overgangsdynamica vooraf te kennen (wat deterministische elliptische bonussen verhindert), hanteert PROSTO geredrandomiseerde exploratie. Een exploratieruisvector $\epsilon_k$ wordt getrokken uit een Gaussisch Proces (GP) met een covariantiestructuur die afhankelijk is van de empirische covariantie van trajectverschillen. Deze ruis wordt toegevoegd aan de beloningschatting om optimisme te induceren.

3. Waardenfunctieschatting via Kernel Ridge Regressie (KRR):
   De waardenfunctie wordt recursief geschat. De verwachte waarde van de volgende toestand wordt benaderd met standaard kernel ridge regressie op overgangssteekproeven. De uiteindelijke Q-functieschatting $\hat{Q}^k_h$ combineert de beloningschatting (KLRR + GP-ruis) en de overgangsschatting (KRR), onderworpen aan clipping om begrensdheid te waarborgen.

4. Beleidsuitvoering:
   De leerling selecteert twee beleidsplannen, $\pi$ en $\pi'$, die gulzig zijn ten opzichte van hun respectieve optimistische Q-functieschattingen. Deze beleidsplannen worden uitgevoerd om de trajecten en preferentiële feedback van de volgende episode te genereren.

Belangrijkste Technische Bijdragen en Uitdagingen
Het artikel identificeert drie primaire technische uitdagingen specifiek voor het combineren van kernel-MDP's met preferentiële feedback op trajectniveau en biedt nieuwe oplossingen:

• Beheersen van Log-Coveringgetallen: In kernel-MDP's schaalt het log-coveringgetal van de klasse van waardenfuncties polynomiaal met het omgekeerde van het coveringsnet $\epsilon$ en hangt het af van de RKHS-normen van de schatters. In tegenstelling tot lineaire MDP's, waar coveringgetallen logaritmisch zijn in het aantal episodes, kunnen kernel-instellingen leiden tot regretgrenzen die leeg zijn als de normen van de schatters te groot worden.

  • Oplossing: De auteurs stemmen de regularisatieparameter $\tau$ in de KLRR zorgvuldig af om de RKHS-norm van de beloningschatter expliciet te beheersen. Dit houdt het coveringgetal van de geïnduceerde functieklassen klein, waardoor zinvolle betrouwbaarheidsintervallen mogelijk worden.

• Exploratie op Trajectniveau met Niet-Gladde Ruis: Standaard exploratiebonussen (elliptische bonussen) vereisen kennis van het volledige traject, wat op het beslismoment niet beschikbaar is. Geredrandomiseerde exploratie via GP-steekproeven wordt gebruikt, maar GP-steekproefpaden van een Matérn-kernel behoren doorgaans niet tot de bijbehorende RKHS (ze zijn minder glad). Dit maakt standaard coveringgrenzen ontoepasbaar.

  • Oplossing: De auteurs leiden nieuwe hoogstwaarschijnlijke Gaussische coveringgrenzen af voor de posterior GP-steekproefpaden. Ze maken gebruik van resultaten van van der Vaart en van Zanten [2008] om aan te tonen dat, hoewel GP-paden buiten de RKHS-bal liggen, ze met hoge waarschijnlijkheid binnen een $\epsilon$-omgeving (in $\ell_\infty$-norm) van een passend vergrote RKHS-bal liggen. Dit maakt het mogelijk om de voor de regretanalyse noodzakelijke coveringgrenzen af te leiden.

• Balanceren van Regularisatie- en Coveringparameters: Het afstemmen van de regularisatieparameters ($\tau$ voor beloning, $\lambda$ voor overgang) en het coveringsnet $\epsilon$ is niet triviaal. Een klein $\epsilon$ vermindert de specificatiefout maar blaast het coveringgetal op; een groot $\epsilon$ doet het tegenovergestelde.

  • Oplossing: De auteurs optimaliseren $\tau$, $\lambda$ en $\epsilon$ gezamenlijk als functies van het aantal episodes $K$ en de kernegladheidsparameter $\beta_p$. Deze balans zorgt ervoor dat de betrouwbaarheidsbreedtes strak genoeg blijven voor sublineaire regret, terwijl de complexiteit van de functieklassen wordt beheerst.

Resultaten en Regretgrenzen
Het artikel bewijst dat PROSTO een sublineaire cumulatieve regretgrens bereikt voor alle kernels in de Matérn-familie. Specifiek schaalt de regret $R(K)$ als:
$$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)$$
waarbij $\beta_p > 1$ de eigenwaarde-afnameparameter van de kernel is, $H$ de horizon is, en $\kappa_Z$ de maximale inverse linkgradient is. De exponent van $K$ is strikt kleiner dan 1, wat convergentie naar het optimale beleidsplan impliceert naarmate $K \to \infty$.

Bovendien is het algoritme rekenkundig efficiënt, met een looptijd die polynomiaal is in het aantal episodes $K. Dit onderscheidt het van eerdere werken over kernel-MDP's met standaard beloningen (bijv. Maran et al. [2024b]), die hoewel ze sublineaire regret bereiken, vertrouwen op domeinpartitionering of optimalisatie-orakels waarvan niet bekend is dat ze in polynomiale tijd uitvoerbaar zijn voor algemene kernel-instellingen.

Betekenis en Claims
De auteurs claimen dat dit werk het eerste algoritme biedt voor preferentiegebaseerd RL in kernel-MDP's dat bewezen sublineaire regret bereikt voor de gehele Matérn-kernelfamilie, terwijl het rekenkundig efficiënt is.

• Theoretische Nieuwheid: Het werk overbrugt de kloof tussen preferentiegebaseerd RL (dat doorgaans tabulaire of lineaire settings behandelt) en kernel-gebaseerde functiebenadering (die niet-lineaire settings behandelt). Het introduceert nieuwe technieken voor het hanteren van het gebrek aan gladheid in GP-exploratieruis binnen de context van waarde-iteratie.
• Rekenkundige Efficiëntie: In tegenstelling tot eerdere no-regret-algoritmen voor gladde MDP's die mogelijk onuitvoerbare optimalisatie vereisen, biedt PROSTO een implementatie in polynomiale tijd.
• Beperkingen: De auteurs erkennen dat de regretgrens mogelijk niet orde-optimaal is. Ze merken op dat benaderingen met domeinpartitionering, die momenteel orde-optimale grenzen bieden in sommige kernel-instellingen, incompatibel zijn met feedback op trajectniveau vanwege de stochasticiteit van overgangen die lokale Bellman-operator-schatting verhindert.

Het artikel concludeert dat, hoewel de afgeleide regretgrens sublineair is, het bereiken van een orde-optimale grens een open vraag blijft, wat waarschijnlijk fundamenteel verschillende technieken vereist dan huidige domeinpartitionering of uniforme coveringsmethoden.