Scheduling users in drive-thru Internet: a multi-armed bandit approach

We consider the problem of allocating a wireless channel to mobile users moving on a straight road. The objective is to maximize a given function of the total data transmitted. We develop a model within the multi-armed bandit framework and formulate an optimization problem under the constraint that at most one user can be served at a time. We solve the relaxed optimization problem, in which one user is served on the average, and show it to be indexable. A simple and easy-to-compute expression is given for the Whittle index. We then propose a heuristic policy for the original optimization problem using Whittle's index policy. The proposed heuristic is shown to perform well compared to some other heuristics in various settings including dynamic scenarios with arrivals of new users and the presence of heterogeneous users.