Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds
Mar 9, 2021
Speakers
Ehsan Emamjomeh-Zadeh
Speaker · 0 followers
Chen-Yu Wei
Speaker · 0 followers
Haipeng Luo
Speaker · 1 follower
David Kempe
Speaker · 0 followers
About
We revisit the problem of online learning with sleeping experts/bandits: in each time step, only a subset of the actions are available for the algorithm to choose from (and learn about). The work of Kleinberg et al. (2010) showed that there exist no-regret algorithms which perform no worse than the best ranking of actions asymptotically. Unfortunately, achieving this regret bound appears computationally hard: Kanade and Steinke (2014) showed that achieving this no-regret performance is at least as hard as PAC-learning DNFs, a notoriously difficult problem. In the present work, we relax the original problem and study computationally efficient no-approximate-regret algorithms: such algorithms may exceed the optimal cost by a multiplicative constant in addition to the additive regret. We give an algorithm that provides a no-approximate-regret guarantee for the general sleeping expert/bandit problems. For several canonical special cases of the problem, we give algorithms with significantly better approximation ratios; these algorithms also illustrate different techniques for achieving no-approximate-regret guarantees.We revisit the problem of online learning with sleeping experts/bandits: in each time step, only a subset of the actions are available for the algorithm to choose from (and learn about). The work of Kleinberg et al. (2010) showed that there exist no-regret algorithms which perform no worse than the best ranking of actions asymptotically. Unfortunately, achieving this regret bound appears computationally hard: Kanade and Steinke (2014) showed that achieving this no-regret performance is at least…
Categories
Mathematics
Category · 2.4k presentations
AI & Data Science
Category · 10.8k presentations
About ALT 2021
The 32nd International Conference on Algorithmic Learning Theory
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Non-uniform Consistency of Online Learning with Random Sampling
Watch later
Changlong Wu, …
On the Sample Complexity of Privately Learning Unbounded Gaussians
Watch later
Stochastic Top-K Subset Bandits with Linear Space and Non-Linear Feedback
Watch later
Intervention Efficient Algorithms for Approximate Learning of Causal Graphs
Watch later
