Bandit Algorithms

15.3 Notes 192 μto show that D(Pμ,Pμ+∆)≈ ∂ ∂∆ D(Pμ,Pμ+∆) ∣∣ ∣∣ ∆=0 ∆ + 1 2 ∂^2 ∂∆^2 D(Pμ,Pμ+∆) ∣∣ ∣∣ ∆=0 ∆^2 = ∂ ∂∆ ∫ Ω log ( dP ...

15.4 Bibliographic remarks 193 An estimator is a functionθˆ:Xn→Θ. Le Cam’s method is used for proving minimax lower bounds on th ...

15.5 Exercises 194 (a)Use Pinsker’s inequality (Eq. 14.11) and Lemma 15.1 and the result of Exercise 14.4 to show Ei[Ti(n)]≤E 0 ...

15.5 Exercises 195 whereC >0 is a universal constant. Prove that the dependence on the sum cannot be eliminated. Hint You wil ...

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

16.1 Asymptotic bounds 197 In finite-time the situation is a little messy, but if one pushes these ideas to the limit, then for ...

16.1 Asymptotic bounds 198 result will follow from Lemma 4.5 and by showing that for any suboptimal armi it holds that lim infn→ ...

16.2 Finite-time bounds 199 M P dinf(P,μ∗,M) {N(μ,σ^2 ) :μ∈R} N(μ,σ^2 ) (μ−μ ∗) 2 2 σ^2 {N(μ,σ^2 ) :μ∈R,σ^2 ∈(0,∞)} N(μ,σ^2 )^12 ...

16.3 Notes 200 Rn(π,ν′)≤Cnpfor allnandν′∈E(ν). Then for anyε∈(0,1], Rn(π,ν)≥^2 (1 +ε)^2 ∑ i:∆i> 0 ( (1−p) log(n) + log (ε∆i 8 ...

16.4 Bibliographic remarks 201 16.4 Bibliographic remarks Asymptotic optimality via a consistency assumption first appeared in t ...

16.5 Exercises 202 E=Mkandπbe a consistent policy forE. Prove that the asymptotic upper bound on the regret proven in Exercise 1 ...

16.5 Exercises 203 (e) Show thatα≥ n∆(ν) 2 8 Clog(n)and conclude that Rn(π,ν)≥^1 2∆(ν) log ( n∆(ν)^2 8 Clog(n) ) . (f) Generaliz ...

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

17.1 Stochastic bandits 205 On the other hand, if the high-probability bound only holds for a singleδas in (17.2), then it seems ...

17.1 Stochastic bandits 206 and Pinsker’s inequality (Theorem 14.2) and the divergence decomposition (Lemma 15.1) we have P ( R ...

17.2 Adversarial bandits 207 Now by assumption for anyν∈Ekwe have Rn(π,ν)≤ ∫∞ 0 P ( ̄ Rn(π,ν)≥x ) dx ≤B √ n(k−1) ∫∞ 0 exp ( −x^1 ...

17.2 Adversarial bandits 208 rewards to be bounded in [0,1]. The second difficulty is we now analyse the adversarial regret rath ...

17.3 Notes 209 straightforward, but for adversarial bandits there is an additional step. Notice that underQiit holds thatXti−XtA ...

17.5 Exercises 210 17.5 Exercises 17.1Prove each of the claims in Section 17.2. ...

Part V Contextual and Linear Bandits ...