Bayesian Risk-Averse Q-Learning with Streaming Observations

Summary

The paper develops a Bayesian risk-averse Q-learning algorithm to tackle the setting of Bayesian risk MDP, which uses Bayesian posterior to estimate the transition model and impose a risk functional to account for the model uncertainty. The claim is that the proposed algorithm learns a "risk-averse yet optimal policy", which has theoretical guarantee of strong convergence.

Strengths

The paper proposes an interesting formalization of an algorithm for Bayesian risks in MDP. The paper is scientifically sound and provides a few interesting results, among others with respect to the convergence (to the "optimal") in the context of infinite data. The paper explains why Monte-Carlo estimators are useful in practice and provides a few interesting theoretical properties. Numerical experiments provide illustrations of the theoretical analysis in the context of two relevant (small-scale) MDPs.

Weaknesses

Even though related work is overall well-discussed, the paper could be more clear about the novelty of the different parts (e.g. Theorem 2.2 and Theorem 2.3 seem relatively generic and even though I'm not an expert in the BRMDP setting, I believe close theorems exist in the literature). The notations and overall formalization might benefit from a few (minor) improvements to improve the readability (see additional comments and questions). Additional comments: - In Equation 1, $d_i$ and $p_i$ do not seem to be formally defined (even though we can guess what they refer to). - In Equation 1, \rho is used with a subscript that depends on a sampling from a Dirichlet posterior but \rho was introduced line 114 without any subscript (the meaning of the subscript might not be fully obvious). - line 97: $r$ is not defined (even though we can guess what they refer to) - line 108: (s,a) is not in math mode (italic). - line 109: "??" instead of a reference to the appendix.

Questions

Main question: - Theorems are mostly provided as fully original. What are the closest related theorems from the literature? - The inventory management problem is considered in two settings as can be read in the supplementary material. The second one is described as "(...) the demand depends on the current inventory level s. (...) we will consider the case where observations are insufficient to estimate the transition probability for every state-action pair". What is actually meant by that? And also, why are there two settings described in the supplementary material but only one in the main paper? Additional questions: - The abstract mentions the following: "The proposed algorithm learns a risk-averse yet optimal policy that depends on the availability of real-world observations." This seems unclear from the abstract because a risk averse policy will in general need make a tradeoff with the best expected return. Do you mean "risk averse policy that converges to the optimal one in the context of unlimited data"? - line 117, $\xi$ is defined as a probability distribution over $\mathbb R^n$, but is described as a "random vector taking values on $\mathbb R^n$". Can you clarify? - Line 123: Could there be some intuitions for the different parts of assumption 2.1? In particular Line 124-128 gives lightweight information about how it is slightly similar to the notion of coherent risk measure but that notion and the difference with it are not detailed. Why is sub additivity not included, why is 2.1.3 important?

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

3 good

Contribution

3 good

Limitations

Some limitations are provided.

Summary

This paper extends previous work on Bayesian Risk-averse MDPs (BRMDPs), an informed alternative to an ambiguity set in the infinite horizon setting. In doing so, the authors first present a nested BRMDP formulation for the state value function. Then, they show that difference between optimal value functions for BRMDP and the true MDP is bounded. Afterwards, the authors presented a multi-stage risk-averse Q-learning algorithm with periodic posterior updates and a Monte Carlo estimator for the proposed risk-averse bellman operators. Simple simulations are presented to verify the better performance as well as the lesser variance of the proposed infinite horizon BRMDP formulation. It should be noted that the Bayesian posterior and Risk functionals are well-defined and that the state and action spaces discussed in the paper are both finite. The work does hold merit, and the findings could be communicated to a larger audience through a conference like NeuRIPS.

Strengths

The paper is generally well-written: 1. The infinite horizon BRMDP formulation is novel and the accompanying recursive Bellman equations follow nicely. 2. Detailed proofs of the distance bound for the State function and the convergence analysis are provided. 3. Experimental results are discerned in a manner that relates directly to claims of risk aversion (smaller variances) and performance gains.

Weaknesses

1. Apart from the assumption of the availability of a behavioral policy to generate real-world data, the rules for updating the sample sizes appear to be a heuristic at best. (ref. Algorithm 1) 2. The Monte Carlo estimators for the Bellman operators, in addition to generating real-world samples to update the Bayesian posterior, will make the algorithm extremely slow. 3. The state and action spaces under consideration appear to be finite, thus limiting the evaluation to more demanding experimental setups.

Questions

1. In line 180, page 5, section 2.5, it is stated that a batch n(t) of observations is available. What is the assumption for the smallest batch size? 2. What is the reasoning behind using the Monte Carlo estimator? 3. Why is the benchmark Q-Learning on the true environment not provided in the experimental results? 4. In line 201, page 6, section 3.1, what does i.i.d sampling of probability distributions p_i mean? 5. What is the computational overhead of the proposed methodology, and how well will it scale?

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

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The authors addressed one limitation of their work, i.e., that the behavior policy which generates the real-world data is assumed to be given. In terms of societal impact, there would be no potential negative impact of this work according to the considered ethical criterion.

Summary

The paper adopts the Bayesian risk MDP (BRMDP) formulation to train a reinforcement learning agent to be robust against model uncertainty. Infinite-horizon discounted value function of BRMDP is defined by a nested formula, and properties for the value function are derived with VaR and CVaR being the risk functional. Furthermore, Q-learning algorithms for BRMDP are proposed using finite-sample estimators for the Bellman operator, and they are shown to converge to the optimal Q-function under some typical assumptions. Numerical experiments for the proposed risk-averse algorithm is shown and compared with its risk-neutral counterpart and other robust RL algorithms.

Strengths

- The paper defines infinite-horizon discounted value for BRMDP, and Theorem 2.3 provides bounds on the difference between the value function of BRMDP to the value function of the true MDP. It shows that the risk-averse version will converge to the true value function as the number of observed transitions grows. - Q-learning algorithms for BRMDP are proposed using finite-sample estimators for the Bellman operator with either VaR or CVaR as the risk functional. The Q-learning algorithms are shown to converge to the optimal risk-averse Q-function in a data-conditional sense, and this further implies its convergence to the true optimal Q-function given infinite amount of observations. - Numerical experiments for the proposed risk-averse algorithm is shown and it outperforms two existing robust Q-learning algorithms.

Weaknesses

- The BRMDP formulation is motivated to provide robust policies, but there is no discussion on what does "robustness" mean in the context of this paper. The only place some kind of robustness measure is mentioned is in the numerical experiments where the variations of performance is brought up in the discussion. But there is no proper definition for the variations and there is only very little discussion. - Theorem 2.3 is claimed to show the trade-off between robustness and conservativeness, but it is hard to talk about robustness without any definition for robustness. In some sense, the upper bound has the risk level parameter $\alpha$ which may be viewed as a kind of robustness level, but no analysis is provided on how the risk level $\alpha$ would affect the behavior of the risk-averse policy and how $\alpha$ would improve the robustness of the performance in some sense.

Questions

- Can we define the robustness using some metric like performance variations? How does the risk-averse policy compared with other policies in terms of some robustness metrics? - It is shown in Theorem 2.2 that BRMDP has a unique optimal value function, but it's not clear wether the random data-conditional optimal Q-function in Definition 4.1 exists. Do we have existence for the data-conditional optimal Q-function following similar arguments?

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

2 fair

Contribution

3 good

Limitations

limitations are adequately addressed in the paper.

Summary

The authors propose a novel multi-stage Bayesian risk-averse Q-learning algorithm to learn the optimal policy with streaming data. A central difference from existing methods is that they attach a risk functional on the future reward at each stage (nested), rather than just once on the total reward. To arrive at unbiased estimators for the Bellman operators, the authors resort to Monte Carlo. The convergence of the Q-learning algorithm is theoretically shown. The authors include empirical investigation of their method on two toy tasks and show that their method is more flexible than some other worst-case criteria.

Strengths

The authors propose a technically rigorous addition to the the BRMDP literature. Their empirical results clearly show the utility of per-step risk functionals, and their extensive theoretical results include a number of - technically involved - contributions. The centrepiece here is certainly the proof of Theorem 4.3, i.e. the uniform convergence of the Bellman operator estimator. The paper is well-written and structured, and the resulting method has the potential to generate impact on the safe RL community.

Weaknesses

While the paper convinces through its soundness and wealth of theoretical contributions, the empirical evaluation could feature more (and more complex) environments. A fundamental weakness seem to be limitations in applying the authors' method to high-dimensional data streams. For example, one weakness is that the authors do not extend their results to Q-learning with non-linear function approximation. I believe this could be done fairly easily, and would lay foundations for their method to be used on high-dimensional data streams. Another weakness to address when moving to high-dimensional data streams seems the relative sample-inefficiency of MC Bellman operator estimators (an empirical study of how efficient their proposed estimator is for high-dimensional data streams would be insightful).

Questions

My questions concern possible extensions of this work, which I do not deem required for acceptance. * Do you think that a more sample-efficient way (as MC is unbiased but generally not efficient) of arriving at unbiased Bellman operator estimators could be attained, e.g. using variational inference? This seems to be required for problems featuring high-dimensional data streams. * The authors note that an extension to active sampling settings would be interesting. This would seem to require "deep exploration", necessitating a more fundamental Bayesian RL approach [1]. Do you see an easier way to make progress in this direction? [1] Bayesian Bellman Operators, Mattie Fellows et al, NeurIPS 2021

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

4 excellent

Limitations

The authors have adequately addressed the limitations of their work, although I would have liked to see a discussion of how their method might scale to high-dimensional data streams. I do not see any negative societal impact arising from this work.

Thanks for the clarfifications

Thanks for the clarifications, I keep my score of 7 unchanged.

Rebuttal reminder

Dear reviewer, We are grateful for the opportunity to address your valuable comments and concerns and will greatly appreciate your feedback in either discussions and scores. If you have further questions, please let us know so we can answer it before the end date of discussion on August 21 1pm EDT. Best regard, Authors