Paper: arXiv 2405.13513
Authors: Shivam Patel, Vivek Borkar
Abstract
Risk sensitive decision making finds important applications in current day use cases. Existing risk measures consider a single or finite collection of random variables, which do not account for the asymptotic behaviour of underlying systems. Conditional Value at Risk (CVaR) is the most commonly used risk measure, and has been extensively utilized for modelling rare events in finite horizon scenarios. Naive extension of existing risk criteria to asymptotic regimes faces fundamental challenges, where basic assumptions of existing risk measures fail. We present a complete simulation based approach for sequentially computing Asymptotic CVaR (ACVaR), a risk measure we define on limiting empirical averages of markovian rewards. Large deviations theory, density estimation, and two-time scale stochastic approximation are utilized to define a ’tilted’ probability kernel on the underlying state space to facilitate ACVaR simulation. Our algorithm enjoys theoretical guarantees, and we numerically evaluate its performance over a variety of test cases.
Complexity vs Empirical Score
- Math Complexity: 8.5/10
- Empirical Rigor: 6.5/10
- Quadrant: Holy Grail — high math complexity, high empirical rigor
Why this score: The paper employs advanced mathematics including large deviations theory, multiplicative Poisson equations, and two-time scale stochastic approximation, placing it firmly in high math complexity. It also presents a concrete algorithm with simulation-based steps and empirical evaluation, indicating moderate to high empirical rigor.
Research Flowchart
flowchart TD
A["Research Goal: Define & Compute<br>Asymptotic CVaR for Markov Chains"] --> B["Methodology: Theoretical Foundation<br>Large Deviations Theory"]
B --> C["Data Input: Markovian Reward System"]
C --> D{"Computational Process:<br>Simulation-based Algorithm"}
D --> E["Tilted Probability Kernel<br>via Density Estimation"]
E --> F["Sequential Computation<br>Two-Time Scale Stochastic Approximation"]
F --> G["Key Finding: Validated ACVaR Measure<br>Numerical Evaluation on Test Cases"]
Evidence Card
What the authors claim, on what data, and who has checked it. Read from the paper's own text by a language model: every quote is verbatim, nothing was re-run. How to read this card
Proposes
The paper proposes an asymptotic variant of CVaR (ACVaR) and a stochastic approximation algorithm to compute it for Markov chains.
Source sentence
We present a complete simulation based approach for sequentially computing Asymptotic CVaR (ACVaR), a risk measure we define on limiting empirical averages of markovian rewards. We adapt the results therein to the problem of evaluating Asymptotic CVaR (ACVaR), a concept defined here, and provide theoretical justification for it as well as supporting numerical experiments for the proposed computational scheme.
Assumes 6
- The underlying process is a finite‑state Markov chain with a reward function g defined on the states. model
Source sentence
Let V ∗:= Vζ∗, ρ∗:= ρζ∗. Theorem 2.2.
- Large‑deviation theory applies to the empirical averages of the rewards. statistical
Source sentence
The proof uses an extension to Markov processes of the Bahadur-Rao theorem for exact asymptotics in large deviations from [10].
- The limiting cumulative distribution function of the reward is piecewise constant and can be approximated by a continuous interpolation. statistical
Source sentence
Let F(·) denote the limiting cumulative distribution function (CDF) of the reward g(Xn). Nevertheless, it is convenient to seek a suitable continuous and continuously increasing interpolation so that its inverse is likewise, in order to avoid some numerical issues.
- A Gaussian kernel density estimator provides a suitable estimate of the inverse CDF needed for the threshold. statistical
Source sentence
In the present work, we have used a Gaussian kernel density estimate [5]. Gaussian kernel estimation was our method of choice justified by its good empirical performance.
Show 2 more
- Two‑time‑scale stochastic approximation with step sizes a(n)=k/(1+(n+1)^0.6) and b(n)=k/(1+(n+1)^0.8) ensures convergence of the adaptive scheme. model
Source sentence
The simulation steps are performed with varying step-sizes which are in agreement with the two time-scale stochastic approximation formalism mentioned earlier. Step sizes are controlled by a single scaling parameter k as a(n) = k 1 + (n + 1)0.6 , b(n) = k 1 + (n + 1)0.8 .
- If a state is never visited, its reward is set to zero. other
Source sentence
If any state is unexplored, we nominally assign it a zero reward.
Data
- Synthetic Markov chain simulations (40, 75, 150 state chains) synthetic unknown
Source sentence
For the sake of brevity, we present here a comparison of 70th, 85th, 90th percentile thresholding in a 40 State Markov chain along with the 90th percentile thresholding in 75 and 150 state Markov chains.
- Deterministic rewards drawn from Uniform(0,4) synthetic unknown
Source sentence
We also tested our method on deterministic rewards that are chosen from a Unif(0, 4) distribution initially, obtaining similar convergence results.
Costs
Not applicable
Finds 4
- The adaptive stochastic approximation scheme converges in under 80 000 steps for all tested state spaces and thresholds. theoretical
Source sentence
We observe convergence for all the cases in under 80K steps, with (possibly) varying step size parameter k required for different state spaces and different values of c.
- Numerical experiments show that ACVaR estimates align with the theoretical expectations across 70th, 85th, and 90th percentile thresholds. performance
Source sentence
For the sake of brevity, we present here a comparison of 70th, 85th, 90th percentile thresholding in a 40 State Markov chain along with the 90th percentile thresholding in 75 and 150 state Markov chains.
- When the reward process is constant, ACVaR reduces to the classical CVaR, confirming consistency with the standard risk measure. theoretical
Source sentence
For Xn ≡a fixed random variable, this would reduce ACVaR to CVaR as desired.
- The algorithm enjoys theoretical guarantees derived from large‑deviation theory and two‑time‑scale stochastic approximation. theoretical
Source sentence
Our algorithm enjoys theoretical guarantees, and we numerically evaluate its performance over a variety of test cases.
Checked by others
No other paper in the archive has been found to support or contradict these findings (compared with 26 related papers). Coverage is partial, so this is neither replication nor refutation.
Code
No repository by the authors found in the paper.
Extracted 2026-11-14 · same card as JSON · A language model chose these items: check the source sentence before relying on one.
Cited References (17)
- Stochastic Approximation: A Dynamical Systems Viewpoint (2022) — link
- Optimization of conditional value-at-risk (2000) — link
- Spectral theory and limit theorems for geometrically ergodic Markov processes (2003) — link
- Nonequilibrium Markov Processes Conditioned on Large Deviations (2014) — link
- Coherent Measures of Risk (1999) — link
- Peformance Analysis Conditioned on Rare Events: An Adaptive Simulation Scheme (2003) — link
- On the coherence of expected shortfall (2002) — link
- Q-Learning for Risk-Sensitive Control (2002) — link
and 9 more
- Risk-Constrained Reinforcement Learning with Percentile Risk Criteria (2015) — link
- Proceedings of the 25th international conference on Machine learning - ICML ‘08 (2008) — link
- Uniform Convergence Rates for Kernel Density Estimation (2017)
- Large deviations conditioned on large deviations I: Markov chain and Langevin equation (2019) — link
- Optimizing the CVaR via Sampling (2015) — link
- A tutorial on kernel density estimation and recent advances (2017) — link
- Risk-averse Distributional Reinforcement Learning: A CVaR Optimization Approach (2019) — link
- Risk-constrained reinforcement learning with percentile risk criteria (2017) — link
- Risk-Sensitive Reinforcement Learning via Policy Gradient Search (2022) — link
0 of 17 cited works are in the corpus; resolved via arXiv source bundles, Semantic Scholar and OpenAlex. Corpus-wide: 2596 linked papers.