Bandit Algorithms

11.5 Notes 152 11.5 Notes 1 Exp3 is nearly optimal in the sense that its expected regret cannot be improved significantly in the ...

11.5 Notes 153 7 Building on the previous note, suppose the reward in roundtis Xt = ft(A 1 ,...,At) andf 1 ,...,fnare a sequence ...

11.6 Bibliographic remarks 154 and Lugosi, 2017, Zimmert and Seldin, 2018]. There are some complications, however, depending on ...

11.7 Exercises 155 On most computersrand()will return a pseudo-random number and since there are only finitely many floating poi ...

11.7 Exercises 156 and define 2-armed adversarial bandit in terms of its losses by yt 1 = { 0 ift≤n/ 2 1 otherwise and yt 2 = { ...

11.7 Exercises 157 0 0. 1 100 150 200 250 η Expected regret Exp3 Figure 11.3Expected regret for Exp3 for different learning rate ...

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

12.1 The Exp3-IX algorithm 159 Eq. (12.1) holds no matter how the loss estimators are chosen provided they satisfyYˆti≥0 for all ...

12.2 Regret analysis 160 1:Input: n,k,η,γ 2:SetLˆ 0 i= 0 for alli 3:fort= 1,...,ndo 4: Calculate the sampling distributionPt: Pt ...

12.2 Regret analysis 161 statement of which requires us to introduce the notion of adapted and predictable sequences of random v ...

12.2 Regret analysis 162 Proof LetAti=I{At=i}as before. WritingYt= ∑ jAtjytj, we calculate Yt− ∑k j=1 PtjYˆtj= ∑k j=1 ( 1 − Ptj ...

12.3 Notes 163 Proof of Lemma 12.2 Fixt∈[n] and letEt[·]=E[·|Ft] denote the conditional expectation with respect toFt. By Lemma ...

12.4 Bibliographic remarks 164 In the worst caseLinis linear innand the usual bound is recovered. But if the optimal arm enjoys ...

12.5 Exercises 165 [Uchibe and Doya, 2004, Wawrzynski and Pacut, 2007, Ionides, 2008, Bottou et al., 2013]. All of these papers ...

12.5 Exercises 166 (f)Combining the previous steps, show that there exists a universal constant C >0 such that for anyδ∈(0,1) ...

12.5 Exercises 167 (c) Show that with probability at least 1−δ, (B)≤ 2 ∑n t=1 ∑k a=1 Ptaβta+ log(1/δ) η . (d) Show that with pro ...

12.5 Exercises 168 (b)What happens asηgrows? Write a bound on the expected regret of Exp3-IX in terms ofηandkandn. ...

Part IV Lower Bounds for Bandits with Finitely Many Arms ...

170 Until now we have indulged ourselves by presenting algorithms and upper bounds on their regret. As satisfying as this is, th ...

171 familiar with information theory could skim this chapter. The final three chapters are devoted to applying information theor ...