Bandit Algorithms

6.4 Exercises 92 is √ 2 /m-subgaussian. You should only use the definitions and the interaction protocol, which states that (a)P ...

6.4 Exercises 93 Hint For (a) start fromRn≤m∆ +n∆exp(−m∆^2 /2) and assume that the second term here dominates the first term. Fi ...

6.4 Exercises 94 (a) Prove that ifεt=ε >0, then limn→∞ Rn n = ε k ∑k i=1 ∆i. (b)Let ∆min=min{∆i: ∆i> 0 }and letεt=min { 1 ...

6.4 Exercises 95 (e)Modify your choice ofm`and show that the regret of the resulting algorithm satisfies Rn≤C ∑ i:∆i> 0 ( ∆i+ ...

6.4 Exercises 96 0 100 200 300 400 50 60 70 m Expected regret Explore-Then-Commit Figure 6.2Expected regret for Explore-Then-Com ...

This material will be published by Cambridge University Press as Bandit Algorithms by Tor Lattimore and Csaba Szepesvari. This p ...

7.1 The optimism principle 98 happen too often because the additional data provided by playing a suboptimal arm means that the u ...

7.1 The optimism principle 99 of rewards experienced so far and theexploration bonus(also known as the confidence width). Beside ...

7.1 The optimism principle 100 already alluded to, one of the main difficulties is that the number of samples Ti(t−1) in the ind ...

7.1 The optimism principle 101 The theorem will be proven by boundingE[Ti(n)] for each suboptimal armi. We make use of a relativ ...

7.1 The optimism principle 102 The first of these sets is decomposed using the definition of UCB 1 (t) { μ 1 ≥min t∈[n] UCB 1 (t ...

7.1 The optimism principle 103 sinceTi(n)≤n. Then using the assumption thatδ= 1/n^2 and this choice ofui leads via (7.9) to E[Ti ...

7.2 Notes 104 As it happens, Theorem 7.2 is close to optimal. We will see in Chapter 15 that no algorithm can enjoy regret small ...

7.2 Notes 105 0 0. 2 0. 4 0. 6 0. 8 1 20 40 60 80 100 ∆ Expected regret ETC (m= 25) ETC (m= 50) ETC (m= 75) ETC (m= 100) ETC (op ...

7.3 Bibliographical remarks 106 optimism, pursued here and in other parts of this book, has so far escaped the attention of rese ...

7.4 Exercises 107 algorithms. LetX 1 ,X 2 ,...be a sequence of independent standard Gaussian random variables defined on probabi ...

7.4 Exercises 108 7.3(High probability bounds) Recall from Chapter 4 that the pseudo-regret is defined to be the random variable ...

7.4 Exercises 109 (d) Implement these algorithms and compare them empirically to UCB(δ). 1:Input kandδ 2:Choose each arm once 3: ...

7.4 Exercises 110 (d)Suppose thatν= (νi)ki=1is a bandit whereSupp(νi)⊂[0,b] and the variance of theith arm isσ^2 i. Design a pol ...

7.4 Exercises 111 This exercise shows that the subgaussian assumption can be relaxed to requiring only finite variance at the pr ...