研究在线学习下如何高效选择测试序列，应对测试成本与信息缺失的权衡。
Online Learning of Optimal Sequential Testing Policies
- 将测试问题建模为带缺失数据的马尔可夫决策过程，设计在线学习策略。
- 证明最小最大后悔率至少为Ω(T^{2/3})，远高于标准MDP的Θ(√T)。
- 提出新算法在特定结构下可突破此瓶颈，适合高成本测试场景研究者。
本文研究一种在线学习问题，旨在为持续到来的受试者设计最优测试策略，每个受试者可通过从共同池中选取的一系列候选测试进行评估。该问题被称为在线测试问题（OTP）。尽管对每位受试者执行所有测试可获得更多信息，但在测试相关且成本高昂时，仅选择子集并基于部分信息做决策更为理想。若测试结果的联合分布已知，问题可转化为马尔可夫决策过程（MDP）并精确求解。然而实际中该分布未知，必须在受试者被测试的过程中在线学习。当受试者未被完全测试时，缺失数据会引入偏差，使问题比标准的周期性MDP更难。我们证明最小最大后悔率至少为Ω(T^{2/3})，相比之下周期性MDP为Θ(√T)，揭示了缺失数据带来的困难。这一更高下界随后由一个“探索后承诺”算法匹配，其累积后悔率为˜O(T^{2/3})，适用于离散和高斯分布。为突出缺失依赖奖励在OTP中的影响，我们研究了一个变体——在线成本敏感最大熵采样问题，其中奖励与缺失数据无关。该结构使得迭代剔除算法可实现˜O(√T)后悔率，打破了OTP的Ω(T^{2/3})下界。数值结果验证了理论分析。总体而言，本工作深化了对缺失数据下探索-利用权衡的理解，并指导高效序贯测试策略的设计。
原文摘要 · Abstract (English)
This paper studies an online learning problem that seeks optimal testing policies for a stream of subjects, each of whom can be evaluated through a sequence of candidate tests drawn from a common pool. We refer to this problem as the Online Testing Problem (OTP). Although conducting every candidate test for a subject provides more information, it is often preferable to select only a subset when tests are correlated and costly, and make decisions with partial information. If the joint distribution of test outcomes were known, the problem could be cast as a Markov Decision Process (MDP) and solved exactly. In practice, this distribution is unknown and must be learned online as subjects are tested. When a subject is not fully tested, the resulting missing data can bias estimates, making the problem fundamentally harder than standard episodic MDPs. We prove that the minimax regret must scale at least as $Ω(T^{\frac{2}{3}})$, in contrast to the $Θ(\sqrt{T})$ rate in episodic MDPs, revealing the difficulty introduced by missingness. This elevated lower bound is then matched by an Explore-Then-Commit algorithm whose cumulative regret is $\tilde{O}(T^{\frac{2}{3}})$ for both discrete and Gaussian distributions. To highlight the consequence of missingness-dependent rewards in OTP, we study a variant called the Online Cost-sensitive Maximum Entropy Sampling Problem, where rewards are independent of missing data. This structure enables an iterative-elimination algorithm that achieves $\tilde{O}(\sqrt{T})$ regret, breaking the $Ω(T^{\frac{2}{3}})$ lower bound for OTP. Numerical results confirm our theory in both settings. Overall, this work deepens the understanding of the exploration--exploitation trade-off under missing data and guides the design of efficient sequential testing policies.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。