实例依赖的序贯极限作为精确信息账本
Instance-dependent sequential limits as an exact information ledger
Akshay Balsubramani
中文摘要
针对 bandit 遗憾、序贯检验、最佳臂识别与马尔可夫决策过程的实例依赖极限，通过一条统一链条给出证明：从散度分解出发，经数据处理得到统计量，再经检验步骤将类保证转化为对历史的要求，最后对备选方案与分配进行优化。其中仅第一步是恒等式。本工作将该链条写成精确账本。由链式法则，数据处理恰好损失一个条件散度，该散度在自然指数族中按臂计数与奖励和消失。单参数族的鞅恒等式将分解扩展到两个实例之间的任意倾斜。经典极限通过带命名缺陷的松弛得到。除渐近步骤外，所有缺陷均可由算法自身运行计算；均匀量化缺陷仅当类保证为数值时可计算。在从电影评分到发动机更换的七个已发表来源上，该账本定位了标准算法与经典极限之间的差异。对于已训练模型间的识别与 Wald 检验，最大项通常是均匀量化项。
关键要点
- 01问题：bandit、序贯检验、最佳臂识别与 MDP 的实例依赖极限缺乏统一且精确的推导框架。
- 02方法：将散度分解→数据处理→统计量→检验→优化的链条写成精确账本，仅首步为恒等式。
- 03结果：数据处理损失恰为条件散度，在自然指数族中按臂计数与奖励和消失；鞅恒等式覆盖任意倾斜。
- 04结果：七个已发表来源上账本定位了标准算法与经典极限的差异，识别与 Wald 检验中最大项常为均匀量化项。
- 05局限：除渐近步骤外缺陷可由算法自身运行计算，均匀量化缺陷仅当类保证为数值时可计算。
解读
尚无解读。
原始英文摘要
arXiv:2610.42133v1 Announce Type: new 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.