用精确信息账本统一推导序贯决策的下界
Instance-dependent sequential limits as an exact information ledger
数学味很浓的论文，把四类序贯问题（bandit、best-arm、MDP 等）的下界推导串成一条链，还拿 7 个真实数据集验证了差距到底出在哪一步。
这篇 arXiv 论文将 bandit 遗憾、序贯检验、best-arm identification 和 Markov 决策过程的 instance-dependent 下界用一条推导链统一证明。链条从散度分解经数据处理到统计量，再通过检验步骤把类别保证转化为对历史轨迹的要求，最后对替代实例和采样分配做优化。其中数据处理步骤恰好损失一个条件散度，且在自然指数族的 per-arm 计数和奖励和下该损失为零。论文在 7 个已发表数据源上用这个账本定位了标准算法与经典下界之间的差距，发现对模型间识别和 Wald 检验，最大项通常来自一致量化步骤。
Instance-dependent sequential limits as an exact information ledger
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.