Bandit Algorithms

29.4 Contextual linear bandits 332 The best way to think about the standard adversarial linear model is that it generalizes the ...

29.5 Notes 333 overcome this annoyance is to apply the adversarial analysis on the event that |Yt|≤Cfor some constantC >0 tha ...

29.6 Bibliographic remarks 334 29.6 Bibliographic remarks Linear bandits on the sphere with parameter noise have been studied by ...

29.7 Exercises 335 where`(At) =〈At,θ〉+ε(At) andε= supa∈Aε(a) and|Yt|≤1 almost surely. (a)Suppose thatA=Bd 2. Show that the expec ...

Part VII Other Topics ...

337 In the penultimate part we collect a few topics to which we could not dedicate a whole part. When deciding what to include w ...

338 Convex bandits LetA⊂Rdbe a convex set. The convex bandit problem comes in both stochastic and adversarial varieties. In both ...

339 [Joulani et al., 2013, Desautels et al., 2014, Cesa-Bianchi et al., 2016, Vernade et al., 2017, 2018, Pike-Burke et al., 201 ...

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

30.1 Applications 341 Budapest Frankfurt Beijing Abu Dhabi Singapore Sydney 1 10 12 11 13 12 10 8 13 7 Figure 30.1Shortest-path ...

30.2 Bandit feedback 342 This scenario can arise in practice when a company is making multiple independent interventions, but th ...

30.3 Semibandit feedback 343 wherePti=E[Ati|Ft− 1 ] withFt=σ(A 1 ,...,At). An easy calculation shows thatE[Yˆti|Ft− 1 ] =yti. 1: ...

30.4 Follow the perturbed leader 344 where the inequality follows from the fact thatexp(−x)≤ 1 −x+x^2 /2 for all x≥0. Taking the ...

30.4 Follow the perturbed leader 345 admits an efficient solution. This feels like the minimum one could get away with. If the s ...

30.4 Follow the perturbed leader 346 All this shows that FTPL can be interpreted as mirror descent with potentialF defined in te ...

30.4 Follow the perturbed leader 347 1:Input A,n,η,β,Q 2:Lˆ 0 = 0 ∈Rd 3:fort= 1,...,ndo 4: SampleZt∼Q 5: ComputeAt= argmaxa∈A〈a, ...

30.4 Follow the perturbed leader 348 calculate the Hessian we use a change of variable to avoid applying the gradient to the non ...

30.5 Notes 349 Putting together all the pieces into Eq. (30.5) leads to Rn≤ m(1 + log(d)) η + ednmη 2 + dnmη 2 ≤m √ 2(1 +e)nd(1 ...

30.6 Bibliographic remarks 350 z,ξ∈Rdandzj≥0. Then you can check thata(z+ξ)i≤a(z− 2 zjej+ξ)i and so ∇^2 F∗(ξ)ij= ∫ Rd a(z+ξ)isig ...

30.7 Exercises 351 30.7 Exercises 30.1(Mirror descent for combinatorial bandits) Prove Theorem 30.1. 30.2(Expected supremum norm ...