# Adaptive Selective Sampling for Online Prediction with Experts

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 37 references that are in the map.
- First posted on arXiv 16 Feb 2023.

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

- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Active Learning and Best-Response Dynamics](https://mlsanity.com/paper/1406.6633/) (2014)
- [Disagreement-based Active Learning in Online Settings](https://mlsanity.com/paper/1904.09056/) (2019)
- [Active Learning with Expert Advice](https://mlsanity.com/paper/1309.6875/) (2013)

## Built on by (most cited first, 3 of 3)

- [Efficient and Optimal No-Regret Caching under Partial Observation](https://mlsanity.com/paper/2503.02758/) (2025)
- [Budgeted Online Active Learning with Expert Advice and Episodic Priors](https://mlsanity.com/paper/2506.03307/) (2025)
- [Multi-agent Adaptive Mechanism Design](https://mlsanity.com/paper/2512.21794/) (2025)

## Abstract (arXiv)

We consider online prediction of a binary sequence with expert advice. For this setting, we devise label-efficient forecasting algorithms, which use a selective sampling scheme that enables collecting much fewer labels than standard procedures, while still retaining optimal worst-case regret guarantees. These algorithms are based on exponentially weighted forecasters, suitable for settings with and without a perfect expert. For a scenario where one expert is strictly better than the others in expectation, we show that the label complexity of the label-efficient forecaster scales roughly as the square root of the number of rounds. Finally, we present numerical experiments empirically showing that the normalized regret of the label-efficient forecaster can asymptotically match known minimax rates for pool-based active learning, suggesting it can optimally adapt to benign settings.