Show description

K For each round t = 1, 2, . . , (1) the forecaster chooses ϕt ∈ P{1, . . , K} and pulls It at random according to ϕt ; (2) the environment draws the reward Yt for that action (also denoted by XIt ,TIt (t) with the notation introduced in the text); (3) the forecaster outputs a recommendation ψt ∈ P{1, . . , K}; (4) If the environment sends a stopping signal, then the game takes an end; otherwise, the next round starts. Fig. 1. The pure exploration problem for multi-armed bandits Pure Exploration in Multi-armed Bandits Problems 25 perform exploration during a random number of rounds T and aim at identifying an ε–best arm.

The distinguishing feature from the classical multi-armed bandit problem is that the exploration phase and the evaluation phase are separated. We now illustrate why this is a natural framework for numerous applications. Historically, the first occurrence of multi-armed bandit problems was given by medical trials. In the case of a severe disease, ill patients only are included in the trial and the cost of picking the wrong treatment is high (the associated reward would equal a large negative value).

By s11:t and s21:t denote the cumulative losses of these experts incurred at steps ≤ t, let vt be the corresponding volume, where t = 1, 2, . .. Define v0 = 1 and Mt = 4vt−1 / for all t ≥ 1. For t ≥ 1, define s1t = 0 and 2 st = Mt if P {It = 1} ≥ 12 , and define s1t = Mt and s2t = 0 otherwise. Let st be one-step loss of the master algorithm and s1:t be its cumulative loss at step t ≥ 1. We have E(s1:t ) ≥ E(st ) = s1t P {It = 1} + s2t P {It = 2} ≥ 1 Mt 2 for all t ≥ 1. Also, since vt = vt−1 + Mt = (1 + 4/ )vt−1 and min si1:t ≤ vt−1 , the i normalized expected regret of the master algorithm is bounded from below 1 2/ − 1 1 ≥ (1 − ).