Abstract
We tackle the problem of estimating risk measures of the infinite-horizondiscounted cost within a Markov cost process. The risk measures we studyinclude variance, Value-at-Risk (VaR), and Conditional Value-at-Risk (CVaR).First, we show that estimating any of these risk measures with$\epsilon$-accuracy, either in expected or high-probability sense, requires atleast $\Omega(1/\epsilon^2)$ samples. Then, using a truncation scheme, wederive an upper bound for the CVaR and variance estimation. This bound matchesour lower bound up to logarithmic factors. Finally, we discuss an extension ofour estimation scheme that covers more general risk measures satisfying acertain continuity criterion, e.g., spectral risk measures, utility-basedshortfall risk. To the best of our knowledge, our work is the first to providelower and upper bounds for estimating any risk measure beyond the mean within aMarkovian setting. Our lower bounds also extend to the infinite-horizondiscounted costs' mean. Even in that case, our lower bound of$\Omega(1/\epsilon^2) $ improves upon the existing $\Omega(1/\epsilon)$ bound[13].