Stable Reinforcement Learning with Unbounded State Space
summary
Algorithm uses a Monte Carlo oracle that takes a single queried state, runs sparse sampling or MCTS rollouts to estimate multi-step Q-values, and returns a softmax action distribution; stability is proved assuming the optimal policy admits a Lyapunov function with bounded jumps and negative drift alpha, and requires the estimation error epsilon and tau = Theta(alpha) to be small; baseline sample complexity per query scales super-polynomially in 1/alpha but an MCTS-style oracle makes it polynomial in 1/alpha; an adaptive test automatically tunes tau.
AI-written summary · about
chapters (17)
- 0:00Intro
- 2:52Motivating Example
- 4:14RL for Learning to Schedule
- 4:57Challenges of Unbounded State Space
- 8:02Summary of Our Results A notion of stability to quantify "goodness" of RL algorithm Intuitively, maintain running system in favorable states
- 9:20Stability: Properties
- 10:40Stability: Formal Definition
- 12:25Algorithm: Key Component Monte Carlo (MC) oracle Output: a probability distribution over actions
- 13:28Algorithm Overview: Basic Version At each time step
- 16:14Monte Carlo Oracles
- 18:20Approximation Guarantees for Oracles • Sparse-Sampling Oracle
- 19:46Assumption The Markov chain M' under the optimal policy is positive recurrent
- 20:36Assumption: Lyapunov Function
- 22:02Main Results
- 23:50Proof Outline
- 24:56Revisit Results
- 27:00Other Variants ► Sample-efficient version Sample complexity per time step for small scales as
related talks
15mMulti-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust Control
31mLearning to Control Unknown Systems
01h 05mFoundations of RL
31mOn the Complexity of Learning Good Policies With and Without Rewards
55mWhat Are the Statistical Limits of Offline Reinforcement Learning With Function Approximation?
28mConfounding-Robust Policy Evaluation In Infinite-Horizon Reinforcement Learning
56mA Tutorial on Reinforcement Learning II
01h 01mA Tutorial on Reinforcement Learning I