# Risk Estimation in a Markov Cost Process: Lower and Upper Bounds

arXiv: https://arxiv.org/abs/2310.11389 · HTML: https://mlsanity.com/paper/2310.11389/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 20 references that are in the map.
- First posted on arXiv 17 Oct 2023.

## Builds on (most cited first, 3 of 3)

- [A Wasserstein distance approach for concentration of empirical risk estimates](https://mlsanity.com/paper/1902.10709/) (2019)
- [Concentration bounds for empirical conditional value-at-risk: The unbounded case](https://mlsanity.com/paper/1808.01739/) (2018)
- [A Tale of Sampling and Estimation in Discounted Reinforcement Learning](https://mlsanity.com/paper/2304.05073/) (2023)

## Built on by (most cited first, 2 of 2)

- [Reinforcement learning with an expectile-based objective](https://mlsanity.com/paper/2602.09300/) (2026)
- [Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learning](https://mlsanity.com/paper/2608.01917/) (2026)

## Abstract (arXiv)

We tackle the problem of estimating risk measures of the infinite-horizon discounted cost within a Markov cost process. The risk measures we study include variance, Value-at-Risk (VaR), and Conditional Value-at-Risk (CVaR). First, we show that estimating any of these risk measures with ε-accuracy, either in expected or high-probability sense, requires at least Omega(1/ε2) samples. Then, using a truncation scheme, we derive an upper bound for the CVaR and variance estimation. This bound matches our lower bound up to logarithmic factors. Finally, we discuss an extension of our estimation scheme that covers more general risk measures satisfying a certain continuity criterion, e.g., spectral risk measures, utility-based shortfall risk. To the best of our knowledge, our work is the first to provide lower and upper bounds for estimating any risk measure beyond the mean within a Markovian setting. Our lower bounds also extend to the infinite-horizon discounted costs' mean. Even in that case, our lower bound of Omega(1/ε2)  improves upon the existing Omega(1/ε) bound [13].