How to play a multi-armed bandit
A classic problem that I discovered in chapter 2 of Sutton and Barto [0]. There, the authors discuss various strategies before finally mentioning the technique of 'Gittins indices' for computing the optimal solution. They don't mention the technique again, presumably because it doesn't generalize to more general reinforcement learning problems. Here I compare the optimal solution to another strategy mentioned in the chapter: the -greedy strategy.
Date: 2017-04-06
The setup

Suppose that you have at hand a bank of ten one-arm bandits, each with an unknown mean payout. At each timestep, you are offered the opportunity to pull the arm of one of the bandits, and you receive a payout. How should you choose which are to pull at each timestep?
That's the classical formulation of the problem, although it might be more fitting instead to think of having an array of projects that you can invest time in (with an unknown) reward, rather than to consider bandits, which have negative means.
Here we'll assume that, for each arm, a value has been drawn from a distribution. The reward is the arm value plus noise. We maximize
for some parameter between 0 and 1, where denotes the reward on the th timestep.
Stop for a moment and think of strategy you might use.
References
-
[0] Reinforcement Learning: An Introduction by Andrew Barto and Richard S. Sutton 1998
-
[1] Multi-Armed Bandit Allocation Indices by John Gittins, Kevin Glazebrook and Richard Weber 2011