Delay as Payoff in MAB

In this paper, we investigate a variant of the classical stochastic Multi-armed Bandit (MAB) problem, where the payoff received by an agent (either cost or reward) is both delayed, and directly corresponds to the magnitude of the delay. This setting models faithfully many real world scenarios such as the time it takes for a data packet to traverse a network given a choice of route (where delay serves as the agent's cost); or a user's time spent on a web page given a choice of content (where delay serves as the agent's reward). Our main contributions are tight upper and lower bounds for both the cost and reward settings. For the case that delays serve as costs, which we are the first to consider, we prove optimal regret that scales as sumi:Deltai > 0fraclog TDeltai + d^*, where T is the maximal number of steps, Deltai are the sub-optimality gaps and d^* is the minimal expected delay amongst arms. For the case that delays serves as rewards, we show optimal regret of sumi:Deltai > 0fraclog TDeltai + bard, where bar d is the second maximal expected delay. These improve over the regret in the general delay-dependent payoff setting, which scales as sumi:Deltai > 0fraclog TDeltai + D, where D is the maximum possible delay. Our regret bounds highlight the difference between the cost and reward scenarios, showing that the improvement in the cost scenario is more significant than for the reward. Finally, we accompany our theoretical results with an empirical evaluation.