# The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 48 references that are in the map.
- First posted on arXiv 1 Oct 2025.

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

- [Reinforcement learning](https://mlsanity.com/paper/2405.10369/) (2024)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (2016)
- [Selective Classification via One-Sided Prediction](https://mlsanity.com/paper/2010.07853/) (2020)
- [Power Constrained Bandits](https://mlsanity.com/paper/2004.06230/) (2020)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Safe Linear Bandits over Unknown Polytopes](https://mlsanity.com/paper/2209.13694/) (2022)
- [Scalable Neural Contextual Bandit for Recommender Systems](https://mlsanity.com/paper/2306.14834/) (2023)
- [Selective Sampling and Imitation Learning via Online Regression](https://mlsanity.com/paper/2307.04998/) (2023)
- [Towards Semi-supervised Learning with Non-random Missing Labels](https://mlsanity.com/paper/2308.08872/) (2023)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Online Selective Classification with Limited Feedback](https://mlsanity.com/paper/2110.14243/) (2021)
- [Probably Approximately Correct Labels](https://mlsanity.com/paper/2506.10908/) (2025)
- [Dynamic Ad Allocation: Bandits with Budgets](https://mlsanity.com/paper/1306.0155/) (2013)
- [Online Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/2405.12958/) (2024)

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