Overblog Follow this blog
Edit post Administration Create my blog
June 3 2011 6 03 /06 /June /2011 13:22

This page is dedicated to start discussions about the article "Adaptive bandits: Towards the best history-dependent strategy". Feel free to post any comment, sugggestion, question, correction, extension... I will enjoy discussing this with you.

  • Abstract:

"We consider multi-armed bandit games with possibly adaptive opponents.
We introduce models  \Theta of constraints based on equivalence classes on the common history (information shared by the player and the opponent) which define two learning scenarios:
(1) The opponent is constrained, i.e.~he provides rewards that are stochastic functions of equivalence classes defined by some model  \theta^*\in\Theta . The regret is measured with respect to (w.r.t.) the best history-dependent strategy.
(2) The opponent is arbitrary and we measure the regret w.r.t.~the best strategy among all mappings from classes to actions (i.e.~the best history-class-based strategy) for the best model in  \Theta .
This allows to model opponents (case 1) or strategies (case 2) which handles finite memory, periodicity, standard stochastic bandits and other situations.

When  \Theta=\{\theta\} , i.e.~only one model is considered, we derive \textit{tractable} algorithms achieving a \textit{tight} regret (at time T) bounded by  \tilde O(\sqrt{TAC}) , where  C is the number of classes of  \theta . Now, when many models are available, all known algorithms achieving a nice regret  O(\sqrt{T}) are unfortunately \textit{not tractable} and scale poorly with the number of models  |\Theta| . Our contribution here is to provide {\em tractable} algorithms with regret bounded by  T^{2/3}C^{1/3}\log(|\Theta|)^{1/2} ."

  • Discussion:

We do not know whether in the case of a pool of models \Phi_\Theta, there exist tractable algorithms with \Phi_\Theta-regret better that T^{2/3} with log dependency w.r.t. |\Theta|.

  • Future work:

Extend this setting to Reinforcement Learning.

Share this post

Repost 0
Published by Odalric-Ambrym Maillard - in Discussing articles
write a comment





Senior Researcher



The Technion
Faculty of Electrical Engineering,
Fishbach Bldg, Rm. 462
32000 Haifa, ISRAEL
Tel: +972 (0)48293638