On ergodic two-armed bandits

Pierre Tarrès (1) , Pierre Vandekerkhove (2)

1 IMT - Institut de Mathématiques de Toulouse UMR5219
2 LAMA - Laboratoire d'Analyse et de Mathématiques Appliquées

A device has two arms with unknown deterministic payoffs and the aim is to asymptotically identify the best one without spending too much time on the other. The Narendra algorithm offers a stochastic procedure to this end. We show under weak ergodic assumptions on these deterministic payoffs that the procedure eventually chooses the best arm (i.e., with greatest Cesaro limit) with probability one for appropriate step sequences of the algorithm. In the case of i.i.d. payoffs, this implies a "quenched" version of the "annealed" result of Lamberton, Pag\'{e}s and Tarr\'{e}s [Ann. Appl. Probab. 14 (2004) 1424--1454] by the law of iterated logarithm, thus generalizing it.

Mots clés: two-armed bandit; Convergence; ergodicity; stochastic algorithms; two-armed bandit.

Domaines: Probabilités [math.PR]

Pierre Tarrès, Pierre Vandekerkhove. On ergodic two-armed bandits. The Annals of Applied Probability, 2012, 22 (2), pp.457-476. ⟨10.1214/10-AAP751⟩. ⟨hal-00796207⟩