University of Cambridge > Talks.cam > Statistics > Computational Challenges in Sleeping Combinatorial Experts

Computational Challenges in Sleeping Combinatorial Experts

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity