On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processes

Summary

The paper shows that the dynamic programming decomposition methods used in risk-averse MDP are suboptimal for CVaR and EVaR, but optimal for VaR. These findings seem important as such decomposition methods become increasingly popular recently.

Strengths

The findings that the decomposition fails for CVaR and EVaR are of importance and interesting to see.

Weaknesses

The paper presents negative outcomes arising from the application of the decomposition method in CVaR and EVaR MDP. However, it does not offer a solution or rigorous analysis to address or evaluate these shortcomings. Particularly, in Theorem 3.2, the authors demonstrate that there exists a risk level where the equalities in (8) do not hold, indicating that the decomposition is suboptimal. While this finding is valuable, it raises crucial questions. For instance, under which parameter values does the optimality of the decomposition hold? If we randomly select a risk level from an interval, what are the chances of achieving optimal decomposition? Can we establish an upper bound on the loss incurred by using the decomposition? Is there an alternative form of decomposition that yields smaller losses? These questions hold significant relevance and would provide insights into handling the limitations. Similar questions can be asked regarding the EVaR. Therefore, although the findings are noteworthy, the paper is not yet ready for publication. Further work on addressing the shortcomings of the decomposition method would significantly enhance the paper's quality.

Questions

- Please refer to the questions asked above. - Is there any way to numerically evaluate the suboptimality of the decomposition?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I do not see any negative societal impact from the paper.

Summary

The paper tackles the risk-level decomposition of risk measures in the finite Markov Decision Process (MDP). The work firstly points out the suboptimality of the decomposition proposed in prior works (Conditional-Value-at-Risk), by mathematically proving that the decomposition in CVaR does not maintain the equality to the optimal policy under policy optimization. Then the work mathematically proves the decomposition in Entropy-Value-at-Risk (EVaR) fails to find the minimum for the policy evaluation. Following that, the paper corrects the decomposition of EVaR and proposes a new dynamic program decomposition for Value-at-Risk (VaR). By avoiding the saddle-point gap in policy optimization, the new method remains optimal for both policy optimization and policy evaluation.

Strengths

The method contributes to identifying the suboptimality in policy optimization and policy evaluation in prior methods (CVaR and EVaR). The paper points out the reason causing the suboptimality and proposes a new method for improvement. As the paper improves the correctness of the policy learning in risk-averse methods, the theoretical result can also be significant when people apply the risk-averse approach in practice. The figures are clear and help with understanding the counterexamples.

Weaknesses

I understand that the paper mainly focuses on theoretical analysis, and it makes sense to me that there is no empirical evidence for the correctness of the new method. One small suggestion is to add a numerical experiment.

Questions

N/A

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes

Summary

The main contribution of the paper is to demonstrate that a popular dynamic programming decomposition for well-known risk metrics only provides suboptimal policies. More precisely, the underlying idea of such decompositions is to operate on an extended state space that incorporates a continuous state variable between 0 and 1 capturing the system risk level at the current stage. The belief in these existing decompositions was that the risk state variable could be finely discretized to approximate the optimal value function arbitrarily. However, the authors show a counter-example for CVaR and EVaR. Finally, they show that VaR does admit such a decomposition with a new proof scheme.

Strengths

+ The paper and proofs are very well-written and structured + Contribution is impactful within the analysis of risk measures I particularly find that this is an outstanding paper and contribution. First, it closes an open theoretical question on a meaningful and growing body of literature composed of 10+ papers only in these last five years, specifically demonstrating via a relatively simple but ingenious example that discretization is necessarily sub-optimal. The results are intriguing because the discretization assumption was a rather intuitive result, justifying many of the attempted proofs in the most recent literature. The authors also provide corrected decompositions for EVaR and VaR. I also note that it is also a bit concerning that these results contradict the optimality of many recent works, which are thus worth revisiting in the future. (On that note, I verified the proofs and examples of this paper to the best of my abilities, but did not re-analyze the previous papers' proofs, except to re-check their statements).

Weaknesses

- Much of the intuition is hidden in the proofs. - Lack of discussion of possible research avenues to address this issue. My primary concern is that the presentation can be excessively technical in some parts. I believe the proofs are very well written and easy to follow, especially as they are mostly counter-examples, but it would be interesting if authors could bring to light what fails more intuitively (just the saddle point discussion was commented on briefly). In particular, my understanding from the examples is that the discretization violates a certain variant of Von Neummann's minimax theorem due to non-convexity/non-concavity of policy choice, here captured in the strict inequality of equation (10). Perhaps my understanding is not accurate, but nonetheless it would be interesting if authors could expand more on the saddle point argument, perhaps providing directions on conditions for other coherent metrics that do not suffer from the same discretization issue. Minor notes: - Please kindly use capital letters when naming lemmas and theorems, e.g., Lemma X as opposed to lemma X. - In the proof of Prop. 3.1, "Define" should be "define"; also please define "ess inf". - In the proof of Theorem 4.2, I am a bit confused with line l.457: "the first inequality follows from adding a constraint on the pairs."

Questions

1. The next natural question is how poor the discretized systems can be. Are there any asymptotic guarantees on its quality, even under some non-zero approximation ratio? 2. Are there specific coherent metrics where the discretization could still be valid?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The authors have not included any limitation subsection.

Summary

The authors demonstrate that dynamic programming decompositions for CVaR and EVaR can be suboptimal, and show that VaR may not be subject to the same problems in MDPs of horizon 1.

Strengths

The paper provides some interesting observations conflicting with previous papers on CVaR and EVaR optimization in RL.

Weaknesses

While this paper makes some interesting observations about the decompositions of CVaR, EVaR, and VaR, it seems like an incomplete paper, without enough contributions meriting acceptance. The “dynamic program” presented in Section 5 seems far from implementable, with weak (if any) guarantees. For contrast, [Chow 2015] shows that the CVaR Bellman operator is a contraction with a unique fixed point, and also discuss how to discretize the space of $\alpha$ to make practical implementations possible. They also provide proof-of-concept experiments. The proposed VaR operator seems to face similar issues (e.g., with $\alpha$ being continuous), but the submitted paper appears to handle none of these points. It would be interesting to see the decomposition proposed in Theorem 5.2 translated into a policy learning algorithm, e.g., of the style of value iteration proposed in [Chow 2015], complete with theoretical analysis and empirical evaluation. Additionally, Theorems 5.1 and Proposition 5.3 appear to only hold for $T=1$ which is essentially a contextual bandit? While the authors state that results can be extended to $T > 1$ using “standard techniques,” I find that $T = 1$ is an unusual assumption in RL (for MDPs) and usually something that makes risk-sensitive RL much easier (because you don’t have to deal with stochasticity from transitions). In this light, it seems worth it to at least expand Section 5 for $T > 1$.

Questions

- In policy evaluation, will the proposed algorithm need to be able to handle continuous $\alpha$, and how can that be done? - Is it possible to learn a policy with $T > 1$, and what would the specific policy learning algorithm look like (in broad strokes)?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

yes

Summary

This paper investigates the effectiveness of decomposition approaches for solving risk-averse Markov Decision Processes (MDPs) with Conditional Value-at-Risk (CVaR), Expected Value-at-Risk (EVaR), and Value-at-Risk (VaR) objectives. The goal is to assess the validity and accuracy of these common decomposition techniques for risk-averse decision-making. Main contributions: Sub-optimality of CVaR and EVaR decomposition: The paper demonstrates that the widely used decomposition approaches for CVaR and EVaR objectives are inherently suboptimal, invalidating previous works. These methods involve a saddle-point gap during policy optimization, leading to incorrect results. As a result, practitioners should exercise caution when using these decomposition techniques for risk-averse MDPs. Optimal VaR decomposition: In contrast to the suboptimal CVaR and EVaR decompositions, the paper identifies the VaR decomposition as an optimal approach for both policy evaluation and optimization in risk-averse MDPs. The VaR decomposition does not suffer from the same saddle-point problem, making it a reliable method for risk-averse decision-making. Increased awareness and call for alternative approaches: The findings highlight the limitations of two traditional decomposition methods, CVaR and EVaR, and emphasize the need for scrutiny when using these decompositions. Researchers are encouraged to explore alternative approaches, such as parametric dynamic programs, to improve risk-averse decision-making in MDPs.

Strengths

Rigorous analysis: The main strength of the paper is its rigorous treatment of three decomposition approaches for risk-averse MDPs. Significant and clearly stated contribution for the field: The paper shows the sub-optimality of CVaR and EVaR decomposition methods invalidating several previous works on the topic. This finding is valuable as it warns practitioners about unknown limitations of these techniques in risk-averse decision-making. Optimal VaR decomposition: By identifying the VaR decomposition as an optimal approach for policy evaluation and optimization in risk-averse MDPs, the paper provides a practical solution to the limitations of CVaR and EVaR. Thus this VaR decomposition is a reliable alternative to these two methods. Encouraging further research: In light of the limitations faced by CVaR and EVaR, the paper calls for exploring alternative approaches, such as parametric dynamic programs. Clarity in presentation and methodology: The paper is well-written. It uses clear explanations, comprehensive mathematical analysis, and compelling illustrative examples.

Weaknesses

Limited set of approaches: Perhaps the main weakness of the paper is the limited set of (three) decomposition approaches being scrutinized. While the paper highlights the sub-optimality of CVaR and Expected Value-at-Risk EVaR methods, it does not compare a broader range of state-of-the-art techniques. This limitation makes unclear the extent to which VaR decomp Google Mapsosition can be considered optimal. I appreciate that it would not be possible, given length constraints and scope of the paper, to evaluate other baselines comprehensively. However, it would be valuable if the authors could mention other state-of-the-art techniques in a related works section, and whether they can say anything about them in relation to the approaches they investigated here. For instance, control as inference and active inference use the KL divergence as a decision-making objective (i.e., a belief-based reward function) which entails risk-averse behaviour, and which might be related to VaR [1,2,3]. Unclear scalability discussion: The paper does not extensively discuss the scalability of the proposed VaR decomposition concerning problem size or dimensionality. I appreciate that this might not be important for theoretically minded readers, however, since the paper has important implications for practitioners (i.e., widespread adoption of VaR) it would be nice to immediately know, via some discussion or suitable reference, how well this method scales as MDPs grow complex and large in applications. Limited generalization: The paper comprehensively addresses the setting of risk-averse MDPs. It would be nice to know whether the theoretical analyses presented here can offer some insights on more general problem classes like risk averse partially observable Markov decision processes (POMDPs). For example, has VaR been extended to risk averse POMDPs, and if so would you expected it to be optimal in this case? From the two points above, one of the main weaknesses of this paper is that it is not straightforward to infer to what extent VaR is a viable approach in a wide range of practical problems, and thus it is unclear to what extent the paper implies an optimal, promising in the near long-term approach to the risk-averse decision problem. In my understanding, this is the main point of broader impact in the machine learning community, so it should be addressed. Typos: l 136, l200 [1] S. Levine, ‘Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review’, arXiv:1805.00909 [cs, stat], May 2018, Accessed: Dec. 29, 2021. [Online]. Available: http://arxiv.org/abs/1805.00909 [2] L. Da Costa, N. Sajid, T. Parr, K. Friston, and R. Smith, ‘Reward Maximization Through Discrete Active Inference’, Neural Computation, vol. 35, no. 5, pp. 807–852, Apr. 2023, doi: 10.1162/neco_a_01574. [3] D. Hafner, P. A. Ortega, J. Ba, T. Parr, K. Friston, and N. Heess, ‘Action and Perception as Divergence Minimization’, arXiv:2009.01791 [cs, math, stat], Oct. 2020, Accessed: Nov. 07, 2020. [Online]. Available: http://arxiv.org/abs/2009.01791

Questions

Can the authors elaborate on their selection of the specific decomposition approaches used for comparison? Are there any reasons why these three approaches were chosen over others? Could the authors provide more insights into the computational complexity and scalability of the VaR decomposition method concerning the size and dimensionality of the risk-averse MDPs, either in a short discussion or references? Are there any notable challenges when applying this approach to large and more complex decision problems? As a broader point of interest, how significant is the choice of the risk level (alpha) in the performance and efficiency of the VaR decomposition method? Are there any guidelines on selecting appropriate alpha values based on a given problem characteristics? This is important to understand the robustness of this method in a new risky environment, a desideratum for any risk averse decision-making algorithm in high stakes applications, which relates to the broader impact of this work as hinted in the last point of the conclusion. Given that the paper focuses on risk-averse MDPs, are there any indications or early results on how the VaR decomposition approach and its optimality might generalize to other types of decision-making frameworks, such as partially observed problems?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

The paper does a good job at addressing its limitations insofar as it focuses on three specific approaches to risk averse decision making. The main limitation which has not been addressed, and which in my opinion should be addressed, is giving more context as to why this three approaches were chosen, or why is it is sensible to choose them, and mention the fact that there exist other state-of-the-art approaches, which need to be considered and comprehensively evaluated in the future, and which could serve as avenues for future research in addition to parametric dynamic programs, e.g., control as inference and active inference.

Thank you for these helpful clarifications and revisions

Thank you for your clarifications and intended revisions. The answers to my questions are helpful, and I believe that your intended revisions will strengthen the paper, help clarifying the paper's contribution and its broader impact, and make it more appealing to a broader audience.

Reply

I appreciate the authors for the reply. I have read it and will maintain the score.