The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification
Not on the map. Why?
Abstract (arXiv)
We study sequential testing for a binary disease outcome when risk follows an unknown logistic model. At each round, the decision maker may either pay for a test revealing the true label or predict the outcome based on patient features and past data. The goal is to minimize costly tests while ensuring the misclassification rate stays below α with probability at least 1-δ. We propose a method that jointly estimates the logistic parameter θstar and the feature distribution, using a conservative threshold on the logistic score to decide when to test. We prove our procedure achieves the target error with high probability and requires only widetilde O(√T) more tests than an oracle with full knowledge. This is the first no-regret guarantee for error-constrained logistic testing, with direct applications to medical screening. Simulations corroborate our theoretical results, showing safe classification of patients and efficient estimation of θstar with few excess tests.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 18 of its 48 references that are in the map. First posted on arXiv 1 Oct 2025.
Builds on
18 of 48 references.
References · 18
- 2024Reinforcement learningcited by 236
- 2021Reinforcement learning based recommender systems: A surveycited by 187
- 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 169
- 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
- 2020Stochastic Bandits with Linear Constraintscited by 68
- 2016Conservative Contextual Linear Banditscited by 56
- 2020Selective Classification via One-Sided Predictioncited by 37
- 2020Power Constrained Banditscited by 30
- 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 27
- 2022Safe Linear Bandits over Unknown Polytopescited by 13
- 2023Scalable Neural Contextual Bandit for Recommender Systemscited by 12
- 2023Selective Sampling and Imitation Learning via Online Regressioncited by 12
6 more
- 2023Towards Semi-supervised Learning with Non-random Missing Labelscited by 12
- 2023Adversarial Resilience in Sequential Prediction via Abstentioncited by 11
- 2021Online Selective Classification with Limited Feedbackcited by 8
- 2013Dynamic Ad Allocation: Bandits with Budgetscited by 7
- 2025Probably Approximately Correct Labelscited by 7
- 2024Online Learning of Halfspaces with Massart Noisecited by 1
Built on by
Not cited yet.