Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a method to optimize a CVaR return in Bayes-adaptive MDPs. The risk considers both the aleatoric and epistemic uncertainty in MDP, and leans a risk-aware policy by optimizing the CVaR return.
main_review: The main idea of this paper to convert the CVaR optimizing problem to a stochastic game. The authors introduce an adversary to minimise the return, so that the bad transitions can be learned more frequent. Such adversarial perturbations is applied in prior functions and transition functions to address two kinds of uncertainty. Prop 1 poses that such objective learns a cvar policy. Overall, I think this paper is well motivated, while the presentation is a bit hard to follow and need to be improved.
limitations_and_societal_impact: 1. One of my concern is why the cvar objective is combined with MCTS? MCTS is a complex model-based methods and combines several components. Such setting also makes the experiments do not have more standard benchmarks. Can this method be used in simpler model-based setting? 
2. About the theory, I wonder if the adversary idea is also applicable in model-free RL methods? For example, learning a risk-aware policy in standard actor-critic methods?
3. For estimating the aleatoric uncertainty and epistemic uncertainty, there are a lot of other methods in RL for exploration and risk learning, e.g., bootstrap for epistemic uncertainty, distributional return/Q for aleatoric uncertainty. Althought these methods are mainly discussed in model-free settings, e.g., Bootstrapped DQN (https://arxiv.org/abs/1602.04621), OB2I (https://arxiv.org/abs/2105.06022), IDS (https://arxiv.org/abs/1812.07544), IQN (https://arxiv.org/abs/1806.06923), I think these methods should be discussed in related works.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents a method for optimizing CVaR in a BAMDP setting which captures both intrinsic and parametric uncertainty. They show that optimizing CVaR in a Bayesian setting is equivalent to finding a stable equilibrium for an adversarial two player game. In addition they present an implementation of their algorithm on the basis of MCTS and show that it is able to achieve better returns at different risk levels than comparable baselines.
main_review: The paper is clearly written and addresses its main topic succinctly and thoroughly. The derivations and proofs appear correct after checking them. The motivation is clearly stated and the algorithm is well developed from there.

Criticism/Suggestions for improvement:

Theoretical part:
The authors choose a static risk setting but do not discuss why. It would be good to elaborate on this design choice, especially since it seems to make the adversarial game more difficult (since the adversary needs to track the budget). (please provide in rebuttal)

MCTS part:
One big drawback of the method that is also discussed by the authors is the poor scalability of their findings. Both a full Bayesian approach to RL and CVaR optimization on its own are hard problems with known scaling issues, combining them seems like a huge computational challenge. This is supported by the experiments which only address very small domains. A longer discussion of potential approximations (several were developed as baselines) would have improved the applicability of the paper. (improvement suggestion)

Related to above it would have been interesting to see how the found solutions of the MCTS approach scale with growing computational budget. How does the error in the two player game evolve with more computational resources and data? (improvement suggestion)

The authors stress several times that their method is able to take into account both parametric and intrinsic uncertainty, yet the experiments do not separate this. It would be very instructive to add two sets of experiments, one where it is vital to be robust towards parametric and one where intrinsic uncertainty is challenging and compare the approach and the baselines on these to show how the method addresses these. While a baseline for this was used, it is unclear whether the difference in performance is due to the difference in methodology or implementation. (if possible, please provide in rebuttal)

Another question is how stable the minmax optimization in this setting is. Many recent paper (i.e. GANs, robust MDP formulations) show that two player optimization is a very difficult topic. Are similar concerns valid here? I would encourage the authors to investigate the stability of the equilibria found with their algorithm either in the practical algorithm or the theoretical derivation. (improvement suggestion)

Conclusion

The paper presents a good derivation of the main contribution, the Bayes adaptive CVaR optimization. While there are several concerns and suggested improvements to the paper, I think that overall the presented submission should be accepted, since some of the additional questions might be out of scope for this paper and even without them, the paper is interesting, novel and clear.

Minor comments:


limitations_and_societal_impact: Limitations regarding scalability were addressed, albeit only shortly. The paper has no discussion of societal impact, but since it addresses theoretical results in RL, this is acceptable.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors introduce the problem of optimising the CVaR in the context of Bayes-Adaptive MDPs, in other words optimising a particular risk metric when faced with uncertainty about the transition dynamics in a Bayesian sequential decision making context. The paper then proposes an algorithm to tackle this problem (reformulated as a stochastic game), an online search technique (called RA-BAMCP) based on MCTS in the augmented state space with an adversary to select the transition outcomes within constraints. The approach is demonstrated on simple domains.
main_review: The paper deals with an important but under-explored problem in RL, risk-sensitive decision-making under uncertainty. Different complex frameworks are combined in this paper (CVaR, BAMDPs, etc.), yet I found the writing to be clear and the paper was pleasant to read. 

One novel contribution (as far as I can tell) is to consider the CVaR optimization in the Bayes-Adaptive setting, and the stochastic game formulation of the problem. The formal problem is exposed with enough precision but, to improve the presentation, I think some didactic example(s) would be useful to provide intuition about the optimal solution in such a setting, and generally make the paper more accessible.

The other contribution is the planning algorithm and the experimental work to demonstrate its efficacy. The use of Bayesian optimization to control the adversary in the search seems reasonable here, and the BAMCP integration makes sense. The experimental domains are simple but probably quite challenging to solve in this BAMDP+risk setting (at least the car nav domain). I was satisfied with the chosen baselines, they give a good coverage for what other methods would do, and the experimental results make sense here. This is a good sanity check that the algorithm is indeed able to optimize the proposed problem formulation, even if the current solution might not be readily scalable to much bigger domains.

Some questions:
- The \delta perturbation on the prior seems to disappear when introducing the stochastic game formulation (sec 4.2). I’m understanding that it’s because \zeta is now perturbing directly the BAMDP transition which includes the prior, and this is explained by line 225-229, but perhaps this is worth expanding a bit and mentioning before in 4.2. 

- L121, I think the min should be a max in the definition of V(s,y). This probably comes from the Chow et al. paper which uses costs instead of rewards in your case?

Extra:
- I could be wrong but I think there might be a variant of RA-BAMCP with root sampling that could work. Couldn’t you do a different perturbation for the sampling at the root from the adversary and then do regular MDP transition perturbations as in Prop 1? Haven’t completely thought this through, and I understand this might be left for future work.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The work addresses risk-aversion in Bayes adaptive MDPs. The problem is formulated in terms of CVaR optimisation and later reformulated as a zero-sum stochastic game. An algorithm is proposed using monte-carlo tree search in line with other works using Bayesian optimization for the adversary's continuous actions. Experiments are conducted in simple domains to validate the algorithm.

main_review: Main review. Please provide a thorough review of the submission, touching on each of the following dimensions:

Originality: 
The paper proposes a CVaR formulation of  Bayes-adaptive MDP. The theoretical novelty here mainly comes from translating the problem to a minimization over measures (Prop 1) and then to a stochastic game (Prop 2). As far as I know, this is novel and by itself has value to the community.  

The proposed algorithm is a MCTS algorithm that searches / plans over actions, chance nodes and adversary nodes. Multi-player versions of MCTS are not new. Additionally, the authors use progressive widening to handle the large action space of the adversary (continuous). This is also already existent in the literature as cited by the authors. It could be that the combination of both techniques is new (I am unsure about this) albeit somewhat trivial.  Finally, the authors use Bayesian optimization for alleviating the problem of finding good proposals for the progressive widening. Again, I believe this addition is somewhat trivial, but I understand that this is what makes the algorithm achieve high performance. So overall, here I see a combination of well-known techniques used in harmony to solve the problem at hand.

Quality: 

The proofs in the appendix are very well explained and easy to follow. I think the proofs are of quality and technically sound. 

The experimental results are conducted in toy domains. I understand that the Bayes -adaptive MDP problem is hard, so I guess this is fine given the theoretical contributions. I found the results a bit difficult to follow and interpret. However, given enough time I think one can parse and interpret the results. The results suggest that the proposed algorithm is on par or better in terms of performance and time compared to the other variations. This conclusion is only obtained from a couple of environments though.


Clarity: 

Most of the paper is very well written. A bit more effort could have been devoted to the result section.  All details provided seem sufficient to reproduce the results.

Significance: 
I think the problem of risk-sensitivity in Bayes adaptive MDPs is very relevant for deploying general-purpose AI applications. Management of risk is important for deployment, and adaptive agents is crucial for achieving flexible AI tools that can solve many problems. As such, the domain of study seems to be significant. Additionally, the theory might inspire researchers to takle the problem in a different way. The algorithm seems complex to implement (Bayesian optimization + MCTS + extended state spaces etc.) so it might not have huge adoption.



limitations_and_societal_impact: The only limitation that is stated is about the root sampling. A more thorough limitations sections would be useful.
review_title: null

Meta-review: This paper proposes a method to optimize a CVaR return in Bayes-adaptive MDPs which captures both intrinsic and parametric uncertainty. Interestingly, the paper shows that optimizing CVaR in a Bayesian setting is equivalent to finding a stable equilibrium for an adversarial two player game. The approach is demonstrated on simple domains
This is an important problem in RL: risk-sensitive decision-making under uncertainty. The paper introduces a methodological perspective which could lead to more work both in terms of modelling and newer empirical work. However the paper is limited in its empirical scalibility, and the writing needs to be imprvoed to clearly convey what is being done without speculation.  
The AC agrees overall reviewer consensus that this is an interesting advance for the community which is under-explored hence is being recommended for acceptance, but the draft needs significant improvement. 
Decision: Accept (Poster)