On Adaptivity in Information-Constrained Online Learning

Siddharth Mitra, Aditya Gopalan

Introduction

In online learning, a learner repeatedly makes decisions and incurs losses. While standard adversarial models assume a worst-case chaotic environment—leading to regret bounds that scale with $\sqrt{T}$—real-world data often exhibits "smoothness" or slow temporal variation. Adapting to this smoothness is challenging when information is restricted, such as in label-efficient prediction (limited label budget), bandit feedback (only observing the chosen action's loss), or partial monitoring (indirect signals). This paper introduces new algorithms that bridge the gap between information constraints and adaptivity to predictable data.

Methodology: Hybrid Regularization and Optimism

The proposed approach extends Optimistic Online Mirror Descent (OMD). The "optimistic" component uses a predicted "message" of the next loss to inform current strategy. To handle the instability introduced by high learning rates in limited-information settings, the authors introduce several key innovations:

  1. Hybrid Regularization: Instead of using a single regularizer like negative entropy or log-barrier, this work employs a weighted sum of both. This hybrid structure provides the necessary curvature to maintain stability under aggressive learning rates while remaining efficient for large action spaces.
  2. Second-Order Corrections: The update rules incorporate a penalty term based on the deviation between actual losses and predicted messages.
  3. Reservoir Sampling: To generate unbiased estimates of past losses under label constraints, the learner employs reservoir sampling to maintain a representative "optimistic message."
Comparison of regularizer ratios across different online learning literature.

Key Results and Insights

The authors demonstrate that even with limited information, regret can be significantly reduced if the environment is slowly varying. The core insight is that the hybrid regularizer allows for high learning rates—essential for exploiting low variation—without sacrificing stability.

The paper establishes new, essentially optimal regret bounds for several fundamental problems, where $Q^*$ represents the variation of the best action and $n$ is the label budget:

  • Label Efficient Prediction: Achieves $\tilde{O}(\sqrt{Q^* T / n})$. In smooth environments where $Q^* \approx \sqrt{T}$ and labels are scarce ($n \approx \sqrt{T}$), this yields $\sqrt{T}$ regret, a significant improvement over the previous $T^{3/4}$ state-of-the-art.
  • Label Efficient Bandits: Establishes a bound of $\tilde{O}(\sqrt{Q^* TK / n})$.
  • Partial Monitoring: Provides the first variation-dependent bounds for "hard" games, achieving $O((QTK)^{1/3})$.
Summary of regret bounds and algorithm parameters for various information-constrained settings.

Discussion and Future Directions

While these results significantly advance adaptive online learning, several open questions remain. A small gap of $\sqrt{K}$ persists between upper and lower bounds in the bandit setting. Furthermore, while the current algorithms are "parameter-free" regarding total variation $Q$, achieving adaptivity to the specific variation of the best arm ($Q^*$) remains an open challenge due to its non-monotonic nature. Future work may also extend these techniques to more complex information structures like locally observable partial monitoring games.

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