Adaptive Partitioning and Learning for Stochastic Control of Diffusion Processes

Technische Samenvatting: Adaptieve Partitionering en Leren voor Stochastische Controle van Diffusieprocessen

Probleemformulering
Dit artikel behandelt de uitdaging van Reinforcement Learning (RL) voor gecontroleerde diffusieprocessen die worden gekenmerkt door onbegrensde continue toestandsruimtes, begrensde continue actieruimtes en beloningen met polynomiale groei. Deze instellingen komen veel voor in de financiële sector, economie en operations research (bijv. portfolio-optimalisatie, dynamische hedging en voorraadbeheer), maar blijven theoretisch onderontwikkeld vergeleken met begrensde of tabelvormige MDP's.

De auteurs formuleren het probleem als een discrete-tijd Markov Beslissingsproces (MDP) geïnduceerd door een Euler–Maruyama-discretisering van een continue-tijd gecontroleerde stochastische differentiële vergelijking (SDE). De toestandsverandering wordt beheerst door:
$$X_{h+1} - X_h = \mu_h(X_h, A_h)\Delta + \sigma_h(X_h, A_h)B_h\sqrt{\Delta}$$
waarbij $\mu$ en $\sigma$ onbekende drift- en volatiliteitsfuncties zijn die afhankelijk zijn van het staat-actiepaar, en $B_h$ i.i.d. Gaussische ruis is. De beloningsfunctie $\bar{R}_h(x, a)$ mag polynomiaal groeien met de toestand, wat de standaard aanname van begrensde beloningen versoepelt. Het doel is om de cumulatieve regret te minimaliseren over $K$ episodes met horizon $H$.

Methodologie: APL-Diffusion Algoritme
De auteurs stellen APL-Diffusion voor, een model-gebaseerd algoritme dat adaptieve partitionering integreert met lokale schatting van de systeemdynamiek. De belangrijkste componenten zijn:

1. Toestandslokalisatie: Om de onbegrensde toestandsruimte aan te pakken, beperkt het algoritme het leren tot een begrensde bal $S_1 = \{x : \|x\| \le \rho\}$. Trajecten die deze bal verlaten, worden afgehandeld via grove schattingen die de regret-grens niet domineren.
2. Adaptieve Partitionering: De gezamenlijke staat-actieruimte wordt verdeeld in hyperkubussen. In tegenstelling tot uniforme roosters wordt de partitionering adaptief verfijnd. Een blok $B$ wordt gesplitst als de geschatte bias de statistische betrouwbaarheidsgrens overschrijdt. Dit balanceert exploratie en benaderingsfouten.
3. Lokale Schatters: Binnen elk partitioneringsblok houdt het algoritme schatters bij voor:
   • Drift ($\hat{\mu}$) en Volatiliteit ($\hat{\sigma}$): Geconstrueerd uit geobserveerde toestandsveranderingen.
   • Beloning ($\hat{R}$): Geconstrueerd uit geobserveerde beloningen.
   • Transitie-kernel: Gemodelleerd als een Gaussische distributie geconditioneerd op de geschatte drift en volatiliteit.
4. Optimistische Planning: Het algoritme construeert optimistische Q-waarden en waardefuncties met behulp van Upper Confidence Bounds (UCB) die rekening houden met de schattingsonzekerheid in de drift, volatiliteit en beloning, evenals de bias geïntroduceerd door de grootte van de partitionering.
5. Beleidsuitvoering: Acties worden gulzig geselecteerd op basis van de optimistische Q-functie schattingen, waarbij de actieruimte binnen een blok uniform wordt gesampled uit de projectie van het blok.

Belangrijkste Bijdragen

1. Theoretisch Kader voor Onbegrensde Diffusies: Het artikel breidt de RL-theorie uit naar onbegrensde diffusieprocessen met polynomiaal groeiende beloningen, een setting waarin bestaande theoretische garanties (vaak gebaseerd op begrensdheid) falen.
2. Nieuwe Zooming Dimensie: Een nieuw begrip van "zooming dimensie" ($z_{max,c}$) wordt gedefinieerd specifiek voor onbegrensde toestandsruimtes. Deze metriek kwantificeert de complexiteit van de nabij-optimale verzameling en zorgt ervoor dat de regret-bounds afhangen van de intrinsieke dimensie van het probleem in plaats van de omgevingdimensie.
3. Concentratie-ongelijkheden: De auteurs leiden concentratie-ongelijkheden af voor de schatters van drift en volatiliteit onder Lipschitz-aannames. Een belangrijke technische uitdaging die is aangepakt, is het vaststellen van concentratie voor covariantie-matrices onder enkel Lipschitz-regulariteit van de volatiliteit, wat de introductie vereiste van tussenliggende termen die niet aanwezig zijn in standaard begrensde MDP-analyses.
4. Regret Bounds: Het artikel stelt een high-probability regret bound vast van de orde:
   $$\tilde{O}\left( H K^{\frac{1 - p^2 - (m+1)^2(z_{max,c}+2) - (m+1)(2d_S + 2m + 4)}{p(p+m+1)(z_{max,c}+2) + p(2d_S + 2m + 4)}} \right)$$
   waarbij $p$ de begrensde momentorde is van de initiële toestandsdistributie, $m+1$ de polynomiale groeidorde van de beloning is, $d_S$ de dimensie van de toestand is, en $z_{max,c}$ de worst-case zooming dimensie is.
   • Wanneer $p \to \infty$ (begrensde initiële momenten), herstelt de bound de orde $\tilde{O}(H K^{\frac{z_{max,c}+1}{z_{max,c}+2}})$, wat consistent is met bestaande resultaten voor begrensde settings (bijv. [Sinclair et al., 2023]).
   • De bound legt expliciet de impact vast van heavy-tailed initiële distributies en snelle beloningsgroei op de efficiëntie van het leren.

Resultaten en Validatie

• Theoretische Analyse: De regret-analyse toont aan dat het algoritme een sublineaire regret bereikt in het aantal episodes $K$. De bounds laten zien dat ze bestaande resultaten voor begrensde settings als een speciaal geval herstellen, terwijl ze garanties uitbreiden naar een bredere klasse van diffusieproblemen.
• Numerieke Experimenten:
  • 1D Voorbeeld: Een hanteerbaar eendimensionaal controleprobleem laat zien dat het algoritme partities adaptief verfijnt in regio's met hoge optimale Q-waarden, wat leidt tot een snelle convergentie van de geschatte waardefunctie. De empirische regret-orde (0.69) bleek beter dan de worst-case theoretische bound (0.75).
  • Mean-Variance Portfolio Optimalisatie: Een hoog-dimensionale toepassing met 5 risicovolle activa en 1 risicovrij actiefum. Ondanks het feit dat het probleem strikte Lipschitz-aannames op de actievariabele schendt (doordat de volatiliteit willekeurig klein kan worden), vertoonde het algoritme een sterke empirische prestatie met een regret-orde van 0.78, waarmee het de worst-case theoretische bound van 0.875 overtrof.

Betekenis
Het artikel beweert het eerste rigoureuze theoretische kader en algoritme te bieden voor RL in gecontroleerde diffusieprocessen met onbegrensde toestanden en polynomiaal groeiende beloningen. Door een gelokaliseerd adaptief partitioneringsschema en een op maat gemaakte zooming dimensie te introduceren, overbrugt dit werk de kloof tussen de theoretische behapbaarheid van begrensde MDP's en de praktische noodzaak om onbegrensde financiële en economische systemen te modelleren. De resultaten suggereren dat efficiënt leren mogelijk is in deze complexe, hoog-dimensionale settings, mits de nabij-optimale regio's een lagere intrinsieke dimensionaliteit bezitten. De numerieke experimenten valideren verder de robuustheid en effectiviteit van het algoritme in realistische, hoog-dimensionale financiële toepassingen.