What is the Statistical Complexity of Reinforcement Learning?
summary
Shows that simple linear Q realizability and linear policy classes still require exponential samples in horizon or dimension, so they fail for high‑dimensional RL, while models like linear MDPs, block MDPs, linear mixtures and LQR* admit polynomial sample complexity under stronger structural assumptions (Bellman‑rank / bilinear / eluder conditions). Introduces the Decision‑Estimation Coefficient (DEC): a Lagrangian tradeoff (Hellinger‑type distance with scale γ) that gives a general lower bound (maxγ {DEC(γ)·T − γ}) and, under convexity, matches achievable rates.
AI-written summary · about