Computational Challenges in Sleeping Combinatorial Experts

Add to your list(s) Download to your calendar using vCal

• Varun Kanade (Oxford)
• Friday 06 May 2016, 16:00-17:00
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge..

If you have a question about this talk, please contact Quentin Berthet.

In this talk, I’ll discuss sleeping variants of two online decision making problems. The first, called the sleeping experts problem, is a generalization of the standard experts problem in which some experts may be unavailable at any given round. The second is the episodic shortest path problem, in which an agent must find a route from a designated start node to an end node; the twist is that the set of available edges may vary over time. The payoffs and the choice of availability is presumed to have set by an oblivious adversary.

Due to the combinatorial nature of these problems, different meaningful notions of regret—per action, policy, ranking are used. I’ll show that in the these problems are hard—in the sense that sub-linear regret bounds are unlikely to exist. However, the hardness is due to computational difficulties rather than statistical ones. I’ll discuss some relaxations that allow us to design no-regret algorithms.

This talk is part of the Statistics series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Guy Emerson's list
• Hanchen DaDaDash
• Interested Talks
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
• Machine Learning
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Statistics
• Statistics Group
• bld31
• custom
• rp587

Note that ex-directory lists are not shown.