BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Computational Challenges in Sleeping Combinatorial Experts - Varun
  Kanade (Oxford)
DTSTART:20160506T150000Z
DTEND:20160506T160000Z
UID:TALK65901@talks.cam.ac.uk
CONTACT:Quentin Berthet
DESCRIPTION:In this talk\, I'll discuss sleeping variants of two online de
 cision making\nproblems. The first\, called the sleeping experts problem\,
  is a generalization\nof the standard experts problem in which some expert
 s may be unavailable at any\ngiven round. The second is the episodic short
 est path problem\, in which an\nagent must find a route from a designated 
 start node to an end node\; the twist\nis that the set of available edges 
 may vary over time. The payoffs and the\nchoice of availability is presume
 d to have set by an oblivious adversary.\n\nDue to the combinatorial natur
 e of these problems\, different meaningful notions\nof regret--per action\
 , policy\, ranking are used. I'll show that in the these\nproblems are har
 d--in the sense that sub-linear regret bounds are unlikely to\nexist. Howe
 ver\, the hardness is due to computational difficulties rather than\nstati
 stical ones. I'll discuss some relaxations that allow us to design\nno-reg
 ret algorithms.
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge.
END:VEVENT
END:VCALENDAR