When can the two-armed bandit algorithm be trusted?

• Daniel Lamberton
• Gilles Pagès
• Pierre Tarres

Code(s) de Classification MSC:

• 62L20 Stochastic Approximation
• 93C40 Adaptive control (code de Narendra lui-meme)
• 91E40 memory and learning
• 68T05 learning and adaptive systems
• 91B32 resource and cost allocation

Résumé:We investigate the asymptotic behaviour of the so-called two-armed bandit algorithm. It is an example of stochastic approximation procedure whose associated ODE has both a repulsive and an attractive equilibrium, at which the procedure is noiseless. We show that if the gain parameter is constant or goes to $0$ not too fast, the algorithm does fall in the noiseless repulsive equilibrium with positive probability whereas it always converges to its natural attractive target when the gain parameter goes to zero at some appropriate rates depending on the parameters of the model. We also elucidate the behaviour of the constant step algorithm when the step goes to $0$. Finally, we highlight the connection between the algorithm and the Polya urn. An application to asset allocation is briefly described.

Mots Clés: Two-armed bandit algorithm, Stochastic Approximation, learning automata, Polya urn, asset allocation.

Date: 2002-12-11

Prépublication numéro: LSP-2002-14