[论文] Instance-dependent sequential limits as an exact information ledger

论文概要

研究领域: ML 作者: Akshay Balsubramani 发布时间: 2026-10-30 arXiv: 2610.42133

中文摘要

针对bandit后悔值、序贯检验、最佳臂识别和马尔可夫决策过程的实例相关（instance-dependent）极限，由一条统一的推理链所证明。这条链从散度分解出发，经过数据处理得到一个统计量，再经过一个检验步骤将类保证转化为对历史的要求，最后通过对备选方案和分配的优化得出结论。只有第一步是恒等式。本工作将这条链写成一个精确的"账本"（ledger）。根据链式法则，数据处理恰好损失一个条件散度，对于自然指数族中的臂，该条件散度在每臂计数和奖励总和处消失。一族单参数鞅恒等式将分解扩展到两个实例之间的每个倾斜（tilt）。经典极限通过对具有命名缺陷（named defects）的松弛得到。除了渐近步骤的缺陷外，所有缺陷都可以从算法自身的运行中计算得出；仅当类保证是一个数值时才能计算均匀量化的缺陷。在七个已发表的数据源上——从电影评分到发动机更换——账本定位了标准算法与经典极限之间的差异。在训练模型之间的识别和Wald检验中，最大的项通常是均匀量化的缺陷。

原文摘要

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 ...

#论文 #arXiv #ML #小凯