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 addatiie 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 is 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 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 BayeddpePartuurbatiio((()
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. 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 (10055
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": "wtHW6ntPKAL", "reviewer": "Reviewer_4TDb", "summary": "The paper discusses parametric (epistmic) versus internal (aleatory) uncertainty in the context of Bayesian reinforcement learning. It extends previous methods for CVaR optimisation in MDPs to the BAMDP setting.\n\nThe response clarified some minor issues, but my main points remain unchanged. ", "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": "The paper discusses parametric (epistmic) versus internal (aleatory) uncertainty in the context of Bayesian reinforcement learning.  Although it claims a significant amount of novelty, a number of works [1,2,3] already combine both types of uncertainty in risk-sensitive Bayesian reinforcement learning, There have also been works on risk-averse tree search [4]. The technical novelty is also limited, as it directly uses earlier results that extended dynamic-programming techniques for aleatory CVaR risk from MDPs to epistemic uncertainty. However, this is the first paper that considers risk-aversion with the Bayes-adaptive MDP framework. The results show that this is a viable methohd.\n\n\nI find it hard to understand how the Bayesian framework fits here exactly. In particular, since the budget is shared arbitrarily between prior and transition perturbations, this implies that there is no clear distinction between aleatory and epistemic uncertainty. This is important, as a decision maker might be risk averse with respect to one type of risk, but not the other. The current approach gives no way to control the behaviour.\n\nOverall, I find the writing quite opaque compared to the Chow et al paper.\n\nProposition 2 $G_{\\pi, \\sigma}$ is undefined. I assume it is the adversary strategy.\n\n\nMinor comments:\n\n> Line 87 \"In this paper, we interpret Z as a reward to be maximised.\"\n\nDo you mean return?\n\n> Line 186 \"all perturbations over T as Xi = x_T_p in T^Xi_p\"\n\nThis is confusing.\n\n\nGeneral questions:\n\nWould be very interesting to see experiments on varying the horizon length.\nWould perhaps CVaR VI BAMDP outperform RA-BAMCP even on the large setting if you \nused a smaller horizon?\n\n\n[1] Depeweg et al. 2018, \"Decomposition of uncertainty in Bayesian deep learning for efficient and risk-sensitive learning.\"\n[2] Clements et al, 2019, \"Estimating risk and uncertainty in deep reinforcement learning.\"\n[3] Eriksson et al, 2021, \"SENTINEL: Taming Uncertainty with Ensemble based Distributional Reinforcement Learning\"\n[4] Lecarpentier and Rachelsson, 2019, \"Non-Stationary Markov Decision Processes a Worst-Case Approach using Model-Based Reinforcement Learning\"\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no clear distinction between aleatory and epistemic uncertainty. This is important, as a decision maker might be risk averse with respect to one type of risk, but not the other. The current approach gives no way to control the behaviour.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "weuHZWV78Iy", "reviewer": "Reviewer_JA6Z", "summary": "This paper considers the problem of risk-averse problems in Bayesian RL inspired by real-world scenarios, aiming to address the two sources of this uncertainty: the parametric (or epistemic) uncertainty and internal (or aleatoric) uncertainty. This paper applies CVaR as the risk measurement and optimizes it by formulating it as a stochastic game, which is novel, and solves it with MCTS.", "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 problem discussed in this paper is important. This paper is well-written. The methods used in this paper are well-motivated. The main framework is built on top of optimizing the CVaR over the return of BAMDP. The Bayes-Adaptive Stochastic Game formulation is new and I think maybe the authors were inspired by adversarial RL methods.\n\nThere are some limitations and questions:\n\n1. Why optimizing CVaR? The Mean-Variance [1] is also a direction. Can you tell me the reason?\n2. Can you also compare your method with VariBAD [2]?\n3. In lines 40-41, “By optimising the CVaR of the return in the BAMDP, our approach simultaneously addresses parametric and internal uncertainty under a single framework.”, is not clear in the paper, can you elaborate it?\n4. You proposed Bayes-Adaptive Stochastic Game, can you discuss more about the differences between your problem and adversarial RL methods [3]?\n5. In lines 232-235, can you give a clearer explanation? Why optimizing CVaR is hard than the expected value? To what magnitude your searching method addresses the growing set of possible histories compared with other methods?\n6. In your experiments, you used many simple scenarios. As you aim to address the two uncertainties in BADMP with risk-averse policies, can you show more complex scenarios, for example,  CARLA and Torcs or other scenarios, to demonstrate more risk-averse behaviour?\n\n[1] Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learning.\n[2] VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learning\n[3] Robust Adversarial Reinforcement Learning\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": "3 hours"}, "extra_text": {}}, {"review_id": "gLpL2k8NQ0r", "reviewer": "Reviewer_hcVR", "summary": "The paper proposes a method to optimize the conditional value-at-risk of the total return in Bayes-adaptive MDPs. They formulate the problem as a two player stochastic game and develop a Monte Carlo tree search based approximate algorithm. They show that the optimized policy is risk-averse to both epistemic/model and aleatory/transition uncertainties. They report several experiments to show the utility of their proposed method.", "questions": "", "limitations": "", "rating": 4, "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": "It is nice to have an illustrative example to clarify ideas at the beginning of the paper, but is the example presented in introduction useful for the purpose? Model uncertainty refers to the uncertainty associated to not knowing the transition probabilities. And the transition uncertainty refers to the inherent stochasticity. It is not clear how the situations presented in the example correspond to those uncertainties. It rather makes things more confusing.\n\nIn line 121, V is defined as \\min_\\pi CVAR(G), where G is defined in terms of reward, not cost. Should this be maximised instead, as shown in equation (4)?\n\nWhat is the definition of a node? Do you aggregate/discretize to define a state and/or node? What is the impact of such process?\n\nRA-BAMCP is an online algorithm which involves computing posteriors at each node of the tree in realtime. Using Beta/Dirichlet distribution, as done in the paper, provides a closed form approach to compute posteriors. But what happens when a closed form approach is not avaialable for a distribution? Does it scale? How about some empirical analysis?\n\nOne main claim in the paper is to apply CVaR over both the model and transition uncertainties. What difference this makes compared to general robust and/or risk averse methods studied in the literature? This is an important question to address, both theoretically and empirically. The paper misses this point. The empirical evaluation may show the difference more clearly by addressing only model uncertainty, only transition uncertainty and then addressing both types of uncertainties. Also, it can be interesting to compare against general robust, soft-robust and risk-averse methods available in the literature.\n\nAs the paper uses many different concepts like SG, MCTS, OFU/UCRL, GP and so on, the paper feels highly convoluted to read. In my opinion, the paper is not well written. A reorganization of the contents focusing readability and clarity may help.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "limitations and impacts are briefly addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "TwrwMeY-OXl", "reviewer": "Reviewer_aH4a", "summary": "The authors propose a new method introducing a risk-averse Bayes-adaptive reinforcement learning. This method aims at tackling two types of uncertainty that have mostly been tackled separately in former works: the epistemic uncertainty coming from imperfect knowledge about the underlying system and aleatoric uncertainty stemming from the internal stochasticity of the system. The authors formulate the risk-averse optimisation problem as a CVaR maximisation of the return in model-based Bayesian RL, which they show is equivalent to solving a stochastic game.  The stochastic game view shows that the proposed method effectively tackles both types of uncertainty and leads to the design of an algorithm based on Bayesian optimisation and MCTS to address the problem.  The proposed algorithm is evaluated against several baselines, demonstrating superior performances on two different tasks.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "In general, I found the paper an interesting read, well organised and provides a promising approach to risk-averse optimisation problems. I have still some questions notably regarding how practical the approach could be beyond the provided small-scaled experiments which still shows interesting results:\n\n1) In related work sections you mention policy gradient methods that assume the agent has access to the true underlying MDP for training/planning in contrast with your method for which you \"only have access to a prior belief distribution over MDPs\". Though in your experiments you say that \"For each episode, the true underlying MDP was sampled from the prior distribution\".  Can you please help me understand if this boils to having access to a true MDP (making the problem formulation less novel)? \n\n3) In the BayesOptPerturbation what motivated the use of an RBF kernel over, for instance, a matern-5/2 kernel? Are there standard assumptions or beliefs on the smoothness of the underlying black-box optimised with BO? Do the authors assume stationarity? Can you please help me understand what specific assumptions are made on the function when using BO?\n\n4) Results of Proposition 3 are interesting. How can those results be considered to arrive at a convergence bound of the overall proposed method? \n\n5) When it comes to the experiment, the main concern is in terms of scalability with respect to the number of states, actions and horizons. As one of the claims of the paper is that the proposed method tackles both aleatoric and stochastic uncertainty, it could be interesting to present a set of experiments with variable degrees of aleatoric/stochastic uncertainty to see what are the strengths and limitations of the method.  Can the authors run such experiments and present an updated version analysing the effect of those degrees?\n\n6) There are also references that just point to the appendix as a whole. Providing a more accurate reference could definitely aid in readability. \n\nRelated Work: \nThere are some related works that could be cited from both the Bayesian optimisation and model-based RL that could strengthen the positioning of the paper: \n1. Scalable Global Optimization via Local Bayesian Optimization\n2. SAMBA: Safe Model-Based & Active Reinforcement Learning\n3. An Empirical Study of Assumptions in Bayesian Optimisation\n4. Taking the Human Out of the Loop: A Review of Bayesian Optimization \n5. Practical Bayesian Optimization of Machine Learning Algorithms\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the methods have been provided. However, social impacts were not discussed and answered as No. I am not sure but I think safety can play a critical role in social impact especially in navigation tasks for example. Maybe the authors could look a bit more into this. ", "review_text": "", "extra_scores": {"ethical_concerns": "I don't foresee ethical issues. However, social impacts have not been considered. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "SBJpwcmEuO", "reviewer": "Reviewer_Kn8T", "summary": "A method for risk-averse Bayes-adaptive RL is developed theoretically and an implementation is provided, together with practical approximations for feasibility. The MDP's transition parameters $\\theta$ are a random variable (hence Bayes-adaptive), leading to two types of relevant uncertainty: that over the MDP itself (parametric, epistemic) and the inherent uncertainty of the MDP transition (internal, aleatoric). The focus of the paper is on optimizing for risk, here through the Conditional Value at Risk (CVaR) metric, w.r.t. both uncertainty types at once.\n\nInspired by [9], the authors propose a seemingly novel derivation for CVaR (Proposition 1), adapted to the Bayesian treatment of $\\theta$. The so-formulated CVaR is then used to pose a two-player stochastic game problem [9, 33], with a new structure. Optimization is done with MC tree search, somewhat similar to [33], but significantly extended. The adversary needs to perturb both the distribution over the transition with parameters $\\theta$  as well as the individual transition probabilities (targeting the risk envelope under all uncertainty), and the search is heavier due to necessary posterior updates (Bayesian $\\theta$). For feasibility, the continuous space of possible perturbation actions of the adversary is approximated through a discrete set, using progressive widening with Bayesian optimization to further extend it during search.\n\nThe method is validated on two toy scenarios, with adequate performance compared to other baselines.\n\n**References**\n\n[9] Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision-making: a CVaR optimization approach. NIPS 2015.\n\n[15] Arthur Guez, David Silver, and Peter Dayan. Efficient Bayes-adaptive reinforcement learning using sample-based search. NIPS 2012.\n\n[33] Apoorva Sharma, James Harrison, Matthew Tsao, and Marco Pavone. Robust and adaptive planning under model uncertainty. ICAPS 2019.\n", "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": "**Originality**\n\nOptimizing CVaR under both epistemic and aleatoric uncertainty has not been explored before, as far as I am aware. The perspective on CVaR in *Proposition 1* appears novel to me, it is inspired by [9], with the addition of adversarial minimization of the value function w.r.t. the distribution over transitions (which is unique to the Bayes-adaptive case). The combination of the chosen strategies (MCTS + progressive widening + Bayesian optimization) is also new to me. Related work appears adequately cited, although I think the claim that this is the first use of MCTS for CVaR optimization in sequential decision making might be overstated ([33] already does this, but only for epistemic uncertainty).\n\n**Strengths**\n\n- The proposed approach appears technically sound. The theoretical analysis is logical, extending the ideas of the cited previous works [9,15,33]. Given the technical complexity of the topic at hand, I believe this is valuable.\n- In terms of clarity, the paper is constructed well, motivation is presented in a reasonable order. The provided code in the supplementary material is appreciated, and should further help with understanding.\n- Full Bayesian modeling of risk in the context of RL is a very significant topic with broad applicability (finance, robotics, safety-critical systems, etc.). I believe it deserves more attention, and the paper does pinpoint specific scalability issues in the fully-Bayesian setting that future research should aim to address.\n- To an extent, the proposed approach does manage to address one of the scalability problems listed below (the prohibitively large continuous perturbation space of the adversary) through the discrete perturbation action set + BayesOpt (GP, Gaussian kernel) combination. This makes the method faster than the relevant baselines, considering both epistemic and aleatoric uncertainty. Still, performance needs to be improved further and it remains an open research question whether such approximations can work for more realistic problems.\n\n**Weaknesses**\n\n- The main weakness of the proposed solution is its scalability (exponential state space, heavy tree search operations due to posterior updates, limited exhaustion of adversary actions in an otherwise continuous high-dimensional space, no MCTS root sampling possible). I believe this is sufficiently acknowledged by the authors in the last two sections of the paper. It is not my expectations that all of these issues should be addressed in a single paper. Be it as it may, in its current version the approach is likely not applicable to real-world scenarios.\n- I also find that the experimental section could be improved. The two presented settings are very limited. This is understandable given the above, but I would have preferred a more varied set of environments with larger state spaces, even if that means evaluating only the proposed approach on some of them. Otherwise it is hard to judge the degree of generalization. The comparison to *CVaR VI Expected MDP*, which averages over the $\\theta$ distribution, is appreciated, but I would have liked to see the related *RAMCP* [33] in the comparison for symmetry, as well as an extended analysis of the modeling choices & structure of the proposed method (e.g. how the assumed prior entropy relates to the overall result / runtime budget).\n\n\n\nOverall, I feel there is merit to the presented theoretical framework and the paper does a decent job at highlighting some of the core issues that remain to be solved, even if I find the experimental section somewhat lacking.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are adequately addressed. The presented work is generic, societal impact should not be directly relevant in this case.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has been carefully discussed by the reviewers, the consensus is that while this paper applies CVaR to the fully-Bayesian setting and its motivation is appreciated (especially the motivation behind CVaR optimization in Bayesian MDP is to address the two sources of uncertainty: the parametric (or epistemic) uncertainty and internal (or aleatoric) uncertainty, which is good),  the contribution on extending CVaR MDPs onto the Bayes MDP setting is quite incremental. Similar to the standard MDP case, the authors managed to show a dual representation results for Bayes MDP and thus are able to modify algorithms such as MCTS to solve CVaR Bayes MDPs. Reviewers also mentioned concerns about scalability of the algorithm, and the lack of more realistic experiments (besides the small-scale experiments reported). For example some reviewers suggested more experimental details such as decoupling the effect of epistemic and aleatoric uncertainty on risk experimentally could also have been included, as well as considering an analysis of different priors (e.g. varying entropy, or an incorrect prior w.r.t. the true MDP distribution).

On the overall, the paper studied an interesting topic but its current form is below the acceptance threshold.



Decision: Accept (Poster)