Abstract Reward Processes: Leveraging State Abstraction for Consistent Off-Policy Evaluation
Authors: Shreyas Chaudhari
Ameet Deshpande
Bruno Castro da Silva
Philip S. Thomas
Venue: NeurIPS 2024 poster (2024)
Keywords: Off-Policy Evaluation
State Abstraction
Importance Sampling
Primary area: reinforcement_learning
TL;DR: Perform model-based OPE, but instead of trying to estimate a perfect model of the MDP, estimate an abstract model, customized to a policy, that preserves the performance of that policy and can be learnt from off-policy data.

Abstract: Evaluating policies using off-policy data is crucial for applying reinforcement learning to real-world problems such as healthcare and autonomous driving. Previous methods for *off-policy evaluation* (OPE) generally suffer from high variance or irreducible bias, leading to unacceptably high prediction errors. In this work, we introduce STAR, a framework for OPE that encompasses a broad range of estimators -- which include existing OPE methods as special cases -- that achieve lower mean squared prediction errors. STAR leverages state abstraction to distill complex, potentially continuous problems into compact, discrete models which we call *abstract reward processes* (ARPs). Predictions from ARPs estimated from off-policy data are provably consistent (asymptotically correct). Rather than proposing a specific estimator, we present a new framework for OPE and empirically demonstrate that estimators within STAR outperform existing methods. The best STAR estimator outperforms baselines in all twelve cases studied, and even the median STAR estimator surpasses the baselines in seven out of the twelve cases.

Abstract Reward Processes: Leveraging State Abstraction for Consistent Off-Policy Evaluation
Shreyas Chaudhari University of Massachusetts schaudhari@cs. umass. edu
Ameet Deshpande Princeton University asd0cs, prw.cctsrinncton..oom edu
Bruno Castro da Silva University of Massachusetts bsilvašcs. umass edu
Philip S. Thomas
University of Massachusetts pthomas@cs. umass. edu
Abstract
Evaluating policies using off-policy data is crucial for applying reinforcement learning real-world problems such as healthcare and autonomous driving. Previ- methods for off-policy evaluation (OPE) generally suffer from high variance or irreducible bias, leading to unacceptably high prediction errors. In this work, we introduce STAR, framework for OPE that encompasses broad range of estimators- which include existing OPE methods as special cases that achieve lower mean squared prediction errors. STAR leverages state abstraction to distill complex, potentially continuous problems into compact, discrete models which call abstract reward processes (ARPs). Predictions from ARPs estimated from off-policy data are provably consistent (asymptotically correct). Rather than propos- ing a specific estimator, demonstrate that estimators within STAR outperform existing methods. The best STAR estimator outperforms baselines in all twelve cases studied, and even the median STAR estimator surpasses the baselines in seven out of the twelve cases.
present new framework for OPE and empirically
Introduction
Within reinforcement learning (RL), off-policy evaluation (OPE) is the foundational challenge of evaluating the performance, J(rr), of policies that are different from the ones used generate data. OPE methods are a general-purpose tool that can be used as part of a local policy search algorithm tool to evaluate policies without requiring their actual deployment for high-risk applications like those in healthcare (38), education [35] [5]. and recommendation systems (5 7 Despite many recent advances in OPE, existing methods struggle to give accurate predictions for many real-world applications 52 showing the need for new perspectives on OPE.
45 to provide insight about policies similar to the current policy,
Existing methods can be broadly divided into two categories: importance sampling (IS) based and model-based [58). IS- (S-based methods are typically consistent (i.e., their predictions converge probabilistically to the correct value in the limit as the amount of data approaches infinity), but have variance that increases exponentially with the horizon [29 31). Model-based methods have lower variance but often introduce bias due to model class mismatch and are not generally guaranteed to be consistent [36]]] 10) A third set of methods, which call mixture methods, combine the predictions obtained from both of these categories [22 53 However, in some cases, combining the predictions also combines the drawbacks- high variance and bias. This leads
ask: Can develop framework for OPE that yields predictions that are both consistent and low variance?
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

M Tbp
A)
M + nbb
p M + mbp))
ARP(x.
p
(e)
(b)
Figure 1: (a): MDP M and policy m are transformed into a discrete abstract reward process (ARP) using a state abstraction function Φ. The ARP aggregates rewards (denoted by stars) and transition probabilities from all states that map to each abstract state. (b): A model of the ARP for the evaluation policy He constructed by: reweighting data generated by T with importance weights p (middle), applying the state abstraction function o, and performing weighted maximum likelihood estimation of the ARP (right). The expected return of a model of this ARP estimated from off aff-policy data is a consistent estimator of the expected return of Te.
In this paper, we introduce a new framework that attains this goal by combining the machinery under- lying IS-based and model-based approaches (not just their predictions). Our proposed framework fundamentally different approach OPE that incorporates importance sampling into model learning for OPE. Our approach is motivated by the intuition that humans build small mental models of their environment to plan and predict, selectively abstracting away information that not relevant to the problem at hand 54 Similarly, complex sequential decision processes can be distilled into compact models that hold sufficient information for (off- )policy evaluation. Specifically, we propose creating small tabular models (even for continuous environments), which we call abstract reward processes (ARPs), customized for the problem at hand and for the policy being evaluated. We call this framework for constructing range of ARPs state-gbstract reward processes (STAR).
Idea Summary: Markoy decision process (MDP) combined with a policy π induces a Markov chain with rewards, called a Markov reward process (MRP). A model of this process can be estimated to evaluate policy æ. However, two main challenges arise: (1) like any model-based approach, estimating MRP can introduce asymptotic bias if the chosen model class cannot represent the underlying MRP; and (2) the model of the MRP must be accurately estimated from off-policy data, i.e., data generated by behavior policy Ti that differs from the evaluation policy Te. The proposed framework addresses both challenges by modeling a special instantiation of an MRP, as detailed next.
First, to address potential model class mismatch, we propose mapping the large and possibly con- tinuous set of states of the MDP to a finite set of abstract states using a discrete state abstraction function. We then represent the resulting MRP defined over abstract states, referred to the abstract reward process (ARP), using tabular models. Since the ARP is finite, tabular models can represent it accurately, depicted in Figure aa). However, using discrete state abstraction may lead to loss of state information that can potentially introduce modeling errors. Surprisingly, we prove that despite state information being abstracted away, the maximum likelihood model of ARP estimated from on-policy data provides consistent estimates of the expected return of the behavior policy mb.
Next, to estimate a model of the ARP corresponding to from data generated by Th, we reweight occurrences of abstract states in the pollcy dataset using importance sampling, see Figure [bb). In expectation, this has the effect of updating the abstract state visitation counts to reflect those resulting from the policy being evaluated. We prove that the weighted maximum likelihood estimate of a model of the ARP estimated from this off-policy dataset provides consistent estimates of the performance of the evaluation policy. The integration of importance sampling into model estimation permits a favorable interpretation of weight clipping for mitigating variance (see Section 4.1.
The STAR framework offers two adjustable knobs-thh the state abstraction function, and the amount of weight clipping- that instantiate a range of OPE estimators. Varying the configurations of these knobs results in different bias-variance trade-offs for OPE, with existing OPE methods forming special cases of the range of estimators that lie within this framework.

---

Contributions: We empirically evaluate estimators instantiated in this framework on synthetic domains and healtheare simulator built from real- ICU data, where the best STAR estimator significantly outperforms baselines in all cases, and even the median STAR estimator surpasses baselines in seven out of twelve cases. It must be emphasized that this work does not propose a specific estimator for OPE; rather, it introduces fundamentally different framework that offers fresh insights on approaches for off-policy evaluation. These insights open up exciting avenues for new research questions and future directions. In this paper, we introduce:
(1) the first model-basee approach for OPE that guarantees asympotic correctness of the estimates without model class assumptions, even for continuous state MDPs (Theorem 4.1.
(2) the concept of abstract reward processes for consistent OPE. ARPs abstract away the complexity of the underlying problem, and distill sufficient information for accurate policy evaluation (Theorem 3.1. Being finite, they can be consistently estimated.
(3) generalizing framework that provides fresh perspective OPE by merging the machinery of model-based and IS-based approaches. The framework offers two tnaale knobs, various configu- rations of which instantiate range of OPE estimators with varying bias-variance characteristics. Existing model-free and model-based methods are special cases in this framework.
2 Background and Notation
An MDP is a tuple M == (5,A.).))).)) where S is the set of states, S, is the state at time t E (0, }. A is the set actions, At is the action at time t, S x A x S + 1 the transition function that characterizes state transition dynamics according to p(s, a, s')
1 A, a.)) r S x A R is the reward function that characterizes rewards according to r(s, a) = =iR, A,=a) 7 E [0, 1] is the reward discount parameter, and S + 00 1] characterizes the initial state distribution according to nss) Pr(So=s) A policy x S x A > [0. 1] characterizes how actions can be selected given the current state according to T (s,a) := Pr(A,-a|Sa =s). We consider finite horizon MDPs (49 where episodes terminate by some (unspecified) time T whhch is common in practical applications of OPE. For simplicity, set y 1, allowing us omit y terms.
For OPE, a dataset (( is collected by deploying behavior policy ma on the MDP M. The dataset of n logged trajectories is denoted by ( == { where each H' == (St, Aj. Rg Si....)
represents an independent trajectory generated by executing The The performance of evaluation
policy ne is its expected return, denoted by ?
T
(TTe) == E
Σ
Rei te
(I)
The problem of off-policy evaluation entails estimating J(Te) with access only to data D(TT) generated by behavior policy T6, without additional interaction with the MDP. To ensure that samples in ((x)) are sufficiently informative, we make the common assumption that any outcome under Te has non-negligible probability of occurring under Tb.
Assumption 2.1. There exists an (unknown) ε > 0 such that for all s E S and a E A. (TT(s, < <) = (5e a) 0).
Background: For a detailed review of OPE methods, we refer the reader to surveys by Voloshin et al. [58) and Uchara et al. [56]. Concepts fundamental to this approach are briefly introduced here.
1. Importance Sampling: Importance sampling (25) enables unbiased estimation of the expected value, Eff(()), of a function f applied to a random variable X ~ p, given samples of a different random variable Y ~ q. The importance sampling estimator is (Y)))) where
'For simplicity, our notation assumes that states, actions, and rewards are discrete random variables allowing for discussion of probabilities, rather than densities or measure theoretic probability. However, the methods proposed in this work extend to MDPs with continuous states, actions, and rewards. Furthermore, although we focus on OPE for MDPs, the method that we propose also applies to partially observable MDPs (POMDPs). "W write: π within statements of probability or expectations to indicate that random variables like S,, A.. and Rd result from the use of policy π.
3

---

p(Y)/a(Y) is term called an importance weight. This technique can provide unbiased estimates
(i.e., E (p(())/g(() f(Y) = = (X)) and has proven effective for variance reduction in Monte Carlo sampling 44 and for model-free OPE in RI. [42]
2. State Abstraction: State abstraction aims to reduce the size of the state space by grouping together similar states in a way that does not change the essence of the underlying problem [2 43
I. A & that map each state S to an abstract state 2 E Z. We consider abstraction functions that partition into disjoint sets, where 2 is finite set.
state abstraction function á : S + Z lies in the set of functions
Notation:
Indicator functions are abbreviated for clarity. For example, 1/ = (60(5
z', (() }} denotes the occurrence of abstract states and s' time steps and in the tth logged trajectory, with 1 defined correspondingly. The expected return of when obtained from O-where may be the MDP, or an ARP-is denoted by [ O). The sample estimate of variable y estimated from samples is denoted by 2h. Summation limits are often dropped for brevity, with Ee denoting E and Σ; denoting Σ
2.1 Markoy Reward Processes
Markov reward process (MRP) extends the idea of a Markov chain by associating states with rewards. Formally, state at time t, p X x X - [0, 1] is the transition function where p(x, x²) == Pr(X(+1=x'I (==)) r: r:d- + R is the reward function where r(z) E[R, X,=x), y E [0, 1] is the discount factor, and : X - [0, 1] is the starting state distribution. We consider finite horizon MRPs where episodes terminate by some (unspecified) timestep and 7
MRP is tuple (X, ", where X' is the set of states of the MRP, X, is the
specific MRP is induced by the use of fixed policy æ on an MDP M, where X' S. The resulting transition and reward functions, denoted by pd and rr respectively, are:
(2 (x,x²) = Pr = =I'
S. Pr(S, = 2; PrS
r (x)
(2)
Pr(s = xT
The Markov property (37 allows for further simplification of the above expressions (detailed in Appendix II,), but this form is most conducive to our subsequent discussion. In this work, we focus on a specific instantiation of an MRP, described in the next section, where the set of states X' of the
MRP are outputs of state abstraction function @ E T.
3 Abstract Reward Processes
An abstract reward process is a Markov reward process derived defined over abstract states- that we use to evaluate æ. The ARP provides two primary benefits for policy evaluation: (1) it preserves sufficient information to exactly evaluate the policy æ, and (2) the ARP can be consistently estimated from data. In this section, we formalize the concept of an ARP, and highlight the theoretical and practical benefits of using ARPs for policy evaluation.
derived from MDP M and policy π and
Given a state abstraction function ø= Ry is an MRP (Z, PT, R7, no), with y 1 (see Appendix A. for discussion on termination in ARPs and MRPs). The components of the ARP are defined over abstract states as:
Z, the ARP 9T is defined such that X' Z. Formally,
P P5 2'): Σ, Pror(((S)==
RT(2)= Σ, Pr(((.)))
and (2) = Pr(((So) =). These expressions cannol be simplified further, unlike the case of an MRP 2] Since is a finite set, i.e., the abstract states are discrete, the components of the ARP can be represented by matrices (we uppercase letters to emphasize this). The expected return of Rig can be computed efficiently using a linear solver evaluate the expression [TT; 9gg) = (I-P - or via Monte Carlo rollouts of the reward process.
ARPs are Performance Preserving: The expected return of an ARP has a surprising property: even though some state information is abstracted away to create simple discrete abstract states, the finite

---

ARP, derived from a possibly continuous and complex MDP, preserves sufficient information about the performance of the policy that defines the ARP for all & ④
Theorem 3.1. V @ the performance of a policy πT is equal to the expected return of the abstract reward process Ry defined MDP M, i.e., [[;; 25) = [[T;
Proof. See Appendix B.1
The result holds for the ground-truth ARP Rd In practice, a model of the ARP must be estimated from data. Next, we deseribe how the choice of defining an ARP over discrete abstract states eliminates model class mismatch, enabling asymptotically correct estimation of the ARP from data.
Methods that learn models from data make an assumption about the class of models used to represent the data. A significant challenge is that of model class mismatch, where this assumed model class is often unable to represent the true data distribution. As an example, neural network parameterizing univariate Gaussian distribution cannot accurately represent data generated from a bimodal distribution. In the context of this work, the transition function of an ARP may specify arbitrary probability distributions over discrete abstract states, necessitating a careful selection of the model class. Tabular models are capable of representing any distribution over discrete variables. Therefore, using tabular models when estimating ARP from data ensures that there is no model class mismatch. This is why we employ state abstraction functions & that partition the state space into a finite number of disjoint sets, discrete abstract states. The abstraction functions may be viewed as: (a) a discrete clustering of the state space, or (b) a discretization of continuous states.
Eliminating Model Class Mismatch:
While this addresses model class mismatch, the use of a discrete state abstraction may itself be a source of modeling error. Mapping groups of (possibly continuous) states discrete abstract states loses information about the state of the MDP. A process defined over the abstract states cannot in general capture the full complexity of the underlying MDP and policy. Nonetheless, Theorem 3.1 guarantees that the ARP is performance peeenneeeereeeiing....mo ensuring that the use of discrete state abstractions not source of error for policy evaluation. Additionally, since have eliminated model class mismatch, a perfect model of the ARP can be asymptotically estimated.
To estimate the ARP from (T))) apply the state abstraction function to states in D(TT) to map them to the abstract state space. Denote the maximum likelihood estimate of the model of the ARP obtained RT M.. The components take the
from the datasct (with abstract states) by R == Pr form:
n,o
Ex, = Pa (2,2)) Ex,lH( H+ (x)
(2) E 1'(20 =}
(4)
Asymptotic Correctness: With access on-policy data D the following result states that ARPs enable consistent model-based estimation of the policy's 's performance.
Lemma 3.2. Vé & the expected return of the maximum likelihood estimate Ry converges almost surely the expected return of the policy n. i.e., [1;; Ri, 0n [ M).
Proof. See Appendix B.2
As the amount of data (n) increases, the estimate of J[m; M) becomes increasingly accurate, i.e., the return estimate is consistent. This result holds for all ø E 4. It implies that even an arbitrarily small model derived from large, complex sequential decision-making problem will not introduce asymptotic bias. However, this theoretical guarantee requires on-policy data and so does not directly assist us in off-policy evaluation. To that end, we introduce a procedure for estimation of the ARP from off-policy data that merges the machinery of IS-based and model-based methods.
3.1 Estimation from Off-Policy Data: Weighted Maximum Likelihood Estimation
We present a method for consistent estimation of the ARP corresponding to the evaluation policy Te from off-policy data (R)) relies the following intuition:
5

---

The expected value of the indicator function of an event represents the probability of that event. Use importance sampling approximate the probability of that event under different distribution.
To estimate an ARP from off-policy data, assign importance weights Po:t to the abstract states (Z, == ((,)) in the dataset D/ Let H, (So, Ap, Ro...., .,,,, St de- note a sub-trajectory up to time t. The importance weight Poxt is then the ratio of the probability
of H. under Te and Th. i.e., Po.e Pr(He:m.)
Pr(Hesme) I1i- (S,AA,))) 3 The maximum likelihood Ag,
estimate (MLE) of R5 obtained from the weighted off-policy data is denoted by R
[2 Prattt R .nn. (n.otte)) where 7n
2 (=0==] remains unchanged, and
Ex, 1112,21pp Ei, pos
(2) Ex, HH=)
Pma-** (2,2)
R R
(5)
Ei,e 11zzpp0
This estimation is form of weighted maximum likelihood estimation ratios in the numerator and denominator of the estimated transition and reward functions of the ARP enables estimation from off-policy data generated by πT- The estimated model of the ARP is consistent and, as shown next, allows for consistent off-policy evaluation.
K Including the importance
Lemma 3.3. Under Assumption 2.1 the weighted maximum likelihood estimate Rh- converges almost surely the ground-truth ARP RT i.e. n.p _ 2i
Proof. See Appendix B.3
4 Off-Policy Evaluation with ARPs
The expected return of A is consistent estimate of the performance of policy ne since A an asymptotically correct estimate of R as per Lemma 3.3
Theorem 4.1.
The expected return of the ARP RTy-D (built from off off-policy data) converges almost n.
surely to the expected return of Te, i.e., [ R ) an, (Te:MM) Proof. See Appendix B.4
To our knowledge, this is the first instance of a model-based OPE method that comes with the theoretical guarantee of consistent performance estimates, even for continuous problems and without model class assumptions. So far, we have achieved one the starting goals-that of consistency. However, the use of importance weights Po:t for weighted MLE is expected to introduce high variance. Next, we discuss methods to mitigate the variance of IS.
4.1 Variance Reduction: Leveraging Markovness of the State Abstraction
A common technique for mitigating the variance of IS IS-based methods for OPE is clipping the importance weights to the e most recent ratios
i.c. P(t-c+ := -I'= where (t + 1)= max(t - e 1, 0). This is often bad approximation for classical IS-based methods, as it implies that only the most recent actions affect the reward distribution at any timestep. which rarely holds true in practice. In STAR, importance weights are incorporated into model estimation, resulting in more reasonable implication of weight clipping.
[8]
A.( (.(S))A))*
By importance weighting the abstract-state occurrences as described in Equation (5). clipping importance weights, in this case, implies that the e most recent abstract states are sufficient to determine the current abstract-state transition and reward distributions. This allows actions from the distant past to influence the current reward, the effects of actions propagate through the abstract state transitions, unlike in IS-dased methods. This condition, that a recent history of abstract states sufficient to predict the current abstract state transition distribution, often approximately holds
'The expression for the importance weight can be extended to continuous and hybrid probability measures using Radon- -ikoddy derivatives. As with other terms, we hereafter denote the importance weight for the th episode pb.t-

---

in practice as discussed in POMDP literature 30 39.. While the approximation may introduce asymptotic bias in exchange for reduced variance, certain abstraction functions that satisfy specific conditions can incur no asymptotic bias.
Weight Clipping without Asymptotic Bias: Intuitively, the use of e-clipped importance weights, P(--c+1)+:a> updates the estimated distribution of the previous с abstract states-as if under the evaluation policy-while leaving the ones before unchanged. c-clipping does not introduce asymptotic bias when the previous c abstract states form a sufficient statistic for predicting the current abstract state transition distribution. This notion of conditional independence from history given the recent past is referred to as the Markovness of the abstraction function 6. We posit that there exist abstraction functions that are c-th order Markov 9..
Definition 4.2 (c-th order Markov). The abstraction function & is e-th order Markov ((S(t=++1)+ ); >>= Pr(((((+ ((S))) TT) for π E {ma, Te)-
Pr(o(S--i)lo(S))
Let P denote the ARP estimated using e-clipped importance weights, P(I-c+1)++t= in place of 0e
Po:t in Equation (5).
Theorem 4.3. Given a c-th order Markov o, the expected return of the abstract reward process
Rg. converges almost surely to the expected return of Te, i.e., J [me; A (0)) as, [[Te M).
0,c
Proof. See Appendix B.5
Even when & does not satisfy the above condition, weight clipping proves to be practical approxi- mation and results in low mean squared prediction error, demonstrated empirically in Section 5 The steps for performing off-policy evaluation by estimating R,, are highlighted in Algorithm
4.2 Fantastic é's and Where to Find Them
Discrete abstraction functions that are e-th order Markov with small values of c represent the most suitable abstractions for enabling asymptotically correct, low-variance off-policy evaluation using STAR. An automated approach to discovering such abstraction functions, however, remains elusive. In a manner reminiscent of the options framework [50], wherein one might consider the usefulness of options before having methods for constructing options automatically, this work emphasizes the remarkable effectiveness of state abstractions used in abstract reward processes for OPE. motivates a research area akin to option discovery: abstraction discovery for OPE.
We expect the following factors to play an important role the search for good abstraction functions: (a) state-visites visitation distributions of ny and Te. determining the granularity of abstraction in different parts of the state set, and (b) the distribution shift in abstract state visitation induced by the two policies, determining the extent of weight clipping that can be applied. Both of these are affected by properties of the underlying MDP, in particular the transition function, and in our initial analyses, we observe varying effects of similar abstractions across different MDPs (Appendix C.2).
We observe that a simple approach of randomly initializing centroids and applying k-means clustering 34 33 where each cluster denotes discrete abstract state, results in abstractions that provide competitive OPE performance, often significantly outperforming existing methods. We call this naive clustering based abstraction method CluSTAR, and use it for our experiments. In some cases, abstraction by aggregation of states can increase the difficulty of estimation of the transition function. For example. aggregation of two states with deterministic transitions-whine perfectly from single observation of those transitions- creattsssss stochastic transitions between abstract states. However, in general, state aggregation tends to simplify estimation by increasing the effective sample size (1
can be estimated
Recovering Existing OPE Methods from STAR:
Different configurations of (Ø, e) induce different
ARPs, R For certain configurations of (0,c):
|2| = and no weight clipping: Mapping all states to single abstract state yields the weighted per-decision importance sampling (WPDIS) estimator [42
2 = S and c = 1: Amounts to state abstraction, and yields the maximum likelihood estimate
of the MRP over states. The MRP is a combination of the approximate-mode estimator 40 that
directly estimates the model dynamics with the evaluation policy.
7

---

The recovery of these familiar estimators at the endpoints of STAR highlights the unifying nature of the framework. More importantly, the intermediate configurations of (g, c) uncover a whole new set of OPE estimators. The ARPs in this space often inherit a mixture of the favorable properties of both of the endpoints. Consequently, the framework yields estimators that can significantly outperform existing methods, as shown empirically in the next section.
5 Empirical Analysis
In this section, we (A) analyze the performance of the set of estimators (ARPs) induced by STAR across different configurations of (ó, c). and (B) compare the performance of the best and median ARPs from this set against existing OPE methods demonstrate that estimators encompassed by STAR often outperform prior OPE methods. We use the following domains for OPE: (1) CartPole
49
A classic control domain in OpenAI Gym O (2) ICU-Sepsis {8: An MDP that simulates
treatment of sepsis in the ICU. ICU-Sepsis is built from real-world medical records obtained from the
MIMIC-III dataset 24 using a modified version of the process described by Komorowski et al. [26].
(3) Asterix from the MinAtar testbed [1]: A miniaturized version of the Atari game Asterix. Details about each domain, and about the behavior and evaluation policies can be found in the Appendix C
The code is available at: https://giii thub. com wwt.///////ssseeeee shreyasc- 13/STAR
(A) Estimator Selection: Estimator selection presents significant challenge for OPE [48] due to the unavailability of a validation set. To select STAR estimators to compare against existing methods, we first report the performance of the set of the ARPs induced by STAR, across a range of configurations of (Ø) c). We highlight the performance of the best and median estimators from this set. For ref- erence, we compare the mean squared prediction errors from the estimated ARPs against WPDIS and approximate- model estimator (MBased), the two endpoints of STAR, as shown in Figure 2 on the CartPole domain. The state ab- straction is performed with CluSTAR with the number of centroids |Z| E {2, 4, 8, 16, 32, 64, 128] and the weight clipping factor E 11, 3, 4, 5) defining 35 ARPs, where the performance of each is indicated by This range of (é, c) is picked based on the intuition that (a) larger values of e are expected to introduce high vari- ance, and (b) this range of 2 covers a variety of granularities of state abstraction (for a continuous problem). The results are averages across 200 trails. The prediction errors for the estimated ARPs are competitive with baselines. This suggests that an average estimator in STAR competitive with existing OPE methods, and even better performance may be attained by using specialized methods for abstraction discovery and estimator selection [55]. Figure 4 in the Appendix, provides a detailed breakdown of the performance of cach ARP in the set considered, presented as a heatmap. This high- lights patterns observed for varying values of |Z| and c across different domains. Further discussion and details about the best best-performing configurations of (d, c) are deferred to Appendix C.2
10
10*
MSE
102
Best
Melian
MBased
X
WPDIS
1000
Dataset
Figure 2: Mcan squared prediction er- rors of the estimated ARPs for the set of hyperparameters swept over for Cart- Pole.
(B) ARPs Can Outperform Existing Methods for OPE: We compare against representative
methods from the main categories of OPE methods: (a) IS-based methods: Vanilla IS, Per-Decision IS, Weighted IS, Weighted Per-Decision IS [42]: (b) Model-based methods: that approximate a model of the MDP-MBasee [49] and directly estimate off- off-policy D-values-FQU and MRDR (27 [I]:
and (c) Mixture methods: DR [22] and MAGIC [53], which blend estimates from the methods in the aforementioned categories. We use implementations from the Caltech OPE Benchmarking Suite (COBS) (58) for all methods. The representative method for minmax style estimators, IH [31], is designed for the infinite horizon setting and performs poorly with y 1 63.. Due to the instability of IH estimates in our experiments, we excluded from comparison.
Results [Figure 3 and 4] The ranges of [Z] and c for each domain, which induces set of ARPs that we consider, are detailed in Appendix C.2 Figure Appendix demonstatss the performance of each ARP from that set as heatmap, showing that the best configuration of (d) c) varies with the dataset size for each domain. In critical applications like sepsis treatment, as simulated in ICU- Sepsis, where incorrect policy performance estimates can be catastrophic, the best estimators in
8

---

(a) CartPole
1000
10000
109
10a
10a
10a
10
10
MSE
10"
10'
10
10'
(b) ICU-Sepsis
50
n 100
n
500
5000
10
10
10
Var arnc
Bae
186
10
10
10-
10-3
10-3
10
20%
(c) Asterix
10a
10
500
10'
1000
10"
10000
10a
10a
MSE
10
10:
10a
10
10a
10a
Rec
Vol arcc
10
10
10
10
200
Figure 3: Mean squared prediction errors of best and median ARPs from STAR compared against existing OPE methods. The empirically estimated birs-variance decomposition of the error is shown. The results are averaged over 200 trials, with error bars indicating standard error. Note: For ICU- Sepsis, regression-basee large state set, as the corresponding Weighted Least Squares methods for regression were slow. In all domains and across all datasizes, the best ARP in STAR outperforms baselines in all cases, and the even the median estimator does so in 7 out of 12 cases.
methods (MRDR and Q-Reg) were computationally intractable due to the
STAR achieve prediction errors that are an order of magnitude lower than the best baseline. These results in Figure emphasize that highly compact ARPs that distill complex sequential processes are particularly effective for poolcy evaluation. The best ARP in STAR for each domain abstracts: (a) the continuous state space of CartPole to ||| = 32 abstract states, (b) the 747 states of ICU-Sepsis to 2 = 16 abstract states, and (c) the 400 states of Asterix to | = 8 abstract states, to construct compact finite ARPs for OPE. Furthermore, the horizon length of CartPole is 50, and episodes in ICU-Sepsis and Asterix go up to 120 and 75 timesteps respectively. Such relatively long horizons have proven to be challenging for prior OPE methods. STAR leverages ARPs to enable OPE at scales commonly seen in practice.
Related Work
The problem of off-policy evaluation (OPE) has been extensively studied due to its relevance for practical applications of reinforcement learning [38 35) Extensive surveys on the topic, both theoretical [56) and empirical (58] [4] delineate the numerous approaches the problem. Model- based approaches for OPE have proven effective [32
62) but are restricted by the model class used. In this work, we use state abstraction define compact models called abstract reward processes, and demonstrate their effectiveness as off- aff-policy estimators. Historically. state abstraction research has focused on grouping similar states in a way that does not change the essence of the underlying problem 28 43 D, to reduce the complexity of the problem. However, the use of state abstractions for OPE remains under-explored. Pavse and Hanna [41 show that the use of state abstraction with marginalized importance sampling achieves variance reduction in high-dimensional state spaces, but their approach does not use abstraction to construct models. Jiang et al. 23 study abstraction selection for model- based RI, balancing model complexity and policy value suboptimality. Abstraction discovery or

---

learning has focussed on discretization of continuous state spaces to reduce problem complexity 47 and distilling the Markov features or reward relevant features [2 59
7 Discussion and Conclusion
In this paper, we have introduced new framework for consistent model-based off-policy evaluation. This framework leverages state abstraction prevent model class mismatch along with importance sampling to consistently learn models from off-policy data. Unlike traditional model-based methods, approach eliminates the need for model class assumptions and provides theoretical guarantees for the obtained performance estimates. Moreover, using state abstraction increases the effective sample size [2I]. which is particularly beneficial in limited data regimes. Importantly. this work presents framework with a new approach to OPE, rather than a specific new method. Estimators that lie within this framework significantly outperform existing OPE methods, with the best estimator consistently outperforming all baselines, as demonstrated in our empirical evaluation.
The framework has two main limitations: it requires knowledge of the probabilities of observed actions under the behavior policy, which may not always be available, and principled method for selecting well-performing configurations of the abstraction function and the weight clipping factor remain elusive. Combining this work with regression addresses the first limitation. Additionally, a data-driven approach to automated estimator selection based on characteristics of the domain, dataset sizes, and other factors, as suggested by Su et al. [48]. would enhance its practical application.
[9] would be a practical extension that
Our findings indicate that even a simple class of abstraction functions can provide competitive OPE performance. We theoretically demonstrate the existence of certain abstraction functions that may offer better performance. Investigating the properties of abstraction functions and developing automated approaches to abstraction discovery for ARPs are promising directions for future work on creating high tigh-performing OPE methods.
We thank Yash Chandak, Mohammad Ghavamzadeh and Dhawal Gupta for their helpful discussions and feedback on this work. We would also like to thank Josiah Hanna, Bo Liu, Cameron Allen, and the anonymous reviewers for their feedback.
Acknowledgements
References
[1] David Abel. A theory of state abstraction for reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 9876-9877, 2019.
[2] Cameron Allen, Neev Parikh, Omer Gottesman, and George Konidaris. Learning Markov state abstractions for deep reinforcement learning. Advances in Neural Information Processing Systems, 34:8229-8241, 2021.
[3] Oliver Bembom and Mark van der Laan. Data-adeptive selection of the truncation level for inverse-probabiliy probability-of-treeeeeee off.rreatment-weeeeeeeeee weightted estimators. 2008.
[4] Patrick Billingsley. Convergence of Probubility Measures. John Wiley & Sons, 2013.
[5] Léon Bottou, Jonas Peters, Joaquin Quiñonero- Candela. Denis X 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(11), (1), 2013.
[6] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl gym. arXiv Preprint arXiv:1606. 01540, 2016.
[7] Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. Advances in Neural Information Processing Systems, 24, 2011.
[8] Kartik Choudhary, Dhawal Gupta, and Philip Thomas. ICU-Sepsis: A benchmark MDP built from real medical data, 2024.
10

---

[9] Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforce- ment learning with a short-term memory. In Proceedings of the International Conference on Machine Learning, pages 5832-5850. PMLR, 2022.
[10] Amir-Massoud Farahmand and Csaba Szepesvári. Model selection in reinforcement learning. Machine Learning, 85(3):29--332, 2011.
[11] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off oof-pol evaluation. In Proceedings of the International Conference on Machine Learning, pages 1447-1456. PMLR, 2018.
[12] Norman Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite Markov decision processes, arXiv Preprint arXiv:1207.4114. 2012.
[13] Chris Field and B Smith. Robust estimation: A weighted maximum likelihood approach. International Statistical Review/Revue Internationale de Statistique, pages 405-424, 1994.
[14] Justin Fu, Mohammad Norouzi, Ofir Nachum, George Tucker, Ziyu Wang, Alexander Novikov, Mengjiao Yang, Michael R Zhang, Yutian Chen, Aviral Kumar, et al. Benchmarks for deep off-policy evaluation. arXiv Preprint arXiv:2103. 16596, 2021.
[15] Ge Gao, Song Ju, Markel Sanz Ausin, and Min Chi. Hope: Human-centric off-policy evaluation for e-learning and healthcare. arXiv Preprint arXiv:2302.09212, 2023.
[16] LC Evans-RF Gariepy and F Ronald. Measure theory and fine properties of functions, Revised edition. CRC Press, 2015.
[17] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. International conference on machine learning, pages 1321-1330. PMLR, 2017.
[18] Zhaohan Guo, Philip S Thomas, and Emma Brunskill. Using options and covariance testing for long horizon off-policy policy evaluation. Advances Neural Information Processing Systems, 30, 2017.
[19] Josiah Hanna, Scott Nickum, and Peter Stone. Importance sampling policy evaluation with an estimated behavior policy. In Proceedings of the International Conference Machine Learning, pages 2605-2613. PMLR, 2019.
[20] Edward L Ionides. Truncated importance sampling. Journal of Computational and Graphical Statistics, 17(2):295-33) -11, 2008
[21] Nan Jiang. Notes state abstractions, 2018. URL https:://///nii cs. wwwiiniiiii..... edu/ files/cs598/ http////9t//n/eee pdf
[22] Nan Jiang and Lihong Li. Doubly robust off- off-policy value evaluation for reinforcement learning. In Proceedings of the International Conference on Machine Learning, pages 652-661. PMLR, 2016.
[23] Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model-based reinforce- ment learning. In Proceedings of the International Conference on Machine Learning, pages 179-188. PMLR, 2015.
[24] Alistair EW Johnson. Tom J Pollard, Lu Shen, Li-wei H Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark. MIMIC-III, a freely accessible critical care database. Scientific Data, 3(1):1-9, 2016.
[25] Herman Kahn and Theodore E Harris. Estimation of particle transmission by random sampling. National Bureau of Standards Applied Muthematics Series, 12:27-30, 1951.
[26] Matthieu Komorowski, Leo A Celi, Omar Badawi, Anthony C Gordon, and A Aldo Faisal. The artificial intelligence clinician learns optimal treatment strategies for sepsis in intensive care. Nature Medicine, 24(1 24(11):171--772 2018.
11

---

[27] Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Proceedings of the International Conference on Machine Learning, pages 3703-3712. PMLR, 2019.
[28]
Lihong Li, Thomas J Walsh, and Michael L Littman. Towards unified theory of state abstraction for MDPs. Artificial Intelligence and Machine Learning (AI&M), 1(2):3 2006.
[29]
Lihong Li, Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. In Proceedings of the Artificial Intelligence and Statistics Conference, pages 608-616. PMLR, 2015.
[30] Michael Littman and Richard S. Sutton. Predictive representations of state. Advances in Neural Information Processing Systems, 14, 2001.
[31] Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse horizon: Infinite-horizon off-policy estimation. Advances in Neural Information Processing Systems, 31, 2018.
[32] Yao Liu, Omer Gottesman, Aniruddh Raghu, Matthieu Komorowski, Aldo A Faisal, Finale Doshi-Velez, and Emma Brunskill. Representation balancing MDPs for off-policy policy evaluation. Advances in Neural Information Processing Systems, 31, 2018.
[33] Stuart Lloyd. Least Squares Quantization in PCM. IEEE Transactions Information Theory, 28(2):129-137, 1982.
[34] James MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, volume I, pages 281-297, Oakland, CA. USA. 1967. University of California Press.
[35] Travis Mandel, Yun-En Liu, Sergey Levine, Emma Brunskill, and Zoran Popovic. Offline policy evaluation across representations with applications to educational games. Proceedings of the International Conference Autonomous Agents and Multiagent Systems, volume 1077, 2014.
[36] Vukosi N Marivate. Improved Empirical Methods in Reinforeemenu-Lerriingg Evaluation. Rutgers The State University of New Jersey, School of Graduate Studies, 2015.
[37] Andrei Andreevich Markov. The theory of algorithms. Trudy Matematicheskogo Instituta Imeni VA Steklova, 42:3-375, 1954.
[38] Susan A Murphy, Mark van der Laan, James M Robins, and Conduct Problems Prevention Re- search Group. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 96(456):1400-4223 2001.
[39] Khanh Xuan Nguyen. Converting POMDPs into MDPs using history representation. Engineer- ing Archive, 2021.
[40] Cosmin Paduraru. Off-Policy Evaluation in Markov Decision Processes. PhD thesis, 2013.
[41] Brahma S Payse and Josiah P Hanna. Scaling marginalized importance sampling to high- dimensional state-spaces via state abstraction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9417-9425, 2023.
[42] Doina Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
[43] Balaraman Ravindran. An Algebraic Approach to Abstraction in Reinforcement Learning. University of Massachusetts Amherst, 2004.
[44] Reuven Y Rubinstein and Dirk P Kroese. Simulation and the Monte Carlo Method. John Wiley & Sons, 2016.
[45] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the International Conference on Machine Learning, pages 1889-1897. PMLR, 2015.
12

---

[46] Pranab K Sen and Julio M Singer. Large Sample Methods in Statistics: An Introduction with Applications. volume 25, CRC Press, 1994.
[47] Sean R Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Adaptive discretization for episodic reinforcement learning in metric spaces. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(3): 2019.
[48] Yi Su, Pavithra Srinath, and Akshay Krishnamurthy. Adaptive estimator selection for off- policy evaluation. In Proceedings of the International Conference Machine Learning, pages 9196-9205. PMLR, 2020.
[49] Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
[50] Richard S Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1-2): 181-211, 1999.
[51] Erik N Talvitie. Simple Partial Models for Complex Dynamical Systems. PhD thesis, University of Michigan, 2010.
[52] Shengpu Tang and Jenna Wiens. Model selection for offline reinforcement learning: Practical considerations for healthcare settings. In Proceedings of the Machine Learning for Healthcare Conference, pages 2-35. PMLR, 2021.
[53] Philip Thomas and Emma Brunskill. Data-efficient off- off-ppolcy policy evaluation for reinforce- ment learning. In Proceedings of the International Conference on Machine Learning, pages 2139-21 2148. PMLR, 2016.
[54] Edward C Tolman. Cognitive maps in rats and men. Psychological Review, 55(4):189, 1948.
[55] Takuma Udagawa, Haruka Kiyohara, Yusuke Narita, Yuta Saito, and Kei Tateno. Policy- adaptive estimator selection for off- off-policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10025-10033, 2023.
[56] Masatoshi Uehara, Chengchun Shi, and Nathan Kallus. A review of off-policy evaluation in reinforcement learning. arXiv Preprint arXiv:2212.0635. 2022.
[57] Aad W Van der Vaart. Asymptotic Statisties, volume 3. Cambridge University Press, 2000.
[58] Cameron Voloshin, Hoang M Le, Nan Jiang, and Yisong Yue. Empirical study of off-policy policy evaluation for reinforcement learning, arXiv Preprint arXiv: 2019.
[59] Tongzhou Wang, Simon S Du, Antonio Torralba, Phillip Isola, Amy Zhang, and Yuandong Tian. Denoised MDPs: Learning world models better than the world itself. arXiv Preprint arXiv:2206. 15477, 2022.
[60] Neil A. Weiss. A Course in Probubility. Addison Wesley, Boston, 2005. ISBN 0-321-18954-X.
[61] Kenny Young and Tian Tian. MinAtar: An Atari-inspired testbed for thorough and reproducible reinforcement learning experiments. arXiv Preprint arXiv:1903.031777 2019.
[62] Michael R Zhang, Tom Le Paine, Ofir Nachum, Cosmin Paduraru, George Tucker, Ziyu Wang, and Mohammad Norouzi. Autoregressive dynamics models for offline policy evaluation and optimization. arXiv Preprint arXiv:2104.13877 2021.
[63] Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. arXiv Preprint arXiv:2002.09072, 2020.
[64] Daniel Zwillinger and Stephen Kokoska. CRC Standard Probability and Statistics Tables and Formulae. CRC Press, 1999.
13

---

A Preliminaries
Consisteney and Almost Sure Convergence Let 0n denote the estimator of statistic 0, estimated from data points. As the amount of data approaches infinity, i.e., as - oo, the estimator is said to converge almost surely f if and only if
Pr
lim 8n, = 11-00
We write On - 0 to denote that the sequence On converges almost surely to 0. An estimator that converges almost surely to the true value of the statistic is said to be (strongly) consistent.
states that if sequence of random variables (X,) converges almost surely to a random variable X, function f has discontinuity points D,, and Pr(X- D,) O, then the sequence (f(X,)) converges almost surely to f(X).
Continuous Mapping Theorem The continuous mapping theorem 57
Tower Rule For random variables X and Y defined on the same probability space, the tower rule states that the expected value of the conditional expected value of X given Y is the same as the expected value of X, i.e.
E
[X]
= E
E [ [Y]..
A.1 Additional Notes on MRPs and ARPs
Here we provide additional details regarding the definitions of MDPs and MRPs. Specifically, show how the expression of the transition and reward functions of the MRP can be simplified when X and discuss how handle termination in ARPs that are derived from finite-horizon MDPs.
A.1.1 Simplitication of Equation 2
The expressions for the components of a Markov reward process (MRP) can be simplified by using the Markov property. The transition function simplifies as:
p" (2r, x¹) E, Pr(S++1 = -,;
Pr(S
E, Pr(S1+1 x 21; Pr(S:
Pr(, = x;
E, EdEd Pr(St+1 = x S: =5, = - P Pr(S, n;
Pr(S = x;
Ee E.EApla, a, x' (x) a) Pr(S. = =;
E. Pr(S = z;
EnEAPle, o, x' )T Pr,S,
PrS, =z;
p(z aEA
Similarly, the reward function simplifies as:
Σ, E [R = x; Pr(,
r" (x:
Pr(s. x;;;
E, Ened r (x, Pr(S,
Σ, Pr =
EAEA (zz, a a)TTTI (r,
E, Pr(S: = x;
Σ (2)
14

---

A.1.2 Handling termination in an MDPs, MRPs, and ARPs
Each episode in a finite-horizon MDP concludes by some timestep T E N, referred to as the termination of that episode. In practice, there are two common ways of modeling termination of episodes in finite-horizon MDPs: 1) including absorbing state 8 in the state set, 2) introducing a termination function 3 + [o, 1] representing the probability termination an episode from = s). In the first case, by timestep 7 the process transitions into the absorbing & after which it continually transitions back to 8ec getting reward of zero. In the second case, after timestep I' the process stops and there
each state, i.e., ((s) = Pr Pr(terminate]
subsequent samples. Expressions involving sums over samples in an epsiode are denoted correspondingly, for example, the expected return ( = - Rr; nT in the first case, and J(T) = ED Re; π. in the second. Both approaches mathematically equivalent and correspondingly, MRPs induced by the combination of finite-horizon MDPs with a policy can model termination in either way.
However, termination in ARPs requires special attention. The introduction of absorbing abstract state 20 places a condition on the abstraction function Φ-it requires the abstraction function to map only 8oc, and no other state, to 2 In this work, we implement termination in code by estimating abstract termination functions that represent the probability termination from each abstract state. Denote the abstract termination function of an ARP by 1 Z [0. 1]. It must be noted that both approaches continue to be mathematically equivalent. The probability of transitioning from any abstract state to 2go is the same as the the probability of termination from that state, i.e., (2) (2 Reo). Note that
s
if = 2oc
(Z 2)
if
Zoo
Similarly, the reward function is zero for the absorbing abstract state: Rg 0. is mathe- matically more succint to model termination with 2 and we use this (equivalent) approach in our theoretical analysis.
In our implementation, 200 is not defined and thus the components of Rg do not take 2o0 input. The equivalant form of the expected return of an ARP, that models termination function, is then given by:
J(;; R5) Ry (I diag(33)) [PRR5 (I- (3g))
[PP)) PR + +..l]
Ro (I- (8)) P Po + (I --daigg (3))
((T diag( PT)) Ro
k=
Correspondingly, the closed form expression for the expected return that accounts for the termination function is given by,
J(T; (I (I (g)g(
PS)) (2)
(6)
Note that (I (I (I- diag (3gg P7 is an invertible matrix, as the left hand side of the expression,
J (w;; Rgg), equal to the expected return J(x;; M) of by Theorem 3.1 which is bounded.
15

---

B Proofs of Theoretical Results
In this section, we provide proofs of the theorems and lemmas in the main text. We start with Theorem that states that ARPs are performance preserving......
3.1
B.1
ARPs are Performance Preserving
Theorem
y & L, the performance of a policy π is equal to the expected return of the abstract reward process Ry defined from MDP M, i.e. RT; = M).
3.1
Proof. This result states that despite the use of discrete state abstraction, the expected return of the ARP R5 equal to the performance of policy т. To prove this, we leverage two equivalent forms of defining the expected return of policy. The first form:
[ )
defines the expected return a of the expected value of the reward each timestep, where the distribution rewards at each timestep is governed by the components of the ARP, namely, no. Pj and R The second, equivalent, form expressing the expected return given by:
(T:
ΣΣ Pr(Z, = ( ZEZ
= Σ Σ =EZ
Pr(Z: = 2; R5));
(8)
where the expected return is denoted as a sum of the reward at each abstract state mutliplied by the visitation frequency of that abstract state. Both Equations a]d
8 are equivalent, i.e..
(T; RT)
EB[RAA ΣΣ
Pr =
Next, denote the terms in Equation 8 in terms of the states of the underlying MDP to show the final result. The reward function R5 can be expressed as,
R5(2) E, EiR ((S))= Pr(())))) Pr(o(5))==
E, EEss = P
(0)))) Pr(S
1 = 21
(r
Exes 10(() = =] Pr(S-s85)) ESES. 10 ())
= =
E.Es 1()() = 2]
where the undiscounted state distribution
49 Section 9.2] under policy denoted by (s)
Σ, Pr(S, = s; T), where ai (Soo) is set to be proportional to any constant value. The normalization constant, k. that makes (s) valid distribution cancels out from both the numerator and the denominator of the above expression. The term Pr(Z, z; T) can be expressed in terms of states as,
Pr(Z. 2;
Pri(. (:0(S.-sA)]L
s; z}.
16

---

Substituting these expressions into Equation g gives,
Σ
Pr(Z 22
2E2
(Eressee E 1 (1))((..))((s =
ΣΣ
= (6])))
(s)(((())
2EZ
NE5S
( ( & (TM =2}
Σ
Pr(S: = (())))))))
(1)
#E2
WEE
o (8)1((())))) (011(0))=))) =2) (E 2
Σ
Σ
Eves 13th ()) =
:E2
AES
Σ
Σ
K.
=
#E2 sES,aEA
Σ
Σ
= 7
#ES,uEA
[T:; M))
where (a) follows from the law of total probability (64).
We have established that ARPs are performance-presseeee preserving, Next, we prove Lemma 3.2 which states that the performance estimate obtained from an estimated model of the ARP converges almost surely to the performance of the policy that induces it. order to do so, we first introduce properties that will be useful in the proof of Lemma 3.2
B.2 Estimation of ARPs from On-Policy Data
At a high level, we prove Lemma 3.2 by first studying the almost sure convergence of the estimated transition function, reward function, and initial state distributions. Once the almost sure convergence of these components has been established, we reason about the implications for the convergence of the policy performance predictions that result from these terms. We begin by studying the almost sure convergence of the transition function.
Property B.2. For all abstract states E Z and z' E 2,
Err(ze = =2; #
then
P& (2,(2 any (2,
(10)
Proof. Recall that
ns (2, Σ E, = =
Pr
Σn 11 =
Let X,, = 1. rewrite Por (2, as
= 2, 2 = =x'} and Yn = 1 = =2}. We can then
X, Y which is a continuous function of X,, and Yn when Y, > 0. At a high level, we will show what X,, and Y, each converge to almost surely, and will then apply the continuous mapping theorem to reason about the almost sure convergence of pa n. (z,=).
P (2,
However, there may be some abstract states Ž C Z that are not reached and thus are not observed in the data. Such abstract states pose problem: If ž e Ž, then Y,, for pa (ž, z²) will be zero,
17

---

and so PT. n.o (2, will be undefined and not continuous function of Xn and Y, (which must be handled appropriately the proof of consistency). First, to ensure that the ARP is well-defined even when is not empty, for abstract states E 2 (abstract states that were not observed in the data), special values can be hardcoded into the transition function, reward functions, and initial state distribution that the components of the ARP continue to be well-defined In particular, for & Z, the transition function can be set to self-transition back to & with probability 1, i.e. P (2,
and par (2, 2) for all 2 Z, the reward function is set to R R (2) and the initial abstract state distribution is 77.6 (2) = 0 for all 2
To reason about the almost sure convergence of PM n, z'), first consider lim Xn,
lim Xn lim n-000
Σ
11 = 2,, = =
n Y1
i=1
lim n+0
= 2
Note that 1(2; 2, Zi = } is independent across episodes (for each i), has bounded variance, and has the same mean for each episode. By Kolmogorov's 's strong law of large numbers [46].
Σ = Zi41 = as [1 = 2, Zu+1 = =
This convergence guarantee holds for all i. From the definition of almost sure convergence, this means that
Vt N. Pr
lim R-+00 π
Σ 1[ = 2, = = Zz+1 2/ 2/}:
(11)
where the expectation results from the use of the policy æ that generated dataset D(TT) By the countable additivity property of probability measures (and the fact that the number of time steps is countable), this implies the following (notice that Vt E N is now inside the statement of probability):
Pr E lim 12000
Σ 11 2,41 =1 = E Z+41 =/1; =1. (12)
Hence,
n Σ
Pr Σ lim n= 7I
Z = Σ E 11 =2'}: = (13)
Next, by the dominated convergence theorem over n can be interchanged, giving:
16
Theorem 1.19], the summation over time and limit
n Σ
= = -
Σ
E [1[Z. = 2, Ze+1 = =2))iT] = (14)
100
i=1
Returning notation, this means that
2.5.
Σ
Σ 11 100::===)))/ z/)) as Σ E [1fz 2, Z41 =2]]
(15)
"The particular behavior of the ARP in these unobserved abstract states is not of consequence. Since they are unreached, the behavior in these abstract states does not impact the expected return of the ARP. However, wish ensure that the transition function, reward function, and initial state distribution still represent well-defined ARP.
"Note that the initial state distribution is not actually problem like the transition and reward functions the previous definitions already ensured that 77 (2) = 0.
18

---

The expected value of the indicator is equal to the probability of the event, and so
EEii 2
= 2
Pr(Zi 2, = 2²:
(16)
This, combined with the fact that the left hand side of Equation 13 X₂ means that
X Σ = 7,41 =²
(17)
Similarly, these same exact steps can be followed to show that
Yn a.a. Σ Pr(Zi = 2)
(18)
Let V = (Xi, Yi), so that n = (X,,, Yi) is sequence of vector-valued random variables. Since
Xn as. E, Pr(Ze Ze+1 = x²; and Yn - E. Pr(Z: 2; 1T,, we have that
vn a.s. Σ
Pr(Zi 2, Ze41 x1ix), Σ Pr(Ze 11 = 2; 1t)
(19)
Consider the function f :R? + R, defined as:
IR?
if y + 0
f(z,8) =
y
(20)
P
n. (2, 22)
otherwise.
Note that discontinuities of f may occur when y = 0. Applying the continuous mapping theorem, have that
f(Vm) ns, E, Pr Z,+1 z';
(21)
Σ. Pr = =;
Pr Σ Pr(Z == =0
(22)
In our case, E, Pr(Z, 2; T) is constant, and so the condition in Equation 22 is simply:
Σ Pr(Zi 2; T) # 0.
(23)
Also, Equation 21 can be simplified to:
na (2,)) ns (z)
(24)
since S(V.) X./Y, = Pa n. (z, and Pz
E, Eu1 by Equation 3
E. P.(2.220)))
Restating this conclusion, we have that
Σ Pr(Zi 23 2; #0,
(25)
then
Po (2,2)) as, 2)(2,2)
(26)
which establishes the property.
Next, we present property that establishes the almost sure convergence of the reward function estimate.
This condition arises due the discontinuity when the second argument zero. See the statement of the continuous mapping theorem in Appendix A for details. "To be more precise (()..) X..Y. when Y.. * 0. However, when Y.. 0, the conclusion that
(WV)) (2, z²) holds from the definition of f in Equation
19

---

Property B.3. For all abstract states E 2, if
Σ Pr(Ze = 2; T) + 0,
(27)
then
R R (z) - (2).
(28)
Proof. Recall that
- E, 1(
R (2)
Σ 2,14
Let X, - = 2) and Y, = , Σ E, 1 = =]. We will show that X,, and Y, converge almost surely, and then apply the continuous mapping theorem reason about the almost sure convergence of (2).
To ensure that the ARP is well-defined even when 2 is not empty, for abstract states E (abstract states that were observed in the data), the reward function can be set to R (2) 0, elaborated in the proof of Property B.2
Consider lim, x X
1
lim Xn = lim
1(2
R
n-000
(=1
lim n=+00
Σ
112 = 2)
1=1
Note that 1[2; R} is independent across episodes (for each has bounded variance, and has the same mean for each episode. By Kolmogorov's 's strong law of large numbers [66].
11 = R}
E [12 = =2
Y2
Σ
Pr(Rt -1 2)r
EER
Pr(Rt = 2;
PER
Pr(R: R3 = 24 12;=;;
Pr(2 2;
E R
Z. 21 Pr(Z, 21 T).
This convergence guarantee holds for all t. As in the proof of Property B.2 by the countable additivity property of probability measures, in conjunction with the dominated convergence theorem [16] Theorem 1.19], this implies that,
lim Pr
11 = =
Σ E [ Ze 2 2; =1. (29)
Returning to a.s notation, this means that
X E R 2: ,; Pr Zz = 2²
(30)
Similarly, these same exact steps can be followed to show that
Y,
Σ
Pr(Z, = 2; T).
(31)
20

---

Let V, = (X,, Yi), so that V. ()) is sequence of vector-valued random variables. Considering the function f R² + R. defined as:
y 0
f(z,))=
(32)
R
otherwise.
Note that discontinuities of / may occur when y 0. Applying the continuous mapping theorem, we have that
f()n) 2 E, E.
Ze = 2: Pr(Z, 2;
(33)
Σ, Pr(Z nT
Σ Pr(Zt 2; T) # 0.
(34)
Thus, when Σ, Pr(Z, = 2; =0 0
RC (z) u.s. (2),),
(35)
which establishes the property.
Next, we present a property that establishes the almost sure convergence of the initial state distribution.
Property B.4. For all abstract states z E Z, fm) "i no(2).
Proof. Recall that
1 n n Σ 1 =).
Let X,, : 1(Z6 = z}. We will show that X,, converges almost surely, and then apply the continuous mapping theorem reason about the almost sure convergence of (z). Note that even when / is empty, the definition of The ensures that is well-defined. Consider 1im X
lim X, lim n-00c =
Σ
1 =
1m
Note that 1 176 >} independent across episodes (for each i), has bounded variance, and has the same mean for each episode. By Kolmogorov's 's strong law of large numbers [46).
1
1
=} a.s. E [7 =}] = Pr =).
In contrast the proofs of the previous two properties, this proof holds for 2, not just the abstract states that have non-zero probability of occuring. This implies that
(2)
a.s. n²(2),
(36)
which establishes the property.
Having established properties that will be useful in the proof of Lemma 3.2 we now turn to proving the lemma.
Lemma 3.2 Vó E d, the expected return of the maximum likelihood estimate Pi converges almost surely to the expected return of the policy n, i.e., [m; Ae Rt. 2s, J(z; M).
Proof. From Theorem we have that [1;; Rgg) [[;; .). Thus, to prove this result, we only need show that J (T;; SA
as this result provided in Properties B.2 B.3 and B.4 Specifically, Properties B.2 and B.3 establish
[i: R Several of the preliminary results required estalish
that for all abstract states z E 2 and
7 E if
Σ Pr(Ze = =; O,
(37)
21

---

then
P (2,2) 2) un, (2 2)
(38)
and
(z) us (z).
(39)
Similarly, Property B.4 establishes that for all abstract states E 2,
a.s. n5(2).
(40)
The expected return [T; R n (m;;R)))) (I (T- n.o) Rg Mn. Σ. E. = 2; R (2 where Pr denotes the empirical estimate of the corresponding probability.
) is a continuous function of n.. == (P
n. R o), given by
Note that the term >. Pr(Z, π) (1-Piis) n..s)
ni i.e., the empirical estimate of the sum of probabilities of encountering the abstract state 2 over all timesteps is equal to value of the
vector (I-P7. Pr n, o at z. By the continuous mapping theorem, if E, 2; + 0,
Σ Pr(Zz = =; a.. Σ -
(41)
Let Er 2; 0}. -) where Z Z. be the set of abstract states that will never be observed empirically as they have no probability of being visited under π The expression for the expected return can be divided into two terms: (1) the first term sums over abstract states for which E. Pr(Z, π)) O, and the values of the components of the ARP-in particular, R R have been specially hardcoded as detailed in Property B.2 and (2) the second term sums over the abstract states for which Σ, Pr(Z, = 2; T) # and thus Equation 41 holds.
(T; = Σ> ΣDO
Pr(Zi = m) R (z) +
Σ #EZ
Σ
Prize= 2;
(42)
=EZ t
Σ
Σ
Pr(Ze 2i 2, 22
(43)
2EZIZ
for E 2 and thus V2 Z, making the first term equal to zero. The constituents of the second term converge almost surely:
As detailed in Property B.2. R (z) R
Σ 2
Σ
Pr(Zz 2: m R)
as.
Σ
Σ
Pr(Z. 2; R5))
(44)
=EZ/2
Σ
Σ
Pr(Zi = 2 (2))
(45)
=EZiZ
Σ
Σ
Pr(Zi 2; + Σ
Σ
Pr(Ze 2i
Rg(2)
2EZ
(46)
ΣΣ = =
(47)
JEZ
= =] Rg).
(48)
We then obtain the final result: [T:; Si
asy J[T = M)=
(49)
*Termination handled as detailed in Appendix A.1
"In relation to Ž defined in Property B.2 note Z C Z. As n. + oo the two sets, with probability 1, become
equal.
22

---

B.3 Estimation of ARPs from Off-Policy Data
So far, we have shown that the expected return the estimated ARP converges almost surely the expected return of the policy that induced it, i.e., consistent on-policy evaluation. Next, we show that a model of the ARP can be consistently estimated from off off-policy data. This requires us to prove that transition functions estimated using off-policy data, incorporating importance weights in their estimation, converge almost surely to the true transition functions induced by the evaluation policy, and that the same holds for the reward functions and initial state distributions.
Property B.6. For all abstruct states z E and 2, if
Σ Pr(Z, = 2; mb) + 0,
(50)
then
T (2, an p (2,
(51)
Proof. Recall that
P (z, Ei,t 11 2'P n2
Ei, 1p
Similar to the proof structure of Property B.2 let X, = "o - P' and Yn
n EE,, 1 For abstract states 2 c that are never reached and thus are not observed the data, special values can be hardcoded into the transition function, reward functions, and initial state distribution so that the components of the ARP continue to be well-defined. In particular, for - E Z, the transition function can be set to self-transition back to Σ with probability 1, i.c., PT (2, 2) = 1 and P (2, 2) 0 for all & 2, the reward function is set to R (=((===()))))))))))))()) = 0
and the initial abstract state distribution is Tn To (2) = 0 for all & E Z. Consider lim, 7 X
lim Xn lim Σ
1 1 2' poo
1,
n 11 z' 2'0,,==3p000
lim Σ +00
Note that 1; 2') is independent across episodes (for each i), has bounded variance, and has the same mean for each episode. By Kolmogorov's 's strong law of large numbers [46),
n 1222 pu. -
Σ
[1 Zt+1 2 2'}poss: mb).
n2
The importance weights change the distribution over which the expectation is computed, as below:
E [1[2, = 2, Z++1 = 2'TPuss5 Te]
II (S, A))(SS An, S(11) ((6())))=.((((4))))) (S Aj) (S Aj)
Σ Σ
((S))
So4t1: Anis
1=
Σ Σ
((S)) II
ग.. (S, Ai)pAs)sssss..)) A Sw1)) ((0(5))=2,(((++1)-
So1+1:
1=0
Anis
Σ E = =
This convergence guarantee holds for all f. By the countable additivity property of probability measures in conjunction with the dominated convergence theorem 16). this implies that,
X a.s.
E [1 = 2, Z = z' 2 me].
(52)
23

---

Similarly, these same exact steps can be followed to show that
Yn 2..
Σ E [1(z = =);
(53)
Let V. (X,, Yi), so that V, (X,, == sequence of vector-valued random variables. Considering the function f / R² + R, defined as:
if y + 0
f(x,u) v Te (2,2")
(54)
P n,
otherwise.
Note that discontinuities of f may occur when y = 0. Applying the continuous mapping theorem, we have that
(()),) E, E11Z Ze-1 mel
(55)
E. 1 2 = 2}: Te)
Σ [1 = me] # O. This implies that
(2,2') - p 22,
(56)
when E, Pr(Ze= 2; mb) # 0, which establishes the property.
Next, we present the properties that establish almost convergence of the reward funetion estimate and the initial state distribution estimated from off-policy data. This follows similar proof structure to their corresponding on-policy properties, with the key difference being the use of importance weights in the estimation.
Property B.7. For all abstruct states z E 2, if
Σ Pr(Ze = z; Tb) + 0,
(57)
then
R (z) ane R5 (2)-
(58)
Proof. Recall that
E1 Ee 1 = 2 R2
R R the (2)
Σ E, P0.2
Let X, - Σ.
1
2 Ripprt and Y, = Σm 1 = =]po.t. Following the
exact steps from Property B.3 we can show that
n Σ 10 -
" [12 = =) RePos3m)
n 1=1
1[2 = Re: Te]
Σ
Pr(R, r, Ze = 23 1e 2)r
rER,3E2
Σ
Pr(Re = r, Ze 2;
PR
Σ r Pr R4 = Ze =; =
APRR
EE
[Re]
Z, = 2; π| Pr = 2; T.)
This convergence guarantee holds for all f. By the countable additivity property of probability measures, in conjunction with the dominated convergence theorem, this implies that
X
R Z₁ = 2; me| Pr(Ze = 2; Re).
(59)
24

---

Similarly, these same exact steps can be followed to show that
Yn _ Pr(Z, 2; me
Pr
(60)
Noting that R Xe, n.o Y,
we can apply the continuous mapping theorem, as done in the proof of
Property B.3 to show that
(z)
R (=),
(61)
n,
when E, Pr(Ze 2; mb) #b)
Property B.8. For all abstract states E 2, 7n
(z)
R...
7 (z).
Proof. Recall that
nn
(2)
Σ
114 20.0
t=1
Let X, = Ei= 1(76 = po- Following the exact steps from Property B.4 we can show that
( = =} شيكة E [1 = =) = Pr(Zo = z).
n
This proof holds for all z E Z. not just the abstract states that have non-zero probability of occuring. This implies that
p (2)
no (z).
Lemma 3.3
Under Assumption 2.1 the weighted maximum likelihood estimate Ro
converges
almost surely to the ground-truth ARP R i.e., R. a.s. 9 T
Proof. The results required establish this result provided in Properties B.6 Specifically, the properties establish that if
B.7 and
B.8
Σ Pr(Z: = 2; m;) + 0,
then
(z,z²)
2
ax. pie (7 z');
R
Ma- (2) 3 (2)(2); (2) n²()),
giving the final result TT 0.6
as R while the values of the components for z 2 are hardcoded
as detailed in Property B.6
B.4 Off-Policy Evaluation with ARPs
Theorem 4.1 The expected return of the ARP Ri (built from off off-policy data) converges almost
surely to the expected return of Te, i.e., ( R ( ax ( M).
Proof. The expected return J Pina is continuous function of R 2i
(P=.- R R Mno - given by J [mT: D "T)) (I -I-Pa p ilar to the proof of Lemma 3.2 by the continuous mapping theorem and Lemma 3.3 final result that enables off- policy evaluation with ARPs:
n,
R
the -T
Nn.o
Sim-
we obtain the
J (TT2 R 2s [ 25 (TT,
25

---

B.5 Variance Reduction: Leveraging Markovness of the State Abstraction
Variance in estimation of the model of the ARP from off off-po can be reduced by clipping the importance weights. We now show that when the state abstraction function is e-th order Markov, clipping the importance weights to the e most recent terms continues to provide a consistent off-policy expected return estimate.
Theorem 4.3 Given e-th order Markov o, the expected return of the abstract reward process
R -H converges almost surely to the expected return of Te, i.e., J [ 6. R -s, J (TT M).
Proof. We only need to show that for a state abstraction function & that is e-th order Markov,
i.e.
(1-41))
for क E (To; ] the following holds:
TT D.S. A
The remaining steps to show that the return estimates consistent follow from Theorem 4.1 For brevity, we denote by Z, == ((S) for the rest of the proof. Consider the expression for the transition function without any weight clipping,
a the (2,2))== == Ei 1222,2'
Ei, 11(2)
As shown Property B.6 E. Pr(Z, 2; mb) # 0, as n + oc the numerator of P *(= z') Σ, E [14 = z, 1, = z' Pasi To]. When the abstract states are e-th
n.
converges almost surely to
order Markov,
Po)(t-c)+ 1 P(t- : conditioned on
(63)
Using the tower rule 660 E (Z, 2, Zu+1 Poiti To] can be re-written as:
E [ Z2 2, Z 2' 2'}oo:t: mb]
=E
[[, = z, Z++1 2 2') P P(t- mb]
=E
E
1124 = 2, 2 = z' P')poitte-o) 1 P(t-o+1))a (z)) 5
E
1[Z, 2, Z =')p(e-ctt)+d
(Zi) mb E
Po:(t-o)+ I (Z)) mmb
=E
EE
[12 2, 7,11 ='')((ecct)++
(Z)) mb
[EE [Poct--))+ (2,1) i Tb
IE
=E [1 = 2, Zt+1 2 1)t To
E
(Po((t-o)+:
Pr(Ze 2, Z(+1 Te)
where (a) follows from Equation 63 and (b) follows from Lemma 3.3 Thus when the abstract states c-th order Markov, the numerator estimated with c-clipped importance weights almost surely converges to the same value as if the importance weights were not clipped. The value to which the denominator converges similarly undergoing change of measure by the use of clipped importance weights, i.e.
[1 = P).o my) E [1 = =)P(t-cttttuim) = Pr(Ze = =2;,e),
(64)
when @ is c-th order Markov. Note that the expression for f86-t5 is: 0.c
" == Ex, 11 2(H2)3/P(0-ct)1-
Ei. 1;(2)((--ct))-
26

---

Let Xn = EE 11f2, 2' Plte- and Y, = - P((2) We can write 0,c (,,") =
Xa, Following the exact steps from Lemma 3.3 that entail a careful applica- Yn
tion of the continuous mapping theorem, we can show that
P (2, u.S. (2,
E Pr(Z: - z; mb) of Similar derivations can be followed for the reward function and the initial state distribution, leading to the required result:
T 2%
when Σ, Pr(Zt = 2; mb) # 0, that enables almost sure convergence of the expected return estimate:
[Te R5,
ni, :T)) = M))
27

---

C
Empirical Details
In this section we provide additional empirical details for the experiments presented in the main paper. An overall step-by-step algorithm for STAR follows:
Algorithm 1 Overview of STAR(Ø, c)
Input: Tei Wb, D m66
1. Apply state abstraction to (T)) and compute importance weights:
(.( .100) Pl -(o-ott)+tt - -Ij-a-+t)) Fo(s) .A.))
Vi Store
2 = (
A
Ri
2. Estimate the components of the ARP TA 0.C
9 P
P
RT T where,
P.C
0.c
0.c
E. 160(8)0)
21 (2 Jeg enata
p
6.c
E., (0((8) = aa-et
Σ., 1(d(s))) )= p
R
En, (((() )= enatta
En 1(0(8))) 1==]
No. Th (2)
3. Compute the expected return [TT (x) from the ARP.
Pr p
16.c
Output: (Te; Nsc -)))
C.1 Domains
We perform empirical evaluations on a range of domains that consist of continuous domains and domains with large state spaces with long horizons. The domains are as follows:
The CartPole domain a classic control problem from OpenAl Gym G The task is to balance pole on cart by moving the cart left or right. The state space is continuous, and the action space is discrete. We use the standard CartPole environment from OpenAl Gym. In the experiments, is uniformly random, i.e., the left and right actions are each taken with probability 0.5. The evaluation policy Te is a policy that takes the action right with probability 0.9 when the pole is leaning left, and right with probability 0.1 when the pole is leaning right. This results in a policy that is not optimal, but is somewhat successful at balancing the pole.
CartPole
ICU-Sepsis The ICU-Sepsis domain simulates the treatment of sepsis in the ICU. Built from the MIMIC-III database [24] and drawing from the analysis of Komorowski al. (26). it consists of 747 states that denote the status of a patient and 25 possible actions that denote possible medical interventions. At the end of each episode, if the patient survives, reward of +1 is given, while death corresponds to a reward of 0, with all intermediate rewards also being O. This results in the expected return of policy corresponding the experiments, is set to an expert policy, provided with the domain and included in the submitted codebase, while m, is policy that is more stochastic version of the expert policy constructed by temperature scaling 17 the action probabilities of expert policy with temperature parameter 2.
the probability that randomly selected patient will survive. In
Asterix The Asterix domain is a miniaturized version of the Atari game Asterix where the task is to collect items while avoiding enemies. We use the implementation of the game from the MinAtar testbed (61, where the dimension of each state is 10 10 x 4, and the action set consists of six actions. The data collecting policy T, uniformly random, while the evaluation policy n picks actions with con-uniform skewed probabilities.
28

---

C.2 Additional Results for Estimator Selection
CartPole
n.2 50
500
1000
10000
323
120
120
320
Tog MSB
log Mor
Asterix
m 50
500
1000
10000
Lug HSC
Iop MSG
Iop MGE
100
ICU Sepsis
= 50
= 100
n- 500
5000
[2]
Figure 4: Heatmap of the log mean squared error (MSE) of the OPE estimators for the CartPole, Asterix, and ICU-Sepsis domains. The vertical axis represents the number of abstract states |2], and the horizontal axis represents the value of the hyperparameter The color intensity indicates the log MSE, with lower values denoting better performance. Note that the variation with [2] is strongly influenced by the class of abstraction functions used, which in this work is CluSTAR.
For each domain, evaluate the OPE performance of the estimated ARP induced by varying configurations (ó, c). For the class of abstraction function, we observe that the simple method CluSTAR performs well across all domains, and hence use it for all experiments. CluSTARtakes an input a single hyperparameter, the number of centroids initialized, denoted by |/. We evaluate the following configurations of 2 and for each domain:
1. CartPole: 35 estimators | E (2, 4, 16, 32, 64, 128), c (1,2,3,4,5}.
2. ICU-Sepsis: 25 estimators ||| E {2, 8, 16, 32), E {1, 3, 4, 5). ICU-Sepsis with 32 and n 5000 is excluded for computational reasons.
3. Asterix: 25 estimators
{2, 4, 16,32) 32), (1,2,3,4,5).
In Figure we report the log MSE for each estimator.
Effect of 22 For the class of abstraction functions induced by CluSTAR, the effect of [Z] varies across domains. In some domains, such as ICU-Sepsis, the estimators obtained by varying this hyperparameter show similar performance. However, domains like Asterix and CartPole, performance is more sensitive to the choice of 2 with larger values performing better.
Effect of c: is expected that large values of e will lead to higher variance of the estimates. low data regimes, small values of result in relatively lower MSE the variance is lowered at the cost of increased bias. As the amount of data increases, the best value also increases. This effect is most pronounced in the Asterix domain, and to lesser extent in the CartPole domain.
The key takeaway from Figure that the optimal |Z| and are function of the amount of data (n), the characteristics of the domain and the class of abstraction functions used.
C.3 Compute
All experiments were run for 200 seeds each, on domains in total. Fach run took between hours to 3 days (depending on the domain) and this duration includes offline data collection. The experiments
29

---

were run using 32 threads on Xeon E5-2680 CPUs on computing cluster, bringing the total compute time to roughly 45000 compute hours.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims are contributions are supported by corresponding theorems and empirical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are highlighted both in the concluding discussion and separate "Limitations" section in the supplementary material.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
31

---

Answer: [Yes]
Justification: All proofs are provided in the supplementary material, and assumptions states clearly in the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The code has been included with the submission. Random seeds are set and fixed across multiple trials, along with the source code of the domain used.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
32

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification; Anonymized code is submitted as .zip file with the submission. The codebase will be made public upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
aablic/guudees/Codeebbbmsss wtw.ooeeeesuoiiiiooooooooioogggo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wwtps/cccpbplgguuuuaeeeeae Stteee///ooSSSeeissSiSi.a www.ssssiicggsooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: There specific section, in the main text and supplementary material, dedicated to choice of hyperparameters along with necessary experimental details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Standard error is reported for main experiments, with the number of trials specified.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
33

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details about the compute resources are provided in the supplementary mate- rial.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp///eerrpp..c//bbb/////iiia
Answer: [Yes]
Justification: Naive application of the framework to safety-critical applications could lead to unintended consequences. A discussion on the limitations and potential impacts of the proposed framework provided in the supplementary material.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Both positive impacts, in terms of strong results for OPE and potential negative impacts, in terms naive application of the framework to safety-critical applications, are discussed in the paper.
34

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Original creators of all domains used and all prior work are duely cited in the paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
35

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thood cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
The code and related artifacts, such as pre-trained policies, are well documented and provided alongside the submission.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
36

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "SYnKaf8CLu", "reviewer": "Reviewer_oq5d", "summary": "This paper studies the problem of Off-Policy Evaluation (OPE), which consists of estimating the value of a policy $\\pi_e$ from an input dataset generated from another behaviour policy $\\pi_b$. One naive way of constructing the estimated return of $\\pi_e$ would be to compute its associated empirical Markov Reward Process (MRP) in the MDP, then apply importance sampling to it. Instead, the technique proposed in the paper is to apply importance sampling to an abstract MRP obtained via some discrete abstraction function. This technique has been validated with theoretical results, and with an experimental comparison against other baselines.", "questions": "4. How did you obtain the probabilities of the behaviour policy for the ICU sepsis dataset?\n5. Which of the baselines assume complete knowledge about the behaviour policy?\n\nThe authors may also address any of the points raised above.", "limitations": "The authors listed all the most important limitations of this work. The contribution has no direct societal impact and it does not require further discussion regarding negative impact.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "(Idea and contribution) The core idea, that is marginalizing states into abstract MRP, is simple. However, it requires special care in selecting appropriate abstract representations that allow lossless evaluation of arbitrary policies. As confirmed by Theorem 3.1, this is indeed the case for the ARP defined in the paper (though it should be noted that this strongly relies on $\\gamma = 1$). From Theorem 3.1 all the other results follow, which verify that the proposed technique is sound for *any mapping function*. The fact that \"actions propagate through the abstract state transitions\" (line 227) is also a very interesting addition, that contributes to the application of importance sampling. Summarizing, the theory developed in the paper is an elegant display of the abstraction process for OPE, and a sound use of HRL principles.\n\n(Evaluation) The technique has been compared with a good number of relevant baselines from the literature. The results show that the proposed estimators have competitive or better performance than their competitors. The authors also reported the median estimator. Even though it is not always the best estimator, this addition allows to have a clearer picture, and it was evaluated positively.\n\n(Presentation) The quality of presentation is high. Each new technical definition is well motivated, and the paper is reasonably self contained.\n\n(Reproducibility) The authors provided the full source code at the time of submission. The hyperparameters are also provided.", "weaknesses": "1. The theoretical results show that the method is sound and any estimator constructed as explained in the paper is an unbiased estimate of the true value.\nHowever, the paper does not provide any theoretical result regarding the reduction in variance, which is the second motivation of this work. This is only confirmed experimentally in some domains.\n\n1. No finite samples analysis has been conducted. Thus, when considering datasets of finite size, no theoretical result regarding the approximation error is available.\n\n1. The method assumes to explicitly know the behaviour policy that generated the data. This is a strong limitation that has been also listed by the authors in the limitation section. This did not contribute heavily to the final score.\n\nMinor:\n- There are some typos in the use of z and z' in equation (2) and in the proof of Theorem 3.1.\n- If accepted, I suggest to use the additional page for explaining the missing details of the experimental evaluation, such as:\n  - How is the MSE for OPE exactly defined\n  - How is the variance-bias measure is constructed for Figure 3.\n  - List Algorithm 1 in the main body", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your careful review of our paper and insightful comments. We appreciate your positive assessment of our contributions and the clarity of our presentation. We address your questions and comments below.\n\n> How did you obtain the probabilities of the behaviour policy for the ICU sepsis dataset?\n\nThe behavior policy is constructed by increasing the temperature parameter to the logits of an expert policy, making it more stochastic. The expert policy weights are provided provided with the ICU-Sepsis benchmark. Behavior probabilities are obtained by querying this modified behavior policy.\n\n> Which of the baselines assume complete knowledge about the behaviour policy?\n\nWe thank the reviewer for pointing out the shared assumption of a known behavior policy among the baselines. All baselines, other than fitted Q-evaluation (FQE), assume knowledge of the behavior policy. Variants to some methods have been proposed where the behavior policy is empirically estimated [1], introducing some bias in estimation, and we expect these to be a straightforward practical extension to STAR.\n\n> Theoretical proof for variance reduction\n\nThe framework of STAR encompasses a range of estimators, controlled by $(\\phi, c)$, each configuration of which instantiates a specific estimator. The efficacy of variance reduction of these estimators is inherently linked to the problem of *abstraction discovery*. Different combinations of abstractions and weight clipping factors yield varying degrees of variance reduction compared to standard OPE, with some configurations potentially not offering any reduction. For instance, weighted per-decision importance sampling (WPDIS) and approximate-model MRP (AM-MRP), representing the end points within STAR (ref: Section 4.2), cannot, in general, be ordered by their variance. Similarly, estimators that lie in between may exhibit significantly lower or higher variance and MSE. We assert the *existence* of such low variance estimators and provide empirical support for this claim.\n\n> Finite sample analysis\n\nA finite sample analysis would necessitate an extension of the simulation lemma [2] for ARPs defined from finite-horizon MDPs. Subsequently, the policy value estimation error can be bounded in terms of the estimation errors in the transition and reward functions of the estimated ARP. Such an extension to the simulation lemma would be a valuable theoretical contribution independent of its application to our work, and represents a promising direction for future exploration.\n\n> Minor\n\nThank you for the suggestions, we shall incorporate these points in the additional space in the updated version.\n\nWe hope we have addressed your concerns, kindly let us know if you have any additional questions.\n\n---\n\n[1] Hanna, Josiah, Scott Niekum, and Peter Stone. \"Importance sampling policy evaluation with an estimated behavior policy.\" International Conference on Machine Learning. PMLR, 2019.\n\n[2] Kearns, Michael, and Satinder Singh. \"Near-optimal reinforcement learning in polynomial time.\" Machine learning 49 (2002): 209-232.", "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": "", "extra_scores": {}}, {"review_id": "mx8jCAn9Lo", "reviewer": "Reviewer_V4gu", "summary": "The paper introduces a new framework, STAR, for off-policy evaluation (OPE). OPE uses a chain with rewards (MRP) to conduct the evaluation. The challenge of this methodology is that the MRP estimation can introduce bias, given the shift between the behavior policy and the policy for evaluation. STAR is designed to address this challenge. STAR projects continuous state space to a tabular space and introduces the abstract reward process (ARP), which refers to the MRP over an abstract state space. The tabular abstract state space reduces the difficulty of reward prediction, thus eliminating the model class mismatch in prediction. It is proved in the paper that projecting states to a discrete space preserves the return.", "questions": "Please see the concern above", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper makes good contributions by proposing a new framework for off-policy evaluation. The proposed method is analyzed in detail with both mathematical proofs and empirical evaluations.\n\n* The introduction clearly lists the challenges and contributions, as well as provides a subsection for an overview of the new method. The way the introduction is organized tunes to be helpful for better understanding.\n\n* For the introduced step, abstracting continuous states with a tabular space, the paper explains the advantages clearly. The paper also provides mathematical proof to explain why this step is not considered as a source of error.", "weaknesses": "* Theorem 3.1 proves why state abstraction preserves the return with a known reward function on the abstraction state space, but it remains unclear how the state abstraction increases the difficulty of learning the transition model for predicting the reward and the next state, and possibly also introduces stochasticity. Assuming the true MDP has $P(r_0, s_1| s_0, a_0) = 1$ and $P(r_1, s_3|s_1, a_0)=1$, if the state abstraction projects $s_0$ and $s_1$ to the same representation $\\phi_0$, which is possible because the latent space is tabular. Then, the model will have to simulate a stochastic transition with probability $P(r_0, s_1 | \\phi_0, a_0)=0.5$ and $P(r_1, s_3 | \\phi_0, a_0)=0.5$. Therefore, it seems how accurate the evaluation is heavily depends on how good the state abstraction is. If so, it would be good to point out in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for taking the time to review our paper, and appreciate your recognition of our work's contributions and analyses. Your observation regarding differing ease of model estimation across various abstractions is insightful, as detailed next. We have updated the paper to include this point.\n\n> Theorem 3.1 proves why [...] in the paper.\n\nAs correctly pointed out, in some cases abstraction by aggregation of states can increase the difficulty of estimation of the transition function (ref: `Note A`). However, in general, state aggregation tends to simplify estimation by increasing the effective sample size [1]. \n\n`Note A:` For example, aggregation of two states with deterministic transitions -- which can be estimated perfectly from a single observation of those transitions -- creates stochastic transitions between abstract states. For these states, the abstraction function being the identity mapping is preferable to one that is a many-to-one mapping.\n\nAs per Theorems 3.1 and 4.1, MSE for OPE using STAR converges to zero as the amount of data increases, regardless of the abstraction function used. However, the rates of convergence can vary with the choice of abstraction. This highlights the need to consider additional factors, such as the ease of estimation and dataset size, while selecting an abstraction in STAR.\n\nWe appreciate you pointing out this subtlety and hope we addressed your concern. We have updated the paper to include this point - kindly let us know if you have any additional questions.\n\n---\n\n[1] Jiang, Nan. \"Notes on state abstractions.\" (2018) URL: https://nanjiang.cs.illinois.edu/files/cs598/note4.pdf", "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": "", "extra_scores": {}}, {"review_id": "jHO0c48y5t", "reviewer": "Reviewer_5Mtw", "summary": "The authors introduce a new framework that groups the states with a similar reward, hence reduces variance of any applied OPE estimator.", "questions": "In [L212] you claim this is the first model-based OPE method that converges to a true policy value without any model class assumptions. How does your method compare to action clustering method of Peng et al. (2023)? This method factors action space instead of the state space, and regardless of the model class, it seems to converge to a true policy value.\n\nIn [L304], you suggest that performance can be improved even further by applying estimator selection methods. Moreover, in [L250], you mention there is no approach to discovering good abstraction functions \\phi. The recent work of Cief et al. (2024) might solve both these issues.\n\nReferences:\n\nPeng, Jie, Hao Zou, Jiashuo Liu, Shaoming Li, Yibao Jiang, Jian Pei, and Peng Cui. “Offline Policy Evaluation in Large Action Spaces via Outcome-Oriented Action Grouping.” In Proceedings of the ACM Web Conference 2023, 1220–30. WWW ’23. New York, NY, USA: Association for Computing Machinery, 2023. https://doi.org/10.1145/3543507.3583448.\n\nCief, Matej, Michal Kompan, and Branislav Kveton. “Cross-Validated Off-Policy Evaluation.” arXiv, May 24, 2024. http://arxiv.org/abs/2405.15332.", "limitations": "The authors extensively discuss the limitations throughout the work, for example, in Conclusions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The framework is technically sound, well discussed, the analysis is on point and addresses important questions, for example that regardless of the choice of state abstraction function \\phi, the overall framework remains asymptotically consistent. The discussion on how the framework translates to existing OPE methods when varying its parameters (\\phi, c) help show where the improvements of this framework lie.\n\nThe experiments are complete and show a strong empirical performance of this method.", "weaknesses": "Minor: [L548, L560, L586, L600, L609] \"See Appendix B\" is obsolete, we are already in Appendix B.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for taking time to review our paper and appreciate you recognizing the strength of the work’s theoretical and empirical analysis. We appreciate you pointing out additional relevant references, and address related questions below.\n\n\n> In [L212] you claim this is the first model-based OPE method that converges to a true policy value without any model class assumptions. How does your method compare to action clustering method of Peng et al. (2023)? This method factors action space instead of the state space, and regardless of the model class, it seems to converge to a true policy value.\n\nGroupIPS performs IPS on the clustered actions and is thus a model-free method, whereas our work involves approximating a model of the system, specifically, an abstract Markov reward process. The use of discrete state abstractions, in conjunction with tabular models, frees our method from requiring knowledge about the model class that can represent the underlying MDP. While the referenced paper does not seem to provide a guarantee for convergence to the true policy value (as per Proposition 3.3, the method is biased), our approach offers the theoretical guarantee of asymptotic convergence to the true policy value. \n\n> In [L304], you suggest that performance can be improved even further by applying estimator selection methods. Moreover, in [L250], you mention there is no approach to discovering good abstraction functions \\phi. The recent work of Cief et al. (2024) might solve both these issues.\n\nThank you for highlighting this reference on estimator selection for OPE. Holding out some off-policy data to estimate a proxy of the true policy value, using a validation OPE estimator, is a promising approach to abstraction selection. We will incorporate this reference and discuss its relationship to our work in the updated version of the paper.\n\n>  [L548, L560, L586, L600, L609] \"See Appendix B\" is obsolete, we are already in Appendix B.\n\nWe shall remove that text in the updated version of the paper.\n\nWe hope we have addressed your concerns, kindly let us know if you have any additional questions.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents an intriguing new framework, STAR, for consistent model-based off-policy evaluation (OPE) using abstract reward processes (ARPs). Theorem 3.1 is quite an interesting building block of the paper, allowing estimation of value under state abstraction. Reviewers agreed this paper is strong, and raised some concerns. A few points about the paper (not all points were raised by reviewers):

- The authors use tabular models for representing ARPs. While they argue that even small models can be effective, there is no analysis of how the complexity scales with the size of the original state space or the desired accuracy. For continuous state spaces, the computational cost of constructing the state abstraction is also not discussed. 
- While the paper provides asymptotic consistency results, it lacks finite-sample analysis. This makes it difficult to assess the practical performance of STAR for finite datasets. Finite-sample error bounds would be crucial for understanding how the estimation error depends on factors like the number of trajectories, the horizon length, the state abstraction function, and the weight clipping factor.
- The authors acknowledge that there is no principled method for selecting the weight clipping factor c. A theoretical or empirical analysis of how to choose c for different ARPs and dataset sizes would be beneficial.
- Although the authors claim that STAR often inherits favorable properties of both IS-based and model-based methods, they do not provide analysis of the bias-variance trade-off. How does the choice of abstraction and weight clipping factor affect the bias and variance of the ARP estimates? How does this trade-off compare to existing OPE methods?
- The authors should improve the overall related work section to include recent advances in OPE. There is vast amount of research on the combination of model and IS based approaches for OPE, contrary to what the authors claim in their paper.

Overall the authors have a novel and interesting result in the paper, though they do not go all the way in term of the analysis, e.g., finite sample analysis and / or bias variance bounds. This makes it difficult to theoretically compare to related work. The paper's empirical evaluation is good and greatly improves the quality of the paper. The paper is still in a borderline state, and I lean toward accepting it. I urge the authors to try to improve the paper as best they can for the final submission given the above comments and the other reviewer comments.
Decision: Accept (poster)