Online Learning with Sublinear Best-Action Queries

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.