Research map / Bandits and online learning / RL theory and MDPs
Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Locally Linearizable MDPs and the Cinderella algorithm, showing that Mildly Smooth MDPs (which include known feasible continuous-MDP families) reduce to this class and achieve no-regret bounds in all regimes.
Problem
No-regret reinforcement learning in continuous state-action MDPs, where existing smoothness or representation assumptions either yield vacuous bounds or suffer exponential dependence on the horizon H.
Approach
Use local linearity: partition the state-action space into regions with region-specific linear parameters over a shared feature map; the Cinderella optimistic algorithm (an extension of Eleanor) learns each region's parameters independently, and Taylor-polynomial local features make mildly smooth MDPs representable in this class.
Key results
- Cinderella achieves regret R_K = Õ(sum_h N_h d_h sqrt(K) + sum_h sqrt(d_h) I K) for locally linearizable MDPs.
- On Mildly Smooth MDPs of smoothness nu, Cinderella achieves regret Õ(H d_{nu*} K^{(nu+2d)/(2nu+2d)} + H^{(2nu+2d)/nu}), with exponent in (1/2,1) so no-regret in every regime.
- For nu > log K, regret is Õ(H log(K)^d sqrt(K) + H^2), recovering near-sqrt(K) behavior as smoothness grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Cinderella instead of Eleanor with feature extension | Locally Linearizable MDPs · Locally Linearizable MDPs | dependence on the number of regions in the approximation-error regret term: \sum_{h=1}^H \sqrt{N_hd_h} \mathcal I K -> \sum_{h=1}^H \sqrt d_h \mathcal I K | Helped |
| use Cinderella with local Taylor features and partitions | Mildly Smooth MDPs · Mildly Smooth MDPs | regret exponent in K: K^{\frac{\nu+3d/2}{2\nu+d}} -> K^{\frac{\nu+2d}{2\nu+2d}} | Helped |
| use Cinderella with local Taylor features and partitions | Strongly Smooth MDPs · Strongly Smooth MDPs | regret exponent in K: K^{\frac{\nu+2d}{2\nu+d}} -> K^{\frac{\nu+2d}{2\nu+2d}} | Helped |
| use Cinderella with local Taylor features and partitions | Kernelized MDPs · Kernelized MDPs | regret exponent in K: K^{\frac{\nu+3d/2}{2\nu+d}} -> K^{\frac{\nu+2d}{2\nu+2d}} | Helped |
| use Cinderella for every finite state-action dimension and smoothness parameter | Mildly Smooth MDPs · Mildly Smooth MDPs | regret exponent in K: K^{\frac{\nu+2d}{2\nu+2d}} | Helped |
Surprising findings
- Eleanor applied directly to the feature-extended representation yields a linear-in-K term growing with sqrt(N_h), which Cinderella avoids.
Limitations
- Algorithm is computationally inefficient, as in Eleanor.
- Exponential dependence on dimension d in the feature dimension d_{nu*} <= nu*^d; lower-order term H^{(2nu+2d)/nu} can be large when d >> nu.
- Theoretical paper with no empirical evaluation.
Experimental setup
Metrics: regret bound order in K
Baselines: Eleanor Legendre-Eleanor Golf Net-Q-Learning Legendre-LSVI KOVI
Builds on: Eleanor Linear MDPs low inherent Bellman error Legendre-Eleanor Kernelized MDPs
Closest papers by meaning
- No-Regret Reinforcement Learning in Smooth MDPs (ICML 2024 · similarity 0.93)
- Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection (NeurIPS 2021 · similarity 0.93)
- RL for Latent MDPs: Regret Guarantees and a Lower Bound (NeurIPS 2021 · similarity 0.92)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.91)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.90)
- Dynamic Regret of Adversarial MDPs with Unknown Transition and Linear Function Approximation (AAAI 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.