Offline policy selection under Uncertainty
Authors: Mengjiao Yang
Bo Dai
Ofir Nachum
George Tucker
Dale Schuurmans
Venue:  (2021)
Keywords: Off-policy selection
reinforcement learning
Bayesian inference

Abstract: The presence of uncertainty in policy evaluation  significantly complicates the process of policy ranking and selection in real-world settings. We formally consider offline policy selection as learning preferences over a set of policy prospects given a fixed experience dataset. While one can select or rank policies based on point estimates of their policy values or high-confidence intervals, access to the full distribution over one's belief of the policy value enables more flexible selection algorithms under a wider range of downstream evaluation metrics. We propose BayesDICE for estimating this belief distribution in terms of posteriors of distribution correction ratios derived from stochastic constraints (as opposed to explicit likelihood, which is not available). Empirically, BayesDICE is highly competitive to existing state-of-the-art approaches in confidence interval estimation. More importantly, we show how the belief distribution estimated by BayesDICE may be used to rank policies with respect to any arbitrary downstream policy selection metric, and we empirically demonstrate that this selection procedure significantly outperforms existing approaches, such as ranking policies according to mean or high-confidence lower bound value estimates.

Under review as a conference paper at ICLR 2021
OFFLINE POLICY SELECTION UNDER UNCERTAINTY
Anonymous authors Paper under double-blind review
ABSTRACT
The presence of uncertainty in policy evaluation significantly complicates the pro- cess of policy ranking and selection in real-world settings. We formally consider offline policy selection as learning preferences over a set of policy prospects given a fixed experience dataset. While one can select or rank policies based on point estimates of their policy values or high-confidence intervals, access to the full distribution over one's belief of the policy value enables more flexible selection algorithms under a wider range of downstream evaluation metrics. We propose BayesDICE for estimating this belief distribution in terms of posteriors of distri- bution correction ratios derived from stochastic constraints (as opposed to explicit likelihood, which is not available). Empirically, BayesDICE is highly competitive to existing state-of-the-ar art approaches in confidence interval estimation. More im- portantly, we show how the belief distribution estimated by BayesDICE may be used to rank policies with respect to any arbitrary downstream policy selection metric, and we empirically demonstrate that this selection procedure significantly outperforms existing approaches, such as ranking policies according to mean or high-confidence lower bound value estimates.
INTRODUCTION
Off-policy evaluation (OPE) (Precup al., 2000) in the context of reinforcement learning (RL) is often motivated as a way to mitigate risk in practical applications where deploying a policy might incur significant cost or safety concerns (Thomas et al. 2015a). Indeed, by providing methods to estimate the value of a target policy solely from a static offine dataset of logged experience in the environment, OPE can help practitioners determine whether a target policy or is not safe and worthwhile to deploy. Still, in many practical applications the ability to accurately estimate the online value of a specific policy is less of a concern than the ability to select or rank a set of policies (one of which may be the currently deployed policy). This problem, related to but subtly different from OPE, is offline policy selection (Doroudi et al., 2017 Paine et al., 2020 Kuzborskij et al.) 2020), and it often arises in practice. For example, in recommendation sy systems, practitioner may have a large number of policies trained offline using various hyperparameters, while cost and safety constraints only allow a few of those policies to be deployed as live experiments. Which policies should be chosen to form the small subset that will be evaluated online?
This and similar questions are closely related to OPE, and indeed, the original motivations for OPE were arguably with offline policy selection in mind (Precup et al., 2000 Diang] 2017). the idea being rank and then select from this set.
that one can use estimates of the value of a of policies
Accordingly, there is rich literature of approaches for computing point estimates of the value of
the policy (Dudik et al. 2011 BBttouu et al. 2013 Diang & Li, 2013) Thomas & Brunskill 2016
Nachum et al.) 2019; Zhang et al.) [0200] Uehara & Jiang 2020; Kallus & Uehara 20200 Yang 2020). Because the offline dataset is finite and collected under a logging policy that may be different from the target policy, prior OPE methods also estimate high-confidence lower and upper
bounds on a target policy's 's value (Thomas et al. [2015a] Kuzborskij et al. 2020 Bottou et al. 2013) Hanna et al., 2016; Feng et al. 2020, Dai et al. 2020; Kostrikov & Nachum, 2020). These existing approaches may be readily applied to our recommendation systems example, by using either mean or lower-confidence bound estimates on each candidate policy to rank the set and picking the top few to deploy online.
However, this naïve approach ignores crucial differences between the problem setting of OPE and the downstream evaluation criteria a practitioner prioritizes. For example, when choosing a few policies out of large number of available policies, a recommendation systems practitioner may

---

Under review as a conference paper at ICLR 2021
have number of objectives in mind: The practitioner may strive to ensure that the policy with the overall highest groundtruth value is within the small subset of selected policies (akin to top-k precision). Or, in scenarios where the practitioner is sensitive to large differences in achieved value, a more relevant downstream metric may be the difference between the largest groundtruth value within the l selected policies compared to the groundtruth of the best possible policy overall (akin to top-k regret). With these or other potential offline policy selection metrics, it is far from obvious that ranking according OPE estimates is ideal (Doroudi et al., 2017).
The diversity of potential downstream metrics in offtine policy selection presents challenge to any algorithm that yields a point estimate for each policy. Any one approach computing point estimates will necessarily be sub-optimal for some policy selection criteria. To circumvent this challenge, we propose to compute a belief distribution over groundtruth values for each policy. Specifically, with the posteriors for the distribution over value for each policy calculated, one can use straightforward procedure that takes estimation uncertainty into account to rank the policy candidates according to arbitrarily complicated downstream metrics. While this belief distribution approach to offline policy selection is attractive, it also presents its own challenge: how should one estimate distribution over a policy's ' value in the pure offline setting?
In this work, we propose Bayesian Distribution Correction Estimation (BayesDICE) for off off-policy estimation of belief distribution over policy's ss value. BayesDICE works by estimating posteri- ors over correction ratios for each state-action pair (correcting for the distribution shift between the off-policy data and the target policy's s on-policy distribution). A belief distribution of the policy's s value may then be estimated by averaging these correction distributions over the offline dataset, weighted by rewards. In this way, BayesDiCE builds on top of the state-of-the-art DICE point esti- mators (Nachum et al. 2019 Zhang et al. 2020; Yang et al. 2020), while uniquely leveraging pos- terior regularization to satisfy chance constraints in Markov decision process (MDP). As prelim- inary experiment, we show that BayesDICE is highly competitive to existing frequentist approaches when applied to confidence interval estimation. More importantly, we demonstrate BayesDICE's application in offlin policy selection under different utility measures on variety of discrete and continuous RL tasks. Among other findings, our policy selection experiments suggest that, while the conventional wisdom focuses on using lower bound estimates to select policies (due to safety con- cerns) (Kuzborskij et al. 2020), policy ranking based on the lower bound estimates does not always lead to lower (top-k) regret. Furthermore, when other metrics of policy selection are considered, such as top-k precision, being able to sample from the posterior enables significantly better policy selection than only having access the mean or confidence bounds of the estimated policy values.
PRELIMINARIES
We consider (S, A, R. T, Mo. 7), which consists of a state space, an action space, a deterministic reward function! transition probability function, initial state distribution, and discount factor y (0, 1]. In this setting, a policy ((ar(s)) interacts with the environment starting at 80 ~ 140 and receives a scalar reward rs R(st, 0z) as the environment transitions into new state 8141 T(st, at each timestep f. The value of a policy is defined as
-orrite- Markov decision process (MDP) (Puterman 1994) denoted as M
p (T) = (1 7) E. Eo..r.. Ee
2.1 OFFLINE POLICY SELECTION We formalize the offline policy selection problem as providing a ranking O E Permm(11 N)) over a set of candidate policies ( given only fixed dataset D =
{x(0) ={x0) ==
(a()), ,,0)), alt), ((1)),()))_) ,()),,(()))? s'0)) where sg Po- (s(3), ali)) d are samples of an unknown distribution dD, ,(()== = R(s()), d()), and g'O) T(s(i) at)) B One approach to the offline policy selection problem to first characterize the value of each policy [Fq. also known as the normal-
ized per-step reward) via OPE under some utility function u(T)) that leverages point estimate (or
For simplicity, we restrict our analysis to deterministic rewards, and extending our methods to stochastic reward scenarios is straightfforwrrd
"This tuple-based representation of the dataset is for notational and theoretical convenience, following Dai et al. (2020): Kostrikov & Nachum 2202)), among others. In practice, the dataset is usually presented as finite- lenth trajectories {[0]] (3)) ,, 81 ,... ,....))"= >) and this can be processed into a dataset of finite samples from Ho and from d x T. For mathematical simplicity, we assume that the dataset is sampled i..dd This
2

---

Under review as a conference paper at ICLR 2021
lower bound) of the policy value; ie.,
O t ArggoorDescondinn((((tr)
2.2 SELECTION EVALUATION
A proposed ranking O will eventually be evaluated according to how well its policy ordering aligns with the policies' groundtruth values. In this section, we elaborate on potential forms of this evalu- ation score.
To this end, let us denote the groundtruth distribution of returns of policy m, by Z(-lm.). In other words, (-- is a distribution over IR such that
R(s;, so ~ po: ar ~ (T(ss), S141 ~ T(s an)
~~ Z(11m.) = 2 = (1 (1-7)
(2)
t=
Note that Ez(-
[2] = p.T.).
As part of the offline policy selection problem, given ranking score S that is function of a proposed ranking and groundtruth policy statistics on many forms and is application specific; e.g.,
The ranking score S can take
top-k precision: This is an ordinal ranking score. The ranking score considers the top & policies in terms of groundtruth means p(TT.) and returns the proportion of these which appear in the top k spots of O.
top-k accuracy: Another ordinal ranking score, this score considers the top-k policies in sorted order in terms of groundtruth means p(z,, and returns the proportion of these which appear in the same ordinal location in O.
top-k correlation: Another ordinal ranking score, this represents the Pearson correlation coeffi- cient between the ranking of top-k policies in sorted order in terms of groundtruth means p(TT,) and the truly best top-k policies.
top-k regret: This is cardinal ranking score. This score respresents the difference in groundtruth means p(T;) between the overall best policy i.e. max; p(m,)) and the best policy among the top-k ranked policies - i.e., [a.] ((TTO))))
Beyond expected return: One may define the above ranking scores in terms of statistics of 7-)m)) other than the groundtruth means p(T,)). For example, in safety-critical applications, one may be concerned with the variance of the policy return. Accordingly, one may define CVaR analogues top-k precision and regret.
For simplicity, will restrict our attention ranking scores which only depend the average return of n; To this end, we will use P; as shorthand for p(T;)) and assume that the ranking score S is function of O and {p,1 N.
2.3 RANKING SCORE SIMULATION FROM THE POSTERIOR
It is not clear whether ranking according vanilla OPE (either mean or confidence based) is ideal for any of the ranking scores above, including, for example, top-1 regret in the presence of uncer- tainty. However, if one has access an approximate belief distribution over the policy's values, there is a simple cumpling-based approach that can be used to find a near-optimal ranking (opti- mality depending on how accurate the belief distribution is) with respect to an arbitrary specified downstream ranking score, and we elaborate on this procedure here.
First, note that if we have access to the true groundtruth policy values (p. and the ranking score function S, can calculate the score value of any ranking O and find the ranking O' that optimizes this score. However, we are limited to a finite offline dataset and the full return distributions are unknown. In this offline setting, we propose instead compute belief distribution then we can optimize over the expected ranking score E. |S(O, (p.)aa) This algorithm simulates realizations of the groundtruth values { by sampling from the belief distribution ((7,)) (N and in this way estimates the expected realized ranking score S over all
.). and shown in Algorithm] i
common assumption in the OPE literature (Uchara & Jiang 2020 and may be relaxed in some cases by assuming fast mixing time (achumm al. 2019).
3

---

Under review as a conference paper at ICLR 2021
possible rankings O As we will show empirically, matching the selection process (the S used in Algorithm M to the downstream ranking score naturally leads to improved performance. The question now becomes how to effectively learn belief distribution over {p,
Algorithm 1 OfffineSelect
1
22
Inputs Posteriors q ((tr ke ranking score & Initialize O" L'* > Track best score
BayesDICE
SfllineSelect
for O in (er,
do
0
D
A
22
L=
for j = 1 to do sample (p
J li=1 ((p))
Figure I: The belief distributions of 7j and 72 de- pend on the uncertainty induced from the finite of- fline data (D and D)). A user might prefer IT only p(22 < P1) < E (a choice of S). OPE based on mean point estimates would select T2 in either case as P1 has the greater mean. Sampling from the posterior belief in Offl nnSell ect allows simulation of any ranking score under S, aligning policy selection with the user's choice of S.
Sum up sample scores
L S(P) I end for if L. I then
>> Update best ranking/score L = 0
end if end for return O" T,"
BAYESDICE
To learn belief distribution over (p,) pursue Bayesian approach to infer approx- imate posterior distribution given prior beliefs. While model-based Bayesian approaches exist (e.g.. (Deisenroth & Rasmussen 2011) and variants (Parmas al., 2018)), they typically suffer from compounding error, so a model-free approach is preferable. However, Bayesian inference is challenging in this model-free scenario because the likelihood function is not easy compute, is defined over infinite horizon returns.
Therefore, we first investigate several approaches representing policy value, before identifying novel posterior estimator that is computationally attractive and can support a broad range of ranking scores for downstream tasks.
3.1 POLICY RANKING SCORE REPRESENTATION
practice, the downstream task of ranking or selecting policy candidates might require more than the value expectation, but also other properties of the policy value distribution. To ensure that the necessary distribution properties are computable, we first consider the class of ranking scores we would like to support:
Offline: Since we focus on ranking policies given only offline data, the ranking score should not depend on-policy samples.
Flexible: Since the downstream task may utilize different ranking scores, the representation of the policy value should be sufficient to support their efficient computation.
With these considerations mind, we review ways to represent the value of a policy æ. Define Q (s, a) = E | 7 R( az) ds) s, ao a] and d= (s, (1 E d (s,a), with di (s) P s, alsu no, Vi < <t,a, (-1s:) , 8:+1 T (- a:)), which are the state-action values and stationary visitations of æ. These satisfy the recursions (s R(s,a) + P'Q" where pd P")(ssa) == E d (8. (1 (1)-))0())(((ap) + P..d' (s, where PT = =(as)) Σ.. T(* a).
,a'));
(3)
(4)
From these identities, the policy value be expressed in equivalent ways:
p(T)- = (1-7)- B (so, ao)]
(5)
30~140
(a. [r(s,a)].
(6)
4

---

Under review as a conference paper at ICLR 2021
Current OPE methods generally based one of the representations (1. (5) (6)
For example,
importance sampling (IS) estimators (Precup et al. 2000, Murphy et al. 2001 Dudik et al. 2
are based on ① LSTDQ (Lagoudakis & Parr 2003 18 representative algorithm for hittngg C? and
thus based on (5) the recent DICE algorithms (Nachum & Dai 2020 Yang et al. 2020) estimate the stationary density ratio < (s, a) ;- (=
d so that p (T) Egp [s rj. and are thus based on (6)
Among the three strategies, the third the most promising in our scenario. First, IS suffers from an exponential growth in variance (Liu et al. (0188) and further requires knowledge of the behavior policy. In contrast, the functions Q" and d' are duals (Nachum & Dail [020 Yang et al. 2020), and share common behavior-agnostic and minimax properties (Uchara & Jiang 2020), However, estimation of Q" assumes a ranking score with a linear dependence on [s, a), and therefore, even if we estimate Q" accurately, it is still impossible to evaluate ranking scores that involve (1 7) E (- - (r,)) such that a(-) R + IR is a nonlinear function (unless one learns a different Q function for each possible ranking score, which may be computationally expensive). By contrast, ranking scores with such nonlinear components can be easily computed from the stationary density ratio as Eg |< (r)]. Given these considerations, the estimator via stationary density ratio satisfies both requirements: it enjoys statistical advantages in the offline setting and is flexible for downstream ranking score calculation. Therefore, we focus on Bayesian estimator for (* next.
3.2 STATIONARY RATIO POSTERIOR ESTIMATION
Recall that to apply simple Bayesian approach to infer the posterior of (", one requires log- likelihood function, but such a quantity not readily calculable in our scenario from the given data. Therefore, we develop an alternative, computationally tractable approach by considering an optimization view of Bayesian inference under a chance constraint, which allows us to derive the posterior over set of stochastic equations.
Let f (-) denote a non-negative convex function with f(0) achieving the minimum 0, e.g., f(z) = x TT.. Also let Aa (s, a) == (1 - ()) + 7 PP. d(s, a) d (s, a). Starting with (5) reduce the |S] |A| many constraints for the stationary distribution of π to a single feature-vector-
based constraint for Ç:
Aa (s, a) = 0, ((s,a) E S A Ad) =0
((0,, Aa)) = 0 max 3 (o. fr (6)=0 =
(8)
BEHO
max EN (s, 3T (r0(5', ,') ò (s)))) + (1-7) Epp f BEH,
(B) ( 0,(9)
where Ho denotes the bounded Hilbert space with the feature mappings Φb dd denotes the distribu- tion generating the empirical experience, and we have used Fenchel duality in the middle step. The function d (..-)
+ RT is feature mapping, with mn possibly infinite. Then the condition (sb, A2) = 0 can be understood as matching the two distributions (1 (1-7)/o (s)=(((s)) P7. a) and d' d(s, a) in terms of their embeddings (Smola et al. 2007). which is a generalization of the ap- proximation methods in (De Farias & Van Roy| 2003 Lakshminarayanan et al.) 2017). In particular, when [S] ||| is finite and we set Φ(s, a) 8 8,.0, where òz.a E {0. 1) ISSII an indicator vector with a single 1 at position (s, a) and O otherwise, we are matching the distributions pointwise. The feature map (s.a) a) can also be set to general reproducing kernel & ((s, .), E RR As long as the kernel & (+, -) is characteristic, the embeddings will match if and only if the distributions are identical almost surely (Sriperumbudur et al. 2011].
Given that the experience was collected by some other means, i.e., D ~ dD, the constraint for in 7 might not hold exactly. Therefore, we consider a feasible set < E {5 : e (C, < c} where
(C, == max ED [ (x+ a) :T (70(5', - & (s, - f (8)] + (1 - 7) Eng [BT
(10)
Note that é (() > 0 since H.g is symmetric. We expect the posterior of (, q (C). to concentrate most of its mass on this set and balance the prior. Formally, this means
min KL (gllp) - XE, s.t. Pg (C) < E.
(11)
where the chance constraint considers the probability of the feasibility of ( under the posterior. This formulation can be equivalently rewritten as min KL (gllp) XI, (C) <c)
(12)
4
5

---

Under review as a conference paper at ICLR 2021
Then, by applying Markov's inequality, L.e., P. (e(() < <c)= 10 P1,P, (e can obtain an upper bound on 12 as
=)>1- 3x((()
min KL (qllp) + 2 [(()
(13)
min max KL (gllp) <(C) ((1()
E Eatcintti)) ED [s (s.a). 38T -(()))) (8)
(1 7) R Ag ( []
(14)
where the equality follows by interchangeability Shapiro et al. 2014 Dai et al. 2017). We amortize
the optimization for 3 w.r.t each to a distribution q (5(() reduce the computational effort.
Due to the space limitation, we postpone the discussion about the important properties of Bayes- DICE, including the parametrization of the posteriors, the variants of BayesDICE for undiscounted MDP and alternatives of the log-liielhhoods, and the connections to the vanilla Bayesian stochastic processes, Appendix A Please refer the details there.
Finally, note that with the posterior approximation for Ç. denoting the estimate for candidate policy i, we can draw posterior samples of p; by drawing sample Si g(C;) and computing P: A E(s.aa)eDD (i(s, a)r. This defines a posterior distribution over P; and we further assume that the distributions are independent for each policy, so q( {(( II: g(p;). This defines the necessary inputs for Of SefflinnSeeeen lect to determine a ranking of the candidate policies.
RELATED WORK
We categorize the relevant related work into three categories: offline policy selection, off-policy evaluation, and Bayesian inference for policy evaluation.
Offiine policy selection The decision making problem we formalize as offline policy selection is member of set of problems in RL referred to model selection. Previously, this term has been used to refer to state abstraction selection | 2017] et al., (015) as well as learning algorithm and feature selection (Foster al. 2019 Pacchiano al. (020). More relevant to our proposed notion of policy selection are a number of previous works which use model selection to refer to the problem of choosing near-optimal Q-function from set of candidate approximation
functions (Fard& & Pineaul 2010; Farahmand & Szepesvári 2011 Irpan et al. 2019 Xie & Jiang 2020). In this case, the evaluation metric is typically defined as the Lo norm of difference of Q versus the state-action value function of the optimal policy Q". While one can relate this evaluation metric to the sub-optimality (i.e.. regret) of the policy induced by the Q-function, we argue that our proposed policy selection problem is both more general since we allow for the use of policy evaluation metrics other than sub-optimality- - and more practically relevant since in many practical applications, the policy may not be expressible policy selection problem we describe is arguably a formalization of the problem approached in Paine et al. (2020) and referred to hyperparameter selection. In contrast to this previous work, not only formalize the decision problem, but also propose a method to directly optimize the policy selection evaluation metric. Offfine policy selection has also been studied by Doroudi et al.) (2017), which considers what properties point estimator should have in order for it to yield good rankings in terms of a notion of ranking score referred as fairness.
the argmax of Qufunctio.. Lastly, the offline
Off-policy evaluation Off-policy evaluation (OPE) is a highly active area of research. While the original motivation for OPE was in the pursuit of policy selection (Precup et al., 2000: Jiang 2017]. the field has historically almost exclusively focused on the related but distinct problem of estimating the online value (accumulated rewards) of a single target policy. In addition to plethora of techniques for providing point estimates of this groundtruth value (Dudík et al. 2011: Bottou et al. 3013,Jiang & Li| 2015] TTomms & Brunskill 2016 Kallus & Ueharal 2020) Nachum et al. Zhang et al., 2020 Yang et al., 2020), there is also a growing body of literature that uses frequentist principles to derive high-confidence lower bounds for the value of policy (Bottou al.)
2019
2013
Thomas et al. 2015b] Hanna et al. 2016 Kuzborskij et al. 2020) Feng et al. 2020; Dai et al.
2020
Kostrikov & Nachum 2020). As our results demonstrate, ranking or selecting policies based
on either their estimated mean or lower confidence bounds can at times be sub-optimal, depending on the evaluation criteria.

---

Under review as a conference paper at ICLR 2021
Bayesian inference for policy evaluation Our proposed method for policy selection relies on Bayesian principles to estimate a posterior distribution over the groundtruth policy value. While many doyesian-inspired methods have been proposed for policy optimization (Deisenroth & Ras- mussen, 2011 Parmas et al. 2018), especially in the context of exploration (Houthooft et 2016) Dearden al. 2013| Kolter & Ng. 2009), relatively few have been proposed for policy evaluation. In one instance, Fard & Pineaul (2010) derive PAC-Bayesian bounds on estimates of the Bellman error of a candidate Q-value function. In contrast to this work, we use our BayesDICE algorithm to estimate a distribution over target policy value, and this distribution allows us to directly optimize arbitrary downstream policy selection metrics.
5 EXPERIMENTS
We empirically evaluate the performance of BayesDICE on confidence interval estimation (which can be used for policy selection) and offline policy selection under linear and neural network pos- terior parametrizations on tabular- Bandit, Taxi (Dietterich) 1998), FrozenLake (Brockman et al.) 2016 and continuous-control - Reacher (Brockman et al. 2016) tasks. As we show below, Bayc outperforms existing methods for confidence interval estimation, producing accurate coverage while maintaining tight interval width, suggesting that BayesDICE achieves accurate pos- terior estimation, being, robust to approximation errors and potentially misaligned Bayesian priors in practice. Moreover, in offlin policy selection settings, matching the selection algorithm (Algo- rithm D to the ranking score (enabled by the estimating the posterior) shows clear advantages over ranking based on point estimates or confidence intervals on variety of ranking scores. See Ap- pendix C for additional results and implementation details.
5.1 CONFIDENCE INTERVAL ESTIMATION
Before applying BayesDICE to policy selection, we evaluate the BayesDICE approximate posterior by computing the accuracy of the confidence intervals it produces. We compare BayesDICE against a known set of confidence interval estimators based on concentration inequalities. To compute these baselines. we first weighted (i.e., celf-normalized) per-step importance sampling (Thomas & Brunskill 2016) to compute a policy value estimate for each logged trajectory. These trajectories provide finite sample of value estimates. We use self-normalized importance sampling since it has been found to yield better empirical results in MDPs despite being biased (Liu et al. 2018 Nachum et al. 2 ; for Bandit results without self- seff-normalization, see Figure 5n Appendix We then empirical Bernstein's 's inequality TTomas et al., 2015b), bias-corrected bootstrap Thomas et al.) 2015a), and Student's 's I-fest derive lower and upper high-confidence bounds on these estimates.
We further consider Bayesian Deep N-Netwrrks (BDQN) (Azizzadenesheli et al. 2018) with an average empirical reward prior in the function approximation setting, which applies Bayesian linear learn distribution of Q-values. Both BayesDICE. and BDQN output a distribution of parameters, from which we conduct Monte Carlo sampling and use the resulting samples to compute confidence interval at a given confidence level.
regression to the last layer of deep Q-network to
We plot the empirical coverage and interval width at different confidence levels in Figure To compute the empirical interval coverage, we conduct 200 trials with randomly sampled datasets. The interval coverage is the proportion of the 200 intervals that contains the true value of the target policy. The interval log- log-width is the median of the log width of the 200 intervals. As shown in Figure 2] BayesDICE's coverage closely follows the intended coverage (black dotted line), while maintaining narrow interval width across all tasks considered. This suggests that BayesDICE's pos- terior estimation is highly accurate, being robust to approximation errors and potentially misaligned Bayesian priors in practice.
5.2 POLICY SELECTION
Next, we demonstrate the benefit of matching the policy selection criteria to the ranking score in offline policy selection. Our evaluation is based on a variety of cardinal and ordinal ranking scores defined in Section 2.2] We begin by considering the use of Algorithm [ with BayesDICE- approximated posteriors. By keeping the BayesDICE posterior fixed, we focus our evaluation on the
performance of Algorithm| We plot the groundtruth performance of this procedure applied to Ban-
dit and Reacher in Figure 3 These figures compare using different S to rank the policies according
to Algorithm| 1 across different downstream ranking scores S. We find that aligning the criteria $ used in Algorithm with the downstream ranking score S is empirically the best approach ($ S).
7

---

Under review as a conference paper at ICLR 2021
BEgq
Bandt sumple
Froventake
Taxt
Reacher trjectoriss
cmmplea
samples - 200
oegectatess
tigectates
Vingenices
Ingeetories
Irievval ing-evdm interval covergge
4
d0
Confieeree meroel
Figure 2: Confidence interval estimation on Bandit, FrozenLake, Taxi, and Reacher. The g-axis shows the empirical coverage and median log-interval width across 200 trials. BayesDICE exhibits near coverage while maintaining narrow interval width, suggesting an accurate posterior ap- proximation.
In contrast, using point estimates such Mean Mean + Std can yield much worse down- stream performance. We also see that in the Bandit setting, where we can analytically compute the Bayes-optimal ranking, using aligned ranking scores in conjunction with BayesDiCE-approximate posteriors achieves near-optimal performance.
Banlii Phobben Top3
Reacher
E- Tup2
Hond Top
Genduan Top-
0,07
8 Trokk
TruR
Tru
130
Figure 3: Policy selection using top-k ranking scores compared to mean/confidence ranking ap- proaches two-armed Bandit and Reacher. In these experiments, fix the posterior the one approximated by BayesDICE and evaluate different Š used in Algorithm to compute policy ranking. We find that using S S (i.e., aligning the ranking score in posterior simulation with the groundtruth evaluation) results in better performance than simple point estimates. Interestingly, the lower-bound point estimate almost always performs worse than the mean or the upper bound.
Having established BayesDICE's ability to compute accurate posterior distributions as well as the benefit of appropriately aligning the ranking score used in Algorithm T we compare BayesDICE to oftte-of-the-ar OPE methods in policy selection. In these experiments, we use Algorithm with posteriors approximated by BayesDICE and S = S. We compare the use of BayesDICE. in this way to ranking via point estimates of DualDICE (Nachum et al. 2019) and other confidence-interval estimation methods introduced in Section We present results in Figure in terms of top-k regret and correlation on bandit and reacher across different sample sizes and behavior data. BayesDICE outperforms other methods on both tasks. See additional ranking results in Appendix
feal 12
Cormassion Tapo
Commicts Eopd
2.13
0/7
00
-05
122
120
10
25
100
Figure 4: Policy selection evaluation under correlation and regret at top-k in two-armed Bandit (left) and Reacher (right) compared other methods using point estimate (DualDICE) or high-confidence lower bounds. Please see Appendix C for more results with respect to other downstream metrics.
CONCLUSION
In this paper, we formally defined the offline policy selection problem, and proposed BayesDICE to first estimate posterior distributions of policy values before using simulation-base procedure
8

---

Under review as a conference paper at ICLR 2021
to compute optimal policy ranking. Empirically, BayesDICE not only provides accurate belief distribution estimation, but also shows excellent performance in policy selection tasks.
REFERENCES
Kamyar Azizzadenesheli, Emma Branskill, and Animashree Anandkumar. Efficient exploration through bayesian deep g-networks. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-9. IEEE, 2018.
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization. Princeton Uni- versity Press, 2009.
Léon Bottou, Jonas Peters, Joaquin Quiñooner- Candela,, Denis Charles, D. Max Chickering, Elon Portugaly. Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14 (65):3207-3260, 2013. URL http::/jmlrr.aa http::/jmlr..rg/pappeeeee wgg/papers//14//ottuu 3t.html.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym. arXiv preprint arXiv:
2016.
Bo Dai, Niao He, Hanjun Dai, and Le Song. Provable bayesian inference via particle mirror descent. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pp. 985-994, 2016.
Bo Dai, Niao He, Yunpeng Pan, Byron Boots, and Le Song. Learning from conditional distributions via dual embeddings. Artificial Intelligence and Statistics, pp. 1458-1467, 2017.
Bo Dai, Ofir Nachum, Yinlam Chow, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Coindice: Off-policy confidence interval estimation. In Advances in Neural Information Processing Systems, 2020.
Daniela Pucci De Farias and Benjamin Van Roy. The linear programming approach approximate dynamic programming. Operations research, (1)) 2003.
Richard Dearden, Nir Friedman, and David Andre. Model-based bayesian exploration. arXiv preprint 1301.. .6690, 2013.
Mare Deisenroth and Carl E Rasmussen. Pilco: A model-based and data-efficiem approach to policy search. In Proceedings of the 28th International Conference on machine learning (ICML-11), pp- 465-472, 2011.
Thomas G Dietterich. The maxq method for hierarchical reinforcement learning. In ICML,, vol- ume 98, pp. 118-126. Citeseer, 1998.
Shayan Doroudi, Philip Thomas, and Emma Brunskill. Importance sampling for fair policy selec- tion. Grantee Submission, 2017.
Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. arXiv preprint arXiv: 103.100444.001 2011.
Yaakov Engel. Shie Mannor, and Ron Meir. Bayes meets bellman: The gaussian process approach to temporal difference learning. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 154-161, 2003.
Amir-massout Farahmand and Csaba Szepesvári. Model selection in reinforcement learning. Ma- chine learning. 85(3):299-332, 2011.
Mahdi M Fard and Joelle Pineau. Pac-hayesian model selection for reinforcement learning. In Advances in Neural Information Processing Systems, pp. 1624-1632, 2010.
Yihao Feng, Tongzheng Ren, Ziyang Tang, and Qiang Liu. Accountable off oollcy evaluation with kernel bellman statistics. arXiv preprint arXiv:2008.0666 2020.

---

Under review as a conference paper at ICLR 2021
Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. In Advances Neural Information Processing Systems, pp. 14741-14752, 2019.
Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, and Aviv Tamar. Bayesian reinforcement learning: A survey. arXiv preprint (1t9.v660904444 2016.
Josiah P Hanna, Peter Stone, and Scott Nickum. Bootstrapping with models: Confidence intervals for off-policy evaluation. arXiv preprint arXiv:1606.06122 06/26, 2016.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Vime: Variational information maximizing exploration. In Advances in Neural Information Processing Systems, pp. 1109-1117, 2016.
Alexander Irpan, Kanishka Rao, Konstantinos Bousmalis, Chris Harris, Julian Ibarz, and Sergey Levine. Off- Off-policy evaluation via off off-polliy classification. In Advances in Neural Information Processing Systems, pp. 5437-5448, 2019.
Nan Jiang. A Theory of Model Selection in Reinforcement Learning. PhD thesis, 2017.
Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. arXiv preprint 1511v375 2015.
Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model-based reinforcement learning. In International Conference Machine Learning, pp. 179-188, 2015.
Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off- off-policy evalu- ation in markov decision processes. Journal of Machine Learning Research, 21(167):1-63, 2020.
J Zico Kolter and Andrew Y Ng. Near-bayesian exploration in polynomial time. In Proceedings of the 26th annual international conference on machine learning, pp. 513-520, 2009.
lyya Kostrikov and Ofir Nachum. Statistical bootstrapping for uncertainty estimation in off off-policy evaluation, 2020.
Ilja Kuzborskij. Claire Vernade, András György, and Csaba Szepesvári. Confident off-policy arXiv preprint
evaluation and selection through self-normalized importance weighting.
arXiv:2006. 2020.
Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of machine learning research, ((DDec):117-1149) 2003.
Chandrashekar Lakshminarayanan, Shalabh Bhatnagar, and Csaba Szepesvári. A linearly relaxed approximate linear program for markov decision processes. CoRR, 1101110044444444 2017.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. In Advances in Neural Information Processing Systems, pp. 5356- 5366, 2018
S. Murphy, M. van der Laan, and J. Robins. Marginal mean models for dynamic regimes. Journal of American Statistical Association, 96(456) 2001.
Ofr Nachum and Bo Dai. Reinforcement learning via renchel- duality. arXiv preprint arXiv:2001.01866 2020.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. DualDICE: Bchavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Newral Information Processing Systems, pp. 2315-2325, 2019.
Arkadi Nemirovski and Alexander Shapiro. Convex approximations of chance constrained pro- grams. SIAM Journal on Optimization, 17(4) 2007.
Brendan ODonoghue, Ian Osband, Remi Munos, and Volodymyr Mnih. The uncertainty bellman equation and exploration. In International Conference on Machine Learning, pp. 3836-3845, 2018.
10

---

Under review as a conference paper at ICLR 2021
Ian Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1 62, 2019.
Aldo Pacchiano, My Phan, Yasin Yadkor,, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. arXiv preprint arXiv:2003.01704, 2020.
Tom Le Paine, Cosmin Paduraru, Andrea Michi, Caglar Gulcehre, Konrad Zolna, Alexander Novikov, Ziyu Wang, and Nando de Freitas. Hyperparameter selection for offline reinforcement learning. arXiv preprint vrXiv:2007.090533 2020.
Paavo Parmas, Carl Edward Rasmussen, Jan Peters, and Kenji Doya. Pipps: Flexible model-based policy search robust to the curse of chaos. In International Conference on Machine Learning, pp- 4065 4074. PMLR, 2018.
Doina Precup, Richard S. Sutton, and Satinder Singh. Eligibility traces for off-policy policy evaluation. In Proceedings of the 17th International Conference on Machine Learning, pp. 759- 766, 2000.
Martin I. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Progrumming. John Wiley & Sons, Inc., 1994.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyúski. Lectures stochastic program- ming: modeling and theory. SIAM, 2014.
Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory. pp. 13-31. Springer, 2007.
Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet. Universality, characteristic kernels and rkhs embedding of measures. Journal of Machine Learning Research, 12(7), 2011.
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference Machine Learning, pp. 2139-21444 2016.
Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High confidence policy improvement. In International Conference on Machine Learning, pp. 2380-2388, 2015a.
Philip S Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off- policy evaluation. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015b.
Masatoshi Uehara and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. 2020.
Tengyang Xie and Nan Jiang. Batch falue-function approximation with only realizability, 2020.
Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-policy evaluation via the regularized lagrangian. In Advances in Neural Information Processing Systems, 2020.
Arnold Zellner. Optimal Information Processing and Bayes's Theorem. The American Statistician, 42(4), November 1988.
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. GenDICE: Generalized offline estimation of stationary values. In International Conference on Learning Representations, 2020.
Jun Zhu, Ning Chen, and Eric P. Xing. Bayesian inference with posterior regularization and ap- plications to infinite latent syms. J. Mach. Learn. Res., 15(1):1799 (7()):179-1188 1847, January 2014. ISSN 1532-4435.
11

---

Appendix
consider the A MORE DISCUSSIONS ON BAYESDICE
In this section, we provide more details about BayesDICE.
q (C) and q (B(c)): We parametrize both & (C) (and the result- ing (8(() Gaussians with the mean and variance approximated by multi-layer perceptron (MLP), i.e.: Ç = (s, a) + SwrS: & &~ (0,, 1). w and w' denote the parameters of the MLP.
Remark (parametrization
Remark (connection to Bayesian inference for stochastic processes): Recall the posterior can be viewed as the solution to an optimization (Zellner 1988 Zhu al., 2014 Dai al. 2016).
DD = argmin gEP
(q (C), log (5. D)) KL (q (C) (()
The (13) is equivalent to define the log- ligeliie proportion (Ç, D). which is stochastic pro- cess, including Gaussian process (GP) by setting f (3) = 1/8T 3. Specifically, plug f (8) = 2 B
back into (33), we have 8 = ED iS (s) (vo(s',a') o (s) (1 7) Euo [o]. resulting the optimization
min KL (qllp) + Å E [s (1) lo (($1, 01 (1. (52, ag 2/2 a2)) ( (52, 02) (15)
with the kernel 22) = (r0(5), a1) - (81, (7011/2 db) (82, (2)) + (32, 02)), which is
(1 (1- & (s), o (s/, at) + 2(1 (5f, (sf.aa) at) (10(522,
GP. Obviously, with different choices of (*)()) (.), the BayesDICE framework far beyond GP.
Although the GP has been applied for RL (Engel et al. 2003 Ghavamzadeh al. 2016 Aziz- zadenesheli et al.) 2018), they all focus on prior on value function; while BayesDICE considers general stochastic processes likelihood, including GP, for the stationary ratio modeling, which as we justified is more flexible for different selection criteria in downstream tasks.
Remark (auxilary constraints and undiscounted MDP): As Yang et al. (2020) suggested, the non-negative and normalization constraints are important for optimization. We exploit positive neu- to ensure the non-negativity of the mean of the (C). For the normalization,
E1. By applying the same technique, it leads to chance constraints IP (())(5) - < E1
extra term Ao Eg max.ER ED IS 11 in
With the normalization condition introduced, the proposed BayesDICE is ready for undiscounted MDP by simply setting 7 1 in (13) together with the above extra term for normalization.
Remark (variants of log- ligeelihhhhh:::: We apply the Markov's inequality to (12) for the upper bound [3). In fact, the optimization with chance constraint has rich literature (Ben- Tal al. 2009), where plenty of surrogates can be derived with different safe approximation. For example, the q is simple, one can directly calculate the CDF for the probability P2 (f( & c): or also exploit different probability inequalities to derive other surrogates, e.g., condition value-at-risk, i.e.,
1
min KL (ally) Xinf / E. (C( -
(16)
4
and Bernstein approximation Nemirovski & Shapiro 2007p. These surrogates lead better ap- proximation to the chance probability P. (E(C) & e) with the extra cost in optimization.
B BAYESDICE FOR EXPLORATION VS. EXPLOITATION TRADEOFF
In main text, we mainly consider exploiting BayesDICE for estimating various ranking scores for both discounted MDP and undiscounted MDP. In fact, with the posterior of the stationary ratio computed, we can also apply for better balance between exploration vs. exploitation for policy optimization.
12

---

Under review as a conference paper at ICLR 2021
Instead of selecting from set of policy candidates, the policy optimization is considering all fea- sible policies and selecting optimistically. Specifically, the feasibility of the stationary state-action distribution can be characterized
dd(,,o) = (1 - 7) po Ps) as E
(17)
where (s)(s) = Ex (s) (s, a). Apply the feature mapping for distribution matching, we d(e)
obtain the constraint for Ç x with ( (s, a) (3.0a)
max 8 B BEHs
Σ ((((s,))
(S(. +(1 - Bu [8 -
-5 (3) = 0.
(18)
Then, we have the posteriors for all valid policies should satisfies
AIP, (e (C- n. D) <c
(19)
with L(s т. D) = max ED Ea (s, T (als)) (s) - (S (s) ( +
(1 - 7) Ens [8T 1" (3). Meanwhile, we will select one posterior from among these poste-
riors all valid policies optimistically, i.e.,
max (())g(m)
Bg UU [T] + A1 X2 (q (C) ( (S)
(20)
s.t. P. (4 (18-(,T, - D) E
(21)
where Eg IU (T, D)J denotes the optimistic policy score to capture the upper bound of the policy value estimation. For example, the most widely used one is
(io r] ED [T (T- -
Bgg [U (T, r, D)] EEE [T r] An
where the second term is the empirical variance and usually known as one kind of "exploration bonus".
Then the whole algorithm is iterating between solving 20 and use the obtain policy collecting data into in (20).
This Exploration-BayesDDCC BayesDICE follows the same philosophy of Osband et al. 2019); ODoogghue al. (2018) where the variance of posterior of the policy value taken into account for exploration. However, there are several significant differences: i), the first and most different is the modeling object, [Osband et al. (2019); [ODonoghue et al. (2018) is updating with Q-function, while we are handling the dual representation; ii), BayesDICE is compatible with arbitary nonlinear function et al. (2019); ODoooghue al. (2018) considers tabular or linear func- tions: iii), BayesDICE is considering infinite-horizon MDP, while Osband et al. 2019); DDoogghue et al. (2018) considers fixed finite- morte-hoiizon case. Therefore, the exploration with BayesDICE pave the path for principle and practical exploration-vs-eet esplxitoonnn algorithm. The regret bound is out of the scope of this paper, and we leave for future work.
approximator,
C EXPERIMENT DETAILS AND ADDITIONAL RESULTS
C.I ENVIRONMENTS AND POLICIES.
Bandit. We create a Bernoulli two-armed bandit with binary rewards where a controls the propor- tion of optimal arm (a 0 and means never and always choosing the optimal arm respec- tively). Our selection experiments are based on 5 target policies with a [0.75, 0.8, 0.85, 0.9, 0.95).
Reacher. We modify the Reacher task to be infinite horizon, and sample trajectories of length 100 in the behavior data. To obtain different behavior and target policies, We first train a deterministic policy from OpenAl Gym (Brockman et al.) 2016) until convergence, and define various policies by converting the optimal policy into a Gaussian policy with optimal mean with standard deviation 0.4- 0.3o. Our selection experiments are based 5 target policies with [0.75, 0.8, 0.85, 0.9. 0.95).
13

---

Under review as a conference paper at ICLR 2021
C.2 DETAILS NEURAL NETWORK IMPLEMENTATION
We parametrize the distribution correction ratio as Gaussian using deep neural network for the continuous control task. Specifically, use feed-forward networks with hidden-layers of 64 neurons each and ReLU as the activation function. The networks are trained using the Adam opti- mizer (31 0.99, 32 0.999) with batch size 2048.
C.3 ADDITIONAL EXPERIMENTAL RESULTS
BayesDICE (ours)
UN-Bernstein UN-Student
Expected coverage
UN-Bootstrapping
Bandit (no normalization) samples 100
samples 50
samples 200
Interval coverage
0.9
0.7
0.7
0.6
0.7
0.6
0.6
0.5
Interval log-width
-1.0
1.5
-1.0
1155
2.0
-1.5
2..0
-25
-20
-3.0
-2.5
-3.5
0.6
0.7
0.8
0.9
0.96
Confidence interval (1 a))
Figure 5: Confidence interval estimation Bandit where the baselines unnormalized (UN).
BIyE (ours)
Marginal Bernstein
Expected coverage
Marginal Bootstrapping
Marginal Student
Frozenlake (marginal)
Taxi (marginal)
# trajectories
50
trajectories
100
trajectories 20
trajectories 50
Interval coverage
1.0
1.0
1.0
0.5
0.5
0.4
04
0.6
02-
0.2
0.7
6,8
0.9
0.95
5.7
0.8
0.9
0.50
0.6
0.7
0.8
0.9
0.00
0.6
0.7
0.8
0.9
0.90
Interval log-width
0.9
0.5
0.6
6/7
0.8
0.6
0.66
3.7
0.8
0.0
Confidence interval (1
Figure 6: Confidence interval estimation with baselines computed from marginalized importance sampling.
14

---

Under review as a conference paper at ICLR 2021
Tog?
Carviatin
Scate Tep3
Seore Sagnet Tog3
0.6
0.8
0.23
0.5
0.02
0.3
0.0
0.01
0.7
0.09
0.5
0.0
0.1
0.53
0.5
0.4
0.4
200
Sccre
Moon
Mexnn Std
Tue Topa
Assioor Poree Top4
0.8
0.7
0.02
0.0
0.5
0.000
0.4
0.5
0.3
0.3
Trajs
TTage
Figure 7: Additional I values for top-k ranking bandit. Ranking results based Algorithm (blue lines) always perform better than using mean or high-confidence lower bound.
Scare
Maaz
Meen SM
Antkeeeniattttteeeiinleeeg Shpp
0.40
0.75
0.5
0.70
0.55
0.40
3.361
0.0125
0.6
03
100
25
20
120
25
Trye
Trage
7rays
Traje
Tipa
Scaco Atc. Togl
Scaro Cereeloaos Topl
Soure = Procaaus Styd
Sccro Begest Tepd
3.6
3.0015
0.6
3.2010
0.4
0.00
3.2005
3.5
0.00300
3.5
0.5
0.5
0.5
0.00000
0.00
0.82022
Tru
Figure 8: Additional & values for top-k ranking reacher and additional scores (precision and regret). Ranking results based on ( lines) generally perform much better than using mean high-confidence lower bound for top-k accuracy and correlation. Precision and regret similar between posterior samples and the mean/confidence bound based ranking.
15

---

Under review as a conference paper at ICLR 2021
Bandit
Estimator
Bootstrap
Bernstein
Student-l
DuaIDICE
Bayes
Score Regret Top2
Score Regret Top3
Score Regret Top4
0.008
0.015
0.006
= Seeee
0.010
0.004
0.01
0.005
0.008
0.015
0.020
0.006
0'0 Awpee
0.015
0.010
0.084
0.010
0.005
0.002
0.005
0.006
0.015
0.010
0.010
0.005
0.005
0.000
0.015
0.0100
0.0075
0.010
60 = Srrie
0.0050
0.002
0.005
0.0025
0.0000
0.000
0.004
0.010
0.006
0.003
0.0 Segii
0.005
0.004
0.002
0.002
0.001
0.000
0.008
0.006
0.003
M
0.004
0.002
0.001
0.0025
30
100
200
25
50
100
200
25
100
200
# Trajs
# Trajs
# Trajs
Figure 9: Improved regret using BayesDICE across all trajectory lengths, behavior data, and top-k values considered for the bandit task.
16

---

Under review as a conference paper at ICLR 2021
Reacher
Estimator
Bootstrap
Bernstein
Student-
DualDICE
BayesDICE
Scons Correlation Top2
Correlation Top3
Soore Correlation Top4
0.5
aloba
0.0
0.0
0.0
-0.5
-0.5
0.5
0.5
TO = Dathe
0.0
0.0
0.5
-0.5
0.5
Alpān 0.2
0.0
-0.5
-0.5
0.5
0.5
Alpha 0.3
0.0
0.5*
00.5
-1.0
0.3
Alpha 0.4
0.0
0.0
-0.5
-0.
-0.5
1..0
-1.0
-1.0
1.0
0.5
0.0
0.0
0.0
O
-0.5
00.5
-0.-
-1.01
-1.0
-1.0
10
25
100
50
100
10
100
Trais
Trajs
Trajs
Figure 10: Improved correlation using BayesDICE across all trajectory lengths, behavior data, and top-k values considered for the reacher task.
17


Reviews:
[{"review_id": "9Bmv9QjvWh", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Significance:\n- This paper studies off-policy model selection problem, which we aim to select a subset of policies based on different evaluation metric, such as top-k precision, top-k accuracy, etc. I am less convinced by the motivation of off-policy model selection, since if we want to find some policy to deploy, does off-policy learning address the problem? It would be great if the authors could give a more practical and clear motivation on this, especially compared with learning. \n\n2. Quality & Clarity:\n- This paper is clearly written and easy to read, though I feel some details in the Appendix should be move into the main paper, especially some setup for the experiments, like the number of overall policies to be evaluated, what is the f in the experiments?\n- The method is based on building posterior distribution of stationary distribution ratio, which tried to build a loss function of the Bellman residual on the average state-action visitation measure, and a KL regularization with the prior distribution. This idea is not new (see DualDice) however utilize them to learn the distribution of density ratio is novel. \n- I love the vision that when we have different evaluation metrics, we may need the whole distribution of the policy value to perform effective selection, and point estimate w. confidence interval may not be suffice in this setting. Regarding to this observation, I can see the importance/significance of this work.\n- The method does make sense to me, and the empirical evaluation is well done (though some problems listed below). Important metrics are examined, like coverage and length of interval. Also, I like the experiments that the authors examine different metrics, and show how point estimate w. confidence estimation gives sub-optimal performance, this makes the motivation much clearer, about why we need the whole posterior distribution.\n\n3. Questions:\n- Regarding to the scale of the method, do we need really to go though all permutations in Alg 1? For some structured score S, can we just use sorting? Also, i see the experiments, there is only 5 policy to select, I am concerned about the scalability of the method. Could you justify more this?\n- Just curious, any explanation about why it fails in some domain, say Taxi in Fig 2? It could be better to discuss more about when the method works, when it fails? Taxi in Fig 2 may be a good example to diagnose this?\n- In experiments, for baseline methods , the authors are using per-step IPS +/- conf level. However, I feel it is kind of unfair for baseline methods, since basically the BayesDICE are using marginalized IPS, is it possible to change the baseline estimate to marginalized IPS for a fair comparison?\n- Can you comment how you address the stochasticity in the reward?\n- Some typo, say Eq4.\n\nOverall, I like the problem it raises, that there exists some metric when a point estimate of policy value +/- conf level may not suffice to give optimal performance. The authors did a pretty good job in addressing this problem, though some problems remain and needs improvement. I am willing to improve my score if my questions are addressed. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7E7iM8RDv4", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method BayesDICE to estimate posteriors over candidate policy values, which can be used for downstream policy selection. Specifically, the authors estimate the posteriors over the correction ratios for state-action pairs, which optimize a combined metric of a chance constraint from collected data and KL from the prior. Computationally, the authors demonstrate the advantages of their approach by having better performances in both coverage and power for policy evaluation and better downstream ranking with respect to different metrics for policy selection.\n\nI think the paper is well written and has made a good investigation of their approach. It would be better if the authors can talk about how different choices of prior influence the results. Besides, for policy selection, when we have a large pool of candidates, how would this be adapted to multiple testing or how would the number of candidates influence the results. Finally, solving eq.14 needs estimation of some expectation over the state action visitation, while the data itself is not independent, how would this influence the results?\n\nsome minor comments\n- section 3.1, the first displayed equation: should it be summing from t=0 to infinity?\n- typo, appendix B, the first sentence, `\"consider exploitin\" -> exploiting ", "extra_scores": {}, "extra_text": {}}, {"review_id": "0UoDJeBJvxC", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Review\n\nGiven as set of pre-specified policies, this paper proposes a Bayesian method to estimate the posterior distribution of their average values, by estimating posterior distributions of their discounted stationary distribution ratios. These posterior distributions are used for off-policy evaluation in various ways.\n\n\n \n## Positives\n\n+ The idea focusing on estimating nonlinear functionals of multiple policy values is appealing.\n\n\n \n## Major concerns\n\n+ The results in Figure 2 are a bit surprising. We expect that methods based on concentration inequalities like Bernstein or student-t to be somewhat conservative, but the results suggest that their confidence intervals are extremely wide. For example, in the Bandit case, even after 200 samples, the interval log-width would suggest that Bernstein's confidence intervals is more than 7x the confidence intervals suggested by BayesDICE. What explains these results?\n\n+ Again on Figure 2, if \"Bernstein\" and \"Student t\" are unbiased methods, then having a very wide confidence interval should translate into over-coverage. However, they seem to be *under*-covering the true value. Are these methods somehow heavily biased? If not, what explains the under-coverage?\n\n+ The paper proposes a method for evaluating non-linear functionals of policy values, such as ranking scores over their values. However, it seems to me that in order to evaluate such nonlinear functions one would require knowledge about the *joint* distribution of values over all policies of interest. In the notation of the paper, one would require knowledge of $q(\\bar{\\rho}_1, ..., \\bar{\\rho}_N)$. However, it is not clear from the method description in Section 3.2 how one is able to estimate this joint distribution. Instead, it seems to me that all we get is $q(\\bar{\\rho}_i)$ for each policy $i$ -- that is, their marginal distributions. If that is the correct interpretation of what's going on in Section 3.2, then that raises the question of whether these distributions are independent. \n\n\n\n \n## Minor concerns\n\n+ In appendix C.1, I did not understand the description of the \"bandit\" environment. Are rewards binary?\n\n+ Several symbols are not formally defined. E.g., on page 4, (lowercase) r(s,a) is not defined.\n\n+ In Algorithm 1, what is the role of quantity L*? Why do we need it as a stopping rule?\n\n+ Some notes on exposition.\n\n  - The authors take some time to reveal what is their estimand --- the discounted stationary distribution ratios. As a reader, I would have benefited from having that explained much earlier, even before the conversation about ranking evaluation.\n\n  - Section 3.2: the authors could have dedicated some more space developing the intuition for their method (e.g. an abridged version of Nachum and Dai 2020), even if that meant relegating some of the mathematical details to the appendix. As it stands, the section makes the paper incomprehensible as a standalone piece of research.\n\n\n## Typos\n\n+ The indices on the sum in the definition of \"stationary visitation\" (p.4) are wrong. On the next line, the last conditioning should have been s[i+1] ~ T(.|s[i],a[i]) instead of s[i+1] ~ T(.|s[t],a[t]).\n+ Philip Thomas' \"High-confidence off- policy evaluation\" citation shows up twice in the bibliography.\n+ indentical --> identical (Pg. 5)", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The review team appreciated the new Bayesian perspective offered by the submission, which lends itself well to selection and ranking, though some of them were still not convinced by the motivation (including in the private post-rebuttal discussion, R3). The reviewers also identified many points for improvement. The paper was borderline and, given the lack of enthusiastic support from the reviewers, the program committee decided to reject it. We strongly encourage you to address the raised concerns and resubmit to a future venue.
Decision: Reject