On Reward-Balancing Methods for Reinforcement Learning

Titel: Over Beloning-Balancerende Methoden voor Versterkend Leren (Reinforcement Learning)

Auteurs: Simone Baroncini, Bahman Gharesifard, en Giuseppe Notarstefano

1. Probleemstelling

Traditionele algoritmen voor Versterkend Leren (RL) binnen het kader van Markov Beslissingsprocessen (MDP's) werken door een beleid (policy) iteratief te verbeteren terwijl de beloningsfunctie ($r$) constant blijft. Het doel is om een beleid te vinden dat de verwachte afgepaste totale beloning (discounted return) maximaliseert.

Het paper introduceert een alternatieve benadering: Reward-Balancing. In plaats van het beleid aan te passen aan een vaste beloning, wordt de beloningsfunctie zelf iteratief aangepast. Het doel is om de MDP te "normaliseren" tot een equivalente MDP waarbij het optimale beleid gierig (greedy) is ten opzichte van de huidige beloningsfunctie. In een "normale" MDP is de optimale waardefunctie overal nul, wat betekent dat het voldoende is om in elke staat de actie met de hoogste (nul) beloning te kiezen.

De uitdaging ligt in het vinden van transformaties die het oorspronkelijke probleem niet veranderen (d.w.z. het behouden van de optimale beleidsset), maar het probleem wel vereenvoudigen. Een specifiek probleem dat wordt aangepakt is hoe dit proces robuust kan worden uitgevoerd wanneer het exacte model van de MDP (overgangskansen) onbekend is en slechts via stochastische steekproeven (sampling) benaderd kan worden.

2. Methodologie

De auteurs hanteren een multidisciplinaire aanpak die wiskundige groepstheorie, meetkunde (vezelbundels), en optimalisatie-theorie combineert.

A. Wiskundige Grondslagen en Groepstheorie

• Advantage-Behoudende Transformaties: De auteurs analyseren een specifieke groep van transformaties op de ruimte van beloningsfuncties. Deze transformaties worden geparametriseerd door een functie $\delta$ op de toestanden en worden gedefinieerd als:
  $$r_{new} = r + b(\delta)$$
  waarbij $b(\delta)$ een lineaire operator is die afhankelijk is van de overgangskansen en de afkorting $\gamma$.
• Behoud van de "Advantage": Een cruciale eigenschap is dat deze transformaties de advantage-functie ($adv_{\pi,r}$) behouden. Dit garandeert dat de relatieve rangschikking van acties binnen een beleid niet verandert; het optimale beleid blijft dus hetzelfde, hoewel de absolute waarden van de beloningen veranderen.
• Normalisatie: Er wordt aangetoond dat elke MDP binnen een "orbit" van deze transformaties een unieke "normale" vorm heeft, waarbij de maximale beloning in elke staat gelijk is aan 0. Het vinden van dit normale punt is equivalent aan het vinden van de optimale waardefunctie van de originele MDP.
• Meetkundige Structuur: De ruimte van beloningsfuncties wordt geanalyseerd als een principale bundel (principal bundle). De "basis" is de verzameling van normale beloningsfuncties, en de "vezels" zijn de orbits van de transformaties. Dit biedt een meetkundig inzicht in hoe normalisatie werkt.

B. Control-Theoretische Reformulatie

Het paper herformuleert het normalisatieproces als een optimalisatieprobleem voor lineaire tijd-invariante systemen:

• Systeem: De beloningsvector $R_t$ is de toestand, en de transformatie $\Delta_t$ is de besturing (input).
• Dynamica: $R_{t+1} = R_t + B\Delta_t$, waarbij $B$ een matrix is afgeleid van de overgangskansen.
• Doel: Ontwerpen van een feedback-wet $\Delta_t = h(R_t)$ die het systeem stabiliseert naar de "normale set" (waarbij de output $h_{max}(R_t) = \max_{u \in U_x} r(u)$ naar 0 convergeert).
• Besturingswetten: Er worden verschillende wetten geanalyseerd:
  1. Ideale feedback: Vereist kennis van de optimale waardefunctie (onpraktisch).
  2. Full-Output Feedback: Gebruikt de huidige maximale beloning als input (equivalent aan Value Iteration).
  3. Safe Reward-Balancing: Een niet-lineaire wet die garandeert dat de beloning negatief blijft.

C. Omgaan met Modelonzekerheid (Stochastische Setting)

Voor het geval het model onbekend is, wordt een Scenario Model Predictive Control (MPC) benadering voorgesteld:

• In plaats van één model te gebruiken, worden $N$ scenario's (steekproeven van het overgangsmodel) gegenereerd.
• Een optimalisatieprobleem wordt opgelost om een besturing te vinden die de gemiddelde cumulatieve beloning minimaliseert over deze scenario's, onder de beperking dat de beloning voor elk scenario negatief blijft (robustheid).
• Dit leidt tot een model-invariant toegestane set van besturingen, wat garandeert dat de normalisatie convergent blijft ongeacht de specifieke steekproefrealisatie.

3. Belangrijkste Bijdragen

1. Theoretische Analyse van Transformaties: Een grondige wiskundige karakterisering van de groep van beloningstransformaties. De auteurs bewijzen dat deze transformaties een vrije actie hebben op de ruimte van beloningsfuncties en dat elke orbit precies één normale MDP bevat.
2. Control-Theoretisch Kader: De eerste reformulatie van reward-balancing als een output-stabilisatieprobleem en een optimaal besturingsprobleem. Dit opent de deur voor het gebruik van geavanceerde controle-theorie (zoals MPC) om nieuwe, betere algoritmen te ontwerpen.
3. Robuustheid en Stochastische Analyse:
   • Het definiëren van de grootste model-invariant toegestane set ($F_I(R)$) die werkt voor elk mogelijk model.
   • Het afleiden van probabilistische grenzen (concentratie-ongelijkheden) voor de afwijking tussen de stochastische update en de ideale update. Dit bewijst dat de methode stabiel blijft onder modelruis.
4. Scenario MPC Implementatie: Het voorstellen van een scenario-based MPC strategie die de prestaties verbetert ten opzichte van bestaande methoden (zoals de volledige output-feedback uit eerdere werken) in onzekere omgevingen.

4. Resultaten

• Simulaties: De auteurs voeren simulaties uit op een MDP met twee toestanden en vijf acties per staat.
• Vergelijking: Ze vergelijken de voorgestelde Scenario MPC methode met de "Full-Output Feedback" methode (een bestaande state-of-the-art methode uit referentie [6]).
• Prestaties:
  • Beide methoden bereiken normalisatie (de beloning convergeert naar 0).
  • De Scenario MPC levert een significant hoger percentage "optimale gierige beleidsstrategieën" op na normalisatie, vooral wanneer het aantal scenario's toeneemt.
  • De gemiddelde beleidsstrategie onder Scenario MPC nadert sneller de ware optimale deterministische strategie dan bij de traditionele methode.
• Trade-off: De paper erkent dat Scenario MPC rekenkundig duurder is dan de simpele feedback-methode, maar toont aan dat de verbetering in kwaliteit van het gevonden beleid de moeite waard kan zijn in kritieke toepassingen.

5. Betekenis en Conclusie

Dit paper is significant omdat het een brug slaat tussen versterkend leren en optimalisatie-theorie/control engineering.

• Het biedt een nieuwe theoretische lens om RL-problemen te bekijken: niet als het leren van een beleid, maar als het "normaliseren" van het probleem via beloningstransformaties.
• Het lost een praktisch probleem op: hoe RL-methoden robuust te maken tegen modelonzekerheid zonder de garanties van optimaliteit te verliezen.
• Door het gebruik van Model Predictive Control (MPC) en stochastische analyse, biedt het een systematisch raamwerk voor het ontwerpen van nieuwe RL-algoritmen die beter presteren dan huidige state-of-the-art methoden, zelfs in onzekere omgevingen.

Kortom, de auteurs tonen aan dat het actief aanpassen van de beloningsfunctie (in plaats van alleen het beleid) een krachtige en wiskundig onderbouwde route is naar efficiënter en robuuster versterkend leren.