Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

Technische Samenvatting: Reinforcement Learning met Paarwijze Voorkeuren in Langetermijn Beslissingsproblemen

Probleemdefinitie
Traditionele reinforcement learning (RL) formuleert doelen als het maximaliseren van de verwachte waarde van een scalaire beloningsfunctie binnen een Markov Beslissingsproces (MDP). Echter, in veel toepassingen, zoals het finetunen van grote taalmodellen (LLM's), is het definiëren van paarwijze voorkeuren (bijv. "traject A is beter dan traject B") vaak natuurlijker en haalbaarder dan het definiëren van een scalaire beloning. Bestaande methoden voor RL met paarwijze voorkeuren extraheren ofwel een beloningsfunctie of optimaliseren direct voor voorkeuren, maar lijden onder twee kritieke beperkingen:

1. Ze vertrouwen op eindige, vaste tijdshorizonten, wat onpraktisch is voor langetermijn beslissingsproblemen waarbij agenten niet stoppen bij een vaste stap.
2. Ze missen theoretische garanties dat stationaire Markov-policies optimaal zijn ten opzichte van geschiedenisafhankelijke policies, een hoeksteen van de standaard MDP-theorie.

Bovendien slagen standaard benaderingen er vaak niet in om niet-transitieve voorkeuren (bijv. de Condorcet-paradox) te vatten, waarbij de geaggregeerde voorkeur van een groep of een evaluatie met meerdere kenmerken geen transitieve ordening vormt.

Methodologie: Markov Decision Contests (MDC's)
De auteurs stellen een nieuw probleemmodel voor, de Markov Decision Contest (MDC), om deze hiaten te overbruggen. Een MDC wordt gedefinieerd door een eindige omgeving $(S, A, P, \mu)$ en een Markov-voorkeursmarge $M: (S \times A) \times (S \times A) \to \mathbb{R}$. Het doel is om een policy $\pi$ te vinden die de gemiddelde voorkeursmarge maximaliseert tegen elke andere policy $\pi'$, geformuleerd als een zero-sum spel:
$$\max_{\pi} \min_{\pi'} \sum_{s,a} \sum_{s',a'} x_\pi(s,a) x_{\pi'}(s',a') M((s,a), (s',a'))$$
waarbij $x_\pi$ de limiterende gemiddelde staat-actie frequentie (occupancy measure) vertegenwoordigt.

Om theoretische verwerkbaarheid in oneindige horizon-settings te garanderen, nemen de auteurs aan dat de transitiekansfunctie unichain en aperiodiek is. Onder deze voorwaarden stellen zij vast dat de verzameling occupancy measures voor geschiedenisafhankelijke policies gelijk is aan de convexe hull van de occupancy measures voor stationaire deterministische policies.

Belangrijkste Bijdragen

1. Optimaliteit van Stationaire Policies: Het artikel bewijst dat binnen eindige unichain MDCs, een stationaire gerandomiseerde policy optimaal is onder alle geschiedenisafhankelijke policies. Dit rechtvaardigt het beperken van de zoekruimte tot Markov-policies, wat de kloof tussen theorie en praktijk voor voorkeursgebaseerde RL overbrugt.
2. Computationele Complexiteit: De auteurs demonstreren dat het exact oplossen van een MDC in P zit (polynomiale tijd). Specifiek construeren zij een lineair programma met $|S||A| + |S| + 1$ variabelen en $2|S||A| + |S| + 1$ restricties. Deze complexiteit is vergelijkbaar met standaard gemiddelde-belonings MDP's, ondanks het feit dat MDCs een striktere generalisatie zijn die niet-transitieve voorkeuren ondersteunt.
3. Hedged Policy Iteration (HPI): Een benaderend iteratief algoritme, Hedged Policy Iteration (HPI), wordt geïntroduceerd. Het maakt gebruik van het Hedge-algoritme om beslissingsregels bij te werken op basis van "marginale waarden" (cumulatieve voorkeursmarges).
   • Convergentie: HPI convergeert naar een optimale policy met een sublineaire snelheid van $O(1/\sqrt{K})$, waarbij $K$ het aantal iteraties is.
   • Schaalbaarheid: De auteurs afleiden een policy-gradient vorm van HPI en een deep learning implementatie (Algoritme 3) die gebruikmaakt van buffers en waarde-functie benaderingen, waardoor het geschikt is voor hoogdimensionele omgevingen.

Experimentele Resultaten
De auteurs evalueerden HPI en een geclipte variant (HPI-Clip) tegenover Self-Play Preference Optimization (SPPO) (Swamy et al., 2024) over 13 hoogdimensionele taken met lange tijdshorizonten (2048 stappen) met behulp van de Mujoco-v5 suite.

• Setup: De taken bevatten standaard continue controleproblemen (waar voorkeuren werden afgeleid van verschil in beloning) en "Mujoco-NT" taken die expliciet niet-transitieve voorkeursmarges bevatten (bijv. best-two-out-of-three regels).
• Prestaties: In 12 van de 13 taken vertoonden HPI en HPI-Clip een significant hogere leer-efficiëntie (gemeten aan de hand van de Area Under the Curve van de episodische return of de geïnverteerde optimaliteitskloof) vergeleken met SPPO.
• Ablatie: De resultaten bleven standhouden wanneer voorkeursmodellen werden geleerd van offline data.

Betekenis en Claims
Het artikel claimt dat reinforcement learning met paarwijze voorkeuren in langetermijn beslissingsproblemen minder complex is dan voorheen gedacht. Door de introductie van het MDC-model bieden de auteurs een raamwerk waarin:

• Stationaire policies theoretisch voldoende zijn, wat de noodzaak voor complexe geschiedenisafhankelijke strategieën wegneemt.
• Het probleem computationeel efficiënt blijft (in P), zelfs met niet-transitieve voorkeuren.
• Praktische algoritmen (HPI) schalen naar hoogdimensionele, langdurige problemen en superieur presteren aan bestaande state-of-the-art methoden.

De auteurs merken op dat hoewel deze resultaten veelbelovend zijn voor toepassingen zoals LLM's in langetermijn taken, verder onderzoek vereist is om te bepalen wanneer het leren van voorkeursmarges de voordelen van beloningsgebaseerd leren overtreft en hoe effectief deze methoden taalmodellen in de praktijk uitlijnen. Het werk beoogt de theorie en praktijk van paarwijze voorkeurs-RL dichter bij elkaar te brengen.