2021/11/09 by Aditya Bhaskara, Ashok Cutkosky, Bhaskara, Aditya +5 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2111.05257
openalex publication_date 2021/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the online linear optimization problem, where at every step the algorithm plays a point xt in the unit ball, and suffers loss ⟨ ct, xt⟩ 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 Θ(√(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 Ω(√(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.