Bandit Online Linear Optimization with Hints and Queries

We study variants of the online linear optimization (OLO) problem with bandit feedback, where the algorithm has access to external information about the unknown cost vector. Our motivation is the recent body of work on using such "hints" towards improving regret bounds for OLO problems in the full-information setting. Unlike in the full-information OLO setting, with bandit feedback, we first show that one cannot improve the standard regret bounds of Õ( √ T ) by using hints, even if they are always well-correlated with the cost vector. In contrast, if the algorithm is empowered to issue queries and if all the responses are correct, then we show O(log T ) regret is achievable. We then show how to make this result more robust-when some of the query responses can be adversarial-by using a little feedback on the quality of the responses.