Risk-Averse Bayes-Adaptive Reinforcement Learning
Authors: Marc Rigter
Bruno Lacerda
Nick Hawes
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
planning
model-based bayesian reinforcement learning
risk

Abstract: In this work, we address risk-averse Bayes-adaptive reinforcement learning. We pose the problem of optimising the conditional value at risk (CVaR) of the total return in Bayes-adaptive Markov decision processes (MDPs).  We show that a policy optimising CVaR in this setting is risk-averse to both the epistemic uncertainty due to the prior distribution over MDPs, and the aleatoric uncertainty due to the inherent stochasticity of MDPs. We reformulate the problem as a two-player stochastic game and propose an approximate algorithm based on Monte Carlo tree search and Bayesian optimisation. Our experiments demonstrate that our approach significantly outperforms baseline approaches for this problem.

Risk-Averse
Bayes-Adaptive Reinforcement Learning
Mare Rigter
Bruno Lacerda
Oxford Robotics Institute University of Oxford mrigter@robots. ox ac. uk
Oxford Roboties Institute
University of Oxford
brunodrobots. ox ac
Nick Hawes
Oxford Roboties Institute University Oxford ni nickhOrobots.com ox. ac. uk
Abstract
In this work, address risk-averse Bayes-adaptive reinforcement learning. We pose the problem of optimising the conditional value at risk (CVaR) of the total return in Bayes- adaativee Markov decision processes (MDPs). We show that policy optimising CVaR in this setting is risk-averse to both the epistemic uncertainty due to the prior distribution over MDPs, and the aleatoric uncertainty due the inherent stochasticity of MDPs. We reformulate the problem as a two-player stochastic game and propose an approximate algorithm based on Monte Carlo tree search and Bayesian optimisation. Our experiments demonstrate that our approach significantly outperforms baseline approaches for this problem.
1 Introduction
In standard model-hased reinforcement learning (RL), an agent interacts with an unknown environ- ment to maximise the expected reward (42). However, for any given episode the total reward received by the agent is uncertain. There are two sources of this uncertainty: the epistemic (or parametric) uncertainty due to imperfect knowledge about the underlying MDP model, and aleatoric (or internal) uncertainty due to the inherent stochasticity of the underlying MDP (20). In many domains, we wish find policies which are risk-averse to both sources of uncertainty.
As an illustrative example, consider a navigation system for an automated taxi service. The system attempts minimise travel duration subject to uncertainty due the traffic conditions, and traffic lights and pedestrian crossings. For each new day of operation, the traffic conditions are initially unknown. This corresponds epistemic uncertainty over the MDP model. This uncertainty is reduced as the agent collects experience and learns which roads are busy or not busy. Traffic lights and pedestrian crossings cause stochasticity in the transition durations corresponding to alcatoric uncertainty. The alcatoric uncertainty remains even as the agent learns about the environment. A direct route, i.e. through the centre of the city, optimises the expected journey duration. However, occasionally this route incurs extremely long durations due to some combination of poor traffic conditions and getting stuck traffic lights and pedestrian crossings. Thus, bad outcomes can be caused by combination of both sources of uncertainty. These rare outcomes may result in unhappy customers for the taxi service. Therefore, we wish to be risk-averse and prioritise greater certainty of avoiding poor outcomes rather than expected performance. To ensure that the risk of a bad journey is avoided, the navigation system must consider both the epistemic and the aleatoric uncertainties.
In model-based Bayesian RL, belief distribution over the underlying MDP is maintained. This quantifies the epistemic uncertainty over the underlying MDP given the transitions observed far.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The Bayesian RL problem can be reformulated as a planning problem in a Bayes-Adaptive MDP (BAMDP) with an augmented state space composed of the belief over the underlying MDP and the state in the underlying MDP [12].
In this work, we address risk-averse decision making in model-based Bayesian RL. Instead of optimising for expected value, we optimise risk metric applied to the total return of the BAMDP. Specifically, we focus on conditional value at risk (CVaR) [34]. The return BAMDP is uncertain due to both the uncertain prior belief over the underlying MDP, and the inherent stochasticity of MDPs. By optimising the CVaR of the return in the BAMDP, our approach simultaneously addresses epistemic and aleatoric uncertainty under a single framework. This is in contrast with previous works which have generally considered risk- aversin to either epistemic or aleatoric uncertainty.
We formulate CVaR optimisation in Bayesian RL as a stochastic game over the BAMDP against an adversarial environment. Solving this game is computationally challenging because the set of reachable augmented states grows exponentially, and the action space of the adversary is continuous. Our proposed algorithm uses Monte Carlo tree search (MCTS) to focus search on promising areas of the augmented state space. To deal with the continuous action space of the adversary, we use Bayesian optimisation to expand promising adversary actions. Our main contributions are:
Addressing CVaR optimisation of the return in model-based Bayesian RL to simultancously mitigate epistemic and aleatoric uncertainty.
An algorithm based on MCTS and Bayesian optimisation for this problem.
To our knowledge, this is the first work to optimise a risk metric in model-based Bayesian RL to simultaneously address both epistemic and aleatoric uncertainty, and the first work to present an MCTS algorithm for CVaR optimisation in sequential decision making problems. Our empirical results show that our algorithm significantly outperforms baseline methods on two domains.
2 Related Work
Many existing works address aversion to risk stemming from either epistemic model uncertainty or alcatoric uncertainty. One of the most popular frameworks for addressing epistemic uncertainty is the Robust or Uncertain MDP 17 26
47 which considers worst-case expected value over a set of possible MDPs. Other works address epistemic uncertainty by assuming that a distribution over the underlying MDP is known. One approach is to find policy which optimises the expected value in the worst K% of parameter realisations [1] Most related to our work is that of Sharma et al. [38] which optimises a risk metric in the Bayesian RL context where the prior is a discrete distribution over a finite number of MDPs However, all of these existing works marginalise out the aleatoric uncertainty by considering the expected value under each possible MDP. In contrast, we optimise CVaR of the return in the Bayesian RL setting to address both epistemic and aleatoric uncertainty.
Conditional value at risk (CVaR) 34 common coherent risk metric which has been applied to MDPs to address alcatoric uncertainty. For an introduction to coherent risk metrics, see (2] In this paper, we consider static risk, where the risk metric is applied to the total return, rather than dynamic risk, where the risk metric is applied recursively 43). For this static CVaR setting, approaches based on value iteration over an augmented state space have been proposed 3 g 32]. Other works propose policy gradient methods to find a locally optimal solution for the optimisation of CVaR 4 6 7
45 46), or general coherent risk metrics 44. These existing approaches all assume the agent has access to the true underlying MDP for training/planning. and optimise the CVaR in that single MDP. In our work, we address the model-based Bayesian RL setting where we only have access to prior belief distribution over MDPs. We find Bayes- adyes--d policies which are risk-averse to both the epistemic uncertainty over the underlying MDP and the alcatoric uncertainty due to stochastic transitions. To our knowledge, existing work has addressed CVaR optimisation in the addattie RL setting to simultaneously address both forms of uncertainty.
31
43
Constrained MDPs impose a constraint on the expected value of a cost [ 36.. Such constraints have been addressed in Bayesian RL [8]. However, this approach only constrains the expected cost and is unclear how to choose cost penalties to obtain the desired risk averse behaviour. Monte Carlo Tree Search (MCTS) has been adapted to expected cost constraints [19]. However, to our knowledge, this is the first work to adapt MCTS to CVaR optimisation in sequential decision making problems.

---

In the Deep RL setting, Deep Q-Networks [24] have been modified to predict the uncertainty over the Q-values associated with epistemic and aleatoric uncertainty T3 and derive a risk- sensitive policy. In this work, we propose to use the Bayes-adaptive formulation of RI. to model and address both uncertainty sources. Another related strand of work is robust adversarial reinforcement learning [28 33) (RARL) which optimises robust policies by simultaneously training which perturbs the environment. RARL it is unclear how much power to give to the adversary to achieve the desired level of robustness, Our approach ensures that the CVaR at the desired confidence
adversary
level optimised.
Preliminaries
Let Z be bounded-mean random variable, i.e. E||Z]] < oC, probability space (0,F, P), with cumulative distribution function F(2)= P(Z S z). In this paper we interpret Z as the total reward, return, to be maximised. The value at risk confidence level E (0, [] is defined as VaR (2) = min F(()) 2 a). The conditional value at risk at confidence level a is defined as
a
CVaR, J (2)d7
(1)
If Z has a continuous distribution, CVaR, (Z) can be defined using the more intuitive expression: CVaR,, (Z) = E| < VaR, (Z)). Thus, CVaR, (Z) may be interpreted as the expected value of the a-portion the left tail the distribution of Z. CVaR may also be defined as the expected value under perturbed distribution using its dual representation 34 37
CVaR = min Eg [Z],
(2)
(EB(a.P)
where WEg [2] denotes the E-weighted expectation of Z, and the risk envelope, B, is given by
0o (
{(w)(W))d- =1]
B(o, P)
g: ((w)
WER
Therefore, the CVaR of a random variable Z may be interpreted as the expectation of under a worst-case perturbed distribution, EP. The risk envelope is defined that the probability density of any outcome can be increased by factor of at most 1/a, whilst ensuring the perturbed distribution is valid probability distribution.
3.1 CVaR Optimisation in Standard MDPs
finite-horizon Markov decision process (MDP) is tuple, - - (S, H, 80), where S and A are finite state and action spaces, R S A R is the reward function, T S A x S [0. 1] the transition function, H the horizon, and 8p is the initial state. A history of M is a sequence h Spags100 01 . ... 04-18; such that T(s;, d, S1+1) >> 0 for all i. We denote the set of all histories over M as H. history-dependent policy is a function æ H.M -> A, and we write IT to denote policies for M. If π only depends say π Markovian, and we denote the set of all Markovian policies as II A policy æ induces
the set of all history-depender
the last state 8; of h, then
distribution P.M over histories and we define G.M = E'o R(s,, at) as the distribution over total returns of M under æ. Many existing works have addressed the problem of optimising the static CVaR of G.M, defined as follows.
Problem 1 (CVaR optimisation in standard MDPs) Let M be an MDP. Find the optimal CVaR of the total return at confidence level oc
max VVRR,,G,M TEII
Unlike dynamic Markov risk measures 35 history-dependent policies may required to optimally
solve this static CVaR optimisation problem 3 8 43). Previous works [ 27 have shown that this

---

problem can be interpreted either being risk risk-averse to aleatoric uncertainty, or as being robust to epistemic uncertainty. The latter interpretation comes from the dual representation CVVRR (Eq. 2 where CVaR is expressed as the expected value under a worst-case perturbed probability distribution.
Methods based on dynamic programming have been proposed to solve Problem T
g 29 In
particular, Chow et al. [8] augment the state space by an additional continuous state factor, E (0, 1]. corresponding the confidence level. The value function for the augmented state (s, y) is defined by (ss,y) x CVaR,(GG (G²",, and can be computed using the following Bellman equation
V(s.g) max a R(s, a) (EBly.T(saa;)
min
(5)
where & represents an adversarial perturbation to the transition probabilities, and the additional state variable, y. ensures that the perturbation to the probability of any history through the MDP is at most 1/y. Thus, y can be thought of as keeping track of the "budget" to adversarially perturb the probabilities. Therefore, V(so. a) is the expected value under the adversarial probability distribution defined by Eq. and 3 and corresponds to the optimal CVaR in the MDP (Problem D To address the continuous state variable, y: g use dynamic programming with linear function approximation.
3.2 Stochastic Games
In this paper, we will formulate CVaR optimisation as a turn bun-based two-player zero-sum stochastic game (SG). An SG between an agent and an adversary is generalisation of an MDP and can be defined using a similar tuple G = (S, A, T, R. H, so). The elements of G are interpreted as with MDPs, but extra structure is added. In particular, 5 partitioned into set of agent states Soot, and a set of adversary states Sude Similarly, A is partitioned into set of agent actions A and a set of adversary actions Aadv, The transition function is defined such that agent actions can only be executed in agent states, and adversary actions can only be executed in adversary states.
We denote the of Markovian agent policies mapping agent states to agent actions as II and the set of Markovian adversary policies, defined similarly, as I A pair (π, σ) of adger-adyversar policies induces probability distribution over histories and define G ((T.a)) Σt R(s,, ac) as the distribution over total returns of G under и and In zero-sum SG, the agent seeks to maximise the expected return reward, whilst the adversary seeks to minimise it:
max min E G rell dESe
(x,))
(6)
3.3 Bayesian RL
Here we describe the Bayesian formulation of decision making in an unknown MDP 21 In Bayesian RL, the dynamics of the MDP M are unknown and we assume that its transition function, T, a latent variable distributed according to prior distribution P(T (h)), where hg represents the empty history where no transitions have been observed. After observing a history h = S00081a, 41-18t. the posterior belief over T is updated using Bayes' rule: P(T)h) x ((N[T)P(T)) ho).
In the Bayes-Adaptive MDP (BAMDP) formulation of Bayesian RL 12]. the uncertainty about the model dynamics is captured by augmenting the state space include the history: S S x H. This captures the model uncertainty as the history is a sufficient statistic for the posterior belief over T given the initial prior belief. The transition and reward functions for this augmented state space are
T ((s, h), (8', has')) = / T(s, a(s,a, s's,(,,))((()
R (*t = R(s,a).
(8)
The initial augmented state s (s), The tuple M+ = (S+ A, A,T+, NT,+ H,, defines the BAMDP. Typically, solutions to the Bayesian RL problem attempt to (approximately) find

---

Bayes-optines policy, which maximises the expected sum of rewards under the prior belief over the transition function. In this work, we address risk-averse solutions the Bayesian RL problem.
4 CVaR Optimisation in Bayes-Adaptive RL
Many existing works address CVaR optimisation in standard MDPs. Here, we assume that we only have access a prior distribution over MDPs, and optimise the CVaR in the corresponding BAMDP.
Problem ( CVaR optimisation Bayes-Adaptive MDPs) Let M be a Bayes-Adaptive MDP. Find the optimal CVaR al confilence level a: max CVaRa =EIIM
(9)
Posing CVaR optimisation over BAMDPs leads to observations. First, unlike Problem T do not need to consider history-dependent policies as the history is already embedded in the BAMDP state. Second, the solution to this problem corresponds a policy which risk-averse both the epistemic uncertainty due to the uncertain belief' over the MDP, and the alcatoric uncertainty due to the stochasticity of the underlying MDP. In the following, elaborate on this second observation.
4.1 Motivation: Robustness to Epistemic and Aleatoric Uncertainty
The solution to Problem i risk-averse to both the epistemic and the aleatoric uncertainty. Intuitively, this is because the return distribution in the BAMDP is influenced both by the prior distribution over models as well as stochastic transitions. In this section, we introduce novel alternative definition of CVaR in BAMDPs to formally illustrate this concept. Specifically, is equivalent to the expected value under an adversarial prior distribution over transition functions, and ad adversarial perturbations to the transition probabilities in all possible transition functions. The perturbation "budget" of the adversary is split multiplicatively between perturbing the probability density of transition functions, and perturbing the transition probabilities along any history. Therefore, the adversary has the power to minimise the return for the agent through a combination of modifying the prior that "bad" transition functions are more likely (epistemic uncertainty), and making "bad" transitions within any given transition function more likely (aleatoric uncertainty).
show that CVaR in BAMDP
We consider an adversarial setting, whereby an adversary is allowed to apply perturbations to modify the prior distribution over the transition function as well as the transition probabilities within each possible transition function, subject to budget constraints. Define T to be the support of P(T ho). and let T, E T be a plausible transition function. Note that, in general, T can be a continuous transition functions
set. Consider perturbation of the prior distribution such that Jr. (TTp)P(TTplyn dd, = 1. Additionally, for Tр E T, consider a perturbation of Tр. Sp S x x S Rzo such that Enes Ep(s, of all possible perturbations of Tp as Ep. and the set of all perturbations over T as E = XT,E7=p- For BAMDP M 8 T + Rz0, and & E, we define M as the BAMDP, obtained from 5(Tp) PhTplho) and perturbed transition
T Rgo
(s(ss,,s)) a,s') Tp(s, a,) = 1 Vs, a. We denote the set
M with perturbed prior distribution (TTpplha) functions 7 (s, a, s') = Ep, a, s') (p a, s'). We are now ready to state Prop. [ which provides an interpretation of CVaR in BAMDPs as expected value under an ad adversarial prior distribution and adversarial transition probabilities. All propositions are proven the supplementary material.
Proposition 1 (CVaR in BAMDPs) Let M be a BAMDP. Then:
(V
min E
"s s.t.
(10)
8:7 B.T-RRa R00
EEE
s ((Tp)p((S) au, $1 (1) a1 82) VTP E T, V(s,, ag ai....... .......8:) 88) Hy-
(p( 4H-1, sH
a
Prop. shows that CVaR can be computed as expected value under an adversarial prior distribution over transition functions, and adversarial perturbations to the transition probabilities in all possible transition functions. Therefore, policy which optimises the CVaR a BAMDP must mitigate the risks due to both sources of uncertainty.
5

---

4.2 Bayes-Adaptive Stochastic Game Formulation
In Prop. [] we formulated CVaR in BAMDPs as expected value under adversarial perturbations the prior, and to each possible MDP. However, this formulation is difficult to solve directly as it requires optimising over the set of variables E. which can have infinite dimension since the space of plausible transition functions may be infinite. Thus, we formulate CVaR optimisation in BAMDPs in way that is more amenable to optimisation: an SG played on an augmented version of the BAMDP. The agent plays against an adversary which modifies the transition probabilities of the original BAMDP. Perturbing the BAMDP transition probabilities is equivalent to perturbing both the prior distribution and each transition function as considered by Prop. [ This extends work on CVaR optimisation in standard MDPs
g to the Bayes-adaptive setting.
We begin by augmenting the state space of the BAMDP with an additional state factor, y E (0. 1], so that now the augmented state comprises (s, h, y) E 5g = S x H x (0, 1]. The stochastic game proceeds follows. Given an augmented state, (s, h, y) E Sg.e0t, the agent applies action, E A, and receives reward Rig ((s, h, v), R(s, a). The state then transitions to an adversary state (s, ha, y) E Sg.ado The adversary then chooses an action from continuous action space, & E E(s, v), to perturb the BAMDP transition probabilities where
El (s,,ah.))) E: S R2o 0 S E(s') 1/y Vs' and Eves E(x')
. T ((s,h), (s', has')) = }
(11)
In Eq. the adversary perturbation is restricted to adhere to the budget defined by Eq. 3 so that the
probability of any history in the BAMDP is perturbed by most 1/y. After the adversary chooses the perturbation action, the game transitions back to agent state (s', hass,,, y E(8') S agg
according to the transition function
T ((s, ha, y). E, (s', hash, yas'.y- (-((''))) = E(s') T ((s, a, (s', (&,has'))
(12)
The initial augmented state of the stochastic game is st.5 = (so, ho, E St.est The tuple G+ = (S) AA, Tz. Rt. HI, st.s) defines the Bayes-Adaptive CVaR Stochastic Game (BA-CVaR-SG), where the joint action space is A = AUE.
The maximin expected value equilibrium of the BA-CVaR-SG optimises the expected value of the BAMDP under perturbations to the probability distribution over paths by an adversary subject to the constraint defined by Eq. 3 Therefore, Prop. states that the maximin expected value equilibrium in the BA-CVaR-SG corresponds to the solution to CVaR optimisation in BAMDPs (Problem 2
Proposition 2 Formulation of CVaR optimisation in BAMDPs as a stochastic game.
max CVaR. (G+T) +
max =ETT9-
min aE
B[G
(13)
Prop. 2 directly extends Prop. from 8 to BAMDPs. The BAMDP transition function is determined
by both the prior distribution over transition functions and the transition functions themselves (Eq. 77) Therefore, perturbing the BAMDP transition function, as considered by Prop. [ is equivalent to
perturbing both the prior distribution and each transition function considered by Prop. I
4.3 Monte Carlo Tree Search Algorithm
Solving the BA-CVaR-SG is still computationally difficult due to two primary reasons. First, the set of reachable augmented states grows exponentially with the horizon due to the exponentially growing set of possible histories. This prohibits the use of the value iteration approach proposed by Chow et al. [8] for standard MDPs. Second, CVaR is considerably more difficult to optimise than expected value. the BA-CVaR-SC formulation, this difficulty is manifested in the continuous action space of the adversary corresponding possible perturbations to the BAMDP transition function.
In this section we present an approximate algorithm, Risk-Averse Bayes-Adaptive Monte Carlo Planning (RA-BAMCE Like BAMCP [16), which applies MCTS to BAMDPs, and applications of

---

Algorithm 1: Risk-Averse Bayes-Adaptive Monte Carlo Planning
function Search (
function ExpandAgent (v)
create root node ug with:
choose E untried actions from action set A add child o' to with:
$g (Vo) = =0
player(vo)= = agent
$Ø (v') (v)
while within computational budget:
a =
Vieaf f- TreePolicy (wa)
player(v') ade
r < DefaultPolicy (Vieaf)
(((') =
Updatellodes
return v'
((v')
arg max
function ExpandAdversary(o)
Echilden no
0
arg min (v²")
if ir((v) = 0:
Enew = RandomPerturbatsion(())
return a(v').((v")
else
Enew BayeddpePartuurbatioo((()
function (reePolicy(:))
while is non-terminal:
((v).inse((((ee)
if player(u) = agent:
add child v' to v with:
if not fully expanded:
$ (v') st (v) {(v') =
return ExpandAgent (v)
else
" + u. v.BestChild()
player (v)) chance return v' function (estChild
else player(v) adv
if (N)) - > [(v)]
return ExpandAdversarr(())
if player(u) agent
else
return
8 - v.BestChild()
[Q(')) + Cmets
log N(v)
max Echildion
N(v*)
else player(v) chance:
else
sample successor according Eq.
return
log N(v) Nuv)
[²(00) Cmets
arg min
function UpdateNodes (e, 7)
Echildren of
while is not null:
((e) =
(v) vv) + (() ((w)
N(v)
parent
MCTS to two-player games such as Go 14| we use MCTS to handle the large state space by focusing search in promising areas. Unlike BAMCP, we perform search over a Bayes-adaptive stochastic game against an adversary which may perturb the probabilities, and we cannot use root sampling as we need access the BAMDP transition dynamics (Eq. 7 to compute the set of admissible adversary actions (Eq. [T]. To handle the continuous action space for the adversary, we use progressive widening [IO] prioritise promising actions.
paired with Bayesian optimisation 22 22
RA-BAMCP Outline Algorithm D proceeds using the standard components of MCTS: selecting nodes within the tree, expanding leaf nodes, performing rollouts using default policy, and updating the statistics decision nodes, adversary decision nodes, and chance nodes. At each new node the value estimate associated with that node, (u)) and visitation count, ((v,, both initialised to At agent (adversary) decision nodes we use an upper (lower) confidence bound to optimistically select actions within the tree. At newly expanded chance nodes we compute P(T)A), the posterior distribution the transition function for the history leading up to that chance node. Using this posterior distribution, can compute the transition function for the BA-CVaR-SG, T at that chance node. When chance node is reached during a simulation, the successor state is sampled using T
tree. The search tree consists of alternating layers three types of nodes: agent
At each adversary node, a discrete set of perturbation actions is available to the adversary, denoted by E(v). We use progressive widening [00 to gradually increase the set of perturbation actions available by adding actions from the continuous set of possible actions, B(v). The rate at which new actions expanded is controlled by the progressive widening parameter, A naive implementation of
7

---

progressive widening would simply sample new perturbation actions randomly. This might require many expansions before finding a good action. To mitigate this issue we use Gaussian process (GP)
Bayesian optimisation to select promising actions to expand in the tree 25 22
In our algorithm the BayesOpt.Perturbaate promising perturbation action at a given adversary node, c. We train a GP using a Gaussian kernel. The input features are existing expanded perturbation actions at the node, & E E(v). The number of input dimensions is equal to the number of successor states with non-zero probability according to the BAMDP transition function. The training labels are the corresponding value estimates in the tree for each of the perturbation actions: (v)), for all children v' of u. The acquisition function for choosing the new perturbation action to expand a lower confidence bound which is optimistic for the minimising adversary: Snew arg min [m({) - Cbo (E)]. where v(E) and o{E) are the mean and standard deviations of the GP predicted posterior distribution respectively. Prop. happ.eestabrr establishes that a near-optimal perturbation will eventually be expanded with high probability if Cho set appropriately.
function performs Bayesian optimisation return
Let ā E (0, 1). Provided that Cho is chosen appropriately (details in the appendix), as the number of perturbations expanded approaches oc, a perturbation within any e 0 of the optimal perturbution will be expanded by the Bayesian optimisation procedure with probability 2 - 5.
Proposition 3
After each simulation, the value estimates at each node are updated using F(v), the reward received from onwards during the simulation. Search continues by performing simulations until the compu- tational budget is exhausted. At this point, the estimated best action for the agent and the adversary is returned. In our experiments we perform online planning: after executing an action and transitioning to new state, we perform more simulations from the new root state.
5 Experiments
Code for the experiments is included in the supplementary material. All algorithms are implemented in C++ and Gurobi is used to solve linear programs for the value iteration (VI) approaches. Computation times are reported for a 3.2 GHz Intel i7 processor with 64 GB of RAM.
No existing works address the problem formulation in this paper. Therefore, we adapt two methods for CVaR optimisation to the BAMDP setting and also compare against approaches for related problems to assess their performance in our setting. We compare the following approaches:
RA-BAMCP: the approach presented in this paper.
CVaR BAMDP Policy Gradient (PG): applies the policy gradient approach CVaR optimisation from 455 with the vectorised belief representation for BAMDPs proposed in [13) with linear function
approximation. Further details on this approach can be found in the supplementary material.
CVaR VI BAMDP: the approximate VI CVaR optimisation approach from [8 applied to the BAMDP. Due to the extremely poor scalability of this approach we only test it on the smaller of our domains.
CVaR VI Expected MDP (EMDP): the approximate VI approach from g applied to the expected MDP parameters according to the prior distribution over transition functions, P(T]ha))
BAMCP: Bdyes-A Monte Carlo Planning which optimises the expected value 16 This is equivalent to RA-BAMCP with the confidence level, a, set to 1.
For RA-BAMCP and BAMCP the MCTS exploration parameter was set to Cmects 2 based on empirical performance. For these methods, we performed 100, 000 simulations for the initial step and 25, 000 simulations per step thereafter. For both of these algorithms the rollout policy used for the agent was the CVRR VI Expected MDP policy, For RA- BAMCP. the rollout policy for the adversary was random, the progressive widening parameter was set to T = 0.2, and the exploration parameter for the GP Bayesian optimisation was also set to Cbo = 2. Details of the GP hyperparameters are in the supplementary material. For CVaR VI Expected MDP and CV&R VI BAMDP. 20 log-spaced points were used to discretise the continuous state space for approximate VI as described by [8]. For CVaR BAMDP Policy Gradient we trained using x 10 simulations and details on hyperparameter tuning are in the supplementary material.
8

---

Betting Game Domain We adapt this domain from the lit- erature on conditional value at risk in Markov decision pro- cesses 3 to the Bayes-adaptive setting. The agent begins with money = 10. At each stage the agent may choose to place a bet from bets {0, 1, 2,2,5 5, 10) provided that sufficient money is available. If the agent wins the game at that stage, an amount of money equal to the bet placed is received. If the agent loses the stage, the amount of money bet is lost. The reward is the total money the agent has after 6 stages of betting. In Bayes- adaptive setting, the probability of winning the game is not known aprioni. Instead, prior distribution over the probability of winning the game is modelled using a beta distribution with parameters a TT T indicating that the odds for the game are likely to be in favour of the agent.
Figure 1: Autonomous naviga- tion domain. Colours indicate the road types as follows black: high- way, red: main road, blue: street, green: lane.
Autonomous Car Navigation Domain An autonomous car must navigate along roads to a desti- nation by choosing from actions {up, down, left, right) (Figure [.]. There are four types of roads: (highway, main road, street, lane) with different transition duration characteristics. The transition distribution for each type of road unknown. Instead, the prior belief over the transition duration distribution for each road type is modelled by a Dirichlet distribution. Thus, the belief is represented by four Dirichlet distributions. Details on the Dirichlet prior used for each road type are included in the supplementary material. Upon traversing each section of road, the agent receives reward time where time the transition duration for traversing that section of road. Upon reaching the destination, the agent receives reward of 80. The search horizon was set to H 10.
5.1 Results
We evaluated the return from each method over 2000 episodes. For each episode, the true underlying MDP was sampled from the prior distribution. Therefore, the return received for each evaluation episode is subject to both epistemic uncertainty due to the uncertain MDP model, and alcatoric uncertainty due to stochastic transitions. Results for this evaluation can be found in Table [ The rows indicate the method and the confidence level, a, that the method is set optimise. The columns indicate the performance of each method for CVaR with a = 0.03 and a = 0.2, and expected value (a 1), evaluated using the sample of 2000 episodes. Note that when evaluating the performance of each algorithm, we only care about the CVaR performance for the confidence level that the algorithm set to optimise.
In the Betting Game domain, strong performance is attained by CVaR VI BAMDP, however the computation time required for this approach is considerable. It was not possible to test CVaR VI BAMDP on the Autonomous Navigation due to its poor scalability. RA-BAMCP attained near-optimal performance at both confidence levels using substantially less computation. CVaR VI Expected MDP performed well at the a = 0.2 confidence level, but very poorly at a = 0.03. This approach performs poorly at 0.03 because by using the expected value of the transition function, the probability of repeatedly losing the game is underestimated. BAMCP performed the best at optimising expected value, but less well than other approaches for optimising CVaR.
CVaR BAMDP Policy Gradient performed strongly in the betting domain with a 0.2. However, attained poor asymptotic performance with a 0.03. Conversely, this method performed well in the navigation domain with a = 0.03, but poorly for a = 0.2. These results indicate that the policy gradient approach is susceptible to local minima. Training curves for CV&R BAMDP Policy Gradient can be found in the supplementary material.
In the Autonomous Car Navigation domain RA- BAMCP outperformed CVaR VI Expected MDP at both confidence levels. As expected, BAMCP again performed the best at optimising expected value, but not CVaR. The return histograms in Figure there is high uncertainty over the return value. As the confidence level a is decreased, applying RA-BA -AMMPP decreases the likelihood of poor returns by shifting the left tail of the return distribution to the right, at the expense of worse expected performance. This demonstrates that RA-BAMCP risk-averse poor return values in the presence of both epistemic and aleatoric uncertainty.
show Ssow that while BAMCP optimises expected value,

---

Mehhd
(.-0.33)
CV2R
Value
RA-BAMCP (a.= 0.03)
RAMPP (.00.3))
$620.5
17
9.98 (0312)
(0.0)
(0.00
(00022)
10.00 (0.0)
C2at IC -00
CYOR 0 0
ClaR EMDP (0)0)0))
61.7
(0.0)
10.45 (0.33)
15.72.0.00
Claß BAMDP (000.33)
4639.3
2,90 (0.06)
10.57 (0.33)
27.34 (0.24)
300
RA-RAMCP io (0-0
(0.9
(.301
20.09 (1 (84)
46.84 (0.37)
Cla8 vi RAMPP (0)02.2
8620.5
0::00 (0:0)
20.77 (1.022
44.15 (0.33)
CVaR Vi EMDP (.2)
61.7
0.90
19.33 (0.99)
39.86 (0.30)
RAMPP 0.2)
4309.7
20
40
60
BAMCP
(3,5
(0.0)
17.07
$9.36
RA-BAMCP 0.22
Betting Game domain
CtoA 1000
Expocted Vanee
400
300
Clal
(o=00
Expected
200
BAMC (100
235.710.2)
23.51 (0.17)
2541.10.00 (0.06)
29.36 (0066
Cluk EMUP (d-d.
96.6
20:65 (0.68)
26.11 (0.16)
30.13 (0.0))
100
Clab RAMPP PG to -0.00)
97232.6
23.92 (0.08)
(0.05)
28.97 (0.05)
20
40
60
RA-RAMCP (.2)
205.1 (0.3)
18.91 (0 44)
27.76 (0.24)
38 (0.15)
Claß vi EMDP (..02)
96.6
4,20 (0,54)
20.42 (0.44)
36.64 (0.21)
8AMCP
Clul RAMDP PC (0-2
36086.
10:05 (0.74)
(4.30
49.67 (0.36)
CVOR to 0.03
CVaR (z 0.22
RAMCP
(4.4
5.56 (0,60)
(0.47
50.16 (0.38)
frequency
300
(b) Autonomous Car Navigation domain
200
Table 1: Results from evaluating the returns of each method for 2000 episodes. Brackets indicate standard er- rors. Time for RA-BA A--AMCPP and BAMCP indicates average total computation time per episode to perform simulations. Time for CVaR VI BAMDP and CV&R VI Expected MDP indicates the time for VI to converge. Time for CVaR BAMDP PG indicates the total training time.
Figure 2: Histogram of returns re- ceived in the Autonomous Car Naviga- tion domain. Vertical red lines indicate CVaRn..3 CVaRp.2, and the expected value of the return distributions.
Results in the supplementary material show that approach using random action expansion rather than Bayesian optimisation attains worse performance for the same computation budget. This demonstrates that Bayesian optimisation for action expansion critical our approach.
Discussion of Limitations and Conclusion
In this work, have addressed CVaR optimisation in the BAMDP formulation of model-based Bayesian RL. This is motivated by the aim mitigating risk due to both epistemic uncertainty over the model, and aleatoric uncertainty due environment stochasticity. Our experimental evaluation demonstrates that our algorithm, RA-BA BAMCP, outperforms baseline approaches for this problem.
One of the limitations of our work is that our approach cannot use root sampling (16). Instead, the posterior distribution is computed at each node the MCTS tree, prohibiting the use of complex priors. In future work, we wish to develop use root sampling. Additionally, due to the exponential growth of the BAMDP and the difficulty of optimising CVaR, the scalability of our approach is limited. In future work, we wish to utilise function approximation to improve the scalability of our approach to more complex problems. One direction could be using a neural network to guide search, in the style of AlphaGo [39]. Another direction could be to extend the policy gradient algorithm that we proposed in the experiments section to make of deep learning.
MCTS algorithm for CVaR optimisation which can
10

---

Acknowledgements and Funding Disclosure
The authors would like to thank Paul Duckworth for valuable feedback on an earlier draft of this work.
This work was supported by Programme Grant from the Engineering and Physical Sciences Research Council (EP/V000748/1), the Clarendon Fund at the University of Oxford, and gift from Amazon Web Services.
References
[1] Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
[2] Philippe Artzner, Freddy Delbaen, Jean-Mare Eber, and David Heath. Coherent measures of risk. Mathematical finance, 9(3):203-233 1999.
[3] Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-valuu-at-risk criteria. Mathematical Methods of Operations Research, 74(3):361-379, 2011.
[4] Vivek Borkar and Rahul Jain. Risk-constrained Markov decision processes. In 49th IEEE Conference Decision and Control (CDC), pages 2664-2669. IEEE, 2010.
[5] Katherine Chen and Michael Bowling. Tractable objectives for robust policy optimization. In Advances in Neural Information Processing Systems, pages
2012.
[6] Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for CVaR optimization in mdps. In Advances in neural information processing systems, pages 3509-3517, 2014.
[7] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070-612) 120, 2017.
[8] Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk- and robust decision- making: CVaR optimization approach. In Advances in Neural Information Processing Systems, pages 1522-1530, 2015.
[9] William Clements, Bastien Van Delft, Benoît-Marie Robaglia, Reda Bahi Slaoui, and Sébastien Toth. Estimating risk and uncertainty in deep reinforcement learning, arXiv preprint /901v99905.00638, 2019.
[10] Adrien Couêtoux, Jean- Man-Baptiste Hoock, Nataliya Sokolovska, Olivier Teytaud, and Nicolas Bonnard. Continuous upper confidence trees. In International Conference on Learning and Intelligent Optimizution, pages 433-445. Springer, 2011.
[11] Erick Delage and Shie Mannor. Percentile optimization for Markov decision processes with parameter uncertainty. Operations research, 58(1):203-2133 2010.
[12] Michael O Duff. Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes. 2003.
[13] Hannes Eriksson, Debabrota Basu, Mina Alibeigi, and Christos Dimitrakakis. Sentinel: Tam- ing uncertainty with insemble-based distributional reinforcement learning. arXiv preprint arXiv:2102. 1075, 2021.
[14] Sylvain Gelly and David Silver. Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence, (75(11):8866111 2011.
[15] Arthur Guez, Nicolas Heess, David Silver, and Peter Dayan. Bayes-adaptive simulation-based search with value function approximation. In NIPS, volume 27, pages 451-459, 2014.
[16] Arthur Guez, David Silver, and Peter Dayan. Efficient Bayes-adaptive reinforcement learning using sample-based search. Advances in neural information processing systems, 25:1025-1033 2012.
[17] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280, 2005.
[18] Jongmin Lee, Youngsoo Jang, Pascal Poupart, and Kee-Fung Kim. Constrained Bayesian reinforcement learning via approximate linear programming. In IJCAI, pages 2088-2095, 2017.
11

---

[19] Jongmin Lee, Geon- -oeong Kim, Pascal Poupart, and Kee- Kee-Eung Kim. Monte-carlo tree search for constrained pomdps. In NeurIPS, pages 7934-7943, 2018.
[20] Shie Mannor, Duncan Simester, Peng Sun, and John N Tsitsiklis. Bias and variance in value function estimation. In Proceedings of the twenty-first international conference Machine learning, page 72, 2004.
[21] James John Martin, Bayesian decision problems and Markov chains. Wiley, 1967.
[22] John Mern, Anil Yildiz, Zachary Sunberg, Tapan Mukerji, and Mykel Kochenderfer. Bayesian optimized Monte Carlo planning. arXiv preprint arXiv:2010.03597, 2020.
[23] Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine Learning Research, 7(12), 2006.
[24] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-5333 533, 2015.
[25] Philippe Morere, Roman Marchant, and Fabio Ramos. Bayesian optimisation for solving continuous cile-action-obbervation pomdps. Advances in Neural Information Processing Systems (NIPS), 2016.
[26] Arnab Nilim and Laurent El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
[27] Takayuki Osogami. Robustness and risk-sensitivity in Markov decision processes. Advances in Neural Information Processing Systems, 25:233-241, 2012.
[28] Xinlei Pan, Daniel Seita, Yang Gao, and John Canny. Risk averse robust adversarial reinforce- ment learning. In 2019 International Conference on Robotics and Automation (ICRA), pages 8522-85288 8528. IEFE, 2019.
[29] Georg Ch Pflug and Alois Pichler. Time-consistent decisions and temporal decomposition of coherent risk functionals. Mathematics of Operations Research, 41(2):682-65) 699, 2016.
[30] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 2817-2826, 2017.
[31] LA Prashanth. Policy gradients for CVaR-constrained MDPs. International Conference on Algorithmic Learning Theory, pages 155-169. Springer, 2014.
[32] Marc Rigter, Paul Duckworth, Bruno Lacerda, and Nick Hawes. Lexicographic optimisation of conditional value at risk and expected value for risk-averse planning in MDPs. arXiv preprint
arXiv:2110.127466 2021.
[33] Mare Rigter, Bruno Lacerda, and Nick Hawes. Minimax regret optimisation for robust planning in uncertain Markov decision processes. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13): 1910-119999993 May 2021.
[34] R Tyrrell Rockafellar, Stanislav Uryasev, al. Optimization of conditional value-at-risk. Journal of risk, 2:21 42, 2000.
[35] Andrzej Ruszezyáski. Risk-averse dynamic programming for Markov decision processes. Mathematical programming, 125(2):235-261, 2010.
[36] Pedro Santana, Sylvie Thiébaux, and Brian Williams. RAO*; An algorithm for chance- constrained POMDP's. 2016.
[37] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszezyúski. Lectures on stochastic programming: modeling and theory. SIAM, 2014.
[38] Apoorva Sharma, James Harrison, Matthew Tsao, and Marco Pavone. Robust and adaptive planning under model uncertainty. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 29, pages 410-418, 2019.
[39] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mas- tering the game of Go with deep neural networks and tree search. nature, 529((587):484 489, 2016.
12

---

[40] Sören Sonnenburg, Gunnar Rätsch, Sebastian Henschel, Christian Widmer, Jonas Behr, Alexan- der Zien, Fabio de Bona, Alexander Binder, Christian Gehl, and Vojtéch Franc. The SHOGUN machine learning toolbox. The Journal of Machine Learning Research, 11:1799-1802. 1802, 2010.
[41] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, page 1015-1022, Madison, WI, USA, 2010. Omnipress.
[42] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[43] Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. In Advances in Neural Information Processing Systems, pages 1468-1476, 2015.
[44] Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Sequential decision making with coherent risk. IEEE Transactions on Automatic Control, 62(7):3323-3338, 2016.
[45] Aviv Tamar, Yonatan Glassner, and Shie Mannor. Optimizing the CVaR via sampling. In Proceedings of the Twenty-Ninth AAAI Conference Artificial Intelligence, AAAI 15, page 2993-2999 AAAI Press, 2015.
[46] Yichuan Charlic Tang. Jian Zhang, and Ruslan Salakhutdinov. Worst cases policy gradients. arXiv preprint arXiv: 1191111668 2019.
[47] Eric M Wolff, Ufuk Topcu, and Richard M Murray, Robust control of uncertain Markov decision processes with temporal logic specifications. In 20/2 IEEE 5 IEEE Conference on Decision and Control (CC)), pages 3372-3379. IEFE, 2012.
13


Reviews:
[{"review_id": "qPDuoM1OU2b", "reviewer": "Reviewer_ZrWX", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nOne 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.\n\nThe 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.\n\nSome questions:\n- 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. \n\n- 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?\n\nExtra:\n- 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "gkb_DvHKEK", "reviewer": "Reviewer_dKwV", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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? \n2. 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?\n3. 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_text": "", "extra_scores": {"ethical_concerns": "Not applicable.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "KDq9aReKUpc", "reviewer": "Reviewer_aq52", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Main review. Please provide a thorough review of the submission, touching on each of the following dimensions:\n\nOriginality: \nThe 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.  \n\nThe 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.\n\nQuality: \n\nThe proofs in the appendix are very well explained and easy to follow. I think the proofs are of quality and technically sound. \n\nThe 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.\n\n\nClarity: \n\nMost 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.\n\nSignificance: \nI 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.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The only limitation that is stated is about the root sampling. A more thorough limitations sections would be useful.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "2Af0DVMYxO", "reviewer": "Reviewer_XkNN", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nCriticism/Suggestions for improvement:\n\nTheoretical part:\nThe 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)\n\nMCTS part:\nOne 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)\n\nRelated 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)\n\nThe 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)\n\nAnother 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)\n\nConclusion\n\nThe 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.\n\nMinor comments:\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)