Bayesian Risk-Averse Q-Learning with Streaming Observations
Authors: Yuhao Wang
Enlu Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: Q-learning
risk-averse reinforcement learning
off-policy learning
Bayesian risk Markov decision process
distributionally robust Markov decision process

Abstract: We consider a robust reinforcement learning problem, where a learning agent learns from a simulated training environment. To account for the model mis-specification between this training environment and the true environment due to lack of data, we adopt a formulation of Bayesian risk MDP (BRMDP) with infinite horizon, which uses Bayesian posterior to estimate the transition model and impose a risk functional to account for the model uncertainty. Observations from the real environment that is out of the agent's control arrive periodically and are utilized by the agent to update the Bayesian posterior to reduce model uncertainty. We theoretically demonstrate that BRMDP balances the trade-off between robustness and conservativeness, and we further develop a multi-stage Bayesian risk-averse Q-learning algorithm to solve BRMDP with streaming observations from real environment. The proposed algorithm learns a risk-averse yet optimal policy that depends on the availability of real-world observations. We provide a theoretical guarantee of strong convergence for the proposed algorithm.

Bayesian Risk-Averse Q-Learning with Streaming Observations
Yuhao Wang
Enlu Zhou
School of Industrial and Systems Engineering
School of Industrial and Systems Engineering
Georgia Institute of Technology
Georgia Institute of Technology
Atlanta, GA 30332 yuhaovangogatech.co edu
Atlanta, GA 30332
enlu. zhou@ise gateehhatahhhhce edu
Abstract
We consider robust reinforcement learning problem, where learning agent learns from a simulated training environment. To account for model misspecification between this training environment and the real environment due to lack of data, we adopt a formulation of Bayesian risk MDP (BRMDP) with infinite horizon, which uses Bayesian posterior estimate the transition model and impose risk measure to account for the model uncertainty. Observations from the real environment that out of the agent's control arrive periodically and utilized by the agent to update the Bayesian posterior to reduce model uncertainty. We theoretically demonstrate that BRMDP balances the trade-off between robustness and conservativeness, and we further develop a multi-stage Bayesian risk-averse Q-learning algorithm solve BRMDP with streaming observations from real environment. The proposed algorithm learns a risk-averse yet optimal policy that depends on the availability real-world observations. We provide theoretical guarantee of strong convergence for the proposed algorithm.
Introduction
Markov Decision Process (MDP) is widely applied in the Reinforcement Learning (RL) community to model sequential decision- decision-making making, where the underlying transition process is Markov Process for a given policy. The Q-learning algorithm, which was first proposed in [28]. learns the optimal Q-function of the unfinit-hhorizor MDP. The Q-function is function in terms of the state and action pair (s, a), which denotes the expected reward when action a is taken at the initial state s and optimal action is taken at subsequent stages. In Q-learning algorithm, the decision maker updates the value of the Q-function by constantly interacting with the training environment and observing the reward and transition each time. The training environment often the estimate of the real environment (where the policy is actually implemented) through past observed data. Implementing the policy learned from the training environment the real environment directly can be risky, because of model misspecification, which is caused by the lack of historical data and possible environment shift. For example, in an inventory management problem where the demand follows some unknown distribution, we have limited observations of past demand realizations or only partially observed data if unfulfilled lost orders are not observed.
One common approach is to consider distributionally robust formulation, where one assumes the
embedding unknown distribution belongs some ambiguity set. This ambiguity is usually chosen
as neighborhood of the reference distribution (estimated from data). For example, [23] considered
the distributionally robust policy learning for the contextual bandit problems, and [32 17 30 studied
the distributionally robust policy learning for the discounted RL setting. In particular, 14 and [15]
considered Q-learning methods for distributionally robust RL with discounted reward, where [4]
constructed the ambiguity set using the Kulbback-Leibler (KL) divergence whereas
[5 used the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Both works designed the Q-learning algorithm by reformulating the robust Bellman equation in its dual form, and thus, transforming the optimization over the distributions to the optimization over scalar.
Wasserstein distance;
While distributionally robust formulation accounts for model misspecification and provides a robust policy that has relatively good performance over all possible distributions in the ambiguity set, it also argued to be conservative as a price for robustness, especially when the worst-case scenario unlikely to happen in reality. This motivates us to take a more flexible risk quantification criterion instead proposed a Bayesian risk optimization
of only considering the worst-case performance. 31 29 (BRO) framework, which adopts the Bayesian posterior distribution, as opposed to an ambiguity set, to quantify distributional parameter uncertainty. With this quantification, a risk measure, which represents the user's s attitude towards risk, is imposed on the objective with respect to the posterior distribution. In this paper, we take this Bayesian risk perspective and formulate the infinite-horioon Bayesian risk MDP (BRMDP) with discounted reward.
BRMDP was first proposed in [3]. where they model the unknown parameter of the MDP via a Bayesian posterior distribution. The posterior distribution is absorbed as an augmented state, together with the original physical state, and is updated at each stage through the realization of the reward and transition at that stage. A risk measure is imposed on the future reward at each stage taken with respect to the posterior distribution at that stage. Before [3, using the Bayesian technique in MDP was considered in [8] to deal with parameter uncertainty, where they simply took expectation on the total reward with respect to the posterior distribution and referred to this MDP model as Sayes-adaptive MDP (BAMDP). Based on BAMDP, there is stream of work on model-based Bayesian RI. (e.g..
[6).. Other model-free Bayesian RL methods include Gaussian process temporal difference learning (.. Bayesian policy gradient methods [1], and Bayesian actor-critic We referred to [12] for a comprehensive overview of Bayesian RL. More recently, considered risk-sensitiv BAMDP by imposing the risk measure on the total reward. In addition, considered a percentile criterion and formulated a second-order cone programming by assuming Gaussian random reward. All three works mentioned above took non-nested formulation ie., only one risk measure is imposed on the total reward. As pointed out in [3] one benefit of the nested formulation (i.c., risk measure is imposed at each stage) is that the resulting optimal policy is time consistent, meaning the policy solved at the initial stage remains optimal at any later stage. In contrast, the non-nested formulation does not have this property (see (2I). In this paper, we considered the nested formulation as in 13.. Notably, (13 as well as most works of BAMDP considered the planning problem over finite horizon. The problem when the number of horizons is small since the number of augmented states, i.c., possible posterior distributions, increases exponentially as the time horizon increases. In this paper, we formulate the infinite-horizon BRMDP whose state space only contains the physical states. As result, this enables us to find the stationary dime-invariant) optimal policy. We develop a Q-learning algorithm to learn this stationary optimal policy, which is quite different from the dynamic programming approach taken by [13.
25
27
18
3
20
methods 26
[22] and 19
be solved efficiently only
On a related note, risk measures are also widely applied in the literature on safe RL (see 10 for a recent survey). In safe RL, risk measures are used to ensure that the learned policy not only performs well but also avoids dangerous states or actions that can cause large one-stage costs. risk measures are typically applied deal with the intrinsic uncertainty of the MDP, taking into account the known transition probability or reward distribution. In contrast, our work uses risk measures to account for parametric uncertainty in the transition probability, which can prevent finding the optimal policy. Moreover, in safe RL, the risk measure is usually imposed on some cost function to satisfy some safety constraint, while we impose it on the reward objective. Although both areas use risk measures, they have different goals and frameworks.
To summarize, all the pre-mentioned work robust RL has focused offline learning where the agent does not interact with the real environment, but only has access to data from the training environment. In contrast, offline learning process to reduce the parametric uncertainty. We also differ from Bayesian online learning, where the Bayesian posterior is updated periodically, and another optimal policy is then re-solved (regardless of computational cost) and deployed. Our approach is off-policy learning, where the learning agent receives streaming real-world observations from some behavior policy, and we focus on designing a Q-learning algorithm for the varying BRMDP that possesses statistical validity rather than simply assuming optimality is obtained after each posterior update.
work utilizes real-world data to update the Bayesian posterior in the
2

---

2 Preliminary and Problem Statement
2.1 Standard Reinforcement Learning
Consider an RI. environment M = "r..P".r:" where S a finite state space, A is a finite action space, r S A x S + R is the reward function bounded by R maxs.a,5' |r(s, a, s'),, pe = {rE (s,a)55x is the transition probabilities, and yy is the discount factor. The standard reinforcement learning aims to find (deterministic) optimal policy π : + A satisfying
V V7 = Eg' (on (r)s, - (V* = sup EE a, + 7V
aEA
2.2 Bayesian Risk Markov Decision Process (BRMDP)
The true transition probabilities, Pe, are usually unknown in real problems, and we need to estimate them using observations from the real world. However, as discussed before, model misspecification due to lack of data can impair the performance of learned policy when deployed in the real environ- ment. Hence, we take a Bayesian approach to estimate the environment and impose a risk measure on the objective with respect to the Bayesian posterior to account for this model (parametric) uncertainty. With finite state and action spaces, we can impose a Dirichlet conjugate prior Φs.a on the transition model of each state-action (s, a) pair and update the Bayesian posterior once we observe transition from state s to s' by taking action a. We defer the details of updating the Dirichlet posterior on (s, a) to the supplementary material.
The Bayesian posterior provides a quantification of uncertainty about the transition model, which a risk-sensitive decision maker seeks to address by making robust decisions using the current model estimate. This can be done by imposing a risk measure on the future reward at each stage, which maps random variable to a real value and reflects different attitudes toward risk. Given Dirichlet posterior & = {ds,a Ja. and a risk measure Pe (f) that maps a function f of the random vector to real value, the value function of BRMDP under policy is defined as
7 (so) =Edown(so) (5o) (ppi (Eai<pi [r(50: da, $1)+
(Bd)~a(ss) (Pproe di (Eezopa (r(1), d1, $2)+
BBd (paa (Bag~pa (r(2,, d2, 88) +
We assume the risk measure P satisfies the following assumption.
Assumption 2.3. Let 5 E P(R") denote random vector taking values in R", and let fi R"" > R, 1,2 denote two measurable functions. The risk measure satisfies the following conditions:
p=(xf((E) (E) for all 7 2
2. (E)) 2 (e(f((E)) (E) 2 f2(E) almost surely.
3. (E( C) ((((((() + C for all constant C.
risk measures satisfying Assumption 2.3 are similar to the coherent risk measures (see 1), except that the sub-additivity is not required. We relax the assumption of coherent risk measure to include the risk measure VaR, which does not admit the sub-additivity.
Notice I takes a nested formulation, where the risk measure is imposed on the future reward at each stage as opposed to the non-nested formulation where the risk measure only imposed once on the total reward, i.c., the value function of the classic MDP. One advantage of the nested formulation is that TT) can be expressed in recursive form:
VO (s)
Ea-r(s) (Pr-o... (Es/~plrss, s') + (s)))(
This enables us to define the Bellman operator to find the time-invarinn optimal policy. Let xO denote the optimal policy such that V == V satisfying
( sup { (Edg~T(so) (piro (Eorop (r(so, do, +1)+ #
E ( (ppareen (Boz~pa [r 82)+
((Ed)) (Pparodsgiss (Logssy ( d2, 83)
3

---

where II contains all randomized (and deterministic) policies. Let L be the Bellman operator such that
L Vs))
aEA max Pp~o.... (Berss///sppppp..e....... 8 + (V())])-
The following theorem ensures that L is contraction mapping and BRMDP admits optimal value function which is the unique fixed point L Its proof is in the supplementary material.
Theorem 2.4. BRMDPs possess the following properties:
1. L is contraction mapping with || L S <>iV Ulloo, where || sup norm in R!
llso the
2. There exists a unique V such that C*Vo. V Moreover
(50*
(ud Pmr- (Es [r(s0: do. 81)+
=eil
yE ~T(( (ppondr (Eszrpa (s1 d1, 82)
7 B (Porddagds (B (82, d2, 83) +...
2.5 BRMDP with VaR and CVaR
Among choices of risk measures that satisfy Assumption 2.3 adopt two of the most commonly used risk measures, VaR and CVaR. For random variable properly defined on some probability space, VaR, is the a-quantitle of X, VaR, (X) i=[{= I =) 2 a). and CVaR,, normally is defined as the mean of o-tail distribution X. However, since we are imposing the risk measure on the reward (regarded the negative of loss) rather than the loss, define CV)Ra(X)
1 (X) (d(())), which is the conditional expectation for X S VaR,.
Before discussing solving the BRMDP, natural question is how this risk-averse formulation is related to the original risk-neutral objective. Let Ve, denote the value function of policy under the true MDP M the difference between Vo, and Va, is bounded by the following theorem.
Theorem 2.6. Suppose the Bayesian prior (sn) 1,,s, s' and p is either VaRa or CVaR Let be deterministic policy. Let Ô millges (s,r(s) and Os be the number of observed transitions from with action N (8) in the dataset. Assuming Os.a 0.ror all (s, (s,a). then with probability at least
1-0
SS 5/S|
|V0. VG 1
Sō
V
(1 (1-7)2
In particular, let Q = min.es. Os then with probability at least 1 - 0
S 5|S|R
- llac < 5
(1-7)2
where V is the optimal value function for M
Theorem 2.6 our reformulated BRMDP coincides with the risk-neutral MDP as more obser- vations are available. In particular, the discrepancy is characterized in terms of the minimal number of observations for any state-action pair with the order at least 0 3, This indicates the BRMDP automatically balances the trade-off between robustness and conservativeness with varying numbers of observations. We defer the proof to the supplementary material due to the space limit.
2.7 Q-Learning for BRMDP
Section 2.2 ensures BRMDP is rell-formulated, that is, it admits optimal value function which can be found as the fixed point of its Bellman operator L This allows us to derive Q-Learning algorithm to learn the optimal policy and value function of BRMDP Recall that an optimal Q-function is defined as
Q0:0(s. (s, a) = Ppr-o.. (Extrp 8') "V (8'))) = Ppmoo.. (Bar (r(8, (Barsp(r,,,,,
8') + max Q (8((((()))))
bEA

---

Let T denote the Bellman operator for the Q-function. That is,
@*)(s,)) Pp-oo.. (Rx + max (()(b))).
DEA
The optimal Q-function (s, a) then satisfies
(s,a) x)Q (ss
where À E (0, 1). In Q-learning algorithm, given a sequence of learning rates {te and an estimator of the Bellman operator 7 we have the Q-learning update rule
Q++1(s,a) = (L_-)))((ss)) + X
2.8 Bayesian Risk-Averse Q-Learning with Streaming Data
Notice that in Section 2.2 and 2.7 the posterior distribution 6 is fixed across stages. As in many previous works, the embedding model is estimated with a fixed set of past observations before solving the problem. However, this one-time estimation of the transition model does not take into consideration utilizing the new data that arrive later, which helps reduce the model uncertainty as well as the conservativeness caused by risk measure, indicated by Theorem 2.6 This motivates us to consider data-driven framework where we dynamically update the estimate of the model. For this purpose, we consider multi-stage Bayesian Q-learning algorithm.
Suppose at the beginning of stage a batch observations in the form of three-tuple (s;, a, s() with batch size n(t) is available. The observation actually deployed in the real world, which does not depend on the learning process. The decision maker incorporates these new data to update the posterior d', with which obtain BRMDP model M,- We then cary out m(t) steps of the Q-learning update, where the initial Q-function in stage t is inherited from the previous stage 1. This framework shown in Figure !
be regarded generated by some policy that is
Observed
Observed (#as 2 Sppee
(#r az ynd)
(eza. Sg 4
Update posterior e(U
Update posterior (i
Update posterior 1
Update O-function m1) steps:
Update O-function for steps:
Update Q-funcion for m(() steps: 4hp Qsaiii
Qua 0
Os Quaei
Quan =0 11am
=f1 Metil
Quati mi1 "hw 1ho89 "aons F Q
+ Quaen
Q
Figure 1: Multi-stage Bayesian risk-averse Q-learning
3 Estimator for Bellman Operator
In Figure 1. key step is to design a proper estimator T for the Bellman operator ensure the convergence of the Q-function. In most of the existing literature on Q-learning, convergence relies on an unbiased estimator of the Bellman operator. While this is usually easy to obtain with the expectation operator which is linear, in BRMDP unbiased estimator for the Bellman operator is difficult if not impossible to obtain, because of (i) the non-linearity of risk measure (VaR and CVaR) and (ii) varying posterior distributions. Unbiased estimators for nonlinear functionals have been studied [2]: however, their method cannot directly applied here since the variance of estimator is uncontrollable in the existence of varying posteriors. Instead, we use the Monto Carlo simulation to obtain an estimator with almost surely diminishing bias. We show Theorem 4.3 and 4.4 that the Monto Carlo estimator is sufficient to guarantee the convergence of the Q-fucttion.
5

---

3.1
Monto Carlo Estimator for VaR and CVaR with Varying Sample Size
Denote by
f(pls, a, = + max
[(s
Σ [((s))((s,,,)8) + max Q(s', (2)
DEA
bEA
E'ES
Given a posterior and Q-function Q, we want to estimate
Q a) = Pproo.. (f(p)s, Q))),
where p is either VaRa CVaR., and (0. 1) denotes the risk level. A Monto Carlo estimator for VaR (f s, a, Q)) and (f o, Q)) with sample size can obtained by first drawing independent and identically distributed (i.i.d)) samples Pr, P2. . Qs.a- Denote by X; :=
f Q), i 1,2,...,N N. Then
VaR VaR..N (f(pls, a, Q)) = XiNa]aN
if if is VaR..
Q(s
[Na]
1 CVaR CVaR,, Q)) = [Na]
Σ XEN if CVaRa.
where XA:N is the kth order statistic out of N samples. Both estimators biased with constant sample size. Increasing the sample size reduces the bias but can computationally inefficient. As the posterior distribution concentrates can have reduced bias. We use a varying sample size that adapts to the updated posterior distribution. Initially, set Na.a fixed minimal sample size N, and decrease increase Ns.a by the beginning of each stage based on whether a new observation improves or not the estimate for the transition model on (s, a). The multi-stage Bayesian Risk-averse Q-Learning algorithms with VaR (BRQL-VaR) and CVaR (BRQL-CVaR) are presented in Algorithm
the true model, even estimators with small sample sizes
Convergence Analysis
In this section, we give the theoretical guarantee of our proposed multi-stage Bayesian risk-averse Q-learning algorithm, which ensures the asymptotic convergence of the learned Q-function to the "optimal" Q-function. We define the random observations from the real environment and all algorithm- related random quantities with respect to probability space (1) P..
Recall that the real-world transition observations assumed to be obtained from some behavior policy that is not controlled by the agents. This may possibly bring a definition problem of "optimal" Q-function. Indeed, if all streaming data are generated by some greedy policy, then the number of transition observations from some state-action pair can remain small, in which case the Bayesian posterior does converge and the learned policy is risk-averse yet random since depends on the Bayesian posterior. As in the offline RL, where the policy is learned based on the initial fixed data set, also define the optimal Q-function as depending the given real-world data but differs from pure offline RL in that the given data is streaming and random.
Definition 4.1. (Data-conditionall optimal Q-function)
Given an observation process W { { at,i, st,1)tt = 1,2, 1, (,)) 8')) and 0 (w) (0 (0% (w)) denote the number of transition observations under w. For each (8, E S x A, define the limiting posterior as
n(t). let
0 s.a.a' (w) Et= m(t) [((s,,, Or.i, s(,.) = (s, as
6pps
if 110 5.a (w)l = =c,
di 3.a
( Dirichlet + 0.0 (w))
otherwise,
where 5ps..( (+) is the Dirac measure centered at true transition probability pf.a = (FE. (5)))
Qui² is the optimal solution to BRMDP with "posterior" d², which satisfies Qui,+ = To Quit. The
data-optimal Q-function Qu.* is random vector since the observation process is random.
With this data-conditional optimal criterion, we can now prove the convergence of the multi-stage Bayesian risk-averse Q-learning algorithm. list of notations for different Q-functions can be found in Table of the supplementary material.

---

Algorithm Multi-stage Bayesian risk-averse Q-laarning
State space S, action space A, reward function r, termination stage T, Q-learning update step size {m((t) learning rate {dete, prior distribution 1 IES. minimal sample size N, risk measure p E VaaRa. CVaR.) with risk level a. Initialize Φ <- o., ((s.a) t 0, Na,a f Vs
Input:
for 1 to 7 do
Obtain n(() observations (8s, Oz, 8() i 1, n()).
for 1 to r(() do
for all (s, a) E S x Ao
o (s,a(s))
( + [(s,, as, s;) (s, a, 8')3
oe = di-1 then
Naa t N S,a +1
else
No. max(Ne.e N,
end if end for end for
for f = to (f) do
M + Σ m(t), Ar1 AM4+
for all (s. E S Aoo
Generate pı,...,PN:
1b,aa 1,2...., NN..
f(plss, Q'(s,a) - xx.) Te. No.a Q(s, a) using 3
end for Q(s, a) + Q' ((, ESXA
end for end for Output: Q-function (((ssa))(ssa)
To prove the convergence of Qt, prove (i) the convergence of Q which depends the convergence of the posterior distribution, and (ii) the convergence of the estimator for the Bellman operator. We summarize two important results in Proposition 4.2 and Theorem Due to the page limit, all the proofs are deferred to the supplementary material.
Proposition 4.2. (Convergence of Q *) Let Q be defined as in Definition 4.1 and of be the posterior distribution obtained stage L. Then the optimal Q-function under posterior distribution o' converges to Quit almost surely. That is,
lim 11Q 1000
11 0
almost surely,
where || |loc is the entry-wise sup norm.
Compared with Theorem 2.6 which characterizes the difference between the BRMDP and the original MDP by computing a concentration bound, Proposition 4.2 ensures the strong convergence of the BRMDP model to the data-conditional optimal Q-function. The next Theorem 4.3 ensures that the bias of the proposed estimator for the Bellman operator with varying sample sizes converges to zero uniformly in Q.
Theorem 4.3. (Diminishing bias for Bellman estimator) Denote by (k) the kth iteration of the Q-learning update. Let tk be the stage such that E's m(t) < < Ets m(t). Let (:R) denote the sample size in iteration is and Wt. denote all the past observations until stage ty. Denote by (1) Q(s = - (ss, a) as defined in Then, we have almost surely,
lim
sup
E E (1) Q(s.a) - T Q(s, a)swa) 0.
||II
R
Theorem provides a uniform convergence the estimated Bellman estimator, which crucial to prove Theorem 4.4 Notably, with both streaming data and risk measure, proof of Theorem 4.3 is
7

---

much more challenging than existing work on distributionally robust Q-learning, where randomness only comes from the learning process, which refers the random data generated by the simulator. In our setting, we have mixed randomness coming from both the observation process and learning process, which complicates the analysis and differs from that of pure offline Q-learning. Also, the analysis is different from online Bayesian Q-learning, where the sample complexity results are usually constructed assuming an optimal policy is resolved and deployed instantly in each period. In contrast, we aim to prove the convergence of Q-learning in order to obtain the optimal policy.
Together with Proposition 4.2 and Theorem Theorem 4.4
we establish the convergence of Algorithm | in
Theorem 4.4. Denote by Qt the Q-function given by Algorithm Mat the end of stage L. Assume T = xc, and the learning rate {de]i=1 satisfies =1=1 )e 00, 21=1 X2 x. Then, have almost surely.
lim 11Q - Q- 10000
Corollary 4.5. Let Q' be defined as in Theorem 4.4 and O be defined as in Definition 4.1 Assume
T and |10 110%allo do, Vs E S, A almost surely, Then
lim 11Q 110 =0 almost surely, 1000
where
(8) Σ ( + max (6'. d'ES
is the true optimal Q-function.
Corollary 4.5 straightforward from Theorem 4.4 which ensures Algorithm will eventually learn the true optimal Q-function if we can obtain an infinite number of observations for each state-action pair.
Numerical Experiments
5.1 Comparison Baselines:
BRQL-VaR: our proposed multi-stage Bayesian risk-averse Q-learning algorithm with risk measure VaR;
BRQL-CVaR: proposed multi-stage Bayesian risk-averse Q-learning algorithm with risk measure CvaR;
BRQL-mean: the risk-neutral Bayesian Q-learning function. That is, the risk measure the expectation taken with respect to the posterior distribution;
DRQL-KL: distributionally robust Q-learnng algorithm with KL divergence (see 14);
DRQL-Wass: distributionally robust Q-learning algorithm with Wasserstein distance (see
(15).
5.2 Testing examples
Coin Toss. Consider coins and observe the number of coins that show heads, where the chance cach coin showing heads is unknown. After observing the number of heads in the last toss, can make guess about whether the next toss will have more heads or fewer heads. If our guess is right, we can get dollar the reward, otherwise,
Example 1:
playing the following game. Each time will toss K
need pay 1 dollar. We also have the choice of not guessing, in which case we do not pay or get paid. We model this game as a discounted infinite-horizon MDP. The state 8, E {0, 1,... K} denotes the number of heads in /th toss. The actions space A = {-1,0, 0, 1), where = 1 corresponds to guess 81+1 > 8t, a = -1 corresponds to guess corresponds
8441 8t, and
guess. Hence, the reward function is
r(s. al (ace') al(s>>) |a|1 (s=a')- Assume each coin shows a head with probability 0.4. The number of coins K 10.

---

Example 2: Inventory Management. Suppose warehouse manager runs a capacity system. At the beginning of period f, the manager observes the current inventory level s, and orders additional goods of the amount 04. An ordering cost of c = 1 is incurred for each unit of goods. The demand follows a truncated Poisson distribution with a mean of and support {0, 1, ...... K.. Suppose the demand arrives during each period and is fulfilled at the end of the period. For each unit of fulfilled demand, we can obtain a profit of u = 5. I unit of demand is not fulfilled at the end of the period, the demand lost and penalty cost of q 2 is incurred. If there are any remaining goods at the end of the period, the goods will be taken to the next period with a holding cost h = per unit. The warehouse has a maximal capacity of K for the goods. We model this problem as discounted with state space S = { --K..... O..... } where (st)* = max(s, st. 0) represents the inventory level min 0) represents the lost demand at the end of period t t-1 1. The action space is A. = {0..... K 8 8*). The reward is
-oriitee MDP
at the beginning of period and (st)
r(s, a, a...ss) s') (c a + h (s')+ +.. (s')s + uas + (s)+t.
We consider two settings: (I) the demand in each period uniformly distributes among {0, I.... K} and (II) the demand depends on the current inventory level s. For the second setting, we will consider the case where observations are insufficient to estimate the transition probability for every state-action pair.
5.3 Experiment Setting
Coin toss. We consider wise streaming observations with batch size n(t) = and stage-wise Q-learning with number of steps m(t) The minimal sample size to estimate the Bellman operator N = 10. Initial observed data batch size n(0) = 10. We set the radius of the KL ball and the Wasserstein ball to be 0.1. The risk level for VaR and CVaR is set to 0.2 Figure 2 and 0.4 in Figure 3
Inventory Management. In Figure 4 We set 10, T = 60, mt) n(t) 5, n(0) 20. and N = =10 The radius of the KL. and the Wasserstein ball is 0.05, and the risk level for VaR and CVaR 0.2. In Figure 5 we set the capacity К 10 and the size of the historical data set n0) 30. The policies are deployed in different environments, where the demand follows different truncated Poisson distributions with means ranging from 3 to 5.
5.4 Results
In Figure 2 we compare the value functions of different algorithms as the time stage increases. The value function each algorithm is calculated by deploying the optimal policy in the real environment. Each curve shows the empirical expected performance and the strip around the curve shows the 95% confidence interval. In both examples, our proposed algorithms outperform the two distributionally robust Q-learning algorithms in both expected performance and variation as the time stage increases, since our proposed algorithms dynamically update the posterior to reduce the model uncertainty while two DRQL algorithms learns with fixed ambiguity set. Compared with the risk-neutral algorithm, BRQL- VaR and BRQL-CVaR achieve lower expected value functions but have smaller variations, which shows the robustness of our two proposed algorithms.
Moreover, in Figure We test for the insufficient data setting, where we only have a set of historical data to estimate the transition model at the initial time stage. The value function is calculated as deploying the learned policy in different environments with demand following different Poisson distributions. Figure Figure5Jjnniccee iindicates the two proposed algorithms achieve higher value functions than the risk-neutral algorithm in the more adversarial setting (with Poisson parameter less than 3), showing their robustness. They also obtain lower value functions than two DRQL algorithms in the adversarial setting and higher value functions in other settings, indicating the risk measure is more flexible compared to the worst-case criterion.
6 Conclusion and Limitation
In this paper, we propose novel multi-stage Bayesian risk-averse Q-learning algorithm to learn the optimal policy with streaming data, by reformulating the infinite-horizon MDP with unknown transition model as aifiite-horizon BRMDP. In particular, we consider the two cases of risk

---

432
407
259
BBC MKL-meer
200
BRgi-maar
aagi-Call
BROL /m
#PGL/WA
2.3-
<aage
Figure 2: Coin Toss: risk level or 0.2
Figure 3: Coin Toss: risk level = 0.4
ERAO IIANN BROL-CWA
220
73-
35
Figure 4: Inventory Management: streaming observations
Figure 5: Inventory Management: fixed BR- MDP
measures, VaR and CVaR, for which we design a Monte Carlo estimator with varying sample sizes to approximate the Bellman operator of BRMDP. We demonstrate the correctness of the BRMDP formulation by providing statistical guarantee and prove the strong asymptotic convergence of the proposed Q-Learning algorithm. The numerical results demonstrate that the proposed algorithms are efficient with streaming data and robust with limited data.
As discussed in the paper, one limitation of the current framework is that the behavior policy that generates real-world observations assumed to given. This suitable for situations when is expensive for the agent to interact with the real environment or to change the policy frequently as may cause large cost or system instability. An interesting future direction learning setting, where at each period the agent also needs to take action in the real world.
consider an online
ACKNOWLEDGMENT
The authors gratefully acknowledge the support by the Air Force Office of Scientific Research under Grants FA9550- 1-0233 and FA9550-22-1-028 and the National Science Foundation under Grant NSF-DMSS0533889.
AUTHOR BIOGRAPHIES
Yuhao Wang a Ph.D. student at the Milton Stewart School Industrial and Systems Engineering at Georgia Institute of Technology. He received his B.S. degree from the Department of Mathematics at Nanjing University, China. in 2021. His research interests include simulation and stochastic optimization and reinforcement learning. His email address is yuhaowang @ gatech. edu gatech. edu/yuhaovang/
and his web page httts:://ssite
Enlu Zhou Professor at H. Milton Stewart School Industrial and Systems Engineering at Georgia Institute of Technology. She received the B.S. degree with highest honors in electrical engineering from Zhejiang University, China, 2004, and received the Ph.D. degree in electrical engineering from the University of Maryland, College Park, in 2009. Her research interests include
10

---

simulation optimization, stochastic optimization. and stochastic control. Her email address is enlu.zhon@isye gateehh.gaehhhddu and her web page hs/https:///ett www.zwou..u.uuu..ooo.uu. http:/ww....iu....ggaaao...... edu/
References
[1] Philippe Artzner, Freddy Delbaen, Jean-Mare Eber, and David Heath. Coherent measures of risk. Mathematical finance, 9(3):203-22) 1999.
[2] Jose H Blanchet, Peter Glynn, and Yanan Pei. Unbiased multilevel monte carlo: Stochas- tic optimization, steady-state simulation, quantiles, and other applications. arXiv preprint arXiv: 09009, 2019.
[3] Pablo Samuel Castro and Doina Precup. Using linear programming for bayesian exploration in markov decision processes. In IJCAI, volume 24372442, 2007.
[4] Richard Dearden, Nir Friedman, and David Andre. Model-based bayesian exploration. arXiv preprint arXiv: 100. 6690, 2013.
[5] Erick Delage and Shie Mannor. Percentile optimization for markov decision processes with parameter uncertainty. Operations research, (8(1))203-211 2010.
[6] Joseph L Doob. Application of the theory of martingales. Le calcul des probabilites et ses applications, pages 23-27, 1949.
[7] Michael O Duff.
Monte-carlo algorithms for the improvement of finite-state stochastic con- trollers: Application to eayes-adaptvve markov decision processes. International Workshop on Arlificial Intelligence and Statistics, pages 93-97. PMLR, 2001.
[8] Michael O' Gororn Duff. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. University Massachusetts Amherst, 2002.
[9] Yaakov Engel, Shie Mannor, and Ron Meir. Bayes meets bellman: The gaussian process approach to temporal difference learning. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 154-161, 2003.
[10] Javier Garcia and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
[11] Mohammad Ghavamzadeh and Yaakov Engel. Bayesian policy gradient algorithms. Advances in neural information processing systems, 19, 2006.
[12) Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, Aviv Tamar, et al. Bayesian reinforce- ment learning: A survey. Foundations and Trends@ in Machine Learning, 8(5-6):359-455 483, 2015.
[13] Yifan Lin, Yuxuan Ren, and Enlu Zhou. Bayesian risk markov decision processes. In Advances Neural Information Processing Systems, 2022.
[14] Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou. Distributionally robust g-learning. In International Conference on Machine Learning, pages 13623-13643, PMLR, 2022.
[15] Ariel Neufeld and Julian Sester. Robust q-learning algorithm for markov decision processes under wasserstein uncertainty. arXiv preprint arXhv:2210.00895 2022.
[16] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
[17] Kishan Panaganti and Dilcep Kalathil. Sample complexity of robust reinforcement learning with generative model. In International Conference on Artificial Intelligence and Statistics, pages 9582-9602. PMLR, 2022.
[18] Pascal Poupart, Nikos Vlassis, Jesse Hoey, and Kevin Regan. An analytic solution to discrete bayesian reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pages 697-704, 2006.

---

[19] Mare Rigter, Bruno Lacerda. and Nick Hawes. Risk-averse bayes-adaptive reinforcement learning. Advances in Neural Information Processing Systems, 34:1142-1154, 2021.
[20] Stephane Ross, Brahim Chaib-draa, and Joelle Pineau. Bayes-adaptive pomdps. Advances in neural information processing systems, 20, 2007.
[21] Alexander Shapiro. Interchangeability principle and dynamic equations in risk averse stochastic programming. Operations Research Letters, 45(4))377-381, 2017.
[22] Apoorva Sharma, James Harrison, Matthew Tsao, and Marco Pavone. Robust and adaptive planning under model uncertainty. Proceedings of the International Conference on Automated Planning and Scheduling, volume 29, pages 410-418, 2019.
[23] Nian Si, Fan Zhang, Zhengyuan Zhou, and Jose Blanchet. Distributionally robust policy evaluation and learning offline contextual bandits. International Conference on Machine Learning, pages 1884-8894. PMLR, 2020.
[24] Satinder Singh, Tommi Jaakkola, Michael L Littman, and Csaba Szepesvári. Convergence results for single-step on-policy cinforoement-leaminng algorithms. Machine learning, 38(3):287-308, 2000.
[25] Malcolm Strens. bayesian framework for reinforcement learning. In ICML, volume 2000, pages 943-950, 2000.
[26] Richard Stuart Sutton. Temporal credit assignment in reinforcement learning. University of Massachusetts Amherst, 1984.
[27] Tao Wang, Daniel Lizotte, Michael Bowling, and Dale Schuurmans. Bayesian sparse sampling for on-line reward optimization. In Proceedings of the 22nd international conference on Machine learning, pages 956-963, 2005.
[28] Christopher John Comish Hellaby Watkins. Learning from delayed rewards. 1989.
[29] Di Wu, Helin Zhu, and Enlu Zhou. A bayesian risk approach to data-driven stochastic opti- mization: Formulations and asymptoties. SIAM Journal Optimization, 28(2)1188--1112 2018.
[30] Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust Markov decision processes: Sample complexity and asymptoties. The Annals of Statisties, 50(6):3223-322 3248, 2022.
[31] Enlu Zhou and Wei Xie. Simulation optimization when facing input uncertainty, In 2015 Winter Simulation Conference (WSC), pages 3714-3724. IEEE, 2015.
[32] Zhengqing Zhou, Zhengyuan Zhou, Qinxun Bai, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3331-3339. PMLR,
2021.
12

---

A Dirichlet Posterior on State-action Pair
Dirichlet distribution is parameterized by a count vector Φ (d)...., Øx), where o; 2 1, such that the density of probability distribution (Pi.....Ph) .P)) is defined f(p Φ) k di For each (s, a) E x A, we impose Dirichlet prior with parameter Φs.0 = (Ø (s V' on the unknown transition probability Ps.a (Ps.a (s ()))ess After we observe the transition (s, a, s') for os,a,s' times Vs' E S, the posterior distribution Ps.a also a Dirichlet distribution with parameter 6s.a + +s,a ($s.a(s') + Os.a, )),,,,))>'.. sES, where Os,a (0s,a,s)) )se..
P;
B Technical Proofs
Table I: Checklist of notations for different Q-functions.
Notation
Explanation
Q
Optimal Q-function of BRMDP with posterior
Qu
Data-conditional optimal Q-function conditioned on observation process w Q-function at stage given by Algorithm |
Optimal Q-function of the true environment
We first introduce the following lemma that guarantees the maximum taken over randomized policies equivalent to being taken over only deterministic policies.
Lemma B.1. (Deterministic Bellman operator)
(s)(s) max Pp-oo... a
+ +VV(s))))))))
sup BBe +
nell
Proof. For an arbitrary randomized policy म, an arbitrary V, denote by x(s, a) P(T(s) a). We have
sup Py~o... (E (Ben:
Σ .EAA
((s.a) (r (V (V))))
aEA
Hence,
Vs) = max Po-oo.a (Bemplrrss, 8') + +>V(s'))) 2 sup (Bawz(s) (Essmlr(ss,,, +V(ss)))) D)
a
The other direction holds naturally since a deterministic policy is also randomized policy.
Lemma B.2. (Non-expansive risk measure) Suppose the risk measure satisfies Assumption 2.3
then
Ip(f((E)) - p((((E)) (l.f(()) - f2(E)lle.oo:
where
|| 11e,,0 is the sup norm with probability measure P.
Proof.
Pe(f((E)) = p S SrA.H//A--AAAOADAACCCCCHAAAA---- RCC
Similarly, we have
pe(f((E)) < (e(f((E) + (l fa(E))ls..0.
Combining together complete the proof.
13

---

Proof of Theorem 2.4
Proof. proof of 1. V O, there exists a deterministic policy n, such that Vs S
(*)(s) S Ppross (Be's~pr(ss (()))) +V()))))))))))))))))) +e.
Then,
-
Spp-dar (B) +>v((()) - Pp-oo r()) (Ex ()) -U)(()))))))))))))))))) +e Umx)]llmmex
S 21 +
Since e can chosen arbitrarily, U, we obtain the desired result.
- S <>IV U| Switching the position of V and
proof of For the first part, since L is contraction mapping, there exists unique V such that L
V For the second part, let x' be arbitrary randomized policy. We have
vo (s)
(*)
sup aEA
( (pirees. (rs,,,)( *VV"
sup Σ sell aEA
(s, a)s. (B [r(s, +
Σ n' a (E (E (r (rssss 7 (s,))
aEA
where the third equality holds because of Lemma B.I
Furthermore, by Assumption 2.3 2, we get
vol*
Σ मt' (s. apprnds (Es [r(s, a, s1)
Σ
x'(51, a1 (1)pppppss,,, (Ber (Bes,g.l1(11, C1, 82) 82) (s2))))
aEA
ALEAA
(4)
Define C such that Vs E S and V E TR(S
C
V(8)
Σ a asss (Bs ((((i))
aEA
By the same induction as
we can derive
v 2 (c )ooo,, Ak 2 1.
Define
7' (l5.a)pproo..... (fs (Bs V0.= (8) Σ
aEA
and
p4+1a
Σ (s, ap (B (Eg)-pl((s,,,s)) + V (81)))-
REA
By Assumption 2.3 and Lemma B.2 have
(o.*(s) 2 (c VV): 2 (kr (s) ~
(5)
As + 00,
x+1 R 0,
|o,x' (8) (s) yb.s (s))
++ x 1loc S
1-7
where Vdl'r is the value function BRMDP with posterior ø and policy n'. Then from 5 we obtain
k+1 - 1- R. V.
Vo.+ (s) Vo. (8) (
By taking & oo, we have (8.+(s) 2 Vd.a (s). Since n' is chosen arbitrarily, we get the desired result.
14

---

Proof of Theorem 2.6
Proof. Denote by
8'E8
We first bound [f(pls, a, V) f(vlss, a, V) in terms of ||p p' 1loo for |V & r- To see this,
R.
1('',,,
D(p(r) (()0)))(((
1ES
S|S| R + ||V||=>||| 1'110
(6)
|t 1 || p' Ioc.
Now consider &s.a. Since 6% = 1, we have the posterior parameter (s.a = Os,a,'' + 1, where o(s, a, s') is the number of transition from s to s' taken action a in the data set. Let M denote the empirical MDP generated with the same data which are used to estimate é, with the empirical transition probability (s.) Ox.a.z' Let Pf be the true transition distribution. Since On,
(0x,a,s) ''E follows the multinomial distribution with parameter ss.ai P2,ar we have
P( - (s)) -
S o
a S
O
by Chebyshev inequality. Define
)s.a(s')
0s.a. + 1
(s.a = Eprora [p(s')]
ExrEs 2onl
Os,a + 181
and
(xa( (s,a(8)
02)((')) Cpposall((s' (s))()
1 17:01 (11db,al1 + 1)
10 ||
O + |
Notice
lo(s') )a.a('') <lp(s') Ps.a (s)) (s,a(s') (s)a
=lp(s') -Ps.a (
0s.a,s' + 1
0s.,ss
Ox,a + S
O Os.a
<lp(s') -s)a(s')1+ +
Os.a
15

---

Since |S| 2 1,0 2 / 0
1
2 0. Then, with probability at least 1
Os 4
0s,a
[8]
S
Ppvds.
(p(s') - P (s')) 2 3/
Oz,a
S
SP prod.
(p(s') (s 2 31
0,
(e.a(s') - (. ]1
(Daal')) Po
|8|
1
S
S prod.
(p(s') Ps.a 21133 3/
0.
s,a
a
Os,a
a
S 0 a,0
SP prod.
(p(s') Po,a(s')1
α
S 0 8.
SP prdd.c
(p(s') -
α
a0%
5,a (5')
18
S
where the second last inequality holds by Chebyshev inequality. Replacing with (s)), obtain with probability at least
|ST s,T(s)
O0. 2 1
P Prids.nno
(p(s') - Ph (s)( 2 3
S
1 1,
a
a
S
This further implies with probability at least 1
18/ 0-1
Pprouiie (Il-- PE 2 3/
|st
O + a e,)(
S Σ PP
Ppmos.mii (1(()))
ps (8) 3/
S - s,7(()
S a.
s'ES
Let U fellp- De 1l 33 | 1
3 (s)
Since with probability at least
a 0-3, VaR is [S]
the a-quantile, and Po... (U) 2 a, we have
inf f(pls, (s), V) S (VaR,) (aaRa)ren pore (s(p),, V)) S PEU
sup (pls,, (T)). V). pet
Hence with probability at least a 0-5
I(VRR, p (o) (f(p)s, v)) - f(= (s),, v)
< sup |f (s), V\ (1),,,)))s,, DEU'
|
sup ||p
1
pEU
(8)
S
S
<3
a
(*)
1-7
S
|
<3
1-7'
where the second last equality is by 6 Since this holds for 8, then we obtain with probability
1 - a0 $
S
S
(VaR, ) ppmee. (f(pss, ((),
f (s), 70) S
1 1-7
16

---

holds for all E S.
Finally, let fa.z denote the Bellman operator for BRMDP with posterior & and policy n, that is V = L =
(s(p),, V):))). Similar as Theorem 2.4 L is a
y-contraction mapping. We have
(s) - Vo- (s)l = =|20 (s) Con (s) + L von (s) Vo (s)
S 5| - Co. +
(s) - V0 (s)l
- - -va + | (s) (s)l.
Since ||V 1loc R Maximize over on both sides, we obtain
I-X- have the second term [LONVen Ven S 3 | 0 by 8
||| 3/8
|V 12 S &Allvox - Ven 11 + +
a (1 (1))
Hence,
|S| 3|S|R
S| 5|S|R
| Ver 1|cc S SO-
V a 71
a (1 (1-99 7)2
For p is CVaRa, notice by we have with probability at least 1
O
(p(6') ps (s)) 2 3v
S
P dr
S
Hence, with probability at least 1 - [ST (s)(s)
2 1
P Pp-eenncs
[Ie- p (e)
[lp
100 231
|
S a0 (()(
(s)
Recall (X) is the conditional conditiooalexppecatiooooo (X S VaR (X)) LetU (pllle Paa S
3y S 2 (,)(s) and W {pl (pl.(pps,.(s))V)) s (VaRa) (f(pls, V))) for |V S
[S] I-x- Then, with probability at least - a 0-
I(CVRR)) (f(pls, -
f(a T (s). V)I
1 1/ I.mm (16)s,,(s))VV) - S (( x (8), V)d
a Swnu- (s), V)) - S( (s)) V)dP
I Jwnu |((0)s, (s)), V)) f(0 (1) |8, (s), V) dP )
+ 1 f
a wwnee ( V)) - I(P x (s), V) dP..
1/
2R
S
0 S|R
a
a (+)(
1 7
+ a
3
a (.) 7
|S| 5|S|R
<0
s,n(s)
a 1 1-7
S 5|
<ō
a 1 1-7"
Then, following the same proof as for VaR., with probability least 1 - a we can bound
S 5|8|
| - Ve I S s
V
(1 71-
This completes the proof of the first part. For the second part, let - be the optimal policy for M. Then we have for both VaR, and CVaR., with probability at least 1 - --Ō--k 1 (TT) 2 - aQ $
vo,, 2 yhn 2 yo. - - 3 / S 5| R
a (1 - "
17

---

Recall n² is the optimal policy for BRMDP, then
[|| 5/8|R
Vea
Vea
2
-oo+=
-
0
a (1 71-
Combining together the proof is completed.
Proof of Proposition 4.2
Proof. First notice
11Q Q =1/70 Q0:, - Qu:0
=1((T0) Qt' - -* -T Qu:)) (T Qu: -70
Sy1Q0 Qu00 + 1|T --= T0 Qua
almost surely, we can prove the convergence of Q if show that almost surely for each (s, a) E x A,
Since 10"
ft
1-y
sup | R
Q(s,a) T Q(s,a)) + as +
(9)
Fix a state-action pair (s, as,a), then for any observation process w, if 11 s. (w)llo < oc, 0% = 2
after some time stage and (9) clearly holds for such w. Otherwise, | (w)]l oc. For those w's,
by Bayesian consistency 6 we know that for any neighborhood of ps,a with parameter
which
defined as Ue- = {o E R EEEE p(x) = 1, lp(x) ( I e, Vx E ES.. lim P(p E Uzlot.a) = almost surely.
For any probability mass function p R Recall f(pls, a. Exspl((s,, maxieA (('' we have Vp E Us.
|/(p|s a, Q) 1 a, Q, = Σ (p))) - ps (+) + +r max ((x
BeA
JES
S 711
|
In the following we fix sample path w such that 0 (w) lox = oo and drop the notation of w for simplicity. We have almost surely:
If p is VaR,: Since P(y E Uclob (a) 1, for any risk level a 0, P(p Uz|d! a for / large enough. Since VaR,, is the a-quantitle, we have
6ie (f(pls,a,Q) > inf f(pls, Q) 2 f(p8als,a, - PEU.
|
VaR.
(10)
Similarly,
(f(p)s,a,() < sup f(pls, a, Q) ()) 1-7 VaR... 8/
|
PEt.
Combining the two inequalities above, we have
"i. |VaR (f(pls, a, Q)) - - Q)1 = 17 (x,,) T Q(s,a)) < ((s)a)))) 1- (11)
|8|R
Since this holds for any with ||Q S ft. I- and 0, we know
lim 200
sup
(T'QQ(s,a) Q(s,a) T Q(s a) = 0.
||01
R
This completes the proof.
18

---

If is CVaRa:
CVaR (f(p)s, =VaR ".. "aaaa" a, Q)) + E Bewds VaR (f(plss a.ls,, Q)) - f(gls, a, Q)) a,
a
=VaRa - (f(pls, + B Burdd /VR th (f(pls, Q)) flgls, Q]+
1 Brrdi Brrds ( s (f(pls,a, Q)) - fqq)s,,,Q))
Since VaR. 2he " (J(1ls,a,Q)) + 188 Q) and (U,) - 0, we have for large
enough t.
1. \VaRa " (f(pls,a, Q)) - f E,
2. A YEU, VaR * (f(pls, Q)) flgls, a, Q)} s 2: |SIR
E nEEg
VaR $2., (f(pls, Q)) - f(gls,a, Q)} & P(p E U 0 I-7
28
S
2s s|R
Then we obtain
CVaR the (f(pls,a, - f(p Q)1 S (1+ 4
a(1
Again, by arbitrary s and the uniformness in Q, we obtain the desired result.
Proof of Theorem 4.3
Proof. Proof sketch. The complete proof is technical. We first provide a proof sketch. Intuitively, the bias term converges since we either have posterior to concentrate the parameter or have an increasing sample size for the Monto Carlo estimator, both of which reduce the bias term zero asymptotically. However, major difficulty is uniform convergence (in terms of all possible values of Q and sample size N), for which existing results do not give a straightforward guarantee. We prove the results by considering the two cases. First, when infinite observations are available. i... ||0 Il = oc, we construct i.i.d. samples (p:)) S f
Q) with the same sampled for an arbitrary given e, where [p,ls, a, Q) is defined as in (2) with probability at least 1 - E, l((p)) takes value no less than f (pals, a, Q) by constant multiple of with probability at least E, h(p)) takes a value bounded by a constant. With the help of the Stirling formula and subtle calculation, we can bound the expectation of order statistics of hpp)), which further lower bounds the Bellman operator estimator. The upper bound can be obtained in similar way. Together we can bound the bias term. Second, the case of limited observations, we prove a uniform convergence of empirical distribution for fpp |s, a, Q) when Q belongs union of disjoint rectangular sets, to which the Glivenko- Cantelli Glivenno-Cantelli theorem can be applied and the uniform convergence of the empirical distributions follows. Combining the two cases we complete the proof.
bounded set. We carefully partition the probability space as
Formal proof. Again, we fix state- acte-actionn pair (s, a), an observation process w for which we drop the notation for simplicity. Let Q be any Q-function such that ||Q]| T We first prove for the VaR risk functional.
Estimator for VaR
we consider the two cases:
0000 oo, then Si is consistent at the true parameter Pl.- Ve > 0. PPp Ueldba
almost surely for such w. where U.
{p [R|S [ExEs((r) =1, 1,(p(x) - ( S e, Ve E {). Then Ve > 0, P(p E
19

---

Uelokaal 2 - for all large t. At iteration k such that ty large enough, we ob- (k)
tain Pi .P2 ..... : w oh For each P; we have P(pt (k) E Uglo%,a) 2 - E.
Furthermore, since Sha is always smooth function, we can find ( E Ue such that P(p, E 0 = - c. Recall
f(pls,a.
Σ (((s))((ss..ss)) + max Q(s.a))
BEA
s'ES
Define
inf f(pls, Q) PEU,
if p (k) E (
h(p
inf a
if pf (b) & (
It is easy to see f(p! (s a, Q) h(p ( Notice the distribution of sampled pia)) only depends on t (1kk) which are further determined by wte Conditioned on wh, h(p, (k))
= 1,2..... (:kk) are i.i.d. random variables taking two values infpeu, f(p a, Q) and inf, f(ps, a, Q) with probability at least inf, flpls, Q) R And
and E, respectively. Notice
inf f(/ls, a, Q) VaRa (f(pls,a, Q11 pEu.
< inf f(p|s, a, Q) - f a, Q)1 + If Q) VaR. (f(pls,a, a, Q))). pEu.
By we have ff Q) VaR (f(pls, Q)) S | for ie large enough. Hence, we obtain
By (10). we have inf, f(pls, a, Q) f(pgalls a, Q)1 هااااا
1-7
1-7
inf f(pls, Q) VaR th (f(pls, Q)) S 2: 1 1-7
||
PEu.
where ||Q1|x again can be bounded by T- Denote by X, f(: (k) |s,a, Q) and Y,
h(pp))) We first bound the conditional expectation of the order statistic Y (N [ i.e.
E|y [N1t2 J.
Since {Y/uu, are i.i.d., we can compute the conditional mass function Y Inaiin as
PPY[nal) inf [(p) Q)(w P
Σ
ed (1 -))m-
(12)
j2 na
We now lower bound the conditional expectation of M[ma]]: by upper bound 122 First,
we can show (>) e1(1 (1(1-))-= e)n is decreasing in term of for j > ne. To see this, take logarithm on the right hand side we have
n2
T()= = log(n!) log((n- - + loge + (n () log(1 - 8).
Compute the difference
j
ni + 1 log j +1 1-
Then vy( + 1) (i( < < 1)e 1. Hence for < a and j 2 na 2 ne >
(n + 1)s 1, mT(5) is decreasing. Hence can upper bound [2 by
20

---

( ([na] e elmai (1 E) n-nan
(n + - -[na))
n!.
[n + [nal)
[no]] (1 - 8) m-m= [no]
(13)
(n [aa ) na
By Stirling Formula,
n2 V2 (e)
n! < 22n
n1 n (=)
T < 2V2TT 2
71
Then we have
2/2mm 2mm
(t n g [[mal] (1 e)n--nac)
< (n + 1 - [na]]
20 - [na]] 1)
[no]]
[no]]
v [na
[noc]
/2
[no]]
)
(n + 1 [na]] 1
(1
[noil)
(1
nna] 12- [1
π [na
[na]]
[nai
For n 2 a(I-aj'
2
have
1. (n + + - [nai]) 2n)
2. g <[na]] < gno
3. (1 c)n- [ma] (1
E).
[[a]]] [no]] 2
[na] ma+1 2 n0 a.
n
n
5.
1
[nci] 1-a
(1
[nai
yn
[na]] (1
[ I )n(2-a) 2 ( (L=a)a(1-0
n
Then
E (1 e) -1) a) /(1 -6)
13
2
11 a)
1-a ) -a) / vaaa a
4 (1
(1 - --) -E)1-a
(1 8)(² VT
(0(1-a)11o
2
C
1 VT.3m
(1-a) a VT
is a constant and B (1-_)) ('11"0)1
where C
For E small enough, we can ensure
B < 1. Let
((x) = log( VI = log x + x log
Then, since log 3 < 0, ((z) attains the maximum at r
Then we have
Tog
C
C
Vn.gm
((())
g
1 e
< C
cll mg
1 -
C
2
1 -
V
log 3
21

---

For n S
a(l-o)] we have
2
P(Y n I.n inf fplss, a, ()(w))
P
<P(V im = =inf f(pls, a, (s)
=1 - (1 =
< - (1 E) u J
Let
(=( == max
e (1 [L)=)aaaal
- E
log B
where (e) 0 as -> 0.
Then we have
| Ina [w =P(Y]na): = inf f(ppp Q)(,),)))))))))))))))))))))))Q)_ (inf f Q)) + P(Y mn inf PEU:
f(pls, a, Q)(w)))
inf f(pls, a, Q)
pi
pEU.
R
2P(Ynnl]: = =inf f(pls, Q) 1 1-
inf fplss a, (w) (VaR d' VaRa"""(plss
+[(Ymna]m>
(s(pls, a, Q)) - -20
PEU,
20'(e) ( (11-)+ * (VaR," t
R
(S(pls, a, (,) - -2 R
Hence we have almost surely,
E|X IN VaR sh (f(p]s, W))
E
a VaR. (f(pls, [))
R 2 C'ss) (1-9)) ) + VaR ((plss,..1) - 2= (1=()_((()) 1-7
R
R
2 2(C'(() ( + +((1-((())))
1-7
= -(()),
where C(E) + 0 as + 0.
Similarly by constructing
sup f(p|,, Q) PEU.
(k) E w if
h(p)
sup fp p
pf (k) $ v,
We can obtain
VaR 2t (f(p)s, a, Q)) s (((s),
B[X o 1o11
almost surely for large enough and ((E) + as c -
Notice T Q(s, a) = VaR th (f(p)s, a, Q)). Furthermore, since both Ö(e) and ((s) do not depend on Q and by arbitrary s, we obtain
lim sup
- [(s))((s)) =.
ST
If 2 < 30, then the posterior distribution on (s, a) remains the same as d for all large
and the sample size (k) tends to infinity. In this case, by Glivenko-Cantell theorem,
22

---

we know almost surely the empirical distribution conditioned on 0% (which is further uniformly converges to the
determined by w), p(k) for the sampled Pi .P2
Nai
(R)
distribution 23 as sample size Nika goes to infinity. Denote by X [p;
(k) Q)
Eves Pi p (s)) s') +y maxbe Q(s' = Errss d (s') d We want to show uniform convergence empirical distribution of (x! 1i.1.2...,N.f. conditioned d5 for d E D uniformly, where D) contains all the possible value can take. Denote by G the empirical distribution conditioned on wa, of {x][0) /=112,..., in terms of d and G the true distribution of d' for p &% We want to show
lim sup n deD,
(x) - (x)) +
almost surely.
J Notice that [d] S T-y and (d+ Φ d Φ tt we have (x G
(x: + t). Hence
only need prove for D {de RISI: M1 1}, where M
1-9 1. Denote
by (P,(() = 1 Σ (p E K} where pl, ... Pu. ~ 0 are i.i.d samples.
For an arbitrary
+ we have
P
Σ d.g. S x
N
N
1s
do4 S σ, (ks - 1)E < S ke, 2,....(81)
=|s
N
N
Is
Σ =1
Pn @1 S
d= - 1)s), (K: 1)5 < q: S Ke,, = =2...., 1 (x Σ
Since the last probability is just some prohability of rectangulars, it can be expressed by finite numher of cumulative distribution function, which by the Glivenko-Cantell theorem, uniformly converge to the true distribution. Then, almosdt surely there exists n. > 0 (independent of kz). for n 2 ne. we have each
Pn
91
(r
Σ
dh 1)5), 1)2 < qi S ke, 2,....18|
dj
6=2
[s|
S di
Σ
do do 1)s), (k: - 1)5 < q S ki, = .,....||5|
+
1
1is
Hence we obtain
[S]
P n
Σ
dogs 5x
1
18]
1
P Pa-oz
5
(x
d. 1)8), (k: 1)s a kee, = 2.....111)
+ -
di
ka
kiss 11
==2
1
P Pyrdw
day.
< +
d,e, (ha - 1)s < S Ae = 2, 2.....1s1
ky=1
k 1
2=2
[S]
[s|
quodar
Σ
dogo S x
Σ dge
+
N
[S]
(1S)
1)M
SP Pquddi
Σ dego Sx+
+
Ñ
N
23

---

Since this holds for any d, æ;, we have
S dogs 5x
18
sup dED,aER
Powez
Σ
d.q- I x0
151 dog S (15) 1)M
18
sup dED,aER
P
Parduu
Paroz
Σ
d, S
N
N
The last term converges to zeto as N + co. This is indicated by
18|
daqa S x (15) 1)M
P Pomdse
Σ
Pyrattia
Σ
d.g. Sx
m=1
mm
doga S x (15) - 1)M
=P -Pa
<
Ñ
(18) - 1)M
P Sortta
< < d,
+
da
d,Ñ
([S) 1
Σ
P
q+
d
d,
==1
Since each 0 S < 1 and its marginal distribution d% (gx)
) is continuous, it is uniformly continuous
in < q Hence each Pawayya
du
x
9o S
de
x
(181-1M
N
converge uniformly to 0 as
N - oo. Hence by arbitrary N, we have
|8| d.g. S
S1 Σ
s $0. )00
lim sup sup
P.
Σ
d.ge
dog. S
n- D
+=1
Similarly, we can obtain the other side as
|S| Σ
S1 Σ dog. 5x/ )
lim inf de R
inf
P..
d.g. 5x
+=1
Hence,
sup (x)( (x)) + d.D.a
almost surely.
We obtain the uniform convergence for empirical distribution d, or equivalently, Q, conditioned
the observation process Hence the quantile estimator X X[mo]]=- VaR S5.a (Q) uniformly in Q almost surely. Furthermore, since X; is bounded,
lim
sup & and X; fw, 10, Q) Evesp (k) (3)((ss)))) +
()(())((s 70 ((s,a)lunl =0
almost surely
1011
Estimator for CVaR
Given sample Pi .22
(k)
(k)
(k) Nia
maXIEA Q(s' b)].
The Monto
Carlo estimator for CV (f(pls,a is
[N(
X
j.v(
Again consider the two cases:
==
000
Then we know almost surely of is consistent at PS.a. Then by the proof
for bias VaR estimator, V1 > > 0, I[ [Ndtle] [w] - VaR. (S(pl8 a, Q)) as

---

almost surely k + uniformly in Q almost surely. Then
[ m1
E
[N a
Σ
X
J:N!!
Wiz
j=1
[ ac
=E
Σ
+ E
Kinea lwise
[N
[N a
a
j=1
j=[NEMe]
[ 1
R
[Nddai
[N
E[[ [Ne.as": : lweel
[N (K)
[N
VaR oh ((pls,a,Q1) VaR. 4% (f(pls, Q))
Since B[x p 1-
s.a
(s, a, Q).
CVaR
(f(pls,,,
fl uniformly for 20 and is chosen arbitrarily, we have Wube CVaR (,(pl,,,,
R
Q
R
h
T-
lim liminf o
{E
ビj=1
X Similarly almost surely.
>
[N
0
uniformly in
also prove CVaR th (f(pls, a, Q)) s uniformly
lim sup
[
Σ
[ma]] [nall f=1
[na
in Q almost surely. Combining the two inequalities together, we obtain
lim k
sup
((T(s)(s - - asssa))wn.]] =0
For 0 (00) < oc. By proof of VaR estimator we know the empirical distribution of (K) [(P) |s, a, Q) conditioned on w, converge uniformly to d% Hence the CVaR estimator also has the desired result.
Lemma B.3. (24] Consider stochastic process (ay, Ar.g), O. where a,, A.,g X - R satisfy the equations
(=-(( (1 (1- (e())))))(()) (x(r)g(z), x x, 0,
Let Pe be a sequence of increasing a-fields such that ag and Dg are Po-measurable and 0 D and Fr-1 are P:measurable. Let w|w denote some weighted maximum norm. Assume that the following hold:
1. the set X is finite.
2. 0 S (x(x) < 1, az())) oo, ai()) oow.p.l.
3. | (a(-) Pilllw <x Axlla + where [0, 1) and a converges to zero w.p.1.
4. Var [g(x) P.) & K (1 | where is some constant.
Then, A, converges to zero with probability one (w.p.l).
Proof for Theorem
Proof. Following the same notation in Theorem Define
4.3 Denote by (()) the Q-function in iteration k.
bias (s, a) = (#) Q
(8) (s, a) - T ((x) (s, w.
Then by Theorem 4.3 and observing [[)(+)] < I-y
almost surely, we have almost surely,
lim bias()) a) = S, A. 20
25

---

Denote by A = =Q(() Qui.. A (8) satisfies
A 1k+1 (s) = (1- Ab) + F(j).
where Pog) Q())() Qui
Let H(s) be the o-field generated by
(A (F (=()) We have
(x) (s, H))ll
= [E[B(Pio &, u) Hay
[E[T(( (s, Q0" (s, + (s,"")((sss) Qu + (ias a) Hai]l
-IE |E[ (Q -00h0"0)"1)0)))000""))0)0 (w)) B[Q (s, (s, H(a)) + Elbias a) Haal
[malmma max (1)) (s', b)) max DEA
9 b)] (()) + Elll - Q. H(w) + (s,
S'ES BEA
SxEllI Q0" "I [H())] + Elll
Qt 1| 1 + (1) a) [74y)]
+ (1 + > B Q 0² 1 + (i) (s, ()
ST|A (8) 11o0 (1 + >) Q ooo H(()) + [Bl (s, a) H[))
where || |ls. denote the entry-wise sup norm. The second equality holds since the Monto Carlo sampling procedure iteration only depends on the posterior 6* and sample size N:(k) which completely determined by the past observations w By Proposition 4.2 and Theorem we know both ||@0*, - Q" oc and bias( (s, a) converge
almost surely. Since they are both bounded, by the bounded convergence theorem the last two terms in the last incqualities converge to zero almost surely. Furthermore, since (s a) s R + || (k) lloo we have
Var (s
S [ || (8) )
S RR + 1)(1 + || 110)
By Lemma B.3
we obtain ||A |l) converges almost surely, which completes the proof.
26


Reviews:
[{"review_id": "gO2oSOanqj", "reviewer": "Reviewer_mBvj", "summary": "The authors propose a novel multi-stage Bayesian risk-averse Q-learning algorithm to learn the optimal policy with streaming data. A central difference from existing methods is that they attach a risk functional on the future reward at each stage (nested), rather than just once on the total reward. To arrive at unbiased estimators for the Bellman operators, the authors resort to Monte Carlo. The convergence of the Q-learning algorithm is theoretically shown. The authors include empirical investigation of their method on two toy tasks and show that their method is more flexible than some other worst-case criteria.", "questions": "My questions concern possible extensions of this work, which I do not deem required for acceptance.\n\n* Do you think that a more sample-efficient way (as MC is unbiased but generally not efficient) of arriving at unbiased Bellman operator estimators could be attained, e.g. using variational inference? This seems to be required for problems featuring high-dimensional data streams.\n\n* The authors note that an extension to active sampling settings would be interesting. This would seem to require \"deep exploration\", necessitating a more fundamental Bayesian RL approach [1]. Do you see an easier way to make progress in this direction?\n\n[1] Bayesian Bellman Operators, Mattie Fellows et al, NeurIPS 2021", "limitations": "The authors have adequately addressed the limitations of their work, although I would have liked to see a discussion of how their method might scale to high-dimensional data streams. I do not see any negative societal impact arising from this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The authors propose a technically rigorous addition to the the BRMDP literature. Their empirical results clearly show the utility of per-step risk functionals, and their extensive theoretical results include a number of - technically involved - contributions.\nThe centrepiece here is certainly the proof of Theorem 4.3, i.e. the uniform convergence of the Bellman operator estimator. \nThe paper is well-written and structured, and the resulting method has the potential to generate impact on the safe RL community.", "weaknesses": "While the paper convinces through its soundness and wealth of theoretical contributions, the empirical evaluation could feature more (and more complex) environments. \n\nA fundamental weakness seem to be limitations in applying the authors' method to high-dimensional data streams. \nFor example, one weakness is that the authors do not extend their results to Q-learning with non-linear function approximation. I believe this could be done fairly easily, and would lay foundations for their method to be used on high-dimensional data streams.\nAnother weakness to address when moving to high-dimensional data streams seems the relative sample-inefficiency of  MC Bellman operator estimators (an empirical study of how efficient their proposed estimator is for high-dimensional data streams would be insightful).\n\n\n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's careful review. For the first question, we agree that it is worth deriving some more sample-efficient the Bellman estimator and thank the reviewer for pointing this out.  One way to do this is to use some gradient-based method to update the Bellman estimator as in [1], where they have a distributionally robust Bellman operator (DRBO) and re-wrote it as a stochastic convex optimization. This enables the author to update their DRBO estimator by updating the decision variable given 1 sample of reward and state transition each time. In our BRMDP, if we restrict the risk functional to CVaR, we can re-write the Bellman estimator as \n\n$$\\mathcal{T}^\\phi Q(s,a) = CVaR_\\alpha^{\\phi_{s,a}} (f(Q|p,s,a)) = \\sup_{\\zeta} \\\\{ \n\\zeta - \\frac{1}{\\alpha}\\mathbf{E}_{p\\sim \\phi} [(\\zeta - f(Q|p,s,a) )^+]   \\\\}, (1) $$\n\n\nwhere $f(Q|p,s,a) = \\sum_{s'\\in\\mathcal{S}} p(s')(R(s,a,s') + \\max_{b\\in \\mathcal{A}}Q_{s',b}) $. \n\nNotice if we know the solution $\\zeta^*$ to (1), then we can obtain an unbiased estimator by simply drawing one sample $p$ from $\\phi_{s,a}$. The righthand side of the last equation in (1) belongs to convex optimization and can be solved using stochastic gradient descent (SGD). However, solving (1) to optimality can be sample-inefficient. To improve efficiency, we do not solve (1) to optimality but only conduct one step of SGD to update the current estimate of $\\zeta^*$ and use it to further estimate the Bellman operator. Such an estimator is biased since we do not solve the problem to optimality.  Nonetheless, we can still expect the convergence of the algorithm if both the estimate of both $Q$ and $\\zeta$ converge at appropriate rates (by setting proper learning rates). This is beyond the scope of this paper but is of interest to future research. \n\nAlso, we agree with the author that variational inference can be used for complicated high-dimensional data streams  to improve sample efficiency in both updates of the posterior disttribution and estimation of the Bellman operator, which is also of future interest.\n\nFor the second question, the reviewer is correct that the extension to active sampling settings requires dealing with \"exploration\" and \"exploitation\". Both our paper and [2]  given by the reviewer took the off-policy approach assuming the real data is given under an arbitrary behavior policy. By choosing a proper behavior policy, both [2] and our approach can be easily extended to the active sampling setting. One possible way of doing so is to adding some exploration bonus $Bonus(s,a)$ such as upper confidence bound. To be more specific, with the current estimation of Q-function, in state $s$ we can take action $a^*$ that maximizes $Q(s,a) + Bonus(s,a)$ to collect data samples for the sate-action pair $(s,a^*)$.\n\n[1] Liang, Zhipeng, et al. \"Single-Trajectory Distributionally Robust Reinforcement Learning.\" arXiv preprint arXiv:2301.11721 (2023).\n\n[2] Bayesian Bellman Operators, Mattie Fellows et al, NeurIPS 2021"}, {"review_id": "dHYYAHHA48", "reviewer": "Reviewer_u4kt", "summary": "The paper adopts the Bayesian risk MDP (BRMDP) formulation to train a reinforcement learning agent to be robust against model uncertainty. Infinite-horizon discounted value function of BRMDP is defined by a nested formula, and properties for the value function are derived with VaR and CVaR being the risk functional. Furthermore, Q-learning algorithms for BRMDP are proposed using finite-sample estimators for the Bellman operator, and they are shown to converge to the optimal Q-function under some typical assumptions. Numerical experiments for the proposed risk-averse algorithm is shown and compared with its risk-neutral counterpart and other robust RL algorithms.", "questions": "- Can we define the robustness using some metric like performance variations? How does the risk-averse policy compared with other policies in terms of some robustness metrics?\n\n- It is shown in Theorem 2.2 that BRMDP has a unique optimal value function, but it's not clear wether the random data-conditional optimal Q-function in Definition 4.1 exists. Do we have existence for the data-conditional optimal Q-function following similar arguments?", "limitations": "limitations are adequately addressed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper defines infinite-horizon discounted value for BRMDP, and Theorem 2.3 provides bounds on the difference between the value function of BRMDP to the value function of the true MDP. It shows that the risk-averse version will converge to the true value function as the number of observed transitions grows.\n\n- Q-learning algorithms for BRMDP are proposed using finite-sample estimators for the Bellman operator with either VaR or CVaR as the risk functional. The Q-learning algorithms are shown to converge to the optimal risk-averse Q-function in a data-conditional sense, and this further implies its convergence to the true optimal Q-function given infinite amount of observations.\n\n- Numerical experiments for the proposed risk-averse algorithm is shown and it outperforms two existing robust Q-learning algorithms.", "weaknesses": "- The BRMDP formulation is motivated to provide robust policies, but there is no discussion on what does \"robustness\" mean in the context of this paper. The only place some kind of robustness measure is mentioned is in the numerical experiments where the variations of performance is brought up in the discussion. But there is no proper definition for the variations and there is only very little discussion.\n\n- Theorem 2.3 is claimed to show the trade-off between robustness and conservativeness, but it is hard to talk about robustness without any definition for robustness. In some sense, the upper bound has the risk level parameter $\\alpha$ which may be viewed as a kind of robustness level, but no analysis is provided on how the risk level $\\alpha$ would affect the behavior of the risk-averse policy and how $\\alpha$ would improve the robustness of the performance in some sense.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's comment. For the first question, we believe the reviewer's concern is whether the robustness of BRMDP can be shown in a more quantifiable and interpretable way. For example, in the literature of distributionally robust RL such as [1,2], they define the optimal robust policy as the policy that has best worst-case performance among a set of potential RL environments which belong to some ambiguity set constructed using some distributional metric. In the formulation of BRMDP, we also consider a set of potential environments, but with the ambiguity set to be the whole simplex space, that is, all the possible transition probabilities. In addition, each possible transition probability is assigned a posterior density and we do not consider the worst-case performance measure but some risk measure. The relation between distributionally robust MDP and risk measure has been studied in [1,2]. In [1], the author proved that when the ambiguity set satisfies some conditions,  minimizing the cost of distributionally robust MDP coincides with  some risk minimization optimization for some risk measure. It is later shown in [2] the equivalence between distributionally robust MDP and risk-sensitive MDP. However, the mapping between distributionally robust MDP and risk-sensitive MDP cannot be explicitly characterized, and the proposed BRMDP involves a nested formulation and risk functional over posterior distribution, all of which make it difficult to define the metric-like performance variations. Nonetheless, we believe it is helpful to characterize how the value function of BRMDP $V^{\\phi,\\pi}$ differentiates from the value function of the original true MDP $V^{c,\\pi}$. While Theorem 2.6 serves this purpose, it is not intuitive enough. Our recent ongoing work shows, for a given deterministic policy $\\pi$, number of transition observation $O_{s,a}$ for state-action pair $(s,a)$, total number of observation $O$, if $\\\\lim_{O \\\\rightarrow \\\\infty} \\\\frac{O_{s,\\\\pi(s)}}{O} = \\\\bar{o}_s,$ \n\nThen\n $V^{\\phi,\\pi}$ can be expressed as\n$$   V^{\\phi,\\pi} = V^{c,\\pi} - \\frac{1}{\\sqrt{O}} C + o_p( \\frac{1}{\\sqrt{O}}), (2) $$\nwhere $C = (I - \\gamma \\mathcal{P}^c_\\pi)^{-1}\\gamma \\bar{o} \\mu^\\pi$ is a constant, $ \\mu^\\pi(s) = \\frac{-\\sigma^\\pi_s}{\\alpha} \\psi(\\Psi^{-1}(\\alpha)),\n (\\sigma^\\pi_s)^2 = (V^{c,\\pi})^\\top diag(i_{s'}^\\pi)(V^{c,\\pi}),$\n$ i_{s'}^\\pi = (\\mathcal{P}^c_{s,\\pi(s)}(s'))^{-1},$,\n$\\psi, \\Psi$ represents the pdf and cdf of standard normal distribution, and $o_p$ represents converge in probability. (2) indicates maximizing the value function of BRMDP\nis equivalent to maximizing the original value function minus some positive \"bias\" term depending on the risk level $\\alpha$ and a problem-dependent variance term $\\sigma_s^2$. Notice $ \\frac{\\psi(\\Psi^{-1}(\\alpha))}{\\alpha} $ is decreasing in $\\alpha$ and no larger than 1. A more risk-averse attitude $\\alpha$ results in a larger bias term. Furthermore, this bias term diminishes in an order of $\\frac{1}{\\sqrt{O}}$, as when more data are collected, we are less pessimistic.\n\nFor the second question, we thank the reviewer for pointing this issue out. The answer is yes. The data-conditional optimal Q-function is defined by each sample trajectory $\\omega$ (which contains all the randomness). For each state-action pair $(s,a)$, the posterior $\\phi^t_{s,a}$ will either remain unchanged after some period $\\tau$ or concentrate on the true transition probability $P^c_{s,a}$ with probability 1. If $\\phi^t_{s,a} = \\phi^\\tau_{s,a}$ for all $t>\\tau$, then $\\mathcal{T}^{\\phi^\\omega} Q(s,a) = \\mathcal{T}^{\\phi_\\tau} Q(s,a)$; Otherwise we can define \n$$\\\\mathcal\\{T\\}^\\{\\\\phi^\\\\omega\\} Q(s,a) := \\mathcal{T}^{c} Q(s,a)  = \\mathbf{E}_\\{P^c\\_{s,a}\\} [R(s,a,s') + \\gamma \\max\\_b Q(s,b)].$$\n\nThen, $Q^{\\omega,*}$ is the unique solution to $\\mathcal{T}^{\\phi^\\omega} $, whose existence can be guaranteed with the same proof of Theorem 2.2. We will clarify this in the paper.\n\n[1] Bäuerle, Nicole, and Alexander Glauner. \"Distributionally robust Markov decision processes and their connection to risk measures.\" Mathematics of Operations Research 47.3 (2022): 1757-1780.\n\n[2] Zhang, Runyu, Yang Hu, and Na Li. \"Regularized Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity.\" arXiv preprint arXiv:2306.11626 (2023)."}, {"review_id": "MddUFYbUA0", "reviewer": "Reviewer_vogF", "summary": "This paper extends previous work on Bayesian Risk-averse MDPs (BRMDPs), an informed alternative to an ambiguity set in the infinite horizon setting. In doing so, the authors first present a nested BRMDP formulation for the state value function. Then, they show that difference between optimal value functions for BRMDP and the true MDP is bounded. Afterwards, the authors presented a multi-stage risk-averse Q-learning algorithm with periodic posterior updates and a Monte Carlo estimator for the proposed risk-averse bellman operators. Simple simulations are presented to verify the better performance as well as the lesser variance of the proposed infinite horizon BRMDP formulation. It should be noted that the Bayesian posterior and Risk functionals are well-defined and that the state and action spaces discussed in the paper are both finite. The work does hold merit, and the findings could be communicated to a larger audience through a conference like NeuRIPS.", "questions": "1. In line 180, page 5, section 2.5, it is stated that a batch n(t) of observations is available. What is the assumption for the smallest batch size?\n\n2. What is the reasoning behind using the Monte Carlo estimator?\n\n3. Why is the benchmark Q-Learning on the true environment not provided in the experimental results?\n\n4. In line 201, page 6, section 3.1, what does i.i.d sampling of probability distributions p_i mean?\n\n5. What is the computational overhead of the proposed methodology, and how well will it scale?\n", "limitations": "The authors addressed one limitation of their work, i.e., that the behavior policy which generates the real-world data is assumed to be given. In terms of societal impact, there would be no potential negative impact of this work according to the considered ethical criterion. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is generally well-written:\n\n1. The infinite horizon BRMDP formulation is novel and the accompanying recursive Bellman equations follow nicely.\n\n2. Detailed proofs of the distance bound for the State function and the convergence analysis are provided.\n\n3. Experimental results are discerned in a manner that relates directly to claims of risk aversion (smaller variances) and performance gains.\n", "weaknesses": "1. Apart from the assumption of the availability of a behavioral policy to generate real-world data, the rules for updating the sample sizes appear to be a heuristic at best. (ref. Algorithm 1)\n\n2. The Monte Carlo estimators for the Bellman operators, in addition to generating real-world samples to update the Bayesian posterior, will make the algorithm extremely slow. \n\n3. The state and action spaces under consideration appear to be finite, thus limiting the evaluation to more demanding experimental setups. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " We appreciate the reviewer's comment. For the first question, the proposed algorithm works for any batch size. For example, we can update the posterior once new data are available, in which case $n(t) \\ge 1$. However, it is of future interest to control the number of Q-learning steps and real-data batch size to improve sample efficiency. \n\nFor the second question, the Monte Carlo estimator is designed for estimating the Bellman operator, which depends on the posterior of transition model but not the real transition model. The real-world sample is only used for updating the posterior belief about the transition model to reduce the epistemic uncertainty. Once we update the posterior at the beginning of each stage, we turn to solving the BRMDP, the risk-averse problem instead of focusing on the original MDP. Our framework can be regarded as Episodic off-line RL, where within each episode (stage) we do not have sources of real data but only a fixed set of data that are used to construct the posterior.\n\nFor the third question, the Q-Learning algorithm only uses real-world data. In our experiment setting, the number of real-world data $n(t) = 5$ is much smaller than the computing budget of Q-learning update $|\\mathcal{S}|m(t) = 50$. As a result, the model-free Q-learning converges quite slowly as we only have very little real-world data. In fact, the reason for our proposed risk-averse formulation is to deal with the epistemic uncertainty caused by the (partially) lack of data, which can attribute to either highly cost real data or safety concerns. \n\nFor the fourth question, recall $\\phi_{s,a}$ denote the Dirichlet posterior distribution on the unknown transition probability $\\mathcal{P}^c_{s,a} \\in \\mathbf{R}^{|\\mathcal{S}|}$. Each $p_i$ is a $|\\mathcal{S}|$-dimensional vector that represents a transition probability. \n\nFor the fifth question, the computational overhead is mainly on generating samples from the posterior distribution to estimate the Bellman operator for each state-action pair. We restrict the choice of risk functional to CVaR, which is always risk-averse, to roughly compute the computational complexity. For each state-action pair, generating a $|\\mathcal{S}|$-dimensional random vector takes $O(|\\mathcal{S}|)$ time.  The number of samples needed to estimate the Bellman operator depends on the posterior update according to the proposed algorithm. If a certain state-action space is never observed, then estimating the Bellman operator can be very costly when the stage is large. Although in the algorithm we allow such sample size to go to infinity to prove the almost sure convergence, which requires the bias term to converge to 0. In practice we can often use a fixed sample size $\\bar{N}$, which can be computed using some concentration bound for CVaR [1] to control the bias with some confidence level. Then, in each stage (inner loop in algorithm), we need to generate $m(t)\\bar{N}|\\mathcal{S}||\\mathcal{A}|$ samples, which then takes $O(m(t)\\bar{N}|\\mathcal{S}|^2|\\mathcal{A}|)$ time. Assume $m(t) = m$ for simplicity. Since the Q-function given by the algorithm is always bounded by $\\frac{\\bar{R}}{1-\\gamma}$, which does not depend on $|\\mathcal{S}|$, the sample size $\\bar{N}$ does not depend on $|\\mathcal{S}|$ by [1]. We have the computational overhead scale as $O(|\\mathcal{S}|^2)$ in terms of the size of state space. When the state space is large, function approximation of the Q-function is of interest to improve the computation efficiency.\n\n     \n[1] Thomas, P., Learned-Miller, E . Concentration Inequalities for Conditional Value at Risk. ICML(2019)."}, {"review_id": "I4DRayo7TD", "reviewer": "Reviewer_kQUg", "summary": "The paper develops a Bayesian risk-averse Q-learning algorithm to tackle the setting of Bayesian risk MDP, which uses Bayesian posterior to estimate the transition model and impose a risk functional to account for the model uncertainty. The claim is that the proposed algorithm learns a \"risk-averse yet optimal policy\", which has theoretical guarantee of strong convergence.", "questions": "Main question:\n- Theorems are mostly provided as fully original. What are the closest related theorems from the literature?\n- The inventory management problem is considered in two settings as can be read in the supplementary material. The second one is described as \"(...) the demand depends on the current inventory level s. (...) we will consider the case where observations are insufficient to estimate the transition probability for every state-action pair\". What is actually meant by that? And also, why are there two settings described in the supplementary material but only one in the main paper?\n\nAdditional questions:\n- The abstract mentions the following: \"The proposed algorithm learns a risk-averse yet optimal policy that depends on the availability of real-world observations.\" This seems unclear from the abstract because a risk averse policy will in general need make a tradeoff with the best expected return. Do you mean \"risk averse policy that converges to the optimal one in the context of unlimited data\"?\n- line 117, $\\xi$ is defined as a probability distribution over $\\mathbb R^n$, but is described as a \"random vector taking values on $\\mathbb R^n$\". Can you clarify?\n- Line 123: Could there be some intuitions for the different parts of assumption 2.1? In particular Line 124-128 gives lightweight information about how it is slightly similar to the notion of coherent risk measure but that notion and the difference with it are not detailed. Why is sub additivity not included, why is 2.1.3 important?", "limitations": "Some limitations are provided.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes an interesting formalization of an algorithm for Bayesian risks in MDP. The paper is scientifically sound and provides a few interesting results, among others with respect to the convergence (to the \"optimal\") in the context of infinite data. The paper explains why Monte-Carlo estimators are useful in practice and provides a few interesting theoretical properties. Numerical experiments provide illustrations of the theoretical analysis in the context of two relevant (small-scale) MDPs.", "weaknesses": "Even though related work is overall well-discussed, the paper could be more clear about the novelty of the different parts (e.g. Theorem 2.2 and Theorem 2.3 seem relatively generic and even though I'm not an expert in the BRMDP setting, I believe close theorems exist in the literature). \n\nThe notations and overall formalization might benefit from a few (minor) improvements to improve the readability (see additional comments and questions).\n\nAdditional comments:\n- In Equation 1, $d_i$ and $p_i$ do not seem to be formally defined (even though we can guess what they refer to).\n- In Equation 1, \\rho is used with a subscript that depends on a sampling from a Dirichlet posterior but \\rho was introduced line 114 without any subscript (the meaning of the subscript might not be fully obvious).\n- line 97: $r$ is not defined (even though we can guess what they refer to)\n- line 108: (s,a) is not in math mode (italic).\n- line 109: \"??\" instead of a reference to the appendix.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "  We appreciate the reviewer's comment. For the first main question,   our presented theorems can be classified into two groups. Theorem 2.2 and 2.3 characterize the property of BRMDP. The BRMDP in this paper is different from previous risk-sensitive MDP in that  risk functional is taken with respect to the posterior distribution to account for epistemic uncertainty, while most previous works of risk-sensitive MDPs impose the risk functional on the known transition probability to account for the aleatoric uncertainty. BRMDP is first proposed in [1], where they consider the finite horizon MDP whose optimal policy can be solved using dynamic programming, while we consider the infinite-horizon and discounted MDP. No existing theorems can be applied here due to the different formulations. But like many works on (robust) infinite-horizon and discounted MDP, we proved Theorem 2.2 in a standard way of showing the Bellman operator is a contraction mapping.  For Theorem 2.3, we do not see previous works have studied such \"convergence\" property, As we mentioned above, the previous works on risk-sensitive MDP mainly deal with aleatoric uncertainty, whose value function does not converge to that of the original MDP. The proof of Theorem 2.3 relies on the contracting property of the Bellman operator as provided in Theorem 2.2 and some statistical properties of risk measure VaR and CVaR, which are well studied in many previous works.  We agree with the reviewer that the proof of these 2 theorems can be regarded as an extension of previous work on robust MDP to BRMDP, with some effort dealing with risk functionals.  \n    \nThe remaining theorems guarantee the convergence of the proposed algorithm, which follows the framework of stochastic approximation as many other works on Q-Learning. However, unlike previous work on either robust or non-robust Q-Learning, where they can obtain an unbiased estimator of the Bellman operator, we cannot do so as discussed in Section 3. Instead, we need to show a uniform convergence of our Monte Carlo estimator of the Bellman operator in Theorem 4.3, which is the most challenging and novel theoretical result of the paper. The proof of Theorem 4.3 is completely new and non-trivial.   \n\nFor the second main question, the sentence \"the demand depends on the current inventory level\" is misplaced and should be deleted. In both settings, the demand does not depend on the inventory level. We greatly thank the reviewer to point this out and we will correct this in the paper. \n    In addition,  the two settings refer to the result in Figure 4 and Figure 5, respectively. In Figure 4, the posterior is updated at the beginning of each stage with some newly arrived data. In Figure 5, the posterior is only estimated once at the beginning of first stage. It can be considered as pure offline Q-learning, which is the same setting as the two distributionally robust (DR) Q-Learning in the comparison baseline. Our purpose of showing result in Figure 2-4 is to illustrate the advantage of utilizing streaming real-world data, as we can reduce the epistemic uncertainty.  In Figure 5, when there is no source of streaming data, we want to illustrate that our Bayesian risk-averse (BR) policy possesses robustness like the other two DR policies. A DR policy has the best worst-case performance over a set of potential transition models. Here we list the performance (value function) of different policies under different transition models. The two DR policies are the most robust as in the worst case shown in Figure 5 (Poisson parameter equal to 2) they obtain the largest value function. Our BR policies with VaR and CVaR fall between the  risk-neutral policy and DR policies, showing the risk measure is a more flexible choice of risk attitude between the worst-case and  risk-neutral case.\n\nFor the first additional question, the reviewer is correct. The risk-averse policy converges to the optimal policy as more data are available as the epistemic uncertainty is reduced to 0. We thank the reviewer to point this out and we will clarify this in the paper.\n\nFor the second additional question, we thank the reviewer to point out this notation issue. We will correct this by deleting the distribution notation.\n\nFor the third additional question, the only reason we replace the sub-additivity with assumption 2.1.3 is to make the assumption more general to include risk measure VaR, which is a widely used risk measure but not satisfies sub-additivity. In addition, we cannot simply delete the sub-additivity assumption without adding Assumption 2.1.3, because Assumption 2.1.3 is necessary to guarantee that the Bellman operator is a contraction mapping in the proof of Theorem 2.2.1.\n\n[1] Lin, Yifan, Yuxuan Ren, and Enlu Zhou. \"Bayesian Risk Markov Decision Processes.\" Advances in Neural Information Processing Systems 35 (2022): 17430-17442."}]

Author rebuttal:

Meta-review: The meta-reviewer has reviewed the paper, the reviews, the responses, and agrees with the majority of the reviewers that this paper meets the NeurIPS standard.
It would be better if the authors could improve the experimental results.
Decision: Accept (poster)