Multiarmed Bandit Problems with Delayed Feedback

Understand

In this paper we initiate the study of optimization of bandit type problems in scenarios where the feedback of a play is not immediately known.

• This arises naturally in allocation problems which have been studied extensively in the literature, albeit in the absence of delays in the feedback.
• We study this problem in the Bayesian setting.
• In presence of delays, no solution with provable guarantees is known to exist with sub-exponential running time.