# Online Learning with Sublinear Best-Action Queries

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 23 Jul 2024.

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

- [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)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (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)
- [Online Learning with Abstention](https://mlsanity.com/paper/1703.03478/) (2017)
- [Fast Rates for Online Prediction with Abstention](https://mlsanity.com/paper/2001.10623/) (2020)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Logarithmic Regret from Sublinear Hints](https://mlsanity.com/paper/2111.05257/) (2021)
- [The Extended Littlestone's Dimension for Learning with Mistakes and Abstentions](https://mlsanity.com/paper/1604.06162/) (2016)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Online Selective Classification with Limited Feedback](https://mlsanity.com/paper/2110.14243/) (2021)
- [Online Learning and Bandits with Queried Hints](https://mlsanity.com/paper/2211.02703/) (2022)
- [Online Graph Coloring with Predictions](https://mlsanity.com/paper/2312.00601/) (2023)
- [Understanding the Role of Feedback in Online Learning with Switching Costs](https://mlsanity.com/paper/2306.09588/) (2023)

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

- [Multi-Armed Bandits With Best-Action Queries](https://mlsanity.com/paper/2605.08287/) (2026)
- [Online Convex Optimization with Sublinear Noisy Probes](https://mlsanity.com/paper/2606.14640/) (2026)

## Abstract (arXiv)

In online learning, a decision maker repeatedly selects one of a set of actions, with the goal of minimizing the overall loss incurred. Following the recent line of research on algorithms endowed with additional predictive features, we revisit this problem by allowing the decision maker to acquire additional information on the actions to be selected. In particular, we study the power of best-action queries, which reveal beforehand the identity of the best action at a given time step. In practice, predictive features may be expensive, so we allow the decision maker to issue at most k such queries. We establish tight bounds on the performance any algorithm can achieve when given access to k best-action queries for different types of feedback models. In particular, we prove that in the full feedback model, k queries are enough to achieve an optimal regret of Thetaleft(minleft√ T, frac Tkrightright). This finding highlights the significant multiplicative advantage in the regret rate achievable with even a modest (sublinear) number k ∈ Omega(√T) of queries. Additionally, we study the challenging setting in which the only available feedback is obtained during the time steps corresponding to the k best-action queries. There, we provide a tight regret rate of Thetaleft(minleftfracT√ k,fracT2k2rightright), which improves over the standard Thetaleft(fracT√ kright) regret rate for label efficient prediction for k ∈ Omega(T2/3).