Counterfactual-Augmented Importance Sampling for Semi-Offline Policy Evaluation
Authors: Shengpu Tang
Jenna Wiens
Venue: NeurIPS 2023 poster (2023)
Keywords: healthcare
reinforcement learning
offline RL
off-policy evaluation
counterfactuals
TL;DR: We propose a new framework that incorporates human annotations of counterfactual actions into OPE, supported by both theoretical and empirical results.

Abstract: In applying reinforcement learning (RL) to high-stakes domains, quantitative and qualitative evaluation using observational data can help practitioners understand the generalization performance of new policies. However, this type of off-policy evaluation (OPE) is inherently limited since offline data may not reflect the distribution shifts resulting from the application of new policies. On the other hand, online evaluation by collecting rollouts according to the new policy is often infeasible, as deploying new policies in these domains can be unsafe. In this work, we propose a semi-offline evaluation framework as an intermediate step between offline and online evaluation, where human users provide annotations of unobserved counterfactual trajectories. While tempting to simply augment existing data with such annotations, we show that this naive approach can lead to biased results. Instead, we design a new family of OPE estimators based on importance sampling (IS) and a novel weighting scheme that incorporate counterfactual annotations without introducing additional bias. We analyze the theoretical properties of our approach, showing its potential to reduce both bias and variance compared to standard IS estimators. Our analyses reveal important practical considerations for handling biased, noisy, or missing annotations. In a series of proof-of-concept experiments involving bandits and a healthcare-inspired simulator, we demonstrate that our approach outperforms purely offline IS estimators and is robust to imperfect annotations. Our framework, combined with principled human-centered design of annotation solicitation, can enable the application of RL in high-stakes domains.

Counterfactual-Augmennee Importance Sampling for Semi-Offline Policy Evaluation
Shengpu Tang, Jenna Wiens Computer Science & Engineering University of Michigan, Ann Arbor, MI, USA
saaggppwwiess] @umich.edu
Reviewed on OpenReview; http:://woorriiiiiwno////o/ooiia
Abstract
In applying reinforcement learning (RL) to high-stakes domains, quantitative and qualitative evaluation using observational data help practitioners understand the generalization performance of new policies. However, this type of off-policy evaluation (OPE) inherently limited since offline data may not reflect the distribu- tion shifts resulting from the application of new policies. On the other hand, online evaluation by collecting rollouts according the new policy is often infeasible, deploying new policies in these domains can be unsafe. In this work, we propose semi-offline evaluation framework
intermediate step between offline and online evaluation, where human users provide annotations of unobserved coun- terfactual trajectories. While tempting simply augment existing data with such annotations, we show that this naive approach can lead to biased results. Instead, we design a new family of OPE estimators based on importance sampling (IS) and a novel weighting scheme that incorporate counterfactual annotations without introducing additional bias. We analyze the theoretical properties of our approach, showing its potential to reduce both bias and variance compared to standard IS estimators. Our analyses reveal important practical considerations biased, noisy, missing annotations. In series of proof-of-concept experiments involving bandits and hcalthcare-inspee innsrired simulator, we demonstrate that our approach outperforms purely offline IS estimators and is robust imperfect an- notations. Our framework, combined with principled coman-centered design annotation solicitation, enable the application of RL in high-stakes domains.
handling
Figure 1: Left The state transition diagram of a tree MDP with 3 steps and actions. States are denoted by O. actions are denoted by arrows (/, ) rewards are denoted in red and given only at terminal transitions. Center - The behavior policy takes specific sequence of actions and leads to the factual trajectory, leaving the rest of the state-action space with poor support. Right The counterfactual annotations provided by human annotators (indicated by &) capture information (in this example, the terminal reward under any policy that takes (/7, 7)) for the second and third steps) about support-deficient regions of the state-action space not visited by the behavior policy.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1 Introduction
Reinforcement learning (RL) has gained popularity in recent years for its ability to solve sequential decision-making problems in various domains [1-7]. Despite these successes, it remains challenging to deploy and use RL in highly consequential or safety-critical domains, such as healthcare, education, and public policy [8-12]. One of the major roadblocks that distinguishes RI.-based systems from their supervised learning counterparts is evaluation.
Evaluation of supervised learning models often involves calculating prediction accuracy against labeled test set [13]. In contrast, evaluation of RL policies is less straightforward and often involves interacting with the environment [2, 3, 14-19]. For domains that lack accurate simulators, this means deploying new policies in the real environment. For instance, in healthcare, online evaluation would require clinicians to follow RL recommendations in selecting treatments for real patients. While mathematically sound, this presents clear safety issues and potential disruptions to workflows. There- fore, most work in these areas has relied exclusively on retrospective evaluations using observational data [20-22], focusing on both quantitative and qualitative aspects. Quantitative evaluations make use of statistical off off-policy evaluation (OPE) methods to account for the distribution shift resulting from the application of new policies [23-25]. Despite their wide use, OPE is fundamentally limited by the available offline data. In particular, past work has noted that unexpected bias and large variance [20] among other reasons make these approaches unreliable [22, 26]. On the other hand, qualitative evaluations typically aim to verify with domain experts whether the RL recommendations are reasonable, but are difficult to standardize and may be susceptible to confirmation bias [20].
In this work, we consider an intermediate step before prospective deployment that improves upon offline evaluation of RL policies. Specifically, we assume human domain experts can provide annota- tions of unobserved counterfactual trajectories that are small deviations of the observed trajectory (Figure 1), where each annotation is some summary of the expected outcomes of counterfactual tra- jectories. For example, in healthcare domains, such annotations may be obtained by asking clinicians what they think would happen to the patient if a different treatment were to be used. Intuitively, these counterfactual annotations can make up for regions of the state-action space with poor support in the offline dataset. However, as we demonstrate, simply adding the annotations as new trajectories to the offline dataset will change the state distribution and lead to biased results. Thus, we design new OPE estimator based on importance sampling (IS) that incorporates both the offline factual data and counterfactual annotations without introducing additional bias. We analyze the theoretical properties of our proposed estimator, noting its advantages over standard IS. Specifically, our estimator requires a weaker condition on support to achieve unbiasedness and has the potential to reduce variance. Through series of proof-of-conee oof-cceccccpptt experiments using toy problems and wealthcare-inspire simulator, we show the benefits of our approach in making use of counterfactual annotations to enable better evaluations of RL policies, even when annotations are biased, noisy, missing. Our semi-offline evaluation framework represents an important step that complements offline evaluations by providing additional confidence in RL policies.
2 Problem Setup
We consider Markov decision processes (MDPs) defined by a tuple M = (8.A, PR, T). where S and A are the state and action spaces, P : S x A + ASS) and R S x A - A(R) the transition and reward functions, di E (SS) is the initial state distribution, 7 E 0, 1] is the discount factor, T E 2 is the fixed horizon. p(s"|s a) denotes the probability density function of P. and R(s,a) a) denotes the expected reward. A policy π : S - A(A) specifies mapping from each state to a probability distribution over actions. A T-step trajectory following policy π is denoted by Tt) ro]l=1 where $1 d1, at 7 T(s)) ri ~ R(s,, ag), St+1 ~ p(s,, at). Here, a 7ss) is short for a ~ (-|s) and s' ~ p(s,a) a) for ~ ppp((ss,)) Let = = 7"-1, denote the return of the trajectory, which is the discounted sum of rewards. The value of a policy n is the expected return, defined as tTT)
T = [(s,, ae,
E, [J]. The value function of policy т, denoted by V : S + R, maps each state to the expected return starting from that state following policy x. Similarly, the action-value function (i.e., the Q-function), Q" S x A + IR, is defined by further restricting the action taken from the starting state. Formally, (s) = Ez [J]s] 31 = s). and Q (s) = E. [J[s] = 8, 01 a).
We also consider value functions at specific horizons: (s)r(s) = E, ET 7- - Trlss = s]. and ( a) = E- 7 - 8, a, = a). Throughout the paper we also consider the non- sequential, bandit setting with horizon T = 1. In this case, a "trajectory" (or, a sample) is denoted by (s, a, where we omit the time step subscript.

---

Our goal is to estimate ((TT),, the value of an evaluation policy Te, given data that were previously collected by some behavior policy T6 in the same environment defined by MM. Let D = ( denote the dataset containing N independent trajectories drawn according to Tr and M.
OPE. The typical approach to this problem relies on off-policy evaluation (OPE). Importance sampling (IS) is a common OPE approach that reweights samples based on how likely they are to occur under Te relative to TT. Given a trajectory т, the 1-step and cumulative IS ratios are defined as I_(ax19)) P: (arl))) and P1:t = II. =1 Pv- The per-decision IS estimator, iPDIS = = P rg is an unbiased estimator of (( [27, 28J. We also consider its recursive definition: j eT where vo = 0, UT-1+1 = Pe(Te + yur-e). In this paper, we discuss the properties of IS-based estimators over single trajectory; our results naturally generalize to dataset 'D containing N trajectories where the final estimator is the average over trajectories. For the bandit setting, we refer PDIS simply as the IS estimator, 5 pr ma(a|s)
(a(ass)
Counterfactual Annotations. In addition to the offline dataset D, our semi-offline framework assumes access to accompanying counterfactual annotations. To introduce the notation, we start with the non-sequential, bandit setting where T = 1, dropping the time step subscripts. Given factual sample т = (s, a, r), let ca E {0, be a binary indicator for whether the counterfactual action ā AAY \ {a} is associated with an annotation, and let the annotation be 9d R. We use S x A + (RR) to denote the annotation function such that g" ~ G(s, a), A counterfactual- augmented sample T- (T.g) consists of the factual sample and counterfactual annotations [gg d² = 1}. where each of ~ G(s, â). Intuitively, a "good" annotation should reflect the scenario where the counterfactual action à is taken and the reward g² R(s, ā) is observed.
Assumption 1 (Perfect annotation, bandit). Eg-G(ss.))ll = R(s, a), Vs E S, E A.
For the sequential setting, define the correspond- ing notation with time step subscripts: for (st. de, rz) occurring at step of trajectory т, we define coun- terfactual indicators of for à E SA' {az) and anno- tations g. [of c 1). Figure provides an example trajectory with counterfactual annotations. Here, each of ~ Gs, ā) is drawn from the horizon- t annotation function G.. While the general notion of counterfactual annotations could be used to capture different information (e.g., the instantaneous reward of the counterfactual action, R(s, ā)), in this work, we study a specific version that allows us to extend the theory of the bandit setting. Specifically, the an- notation for counterfactual action ä summarizes the annotator's 's belief of the expected future return (sum of rewards) in the remaining T t + 1 steps after taking the counterfactual action ā from state st. and then following the evaluation policy πe. In other words, the annotation plays the same role as the Q-function. This leads to more refined assumption on the horizon-specifie annotation function G.-
11 -1=
2g y.Po
Figure 2: A trajectory augmented with coun- terfactual annotations, where the action space is A {x. y: v. The factual trajectory is shown in black. Solid blue arrows indicate the counterfactual annotations were queried and obtained; dashed gray arrows indicate the annotations are not available. Each transition arrow is labeled with (action, value), where value is either an observed immediate reward or a counterfactual annotation.
Assumption 2 (Perfect annotation, MDP). Egr.G, [g] = Q5 a), Vs E S, a E A.
Under Assumption 2, if we obtained infinitely many annotations for all initial states and all actions, then evaluation becomes trivial (we essentially recover the Q-function of all initial states). However, we consider the non-asymptotic regime where not every annotation is available, as certain annotations might be difficult to obtain. For example, annotating initial states requires reasoning about the full horizon T. Furthermore, since this is a rather strong assumption (we need different annotations for each n.), later we explore relaxation where the annotations reflect the behavior policy m, instead.
3 Methods
To motivate our approach, we begin with a didactic bandit example to illustrate how the naive incorporation of counterfactual annotations issue, we propose a modification of IS estimators that reweights the factual data and counterfactual annotations. We formally describe how this idea applies to IS (in the bandit setting) and PDIS (in the sequential RI. setting), giving rise to a family of semi-offline We study the impact of different assumptions regarding the annotations on the performance of our proposed estimators both theoretically (Section 4) and empirically (Section 5).
yield biased estimates. In order to address this
cunterfactuallaagmeette IS estimators.
3

---

3.1 Intuition
Consider a one-step bandit (Figure 3a) with two states {81, 82} (drawn with equal probability) and two actions, up (/2) and down (N). The reward from $1 +1 and from 82 is 0 (i.e., rewards do not depend on the action), meaning all policies have an expected reward of 0.5. Suppose the behavior policy always selects / generating a dataset with poor support for policies that assign nonzero probabilities to > (Figure 3b). Now suppose we also have access to human-provinn of counterfactual actions, but not all counterfactual annotations are available (either because they were never queried or the users declined to provide annotations). In our example (Figure 3c), one annotation collected for the counterfactual action >> at state $1, indicating that the human annotator believes the reward for taking action > from state is +1 (which is the true reward). To make use of this information, one might be tempted to add the counterfactual annotation as new sample. The augmented dataset (Figure 3d) would allow us to evaluate policies (e.g., using IS) that assign non-zero probabilities to Y in state 81. While seemingly plausible, this naive approach inadvertently changes the state distribution and results in a dataset inconsistent with the original problem (it looks like state $1 is seen more often than reality). A quick calculation reveals that applying IS to this unweighted augmented dataset gives biased estimate of new policy as 2/3 instead of 0.5 (see Appendix B). To address this issue, in Section 3.2 we propose a new reweighting procedure that maintains the state distribution of the original dataset while incorporating counterfactual annotations.
annotations
(a) State diagram
[c) Counterfactaal ArtitarffcctullAnmnatiiooooo
Figure 3: (a) The state diagram of bandit problem with two states and two actions. (b) factual dataset containing two samples. (c) The factual samples augmented with counterfactual annotations. (d) The (unweighted) augmented dataset constructed from factual samples and counterfactual annotations. Compared to the original factual dataset, the relative frequency of $2 has changed from 1 1 to 2 1.
0
(b) Factuel dataset
(d) Unweighted augmented dataset
3.2 Augmenting IS Estimators with Counterfactual Annotations
To avoid the bias issue described in Section 3.1, informally, we want to split the contribution of each sample between the factual data and counterfactual annotations, Given a factual sample (s, a, r) and the associated counterfactual annotations g. let w [w"] } U (w ā E A \ {a}} be a set of user-defined non-negative weights that satisfy w" + EaE)((a) w 1. These weights specify
how much we want the estimator to "listen" to the counterfactual annotations (w²) relative to the factual data (w"). We restrict w = 0 when ea = 0, i.e., non-zero weight is only allowed when the annotation available. In general, one may assign different weights for each occurrence of (s, a) (e.g.. the counterfactual annotation is obtained for one instance but missing for another); let W(lss, a) = R[[a] denote the average weight assigned to when the factual data is (s,a) a) (see example in Appendix B. After reweighting, the state distribution is maintained (since the weights associated with each sample sum to 1) but the state-conditional action distributions have changed; this "weighted" augmented dataset can be seen as if it was generated using different behavior policy.
Definition
1aciiionnnAAnnnnaaii (Augmented behavior policy).
Tot (als) W
+ EaEAMa) W Walss, (āls)
Here, Tbi (als) represents the probability that information about action is observed for state (similar to how an "average policy" may be defined for multiple behavior policies [29]), either as factual action in the dataset, or as an annotated counterfactual action when some other action à the factual action. Next, we define our proposed estimators (for bandits) based on IS.
Definition (Counterfactual auggeented IS). Given a wwwpeterfactuallagmmeetttt sample T = (r.g) and weights (w ā E A). where ge-1s = nh par EaEAtaa) wa "ā"" where م² (a(()) for each E.A. Ta (a]s]
(s,aar) r), g و da 1). the C-IS estimator is
The C-IS estimator is a weighted convex combination of the factual IS estimate par and the coun- terfactual IS estimates g for all counterfactual actions E AA \ {a). We also study special case where all annotations are available and the weights are split equally among actions, such that _ = ف A/| Then, Th. becomes the uniformly random policy, and after substituting into Definition 2, we obtain the following estimator.

---

Definition 3 (C-IS with equal weights). Given a counterfactuallaaggeenn sample T! = (T,g), the C*-IS estimator is ic--15 (als)) Eaed)((a) T. (ā g)
Remark. Definition 3 provides an alternative interpretation of the estimator when using equal weights: if Assumption holds (i.c., the annotation function G is the true reward function R), we effectively observe both the factual and counterfactual rewards from R. Then, we can directly use the definition of the value function to calculate the expected reward under Te using the action probabilities Te (-(s)s).
For the sequential setting, given a trajectory with T steps, we define the collection of weights over all time steps,
{w," tt I...T) U {uî â E A policy Th- is similarly defined (see Definition 1). By extending the recursive definition of PDIS, we obtain the following two estimators (assuming either arbitrary weights or equal weights).
The augmented behavior
Definition (Counterfactual-auu -agmeette PDIS). Given a counterfactual-augmeeen (T. 9) and weights w defined above, where [(5,, de, re)] 9 {ge cf 1). the C-PDIS estimator is JC.PDIS = vr, with ey defined recursively as % = 0, tr--+1 = w Pi (rr + 70--1) +
trajectory T
EaEA)(a) wi Pigh fort = I...., where p
n. [ for each ā E
Ty+ (2]es)
Definition 5 (C-PDIS with equal weights). Given a counterfactual-augnne -augeeenee trajectory T (T,g), the C*DPDIS estimator is &C-PPDiS vr, with By defined recursively as % = 0, 0y Te(aalss)(rr + yor-1) + EaeA((a.) Te ()) for t T...1
Next, we study the theoretical properties of our proposed estimators, relating their OPE performance (in terms of bias and variance) assumptions on counterfactual annotations and the offline dataset.
4 Theoretical Analyses
We first present results for the bandit setting, where we study and compare the properties of the C-IS estimator with standard IS in terms of bias, variance, and the assumptions required, highlighting scenarios where bias and variance reduction is guaranteed. We then show how these results generalize to C-PDIS in the sequential RL setting. Finally, we discuss practical implications of the theoretical results. Full derivations are in Appendix C.
To begin, we review existing results for IS. Recall the following assumption of common support. Assumption (Common support). Ta(als) > 0 - To $) > 0, Vs E S,a A.
If Assumption 3 holds, IS is unbiased (i.e., [- = v )). and its variance is [27]:
V[o*5]= = Vandi [V (s)] + Eund, (pl(a R(s, a)]] + Ex-di [Eu-n [p(a]s) (x ())
where ( a)² = V R(..( [r] is the variance associated with the reward function R(s, a). The first term reflects the inherent randomness from the state distribution
related to importance sampling. The second term reflects the randomness in the behavior policy, whereas the third term reflects the randomness in rewards; these two terms are affected by the distribution of importance ratios p(als). When Assumption 3 is not satisfied, the IS estimator is biased [30]. where the bias is related to actions with no support: Bias[ [[ (TT.) = Eg-d, ELEu(+..))) Te (()s) a)], with
(s, mp) = {a (a(as)) = 0} denoting the set of unsupported actions.
Intuitively, when Assumption 3 does not hold. the C-1S estimator can make use of information from the counterfactual annotations for unsupported actions, thereby reducing bias compared IS (Section 4.1). For cases when IS is already unbiased, counterfactual annotations play the role of additional data and should help further reduce variance (Section 4.2).
4.1 Bias Analyses for C-IS
To formalize the effect of counterfactual annotations on support, we state the following assumption.
Assumption 4 (Common support with annotations). (als) > 0 Tb (als) > 0, Vs E S,a E A.
Assumption is weaker version of Assumption 3, because Ty. (als) > requires either Waass, (a]s)) > 0 (same as Assumption 3, assuming W Wals, a) * 0) or (als. ()Tx(āls) > 0 for at least some á E A {a). In other words, information about action a can from either factual sample or counterfactual annotations (recall Definition 1). Next, we state the main results for the bias of C-IS (unless specified otherwise, expectations are taken with respect to E.), These results hold for any nonzero w and directly generalize to the special case of C*-IS where the weights are 1/ Al.
5

---

Theorem 1 (Unbiasedness of C-IS). In the bandit setting, when both Assumptions and 4 hold, the C-IS estimator is unbiased, Blūc-isi- = v(Te)).
Proposition 2 (Bias of C-IS due to support). When Assumption 1 holds but Assumption 4 is violated, Bias[oc4s] = -Es-d1 I- _EE((...,))) ) Fe(als))(s a) where U(8 Tb+ = {a Tb. (a|s) 0} are
unsupported actions in the counterfactual-cne -uggmettted-eeeeeee dataset.
Proposition 3 (Bias of C-IS due imperfect annotations). When Assumption 4 holds but Assump-
tion / is violated, Bias( = Bynds Buwna(ts) [ów (8, a) 6G(8, a)]. where we measure violation of
Assumption I as (s a) = LE ((,a)( [g] - R(ss, a), and ów a) = (1 W(als.a)m,(als))
R6+ (a|s)
Proposition 4 (A sufficient condition for bias reduction). Assumption holds (but Assumption is violated). R(s, a) 2 0 for all s E S. E A. and there exists (s. a) such that Th(als) 0,
T6 (a|s) > 0, ne (als) )) > 0, R(s, a) > 0, then [Bias[iC-S]]| < [Bias(o*5)
There are two sources of bias for C-IS: missing annotations contribute to the bias as the rewards of unsupported actions (Proposition 2), whereas imperfect annotations contribute to the bias as the annotation егrоr over supported actions (Proposition 3). If both assumptions are violated, the resulting bias is the combination of the two (see Appendix C). If both assumptions hold, C-IS is unbiased (Theorem 1). Even when not all counterfactual annotations are collected (Assumption 4 is violated), C-IS can evaluate more policies without bias (assuming perfect annotations), because there is a larger space of policies "supported" by the saatirrffcttullaaggeeetee least one counterfactual annotation for an action with no support the factual data, C-IS has less bias than IS (under mild conditions, Proposition 4). Lastly, we note the useful corollary of Theorem 1. Corollary 5 (Expectation of augmented importance ratios). Lel Piw = pp EaEAM(ay w given T and w. Under Assumption 4, [[ 1.
dataset. In particular, if there is at
Remark. Corollary 5 suggests that for each sample, Piv plays a similar role as the standard importance ratio P in IS, which may be used for calculating the effective sample size (ESS) [31]. Naturally, we can also create a weighted version of our proposed estimators (e.g.. C-WIS), with the normalization factor defined using Pw-
4.2 Variance Analyses for C-IS
Compared the bias analyses above, the variance of C-IS has more involved dependence on weights up as well as the variance of the annotation function, aG (8, a)² = V Vo-G(=aa) [g]. For clarity, defer the full derivations to Appendix C.3; here, we present results for C*-IS where the weights are all set to 1/|A and the annotation function has the same variance as the reward function. Theorem (Variance of C*-IS). Assuming (G(s a)² = oR(s, a)2, under Assumptions and 4.
VI0C-111 V Va-d, (s)] + Eawd, (a) [mo(s plals)² (R(s,a)²]
where p(als) [e(ale) the importance ratio under the original behavior policy.
my(a|s]
Proposition 7 (Variance Reduction of C*-IS). Under the premise of Theorem 6, V[OC*-IS I V[S
Comparing Eqn. (2) with the three terms of the variance decomposition of IS in Eqn. (1), we note that the first term Va-d, (V*=(s) is identical, the dropped second term (of Eqn. (1)) is non-negative vari- ance term, and the third term is scaled by a factor To (a|s) S (for each instantiation of the expression inside the expectation), leading to guaranteed variance reduction (Proposition 7). We derive the full variance decomposition for C-IS in Theorem 13. Unlike C*-IS, variance reduction is not guaranteed for C-IS. This is due to additional non-negative terms that depend on the variance/covariane of weights w and terms that depend on the difference in variance between annotations and rewards C a)² a (2 a²² (could be positive or negative); these terms all vanish to zero in the case of C*-IS where weights are constant (1 ([) and as a)² =
4.3 Extensions to C-PDIS
We note that the corresponding results in the bandit setting can be derived for the MDP setting using an induction-style proof, with similar interpretations of the factors that contribute to reduced bias and reduced variance when compared to standard PDIS. Below, we briefly demonstrate how the unbiasedness result (Theorem 1) extends to the MDP setting. We further explore the sequential RI. setting in the empirical experiments.

---

Theorem 8 (Unbiasedness of C-PDIS), In the MDP setting, when both Assumptions 2 and 4 hold, the C-PDIS estimator is unbiased, E[GC-PDis]= = (TTe).
Proof Sketch. Here, we explain the intuition behind the proof for C*+PDIS, which proceeds via backward induction (Figure 4). In the recursive definition (Definition 4), we aim to show that every er-++1 is unbiased estimator of the horizon-t value function. At each horizon t, we view the problem as a one-step bandit problem (reducing the estimator to C*-IS), where the factual action leads to factual trajectory and the counterfactual action(s) leads to the counterfactual annotation(s), both of which are used to construct unbiased estimates of horizon-/ Q-values (for a, and i, respectively). In the end, the estimates from the two branches are combined according to Te, resulting in the correct expectation of the horizon-L value of state 8. See full proof for C-PDIS in Appendix C.4.
Figure 4: Illustration of proof idea. (i) The factual
(ii) t-py-] (is(ona))
estimate -1 provides an unbiased estimate of the horizon-(t + 1) value of state St+1. (ii) When com- bined with the factual reward Tt. we obtain an un- biased estimate of the horizon-t Q-value of (st, a.). (iii) By assumption, the counterfactual annotations provide unbiased estimates of the horizon-t Qavalue of (st. ā). (iv) The factual and counterfactual esti- mates are combined using Te- For clarity, we omit details about state distributions here (see appendix).
(Iv)
a11= (x.)
E/er
En (4) a]]
8,
q
(iii) Bly"| (t.44
4.4 Practical Implications
So far, we have been focusing on the theoretical framework for incorporating counterfactual an- notations into OPE. However, the actual implementation of this approach poses several practical challenges. We believe this underscores the fact that this is a rich area for research with many potential directions. In this section, we address several real-world scenarios that do not adhere to the theoretical assumptions - specifically, when annotations are biased, noisy, or missing.
Correcting annotation bias. Comparing Assumptions 1 and 2, we note an important distinction between the bandit setting and the sequential RL setting. For bandits, we simply want G to mimic the reward model R. contrast, for the RL setting, G, should ideally mimic the Q-function of the evaluation policy Q" Such annotations can be difficult if not impossible to obtain in practice (e.g.. for healthcare, would require asking clinicians to reason about a sequence of counterfactual actions and predict the outcome). Thus, we additionally consider a relaxation of Assumption 2 where instead Ey--G.ss.a) [g] = OeT reflecting expected return under the behavior policy (which is more likely in practice). This annotation bias 6g = Q Q% results in a biased estimator (Proposition 3). To correct this bias, we suggest first estimating the annotation bias function éa(s, a) using an approximate MDP built from offline data, and then mapping each annotation as 9 = go - EG (s, a) (see Appendix D.I for details). In Section 5.2, we empirically measure the impact of this alternative assumption and the bias-correction procedure (which we denote as Q + -Tee on OPE performance.
Reweighting noisy annotations. So long as Assumption or 2 is satisfied, the noise (i.e., variance) of the annotations does not affect unbiasedness; however, as shown in Theorem 13, the variance of our proposed estimators directly depends on how noisy the annotations are. Intuitively, if the annotation variance is smaller than the reward variance, we want the final estimate to "listen" more to the annotations and less to the factual data (and vice versa). We empirically explore the impact of annotation noise in both Section 5 and Appendix F,, noting that while using equal weights (as in C*-IS) outperforms standard IS, adjusting weights based on the relative magnitudes of o and og can further improve OPE performance.
Imputing missing annotations. For many real-world domains, it is unlikely that we can obtain an annotation for every counterfactual action every time step (the total number of annotations needed is - 1T) While desirable to use equal weights as in C* (and C*-PDIS) due to its variance reduction guarantee, this not possible if some annotations are missing (in which case the factual data must have =n = 1), and this can actually lead to higher variance (see Appendix D.2 for an example). To alleviate this variance increase, we suggest estimating an annotation model G from available annotations and using it to impute the missing annotations (see Appendix D.2). Although & may be a biased estimator of G (due to annotation noise) and introduce additional bias to the final estimate, we empirically observe favorable bias faa-variance trade-off (Section 5.2).
7

---

In general, one would expect more counterfactual annotations to reduce both bias and variance; at the same time, these annotations may be imperfect (biased or noisy) and directly increase bias or variance. Our analyses in Section 4 and Appendix C show that both bias and variance depend on weights w, suggesting the weighting scheme as a key mechanism to achieve optimal bias and variance. In Appendix D.3 we explore an analytical approach for solving the variance-minimiz weighting scheme and note the solution is highly non-trivial. We empirically explore the impact of different weights in Appendix E. and note that using equal weights (as in C*-IS) is promising heuristic, since it achieves good performance in most settings. We believe that optimizing the weights can further improve OPE performance and is interesting direction for future work.
5 Experiments
First, through suite of simple bandit problems, we verify the theoretical properties of C-IS. Then, we apply our approach to a healthcare-inspired RL simulation domain, where we compare the performance of our proposed approach, C-PDIS, to several baselines in terms of their OPE accuracy and ability to rank policies, and explore robustness to bias, noise, and missingness in the annotations.
5.1 Synthetic Domains Bandits
We consider class of bandit problems with two states {s1, $2} (drawn with equal probability). two actions A = {/, ' (recall Figure 3), and corresponding reward distributions R(s; a) ~ N (R((s 2²). Without loss of generality, we assume / is always taken from 82 by both m, and n.- For 81, we consider deterministic policies in which one action is always taken, and a stochastic policy that takes the two actions with equal probability (see column/row header in Table 1). Given (To, xe), we draw 1. 000 samples following Ty and then evaluate T, using various estimators, including standard IS, the naive baseline of adding counterfactual annotations as new samples (Section 3.1), and C*-IS. We assume that counterfactual annotations are only available for 81, and all annotations drawn from the true reward function. We measure the bias, standard deviation (std, the square root of variance), and root mean-squared error (RMSE) of the estimators with respect to (TTe).
Naive baseline fails due to bias, whereas C can duce bias and/or variance compared to IS. In Table 1,
Table 1: Summary of performance on the bandit problem for various ma (rows) and He (columns). where each policy is de- noted by its probabilities assigned to the two actions from $1. Each cell of the table corresponds
we display the results for Ris,// 1, R(
2,
(e2-)) 1, a = 0.5 (other settings in Appendix 1) The naive baseline fails to improve upon IS (and often underperforms IS in terms of RMSE) and can have a nonzero bias even when IS is unbiased (Table 1, row 2, column 2). C*-IS achieves a lower RMSE than IS across all settings considered. The benefits of C*-IS align with our theoretical analyses. (i) Bias Reduction for Support-Deficien Data. When Th is deterministic (first row), the unselected action has poor support and IS has a nonzero bias whereas C+-IS is unbiased. Though C*-IS sometimes has a larger variance than IS, the bias reduction outweighs the variance increase and leads to overall lower RMSE, (ii) Variance Reduction for Well- Supported Data. the second row, data generated by Ty has full support. Both IS and C*-IS are unbiased, but C*-IS leverages counterfactual annotations to achieve lower variance and lower RMSE.
(mb, ne) combination, for which we report (bias, std, RMSE) for three estimators: IS in the top row, naive in the middle row, and C*-IS in the bottom row. Settings with To(s)) = [0, 1] are omit- ted due to symmetry.
me
1, 0]
[0, 1
[0.5,
We
-1 0.6 1.2
-0.5 0.5 0.7
[1, 0]
0.2
1.8
1.8
0.1
0.7 0.7
0 0.7
0.7
0 0.5 0.5
0
0.9 0.9
0
1.6
1.6
[0.5,
1
0.2
1.8
1.8
0 0.5
0.5
0
0.7
0.7
We vary the assumptions (e.g., weights in C-IS, noisy/missing annotations) and present further exper- iments in Appendix 1. These results suggest that (i) Equal weights (in C*-IS) is good heuristic though not always "optimal" and (ii) Imputing missing annotations can reduce variance.
5.2 Healthcare Domain- Sepsis Simulator
Next, we apply our approach to evaluate policies in simulated RL domain modeled after the physiology of sepsis patients [32]. Following prior work [22], we collected 50 offline datasets from the sepsis simulator (using different random seeds) each with 1000 episodes by following an e-greedy behavior policy with respect to the optimal policy where e = 0. We considered a set of deterministic policies (including the optimal policy) as evaluation policies, which have different performance and
8

---

Table 2: Comparison of baseline and proposed estimators in terms of OPE performance (RMSE. ESS). ranking performance (Spearman's 's rank correlation) and binary classification performance (accuracy, FPR, FNR) on the sepsis simulator, reported as mean + std from 50 repeated runs. Bolded results are the best for each metric, whereas highlighted results outperform all baselines.
Estimator
RMSE
EES
Spearman
&Accuracy
%PPR
4. 1
Baseline
PDIS (wlo annot.)
0.113
76.8 2:40
0.596
76.5 315
33.7
15.9
Naive unweighted (G (
0,128 20006
207.2
=015
0.089
50.0 =60
11.6 #&3
78.1 #136
Naive weighted (0 9mh
0.097 20006
300.8
1116
20177
64.3 -47
24.0 2:27
44.3 2114
Proposed
C PDIS (G 1G-99 QT))
0.013
994.0 1001
0.995
1000
95.7 =31
4.5 159
#53
ideal case
C*ID (G Qm)
0.070
994,0 1001
0,961
86.8 =22
22.0
8.2 2113
relaxing Assump. 2
C. PDIP (G 9th 6%)
0.028 20.007
994.0
10.1
0.979
20.00
90.1 =54
4.2 16.6
14.1 290
PDG (basaline)
CT-POIS naney snrol
POIS (osssire)
C-PDI8. wi impulation C*MPONS wf mouusaion
CXPOIS - on)
ideal case
C*PDII gh Qr-)
C-PDIS (G 9r))
RMSE
0.1
RMBE
0.0
0.0
Sparmmn
Spaeemen
0.2
Corss
0.5
0.5
0.1
So. Class
Acourasy
1.0
Bin Clees
Alsurecyy
0.9
0.3
0.0
815 ofaensaatiionn moiso
0.5
1.0
0.0
fraction of annotated semples
1.0
Figure 5: (Left) RMSE of C*-PDIS vs. distance to Te (in terms of KL divergence) for each Te- plotted with linear trend lines. OPE error increases as Te becomes more different from behavior. (Center&Righh Performance of our proposed approach under noisy and missing annotations. Trend lines show average of 50 runs + one std. C**PDIS is generally robust to noise, and imputing the missing annotations can help maintain competitive performance (relative to the ideal setting) even in the presence of high degrees of missingness.
varying degrees of similarity vs behavior. We compared our proposed estimator (with different annotation functions) with a set of basclines, including standard PDIS (without annotations) and two naive baselines (with perfect annotations): "naive unweighted" simply adds counterfactual annotations as new trajectories and has the same issue discussed in Section 3.1, whereas "naive weighted" reweights the annotations at the trajectory level instead of per-decision. See Appendix E.2 for detailed experimental setup. As the main OPE metric, we report RMSE of value estimates true values as well as the effective sample size (ESS). Additionally, we report metrics for two downstream uses of OPE for model selection. (i) When used rank policies. We report the Spearman's 's rank correlation between ū(T.) and v (T)) (computed over all म. 's) [22, 26). (ii) When used to determine whether &e is better worse than TT- We formulate binary classification problem of u(T.) > v(m)) vs (TT)) < U(Tb). and report the accuracy, false positive rate (FPR) and false negative rate (FNR).
C*-PDIS outperforms all baselines across all metries in the ideal setting. As shown in Table 2, when all counterfactuals are available and annotated with the evaluation policy's ' Q-function (G = Q*=), C*LPDIS outperforms baseline PDIS (without annotations) in all metrics, demonstrating that it provides more accurate OPE estimates. In contrast, the two naive approaches fail to provide accurate estimates and often underperform standard PDIS.
C*-PDIS is robust to biased annotations. Under the more realistic scenario where = QT i.e., annotations summarize the future returns under ne rather than me, we observe a degradation in all metrics compared to the ideal case, though C*-PDIS is still superior to PDIS (Table 2). Applying the bias correction procedure (G Q)= + QTe, see Appendix D.I) helps in recovering performance closer to the ideal case, especially when Te is far from To (Figure 5-left).
Variance reduction of C*IP outweighs the effect of noisy annotations. When annotations are perturbed with increasing amounts of noise (Figure 5-center). performance degradation is minimal even at the highest level of noise tested (with a std of 1, which is large relative to the reward range [-1, 1]. and larger than 0.31 the std of initial state values). Our estimator remains competitive relative to baselines, suggesting that the benefit of variance reduction from additional data (through counterfactual annotations) outweighs the variance increase from annotation noise, even when annotations are much noisier than factual data. See Appendix E.2 for variations of this experiment.

---

Collecting more annotations and imputing missing annotations improves performance. As the amount of available annotations increases (Figure 5-right), our approach interpolates between baseline PDIS and the ideal case of C*-PDIS with a monotonic improvement in performance. Furthermore, imputing annotations achieves better performance, suggesting it is promising strategy when not all annotations can be collected in practice. See Appendix H.2 for variations of this experiment where the imputed annotations have varying degrees of bias due to annotation noise.
6 Related Work
There is rich literature on statistical methods for offline policy evaluation (OPE), including direct methods (DM), importance sampling (IS), and doubly-robust (DR) approaches [24, 26]. DM directly uses offiine data to learn the value function of the evaluation policy (e.g., using model-based or model-free approaches) [33, 34j. We do not consider DM in our work since it often involves function approximators whose bias and variance may be difficult to analyze [35]. On the other hand, IS uses a weighted average of trajectory returns to correct the distributional mismatch between the evaluation and behaviour policies [28, 27]. Our proposed estimator directly builds on IS and uses counterfactual annotations to reduce its variance (and bias), while carefully addressing the nuances involved with reweighting the counterfactual annotations to maintain the unbiasedness property. Finally, DR approaches combine IS and DM and reduce the variance of IS by using the estimates from DM control variate [27, 36-38). Our approach is a complementary source of variance reduction and may be combined with DR approaches by modifying our current definitions to include control variate. We note that other approaches exist for managing the variance of IS in long-horizon settings by considering the stationary or marginalized state distributions [39-41]. Incorporating counterfactual annotations into these estimators is an interesting direction of future research.
Our work focuses on OPE rather than policy learning, but the broader theme of human input for RL has recently gained renewed attention, particularly in natural language processing tasks [42-44]. In many of these problems, human input is in the form of preferences (or rankings) over actions, states, or (sub- stab)ttraecttoiiss [45]. Other related annotation approaches also exist in non-RL areas, where past work has proposed to ask annotators to alter text to match a counterfactual target label [46] and incorporating annotations of potential unmeasured confounders [47]. In contrast, our work investigates the role of specific form of human input, counterfactual annotations in offline RL, in improving OPE performance. We focus on offline evaluation due to its practical importance in high-stakes RL domains such as healthcare, though our insights could also potentially benefit offline learning in these domains. While we did not discuss how counterfactual annotations are obtained, our theoretical analysis establishes thorough understanding of their desirable characteristics. This can help motivate methods for converting different forms of human feedback into useful counterfactual annotations (c.g., learning reward/annotation models from human preferences [42]). Conversely, progress in the field of preference learning and saaminngtt--ran may benefit our approach by providing mechanisms to solicit high-quality annotations [48].
7 Discussion & Conclusion
In this paper, we propose novel semi-offline policy evaluation framework that incorporates counter- factual annotations into traditional IS estimators. We emphasize that the naive approach of viewing annotations additional data can lead to bias and propose simple reweighting scheme to address this issue. We formally study the theoretical properties of our approach, identifying scenarios where bias and variance reduction is guaranteed. Driven by a deep understanding of these theoretical properties, we further propose practically motivated strategies to handle biased, noisy, or missing an- notations. Through proof-of-concept experiments on bandits and healtheare-inspiree RL simulator, we demonstrate that our approach outperforms standard IS and is robust to imperfect annotations. Our semi-offline framework serves an intermediate step between offline and online evaluations and has the potential to enable practical applications of RI. in high-stakes domains. Though motivated by current limitations of offline evaluation, we caution that our approach is not meant replace existing OPE methods, but rather to complement them. Collecting annotations from domain experts comes at a cost (of real human time and labor), and thus, our approach should only be applied after a policy has passed all checks on retrospective data. While not explored in this paper, future work should focus on assessing the quality of counterfactual annotations the domains of interest through human experiments. See Appendix A for more detailed discussions on limitations, societal impacts, and future directions. Overall, we believe our contributions will inspire further investigations into the practical obstacles that emerge in semi-ofiline evaluation (e.g., devising human-centered strategies for soliciting counterfactual annotations that align with theoretical assumptions) and will bring RI. closer to reality in healthcare and other high-stakes decision- domains.
10

---

Acknowledgments
This work was supported by the National Library of Medicine of the National Institutes of Health (grant RO1LMM13322 to JW). The views and conclusions in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the National Institutes of Health. The authors would like to thank Michael Sjoding and members of the MLD3 group for helpful discussions regarding this work, as well as the anonymous reviewers for constructive feedback.
Data and Code Availability
The code for all experiments is available at http:///ttthbbooo///llD/////oott Semmro/ SemiOPE.
References
[1] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint arXi::13/2.5602, 2013.
[2] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540;:529-533 2015. URL. https://doi.org 10. 1038/nature 14236.
[3] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panncershelvam, Mare Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016. URL https://doi.org 1r0/ 1038/nature
[4] Ilge Akkaya, Marcin Andrychowicz, Maciek Chociej. Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino. Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving Rubik's cube with a robot hand. arXiv preprint arXiv: / 09/0.07/ 13, 2019.
[5] Nevena Lazic, Craig Boutilier, Tyler Lu, Eehern Wong, Binz Roy, MK Ryu, and Greg Imwalle, Data center cooling using model- preddetivee control. Advances in Neural Information Processing Systems, 31, 2018.
[6] Jeff Wu, Long Ouyang, Daniel M Ziegler, Nisan Stiennon, Ryan Lowe, Jan Leike, and Paul Christiano. Recursively summarizing books with human feedback. arXiv preprint arXiv:2109.10886 2021.
[7] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Gray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models follow instructions with human feedback. In Advances in Neural Information Processing Systems, 2022. URL https://openreviewneeee Stt.e//e///ooooumn//ttKssAAAAA
[8] Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: A survey.
ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
[9] Katyaini Lakkaraju. Human- Human-Centric Machine Learning: Enabling Machine Learning for High- Dicision-Making PhD thesis, Stanford University, 2018.
[10] Shayan Doroudi, Vincent Aleven, and Emma Brunskill. Where's 's the reward? A review of reinforcement learning for instructional sequencing. International Journal of Artificial Intelligence in Education, 29: 168-620, 2019.
[11] Shengpu Tang, Aditya Modi, Michael Sjoding, and Jenna Wiens. Clinician-in-the-loog decision making: Reinforcement learning with near-optimal set-valued policies. In International Conference on Machine Learning, pages 9387-9394 939779996,.67 2020. URL http://prroceedings mir.press/s 19taal199/.//.///aaa
[12] Shengpu Tang, Maggic Makar, Michael Sjoding, Finale Doshi- Velez, and Jenna Wiens. Leveraging factored action spaces for efficient offline reinforcement learning in healthcare. In Advances in Neural Information Processing Systems, pages 34272-34286 2022. URL https://openreview.ct http:://oppeeeeeeeeeeeeerrnnnnea
[13] Christopher M Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning, volume 4. Springer, 2006.
[14] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- -bandtt approach to personalized news article recommendation. In Proceedings of the 19th International Conference World Wide Web, pages 661-670, 2010.
[15] Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly. Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Scalable deep reinforcement learning for vision- based robotic manipulation. In Conference Robot Learning, pages 651-673, 2018.
11

---

[16] BM Adams, HT Banks, Hee-Dae Kwon, and Hien T Tran. Dynamic multidrug therapies for HII: Optimal and STI control approaches. Mathematical Bioxciences & Engineering, 1(2):223-241, 2004.
[17] Chiara Dalla Man, Francesco Micheletto, Dayu Lv, Mare Breton, Boris Kovatchev, and Claudio Cobelli. The UVA/PADOVA type 1 diabetes simulator: New features. Journal of diabetes science and technology. 8(1):26 34, 2014.
[18] Jinyu Xie. Simglucose (v0.2.1), 2018. Available: https//ggihua.ccm////x/22//nnngn Accessed on 2023-01-01.
[19] Ian Fox, Joyce Lee. Rodica Pop-Busui, and Jenna Wiens. Deep reinforcement learning for closed-loop blood glucose control. In Machine Learning for Healthcare Conference, pages 508-536. PMLR, 2020.
[20] Omer Gottesman, Fredrik Johansson, Joshua Mcier, Jack Dent, Donghun Lec, Srivatsan Srinivasan, Linying Zhang. Yi Ding. David Wihl, Xuefeng Peng, et al. Evaluating reinforcement learning algorithms in observational health settings. arXiv preprint arXiv: 12298, 2018.
[21] Omer Gottesman, Fredrik Johansson, Matthieu Komorowski, Aldo Faisal. David Sontag, Finale Doshi- Velez, and Leo Anthony Celi. Guidelines for reinforcement learning in healthcare. Nature medicine, 25(1):
16-18, 18, 2019.
[22] Shengpu Tang and Jenna Wiens. Model selection for offiine reinforcement learning: Practical considerations for healthcare settings. In Machine Learning for Healthcare Conference, pages 2-35, 2021. URL https://roceeedngg.mlir
Tateess/v19///0 49/tang2
[23] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.0 016405..63,3, 2020.
[24] Cameron Voloshin, Hoang Minh Le, Nan Jiang, and Yisong Yue. Empirical study of off policy policy evaluation for reinforcement learning. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, 2021. URL http:://neemeeiiiee.ee//mmmeett "eef/forummmddIssiKkk....
[25] Sonali Parbhoo. Shalmali Joshi, and Finale Doshi- Velez. Generalizing off- policy evaluation from causal perspective for sequential decision decision-making arXiv preprint arXiv:2201.0820 2022.
[26] Tom Le Paine, Cosmin Paduraru, Andrea Michi, Caglar Gulcehre, Konrad Zoina, Alexander Novikov, Ziyu Wang, and Nando Freitas. Hyperparameter selection for offline reinforcement learning. arXiv preprint arXiv:2007. 09055, 2020.
[27] Miroslav Dudik, Dumitru Erhan, John Langford, and Lihong Li. Doubly robust policy evaluation and optimization. Statistical Science, pages 485-511, 2014.
[28] Doina Precup. Richard S Sutton, and Satinder P Singh. Eligibility traces for off off-policy policy evaluation. In Proceedings of the Seventeenth International Conference on Machine Learning, pages 759-766, 2000.
[29] Aman Agarwal, Soumya Basu, Tobias Schnabel, and Thorsten Joachims. Effective evaluation using logged bandit feedback from multiple loggers. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 687-696, 2017.
[30] Noveen Sachdeva, Yi Su, and Thorsten Joachims. Off-policy bandits with deficient support. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery &Dta Mining, pages 965 905.975,222 2020.
[31] Victor Elvira, Luca Martino, and Christian P Robert. Rethinking the effective sample size. International Statistical Review, 90(3):22-5550 2022.
[32] Michael Oberst and David Sontag. Counterfactual off-policy evaluation with gumbel-max structural causal models. In International Conference on Machine Learning, pages 4881-4890. PMLR, 2019.
[33] Cosmin Paduraru. Off-policy Evaluation in Markov Decision Processes. PhD thesis, McGill University, 2012.
[34] Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In International Conference on Machine Learning, pages 3703-3712. PMLR, 2019.
[35] Sonali Parbhoo, Omer Gottesman, and Finale Doshi- Velez. Shaping control variates for off-policy evaluation. In Offline Reinforcement Learning Workshop Neural Information Processing Systems (NeurIPS), 2020.
[36] Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement lcarning. In International Conference on Machine Learning, pages 2139-2148. PMLR, 2016.
[37] Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 652-661. PMLR, 2016.
[38] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference on Machine Learning, pages 1447-1456. PMLR, 2018.
12

---

[39] Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: heriiitehoorion oft-policy estimation. In Advances in Neural Information Processing Systems, 2018.
[40] Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal oft-policy evaluation for reinforcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems, 2019.
[41] Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. DualDICE: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, 2019.
[42] Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021, 2020.
[43] Rajkumar Ramamurthy, Prithviraj Ammanabrolu, Kianté Brantley, Jack Hessel, Rafet Sifa, Christian Bauckhage, Hannaneh Hajishirzi, and Yejin Choi. Is reinforcement learning (not) for natural language processing: Benchmarks, baselines, and building blocks for natural language policy optimization. In International Conference Learning Representations, 2023. URL http:://ppeneeiie.ee///ooura Sallzds2uUyB.
[44] Qisen Yang, Shenzhi Wang, Matthieu Gaetan Lin, Shiji Song, and Gao Huang. Boosting offline rein- forcement learning with action preference query. In International Conference Machine Learning. 2023.
[45] Christian Wirth, Riad Akrour, Gerhard Ncumann, Johannes Fürnkranz, et al. A survey of preference-based reinforcement lcarning methods. Journal of Machine Learning Research, 18(136):1-44 2017.
[46] Divyansh Kaushik, Eduard Hovy, and Zachary Lipton. Learning the difference that makes a difference with coumterfactualll--ageeettte data. In International Conference on Learning Reprexentations, 2020. http:///eweee.eeeeooomom/t---a.
URL
[47] Megha Srivastava, Tatsunori Hashimoto, and Percy Liang. Robustness to spurious correlations via human annotations. In International Conference on Machine Learning, pages 9109-91 19. PMIR, 2020.
[48] Banghua Zhu, Jiantao Jiao, and Michael Jordan. Principled reinforcement learning with human feed- back from pairwise or k-wise comparisons. ICLR 2023 Workshop on Mathmatical and Empirical Understanding of Foundation Models, 2023.
13

---

A Further Discussions
Limitations. This work proposes and theoretically studies a new framework of semi-offline evaluation of RL policies. While our core idea is to incorporate human annotations into the evaluation process, we did not make use of real human annotations in our experiments and relied on simulations instead. Given the costs associated with user studies, we opted not to conduct user studies before we have a thorough understanding of when and why our approach works (or does not work) and how can be implemented in practice. Our present paper focuses on describing and analyzing a formal mathematical framework of counterfactual annotations, which provides valuable insights as to what types of annotations are useful, how they should be incorporated into OPE, and which factors impact performance (see method description in Section and theoretical analyses in Scction 4). Our experiments further demonstrate the robustness of our approach when we deviate from the ideal setting (see Section 5). Despite best efforts, our experiments do not capture all possible scenarios in the real world. We list several important practical implications in Section 4.4 and encourage future research into these directions. Additional areas of interest that we did not explore include: alternative forms of annotations (e.g.. preference, immediate reward), whether these other annotation types could be converted to match our assumptions so that our framework still applies, how best to design the question phrasing for the annotators, evaluating annotation quality, targeted annotation solicitation and optimizing annotation solicitation under budget constraint.
Ethical Considerations and Societal Impact. Since experiments only involved simulations and no real humans, we did not pose immediate ethical concerns or safety threats. Nonetheless, in high-stakes decision-making tasks such healthcare, computationally-deriiee RL policies must be carefully validated before their final adoption. While we are motivated by the current limitations of standard offline evaluation methods, caution that our approach is not meant to replace, but rather to complement, existing OPE approaches. Collecting these annotations from real human domain experts comes at cost, and thus recommend applying our approach only when a policy has passed all checks on retrospective data. We note that compared to traditional qualitative evaluations (e.g.. typically done by asking domain experts whether RL. recommendations make sense), our approach is less likely (though still possible) to affect the existing decision making or suffer from confirmation bias, since we do not need reveal the evaluation policy the annotation collection stage. Future work that adopts our framework should carefully design the annotation solicitation process (including when and how the question is posed to the annotators) so as achieve safe, non-disruptive evaluations of offline RL policies before their prospective use. Additionally, more work is needed to understand the extent to which humans can provide accurate annotations of counterfactuals. These human experiments should be addressed in the context of specific application domains and the target groups of expert human annotators.
Future Directions on Counterfactual Annotations. Our present paper establishes important theo- retical groundwork for using counterfactual annotations in semi-offline policy evaluation. However, we did not collect any real annotations with human annotators as those are outside of the scope of the main research question we seek to address in our current paper. To fully realize the impact of this work, real-world human experiments would be the necessary next step, with a focus on obtaining faithful annotations (with small bias and small noise). More specifically, would be important to empirically measure if and how various factors influence annotation quality, including: horizon t (annotating beginning of an episode or the terminal step), the inherent stochasticity associated with the annotated state-action pair and how often they appear in data (under TT). Equipped with this knowledge, it is then important to select which annotations to prioritize given a limited annotation budget. Many of these questions delve into the realm of HCI and are outside the scope of this paper's s methodological contributions for offline RL and OPF, and we encourage researchers and practitioners in different research areas (e.g., RL, HCI, healthcare, education) to build upon the ideas in our work.
14

---

B Toy Example for Intuition
(3) State diagram
(C) Counterfactual Annotations
(b) Factual dataset
(d) Unweighted augmented dataset
Figure 6: For ease of reference, Figure 3 is reproduced here. (a) The state diagram of bandit problem with two states and two actions. (b) A factual dataset containing two samples. (c) The factual samples augmented with counterfactual annotations. (d) The (unweighted) augmented dataset constructed from factual samples and counterfactual annotations. Compared to the factual dataset, the relative frequency $1 vs 82 changed from to :
Recall the example discussed in Section 3.1 (figure reproduced here in Figure 6). The bandit problem has two states {$1. $2) (drawn with equal probability) and two actions, up (/2) and down ( (S)) The reward from $ is +1 and from $2 is (i.e., rewards do not depend on the action), meaning all policies have an expected reward of 0.5. Suppose the behavior policy always selects / generating a dataset with poor support for policies that assign nonzero probabilities to > (Figure 6b). Now suppose also have access to human-provided annotations of counterfactual actions, but not all counterfactual annotations are available (either because they were never queried or the users declined to provide annotations). In our example (Figure 6c), one annotation is collected for the counterfactual action >> state $1, indicating that the human annotator believes the reward for taking action ' from state s1 is +1. To make use of this information, one might consider adding the counterfactual annotation as new sample. The augmented dataset (Figure 6d) would allow us to evaluate policies (e.g.. using IS) that assign non-zero probabilities to in state Unfortunately, this naive approach leads to biased results, which we walk through in detail below.
Consider an evaluation policy that takes ' 81 and / in 82, i.e., TT (81) [0, 1] and Te(82) = [1,0] (denoted in terms of the probabilities assigned to the two actions, / and \)-
If we use the original n, in the factual dataset (Figure 6b) where TT(31) = [1. 0.. Tx(2)) =
[1, 0). the IS estimator is ill-defined because we will encounter divide-by-zero error:
1 ( x (+1)
x+1)
1 (+1) ++ (0)) undefined
3
Instead, one may consider the behavior policy in the augmented dataset (Figure 6d), which gives (s1) = [0.5, 0.5], TT(82) = 11.0]. The IS estimate is:
2
x (+1)+ 0.5 x (+1)+ x (0)
3 0.5
3
However, as stated above, all policies should have a value of 0.5, meaning that 3 is a biased estimate. The core of the issue is because directly adding counterfactual annotations inadvertently changes the state distribution and results in a dataset inconsistent with the original problem. In particular, comparing Figure 6b vs 6d, the relative frequency of s vs $2 has changed from 1 1 2
Our proposed estimator addresses this issue by reweighting the factual data and counterfactual annotations in order to maintain the state distribution. Suppose assign weight to (s1, and 1 - & to ($1, Y) for some a E (0, 1), i.e., the two non-negative weights associated with $1 sum to 1. The sample (s2, / receives a weight of by default since it does not have associated counterfactual annotation. In this way. the state distribution remains equally split between 8) and $2.
Using Definition 1, we can calculate the augmented behavior policy Th- (81) [ax, 1 a). T&- (82) [1,0). Applying C-IS as defined Definition we see our proposed approach produces the correct, unbiased estimate of 0.5:
15

---

for 81,
a x x (+1) + (1 - a) x 1
x (+1)) =
for 82,
1 [ x (0) =0
overall: 2 0.5
+ (1
B.1 Another Example Illustrating the Weighting Scheme
Suppose similar to Figure 6, we now have a bandit problem with only single state {s} such that all policies have an expected reward of 1. Suppose the behavior policy always selects /. generating a dataset containing two samples: sample #1 (s, 7) with an annotation for Y sample #2 is simply (s, /") with no annotation for > In applying our approach, for sample #1 we can (0, 1), i.e., the two non-negative weights associated with sample #1 sum to 1; for sample #2 the weights are simply [1, 0j. Then, the average weights for state are W |s, 7) I+a and W(' |s. M) __ For example, if 0.8, then the weights for sample are [0.8, 0.2] and the average weights associated with state s are [0.9, 0.1]. Note that while the average weights W (used for calculating т&- and C-IS) are state-specific, the user-assigned weights w are sample-specific furthermore, the sample-specific weights should not be interpreted as "random", user may deliberately set weights to split equally into [0.5, 0.5], or to [1,0] which ignores the annotation if they believe it of poor quality.
assign weights [ar 1 ai] for some
2
Using Definition 1, we can calculate the augmented behavior policy To (s) = 1 C-IS as defined in Definition we see our proposed approach produces an unbiased estimate of 1:
2 1_0). Applying
1 + a
0 (+1)
1-a
(+11)
2
2
I-a
2
C Extended Theoretical Analyses
Unless otherwise stated, the estimators are for Te, i.e., è 6(Ta).
C.1 IS: Bias & Variance
We formally state and prove the bias and variance results for IS (informally described in Section 4). The proofs are adapted from existing literature [27, 30].
Theorem 9 (Unbiasedness of IS). In the bandit setting, when Assumption 3 holds, B[ii5] = v(Te)-
Proposition 10 (Bias IS). In the bandit setting. when Assumption 3 is violated, Bias jo = Exwdd Eoeu(e.).) R((aaa))ssss))) a)] where (s, Tb) = {a [<([s)))))) = 0) are unsupported actions in the dataset.
Proposition 11 (Variance of IS), In the bandit setting, when Assumption 3 holds, the variance of IS can be written as:
v(05 V Vandi [V** (s)] + Bandy (V (alma())) R(s, a)]] + Eandy (Ba-as(s) oR(s, a) where a a)) = V V)-R(e.)))))) is the variance associated with the reward function R(s,a).
Derivation for Bias IS IS (adapted from (30]).
Bias E1 v(Te)
Tb(a|s) (e(a))
= E snudy
Σ
(a(a)s)
R(s a)
-
andd
E
Σ ne Te(als) LaEA
E sovd]
Σ
Te(als))(s,aa)
Σ ((())))
aEA
16

---

E goudi
Σ
Te(a)s)((ssaa)
(El((s
Assumption holds, The (als)) = 0 for a E (s,, T6) and thus Bias[o = 0.
Derivation for Variance of IS (adapted from (27]). We apply the law of total variance:
V(0h)
(tw) (or)
V Vandi
(((e) [pr] + Eaadss WaanstelrmrReaalll
(e(a)s)
+ Bends V (e + Bawnsl)) (a (nwn(aa V Vonds Euwna(s)) [a(a E (rw
V Wndd [BawF(() (s) (R(ss a]] + Esndi (Vamm(s)lpR(ss.0 a]]] + Eavd, Bawns(s)
[r]]
Vond, [V (s) + Esnd, (a)m(s)\l(aasssfft a)]] + Esnd, [Bawno(s) [p(als)
C.2 C-IS: Bias Analyses
We start by showing unbiasedness of C-IS in the ideal case (Theorem 1). Theorem (Unbiasedness of C-IS), the bandit setting, when both Assumptions and hold, the C-IS estimator is unbiased, B[ic-1S] v(T)).
Proof of Theorem I. Starting with Definition 2.
E C-11
E
w p
whth pa
(EA((a)
Te(a
E swdd anuiT(e)
E
E Wn [w0] Tbt (a|s)
Er R(s,a) [r]
(ā s)
Bwew [wi]
Tbe (a|s)
(EAl(a)
Ta(āls)
E
Tb(a)s)
R(
Tot (d(s)
LaEA
aEA
(( (ā)
E
R(s, a)
goudy
Tb. (ā(s)
LEAA
aaEA
(3)
((lass)
[e(ā(s) R(s, a)
Thb (5)
AEA
REA
Te (āls)
E
To (āts)
R(s, @)
grdd
Io-fats
U
Σ (ā)s)) (() a)
E soeds
UEAA
E
[R(s, a)]
arudi ämTT
= E endd
[V* (s)
where in (1) we replace Ey-C(+,a) [g] with R(s â) following Assumption and combine with
R(,,) [r] in single summation over à E A. in (2) we swap the order of summations, in (3) we take out common factors that do not depend on a, and in (4) we use Definition 1 for g&- bā(ā))) which cancels out the denominator in the importance ratio on the next line.
D
17

---

Next, we look at two factors contributing to the bias of C-IS: lack of support and imperfect annotations. Proposition (Bias of C-IS due to support). When Assumption I holds but Assumption is violated. (((aas)R(ss)) a)] where U(ss, T {a : Tb (als) = 0} are
Bias[oC-15] = Eg [-
-EM((s.. seaer/acccullluggnntttee dataset.
unsupported actions in the
Proposition 3 (Bias of C-IS due to imperfect annotations). When Assumption holds but Assump-
lion I is violated, Bias( Bewd; Buwn.(s) [Bw (0, a) EG(s, a)}, where measure violation of Assumption I as cg (s, a) ((, [g] R(s, a), and dw (8, a) (1 W(als.a)
Tsi (als)
Proposition 12 (Bias of C-IS, combined). When both Assumptions and 4 are violated, Bias|oCis) Eg-di Eeet(s (a]a))) R((sa)) a)] + Bgwdi (EGEAV((S,))) dw (s, ne(als) ea a)
( Te (als) Ea(s, a)),, where U(s, Tb:) = {a (al(a))) = 0} are unsup- ported actions in the cenntterfaccallauggmmeee dataset, EG(s, a) EggG(ss R(s, a), and 68(8, a) (1 (1- W (alla.a)
Tn- [a]=)
Remark. There are two main sources of bias for C-IS, resulting from each of the two assumptions being violated. In Proposition 12, missing annotations (i.e., violation of Assumption 4) contribute to the bias through the first term the rewards of unsupported actions, whereas imperfect annotations (i.e., violation of Assumption 1) contribute to the bias through the second term the annotation error over supported actions. When both assumptions hold, C-IS only requires weaker version of the common support assumption to remain unbiased (Theorem I); consequently, compared to IS, there is a larger space of policies that C-IS can evaluate without bias. Note that the unbiasedness property is not affected by the user-defined weighting scheme (except that the weights must not be to 0 or 1) and directly applies to C*-IS. When only Assumption holds (Proposition 2), the bias is related to the negative rewards over unsupported actions. On the other hand, when only Assumption 4 holds (Proposition 3), the annotation error Eg contributes to the resulting bias and this contribution is scaled when the estimator can make of (unbiased) factual samples of the
by factor of 6w (s, a) state-action pair (s, a) (i.e., when T6 8) > 0 and Wa]s,, s, a) > 0).
We show Proposition 12 first and then discuss Propositions 2 and as two special cases.
Proof of Proposition 12.
Bias
15 v(TTe)
BunnWWalaa [w0) (a Tbp (a|s)
=
E sods
Σ
To(als)
E
(REA((((oma))
The (ā Eg ((s ) (((Te)
Te(ā]s)
E Walssa
[w0"
aEA
E
Σ
Ta(a|s)
Σ
W(āls,a)
Te (āls)
(R(s, + =c(s,a)
(ā(s)
LaE.)
(EA.U((TTTO))
W(aas, a) Te(a|s)
The (als) co(o,a) (0))))
v(Te)
W( (āls)
E
Σ
Ta(as)
Σ
R(s a)
-V(Te)
sndi
Tb (ā(s)
(EA
W (e
+ E
Ta(a)s)
Σ
EG (s,
smid
To
(EA
Te (als)
E
Ta(ass)
Toi (als) (8,
gnddi
(
Te (ā(s)
= E
Σ
(((ass)
R(s, a) - v(Te))
sods
Toe (ā]s)
( (a.
18

---

Te(a)s)
E
E
Σ Tālss))
EG (5,
soddi
Tb. (ā(s)
(a(s)) (EEA)
B
E
Ta(als)
(s,
gndd
Toe (a|s)
LEEA(u(s.m))
E
Te(a(s)R(s,a)
+ E gmud
AE Te(a(s)ca(s,a)
Σ
sodd
To(als) Thb (a|s)
E soudi
Σ LoEA(U((ams))
Te (a(a)s)W(als,)
(5, a)
E
Te Te(als)R(sso))
awdd
mEl
+ E anddi
E
=e(als)ec(s,aa)
where dw (s (1- W(a ((alsa)))aaas)))
ma+ [ala]
Note that (s, Tb+) C (((8,, Tb), because mh- Th- (a|s) 0 implies ma(als) (factual data does not contain action a) and (a]ss, a) = 0, vä E A (counterfactual annotations for other actions also do contain action a).
L
Proof for Proposition 2. Given Assumption but not Assumption
Bi
E|
v(Te)
W(āls,a) (ā( A(s, .i)
E andi
Σ mo(als)
Σ
v((Te)
T (āls)
(E.))((s.m.)
(ā(s))
E
Σ
Σ
(((als)((āsssa)
R(s, a)
E
Σ
Tee (a(a)))(ss.
s-d1
Tbbi (als)
snd,
(EA\U((B.To-)
(EEA)c((sm.))
LaE.A
E andi
Σ
Te(a))))((s,a) Σ
(e(a)))
aEA
E
E Eveulsmo Te(a(s))((s,a))
Proof for Proposition 3. Given Assumptions 3 and but not Assumption 1,
o- = [[]0-18]-0 - (
Te (als)) (R(s, α) + tec(s,a)) )
(a(s)) The (a|s)
E awd,
Σ (a(ass)
W(als,a) a)
R(s, ā) + Σ
W(āls,
- v(TTe)
The (āls)
aEA
aEAl(a)
(G(s a) )] v(Te)
Σ W (ā(s))
W a) (a(ā)s)
E
no(als)
R(s, ā) +
Σ
8 swdh
Tb- (ā|s)
To (als)
AEAA
aEA
aEd\fat
Te (
E
((lsss)
R(s,ā) a)
v(TT)
aodh
Te. (ās)
19

---

[a(sss Thy (ā)ss) (s a)
(ā]s,
srudi
LeE
Te (als) T (als)
To(als)W(als, a)
cG(s, a)
sodd
aadA
Σ [e(als)W(alss.) a) To(als) LEA
E s-di
Σ =e(((s)ca(s,ā)
co(s, a)
andi
To- (als)
LiEA
E (1-
W((ls, cc((,a)
E
andd am))(s)
Tb- (als))
While it is generally true that the space of policies that C-IS can evaluate without bias is larger than that of IS, since the lack of support leads to C-IS being biased towards (similar to the case of standard IS), the magnitude of bias of C-IS is not guaranteed to be less than standard IS without additional assumptions about the rewards. However, if all rewards are non-negative, then under mild assumptions, we can prove the following bias reduction result.
Proposition 4 (A sufficient condition for bias reduction). If Assumption holds (but Assumption violated), R(s, 2 for all s S. E A. and there exists (s.a) such that Ta(as)) Tb (a|s) 0, Te (als) 0, R(s, a) > 0, then [Bias [s < (Bias(o*5)
Proof. (ias(("S)
Biiss 1511
E srudi
Σ ael((s))))
To(als)R(s,aa)
Σ Eueutssoo (e(a)s)R(s,a)
snuds
E ardh
Σ E Te(a R((
Te
Eneuia Te(als)R(s.0))
Σ
snidi
E swdd
Σ ) (((a)))
>0
Lastly, note useful corollary of Theorem 1.
Corollary 5 (Expectation of augmented importance ratios). Let Piv = w²pp + EεEA)Aa) wap
given 7 and w. Under Assumption 4, Espwy 1.
Proof of Corollary 5. Starting with Theorem and substituting R(s, = G(s,a) as the
constant reward and annotation for all S,a a E A, we have: E,+ (wo + =EEed(1a) 10th pa]
Exzd, (e))m =
20

---

C.3 C-IS: Variance Analyses
For variance analyses, we focus on the scenario where Assumptions and hold and bias zero. Below, we state the variance decomposition results under few assumptions about the weighting scheme and the annotation variance.
Theorem 13 (Variance of C-IS), Let (a(as)) = p melals) be the importance ratio defined using xy, (als) the augmented behavior policy, and assume variance of the annotation function and the variance
of the reward function are related by o oR(s,a)² oR(S, + (s) where (s, E I. then under Assumptions I and 4,
V[ocis] V ondd [ (s)] + Berdi Vanto(s)
E ( a() R(s. a)]]
+ Bxndy (aw))s))
Eaeap' (als) (aenp((p/WWlsss)oonlss
+ Bawd, (s))
+ Eawd, (s))
Σ EBEAp*(als) R(s (ww
(3)
+ Bxndt (a)))(s)
ExEAp' (ā|s)² (n(s) "dw
+ Bendi E Ba)))()
((s,a)
+ Eand, Eawn((s)
0, Σ OL
where C(8,a) =2
P (a:ls) p (asls) us)) R(s, az) ())(W(a)s,,), W(sl,,,)))
Corollary 14 (Variance of C*-IS). Assuming Cateeinnnnolss,aooo a) on(s, + where (s)
then under Assumptions I and 4,
v[00-118] = Vand, [V (s)]+ Eawd, Bawno(s) (o(a|s) =n(,,))²
+ Egsdd ( =e(a|s)²A
where p(als) (a(a))
Ty(a|s] is the importance ratio under the original behavior policy.
Remark. The variance decomposition in Theorem 13 contains eight terms. The first three terms correspond to the three terms in the IS variance decomposition in Equ. (1), the fourth and eighth terms are related to the variance difference between annotations and rewards, whereas the remaining three terms are all related to the variance (and covariance) of the weight distribution W(+Is, a). As we will demonstrate empirically (Appendix F. depending on the weight distributions, variance of C-IS may actually be larger than that of IS. While is difficult to guarantee a general variance reduction, we provide intuition for few special cases. (i) If the weights are constant (i.e., W (-]ss, a) is the same value for all instantiations of (s, a) in the data), then the last four terms will all vanish to zero. (ii) When the annotation function and reward function have the same variance, A (s, a) O, the fourth and eight terms vanish to zero; with this assumption, we can straightforwardly obtain Theorem 6 from Corollary 14. (iii) Suppose for each state-action pair (s, a). we set factual weights W Walss a) and counterfactual weights W(a a) O. Then, we effectively ignore all counterfactual annotations, and the variance of C-IS becomes identical to that of IS.
We prove the most general case for Theorem 13 first, and then derive Corollary 14 special case.
Proof of Theorem 13. We apply the law of total variance:
swdh (s) g-G(ee).wwW(saa)
w p
Σ
whth p
gi
aEAlfaa}
= VE E. (e)
wa pr
Σ
wa paga
E
V ceaa(e).r~
u per +r
Σ
w pa
ga
avdi
gr-G(s,)) w.w (s,a)
aEA\(a)
ardd
g-G((,). w.l.. (s,a)
aEAl(a)
(1)
(1)
21

---

As shown in the bias analyses, we have (1) Vandi [V*c We further apply the law of total variance on (1'):
(1') = snuds
Ey
W pr
Σ dEAl(a}
g
...(2)
arvb((s)
E
V VroM(saa,gGGas)) w~W((s,))
2 po aEAl(a)
wa wapa p 9
(2')
souda
arv
Since (r, g) and w are conditionally independent given (s, a),
E (2)
p E Bm= wiala Mr ())(()
Σ &EAl{a)
p w = wW 8º G(aa()))
s sn
ar)
E
y a>)
p¹ W(anaw Mam
Σ aEA((a)
D'Eusnw (aa Baa
and,
p+ (als)[((sss))) |
E a-id
V (+)
LãEA
where in the last step. apply Assumption to combine the expressions involving R(s,a) [r] Bgtaa(
and
[9]] (both are equal to R(s, a)) into a single summation over A.
We further apply the law of total variance on (2'):
(2') = gwddy ac)t((s)
V Ri. g~G(s,)
w p'r+
Σ
wa ppg
g
...(3)
dEAllta}
+ EynRls V WwnW(s.a) Gr,()
w purpr
Σ
wa p g
(3)
grdd (3)
aEAl(a)
Then we have
(3)
E
V VenR(saa) (
Σ aEA\(a)
Vonciee) ( 2 VorCiee)( Buun
a aidi am))((s)
E awdh awmmlss
E
p
Σ GEAlfat
pt (als,
E aud, (s)
E
Σ LeE
E
E
Σ (EA((()
()
aridi amt)(s)
where in the last step we substitute a) on(s, (o)
Letting g" for clarity, have
(3')
E Ep-R(ssa)
+2
Σ
u (ov=-W(s.))00' (d w ,p g wa)
soidi aw)t((s) g~G(s,)
BEA
0;00EA
22

---

I3 E
R(s,a)
Σ (ne
srdd anv gr(((s))
aEA
aizta
+
Σ (1))))))))))))))) x )((as))a((ss@)oo(lss...
ALRyEA
E
E
Σ (āls)) [((s,))) talls
Σ
srid (
LiEA
aEAlfa)
a;pia
2
Σ
(arls) p= (ayls) R(s,a,) R(s,a,) Co
Be EA
E E
( Σ p (ā]s)² R(s, a) ow
E soud am))(()
E
Σ p* ( on(ss a) (
(+)
LÃEAA
LÑEA
Σ ((. aEAM{a
andd (s))a(s)
(6)
auzta
Σ GLR
p (ails) pt (azls) R(s,a) R(s,a,) Cov (W(alls, W(aylsa))
anud as)TT(s))
Putting together expressions (1) through (7), we have the desired decomposition for V[ECIs].
Proof of Corollary 14. Here we derive the variance of C*-IS, which is C-IS with W a) = -A-1 Since the weights are constant, expressions (7) all vanish to zero because the variance and covariance associated with W(+ss, a) are both zero. We focus on simplifying the second, third, and fourth terms in the variance decomposition (which correspond to expressions (2) and (3) in the proof above; we denote the two parts of (3) as (3.1) and (3.2)). First, note that
Thh (a|s) Esed ())((s)
Eaed |A| (
= -AAI-1 (EBEA
= |A--1
Then,
(2) Egndy
V (a)
EREA P* pt (als) ((ās, a) R(s,a))
Egndi
(a)to())
Te(a(s) Eres
T/I (1/IA) R(s, a)
Eannyy
Varns(e)
[EEEATE Th (alss) a)]
Egnd,
W VaNts(K) [s){
(3.1) Egnd, Ba-zy(s)
(als)) W(lss a)² az) Edes (a(a))
Eannd Bawzs(s)
(1/ (1/1 ())
23

---

Bandh
EnEA Tb(als) EãEa Te [R
Rgnd
Eãed
Te(ss) an(
Bgnds
LIEA L (e( (e(
Bandi
EGEA mb(als) plass)
-Bendy BawxL(s) (m plds) on(s,))
(3.2) = Bonds (s))
EnEA(a)) ((b)) (s,
-Bndd E (s)
Telālee EdEdha (MAI (1/1A1) (s,
Bondi
EnEATb(als) mb(a)s) EREANTa) (a]s)) (8
Bandi
EREArIO) EoEAsT((lss) (a(s)) (s,
Bands
Eaedila Te(als) (s.
C.4 C-PDIS: Bias Analyses
Theorem (Unbiasedness C-PDIS). In the MDP setting, when both Assumptions and 4 hold, the C-PDIS estimator is unbiased, B[ vmx)).
First, we introduce a few definitions useful for the proof. Let the t-step state distribution be denoted 81 di, de T(s=)). Similarly, the t-step state-action distribution is df (s. a) = Pr(s: s, a, = a 81 d1, ay ~ x). Note that d'')(s') = Bs,a=d [p(s s'|ss, a)].
by dī (s) Pr(s,
Let d, di denote the distribution under the behavior policy. Recall the horizon-/ value functions: VT (s) 1.7. rr s). (*. a)
12 7t Tr s, de = a). Based ((+1):((s)) (s')]. Note that vTT.)) = Eg-d, (s)). Also recall Assumption 2, the perfect annotation function in the MDP setting satisfies Eg (g) Q (s,a) for (s, a) at step of the trajectory.
Th on the Bellman equation, Q7 a) = r(8, a) + 7 Ex'mp(s,a) (l+1):T
Recall the recursive definition of C-PDIS (Definition 4): JC.PDIS UT, with Up UT- Bt w Ps (re + -or--) + EaEAM(a,) w p. g. for t = T...1, where pf (alar)
(ā)s,)
Proof. We show this via backward induction on a sequence of horizon-t value functions of n. denoted by (s). The goal is to show that [er Egnde i ( ((r for all t = T...0 (for clarity, the subscript of expectation of the estimator may be omitted and assumed to be E with generated by the behavior policy na unless otherwise specified).
Base case. It trivially that E[vo] Eo-dr+1 Fe (1) after 1. T and s dr+1 can be seen as a dummy absorbing state.
since there more steps
Inductive step. Suppose [] Egndeti V ((41))(())) (s)] holds. For factual state-action pair (s, a) de occurring step we have
E (re + 20T- = 8,0rdd
E s,and,
rt +
E [V d'nden
(itter(d')
E s,a
rt +
E -h d'mp((13,)) ((ttaar(s))
E.
(s,
s,and.
24

---

To show the case for - 1,
E U [+1- = E
as Pt (rr + (VT-1) +
E
w/ pi oi
REAl(a))
Te Te(a)s) Tb. (als)
E ardde am)
E
E Eup-W(ala,o) [uu]
R. Ba,ande (ir + -r
(als))
Σ
of (((,)l9)))))
Tb. (āls)
aEAlfat
(als))
E
Tb(a|s)
W(als,
Q (s, a)
grude
Teb (ā|s)
LAEA
AdEA
Te (ā
(alas)
Qu.7 (8, a)
erude
To (ā(s)
LäEA
NaEd
(3)
((la)s)W(((o,cu))
[a(()))
Qur (8, a)
grids
(ā(s)
LEEd
aEd
Tee (āls)
E
Ib+ (ats)
2 (s, @)
grdde
(ats]
LEE
E gnd
Te(āls)
LaEA
E endde dooie
E
10th (s, a)]
E snude
[VTTe (s)]
where in (1) we replace E (3 [ with (T, a) following Assumption and combine with E, it's + -er-=] = (s, (as shown above) in single summation over à E .A, in (2) we swap the order of summations, in (3) we take out common factors that not depend on the inner summation a, and in (4) we use Definition 1 for πB- (āls), which cancels out the denominator in the importance ratio on the next line. The proof techniques are similar to that in Appendix C.2.
Since E[cr-c] = Eg [M ((41): (s)] implies E[UT-[+1] Eswd, [V (VTT(s)), and the base case Elva] Bewdr (VT++1) [+) true, by mathematical induction, we have the desired property that E B[jC-PDIS] E(ey] Eand, 12 (s)] u(Te).
25

---

D Extended Discussions on Practical Implications
D.1 Using Approximate MDP Model to Correct Annotation Bias
In the sequential RI. setting, if the annotation function reflects the expected returns under the hehavior policy, i.e. G2 Q then annotations have nonzero bias of éG, Q Q * O (since Q77 * QUT for meaningful OPE problems where Te * Tb), and consequenty, C-PDIS using such annotations becomes biased. While such annotations may aid in model selection (as shown in experiments), here we further propose a procedure to convert the annotations so that they better reflect the evaluation policy.
From the offline data, we first learn an approximate model of the MDP M, which includes the transition model p(s'|s, a) and reward model f(s, a). M is then used evaluate both my and me using a model-based approach. leading to estimated horizon-specific Q-functions, Q and Q We then approximate the annotation error for state 8; occurring at horizon i and counterfactual action ÊG, (st, a) Qūr (s) Our ū). Given the factual state-action pair (sk") ag a())) and the
counterfactual annotation (9,, Q (1r .a) for action ä, we convert the annotation as
0i 0(0) (1)@ (st,a)
One may verify that ( (7 a) in expectation. Note that this approach for annotation
(s
conversion is only possible the counterfactual action has support in the offline data (i.e., (s a) is seen in the data); otherwise, we suggest using the annotation collected.
D.2 Imputing Missing Annotations
Consider the following scenario: for two instances of the same factual (8, a) in the dataset, only one instance has counterfactual annotation but not the other. This means that the weights for the factual and counterfactual are (0.5, 0.5) and (1, 0) (assuming a binary action space), and the weight distribution W--|s, a) has nonzero variance and covariance. Specifically, in the example above with two samples, ow ow(aa ss, a)² = ow (ā) s. a)² = Cov(W (a)ss, a). W (āls, a)) 0.0625. These variances appear in the variance decomposition of C-IS shown in Theorem 13 and may lead to an overall larger variance compared to IS.
To address this issue, we suggest procedure to impute the missing annotations using other available
()), ())a c ())a 1} associated with dataset annotations when possible. Given all annotations gD {og
D = (T6)) Ji=1, we first build an approximate annotation model & by solving a regression problem on {(s)") g) (().)))).)) (9,2) cf
(f)_ā = 1} using all available annotations gp. For discrete state and action spaces, this essentially to averaging the annotations for each state-action pair. Then, G can be used to impute the missing annotations as ğ = (G(s) (() a) C (1).ā = 0, à E A {af")) if there is "support" for annotations of the same state and action, i.e., Ct (6),6 O (annotation is missing) and
1[s = (1) (('),a > 0 (annotation has support and thus can be imputed). This approximate annotation model Ô may be biased, but generally its bias can be outweighed by the benefit of variance reduction for having equal weights (we also observed this empirically in Appendices E.1 and E.2).
D.3 Optimizing Weighting Schemes to Minimize Variance
Using a worked example, we illustrate that optimizing weights for variance reduction is highly non-trivial problem. Suppose we have bandit problem with one state {s), two actions {/, Y and the reward function is R(s,, /) = (r oz), R(s, k) NNrr,, Furthermore, suppose all annotations are available, allowing suppose the annotation function is identical to the reward function, i.e., G R. We can simplify the variance decomposition of C-IS to be
to use constant weights and eliminate the weight variances, and
V[Gc-1]1 V snid TT + Eandy VanTs(o)
W()ls R(s
(4)
+ Eandy Barzs(s)
W(] a) (a.
26

---

We denote policies in terms of the probabilities assigned to the two actions.
Setting 1. Consider (8) = [1.0, Tee (8) (ax, 1 or.. The offline dataset contains only (s, = with counterfactual annotations (s, = ) and we assume they are each assigned a weight of w and (1 w). The augmented behavior policy is then mbr (s) [w, - w). The first and second terms of Eqn. (4) are zero because no variance is associated with sampling state-action pairs (only one possibility under mb). The third term becomes (state 5 omitted from the expressions)
Tb. W W 180
Te(2)
Tel
W(> I
Tb
1- x (1-w) x oî
2² x 0 +
w
1 w
= woxo 2 + - (1- a)
(aoi (1 a)oî) w (1 a)o}
This is a linear function of w, and where the variance achieves the minimum value depends on the slope (aog - (1 a
If aao (1 a)of the slope is zero, and w does not affect variance.
. If ao < (1 a. the slope is negative, and w" + 1 achieves minimum variance of ad
If ao > (1 a)of. the slope is positive, and w=" ++ 0 achieves minimum variance of
a1-
Setting 2. Consider Ny (s) = [3.1 13 17,1-117 3) (s()) = (a, 1- a-).. In the offline dataset, (s, a =/ appears with probability / and (s, = appears with probability 1 - B. When the factual data is (s, a = =/), the counterfactual annotation is for (s, ā =>x). and let the weights be wp and (1 wo); when the factual data is (s, a L),, the counterfactual annotation is for (s, 7),, and let the weights be wi and (1 - w1). ). The augmented behavior policy is then
TB+ (s) = [,30 + (1 3) w1)
1 wo) (1 B)w1
The first term of Eqn. (4) is zero because there is only one state. The third term is ~el2))
Te
>>00
W W 1()1))00))
Tb- (2)
+11- 3)
Tel
W 119
Tb' (x)
T (/)
= B Swo + (1 - [1 w1)
a
x w/
x o0 +
1
x (1 - ww)) x oî)
3(1 - wwo) + (1 - -B)w1
+ (1 11-83 (B)) Bw0 + (1 3) w1)
x (1 --w) )² x o/ 3(1 wo) + (1 3)w1
1-6
w oî)
Bwg + (1 -1)((1 w2)2
3(1 w 2 + (1 B)u?
o 2 + B - wp) + (1 w1
(1 a)oî
Bwo + (1 - B1 w1)
Next, we will attempt to simplify the second variance term:
V Vant((s)
Eaea ()
First note that
Eawss(s)
(als) a) [(s,a)]
Te T))
W Myo + Te
W(> A)
Tb.
Tbe
a
1-a
x w X ro +
x (1 - w) x
1-
= -arp + - +11-arr
27

---

Then, the second variance term becomes
1-a a
(1 (1-woy wo) r. - -(aro (1 +1- a)ri) 2
B
wo ro +
Bwop + (1 113 w1)
3(1 wa) + (1 - 93wm
2
+ (1 -) Bwo + -11- (0-33)(1- w1)
a
x (1 - (1- x x +
- a
x w x (aru + (1 -o)rz)
B(1 wo) + (1 B)
= 3 Jaro( Bw0 + (1- (1- - wi) - 1) + (1 a)ri
(1 wp)
3(1 - wo) + (1 3)w
+ (1 (3) aro /w00 + (1 - (1 w1)
1 u1
1) ( -a)r
W1
11
3(1 wo) + (1 =))01
3 20 Bwo + (1 - -1 - wi
w0
1) 2
+ (1 2/2
3(1 Wo) + (1 3)wi 1)
(1 (1- wo)
330 + - (11 - wi) -1)
w00
(1 - wo)
1)]
+ 20(11 -x)ror
311 - ww)) + (1 (3)w1
+ (1 11--3 B) 200 Bwo + (1 - B) - -w) 1) 2 + (1 a-))
1 - W1
3(1 - wo) + (1 B)wi 1) 2
W1
+ 2a a)rori
B3000 + (1 - (1 - w1) - 1) 3(1 - ww) + (1 B3)01
1 W1
W1
a2r0 3
W0
-1) 1)² (1 3)
1 1 W1
1) 27
Bwo + (1 (1 w1)
Bwo + (1 B1 wn)
+ (1 11--0 7)?
3
1 - w0
1)²
2 (1 33
W1
21
3(1 - wo) + (1 3)wi
3 - wo) + (1 3)
20(11 a)rori
Wi
1) 3311 - -wo) + (1 (3)
1- Wy
Bun + - (1 - w1)
Bwo + (1 - 3)(1 - w1) ()( 3(1 - wo) + (1 - B)wi
W1
W11
1)]
As shown above, the variance expression is a rather complicated function of (wo, w1). To solve for its minimum, one may take the derivatives with respect to each of wi and Wi and solve for the zeros. The final solution will depend the problem parameters, including ro, F1, ob of af,,,,5 3. Here, we do not solve for the final solution, and note that this approach may not be applicable to real-world problems due to its explicitly dependence problem parameters that may be unknown. We encourage future work to explore different methods to find the variance-minimizing weighting schemes.
28

---

E Extended Experiments
E.1 Synthetic Domains- Bandits
E.1.1 Two-State Bandits
We expand on the experiments shown in Section 5.1, where we consider class of bandit problems with two states {s1, $2} (drawn with equal probability), two actions = (/. R (recall Figure 3), and corresponding reward distributions R(s, a) ~ (s.)). assume / is always taken from 82 by both Hú and TT. For 81, we consider deterministie policies (in which one action is always taken) as well as stochastic policies (which take the two actions with probabilities that sum to 1); see column/row header in Table 3. Given (Tb, Te), we draw 1, 000 samples following тr and then evaluate ne using various estimators, including standard IS, the naive baseline of adding counterfactual annotations as new samples (Section 3.1), and C*-IS. We assume that counterfactual annotations are only available for 81, and all annotations are drawn from the true reward function. We measure the bias, standard deviation (square root of variance), and root mean- squared error (RMSE) of the estimators with respect to u(Te). ). In Table we consider three settings of the rewards: (i) R(ss./)) = 1, R ) = 2, i... both actions lead to a positive reward. (ii) Re = -1, R( = i.e., one action leads to positive reward and the other leads to a negative reward, (iii) (s../) = -1, S(,, = 2. i.e., both actions lead to negative reward. In all cases, the reward for state 82 set to for both actions.
Without loss of generality, we
Naive baseline fails due to bias. The naive baseline often has a nonzero bias and worse RMSE than IS regardless of whether the offline data has support. This is consistent with our analyses and example provided in Appendix B.
Bias reduction in support-deficien settings. In the first two rows of each sub-table in Table 3, ma is deterministic and the untaken action has poor support in the offline data. IS is often biased for these cases; note that in cases where Te assigns a small probability to the unsupported action (e.g.. row 2, column 4, me takes / with probability 0.1), the bias small and shows up as after rounding. In particular, when rewards as all positive (the first table of Table 3), the bias negative, and when rewards are all negative (the third table of Table 3), the bias is positive. In the second table of Table 3, the direction of bias depends the reward of the unsupported action. In the last three rows, IS is unbiased when the offline data has full support. In contrast, C*-IS is unbiased in all cases (but for rounding errors), and can reduce bias compared to IS in -upport-deficien settings by making use of counterfactual annotations. RMSE of CI- often (but not always) reduced compared to IS even though variance can sometimes increase. This is consistent with our analyses in Appendix C.2.
Variance reduction in well-supported settings. In the last three rows of each sub-table Table 3, the offline data has full support because na is stochastic, and IS is unbiased in these cases. C*-IS is also unbiased in these cases and achieves lower variance, leading to lower RMSE than IS. This is consistent with our analyses in Appendix C.3.
E.1.2 One-State Bandits
To simplify further experiments, we modify the two-state bandits above so that $2 is drawn with probability 0 ー equivalently, have set of one-state bandits (with only $1) with two actions A (0.1) where 0 corresponds to 7 and corresponds to Y, and corresponding reward distributions Ra ~ ((RR, oz) and R1 [NR1, For лe and Te, consider the same set of policies as before, and the same evaluation setup. We omit the naive approach in this setting because it is equivalent our proposed approach when there is only state (the state distribution is not affected by adding counterfactual annotations directly).
Results for this setting are summarized in Table 4 and show similar trends as above. Next, we use the one-state bandit to study the effect of weights w on OPE performance.
29

---

Table 3: Summary of performance on the two-state bandit problem for various R6 (rows) and Ta (columns), where each policy is denoted by its probabilities assigned to the two actions from $1. Each cell of the table corresponds to (Th, me) combination, for which we report (bias, std, RMSE) for three estimators: IS in the top row, naive in the middle row, and C*-IS in the bottom row.
R( = Re, >= =2
[1,
0]
[0
1]
[0.5, 0.5]
[0.1, 0.9)
[0.8, 0.2]
-0.5
0.5
0.7
-0.2
[1.0,.00
0.2
1.1
1.2
0.3
2
0.3
0.9
1
0.3
1.8
1.8
0.2
0.9
0.9
0.9
-0.5
-0.2
-0.4
0.6
[0.0,
0.2
111
1.1
0.3
2
2
0.3
0.9
1
0.3
1.8
1.8
0.2
0.8
0.9
0
1
0
1.8
1.8
0
1
1
16
1.6
0
0.8
0.8
0.5)
0.2
1.1
0.3
2
0.3
0.9
1
0.3
1.8
1.8
0.2
0.8
0.9
1.1
1.1
0.9
0.9
1.1
1.1
0.7
0.7
0.1
266
2.6
0
1.2
1.2
0
1.3
1,3
0
1.1
1.1
0.1
2
2
(0.1,0.9
0.7
0.7
1.1
1.1
0
0.9
0.9
1.1
1.1
0
0.7
0.7
0
0.8
0.8
0.1
322
3.2
0
1.6
1.6
2.9
2.9
0
0.8
0.8
0..8,
0.8
0.7
0.7
0
1.1
1.1
0
0.9
0.9
1.1
1.1
0.7
0.7
R(SI.)1 = -1, (( =1
[1, 0]
[0
1]
[0.5,
[0.1, 0..1
[0.8, 0.2]
0.7
-0.5
0.4
0.6
-0.2
0.5
0.5
-0.4
0.4
-0.1
0.6
0.6
[1.00.0]
-0.1
1.1
1.1
0.2
1.1
1.1
0.9
0.9
0.2
1.1
1.1
-0.1
1
0.7
0.7
0
0.7
0.7
0
0.4
0.4
0.6
0.6
0
0.6
0.6
0.00, 1.0]
0.1
111
1.1
0.2
1.1
1.2
0
0.9
0.9
0.2
1.1
1.1
-0.1
1
1
0.7
0.7
0.7
0.1
0.1
0.6
0.6
0.9
[0.5.0.3 0.5]
0.1
11
1.1
0.2
12
1.2
0
1
1
0.2
1.1
1.1
-0.1
1
1
0.1
0.1
0.6
0.6
24
2.4
0.7
0.7
0
1.4
1.4
0.8
0.8
0
2
2
(0.1
0.1
0.2
111
1.2
0.9
0.9
0.2
1.1
1.1
-0.1
1
1
0.7
0.7
0.4
0.4
0.6
0.6
0.6
0.6
0
0.8
0.8
0.1
18
1.8
0
11
1.1
0.1
1.7
1.7
0
0.8
0.8
0..8.0.2
0.9
0.1
0.7
0.7
0.7
0.7
0
0.4
0.4
0.6
0.6
0.5
0.5
R( -1, \ =-2
[1. 0
[0
1]
[0.5, 0.5]
10.1, 0.9]
[0.8, 0.2]
m
0
0.7
0.7
1
0.4
1.1
0.5
0.5
0.7
0.9
0.4
0.2
0.6
0.7
[..0..0]
0
0.7
0.7
0.1
11
1.1
0.1
0.9
0.9
0.1
1.1
1.1
0
0.8
0.8
0.5
0.4
0.6
0.1
1.1
1.1
0.3
0.7
0.7
0.1
0.4
D.4
0.6
1.00
0.1
1.1
-03
2
2
-0.2
1
-0.3
1.7
1.8
-0.2
0.9
0.9
0.7
0.7
0.1
1.1
1.1
0.9
0.9
0.1
1.1
1.1
0
0.8
0.8
[0.5, 0.5]
0.1
1.1
1.1
-0.3
2
2
-0.2
1
1
-0.3
1.7
1.8
0.2
0.8
0.9
0.1
0.9
0.9
24
0.1
1.3
1.3
0.1
1.1
1.1
1.9
1.9
0.9
0.1
111
111
-0.3
2
2
-0.2
1
1
-0.3
1.7
1.8
0.2
0.9
0.9
0
0.8
0.8
0.1
3.1
3.1
0
1.5
1.5
0.1
288
2.8
0
0.8
0.8
[0.8. 0.2]
-0.1
1.1
-033
2
0.2
1
-0.3
1.8
1.8
-02
0.8
0.9
0.1
0.7
0.7
1.
1.1
0.1
0.9
0.9
1.1
1.1
0.1
0.8
0.8
30

---

Table 4: Summary of performance on the one-state bandit problem for various To (rows) and Te (columns), where each policy is denoted by its probabilities assigned to the two actions from 81. Each cell of the table corresponds to (Tb, Te) combination, for which we report (bias, std, RMSE) for three estimators: IS in the top row, naive in the middle row, and C*-IS in the bottom row.
Ry 1, R1
[1, 0]
[0, 1]
[0.5, 0.5]
[0.1, 0.9]
[0.8, 0.2]
W6
[1.0.0.0 0.0]
0.03
0.5
-0.980.25
1.01
-0.37
0.4 0.55
0.03
0.5
0.02
0.47
0.47
0.03 0.34 0.35
0.02
0.43 0.43
0.03
0.41 0.41
[0.0, 1.0]
0
1
0.03
0.5
0.5
-0.48..25
0.54
-0.07
0.45 0.45
-0.79 0.1 0.8
0.02
0.47
0.47
0.03
0.5
0.5
0.03 0.34 0.35
0.03 0.45 0.45
0.02
0:39
0.39
0.5]
0.01
1.23
1.23
0.09
2.17
2.17
0.05
0.71 0.71
0.08
1.86 1.86
0.02 0.60 0.60
0.03 0.47 0.47
0.02 0.5 0.5
0.03
0.34 0.35
0.02
0.46
0.46
0.03 0.39 0.39
[0.1,
0.08 3.46 3.46
0.02
0.88
0.88
0.05 1.45 1.45
0.03
0.59 0.59
0.07
2.64 2.64
0.01 0.47 0.47
0.04 0.5
0.5
0.03
0.34 0.35
0.03
0.45 0.45
0.02 0.39 0.39
[0.8, 0.2]
0.03 0.75 0.75
0.05
4.28
4.28
0.04
1.92 1.92
0.05
3.81
0.03
0.65 0.65
0.04 0.48 0.48
0.01
0.49 0.49
0.03
0.34
0.35
0.02
0.44 0.44
0.03
0.4 0.4
Rg = -1, R4 =
[1, 0]
[0, 1]
[0.5,
[0.1, 0.9]
[0.8, 0.2]
776
[1.0, 0.0]
0.03 0.5 0.5
-0.180.25
0.54
-0.9
0.05 0.9
-0.17 0.4 0.43
0.03 0.5
0.5
0.02
0.47
0.47
0.03
0.34 0.35
0.02
0.43
0.43
0.03
0.41 0.41
[0.0, 1.0]
0
1
0.03
0.5
0.5
0.52
0.25 0.57
0.13
0.45 0.47
0.81
D.1 0.81
0.02 0.47
0.47
0.03
0.5
0.5
0.03
0.34 0.35
0.03
0.45
0.45
0.02
0.39 0.39
[0.5,
0.06
1.17
1.17
0,06
1.28
1.28
0.06
1.12 1.12
0.06
1.23 1.23
0.06 1.13 1.13
0.03
0.47 0.47
0,02
0.5
0.5
0.03
0.31 0.35
0.02
0.46
0.46
0.03 0.39 0.39
[0.1,
-0.013.37 3.37
0.03 0.61
-0.01 1.86 1.86
0.02
-0.03
2.76
0.47 0.47
0.03 0.34 0.35
0.00
0.45 0.15
0.02 0.39 0.39
[0.8, 0.2]
0.02 0.74 0.71
0.06
2/12
2-12
0.04
1.16 1.46
0.06
2.22
2.23
0.03
0.95 0.96
0.04 0.48 0.48
0.01
0.49 0.49
0.03
0.34 0.35
0.02
0.44 0.44
0.03 0.4 0.4
RS
11 R = --2
[1, 0]
[0,
1]
[0.3, 0.5)
[0.1, 0.9)
[0.8, 0.2)
[1.0.0.0 0.0
0.03 0.5 0.5
2
0
2
1.02
0.25 1.05
1.8 0.05 1.8
0.43 0.4 0.58
0.03 0.5
0.5
0.02
0.47
0.47
0.03
0.34 0.35
0.02
0.43
0.43
0.03
0.41 0.41
[0.0, 1.0]
0
1
0.03
0.5
0.5
0.52
0.25 0.57
0.13
0.45
0.47
0.81 0.1 0.81
0.02 0.47
0.47
0.03
0.5
0.5
0.03 0.34 0.35
0.03
0.45
0.45
0.02
0.39 0.39
[0.5,
0.06
1.17
1.17
-0.01
2.1
2.1
0.02
0.7 0.71
1.8
1.8
0.04 0.67 0.67
0.03 0.47
0.47
0.02
0.5
0.5
0.03
0.34 0.35
0.02
0.46
0.46
0.03 0.39 0.39
(0.1.0.9)
-0.043.37 3.37
0.58
-0.022..57 2.57
0.47 0.47
0.34
0.35
0.02 0.39 0.39
[0.8, 0.2]
0.02 0.74 0.74
0.09
4.02
4.02
0.06
1.8 1.8
0.08
3.57
3.57
0.04
0.63 0.63
0.04 0.48 0.48
0.01 0.49
0.49
0.03
0.34
0.35
0.02
0.44 0.44
0.03 0.4 0.4
31

---

Using equal weights (in C*-1S) is a reasonable heuristic though not always variance- minimmiinnnniiinin In the results above, C*-IS assumed the weights are split equally for factual and counterfactual data. Next, we explore the effect of different weighting schemes on the performance of C-IS, applied to the same class of bandit problems described above. Note that, consistent with Theorem 1, C-IS remains unbiased regardless of weights, except potentially at extreme values of weights (0 or 1) that ignore either the factual data or counterfactual annotations. Across different settings (Figure 7a-d), we found that the ideal weighting scheme is problem-specific, and certain weights may lead to higher variance compared to standard demonstrate that C*-IS, though not always variance-mininn minimizing, consistently achieves lower variance than standard IS (when the data has full support and the estimator is unbiased). Additionally, variance in the weight distributions directly contributes to variance in the resulting estimator (Figure 7c), corroborating our analysis in Theorem 13. Overall, our results suggest that C*-IS, which uses constant weights split equally among actions, is promising heuristic for using C-IS in practice.
(e.g,, lower left region of Figure 7b). Encouragingly, these results also
(b)
(d)
(e)
W/18 Mice
11/0 4
Hagg (P x0
Figure 7: Heatmaps of log std for C-IS using different weights applied to various problems (with different bandit parameters, Tb. Tez and annotation quality; exact parameter settings are specified below). W(l,s, a)) the weight wa assigned to action à given the factual sample (s, a). Asterisks indicate the weights under which the variance is minimized for each problem. Gray crosses x indicate where the estimator is biased. Red circles O correspond C*-IS. Yellow dots in the upper right corners correspond to standard IS (where applicable). (a-b) Constant weights where we sweep the factual weight within the range [o, 1] for both actions. (c-d) Similar to (a), where the annotations have a larger (c) or smaller (d) variance than the reward function. (e) Weights are drawn from uniform distributions centered at 0.5. We sweep the range of the uniform distributions within [0,1]. 1].
Parameter settings: (a) Base setting, R [1. 21.2).o0 oR = [1. 1J. n. = [0.1, T. = [0.8, 0.2), .g 7g. (b) Amnolations are not useful. 0.1.0.11.... n. [0.95, 0.05). ag ag (c) Annotations has larger variance than rewards,
1]. my = 0.9), v. j0.8, 0.2) og 0.5er (e) [1, 2). [1. 11. No [U.1, 0.9). n. [0.8, 0.2]. ag on.
[1. gg
[1,
on = [1. = (0.1,0.9),. F. [o.s, 0.2). ag = 20 (d) Annotations has smaller variance than rewards, R = [1. 2). on 11
Imputing missing annotations can reduce variance. Finally, we explore the impact of missing annotations on the performance of C-IS. As shown in Figure 8a, obtaining more counterfactual annotations generally helps to reduce the variance. However, as noted in our variance analyses, annotations for the same factual (s, a) are sometimes missing, we cannot directly apply C*-IS with equal weights; this may lead to increased variance due to variance in the weights. Here, we use a simple strategy to impute the missing annotations with the average of other annotations (for the same counterfactual of the same factual (s, a)). As shown in Figure 8b, this reduces the variance further especially when not all annotations available.
Figure 8: Heatmaps of log std for C-IS where some counterfactual annotations may be missing. We vary the fraction of acquired annotations for the ac- tions independently within 1]. (a) Equal weights (as in C*-IS) are used when annotations are available; otherwise, the factual weight is set to 1 when anno- tations are missing. (b) The missing annotations are imputed using other similar annotations. Imputing missing annotations allows for C*-IS to be applied directly and it achieves lower variance. Parameter settings are the same as Figure 7a.
(a) Without imputation (b) With imputation
Portie anwlened Lrdkl
32

---

E.2 Healthcare Domain
Sepsis Simulator
E.2.1 Experimental Setup
Simulator Description. The patient state is characterized by five variables: binary indicator for diabetes status, and four ordinal-valued vital signs (heart rate, blood pressure, oxygen concentration, glucose). Following prior work [22], we used discrete state space with [S] 1440. The action space corresponds to the administration of vasopressors and takes on binary value (on/off), which may increase or decrease the values of certain vital signs (with pre-specified probabilities) at the next time step. The action space in the original simulator formulation involves combinations of treatments: antibiotics, vasopressors, and mechanical ventilation; we focus on only vasopressors for the purpose of illustration. The episode ends when the patient is discharged occurs when all vitals are normal and all treatments are turned off, whereas death occurs if three or more vitals are abnormal. Rewards are sparse and only assigned the end of each episode, with +1 for survival and 1 for death. Episodes that reach the maximum length of 20 are truncated with zero terminal reward.
died; discharge only
Evaluation Setup. Following prior work [22], we collected 50 offline datasets from the sepsis simulator (using different random seeds) each with 1000 episodes by following e-greedy behavior policy with respect to the optimal policy where e = 0.1. For the evaluation policies, we created set of deterministic policies by perturbing the optimal policy such that each policy takes the non-optimal actions in a randomly selected subset of states. We varied the number of "action-flipped" states in {50, 100, 200, 300, }00} and generated 5 different evaluation policies for each; we also included the optimal policy in the candidate set, resulting in a total of 26 candidate evaluation policies. These represent policies that may be derived from offline data by typical RL approaches that aim to learn deterministic policies, and are of diverse quality where approximately half are superior to the behavior policy while the other half are inferior (Figure 9). As the baseline estimator that only makes of offline data, we applied standard PDIS which does not rely on counterfactual annotations. To apply C*-PDIS, we assume all counterfactual annotations are collected in our main experiments in which they may be drawn from different annotation functions; we explore the impact of missing annotations in subsequent sensitivity analyses. For C*-PDIS, considered three different annotation functions: (i) G Q"= the Q-function of the evaluation policy тe: (ii) G = Q** the Q-function of the behavior policy, and (iii) G QT + QFe,, where we apply the bias correction procedure discussed in Appendix D.I. We also compare to two naive baselines (given perfect annotations): "naive unweighted" simply adds counterfactual annotations as new trajectories and has the same issue discussed in Section 3.1, whereas "naive weighted" reweights the annotations at the trajectory level instead of per-decision. More formally, assuming a binary action space A {0, 1} (without loss of generality), given a trajectory of length T with counterfactual annotations at each step,
= [st, Qg, r.]/= = {g] I-ae "T where 1 - is the counterfactual action for a,, the naive weighted estimator is defined as
(1 (1-E% If wi)i
ΣT= (WiPIa-IP)
(E TV' + gt -)))))
Intuitively, this first converts each annotation into a sub-trajectory that terminates at the step of annotation with the counterfactual action [$1, (1,,"", 8t, at Mt). and then performs IS on each sub-trajectory (including the original trajectory), and finally computes a weighted sum of these T' + 1 estimates (1 factual estimate, T counterfactual estimates) using weights (1 - - wt). W1,-- Wr. The reason why "naive weighted does not work is more subtle: while reweighting the (partial) trajectories constructed from the counterfactual annotations correctly maintains the initial state distribution, does not correctly maintain the intermediate state distributions.
33

---

0.8
polcy valus
0.2
0.2
0.0
optnal betweitr
optial
Deloviior
-04
10
15
20
20
10
20
policy Index
polioy Indox
Figure 9: The true value v(TTe) of each of the 26 evaluation policies. The two dashed line are, respectively. the value of the optimal policy and the value of the behavior policy e(m)) (which is e-greedy with respect to the optimal policy where e = 0.1). On the right, we additionally plot error bars representing = standard deviation of the values initial states for each of the policies. The average std of initial state values over all 26 policies is 0.312.
E.2.2 Results
C*-PDIS outperforms all baselines in all metrics for the ideal setting, As shown Table 5, when all counterfactuals available and annotated with the evaluation policy's Q-function (G =**), C*-PDIS outperforms baseline PDIS (without annotations) in all metrics, suggesting that it provides more accurate OPE estimates. In contrast, the two naive approaches fail to provide accurate estimates and often underperform standard PDIS.
C* .DII is robust to biased annotations. Under the more realistic scenario where G G QTh i.e., annotations summarize the future returns under Na rather than ne. we observe a degradation in all metrics compared to the ideal case, though C*-PDIS is still superior to PDIS (Table 5). Applying the bias correction procedure = Q + QT (see Appendix D.1) helps recover performance to be closer to the ideal case, and is especially helpful for Te that are far away from Na (Figure 10).
Table 5: Comparison of baseline and proposed estimators in terms of OPE performance (RMSE, ESS), ranking performance (Spearman's 's rank correlation) and binary classification performance (accuracy, FPR, FNR) on the sepsis simulator, reported as mean + std from 50 repeated runs. Bolded results are the best for each metric, whereas highlighted results outperform all baselines. The upper table shows the overall results; the lower table shows the breakdown by ordinary and weighted IS (OIS vs WIS) applied to each approach.
Estimator
RMSE
ESS
Spearman
% Aeccurayy
%&PR
FNR
Baxeline
PDIS (w/o annot.)
0.113 1003s
76.8 144.0
0.596
10.100
76,5 135
33.7 187
15.9 146
Naive unweighted (G Q*))
0.128 4000
207.2
491.
0.089
40,09
50.0 160
11.6 183
78.1 1136
Naive weighted
Q*1)
0.097
300.8
0.420
64.3 #47
24.0
44.3
Proposed
C*-PDIS (G QT))
0.013 +0,05
994.0 110.1
0.995
95.7 #311
4.5 160
4.2 #53
ideal case
C*DP (G Q0))
0.070 +0000
994.0
#10.1
0.961
1000
86.8 #82
22.0 #200
8.2 #11.3
relaxing
CsLPDIS (G - -+
0.028 10.00
994.0
110.1
0.979
10010
90.1 15.4
4.2 16666
14.1 193
Assump.
Estimator
RMSE
1 ESS
Spearman
Accuracy
FFPR
%FNN
PDOIS (w/o annot.)
0.079 10054
1.40
0. 0.868 1008)
79.8 15.
6.4 17.3
30.3 188
PDWIS (w/o annot.)
0.136
76.8
0.523
73.2
61.1
1.6
C*PPDOIS (Q- Q**)
0.013 20.05
994.0
=10.1
0.995 +000
95.6
4.5 #6.
4.3 #53
C*.PDWIS (G Q=))
0,013 10.00
994.0
110.1
0,995 10000
95.7 110
4.5 169
4.1 15.11
Breakdown
Cs Qm)
0.070 200
994.0
=:0.1
0,962 +0012
86.7 #83
20.2 =20.1
8.3 1:114
C (6 Qt1)
0.070 =0.003
994.0
1000
0.961
#0012
86.9 #8.1
19.8 #20.1
8.1 +11.2
C PDOIS (G 0F (%%)
0.028 100000
994.0
10.1
0.979 10010
90.1 15.4
4.2 156
14.1 197
PDWIS (G) Q )
0.028 000007
994.0
10.1
0.979 +0010
90.1 +5.4
26.
14.1 497
34

---

PDIS (baseline)
C*-PDIS (G Q
C*-PDIS (G Q + QT))
C*-PDIS Q^))
TMSE(v(T....(MA)) ((m,))
0.2
0.1
0.0
0.0
1.0
(KU(F ((x.)
Figure 10: RMSE C*-PDIS vs. distance to Ne (in terms of KI. divergence) for each Tes plotted with linear trend lines. OPE error increases Ne becomes more different from behavior.
Variance reduction of C*-PDIS outweighs the effect of noisy annotations. To understand the robustness of estimator annotation noise, we perturbed the annotations with varying amounts of noise. Specifically, each annotation added with a noise value drawn from zero-mean Gaussian distributions with pre-specified standard deviation which we vary. As the level of annotation noise increases (Figure I-leeft), performance degradation is minimal even at the highest level of noise tested (with std of which large relative to the reward range [-1, 1], and most notably larger than 0.31, the std of initial state values of this domain). Our estimator remains competitive relative to the baseline PDIS, suggesting that the benefit of variance reduction from additional data (through counterfactual annotations) outweighs the variance increase from annotation noise, even when annotations are much noisier than factual data. The same trend holds when only 10% of counterfactual annotations are collected (Figure 11-right).
PDIS (baseline)
C C*-PDIS, noisy annot.
case
RMSE
0.1
RMSE
0.1
Spearman
1.0
Spearman Con.
1.0
Corr.
Bin. Class. Accurapy
Bin. Class. Accuracy
0.8
0.8
0.0
0.5
1.0
0.0
0.5
1.0
Std of annotation noise
Sid annotation noise
Figure 11: Performance of our proposed C*-PDIS estimator is generally robust to noisy annotations. Trend lines show average of 50 runs one std. When all annotations are available (left), the performance degradation C*.PDIS is minimal even at the highest level of noise tested. When only 10% of the counterfactuals annotated (right), performance degradation is more noticeable and eventually becomes worse than baseline PDIS without annotations.
35

---

Collecting more annotations and imputing missing annotations improves performance. As the amount available annotations increases (Figure 12), our approach interpolates between baseline PDIS and the ideal case of C*-PDIS with an monotonic improvement in performance. Furthermore, imputing annotations (as described in Appendix D.2) achieves better performance, suggesting is promising strategy to handle missing annotations when not all annotations can be obtained in practice. The same trend holds under different amounts of annotation noise (Figure 12 left vs right).
PDIS (baseline)
C-PDIS w/o imputation
ideal case
C*-PDIS, w/ imputation
RMSE
0.1
RMSE
0.1
0.0
0.0
Spearman
1.0
Speamann
1.0
Corr.
Corr.
0.5
0.5
Bin. Class. Accuracy
1.0
Bin. Class. Accuracy
1.0
0.8
0.8
0.0
0.5
1.0
0.0
0.5
fraction of annotated samples
fraction of annotated samples
Figure 12: Performance of our proposed C*-PDIS estimator robust to missing annotations, espe- cially when the missing annotations imputed. Trend lines show average of 50 runs + one std. As the fraction of annotated samples increases, performance interpolates between baseline PDIS and the ideal case where all counterfactual annotations available. The imputed version outperforms the unimputed version and maintains a competitive performance (relative to the ideal case) even in the presence of high degrees of missingness. The same general trend holds across the two settings with different amounts of annotation noise (left: std of 0.2, right: std of 1.0), though the imputed annotations have a larger bias when annotations are noisier, leading slightly worse performance even when all annotations are available.
36


Reviews:
[{"review_id": "LuHvfFOj0Q", "reviewer": "Reviewer_71Lt", "summary": "This paper studies offline policy evaluation in reinforcement learning, where the behavior policy, some interaction trajectories, and some human annotated trajectories (modified from interaction trajectories) are available. The paper points out that, since the number of human annotated trajectories are not the same across interaction trajectories, naively treating these human annotated trajectories the same as interaction trajectories can introduce bias (for example, in bandits, the context distribution changes), even if human annotations are perfect. So the paper proposes to weight the trajectories such that for each interaction trajectory, the weights of this trajectory and the trajectories  annotated from this trajectory sum to one. This ensures estimating the value of a policy from the correct state distribution. \n\nThe paper analyzed the bias and variance of the proposed estimator in the bandit setting and the bias of the estimator in the RL setting, under some specific settings (sometimes when the weights are the same and every trajectory is annotated, sometimes human annotations are perfect) and conducted empirical evaluation to show that the proposed estimator can reduce estimation error. \n\n", "questions": "See weaknesses. ", "limitations": "The authors adequately addressed the limitations. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and easy to follow. \n\nThe paper studies an interesting problem of off-policy evaluation in reinforcement learning with the help of both interaction data and human annotations. This setting makes sense when data is sparse and human annotations are accurate and affordable. \n\nThe paper both theoretically and empirically analyze the bias and variance of the proposed estimator. \n\n\n", "weaknesses": "My major concern is about the novelty of the paper. The paper did not answer the question of how to set the weights of interaction data and human annotations. To me, it seems that weighting is an obvious approach to try when correcting for the state distribution. I believe there are other works using similar idea. For example [1]. The interesting question to me is how to set the weights for optimal estimation error reduction. Unfortunately, this is not discussed in the paper. \n\nIt would be nice to discuss the relationship between this work and policy evaluation from multiple loggers (e.g. [2]). To me, they are similar problems since human annotations are like collected from another logging policy (except we need to correct for the state distribution). \n\nI am a bit confused about the definition of C^\\star-IS. The authors mentioned that C^\\star-IS corresponds to w = 1/|A|. The authors also mentioned that the weight should be zero when there are no annotations. This means only when we have full information data can we use C^\\star-IS. First, this seems a less interesting setting to analyze since the fundamental problem of missing data in RL is gone. Second, in the experiments, some actions were not annotated, but C^\\star-IS is still used. There seems to be a contradiction? \n\nMinor:\n\nIn line 50, the paper mentioned that the estimator requires a weaker condition. To me, this is an overclaim, since in reality, only the support condition is weaker, but an additional strong assumption that human annotations are perfect is also required. \n\n[1] Learning to Rank with Selection Bias in Personal Search Xuanhui Wang, Michael Bendersky, Donald Metzler, Marc Najork SIGIR 16\n\n[2] Effective Evaluation using Logged Bandit Feedback from Multiple Loggers A. Agarwal and S. Basu and T. Schnabel and T. Joachims KDD 17  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their overall positive assessment of our paper and valuable feedback, including providing additional references. We are encouraged that the reviewer found our paper to be well-written and recognized its potential impact. We address the main questions below: \n\n**1. How to set weights for optimal estimation error reduction?** (see also: [overall response](/forum?id=dsH244r9fA&noteId=jKEOBV6cyp), [noPk](/forum?id=dsH244r9fA&noteId=l1RyMRJL8s))\n\nWe agree with the reviewer that this is indeed an interesting question that arises from our approach, and **in the paper we have provided a partial answer**. \n- We explored this empirically in Fig 7 (Appendix E.1, page 27), where we sweep the weights and measure the resulting estimator variance. We found that (L839) “the ideal weighting scheme is problem-specific, and certain weights may lead to higher variance compared to standard IS”. We also found that (L841) “C*-IS, though not always variance-minimizing, consistently achieves lower variance than standard IS”. Unfortunately due to space constraints we couldn’t include the full results and summarized as (L350) “Equal weights (in C*-IS) is a good heuristic though not always ‘optimal’ ” in the text. Since it is an important takeaway of our paper, we will expand upon this part given the one extra content page at camera-ready. \n- We also considered this problem analytically (solving for variance-minimizing weights in the bandit case, which turned into a quartic equation) and numerically (optimizing variance objective using SGD). However, unless problem-specific parameters are known, we have yet to come up with a general way to minimize variance. Therefore, we suggest C*-IS (with equal weights) as a heuristic and highlighted this as a direction for future research (L311) that would build upon our semi-offline evaluation framework. \n\n**2. Clarifying C\\*-IS and missing annotations, is there a contradiction?**\n\nYou are correct in noting that (i) C*-IS corresponds to w = 1/|A|, (ii) weights should be zero when there are no annotations, and (iii) in the experiments, some actions were not annotated i.e. missing. However, there is **no contradiction** because we proposed an approach to impute missing annotations, described in Sec 4.4 (L286-292) and Appendix D.1, and applied it in our experiments (L385). \n- Our variance analysis (Sec 4.2, Appendix C.3) suggests that variance may increase if non-uniform weights are used (illustrated empirically in Fig 8 on page 27 of Appendix), motivating the idea of imputing missing annotations. This can reduce variance at the potential cost of increasing bias (L768-770), and in experiments we have empirically observed it to be effective overall. This is an important part of the approach to make it more practical, and in the final version we plan to expand upon this part to make sure readers do not miss it. \n\n**3. “My major concern is about the novelty of the paper”** (see also: [overall response](/forum?id=dsH244r9fA&noteId=jKEOBV6cyp), [fzzo](https://openreview.net/forum?id=dsH244r9fA&noteId=SS3U84sY4C))\n\nIn this paper, we establish a formal framework of ‘semi-offline’ evaluation (offline data + counterfactual annotations), and propose a new estimator for this setting based on importance sampling. While the C-IS estimator is simple (using reweighting, similar to e.g. ref [1] in the review), our analysis **reveals new theoretical insights and important practical considerations** for practitioners to keep in mind, e.g. it’s better to impute missing annotations and use equal weights. Therefore, we believe our paper makes non-trivial contributions to the community and is an important step to enabling RL applications in high-stakes domains such as healthcare. \n\n**4. Relationship to OPE with multiple loggers**\n\nThis is indeed an interesting connection. We agree with the reviewer that a possible interpretation of counterfactual annotations is “data” from another logging policy i.e., the “annotation policy”. There is also a nice parallel in the policy definitions between Agarwal et al. (ref [2] in the review) vs our paper: in Agarwal et al. (Definition 5.1) the average policy $\\pi_{avg}$ is the weighted average of multiple logging policies, whereas our augmented behavior policy (Definition 1, L162) $\\pi_{b^+}$ can be seen as the weighted average of the behavior policy and “annotation policy”. However, there are two key distinctions between our framework vs Agarwal et al.: (i) our formulation of annotation is a single number rather than a (sub-)trajectory in the RL setting, (ii) we need to correct for state distributions that a naive approach fails to account for. We will add this discussion to the related works section (currently in Appendix A.1). \n\n**5. Regarding the language around weaker condition**\n\nThank you for this suggestion. We will change the claim \"weaker condition\" -> \"weaker condition on support\" so it is more accurate. "}, {"review_id": "fxRsvleJAU", "reviewer": "Reviewer_Qcjd", "summary": "The paper considers OPE with annotation to improve the performance of OPE. The paper explains why naively incorporating such information may lead to a biased estimate. And the paper provides a theoretical analysis of the bias and variance. Finally, the paper demonstrates the performance of the proposed method using synthetic bandit and healthcare experients.", "questions": "1. IN Section 3, are weights state-dependent? And it seems the weights are random. How should I understand it? \n\n2. Why the variance does not depend on the variance of the annotation var(g)?", "limitations": "The authors discussed some limitations in Section 4.4.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "OPE is well-known to suffer from high variance. And incorporating other information is important and relevant. The paper studies an interesting and important question and proposes useful solutions with theoretical guarantees.", "weaknesses": "The clarity of the paper needs to improve. The main concept of this paper, annotation, is first introduced in Section 2. And In the Introduction, the authors only mention this notion in Figure 1. I think the authors should introduce and discuss \"annotation\" in the introduction to facilitate the reader's understanding. There are some other confusing points that may hinder comprehension, which I list in the Question section.\n\nAssumptions 1 and 2 seem very strong. Could the authors discuss the impact of the bias of the annotation?\n\nIt seems in the current formulation, a behavior trajectory with annotations is very similar to many behavior trajectories. At least in the bandit case, I think they are equivalent. If it is correct, it will affect the paper's novelty and contribution.\n\nRelated to the clarity, \"distribution shifts\" are mentioned in the abstract, but never show up again in the paper. I think it is better to discuss the issues of distribution shifts induced by different policies in RL. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and evaluate our work. Below, we list specific updates on which we plan to focus our efforts, as well as provide answers to the questions raised. \n\n**1. “The clarity of the paper needs to improve”**\n\nThank you for your detailed suggestions on improving the clarity of the paper. In our revision we will address the following points: \n\n> **Paper should introduce the concept of annotation earlier**\n> \n> We agree. We plan to update the introduction to (i) provide concrete examples of what a counterfactual annotation means, specifically in the context of healthcare: “asking doctors what they think would happen to the patient if the opposite treatment was used instead, assuming the standard care procedure was followed afterwards”, and (ii) incorporate related works on annotations/augmentations mentioned by Reviewer fzzo, and point out that our definition of counterfactual annotation is specific to RL and differs from existing notions of annotations. \n\n> **Are weights state-dependent?** \n>\n> No. Weights are specific to **each sample**, not necessarily to each state. Here’s a clarifying example: given an MDP with a single state $s$ and two actions {↗, ↘}. Suppose we have two samples: sample #1 is simply ($s$,↗) with no annotation for ↘, so the weights to the two actions must be $[1,0]$; sample #2 is also ($s$,↗) but with an annotation for ↘, and the weights can be any two non-negative number that sums to 1 as specified by the user, e.g. $[0.8, 0.2]$. (Note that this doesn’t mean the weights are “random”, as the user may *deliberately* set weights to be equal $[0.5,0.5]$, or to $[1,0]$ which ignores the annotation if they believe it is of poor quality.) The average weight (L159) of these two samples is $\\bar{W}(\\$↗$|s,$↗$) = 0.9$, $\\bar{W}($↘$|s,$↗$) = 0.1$, and is used in computing the augmented behavior policy per Definition 1. We hope this example, together with the description in Sec 3.2 as well as our code implementation in the supplement, can help clarify the definitions, and we will add this example to the appendix. \n\n> **Paper should discuss the issues of “distribution shift” induced by different policies in RL**\n>\n> Absolutely, we will expand the discussion of distribution shift in (offline) RL and how it is the main challenge of OPE, providing additional references such as [1][2][3][4]. Thank you for this suggestion. \n> \n> [1] Kumar, et al. \"Stabilizing off-policy q-learning via bootstrapping error reduction.\" NeurIPS 2019.\n> [2] Kumar, et al. \"Conservative q-learning for offline reinforcement learning.\" NeurIPS 2020. \n> [3] Laroche, et al. \"Safe policy improvement with baseline bootstrapping.\" ICML 2019.\n> [4] Parbhoo, et al. \"Generalizing off-policy evaluation from a causal perspective for sequential decision-making.\" arXiv 2022.\n\n**2. Assumptions seem very strong, what’s the impact of annotation bias?**\n\nWe agree with the reviewer that Assumptions 1&2 are rather strong, and this is exactly why our paper also presents analyses and experiments for **when the assumptions are violated, i.e., annotations are biased**. \n- Under Sec 4.1, in Proposition 3 we provide detailed theoretical analysis of the effect of bias due to imperfect annotations, where the bias is $\\epsilon_G$. \n- In Sec 4.4 (L293) and Appendix D.2 we further provide an approach to directly correct for annotation bias using a model-based approach. \n- In Sec 5.2 experiments on the sepsis simulator (L374), we empirically studied the impact of bias and we found our approach to be robust to annotation bias. \n\n**3. Behavior trajectory with annotations vs many behavior trajectories, are they the same?**\n\nNo, they're not the same. If we understand the reviewer correctly, the interpretation of “many behavior trajectories” corresponds to the naive approach that we describe in Sec 3.1 - this approach is the first thing that came to our mind as well, but as it turns out it's not correct as it does not handle state distributions correctly: states that receive more annotations will be overrepresented in the augmented dataset, and this will bias the final estimate. \n\n**4. What happens if annotation variance differs from reward variance?** (see also: [overall response](/forum?id=dsH244r9fA&noteId=jKEOBV6cyp), [noPk](/forum?id=dsH244r9fA&noteId=l1RyMRJL8s))\n\nFor clarity, in Theorems 6&13 we assume annotation variance $\\sigma_G^2$ is the same as reward variance $\\sigma_R^2$. More generally, we can assume some relationship between the two such that $\\sigma_G(s,a)^2 = \\sigma_R(s,a)^2 + \\Delta_{\\sigma}(s,a)^2$, which leads to an additional term that depends on $\\Delta_{\\sigma}(s,a)^2$ in Theorems 6&13 variance decomposition expressions. **Due to space constraints, please see paragraph 2 of the [overall response](/forum?id=dsH244r9fA&noteId=jKEOBV6cyp) (above) for detailed derivations, which we plan to add to the appendix.**\n"}, {"review_id": "LYE68J0oXG", "reviewer": "Reviewer_noPk", "summary": "This paper offers a new OPE estimator leveraging additional annotations of counterfactual actions. The paper provided an extremely thorough and comprehensive discussion of the theoretical property of this estimator. This helps us develop an understanding of how it operates. This paper also discussed fully the limitations of the approach and how the estimator would behave if different assumptions have been violated.\n\nI generally find this to be a good paper, with limited experiments and not enough real-world motivation, but I can potentially see an application of this method, even though, for now, I don’t yet know what it could be.", "questions": "1. Section 4.2 discusses the variance of the annotation function that would impact the variance of C*-IS. It assumes that the annotation function has the same variance as the reward function. Can the authors provide some insights on what happens when the annotation function has a lower variance than the reward function (this is possible because human annotations are malleable) or higher variance?", "limitations": "The authors addressed the limitations in the paper.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The theoretical discussion of the estimator is very clear and very thorough. The paper discussed how bias of the annotator functions would impact the bias of the estimator. The paper also discussed when and how annotations could help reduce bias and variance of the estimator. The paper is also very clearly written. The proofs in the appendix are easy to follow (although I have not checked all of them). The experiments in the appendix are well documented.", "weaknesses": "There are a few weaknesses of this paper that prevents it from having a higher impact.\n1. No human experiment has been offered. There is no actual investigation of what human inter-annotator variance would look like. It is somewhat known in a few important domains, such as dialogue evaluation (perhaps not surprisingly, this is a huge application field where RL is applied to natural language processing), inter-annotator agreement on certain metrics can be huge [1] (Table 2). The authors didn’t collect real human annotations at all, and the paper lacks key data that can shed light on whether this approach can work with real human annotations. Also, collecting $\\omega$ would seem to be difficult as well. It is unfortunate that the authors didn’t opt to do this, but I don’t think this eclipses other amazing parts of this paper.\n2. The experiments are too synthetic. This is a complaint similar to but slightly different from the previous point. Most RL/Bandit tasks have real-world motivations. By using a synthetic bandit experiment and Sepsis, the authors did not convince me that these two tasks would clearly benefit from human annotations. When are human annotations desirable in an RL/bandit task? How hard is it to obtain human annotations, especially for a sequential setting where some level of “imagine what the policy would do in the future” is involved? Can the authors shed some light on what kind of real-world task they hope to apply this OPE estimator to?\n\n[1] Lowe, Ryan, et al. \"Towards an automatic turing test: Learning to evaluate dialogue responses.\" arXiv preprint arXiv:1708.07149 (2017).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are encouraged that the reviewer appreciated our clear/thorough theoretical analyses, as well as well-documented experiments. We also want to point out that we have provided full code implementation in the supplement. Below, we address the feedback from the reviewer: \n\n**1. Regarding human experiments**\n\nWe resonate strongly with the reviewer that, in order to further realize the utility and potential impact of our work, human experiments on the annotation quality/variability would be necessary; we have explicitly mentioned this under limitations and as future work (L520). **We are grateful that the reviewer acknowledges the contributions of our paper even without a user study.** Importantly, our work sheds light on desirable properties of useful counterfactual annotations, which points to exciting directions of future research in RL as well as HCI (L530-L534); there is also opportunity to draw lessons from the NLP community about human annotation quality/variability (such as ref [1] mentioned by Reviewer noPk). \n\nRe the side note about “collection of w”: please see [overall response](/forum?id=dsH244r9fA&noteId=jKEOBV6cyp) paragraph **4.** (and we also responded to Reviewer [71Lt](/forum?id=dsH244r9fA&noteId=LuHvfFOj0Q) regarding this); to summarize, in the paper we explored different weight settings both theoretically and empirically, and we suggest using equal weights as per C*-IS as a useful heuristic. \n\n**2. What are the real-world application domains of our approach?** (see also: [overall response](/forum?id=dsH244r9fA&noteId=jKEOBV6cyp), [rPY7](/forum?id=dsH244r9fA&noteId=6fGRmonfcP))\n\nOur approach is best suited for high-stakes RL domains where online evaluation is risky, but domain experts can provide additional feedback on new policies. One domain that the authors have the most experience in is healthcare, where the goal is to optimize sequential treatment policies (e.g. Komorowski et al. 2018). In this domain, clinicians are constantly evaluating alternative treatment paths in their minds when making treatment decisions but we only observe what was actually done; counterfactual annotations can be seen as a mechanism to elicit this information in their thought process that is otherwise not recorded. We envision clinicians to be asked questions such as “given that the patient received treatment A, if treatment B was used instead, what do you think would happen to the patient”. \n\nThe sepsis simulator experiment is our best attempt at using an existing RL domain with strong healthcare motivations, where we have full control over the simulation parameters (various policy configurations etc) and online access (to evaluate OPE methods with ground-truth). While admittedly imperfect (which we acknowledged as a limitation on L528), our simulation experiments do attempt to cover various realistic scenarios including missing/noisy/biased annotations and show the robustness of our approach. \n\n[1] Komorowski et al. “The Artificial Intelligence Clinician learns optimal treatment strategies for sepsis in intensive care”. Nature Medicine, 2018. \n\n**3. What happens if annotation variance differs from reward variance?** (see also: [overall response](/forum?id=dsH244r9fA&noteId=jKEOBV6cyp), [Qcjd](/forum?id=dsH244r9fA&noteId=uEp9MwDHCX))\n\nFor clarity, in Theorems 6&13 we assume annotation variance $\\sigma_G^2$ is the same as reward variance $\\sigma_R^2$. More generally, we can assume some relationship between the two such that $\\sigma_G(s,a)^2 = \\sigma_R(s,a)^2 + \\Delta_{\\sigma}(s,a)^2$. Then, in the proof of Theorem 13 (Appendix C.3, page 13), the majority of the derivation stays the same except for term (3) where we now apply a different assumption on annotation variance (L712). The resulting variance decomposition will have an additional term $\\mathbb{E}\\_{s \\sim d_1} \\mathbb{E}\\_{a \\sim \\pi_b(s)} [\\sum\\_{\\tilde{a} \\sim \\mathcal{A} \\setminus \\\\{a\\\\}} \\rho^{+}(\\tilde{a}|s)^2 \\bar{W}(\\tilde{a}|s,a)^2 \\Delta_{\\sigma}(s,\\tilde{a})^2]$ related to the difference in variance $\\Delta_{\\sigma}^2$. Note that this also suggests that when the annotations have a larger variance than the rewards, we may want to assign it a smaller weight, and vice versa -- which makes sense intuitively. \n\nSimilarly, the modified version of Theorem 6 will contain an additional third term: \n\n$\\mathbb{V}[\\hat{v}^{\\textup{C*-IS}}] = \\mathbb{V}\\_{s\\sim d_1}[V^{\\pi_e}(s)] + \\mathbb{E}\\_{s\\sim d_1} \\mathbb{E}\\_{a\\sim \\pi(s)}[\\pi_b(a|s) \\rho(a|s)^2 \\sigma_R(s,a)^2]+ \\mathbb{E}\\_{s\\sim d_1}[\\sum\\_{\\tilde{a} \\sim \\mathcal{A} \\setminus \\\\{a\\\\}} \\pi_e(\\tilde{a}|s)^2 \\Delta_{\\sigma}(s,\\tilde{a})^2]$\n\nWhere the original Theorem 6 can be obtained by setting $\\Delta_{\\sigma}^2$ to 0, making the last term vanish. \n\nWe will add the full derivations to the appendix. \n"}, {"review_id": "73B980NU7S", "reviewer": "Reviewer_fzzo", "summary": "- Propose a setting in OPE where experts can annotate the value of counterfactual actions.\n- A new importance sampling scheme for the setting is proposed.\n- Theoretical analysis and experiments confirm superiority over the unweighted case, etc.", "questions": "1. What is the exact definition of \"naive weighted\"? What is the theoretical advantage of the proposed method?\n1. The problem with the naive IS method is shown in section 3.1, but is this not simply because the state visitation probability $d_\\pi(s)$ is not corrected? The problem can be solved by simply applying any OPE method that takes $d_\\pi(s)$ into account, such as DualDICE [3], to the augmented dataset.\n\n[3] Nachum, Ofir, et al. \"Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections.\" Advances in neural information processing systems 32 (2019).", "limitations": "1. The proposed method requires costly accurate annotation, which is properly investigated theoretically and experimentally.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "1. The proposed setting of expert annotating the counterfactual values seems like a direction worth exploring\n1. Clearly written with some theoretical guarantees. In particular, the bias and variance are carefully discussed for cases where assumptions such as the coverage are not met, and benefit such as bias reduction compared to importance sampling (IS) is shown.\n1. A useful heuristic is proposed (equal weighting)", "weaknesses": "1. The method itself and the baselines are fairly naive.\n    1. Comparisons with standard OPE baselines, such as the direct and doubly robust methods as well as the IS method, may be of value to better estimate the benefit of annotating counterfactuals for readers.\n    1. Also have a question about the claimed problem with the naive IS method, which is pointed out in section 3.1. See Question 2 below.\n1. Other similar annotation augmentation approaches (e.g., [1,2], but not limited to) are not compared neigher theoretically nor experimentally. I believe that the proposal to add counterfactual annotations is a costly and significant change to the problem setting and should be widely compared to similar approaches widely.\n\n[1] Srivastava, Megha, Tatsunori Hashimoto, and Percy Liang. \"Robustness to spurious correlations via human annotations.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Kaushik, Divyansh, Eduard Hovy, and Zachary Lipton. \"Learning The Difference That Makes A Difference With Counterfactually-Augmented Data.\" International Conference on Learning Representations. 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and evaluate our work. Below, we provide clarifications and answers to your questions. \n\n**1. “The method itself and the baselines are fairly naive”** (see also: [overall response](/forum?id=dsH244r9fA&noteId=jKEOBV6cyp), [71Lt](/forum?id=dsH244r9fA&noteId=tJFHuJCKwM))\n\nIn this paper, we establish a formal framework of ‘semi-offline’ evaluation (offline data + counterfactual annotations), and propose a new estimator for this setting based on importance sampling. While the C-IS estimator is simple, our analysis **reveals new theoretical insights and important practical considerations** for practitioners to keep in mind, e.g. it’s better to impute missing annotations and use equal weights. Therefore, we believe our paper makes non-trivial contributions to the community and is an important step to enabling RL applications in high-stakes domains such as healthcare.  \n\n- Comparison to other OPE methods: We believe the relevant comparison is C-IS against IS (and C-PDIS against PDIS), as **improvement of C-PDIS over PDIS directly illustrates the benefit of counterfactual annotations**. In other words, whenever good counterfactual annotations are available, our results (theoretical + empirical) suggest that the counterfactual-augmented version C-PDIS should be preferred over vanilla PDIS. Results for other OPE methods are not shown as they are not directly relevant to supporting our main claim on the utility of counterfactual annotations (and how to incorporate them to IS-based estimators). In addition, past benchmarking works have found that the best OPE method is environment-specific and has recommended multiple OPE methods should be used in practice [Fu et al. 2021, Voloshin et al. 2021]. We believe there is opportunity to augment other classes of OPE methods with counterfactual annotations and have highlighted this potential in related work (in Appendix A.1 on page 12). \n\n    [1] Voloshin et al. “Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning”. NeurIPS D&B 2021. \n    [2] Fu et al. “Benchmarks for Deep Off-Policy Evaluation”. ICLR 2021. \n\n**2. Relationship to other annotation/augmentation approaches** \n\nWe appreciate these additional references. It is certainly true that the annotations required in our approach will share similar challenges to those in the cited works (e.g. subjectivity, inter-rater disagreement), and we will expand our discussion on this in the revised version. Here, we would like to point out a few key distinctions between our approach and these past work: compared to Kaushik et al. ICLR 2019 (annotators alter text to match a counterfactual target label) and Megha et al. ICML 2020 (humans provide annotations of potential unmeasured confounder), our formulation of counterfactual annotations is more naturally suited to sequential decision making in RL, focused on the unobserved trajectories in the offline setting. This is an underexplored area with great potential to enable practical RL in high-stakes domains. \n\n**3. What’s the exact definition of naive weighted?**\n\nWe believe the reviewer is referring to the “naive weighted” baseline that was mentioned on L361 in the sepsis simulator experiments, whose results are shown in Table 2 on page 9. We have informally defined “naive weighted” on L361 as an approach that “reweights the annotations at the trajectory level instead of per-decision” (we weren’t able to elaborate in the main text due to space constraint). More formally (wlog), assuming a binary action space $\\\\{0,1\\\\}$, given a trajectory of length $T$ with counterfactual annotations at each step, $\\tau = [s_t, a_t, r_t]\\_{t=1}^{T}$, $\\boldsymbol{g} = \\\\{g_t^{1-a_t}\\\\}\\_{t=1}^{T}$ where $1-a_t$ is the counterfactual action for $a_t$, the naive weighted estimator is defined as\n\n$(1-\\sum\\_{t=1}^{T} w_t) \\rho_{1:T} (\\sum\\_{t=1}^{T} r_t) + \\sum\\_{t=1}^{T} \\big( w_t \\rho_{1:t-1} \\rho_t^{1-a_t} (\\sum\\_{t’=1}^{t-1} r_{t’} + g_t) \\big)$\n\nIntuitively, this first converts each annotation into a sub-trajectory that terminates at the step of annotation with the counterfactual action $[s_1, a_1, r_1, \\cdots, s_t, 1-a_t, g_t]$, and then performs IS on each sub-trajectory (including the original trajectory), and finally computes a weighted sum of these T+1 estimates (1 factual estimate, T counterfactual estimates) using weights $(1-\\sum\\_{t=1}^{T} w_t)$, $w_1, \\cdots, w_T$. \n\nWe have elaborated the reason why it does not work in Appendix E.2, L886-L891 on page 28: \n> The reason why “naive weighted” does not work is more subtle: while reweighting the (partial) trajectories constructed from the counterfactual annotations correctly maintains the initial state distribution, it does not correctly maintain the intermediate state distributions.\n\n**4. Why not apply OPE methods that take state distribution d_π(s) into account?**\n\nWe chose to focus on importance sampling based OPE methods due to their simplicity of implementation and common use, as well as comprehensive theoretical guarantees as discussed in past work [1][2]. In the paper, we do provide a solution to the bias issue with the naive incorporation of counterfactual annotations to IS. On the other hand, we acknowledged in related works (L562-L564) that there is a family of approaches based on importance weighting on marginalized state distributions $d_{\\pi}(s)$. We believe that similar modifications to the MIS/DICE estimator family can be made - and are also a valid solution to the overall problem - but require separate full analyses on their bias/variance properties, which is outside the scope of our current paper. \n\n[1] Levine et al. “Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems”. arXiv 2020. \n[2] Precup. “Eligibility traces for off-policy policy evaluation”. 2000. \n"}, {"review_id": "p6LpkoTit5", "reviewer": "Reviewer_rPY7", "summary": "The paper proposed a novel method for off-policy evaluation with offline data that entails human input. Specifically, the paper assumes access to human annotations for counterfactual state-action pairs as counterfactual immediate reward (in bandits) or Q values (in RL) under the behaviour policy (as a relaxation to Q values under the evaluation policy). They used a bandit example to show that simply incorporating counterfactual annotations into the offline data can shift state distribution and therefore bias overall estimates. To keep the state distribution unchanged, they further assume access to a human-privided weight for each visited / annotated counterfactual state-action pair. Effectively this creates an augmented behaviour policy as if smoothed towards a uniform policy. They are then able to reweigh the importance sampling ratios and conduct OPE as a weighted sum of the conventional backwards bootstrapping and human annotation. They then move on to give theoretic analyses about the bias and variance of the proposed OPE estimator. Experiments conducted on a synthetic bandit problem and a healthcare problem with simulator demonstrated overall improved performance than vanilla IS and ablated versions of the proposed method itself", "questions": "1. how would human experts provide Q values under the behaviour policy in practice? It does not seem any easier than providing \nQ values under the evaluation policy both of which entail a sequence of counterfactual state-action pairs that are not their own choices\n2. Appendix D.2, to relax Q under the evaluation policy to Q under the behaviour policy in the annotation, why simply considering a bias term in the annotation is enough? It seems to me you would also need to reweigh the annotation based on how relatively likely the counterfactual action is selected. Yes you have indeed reweighed for this between the evaluation policy and the augmented behaviour policy, but now you have a third policy, i.e. the original behaviour policy before augmentation (under which you have the Q values). I would imagine in addition to the IS ratio as you have in place already, you would also need to reweigh the Q value with e.g. product of subsequent IS ratios between the evaluation policy and the original behaviour policy. However, I see in your experiments you showed that the performance is not much affected with biased annotations, so I suppose not reweighing the biased annotations is not a major issue, but it would still be good to see further justification for that.", "limitations": "please see above", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. proposed a novel method for OPE with offline data, which seems increasingly timely as machine learning is marching into real life\n2. experiments have tested thorough aspects of the proposed idea", "weaknesses": "1. even if the paper goes into length to keep state distribution not affected by incorporating human annotations, it still does not address the distribution shift between the state distribution induced by the behaviour policy and by the evaluation policy\n2. expert annotations for counterfactual state-action pairs along with their weights are also expensive to get (though argubly safer / easier than rolling out the evaluation policy in real world) and inevitably subjective\n3. unclear how the promising results could extend to real-world scenarios", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer rPY7 for the time spent reading our paper (including the appendix) and their helpful feedback. We are also encouraged by their overall positive assessment of our paper. Below we address the reviewer's questions and concerns. \n\n**1. The proposed method does not address state distribution shift between $\\pi_e$ and $\\pi_b$**\n\nVanilla IS (and PDIS) are unbiased under the common support assumption (Assumption 3 in our paper) and do not require explicit handling of the state distribution shift due to different policies. Our paper points out the bias issue of naive incorporation of counterfactual annotations (where states with more annotations are over-represented) and provides a simple reweighting solution to address it. \n\n- We also acknowledged in related works (L562-L564) that there is a family of approaches based on importance weighting on marginalized state distributions $d_{\\pi}(s)$. We believe that similar modifications to the MIS/DICE estimator family can be made, but require separate full analyses on their bias/variance, which is outside the scope of our current paper. \n\n**2. Is it even practical to collect counterfactual annotations? “How would human experts provide Q values under the behaviour policy in practice?”** (see also: [overall response](/forum?id=dsH244r9fA&noteId=jKEOBV6cyp), [noPk](/forum?id=dsH244r9fA&noteId=l1RyMRJL8s))\n\nOne domain that the authors have the most experience in is healthcare, where the goal is to optimize sequential treatment policies (e.g. Komorowski et al. 2018). In this domain, clinicians are constantly evaluating alternative treatment paths in their minds when making treatment decisions but we only observe what was actually done; counterfactual annotations can be seen as a mechanism to elicit this information in their thought process that is otherwise not recorded. We envision clinicians to be asked questions such as “given that the patient received treatment A, if treatment B was used instead, what do you think would happen to the patient”. \n\n[1] Komorowski et al. “The Artificial Intelligence Clinician learns optimal treatment strategies for sepsis in intensive care”. Nature Medicine, 2018. \n\n- Re subjectivity of annotations: while an inevitable property of human annotations, we want to point out two potential remedies that could improve the usefulness of our approach: (i) we can average the annotations from multiple annotators to reduce annotation variance, (ii) our approach is relatively robust to high levels of annotation noise (as seen in Fig 5 experiments), and informally speaking, if the annotation noise is similar to observed reward variance, then the variance reduction we get is as if we have collected more offline data. We also believe there is opportunity for future research especially in the HCI space (which we mention on L530-L534) to improve annotation solicitation (e.g. better question phrasing to reduce subjectivity in response). \n\n**3. Question about Appendix D.2, why simply considering a bias term in the annotation is enough?**\n\nThank you for raising this detailed question, we are happy to provide more clarification to your question (main points are summarized below).\n> “why simply considering a bias term in the annotation is enough? ... you would also need to reweigh the Q value with e.g. product of subsequent IS ratios between the evaluation policy and the original behaviour policy…”\n\nWe would like to refer the reviewer to the unbiasedness proof of C-PDIS, which we have sketched in L272-L279 and illustrated in Figure 4, and fully derived in Appendix C.4 (starting L725 on page 21). In Figure 4 (ii) and (iii), what we require for unbiasedness is that both the factual and counterfactual branches provide unbiased estimates of Q under $\\pi_e$, for factual $a_t$ and counterfactual $\\tilde{a}$ respectively. When using the bias-correction approach in Appx D.2, we are directly mapping the annotation from Q of $π_b$ (the original behavior policy) to Q of $π_e$ (the evaluation policy) by estimating their difference (i.e. the annotation bias). Indeed, an alternative approach to correct this bias is to apply IS, as proposed by the reviewer by using the “product of subsequent IS ratios between the evaluation policy and the original behaviour policy”. However, the main challenge here is that we only have the annotation for $\\tilde{a}$ but no subsequent sub-trajectory information (recall Fig 4(iii)). We have experimented with a version of this approach where we search for all matching sub-trajectories that start with $(s_t, \\tilde{a})$ and use the average subsequent IS ratio to reweight, but we found that it introduced a lot more variance (due to limited number of matching sub-trajectories) than the model-based bias-correction procedure described in the paper. \n"}]

Author rebuttal:
We thank all reviewers for taking time to read our paper and providing valuable feedback. 

Overall, reviewers found our paper to be well-written (71Lt, noPk, fzzo), addressing an interesting (71Lt), important (Qcjd) and timely problem (rPY7), and proposing a novel solution (rPY7) with comprehensive theoretical guarantees (noPk) and thorough experiments (rPY7). Reviewers also commented that the paper has carefully considered limitations and the effects when assumptions are violated (noPk), suggesting our work points to a direction worth exploring (fzzo). 

Below we respond to each review with a separate rebuttal, and here we summarize the common themes mentioned by multiple reviewers. 

**1. Clarifying our contributions: concerns about “novelty” (71Lt), proposed method is “fairly naive” (fzzo)**

In this paper, we establish a formal framework of ‘semi-offline’ evaluation (offline data + counterfactual annotations), and propose a new estimator for this setting based on importance sampling. While the C-IS estimator is simple, our analysis **reveals new theoretical insights and important practical considerations** for practitioners to keep in mind, e.g. it’s better to impute missing annotations and use equal weights. Therefore, we believe our paper makes non-trivial contributions to the community and is an important step to enabling RL applications in high-stakes domains such as healthcare. 

**2. What happens if annotation variance differs from reward variance?** (Qcjd, noPk)

For clarity, in Theorems 6&13 we assume annotation variance $\sigma_G^2$ is the same as reward variance $\sigma_R^2$. More generally, we can assume some relationship between the two such that $\sigma_G(s,a)^2 = \sigma_R(s,a)^2 + \Delta_{\sigma}(s,a)^2$. Then, in the proof of Theorem 13 (Appendix C.3, page 13), the majority of the derivation stays the same except for term (3) where we now apply a different assumption on annotation variance (L712). The resulting variance decomposition will have an additional term $\mathbb{E}\_{s \sim d_1} \mathbb{E}\_{a \sim \pi_b(s)} [\sum\_{\tilde{a} \sim \mathcal{A} \setminus \\{a\\}} \rho^{+}(\tilde{a}|s)^2 \bar{W}(\tilde{a}|s,a)^2 \Delta_{\sigma}(s,\tilde{a})^2]$ related to the difference in variance $\Delta_{\sigma}^2$. Note that this also suggests that when the annotations have a larger variance than the rewards, we may want to assign it a smaller weight, and vice versa -- which makes sense intuitively. 

Similarly, the modified version of Theorem 6 will contain an additional third term: 

$\mathbb{V}[\hat{v}^{\textup{C*-IS}}] = \mathbb{V}\_{s\sim d_1}[V^{\pi_e}(s)] + \mathbb{E}\_{s\sim d_1} \mathbb{E}\_{a\sim \pi(s)}[\pi_b(a|s) \rho(a|s)^2 \sigma_R(s,a)^2]+ \mathbb{E}\_{s\sim d_1}[\sum\_{\tilde{a} \sim \mathcal{A} \setminus \\{a\\}} \pi_e(\tilde{a}|s)^2 \Delta_{\sigma}(s,\tilde{a})^2]$

Where the original Theorem 6 can be obtained by setting $\Delta_{\sigma}^2$ to 0, making the last term vanish. 

We will add the full derivations to the appendix. 

**3. Is it even practical to collect counterfactual annotations?** (noPk, rPY7)

Our approach is best suited for high-stakes RL domains where online evaluation is risky, but domain experts can provide additional feedback on new policies. One domain that the authors have the most experience in is healthcare, where the goal is to optimize sequential treatment policies (e.g. Komorowski et al. 2018). In this domain, clinicians are constantly evaluating alternative treatment paths in their minds when making treatment decisions but we only observe what was actually done; counterfactual annotations can be seen as a mechanism to elicit this information in their thought process that is otherwise not recorded. As acknowledged by Reviewer noPk, even without results from a user study, our paper provides valuable contributions to the community, where we formalize a framework for semi-offline evaluation using counterfactual annotations and study the theoretical properties of a new estimator for this setting. Importantly, our work sheds light on desirable properties of useful counterfactual annotations, which points to exciting directions of future research in RL as well as HCI (L530-L534); there is also opportunity to draw lessons from the NLP community about human annotation quality/variability (such as ref [1] mentioned by Reviewer noPk). 

Komorowski et al. “The Artificial Intelligence Clinician learns optimal treatment strategies for sepsis in intensive care”. Nature Medicine, 2018. 

**4. How to set weights for optimal estimation error reduction?** (71Lt, noPk)

This is indeed an interesting question that arises from our approach, and **in the paper we have provided a partial answer**. 
- We explored this empirically in Fig 7 (Appendix E.1, page 27), where we sweep the weights and measure the resulting estimator variance. We found that (L839) “the ideal weighting scheme is problem-specific, and certain weights may lead to higher variance compared to standard IS”. We also found that (L841) “C*-IS, though not always variance-minimizing, consistently achieves lower variance than standard IS”. Unfortunately due to space constraints we couldn’t include the full results and summarized as (L350) “Equal weights (in C*-IS) is a good heuristic though not always ‘optimal’ ” in the text. Since it is an important takeaway of our paper, we will expand upon this part given the one extra content page at camera-ready. 
- We also considered this problem analytically (solving for variance-minimizing weights in the bandit case, which turned into a quartic equation) and numerically (optimizing variance objective using SGD). However, unless problem-specific parameters are known, we have yet to come up with a general way to minimize variance. Therefore, we suggest C*-IS (with equal weights) as a heuristic and highlighted this as a direction for future research (L311) that would build upon our semi-offline framework. 

Meta-review: This paper is proposing a weighted Importance Sampling based off-policy evaluation that weighs between factual and counterfactual trajectories. They analyze bias-variance properties of two main IS estimators they propose under the assumption that counterfactual annotations are accurate.

Overall, the approach of weighting matches state distributions across factual and counterfactual trajectories and is a fairly natural approach. Concerns raised by reviewers are:

    1. Method not novel enough (intuitive idea)
    2. Assumption of no bias in counterfactual human annotations is unrealistic
    3. No real-world evaluation. The experiments consist of a synthetic bandit setting and a Sepsis healthcare simulator.

Overall, I agree with points 2. and 3. Authors have addressed some of the concerns regarding the assumption of no-bias during discussion. And the submission could be significantly enhanced with better empirical evaluation. 

Overall, due to the comprehensive nature of the theoretical analysis, which I encourage authors to add in the final version, and two experiments, I will currently recommend a weak accept.
Decision: Accept (poster)