# Limits of Approximating the Median Treatment Effect

arXiv: https://arxiv.org/abs/2403.10618 · HTML: https://mlsanity.com/paper/2403.10618/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 16 references that are in the map.
- First posted on arXiv 15 Mar 2024.

## Builds on (most cited first, 9 of 9)

- [Recursive Partitioning for Heterogeneous Causal Effects](https://mlsanity.com/paper/1504.01132/) (2015)
- [Nonparametric methods for doubly robust estimation of continuous treatment effects](https://mlsanity.com/paper/1507.00747/) (2015)
- [Sequential estimation of quantiles with applications to A/B-testing and best-arm identification](https://mlsanity.com/paper/1906.09712/) (2019)
- [What's the Harm? Sharp Bounds on the Fraction Negatively Affected by Treatment](https://mlsanity.com/paper/2205.10327/) (2022)
- [Balancing Covariates in Randomized Experiments with the Gram-Schmidt Walk Design](https://mlsanity.com/paper/1911.03071/) (2019)
- [Decomposing Treatment Effect Variation](https://mlsanity.com/paper/1605.06566/) (2016)
- [Median Optimal Treatment Regimes](https://mlsanity.com/paper/2103.01802/) (2021)
- [Sample Constrained Treatment Effect Estimation](https://mlsanity.com/paper/2210.06594/) (2022)
- [Counterfactual Density Estimation using Kernel Stein Discrepancies](https://mlsanity.com/paper/2309.16129/) (2023)

## Abstract (arXiv)

Average Treatment Effect (ATE) estimation is a well-studied problem in causal inference. However, it does not necessarily capture the heterogeneity in the data, and several approaches have been proposed to tackle the issue, including estimating the Quantile Treatment Effects. In the finite population setting containing n individuals, with treatment and control values denoted by the potential outcome vectors a, b, much of the prior work focused on estimating median(a) - median(b), where median(mathbf x) denotes the median value in the sorted ordering of all the values in vector mathbf x. It is known that estimating the difference of medians is easier than the desired estimand of median(a-b), called the Median Treatment Effect (MTE). The fundamental problem of causal inference -- for every individual i, we can only observe one of the potential outcome values, i.e., either the value ai or bi, but not both, makes estimating MTE particularly challenging. In this work, we argue that MTE is not estimable and detail a novel notion of approximation that relies on the sorted order of the values in a-b. Next, we identify a quantity called variability that exactly captures the complexity of MTE estimation. By drawing connections to instance-optimality studied in theoretical computer science, we show that every algorithm for estimating the MTE obtains an approximation error that is no better than the error of an algorithm that computes variability. Finally, we provide a simple linear time algorithm for computing the variability exactly. Unlike much prior work, a particular highlight of our work is that we make no assumptions about how the potential outcome vectors are generated or how they are correlated, except that the potential outcome values are k-ary, i.e., take one of k discrete values.