# Taking a hint: How to leverage loss predictors in contextual bandits?

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2020.

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

- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach](https://mlsanity.com/paper/2112.03432/) (2021)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Can Q-Learning be Improved with Advice?](https://mlsanity.com/paper/2110.13052/) (2021)
- [Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2211.06358/) (2022)
- [An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2412.08060/) (2024)
- [How Does Variance Shape the Regret in Contextual Bandits?](https://mlsanity.com/paper/2410.12713/) (2024)
- [Leveraging Initial Hints for Free in Stochastic Linear Bandits](https://mlsanity.com/paper/2203.04274/) (2022)
- [Improved Adaptive Algorithm for Scalable Active Learning with Weak Labeler](https://mlsanity.com/paper/2211.02233/) (2022)
- [Online Learning in Contextual Second-Price Pay-Per-Click Auctions](https://mlsanity.com/paper/2310.05047/) (2023)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)
- [Contextual Online Pricing with (Biased) Offline Data](https://mlsanity.com/paper/2507.02762/) (2025)
- [Corruption Robust Active Learning](https://mlsanity.com/paper/2106.11220/) (2021)
- [Catoni Contextual Bandits are Robust to Heavy-tailed Rewards](https://mlsanity.com/paper/2502.02486/) (2025)
- [A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity](https://mlsanity.com/paper/2307.15154/) (2023)
- [Efficiently Solving Discounted MDPs with Predictions on Transition Matrices](https://mlsanity.com/paper/2502.15345/) (2025)
- [Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2511.02123/) (2025)
- [Online Resource Allocation: Bandits feedback and Advice on Time-varying Demands](https://mlsanity.com/paper/2302.04182/) (2023)
- [Bandit Convex Optimization with Gradient Prediction Adaptivity](https://mlsanity.com/paper/2605.22191/) (2026)
- [Offline-to-Online Learning in Linear Bandits](https://mlsanity.com/paper/2606.04305/) (2026)

## Abstract (arXiv)

We initiate the study of learning in contextual bandits with the help of loss predictors. The main question we address is whether one can improve over the minimax regret O(√T) for learning over T rounds, when the total error of the predictor E ≤ T is relatively small. We provide a complete answer to this question, including upper and lower bounds for various settings: adversarial versus stochastic environments, known versus unknown E, and single versus multiple predictors. We show several surprising results, such as 1) the optimal regret is O(min√T, √ET^frac14) when E is known, a sharp contrast to the standard and better bound O(√E) for non-contextual problems (such as multi-armed bandits); 2) the same bound cannot be achieved if E is unknown, but as a remedy, O(√ET^frac13) is achievable; 3) with M predictors, a linear dependence on M is necessary, even if logarithmic dependence is possible for non-contextual problems. We also develop several novel algorithmic techniques to achieve matching upper bounds, including 1) a key action remapping technique for optimal regret with known E, 2) implementing Catoni's robust mean estimator efficiently via an ERM oracle leading to an efficient algorithm in the stochastic setting with optimal regret, 3) constructing an underestimator for E via estimating the histogram with bins of exponentially increasing size for the stochastic setting with unknown E, and 4) a self-referential scheme for learning with multiple predictors, all of which might be of independent interest.