Events

Markovian Interference and the Differences-in-Qs Estimator

We consider experiments in dynamical systems where interventions on some experimental units impact other units through a limiting constraint (such as a limited inventory). 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. Typical off-policy estimators apparently incur a large penalty in variance relative to state-of-the-art heuristics. We introduce the Differences-In-Q’s (DQ) estimator. We show that the DQ estimator can in general have exponentially smaller variance than unbiased 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. Along the way, we develop a new Laurent expansion for average cost dynamic programming that is of general interest. Our empirical evaluation includes a set of experiments on a city-scale ride-hailing simulator.