Instance dependent limits reveal algorithm gaps in sequential decisions
Instance-dependent sequential limits as an exact information ledger
Machine LearningInformation Theory
Summary
When computers try to learn or decide by testing options one after another, they face limits on how well they can do. This work finds a neat way to exactly track the information used at each step, showing where small losses happen in the process. By applying this method to various real examples, the authors show how common algorithms fall short compared to the best possible limits. This helps identify parts of learning and testing systems that could be improved.
What this means in practice
- •For machine learning engineers: Evaluate how well sequential decision algorithms perform compared to fundamental limits using exact information tracking from recorded runs.
- •For quality control teams: Improve sequential testing processes by pinpointing inefficiencies in how data is gathered and decisions are made over time.
Tested on seven published datasets.
Authors
Akshay Balsubramani
Abstract
Instance-dependent limits for bandit regret, sequential tests, best-arm identification and Markov decision processes are proved by one chain. It runs from a divergence decomposition through data processing to a statistic, a testing step that turns a class guarantee into a requirement on the history, and optimization over alternatives and allocations. Only the first step is an identity. This work writes the chain as an exact ledger. By the chain rule, data processing loses exactly a conditional divergence, which vanishes for arms in natural exponential families at the per-arm counts and reward sums. A one-parameter family of martingale identities extends the decomposition to every tilt between two instances. The classical limits follow by relaxations with named defects. All defects but the asymptotic step's can be computed from an algorithm's own runs, the uniform quantification's only when the class guarantee is a number. On seven published sources, from movie ratings to engine replacement, the ledger locates the difference between standard algorithms and the classical limits. For identification among trained models and for Wald's test the largest term is usually the uniform quantification's.