# Forward-PECVaR Algorithm: Exact Evaluation for CVaR SSPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 19 references that are in the map.
- First posted on arXiv 1 Mar 2023.

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

- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [Optimizing the CVaR via Sampling](https://mlsanity.com/paper/1404.3862/) (2014)
- [Algorithms for CVaR Optimization in MDPs](https://mlsanity.com/paper/1406.3339/) (2014)
- [Being Optimistic to Be Conservative: Quickly Learning a CVaR Policy](https://mlsanity.com/paper/1911.01546/) (2019)
- [Worst Cases Policy Gradients](https://mlsanity.com/paper/1911.03618/) (2019)
- [Policy Gradients for CVaR-Constrained MDPs](https://mlsanity.com/paper/1405.2690/) (2014)
- [Risk Aversion in Finite Markov Decision Processes Using Total Cost Criteria and Average Value at Risk](https://mlsanity.com/paper/1602.05130/) (2016)
- [Planning for Risk-Aversion and Expected Value in MDPs](https://mlsanity.com/paper/2110.12746/) (2021)
- [Risk-aware Stochastic Shortest Path](https://mlsanity.com/paper/2203.01640/) (2022)

## Abstract (arXiv)

The Stochastic Shortest Path (SSP) problem models probabilistic sequential-decision problems where an agent must pursue a goal while minimizing a cost function. Because of the probabilistic dynamics, it is desired to have a cost function that considers risk. Conditional Value at Risk (CVaR) is a criterion that allows modeling an arbitrary level of risk by considering the expectation of a fraction α of worse trajectories. Although an optimal policy is non-Markovian, solutions of CVaR-SSP can be found approximately with Value Iteration based algorithms such as CVaR Value Iteration with Linear Interpolation (CVaRVIQ) and CVaR Value Iteration via Quantile Representation (CVaRVILI). These type of solutions depends on the algorithm's parameters such as the number of atoms and α0 (the minimum α). To compare the policies returned by these algorithms, we need a way to exactly evaluate stationary policies of CVaR-SSPs. Although there is an algorithm that evaluates these policies, this only works on problems with uniform costs. In this paper, we propose a new algorithm, Forward-PECVaR (ForPECVaR), that evaluates exactly stationary policies of CVaR-SSPs with non-uniform costs. We evaluate empirically CVaR Value Iteration algorithms that found solutions approximately regarding their quality compared with the exact solution, and the influence of the algorithm parameters in the quality and scalability of the solutions. Experiments in two domains show that it is important to use an α0 smaller than the α target and an adequate number of atoms to obtain a good approximation.