Bandit Algorithms

212 Suppose you want to use a bandit algorithm to decide which ads to display on your website. Can you reasonably do this with o ...

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

18.1 Contextual bandits: one bandit per context 214 Adversary secretly chooses rewards (xt)nt=1withxt∈[0,1]k Adversary secretly ...

18.2 Bandits with expert advice 215 when all contexts are observed equally often, in which case we have Rn≤ 2 √ nk|C|log(k). (18 ...

18.2 Bandits with expert advice 216 Figure 18.2Prediction with expert advice. The experts, upon seeing a foot give expert advice ...

18.2 Bandits with expert advice 217 Adversary secretly chooses rewardsx∈[0,1]n×k Experts secretly choose predictionsE(1),...,E(n ...

18.3 Exp4 218 18.3 Exp4 Exp4 is not just an increased version number, but stands forExponential weighting forExploration andExpl ...

18.4 Regret analysis 219 expected regret of Exp4 defined in Algorithm 11 afternrounds. Then, Rn≤ √ 2 nklog(M). (18.7) After tran ...

18.5 Notes 220 Substituting into Eq. (18.11) leads to Rn≤ log(M) η + ηnK 2 = √ 2 nKlog(M). Let us see how this theorem can be ap ...

18.5 Notes 221 of the regret, but also increases the regret. This is similar to what we have observed in stochastic bandits. Tun ...

18.6 Bibliographic remarks 222 problem. The distribution is constrained so that the importance weights will not be too large, wh ...

18.7 Exercises 223 the degree of agreement amongst the experts. Neu [2015a] proves high probability bounds for Exp4-IX. You can ...

18.7 Exercises 224 18.3 In this exercise you will prove an analogue of Theorem 12.1 for Exp4-IX. In the contextual setting the r ...

18.7 Exercises 225 ξonCand the rewards are (Xt)nt=1where the conditional law ofXtgivenCt andAtisPCtAt. The mean reward when choo ...

18.7 Exercises 226 We did not talk about VC dimension in this book. An introduction is given by Shalev-Shwartz and Ben-David [20 ...

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

19.1 Stochastic contextual bandits 228 because it depends on the contextCt. The loss due to the lack of knowledge ofr makes the ...

19.2 Stochastic linear bandits 229 to assuming that the dimensionalitydis finite. In fact, one may push this to the extreme and ...

19.2 Stochastic linear bandits 230 (A 1 ,X 1 ,...,At− 1 ,Xt− 1 ) that contains the unknown parameter vectorθ∗with high probabili ...

19.3 Regret analysis 231 Soˆθtis an estimate ofθ∗, which makes it natural to chooseCtto be centered at θˆt− 1. For what follows ...