Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity

Technische Samenvatting: Beloningsherverdeling voor CVaR MDP's met een Bellman-operator op L-infinity

Probleemstelling
In veiligheidskritische toepassingen is het optimaliseren van de verwachte opbrengst (risiconeutraal) vaak onvoldoende, omdat dit zeldzame maar catastrofale uitkomsten kan toestaan. Statische Conditional Value-at-Risk (CVaR) is een coherente risicomaatstaf die wordt gebruikt om de onderste staart van de return-distributie te beheersen. Echter, in tegenstelling tot risiconeutrale doelstellingen, mist de statische CVaR van een return geen recursieve scheidbaarheid over de nominale toestandsruimte, wat een standaard Markoviaanse Bellman-decompositie verhindert.

Bestaande benaderingen, met name die van Bäurle & Ott (2011), pakken dit aan door de toestandsruimte uit te breiden met een continue "budget"-variabele die de cumulatieve beloningen bijhoudt. Hoewel theoretisch solide, lijdt deze formulering onder twee kritieke praktische beperkingen:

1. Sparse Rewards (IJle Beloningen): De voor CVaR relevante informatie is volledig geconcentreerd in een terminale functional van de uitgebreide toestand. Dit resulteert in nul per-stap beloningen in de uitgebreide Markov Decision Process (MDP), wat leidt tot vertraagde feedback die uitdagingen bij exploratie en temporele credit assignment verergert, met name in oneindige horizon-instellingen.
2. Beperkte Convergentie: De Bellman-operator geassocieerd met de formulering van Bäurle & Ott is alleen gegarandeerd een contractie op een zeer beperkte verzameling onbegrensde functies. Op de meer praktische ruimte van begrensde functies ($L^\infty$), staat de operator een degeneratieve vaste waarde toe (de nul-functie), waardoor standaard value iteration en Q-learning ontoepasbaar zijn zonder zorgvuldige, vaak onhaalbare initialisatievoorwaarden.

Methodologie
De auteurs stellen een nieuwe herformulering voor van de statische CVaR-doelstelling die deze beperkingen oplost door middel van een algebraïsche transformatie van de waardefunctie.

1. Getransformeerde Uitgebreide MDP: Bouwend op de toestandsuitbreiding van Bäurle & Ott (2011), definiëren de auteurs een nieuwe waardefunctie $\bar{v}^*(s, z)$ die een verschuivingsterm $z^-$ (het negatieve deel van het budget) incorporeert. Deze transformatie maakt de afleiding van een nieuwe Bellman-operator mogelijk, $\bar{T}$, gedefinieerd op de ruimte van begrensde functies $L^\infty(\bar{S})$.
2. Beloningsherverdeling: De kerninnovatie is de definitie van een nieuwe per-stap beloningsfunctie $\tilde{r}(s, z, a) = z^- - (r(s, a) + z)^-$. In tegenstelling tot de vorige formulering, die nul tussenliggende beloningen opleverde, is deze nieuwe beloning dicht en informatief bij elke stap, waardoor de voor CVaR relevante signalen effectief over de trajectorie worden herverdeeld.
3. Contractie-eigenschappen: De auteurs bewijzen dat de nieuwe operator $\bar{T}$ een $\gamma$-contractie is met betrekking tot de sup-norm op de volledige ruimte van begrensde functies. Dit zorgt ervoor dat value iteration convergeert naar een unieke vaste waarde zonder de restrictieve initialisatievoorwaarden van eerder werk te vereisen.
4. Discretisatie en Approximatie: Omdat de uitgebreide toestand $z$ continu is, gebruiken de auteurs een uniforme discretisatieschema. Ze definiëren onder- en bovengrens-operatoren ($\bar{T}^l$ en $\bar{T}^u$) met behulp van envelop-functies om de ware operator te benaderen. Ze stellen theoretische grenzen vast die aantonen dat de fout tussen de optimale CVaR en de gediscretiseerde benadering evenredig schaalt met de granulariteit van de discretisatie en de kortingsfactor.
5. Algoritmen: Op basis van dit framework ontwikkelen zij:
   • Statische CVaR Value Iteration: Een model-gebaseerd algoritme dat de optimale Q-functie voor alle initiële toestanden en budgetniveaus simultaan berekent.
   • Statische CVaR Q-Learning: Een model-vrij algoritme dat gebruikmaakt van een block-update strategie. Door gebruik te maken van de deterministische aard van de uitgebreide toestandsovergang, herlabelt het algoritme een enkel traject om Q-waarden voor meerdere initiële budgethypothesen bij te werken, wat de efficiëntie van gegevensgebruik verbetert. Convergentie wordt bewezen onder de standaard Robbins-Monro stapgroottecondities.

Belangrijkste Bijdragen

• Nieuwe Bellman-operator: Het artikel introduceert een Bellman-operator voor oneindige-horizon statische CVaR die opereert op een uitgebreide toestandsruimte, exact is ten opzichte van de controle-doelstelling, niet-ijle per-stap beloningen biedt, en een contractie-mapping is op begrensde functies.
• Approximatiegaranties: De auteurs bieden rigoureuze benaderingsfoutgrenzen voor gediscretiseerde statische CVaR, waarbij de prestatiekloof als functie van de roosterresolutie wordt gekwantificeerd.
• Convergentiebewijzen: Het artikel stelt voldoende voorwaarden vast voor de convergentie van het voorgestelde Q-learning algoritme naar de optimale actie-waardefunctie in de gediscretiseerde uitgebreide ruimte.
• Globale Optimaliteit: De algoritmen leveren globaal optimale oplossingen voor alle risiconiveaus (initiële uitgebreide toestanden) in een enkele run, in plaats van dat er aparte training nodig is voor elk risicoparameter.

Empirische Resultaten
De auteurs valideren hun aanpak in een stochastische gridworld-omgeving ("Crater Walk") waar een agent moet navigeren van een startpunt naar een doel terwijl een krater (hoge straf) wordt vermeden en brandstofverbruik (stap-straf) wordt geminimaliseerd.

• Risicosensitiviteit: De geleerde beleidsregels passen het gedrag succesvol aan op basis van de risicoparameter $\alpha$. Naarmate $\alpha$ afneemt (toenemende risico-aversie), krimpt de onderste staart van de return-distributie en vermijdt de agent de krater vaker, zelfs als dit een langer pad vereist.
• Prestaties: Zowel de Value Iteration als de Q-learning algoritmen bereiken een effectieve balans tussen prestaties en veiligheid. Het Q-learning algoritme convergeert binnen 50.000 trainingsiteraties.
• Discretisatie-nauwkeurigheid: Experimenten waarbij de discretisatieresolutie wordt gevarieerd (van 100 tot 5000 bins) tonen aan dat de prestatiecurves van de onder- en bovengrens-operatoren convergeren naar de ware optimale waarde naarmate de resolutie toeneemt, wat de theoretische foutgrenzen empirisch valideert.

Betekenis en Claims
Het artikel claimt dat de beperkingen van ijle beloningen en restrictieve convergentiegaranties in statische CVaR MDP's niet inherent zijn aan het probleem zelf, maar een artefact zijn van specifieke modelleringskeuzes in eerdere literatuur. Door een exacte herformulering voor te stellen die beloningen herverdeelt en opereert op begrensde functies, stellen de auteurs standaard dynamische programmering en model-vrije reinforcement learning technieken beschikbaar voor statische risicosensitieve problemen. Dit werk legt de basis voor schaalbare, risico-averse RL-algoritmen die niet vertrouwen op heuristische beloningsbeperking of gespecialiseerde risico-curricula. De auteurs merken op dat hoewel hun empirische analyse zich richt op tabular settings, het theoretische framework toekomstige uitbreidingen naar functiebenadering (bijv. diepe neurale netwerken) ondersteunt om continue toestandsruimten te behandelen zonder restricties op het teken van de beloning.