Timezone: »

 
Poster
Linear bandits with Stochastic Delayed Feedback
Claire Vernade · Alexandra Carpentier · Tor Lattimore · Giovanni Zappella · Beyza Ermis · Michael Brueckner

Thu Jul 16 02:00 PM -- 02:45 PM & Fri Jul 17 03:00 AM -- 03:45 AM (PDT) @
in Poster Session 47 »

Stochastic linear bandits are a natural and well-studied model for structured exploration/exploitation problems and are widely used in applications such as on-line marketing and recommendation. One of the main challenges faced by practitioners hoping to apply existing algorithms is that usually the feedback is randomly delayed and delays are only partially observable. For example, while a purchase is usually observable some time after the display, the decision of not buying is never explicitly sent to the system. In other words, the learner only observes delayed positive events. We formalize this problem as a novel stochastic delayed linear bandit and propose OTFLinUCB and OTFLinTS, two computationally efficient algorithms able to integrate new information as it becomes available and to deal with the permanently censored feedback. We prove optimal O(d\sqrt{T}) bounds on the regret of the first algorithm and study the dependency on delay-dependent parameters. Our model, assumptions and results are validated by experiments on simulated and real data.

Keywords: Online Learning / Bandits · Online Learning, Active Learning, and Bandits

Author Information

Claire Vernade (DeepMind)
Alexandra Carpentier (Otto-von-Guericke University)
Tor Lattimore (DeepMind)
Giovanni Zappella (Amazon)
Beyza Ermis (Amazon Research)
Michael Brueckner (Amazon Research Berlin)

More from the Same Authors