Research map / Learning theory and algorithms / Sample complexity
Risk Estimation in a Markov Cost Process: Lower and Upper Bounds
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives minimax sample-complexity lower bounds (Omega(1/eps^2)) for estimating VaR, CVaR, variance and mean of the discounted cost of a Markov cost process, and matching truncated-horizon upper bounds (up to logs) for CVaR, variance and Lipschitz risk measures.
Problem
Estimating risk measures (variance, VaR, CVaR) of the infinite-horizon discounted cost from a single sample path of a Markov cost process, where the sample complexity of such estimation was previously unknown beyond the mean.
Approach
Lower bounds via a two-state hard MCP instance (deterministic costs) and a single-state Gaussian-cost reduction (stochastic costs), plus a truncated-horizon estimator that resets the chain every T steps and applies i.i.d. empirical estimators to the m=N/T truncated trajectories.
Key results
- Any VaR/CVaR/variance estimator needs Omega(1/epsilon^2) samples in both expected and high-probability senses (deterministic and stochastic cost instances).
- Truncated CVaR estimator achieves expected error bound 32(1-gamma^T)^2K^2/((1-alpha)(1-gamma)^2 sqrt(m)) + gamma^T K/(1-gamma) with m=N/T, giving O~(1/epsilon^2) sample complexity matching the lower bound up to logs.
- The lower bound for the discounted mean improves the prior Omega(1/epsilon) bound to Omega(1/epsilon^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Establish a minimax lower bound for mean, VaR, CVaR, and variance estimation | MCP risk estimation · Expected estimation error | sample complexity: $\Omega \left(\frac{1}{\epsilon^2} \right)$ | Helped |
| Use a truncation-based estimator | MCP CVaR estimation · Expected estimation error | sample complexity: $\widetilde{\mathcal{O}} \left(\frac{1}{\epsilon^2} \right)$ | Helped |
| Extend the truncation-based estimator to Lipschitz risk measures | MCP Lipschitz risk estimation · Expected estimation error | sample complexity: $\widetilde{\mathcal{O}} \left(\frac{1}{\epsilon^2} \right)$ | Helped |
| Use the truncation-based estimator | MCP variance estimation · Expected estimation error | sample complexity: $\widetilde{\mathcal{O}} \left(\frac{1}{\epsilon^2} \right)$ | Helped |
| Strengthen the mean-estimation minimax lower bound | MCP mean estimation · High-probability estimation | sample complexity lower bound: $\Omega\left(\frac{1}{\epsilon}\right)$ -> $\Omega \left(\epsilon^{-2} \ln\left(\frac{1}{\delta}\right) \right)$ | Helped |
| Establish high-probability minimax lower bounds for mean, VaR, and CVaR | MCP risk estimation · High-probability estimation | sample complexity: $\Omega \left(\epsilon^{-2} \ln\left(\frac{1}{\delta}\right) \right)$ | Helped |
| Use truncated trajectories to estimate VaR and CVaR | MCP VaR and CVaR estimation · High-probability estimation | sample complexity: $\widetilde{\mathcal{O}} \left(\epsilon^{-2}\ln (\frac{1}{\delta})\right)$ | Helped |
| Extend truncated estimation to Lipschitz risk measures | MCP Lipschitz risk estimation · High-probability estimation | sample complexity: $\widetilde{\mathcal{O}} \left(\epsilon^{-2}\ln (\frac{1}{\delta})\right)$ | Helped |
| Use truncated trajectories to estimate variance | MCP variance estimation · High-probability estimation | sample complexity: $\widetilde{\mathcal{O}} \left(\epsilon^{-2}\ln (\frac{1}{\delta})\right)$ | Helped |
Surprising findings
- The prior Omega(1/sqrt(n)) minimax mean lower bound in the closest related work is misleading; with its epsilon dependence accounted for it is only O(1/n).
Limitations
- Gap in delta-dependence between lower bound (log 1/delta) and upper bound (sqrt(log 1/delta)) for high-probability bounds.
- VaR concentration requires a minimum density growth assumption (A1) on the truncated distribution.
- Upper bounds only hold up to logarithmic factors in the sample complexity.
Experimental setup
Metrics: sample complexity expected estimation error high-probability tail bound
Baselines: Minimax O(1/epsilon) lower bound for discounted mean estimation
Builds on: Lower bound for mean estimation of discounted cost (Zhang et al. style minimax a i.i.d. CVaR estimators (Brown 2007 / Thomas and Learned-Miller concentration)
Closest papers by meaning
- Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes (NeurIPS 2024 · similarity 0.87)
- Planning and Learning in Average Risk-aware MDPs (NeurIPS 2025 · similarity 0.85)
- Truncated Variance Reduced Value Iteration (NeurIPS 2024 · similarity 0.85)
- Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.85)
- The Number of Trials Matters in Infinite-Horizon General-Utility Markov Decision Processes (ICML 2025 · similarity 0.84)
- Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.