Markovian Interference in Experiments
Authors: Vivek Farias
Andrew A Li
Tianyi Peng
Andrew Zheng
Venue: NeurIPS 2022 Accept (2022)
Keywords: Causal inference
Off-policy Evaluation
Experimentation
Interference
Reinforcement Learning

Abstract: We consider experiments in dynamical systems where interventions on some experimental units impact other units through a limiting constraint (such as a limited supply of products). Despite outsize practical importance, the best estimators for this `Markovian' interference problem are largely heuristic in nature, and their bias is not well understood. We formalize the problem of inference in such experiments as one of policy evaluation. Off-policy estimators, while unbiased, apparently incur a large penalty in variance relative to state-of-the-art heuristics. We introduce an on-policy estimator: the Differences-In-Q's (DQ) estimator. We show that the DQ estimator can in general have exponentially smaller variance than off-policy evaluation. At the same time, its bias is second order in the impact of the intervention. This yields a striking bias-variance tradeoff so that the DQ estimator effectively dominates state-of-the-art alternatives. From a theoretical perspective, we introduce three separate novel techniques that are of independent interest in the theory of Reinforcement Learning (RL). Our empirical evaluation includes a set of experiments on a city-scale ride-hailing simulator.  

Markovian Interference in Experiments
Vivek Farias Sloan School Management Massachusetts Institute of Technology Cambridge, MA 02139 rivekf@mit.co
Andrew A. Li Tepper School of Business Carnegie Mellon University Pittsburgh, PA 15213 aali10cmu. edu
Tianyi Peng
Andrew Zheng
Department of Acronautics and Astronautics Massachusetts Institute of Technology Cambridge, MA 02139 tianyi@mit.edi
Operations Research Center Massachuselts Institute of Technology Cambridge, MA 02139 atz@mit.edu
Abstract
We consider experiments dynamical systems where interventions on some experimental units impact other units through limiting constraint (such as a limited supply products). Despite outsize practical importance, the best estimators for this 'Markovian' interference problem largely heuristic nature, and their bias is not well understood. We formalize the problem of inference in such experiments one of policy evaluation. Off-policy cstimators, while unbiased, apparently incur a large penalty in variance on-policy estimator:
relative to state-of-the-art heuristics. We introduce the Ciferrecces-InQQ2 (DQ) estimator. We show that the DQ estimator can in general have exponentially smaller variance than off-policy evaluation. At the same time, its bias second order in the impact of the intervention. This yields striking bias-variance tradeoff that the DQ estimator effectively dominates state-of-theear alternatives. From theoretical perspective, we introduce three separate novel techniques that are of independent interest in the theory of Reinforcement Learning (RL). Our empirical evaluation includes a set of experiments on a city-scale ride-hailing simulator.
1. Introduction
Experimentation is broadly deployed learning tool in online commerce that is, in principle, simple: apply the treatment in question at random (c.g. an A/B test), and 'naively" infer the treatment effect by differencing the average outcomes under treatment and control. About decade ago, Blake and Cocy [ pointed out a challenge in such experimcntation on Ebay:
"Consider the example of lesting a new search engine ranking algoritim which steers lest bugers lowards a particular class of ilems for sale. If lest users buy up those ilems, the supply available to the control users declines."
The above violation of the so-called Stable Unit Treatment Value Assumption (SUTVA [2]). has been viewed as problematic in the context of online platforms at least as early as Reiley's
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

seminal 'Magic on the Internet' work [4]; Blake and Coey 8 were simply pointing out that the resulting inferential biases were large, which is particularly problematic since treatment effects in this context are typically tiny. The interference problem above is germane to experimentation on commerce platforms where interventions on a given experimental unit impact other units since all units effectively share common inventory of 'demand' or 'supply' depending on context.
Despite what appears to be the ubiquity of such interference, practical solution is far from settled. The majority of approaches so far fall under the category of experimental design, the idea being that a more-careful assignment of treatment will render the bias of the saiiely'-deriven inference negligible. This ongoing line of work has produced sophisticated experiment designs which, in the best cases, provably reduce bias under highly specialized models. While this is promising in theory, experimentation on online platforms particular still largely relies on the simplest designs, i.e. A/B tests. For reasons including cost and organizational frictions, sophisticated experimental designs may not be an ideal lever, and are often infeasible.
Markovian Interference and Existing Approaches: We study a generic experimentation problem within system represented Markov Decision Process (MDP), where treatment corresponds to an action which may interfere with state transitions. This form of interference, which we refer as Markovian, naturally subsumes the platform examples above, as recently noted by others either implicitly E or explicitly 24 E In that example, a user arrives at each time step, the flatform chooses an action (whether to treat the user), and the user's purchase decision alters the system stale (inventory levels).
Our goal is to estimate the Average Treatment Effect (ATE), defined as the difference in steady-state reward with and without applying the treatment. In light of the above discussion, we assume that experimentation is done under simple randomization (i.e. A/B testing). Now without design as a lever, there are perhaps two existing families of estimators:
1. Naive: We will explicitly define the Naive estimator in the next section, but the strategy amounts to simply ignoring the presence of interference. This is by and large what is done in practice. Of course it may suffer from high bias (we show this formally in Example D but it serves as more than just a strawman. In particular, bias is only one side of the estimation coin, and with respect to the other side, namely variance, the Naive estimator effectively the best possible.
2. Off- Off-Policy Evaluation (OPE): Another approach comes from viewing our problem as one of policy evaluation in reinforcement learning (RL). Succinetly, it can be viewed as estimating the average reward of two different policies (no treatment, or treatment) given obscrvations from some third policy (simple randomization). This immediately suggests framing the problem as one of Off- Evaluation, and borrowing one of many existing unbiased estimators, e.g. 50 40 83
28 This tack appears to be promising, e.g. but we observe that the resulting variance is necessarily large (Theorem 3
22
27
44
Against the above backdrop, propose a novel on-policy treatment- affect estimator, which we dub the 'Differences- In-Q'' (DQ)' estimator, for experiments with Markovian interference. In mutshell, characterize our contribution as follows:
Our Contributions:
The DQ estimalor has provably negligible bias relative the trealmend effect. Its variance con, in general, be exponentially smaller thon that of an efficent off-policc estimator. In both stylized and large-scade scale real-world models, it dominates moute-ofthhe-ae alternatives.
We next describe these relative merits in greater detail:
1. Second-order Bias: We show (Theorem I that when the impact of an intervention on transition probabilities is (6), the bias of the DQ estimator is O(5²). The DQ estimator thus leverages the one piece of structure we have relative to generic off off-policy evaluation: treatment effects are typically small.
2. Variance: We show (Theorem 2 that the DQ estimator is asymptotically normal, and provide a non-trivial, explicit characterization of its variance. By comparison, we show (Theorem 4 that this variance can, in general, be exponentially (in the size of the state space) smaller than the variance of any unbiased off- off-policy estimator.
2

---

Summarizing the above points, we are the first (to our knowledge) to explicitly characterize the favorable bias-variance trade-off in using on-policy estimation tackle off off-policy evaluation. This new lens has broader implications for OPE, and policy optimization in RI.
3. Practical Performance: We conduct experiments in both a caricatured one-dimensional environment proposed by others 24,, as well as city-scale simulator of a ride-sharing platform. We show that in both settings the DQ estimator has MSE that is substantially lower than (a) naive and off off-policy estimators, and even (b) estimators given access to incumbent state-of-the-art experimental designs.
Related Literature:
The largest portion of work in interference is in experimental design,
with the design levers ranging from stopping times in A/B tests
30
23
57
25 to any
form of moro-sophisticated 'clustering' of units [T 16 19
14
15
to clustering
specifically when interference is represented by a network 35
54
39
60 to the
proportion of units treated 21 48 g to the timing of treatment
and beyond 51 35 10 20 42 As alluded to earlier, these sophisticated designs can be powerful,
1
3 29 but cost, user experience, and other implementation concerns restrict their application in
practice 31 32
We view this paper orthogonal to this literature, but will eventually compare against recent state-of-the--rt design, so-called two-sided randomization 24 5 the context of two-sided marketplaces (e.g. the one simulate)..
that is specific to
46 The fundamental challenge in OPE is high variance, which can be attributed to the nature of the algorithmic tools used, e.g. sampling procedures 50 49 33
As stated carlier, the problem we study one of off-policy evaluation (OPE)
Recent work on 'doubly-rouust estimators [22 27 28 has improved on variance (incidentally, our estimator is loosely tied to these, as we discuss in Section G). but again we will show, via a formal lower bound, that unbiased estimators as a whole have prohibitively large variance. Finally, our motivation is close spirit to a recent paper !E! which applies OPE directly in Markovian interference settings; we make a direct experimental comparison in Section 5
In the policy optimization literature, 'trust-region' methods [ and conservative policy iteration [6 use a related on-policy estimation approach to bound policy improvement. However, the explicit application of on-policy estimation in the context of OPE, and in particular the striking virsvvariance tradeoff this enables, are novel to this paper.
2. Model
This section formalizes the inference problem that tackle, casting it in the language of MDPs. Vis-à-vis the existing literature, this lens allows us to reason about the problem using large, well-established toolkit, and makes obvious the fact that OPE provides unbiased estimation of the ATE. We then present what we call the 'Naive' estimator (alluded to in the introduction). This is the lowest-variance estimator one can hope for in this setting, but it can have significant bias, as we will see.
We begin by defining MDP with state space S. We denote by 8 E S the state of the MDP at time E N. Every state is associated with a set of available actions A which govern the transition probabilities between states via the (unknown) function p S x S - [0, 1]. We assume that A = {0, }} irrespective of state; for descriptive purposes, we will associate the '1' action with the use of a prospective intervention, so that '0' is associated with not employing the intervention. We denote by r(s, a) the reward earned in state having employed action maps states to random actions. We define the average reward X"
a. A policy π S under any (ergodic, unichain) policy π, according to:
A lim Er(sE.((S)) T-000 T
There are three policies we define explicitly:
The Incumbent Policy mo: This policy never uses the intervention, so that To(s) = 0 for all 8. This is businnss as usual'. Denote the associated transition matrix as Po (i.e. the entries of Po are exactly p(.,0,)) O)))
3

---

The Intervention Policy πi: This policy always uses the intervention, so that Ti(s) = 1 for all s. This reflects the system, should the intervention under consideration be 'rolled out'. Denote the associated transition matrix as Pi.
The Experimentation Policy Tp: This policy corresponds to the experiment design. Sim- ple randomization would select (Ts) with some fixed probability p, say 1/2, independently at every period. This corresponds the sort of search engine experiment alluded to the introduction. The transition matrix associated with this design is then P1/2 P + PP.
The Inference Problem:
We are given single sequence of T states, actions, and rewards, observed under the experimentation policy "р (recall that cost and constraints 3T 82 prohibit from rumning To or лi separately until convergence). The data we have is the sequence {($, re; az)) ...... T), wherein at - np(s)). We must estimate the average treatment effect (ATE):
-
2.1.
The Naive Estimator and Bias
A natural approach to estimating the ATE is to simple randomization (i.e. P1/2) and the following Naive estimator:
(1)
ATEN
Σ IET1
r(s,, 0z)
Σ r(s),a)) az),
[T1
(Tol
TET
where Ti = [t: a, 1) and To = (t : a, 00. In the context of the search engine experiment, this corresponds to simply averaging some metric of interest (say, conversion) among the test users (Zi) and control users (To). What goes wrong simply that the two empirical averages above, that seck to estimate A and A respectively, employ the wrong mcasure over states. This sufficient to introduce bias that is on the order of the treatment effect being estimated:
Example 1. Consider an MDP on two states, S (0, We collect a reward of 0 in state irrespective of the action laken in that state (r(0,0) = (0, =0=), 0), and a reward of 1 in slate 1, again, irrespective of aclion (r(1, 0) -(1,1)=1), On the other hand, transitions are impacted by our choice of action. Specifically, lel p(0, 0, =0 =p(0, O, 1)
p,,,0,
p(1, 0, 1/2. We maintain p0O, 1, = p(0, 1) = 1/2 so that the intervention has effect at state 0. On the other hand, we let 1, = 1/2+ 8, so that p(1, 1, = 1/2 8, for some 5 > 0. In words, the intervention tends to discourage transition to 0 from state 1.
In the above example, it is easy to calculate that ATE = (1/2)5/(1 - 8), reflecting the shift in the stationary distribution favoring state 1, induced under the intervention. On the other hand, can calculate that limy ATEx 0, that the bias induced by the "experimentation policy relative to the stationary distributions under the incumbent and intervention policies respectively, is comparable to the size of the treatment effect.
3. The Differences-In-Q's Estimator
We are now prepared to introduce our estimator for inference in the presence of Markovian interference. Before defining estimator, which will see is only slightly more complicated than the Naive estimator, we recall a few useful objects associated with MDPs. First, for a fixed policy म, define the Bellman operator Tx R|SI x R - RISI according to
T=(V,A) Fx A1 + P.V.
where Fn : S ->> is defined according to r = E (r(s, (s))] {[((s,(ss)) denoted X7, and the bias function corresponding to म, denoted Vn, then a solution to the fixed point equation Tù (V, V. Finally, the Q-function associated with denoted Qx S A R, is defined according
The average cost of policy n,
(2)
Qx(s,a)= r(s, X (s)V so 3,00 =a]

---

3.1. An Idealized First Step
In motivating our estimator, let begin with the following idealization of the Naive estimator, where we denote by P1/2 the steady state distribution under the randomization policy 21/2i
Ep1/2 ATEN]
Σ (()
It is not hard to see that in the context of Example we continue to have E/y/2 [ATEv] that this idealization of the Naive estimator continues to have bias on the order of the treatment effect. Consider then, the following alternative:
(3)
Ep//
[AEE]]
(1r((()) (Qmya (s, 1) (s,)
where the term Ep1/2 [ATEp] can for now just be thought of idcalized constant (ATEp is defined soon in ( Compared to Ep./2[ATA we see that Ept,2 [ATEp] takes remarkably similar form, except that as opposed to an average over differences rewards, we compute average of differences in Q-function values. The idea is that doing will hopefully compensate for the shift in distribution induced by T1/2- We return to our example to check:
Example 1 (Continued). Conlinuing with our example, the average reward X51/2, and the stationary distribution P1/2 (see Appendidfy. Doing so allows us to calculate that
explicilly calculate (x)/2((s))
[ATE]]
8
Eps/2
8/2)3
That is, |ATE [ATF,]] O so that the bias of this idcalized estimator is second- order (i.e. negligible) relative to the ATE.
the dramatic mitigation bias we see in Example D generic? If the experimentation policy mixes fast, first set of results essentially answers this question in the affirmative. In particular, we make the following mixing time assumption:
Assumption (Mixing time). There exist constants C and such that for all s E S and for any inleger k 2 0,
drv (Pv(Pi/2(s,)) ) s CX*,
where . denotes total variation distance.
We then have that the second order bias in Example is, in fact, generic: Theorem 1 (Bias of DQ). Assume that for any state E S, (Tv( p(s, 8. Then,
ATE Eppya [TEDD] < C (1-2) Tiax 8²
where Tmax max (r(s,a) and C' is a constant depending (potgnomially) on log(C".
3.2.
The Differences-In-Q's Estimator
Motivated by the development in the previous subsection, the Differences-In-Q's (DQ) estimator we propose to use is simply
(4)
ATE, = T
1
Σ IET)
(
Qnys (st, 0z):
Tol
TETo
Appendices be found at https://arxivvorrg// 22tp:/00/rr./aa//2002222227

---

where we take an empirical average over the state trajectory produced under the randomiza- tion policy, and Q,yz is an estimator of the Q-function. For concreteness, we obtain 2 by solving
Σ r(),, - - + ((8+1)) ((sH1)))(s)) -v(s))
(5)
min V.
Our main result. characterizes the variance and asymptotic normality of ATED: Theorem 2 (Variance and Asymptotic Normality of DQ). The DQ estimator is asymptotically normal so that
VT (ATED -Ep//2
(ATED) 4 N(),,f)).
with standard deviation
5/2
OD ODSC
(1-x
log min.es P1/2(8) Tmax.
where C' is conslant depending (polgnomially) on log(C).
One Extreme of the Bias- Variance Tradeoff: We may heuristically think of the Naive estimator as representing one extreme of the bias-variance tradeoff among reasonable estimators. For the sake of comparison, by the Markov Chain CLT, the Naive estimator is also asymptotically normal with standard deviation ( for the estimation of the mean of a Markov chain 18 On the other hand, while the Naive estimator is effectively useless for the problem at hand given its bias is in general ( that of the DQ estimator is ((8²).
A)2/2). This rate is efficient
3.3. A series expansion for the ATE
Our key technical contribution, as well as the motivation for the DQ estimator, is a novel Taylor series representation of the ATE which describes the off-policy avcrage reward as a sum of terms that can be estimated on-policy. The Naive estimator emerges as the zeroth-order truncation of the series; and the idcalized DQ estimator the natural first-order correction. The proof of Theorem proceeds by bounding the remainder. Here we sketch the deriviation of this series; see the Appendix for the full proof.
We first define few pieces of useful notation. Tet Po E TRIS P1/2 E RISI P1 E RRS] be the vectors of the stationary distributions of Po, P1,2, P1 accordingly. Let R| F1/2 RRSS rı [R|S| be the reward vectors associated with policies no, 11/2, 11, i.c., ra(s) = r(s,(( a) and T1/2 rru + fr1. The proof relies on a classic perturbation result, which allows us to quantify exactly the error induced by distribution shift:
Lemma 1 (Stationary Distribution Perturbation [36]). Let P,P' E RiS|x[S| be kernels of aperiodic and irreducible Markov Chains, with stationary distributions p.pl E RISI, Then,
pT = + pp (P' - P)(I - P)#
where (T- = P 1p is the group inverse of - P.
We will first apply Lemma to express X1 = pT rı in terms of P1/2:
- pf (Pi P1/2)( P1/2)*
We can now apply Lemma lggain to Pr in the RHS; applying this K times iteratively yields the expansion:
K
o (PI -1/2)( #1 n + Pi (P1 - P1/2)( - 11/2)*#1 K+1
0m0

---

This expansion expresses the off-policy average reward as a sum of on-policy quantities (i.e., expectations under P1/2); plus remainder term that can be bounded as:
Pi [PP- - P1/2)( +1 ri 1
K+1
C² 1-
8
K+1
Tmax
This has several immediate implications. First, the Naive estimator converges to the difference between the zeroth terms the expansion (i.e., K = 0) for p F1 and p ro; the resulting bias is then O()). The DQ estimator, in contrast, converges to the difference between the first-order partial sums of the expansion (i.e., K = 1) for pi P1 and p ro: the O(5²) bias in Theorem ] then follows immediately. This strategy can be iterated to generalize the DQ estinator to arbitrarily high-order bias corrections.
4. The Price of Being Unbiased
Thus far, we have seen that the DQ estimator provides a dramatic mitigation in bias (Theorem [ at a relatively modest price in variance (Theorem 2 This suggests another question: could we hope construct an unbiased estimator that has low variance (i.c. comparable to either the Naive or DQ estimators). We will see that the short answer is: no.
4.1. The Variance of an Optimal Unbiased Estimator
As noted earlier, plethora of Off- pooicol evaluation (OPE) algorithms might be used to provide an unbiased estimate of the ATE. Rather than consider a particular OPE algorithm, here we produce lower bound the variance of any unbiased OPE algorithm. While such a bound is obviously what we seck to accomplish in this paper). will primarily be interested in comparing this lower bound to the variance of the DQ estimator from Theorem 2
independent interest (since OPE is a far more general problem than
Theorem (Variance Lower Bound for Unbiased Estimators). Assume we are given a dataset (st, Oa, r(st, ae)) : = O,..., generated under the experimentatiin policy T1/2, with so distribuled according P1/2- Then for any unbiased eslimator & of ATE, we have that
T. Var(f)= 2 Σ (1(3)²
Ep(s, (s) 1)
P1)2(8)
+ Σ Po(s)²
P1/2(8) E
V. (8) +r, )TO)² - 03.
It is worth remarking that this lower bound is tight: in the appendix we show that an (STD(O) OPE algorithm achieves this lower bound. While this of independent interest vis-à-vis average cost OPE, we turn next to our ostensible goal here evaluating the "price" of unbiasedness. We can do so simply by comparing the variance of the DQ estimator with the lower bound above. In fact, we are able to exhibit class of one-dimensional Markov chains (in essence the same model proposed by 24 as a caricature of the dynamic interference problem) for which we have:
Theorem 4 (Price of Unbiasedness). For any 0 < S
5: there erists a class of MDPs parometerized by n E N, where is the number of states, such that
oD
=
Toff
for some constant > 1. Furthermore, [ATE - E[ATED)/ATE) 8.
Theorems and logether reveal the opposite extreme of the bias-variance Tradeoff. Specifically, if we insisted on unbiased estimator for our problem (of which there are many, thanks our framing of the problem as one of OPE), we would pay large price in terms of variance. In particular Theorem
Another Extreme of the Bias- Variance Tradeoff:

---

illustrates that this price can grow exponentially in the size of the state space. This jibes with our empirical evaluation in both caricatured and large-scale MDPs in Section
Taken together our results reveal that the DQ estimator accomplishes a striking bias- variance tradeoff: it has substantially smaller variance than any unbiased estimator (in fact, comparable to the Naive estimator), all while ensuring bias that is second order in the impact of the intervention.
5. Experiments
This section will empirically investigate the DQ estimator and a number of alternatives in two settings: simple oie-dimmnii toy model proposed by 24 and more realistically, city-scale simulator of ride-hailing platform similar to what large ride-hailing operators use in production. The alternatives consider include: 1) the Naive estimator; 2) TSRI-1 and TSRI-2, the "two-sided randomization" (TSR) designs catnss/sstmmttrss from 24]; 3) a varicty of OPE estimators. For the OPE estimators, note that off-policy average reward estimation
has only recently been addressed in 56 59]. and we implement their specific estimators
which simply denote TD and GTD respectively. We also implement extension to an LSTD type estimator proposed in 44
5.1. A toy example
We first study all of our estimators in a simple setting that does not call for any sort of value function approximation. Our goal is to understand the relative merits of these estimators in terms their bias and variance. To this end, we adopt precisely the toy MDP studied by 24]: ; stylized model of rental marketplace. This MDP is essentially 1-D Markov chain on N 5000 states parameterized by a 'customer arrival' rate X and a 'rental duration' rate μ.. At given state (so that units of inventory are in the system), the probability that an arriving eustomer rents a unit impacted by the intervention. As such if the intervention increases the probability of customer renting, this reduces the inventory availability for customers that arrive later. Our MDP setup exactly replicates that of 244, with N 5000, 1, μ 1; see the appendix for further details. We run all estimators over
20
19
DQ
Rel. RMSE
Nake
TBR-1
TSR-2
OPE (LSTD)
0.50
1.8
0.01
1.5
Nev
TSRI-
TBR
(LSTD)OPE (TD)
Figure 1: Toy-example from 24
Left Estimated ATE time t/N 10*
100
trajectories. Dashed line indicates actual ATE. Diamonds indicate the asymptotic mean each estimator. DQ shows compelling bias-variance tradeoff for this experimental budget. Right: Relative RMSE vs. Time; DQ dominates the alternatives at all timescales.
100 separate trajectories of length t = 10 N of the above MDP initialized in its stationary distribution. Figure I summarizes the results of this experiment. Beginning with the left panel, which reports estimated quantities at L 10 N, we immediately see: TSR improves on Naive: The actual ATE in the experiment 1.5%. Whereas has the lowest variance of the estimators here, the Naive estimator has among the highest bias. The

---

two TSR estimators reduce this bias substantially at modest increase in variance. It is worth noting, as a sanity check, that these results precisely recreate those reported in [24 OPE estimators are high variance: The OPE estimators have the highest variance of those considered here. The TD estimator has the lower variance but this is simply because it is implicitly regularized. Run long enough, both estimators will recover the treatment effect. DQ shows a compelling bias-variance tradeoff: In contrast, the DQ estimator has the lowest bias at t = 1 and its variance is comparable to the TSR estimators (It is worth noting that run long enough, the DQ estimator had a bias of ~ -5 x 10-7).
Conclusions hold across experimental budgets: Turning our attention briefty to the we show the relative RMSE (i.e. RMSE normalized by the treatment
right chart in Figure | effect) of the various estimators considered here across all experimental budgets t. RMSE eveectively scalarizes bias and variance and we see that on this scalarization the DQ estimator dominates the other estimators considered here over all choice of t.
We note that specialized designs such as TSR can still be valuable in specific settings: when A > μt for example, TSR is nearly unbiased (as shown in 24),, and can outperform DQ; see the appendix for such a study.
5.2. A Large-Scale Ridesharing Simulator
We next turn our attention to a city-scale ridesharing simulator similar to those used in production at large ride-hailing services. We will consider the problem of experimenting with changes to dispatching rules. Experimenting with these changes naturally creates Markovian interference by impacting the downstream supply/ positioning of drivers. Relative to the carlier toy example, the corresponding MDP here has an intractably large state-space, necossitating value function approximation for the DQ and OPE estimators.
Ridesharing admits a natural MDP; see e.g. [. The state at the time of a request, corresponds to that of all drivers at that time: position, assigned routes, riders, and the pickup/dropoff location of the request. Actions correspond to driver assignments and pricing decisions. The reward for a request is the price paid by the rider, less cost incurred to service the request. Our simulator models Manhattan. Riders and drivers are generated according to real world data, based on [I; this yields ~ 300k requests and ~ 7k unique drivers per real day. An arriving request is served a menu of options generated by a price engine. The rider chooses an option based on a choice model calibrated on taxi prices (for the outside option) and implied delay disutility from typical match rates. A dispatch engine assigns driver to the rider; the engine chooses the driver who can serve the rider at minimal marginal cost, subject to the product's 's constraints. Finally drivers proceed along their assigned routes until the next request. is received. The simulator implements pooling. Users can switch out demand and supply generation, pricing and dispatch algorithms, driver repositioning, and the choice model via simple API. Other simulators exist in the literature AI 58 but lack either an open-source implementation, or implement a subset of the functionality here.
The simulator:
We experiment with dispatch policies. Specifically, we consider assigning a request to an idle driver or a 'pool' driver, i.c. a driver who alrcady has riders in their car. A dispatch algorithm might prefer the former, but only if the cost of the resulting trip is at most a% higher than the cost of assigning to pool driver. We consider three experiments, each of which changes from baseline of 0 to one of three distinct values: 30%, 50% or 70%, with ATEs of 0.5%, -0.9%, and -4.6% respectively. As we noted earlier, we would expect significant. interference in this experiment (or indeed any experiment that experiments with pricing or dispatch) since an intervention changes the availability / position of drivers for subsequent requests.
The experiment:
Figure 2 summarizes the results of the above experiments, wherein each estimator was run over 50 independent simulator trajectories, each over 3 x 105 requests. The DQ and OPE estimators shared a common lincar approximation architecture with basis functions that count the number of drivers at every occupancy level. We note that this approximation introduces ils own bias which is not addressed by our theory. We immediately see: Strong Impact of Interference: As we might expect, interference has significant impact here as witnessed by the large bias in the Naive estimator.
Incumbent estimators do not improve on Naive: None of the incumbent estimators
9

---

ATP 46
ATP
XTP 05
ATE 44
100
Nahv
RMSE
TSH12
GPE (oro)
10
Heme
rans
Eumryy
OPE
no Hane
ran.
ran1
E
(11g))
oN (98)))
nd Aali
tamo
oee g on (D70)
Figure 2: Ridesharing model Left: AÎE at t = 3 x 10 50 trajectories. Dashed line indicates actual ATE, DQ has lowest bias, and only estimator to estimate correct sign of the treatment at all effect sizes. Right: RMSE vs. Time; DQ dominates at all time scales.
improve Naive in this hard problem. This is also the case for the TSR designs, which in this large scale setting surprisingly appear to have significant variance. The OPE estimators have lower variance due the regularization caused by value function approximation.
DQ works: In all three experiments, the bias in DQ (although in a relative sense higher Ihan in the loy model) is subslantially smaller than the alternatives, and also smaller than the ATE. This is evident in the left panel in Figure 2 Notice that in the rightmost experiment (ATE 0.5), DQ the only estimator to learn that the ATE positive. Like in the toy model, the right panel shows that these results are robust over experimentation budgets.
6. Discussion: refining the bias-variance tradeoff
To summarize, we have shown that the DQ estimator achieves a surprising bars-nariance tradeoff by applying on-policy estimation to the Markovian interference problem, and more generally to OPE. Here we draw further connections between the Naive, DQ, and OPE estimators, and suggest how to interpolate between these estimators to realize other points along the virs-nari curve.
State-space aggregation and the Naive estimator: Consider approximate estimation of the value function via state aggregation, for example in cases where the state space is massive. At one extreme, the DQ estimator corresponds to performing no aggregation; at the other, using single aggregate state reproduces the Naive estimator exactly. Controlling the level of aggregation (or more generally, the complexity of the value function approximation) interpolates between the DQ and Naive estimators.
Regularization and the OPE meta-estimator: large family of OPE estimators are formulated explicitly based the following identity the ATE:
ATE = E (1/2)(pz(s) + Po())) (0, 1) Qxy
(6)
P1/2(8)
Doubly robust estimators (see e.g. 27 52 for example, plug in estimates of the likelihood
ratio and value functions to (5), as do the closely related primal-dual estimators (see [3] 47).
However theory (Theorem 3) demonstrates that the cost of this unbiased estimation prohibitively high.
Notice, however, that simply setting the likelihood ratio to one immediately recovers the DQ estimator and its favorable guarantees. By regularizing the likelihood ratio estimates in OPE methods lowards one, then, one can interpolate along the bias-variance curve wet DQ and unbiased OPE. Recent regularized primal-dual OPE algorithms (e.g. 3% have in fact realized empirical performance gains from such regularization.
10

---

Higher-order Differences-in-Q::: As alluded to in Section 3.3 the series expansion that motivates the DQ estimator can be extended to obtain arbitrarily high-order bias corrections. The resulting estimators admit natural interpretations as Differences-inn- on-Qu-of- Differences-in--a Qs. This series of bias corrections represents a natural interpolation along the full bias-variance curve, from Naive estimation to unbiased OPE. Analyzing the bias variance tradeoff along this curve is an exciting direction for future work.
References
[1] TLC Trip Record Data TLC. httt:://ww....n.gerwsgghhg/e//br
dage.page.
[2] Susan Athey, Dean Eckles, and Guido W Imbens. Fxact p-values for network interference. Journal of the American Statistical Association, (:1522))230-240) 2018.
[3 Lars Backstrom and Jon Kleinberg, Network bucket testing. In Proceedings of the 20th international conference on World wide web, pages 615 624, 2011.
[4] Sarah Baird, J Aislinn Bohren, Craig Mcintosh, and Berk Özler. Optimal design of experiments in the presence of interference. Review of Economics and Statistics, 100(5):844-800 860, 2018.
[5] Patrick Bajari, Brian Burdick, Guido W Imbens, Lorenzo Masoero, James McQueen, Thomas Richardson, and Ido M Rosen. Multiple randomization designs. arXie preprint arXiv:2112. 194995 2021.
[6] Guillaume W Basse and Edoardo M Airoldi. Model-assisted design of experiments in the presence of network-correlated outcomes. Biometrika, 105(4):849 858, 2018.
[7] Guillaume W Basse, Avi Feller, and Panos Toulis. Randomization tests of causal effects under interference. Biomelrika, 106(2):487-495 494, 2019.
88 Thomas Blake and Dominic Cocy. Why marketplace experimentation is harder than it seems: The role of test-control interference. In Proceedings of the fifleenth ACM conference on Economics and computation, pages 567 582, 2014.
9 lavor Bojinov, David Simchi-Levi. and Jinglong Zhao. Design and analysis of switchback experiments. Available at SSRN 3684168, 2020.
110 David Choi. Estimation of monotone treatment effects in network experiments. Journal of the American Statistical Association, 112(519):1147-1155 2017.
[11] Jerome Cornfield. Randomization by group: a formal analysis. American journal of epidemiology, 108 102 1978.
[12] David Roxbee Cox. Planning of experiments. 1958.
[13] Bo Dai, Albert Shaw, Niao He, Lihong Li, and Le Song. Boosting the Actor with Dual Critic. arXie: 10282 fesf, December 2017.
[14] Allan Donner and Neil Klar. Pitfalls of and controversies in cluster randomization trials. American journal of public health, 94(3):416-422 2004.
[15] Dean Eckles, Brian Karrer, and Johan Ugander. Design and analysis of experiments in networks: Reducing bias from interference. Journal of Causal Inference, 5(1), 2017.
[16] John W Farquhar. The community-baset model of life style intervention trials. Americun journal of epidemiology, (08(2))103-11) 111, 1978.
[17] Peter W Glynn, Ramesh Johari, and Mohammad Rasouli. Adaptive Experimental Design with Temporal Interference: A Maximum Likelihood Approach. In Advances Newral Information Processing Systems, volume 33, pages 15054-15064 Curran Associates, Inc., 2020.
11

---

[18] Priscilla E Greenwood and Wolfgang Wefelmeyer. Efficiency of empirical estimators for markov chains. The Annals of Statistics, pages 132-143, 1995.
[19] COMMIT Research Group. Community intervention trial for smoking cessation (com- mit): summary of design and intervention. JNCI: Journal of the National Cancer Institute, 83(22)):620-1622) 1991.
[20] Huan Gui, Ya Xu, Anmol Bhasin, and Jiawei Han. Network a/b testing: From sampling to estimation. In Proceedings of the 24th International Conference on World Wide Web, pages 399 409, 2015.
[21] Michael G Hudgens and M Elizabeth Halloran. Toward causal inference with interference. Journal of the American Statistical Association, 103(482) 88322288222222 842, 2008.
[22] Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference Machine Learning, pages 652-661. PMLR, 2016.
[23] Ramesh Johari, Pete Koomen, Leonid Pekelis, and David Walsh. Peeking at a/b tests: Why it matters, and what to do about it. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1517-1525, 2017.
[24] Ramesh Johari, Hannah Li, Inessa Liskovich, and Gabriel Y Weintraub. Experimental design in two-sided platforms: An analysis of bias. Management Science, 2022.
[25] Ramesh Johari, Leo Pekelis, and David Walsh. Always valid inference: Continuous monitoring of A/B tests. Operations Research (To Appear), 2020.
[26] Sham Kakade and John Langford. Approximately Optimal Approximate Reinforcement Learning. In In Proc. 19th International Conference on Machine Learning, pages 267 274, 2002.
[27] Nathan Kallus and Masatoshi Uchara. Double reinforcement learning for efficient off-policy evaluation in markov decision processes. J. Mach. Learn. Res., (167))11-63 2020.
[28] Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon in off- off-policy evaluation with double reinforcement learning. Operations Research, 2022.
[29] Liran Katzir, Edo Liberty, and Oren Somekh. Framework and algorithms for network bucket lesting. In Proceedings of the 21st international conference on World Wide Web, pages 1029-1036, 2012.
[30] Eugene Kharitonov, Aleksandr Vorobev, Craig Macdonald, Pavel Serdyukov, and ladh Ounis. Sequential testing for early stopping of online experiments. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 473 482, 2015.
[31] John Kirn. Challenges in Experimentation. axpeimeettaionn-eeewlBaaaer April 2022.
[32] Ron Kohavi, Diane Tang, and Ya Xu. Trustworthy online controlled experiments: A practical guide to a/b lesting. Cambridge University Press, 2020.
[33] Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite-horizon off-policy estimation. Advances in Neural Information Processing Systems, 31, 2018
[34] David Lucking-Reiin Reiley. Using Field Experiments to Test Equivalence between Auc- tion Formats: Magic on the Internet. American Economic Review, 895):0066 1080, December 1999.
(35] Charles F Manski. Identification of treatment response with social interactions. The Econometries Journal, 16(1):81-S2) S23, 2013.
12

---

[36] Carl D Meyer, Jr. The condition of finite markov chain and perturbation bounds for the limiting probabilities. SIAM Journal on Algebraic Discrete Methods, 1(3).
[37] David M Murray et al. Design and analysis of group-randomized trials, volume 29. Monographs in Epidemiooogy and, 1998.
[38] Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Bchavior-agnostic ostimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, pages 2315-2325, 2019.
[39] Jean Pouget-Abadie, Kevin Aydin, Warren Schudy, Kay Brodersen, and Vahab Mirrokni. Variance reduction in bipartite experiments through correlation clustering. Advances in Neural Information Processing Systems, 32, 2019.
[40] Doina Precup, Richard $ Sutton, and Sanjoy Dasgupta. Off-policy temporal-difference learning with function approximation. In TCML, pages 417-424, 2001.
[41] Zhiwei Tony Qin, Hongtu Zhu, and Jieping Ye. Reinforcement Learning for Ridesharing: A Survey. In 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), pages
September 2021.
[42] Martin Saveski, Jean Pouget-Abadis Guillaume Saint-Jacques, Weitao Duan, Souvik Ghosh, Ya Xu, and Edoardo M Airoldi. Delecting network effects: Randomizing over randomized experiments. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and dala mining, pages 1027-1035, 2017.
[43] John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889- 1897. PMLR, 2015.
[44] Chengehun Shi, Xiaoyu Wang, Shikai Luo, Hongtu Zhu, Jieping Ye, and Rui Song. Dynamic Causal Effects Evaluation in A/B Testing with a Reinforcement Learning Framework. Journal of the American Statistical Association, 0jaa):1-29, January 2022.
[45) Carla Sncider, Yixin Tang, and Y Tang. Experiment rigor for switchback experi- ment analysis. URL: https://doordar engineering/200 2219 0020 20/ eepperimenttrigorfor suitchbackerpprimmett anaaissss, 2018.
[46] Richard S Sutton, Csaba Szepesvári, and Hamid Reza Maei. A convergent o (n) algorithm for off- off-policy Aduances neural information processing systems, 1662 2008.
learning with linear function approximation.
[47] Ziyang Tang, Yihao Feng, Lihong Li, Dengyong Zhou, and Qiang Liu. Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation, October 2019.
[48] Eric J Tehetgen Tehetgen and Tyler J VanderWeele. On causal inference in the presence of interference. Statistical methods in medical research, 21(1):55-775 75, 2012.
[49] Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning, pages 2139 2148. PMLR, 2016.
[50] Philip Thomas, Georgios Theocharous, and Mohammad Ghavanzadeh. High-confidence off- off-policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[51] Panos Toulis and Edward Kao. Estimation of causal peer influence effects. In Interna- tional conference on machine learning, pages 1489 1497. PMLR, 2013.
[52] Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax Weight and Q-Function Learning for Off-Policy Evaluation. In Proceedings of the 37th International Conference on Machine Learning, pages 9659-9668. PMLR, November 2020.
13

---

[53] Johan Ugander and Lars Backstrom. Balanced label propagation for partitioning massive graphs. In Proceedings of the sirth ACM international conference on Web search and data mining, pages 507-516, 2013.
[54] Johan Ugander, Brian Karrer, Lars Backstrom, and Jon Kleinberg. Graph cluster randomization: Network exposure to multiple universes. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and dala minnngg, pages 329 337, 2013.
[55] Dylan Walker and Lev Muchnik. Design of randomized experiments in networks. Proceedings of the IEEE, 102(12):1940-1951. 2014.
[56] Yi Wan, Abhishek Naik, and Richard S. Sutton. Learning and Planning in Average- Reward Markov Decision Processcs. In Proceedings of the 38th International Conference on Machine Learning, pages 10653-10662 PMLR, July 2021.
[57] Fanny Yang, Aaditya Ramdas, Kevin G Jamieson, and Martin J Wainwright. A framework for multi-a (rmed)/b (andit) testing with online fdr control. Advances in Neural Information Processing Systems, 30, 2017.
[58] Rui Yao and Shlomo Bekhor. A ridesharing simulation platform that considers dynamic supply-demand interactions. April 2021.
[59] Shangtong Zhang, Yi Wan, Richard S. Sutton, and Shimon Whiteson. Average-Reward Off-Policy Policy Evaluation with Function Approximation. In Proceedings of the 38th International Conference on Machine Learning, pages 12578-12588, PMLR, July 2021.
[60] Corwin M Zigler and Georgia Papadogcorgou. Bipartite causal inference with interference. Statistical science: review journal of the Institute of Mathematical Statistics, 36(1):109, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect
the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms
to them? [Yes]
2. If you are including thcoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all thcoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (cither the supplemental material or as a URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after rumning experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix.
4. Tf you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] No use of existing assets.
14

---

(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as
URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are esing/curating contains personally
identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "KY3vPI1zY1", "reviewer": "Reviewer_frjR", "summary": "This paper develops a novel biased estimator for the average treatment effect with an MDP model. Here, the average treatment effect is the difference between the reward obtained with and without treatment. This estimator is the difference between the empirical average of Q-values corresponding to the cases with and without applying treatment, which is very similar to a naive estimator that computes the difference of rewards instead of Q-values. However, the authors show that in some cases, this new estimator has a negligible bias, which is significantly better than the naive estimator. Moreover, with some mild conditions, they show that this new estimator is asymptotically unbiased. The variance of the limit random variable of this new estimator enjoys a smaller variance than all unbiased estimators. Finally, the authors elaborate their results with numerical experiments.", "questions": "1. I was wondering whether you could provide more intuition to use the Q-value.\n        \n2. If the probability of applying the treatment is not 1/2, which might be a small value, how will this change affect those results.\n\n3. I wonder if there are some finite sample results corresponding to Theorem 2?\n        \n4. For the comparison between the naive estimator and the DQ estimator, if the difference of the transition probability distributions between applying treatment or not is large, will the naive estimator work better or not?", "limitations": "I think there is no potential negative social impact of the work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The idea of this new estimator is simple and clear, and, at the same time, the authors provide strong results.\n        \n2. This new estimator is computationally affordable.\n\nWeaknesses:\n\n1. It would be better to have some finite sample results corresponding to Theorem 2. \n        \n2. The motivation or intuition of using Q-value instead of reward seems not strong enough.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AS5aAErBlZX", "reviewer": "Reviewer_P5xj", "summary": "This paper examines estimating the difference in reward performance of two policies for a Markov Decision Process (MDP) by running a mixture policy and performing on-policy evaluation. The paper shows theoretically the benefits over current methods of policy evaluation of using a difference in $Q$ values estimation process. Specifically, this approach obtains a small estimator variance and a estimation bias that is second order in the effect of the \"intervention\" policy (the policy being tested against an existing policy). ", "questions": "Line 38: \"designs are not be an ideal lever\";  perhaps \"be\" should be deleted.\n\nLine 38 and 39: \"and often infeasible\"; perhaps this should be \"and are often infeasible\" .\n\n", "limitations": "It would have been nice to see some proof outlines in the paper. There was no supplementary appendix at the end of the paper. I assume it required a separate download.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(S) the paper is very well written. It is clear and precise. I found very few typos.\n\n(S) The paper tackles a very  important problem and gives a compelling argument and demonstration for how it can be solved in a much better fashion compared to current approaches.\n\n(S) Theoretical results are explained well (NOTE: although no proofs are included in the body of the paper). \n\n(S) The experimental results use a large scale realistic problem and shown strong evidence for substantial and meaningful improvement.\n\n(S) The experimental results are very well presented and interpreted.\n\n(S) Excellent reference list (66 references).\n\n(W) It would have been nice to see proof outlines (at least) in the paper. I assume proofs are given in supplemental material ( I did not check).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8v0JaIpi6s", "reviewer": "Reviewer_7PnB", "summary": "The paper considers the problem of estimating the average treatment effect, where experimenting on some treatment group might also affect the control group. The problem is motivated by several practical scenarios, such as inventory management, ride sharing, etc, where both the treatment and the control group share a common pool of resources. The authors cast this as an off-policy evaluation problem and propose a new estimator that adequately balances the bias-variance trade-off in this setting. Experiments on a toy domain and raid-hailing simulator are used to demonstrate the effectiveness of the proposed method.\n\n", "questions": "A\\. Section 2.1: My understanding is that during implementation the intervention policy is at least tried to be coherent within an episode (here episode might correspond to one user or one session). In the discussion/example it seems like the policy is being switched within a single episode. I can see one argument that from the point of view of the system, it may not be able to distinguish different users, but in that case it is a POMDP setting and not an MDP one?\n\nI see the high-level problem but I am quite confused by the formulation of it. (For disclosure, I am not well aware of the interference literature.)\n\nB\\. Assumption 1: For which values of $k$? I am not sure if I have a complete understanding of what this assumption implies and how practical it is. Particularly, along with the assumption in Theorem 1, what does it say about the steady state distribution and the mixing time for the treatment and the control policies?   \n\nC\\. Line 176 and Eqn 3: At both the places the proposed estimator is dropped in without much discussion about why one would expect this to work. I see the proof for Theorem 1, but I am failing to understand intuitively why the proposed procedure helps. Both the Q functions and the distribution for computing the expectations are for the data collecting policy. It feels like this estimator is only making one step correction according to the two policies being compared, which is a lot like what the naive estimator would do as well. What is the correct way to interpret this estimator?\n\n\nD\\. How does the mixing time assumption influence the empirical results? Showing this on the toy-example at least would be helpful. \n", "limitations": "While the proposed method is straightforward to express, I do not think I have a good understanding of it to provide any constructive criticism (I had not bid to review this work). As such, I have lowered my confidence for this review and will update my score based on discussions with other reviewers after the rebuttal.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The problem is applicable to a large number of practical applications and thus the work can be of high relevance to a broad audience.\n- The proposed estimator is straightforward to implement, and at the same time provides adequate bias-variance trade-off.\n- The proposed method provides strong performance in the experiments conducted.\n\nWeakness\n\n- It is not clear how reasonable is Assumption 1.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5SiCl3HYKd", "reviewer": "Reviewer_RgZV", "summary": "The paper introduces a treatment estimator for experiments with markovian interference using an on-policy RL approach. The authors show that their estimator achieves a good bias variance tradeoff vs other baselines (two sided randomization, off policy estimators), and that unbiased estimators necessarily have large variance. Finally, the technical results and estimation strategies are illustrated in two experiments: on that re-uses the framework from Johari et al, and another the author's own simulation code that simulates a ride-sharing experiment.", "questions": "The averaging of estimates over long periods of time into single point estimates is not always regular practice, and I'm afraid that in this case, the framework wouldn't apply so easily. Often, just daily estimates are compiled and reported. Is this because of non markovian interference, or seasonal effects, or time to reach equilibrium? Some discussion there would clarify things for the reader and map this to a setting they are familiar with. ", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper seemed to me to be strong. It's well written and was enjoyable to read. I have little criticism to make, though I have to admit I'm not familiar enough with the RL literature to be entirely confident in my assessment. I particularly appreciated that the experiment section was clear, and re-used available open source code, or made the code available, with sufficient baselines.\n\n One thing that would improve the paper is to relate the notation to the potential outcomes notation which is standard in this setting and which many readers in this space are familiar with. More specifically, it would be nice to characterize in this notation which settings can be considered markovian interference where this framework applies.\n\nnit: typos l. 38, l. 68.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept