Multi-Environment POMDPs with Finite-Horizon Objectives

Technische Samenvatting: Multi-Environment POMDPs met eindhorizont-doelstellingen

Probleemstelling
Dit werk behandelt het probleem van het berekenen van optimale waarden en beleidslijnen in Multi-Environment Partially Observable Markov Decision Processes (MEPOMDPs) met eindhorizont-doelstellingen. In een standaard Partially Observable MDP (POMDP) interacteert een agent met een stochastische omgeving en ontvangt slechts gedeeltelijke staat-informatie. Een MEPOMDP breidt dit uit door aan te nemen dat de beginstaat onbekend is en op een adversarische manier wordt gekozen uit een verzameling van $n$ mogelijke beginstaten $\{s_1, \dots, s_n\}$. De agent moet een enkel beleid berekenen dat de minimale verwachte beloning over alle mogelijke beginomgevingen maximaliseert. Het doel is om de som van beloningen over een eindige horizon $k$ te maximaliseren.

Het artikel richt zich op twee computationele problemen:

1. Het Waardeprobleem: Het berekenen van de optimale waarde $v = \sup_{\sigma} \min_{i \in [n]} E^k_{s_i}(\sigma)$.
2. Het Drempelprobleem: Het bepalen of $v \ge \lambda$ voor een gegeven rationele drempel $\lambda$.

Een kritieke theoretische nuance die wordt geïdentificeerd, is dat MEPOMDPs, in tegenstelling tot standaard POMDPs waar deterministische beleidslijnen volstaan voor optimaliteit, over het algemeen gerandomiseerde beleidslijnen vereisen om de optimale waarde te bereiken, aangezien deterministische strategieën kunnen falen om de constraint voor de worst-case beginstaat te voldoen.

Methodologie en Algoritmen
De auteurs ontwikkelen zowel theoretische complexiteitsgrenzen als praktische algoritmen om deze problemen op te lossen.

• Complexiteitsanalyse: Het artikel stelt vast dat het drempelprobleem en zijn benaderingsversie PSPACE-volledig zijn. De ondergrens is geërfd van de bekende PSPACE-hardheid van standaard POMDPs (waarbij $n=1$). De bovengrens wordt bewezen via een niet-deterministisch algoritme dat gebruikmaakt van de stelling van Carathéodory. Deze stelling impliceert dat als er een beleid bestaat dat een bepaalde waarde bereikt over $n$ omgevingen, er een "mengsel" bestaat van maximaal $n$ deterministische beleidslijnen dat dezelfde garantie bereikt. Dit maakt het mogelijk om de zoekruimte te reduceren tot combinaties van een beperkt aantal deterministische strategieën.

• Ruimte-efficiënt deterministisch algoritme (Algoritme 2): Om de exponentiële ruimtevereisten van standaard determinisering (bijvoorbeeld via de stelling van Savitch) te vermijden, presenteren de auteurs een deterministisch algoritme dat binnen polynoomruimte werkt. In plaats van hele beleidslijnen te raden, enumereren het algoritme mogelijke waarden voor multi-verwachte uitbetalingen en verifieert het hun bereikbaarheid recursief. Het construeert partiële sommen van de Bellman-updatevergelijking en controleert of een doelwaarde kan worden ontbonden in geldige sub-strategieën. Hoewel dit theoretisch optimaal is qua ruimte ($O(|S| \cdot |O| \cdot n \cdot k \cdot \pi(N))$), merken de auteurs op dat deze aanpak computationeel onuitvoerbaar is voor de meeste praktische gevallen vanwege ingewikkelde lussen.

• Praktisch tijd-efficiënt algoritme (Algoritme 3): Voor empirische evaluatie stellen de auteurs een bottom-up-algoritme voor dat de verzameling van bereikbare multi-verwachte uitbetalingen voor toenemende horizons berekent. Deze methode onderhoudt een verzameling van niet-gedomineerde uitbetalingsvectoren (de "frontier"). In elke stap worden vectoren die convex worden gedomineerd door anderen geschrapt, aangezien deze overeenkomen met beleidsfamilie die geen verdere exploratie behoeven. Hoewel dit algoritme in het slechtste geval exponentiële ruimte kan gebruiken, is het ontworpen voor schaalbaarheid in de praktijk.

Belangrijkste Bijdragen

1. Complexiteitsclassificatie: Het artikel bewijst dat het berekenen van waarden in MEPOMDPs met eindige horizons PSPACE-volledig is, wat overeenkomt met de complexiteit van standaard POMDPs ondanks de toegevoegde adversarische beginstaatsconstraint.
2. Theoretisch Inzicht: Het toont aan dat optimale beleidslijnen in MEPOMDPs kunnen worden weergegeven als mengsels van maximaal $n$ deterministische beleidslijnen, waarbij $n$ het aantal beginomgevingen is.
3. Algoritmische Vooruitgang:
   • Een deterministisch, polynoomruimte-algoritme (Algoritme 2) dat een theoretische bovengrens voor ruimtecomplexiteit biedt.
   • Een praktisch, tijd-efficiënt algoritme (Algoritme 3) dat gebruikmaakt van het afschermen van gedomineerde uitbetalingsvectoren.
4. Empirische Validatie: Het praktische algoritme wordt geëvalueerd tegenover het enige eerder bekende exacte algoritme (van Bovy et al. [1]) op drie benchmarksets: Rock Sample, Robot Navigation en Identification (Friend or Foe).

Resultaten
Experimentele resultaten geven aan dat het voorgestelde praktische algoritme (Algoritme 3) significant beter presteert dan de state-of-the-art tool uit [1].

• Prestaties: De nieuwe methode lost instanties op met tot 574 staten en horizons tot $k=7$ binnen redelijke tijdsbestekken, terwijl de baseline-tool vaak time-outt (limiet van 3600s) op veel kleinere instanties.
• Schaalbaarheid: De rekentijd schaalt sterk met de horizon $k$, wat wordt geïdentificeerd als de primaire bottleneck voor schaalbaarheid. Het aantal staten en beginomgevingen heeft een minder dominante invloed op de runtime vergeleken met de horizon.
• Vergelijking: In de Rock Sample-benchmarks lost de voorgestelde methode instanties op waar de baseline time-outt, vaak met snelheidswinsten van meerdere ordes van grootte (bijvoorbeeld het oplossen van een instantie met 574 staten in ~784 seconden versus een time-out voor de baseline).

Betekenis en Beperkingen
Het artikel claimt betekenis door de eerste strakke complexiteitsgrenzen voor MEPOMDPs te bieden en een praktisch algoritme aan te bieden dat bestaande tools aanzienlijk verbetert. De auteurs erkennen een standaard afweging tussen theoretische en praktische prestaties: het ruimte-efficiënte algoritme (Algoritme 2) is theoretisch onderbouwd maar praktisch traag, terwijl het tijd-efficiënte algoritme (Algoritme 3) snel is in de praktijk maar in het slechtste geval geen polynoomruimte-garantie heeft.

Het werk is beperkt tot eindhorizont-doelstellingen. De auteurs merken op dat hoewel het exacte probleem voor kortingssom-doelstellingen onbeslisbaar is voor POMDPs, hun algoritme potentieel kan worden aangepast voor benaderde kortingssom-doelstellingen door deze te reduceren tot eindhorizont-problemen, hoewel dit toekomstig werk blijft. Het artikel stelt geen nieuwe toepassingen voor buiten de standaard benchmarks die voor evaluatie zijn gebruikt.