Technische Samenvatting: Q-Learning onder de Gemiddelde Kosten-criteria voor Continue MDP's

1. Probleemformulering

Dit artikel behandelt de uitdaging van het oplossen van Markov-beslissingsprocessen (MDP's) met continue toestands- en actieruimtes onder het oneindig-horizon gemiddelde kosten-criterium. Het model wordt gedefinieerd door een tupel $(X, U, \mathcal{T}, c)$, waarbij $X$ en $U$ standaard Borel-ruimtes zijn (volledige, scheidbare metriekruimtes), $\mathcal{T}$ de transitie-kernel is, en $c$ de kostenfunctie is. Het doel is om een beleid $\pi$ te vinden dat de langetermijn gemiddelde kosten minimaliseert:
$$J^*(x) := \inf_{\pi} \limsup_{T \to \infty} \frac{1}{T} \mathbb{E}^\pi_x \left[ \sum_{t=0}^{T-1} c(x_t, u_t) \right]$$

De auteurs benadrukken dat hoewel eindige-horizon en gedisconteerde kostenproblemen voor continue ruimtes goed bestudeerd zijn met behulp van contractie-eigenschappen van Bellman-operatoren, problemen met gemiddelde kosten unieke moeilijkheden met zich meebrengen. Specifiek verwijdert het gebrek aan een discontfactor de directe contractie-eigenschap, wat alternatieve stabiliteits- en ergodischheidsaannames vereist. Bovendien richt de bestaande literatuur over reinforcement learning (RL) voor gemiddelde kosten zich grotendeels op eindige ruimtes of legt zij restrictieve structurele aannames op (bijv. lineaire dynamica, Lipschitz-beleid) die de toepasbaarheid op algemene continue ruimtes beperken.

2. Methodologie

Het artikel hanteert een tweeledige aanpak: eindige benadering via kwantisatie en reinforcement learning-algoritmen ontworpen voor deze benaderingen.

2.1 Discretisatie en Benadering

De kernmethodologie behelst het construeren van een eindige-toestand, eindige-actie benaderend MDP door de continue ruimtes te kwantiseren.

• Toestandskwantisatie: De toestandsruimte $X$ wordt verdeeld in disjuncte bins $\{B_i\}_{i=1}^M$ met representatieve toestanden $y_i$. Een afbeelding $q: X \to Y$ (waarbij $Y$ de eindige verzameling van representatieve toestanden is) wordt gedefinieerd.
• Actiekwantisatie: De actieruimte $U$ wordt benaderd door een eindige verzameling $\Lambda$.
• Constructie van het benaderde model: Het benaderde model $(\hat{X}, \hat{U}, \hat{\mathcal{T}}, \hat{c})$ wordt gedefinieerd met behruik van een gewichtsmaat $\mu$ (vaak de invariante maat van het toestandsproces). De benaderde kosten- en transitie-kernels zijn gemiddelden van de oorspronkelijke functies over de kwantisatie-bins:
  $$\hat{c}(y_i, u) = \int_{B_i} c(z, u) \mu_{y_i}(dz), \quad \hat{\mathcal{T}}(A|y_i, u) = \int_{B_i} \mathcal{T}(A|z, u) \mu_{y_i}(dz)$$
• Verzwakte continuïteitscondities: Een significante methodologische verschuiving is de verzwakking van de Total Variation (TV) continuïteitsconditie, die standaard is in de voorafgaande benaderingsliteratuur (bijv. Saldi et al., 2018). De auteurs vestigen benaderingsresultaten onder:
  1. Zwakke Continuïteit (Feller): Voldoende voor asymptotische convergentie van fouten naarmate de roostergroottes verdwijnen.
  2. Wasserstein Continuïteit: Voldoende voor het vaststellen van expliciete convergentiesnelheden (foutgrenzen) naarmate de roostergroottes verdwijnen.

2.2 Reinforcement Learning Algoritmen

Het artikel stelt Gekwantiseerde Q-Learning algoritmen voor om het optimale beleid voor het benaderde model direct uit data te leren.

• Synchroon Algoritme (Algoritme 1): Updateert Q-waarden voor alle toestand-actie paren in het eindige rooster simultaan. Het vertrouwt op het samplen van toestanden uit elke bin volgens een vooraf bepaalde maat.
• Asynchroon Algoritme (Algoritme 2): Updateert Q-waarden op basis van een enkele traject van het oorspronkelijke continue proces. Dit is praktischer maar introduceert een niet-Markoviaanse ruisterm omdat het gekwantiseerde proces $q(X_t)$ geen Markov-keten is (het is een deels observeerbaar MDP vanuit het perspectief van de gekwantiseerde toestand).
• Convergentiemechanisme: Om de gemiddelde kosten-criteria en het gebrek aan begrenzing in Q-iteraten (in tegen tegenstelling tot gedisconteerde gevallen) te behandelen, maken de auteurs gebruik van:
  • Span Semi-normen voor synchrone updates.
  • Ergodischheidsaannames: Het exploratiebeleid moet een unieke invariante maat induceren met volledige ondersteuning over de gekwantiseerde bins.
  • Verschoven Updates: Het asynchrone algoritme trekt een referentiewaarde af (gebaseerd op een specifieke bin) om de iteratie te stabiliseren, waarbij het gekwantiseerde proces als een POMDP wordt behandeld.

3. Belangrijkste Bijdragen

Het artikel levert drie primaire bijdragen en daarmee een vooruitgang in de stand van de techniek voor continue-ruimte gemiddelde kosten-controle:

1. Benaderingstheorie met Zwakkere Condities:

   • De auteurs bieden foutgrenzen voor eindige benaderingen onder zwakke continuïteit en Wasserstein continuïteit, waarmee de strikte Total Variation continuïteit die vereist is door eerdere werken (bijv. Saldi et evenals 2018), wordt versoepeld.
   • Zij stellen vast dat onder Wasserstein continuïteit (met een contractieconstante $K_T < 1$), de fout in de optimale gemiddelde kosten afneemt met een snelheid die proportioneel is aan de kwantisatiefout (specifiek $L_X^\delta$).
   • Onder zwakke continuïteit alleen bewijzen zij de asymptotische convergentie van de kosten van het benaderde beleid naar de optimale kosten naarmate de discretisatie fijner wordt.

2. Convergentie van Gekwantiseerde Q-Learning:

   • Het artikel vestigt de bijna zekere (almost sure) convergentie van zowel synchrone als asynchrone Q-learning algoritmen voor continue ruimtes.
   • Cruciaal is dat zij bewijzen dat deze algoritmen convergeren naar de optimale Q-waarden van het geconstrueerde eindige benaderde model, en niet enkel naar het oorspronkelijke continue model. Dit onderscheid is essentieel omdat het gekwantiseerde proces niet strikt Markoviaans is.
   • De analyse generaliseert eerdere resultaten (bijv. Kara en Yüksel, 2023) van gedisconteerde kosten naar het meer uitdagende gemiddelde kosten-criterium, wat nieuwe technische analyses vereist om ongebegrensde Q-iteraten te behandelen.

3. Nabij-optimaliteitsgaranties:

   • Door de benaderingsfoutgrenzen te combineren met de convergentie van de learning-algoritmen, demonstreert het artikel dat de via gekwantiseerde Q-learning geleerde beleidssystemen nabij-optimaal zijn voor de oorspronkelijke continue MDP's.
   • Het prestatieverlies is expliciet begrensd in termen van de kwantisatie-resolutie en de Lipschitz-constanten van de kosten- en transitie-kernels.

4. Belangrijke Resultaten en Stellingen

• Stelling 1 & 2 (Benaderingsgrenzen): Vestigen bovengrens op het verschil tussen de optimale gemiddelde kosten van het oorspronkelijke model ($\rho$) en het benaderde model ($\hat{\rho}$).
  • Onder Wasserstein continuïteit: $|\rho - \hat{\rho}| \leq C \cdot (L_X)^\delta$, waarbij $L_X$ de kwantisatiefout is.
  • Onder zwakke continuïteit: $\lim_{n \to \infty} \rho(\pi_n) = \rho$.
• Stelling 5 & 6 (Algoritme Convergentie): Bewijzen dat de synchrone en asynchrone Q-learning iteraties convergeren naar de optimale Q-waarden van het eindige benaderde model. De asynchrone convergentie berust op de ergodischheid van het toestandsproces onder het exploratiebeleid.
• Corollary 1: Combineert de benaderings- en learning-resultaten om aan te tonen dat het geleerde beleid $\hat{\pi}$ voldoet aan $\rho(\hat{\pi}) - \rho \leq \epsilon$, waarbij $\epsilon$ verdwijnt naarmate de discretisatie-roostergrootte naar nul nadert.

5. Betekenis en Claims

De auteurs positioneren dit werk als een oplossing voor openstaande problemen in de literatuur betreffende reinforcement learning voor gemiddelde kosten-MDP's met continue ruimtes.

• Versoepeling van Aannames: Het artikel claimt een significante theoretische vooruitgang door af te stappen van Total Variation continuïteit, die vaak te restrictief is voor praktische modellen, en over te gaan naar Zwakke en Wasserstein continuïteit. Dit verbredt de klasse van systemen (bijv. die met additieve ruis of specifieke dynamica) waarvoor theoretische garanties kunnen worden geboden.
• Brug tussen Theorie en Praktijk: Door te bewijzen dat Q-learning convergeert naar de oplossing van een goed gedefinieerde eindige benadering, biedt het artikel een rigoureuze rechtvaardiging voor het gebruik van discretisatie-gebaseerde RL in continue gemiddelde kosten-settings. Het verheldert dat de "nabij-optimaliteit" een direct gevolg is van de kwaliteit van de benadering, en niet een artefact van het learning-algoritme zelf.
• Afhandeling van Niet-Markoviaanse Kwantisatie: Het artikel adresseert expliciet de technische moeilijkheid dat het gekwantiseerde toestandsproces een POMDP is, en geen MDP, en biedt een convergentiebewijs voor asynchrone learning in deze setting onder gemiddelde kosten-criteria, een gat dat eerder in de literatuur werd opgemerkt (bijv. Wan et al., 2021).

Het artikel sluit af met een numerieke casestudy op een continu controleprobleem, die de convergentie van de waarde-functies en de reductie van regret demonstreert naarmate de kwantisatie-snelheid toeneemt, wat de theoretische grenzen valideert.