Dynamic Regret Minimization for Bandits without Prior Knowledge

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=kLMVbPnD5kc


Duration: 46:00
1,510 views
11

Chen-Yu Wei (University of Southern California)
https://simons.berkeley.edu/talks/tbd-482
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond

To evaluate the performance of a bandit learner in a changing environment, the standard notion of regret is insufficient. Instead, "dynamic regret" is a better measure that can evaluate the learner's ability to track the changes. How to achieve the optimal dynamic regret without prior knowledge on the number of times the environment changes had been open for a long time, and was recently resolved by Auer, Gajane, and Ortner in their COLT 2019 paper. We will discuss their consecutive sampling technique, which is rare in the bandit literature, and see how their idea can be elegantly generalized to a wide range of bandit/RL problems. Finally, we will discuss important open problems that remain in the area.



Other Videos By Simons Institute for the Theory of Computing


2022-09-27Higher-Order Graphon Theory: Fluctuations, Inference, and Degeneracies
2022-09-27A Large Deviation Principle for Block Models
2022-09-27Mean-field approximations for high-dimensional Bayesian Regression
2022-09-27Response of Graphs to Competing Constraints
2022-09-27Sparse Random Graphs: Interplay of Local and Global Structure
2022-09-26Analytic Approach to Guasirandomness
2022-09-26Random Cluster Model on Regular Graphs
2022-09-17Generalization and Robustness in Offline Reinforcement Learning
2022-09-17Adaptivity and Confounding in Multi-armed Bandit Experiments
2022-09-16When Can We Use Weak Function Approximation to Solve Large Scale Planning Problems in MDPs?
2022-09-16Dynamic Regret Minimization for Bandits without Prior Knowledge
2022-09-16Oracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust Learning
2022-09-16Adaptive Monopoly Regulation
2022-09-16Information Collection Through Strategic Agents
2022-09-16Incentivized Exploration
2022-09-15Attributes: Selective Learning and Influence
2022-09-15Markov Persuasion Process and its Reinforcement Learning
2022-09-15Parsimonious Learning-Augmented Algorithms
2022-09-14Machine Learning for Faster Optimization
2022-09-14Flow Time Scheduling with Uncertain Processing Time
2022-09-14Best Of Both Worlds: Stochastic & Adversarial Best-Arm Identification


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Quantifying Uncertainty: Stochastic Adversarial and Beyond
Chen-Yu Wei