On Adaptivity in Information-constrained Online Learning

Siddharth Mitra, Aditya Gopalan

Abstract: 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 hard class of games having minimax regret of order $T^{\frac{2}{3}}$. We provide a strategy with an $\mathcal{O}((Q^*T)^{\frac{1}{3}})$ bound for revealing action games, along with one with a $\mathcal{O}((QT)^{\frac{1}{3}})$ bound for the full class of hard partial monitoring games, both being strict improvements over current bounds.

Introduction

In the realm of online learning, algorithms typically make sequential decisions and receive feedback to refine their future choices. Traditionally, these environments are categorized as either stochastic (stationary) or adversarial (worst-case). Recent advancements have focused on "adaptive" algorithms that bridge this gap, performing optimally in worst-case scenarios while exploiting "easy" data—sequences where losses change slowly over time, characterized by low quadratic variation ($Q^*$).

However, a significant hurdle remains: most adaptive algorithms assume the learner receives feedback at every step. In many real-world applications, acquiring labels or feedback is expensive or strictly limited. This paper addresses the challenge of label efficient prediction: can an algorithm still exploit temporal regularity when it is starved for information?

The Challenge of Information Scarcity

In label efficient settings, a learner has a budget of $n$ queries over $T$ rounds. Standard adaptive techniques often fail here because information constraints change the underlying geometry of the learning problem.

When feedback is limited, algorithms must scale up the losses they do observe using inverse propensity weighting. This scaling typically forces standard regularizers, like negative entropy, to adopt extremely conservative learning rates to maintain stability. This conservatism, in turn, destroys the algorithm's ability to adapt to low variation. Conversely, while log-barrier regularizers allow for more aggressive learning rates, they often introduce a sub-optimal dependence on the number of actions ($K$).

Hybrid Regularization and Optimism

To overcome these limitations, the authors introduce a novel Hybrid Regularizer. By carefully weighting negative entropy and log-barrier components, the algorithm achieves the necessary stability for sparse feedback without sacrificing the ability to adapt to environmental smoothness.

Comparison of regularizer ratios used in this work versus prior literature.

Beyond regularization, the framework utilizes Optimistic Online Mirror Descent (OMD). Even with limited data, the algorithm constructs reliable "optimistic" hints about future losses using reservoir sampling. These hints, combined with budget-aware second-order corrections—penalties for actions that deviate significantly from expected losses—allow the learner to exploit temporal regularity almost as effectively as if it had full information.

Key Results and Regret Bounds

The paper provides rigorous mathematical guarantees across several problem settings, demonstrating that adaptivity is possible even in "hard" partial monitoring games. The core achievement is the derivation of regret bounds that scale with the actual variation of the data ($Q^*$) and the information budget ($n$).

Summary of algorithmic components and regret bounds for various information-constrained problems.

Key performance highlights include:

  • Label Efficient Prediction: Achieves a regret bound of $\tilde{\mathcal{O}}(\sqrt{Q^* T / n})$. In stable environments where $Q^*$ is small, this vastly outperforms traditional variation-independent algorithms that typically suffer $\mathcal{O}(T^{3/4})$ regret.
  • Label Efficient Bandits: Extends the framework to bandit feedback (where only the chosen action's loss is visible upon request), achieving $\tilde{\mathcal{O}}(\sqrt{Q^* T K / n})$ regret.
  • Partial Monitoring: Provides the first instance-dependent bounds for "hard" partial monitoring games, achieving $\mathcal{O}((QTK)^{1/3})$ regret.

Conclusion and Future Work

This work proves that information scarcity does not preclude environmental adaptivity. By redesigning the geometry of the learner's regularizer, it is possible to maintain stability while remaining sensitive to predictable patterns in data.

Despite these advances, several theoretical challenges remain. There is a persistent $\sqrt{K}$ gap between current upper bounds and theoretical lower bounds. Additionally, while the authors provide a parameter-free version for $Q$-dependent bounds, creating a truly universal, parameter-free algorithm for the tighter $Q^*$-dependent bound remains an open problem for the community.

Summary updated

Abstract

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 \textit{hard} class of games having minimax regret of order $T^{\frac{2}{3}}$. We provide a strategy with an $\mathcal{O}((Q^*T)^{\frac{1}{3}})$ bound for revealing action games, along with one with a $\mathcal{O}((QT)^{\frac{1}{3}})$ bound for the full class of hard partial monitoring games, both being strict improvements over current bounds.
BibTeX
@inproceedings{mitra2020adaptivity,
  author = {Siddharth Mitra and Aditya Gopalan},
  title = {{On Adaptivity in Information-constrained Online Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.5964},
}
Figure