Markovian Interference in Experiments

The Differences-In-Q's Estimator

We are now prepared to introduce our estimator for inference in the presence of Markovian interference. Before defining our estimator, which we will see is only slightly more complicated than the Naive estimator, we recall a few useful objectis in average-reward MDPs. Denote the average cost of a policy $\pi$ by $\lambda^{\pi}$. The $V$-function of a policy $\pi$, $V_{\pi}$, characterizes the “reward-to-go” $V_{\pi}(s) := \E\Big[\sum_{t=0}^{\infty} r(s_t, a_t) - \lambda^{\pi}~\big|~s_0 = s\Big].$ It is also known that $(V_{\pi}, \lambda^{\pi})$ is the fixed point of the Bellman operator $T_{\pi}$ with $T_{\pi}(V_{\pi}, \lambda^{\pi}) = V_{\pi}.$ Here $T_{\pi}: \mathbb{R}^{|\Sscr|} \times \mathbb{R} \rightarrow \mathbb{R}^{|\Sscr|}$ is given by $T_\pi (V, \lambda) = r_\pi - \lambda \mathbf{1} + P_{\pi} V$ where $r_\pi: \Sscr \rightarrow \mathbb{R}$ is defined according to $r_\pi(s) = \E\left[r(s, \pi(s))\right]$. Finally, the $Q$-function associated with $\pi$, denoted $Q_\pi: \Sscr \times \Ascr \rightarrow \mathbb{R}$, is defined according to $Q_\pi(s,a) := \E\Big[\sum_{t=0}^{\infty} r(s_t, a_t) - \lambda^{\pi}~\big|~s_0 = s, a_0 = a\Big]$. Put simply, the $Q$-function measures the `excess' reward obtained starting from $s$ with the action $a$ relative to the average reward under $\pi$.

An Idealized First Step

In motivating our estimator, let us begin with the following idealization of the Naive estimator, where we denote by $\rho_{1/2}$ the steady state distribution under the randomization policy $\pi_{1/2}$: $\E_{\rho_{1/2}} \left[\hat {\rm ATE}_{\rm NV}\right] = \sum_s \rho_{1/2}(s) \left[ r(s,1) - r(s,0)\right].$ It is not hard to see that in the example of Section (ref), we continue to have $\lvert \E_{\rho_{1/2}} [\hat {\rm ATE}_{\rm NV} ] - {\rm ATE} \rvert \approx \frac{p\lambda}{\mu} \mathrm{ATE}$, i.e. this idealization of the Naive estimator continues to have bias on the order of the treatment effect. Consider then, the following alternative: \[ \E_{\rho_{1/2}} \left[\tauDK\right] = \sum_s \rho_{1/2}(s) \left[Q_{\pi_{1/2}}(s,1) - Q_{\pi_{1/2}}(s,0)\right], \] where the term $\E_{\rho_{1/2}} [\tauDK]$ can for now just be thought of as an idealized constant ($\tauDK$ is defined soon in (ref)). Compared to $\E_{\rho_{1/2}} [\hat {\rm ATE}_{\rm NV}]$, we see that $\E_{\rho_{1/2}} [\hat {\rm ATE}_{\rm DQ}]$ takes a remarkably similar form, except that as opposed to an average over differences in rewards, we compute an average of differences in $Q$-function values. The idea is that doing so will hopefully compensate for the shift in distribution induced by $\pi_{1/2}$, as it does in the example of Section (ref).

Is the dramatic mitigation of bias we see in the example generic? If the experimentation policy mixes fast, our first set of results essentially answers this question in the affirmative. In particular, we make the following mixing time assumption:

We then have that the second order bias we saw in Section (ref) is, in fact, generic:

The Differences-In-Q's Estimator

Motivated by the development in the previous subsection, the {\em Differences-In-Q's (DQ)} estimator we propose to use is simply

where we take an empirical average over the state trajectory produced under the randomization policy, and $\hat Q_{\pi_{1/2}}$ is an estimator of the $Q$-function. For concreteness, we obtain $\hat Q_{\pi_{1/2}}$ by solving

Our main result characterizes the variance and asymptotic normality of $\hat {\rm ATE}_{\rm DQ}$:

The fact that $\sigma_{\rm DQ}$ in (ref) only depends on $1/\rho_{\min}$ logarithmically is somewhat surprising. In fact, a coarse analysis will lead to $\sigma_{D} = \Omega\left(\frac{1}{\rho_{\min}}\right)$, which shows no advantage compared to the unbiased OPE estimators (which we will see momentarily). The key enabler for this striking result is a novel lemma that exploits an entry-wise bound for controlling the variance, even at states that are rarely visited (we dub this the “Entry-wise Non-expansive Lemma”; see (ref)). The lemma admits a simple form and may have broader implications for analyzing variance in OPE estimators (see Discussions in (ref)). In addition, our asymptotic normality analysis borrows the delta-method framework used in the context of on-policy LSTD konda2002actor, but with a novel linearization that dramatically simplifies the analysis. See (ref) for more details.

\noindentOne 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 $\Theta (r_{\rm max}/ (1-\lambda)^{1/2})$. This rate is efficient for the estimation of the mean of a Markov chain greenwood1995efficiency. On the other hand, while the Naive estimator is effectively useless for the problem at hand given its bias is in general $\Theta(\delta)$, that of the DQ estimator is $O(\delta^2)$.

Proof of (ref)

The proof of (ref) is a simple proof built on a perturbation formula for stationary distributions of Markov chains. We in fact construct a novel Taylor series representation of the ATE parameterized by $\delta$ that controls the perturbation around $P_{1 / 2}$, which yields the Naive estimator as the zeroth-order truncation of the series; and the idealized DQ estimator as the natural first-order correction. (ref) then proceeds by bounding the remainder. This strategy additionally allows us to generalize the DQ estimator to arbitrarily high-order bias corrections, by computing $Q$-functions iteratively. Here we present the proof (with some details omitted for simplicity).

We first define few pieces of useful notation. Let $\rho_{0} \in \R^{|\Sscr|}, \rho_{1/2} \in \R^{|\Sscr|}, \rho_{1} \in \R^{|\Sscr|}$ be the vectors of the stationary distributions of $P_0, P_{1/2}, P_{1}$ accordingly. Let $r_0 \in \R^{|\Sscr|}, r_{1/2} \in \R^{|\Sscr|}, r_1 \in \R^{|\Sscr|}$ be the reward vectors associated with policies $\pi_0, \pi_{1/2}, \pi_{1}$, i.e., $r_{a}(s) = r(s, a)$ and $r_{1/2} = \frac{1}{2} r_0 + \frac{1}{2} r_1.$

To begin, we parameterize $P_0 := P_{1/2} - \delta A$ and $P_1 := P_{1/2} + \delta A$ by $\delta$ with fixed $P_{1/2}$ and some fixed matrix $A \in \R^{|\Sscr|\times |\Sscr|}$ with $\|A\|_{1,\infty} \leq 1$ ($\|A\|_{1,\infty} = \max_{i}\sum_{j}|A_{ij}|$)\footnote{This is always possible since $d_{\rm TV}( p(s,1,\cdot), p(s,0,\cdot) ) \leq \delta.$ }. Then, $\rho_{0}$ and $\rho_{1}$ can also be viewed as a function of $\delta.$ Also recall ${\rm{ATE}} = \rho_{1}^{\top} r_{1} - \rho_{0}^{\top} r_0$. Our goal is to represent ${\rm{ATE}}$ as a function of $\delta$ and then study the Taylor expansion of such a function. To do so, we use the following known perturbation formula of Markov chains.

Let us apply (ref) to $\rho_{1}^{\top} r_1$ based on the perturbation between $\rho_{1/2}$ and $\rho_{1}$.

Note that we can apply (ref) again to the $\rho_{1}$ in the RHS of (ref) and then repeat this process,

for any $K = 0, 1, 2, \dotsc$. Essentially (ref) provides the $K$-th order Taylor expansion for $\rho_{1}^{\top}r_1$ with an explicit remainder. Furthermore, we can bound the remainder by

Here in (i) we use that for any vector $a, b$ and matrix $B$, we have $|a^{\top}b| \leq \|a\|_{1}\|b\|_{\max}$ and $\norm{a^{\top}B}_{1} \leq \norm{a}_{1} \norm{B}_{1,\infty}$. In (ii) we use that $\norm{\rho_1}_1 = 1, \norm{A}_{1,\infty} \leq 1$. In (iii), we use the following lemma implied by the mixing time assumption and the series expansion of $(I-P)^{\#}.$

Appplying a similar process to $\rho_{0}^{\top}r_0$, we obtain the Taylor expansion for the ATE.

where $|a_{K}| \leq 2\left(\frac{2\ln(C)+1}{1-\lambda}\right)^{K+1} r_{\max}.$ It is easy to see that the Naive estimator $\rho_{1/2}^{\top}(r_1-r_0)$ corresponds to the zeroth-order truncation. In fact, the DQ estimator, i.e., $\E_{\rho_{1/2}} \left[\tauDK \right]$, exactly matches the first-order truncation. To see this, by the definition of $\E_{\rho_{1/2}} \left[\tauDK \right]$ and $Q$-functions,

where $V_{1/2}$ is the induced vector of the $V$-function of policy $\pi_{1/2}.$ By the well-known fact that $V_{1/2} = (I-P_{1/2})^{\#} r_{1/2}$ induced by the Bellman equation, we then have

Then indeed $\E_{\rho_{1/2}} \left[\tauDK \right]$ is the first-order Taylor truncation. Together, this completes the proof. \noindentGeneralization to Higher-Order Bias Correction. In fact, the K-th order Taylor expansion of ATE allows us to design estimators that can correct higher-order bias, based on computing difference-in-Q functions iteratively. See details in (ref).

Proof Sketch of (ref)

We aim to use the Markov chain CLT (jones2004markov) to show asymptotic normality of our estimator. The Markov chain CLT states that for a Markov chain $X_{1}, X_{2}, \dotsc, $ and a bounded function $u$ with domain on the state space, there exists $\Sigma_{u}$ such that $\sqrt{T}\left(\frac{1}{T}\sum_{t=1}^{T} u(X_t) - u^{*}\right) \overset{d}{\rightarrow} N(0, \Sigma_{u})$ where $u^{*}$ is the expected value of $u$ under the stationary distribution of the Markov chain. See proof details in (ref).

\noindentDelta method. Unfortunately, the estimator $\tauDK$ can not be directly written as an empirical average of some function $u.$ To address this issue, we use the the delta method (traced back to doob1935limiting, see (ref)). In particular, we write $\tauDK = f(u_T)$ as a function of a random vector $u_{T}$ given by $u_{T} := \frac{1}{T}\sum_{t=1}^{T} u(X_{t}).$ Under some minor conditions, the delta method states that $\sqrt{T} \left(f(u_{T}) - f(u^{*})\right) \overset{d}{\rightarrow} N(0, \sigma_{f}^2)$ where $\sigma_{f}^2 := \nabla f(u^{*})^{\top} \Sigma_{u} \nabla f(u^{*})$ and $\nabla f(u^{*})$ is the gradient of $f$ evaluating at the point $u^{*}.$ This forms the basis for proving (ref).

\noindentLinearization. To simplify the analysis for $\sigma_{f}$, instead of computing $\Sigma_{u}$ explicitly, we “linearize” the function $f$ by defining $\tilde{f}(X_{t}) := \nabla f(u^{*})^{\top}(u(X_t)-u^{*})$ and the delta method in fact implies (see (ref)) $\sqrt{T}\left(\frac{1}{T}\sum_{t=1}^{T} \tilde{f}(X_t)\right) \overset{d}{\rightarrow} N(0, \sigma_{f}^2),$ i.e., the linearized $f$ converges with the same limiting variance as the original $f.$ Therefore, we can focus on $\tilde{f}$ for analyzing $\sigma_{f}.$

\noindentBounding $\sigma_f$ with Entry-wise Non-expansive Lemma. To bound $\sigma_{f}$, we will invoke (ref), which states that $\sigma_{f} \leq \sqrt{2}\sqrt{\frac{2\ln(C)+1}{1-\lambda}}\tilde{f}_{\max}$ where $\tilde{f}_{\max} := \max_{s} |\tilde{f}(s)|.$ Then the problem reduces to bounding $\tilde{f}_{\max}$, which will be controlled by the following key lemma.