Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach
In this paper we address the problem of decision making within a Markov decision process (MDP) framework where risk and modeling errors are taken into account. Our approach is to minimize a risk-sensitive conditional-value-at-risk (CVaR) objective, as opposed to a standard risk-neutral expectation. We refer to such problem as CVaR MDP. Our first contribution is to show that a CVaR objective, besides capturing risk sensitivity, has an alternative interpretation as expected cost under worst-case modeling errors, for a given error budget. This result, which is of independent interest, motivates CVaR MDPs as a unifying framework for risk-sensitive and robust decision making. Our second contribution is to present an approximate value-iteration algorithm for CVaR MDPs and analyze its convergence rate. To our knowledge, this is the first solution algorithm for CVaR MDPs that enjoys error guarantees. Finally, we present results from numerical experiments that corroborate our theoretical findings and show the practicality of our approach.
The paper shows that a CVaR objective has an alternative interpretation as expected cost under worst-case modeling errors, if modeling errors are bounded by a budjet, bounding their product.The paper also introduces an approximate value iteration algorithm for CVaR MDPs, which is to the best of their knowledge the first solution to CVaR MDPs with convergence error guarantees, and the first algorithm to approximate globally optimal policies for CVaR MDPs. Points that require improvement are:  (1) While proofs can be found in the supplementary material, it   seems necessary to have at least proof sketches inside the paper,   especially given that one of the two main contributions of the paper   is the proof of proposition 1. (2) The paper heavily relies on an error budget constraint that     seems non-intuitive/non-realistic to me. It would be good to     explain whether this error-budget just makes the math easier, or     does it also have a realistic interpretation. (3) Experiment with a more complex domain could strenghten the pThe paper is of high-quality, and very well-presented.The paper provides significant insight on the connection between risk-sensitivity and robustness, as well as a practical algorithm for discrete state/action CVAR MDPs. Robust MDPs are an important research problem, and the paper makes progress towards better understanding and solving them.Detailed comments by order of appearance: ========================================= - line 39 'worst-case scenario' - what does it mean: worst-case cost under worst-case parameters? or expected-cost under worst-case parameters?- line 47 - why purturbing only transition probabilities, and not reward as well? would your result hold with reward purturbation? Some clarification is needed here, and possibly in the abstract.- line 79 - 'compute globally optimal' - since your algorithm is an approximate VI, wouldn't it be more accurate to say "approximate globally optimal..." and mention the dependence on interpolation resolution?- line 119 'our results easily generalize' - if they indeed generalize, it would be good to briefly explain how at a later section of the paper.- line 122 it should be H x A x X - line 128 you use Z_t for C(x,a) - please briefly clarify the connection explicitely- line 144 'worst-case expected ... in presence of worst-case' => 'expected ... in presence of worst-case' Also, could you relate 'expected reward under worst-case purturbation'to 'worst-case reward under worst-case purturbation' and possibly toto 'worst-case reward under expected purturbation'?- line 148 - (x_0...x_T) - it's not clear if you include actions in the trajectory, and if not, why not (later it becomes clearer when you use a deterministic, fixed policy)- line 151 - why (x_0...x_T) starting from x_1, especially given that cost is C(x,a)?- line 165 - the error budget seems uninutitive to me. Beyond the fact that it's not clear why errors should be bounded by a budget, this specific form of budget which bounds the product of errors seem uninutitive.Other than helping the math, does this come in realistic contexts? if yes, could you demonstrate?Also does your algorithm needs to know the budget (\eta) in advance? if not, what happens when: the assumed budget is smaller than the actual errors? if yes, is there a way to find a budget (upper-bound) efficiently in the presence of the exponential number of possible error combinations?Also, it's not clear to my why bounding the delta product from above bounds the errors: very small deltas (e.g. delta=0) applied to 'good' transitions may be as bad - don't they? line 166 - "states that the worst cannot happen at each time" - it sounds more accurate to say "*can* state that the worst...", since if the budget is large enough, the worst can happen at each time- While proofs can be found in the supplementary material, it seems necessary to have at least proof sketches inside the paper, especially for proposition 1, andespecially given that some proofs are part of the main claimed contributions of the paper. - line 177 - if you claim the comparison is 'instructive', it seems appropriate, to guide the reader and provide a brief explanation to what is instructive in the comparison.- Theorem 2: it might add to clarify if 'Z' is replaced by something line \mathcal{Z}_t- experiments:  - The experiments verify that your algorithm behaves as expected with   respect to risk and model errors on a grid world example. This is   good as a first step, but it would be better verify your algorithm   on a more complex domain.  - it seems that you built the obstacles in a way that the length of   the optimal path for any given (increasing) safety level is   increasing. It would be good explicitely clarify that (I didn't find   a mention of that in the paper).  - initially it confuses that the obstacles are yellow, given that the   value function is also yellow in parts - it seems like obstacles have   high value  - shouldn't M be negative (since your plotted value function has   negative values)