Timezone: »

 
Oral
The Price of Bandit Information for Online Optimization
Varsha Dani · Thomas P Hayes · Sham M Kakade

Tue Dec 04 04:20 PM -- 04:40 PM (PST) @
in Session 3: Theory and Sequential Decision Making »
In the online linear optimization problem, a learner must choose, in each round, a decision from a set $D \subset \R^n$ in order to minimize an (unknown and changing) linear cost function. We present sharp rates of convergence (with respect to additive regret) for both the full information setting (where the cost function is revealed at the end of each round) and in the bandit setting (where only the scalar cost incurred is revealed). In particular, this paper is concerned with the \emph{price of bandit information} --- how much worse the regret is in the bandit case as compared to the full information case. For the full information case, the upper bound on the regret is $O^*(\sqrt{nT})$, where $n$ is the ambient dimension and $T$ is the time horizon. For the bandit case, we present an algorithm which achieves $O^*(n^{3/2}\sqrt{T})$ regret --- all previous (nontrivial) bounds here were $O(\textrm{poly}(n)T^{2/3})$ or worse. It is striking that the convergence rate for the bandit setting is only a factor of $n$ worse than in the full information case --- in stark contrast to the $K$-arm bandit setting, where the gap in the dependence on $K$ is exponential ($\sqrt{TK}$ vs. $\sqrt{T\log K}$). We also present lower bounds showing that this gap is at least $\sqrt{n}$, which we conjecture to be the correct order. The bandit algorithm we present can be implemented efficiently in special cases of particular interest, such as path planning and Markov Decision Problems.

Author Information

Varsha Dani (University of Chicago)
Thomas P Hayes (Toyota Technological Institute at Chicago)
Sham M Kakade (Harvard University & Amazon)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors