Bayesian Risk Markov Decision Processes
Authors: Yifan Lin
Yuxuan Ren
Enlu Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: risk averse
Markov decision processes
reinforcement learning
parameter uncertainty
approximate dynamic programming

Abstract: We consider finite-horizon Markov Decision Processes where parameters, such as transition probabilities, are unknown and estimated from data. The popular distributionally robust approach to addressing the parameter uncertainty can sometimes be overly conservative. In this paper, we propose a new formulation, Bayesian risk Markov decision process (BR-MDP), to address parameter uncertainty in MDPs, where a risk functional is applied in nested form to the expected total cost with respect to the Bayesian posterior distributions of the unknown parameters. The proposed formulation provides more flexible risk attitudes towards parameter uncertainty and takes into account the availability of data in future time stages. To solve the proposed formulation with the conditional value-at-risk (CVaR) risk functional, we propose an efficient approximation algorithm by deriving an analytical approximation of the value function and utilizing the convexity of CVaR. We demonstrate the empirical performance of the BR-MDP formulation and proposed algorithms on a gambler’s betting problem and an inventory control problem.

Bayesian Risk Markov Decision Processes
Yifan Lin
Yuxuan Ren
Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332, USA ylin4290gatech.
Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332, USA yren798gatech.c edu
Enlu Zhou
Industrial and Systems Engineering
Georgia Institute of Technology
Atlanta, GA 30332, USA
enlu enlu.zhoußisy. hatpuuuiiieeeeeeeeeeeeeeeee gatech. edu
Abstract
We consider finite-horizon Markov Decision Processes where parameters, such transition probabilities, are unknown and estimated from data. The popular distri- butionally robust approach to addressing the parameter uncertainty can sometimes be overly conservative. In this paper, we propose a new formulation, Bayesian risk Markov decision process (BR-MDP), MDPs, where a risk functional is applied in nested form to the expected total cost with respect the Bayesian posterior distributions of the unknown parameters. The proposed formulation provides more flexible risk attitudes towards parameter uncertainty and takes into account the availability of data future time stages. To solve the proposed formulation with the conditional value-at-risk (CVaR) risk functional, we propose an efficient approximation algorithm by deriving an analyti- cal approximation of the value function and utilizing the convexity of CVaR. We demonstrate the empirical performance of the BR-MDP formulation and proposed algorithms on gambler's betting problem and an inventory control problem.
address parameter uncertainty in
Introduction
Markov decision process (MDP) is paradigm for modeling sequential decision making under uncertainty. From a modeling perspective, some parameters of MDPs are unknown and need to be estimated from data. In this paper, consider MDPs where transition probability and cost parameters are not known. A natural question would be: given a finite and probably small set of data, how does a decision maker find an "optimal" policy that minimizes the expected total cost under the uncertain transition probability and cost parameters?
A possible approach that mitigates the parameter uncertainty (also known epistemic uncertainty) lies the framework of distributionally robust MDPs (DR-MDPs, (T). DR-MDP regards the unknown parameters random variables and assumes the associated distributions belong to ambiguity set that is constructed from the data. DR-MDP then finds the optimal policy that minimizes the expected total cost with the parameters following the most adversarial distribution within the ambiguity set. However, distributionally robust approaches might yield overly conservative solutions that perform poorly for scenarios that pointed out in (2), DR-MDP does not explicitly specify the dynamics of the considered problem in the sense that the distribution of the unknown parameters does not depend on realizations of the data process, and therefore is generally not time consistent (we refer the reader to [2) for details on time consistency).
likely to happen than the worst case. Moreover, as
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In view of the aforementioned drawbacks of DR-MDP, we propose new formulation named as Bayesian risk MDP (BR-MDP), address the parameter uncertainty in MDPs. BR-MDP takes a similar perspective as Bayesian risk optimization (BRO), which is a new framework proposed by for static (single stage) optimization. They quantify the parameter uncertainty using a Bayesian posterior distribution to replace the ambiguity set in DRO, and impose risk functional on the objective function with respect to the posterior distribution. To extend to BRO to MDPs and also ensure time consistency, we propose to use a nested risk functional taken with respect to the process of Bayesian posterior distributions, where the posterior is updated with all realizations of randomness up to each time stage. We show the proposed BR-MDP formulation is time consistent, and derive the corresponding dynamic programming equation with an augmented state that incorporates the posterior information. The proposed framework works for an offline planning problem, where the decision maker, after loaded with the learned optimal policy and put to the real environment, acts like it adapts to the environment.
To solve the proposed BR-MDP formulation, we develop an efficient algorithm by drawing a connection between BR-MDP and partially observable MDP (POMDP) and utilizing the convexity of CVaR. The connection between BR-MDP and POMDP is motivated by the observation that the posterior distribution in BR-MDP is exactly like the belief state (which is the posterior distribution of the unobserved state given the history of observations) in a POMDP. The optimal value function of POMDP (in minimization problem) can be expressed an lower envelope of set of linear functions (also called a- functions, see [5). We show a similar a- e-ffnction representation of the value function for BR-MDP, where the number of a-functions grow exponentially over time. To have computationally feasible algorithm, we further derive an analytical approximation of the value function that keeps constant number of a-functions over time.
To summarize, the contributions of this paper are two folds. First, we propose a new time-consistent formulation BR-MDP to handle the parameter uncertainty in MDPs. Second, we propose an efficient algorithm to solve the proposed formulation with a CVaR risk functional, and the algorithm can be easily extended to other coherent risk measures (see [6 for an overview on coherent risk measures).
2 Related Literature
One possible approach that mitigates the parameter uncertainty in MDPs lies in the framework of robust MDPs (e.g. 7
g g 1O II). In robust MDPs, parameters usually assumed to belong to
known set referred to as the ambiguity set, and the optimal decisions are chosen according to their performance under the worst possible parameter realizations within the ambiguity set. [1 further extends the distributionally robust approach to MDPs (DR-MDPs) with parameter uncertainty and uti- lizes the probabilistic information of the unknown parameters. Different from all the aforementioned works, we take a Bayesian perspective in the BR-MDP formulation and seek a trade-off between the posterior expected performance and the robustness in the actual performance.
is worth noting that applying the Bayesian approach to MDPs has been considered in 12]. which proposes Bayes-adaptive MDP (BAMDP) formulation with augmented state composed of the underlying MDP state and the posterior distribution of the unknown parameters. In BAMDP, each transition probability is treated as unknown parameter associated with Dirichlet prior distribution, and an expectation is taken with respect to the Dirichlet posterior on the expected total cost. In contrast, our BR-MDP formulation imposes risk functional, taken with respect the posterior distribution (which could be chosen as Dirichlet distribution but is more general), on the expected total cost in nested form. On related note, risk-averse decision making has been widely studied in MDPs. Apart from the robust MDPs that address the parameter uncertainty, risk-sensitive MDPs (e.g. [5 16) address the intrinsic uncertainty (also known as alcatoric uncertainty) that is due to the inherent stochasticity of the underlying MDP, by replacing the risk-ncutral expectation (with respect the state transition) by general risk measures, such as conditional value-at-risk (CVaR, see [17). Most of the existing literature on risk-sensitive MDPs consider static risk functional applied to the total return (e.g. [88 19 20 21). There are two recent works closely related to ours, both of which apply a risk functional to BAMDP. Specifically, [22 formulates the risk-sensitive planning problem as a two-player zero-sum game and then applies static risk functional to the expected total cost, which adds robustness to the incorrect priors over model parameters; (23] optimizes a CVaR risk functional over the total cost and simultaneously addresses both epistemic and aleatoric uncertainty. In contrast, we consider nested risk functional due to the time consistency consideration discussed
13 14

---

in previous section. Also note that our problem setting relies on partial knowledge of the model (state transition equation, cost function etc.) and works an offline planning setting with no interaction with the environment, and hence is different from Bayesian reinforcement learning (e.g. [24]]] 25
3 Preliminaries and Problem Formulation
3.1 Preliminaries: BRO and CVaR
Bayesian risk optimization (BRO, see considers a general stochastic optimization problem: min, Ep- [b(2,.)], where is the decision vector. & is a random vector with distribution IP h is a deterministic cost function. The true distribution P is rarely known in practice and often needs to be estimated from data. It is very likely that the solution obtained from solving an estimated model performs badly under the true model. To avoid such a scenario, BRO seeks robustmess in the actual performance by imposing a risk functional to the expected cost function and solving the following problem: ming pr,, [Bp,(h(x,
where p is a risk functional, and F,, is the posterior distribution of 0 after observing n data points. It is assumed that the unknown distribution IP belongs to parametric family (Fap 0 E )), where the parameter space and 0- E O is the unknown true parameter value. Taking Bayesian perspective, 8 is viewed realization of random vector 8.
In particular, conditional value-at-risk (CVaR), a common coherent risk measure (see [6], is con- sidered for the risk functional. For random variable X defined on a probability space (9, F, value-at-riss risk VaR is defined as the a-quantile of X, i.e., (X) == inf (t P(X <t) 2 a). where the confidence level a E (0, 1). Assuming there is no probability atom at VaR*(X) CVaR confidence level is defined as the mean of the a-tail distribution of X, i.e. CVaR, (X) =
E [ X 2 Val., (X)]. It shown in [1 that CVaR can be written as convex optimization:
CX)
min wER
+
1
E B[(x ((xx-w)+] w)t1}
where (.)+ stands for max(0,)) :).
3.2 New formulation: Bayesian risk MDPs (BR-MDPs)
Consider a finite-horizon MDP defined as AS,A, P,C), C), where S is the state space, A is the action space, P is the transition probability with P(*++1 St, at) denoting the probability of transitioning to state 92+1 from state 8t when action d, is taken, C is the cost function with C2 (52, at, s141) denoting the cost at time stage when action 0g is taken and state transitions from 8 to $1+1- A Markovian deterministic policy is function mapping from S to A. Given initial state Su, the goal is to find an optimal policy that minimizes the expected total cost: minE5. P.C
T-1 Ce (St, at s Σ t==
where P.. is the expectation with policy when the transition probability is P and the cost is C. In practice, P and are often unknown and estimated from data.
To deal with the parameter uncertainty in MDPs, we propose new formulation, Bayesian risk MDP (BR-MDP), by extending BRO in static optimization to MDPs. We assume the state transition is specified by the state equation St+1 gr (st ag, Ee) with known transition function gt. which involves state St E S S R', action a: A C IR", and randomness & E E S R2 where s, a, are the dimensions of the state, action, and randomness, respectively. We assume {Ee, 0,... T --1 1} are independent and identically distributed (i.i.d)). Note that the state equation together with the distribution of & uniquely determines the transition probability of the MDP, i.e., P(*++1 E SS ax) = P((s, E E gr ge(st, at, (x) E Hs,, az), where S' is measurable set in S. We refer the readers to Chapter 3.5 in (26) for the equivalence between stochastic optimal control and MDP formulation. We use the representation of state equations instead of transition probabilities in MDPs, for the purpose of decoupling the randomness and the policy, leading to a cleaner formulation in the nested form. We assume the distribution of & denoted by f(; 00), belongs to parametric family {f(:; 0)10 E θ}. where θ C Rd is the parameter space, d is the dimension of the parameter 0, and 0c E is the true but unknown parameter value. The parametric assumption is satisfied in many problems; for example, in inventory control the customer demand is often assumed to follow a Poisson process (see (77) with unknown arrival rate. The cost time stage is assumed to be a function of state st, action de, and randomness & i..., Co(st, ae Et).
3

---

We start with prior distribution Ao over the parameter space θ, which captures the initial uncertainty in the parameter estimate from initial data set and can also incorporate expert opinion. Then given an observed realization of the data process, we update the posterior distribution b4 according the Bayes' rule. Let the policy be a sequence of mappings from state s; and posterior μr to the action space, i.e., π = (T Te S x M, + A, = 0, ... T - 1/. where M, is the space of posterior distributions at time stage t. Now we present the BR MRP formulation below.
min Pro Py--0o) [Co(sv, 0o, Co) + + Ppr P (((0r-))) (Cr-1 or ar Ex Cr(sr)]]
(2)
s.l. 8141 = ge (s1, ai, (,) 1= 0.... ,T - 1; (0)5 (Ex; 0)
(3)
(++ To (0) (Ex; 0) de'
t= 0, ,
(4)
where a = (5( Me), 0g is a random vector following distribution μ4,, ((=00) denotes the expectation
with respect to &r ~ [(; 0,) conditional on O,, and Pu. denotes a risk functional with respect to O, pec. We assume the last-stage cost only depends on the state, hence denoted by CT())). Equation (3) is the transition of the state 8c, and without loss generality we assume the initial state so takes deterministic value. Equation (4 is the updating of the posterior 14 given the prior po.
3.3 Time consistency and dynamic programming
is important to note that the BR-MDP formulation (2) takes nested form of the risk functional. primary motivation for considering such nested risk functional is the issue of time consistency (see R0 ), which means that the optimal policy solved at time stage 0 still optimal for any remaining time stage / 2 with respect to the conditional risk functional, even when the realization of the randomness & is revealed up to that time stage. contrast, optimizing a static risk functional can lead to "time-inconsistent" behavior, where the optimal policy at the current time stage can become suboptimal in the next time stage simply because a new piece of information is revealed (see (28 )
28 29
To illustrate, consider the simple case of a three-stage problem where the risk functional i CVaR with confidence level a. Our BR-MDP solves a nested formulation
min Pro E(--00) (Co aos fo) + Ped (C (:) C2 aq.ag
while the non-nested counterpart solves
min Pru (so, ao. {o) + Ci,, + C2(2)), 00.01
where the expectation is taken with respect to (w.rt.) the joint distribution of En and &1, and the static risk functional is applied to the total cost. Then we have the following relation between the two formulations:
Pro (e (Co a. Eo) + Pa: Byc [C (11, (1) C2(2))]
2 Pro (( [Co(so, no. Eo) + 1e C11, &1) + C2(2))
Pro E(Co an, Eo) C1 C2(s2)).
where the inequality justified by CVaR being the right tail average of the distribution, and the equality follows from the tower property of conditional expectation. The upper bound is used to show that the static risk functional always yields a higher total expect cost than the nested risk functional, illustrating the benefit of nested risk functional which originates from time consistency.
Another drawback of the static formulation for general risk functional is the lack of dynamic programming equation. In particular, 22] points out that for the static formulation, the derivation of the dynamic programming equation is based on the interchangeability principle and the decomposability property of the risk functional, where such decomposability property holds only for expectation and max-type risk functionals. On the other hand, for our nested formulation 2 the corresponding dynamic programming equation is easily obtained as follows:
Vi' (st, 14) = min a,EAA Pr. (((..)) (st,,, 0e, Ee) + Vit (8L41, 11+1) ) $t, Mr, ai) Yst, H4s, (5)
where 8, and #r follow equation and (4) respectively. Therefore, our BR-MDP formulation provides a time-consistent risk-averse framework to deal with epistemic uncertainty in MDPs. The exact dynamic programming is summarized in Algorithm I for benchmark purpose.

---

Algorithm 1: Exact dynamic programming for finite-horizon BR-MDPs.
input: finite horizon T, initial state 80, prior distribution /oo:
output: optimal value function Vo (So. Ho) and corresponding optimal policy n";
set Vi (ST: (T) = (TT)), V(ST:PT) E S x Mc;
for & 4 T do
for each (#t, (4)) E x M₁ do solve dynamic programming equation (5); set m (St, == a; where aj attains (s),
end
end
4 An Analytical Approximate Solution to BR-MDPs
Although the exact dynamic programming works for general risk functional, there are two challenges to carry it out. First, the expectation and the risk functional are generally impossible to compute analytically and estimation by (nested) Monte Carlo simulation can be computationally expensive. Second, the update of the posterior distribution 14; does not have a closed form in general and often results in an infinite-dimensional posterior. We circumvent the latter difficulty by using conjugate families of distributions (see Chapter 5 in [31,, where the posterior distribution falls into the same parametric family as the prior distribution, and thus maintain the dimensionality of the posterior to be the finite (and often small) dimension of the parameter space of the conjugate distribution. However, the posterior parameters usually take continuous values and hence BR-MDP with the augmented state (s. μ4) is a continuous-stee which is the equivalent transformation of a POMDP by regarding the posterior distribution of the unobserved state (belief) state (see (32), and posterior distribution J4, is just like the belief state in POMDP in the sense that both are posterior distributions updated via Baye's 's rule. This observation motivates algorithm development in this section.
MDP. We note that this continuous-star MDP resembles belief-MDP,
Specifically, we derive an efficient approximation algorithm for the BR-MDP with the risk functional CVaR. The main idea is that for CVaR, once know the variable in [ it is reduced to an expectation of a convex function. If there a way to approximate the value function for given u, we utilize the convexity of CVaR and apply gradient descent to solve for u. Hence, proceed by first deriving the approximate value function for a fixed u and time stage. Similar to POMDP whose value function can be represented by set of so-called o--unctions, a-function representation of the value function in BR-MDP, and then derive the approximate value function based this representation. All proofs of the propositions/therrmss below can be found in Appendix.
first show an
4.1 a-function representation of the value function
By the definition of CVaR (see (T)) with confidence level we can rewrite the dynamic program- ming equation for the BR-MDE
mi(0) ([ (C(s,,)) (241(1-11 (++1)) dg ue
Vi (st, pc) min M1
d0
(6)
where we assume that & and 0 take continuous values, and the integration can be numerically approximated by Monte Carlo sampling. If & and are discrete, the integral can be replaced by summation. The next proposition shows that the optimal value function corresponds to the lower envelope of a set of a-functions.
Proposition 4.1 (a-function representation). The optimal value function in 66 can be represented by the lower envelope of set of a-functions denoted by I, = {astares i.e.
/
V, (4)
min a.er,
where (3t, uet I-a (Ja 0(E:0) (Colse, oc, {) + minows Ss ac+1(10441, 0)
(=(0)
d8 dg - 2e
5

---

Note that there is a major distinction between the a-function representations of a POMDP and BR-MDP: the optimal value function in the risk-neutral POMDP is piecewise linear and convex in the belief state (see [5] ), whereas the optimal value function in BR-MDP is no longer piecewise linear in the posterior due to the (+) operator in CVaR. In addition, it computationally impossible to obtain the a- o-functions except for the last time stage. Specifically, denote the cardinality of the 0c+1
set as | Note that for each realization of & there are | candidates for the minimizer ar+1 .(E)
which attains the minimum of Jo 04+1(5 0) Jn (E:8)]((
M4 (O)
d8. There are total of [+1||
candidates for r, let alone the optimization over u4. To deal with the difficulty in computing the
a-functions in POMDPs, [3 proposes several approximation algorithms, and later [34] extends the analysis to continuous-state optimal stopping problem by applying Jensen's inequality to the exact value iteration in different ways and obtains a more computationally efficient approximation the optimal value function. Inspired by these works, we derive an approximation approach next.
4.2 a-function approximation
In this section, we derive the a-function approximation for fixed vector (wo, "i, -r--1) 1)- Without loss of generality, we assume the cost function at each time stage is non-negative (otherwise add large constant to the cost at each time stage). For ease of exposition, we rewrite (6) as Vi (8t, = minl,,AA..E (8t, Pt, or, uz), where (7 Me, at us)
Ur T-a So (o) (f= f(;; (st, ae, {) + Vi+1($444 1e+1)) de uz)* d0. Let Vi(sts uc) == ming, (sc. He. Ge, Ue) be the "optimal" value function for a given ut. Let (s(. = ming,Er, Jo (8,, ())((()d where I, = (aa)aE and
02 (1 0) U1 1 - (Ca(st, ()((())) un min a241 (1 ())(::))))()))))))))) de. a++1
Kg( U4) serves as lower bound for Vz(se, me) (see Proposition 4.2 and is similar to the fast informed bound in POMDPs (see (33). Note that the set L. has a constant cardinality of [.A]. However, it involves minimum within an integral, which can be hard to compute numerically. Also, the lower bound is loose in the sense that could be negative, while the true CVaR value always non non-negative (due to the non-negative cost). Next, let Vi (4) == min Se (st,,, 0) (0)d0, where It- {āE]aLEA and
ār((),,) 0)= = U4 + T ( Co(oe, or, ()((s; - Ut
+ - ( 0)S(E: O)dE.
Vi(Se, serves as an upper bound for Va(se, Mt) (see Proposition 4.2), and is similar to the unob- servable MDP bound in POMDPs (see (33). obtained by discarding all observations available to the decision maker. Suppose the cardinality at time stage t + 1 is [[e+1l, then I3 has total number derive another approximate value function V that is
of [[Al[[rtal (11 candidates. In the following, bounded by V, and Vi, and is at least better than one of the above bounds. It keeps a constant number [A| of a-functions each time stage, thus drastically reducing the computational complexity. Let Vi(s., (c) = min Se (s,, (f)d()) where T. = ( and
āe(St. 0) Ut 1-a ( (((ss, - un + min
/
au41
Proposition 4.2. For all t < T and any given us R. the following inequalities hold:
V,(s,, (4) & Vi(se, (t) & Ve(se, ne), V, pt) & Ve(St. S Ve(ss,
To have an implementable algorithm, we need to use the approximate updating of a-functions iteratively and replace the true a-functions at the t time stage in 7 by the approximate ā- functions from the previous iteration. It is clear that the iterative approximations preserve the directions of the inequalities. Define u4 = (ue,'. , 1)) The approximate value function at time stage t for a given un is given by Vi Hc, ux) = min Jo (e ()) (f)dd,, where F. {āc) aae and

---

1 (st, 0) = 1
(Lg (( - min 2.
(8)
4.3 Approximate dynamic programming with gradient descent
In this section, we incorporate a-fumction approximation with gradient descent on (uo, U1." uT-1) based on the convexity of the approximate value function w.r.t. (2o, U1, -rr-)), , as formally shown in the theorem below.
Theorem 4.3. Suppose the cost function Ca(s, a, E) is jointly corvex in (s, u) for any fixed &, and the state trunsition function gi ge(s, 0, E) is jointly convex in (s, a) for any fixed &. Then the approximate value function Vi (1(S Pt, ut:) is convex in Uga for all t < T.
The jointly convex assumption Theorem 4.3 is common for gradient- baaeee algorithms for solving multi-stage decision making problems (e.g. (35]] It is satisfied in many real-world problems such as
inventory control (e.g. (36]) and portfolio optimization (e.g. 337 We present the full algorithm in Algorithm
Algorithm 2: Approximate dynamic programming for
CVaR BR-MDPs.
input: finite horizon T. initial state $u. prior distribution Nos initial vector
u = (ug. uf.... ... -)--)). gradient descent step size 77 for = 0, 0,1, initialization: set (ST 0) (s(T)), VST E S, v0 E θ set
while some stopping criterion is met do for t 4 T
do
for each action a, E A. compute āi (st. 0) according to (8): end
approximate the value function (s noo u²t) mina. So (s0, 0)Ho(0) (0)d0;
compute the gradient Ba update the vector u k+1 ut 7p Bu
aVg
OV.
set l k 1.
end
output the approximate value function Vo(5o, Ho, ) and the optimal policy (3t, pt) == arg min Se (e dz () (0)c0.
Note that in Algorithm 2 when applying the gradient descent, we need to compute the gradient of the approximate value function w.r.t. the vector (uo, "1 iT. For 0%
we have
Bug
oi. = -11 (1 (1-1-a- -11 ( Colso, 26, ()(((; 0)dg - uo + min Ouo
()((;))) 2 o0) (0)
an J
where áj arg min an E. So To(5o. (0)do For via = 1,... - 1, we have
oVo Ou
[ a 1 1/ Co(so, ()) un + min / (((s),))((E)))) 2 of
1
[ σāi
Om." S(E; O(E: (o)d00
where Bu, can be computed recursively from
06 for 1 1,... 1. Ou.
The approximate value function output by Algorithm function, which shown in the theorem below.
2 provides upper bound on the optimal value
Theorem 4.4. min (st, As, up is upper bound for the optimal value function V.* Hc).
Even though the approximate value function is an upper bound on the optimal value function, we will later show in the numerical experiments that the gap between these two is small. As final note, even though we develop the algorithm for the risk functional CVaR, can be extended easily to other coherent risk measures. Consider class of coherent risk measures which can be represented in the
7

---

following parametric form R(Z)= == AMA (2, where V : RR A function and (2, X) is convex A). CVaR is an example such coherent risk measure. As another example, consider the following coherent risk measure based on Kullback-Leei which is also an example given 35 Here the risk functional takes the form
A- - R is a real-valued
divergence
38
(Z) = inf de + 7.A20
Ae
3/A T
2/A
}
where is the user-defined ambiguity set size. It can be easily checked that this coherent risk measure takes the required form R(2)= := infxeA E (Z, A)], for some À and y function. We can write the dynamic programming equation for the BR-MDP with the above coherent risk measure
az {1 mn(onv ((E:0) (C, 92, <) + VV (8141 ((41)) dg, X X
/
(8 Me) = min a.EA A.EA
Following the same procedure, we can use a-function to represent the value function, apply the same technique to approximate the a-functions for a given vector Au. , -Ar-1, and then apply gradient
descent on the upproximate value function. The convergence is guaranteed due to the convexity. Since the derivation of a-function representation and approximation (obtained by applying Jensen's inequality) are essentially the same, we omit the full procedures.
5 Numerical experiments
We illustrate the performance of our proposed formulation and algorithms with two offline planning problems.
(1) Gambler's betting problem. Consider gambler betting in the casino with initial money of so. At each time stage the gambler chooses how much to bet from a set 1,, 2, 3, 5). The gambler bets for T rounds. The cost at each time stage is -a- E. where stands for action of how much to bet, 5 = 2 stands for win, & -1 stands for loss, and the winning rate
[g 2) unknown. We add a constant c = 10 make the adjusted cost c & non-negative to run our algorithm (since the algorithm requires non-negative stage-wise cost), and then subtract cT' from the resultant total adjusted cost to recover the total cost. The data set consists of historical betting records with size N.
(2) Inventory control problem. Consider a warehouse manager with initial inventory level so- At each time stage the manager chooses how much to replenish from the 1, 8). where M = 15 is the storage capacity. The customer demand is a random variable following Poisson distribution with parameter 6 truncated below Mc 20, which is the maximal customer demand the warchouse can handle. The state transition is given by Sc+1 max(s; 9t a₁ εe, 0). the cost function given by C (st. ae, { h4 max(s; E., 0) + P: max(E, s; ae, 0). where h; is the holding cost and is the penalty cost. The final stage cost is set to 0 for simplicity. The manager has to plan for 6 time stages. The data set consists of historical customer demands with size N.
We compare the following approaches.
(1) BR-MDP (e.): exact dynamic programming (Algorithm) D. where the state 8, and 14, are discretized to fine grid carry out the dynamic programming (see Appendix for details).
(2) BR-MDP (a.): approximate dynamic programming (Algorithm)
(3) Nominal: maximal likelihood estimation (MLE) estimator 0 is computed from the given data, and then policy is obtained by solving the MDP with parameter OMLE.
(4) DR-MDP: distributionally robust MDP presented in 1
For each of the considered approaches, we obtain the corresponding optimal policy for a same data set, and then evaluate the actual performance of the obtained policy on the true system. i.e., MDP with the true parameter ().. This referred to as one replication, and we repeat the experiments for 100 replications on different independent data sets. Results for the gambler's betting problem can be found in Table Ta Table 2 Figure and Figure Tb Results for the inventory control problem can be found in Table lb

---

Table 1: Average time to solve each formulation, mean and variance of actual performance of the solved policy on 100 replications. Data size N = 10.
0 =
0.45
8 =
0.55
0 = 12
Approach
time(s)
mean
variance
mcan
variance
time(s)
mean
variance
BR-MDP (e., a = 0.4)
65.52
-8.82
9.92
-17.83
8.24
2951.12
81.63
5.15
BR-MDP (a., 0.4)
5.02
-8.26
11.42
-17.16
6.50
224.57
83.55
12.82
Nominal
0.74
-6.30
26.46
-17995
34.22
2.58
84.44
54.17
BR-MDP (c., a 1)
67.83
-2.38
7.02
-4.25
4.49
2947.20
83.25
3.46
DR-MDP
0.69
0.00
0.00
0.00
0.00
2.44
99.77
0.00
(a) Betting problem.
(b) Inventory problem.
Table 2: Mean and variance of actual performance in the betting problem. Data size N varies from 5, 10, to 100. Experiments are run on 100 replications.
8" = 0.45
0
0.55
Approach
meun
vartance
mean
vartance
meam
variance
meun
Vartunce
meam
Vartance
meun
Vartance
(C. = 0.4)
-7.83
14.67
-8.82
9.92
-9.26
7.31
-16.27
13:05
-17.83
8.24
-18.12
3,50
BR MDFM (a.. a 0.4)
-7.21
15.44
-8.6
11.42
-9.13
7.73
-16.12
15.52
-17.16
6.30
-17.89
6.20
Nominal
-5.88
54.12
-6.30
26.46
-9.45
9.92
-15.85
46.92
-17.95
34.22
-18.25
6.92
BR-MDP 1)
-2.12
6.06
-2.38
7.02
-1.15
3.42
-3.05
8.35
4.25
4,49
-1.36
2.46
DR-MDP
-0.10
1.09
0.00
0,00
0.00
0.00
-0.12
1.31
0.00
0.00
0.00
0.00
Table [ reports the average computation time to obtain the optimal policy and the mean and variance of the actual performance of the obtained policy over the 100 replications. Table rrrporrs rrble[]reports the actual performance of different formulations over 100 replications with different data size N = 5, 10, 100. We have the following observations.
(1) Robustness of BR-MDP: BR-MDP is the most robust in the sense of balancing the mean (smaller mean cost) and variability (smaller variance) of the actual performance of its solution. In contrast, the nominal approach has much larger variance, especially when the data size is small, indicating it is not robust against parameter uncertainty. On the other hand, DR-MDP is overly conservative since the variance of actual performance is and the mean is the largest (i.c., the worst) among all approaches. This conservativeness is often not desirable: for example, in the betting problem, DR-MDP always chooses the conservative action "not bet",, which is obviously not optimal when d (probability of winning) is large and the goal is to minimize the expected cost.
Efficiency of the approximation algorithm for BR-MDP: the computation time of the approximation algorithm for BR-MDP is less than 1/10 of that of the exact algorithm, while the performance (mean, variance) is not much different.
(3) Larger data size reduces parameter uncertainty: as expected, as we have more data, the uncertainty about model parameters reduces. Hence, the benefit of considering future data realization in BR-MDP decreases compared to the nominal approach, resulting in their similar performance when the data size is large (N = 100 in our examples). The reason is that both the posterior distribution (used in BR-MDP) and the MLE estimator (used in the nominal approach) converge to the true parameter as data size goes to infinity.
Figure la shows the histogram of actual performance over 100 replications for the nominal approach and CVaR BR-MDP (exact) with different confidence levels = 0.1, 0.5, 0.99 under 0 0.45. We have the following observations combining Table [ Figure Ta
Robustness of BR-MDP: BR-MDP (both exact and approximate) produce more consistent solution performance across a wide range of input data compared to the nominal approach, which can be seen from the smaller variance in Table [ [nd more concentrated distribution of the actual performance in Figure Ta
(2) Benefit of learning from future data realization (time consistency): Figure la shows that in the betting problem with 6 = 0.45, the nominal approach has 40 replications where MLE estimator OMI.E. < 0.33 and the gambler chooses not to bet, which is not the optimal action. In contrast, BR-MDP formulation learns from the future data realization and updates its posterior distribution on 0. As a result, in those 40 replications, the gambler initially chooses not to bet, but after some time chooses to bet, which results in the left-shift of

---

100
BR-MCP lexact, 0.13
CVaR BR. SR-MDP jexact,
Nominal
DR MDP
Fequency
60
-20
-30
20
BR-MDP (approx, a 0.4)
BR-MDP (exact, a044
je(l) pol2) so(3) px(4) se15) pe16) pa(?) (=(9) prior distribution
actual performance
(a) Histogram of actual performance over 100 replica- tions for CVaR BR- BR-MDP (exact) with different a.
(b) Value functions of CVaR BR-MDP (exact and approx) under different priors.
the actual performance distribution. This illustrates time consistency (or in other words, adaptivity to the data process) of our BR-MDP formulation. This illustration is even more evident by the comparison between DR-MDP and BR-MDP with 1 (CVaR with = 1 corresponds to the worst-case measure), where the only difference is that BR-MDP takes nested form of risk functional while DR-MDP uses static one.
Effect of risk level: risk level a affects the conservativeness of BR-MDP; as a increases, the gambler is more likely to take a conservative action (which is not to bet), so the actual performance distribution will shift more the right.
(4) Effectiveness the approximation algorithm for BR-MDP: Figure Tb plots the value function Vi (#o: (o) of BR-MDP (exact) and Vo (so, (o) of BR-MDP (approx) under differ- ent prior distributions μo with 0 0.45, verifying Theorem 4.4 that Vi (30, (4) is indeed upper bound for Vi (so, Mo) but the difference between these two is small.
Conclusion
In this paper, we propose robustness against parameter uncertainty in MDPs. BR-MDP a time-consistent formulation with a dynamic risk functional that seeks the trade-off between the posterior expected performance and the robustness in the actual performance. For finite-horizon BR-MDP with the CVaR risk functional, we develop efficient approximation algorithm by drawing connection between BR-MDPs and POMDPs and deriving an approximate alpha-fun functi-f representation that remains a low computational cost. Our experiment results demonstrate the efficiency the proposed approximate algorithm, and show the robustness and the adaptivity to future data realization of the BR-MDP formulation.
formulation, coined Bayesian Risk MDP (BR-MDP), provide
One of the limitations of work is the parametric assumption the distribution of randomness. In the future work, we wish to extend the BR-MDP formulation to non-parametric Bayesian setting, and evaluate the performance of the proposed formulation and algorithm real-world data sets in more challenging problems. In addition, the proposed alpha-function approximation algorithm provides an upper bound of the exact value, while there no theoretical guarantee on the gap between the two. In future we will develop more efficient approximation algorithms with a convergence guarantee, such as methods based on stochastic dual dynamic programming. There are also other interesting directions, such as extending the BR-MDP formulation to an infinite horizon problem and utilizing function approximation improve the scalability of the proposed approach to more complex domains.
Acknowledgments and Disclosure of Funding
The authors gratefully acknowledge the support by the Air Force Office of Scientific Research under Grant FA9550- 189550-19111 -0283 and Grant FA9550-22-1-0244, and National Science Foundation under Grant DMS2053489.
10

---

References
[1] Huan Xu and Shie Mannor. Distributionally robust markov decision processes. In J. Lafferty, C. Williams, Shawe-Taylor. R. Zemel, and Culotta, editors. Proceedings of the 23rd International Conference on Neural Information Processing Systems, 2010.
[2] Alexander Shapiro. Tutorial on risk neutral, distributionally robust and risk averse multistage stochastic programming, European Journal of Operational Research, 288( (1): 13, 2021.
[3] Enlu Zhou and Wei Xie. Simulation optimization when facing input uncertainty. In L. Yilmaz, W. K V. Chan, I. Moon, T. M. K. Roeder, C. Macal, and M. D. Rossetti, editors, Proceedings of the 2015 Winter Simulation Conference, pages 3714-3724, 2015.
[4] Di Wu, Helin Zhu, and Enlu Zhou. A bayesian risk approach to data-driven stochastic optimization: Formulations and asymptoties. SIAM Journal on Optimization, 28(2):1588-16 2018.
[5] Richard D Smallwood and Edward Sondik. The optimal control of partially observable markov processes over a finite horizon. Operations research, 21(5):1011-1088, 1973.
[6] Philippe Artzner, Freddy Delhaen, Jean-Mare Eber, and David Heath. Coherent measures of risk. Mathe- matical Finance, 93):203-228, 1999.
[7] Arnab Nilim and Laurent Ghaoui. Robustness in markov decision problems with uncertain transition matrices. In S. Thrun, L. Saul, and B. Schölkopf. editors, Proceedings of the 16th International Conference on Neural Information Processing Systems, 2004.
[8] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-29) 2005.
[9] Erick Delage and Shie Mannor. Percentile optimization for markov decision processes with parameter uncertainty. Operations research, 58( ():203)32233 2010.
[10] Wolfram Wiesemann, Daniel Kuhn, and Ber; Rustem. Robust markov decision processes. Mathematics of Operations Research, 38( (1)) (88())1133-11)) 153--183, 2013.
[11] Marck Petrik and Reazul Hasan Russel. Beyond confidence regions: Tight bayesian ambiguity sets for robust mdps. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, 2019.
[12] Michael O. Duff. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. Ph.D. diss., University of Massachusetts Amherst, 2002.
[13] Ronald A Howard and James Matheson. Risk-sensitive markov decision processes. Management science, 18(7):356-36, 1972.
[14] Andrzej Ruszczyúski. Risk-averse dynamic programming for markov decision processes. Mathematical programming, 125(2):235 261, 2010.
[15] Marek Petrik and Dharmashankar Subramanian. An approximate solution method for large risk-averse markov decision processes. In Nando de Freitas and Kevin Murphy, editors, Proceedings of the Twenty- Eighth Conference on Uncertainty in Artificial Intelligence, page 805-814, 2012.
[16] Takayuki Osogami. Robustness and risk senksttesstiiit in markov decision processes. Pereira, C. Burges, L. Bottou, and K. Q. Weinberger, editors, Proceedings of the 25th International Conference on Neural Information Processing Systems, 2012.
[17] R. Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2: 21-41, 2000.
[18] Nicole Bäuerle and Jonathan Out Markov decision processes with average-value-at-risk criteria. Mathe- matical Methods of Operations Research, 74(3)336133) 2011.
[19] Yinlam Chow and Mohammad Ghavamzadeh, Algorithms for evar optimization mdps. In Z. Ghahramani. M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Proceedings the 27th International Conference on Neural Information Processing Systems, 2014.
[20] William B Haskell and Rahul Jain, A convex analytic approach to risk-aware markov decision processes. SIAM Journal on Control and Optimization, 53(3):1569-1555 2015.

---

[21] Yinlam Chow, Aviv Tamar. Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision-making: optimization approach. In C. Cortes, D. Lee, M. Sugiyama, and R. Garnell, editors, Proceedings 28th International Conference on Neural Information Processing Syxtems, 2015.
[22] Apoorva Sharma, James Harrison, Matthew Tsao, Marco Pavone. Robust and adaptive planning under model uncertainty. In Pradeep Varakantham Akshat Kumar, Sylvie Thiébaux and William Yeoh, editors, Proceedings of the 29th International Conference Automated Planning and Scheduling, pages 410-418, 2019.
[23] Mare Rigter, Bruno Lacerda, and Nick Hawes. Risk-averse bayes-adaptive reinforcement learning. In Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Pruceedings of the 34th International Conference on Neural Information Processing Systems, pages 142-11544 154, 2021.
[24] Mahdi Imani, Seyede Fatemeh Ghoreishi, and Ulisses M. Braga-Neto. Bayesian control of large mdps with unknown dynamics in data-poor poor environments. In S. Bengio. H. Wallach, H. Larochelle. K. Grauman, N. Desa-Bianchi, and Garnett, editors, Proceedings of the 31th International Conference Neural Information Procexsing Systems, 2018.
[25] Esther Derman, Daniel Mankowitz, Timothy Mann, Shie Mannor. A bayesian approach to robust reinforcement learning, In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, pages 648-658. 2020.
[26] Martin I. Puterman, Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[27] Guillermo Gallego and Garrett Van Ryzin. Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management science, 40(8):999-,020, 1994.
[28] Takayuki Osogami and Tetsuro Morimura. Time- conesconsi of optimization problems. In Jörg Hoffmann and Bart Selman, editors, Proceedings of the 26th AAAI Conference on Artificial Intelligence, page 1945-1951, 2012.
[29] Dan A lancu, Marek Petrik, and Dharmashankar Subramanian. Tight approximations of dynamic risk measures. Mathematics of Operations Research, 40(3):655 682, 2015.
[30] Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. In C. Cortes, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Proceedings of the 28th International Conference on Neural Information Processing Systems, 2015.
[31] Robert Schlaifer and Howard Raiffa. Applied statistical decision theory. Springer Science & Business Media, 1961.
[32] Dimitri P Bertsekas. Dynamic programming and optimal control: Vol. 1. Athena scientific, 2000.
[33] Milos Hauskrecht. Value-function approximations for partially observable markov decision processes. Journal of artificial intelligence research, 13:33-94, 2000.
[34] Enlu Zhou. Optimal stopping under partial observation: Near-value iteration. JEEE Transactions on Automatic Control, 58(2):500-506, 2013.
[35] Vincent Guigues, Alexander Shapiro, and Yi Cheng. Risk-averse stochastic optimal control: an efficiently computable statistical upper bound, 2021.
[36] Hyeong Soo Chang. Michael C Fu, Jiaqiao Hu, and Steven I Marcus. An adaptive sampling algorithm for solving markov decision processes. Operations Research, 53(1):126-133 2005.
[37] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends Optimization, (3-4):157-325, 2016.
[38] Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathematical statistics, 22(1))79-86, 1951.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We describe the limitations the conclusion
section.
(c) Did you discuss any potential negative societal impacts of your work? [No] report no negative societal impacts, including but not limited to potential malicious or unintended uses, environmental impact, fairness considerations, privacy considerations, or security considerations. (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (cither in the supplemental material or as URL)? (Ys))
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g.. code, data, models) or curating/releasing new assets...
(a) If your work uses existing asscts, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 'e us-
ing/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "u53tsiI4tQY", "reviewer": "Reviewer_YVjo", "summary": "The paper presents a Bayesian risk approach for finite-horizon MDPs under uncertainty. By using some techniques from Bayesian risk optimization, the authors develop an approximation algorithm to solve the MDP problem. The algorithm is then supported by numerical experiments based on two finite-horizon offline planning problems.  The paper is well-written. Both robust MDP and Bayesian risk optimization are important areas in Machine Learning/Optimization. Thus, the problem considered is interesting and worth investigating. ", "questions": "- Page 4, line 2 is unclear, what is $\\Xi_t$. It was not defined before\n- The pdf and the version in the supplement are different. Any explanation for this? \n- Why is the conclusion missing?\n- In (6), both $V_{1}$  and $V_{t+1}$ on the both sides depend on $\\mu_t$. Should it be $\\mu_{t+1}$ on the right hand side?", "limitations": "There would be no potential negative societal impact of this work.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\nThe formulation is new.  The paper is technically sound and well written/organized. \nThe combination of MDP under uncertainty and Bayesian Risk Optimization seems interesting and promising. \n\n## Weaknesses:\n I believe the paper is not ready for publication due to several limitations as stated below:\n\nRobust MDP and Bayesian risk optimization formulations are widely studied and well understood. Thus, the results developed in the paper are quite **trivial**, given all the techniques we have in the literature. For example, Section 2 (including Algorithm1) only presents already known or trivial material. The alpha-function representation is also a direct result of equation (5) and some techniques in the Bayesian risk optimization literature. The Bellman equation in (6) is just a standard Bellman equation with a continuous state space, for which several efficient (approximation) algorithms exist, but I do not see an explicit comparison of the proposed algorithm against existing ones.  \n\nThe paper only focuses on finite-horizon MPDs which makes it limited, as many applications will require infinite MDPs\n\nSome assumptions are vague and require explanations, for example, the authors assume on Page 5 that \\Theta is finite. It is true that we can always discretize a continuous space, but it raises several questions: How to discretize, how many discrete samples would be needed?  approximation errors as a function of the discretization points...\n\nThe authors claim that their algorithm can be extended easily to other coherent risk measures. To support this point, it is better to provide formulations and results with other risk measures.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "dust7sxSeA3", "reviewer": "Reviewer_sCox", "summary": "This paper proposes a Bayesian risk MDP called BR-MDP to account for both the uncertainties in transition probabilities and costs/rewards. The model takes a nested form of the risk functional, which endows its optimal policy with time consistency. The computational difficulties in the expectation and the risk functional, as well as the posterior with a possibly infinite dimension, are two main challenges in obtaining the solution of the BR-MDP. To overcome the latter, the authors focus on the conjugate families of distributions, while for the former, the authors consider the conditional value-at-risk and derive an $\\alpha$-function approximation of the optimal value function and propose an algorithm to solve for the approximate value function efficiently. Two empirical studies are carried out to demonstrate the performance of the proposed model and the efficiency of the proposed algorithm.", "questions": "\nBelow are some other comments for the paper.\n\n$\\bullet$ Line $138$, page $4$ (Section $2$): I wonder what is the meaning of $\\Xi_t$. Is it a random variable or a set?\n\n$\\bullet$ Line $164$, page $4$ (Section $2$): by \"To illustrate\", I expect the authors to demonstrate the time consistency of the BR-MDP, but they just show that the objective value of BR-MDP serves as an upper bound for the objective of the one considering static risk functional. I would suggest the authors relate this to the concept of time consistency.\n\n$\\bullet$ Line $166$, page $4$ (Section $2$): based on formula $(2)$, should it be $\\mathcal{C}_1(s_1)$ rather than $\\mathcal{C}_1(s_1,a_1,\\xi_1)$?\n\n$\\bullet$ Line $212$, page $6$ (Section $3$): the definition $\\Gamma_t=\\{\\alpha_t\\}_{a_t\\in\\mathcal{A}}$ is confusing. Does it imply that the cardinalities of $\\Gamma_0, \\Gamma_1,...$ are all $\\vert\\mathcal{A}\\vert$?\n\n$\\bullet$ Line $294$, page $8$ (Section $4$): what is the value of $M_C$?\n\n$\\bullet$ Lines $312$ to $313$, page $8$ (Section $4$): it seems to me that the low variation of performances of a model is always desirable.\n\n$\\bullet$ Lines $334$ to $337$, page $9$ (Section $4$): the advantage of BR-MDP over DR-MDP in Table $1$ is too minor (59.64(1.42) versus 60.00(0.00)). Hence this may not be an ``evident illustration\".\n\n$\\bullet$ Line $342$, page $9$ (Section $4$): to better illustrate the claim that \"the difference is small\", I would suggest the authors provide a table to report the relative gaps (in \\%) between $\\tilde{V}^*_0(s_0,\\mu_0)$ and $V^*_0(s_0,\\mu_0)$.\n\n$\\bullet$ Could the authors briefly clarify why the exact solution of CVaR BR-MDP is computationally available in the experiments (Since they state in the first paragraph of Section $3$ that this exact solution is hard to obtain)?\n\n$\\bullet$ The sizes of the historical data are fixed to be $10$ in both experiments. I would suggest the authors vary the sample sizes to better examine the performances of the models.\n\n$\\bullet$ Could the authors explain why the computation times of \"Nominal\" and \"DR-MDP\" are not reported in Table $1$?\n\n$\\bullet$ I would suggest the authors explain why the performances of DR-MDP are not reported in Figure $1{\\rm a}$.\n\n$\\bullet$ Line $121$, page $3$ (Section $2$): \"$Z$\" should be \"$X$\"?\n\n$\\bullet$ Lines $169$ to $170$, page $4$ (Section $2$): the right-hand side of the inequality, should it be $\\mathbb{E}_{\\xi_1}$ rather than $\\mathbb{E}_{\\xi_1\\vert\\xi_0}$ (based on the independence of $\\xi_t$'s described in Lines $135$ to $136$)?\n\n$\\bullet$ Lines $205$ to $206$, page $5$ (Section $2$): should it be \"...$V_{t+1}^*(s_{t+1},\\mu_{t+1})...$\"?\n\n$\\bullet$ Lines $211$ to $213$, page $6$ (Section $3$): the statement should be: \"$V_t^*=...$, where $\\alpha_t(s_t,\\theta)=...$\". Also, what is the range of $t$ for the equations to hold?\n\n$\\bullet$ Lines $234$ to $235$, page $6$ (Section $3$): $f(\\xi\\vert\\theta)$ should be $f(\\xi;\\theta)$ for consistency.\n\n$\\bullet$ Algorithm $2$, page $7$: the algorithm should have only one \"\\textbf{output}\".\n\n$\\bullet$ Table $1$, page $9$ (Section $4$): the rows of the two tables should be aligned correspondingly.\n\n$\\bullet$ Figure $1$, page $9$ (Section $4$): it might be better to divide Figure $1$ into two figures.\n\n", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nOverall, the paper is well-written. I especially appreciate the design of the approximate dynamic programming to overcome computational inefficiency. \n\nWeaknesses:\n1. Please be very specific if the proposed framework only works with one-dimensional uncertainty, i.e., $\\theta$. If yes, please acknowledge this well and provide strong justifications. \n2. I think several key assumptions for the whole framework should be listed more clearly and frankly. For example, when talking about the $\\alpha$-function representation (a major focus of this paper), the authors hide the critical assumption that \"the parameter space is a finite set\" quite \"deep\", which does not seem to be proper to me. For another example, for Theorem 3.2, the authors require joint convexity while not providing any justification (e.g., is it easy to satisfy). \n3. I would encourage the authors to talk more about how they are motivated by \"POMDP\" and discuss the connections in more detail.\n4. In the experiments, the results are not convincing enough (\\textit{e.g.}, only one sample size is considered, and the advantage of the proposed model is not obvious,", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EivJXf0zS42", "reviewer": "Reviewer_wNPu", "summary": "This paper provides a Bayesian risk Markov Decision Process (BR-MDP) formulation to address parameter uncertainty in MDP. \n- The paper uses a Bayesian posterior distribution as opposed to ambiguity set, and imposes a risk functional on the objective function with respect to the posterior distribution. \n- Specifically, the authors assume the distribution of the randomness in the system belongs to some parametric family, and model the uncertainty over the unknown parameters via Bayesian posterior distributions. \n- Furthermore, a CVaR risk functional taken with respect to the posterior distribution on the expected total cost is proposed in a nested form to promote time-consistency solutions.\n- Finally, the authors derived a dynamic programming solution with an augmented state that incorporates the posterior information and proposes an analytical approximate solution to BR-MDP. ", "questions": "- Section 3.2, The first paragraph is hard to follow, the rewriting of equation 6 is not clear. \n- Line 233, it says $V_t(s_t, \\mu_t)$  stands for the \"optimal\" value function, what does  $V^*_t(s_t, \\mu_t)$ (equation 6) stand for? \n- Does the proposed method scale when the parameter space is high-dimensional? \n\n\nPossible typos: \n- Equation 6: rhs, $V_{t+1}^*(s_{t+1}, \\mu_t)$ should be $V_{t+1}^*(s_{t+1}, \\mu_{t+1})$\n- Line 234-235, both $f(\\epsilon; \\theta)$ and $f(\\epsilon|\\theta)$ appeared in this equation. Do they mean the same thing? ", "limitations": "The authors did not addressed any limitations and potential negative societal impact of their work. \n\n\n## Suggestions: \n###  Several ways to improve the clarity of the paper: \n  - Condense introduction part (the current version may well suited for a journal paper; but for conference paper, the space of the introduction is a bit too much) \n  - Check the notations and remove redundant information. e.g. equation 4 appears in multiple places (line 177, line 213 (integral is replaced by \\Sum). \n\n\n\n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\n- The idea of using Bayesian posterior to model the uncertainty in the parameters of MDP is intuitive and will improve the overly conservative problem in distributionally robust-MDP method. \n- Compressive theoretical analysis of the approximation are provided. \n- The proposed approximation method reduce the computation time significantly while not influencing the performance. \n\n\n## Weakness:\n- The readability of the paper suffers from inconsistency and heavy notations. \n- The paper seems unfinished since it lacks a conclusion section. \n- The effectiveness of the paper is only evaluated on simple synthetic experiments. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6tKNg66mjLJ", "reviewer": "Reviewer_TzUd", "summary": "This paper proposes the Bayesian Risk MDP (BR-MDP) framework to deal with the epistemic uncertainty in sequential decision problems. In the introduced framework, a coherent risk functional is applied to the expectation of the total cost under the posterior distribution of the model parameters. Differently from prior works, the risk functional is applied in a nested form, which preserves the time consistency of the objective and allows to write a dynamic programming equation of the optimal value function. However, solving the dynamic programming problem analytically is far-fetched. The paper thus introduces an approximate algorithm, partially inspired by POMDP methods, for a specific instance of the BR-MDP with the CVaR risk functional. Finally, the given methodology is empirically evaluated in toy domains.", "questions": "1) The work by Chow et al., 2015 [22] seems to be closely related to this submission. Although they tackle the cost-variability risk instead of the epistemic risk, they also consider a CVaR risk measure in a nested form to derive a Bellman equation (Sec. 3) that allows for approximate dynamic programming. Can the authors discuss the relation with this prior work, and especially the technical differences with respect to this submission?\n\n2) Chow et al., 2015 [22] make an interesting connection between cost-variability risk and epistemic risk. They prove that a solution that is sensitive to the cost-variability provides also robustness to the epistemic uncertainty as a by-product. Do the authors think that a similar case could be made in their setting, i.e., that a solution to the BR-MDP problem could provide some robustness to the cost-variability risk as well?\n\n3) The proposed BR-MDP framework is similar in flavor to a Bayes-adaptive approach with a time consistent risk functional over the model parameters. Can the authors discuss the impact of the time consistency? Can they explain why an approximate solution to the BR-MDP problem is necessarily better than a (possibly exact) solution to the BAMDP problem with a risk functional applied on the full trajectory rather than in a nested form?\n\n4) Is the proposed approximate methodology really practical? Can the authors comment on how the Eq. 8 could be computed/estimated in more challenging domains?\n\n5) Can the authors better explain why the Eq. 7 is significantly easier to compute than the exact Eq. 6? I guess the main benefit is pulling the min out of the expectation, but I found this paragraph quite hard to process (especially lines 218-222 could be revised).\n\n6) Theorem 3.4 characterizes the approximate value function as an upper bound of the exact value. Do the authors believe there is hope to assess guarantees on the gap between the two?", "limitations": "I think that a discussion on the negative societal impact can be avoided in this paper. However, the authors answered 'Yes' to the checklist question on the limitations of their work, but they did not provide motivation or context for their answer. Can the authors list the main limitations of their approach?", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- (Relevant Problem) This paper tackles the relevant problem of robust decision-making under uncertainty on the model parameters.\n- (Framework) I am not particularly familiar with the related literature, but to my understanding this is the first Bayes-adaptive framework that incorporates a time consistent risk measure over the epistemic uncertainty.\n- (Methodology) Since solving the BR-MDP problem is intractable in general, the paper proposes an interesting value function approximation method that is partially inspired by POMDP literature.\n\nWeaknesses\n- (Weak Empirical Analysis) The empirical analysis does not fully motivate the framework and the methodology, as the performance of the proposed approach does not seem to be significantly superior than the (not necessarily strong) baselines.\n- (Notation and Clarity) The notation is quite convoluted and not always sharp. This undermines the clarity of some portions of the work.\n\nThe premise of incorporating the sensitivity to the epistemic risk in a Bayes-adaptive framework is interesting, and also a natural continuation of the robust decision-making stream of works. The technical contribution does not seem to be ground-breaking, as most of the ideas can be traced back to previous works in cost-variability sensitivity and POMDPs, but this would be totally fine given the other contributions, i.e., the methodology and the framework itself. My main concern regards the empirical validation: It is ok for an essentially methodological/theoretical paper to have an empirical analysis in toy problems, but it should showcase the benefit brought by the method. Instead, the performance seems to be close to the baselines, especially to the naïve maximum likelihood estimator.\n\nFor the aforementioned reasons, I am still unsure on the significance of the work, and I am providing a slightly negative evaluation. However, I am open to increase my score if the authors can address my concerns on the motivation and potential of the proposed approach in their rebuttal.\n\n---\nAFTER DISCUSSION\n\nI have increased my score to weak accept to acknowledge the value of this work that emerged from discussion with the authors and other reviewers. However, I believe this paper is still missing either a stronger theoretical result on the benefit of the nested form or a stronger empirical evaluation in more challenging domains to be outstanding in any way.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept