Online learning with queries

The online learning problem requires a player to iteratively choose an action in an unknown and changing environment. In the standard setting of this problem, the player has to choose an action in each round before knowing anything about the corresponding loss. However, there are situations in which it seems possible for the player to spend efforts or resources to collect some prior information before her actions. This motivates us to study a variant of the online learning problem, in which the player is allowed to query B bits from the loss vector in each round before choosing her action. Suppose each loss value is represented by K bits and distinct loss values differ by at least some amount Δ, and suppose there are N actions to choose and T rounds to play. We provide an algorithm for this problem which achieves a regret of the following form. Before B approaching B 1 = NK /2, the regret stays at O (√ T ln N ), and after B exceeding B 1 but before approaching B 2 = NK /2 + 3 K /2-1, the regret drops slightly to O (√( T ln N )/ N ), while after B exceeding B 2 , the regret takes a dramatic drop to ( N ln N )/Δ. Our algorithm is in fact close to optimal as we also provide regret lower bounds which almost match the regret upper bounds achieved by our algorithm.