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

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

Computational Challenges in Sleeping Combinatorial Experts

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Room 9, Faculty of Asian & Middle Eastern Studies Umney Lounge, Robinson College Average on weekdays: 9155.02469136 kWh

Other talks

Theophilus Richmond’s The First Crossing: The Transition from Slavery to Indentureship in the Caribbean and the Case of the Black Slave on the Hesperus The Jiangmen Underground Neutrino Observatory (JUNO): Status and First Physics Results TBC Spectral theory for Dirac operators with singular potentials Cultural evolution creates language-like structure: from humans to humpback whales and beyond Afternoon Break
 

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