Timezone: »

 
Poster
Bandit Online Linear Optimization with Hints and Queries
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit

Tue Jul 25 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #428
in Poster Session 2 »
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 $\tilde{O}(\sqrt{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.
[ PDF]  [ Poster] 

Author Information

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

More from the Same Authors