Timezone: »

 
Poster
Online Learning with Imperfect Hints
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit

Thu Jul 16 07:00 AM -- 07:45 AM & Thu Jul 16 06:00 PM -- 06:45 PM (PDT) @
in Poster Session 42 »
We consider a variant of the classical online linear optimization problem in which at every step, the online player receives a ``hint'' vector before choosing the action for that round. Rather surprisingly, it was shown that if the hint vector is guaranteed to have a positive correlation with the cost vector, then the online player can achieve a regret of $O(\log T)$, thus significantly improving over the $O(\sqrt{T})$ regret in the general setting. However, the result and analysis require the correlation property at \emph{all} time steps, thus raising the natural question: can we design online learning algorithms that are resilient to bad hints? In this paper we develop algorithms and nearly matching lower bounds for online learning with imperfect hints. Our algorithms are oblivious to the quality of the hints, and the regret bounds interpolate between the always-correlated hints case and the no-hints case. Our results also generalize, simplify, and improve upon previous results on optimistic regret bounds, which can be viewed as an additive version of hints.
Keywords: Online Learning / Bandits · Online Learning, Active Learning, and Bandits

Author Information

Aditya Bhaskara (University of Utah)
Ashok Cutkosky (Boston University)
Ravi Kumar (Google)
Manish Purohit (Google Research)

More from the Same Authors