Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

Technische Samenvatting: Sterk Polynomiale Tijdcomplexiteit van Policy Iteratie voor $L_\infty$ Robuuste MDP's

Probleemstelling
Het artikel behandelt een fundamenteel openstaand probleem in sequentiële besluitvorming onder onzekerheid: het bestaan van sterk polynomiale tijdalgoritmen voor Robuuste Markov Beslissingsprocessen (RMDP's) met $L_\infty$ onzekerheidssets en een vaste kortingsfactor. Terwijl klassieke MDP's beschikken over sterk polynomiale algoritmen voor exacte waardecomputatie (Ye, 2011), en polynomiale tijdalgoritmen bestaan voor RMDP's via lineaire programmering, bleef de vraag of RMDP's sterk polynomiale algoritmen toelaten (waarbij het aantal rekenkundige operaties onafhankelijk is van de bit-lengte van de inputcoëfficiënten) onopgelost. Specifiek faalden eerdere pogingen om $(s, a)$-rechthoekige RMDP's te reduceren naar turn-based stochastische spellen door het falen van polynomiale reducties vanwege het exponentiële aantal acties dat vereist is om $L_\infty$ onzekerheidspolytoop te representeren.

Model en Definities
De auteurs richten zich op $(s, a)$-rechthoekige RMDP's met $L_\infty$ onzekerheidssets.

• $(s, a)$-rechthoekigheid: De omgeving selecteert transitie-waarschijnlijkheden onafhankelijk voor elk staat-actie paar, waardoor een dynamisch programmeerstructuur behouden blijft.
• $L_\infty$ Onzekerheid: Voor elk staat-actie paar $(s, a)$ ligt de ware transitievector binnen een $L_\infty$-bal met straal $\delta_{s,a}$ rond een nominale schatting $\hat{P}_{s,a}$.
• Doelstelling: De agent streeft ernaar een beleid $\sigma$ te vinden dat de slechtst denkbare verwachte gedisconteerde kosten minimaliseert tegen een adversariële omgeving-beleid $\tau$.
• Sterk Polynomiaal Tijd: Een algoritme is sterk polynomiaal als het aantal rekenkundige operaties begrensd is door een polynoom in het aantal variabelen en restricties, en de grootte van de getallen tijdens de berekening polynomiaal is in de inputgrootte, onafhankelijk van de numerieke waarden van de coëfficiënten.

Methodologie
Het artikel analyseert het Robuuste Policy Iteratie (PI) algoritme, dat afwisselt tussen Policy Evaluatie en Policy Improvement.

1. Robuuste Markov Ketens (RMC's): De auteurs analyseren eerst het eenvoudigere geval waarbij de agent één actie per staat heeft (RMC-PI).

   • Policy Improvement: In plaats van een Lineair Programma (LP) op te lossen dat afhankelijk is van bit-precisie, maken de auteurs gebruik van een Homotopie Algoritme (Behzadian et al., 2021) om de optimale omgeving-respons te berekenen. Dit algoritme draait in $O(n \log n)$ en produceert beleidsregels met een specifieke structurele eigenschap: de transitie-waarschijnlijkheden worden aangepast door massa te verplaatsen van "donor"-staten naar "ontvanger"-staten totdat grenzen (0, 1, of de onzekerheidsstraal) worden geraakt.
   • Potentiaalfunctie: Een nieuwe potentiaalfunctie $f_\tau(s, s', s'')$ wordt geïntroduceerd om de overdracht van waarschijnlijkheidsmassa bij de homotopie-algoritme bij te houden. Deze functie meet de potentiële verbetering in waarde door massa te verschuiven van een staat met een lagere optimale waarde naar een staat met een hogere optimale waarde.
   • Combinatorische Grenzen: De auteurs bewijzen dat de "discrepantie" tussen de huidige beleids-transitie-waarschijnlijkheden en de optimale waarschijnlijkheden geometrisch afneemt. Cruciaal is dat zij een combinatorisch lemma (Lemma 8) vaststellen met betrekking tot het aantal verschillende Meest Significante Bits (MSB's) in gesigneerde deelsommen van reële getallen. Dit lemma, afgeleid van een algemener theorem (Theorem 20/21), begrenst het aantal mogelijke MSB's door $O(|X| \log |X|)$.
   • Convergentie-argument: Door de geometrische contractie van de waarde-fout (Lemma 2) te combineren met het eindige aantal mogelijke MSB's voor de discrepantie (Lemma 8), tonen de auteurs aan dat het algoritme niet oneindig lang steeds kleinere updates kan blijven maken. De MSB van de discrepantie moet een polynomiaal aantal keren veranderen.

2. Robuuste MDP's (RMDP's): De analyse wordt uitgebreid naar het algemene RMDP-geval (RMDP-PI).

   • Het algoritme lost iteratief het RMC subprobleem op voor het huidige agent-beleid om de slechtst denkbare omgeving-respons te vinden, en werkt vervolgens het agent-beleid bij om de resulterende kosten te minimaliseren.
   • Een vergelijkbare potentiaalfunctie wordt gedefinieerd voor acties, waarbij de kosten van het afwijken van de optimale agent-actie worden bijgehouden.
   • Dezelfde logica is van toepassing: de actie met de maximale potentiaal kan niet langer dan een logaritmisch aantal iteraties voortbestaan voordat de contractie van de waarde-fout een verandering afdwingt.

Belangrijkste Bijdragen en Resultaten

• Sterk Polynomiaale RMC-PI: De auteurs bewijzen dat Robuuste Policy Iteratie voor RMC's met $n$ staten en een constante kortingsfactor $\gamma$ termineert in $O(n^4 \log n \cdot \frac{\log((1-\gamma)/n^2)}{\log \gamma})$ iteraties. Aangezien elke iteratie bestaat uit polynomiale tijd operaties (matrixinversie en homotopie-stappen), is de totale looptijd sterk polynomiaal.
• Sterk Polynomiaale RMDP-PI: Het resultaat wordt gegeneraliseerd naar RMDP's met $n$ staten en $m$ acties. Het algoritme termineert in $O(n \cdot m \cdot \frac{\log(1-\gamma)}{\log \gamma})$ iteraties, wat vaststelt dat RMDP-PI ook sterk polynomiaal is.
• Combinatorisch Lemma: Het artikel introduceert Lemma 8, een nieuw combinatorisch resultaat dat het aantal verschillende MSB's in gesigneerde deelsommen begrenst, wat centraal staat in het complexiteitsbewijs. De auteurs merken op dat een sterkere versie van dit theorem onafhankelijk is afgeleid door een AI-onderzoekagent (Aletheia), wat een bijdrage van AI aan de wiskunde benadrukt.

Betekenis en Claims
Het artikel beweert een belangrijk openstaand probleem in de theorie van robuuste optimalisatie te hebben opgelost. Door aan te tonen dat een robuust policy iteratie algoritme in sterk polynomiale tijd draait voor $(s, a)$-rechthoekige $L_\infty$ RMDP's, generaliseren de auteurs het baanbrekende resultaat van Ye (2011) voor klassieke MDP's naar de robuuste setting. Dit resultaat is significant omdat:

1. Het een theoretische garantie biedt voor het berekenen van exacte waarden (in plaats van benaderingen) voor RMDP's zonder afhankelijkheid van de bit-lengte van inputparameters.
2. Het de beperkingen van vorige reductietechnieken overwint die faalden door een exponentiële opblazing in het aantal acties.
3. Het vaststelt dat de robuuste Bellman-operator, ondanks de oneindige onzekerheidsset, efficiënt genavigeerd kan worden met behulp van de combinatorische eigenschappen van het homotopie-algoritme.

De auteurs concluderen dat hoewel de theoretische fundamenten nu zijn gelegd, toekomstig werk empirische studies naar data-gedreven onzekerheidssets zou kunnen verkennen en of deze potentiaal-gebaseerde argumenten kunnen leiden tot verbeterde praktische varianten of stopcriteria. Ze merken ook op dat de vraag naar polynomiale grenzen voor standaard MDP policy iteratie varianten open blijft.