Learning to Control Unknown Systems

on YouTube ↗31m

" summary

Proposes a concrete algorithm that applies posterior sampling to unknown finite MDPs and to linear stochastic systems: maintain a Bayesian posterior over transition/A,B parameters, sample θ at episode start, solve the MDP or LQR via dynamic programming, execute that policy until either every episode length increases by one or some state-action visit count doubles (or covariance halves for linear systems). Proves expected regret Õ(√T) (constants explicit, linear in |S|, √ in |A|), shows sublinear regret empirically on benchmark tasks but requires a closed-loop stability assumption for the proofs.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 1:03A Markov Decision Process
3. 1:38Dynamic Programming
4. 2:24Unknown Model
5. 4:04Bandit Models and Online Learning
6. 9:26The (Thompson) Posterior Sampling Algorithm
7. 11:35Learning an Unknown MDP
8. 15:38The PSDE Algorithm: Posterior Sampling with Dynamic Episodes
9. 16:32Non-asymptotic Regret bound for PSDE
10. 17:54Numerical Performance
11. 18:56Proof Outline
12. 22:54Unknown Stochastic Linear System
13. 23:50Stochastic Adaptive Control
14. 24:55The Posterior Sampling with Dynamic Episodes (PSDE) Learning Algorithm
15. 25:43VT-Regret of PSDE Algorithm
16. 26:54Conclusions

" related talks

• 31mStable Reinforcement Learning with Unbounded State SpaceQiaomin Xie · Reinforcement Learning from Batch Data and Simulation
• 15mMulti-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust ControlKaiqing Zhang · Meet the Fellows Welcome Event
• 01h 05mFoundations of RLRayadurgam Srikant · Data-Driven Decision Processes Boot Camp 2022
• 46mDynamic Regret Minimization for Bandits without Prior KnowledgeChen-Yu Wei · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 56mA Tutorial on Reinforcement Learning IIEmma Brunskill · Foundations of Machine Learning Boot Camp 2017
• 42mReinforcement Learning using Generative Models for Continuous State and Action Space SystemsRahul Jain · Reinforcement Learning from Batch Data and Simulation
• 01h 01mA Tutorial on Reinforcement Learning IEmma Brunskill · Foundations of Machine Learning Boot Camp 2017
• 01h 17mOnline Reinforcement Learning and RegretSean Sinclair, Christina Lee Yu · Data-Driven Decision Processes Boot Camp 2022