@inproceedings{
russo2024online,
title={Online Learning with Sublinear Best-Action Queries},
author={Matteo Russo and Andrea Celli and Riccardo Colini Baldeschi and Federico Fusco and Daniel Haimovich and Dima Karamshuk and Stefano Leonardi and Niek Tax},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=9uKeqtIoGZ}
}
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 \emph{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 $\Theta(\min\{\sqrt T, \frac{T}{k}\})$. This finding highlights the significant multiplicative advantage in the regret rate achievable with even a modest (sublinear) number $k \in \Omega(\sqrt{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 $\Theta(\min\{\frac{T}{\sqrt k},\frac{T^2}{k^2}\})$, which improves over the standard $\Theta(\frac{T}{\sqrt k})$ regret rate for label efficient prediction for $k \in \Omega(T^{2/3})$.
Online Learning with Sublinear Best-Action Queries
Matteo Russo Andrea Celli Riccardo Colini Baldeschi Federico Fusco Daniel Haimovich Dima Karamshuk Stefano Leonardi Niek Tax