Technische Samenvatting: Suboptimaliteitsgrenzen voor certainty equivalent policies in deels geobserveerde systemen

Probleemstelling

In veel domeinen zoals robotica, autonome systemen en de financiële sector opereren besluitvormers onder gedeeltelijke observeerbaarheid, wat wordt gemodelleerd als Partially Observable Markov Decision Processes (POMDP's). Het optimaal oplossen van POMDP's is computationeel onhandelbaar (PSPACE-hard), en het vinden van bijna optimale policies is eveneens moeilijk. Hoewel er heuristische methoden bestaan, missen deze vaak bewijsbare prestatiegaranties.

Het Certainty Equivalence (CE) principe, dat goed gevestigd is in de Linear-Quadratic-Gaussian (LQG) regeling, suggereert dat de optimale actie voor een stochastisch systeem verkregen kan worden door de optimale state-feedback policy van het bijbehorende deterministische systeem toe te passen op de Minimum Mean Square Error (MMSE) schatting van de toestand. Echter, voor algemene niet-lineaire deels geobserveerde systemen is de CE policy (gebruikmakend van een willekeurige toestandsschatting) over het algemeen niet optimaal.

Het centrale probleem dat in dit artikel wordt behandeld, is het kwantificeren van de mate van suboptimaliteit van certainty equivalent policies in algemene POMDP's. Specifiek trachten de auteurs expliciete bovengrenzen af te leiden voor het prestatieverschil tussen een CE policy en de optimale POMDP policy, met name wanneer de systeemdynamica en kosten vloeiend zijn, en wanneer de toestandsschattingfout klein is.

Methodologie

Het artikel generaliseert het CE-principe naar willekeurige POMDP's en willekeurige toestandsschatters (niet beperkt tot MMSE). De methodologie steunt op het Approximate Information State (AIS) raamwerk.

1. Systeemmodellering:

   • De auteurs beschouwen een discrete-tijd POMDP $\mathcal{P}$ met een toestandsruimte $\mathcal{S}$, observatieruimte $\mathcal{Y}$ en actieruimte $\mathcal{A}$.
   • Zij definiëren een bijbehorende volledig observeerbare Markov Decision Process (MDP) $\mathcal{M}$ waarbij de controller toegang heeft tot de ware toestand $S_t$.
   • Een Certainty Equivalent Policy $\mu^E$ wordt gedefinieerd als $\mu^E_t(h_t) = \pi^M_t(E_t(h_t))$, waarbij $\pi^M$ de optimale policy is voor de volledig observeerbare MDP $\mathcal{M}$, en $E_t$ een willekeurige toestandsschatter is die de geschiedenis $h_t$ naar een toestandsschatting brengt.

2. Toestandabstractie:

   • Om grootschalige systemen aan te kunnen, wordt het raamwerk uitgebreid naar Toestandabstractie. Een abstracte toestandsruimte $\tilde{\mathcal{S}}$ wordt geïntroduceerd via een abstractiefunctie $\phi: \mathcal{S} \to \tilde{\mathcal{S}}$.
   • Een abstracte MDP $\tilde{\mathcal{M}}$ wordt geconstrueerd met dynamica en kosten afgeleid van de oorspronkelijke MDP via stochastische kernels $\lambda^P$ en $\lambda^c$.
   • De CE policy wordt vervolgens gedefinieerd met behulp van de optimale policy van de abstracte MDP $\tilde{\mathcal{M}}$ en schattingen van de abstracte toestand.

3. Vloeiendheidsveronderstellingen:

   • De analyse gaat ervan uit dat de systeemdynamica en de kosten per stap "vloeiend" zijn in de zin van concave, niet-dalende functies $F^P_t$ en $F^c_t$.
   • Specifiek worden de Wasserstein-1 afstand tussen transitie-kernels en het verschil in kosten begrensd door deze functies van de afstand tussen toestanden (of abstracte toestanden). Dit generaliseert standaard Lipschitz-continuïteitsveronderstellingen.

4. Approximate Information State (AIS) Raamwerk:

   • De auteurs maken gebruik van het AIS-raamwerk om de suboptimaliteitskloof te begrenzen. Zij tonen aan dat de tupel bestaande uit de toestandsschatter, de abstracte kostenfunctie en de abstracte dynamica een $(\epsilon, \delta)$-AIS generator vormt.
   • De parameters $\epsilon_t$ (kostenbenaderingsfout) en $\delta_t$ (dynamische voorspellingsfout) zijn expliciet afgeleid in termen van de worst-case conditionele verwachte schattingsfout $\eta_t$.

Belangrijkste Bijdragen

Het artikel levert drie primaire bijdragen:

1. Expliciete Suboptimaliteitsgrenzen: De auteurs leiden expliciete bovengrenzen af voor de suboptimaliteit van certainty equivalent policies. Deze grenzen zijn afhankelijk van de "vloeiendheid" van het systeem (Lipschitz-constanten of gegeneraliseerde functies $F^P, F^c$) en de kwaliteit van de toestandsschatter (gemeten door de worst-case verwachte toestandsschatingsfout).

   • De grens wordt gegeven door $W^{\mathcal{P}, \mu^E}_t(h_t) - W^{\mathcal{P}}_t(h_t) \leq 2\alpha_t$, waarbij $\alpha_t$ een recursieve functie is van $\epsilon_t$ en $\delta_t$.

2. Uitbreiding naar Toestandabstractie: De resultaten worden gegeneraliseerd naar situaties waarin toestandabstractie (kwantisatie of feature extractie) wordt toegepast. Dit maakt het mogelijk het raamwerk toe te passen op grootschalige systemen waarbij de volledige toestand wordt geaggregeerd in een lager-dimensionale abstracte toestand. De grenzen houden rekening met fouten die voortkomen uit zowel het abstractieproces als de toestandsschatting.

3. Illustratieve Voorbeelden: Het artikel biedt verschillende concrete voorbeelden die de toepasbaarheid van de afgeleide grenzen demonstreren:

   • Begrensde Observatieruis: Het aantonen van een lineaire schaling van de suboptimaliteitsgrens met de ruisradius.
   • Intermitterend Gedegradeerde Observaties: Het omgaan met scenario's waarin observaties incidenteel slecht zijn.
   • Toestandskwantisatie: Het analyseren van het gecombineerde effect van kwantisatiefout en observatieruis.
   • Leren/Adaptieve Regeling: Het toepassen van de grenzen op parameterschattingproblemen waarbij de systeemparameters onbekend zijn.
   • Event-Triggered Communicatie: Het analyseren van controlesystemen waarbij communicatie alleen wordt getriggerd wanneer de schattingsfout een drempel overschrijdt.
   • Niet-homogene Multi-particle Systemen: Het toepassen van het raamwerk op systemen met een globale mean-field component en lokale deeltjesdynamica.

Resultaten

Het belangrijkste theoretische resultaat (Theorem 2) stelt vast dat indien de systeemdynamica en kosten voldoen aan specifieke vloeiendheidscondities (Assumption 5) en de schatter een begrensde worst-case fout heeft (Assumption 6), het prestatieverschil tussen de CE policy en de optimale policy begrensd is.

• Afhankelijkheid van Schattingsfout: De grenzen zijn direct proportioneel aan de schattingsfout $\eta_t$. Naarmate $\eta_t \to 0$ (perfecte schatting), verdwijnt de suboptimaliteitskloof.
• Afhankelijkheid van Vloeiendheid: De omvang van de kloof wordt geschaald door de Lipschitz-achtige constanten van de dynamica en kostenfuncties.
• Toestandabstractie: Wanneer abstracte toestanden worden gebruikt, bevat de grens termen gerelateerd aan de abstractiefout (de afstand tussen de ware toestand en de abstractie daarvan) naast de schattingsfout.

In de illustratieve voorbeelden laten de auteurs zien dat voor systemen met begrensde ruis of frequente nauwkeurige observaties, de CE policy bijna optimale prestaties levert, wat een computationeel hanteerbaar alternatief biedt voor het oplossen van de volledige POMDP.

Betekenis en Claims

Het artikel claimt een generalisatie van het certainty equivalence principe te bieden voor algemene POMDP's, waarmee het verder gaat dan de restrictieve LQG-setting. De betekenis ligt in:

• Theoretische Rechtvaardiging: Het biedt een rigoureuze theoretische basis voor het gebruik van CE policies in niet-lineaire, deels geobserveerde omgevingen, waarbij exact wordt gekwantificeerd hoe "slecht" het beleid kan zijn op basis van de kwaliteit van de schatting.
• Praktische Hanteerbaarheid: Het suggereert dat in scenario's waar exacte optimale POMDP-oplossingen computationeel onhandelbaar zijn, CE policies een praktisch alternatief bieden. Indien de toestandsschatingsfout klein is, kunnen deze policies bijna optimale prestaties leveren zonder de exponentiële complexiteit van belief-state dynamic programming.
• Verenigd Raamwerk: Door toestandabstractie te integreren, overbrugt het raamwerk de kloof tussen regeltechniek en grootschalig systeemontwerp, waardoor de analyse van gekwantiseerde of feature-gebaseerde controlesystemen mogelijk wordt.

De auteurs merken expliciet op dat hun analyse steunt op het AIS-raamwerk en de aannames van vloeiendheid. Zij beweren niet dat CE policies optimaal zijn voor alle modellen (zij merken in Remark 3 op dat CE policies kunnen falen in modellen waar actieve sensing vereist is om de toestand te leren). De resultaten worden gepresenteerd als grenzen die de mate van suboptimaliteit karakteriseren, in plaats van garanties van optimaliteit.