# Online Learning and Bandits with Queried Hints

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 67 references that are in the map.
- First posted on arXiv 4 Nov 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [Logarithmic Regret from Sublinear Hints](https://mlsanity.com/paper/2111.05257/) (2021)
- [Online Learning via the Differential Privacy Lens](https://mlsanity.com/paper/1711.10019/) (2017)
- [Pandora's Problem with Nonobligatory Inspection](https://mlsanity.com/paper/1905.01428/) (2019)
- [ktexttt-experts -- Online Policies and Fundamental Limits](https://mlsanity.com/paper/2110.07881/) (2021)
- [Multiarmed Bandits With Limited Expert Advice](https://mlsanity.com/paper/1306.4653/) (2013)
- [Observe Before Play: Multi-armed Bandit with Pre-observations](https://mlsanity.com/paper/1911.09458/) (2019)

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

- [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)
- [Adaptive Regret for Bandits Made Possible: Two Queries Suffice](https://mlsanity.com/paper/2401.09278/) (2024)
- [Fusing Reward and Dueling Feedback in Stochastic Bandits](https://mlsanity.com/paper/2504.15812/) (2025)
- [Online Convex Optimization with Sublinear Noisy Probes](https://mlsanity.com/paper/2606.14640/) (2026)
- [Bandits with Probing: Optimal Regret and the Limits of Winner Feedback](https://mlsanity.com/paper/2609.15248/) (2026)

## Abstract (arXiv)

We consider the classic online learning and stochastic multi-armed bandit (MAB) problems, when at each step, the online policy can probe and find out which of a small number (k) of choices has better reward (or loss) before making its choice. In this model, we derive algorithms whose regret bounds have exponentially better dependence on the time horizon compared to the classic regret bounds. In particular, we show that probing with k=2 suffices to achieve time-independent regret bounds for online linear and convex optimization. The same number of probes improve the regret bound of stochastic MAB with independent arms from O(√nT) to O(n2 log T), where n is the number of arms and T is the horizon length. For stochastic MAB, we also consider a stronger model where a probe reveals the reward values of the probed arms, and show that in this case, k=3 probes suffice to achieve parameter-independent constant regret, O(n2). Such regret bounds cannot be achieved even with full feedback after the play, showcasing the power of limited ``advice'' via probing before making the play. We also present extensions to the setting where the hints can be imperfect, and to the case of stochastic MAB where the rewards of the arms can be correlated.