Information Ledger: Exact Decomposition of Sequential Decision Limits

In the theory of reinforcement learning and sequential decision-making, instance-dependent limits have always been key to understanding the performance boundaries of algorithms. A recent study unifies the instance-dependent limits of multi-armed bandit regret, sequential testing, best-arm identification, and Markov decision processes (MDPs) into a single proof chain. This chain starts from a divergence decomposition, passes through data processing, and ultimately derives the classical limits via statistics, testing steps, and optimization over alternatives and allocations. The authors write this chain as an exact "information ledger," where the losses and gains at each step are clearly accounted for.

From Divergence Decomposition to Exact Ledger

The core of this proof chain lies in the identity of divergence decomposition. Specifically, the KL divergence between two instances can be decomposed into a sum of per-arm contributions, and the data processing inequality here is not a simple relaxation—it exactly loses a conditional divergence. For arms in the natural exponential family, given the per-arm counts and reward sums, this conditional divergence is exactly zero. Thus, the first entry in the ledger is: the data processing step introduces no additional relaxation; it merely redistributes information.

The authors further introduce a one-parameter family of martingale identities, generalizing the decomposition to arbitrary tilts between two instances. This means that, not only for the original distribution, but for any exponential tilt, the divergence can be tracked exactly. This provides a flexible mathematical tool for subsequent limit analysis.

KL divergence (Kullback-Leibler divergence) is an asymmetric measure of the difference between two probability distributions, defined as (D_{\mathrm{KL}}(P | Q) = \mathbb{E}P[\log \frac{dP}{dQ}]). In bandit problems, if two instances differ only in the reward distribution of one arm, the total KL divergence decomposes into a sum of per-arm contributions. The data processing inequality states that after applying any (possibly random) transformation to the data, the divergence between the two distributions does not increase, i.e., (D{\mathrm{KL}}(P_Y | Q_Y) \le D_{\mathrm{KL}}(P_X | Q_X)). Typically it is used as an inequality for bounding, but this paper emphasizes its equality form: the loss is exactly the conditional divergence between the original distributions given the transformed statistic. For the natural exponential family, when the transformation is taken as the per-arm counts and reward sums, this conditional divergence is zero, so the data processing step introduces no information loss.

The natural exponential family is a class of common probability distributions whose density can be written as (p(x;\theta) = h(x)\exp(\theta^\top T(x) - A(\theta))), where (T(x)) is the sufficient statistic and (A(\theta)) is the log-partition function. Bernoulli, Gaussian, Poisson, and other distributions belong to this family. In bandits, if each arm's reward distribution comes from an exponential family, then given that arm's count and reward sum (i.e., the sufficient statistic), the posterior or conditional distribution of the parameter no longer depends on the specific values of the raw data, so the conditional divergence is zero. Moreover, the exponential family allows obtaining a tilted distribution by adjusting the natural parameter (\theta), i.e., (p_\theta(x) \propto p(x)e^{\theta^\top T(x)}), which provides the basis for generalizing the divergence decomposition to arbitrary tilts.

Classical Limits as Results of Relaxation

With the exact ledger in hand, deriving the classical limits becomes a matter of relaxing the terms in the ledger. Each relaxation step corresponds to a "named defect," and these defects quantify the gap between the limit and the exact value. Except for the defect of the asymptotic step, all other defects can be computed from the algorithm's own run. The defect of uniform quantification is computable only when the class guarantee is a specific numerical value.

The value of this framework lies in clearly identifying the sources of discrepancy between standard algorithms and classical limits. The authors validate it on seven published data sources, from movie ratings to engine replacement, and the ledger successfully locates the discrepancies. For example, in identification between trained models and Wald tests, the largest defect term typically comes from uniform quantification.

Wald test is a classical method in statistical hypothesis testing, used to test constraints (H_0: \theta = \theta_0) on a parameter (\theta). Its test statistic is based on the Mahalanobis distance between the maximum likelihood estimate (\hat{\theta}) and (\theta_0): (W = (\hat{\theta}-\theta_0)^\top I(\hat{\theta})(\hat{\theta}-\theta_0)), where (I(\theta)) is the Fisher information matrix. Under the null hypothesis, (W) asymptotically follows a chi-squared distribution. In the context of sequential testing, the instance-dependent limit of the Wald test is typically derived via a chain of KL divergences, and the "uniform quantification" defect refers to replacing instance-dependent exact quantities with a uniform threshold or bound, thereby causing a loss in test power. The ledger framework in this paper can quantify this defect and points out that it is often the largest source of relaxation in the Wald test.

Implications for Algorithm Practice

The significance of this work lies not only in theoretical unification but also in providing a diagnostic tool for algorithm design. Through the ledger, researchers can precisely know at which step the algorithm loses information, allowing for targeted improvements. For example, if uniform quantification is the main defect, then more refined class guarantees or adaptive allocation strategies may be needed.

Moreover, the ledger framework is extensible. Although this paper focuses on the four types of problems above, its methodology may apply to a broader range of sequential decision-making scenarios. Future work can explore how to apply the ledger to more complex models or how to use the ledger to design new algorithms.

In summary, this study transforms the proof chain of instance-dependent limits into an exact information ledger, providing a new perspective for understanding algorithm performance. It emphasizes the exactness of the data processing step and reveals the relaxation structure behind classical limits. For theoretical researchers, this is a powerful analytical tool; for practitioners, it provides a way to diagnose algorithmic defects.

One-line Summary

The study unifies the instance-dependent limits of four sequential decision problems into an exact information ledger, quantifying relaxation defects.

Paragraph Summary

The study proposes a unified proof chain linking the instance-dependent limits of multi-armed bandit regret, sequential testing, best-arm identification, and Markov decision processes. The core is the identity of divergence decomposition: KL divergence decomposes into a sum of per-arm contributions, the data processing step exactly loses a conditional divergence, and under the natural exponential family this conditional divergence is zero, so the ledger has no additional relaxation. Via a one-parameter family of martingale identities, the decomposition generalizes to arbitrary tilts. Classical limits are obtained by relaxing the ledger terms, with each relaxation step corresponding to a "named defect"; most defects can be computed from the algorithm's run, while the uniform quantification defect is computable only when the class guarantee is a specific numerical value. Validation on seven data sources shows that the ledger can locate discrepancies between standard algorithms and classical limits, and uniform quantification is typically the largest defect term in identification and Wald tests.