Reinforcement Learning in Feature Space: Complexity and Regret
summary
Shows that tabular sample complexity reaches the known S A / (1−γ)^3 type limits, then moves to low‑rank transition kernel: P(s'|s,a)=φ(s,a)^T M ψ(s') and estimates M by ridge regression from trajectories. Uses confidence balls + optimistic Bellman updates to drive exploration; proves regret ≲ O(d · H^2 · √T) (linear in feature dim, √T) with a kernel extension (effective dimension replaces d) and reports practical gains from diffusion‑map embeddings and convex‑hull landmarks in experiments.
AI-written summary · about
chapters (22)
- 0:00Intro
- 3:59Markov decision process
- 5:24What does a sample mean?
- 6:56Complexity and Regret for Tabular MDP
- 11:14Rethinking Bellman equation
- 13:17State Feature Map
- 14:18Representing value function using linear combination of features
- 15:32Reducing Bellman equation using features
- 17:16Sample complexity of RL with features
- 18:11Learning to Control On-The-Fly
- 20:29Episodic Reinforcement Learning
- 22:13Hilbert space embedding of transition kernel
- 26:05The MatrixRL Algorithm
- 29:34Regret Analysis
- 33:15From feature to kernel
- 34:05MatrixRL has a equivalent kernelization
- 34:41Pros and cons for using features for RL
- 37:17What could be good state features?
- 40:16Finding Metastable State Clusters
- 40:55Unsupervised state aggregation learning
- 41:32Soft state aggregation for NYC taxi data
- 42:01Example: State Trajectories of Demon Attack
related talks
56mA Tutorial on Reinforcement Learning II
01h 17mOnline Reinforcement Learning and Regret
44mActive Regression via Linear-Sample Sparsification
11mLinear Predictors in Reinforcement Learning: ...
31mLearning to Control Unknown Systems
01h 01mRobustness, Stochastics, Uncertainty 2
35mJe ne regrette rien: Teaching Machine Learning Models Regret Avoidance
30mRepresentation Learning and Exploration in Reinforcement Learning