The Simplex and Policy-Iteration Methods are Strongly Polynomial...

on YouTube ↗52m

" summary

Shows that MDPs with a fixed discount are solvable by standard LP methods with explicit iteration bounds: policy iteration finishes in O(n/(1−γ) log(1/(1−γ))) steps and behaves linear when γ is fixed, while simplex with a greedy pivot gives quadratic-step guarantees. For deterministic MDPs simplex becomes strongly polynomial independent of γ (proved bound roughly m^3 n^2 log^2 m). Proofs use the LP formulation, pivot/strategy-elimination arguments, and path-versus-cycle flow analysis; policy-iteration’s strong-polynomial status for deterministic MDPs remains open.

AI-written summary · about

" chapters (25)

1. 0:00Intro
2. 1:29Linear Programming (LP)
3. 2:17Algebra of Linear Programming
4. 3:25Geometry of Linear Programming
5. 4:28LP Algorithms the Interior-Point Method
6. 8:24MDP Stationary Policy
7. 10:20An MDP Toy Example
8. 12:30The Linear Programming Form of the MDP
9. 13:41The Interpretations of the LP Dual Formulation
10. 15:04Pricing: the Cost-to-Go Values of the States
11. 16:12The Primal LP Form of the MDP
12. 17:37Algorithmic Events of the MDP Methods
13. 20:12Recall the Cost-to-Go Values of the States
14. 21:52The Simplex or Simple Policy Iteration: greedy rule
15. 22:21The Simplex or Simple Policy Iteration: index rule
16. 23:26Polynomial vs Strongly Polynomial
17. 25:52Complexity of the Policy Iteration and Simplex Methods
18. 26:14Complexity Theorem for MDP with Discount • The classic simplex method (Dantzis pivoting rule) and the policy iteration method, starting from any
19. 30:21The Turn-Based Two-Person Zero-Sum Game
20. 33:30Robust MDP with Discount
21. 36:11Deterministic MDP with Discount
22. 38:58High Level Ideas of the Proof I
23. 42:00More Results and Extensions
24. 43:57Remarks
25. 46:03Open Problems?

" related talks

• 20mThe Complexity of Infinite-Horizon General-Sum Stochastic GamesYujia Jin, Vidya Muthukumar, Aaron Sidford · ITCS 2023
• 55mOptimality and Approximation with Policy Gradient Methods in Markov Decision ProcessesAlekh Agarwal · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 57mFundamentals of Markov Decision ProcessesWeina Wang · Data-Driven Decision Processes Boot Camp 2022
• 52mWhen Can We Use Weak Function Approximation to Solve Large Scale Planning Problems in MDPs?Csaba Szepesvári · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 28mConfounding-Robust Policy Evaluation In Infinite-Horizon Reinforcement LearningAngela Zhou · Algorithmic Aspects of Causal Inference 2022
• 32mMonte Carlo Sampling Approach to Solving Stochastic Multistage ProgramsAlex Shapiro · Reinforcement Learning from Batch Data and Simulation
• 44mBeyond Worst-Case: Instance-Dependent Optimality in Reinforcement LearningMartin Wainwright · Reinforcement Learning from Batch Data and Simulation
• 37mMultiagent Reinforcement Learning: Rollout and Policy IterationDimitri Bertsekas · Reinforcement Learning from Batch Data and Simulation