Percentile Criterion Optimization in Offline Reinforcement Learning
Authors: Cyrus Cousins
Elita Lobo
Marek Petrik
Yair Zick
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Bayesian Uncertainty
Robustness

Abstract: In reinforcement learning, robust policies for high-stakes decision-making problems with limited data are usually computed by optimizing the percentile criterion. The percentile criterion is optimized by constructing an uncertainty set that contains the true model with high probability and optimizing the policy for the worst model in the set. Since the percentile criterion is non-convex, constructing these sets itself is challenging. Existing works use Bayesian credible regions as uncertainty sets, but they are often unnecessarily large and result in learning overly conservative policies. To overcome these shortcomings, we propose a novel Value-at-Risk based dynamic programming algorithm to optimize the percentile criterion without explicitly constructing any uncertainty sets. Our theoretical and empirical results show that our algorithm implicitly constructs much smaller uncertainty sets and learns less-conservative robust policies.

Percentile Criterion Optimization in Offline Reinforcement Learning
Elita A. Lobo
Cyrus Cousins
Department of Computer Science University of Massachusetts Amherst elobo@umass edu
Department of Computer Science
University of Massachusetts Amherst cbcousins@umass edu
Yair Zick
Marek Petrik
Department of Computer Science University of Massachusetts Amherst yzickOumass edu
Department of Computer Science University of New Hampshire mpetrikēcs unh. edu
Abstract
In reinforcement learning, robust policies for high-stakes decision- makinn prob- lems with limited data are usually computed by optimizing the percentile criterion. The percentile criterion is approximately solved by constructing an ambiguity set that contains the true model with high probability and optimizing the policy for the worst model in the set. Since the percentile criterion is non-convex, constructing ambiguity sets often challenging. Existing work uses Bayesian credible regions as ambiguity sets, but they are often unnecessarily large and result in learning overly conservative policies. To overcome these shortcomings, we propose a novel Value- at-Risk based dynamic programming algorithm to optimize the percentile criterion without explicitly constructing any ambiguity sets. Our theoretical and empirical results show that algorithm implicitly constructs much smaller ambiguity sets and learns less conservative robust policies.
Introduction
Batch Reinforcement Learning (Batch RL) [26] is popularly used for solving sequential decision- making problems using limited data. These algorithms are crucial in high-stakes domains where exploration either infeasible or expensive, and policies must be learned from limited data. In model-based Batch RL algorithms, transition probabilities are learned from the data well. Due insufficient data, these transition probabilities are often imprecise. Errors in transition probabilities accumulate, resulting in low-performing policies that fail when deployed.
To account for the uncertainty transition probabilities, prior work uses Bayesian models [10 to model uncertainty and optimize the policy to maximize the returns corresponding to the worst deperccnttlee transition probability model. These policies guarantee that the true expected returns will be least large the optimal returns with high confidence. This technique is commonly referred to as the percentile-criten is NP-hard to optimize. Thus. current work Robust Markov Decision Processes (RMDPs) to optimize a lower bound on the percentile criterion. An RMDP takes as input an ambiguity set (uncertainty set) that contains the transition probability model with high confidence and finds policy that maximizes the returns the worst model in the ambiguity set.
27
40
45
47
optimization. Unfortunately, the percentile criterion
Since the percentile criterion is non-convex, constructing ambiguity sets itself is challenging problem. Existing work uses Bayesian credible regions (BCR) [40] as ambiguity sets. However, these ambiguity sets are often unnecessarily large [5 40 and result in learning conservative robust policies.
37th Conference on Ncural Information Processing Systems (NcurIPS 2023).

---

Some recent works approximate ambiguity sets using various heuristics BL A0), but we show that they remain too conservative. Thus, the question of the optimal ambiguity set, i.e., ambiguity sets that result in optimizing the tightest possible lower bound on the percentile criterion and less-conservative policies remains unanswered.
Our Contributions In this paper, we answer two important questions: a) Are Bayesian credible regions the optimal ambiguity sets for optimizing the percentile criterion? b) Can we obtain less conservative solution to the percentile criterion than RMDPs with BCR ambiguity sets while retaining its percentile guarantees? Our theoretical findings show that Bayesian credible regions can grow significantly with the number of states and therefore, tend to be unnecessarily large, resulting in highly conservative policies. As our main contribution, we provide dynamic programming framework (Section B). which we name the VaR framework, for optimizing a lower bound on the percentile criterion without explicitly constructing ambiguity sets. Specifically, we propose new robust Bellman operator, the Value at Risk (VaR) Bellman operator, for optimizing the percentile criterion. We show that it is valid contraction mapping that optimizes a tighter lower bound on the percentile criterion, compared to RMDPs with BCR ambiguity sets (Section 3 We theoretically analyze and bound the performance loss of our framework (Section B.1). We provide Generalized VaR Value iteration algorithm and analyze its error bounds. We also show that there exist directions in which the Bayesian credible regions can grow unnecessarily large with the number of states in the MDP and possibly result in a conservative solution. On the other hand, the ambiguity sets implicitly optimized by the VaR Bellman operator tend be smaller, i.e., they have smaller asymptotic radius and are independent of the number of states (Section 4). Finally, we empirically demonstrate the efficacy of our framework in three domains (Section
1.1 Related Work
propose different methods for solving the percentile criterion, as well as other robust measures for handling uncertainty in the transition probabilities estimates. Russel and Petrik 44 and Behzadian et al. 3 propose various heuristies for minimizing the size of the ambiguity sets constructed for the percentile-criterion. Russel and Petrik [40] propose a method that interleaves robust value iteration with ambiguity set size optimization. Behzadian et al. (3] propose an iterative algorithm that optimizes the weights of & and foo ambiguity sets while optimizing the robust policy. However, these methods still construct Bayesian credible sets which can be unnecessarily large and result in conservative policies, as we show in Section 5
Several work B3
34
40
Other works consider partial correlations between uncertain transition probabilities to mitigate the conservativeness of learned policies [4] [5 ness of S- and SA-rectangular ambiguity sets by capturing correlations between the uncertainty and by limiting the number of times the uncertain parameters deviate from the mean parameters. Despite
19
29 30 These approaches mitigate the conservative-
these heuristics, most of these works 2 20 40 53 either rely on weak statistical concentration bounds to construct frequentist ambiguity sets, or use Bayesian credible regions as ambiguity sets. resulting in conservative policies.
These sets still tend to be unnecessarily large [5 40)
50 52 have proposed RL algorithms that use measures like Conditional Value at Risk, Entropic risk measure amongst other risk measures. However, we note that these works use risk measures to obtain robustness guarantees against aleatoric uncertainty (system uncertainty) and not epistemic uncertainty (model uncertainty), which is the focus of our work. Since these works optimize completely different objective, we do not compare our
Finally, a large number of works 12
16 36
framework against theirs. Robust RI. work 2 14 20
proposes other robust measures for handling uncertainty in transition probabilities; however, these approaches do not provide probabilistic guarantees on the expected returns, and compute overly conservative policies.
28
32 55
2 Preliminaries
In the standard reinforcement learning setting, a sequential decision task is modeled as Markov
Decision Process (MDP) [37 48 An MDP is a tuple (8, A, P, R, Po, 7) that consists of (a) a set
of states S = (1,2...... 5). (b) set of actions A = (1, ... A}. (c) deterministic reward
function R: Ax - IR, (d) a transition probability function P: S x A - AS, (e) an initial
state distribution Po A where A represents the S-dimensional probability simplex, and (f)
2

---

discount factor Y E [0, 1]. We use Ps,a to denote the vector of transition probabilities P(s, a, corresponding the state and action a. Likewise, we use s. to denote the vector of rewards R[s, a) corresponding to state s and action a. Markovian policy æ: S + A maps each state to a distribution over actions A. In a general RL setting, the goal is to compute a policy that maximizes the expected discounted return p( P) over an infinite horizon,
max p( P) max E Fell
Σ t=
(r(s,, 0c. so po. a2 (T:)), S141 P(st, as.))
The value of a policy π at any state s the discounted sum of rewards received by an RL agent, if starts from state 8, i.e., vz (s) E 7 dt, $141)|50 5, az 8141 P(s,, az, :)].
We assume a batch reinforcement learning setting [26] where the reward function known, but the true transition probabilities P are unknown. Following prior work on robust Bayesian RL 88 [3 40 [5]] we use parametric Bayesian models to represent uncertainty over the true transition probabilities pa, We will use P (Pa.a aES, denote the random transition probabilities. We assume have batch of data D = {si, 0j, " which in conjunction with some prior distribution defines the posterior distribution of transition probabilities P.
The Fisher information measures the amount of information about the unknown true parameters
0" E IRd carried by an observable random variable X E II"". If [(x;; 0*) is the probability density of X conditioned on 0", then the Fisher information is given by r(0")=B) (V log f(x:0" (XV)))))VVV f(X:0
Then, in the Bayesian setting, the Bernstein von Mises theorem 51 states that under mild regularity conditions the posterior distribution of the parameters O converges in the limit to the distribution of the MLE of 0* which is asymptotically Gaussian, in particular, lim (N )r) - (O -(0))-1) where ~o indicates convergence in distribution. In many cases, the above holds even though the conditions of the Bernstein-von Mises theorem not met [17 [8]. Of particular interest in this setting the Dirichlet distribution where the asymptotic MLE is multivariate Gaussian under certain conditions the prior distribution [18] although in this case, it is degenerate (i.e., the covariance matrix is not full-rank).
For asymptotic results, we assume that the data D is sampled such that each state and action is observed infinitely many times as N - D0. Furthermore, we assume henceforth that the prior is asymptotically negligible, and the MLE is asymptotically Gaussian with covariance matrix T(P") //N. Therefore, the posterior distribution of P is also asymptotically Gaussian with covariance matrix I(P") /N. Under these conditions, we will estimate the Fisher information corresponding to f- = P' using the asymptotic covariance of the posterior distribution of P.
To avoid unnecessary computational technicalities, will assume that P is discrete random variable taking on values P(w)), w E Ω for some Ω (1,..., M) with distribution f. That is, the random variable P represents a discrete approximation of the true, possibly continuous posterior, as is common in methods like Sample Average Approximation (SAA) 43)
Percentile Criterion model uncertainty 13 It aims to compute a policy that maximizes the returns corresponding to the worst a-percentile model:
The a-percentile criterion is popularly used to derive robust policies under
arg max HEll
{UE Pr Paj
p(T, P) P) 2 21
(I)
The value y lower-bounds the true expected discounted returns with confidence a where a E (0, 4/2). Optimizing the percentile criterion is equivalent to optimizing the Value at Risk (VaR.,) of expected discounted returns when there exists uncertainty in transition probabilities P and the expected returns function p is lower-semicontinuoss The optimization in is equivalent to
max VaR, [p(nT, P)]
wElt
where VaR, of a bounded random variable X with a CDF function F IR - [0, 1] is defined as 38
VaR [X] sup(t R Pr 2 2
3

---

A lower value of a in ① indicates a higher confidence in the returns achieved in expectation. For example, Valo,
x indicates that the true returns will be at least equal to the robust returns for 95% of the transition probability models. When clear from context, we use VaR to denote the Value at Risk at confidence level a. Unfortunately, the optimization problem in is NP-hard to optimize and is usually approximately solved using Robust MDPs.
Robust MDPs Robust MDPs (RMDPs) generalize MDPs to account for uncertainty, or ambiguity. in the transition probabilities. An ambiguity set for an RMDP is constructed such that contains the true model with high confidence. The optimal policy of Robust MDP x² maximizes the returns of the worst model the ambiguity set: x² arg max, minpep p(m, P). General RMDPs are NP-hard to solve [53], but they are tractable for broad classes of ambiguity sets. The simplest such type is the SA SArrecaaggular ambiguity set [33 [3), defined as
P P=(PE E SSSA
Ps.a E Pxs,a As ES Va E
for a given P..a S AS E S,a E A. SA-rectangular ambiguity sets B 40 assume that the transition probabilities corresponding to each state-action pair are independent. Sim- ilarly to MDPs, the optimal robust value function v" E RR for an SA-rectangular RMDP is the unique fixed point of the robust Bellman optimality operator T: RS RR defined as (Tv), = m minp... EP.. Pb.a (Ta,a 7.
To optimize the percentile criterion, SA- SArrengang ambiguity set P is constructed such that it contains the true model with high probability, and thus, the following equation holds.
Pr p(T,
min p(T,, P) 2 a PEP
Although RMDPs have been used to solve the percentile criterion [3, the quality of the robust policies computes depends mainly on the size of the ambiguity sets. The larger the ambiguity sets, the more conservative the robust policy (30]. SA-rectangular ambiguity sets are most commonly studied; thus we focus our attention on SA-rectangular Robust MDPs. We investigate whether Bayesian credible regions optimal ambiguity sets for optimizing the percentile criterion. We refer to BAreccaan RMDPs and SA-rectangular ambiguity sets as Robust MDPs and ambiguity sets respectively.
Our work focuses on Bayesian (rather than frequentist) ambiguity sets, Bayesian ambiguity sets are usually constructed from Bayesian credible regions (BCR) let Va.a represent the size of the BCR ambiguity sets; PBCR.. and Ps.a represent the mean transition probabilities. The set PBCR is constructed as
B 40]. Given state and an action o,
s,a
PBCR. = = (b) = {pr.. E A | s,a
Ps.a - Ps.a S Vs,a}
(4)
where q E (1, represents the norm of the weighted ball in (4) and b E TR. is weight vector. Here, b is jointly optimized with vi E IR to minimize the span of the ambiguity sets such that the true model is contained in the ambiguity set with high confidence, i.e., Pr (p..a E (b..ab, 1h, 4)) 2
We refer to BCR ambiguity sets with non non-uniform weights as weighted BCR ambiguity sets. We refer to the Robust Bellman optimality operator with BCR ambiguity sets (TBCR_) the BCR, Bellman optimality operator, and to RMDPs with BCR ambiguity sets as BCR RMDPs. For any å E (0, 1/2). setting the confidence level in TECR, to 8/s.A for all state-action pairs yields 8 confidence on the returns of the optimal robust policy [3. However, we show that even span-optimized BCR RMDPs can be sub-optimal for optimizing the percentile criterion.
We use the shorthand Ws.o for any 8 E S, a E A denote the vector of values associated with value E S and the one-step return from state s and action a, i.e., Ws,a Ts,a + tyu. We use Ps,a E R and Σ.,a E Sx5 for any s E S, E to represent the empirical mean and covariance transition probabilities Ps.a estimated from D. We use rilde to indicate that it is random variable. We use Φ(-) and (-)) represent the probability distribution function (PDF) and cumulative distribution function (CDF) respectively of the normal distribution with mean 0 and variance 1. The -Miikooski norm |æø|| for a vector given some positive-definite matrix Z is defined as ||>||| z Z -
We illustrate the conservativeness of BCR, ambiguity sets with the following example. Example 2.1. Consider an MDP with four states (8o, 81, 82, 83} and a single action {ao). The state so is the initial state and the states 51, 82, 53 terminal states with zero rewards. For the

---

sake of simplicity, we assume that it is only possible to transition to state and S3 from state 8o. The transition probability of aao.an uncertain and distributed as Dirichlet distribution Po ~ 11, 10, with mean [0.48, 0.48, 0.04). The rewards for transitions from state so are given by a0 [0.25, 0.25,
We wish to optimize the percentile criterion with confidence level ò = 0.2. Following the sampling procedure proposed by Russel and Petrik (40] to construct uniformly weighted BCR, ambiguity set for Pso.a with 100 posterior samples, yields an ambiguity set $0,40
{o ApEAS A Pp Pau.ag 1 0.277) In this case, the reward estimate against the worst model in the ambiguity set p [0.50, 0.32, 0.18) is pBCR, 0.025. Since we have single non-terminating state in the MDP, the percentile returns given by p VaR, Va P Teo.aul. Computing p VaR for Dirichlet distribution Dir(10, 10, 1), we get p VaRn 0.17 > p pBRR, Thus, this example shows that BCR ambiguity sets can be unnecessarily large, and thereby result in conservative policies.
3 VaR Framework
We introduce the VaR Bellman optimality operator TvaR,, for approximately solving the percentile criterion. We show that TVAR., is a valid Bellman operator: it is a contraction mapping and lower bounds the percentile criterion. For any value function v E RS. state E S and action A, define the VaR. Bellman optimality operator TvaR.,
(TvaR, v) max VaRa aeA
[P- (r + tw)
(5)
For each state s, TvaR, maximizes the value corresponding to the worst a-percentile model. In contrast to the BCR, Bellman optimality operator TBCR., computing TvaR., does not require con- structing ambiguity sets from confidence regions; can simply be estimated from samples of the model posterior distribution, as we later show.
Proposition 3.1 (Validity). The following properties of TvaR, hold for all value functions u, v E R.S
The operator TVaR., is contraction mapping on R.S. [[TVaR, u-TTaa, o1100 S u1loo
2. The operator TvaR., is monotone: ' v TvaR Z TvaR.
3. The equality TvaR." à = has a unique solution.
Proposition 3.1 formally proves that TVAR, is a valid Bellman operator, i.c., it is a contraction mapping. monotone, and has unique fixed point ê (TvaR, 6). Here on, will refer to the policy (ft) corresponding to the fixed point value ú as the VaRa, policy.
5-000
2300
$2
200
BCK
SCR
83
53
(a) Asymptotic Radii
(b) Dirichlet(5,5.5)
(c) (3r,,clee(30,33,,00
Figure 1: Figure la (left) compares the asymptotic radius of Σ M-iikowskii norm BCR ambiguity sets to VaR., ambiguity sets, where Σ is the covariance matrix. The size of the BCR ambiguity sets significantly grows with the number of states. Figure and and Figure[[c[(righ) compare the asymptotic forms of BCR, and VaR, ambiguity sets under high and low uncertainty in I at confidence level = 0.2 respectively. The grey dots represent the transition probabilities samples from a Dirichlet distribution. The sizes of BCR, and VaR,, ambiguity sets increase with an increase in the uncertainty in P. however, the VaR, ambiguity sets are smaller than the BCR, ambiguity sets.
5

---

We now show that the VaR Bellman optimality operator TvaR, optimizes lower bound on the percentile criterion. Given a policy n, state E S, and transition probabilities P, let
DT Σ r(s, (rs.a tv)
acA
represent the Bellman evaluation operator for transition probabilities P. Furthermore, let
(TaR,, v)s = Σ T(s, a) VaRa (r,a((ss + rv)]
aEA
represent the VaR Bellman evaluation operator for random transition probabilities P. We use 6" to denote the fixed point of VaR.. Furthermore, we use H" to represent the random fixed point of
TE which is computed using random realization of the transition probabilities P sampled from the posterior distribution conditioned on observed transitions D.
Proposition 3.2 (Lower Bound Percentile Criterion), For any 8 (0, 1/2), ifwe set the confidence level a in the operator VaR., to 6/5, then for every policy E IT: Pry [0" = 0" 2 6.
Proposition 3.2 shows that for any policy π and state 8, the VaR. value at state s, 6 lower bounds the value (s) with high confidence. Comparing Proposition 3.2 with the definition of the percentile-criterion in (T). we see that the percentie-criterion requires confidence guarantees only the returns computed from the initial states, whereas the equation in Proposition 3.2 provides confidence guarantees on the value of every state. Therefore, for any policy æ, the value pO 6th is
lower bound on the percentile-criterion objective VaRs [P(T, P)]. Since Tvant finds policy that maximizes the value pa 6t, it follows (37 that TvaR, optimizes a lower bound on the percentile criterion in (T.
Proposition 3.3. Suppose that Paoo for any state and action is multivariate sub- Gaussian with mean Pa.a and covariance factor Ea,a, i.e., E exp (A(Pa,a )aaa) ( s exp W w/22, w/22) AA R. VEW RRS. Then, for any state E S, TvaR, satisfies
(TvaR, u)s 2 max oEA (p. ws,a - /1ll/aaVws.a /ws,a DnaWaaa
As a special case, when Ps.a is normally distributed Ps.a N (Ps.a Daa), then TvaR for any state 8 E S can be expressed as
(TvaB, v). max aEA
8. Ws,a
Proposition 3.3 shows that by assuming that the transition probabilities are sub-Gaussian, we can easily compute a lower bound of the VaR Bellman update (TvaR, e) for given value function using only the mean and the covariance matrix of P. In the special case where P is normally distributed, we can compute the VaRt Bellman optimality operator TvaR. (v) exactly.
3.1 Performance Guarantees
We now derive finite-sample and asymptotic bounds on the loss of the VaR framework.
Theorem 3,4 (Performance). Let be the fixed point of the VaR Bellman optimality operator TyaR., and x* be the optimal policy in (T). Let p" VaRs [p(x* P)) denote the optimal percentile returns and ò = pb è denote the lower bound the percentile returns computed using the Bellman operator TvaR,, with a = 8/s. Then for each (0, 3/2):
max max
(VaR, [P Ws.
VaRa [P5,a Ws,a]
(6)
SES
Theorem 3.4 bounds the finite sample performance loss of the VaR framework. The loss varies proportionally to the maximum difference between the 6/s and 1 - (1-5/s) percentile of the one-step Bellman update for the optimal robust value function Furthermore, the VaR framework performs better when the uncertainty in the transition probabilities is small.

---

Theorem 3.5 (Asymptotic Performance). Suppose that the normality assumptions on the posterior distribution P in Section 2 are satisfied. For any ó E (0, 1/2), set a =/5 in TvaR.. For any state s and action a, let (P2z.) be the Fisher information matrix corresponding to the true transition probabilities aa Furthermore, let d max.eS, u 1 ((""a))~-s,, be the maximum over state-action pairs of the asymptotic variance of the returns estimate p% Ws Then the asymptotic performance of the VaR framework P w.r.t. the optimal percentile returns p² satisfies
1 (20 (1-885) S (8l1(88))))))))))
1
lim VN P) N-000
Theorem 3.5 shows that the asymptotic loss in performance of the VaR framework convergence to 0, i... limn -oo (p" 0.
3.2 Dynamic Programming Algorithm
We provide detailed description of the VaR value iteration algorithm (Algorithm 3.1) below. We also bound the number of samples required to estimate a single VaR. Bellman update (7VRR. v), for any given policy and state with high confidence Ç.
Algorithm 3.1: Generalized VaR Value Iteration Algorithm
Input: Confidence a E (0, 1/2), Value approximation error 2 0, Transition models P(wi) ), ((wz).--- -w.,) (wwr) sampled from posterior distribution
Output: Robust policy Ta. Lower bound us
Initialize robust value-function un 0, k = repeat
+- to S do for
for to A do
W..a t- rx,a + Y2AA
I-step return from (s, empirical VaR..
g. -- VaR.. (p_, w.
end
end
< ++11
10
(s) + max. (qu),, Ts(s) t max,e
I/ VaR., Bellman optimality update
11
until luu ux-1l 1100 < e(1-7)/7
12
return Tk, 24k
In each iteration of Algorithm 3.1 we compute the one-step VaR. Bellman update TvaR. (v) using the current value function u. When 23 to efficiently compute the empirical estimate of the a-percentile of 1-step returns for any state action a, and value function v, i.e., [aR. (rs.a + yv)]. On the other hand, when P is normally distributed, compute the VaR. Bellman optimality update TvaR, (v) using the empirical estimate of mean (Pa.a)ess,ac) and covariance (E..))ES.aee of the transition probabilities derived from the data I (Proposition 3.3. We repeat these steps until convergence.
normally distributed, we use the Quick Select algorithm
Proposition 3.6 (Empirical Error Bound). For any state action and value function let VaRa [T. us,a] represent the empirical estimate of a-percentile of returns VaRa Ws,a and 6; represent the cumulative density function (CDF) of the random estimate of returns P Ws.a- Suppose that $ is differentiable at the point VaR,, V.R,IpT. Ws,) and let 17 B (VaR, [pT ws,al) represents the density of estimate of returns at point VaR [PT. [T..a W..a). Let M be the number of posterior samples required to obtain empirical error E IR, with confidence - where O < <<> i.e., Pr [VaRalPT.. w.aal VaRalpT. ws,all >
< <. Then, lim M In(9/4)/2x/
We now show that Algorithm 3.1 produces a policy na and value function us that approximates the optimal value function é.
Proposition 3.7 (Value Iteration Error). Define the empirical VaR Bellman optimality operator
Taan. for any value e S and state S as (T v) maX VaRa, [T W.a).. Let
7

---

è E R and it E I represent the fixed points of TvaR, and VAR.. respectively. Suppose that
Algorithm 3.7 returns policy Th and value function u2 and | uolloo rmax/11y. Then,
287
ü us l0 S e, and l| - Uka 10 S 1 1-7
Furthermore, the gap between the empirical and true value functtin is bounded by
| 001000 I 1-7 min (ITvaR. i - TvaR. dilloo: IT ė TvaR, -llo))
Proposition 3.8 (Time Complexity). Let Tmax = d' [R(s, a, 5')),, Then, Algorithm 3.1
lerminates in k [DRRy (tt))))) ) iterations with time complexity O (s² (52 AM (x()))
Furthermore, for any failure probability Ç E (0, 1), suppose that the CDF (4r)) of the random estimate of 1-step returns PT. Vssa is differentiable at the point VaR,, a. and set = &' ('(VaRo [p ws,a)) and M = 1-
1/c(8/)
Then with probability at least - S, holds that time.
||0 unlloo S Os)), and Algorithm 3.1 runs in O
52 (S22lloss Alo0s/y Tmaa
mn)(2)
(1-00-
4 Comparison with Bayesian Credible Regions
We are now ready answer the question: Are Bayesian credible regions the optimal ambiguity sets for optimizing the percentile criterion? For this, we compare the VaR framework with BCR Robust MDPs. First, we derive the robust form of the VaR framework and show that in contrast to the BCR Bellman operator, the VaR Bellman optimality operator implicitly constructs value function dependent ambiguity sets, and thus, these sets tend to be smaller (Proposition I.I). Then, we compare the asymptotic radii of the BCR ambiguity sets and the VaR. ambiguity sets implicitly constructed by TvaR.- For any given confidence level a, the radius of the VaR ambiguity sets asymptotically smaller than that of BCR ambiguity sets (Theorem 4.3). Precisely, the ratio of the radii of VaR ambiguity sets to BCR ambiguity sets is at least v /X3-1.1-.00-
where x5=-1,1-a is the CDF inverse of - a percentile of Chi- squared distribution with degree of freedom S - 1 and Φ 1 the percentile of (0, 1). This implies that there exist directions which the BCR ambiguity sets are at least ((v3) larger than VaR ambiguity sets. Thus, we prove that VaR framework better suited for optimizing the percentile criterion than RMDPs with BCR ambiguity sets.
For any value function v. define the VaR ambiguity set VaR, as
V
X
VaR, 8.a
where
VaR,
{Ps,a E E Ip v2
VaRa v] (7)
s,a
sES,aEA
Proposition 4.1 (Equivalence). The VaR Bellman optimality operator TvaR,, can be expressed
Vs E:: (TvaR_ v), max min acA pEPYaR..
pr(rs.. + 770
Furthermore, the optimal VaR policy E II" solves max min pepaR. p(T, P) where R is the fixed point of the VaR Bellman operator Tvan., i.e., (Tvan, 6).
Proposition 4.1 shows that the VaR Bellman optimality operator optimizes unique robust MDP whose ambiguity sets are SA-rectangular and value function dependent. Notice that for any state 5, action a and value function v. the VaR ambiguity set is a half-space {Ps.a E A P..... v VaR., Ip_. v dependent on the value function e. In contrast, BCR ambi- guity sets are independent of any policy value function and are constructed such that they provide high-confidence guarantees on returns of all policies simultaneously. As a result, BCR ambiguity sets tend to be unnecessarily large.
We now compute the ratio of the asymptotic radii of BCR ambiguity sets and VaR ambiguity sets. Theorem 4.2 (Asymptotic Radii of VaR Ambiguity Sets). For any state and action a, let 18-1
( )--1)) be the Fisher information of the first S- transition probabilities, i.e., (

---

I([(p" ail 18-1 (i
Define (((t,a)=
sin
Suppose that the normality assumptions on the posterior
0r
distribution P in Section 2 are satisfied. Then,
lim VN Pāaa) {Pao E A |Pa.0 Pa Pa S $1 -a)] Pi,a (8) N-200
Theorem shows that the asymptotic form of the VaR ambiguity set is an ellipsoid. Note that, in contrast to the finite-sample VaR ambiguity set PVRR, in problem (7). the asymptotic VaR ambiguity set VaR is independent of the value function v. This is because VaR,, [P],a'] is convex in the value function [39]. Therefore, the asymptotic ambiguity set PValt is simply the intersection of closed half-spaces in PVaR." computed over all value functions
R$ (9. It also worth noting that the radius of the asymptotic VaR ambiguity set PVRR constant. In contrast, the asymptotic radius of the BCR ambiguity sets grows with the number of states in at least one direction, show in the following proposition.
Theorem 4.3 (Asymptotic Radius of Bayesian Credible Regions), For any state and action a, let PRCR_. represent any Bayesian credible region. Let { < VX 105--11-/00-(a--) (1-a)). Suppose that the normality assumptions on the posterior distribution of P in Section 2 are satisfied. Then,
Vs E lim VN(PBCR. -D=,a) g lim VNE(PVVR. N-+00
-P",a)
N N
We note that Theorem 4.3 is adaptation of Theorem 10 in 21 in RL which proves that there exist
directions in which the Bayesian credible regions is at least &
larger than VaR ambiguity sets. Since the value of & only grows with the number of states, we conclude that BCR ambiguity sets sub-optimal for optimizing the percentile criterion. Figure I shows the growth the ratio of radius BCR to VaR ambiguity sets with an increasing number of states.
V
5
Experiments
We now empirically analyze the robustness of the VaR framework in three different domains.
The Riverswim MDP (46 consists of five states and two actions. The state represents the coordinates of the swimmer the river and action represents the direction of the swim. The task of the agent is to learn a policy that would take the swimmer to the other end of the river.
Riverswim:
Population Growth Model: The Population Growth MDP (25) models the population growth of pests and consists of 50 states and 5 actions. The states represent the pest population and actions represent the pest control measures. In our experiments, we use two different instantiations of the Population Growth Model: Population-Small and Population, which vary in the number of posterior samples.
Inventory Management: The Inventory Management MDP (56] models the classical inventory management problem and consists of 30 states and 30 actions. States represent the inventory level and actions represent the inventory be purchased. The sale price s, holding cost and purchase costs P are 3.99, 0.03, and 2.219. The demand is normally distributed with mean= and standard deviation s/c.
Implementation details: For each domain in our experiments, we sample a dataset D consisting of the state s, the action taken a, the reward r and
tuples of the form {s, a,,r, 8'), corresponding the next state s'. We construct a posterior distribution over the models using D, assuming Dirichlet priors over the model parameters. Using MCMC sampling, we construct two datasets Dj and D2 containing M and K transition probability models, respectively.
We construct L train datasets by randomly sampling 80% of the models from Dj each time. We use Di as our test dataset. For any confidence level 5, we train one RL agent per train dataset and method.
For evaluation, we consider two instances of the VaR. framework: one (denoted by VaRN) that assumes that P is a multivariate normal, and another (denoted by VaR) that does not assume any structure over P. We use seven baseline methods for evaluating the robustness of our framework, They are: Naive Hoeffding (35), Optimized Hoeffding (Opt Hoeffding) (3), Soft-Robust (5), and BCR Robust MDPs with weighted & ambiguity sets (WBCR 4 [3. weighted foo ambiguity sets

---

(WBCR ( 31, unweighted & ambiguity sets (BCR (1) 44 and unweighted &o ambiguity sets (BCR 1) ambiguity [40] sets. See Appendix in the appendix for more details.
We report the 95% confidence interval of the robust performance (ó-percentile of expected returns) of the VaR framework the test dataset with that of other baselines for different values of 6.
Methods
Riverswim
Inventory
Population-Small
Population
VaR
68.54 5.08
457.95 + 0.74
-3102.48
429.7
-457.877 + 147.3
VaRN
67.27 + 0.0
452.78 + 0.02
-4005.53 8.76
-4570.17 + 38.84
BCR I
67.27 +
369.67 + 0.0
-5614.95 + 80.28
-6013.21 + 1177.94
BCR L.o
67.27
199.41 = 39.02
-7908.92 41.6
.9033.7 84.28
WBCR
67.9 3.82
454.1 i 4.16
-2290338 1084.26
-548.01 + 225.2
WBCR tso
67.27 0.0
199.4 : 39.02
-7712.43 55,96
-8377.64 + 126.24
Soft-Robust
61.79 + 1.46
460.6 + 0.0
-3647.18 + 94.62
-6932.86 + 154.16
Naive Hoeffding
51.52 + 6.06
+.0
-8647.7 = 59.5
-9127.14 + 140.98
Opt Hoeffding
50.76 4.56
+.0
-8640.48 2.34
-9163.64 + 13.62
Table I: shows the 95% confidence interval of the robust (percentile) returns achieved by VaR, VaRN,
BCR i, BCR foc. WBCR &,. WBCR, Soft Robust, Worst RMDP, Naive Hoeffding and Opt Hoeffding agents at = 0.05 in Riverswim, Inventory, Population-Small, and Population domain.
Experimental Results Table summarizes the performance of the VaR framework and the base- lines for confidence level 8 0.05 (Table 2 and Table in the appendix summarizes the results for 5 = 0.15 and = 0.3 respectively.). We observe that for confidence level = 0.05, the VaR framework outperforms the baseline methods in terms of mean robust performance in most domains. On the other hand, for 5 = 0.15, the VaR framework outperforms basclines in the Population and Population-Sman domains and has comparable performance the Soft-Robust method in the Inven- tory domain. However, at 5 = 0.3 we observe that the VaR framework has lower robust performance relative to the the Soft-Ree Roft-Robust method in Riverswim and Population domains. We conjecture that this is because the Soft- Roft-Roobut method optimizes the policy to maximize the mean of expected returns and therefore able to perform better in cases where lower level of robustness is required. However, we note that in contrast to our method, the Soft-Robust method does not provide probabilistic guarantees against worst-case scenarios.
Furthermore, as expected, we find that in many cases, the robust performance of BCR Robust MDPs with span-optimized (weighted) ambiguity sets (WBCR l, WBCR foe) is relatively higher than the robust performance of Robust MDPs with unweighted BCR ambiguity sets (BCR é, BCR loo). However, we find that even Robust MDPs with span-optimized BCR ambiguity sets are generally unable to outperform the robust performance of our VaR, framework.
Figure 2 compares the robust performance of the VaR. framework and the baselines on both train and test models. The trends in the robust performance of the VaR framework and the baselines are similar both train and test models.
6 Conclusion and Future Work
The main limitation of the VaR. framework is that does not consider the correlations in the uncertainty of transition probabilities across states and actions [19 29 30). However, due to the non-convex nature of the percentile-criterion 3 40), constructing a tractable VaR, Bellman operator that considers these correlations is not feasible. One plausible solution is to use Conditional Value at Risk Bellman operator [ 27 which is convex and lower bounds the Value at Risk measure. We leave the analysis of this approach for future work. Empirical analysis of the VaR., framework in domains with continuous state-action spaces also an interesting avenue for future work.
In conclusion, we propose a novel dynamic programming algorithm that optimizes a tight lower- bound approximation on the percentile criterion without explicitly constructing ambiguity sets. We theoretically show that our algorithm implicitly constructs tight ambiguity sets whose asymptotic radius is smaller than that of any Bayesian credible region, and therefore, computes less conservative policies with the same confidence guarantees on returns. We also derive finite-sample and asymp- totie bounds on the performance loss due to our approximation. Finally, our experimental results demonstrate the efficacy of our method in several domains.
10

---

Acknowledgments
The work in the paper was supported, in part, by NSF grants 2144601 and 1815275.
References
[1] Praveen Agarwal, Mohamed Jelli, and Bessem Samet. Banach contraction principle and applications, pages 1-23. Springer Singapore, Singapore, 2018.
[2] Kishan Panaganti Badrinath and Dileep Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning, pages 51 1-520, 2021.
[3] Bahram Behzadian, Reazul Hasan Russel, Marek Petrik, and Chin Pang Ho. Optimizing percentile criterion using robust MDPs. In Proceedings of the 24th International Conference on Artificial Intelligence and Statisties (AISTATS), pages 1009-1017, 2021.
[4] Bahram Behzadian, Marek Petrik, and Chin Pang Ho. Fast algorithms for connttatra s-rectangular robust MDPs. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[5] Aharon Ben-Tal, Dimitris Bertsimas, and David B. Brown, soft robust model for optimization under ambiguity. Operations Research, 18(4):1220-1233) 2010.
[6] Dimitri P. Bertsekas. Abstract dynamic programming. Athena Scientific, 2013. ISBN 978-1- 986529-42-7.
[7] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.
[8] G. P. Box and G. C. Tiao. Bayesian inference in statistical analysis. International Statistical Review, 43:242, 1973.
[9] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[10] Peter Buchholz and Dimitri Scheftelowitsch. Computation of weighted sums of rewards for concurrent MDPs. Mathematical Methods of Operations Research, 89, 2019.
[11] Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for CVaR optimization in MDPs. In International Conference on Neural Information Processing Systems, pages 3509-3517, MIT Press, 2014.
[12] Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for CVaR optimization in mdps. Neural Information Processing Systems NIPS' 14, page 3509-3517, Cambridge, MA, USA, 2014. MIT Press.
[13] E. Delage and S. Mannor. Percentile optimization for Markov decision processes with parameter uncertainty. Operations Research, 58(1 (1:20)2222233 2010.
[14] Esther Derman, Daniel Mankowitz, Timothy A Mann, and Shie Mannor. Soft-robust actor-critic policy-gradient. In Annual Conference Uncertainty in Artificial Intelligence, 2018.
[15] Esther Derman, Daniel Mankowitz, Timothy A. Mann, and Shie Mannor. A Bayesian approach to robust reinforcement learning. In Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2019.
[16] Javier García, Fern, and Fernández. comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(42):1437-1488 2015.
[17] Andrew Gelman, John B Carlin, Hal S Stern, and Donald B Rubin. Bayesian Data Analysis. Chapman and Hal//CRC, 2014.
[18] Charles Geyer and Glen Meeden. Asymptoties for constrained dirichler distributions. Bayesian Analysis, 8:89-110, 03 2013.

---

[19] Vineet Goyal and Julien Grand-Clement Robust Markov decision process: Beyond rectangular- ity. Mathematics of Operations Research, 48(1):203- 2023.
[20] Julien
and Christian Kroer. First-order methods for Wasserstein distributionally robust MDP. In International Conference Machine Learning (ICML), pages 2010-200 2019, 2021.
[21] Vishal Gupta. Near-optimal Bayesian ambiguity sets for distributionally robust optimization. Management Science, 56(9), 2019.
[22] T. Haarnoja, A. Zhou, Abbeel, and S. Levine. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforeement Learning with Stochastic Actor. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 1861-1870, 2018.
[23] C. A. R. Hoare. Algorithm 65: Find. Communications of the ACM, 4(7)) 1961.
[24] Garud N. Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
[25] Mare Kery and Michael Schaub. Bayesian Population Analysis Using WinBUGS. Elsevier, 2012.
[26] Sasche Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. Springer, 2012.
[27] Elita A. Lobo, Mohammad Ghavamzadeh, and Marek Petrik. Soft-robust algorithms for batch reinforcement learning, 2021.
[28] Daniel J. Mankowitz, Nir Levine, Rae Ung Jeong, Abbas Abdolmaleki, Jost Tobias Springen- berg, Timothy Mann, Todd Hester, and Martin A. Riedmiller. Robust reinforcement learning for continuous control with model misspecification. In Proceedings of the 2020 International Conference on Learning Representations (ICLR), 2020.
[29] Shie Mannor, Ofir Mebel, and Huan Xu. Lightning does not strike twice: Robust MDPs with coupled uncertainty. Proceedings of the 29th International Conference on Machine Learning (ICML), pages 451-458, 2012.
[30] Shie Mannor, Ofir Mebel, and Huan Xu. Robust MDPs with K-rectangular uncertainty. Mathe- matics of Operations Research, 41 41(4):1484-155 1509,, 2016.
[31] P. Massart. The tight constant in the Dvoretzky- wwweeeeeeeefeeiiiiii inequality. The Annals of Probability, 18: 1269 1283, 1990.
[32] Ariel Neufeld and Julian Sester. Robust q- g-learning algorithm for Markov decision processes under wasserstein uncertainty. 2023.
[33] Arnab Nilim and Laurent El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798 2005.
[34] Marek Petrik and Ronny Luss. Interpretable Policies for Dynamic Product Recommendations. In Uncertainty in Artificial Intelligence (UAI), 2016.
[35] Marek Petrik, Mohammad Ghavamzadeh, and Yinlam Chow. Safe policy improvement by mini- mizing robust baseline regret. In International Conference on Neural Information Processing Systems, pages 2314,, 2016.
[36] L. A. Prashanth. Policy gradients for CVaR caaR-conttrained mdps. In Peter Auer, Alexander Clark, Thomas Zeugmann, and Sandra Zilles, editors, Algorithmic Learning Theory, pages 155-169, Cham, 2014. Springer International Publishing. ISBN 978-3-319-1166244
[37] Martin L. Puterman. Markov Decision Processes: Discrete stochastic dynamic programming. John Wiley and Sons, Inc., 2nd edition, 2005.
[38] R. Tyrrell Rockafellar. Convex analysis. Princeton University Press, 1970.
12

---

[39] R. Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2:21-41, 2000.
[40] Reazul Hasan Russel and Marek Petrik. Beyond confidence regions: Tight Bayesian ambiguity sets for robust MDPs. In Proceedings of the 32nd Annual Conference Neural Information Processing Systems (NeurIPS), 2019.
[41] Sergey Sarykalin, Gaia Serraino, and Stan Uryasev. Value-at-risk vs. conditional value-at -atte- in risk management and optimization, chapter 13, pages 270-294. INFORMS, 2008.
[42] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. CoRR, N001777.003444 2017.
[43] A. Shapiro, W. Tekaya, J. P. da Costa, and M. P. Soares. Risk-neutral and risk-averse stochastic dual dynamic programming method. European Journal of Operational Research, pages 375- 391, 2013.
[44] Silvestr Stanko and Karel Macek. Risk-averse distributional reinforcement learning: A CVaR optimization approach. In International Joint Conference on Computational Intelligence, 2019.
[45] Lauren Steimle, David Kaufman, and Brian Denton. Multi-model Markov decision processes. Optimization Online, 2018.
[46] Alexander L. Strehl and Michael L. Littman. A theoretical analysis of model-based interval estimation. In International Conference on Machine Learning (ICML), 2005.
[47] Xihong Su and Marek Petrik. Solving multi-model MDPs by coordinate ascent and dynamic programming.. In Uncertainty Artificial Intelligence (UAI), 2023.
[48] Richard Sutton and Andrew G. Barto. Reinforcement Learning: An introduction. A Bradford Book, 2018
[49] Aviv Tamar, Dotan Di Castro, and Shie Mannor. Policy gradients with variance related risk criteria. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' 12, page 1651-1658, Madison, WI, USA, 2012. Omnipress. ISBN 9781450312851.
[50] Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[51] A. W. van der Vaart. Asymptotic statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998.
[52] Nithia Vijayan and L. A. Prashanth. A policy gradient approach for optimization of smooth risk measures. In Robin J. Evans and Ilya Shpitser, editors, Proceedings of the Thirty- -Nithh Conference Uncertainty in Artificial Intelligence, volume 216 of Proceedings of Machine Learning Research, pages 2168-2178. PMLR, 31 Jul-04 Aug 2023.
[53] Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153-183, 2013.
[54] Huan Xu and Shie Mannor. The robustness- perpsmmms trade-off in Markov decision processes. In Proceedings of the 19th Annual Conference on Neural Information Processing Systems (NeurIPS), 2006.
[55] Huan Xu and Shie Mannor. Distributionally robust Markov decision processes. Mathematics of Operations Research, 37(2):288-333 300, 2012.
[56] Paul Herbert Zipkin. Foundations of inventory management. McGraw-Hill, Boston, 2000.
13

---

A Additional theoretical results
Definition A.1 (Translation Subvariance). The operator I IRS RR satisfies the translation
subvariance property if for all vector v E 1 and scalar there exists E [0, 1) that satisfies
5(v + c1) = (Iv) hel
Definition A.2 (Monotonicity), The operator I R + R& satisfies the monotonicity property if for all R and u E R such that v u, I satisfies
To Tu
Lemma A.3 (Contraction Mapping 66) The operator I R$ RR is a contruction mapping if
satisfies monotonicity and translation subvariance properties, i.e., there exists 7 E [0, 1) such that for all u E S v RR,, I satisfies
[ Tullx S S7 - -01000
The proof Lemma A.3 follows directly from Proposition 2.1.3 in 6 We re-derive the proof for the sake of completeness.
Proof. Denote
c max iu, Us sES
Therefore for all E S.
U, - v2 S C.
Applying to these inequalities and using the translation subvariance (Definition A.I and mono- tonicity (Definition A.2) properties, obtain that for all E S.
(Iu), - 70 (Iv), (Iu), + 7c.
follows that for all s S.
(Tv)); (Tu)s S 7c
and therefore [Tu Tulloo I yc. proving the stated result.
Lemma A... For any policy x. let o and at' be the fixed point the the VaR policy evaluation operator TaR. and Bellman policy evaluation operator Tp. If the VaR Bellman policy evaluation operator Tar. dominates the Bellman policy evaluation operator Tp at 6²" iee., VaR. 6t 3 TT "p"", then, the fixed point of the VaR Bellman evaluation operator TaR., dominates the fixed point of the Bellman evaluation operator TF, i.e., 6" < 0²
We note that in contrast the Bellman policy evaluation operator Tp. the VaR Bellman policy evaluation operator T VaR., is function of the random variable P and is not dependent the transition probabilities P assumed in this setting.
Using the assumption TvaR, 8t algebraic manipulations:
T and from 6 VaR, o and a. TT get by
Proof.
8T
VaR. 6" Tpu" TTp TT 3 3 -0"=
Here P. is the transition probability function corresponding to policy x. Subtracting PP, - -²)) from the above inequality gives.
(1 11-PPp PP-PP)(O v²) 0
where I is the identity matrix.
(I (P-PPa)-1 is monotone can be seen from its Neumann series.
8" -- 1 (I - =0=
which proves the result.
14

---

B Proofs
B.1 Proof of Proposition 3.1
Proposition 3.1 (Validity). The following properties of TvaR., hold for all value functions u, v E RS.
1. The operator TvaB., is contraction mapping on R: [|T -vai,, 01120 S u-1lo-
2. The operator TvaB., is monotone: u ž v = Tvalt., u 2 TvaR, v.
3. The equality TvaR, 8 è has unique solution.
Proof. From Lemma A.3 we know that an operator is a contraction mapping if it satisfies monotonic- ity and subvariance property.
In this proof, we will show that the VaR. Bellman operator VaR, satisfies monotonicity and subvari- ance property, and therefore, a contraction mapping.
will use shorthand rs.a to denote the reward vector corresponding to state and action a, i.e., Ta.a a(..u,)).
First, we show that TvaR,, satisfies translation subvariance property. Consider any e IR and state s. Then.
(TvaR. (v + cc))), max VaR., (pk. (T., +
aEAA
(a)
max VaR., P (Ts,a a + 7 + 7c1)]
acA
Val., [P T s, (ra,a + rv) 7c]
max aEA
max VaR Ps.a (Tx,a + y0)] + 7c acA
(TvaR.. v), 7c
(a) follows from simple algebraic manipulations, (b) follows from ycp yc, (c) follows from the translational invariance property of VaR, measure 41 and (d) follows the definition of the VaR Bellman operator Taa.."
Next, we show that TvaR. satisfies the monotonicity property.
Let u and v be any two value functions such that N u. Consider any state s E S. Then,
(TvaR, v).- (TvaR, u)
max VaR (p. (re.a + tw]]] max VaR (a (r.,a + yu)] aEAA
aeA
max (VaRa ( to)] VaRa P (re, + ru)))
0
(TvaR., v), (TvaR, u)s
(a) follows from the definition of the VaR,, Bellman operator TvaR,, (b) follows from the fact that (Ta.a) yv)], (c) follows from the Va' E A. max.5.A VaR,, [p_ (r..(r + rw)] < VaR,, pp. (r monotonicity property [1] of the VaR operator and u 2 v.
Thus, we prove that TvaR, is --contraction mapping and monotone operator. Since TvaR, is contraction operator on a Banach space and from the Banach fixed point theorem [I] follows that the operator TvaR,, has unique solution é. i.e., Tvan é.
Given a policy x. a state s E S, and transition probabilities P, let
(T Σ (ss, a a. W.s and (TaR,, v), Σ T(s,a) VaR pT.uusal
represent the Bellman evaluation operator corresponding to transition probabilities P and the VaR., Bellman evaluation operator, respectively.
15

---

B.2 Proof of Proposition 3.2
Proposition 3.2 (Lower Bound Percentile Criterion). For any å (0, 1/2), we set the confidence
level a in the operator VaR., to 9/s, then for every policy E II: Prp 0 = 8" D 2 1 6.
Proof. Let a 8/s. Recall that for any policy n, state & E S, transition probabilities P, the Bellman evaluation operator TB and the VaR Bellman evaluation operator VaR, are defined as
(Tpu)s =
Σ aEA
π (8, a)PP 2,0 and (TaRR v)
Σ aEA
T(8, VaRa [P W.
respectively.
Let it be the fixed point of VaR.. conditioned on observed transitions D, and let et be random variable that represents the fixed point of T for given realization of the transition probabilities P. Then, applying Lemma A.4 to VaR, and 7p. we have, 0- 3 v= implies
VAR e' 3 TTO"
That is for each state 8,
VaRa (,,))) 6-1 S P po, 0*
(10)
Using the equation 10) we can bound the probability that the VaR value function lower bounds the true value.
Pr 3 0.h 6 Pr Vs E VaR, ( 8"
S DT.
(())
0*
D
(11)
From the definition of VaR, we know that for any state and action
Pr
VaRa Ps 6*]
pl 0 Dj 2
(12)
Therefore, using union bound and in
we can write
Pr O
D
Pr
VaR
PT (,))
PT
P
SES
Thus,
5
S 5
Pr 10
6D = Σ
=
S
5
#5S
16

---

B.3 Proof of Proposition 3.3
Proposition 3.3. Suppose that Ps.o for any state 8 and action a, is a multivariate sub- Gaussian with mean Ps.a and covariance factor Da,. i.e. E exp (A(p,aa - pa.)) ) s
exp (AZw'znn "naww//h w/22, AA E R. Vi E Then, for any state E S, TvaR. satisfies
(TvaR., U)s 2 max oEA
(a Wsaa (2lm(//) Ws,aDs,auu
As a special case, when Ps.a is normally distributed Ps.a N (P Doah then TvaR., for any state E S can be expressed as
(TvaR.. v)2 max aEd
Pro +5- -a) a) /W,,0 E0 2020
Proof.
(TaR. v)s - max Valt, [p W.aa] aEA
(
maxsup {t) Pr (p3,a Ws 2t) 2 a}
aEAA
max inf {1 Pr ((p., D > (1 Do.a w.o) < aa
aEA
max inf {t] Pr (exp( - P > exp(t Poo < - aa}
aAA
(t a Proeaadd
max inf aEA
t - exp
exp
< 1
2w E,,a Wsaa 6,0
1 iax
t (t pT. w..a)² -2lm(a) Ee.o Wo.0
aEA
maxinf aEA
(1 pT, Wo,) E (-V21n(+/o) w! DanWear V 22n((/a) (all/o)/ul
/Ww, Es,a Was
max
P Wsa
(2ln(H/o)V/w.. D. Es,
aEA
Equality (a) follows from the definition of VaR. (b) follows from using the fact that VaR.[X] infft E R Pr[X > < 1-a} and subtracting p... ws,a on both sides, (c) follows from taking ex- ponential on both sides, (d) follows from applying the upper- bound given by Chernoff bound for sub-Gaussian distribution 77 i.... Pr (exp((ps,a )e..) T..,)) S exp(t p..a Ws.a) S
(t.-p... exp 2w. Eo,a We..
(e) follows from subtracting on both sides and then, taking In on both
sides, (f) follows from simple algebraic manipulations and (g) follows from taking the infimum of the solution interval of t.
Solving for t in step (g), we get VaR., (T. Ws.al PT. wsaa which proves the stated result.
(2ln///) Ws.a Dg,a W.o
Next, we derive the VaR Bellman optimality update TvaR, (v) when As S, E A is normally distributed.
Consider the VaR. Bellman optimality operator defined for any state and value function v as
(TvaR, v), max VaR
PTT Ws.a
(13)
aEAA
From the theory of multivariate Gaussian distributions 77, know that, for any state and action if ps.a is Gaussian distributed N (ps... E, then, P W..o is also Gaussian distributed A ( as w E. ). To find the VaR Ip_ Wa,al for any state and action it is sufficient
17

---

to find t such that Pr(p., Ws,a > t) = a.
(i -o-Paa) us
Ps.a Ws.a
Pr
a
[ W Do, Sasaassa
P Wa,0 1 +
1
W sia 2i Ws
p W8.0
(a)
ww! s,a E Di Wsa
t p wsaa (a) ( Ds
= p Usaa - 1- - a) / W.o
The first equation follows from substracting p ws. and dividing by V / Ws on both sides.
The second equality follows from the definition of CDF of (00 1) and the third equality follows from simple algebraic manipulations.
Substituting the value of t VaRa.p w.al p ssa x 1- a)v w E.,o ws we obtain the stated results.
The normal form of the VaR Bellman optimality operator Tvan, is useful to analyze the asymptotic properties of the VaR Bellman operator.
B.4 Proof of Theorem
Theorem 3.4 (Performance). Let be the fixed point of the VaR Bellman optimality operator TvaB.. and x² be the optimal policy in (I). Let p" = VaR, [p(x", , P)] denote the optimal percentile returns and ~ p= Pb b denote the lower bound on the percentile returns computed using the Bellman operator TvaR, with 8/s. Then for each 8 1/2):
ps
max max SES aEA (VaR 1p Ws.a VaRa [P woal)
(6)
Proof. We denote the optimal policy that optimizes the 5-percentile criterion by T², i.e., x² E arg maxrem VaRs[p(TT, P)].
Recall that è E _ is the fixed point of the VaR,, Bellman optimality operator TvaR. i.e., à TvaR, i and p. â is the returns of the corresponding policy. The operator TØ represents the Bellman evaluation operator for a given policy æ E and a transition probability model P. The Bellman evaluation operator Tp for any S and value E IRS is defined as
(T Ps,((s) W))(())
where (s))(s) (s) +..
is known that the Bellman operator T3 is a --contraction mapping, monotone, and has a unique fixed point. We will use 8** T 8=" to represent the random unique fixed point the Bellman operator T defined for random realization of transition probabilities P. Furthermore, we will use P TT p(m", P) denote the random expected returns corresponding to policy n² and random realization of the transition probabilities P.
Suppose that E R4 upper-bounds the difference in performance of the VaR., policy and optimal perventile-criterion policy n², i.c., p² p=c + p²
18

---

From the definition of VaR. and π², we know that
VaRs(p(<'' P)] sup(t: Pr(p(TT, ,) t > - -0)
Since I + e upper bounds p², we can write
Pr(p(T", P) S 2 = Prip( p)
(14)
The above equation suggests that the error in the performance of the VaR policy is upper-bounded by if Pr[p(T", P) S c) holds with at least probability.
To derive a lower bound on proceed follows.
We begin by showing that p( P) I I
0 oc.
p( ,) - -= p( P) - pb
from the definition of ý and p(TT" P))
1 pp 0r p 6l
|x| 2
(15)
< | (pollil10= -11l@1""""" ô0loo
from Hölder's Inequality
|
60110
|poll 1
Next, we bound l
م|ا to obtain a lower-bound on C.
1/00
l0Th - - à Tpp ú11
1TT 8T -Tp'à+ -+ TØ û TvaR. 0/000
^ Mn
ITp 8" -Tp 611x0 + T i TvaR.. 811o0
~ -0 + +1TT e TVaR. o1100
(a) follows by simply adding and subtracting 7 ú. (b) follows from the fact that "* and ô are the fixed points of TT. and TvaR,, respectively, (c) follows from applying the triangle inequality the R.H.S., and (d) follows from the contraction property of Bellman operator.
Rearranging and re-normalizing the above terms, we get
E1100 S (1 -
T Tvan, 81100
(16)
Then, combining 15 and T6.. we get
p(TT" P) p I|Tp Ta
(8)
(TT 0)2 (TvaR,
max #ES
Y
(17)
(b)
p (s) (2, - VaRa ())
max SES
1
( VaRa (0)
max
sES
(a) follows from the definition of Too norm, (b) follows from the definitions of Tvale, and TH Bellman operators, and (c) follows from the fact that (s)) arg max VaRa, [T (t and thus, VaR.. [T..tt)) u (a))(s)) 2 VaRa (7) (0))
Therefore, for any O.
write
max Pr p(m P) -5 - sES
(VaR, L-g- ( ( VaRa (0) 28
Pr p(T",, P) - - ? sES,
(VaR 1D [. VaR,, [p ( 28
max
(18)
19

---

The first equation in the above follows from Pr Pz.a wsaa > V -يي [ Ussaa
-' for any state s and action a and applying union bound over all states g
yields Pr Ws VaR P ws Vs E
1 - 6. Thus, we get 2 8. The second equation follows by
Pr De. I VaR ميي [P_ w. Vs E
simply replacing x (s) with the worst-case action, i.e., action that maximizes the upper bound.
Comparing (4) and (18) we get
p
max max SES aEA
inf =>0
VaR, 1-6-e P Ws.a VaRa
[P Ws,a
Note that VaR of returns is upper semicontinuous and thus, this implies that the infimum in the above equation achieved &
Therefore, we can write
p² 0 2 1-7 SES aed
max max
(VaR عرد 1p Ws, - VaRo [pJ.a Waoa)
B.5 Proof of Theorem 3,5
Theorem 3.5 (Asymptotic Performance). Suppose that the normality assumptions on the posterior distribution P Section 2 are satisfied. For any 8 E (0, 1/2), set a 6/s in TvaR.. For any state s and action a, let (P'. be the Fisher information matrix corresponding to the true transition probabilities Pa.a. Furthermore, let omas max state-action pairs of the asymptotic variance of the returns estimate p Ws Then the asymptotic performance of the VaR frameworkk P w.r.t. the optimal percentile returns p² satisfies
( be the maximum over
1 (2 6// S 1-7 (8l((5/)))))
1
lim VN(p" P) S N-000
Proof. As noted in Section - we assume that as N - oo, the posterior distribution of transition probabilities at any state and action (P=,a) converges in the limit to multivariate Gaussian distribution with mean Pã.a and covariance matrix I(pt.))t/N. Hence, we can write
lim (p 000
s.a Ws,a P.a ws,a) ~ NO, wT (p".a)-'ws
We know from Proposition be written VaR.,, p t h- (a)o.. Therefore, applying this result to the R.H.S. of Equation 6 we get
3.3
that VaR,, of a univariate Gaussian random variable ~ N o²)
(2) lim N - p)
(1- 11-1-) / WT W3
max max SES aeA
VNP
Ws.a + --1
5
N 000
1 1-
VN''a T "us,a + Φ-
8
Jnn I(pp (pptaa)lzus -1
V
5
(b)
(0-(1-1-0)
Φ-1
1-)
/WTTaa [P Wusa
max max sES aEA
1
S
wT Tpp)..) -1e0s,
S
1
(3))
max max #ES aEA
-h-1
v W. IPP".a) -le.)) -ewaa
5
(8)
8
2b-1
max max SES aEA
5
V
(19)
20

---

(a) follows from the definition of VaRa under Gaussian assumptions, (b) and (c) follow from simple algebraic manipulations, and (d) follows from the fact that vć E (0, 1/2), 0 2 Φb (1-15) 1-6
Φ (1 3), and assuming S > 1. Φ (()). - + ( (5)
We prove the second inequality Theorem 3.5 by leveraging the sub-Gaussian bounds for a standard normal distribution (0, d)) to show that Va' E (0, 1/2), $ $ a') I /2in(/a").
We know that for standard normal distribution X N(0, where R, the following sub-Gaussian bounds holds 77:
Pr (-V22n(2/o)) x S 22nn(2/o)o)) 2 1d
(20)
By definition, for standard normal distribution N/ o2) holds
Pr Pr(- of /2)o S x < 2 - o/ /2) = 1-a
(21)
Comparing equation 20 and 21 we get
+ (1 -///2/2) S 2ln((//)) = Φ Φ- - a') S /2l((//))
(22)
Using the result in
22 in equation 19), proves the second inequality of the theorem.
B.6 Proof of Proposition 3.6
Proposition 3.6 (Empirical Error Bound). For any state s, action and value function v. let (aR.lp... Ws,a] represent the empirical estimate of a-percentile of returns VaRa MaRalpp.. Ws and f represent the cumulative density function (CDF) of the random estimate of returns pT Ws.a Suppose that $ is differentiable at the point VaR [p Ws,a and let nj 4's (VaRa ws,al) represents the density of estimate of returns at point Va. W.,a). Let M* be the number of posterior samples required obtain empirical error E IR with confidence S. where 0 1. ie., Pr VaaRa p w.,a] - VaR LF..a a)l > 8 < S. Then, lime 5 1n(3/)/222
Proof. To prove this theorem, we first compute the derivative of the inverse of the CDF 047 (a)/Ba as follows. From the definition of the edf d, and VaR, we know that, for any a E (0. 1/2). (a) = (P.. W.
From the inverse- function theorem, we get,
(07 (a))'
D,,(aR, (p.Ta ws.al)
1
(a))
Equipped with the above result, we can now proceed to prove the main result.
To prove the result, we need to find M such that
Pr VaR., po wssa) - e VaR.. ID. w. 5 VaR,, 113, wr,al + 1
(23)
Pr 1 (a- mn) VaR., p._ wral S , (a + en) 1-5.
Equation (a) follows from applying a first order Taylor expansion to 471 around the point We apply the following results to obtain bound M
Let E and F represent the empirical CDF and the true CDF of random variable 2. Suppose that the empirical estimate of the CDF F is estimated using M samples from the true distribution of Ž and
21

---

0 < Ç < represents the desired level of confidence guarantees, Then, from DWK inequality [1].
we know that
Pr (IL Flloo 2 Vine/ca/22))) sc
The above equation implies that
< (p 21) or (p) > (1 un) sc, Pr 3p E (0,1): (0,1):
(24)
where 24 = de = /
Thus, applying equation
24 to i.e., = /Inl/cl/2M" = En gives M = ln(3/c//22n)
B.7 Proof of Proposition 3.7
Proposition 3.7 (Value Iteration Error). Define the empirical VaR Bellman optimality operator Valk, for any value v E TRS and state 8 E S as (Tvals v)s = maxaeA VaRa, [F],a Ws,a] Let R and E IRS represent the fixed points of TvaR, and Tvaro respectively. Suppose that Algorithm 3.7 retuurss policy me and value function ug and | -olloo S fmax//1y. Then,
287
[ usl S S, and l UnA ll S 1 1-7
Furthermore, the gap between the empirical and true value function is bounded by
| 001000 S 1-7 min (II ū TvaR, uiloo Vark, è Tvalk, 611oo)
Proof. We begin by noting that similar to the VaR Bellman operator TvaR., the empirical VaR Bellman operator Taa is also a contraction mapping because of the monotonicity of the VaR, operator and since the empirical VaR,, in the algorithm is always computed from fixed set of transition probabilities sampled from the posterior of P.
We can bound the error between the value function us returned by Algorithm 3.1 and the fixed point (ū) of T VaR.
1 ú/loc
uk-1 u1 -2k ái/10
(2)
24 llc
1/ áiloo
(b)
E(7 -1) 1)
244
+ l|ue àl1oo
(
(0)
s(1 -7)
||RAk
ú/lox
7
(d) áll
||a
(a) follows from applying the triangle inequality to the l.c norm, (b) follows from the fact that [u - ll I =(1 <(1-7)/> and || - م|/ E 1 1| wl due to the contraction property of
Tvak, operator, and finally, (c) and (d) follow from simply arranging the terms on both sides.
Next, we bound the approximation error || |
ur bl.0
From the above result, we can write
-11 < á uk <1
(25)
22

---

We will use the shorthand T and T to represent the policy The empirical VaR Bellman optimality
VVR_.' and VaR. Bellman policy evaluation operator VaR_ respectively. Suppose that d û U
VaR.
Ux
( Tū T UT
(b)
T(u + +e1) - UTU
Tu: - -T"u, + yEl
(
TTuu -Tuu + +El
< <T + +e1) - T uh + 7el
(26)
TTu - Tu"u u + 2yEl
|
@
1T û T u + 2y 20
?1/á u xc 2781
(1
@ 2
( 27 S (1 (1-7)
|
(a) follows from the fact that ú is the fixed point of Tū and u, is the fixed point of T", (6) follows from (25). (c) follows from the y-contraction property of T operator, (d) follows from the definition of policy
Tk. (e) follows from (25.. (f) follows from simple algebraic manipulations, (g)
follows from taking -norm on both sides, (h) follows from applying triangle inequality, and and (j) follow from simple algebraic manipulations.
Thus, f u.rloo
2-
Next we bound the error between the optimal value function e and the fixed point of the empirical VaR Bellman optimality operator a.
|
ú ú//oc TvaR. è TvaR., á TvaR, á TvaR. ú0110
[Taa. i - -TvaR, â + Tvan. ā - -TvaR 20/10
[[aatt è - -Tvalt, úill + ||Tvate á - TvaR úi/lo
6 állxx + || ú a-T ú/1x:
Twak.
(a) follows by simply adding and subtracting Tvan., ú, (b) follows from simply arranging the terms, (c) follows from applying triangle inequality, and (d) follows from the contraction property of the Bellman operator Tvan.,
Using simple algebraic manipulations and rearranging the terms in the above equation, we can write
0 úllco I [TvaR. â - TvaR. álloo
(27)
1-7
Similarly, can bound | u|| 3o in the following manner.
6 a/ooc Tvant, é + TvaR. è T Toan Tvak, á||
Tvank à - -Takk á + Taak. --Taak ái/lo
1/@
| è - TaaR ál/ + [|Tvak i TvaR_ ôl1o0
(d)
à/1 úl1oo + TvaR. i T U1100 N
23

---

(a) follows by simply adding and subtracting VaR é, (b) follows from simply arranging the terms, (c) follows from applying triangle inequality, and (d) follows from the contraction property of the Bellman operator VaR.."
Using simple algebraic manipulations and rearranging the terms in the above equation, we can write
| ú0/00 [Tva. ò Va.R. òl1c
(28)
1-7
Thus ||0 ú/100 S , min (ITvaR_ -TViR. ö1|0,, [TvaR á ViaR allbx)
B.8 Proof of Proposition 3.8
Proposition 3.8 (Time Complexity). Let Tmax = o [R(s, a, s')l. Then, Algorithm 3.1
terminates in k = [oggay ((()))) 1 iterations with time complexity O (st AM logt,, Smmr)) )).
Furthermore, for any failure probability Ç (0, 1), suppose that the CDF (Lr) of the random estimate of 1-step returns P ussa is differentiable the point VaRa.P! a), and set " d' D'VaR pT.a a.) and M Of ((pa-n))
1ox(9/c) Then with probability at least S, holds that
|| - ux < (E). and Algorithm 3.1 runs in O
time.
Proof. To bound the number of iterations (k) required achieve value approximation error ||4 we first bound the value approximation error [u; úil30 as follows.
úl 20 I
-
11x
- | VaR.
á TvaR. u4 lox
(6)
5 7/| -/ 1x-1//00
7 [?||TTRR_ át - Var U6-21lo0
(d) Tmax
1-7
(a) follows from the definition of the VaR Bellman operator TvaR. (b) follows from the contraction property of the empirical VaR Bellman operator Trak_ (c) follows from applying the same procedure
as in (a) step (b), and (d) follows from unrolling (c) over ie 2 time steps and using the fact that
||u uo oo S F-mx/1-7 for uo = 0.
We find A such that -| l00 Se
(Fmax) =
In Fmaxx
6(1-7)
k:
(29)
In(1/))
Tmax
k = log
(E(1 (((-)))
The time complexity follows from the fact that any quantile of an array of real values can be computed linear time using the Quick Select algorithm [23), computing 1-step return requires O(S) operations, and single iteration of the loop in lines 3-12 of Algorithm 3.1 computes quantile of returns SA times.
Suppose that by differentiable at the point VaRa w,,a and let 17 = (VaRa PT. ws,a) represents the density of estimate of returns point VaR., IpT W.

---

Let for any state and action ú0,a =,a + -... From Proposition 3.6 we know that to guarantee
Pr VaR u. VaRalp... w.,aal E I 5 M should satisfy lime- Me² = 1n(9/)/22
llTVRR 6 D-Tvon_ 8ll
Furthermore, in Proposition 3.7 we showed that |/ë - 20/00 I Then,
TvaR_ -- VaRo 01100
Pr ( 0/100 S
Pr
6
1 1-9
Pr
Tvaat ①
VaaR 01100 S 55 ((1
(
Σ
Pr
max aEA
VaRa (p ússaa
max VaRa P Uxs E(1 - aeA
#ES
5
S
S
5
(30)
(a) follows from the fact that || ú [Taa, 0-TyiR, +l (b) follows from arranging terms,
1-7
(c) follows from applying the union bound, and (d) follows from applying Proposition and confidence c/s.
and setting
The final time complexity results follow from the triangle inequality té-uullls S || ú x + U.y.
ü so and combining results in Equation (30), Proposition 3.6 and the first part of Proposition 3.8
B.9 Proof of Proposition 4.1
Proposition 4.1 (Equivalence). The VaR. Bellman optimality operator TvaR,, can be expressed as E (TvaR. v) = max min (T + tv)
aeA VAR.. VAR.e
Furthermore, the optimal VaR policy î E TT solves max min pepaan, p( P) where è E RRS is the fixed point of the VaR Bellman operator TvaR. i.e., ό (TvaR. t).
Proof. The first part of the proposition simply follows from the definition of the VaR operator. For any state s, action and value function v, we write
min
p p'
VaRa [p_. Ws.a
(31)
PEP VoR.
The minimum above exists as it minimizes linear function compact set. The direction ">" in (3T) follows immediately from the constraint the construction of the set ValR, The direction "<" follows by linear program duality of the minimization over and from the fact that VaRa pT. w. 2 min W.
Recall that the VaR. Bellman optimality operator defined for each s E S and R as
(TvaR, v),
max VaRa [p_,0 W..a
(32)
aeA
Suppose that the unique fixed point of Tvan, and ússa = rs + 7 the corresponding transition value for each 8 E S and a E A. That is
Tvan.
Then, we define the following robust Bellman operator T: TRS_ RS for each s and v E RS as
(Tv),
max min TTus Wssa aEA Van.
where
(33)
VaR,6
{pe 8 pp Tv Z VaR [p. m
25

---

We now show that ô is also the fixed point of the robust Bellman operator T. Using the equality in (31) we get that
TVaR e
max VaRa [P 1
atA
max a pEP
min
p W0,0
=T
Therefore, è is the unique fixed point of the SA-rectangular robust Bellman operator [24 and á is greedy with respect to the optimal robust value function and, therefore, is an optimal policy that solves
max TEIL PEPVOR,
min
P(TT, P)
(34)
where ò E R is the fixed point of the VaR Bellman operator TvaR.. i..,, è (TvaR.. d).
B.10 Proof of Theorem 4.2
Theorem 4.2 (Asymptotic Radii of VaR Ambiguity Sets). For any state s and action a, let
I(((pr,) 15-1) be the Fisher information of the first S transition probabilities, i.e., aa 18-1
[[((pp 0
Define (=(
Suppose that the normality assumptions on the posterior
distribution P in Section 2 are satisfied. Then,
lim VN P².aa) {paa E A |Pa. Pi,allr( is
15 -()] Pi (8)
For any state and action a, define the 1-step Bellman update function fa,a RR - R such that
(v) Val2a [ (r + yu)]
As noted in (2). we assume that as N > oc, the posterior distribution of transition probabilities for any state and action (P..a) converges in the limit to multivariate Gaussian distribution with mean a and degenerate covariance matrix a//N. Therefore, the 1-step returns P Wxo. is
asymptotically univariate Gaussian random variable, i.e., lim VN N (0, wo (p'.) w..a) Then, we can write
Ws.a D' W..a) ~
lim VN (fea(v) - P'sa (ssa) - -1 a)) [e]][/Wacc (s,all(ppt.) N
(35)
where --1 represents the CDF inverse of standard normal distribution. Equation 35 follows from the analytical form VaR of a Gaussian random variable, i.e., for any Gaussian random variable
Y ~N((,, with mean μ., variance o², and confidence level a, VaRa[Y] = + 10 a)o.
Since fe,a is convex in o when ps.a is Multivariate Gaussian distributed, we can use the definition of support function of closed convex set 9 to retrieve the unique ambiguity set PaRR.
Note that, in this case the support function is feaa and Valt, is the unknown closed convex set 8,a
Vo E R min (ra + + fv)(
Pa.EEP Vall
Vo R min VND. Wna VN
Vo RS:
min
VN (PT.a Wsaa - D T Twa,) VN((foo -P..a "wsa)
Ps.a VaR.
Vo R Zea E (VN(PVAR. -
-P' P%a)): 2 Wan a,0 -- a))l
where the last statement follows from the positive homogeneity and translation property of support functions.
26

---

Rearranging the terms in the above and setting 2s,a Po,a Ps.ar we get
lim v (N(Paa PP..) N-000
P Piia vu R Ps.a E A Wa 2 Piça Ws, (1-oll
(36)
Using basic algebraic manipulations as shown Proposition B.I we can write the asymptotic form of ambiguity set s,a as an ellipsoid
lim VN - P'saa) = { Po. E A Psallr S $ x- a)) N
Pe.a
(37)
Proposition B.1. Consider the ambiguity sets given in equations representations are equivalent.
36 and
37
These two
Proof. For any state s and action a, as N - D0, - E VN 6.8
Pi.a) satisfies
P Ws. Pa Ws,a - ① 11 a))l2sall
Ph. s.a Ps.a Us. 2 - - [1)l [)]l a))lwssall1(pp... lipt..))
(38)
w T s,a (Pa.a
Pi (Pr.a paaa)
I Us S (Φ ( a))² s.a [P )
The first and second equations follow from the definition Valt and simple algebraic manipulations. The third equation follows by multiplying by -1 on both sides and squaring both sides.
Recall that Ps.o for any state and action is categorical random variable. We assumed that the prior is a Dirichlet distribution and therefore. by the property of conjugate prior, the posterior distribution of Ps.a is also Dirichlet distribution. We assumed in Section that as N co, Ps.a is with mean P and degenerate covariance matrix (p,.,) A/N, i.e., covariance matrix I(p)..) /N has S 1 independent rows and S independent columns.
For any state and action a and transition probabilities Ps.a. let Is.a E R-S1 represent the first S - elements of the random variable Ps.a. i.e., as.a = {(p (:))))
5-1 Then, as is Gaussian-
distributed with the mean a² ((p%,))) and invertible covariance matrix ((92,))"// /NN I1f(e" -...))/)))
Thus, if we sample qs,a from N' (gi,.: (9.aa) and qs,a 2 0 and S-1 E (qx.ass S 1, then we
can easily compute the corresponding transition model as
{(g 51 {(P 1:)
8-1
(39)
(qa,a)s =1 Σ (Ps.a)
i=1
Equipped with the above notation, we can proceed to prove the result.
Using the definition of positive semi-definite matrices in Equation (38) we can write
( (< (1 (()'" (Pa.a - (P..) p =0
(40)
Sub-matrices of positive-semidefinte matrices are also bositive-semidefinn Thus, we can write,
((--((1a))
(q (9 aaaa )) 2
(1(9),)) (1))(1_))) (q - (a (haa (1(g),.)
((0 (1-- (1)-a)))² (a) -Qsa (aa )ra))) 1( . 0
(( a II(g drna
a
(qsaa - (a - aaa) 1(q ((qr,a - I:aa I (( ):m)) 2
( (0- - -a) " ( (q -ra)) - (fg.. - -iia) "
I o - ))a))) 2 =0.
27

---

(a) holds because for any A E REx if A
Ax = 0. E R", then A = 0, (b) follows from MU = OYU, M = 0, (c) follows from simple algebraic manipulations, (d) follows from (q,,a - ( I (q,,a - q:.a) 2 because [(g5aa) = 0, and (e) follows from simply rearranging all the terms in the above equation.
Therefore, we get
(As.a (PP -2,0) S (1 (1-)))
a))2 = 11 Teall S $ a)
Thus, it follows from construction that |Pssa Pi (r(p,)) ) Φ (1 a).
The proof for the other direction is simply the reverse of this proof and therefore we omit it.
B.11 Proof of Theorem 4.3
Theorem 4.3 (Asymptotic Radius of Bayesian Credible Regions). For any state and action let PECR. represent any Bayesian credible region. Let & < V 111-11 '(1-o). Suppose that the normality assumptions on the posterior distribution of P in Section 2 are satisfied. Then,
Ys S, A: lim
VN(BCCR -P.aa) Z lim VNE(P N0000
s.a - -P=,a)
N
Proof. For any state and action a and transition probabilities ps.a. Is.a RRS1 represent the first S elements the random variable Ps.a. i.e., Is.a = ((P ) Then, Ôx.a is Gaussian- distributed with the mean 9² a and invertible covariance matrix 1(at,u)"\/a Itl(e" ....+)))))
Thus, if we sample Is.a from N (g ((7,,a) //v) and Is.a 2 0 and E can easily compute the corresponding transition model as
(qua); & 1, then we
di = ((Ppa))i S-1 (qs,)ss =1 Σ (pea)i
(41)
Equipped with the above notation, we will now prove this theorem by contradiction.
For any state and action a, suppose that lim VP(PECR -D.a) S -imm--o00 VNE(P p..o).
Since PBCRa is credible region, it satisfies that
Pr (Dr,a P=aa)) E PBCR. P'.aa
(h)
Pr
VN(ps.a - Paa) E lim VN(BBCR. pr.)) N
lim
N sm
Pr
lim No000
VN(pe.o -Pia) lim VNeePValk - -Pr.))
N-200
(
lim VN Pi.)) TTatt N
- Pi.a) (1 a))²
(a) follows from the definition of Bayesian credible regions, (b) follows from multiplying by VN on both sides and taking limit N + co, (c) follows from the assumption limy VN -P',a) S
1 VNg(PVaR. p.a)). and (d) follows from applying results in (37 and squaring both
sides.
28

---

Since & < Vx3-mu= -- there exists 3 > such that (3 13_-111-- B. Fix such
B. Then write
1 1 S Pr
lim VN - (( -Pea) S 5 (1 - a))² a))))
N-000
In
Pr
lim VN(Ps,o (PP Ps.a) I (XS- (13-1,1-8-0 83]
(6)
$ Pr
lim [|V Pi Pi
(x5 (X8-1,1- 33)
N00
1 Pr
|VN P2 X N
lim
(
-1-8 3 < x
Contradiction!
(a) follows from choosing 3 > 0 such that (1- 2 X5-1,13-a -3, (b) follows from simple algebraic manipulations, follows because of the monotonic property of CDF, and (d) follows
because lim VN(ps... P²a)) NO, I(p",a from construction, lim ll IVN /N(p.. (ps.a
P2.a))lf j- = - (Q... Li,a) [1 (1:::))- -- and, lim \| ($s.a Ts MlF sum of squares of S - normal random variables, which in turn is standard Chi-squared random variable with degrees of freedom $ - 1. Therefore, the probability in (d) can be at most
- B - a.
Therefore, 2
11-a
C Experiments
Algorithm C.I: VaR Value Iteration Algorithm for Gaussian case
Confidence E (0, 1/2), Posterior distribution f, Value approximation Output: Robust policy иe. Lower bound ue Initialize robust value-function uo E R$
Input:
Sample models (ww), P(wz).... P(WM) from posterior repeat
for <- 1 to S do for to A do
w.a &- Ts,a + 7uA
1-step return from (s,a)
g. +- p. u.n
(1 c1) /wo E. Wnn Pa,as En,, are mean covariance at (s,a)
end
end
10
<- ++ (s) +- max. A A (4a). Tx(s)= +- max
11
I/ VaR., Bellman optimality update
12
until luu: ug-1llox S c(1-7)/7
13
return Tk. 4k
D Scalability of the VaR Framework
We define the VaR,, q-value function (Q-function) for any policy E ll q" A A such that for any state and action a, (s, a) = (pT. + +ov=), ), where v"' TVaR, v= is the fixed point of the VaR., Bellman evaluation operator for policy We will use q to denote the valuu function corresponding to the optimal VaR,, policy â, i.e., ((s) = arg max, ( a).
Let qo and d denote the parameterized Q-value and corresponding target Q-value networks with parameters / E O and E respectively. Here qo and Ω may represent any function approximators with parameter space e.
29

---

Methods
Riverswim
Inventory
Population-Small
Population
VaR
83.51 + 11.76
474.98 + 0.7
-1877.66 104.64
33388.26 213.44
VaRN
92.32 + 11.76
472.49 + 2.24
-2271.13 + 165.98
-3140.68 + 122.72
BCR 4
82.04 8.82
377.73 0.0
-3731.29 i 122.4
-4363.46 1: 240.62
BCR Loo
10.57:10.0
199.82 1 39.5
-6668.47 43.1
-8118.68 1: 327.74
WBCR
82.04 1: 8.82
470.39 1 5.82
-3286.26 1115.22
-4257.33 1 194.4
WBCR so
80.57 =
199.82 = 39.5
-6395.77 88.1
-7547.52 = 160,76
Soft-Robust
115.33 + 1.16
477.81 0.0
-2052.83 + 78.2
-3869.46 = 124.72
Naive Hocffding
52.29 :
-0.0
-7778.21 + 89.36
-8496.47 = 205.54
Opt Hoeffding
51.15 6.88
-0.0 + 0.0
-7723.6 + 4.82
-8583.83 + 16.06
Table 2: shows the 95% confidence interval of the robust (percentile) returns achieved by VaR, VaRN,
BCR f, BCR Loc. WBCR l, WBCR, Soft Robust, Naive Hoeffding and Opt Hoeffding agents 5 = 0.15 in Riverswim, Inventory, Population-Small, and Population domain.
Methods
Riverswim
Inventory
Population-Small
Population
VaR
100.27 1 17.24
483.08 1
-1117.57 1: 240.02
-1850.26 = 191.08
BCR 4
108.9 + 21.12
391.39 +: 34.28
-2578.25 + 104.04
-3058.77 = 972.58
BCR 1.0
95.96 + 0.0
254.43 + 44.82
-5437.67 + 46.26
-6428.03 + 1.58.36
WBCR
108.9 21.12
481.07 4.58
- 685.08
2492.599 228.48
WBCR Loo
95.96 0.0
239.76 0.0
-5133885 = 85.44
5944.77
192.38
VaRN
123.78 + 15.34
482.92 = 1.8
-1514.44 = 24.62
-1785.77 = 125.52
Soft-Robust
165.15 + 0.54
484.53 0.0 0.0
-692.08 + 55.04
-1565.09 + 76.24
Naive Hoeffding
53.31 + 13.26
+.0
-7326.64 = 77.52
-7560.94 = 295.96
Opt Hoeffding
51.66 9.94
-0.0
-7020.42 = 4.74
-7457.76 + 12.44
Table 3: shows the 95% confidence interval of the robust (percentile) returns achieved by VaR, VaRN, BCR L1. BCR fox. WBCR éi, WBCR, Soft Robust, Naive Hoeffding and Opt Hoeffding agents 5 = 0.30 in Riverswim, Inventory, Population-Sman Small, and Population domain. Bolded text indicates the instances which the VaR. framework outperforms the other baselines in terms of the mean robust performance.
The optimal Q-value network (4a-) can be learned by simply minimizing the empirical VaR, Bellman residual error JvaR., (0), i.e.,
ÿ0- arg min JVRR (0) 0
( (10(8),)) d'EA
max VaR, [Ex'-p... (Fs, 790(6' 27
(42)
arg min (s,a)D
oEe
where data D is list state-action (s, a) tuples that is collected using the current policy on the mean model P. In this case, the target Q-value network parameters 0 periodically updated by overwriting the target value network parameter with the Q-value network parameters (0).
We can also using any the existing Actor-Critic methods In this case, instead of optimizing the policy to minimize the Bellman residual error, the algorithm will have to optimize the policy to minimize the VaR,, Bellman residual error JVaR,, (0).
22
42
learn the optimal VaR,, policy,
E Implementation Details
Hyperparameters for Riverswim Domain
Number of train models per dataset
80
(M)
Number of test models (K)
700
Number of train datasets (L)
10
Hyperparameters for Inventory Domain
Number of train models per dataset (M)
80
Number of test models (K)
200
Number of train datasets (L)
10
30

---

63
putdfaar divill
Inventory Domain
(b) Riverswim Domain
(c) Population Domain
(d) Population Aopulation-Small Small Domain
Comparison of test and train robust returns achieved by VaR, VaRN, BCR l1, BCR loc. WBCR E,, WBCR, Soft Robust, Naive Hoeffding and Opt Hoeffding agents at confidence level 0.05 in Riverswim, Inventory, Population-Smal and Population domain. VaR framework achieves the highest mean robust returns in most the domains on test and train datasets.
Figure 2:
Hyperparameters for Population-Small Domain
Number of train models per dataset (M)
80
Number of test models (K)
100
Number of train datasets (L)
10
Hyperparameters for Population Domain
Number of train models per dataset (M)
800
Number of test models (K)
1000
Number of train datasets (L)
E.1
Code
The code and datasets are made available at http://dihhbccommmtiabbbaaaaaanf
E.2
Machine Specifications
We concurrently ran all experiments using 120 threads CPU swarm cluster with 2GB memory per thread. The total computational time was ~3 hours.
31


Reviews:
[{"review_id": "0KvPEh0Yy9", "reviewer": "Reviewer_CU8M", "summary": "This paper proposes using percentile criterion optimization for offline and robust reinforcement learning. Instead of using the Bellman optimality operator for value iteration, this paper suggests an algorithm using the Value-at-Risk (VaR) operator to account for pessimism. The VaR operator takes the given percentile of the return among ambiguity sets rather than the maximum. The authors show theoretically and empirically that such an operator leads to tighter value estimation with a given confidence level compared to prior works using Bayesian credible regions. Experiments on several tabular MDPs show that the VaR framework performs better than prior works using Bayesian credible regions.\n", "questions": "1. How does the proposed method compare to frequentist methods, especially when the posterior is not normally distributed?\n\n2. How can we scale up the proposed method to large-scale RL problems?", "limitations": "Limitations are well discussed in the paper.\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper investigates an important problem of robust RL: Bayesian credible regions can be unnecessarily large, leading to overly conservative policies. The proposed VaR operator provably improves prior methods using the Bayesian credible regions.\n\n2. The paper provides a statistical complexity analysis and a computation complexity bound for the proposed empirical VaR operator.\n\n3. The paper is generally well-written and easy to read.", "weaknesses": "1. The proposed method degrades to frequentist pessimism with confidence sets (e.g., [1,2]) for Gaussian cases, which means the method is essentially the same as prior frequentist methods up to constant factors when the posterior is normally distributed, or the approximation in line 8 of Algorithm 3.1 is used (i.e., *VaRN* in the experiments). From the experiments, it seems that *VaRN* performs similarly to *VaR*. It is unclear how much improvement the proposed algorithm has over prior frequentist methods, especially when the posterior is not normally distributed.\n   \n2. The experiments are conducted on small tabular MDPs, and it is unclear how to scale up the proposed method to real-world settings. While the focus of the paper is on the theory side, real-world scale experiments would greatly strengthen the paper.\n\n\n[1] Jin, Chi, et al. \"Provably efficient reinforcement learning with linear function approximation.\" Conference on Learning Theory. PMLR, 2020.\n\n[2] Jin, Ying, Zhuoran Yang, and Zhaoran Wang. \"Is pessimism provably efficient for offline rl?.\" International Conference on Machine Learning. PMLR, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your review and helpful questions and suggestions.\n\n*The proposed method degrades to frequentist pessimism with confidence sets*\nIt is not true that the method degrades to frequentist pessimism. The method remains Bayesian, no matter what is the number of samples. We agree that the solution techniques are similar to methods that aim to provide frequentist guarantees, but the pessimistic coefficients involved in the algorithms are computed very differently in the Bayesian setting from the frequentist setting [3]. As a result, the guarantees in our objective do not translate to similar guarantees in frequentist settings (and vice versa).\n\nAlso note that the normal posterior result (Bernstein-Von Mises) represents a frequentist analysis of a Bayesian setting. Even in this case, the guarantees that we compute are Bayesian, regardless of the number of samples.\n\n\n*The proposed method degrades to frequentist pessimism ... as prior frequentist methods up to constant factors when the posterior is normally distributed, or the approximation in line 8 of Algorithm 3.1 is used (i.e., VaRN in the experiments).*\n\nWe note that the Gaussian VaR Bellman operator (Proposition A.2) and the Sub-Gaussian VaR Bellman operator (Proposition 3.2) are only special cases of our VaR framework. The main contributions of this paper are  a) \na generalized VaR Bellman operator (Equation 5) for optimizing the percentile criterion and b) An in-depth theoretical analysis of the properties of this framework showing that the VaR Bellman operator optimizes a tighter lower bound on the percentile criterion than the state-of-the-art robust MDPs with BCR ambiguity sets. The generalized VaR Bellman operator does not make any assumptions on the distribution of the transition models. \n\nFurthermore, the methods proposed in [1,2] are not comparable with our framework for two reasons. a) They do not specifically account for Bayesian uncertainty in the transition models and hence do not provide any robustness guarantees against the worst $\\alpha$ percentile model, which is our main objective. b) It is not clear how to adapt these algorithms to handle Bayesian uncertainty in the models.\nFinally, [1,2] do not theoretically or empirically compare their results with any Bayesian Robust RL methods.\n\n*From the experiments, it seems that VaRN performs similarly to VaR. It is unclear how much improvement the proposed algorithm has over prior frequentist methods, especially when the posterior is not normally distributed.*\n\nPrior work [3,4] has compared frequentist and Bayesian approaches in the context of robust MDPs. This work already shows that Robust MDPs with Bayesian credible regions outperform Robust MDPs with frequentist ambiguity sets (See figure 4 in [3], Table 1 and 2 in [4]) for any given confidence level. \nOur work improves over the state-of-the-art Robust MDPs with Bayesian credible regions and therefore are guaranteed to perform better than Robust MDPs with frequentist ambiguity sets. Per the reviewer's request, we have added additional experiments that compare with the above-mentioned frequentist methods. \n\n*The experiments are conducted on small tabular MDPs, and it is unclear how to scale up the proposed method to real-world settings. While the focus of the paper is on the theory side, real-world-scale experiments would greatly strengthen the paper.*\n\nThank you for this suggestion. As you rightly pointed out, the focus of this paper is to theoretically show the limitations of existing state-of-the-art algorithms that optimize the percentile criterion framework and propose a new framework with better theoretical guarantees. \n However, the VaR algorithm can be scaled to MDPs with continuous state space. Please check the global response for more details.\n\n[1] Jin, Chi, et al. \"Provably efficient reinforcement learning with linear function approximation.\" Conference on Learning Theory. PMLR, 2020.\n\n[2] Jin, Ying, Zhuoran Yang, and Zhaoran Wang. \"Is pessimism provably efficient for offline rl?.\" International Conference on Machine Learning. PMLR, 2021.\n\n[3] Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs, Neurips 2018\n\n[4] Optimizing Percentile Criterion using Robust MDPs, AISTATS 2021\n\n"}, {"review_id": "o3WBlBQwa5", "reviewer": "Reviewer_JNMN", "summary": "This paper studies a type of robust offline reinforcement learning methods, percentile criterion optimization. Percentile criterion optimization optimizes the policy under the worst \\alpha-percent of the models in an uncertainty set of models, based on the data. In this paper, the authors proposed a type of value iteration algorithms, replacing the standard Bellman backup values with value at risk (VaR) with respect to the posterior distribution of underlying models. The work is built on top of the previous work on Bayesian ambiguity sets and has a less conservative value estimates compared with previous work BCR.", "questions": "1. Please address the questions about soundness of section 4 in weakness #1.\n2. Why it is important to consider Percentile Criterion for offline RL, given it is often very conservative?\n3. Can authors explain the relationship between the proposed methods with robust dynamic programming [3] and the optimal ambiguity set in [paper's ref 14 and 28]. My understanding is that the proposed method is an instantiation of robust dynamic programming algorithm [3] with the uncertainty set to be the optimal ambiguity set in [paper's ref 14 and 28].", "limitations": "The author discussed the limitations of their work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This work proposed a VaR based dynamic programming method to optimize the percentile criterion, and avoid explicitly construct the uncertainty set of models. The proposed dynamic programming method is more tractable computationally compared with some methods constructing the uncertainty set explicitly.\n2. The theoretical analysis in this paper shows that the proposed method can always yield a value estimates that dominate the value function produced by BCR methods, and be a lower confidence bound in the meantime.\n", "weaknesses": "1. The notations and proofs details about the results to section 4 is not very clear.\n - a) It is not clear what is the definition of $v^\\pi$. Which dynamics/models the value function is with respect to. \n - b) The top paragraph in Page 22, in the proof of Proposition 4.1, is very unclear. Please cite and state which theorem it uses, and what's the condition and results, or derive the complete proof for this particular results.\n - c) What does the notation of a set minus a vector (or multiplied by a scalar) means in Eq (10)?\n - b) How does Theorem 4.4 shows \"the asymptotic radius of the BCR ambiguity sets grows with the number of states\" and is \"larger\" (claimed in the last paragraph of introduction), without showing the asymptotic shape of the BCR ambiguity sets. Theorem 4.4 only shows there exists certain elements in $\\mathcal{P}^{BCR}_{s,a}$ that can be from a distance (depending on $|S|$) with $\\bar{p}$.\n\n2. The proposed methods and analysis are limited to the finite state-action space. \n\n3. The empirical study only includes different variants of BCR as baselines.\n\n4. This paper lacks some discussion about related work.\n - a) It lacks of discussion on more practical, robust MDP inspired methods such as [1].\n - b) The discussion of related work is limited to the robust MDP literature and especially Bayesian robust MDP. It lacks of discussion on methods based on frequentists' lower confidence bounds, which is similar to Proposition 3.2, for example pessimistic approaches with tabular settings or linear function approximation ([2] and many similar work).\n\n[1] Model-Based Offline Reinforcement Learning with Pessimism-Modulated Dynamics Belief. NeurIPS 2022.\n\n[2] Is Pessimism Provably Efficient for Offline RL. ICML 2021.\n\n[3] Robust Dynamic Programming. Garud N. Iyengar", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your review and helpful questions and suggestions.\n\n*The notations and proof details about the results in section 4 are not very clear.*\nThank you for pointing this out. We have added the correct notation in the attached pdf. We will add this fix to the main paper.\n\n*The top paragraph on Page 22, in the proof of Proposition 4.1, is very unclear.*\n\nThank you for your feedback. The proof follows along lines similar to Theorem 2.1 in [1] which shows that a robust Bellman operator with S-A rectangular ambiguity sets (e.g. The VaR ambiguity sets in Equation 3) optimizes the policy to maximize the returns of the worst model in the ambiguity set (Equation 4). Due to lack of space, we cannot provide the entire proof in the rebuttal but we will add it in the next version of the paper.\n\n[1] Robust Dynamic Programming, Mathematics of Operations Research, 2014\n\n*What does the notation of a set minus a vector mean?*\n\nThis notation indicates that we are simply subtracting the given vector from each vector in the set. Both, VaR and BCR ambiguity sets are ellipsoids centered at $\\bar{p}_{s,a}$. We are simply zero-centering these ambiguity sets. This notation is common in Operations research papers [2].\n\n[2] Near-Optimal Bayesian Ambiguity Sets for Distributionally Robust Optimization\nWe will clarify this notation in the main paper. \n\n\n*How does Theorem 4.4 show \"the asymptotic radius of the BCR ambiguity... is \"larger\"? *\n\nThe theorem shows that even we scale the $VaR$ ambiguity set by $\\xi <\\frac{\\sqrt{\\chi^2_{S,1-\\alpha}}}{\\Phi^{-1}(1-\\alpha)}$, it will not contain any $BCR$ ambiguity set. In other words, the result is independent of the particular shape of the BCR ambiguity set. Here, the factor $\\frac{\\sqrt{\\chi^2_{S,1-\\alpha}}}{\\Phi^{-1}(1-\\alpha)}$ is proportional to the square root of  $1-\\alpha$ percentile of a Chi-squared distribution with $|S|$ degrees of freedom. The value of $1-\\alpha$ percentile of a Chi-squared distribution grows with the number of degrees of freedom and hence we state that the size of $\\mathcal{P}_{s,a}^{BCR}$ will grow with $|S|$. The result uses Theorem 10 in [2], which proves it by contradiction. \n\n*The empirical study only includes different variants of BCR as baselines.*\n\nThe goal of our paper is to improve upon the existing algorithms that optimize the percentile criterion. The Robust MDPs with $L_1$ and $L_{\\infty}$ weighted ambiguity sets (WBCR-$l_{1}$, WBCR-$l_{\\infty}$) proposed by [3] are the state-of-the-art frameworks that optimize the percentile criterion and hence, we compare against these methods. However, we have included additional experiments that compare against other baselines in the attached pdf.\n\n*This paper lacks of discussion on methods based on frequentist bounds. ...more practical, robust MDP*\nWe will add a discussion about this paper in our related works section.\n\n* It lacks a discussion on methods based on frequentists' lower confidence bounds*\n\nThank you for pointing this out. We will add a discussion on the frequentist methods and compare confidence bounds with them in the next version of our paper. We note that prior work [3,5] has empirically shown that Robust MDPs with Bayesian credible regions give better robustness guarantees against model uncertainty than Robust MDPs with frequentist ambiguity sets. Our work improves upon the confidence guarantees of [3,4] by a factor of |A|.\n\n[3] Optimizing Percentile Criterion using Robust MDPs, AISTATS 2021\n[4] Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs, Neurips 2018\n\n*Why it is important to consider Percentile Criterion, given it is often very conservative*\n\nThe percentile criterion is well-studied in the Robust RL [3,5,6,7] literature due to its probabilistic robustness guarantees under model uncertainty. In model-based offline RL, transition probabilities must be estimated from data. Errors in estimates of transition probabilities can accumulate and results in learning policies that fail catastrophically when deployed. Hence, we need the percentile criterion to account for uncertainty in the transition models.\nThe percentile criterion is less conservative than worst-case Robust MDPs [4] that are popularly adopted in Robust RL literature. This is because the latter optimize against the worst model in the uncertainty set whereas the percentile criterion allows users to determine the percentage of models against which the policy should be robust. \n\n[6] Percentile Optimization for Markov Decision Processes with Parameter Uncertainty\n\n[7] Value-at-Risk vs. Conditional Value-at-Risk in Risk Management and Optimization, Operations Research 2014\n\n*Can authors explain the methods in [3] and in [paper's ref 14 and 28]?*\n\nThe robust dynamic programming work in [3] optimizes Robust MDPs with frequentist ambiguity sets and provides frequentist guarantees whereas the VaR framework internally constructs Bayesian ambiguity sets and provides Bayesian robustness guarantees against model uncertainty. \n[14] constructs Wasserstein ambiguity sets but does not optimize the percentile criterion and hence, does not provide any probabilistic guarantees on the true returns of the optimal policy like the VaR framework.\n[28] optimizes the percentile criterion using Robust MDPs with Bayesian credible regions and frequentist ambiguity sets and shows that Robust MDPs with Bayesian ambiguity regions perform better than Robust MDPs with frequentist ambiguity sets.\nOur work improves upon the confidence guarantees provided in [28] by a factor of $|A|$, (see Proposition 3.1) i.e. The confidence level $\\alpha$ used in the construction of ambiguity sets for $1-\\delta$ confidence on the true return is required to be $\\frac{\\delta}{SA}$ in [28] whereas in our work only requires $\\alpha$ to be $\\frac{\\delta}{S}$ for the same confidence guarantees. We also show that the VaR framework will outperform Robust MDPs with any type of Bayesian credible region with high probability (Theorem 4.4).\n"}, {"review_id": "CxHntXD9rq", "reviewer": "Reviewer_8VhD", "summary": "This paper considers robust policy optimization problem, which optimizes the percentile criterion to get a policy. It constructs an uncertainty set that contains the true model with high probability, and optimizes for the worst model in the set. Previous works use Bayesian credible regions as uncertainty sets, but it was usually considered to be overly conservative. This paper proposes Value-at-Risk based dynamic programming approach that does not explicitly construct uncertainty sets, but learns with a modified backup operator. The paper shows that theoretically and empirically the proposed approach constructs much less conservative robust policy compared to Bayesian credible regions.", "questions": "- How is this approach \"practically\" differs from CVAR based approaches? Can you provide empirical results of CVAR algorithms as well?\n- Are the experiment results statistically significant?\n- Even if BCR method assumes a lot larger region resulting in overly conservative polices, isn't it OK practically if we get good trade-off between the return and the robustness? Since we will usually optimize the robustness hyper-parameter to make the algorithm work in desired way, if BCR with $\\delta=0.5$ gives same policy to VaR with $\\delta=0.05$, it seems just fine for me. If we give $\\delta=1$, the compared algorithms will all act like standard RL algorithms, and there will exist $\\delta'$ for BCR that corresponds to the performance of $VaR$ with $\\delta$.", "limitations": "The authors addressed the limitations.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- First paper to consider VaR framework and VaR Bellman operators, which are quite novel.\n- Concrete theoretical results for proposed framework and algorithm\n- Explicitly comparing the size of ambiguity sets theoretically seems to be a novel approach\n- The algorithm itself is quite simple and practical", "weaknesses": "- mainly only compares with BCR theoretically and empirically, while there exists a number of other different approaches in solving Robust MDP, as far as I know.\n- I does not think showing the returns alone in the experiments are enough to prove the efficiency of proposed methods, since any RL algorithm that is independent to given $\\delta$ will give the best return. In other words, we need to be sure that the algorithms satisfies the percentile criterion. In that sense, the empirical experiments do not seem complete.\n- While this paper only focuses on methods to solve for percentile criterion and robust MDPs, it would be interesting to also compare against other safe RL or offline RL methods to see whether the algorithm works practically compared to those methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and helpful questions and suggestions.\n\n*mainly only compares with BCR theoretically and empirically, while there exists a number of other different approaches in solving Robust MDP, as far as I know.*\nWe have addressed this concern in the global response to the authors.\n\n*I do not think showing the returns alone in the experiments is enough to prove the efficiency of the proposed methods since any RL algorithm that is independent of the given will give the best return. In other words, we need to be sure that the algorithms satisfy the percentile criterion. In that sense, the empirical experiments do not seem complete.*\n \nWe would like to clarify that we compare the percentile returns of all the algorithms on the test dataset. The percentile returns are computed as the expected returns corresponding to the worst $\\delta$-percentile model in the test set (for 1-$\\delta confidence guarantees).\n \n*While this paper only focuses on methods to solve for percentile criterion and robust MDPs, it would be interesting to also compare against other safe RL or offline RL methods to see whether the algorithm works practically compared to those methods.*\n\n\nThank you for this suggestion. Our paper focuses on developing and theoretically analyzing a percentile-criterion optimization framework that improves upon existing percentile-optimization frameworks in Robust Robust Reinforcement Learning. We are more concerned with handling model uncertainty (epistemic uncertainty) and not system uncertainty (aleatoric uncertainty) which is what safe RL methods do and therefore, we do not think that these methods can be compared with safe RL methods. Additionally, it is unclear how to modify the safe RL and general offline RL methods to work with Bayesian uncertainty.\n\n*How is this approach \"practically\" differs from CVAR-based approaches? Can you provide empirical results of CVAR algorithms as well?*\n\nAll the existing work [1,2,3,4,5,6] based on CVAR approaches only handles aleatoric (system) uncertainty and not model uncertainty. We have provided additional experimental results with a CVaR Bellman framework. However, we note that we are not aware of any published work that proposes that analyzes the CVaR measure in the context of model uncertainty.\n\n[1] Risk-Constrained Reinforcement Learning\n\nwith Percentile Risk Criteria, JMLR 2018\n\n[2] Towards Safe Reinforcement Learning via Constraining Conditional Value at Risk, ICML 2021\n\n[3]Algorithms for CVaR Optimization in MDPs, Neurips 2014\n\n[4] Risk-Averse Offline Reinforcement Learning\n\n[5] Risk-Averse Offline Reinforcement Learning, Arxiv 2021\n\n[6] Being Optimistic to Be Conservative: Quickly Learning a CVaR Policy, 2019\n\n\n\n*Are the experiment results statistically significant?*\n\n\nIn the main paper, we have used a single train dataset of models for training the agent and a single test dataset of models for computing the percentile returns. The experiments in the paper were meant to be case studies and so we did not ensure that they are statistically significant. However, we have now computed statistically significant results and added them in the attached pdf below.\nWe will add these results to the final version of the paper.\n\n*Even if BCR method assumes a lot larger region resulting in overly conservative policies, isn't it OK practically if we get a good trade-off between the return and the robustness?*\n\nWhen we say that the robust policies are overly conservative, it means that they tend to take unnecessarily sub-optimal actions in the worst-case scenario which results in the agent achieving poor poor robust performance. The goal of Robust RL frameworks is to maximize the worst-case returns and therefore, there is a need for learning policies that have good robust performance for the same confidence guarantees.\nPrior work has shown [1,2,3] that large uncertainty sets result in poor robust performance and therefore, much work [1,2] has attempted to optimize the size of these ambiguity sets using various heuristics. However, many of these works use Bayesian credible regions as ambiguity sets which can be very large as we show in our paper (Theorem 4.4). Therefore, these works still suffer from conservative policies. Our work evades this problem by using the VaR framework that constructs ambiguity sets that are tighter than any Bayesian credible regions.\n \n[1] Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs, Neurips 2018\n\n[2] Optimizing Percentile Criterion using Robust MDPs, AISTATS 2021\n\n[3] A Bayesian Approach to Robust Reinforcement Learning, UAI 2019\n.\n\n\n"}, {"review_id": "s3l8sotJHi", "reviewer": "Reviewer_sypg", "summary": "This paper proposes a novel offline RL algorithm, which is a dynamic programming algorithm to optimize a tight lower-bound approximation on the percentile criterion based on Value-at-Risk. \nA solid theoretical analysis is made to demonstrate the proposed VaR value iteration algorithm implicitly constructs tight uncertainty sets that are smaller in size than any optimized Bayesian credible region (BCR).\nFurthermore, this work provides both finite-sample and asymptotic bounds on the loss within the VaR framework.\nEmpirical results show that VaR outperforms BCR Robust MDPs on several tasks.", "questions": "1. As stated in *Proposition 3.1*, the confidence level $\\alpha$ is set as $\\delta / S$. However, when the state space is large, will the calculation of $\\text{VaR} _{\\alpha}[\\tilde{p} _{s,a} ^ \\top \\omega _{s,a}]$ be challenging due to the high confidence?\n2. Additionally, the small value of $\\alpha$ in *Proposition 3.2* results in a large value in the second term of the RHS. This raises concerns about the tightness of the lower bound and its suitability for optimizing the LHS.\n3. I don't think the results of VaR and VaRN on Riverswim should be bolded in Table 1 since they are the same as others. \nFurthermore, the results for Riverswim do not differentiate between the algorithms.\nIt would be worth considering increasing the number of states in Riverswim to enhance the difficulty level and provide a more comprehensive evaluation for the algorithms.", "limitations": "**Limitations** is discussed in *Section 6*.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The proposed VaR algorithm is devised to optimize a lower bound on the percentile criterion without explicitly constructing ambiguity sets compared to BCR.\n2. The paper provides comprehensive theoretical analysis on various aspects, including the Lower Bound Percentile Criterion, finite-sample and asymptotic bounds on the loss within the VaR framework, as well as the Equivalence of VaR Bellman optimality operator and a unique robust MDP with SA-rectangular ambiguity sets. These analyses offer reliable guarantees and contribute to the robustness of the proposed approach.", "weaknesses": "1. The VaR algorithm heavily relies on a precisely estimated transition model $\\tilde{p} _{s,a}$. However, in offline RL, the availability of a limited dataset poses a constraint on the quality of this estimation. This limitation could potentially pose challenges for the VaR algorithm, particularly in complex tasks where the accurate modeling of the transition dynamics becomes more challenging.\n2. The proposed VaR, as originally designed, focuses on MDPs with discrete state and action spaces. \nExtending the algorithm to complex environments with continuous state and action space can be really hard.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your review and helpful questions and suggestions.\n\n*The VaR algorithm heavily relies on a precisely estimated transition model*\n\n**We would like to clarify that this is not true. We use Bayesian models to represent the uncertainty in the transition model estimate. We have mentioned in the preliminaries of the main paper that we derive a posterior distribution over the transition models using the offline data $\\mathcal{D}$. We are proposing the percentile criterion method to achieve robustness against the uncertainty in the estimate transition model.**\n\n*The proposed VaR, as originally designed, focuses on MDPs with discrete state and action spaces. Extending the algorithm to complex environments with continuous state and action space can be really hard.*\n\nWe would like to clarify that this claim is not true as well. It is possible to scale this algorithm to MDPs with continuous state space. We have addressed this concern in the global response.\n\n*As stated in Proposition 3.1, the confidence level ...is set as. However, when the state space is large, will the calculation of \n be challenging due to the high confidence?*\n\nFor large state spaces, the confidence level would have to be treated as a hyper-parameter and selected using cross-validation method based on the desired empirical robust performance on the validation dataset. Please see the global response for more details.\n\nIt is also important to note that several prior works establish guarantees for tabular MDPs [1,2,3,4] as establishing these guarantees for MDPs with continuous state space is difficult. In these prior works, the confidence level depends on both, the number of states |S| as well as the number of actions |A|. Our work improves upon these works by obtaining a tighter bound on the confidence level $\\alpha$ that is only dependent on |S| instead of |S| and |A| (Proposition 3.1).\n\n[1] Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs, Neurips 2018\n[2] Optimizing Percentile Criterion using Robust MDPs, AISTATS 2021\n[3] Robust Markov Decision Processes, Mathematics of Operations Research, 2014\n[4] Robust Dynamic Programming, Mathematics of Operations Research, 2014\n\n*Additionally, the small value of Proposition 3.2 results in a large value in the second term of the RHS. This raises concerns about the tightness of the lower bound and its suitability for optimizing the LHS.*\n \n As mentioned above, our work improves upon the bounds established by prior work.\n We agree that these bounds may not very tight but they are better than the state-of-the-art percentile-optimization frameworks proposed in [1,2].\n \n \n*I don't think the results of VaR and VaRN on Riverswim should be bolded in Table 1 since they are the same as others. Furthermore, the results for Riverswim do not differentiate between the algorithms. It would be worth considering increasing the number of states in Riverswim to enhance the difficulty level and provide a more comprehensive evaluation of the algorithms.*\n\nThank you for this suggestion. We will use a larger and more complex Riverswim environment in the final version of the paper as well as fix the bolding in Table 1. \n"}, {"review_id": "yTrQYut60t", "reviewer": "Reviewer_CS3B", "summary": "This paper proposes a novel dynamic programming algorithm for optimizing the percentile criterion in offline Reinforcement Learning (RL) without explicitly constructing any uncertainty sets. The authors introduce the Value-at-Risk (VaR) Bellman operator for optimizing the percentile criterion, and show that it is a valid contraction mapping that optimizes a tighter lower bound on the percentile criterion compared to Robust Markov Decision Processes (RMDPs) with Bayesian credible region (BCR) ambiguity sets. The paper also provides theoretical analysis and bounds on the performance loss of the proposed framework and compares the asymptotic sizes of BCR and VaR ambiguity sets. Empirical results demonstrate the efficacy of the VaR framework in several domains.", "questions": "In Table 1 of the paper, what is the criterion for highlighting a cell in each row corresponding to different domains (Riverswim, Population, Population-Small, and Inventory)? It seems that all of the item in the first row should be highlighted.\n\nWhat will the number of samples of the posterior samples of $\\tilde{P}$ affect the experimental results?", "limitations": "The paper does not discuss the application of the VaR framework to continuous state-action spaces in RL domains, limiting the understanding of its applicability to a wider range of problems. The time complexity of a single iteration in the algorithm, as mentioned, is O(SAN), which may make it challenging to apply the method to MDPs with large or continuous state and action spaces.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "As a non-expert in this field, I find the paper interesting and addressing an important problem in offline reinforcement learning by proposing a novel dynamic programming algorithm.\nThe authors provide a thorough analysis of the proposed VaR framework, including performance guarantees and comparisons with BCR ambiguity sets.\nEmpirical results show the effectiveness of the VaR framework in various domains, outperforming baselines in terms of robust performance.", "weaknesses": "The clarity of this paper could indeed be improved in several aspects. For instance, the authors use \"w\" to represent the index in line 89 and also use \"w_{s,a}\" in line 139 to represent the values, which might be confusing for readers.\n\nAdditionally, the authors attempt to answer a key question in this paper: \"Are Bayesian credible regions the optimal ambiguity sets for optimizing the percentile criterion?\" However, this problem is not clearly defined, and the criterion for optimality is not explicitly explained. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your review and helpful questions and suggestions.\n\n*The clarity of this paper could indeed be improved in several aspects. For instance, the authors use \"w\" to represent the index in line 89 and also use \"w\\_{s, a}\" in line 139 to represent the values, which might be confusing for readers.*\n\nThank you so much for this suggestion. We will improve this in the next version of the paper.\n\n*Additionally, the authors attempt to answer a key question in this paper: \"Are Bayesian credible regions the optimal ambiguity sets for optimizing the percentile criterion?\" However, this problem is not clearly defined, and the criterion for optimality is not explicitly explained.*\n\nThank you for pointing this out. We will explicitly specify the criterion for optimality in the main paper. \nThe criterion for optimality is the size of the ambiguity sets for any given confidence level $\\alpha$. It is well known [1,2,3] that larger ambiguity sets result in unnecessarily conservative policies and poor robust returns.\nThe goal of the paper was to show that the Bayesian credible regions can be unnecessarily large (Theorem  4.1) and are always larger than the VaR ambiguity sets for the same confidence level (Theorem 4.4). This implies that the Bayesian credible regions are not in-fact optimal for optimizing the percentile criterion and that VaR ambiguity sets are better suited for optimizing the percentile criterion.\n\n[3] A Bayesian Approach to Robust Reinforcement Learning, UAI 2019\n\n*In Table 1 of the paper, what is the criterion for highlighting a cell in each row corresponding to different domains (Riverswim, Population, Population-Small, and Inventory)? It seems that all of the items in the first row should be highlighted.*\n\nThank you for pointing it out. We will fix it in the next version of the paper.\n\n*What will the number of samples of the posterior samples  affect the experimental results?*\n Theorem 3.4 computes the asymptotic performance loss of the VaR framework relative to the performance of the optimal policy that optimizes the percentile criterion. As expected, the performance loss goes to zero, as the number of posterior samples goes to infinity , i.e., $N\\to\\infty$.\n We will add an ablation study to the main paper that shows how the number of samples empirically affects the experimental results. \n\n*The paper does not discuss the application of the VaR framework to continuous state-action spaces in RL domains, limiting the understanding of its applicability to a wider range of problems. The time complexity of a single iteration in the algorithm, as mentioned, is O(SAN), which may make it challenging to apply the method to MDPs with large or continuous state and action spaces.*\n \nWe note that this complexity is only for tabular MDPs. In the case of MDPs with continuous states, we can use the Sample Average Approximation method (SAA) [1] to obtain an empirical estimate of the $VaR$ update via sampling. In this case, the time complexity would depend on the number of samples of next-states sampled using the transition models sampled from the posterior, the number of these (posterior) transition models and the number of actions.\n We have provided a discussion on how to scale our algorithm to MDPs with continuous state space in the global response.\n \n [1] Sample Average Approximation,  Encyclopedia of Operations Research and Management Science 2016\n\n"}]

Author rebuttal:
**Scalability of VaR Framework**

The main goal of this paper is to theoretically show the limitations of existing state-of-the-art algorithms that optimize the percentile criterion framework and propose a new framework with better theoretical guarantees and therefore, we focus less on the empirical analysis.
***However, it is possible to computationally scale our framework to MDPs with continuous state spaces.***

Recall that the VaR Bellman operator optimizes a lower bound on the percentile criterion. Thus, we can use the VaR Bellman operator with any deep Q-learning or Actor-Critic methods and minimize the VaR Bellman residual error ($J_{VaR}(q^{\pi}_{\theta})$ defined in attached pdf) to obtain the optimal VaR policy that optimizes a lower bound on the percentile-criterion.

In this case, we would treat the confidence level $\alpha$ as the hyperparameter value and choose $\alpha$ using the cross-validation method based on the desired empirical robustness performance on the validation model dataset. Note that this approach is not uncommon. Several scalable prior work on Robust MDPs that use KL Divergence based ambiguity sets, Relative Entropy based ambiguity sets, Wasserstein distance based ambiguity sets or  $\Phi$-Divergence based ambiguity sets [1,2,10,11] treat the size of these ambiguity sets as a hyperparameter.

We can also directly use scalable algorithms for Robust MDPs when we assume that $\tilde{P}$ is Gaussian distributed. Recall that when $\tilde{P}$ is Gaussian distributed, the VaR Bellman operator optimizes a Robust MDP with a special ambiguity set provided in Eq 9 in the main paper.

Thus, we can use scalable algorithms in [8,9] to directly optimize this Robust MDP.

We note that our current theoretical probabilistic guarantees only apply to tabular settings. However, it is important to realize that several prior [1,2,3,4,5,6,7] work on Robust MDPs and percentile optimization only provide theoretical guarantees for tabular settings. This does not indicate that it is not possible to get any guarantees for continuous state space but that it is difficult and unclear how to derive them. 

[1] Robust Markov Decision Processes, Mathematics of Operations Research, 2014

[2] Robust Dynamic Programming, Mathematics of Operations Research, 2014

[3] Distributionally Robust Markov Decision Processes, Neurips 2010

[4] Robust Markov Decision Processes: Beyond Rectangularity, 2018

[5] Reinforcement Learning in Robust Markov Decision Processes, Neurips 2013

[6] Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs

[7] Optimizing Percentile Criterion using Robust MDPs, AISTATS 2021

[8] Scaling Up Robust MDPs by Reinforcement Learning, JMLR 2014

[9] Robust Reinforcement Learning using Least Squares Policy Iteration with Provable Performance Guarantees, ICML 2021

[10] Wasserstein Robust Reinforcement Learning, 2019
[11] Robust ϕ-Divergence MDPs

**Additional Experiments**

We have compared our VaR framework against the following baselines in the additional experiments provided in the pdf.

 [1*] WBCR $l_1$, WBCR $l_{\infty}$ -> Optimizing Percentile Criterion using Robust MDPs, AISTATS 2021
 
[2*] BCR $l_1$, BCR $l_{\infty}$, Optimized Hoeffding -> Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs, Neurips 2018, Deviation of the Empirical Distribution, Weissman et al, 2003

[3*] Worst RMDP -> Robust Reinforcement Learning under model misspecification, ICLR 2020

[4*] Soft-robust -> Soft-Robust Actor-Critic Policy-Gradient, UAI 2018

[5*] Naive Hoeffding -> Safe Policy Improvement by Minimizing Robust Baseline Regret, Petrik et al 2016, Inequalities for the L1 


Experiment details: We use the Bootstrap sampling approach to compute the mean and standard deviation statistic on the robust performance ($\delta$ percentile of expected returns) of the robust RL methods.  We generate 10 datasets of train model by randomly sampling 80% models from the original train dataset. We use each train dataset to train one RL agent per method. We then compute the mean and standard deviation of the robust performance ($\delta$ percentile of expected returns) of RL agents of each method on the test dataset. 

Table 1 and Table 2 show the mean and standard deviation of the robust (percentile) returns at confidence level $\delta=0.05$ and $\delta=0.30$ achieved by *{VaR}*, *VaRN*, *BCR* $\ell_1$, *BCR* $\ell_\infty$, *WBCR* $\ell_1$ and *WBCR* $\ell_\infty$, *CVaR*, *Soft-Robust*, *Worst (-case) RMDP*, *Naive Hoeffding* and *Optimized Hoeffding* in Riverswim, Inventory , Population Small and Population domains. 

We note that frequentist methods , i.e., Naive Hoeffding and Optimized Hoeffding construct frequentist ambiguity sets (Theorem 4.1 and Appendix C.1 in [2*]) whose size depends on the number of samples observed per state-action pair in the dataset . In Riverswim, Population small and Population dataset, the number of samples for some state-action pairs is 0 and hence, we couldn't evaluate frequentist methods on these datasets.


Our experiments confirm that VaR Framework and Bayesian Robust MDPs achieve superior robust performance compared to frequentist methods (Naive Hoeffding and Optimized Hoeffding).

We also note that in many cases, we observe that VaR has similar performance to Soft-robust and Worst-case RMDP. We conjecture that this is due to small variance in the transition models as a result of which the expected returns distribution does not have a fat tail. Furthermore, we also believe that the environments may be too simple for evaluating the true difference in performance of these robust measures. However, note that prior work have used these environments for robustness evaluation [6,7].   We will work towards adding more complex environments in the camera ready version of the paper.





Meta-review: This paper considers a novel notion of ambiguity sets based on Bayesian inference to execute risk-sensitive optimization in the offline setting, with technically innovative theoretical analysis substantiating the proposed approach. While experimental evidence is limited, theoretical development and analysis is novel enough to warrant acceptance, which is mostly the perspective of the reviewers.
Decision: Accept (poster)