On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processes
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909239875731456 |
|---|---|
| author | Hau, Jia Lin Delage, Erick Ghavamzadeh, Mohammad Petrik, Marek |
| author_facet | Hau, Jia Lin Delage, Erick Ghavamzadeh, Mohammad Petrik, Marek |
| contents | Optimizing static risk-averse objectives in Markov decision processes is difficult because they do not admit standard dynamic programming equations common in Reinforcement Learning (RL) algorithms. Dynamic programming decompositions that augment the state space with discrete risk levels have recently gained popularity in the RL community. Prior work has shown that these decompositions are optimal when the risk level is discretized sufficiently. However, we show that these popular decompositions for Conditional-Value-at-Risk (CVaR) and Entropic-Value-at-Risk (EVaR) are inherently suboptimal regardless of the discretization level. In particular, we show that a saddle point property assumed to hold in prior literature may be violated. However, a decomposition does hold for Value-at-Risk and our proof demonstrates how this risk measure differs from CVaR and EVaR. Our findings are significant because risk-averse algorithms are used in high-stake environments, making their correctness much more critical. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_12477 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processes Hau, Jia Lin Delage, Erick Ghavamzadeh, Mohammad Petrik, Marek Optimization and Control Artificial Intelligence Optimizing static risk-averse objectives in Markov decision processes is difficult because they do not admit standard dynamic programming equations common in Reinforcement Learning (RL) algorithms. Dynamic programming decompositions that augment the state space with discrete risk levels have recently gained popularity in the RL community. Prior work has shown that these decompositions are optimal when the risk level is discretized sufficiently. However, we show that these popular decompositions for Conditional-Value-at-Risk (CVaR) and Entropic-Value-at-Risk (EVaR) are inherently suboptimal regardless of the discretization level. In particular, we show that a saddle point property assumed to hold in prior literature may be violated. However, a decomposition does hold for Value-at-Risk and our proof demonstrates how this risk measure differs from CVaR and EVaR. Our findings are significant because risk-averse algorithms are used in high-stake environments, making their correctness much more critical. |
| title | On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processes |
| topic | Optimization and Control Artificial Intelligence |
| url | https://arxiv.org/abs/2304.12477 |