# Logarithmic Regret from Sublinear Hints

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 9 Nov 2021.

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

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Online Algorithms for Weighted Paging with Predictions](https://mlsanity.com/paper/2006.09509/) (2020)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Improved Path-length Regret Bounds for Bandits](https://mlsanity.com/paper/1901.10604/) (2019)
- [Adaptive scale-invariant online algorithms for learning linear models](https://mlsanity.com/paper/1902.07528/) (2019)
- [Fast Rates for Online Prediction with Abstention](https://mlsanity.com/paper/2001.10623/) (2020)
- [Online Linear Optimization with Many Hints](https://mlsanity.com/paper/2010.03082/) (2020)
- [Semi-Online Bipartite Matching](https://mlsanity.com/paper/1812.00134/) (2018)

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

- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Online Learning and Bandits with Queried Hints](https://mlsanity.com/paper/2211.02703/) (2022)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Online Learning with Sublinear Best-Action Queries](https://mlsanity.com/paper/2407.16355/) (2024)
- [Multi-Armed Bandits With Best-Action Queries](https://mlsanity.com/paper/2605.08287/) (2026)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)
- [The Value of Information in Resource-Constrained Pricing](https://mlsanity.com/paper/2603.24974/) (2026)
- [Online Convex Optimization with Sublinear Noisy Probes](https://mlsanity.com/paper/2606.14640/) (2026)
- [Augmented Hypothesis Testing with Persona-Based LLM Simulations](https://mlsanity.com/paper/2609.24629/) (2026)

## Abstract (arXiv)

We consider the online linear optimization problem, where at every step the algorithm plays a point xt in the unit ball, and suffers loss langle ct, xtrangle for some cost vector ct that is then revealed to the algorithm. Recent work showed that if an algorithm receives a hint ht that has non-trivial correlation with ct before it plays xt, then it can achieve a regret guarantee of O(log T), improving on the bound of Theta(√T) in the standard setting. In this work, we study the question of whether an algorithm really requires a hint at every time step. Somewhat surprisingly, we show that an algorithm can obtain O(log T) regret with just O(√T) hints under a natural query model; in contrast, we also show that o(√T) hints cannot guarantee better than Omega(√T) regret. We give two applications of our result, to the well-studied setting of optimistic regret bounds and to the problem of online learning with abstention.