Central Limit Theorems for Sample Average Approximations in Stochastic Optimal Control
Johannes Milz, Alexander Shapiro · 2025
Read Central Limit Theorems for Sample Average Approximations in Stochastic Optimal Control by Johannes Milz, Alexander Shapiro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01942.txt.
Introduction
Johannes Milz and Alexander Shapiro work out how wrong a simulated optimal controller can be, in the precise language of limit theorems. Sample average approximation replaces an uncertain future with a finite batch of scenarios and solves that instead. The pair prove central limit theorems for its value functions in finite-horizon stochastic control.
The engine is an abstract limit theorem for stochastic backward recursions, which hands back the limiting law stage by stage. At each stage the asymptotic variance splits into fresh noise from that stage plus future variance propagated backward, a clean picture of uncertainty compounding through time. The linear quadratic regulator gets explicit formulas, and the authors close by examining what changes when the optimal policy is not unique.
Catalog record
| CREATOR | Johannes Milz, Alexander Shapiro |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-01942
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Central Limit Theorems for Sample Average Approximations in Stochastic Optimal Control Thanks: Funding: The research of the first author was supported by the National Science Foundation under Grant No. DMS-2410944. The research of the second author was partially supported by Air Force Office of Scientific Research (AFOSR) under Grant FA9550-22-1-0244. Johannes Milz, Alexander Shapiro Abstract We establish central limit theorems for the Sample Average Approximation (SAA) method in discrete-time, finite-horizon Stochastic Optimal Control. Using the dynamic programming principle and backward induction, we characterize the limiting distributions of the SAA value functions. The asymptotic variance at each stage decomposes into two components: a current-stage variance arising from immediate randomness, and a propagated future variance accumulated from subsequent stages. This decomposition clarifies how statistical uncertainty propagates backward through time. Our derivation relies on a stochastic equicontinuity condition, for which we provide sufficient conditions. We illustrate the variance decomposition using the classical Linear Quadratic Regulator (LQR) problem. Although its unbounded state and control spaces violate the compactness assumptions of our framework, the LQR setting enables explicit computation and visualization of both variance components. Keywords: asymptotic distribution, delta theorem, stochastic optimal control, sample average approximation, dynamic programming 1 Introduction An approach to solving stochastic programming problems is to approximate the ‘true’ distribution of the corresponding random vector by the empirical distribution based on a randomly generated sample. This approach became known as the Sample Average Approximation (SAA) method [ 7 ] . For static (one stage) stochastic programs statistical inference of the SAA method is well developed (cf., [ 16 , Section 5.1] ). It is known that under mild regularity conditions the optimal value of the SAA problem asymptotically has a normal distribution, provided that the true problem has a unique optimal solution. On the other hand, little is known about asymptotics of the SAA method applied to multistage stochastic optimization problems. The main goal of this paper is to derive Central Limit Theorem (CLT)-type asymptotics for Stochastic Optimal Control (SOC) in discrete time. One motivation for studying such CLTs is the construction of confidence intervals to certify termination of optimization methods such as MSPPy [ 5 ] . Contributions The primary contributions of this paper are as follows: 1. We establish CLTs for SAA value functions using the dynamic programming principle and backward induction. These CLTs are derived under a stochastic equicontinuity-type condition on the SAA dynamic programming operators. Our analysis reveals that the asymptotic variance at each stage decomposes into a current stage variance and a propagated future variance . This provides some insights into how sampling errors accumulate backward through time. 2. We provide a set of sufficient conditions for verifying the stochastic equicontinuity-type condition. We demonstrate their applicability by verifying them for an inventory control problem. 3. We analytically derive the CLT for the linear quadratic regulator (LQR). Although the unbounded state and control spaces in the LQR problem violate the compactness assumptions required by our general framework, it permits explicit computation and yields valuable insight into the behavior of both variance components. We illustrate these findings graphically. Related work The sample complexity of multistage stochastic programming has been established in [ 14 , 13 ] . However, as noted above, the literature on the limit distributions of SAA value functions and SAA solutions and policies remains relatively sparse. For instance, [ 6 ] analyzes limit distributions in the context of two-stage integer programming, but the results do not appear to extend to multistage settings. Limit theorems for infinite-horizon, discounted stochastic optimal control are provided in [ 15 ] . More recently, [ 19 ] analyzes the asymptotic behavior of data-driven policies in a periodic review stochastic inventory control problem. Outline Section 2 presents the stochastic optimal control model, key assumptions, and establishes the base case for our inductive CLTs. Section 3 establishes CLTs for the SAA value functions, introduces the concepts of current-stage and propagated variance, and discusses sufficient conditions. Section 4 illustrates our theoretical results with a LQR example. Section 5 summarizes our findings. Finally, Appendix A provides detailed derivations for the LQR example. Notation We use the following notation. We define [a]_{+}\coloneqq\max\{0,a\} . For a process \xi_{1},\ldots, we denote by \xi_{[t]}=(\xi_{1},\ldots,\xi_{t}) its history. By ‘ := ’ we mean “equal by definition”. By ‘ {\rightsquigarrow}\, ’ we denote convergence in distribution. By \delta_{\xi} we denote the measure of mass one at \xi (Dirac measure). We denote by \mathcal{N}(\mu,\Sigma) the normal distribution with mean vector \mu and covariance matrix \Sigma . For random variables X and Y we denote by {\mathbb{E}}[X|Y] the conditional expectation of X given Y . For a compact metric space {\cal X} we denote by C({\cal X}) the space of continuous functions \phi:{\cal X}\to{\mathbb{R}} equipped with the supremum norm \|\phi\|_{\infty}=\sup_{x\in\mathcal{X}}|\phi(x)| . By {\mathfrak{o}}_{p}(1) we denote a random variable uniformly convergent in probability to zero. That is, for a sequence of random variables Z_{N}\in C({\cal X}) by writing Z_{N}={\mathfrak{o}}_{p}(N^{-\alpha}) we mean that N^{\alpha}\|Z_{N}\|_{\infty} converges in probability to zero as N\to\infty , i.e., Z_{N}={\mathfrak{o}}_{p}(N^{-\alpha})\;\text{means that}\;\|Z_{N}\|_{\infty}=o_{p}(N^{-\alpha}). (1.1) Let \mathcal{X} and \mathcal{Y} be compact metric spaces. For a mapping G:C({\cal X})\to C({\cal Y}) we denote by G^{\prime}(\phi;\eta):=\lim_{\tau\downarrow 0}\frac{G(\phi+\tau\eta)-G(\phi)}{\tau} (1.2) the directional derivative of G(\cdot) at \phi in direction \eta , where the limit is with respect to the \|\cdot\|_{\infty} -norm. For a compact subset \mathcal{Y}_{0} of a metric space \mathcal{Y} , the metric entropy \mathcal{H}(\varepsilon,\mathcal{Y}_{0}) is the natural logarithm of the \varepsilon -covering number of \mathcal{Y}_{0} (with respect to \mathcal{Y} ). 2 Stochastic optimal control in discrete time We consider the discrete time, finite horizon SOC model (e.g., [ 3 ] ): \min\limits_{\pi\in\Pi}{\mathbb{E}}^{\pi}\left[\sum_{t=1}^{T}f_{t}(x_{t},u_{t},\xi_{t})+f_{T+1}(x_{T+1})\right], (2.1) where \Pi is the set of polices satisfying the constraints \Pi=\Big\{\pi=(\pi_{1},\ldots,\pi_{T}):u_{t}=\pi_{t}(x_{t},\xi_{[t-1]}),u_{t}\in{\cal U}_{t},x_{t+1}=F_{t}(x_{t},u_{t},\xi_{t}),\;\;t=1,\ldots,T\Big\}. (2.2) Here variables x_{t}\in{\mathbb{R}}^{n_{t}} , t=1,\ldots,T+1 , represent the state of the system, u_{t}\in{\mathbb{R}}^{m_{t}} , t=1,\ldots,T , are controls, \xi_{t}\sim P_{t} are random vectors whose probability distribution P_{t} is supported on a closed subset \Xi_{t} of {\mathbb{R}}^{d_{t}} , f_{t}:{\mathbb{R}}^{n_{t}}\times{\mathbb{R}}^{m_{t}}\times{\mathbb{R}}^{d_{t}}\to{\mathbb{R}} , t=1,\ldots,T , are cost functions, f_{T+1}\colon{\mathbb{R}}^{n_{T+1}}\to{\mathbb{R}} is the final cost function, F_{t}:{\mathbb{R}}^{n_{t}}\times{\mathbb{R}}^{m_{t}}\times{\mathbb{R}}^{d_{t}}\to{\mathbb{R}}^{n_{t+1}} are (measurable) mappings, and {\cal U}_{t} is a (nonempty) subset of {\mathbb{R}}^{m_{t}} . The values x_{1} and \xi_{0} are deterministic (initial conditions); it is also possible to view x_{1} as random with a given distribution, this is not essential for the following discussion. Assumption 2.1 . (i) The probability distribution P_{t} of \xi_{t} does not depend on our decisions (on states and actions), t=1,\ldots,T . (ii) The random process \xi_{1},\ldots,\xi_{T} is stagewise independent, i.e., random vector \xi_{t+1} is independent of \xi_{[t]}=(\xi_{1},\ldots,\xi_{t}) , t=1,\ldots,T-1 . The optimization in ( 2.1 ) is performed over policies \pi\in\Pi determined by decisions u_{t} and state variables x_{t} considered as functions of \xi_{[t-1]}=(\xi_{1},\ldots,\xi_{t-1}) , t=1,\ldots,T , and satisfying the feasibility constraints ( 2.2 ). We also denote \Xi_{[t]}\coloneqq\Xi_{1}\times\cdots\times\Xi_{t} . For the sake of simplicity, in order not to distract from the main message of the paper, we assume that the control sets {\cal U}_{t} do not depend on x_{t} . It is possible to extend the analysis to the general case, where the control sets are functions of the state variables. Remark 2.1 . Note that because of the basic assumption that the probability distribution of \xi_{1},\ldots,\xi_{T} does not depend on our decisions (does not depend on states and actions), it suffices to consider