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_cc_2024_Conference
Published: 2024-05-13 20:30:17

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.

Main paper: 
 introduction: 
 Within reinforcement learning (RL), off-policy evaluation (OPE) is the foundational challenge of evaluating the performance, J(π), of policies π that are different from the ones used to generate data. OPE methods are a general-purpose tool that can be used as part of a local policy search algorithm [45] to provide insight about policies similar to the current policy, or as a tool to evaluate policies without requiring their actual deployment for high-risk applications like those in healthcare [38] , education [35, 15] , 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.Existing methods can be broadly divided into two categories: importance sampling (IS) based and model-based [58] . IS-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 we 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 us to ask: Can we develop a framework for OPE that yields predictions that are both consistent and low variance? A model of the ARP for the evaluation policy π e is constructed by: reweighting data generated by π b with importance weights ρ (middle), applying the state abstraction function ϕ, and performing weighted maximum likelihood estimation of the ARP (right). The expected return of a model of this ARP estimated from off-policy data is a consistent estimator of the expected return of π e .In this paper, we introduce a new framework that attains this goal by combining the machinery underlying IS-based and model-based approaches (not just their predictions). Our proposed framework is a fundamentally different approach to 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 is 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 a range of ARPs state-abstract reward processes (STAR).Idea Summary: A Markov 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 an 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 a behavior policy π b that differs from the evaluation policy π e . 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 continuous 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 as the abstract reward process (ARP), using tabular models. Since the ARP is finite, tabular models can represent it accurately, as depicted in Figure 1 (a). However, using a 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 an ARP estimated from on-policy data provides consistent estimates of the expected return of the behavior policy π b .Next, to estimate a model of the ARP corresponding to π e from data generated by π b , we reweight occurrences of abstract states in the off-policy dataset using importance sampling, see Figure 1(b) . 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-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 a healthcare simulator built from real-world 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 a 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-based 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) a generalizing framework that provides a fresh perspective on OPE by merging the machinery of model-based and IS-based approaches. The framework offers two tunable knobs, various configurations of which instantiate a range of OPE estimators with varying bias-variance characteristics.Existing model-free and model-based methods are special cases in this framework. 
background and notation: 
 An MDP is a tuple M := (S, A, p, r, γ, η) where S is the set of states, S t is the state at time t ∈ {0, 1, . . . }, A is the set actions, A t is the action at time t, p :S × A × S → [0, 1]is the transition function that characterizes state transition dynamics according to p(s, a, s ′ ) := Pr(S t+1 =s ′ |S t =s, A t =a), r : S × A → R is the reward function that characterizes rewards according to r(s, a):= E[R t |S t =s, A t =a], γ ∈ [0, 1]is the reward discount parameter, and η : S → [0, 1] characterizes the initial state distribution according to η(s) := Pr(S 0 =s). 1 A policy π : S × A → [0, 1] characterizes how actions can be selected given the current state according to π(s, a) := Pr(A t =a|S t =s). We consider finite horizon MDPs [49] where episodes terminate by some (unspecified) time T ∈ N-which is common in practical applications of OPE. For simplicity, we set γ = 1, allowing us to omit γ terms.For OPE, a dataset D := {H i } n i=1where each H i := (S i 0 , A i 0 , R i 0 , S i 1 , . . . ) represents an independent trajectory generated by executing π b . The performance of an evaluation policy π e is its expected return, denoted by2 EQUATIONThe problem of off-policy evaluation entails estimating J(π e ) with access only to data D(π b )n , generated by a behavior policy π b , without additional interaction with the MDP. To ensure that samples in D (π b ) n are sufficiently informative, we make the common assumption that any outcome under π e has non-negligible probability of occurring under π b . Assumption 2.1. There exists an (unknown) ε > 0 such that for all s ∈ S and a ∈ A, (π b (s, a) < ε) =⇒ (π e (s, a) = 0). Background: For a detailed review of OPE methods, we refer the reader to surveys by Voloshin et al. [58] and Uehara 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, E[f (X)], 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 (p(Y )/q(Y ))f (Y ), where p(Y )/q(Y ) is a term called an importance weight. This technique can provide unbiased estimates (i.e., E[(p(Y )/q(Y ))f (Y )] = E [f (X)]) and has proven effective for variance reduction in Monte Carlo sampling [44] and for model-free OPE in RL [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 [28, 43, 1] . A state abstraction function ϕ : S → Z lies in the set of functions ϕ ∈ Φ that map each state s ∈ S to an abstract state z ∈ Z. We consider abstraction functions that partition S into disjoint sets, where Z is a finite set.Notation: Indicator functions are abbreviated for clarity. For example,1 i t {z, z ′ } := 1{ϕ(S (i) t+1 ) = z ′ , ϕ(S (i)t ) = z} denotes the occurrence of abstract states z and z ′ at time steps t and t + 1 in the i th logged trajectory, with 1 i t {z} defined correspondingly. The expected return of π when obtained from O-where O may be the MDP, or an ARP-is denoted by J(π; O). The sample estimate of a variable y estimated from n samples is denoted by ŷn . Summation limits are often dropped for brevity, with t denoting T t=0 and i denoting n i=1 .A Markov reward process (MRP) extends the idea of a Markov chain by associating states with rewards. Formally, an MRP is a tuple (X , p, r, γ, η) where X is the set of states of the MRP, X t is the state at time t, p : X × X → [0, 1] is the transition function where p(x, x ′ ) := Pr(X t+1 =x ′ |X t =x), r : X → R is the reward function where r(x):= E[R t |X t =x], γ ∈ [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 set γ = 1.A specific MRP is induced by the use of a fixed policy π on an MDP M , where X = S. The resulting transition and reward functions, denoted by p π and r π respectively, are:EQUATIONThe Markov property [37] allows for further simplification of the above expressions (detailed in Appendix A.1), 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 a state abstraction function ϕ ∈ Φ.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 as a separate "Limitations" section in the supplementary material.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
abstract reward processes: 
 An abstract reward process is a Markov reward process-derived from MDP M and policy π and 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.ϕ : S → Z, the ARP R π ϕ is defined such that X = Z. Formally, R π ϕ is an MRP (Z, P π ϕ , R π ϕ , η ϕ ), with γ = 1 (see Appendix A.1 for a discussion on termination in ARPs and MRPs). The components of the ARP are defined over abstract states as:EQUATIONand η ϕ (z) := Pr(ϕ(S 0 ) = z). These expressions cannot be simplified further, unlike the case of an MRP [2] . Since Z is a finite set, i.e., the abstract states are discrete, the components of the ARP can be represented by matrices (we use uppercase letters to emphasize this). The expected return of R π ϕ can be computed efficiently using a linear solver to evaluate the expression J(π; R π ϕ ) := (I-P π ϕ ) -1 R π ϕ η ϕ , 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. ∀ ϕ ∈ Φ, the performance of a policy π is equal to the expected return of the abstract reward process R π ϕ defined from MDP M , i.e., J(π; R π ϕ ) = J(π; M ). Proof. See Appendix B.1.The result holds for the ground-truth ARP R π ϕ . In practice, a model of the ARP must be estimated from data. Next, we describe how the choice of defining an ARP over discrete abstract states eliminates model class mismatch, enabling asymptotically correct estimation of the ARP from data.Eliminating Model Class Mismatch: 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, a neural network parameterizing a 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 an 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, or 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.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 to 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-preserving, ensuring that the use of discrete state abstractions is not a source of error for policy evaluation. Additionally, since we have eliminated model class mismatch, a perfect model of the ARP can be asymptotically estimated.To estimate the ARP from D n to map them to the abstract state space. Denote the maximum likelihood estimate of the model of the ARP obtained from the dataset (with abstract states) by R π n,ϕ :=(Z, P π n,ϕ , R π n,ϕ , η n,ϕ ). The components take the form:EQUATIONAsymptotic Correctness: With access to on-policy data D (π)n , the following result states that ARPs enable consistent model-based estimation of the policy's performance. Lemma 3.2. ∀ϕ ∈ Φ, the expected return of the maximum likelihood estimate R π n,ϕ converges almost surely to the expected return of the policy π, i.e., J(π; R π n,ϕ ) a.s.-→ J(π; M ).Proof. See Appendix B.2.As the amount of data (n) increases, the estimate of J(π; M ) becomes increasingly accurate, i.e., the return estimate is consistent. This result holds for all ϕ ∈ Φ. It implies that even an arbitrarily small model derived from a 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.We present a method for consistent estimation of the ARP corresponding to the evaluation policy π e from off-policy data D(π b )n . It relies on the following intuition:The expected value of the indicator function of an event represents the probability of that event.Use importance sampling to approximate the probability of that event under a different distribution.To estimate an ARP from off-policy data, assign importance weights ρ 0:t to the abstract states(Z t := ϕ(S t )) in the dataset D (π b )n . Let H t := (S 0 , A 0 , R 0 , . . . , S t-1 , A t-1 , R t-1 , S t , A t ) denote a sub-trajectory up to time t. The importance weight ρ 0:t is then the ratio of the probability of H t under π e and π b , i.e., ρ 0:t := Pr(Ht;πe) Pr(Ht;π b ) = t j=0 πe(Sj ,Aj ) π b (Sj ,Aj ) . 3 The maximum likelihood estimate (MLE) of R πe ϕ obtained from the weighted off-policy data is denoted by R π b →πe n,ϕ:= Z, P π b →πe n,ϕ , R π b →πe n,ϕ , η π b →πe n,ϕ, where η π b →πe n,ϕ(z) = n i=1 1 i {z0=z} nremains unchanged, andEQUATION)This estimation is a form of weighted maximum likelihood estimation [13] . Including the importance ratios in the numerator and denominator of the estimated transition and reward functions of the ARP enables estimation from off-policy data generated by π b . The estimated model of the ARP is consistent and, as shown next, allows for consistent off-policy evaluation. -→ J(π e ; M ).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 of the starting goals-that of consistency. However, the use of importance weights ρ 0:t for weighted MLE is expected to introduce high variance. Next, we discuss methods to mitigate the variance of IS.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: Anonymized code is submitted as a .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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
variance reduction: leveraging markovness of the state abstraction: 
 A common technique for mitigating the variance of IS-based methods for OPE is clipping the importance weights to the c most recent ratios [18, 3, 20] , i.e., ρ (t-c+1) (Si,Ai) , where (t -c + 1) + := max(t -c + 1, 0). This is often a bad approximation for classical IS-based methods, as it implies that only the c 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 a more reasonable implication of weight clipping.+ :t := t i=(t-c+1) + πe(Si,Ai) π bBy importance weighting the abstract-state occurrences as described in Equation ( 5), clipping importance weights, in this case, implies that the c 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, as the effects of actions propagate through the abstract state transitions, unlike in IS-based methods. This condition, that a recent history of abstract states is sufficient to predict the current abstract state transition distribution, often approximately holds 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 c-clipped importance weights, ρ (t-c+1) + :t , updates the estimated distribution of the previous c 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 ϕ. We posit that there exist abstraction functions that are c-th order Markov [51, 9] . Definition 4.2 (c-th order Markov). The abstraction function ϕ is c-th order Markov ifPr(ϕ(S t+1 )|ϕ(S t ), • • • , ϕ(S (t-c+1) + ); π)= Pr(ϕ(S t+1 )|ϕ(S t ), • • • , ϕ(S 0 ); π) for π ∈ {π b , π e }. Let R π b →πe ϕ,cdenote the ARP estimated using c-clipped importance weights, ρ (t-c+1) + :t , in place of ρ 0:t in Equation ( 5). -→ J(π e ; M ).Proof. See Appendix B.5.Even when ϕ does not satisfy the above condition, weight clipping proves to be a practical approximation and results in low mean squared prediction error, as demonstrated empirically in Section 5. The steps for performing off-policy evaluation by estimating R π b →πe ϕ,c are highlighted in Algorithm 1.Discrete abstraction functions that are c-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. It motivates a research area akin to option discovery: abstraction discovery for OPE.We expect the following factors to play an important role in the search for good abstraction functions: (a) state-visitation distributions of π b and π e , 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 a 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-which can be estimated perfectly from a single observation of those transitions-creates stochastic transitions between abstract states. However, in general, state aggregation tends to simplify estimation by increasing the effective sample size [21] .STAR: Different configurations of (ϕ, c) induce different ARPs, R π b →πe ϕ,c. For certain configurations of (ϕ, c):• |Z| = 1 and no weight clipping: Mapping all states to a single abstract state yields the weighted per-decision importance sampling (WPDIS) estimator [42] . • Z = S and c = 1: Amounts to no state abstraction, and yields the maximum likelihood estimate of the MRP over states. The MRP is a combination of the approximate-model estimator [40] that directly estimates the model dynamics with the evaluation policy.The recovery of these familiar estimators at the endpoints of STAR highlights the unifying nature of the framework. More importantly, the intermediate configurations of (ϕ, 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. 
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 to 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 [6] .(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 [61] : 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://github.com/shreyasc-13/STAR. (A) Estimator Selection: Estimator selection presents a 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 reference, we compare the mean squared prediction errors from the estimated ARPs against WPDIS and approximatemodel estimator (MBased), the two endpoints of STAR, as shown in Figure 2 on the CartPole domain. [27, 11] ; 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 γ = 1 [63] . Due to the instability of IH estimates in our experiments, we excluded it from comparison.Results [Figure 3 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.STAR achieve prediction errors that are an order of magnitude lower than the best baseline. These results in Figure 3 emphasize that highly compact ARPs that distill complex sequential processes are particularly effective for off-policy evaluation.  
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, 14] delineate the numerous approaches to the problem. Modelbased approaches for OPE have proven effective [32, 62] but are restricted by the model class used.In this work, we use state abstraction to define compact models called abstract reward processes, and demonstrate their effectiveness as off-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, 1] , 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 modelbased RL, 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 [2] or reward relevant features [12, 59] .Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? 
discussion and conclusion: 
 In this paper, we have introduced a new framework for consistent model-based off-policy evaluation. This framework leverages state abstraction to prevent model class mismatch along with importance sampling to consistently learn models from off-policy data. Unlike traditional model-based methods, our 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 [21] , which is particularly beneficial in limited data regimes. Importantly, this work presents a 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 a principled method for selecting well-performing configurations of the abstraction function and the weight clipping factor remain elusive. Combining this work with regression IS [19] would be a practical extension that 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.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-performing OPE methods.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or 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 out 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 are 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: 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)? 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 a best faith effort. 12. Licenses for existing assets Question: 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? 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 use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: The code and related artifacts, such as pre-trained policies, are well documented and provided alongside the submission.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects.• 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. 
 
 Appendix: Consistency and Almost Sure Convergence Let θn denote the estimator of a statistic θ, estimated from n data points. As the amount of data approaches infinity, i.e., as n → ∞, the estimator is said to converge almost surely to θ if and only ifPr lim n→∞ θn = θ = 1.We write θ n a.s.-→ θ to denote that the sequence θ n converges almost surely to θ. An estimator that converges almost surely to the true value of the statistic is said to be (strongly) consistent.The continuous mapping theorem [4, 57] states that if a sequence of random variables (X i ) n i=1 converges almost surely to a random variable X, a function f has discontinuity points D f , and Pr(X ∈ D f ) = 0, then the sequence (f (X i )) n i=1 converges almost surely to f (X).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 [X | Y ]] .Here we provide additional details regarding the definitions of MDPs and MRPs. Specifically, we show how the expression of the transition and reward functions of the MRP can be simplified when X = S and discuss how to handle termination in ARPs that are derived from finite-horizon MDPs.A.1.1 Simplification of Equation 2The expressions for the components of a Markov reward process (MRP) can be simplified by using the Markov property. The transition function simplifies as:p π (x, x ′ ) = t Pr(S t+1 = x ′ , S t = x; π) t Pr(S t = x; π) = t Pr(S t+1 = x ′ | S t = x; π) Pr(S t = x; π) t Pr(S t = x; π) = t a∈A Pr(S t+1 = x ′ | S t = x, A t = a; π) Pr(A t = a|S t = x) Pr(S t = x; π) t Pr(S t = x; π) = t a∈A p(x, a, x ′ )π(x, a) Pr(S t = x; π) t Pr(S t = x; π) = a∈A p(x, a, x ′ )π(x, a) ( t Pr(S t = x; π)) t Pr(S t = x; π) = a∈A p(x, a, x ′ )π(x, a).Similarly, the reward function simplifies as:r π (x) = t E [R t |S t = x; π] Pr(S t = x; π)t Pr(S t = x; π) = t a∈A r(x, a)π(x, a) Pr(S t = x; π) t Pr(S t = x; π) = a∈A r(x, a)π(x, a) ( t Pr(S t = x; π)) t Pr(S t = x; π) = a∈A r(x, a)π(x, a).Each episode in a finite-horizon MDP concludes by some timestep T ∈ 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 an absorbing state s ∞ in the state set, or 2) introducing a termination function β : S → [0, 1] representing the probability of termination of an episode from each state, i.e., β(s) := Pr(terminate|S t = s). In the first case, by timestep T the process transitions into the absorbing s ∞ after which it continually transitions back to s ∞ getting a reward of zero. In the second case, after timestep T the process stops and there are no subsequent samples. Expressions involving sums over samples in an epsiode are denoted correspondingly, for example, the expected return J(π It must be noted that both approaches continue to be mathematically equivalent. The probability of transitioning from any abstract state z to z ∞ is the same as the the probability of termination from that state, i.e., β π ϕ (z) = P π ϕ (z, z ∞ ). Note that) := E[ ∞ t=1 R t ; π]P π ϕ (z ∞ , z) = 0 if z ̸ = z ∞ 1 if z = z ∞ .Similarly, the reward function is zero for the absorbing abstract state: R π ϕ (z ∞ ) = 0. It is mathematically more succint to model termination with z ∞ , and we use this (equivalent) approach in our theoretical analysis.In our implementation, z ∞ is not defined and thus the components of R ϕ do not take z ∞ as input. The equivalant form of the expected return of an ARP, that models a termination function, is then given by:J(π; R π ϕ ) = R π ϕ η ϕ + I -diag(β π ϕ ) P π ϕ R π ϕ η ϕ + I -diag(β π ϕ ) (P π ϕ ) 2 R π ϕ η ϕ + . . . = R π ϕ η ϕ + I -diag(β π ϕ ) P π ϕ R π ϕ η ϕ + I -diag(β π ϕ ) 2 (P π ϕ ) 2 R π ϕ η ϕ + . . . = ∞ k=0 I -diag(β π ϕ ) P π ϕ k R π ϕ η ϕ .Correspondingly, the closed form expression for the expected return that accounts for the termination function is given by,EQUATIONNote that I -Idiag(β π ϕ ) P π ϕ is an invertible matrix, as the left hand side of the expression, J(π; R π ϕ ), is equal to the expected return J(π; M ) of π by Theorem 3.1, which is bounded.In this section, we provide proofs of the theorems and lemmas in the main text. We start with Theorem 3.1 that states that ARPs are performance-preserving.B.1 ARPs are Performance Preserving Theorem 3.1. ∀ ϕ ∈ Φ, the performance of a policy π is equal to the expected return of the abstract reward process R π ϕ defined from MDP M , i.e., J(π; R π ϕ ) = J(π; M ).Proof. This result states that despite the use of a discrete state abstraction, the expected return of the ARP R π ϕ is equal to the performance of policy π. To prove this, we leverage two equivalent forms of defining the expected return of a policy. The first form:EQUATIONdefines the expected return as a sum of the expected value of the reward at each timestep, where the distribution of rewards at each timestep is governed by the components of the ARP, namely, η ϕ , P π ϕ and R π ϕ . The second, equivalent, form of expressing the expected return is given by:EQUATIONwhere 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 7 and 8 are equivalent, i.e.,EQUATIONNext, we denote the terms in Equation 8 in terms of the states of the underlying MDP to show the final result. The reward function R π ϕ can be expressed as, t Pr(S t = s; π), where ψ π (s ∞ ) is set to be proportional to any constant value. The normalization constant, κ, that makes ψ π (s) a valid distribution cancels out from both the numerator and the denominator of the above expression. The term Pr(Z t = z; π) can be expressed in terms of states as, where (a) follows from the law of total probability [64] .R π ϕ (z) := t E[RPr(Z t = z; π) = s∈S Pr(S t = s; π)1{ϕ(s) = z}.We have established that ARPs are performance-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. In order to do so, we first introduce properties that will be useful in the proof of Lemma 3.2.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 z ∈ Z andEQUATIONProof. Recall thatP π n,ϕ (z, z ′ ) = n i=1 t 1{Z i t = z, Z i t+1 = z ′ } n i=1 t 1{Z i t = z} . Let X n := 1 n n i=1 t 1{Z i t = z, Z i t+1 = z ′ } and Y n := 1 n n i=1 t 1{Z i t = z}. We can then rewrite P π n,ϕ (z, z ′ ) as P π n,ϕ (z, z ′ ) = X n Y n ,which is a continuous function of X n and Y n when Y n > 0. At a high level, we will show what X n and Y n each converge to almost surely, and will then apply the continuous mapping theorem to reason about the almost sure convergence of P π n,ϕ (z, z ′ ).However, there may be some abstract states Z ⊂ Z that are not reached and thus are not observed in the data. Such abstract states pose a problem: If z ∈ Z, then Y n for P π n,ϕ (z, z ′ ) will be zero, and so P π n,ϕ (z, z ′ ) will be undefined and not a continuous function of X n and Y n (which must be handled appropriately in the proof of consistency). First, to ensure that the ARP is well-defined even when Z is not empty, for abstract states z ∈ Z (abstract states that were not observed in 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. 4 In particular, for z ∈ Z, the transition function can be set to self-transition back to z with probability 1, i.e., P π n,ϕ (z, z) = 1 and P π n,ϕ (z, z) = 0 for all z / ∈ Z, the reward function is set to R π n,ϕ (z) = 0 and the initial abstract state distribution is η π n,ϕ (z) = 0 for all z ∈ Z. 5To reason about the almost sure convergence of P π n,ϕ (z, z ′ ), first consider lim n→∞ X n ,lim n→∞ X n = lim n→∞ 1 n n i=1 t 1{Z i t = z, Z i t+1 = z ′ } = lim n→∞ t 1 n n i=1 1{Z i t = z, Z i t+1 = z ′ } .Note that 1{Z i t = z, Z i t+1 = z ′ } is independent across episodes (for each i), has bounded variance, and has the same mean for each episode. By Kolmogorov's strong law of large numbers [46] ,1 n n i=1 1{Z i t = z, Z i t+1 = z ′ } a.s.-→E[1{Z t = z, Z t+1 = z ′ }; π] ,This convergence guarantee holds for all t. From the definition of almost sure convergence, this means thatEQUATIONwhere the expectation results from the use of the policy π that generated dataset D (π)n . 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 ∀t ∈ N is now inside the statement of probability):Pr ∀t ∈ N, lim n→∞ 1 n n i=1 1{Z i t = z, Z i t+1 = z ′ } = E [1{Z t = z, Z t+1 = z ′ }; π] = 1. (12)Hence,EQUATIONNext, by the dominated convergence theorem [16, Theorem 1.19] , the summation over time and limit over n can be interchanged, giving:EQUATIONReturning to a.s.-→ notation, this means thatEQUATIONThe expected value of the indicator is equal to the probability of the event, and soEQUATIONThis, combined with the fact that the left hand side of Equation 15 is X n means thatEQUATIONSimilarly, these same exact steps can be followed to show thatEQUATION)LetΨ i = (X i , Y i ), so that Ψ n = (X i , Y i ) n i=1 is a sequence of vector-valued random variables. Since X n a.s. -→ t Pr(Z t = z, Z t+1 = z ′ ; π) and Y n a.s.-→ t Pr(Z t = z; π), we have thatEQUATION)Consider the function f : R 2 → R, defined as:EQUATION)Note that discontinuities of f may occur when y = 0. Applying the continuous mapping theorem, we have thatEQUATIONif 6Pr t Pr(Z t = z; π) = 0 = 0.In our case, t Pr(Z t = z; π) is a constant, and so the condition in Equation 22is simply:EQUATIONAlso, Equation 21 can be simplified to:EQUATIONsince 7 andf (Ψ n ) = X n /Y n = P π n,ϕ (z, z ′ ),P π ϕ (z, z ′ ) = t Pr(Zt=z,Zt+1=z ′ ;π) t Pr(Zt=z;π)by Equation 3. Restating this conclusion, we have that ifEQUATIONEQUATIONwhich establishes the property.Next, we present a property that establishes the almost sure convergence of the reward function estimate.EQUATIONEQUATION)Proof. Recall thatR π n,ϕ (z) = n i=1 t 1{Z i t = z}R i t n i=1 t 1{Z i t = z} . Let X n := 1 n n i=1 t 1{Z i t = z}R i t and Y n := 1 n n i=1t 1{Z i t = z}. We will show that X n and Y n converge almost surely, and then apply the continuous mapping theorem to reason about the almost sure convergence of R π n,ϕ (z).To ensure that the ARP is well-defined even when Z is not empty, for abstract states z ∈ Z (abstract states that were not observed in the data), the reward function can be set to R π n,ϕ (z) = 0, as elaborated in the proof of Property B.2.Consider lim n→∞ X n , lim n→∞ X n = lim n→∞ 1 n n i=1 t 1{Z i t = z}R i t = lim n→∞ t 1 n n i=1 1{Z i t = z}R i t .Note that 1{Z i t = z}R i t is independent across episodes (for each i), has bounded variance, and has the same mean for each episode. By Kolmogorov's strong law of large numbers [46] ,1 n n i=1 1{Z i t = z}R i t a.s.-→E[1{Z t = z}R t ; π] = r∈R,z∈Z Pr(R t = r, Z t = z; π)1{Z t = z}r = r∈R Pr(R t = r, Z t = z; π)r = r∈R r Pr(R t = r | Z t = z; π) Pr(Z t = z; π) =E [R t | Z t = z; π] Pr(Z t = z; π).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,EQUATIONReturning to a.s.-→ notation, this means thatEQUATIONSimilarly, these same exact steps can be followed to show thatEQUATIONthenP π n,ϕ (z, z ′ ) a.s.-→ P π ϕ (z, z ′ ), (38) and R π n,ϕ (z) a.s.-→ R π ϕ (z).(39) Similarly, Property B.4 establishes that for all abstract states z ∈ Z,EQUATION)The expected return J(π; R π n,ϕ ) is a continuous function of R π n,ϕ := ( P π n,ϕ , R π n,ϕ , η n,ϕ ), given by 8 where Pr denotes the empirical estimate of the corresponding probability.J(π; R π n,ϕ ) = I -P π n,ϕ -1 R π n,ϕ η n,ϕ = z t Pr(Z t = z; π) R π n,ϕ (z)Note that the term t Pr(Z t = z; π) = I -P π n,ϕ -1 η n,ϕ z , i.e., the empirical estimate of the sum of probabilities of encountering the abstract state z over all timesteps is equal to value of the vectorEQUATION)Let Z = {z : t Pr(Z t = z; π) = 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 π. 9 The expression for the expected return can be divided into two terms: (1) the first term sums over abstract states for which t Pr(Z t = z; π) = 0, and the values of the components of the ARP-in particular, R π n,ϕ -have been specially hardcoded as detailed in Property B.2, and (2) the second term sums over the abstract states for which t Pr(Z t = z; π) ̸ = 0 and thus Equation 41 holds.EQUATIONEQUATIONAs detailed in Property B.2, R π n,ϕ (z) = 0 for z ∈ Z and thus ∀z ∈ Z, making the first term equal to zero. The constituents of the second term converge almost surely:EQUATIONEQUATIONEQUATION)We then obtain the final result:EQUATIONSo far, we have shown that the expected return of the estimated ARP converges almost surely to 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-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 abstract states z ∈ Z andEQUATIONthenEQUATIONProof. Recall thatP π b →πe n,ϕ (z, z ′ ) = i,t 1 i t {z, z ′ }ρ 0:t i,t 1 i t {z}ρ 0:t .Similar to the proof structure of Property B.2, let X n := 1 n i,t 1 i t {z, z ′ }ρ 0:t and Y n :=1 n i,t 1 i t {z}ρ 0:t . For abstract states Z ⊂ Z that are never reached and thus are not observed in 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 z ∈ Z, the transition function can be set to self-transition back to z with probability 1, i.e.,EQUATION= 0 and the initial abstract state distribution isη π b →πe n,ϕ (z) = 0 for all z ∈ Z. Consider lim n→∞ X n , lim n→∞ X n = lim n→∞ 1 n i,t 1 i t {z, z ′ }ρ 0:t = lim n→∞ t 1 n n i=1 1 i t {z, z ′ }ρ 0:t .Note that 1 i t {z, z ′ }ρ 0:t is independent across episodes (for each i), has bounded variance, and has the same mean for each episode. By Kolmogorov's strong law of large numbers [46] ,1 n n i=1 1 i t {z, z ′ }ρ 0:t a.s. -→ E [1{Z t = z, Z t+1 = z ′ }ρ 0:t ; π b ] .The importance weights change the distribution over which the expectation is computed, as below:E [1{Z t = z, Z t+1 = z ′ }ρ 0:t ; π b ] = t S0:t+1, A0:t η(S 0 ) t l=0 π b (S l , A l )p(S l , A l , S l+1 ) 1{ϕ(S t )=z, ϕ(S t+1 )=z ′ }   t j=0 π e (S j , A j ) π b (S j , A j )   = t S0:t+1, A0:t η(S 0 ) t l=0 π e (S l , A l )p(S l , A l , S l+1 ) 1{ϕ(S t )=z, ϕ(S t+1 )=z ′ } = t E [1{Z t = z, Z t+1 = z ′ }; π e ]This convergence guarantee holds for all t. By the countable additivity property of probability measures in conjunction with the dominated convergence theorem [16] , this implies that,EQUATIONSimilarly, these same exact steps can be followed to show thatEQUATIONNoting that R π b →πe n,ϕ= Xn Yn , we can apply the continuous mapping theorem, as done in the proof of Property B.3, to show thatEQUATION-→ R πe ϕ (z),when t Pr(Z t = z; π b ) ̸ = 0.Property B.8. For all abstract states z ∈ Z,EQUATION-→ η πe ϕ (z).Proof. Recall thatη π b →πe n,ϕ (z) = 1 n n i=1 1{Z i 0 = z}ρ 0 . Let X n := 1 n n i=1 1{Z i 0 = z}ρ 0 .Following the exact steps from Property B.4, we can show that1 n 1{Z i t = z} a.s. -→ E [1{Z 0 = z}ρ 0 ] = Pr(Z 0 = z).This proof holds for all z ∈ Z, not just the abstract states that have non-zero probability of occuring. This implies thatEQUATION-→ η πe ϕ (z). -→ R πe ϕ .Proof. The results required to establish this result are provided in Properties B.6, B.7, and B.8. Specifically, the properties establish that if t Pr(Z t = z; π b ) ̸ = 0, thenEQUATION-EQUATION-→ R πe ϕ (z);EQUATION-→ η ϕ (z),EQUATION-→ R πe ϕ , while the values of the components for z ∈ Z are hardcoded as detailed in Property B.6. -→ J(π e ; M ).e ; R π b →πe n,ϕ ) is a continuous function of R π b →πe n,ϕ := ( P π b →πe n,ϕ , R π b →πe n,ϕ , η π b →πe n,ϕ), given by J(π e ; R π b →πe n,ϕ) = I -P π b →πe n,ϕ -1 R π b →πe n,ϕ η π b →πe n,ϕ. Similar to the proof of Lemma 3.2, by the continuous mapping theorem and Lemma 3.3, we obtain the final result that enables off-policy evaluation with ARPs:J(π e ; R π b →πe n,ϕ ) a.s.-→ J(π e ; R πe ϕ ) = J(π e ; M ).Variance in estimation of the model of the ARP from off-policy can be reduced by clipping the importance weights. We now show that when the state abstraction function is c-th order Markov, clipping the importance weights to the c most recent terms continues to provide a consistent off-policy expected return estimate. -→ J(π e ; M ).Proof. We only need to show that for a state abstraction function ϕ ∈ Φ that is c-th order Markov, i.e., Pr(ϕ(S t+1 )|ϕ(S t ), ϕ(S t-1 ), . . . , ϕ(S (t-c+1) + ); π) = Pr(ϕ(S t+1 )|ϕ(S t ), ϕ(S t-1 ), . . . , ϕ(S 1 ), ϕ(S 0 ); π), for π ∈ {π b , π e } the following holds:R π b →πe ϕ,ca.s.-→ R πe ϕ . The remaining steps to show that the return estimates are consistent follow from Theorem 4.1. For brevity, we denote by Z t := ϕ(S t ) for the rest of the proof. Consider the expression for the transition function without any weight clipping,EQUATIONUsing the tower rule [60] , E [1{Z t = z, Z t+1 = z ′ }ρ 0:t ; π b ] can be re-written as:E [1{Z t = z, Z t+1 = z ′ }ρ 0:t ; π b ] =E 1{Z t = z, Z t+1 = z ′ }ρ 0:(t-c) + ρ (t-c+1) + :t ; π b =E E 1{Z t = z, Z t+1 = z ′ }ρ 0:(t-c) + ρ (t-c+1) + :t | (Z i ) t i=(t-c+1) + ; π b ; π b (a) = E E 1{Z t = z, Z t+1 = z ′ }ρ (t-c+1) + :t | (Z i ) t i=(t-c+1) + ; π b E ρ 0:(t-c) + | (Z i ) t i=(t-c+1) + ; π b ; π b =E E 1{Z t = z, Z t+1 = z ′ }ρ (t-c+1) + :t | (Z i ) t i=(t-c+1) + ; π b ; π b E E ρ 0:(t-c) + | (Z i ) t i=(t-c+1) + ; π b ; π b =E 1{Z t = z, Z t+1 = z ′ }ρ (t-c+1) + :t ; π b E ρ 0:(t-c) + ; π b =1 (b) = Pr(Z t = z, Z t+1 = z ′ ; π e ),where (a) follows from Equation 63 and (b) follows from Lemma 3.3. Thus when the abstract states are 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 a change of measure by the use of clipped importance weights, i.e.,EQUATIONwhen ϕ is c-th order Markov. Note that the expression for P π b →πe ϕ,c is:P π b →πe ϕ,c(z, z ′ ) := (z, z ′ ) = Xn Yn . Following the exact steps from Lemma 3.3, that entail a careful application of the continuous mapping theorem, we can show thatP π b →πe ϕ,c (z, z ′ ) a.s.-→ P πe ϕ (z, z ′ ), if t Pr(Z t = z; π b ) ̸ = 0. Similar derivations can be followed for the reward function and the initial state distribution, leading to the required result:R π b →πe ϕ,ca.s.-→ R πe ϕ when t Pr(Z t = z; π b ) ̸ = 0, that enables almost sure convergence of the expected return estimate:J(π e ; R π b →πe ϕ,c ) a.s.-→ J(π e ; R πe ϕ ) = J(π e ; M ).In this section we provide additional empirical details for the experiments presented in the main paper. An overall step-by-step algorithm for STAR is as follows:Algorithm 1 Overview of STAR(ϕ, c) and compute importance weights:Input: π e ,EQUATIONt , ρ(i) (t-c+1) + :t = t j=(t-c+1) + πe(S (i) j ,A (i) j ) π b (S (i) j ,A (i) j ) 2. Estimate the components of the ARP R π b →πe ϕ,c : R π b →πe ϕ,c = P π b →πe ϕ,c , R π b →πe ϕ,c , η π b →πe ϕ,cwhere, 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:EQUATIONCartPole The CartPole domain is a classic control problem from OpenAI Gym [6] . The task is to balance a pole on a 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 OpenAI Gym. In the experiments, π b is uniformly random, i.e., the left and right actions are each taken with probability 0.5. The evaluation policy π e 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.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 et 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, a reward of +1 is given, while death corresponds to a reward of 0, with all intermediate rewards also being 0. This results in the expected return of a policy corresponding to the probability that a randomly selected patient will survive. In the experiments, π e is set to an expert policy, provided with the domain and included in the submitted codebase, while π b is a policy that is a more stochastic version of the expert policy constructed by temperature scaling [17] the action probabilities of expert policy with a temperature parameter τ = 2.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 × 4, and the action set consists of six actions. The data collecting policy π b is uniformly random, while the evaluation policy π e picks actions with non-uniform skewed probabilities.were run using 32 threads on Xeon E5-2680 CPUs on a computing cluster, bringing the total compute time to roughly 45000 compute hours. 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 in 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 as long as it is clear that these goals are not attained by the paper.Justification: There is a 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 in the core of the paper to a 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, or as supplemental material.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).We write ; π within statements of probability or expectations to indicate that random variables like St, At, and Rt result from the use of policy π.The expression for the importance weight can be extended to continuous and hybrid probability measures using Radon-Nikodym derivatives. As with other terms, we hereafter denote the importance weight for the i th episode as ρ i 0:t .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, we wish to ensure that the transition function, reward function, and initial state distribution still represent a well-defined ARP.Note that the initial state distribution is not actually a problem like the transition and reward functions-the previous definitions already ensured that η π n,ϕ (z) = 0.This condition arises due to the discontinuity of f when the second argument is zero. See the statement of the continuous mapping theorem in Appendix A for details.To be more precise f (Ψn) = Xn/Yn when Yn ̸ = 0. However, even when Yn = 0, the conclusion that f (Ψn) = P π n,ϕ (z, z ′ ) holds from the definition of f in Equation20.Termination is handled as detailed in Appendix A.1.In relation to Z defined in Property B.2, note Z ⊆ Z. As n → ∞ the two sets, with probability 1, become equal. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
However, 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.

1. No finite samples analysis has been conducted. Thus, when considering datasets of finite size, no theoretical result regarding the approximation error is available.

1. 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.

Minor:
- There are some typos in the use of z and z' in equation (2) and in the proof of Theorem 3.1.
- If accepted, I suggest to use the additional page for explaining the missing details of the experimental evaluation, such as:
  - How is the MSE for OPE exactly defined
  - How is the variance-bias measure is constructed for Figure 3.
  - List Algorithm 1 in the main body
questions: questions: 4. How did you obtain the probabilities of the behaviour policy for the ICU sepsis dataset?
5. Which of the baselines assume complete knowledge about the behaviour policy?

The authors may also address any of the points raised above.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
questions: questions: Please see the concern above
limitations: limitations: Yes
paper_summary: paper_summary: The authors introduce a new framework that groups the states with a similar reward, hence reduces variance of any applied OPE estimator.
strength_weakness: strength_weakness: Minor: [L548, L560, L586, L600, L609] "See Appendix B" is obsolete, we are already in Appendix B.
questions: 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.

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.

References:

Peng, 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.

Cief, Matej, Michal Kompan, and Branislav Kveton. “Cross-Validated Off-Policy Evaluation.” arXiv, May 24, 2024. http://arxiv.org/abs/2405.15332.
limitations: limitations: The authors extensively discuss the limitations throughout the work, for example, in Conclusions.

Comments: title: Reply
comment: I would like to thank the authors for their reply. The reply addressed my concern. After reading the reply and other reviews, I increased the score.
Thank you for taking the time to answer my questions. After reviewing all discussions, I am keeping my score and will advocate for accepting the paper (if the discussion will be needed, it seems the vote is unanimous).