For φ-divergences with superlinear growth, sample average approximation achieves P-independent sample complexity for worst-case expectation estimation depending only on φ's growth, ball radius and precision, with optimality via lower bounds; non-superlinear φ yields unbounded P-dependent complexity.
Sample Complexity for Markov Decision Processes and Stochastic Optimal Control with Static Risk Measures
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We present an elementary state augmentation method for a class of static risk measure applied to the total cost for both Markov decision processes and stochastic optimal control, such that dynamic programming equations can be derived on the augmented space. Through this we discuss the sample complexities of these two problems for both finite-horizon and infinite-horizon settings. We demonstrate the application of the proposed approach through studying distributionally robust functional generated by $\phi$-divergences including conditional value-at-risk.
fields
math.OC 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Sample Average Approximation for Distributionally Robust Optimization with $\phi$-divergences
For φ-divergences with superlinear growth, sample average approximation achieves P-independent sample complexity for worst-case expectation estimation depending only on φ's growth, ball radius and precision, with optimality via lower bounds; non-superlinear φ yields unbounded P-dependent complexity.