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:
- 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.
- Second-Order Corrections: The update rules incorporate a penalty term based on the deviation between actual losses and predicted messages.
- Reservoir Sampling: To generate unbiased estimates of past losses under label constraints, the learner employs reservoir sampling to maintain a representative "optimistic message."
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})$.
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