# Online Learning of Optimal Sequential Testing Policies

arXiv: https://arxiv.org/abs/2509.03707 · HTML: https://mlsanity.com/paper/2509.03707/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 3 Sep 2025.

## Builds on (most cited first, 8 of 8)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Sequential estimation of quantiles with applications to A/B-testing and best-arm identification](https://mlsanity.com/paper/1906.09712/) (2019)
- [Deep Reinforcement Learning for Cost-Effective Medical Diagnosis](https://mlsanity.com/paper/2302.10261/) (2023)
- [Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations](https://mlsanity.com/paper/2212.14411/) (2022)
- [Greedy Approximation Algorithms for Active Sequential Hypothesis Testing](https://mlsanity.com/paper/2103.04250/) (2021)

## Abstract (arXiv)

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 Omega(T^frac23), in contrast to the Theta(√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 tildeO(T^frac23) 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 tildeO(√T) regret, breaking the Omega(T^frac23) 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.