Bandit Algorithms

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

13.1 Main ideas underlying minimax lower bounds 173 13.1 Main ideas underlying minimax lower bounds LetX 1 ,...,Xnbe a sequence ...

13.1 Main ideas underlying minimax lower bounds 174 μ,μ′ ∈[0,1]k. In order to prove a lower bound it suffices to show that for e ...

13.2 Notes 175 expect thatE[T 1 (n)]≈E′[T 1 (n)]. IfE[T 1 (n)]< n/2, then by Eq. (13.2) we have Rn(π,ν)≥ n 2 √ k− 1 n = 1 2 √ ...

13.3 Bibliographic remarks 176 3 The regret on a class of banditsEis a multi-objective criterion. Some policies will be good for ...

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

14.1 Entropy and optimal coding 178 The easiest choice is to usedlog 2 (N)ebits no matter the value ofX. This simple code is som ...

14.2 The relative entropy 179 14.2 The relative entropy Suppose that Alice and Bob agree to use a code that is optimal whenXis s ...

14.2 The relative entropy 180 on this space. Then, D(P,Q) =    ∫ log ( dP dQ(ω) ) dP(ω), ifPQ; ∞, otherwise. This reduces to ...

14.2 The relative entropy 181 The proof may be found at the end of the chapter, but first some interpretation and a simple appli ...

14.3 Notes 182 This indeed is sufficient since ∫ p∧q= ∫ Ap∧q+ ∫ Acp∧q≤ ∫ Ap+ ∫ Acq= P(A) +Q(Ac). We start with an inequality att ...

14.3 Notes 183 as aσ-algebra except that being closed under countable unions is replaced by the condition that it be closed unde ...

14.3 Notes 184 0 1 − 0. 5 0 0. 5 1 x x/ 2 1 − √ 1 −x 1 − √ log(1/x)/ 2 Figure 14.1Tightening the inequality of Le Cam is large, ...

14.4 Bibliographic remarks 185 14.4 Bibliographic remarks There are many references for information theory. Most well known (and ...

14.5 Exercises 186 (b) Show that the Radon-NykodimdP/dμexists and thatdP/dμ(ω) =p(ω). 14.7(Relative entropy for Gaussian distrib ...

14.5 Exercises 187 τ∈[n] almost surely. Show that D(P|Fτ,Q|Fτ) =EP [τ ∑ t=1 D(Pt(·|X 1 ,...,Xt− 1 ),Qt(·|X 1 ,...,Xt− 1 )) ] . ...

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

15.2 Minimax lower bounds 189 as pνπ(a 1 ,x 1 ,...,an,xn) = ∏n t=1 πt(at|a 1 ,x 1 ,...,at− 1 ,xt− 1 )pat(xt). The density ofPν′i ...

15.2 Minimax lower bounds 190 Figure 15.1The idea of the minimax lower bound. Given a policy and one environment, the evil antag ...

15.3 Notes 191 Lemma 4.5 and a simple calculation leads to Rn(π,νμ)≥Pμ(T 1 (n)≤n/2) n∆ 2 and Rn(π,νμ′)>Pμ′(T 1 (n)> n/2) n ...