Effective Sparsity in Distribution and Error Estimation and Off-Policy Evaluation

Estimating a discrete probability distribution from a finite sample is a fundamental problem in machine learning and statistics. Classical guarantees typically depend on the alphabet size $K$ or the observed support $T$, although in many applications the quantity of interest depends only on a structured, data-dependent combination of distributional errors. We identify *effective sparsity* as a useful notion of complexity for such quantities and develop a concentration bound that adapts to the residual structure of data-dependent coefficients while separately accounting for the probability mass of unseen categories. *Our bound removes the direct dependence on $\sqrt{K}$ and $\sqrt{|T|}$*, which can be crucial in high-dimensional problems with approximately sparse structure. We further demonstrate substantial improvements in two important problems. First, in generalization analysis via Algorithmic Robustness, our bound replaces the $\sqrt{K}$ or $\sqrt{|T|}$ dependence in existing guarantees by the effective residual mass of local model errors. Experiments on 22 pretrained ImageNet models show that our uncertainty term is consistently substantially smaller than the recent robustness-based bound. Second, in off-policy evaluation for finite-horizon confounded partially observable decision processes, our analysis replaces the exponential dependence on the observation-action history space in existing first-order error bounds by polynomial dependence on the horizon under realistic effective-sparsity conditions, *yielding an exponential improvement in the dependence on history size*. These results establish effective sparsity as a general mechanism for obtaining substantially sharper distribution and error estimation guarantees in high-dimensional problems.