BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Approximations of the Restless Bandit Problem - Azadeh Khaleghi (L
 ancaster)
DTSTART:20180223T160000Z
DTEND:20180223T170000Z
UID:TALK98686@talks.cam.ac.uk
CONTACT:Quentin Berthet
DESCRIPTION:\nThe multi-armed restless bandit problem is studied in the ca
 se where the pay-off distributions are jointly stationary ϕ-mixing. This 
 version of the problem provides a more realistic model for most real-world
  applications\, but cannot be optimally solved in practice. Our objective 
 is to characterize a sub-class of the problem where good approximate solut
 ions can be found using tractable approaches. Specifically\, it is shown t
 hat under some conditions on the ϕ-mixing coefficients\, a modified versi
 on of UCB can prove effective. The main challenge is that\, unlike in the 
 i.i.d. setting\, the distributions of the sampled pay-offs may not have th
 e same characteristics as those of the original bandit arms. In particular
 \, ϕ-mixing property does not necessarily carry over. This is overcome by
  carefully controlling the effect of a sampling policy on the pay-off dist
 ributions. Some of the proof techniques developed in this paper can be mor
 e generally used in the context of online sampling under dependence. Propo
 sed algorithms are accompanied by corresponding regret analysis.
LOCATION:MR12
END:VEVENT
END:VCALENDAR