Beyond Average Return in Markov Decision Processes

Summary

The paper investigates general functionals of the distribution over returns in three situations: 1) For policy evaluation, the authors prove some error bounds for a given distributional RL algorithm. 2) For planning, the authors exhibit the functional form that is optimizable via dynamic programming. 3) For reinforcement learning, they provide a Q-learning algorithm when the functional is linear or exponential

Strengths

The paper investigates an interesting question, which is useful for sequential decision-making with more sophisticated decision criteria. The writing is generally quite clear.

Weaknesses

The obtained error bound for policy evaluation seems to be very loose, as also suggested by the experiments. Can we say anything about the tightness of this bound? The novelty of some of the obtained results seems to be limited: 1) How different is the known result about Bellman closedness and the new result about Bellman optimizability (Theorem 2)? Isn't the former property a necessary condition for the latter? 2) Regarding the proposed Q-learning algorithm, the linear case seems to be trivial. For the exponential case, how different is the proposed update compared to Borkar's? The paper should be checked for typos (see below for some of them).

Questions

See questions above. Some minor issues: - line 52: p_h -> p_h^a(x, \cdot) and R_h -> R_h(x, a) - line 74: p_{h+1}^a(s, \cdot) -> p_{h+1}^a(x, \cdot) - line 95: the definition of \mathcal P_Q(\mathbb R) should include the condition in (5) - line 96: W_1 should be defined here - line 209: m - line 222: \eta vs \eta^* - line 227: missing /extra word? - line 239: the other von Neumann-Morgenstern axioms are not needed? - line 269: sections addresses - line 271: linear of exponential

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Not applicable

Summary

This paper considers the problem of using distributional reinforcement learning to perform policy evaluation and planning with more general classes of reward functionals than those typically considered in standard Markov decision processes and RL. The paper focuses in particular on dynamic programming methods for obtaining distributional Q functions based on distributional Bellman operators, as well as how to use these methods for planning with the resulting distributional Q functions. The main contributions of the paper are twofold: (1) when performing distributional policy evaluation on general utilities using a certain kind of distributional Q function approximation scheme, worst-case bounds in terms of Wasserstein distance of the approximation from the true distributional Q function are provided; (2) when performing planning using distributional Q functions, a new notion of "Bellman optimizability" of reward functionals is given, and it is shown that the only Bellman optimizable reward functionals are the class of exponential utilities. It was previously known that standard (i.e., not distributional) dynamic programming methods (see, e.g., lines 213-214) can be applied to solve planning problems with general utilities, so contribution (2) provides a negative result suggesting that distributional RL methods, though providing a very general framework for performing evaluation and planning via dynamic programming, are not strictly necessary to solve the class of problems to which they are theoretically suited.

Strengths

Overall, the paper is well-written and the results add clarity to the distributional RL landscape that is likely to be of interest to the community. Regarding significance, contribution (1) outlined in the summary given above is potentially useful for a wider range of utilities than previously considered, but the results appear to be straightforward extensions of existing results (see C.1, C.2 in the appendix). The main result of the paper is instead contribution (2), provided in the form of Theorem 2 (lines 248-250). This result delimits the applicability of distributional dynamic programming to classes of utilities that can be handled using non-distributional techniques, suggesting that the primary usefulness of distributional RL methods may be experimental instead of theoretical. It is refreshing to see an ML paper making an effort to soberly clarify the mathematical limits of a particular subfield of ML research. The proof of this result (see D.2) appears to boil down to first constructing a differential equation based on the integrand of the utility, then solving to show that the integrand must correspond to an exponential utility. The proof is not long, but the idea is clever.

Weaknesses

I have two main concerns regarding the paper: * Contributions (1) and (2) are somewhat disjointed. On the one hand, (1) provides reassurances that Algorithm 1 enjoys approximation bounds for a wide variety of different utilities. At the same time, (2) undermines this result by showing that planning using the resulting distributional Q functions is only theoretically meaningful for a much-restricted subset of those utilities. Some clarification of the implications of (2) for (1) would be helpful. * In the proof of Theorem 2, it is assumed that the utility integrand $f$ is twice-differentiable and $f'(x) \neq 0$, for all values of $x$. This assumption is critical to Theorem 2, thus to contribution (2), and thus to the overall contribution of the paper. It is stated on lines 516-517 that this assumption "could be proven through long and fastidious analysis that is beyond the scope of this article", yet no indication of how this might be accomplished is provided. Given its importance to the paper, I argue that this is within scope of the article, so that a proof sketch or at least a convincing explanation of why this assumption holds is needed.

Questions

* Given Theorem 2, what is the main usefulness and impact of the approximation bounds provided in section 3? * Why is Bellman optimizability (Definition 2, lines 221-222) the right notion of what it means for a problem to be solvable using distributional RL? Are there incompatible notions of optimality that might invalidate Theorem 2? If not, why not? * Why does the assumption regarding the utility integrand $f$ on lines 516-517 in the appendix hold? * It is mentioned that policy stationarity is disrupted in the discounted setting on lines 289-290. Can you provide references ensuring sufficiency of stationary policies in the setting you consider?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

3 good

Presentation

3 good

Contribution

3 good

Limitations

Aside from the weaknesses and questions above, the authors have adequately addressed the limitations of this work.

Summary

Classic RL maximizes the (discounted) cumulative reward in Markov Decision Processes (MDPs). This paper studies more general functionals of rewards, such as generalized means. These more general functionals are useful to consider for certain applications, such as those with safety concerns. Furthermore, the study of these more general functionals has been not well understood in the literature. For finite-horizon prediction problems, this paper 1) argues that only generalized means of rewards can be obtained exactly using dynamic programming and there is no need to resort to learning the entire distribution of return (I am confused about this part, see Questions), and 2) provides an upper bound of estimation error for utility functionals, which are more general than generalized means, when approximated with Quantile Distributional RL. Both 1) and 2) mirror Rowland et al.'s (2019) results, which were developed concerning the discounted setting. The most important result is for finite-horizon control problems. This paper shows that the only Bellman optimizable functionals (those that can be optimized by applying Dynamic Programming to the distribution of return) are generalized means. Combined with a previous result showing that generalized means can be solved using dynamic programming (no distribution involved), this result shows that the only functionals that are optimizable by Distributional RL can be optimized by Dynamic Programming, which is a much more efficient algorithm.

Strengths

The problem that this paper studies is an important one. The main result, which shows that the only functionals that are optimizable by Distributional RL can be optimized by Dynamic Programming, is remarkable.

Weaknesses

The writing of the paper needs improvements. Specifically: 1) right now, the presentation of the paper is driven by the technical results that it wants to show, rather than the messages that it wants the readers to know. The paper presents an important result about Distributional RL: the only functionals that are optimizable by Distributional RL can be optimized by Dynamic Programming. As the authors highlighted in line 260, this result is the most important one and it narrows down the avenues to explain its (distributional RL) empirical success (line 310). However, this result is not outspoken throughout the paper, until an inconspicuous discussion on page 8. Why not say your most important result in the Abstract and the Introduction sections? 2) The notations given background section need to be clearly defined: the notation (z_i)_i needs to be defined. \delta is not defined (line 96). \mu is not defined (line 97). F_\mu is not defined (line 98). what is \eta in line 100? \Delta_\eta is not defined in line 101. Line 124: U_f is not defined. 3) typos: extra m at the end of line 209 line 184: should be "see Figure1 (left)" line 199: should be "Figure 2 (left)" the order of the two subfigures in Figure 2 would better be reversed in accordance to the texts.

Questions

"Much of the existing theory is based of discounted MDPs, but many recent efficient RL algorithms with strong guarantees are for finite-horizon, undiscounted setting" What kind of theory do you mean for discounted MDPs? Could you give examples that illustrate this argument? Could you point to the result by Rowland et al. (2019) that gives equation 6? Note that other parameterizations exist but are less practical. Could you explain why is this true or refer to other works that show that this is true? Line 122-123: when lambda > 0, the utility is higher for Gaussian distribution with a larger sigma (higher variance), so isn't this case risk-seeking? Line 124: you don't need to mention this axiom at this point. I have been wondering why I need to know this until I found it being used in section 4. Line 152 is confusing to me: do you mean that for any L >= 1, statistics corresponding to the first L+1 moments form a Bellman closed set? Line 152: Theorem 4.3 by Rowland et al. (2019) only mentioned moment functionals but not exponential functionals. Furthermore, although you prove in A.3 that sets of multiplication of moments functionals and exponential functionals also form a Bellman closed set in the finite horizon setting, you didn't show that these are the only families of functionals that form Bellman closed sets in this setting. The footnote on page 5: how can the support of return be -h + 1 given that all rewards are non-negative? Line 215: is the question open for utilities other than exponential ones for control problems? Line 221: why define Bellman optimizability instead of extending the definition of Bellman closeness to control problems? In addition, it is weird to define a quantity, which you want to optimize, using an algorithm that optimizes it. Do you see other ways that make this definition without resorting to a particular algorithm? Line 241: why does this result narrow down the family Bellman optimizability functionals to utilities? I mean, literally. Section 5: why would we want to see a new algorithm without any theoretical/empirical study of the algorithm?

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

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

4 excellent

Limitations

N/A

Summary

This paper addresses

Strengths

1. The method is very well-presented, with notations, terms and algorithms put in a very clear and understandable fashion. They are introduced without fancy names and terms, which is great. 2. The questions are well-stated and addressed respectively from a theoretical perspective, and they are fundamental problems. 3. The significance of contribution is good. It provides a good starting point to address the statistical functional evaluation problem.

Weaknesses

1. Some statements in the propositions lack references to earlier works, such as quantile functions an CVaR (metric). 2. The learning environment description is lacked. 3. The limitations, potential societal impacts and ethical concerns, and future work are lacking.

Questions

My suggestions has been listed in weaknesses, which I will paraphrase here: 1. Please fix grammatical errors and add proper references on early works, especially for the sections with propositions. 2. Please connect your work to more practical applications. I know it might be hard to conduct experiments as additions to this paper, but some discussions would be helpful. 3. Please give more details about the experiments on functional distance calculation. 4. Most importantly, please add descriptions on potential limitations, concerns, and societal impacts about the work at the very last of the paper.

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

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Although since it is a theoretical paper, I do not think an external ethical review is needed, the limitations, potential societal impacts and ethical concerns, and future work are lacking. Authors may address it later if applicable.

Response

Thank you for the rebuttal. I am still not clear about the relation between Bellman closedness and Bellman optimizability. Should Bellman close functional necessarily be Bellman optimizable?