# On Adaptivity in Information-constrained Online Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2019.

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

- [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 study how to adapt to smoothly-varying ('easy') environments in well-known online learning problems where acquiring information is expensive. For the problem of label efficient prediction, which is a budgeted version of prediction with expert advice, we present an online algorithm whose regret depends optimally on the number of labels allowed and Q^* (the quadratic variation of the losses of the best action in hindsight), along with a parameter-free counterpart whose regret depends optimally on Q (the quadratic variation of the losses of all the actions). These quantities can be significantly smaller than T (the total time horizon), yielding an improvement over existing, variation-independent results for the problem. We then extend our analysis to handle label efficient prediction with bandit feedback, i.e., label efficient bandits. Our work builds upon the framework of optimistic online mirror descent, and leverages second order corrections along with a carefully designed hybrid regularizer that encodes the constrained information structure of the problem. We then consider revealing action-partial monitoring games -- a version of label efficient prediction with additive information costs, which in general are known to lie in the textithard class of games having minimax regret of order T^frac23. We provide a strategy with an O((Q^*T)^frac13) bound for revealing action games, along with one with a O((QT)^frac13) bound for the full class of hard partial monitoring games, both being strict improvements over current bounds.