Regret Minimization for Stochastic Shortest Paths

on YouTube ↗31m

" summary

Presents algorithms for minimizing regret in stochastic shortest-path problems where transitions and costs are unknown. Describes regret bounds and techniques using online learning and reinforcement-learning tools (e.g., exploration strategies and concentration inequalities) tailored to shortest-path MDPs with goal states.

AI-written summary · about

" chapters (17)

1. 0:00Start
2. 0:57Stochastic Shortest Paths
3. 3:32SSP generalizes other models
4. 5:22Online learning SSP: Model
5. 6:54Online learning SSP: Regret
6. 7:39SSP regret: Previous works
7. 9:07SSP regret: our works
8. 10:18Planning in SSPs (Bertsekas and Tsitsiklis, 1991)
9. 12:14Making policies proper: Cmin 0
10. 15:07SSP regret: positive costs
11. 16:16SSP algorithm
12. 19:15SSP our algorithms
13. 23:40Regret analysis: bounds
14. 24:58Hoeffding versus Berenstein bound
15. 25:38Lower bound
16. 27:30Adversarial SSP
17. 28:43Summary

" related talks

• 01h 17mOnline Reinforcement Learning and RegretSean Sinclair, Christina Lee Yu · Data-Driven Decision Processes Boot Camp 2022
• 48mA Simple Condition for Constant Regret in Online Decision-MakingDaniel Freund · Matching and Objectives
• 46mDynamic Regret Minimization for Bandits without Prior KnowledgeChen-Yu Wei · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 42mA Regret Minimization Approach to Mutli-Agent Control and RLElad Hazan · Multi-Agent Reinforcement Learning and Bandit Learning
• 35mJe ne regrette rien: Teaching Machine Learning Models Regret AvoidanceLaura Israel · PyData Amsterdam 2024
• 31mLearning to Control Unknown SystemsRahul Jain · Societal Networks 2018
• 49mFast Rates for No-Regret Learning in General GamesNoah Golowich · Adversarial Approaches in Machine Learning 2022
• 58mMemory-Regret Tradeoff for Online LearningAviad Rubinstein, Binghui Peng · Sketching and Algorithm Design 2023