ON ERGODIC TWO-ARMED BANDITS

Journal article

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ès and Tarrès [Ann. Appl. Probab. 14 (2004) 1424- 1454] by the law of iterated logarithm, thus generalizing it. More precisely, if {equation presented}, are the deterministic reward sequences we would get if we played at time i, we obtain infallibility with the same assumption on nonincreasing step sequences on the payoffs as in Lamberton, Pagès and Tarrès [Ann. Appl. Probab. 14 (2004) 1424-1454], replacing the i.i.d. assumption by the hypothesis that the empirical averages {equation presented} converge, as n tends to infinity, respectively, to θA and θB, with rate at least {equation presented}, for some ε > 0. We also show a fallibility result, that is, convergence with positive probability to the choice of the wrong arm, which implies the corresponding result of Lamberton, Pagès and Tarrès [Ann. Appl. Probab. 14 (2004) 1424-1454] in the i.i.d. case. © Institute of Mathematical Statistics, 2012.

Authors: Tarres, P; Vandekerkhove, P

• Publication status: Published
• Journal: ANNALS OF APPLIED PROBABILITY
• Volume: 22
• Issue: 2
• Pages: 457-476
• Publication date: 2012-04-01
• DOI: 10.1214/10-AAP751
• ISSN: 1050-5164
• Language: English
• Keywords: two-armed bandit; stochastic algorithms; Convergence; ergodicity