ON ERGODIC TWO-ARMED BANDITS

• 成果类型: Article
• 署名作者: Tarres, Pierre; Vandekerkhove, Pierre
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Gustave-Eiffel; Universite Paris-Est-Creteil-Val-de-Marne (UPEC)
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/10-AAP751
• 发表日期: 2012
• 页码: 457-476
• 关键词: algorithm; Automata

摘要

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, Pages and Tarres [Ann. Appl. Probab. 14 (2004) 1424-1454] by the law of iterated logarithm, thus generalizing it. More precisely, if (eta(l),i)(i is an element of N) is an element of {0, 1}(N), l is an element of {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, Pages and Tarres [Ann. Appl. Probab. 14 (2004) 1424-1454], replacing the i.i.d. assumption by the hypothesis that the empirical averages Sigma(n)(i=1) eta(A,i)/n and Sigma(n)(i=1) 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+epsilon), for some epsilon > 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 Larnberton, Pages and Tarres [Ann. Appl. Probab. 14 (2004) 1424-1454] in the i.i.d. case.