On ergodic two-armed bandits

Details On ergodic two-armed bandits On ergodic two-armed bandits

2009-05-04

arxiv.org/abs/0905.0463v2

Annals of Applied Probability Vol. 22, No. 2, 457-476 (2012)

Mathematics

Probability

Published in at http://dx.doi.org/10.1214/10-AAP751 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst

Scientific paper

10.1214/10-AAP751

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. More precisely, if $(\eta_{\ell,i})_{i\in \mathbb {N}}\in\{0,1\}^{\mathbb {N}}$, $\ell\in\{A,B\}$, 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\`{e}s and Tarr\`{e}s [Ann. Appl. Probab. 14 (2004) 1424--1454], replacing the i.i.d. assumption by the hypothesis that the empirical averages $\sum_{i=1}^n\eta_{A,i}/n$ and $\sum_{i=1}^n\eta_{B,i}/n$ converge, as $n$ tends to infinity, respectively, to $\theta_A$ and $\theta_B$, with rate at least $1/(\log n)^{1+\varepsilon}$, for some $\varepsilon >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\`{e}s and Tarr\`{e}s [Ann. Appl. Probab. 14 (2004) 1424--1454] in the i.i.d. case.

Affiliated with

Also associated with

No associations

Rating

On ergodic two-armed bandits does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On ergodic two-armed bandits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On ergodic two-armed bandits will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-200123