  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.
