Entropic Risk Optimization in Discounted MDPs

Jia Lin Hau, Marek Petrik, Mohammad GhavamzadehAISTATS 2023 · OpenReview

Abstract

Risk-averse Markov Decision Processes (MDPs) have optimal policies that achieve high returns with low variability, but these MDPs are often difficult to solve. Only a few practical risk-averse objectives admit a dynamic programming (DP) formulation, which is the mainstay of most MDP and RL algorithms. We derive a new DP formulation for discounted risk-averse MDPs with Entropic Risk Measure (ERM) and Entropic Value at Risk (EVaR) objectives. Our DP formulation for ERM, which is possible because of our novel definition of value function with time-dependent risk levels, can approximate optimal policies in a time that is polynomial in the approximation error. We then use the ERM algorithm to optimize the EVaR objective in polynomial time using an optimized discretization scheme. Our numerical results show the viability of our formulations and algorithms in discounted MDPs.

Introduction

In high-stakes domains such as healthcare and finance, maximizing expected returns is often insufficient. A policy that performs well on average but carries a non-negligible risk of catastrophic failure is unacceptable. This necessitates Risk-Averse Reinforcement Learning (RL), where agents are trained to maximize rewards while minimizing "tail-end" risks.

Standard RL typically focuses on risk-neutral objectives. While measures like Conditional Value-at-Risk (CVaR) are popular for risk-aversion, they are computationally challenging in discounted MDPs, often requiring state-space augmentation. This paper addresses these challenges by providing polynomial-time algorithms for optimizing the Entropic Risk Measure (ERM) and Entropic Value-at-Risk (EVaR) without the need for state augmentation.

Theoretical Foundations and the Tower Property

The primary obstacle in risk-averse DP is the violation of the Tower Property. In standard MDPs, the expectation of an expectation is the expectation, allowing for recursive value function updates. As shown in Figure 3, many risk measures lack this property or other desirable traits like law invariance or positive homogeneity.

Comparison of risk measure properties.

The authors identify a breakthrough property: Positive Quasi-homogeneity. They demonstrate that for discounted MDPs, DP is possible if the risk sensitivity parameter $\beta$ is adjusted over time. Specifically, by decaying the risk level exponentially ($\beta \gamma^t$), the agent's risk-aversion decreases as future rewards are discounted, enabling a valid Bellman equation.

Methodology: ERM and EVaR Optimization

The research introduces two primary algorithms:

  1. ERM-VI (Value Iteration): Utilizes time-dependent risk levels to solve the ERM objective.
  2. EVaR-MDP: Optimizes EVaR by treating it as the supremum of ERM over a range of risk levels.

To solve the EVaR objective efficiently, the authors employ an optimized discretization scheme for the risk parameter $\beta$. Figure 2 illustrates the function $h(\beta)$ and the discrete points used to find the optimal risk level.

Optimization of EVaR over the risk sensitivity parameter $\beta$.

A significant theoretical finding is that for discounted ERM and EVaR, optimal policies are deterministic and Markovian, though non-stationary due to the time-dependent risk levels.

Experimental Results

The algorithms were tested on several tabular MDP benchmarks, including Machine Replacement, Gambler’s Ruin, Inventory Management, and River-swim.

Key findings include:

  • Efficiency: The proposed EVaR algorithm is significantly faster than traditional "Augmented CVaR" methods. In the Inventory Management domain, the new method achieved solutions in ~1.1 seconds compared to 780 seconds for the augmented approach.
  • Risk Mitigation: EVaR-based policies consistently outperformed risk-neutral and nested risk measures in actual risk metrics, providing better protection against tail-end events.
  • Discretization Impact: The results confirmed that the derived optimized grid for $\beta$ is essential for performance, as naive discretization led to significantly worse outcomes.

Conclusion and Future Directions

This work provides a tractable framework for risk-averse optimization in discounted MDPs using ERM and EVaR. By leveraging decaying risk levels, the authors bypass the need for state augmentation while maintaining polynomial-time complexity. Future research will focus on scaling these methods to high-dimensional state spaces using Deep RL and function approximation, as well as addressing the non-stationarity inherent in time-dependent risk levels.

Summary updated

Abstract

Risk-averse Markov Decision Processes (MDPs) have optimal policies that achieve high returns with low variability, but these MDPs are often difficult to solve. Only a few practical risk-averse objectives admit a dynamic programming (DP) formulation, which is the mainstay of most MDP and RL algorithms. We derive a new DP formulation for discounted risk-averse MDPs with Entropic Risk Measure (ERM) and Entropic Value at Risk (EVaR) objectives. Our DP formulation for ERM, which is possible because of our novel definition of value function with time-dependent risk levels, can approximate optimal policies in a time that is polynomial in the approximation error. We then use the ERM algorithm to optimize the EVaR objective in polynomial time using an optimized discretization scheme. Our numerical results show the viability of our formulations and algorithms in discounted MDPs.
BibTeX
@inproceedings{hau2023entropic,
  author = {Jia Lin Hau and Marek Petrik and Mohammad Ghavamzadeh},
  title = {{Entropic Risk Optimization in Discounted MDPs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=AqkpQuGgMt},
}
Figure