Instance-Dependent Sequential Limits as an Exact Information Ledger (arXiv 2610.42133)

Summary

A new paper by Akshay Balsubramani (arXiv:2610.42133, October 2026) unifies instance-dependent limits for bandit regret, sequential testing, best-arm identification, and Markov decision processes into a single inferential chain. The chain runs from a divergence decomposition through data processing to a statistic, a testing step that converts class guarantees into requirements on the history, and optimization over alternatives and allocations. The work formalizes this chain as an exact 'ledger': by the chain rule, data processing loses exactly one conditional divergence, which vanishes for arms in natural exponential families at per-arm counts and reward sums. A one-parameter family of martingale identities extends the decomposition to every tilt between two instances. Classical limits emerge as relaxations with named defects; all defects except those from asymptotic steps are computable from the algorithm's own run, and uniformly quantified defects are computable when the class guarantee is numeric. On seven published datasets—from movie ratings to engine replacements—the ledger pinpoints gaps between standard algorithms and classical limits. In best-arm identification and Wald tests between trained models, the dominant terms are typically the uniformly quantified defects.