Research map / Bandits and online learning / RL theory and MDPs
No-Regret Reinforcement Learning in Smooth 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 ν-smoothness classes of MDPs (strongly and weakly smooth) and two Legendre-polynomial feature-based algorithms, Legendre-Eleanor (no-regret for weakly smooth) and Legendre-LSVI (polynomial-time, strongly smooth), with theoretical regret bounds and only a small simulated LQR-style experiment.
Problem
No-regret reinforcement learning in MDPs with continuous state and/or action spaces under general structural smoothness assumptions, beyond linear, LQR, Lipschitz, and kernelized MDPs.
Approach
Defines strongly smooth (transition and reward in C^{ν,1}) and weakly smooth (Bellman optimality operator bounded on C^{ν,1}) MDPs, and represents them with an orthogonal Legendre polynomial feature map, which yields low inherent Bellman error (used with Eleanor) or a linear MDP (used with LSVI-UCB).
Key results
- Legendre-Eleanor achieves regret Õ(K^{(3d/2+ν+1)/(d+2(ν+1))}) for weakly smooth MDPs when ν > d/2-1, approaching √K as ν→∞.
- Legendre-LSVI achieves regret Õ(H^{3/2} K^{(2d+ν+1)/(d+2(ν+1))}) for strongly smooth MDPs when d ≤ ν+1, with time complexity O(K^2 H) under the chosen N.
- In simulated modified LQR experiments, Legendre-feature LSVI (Leg(3), Leg(4)) learns to high return while standard polynomial features (Poly(3), Poly(4)) fail to learn within 500 episodes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Legendre polynomial features instead of standard polynomial features (ablation) | Legendre-LSVI on modified LQR environments · Modified LQR, both environments | episodic return | Helped |
| Use standard polynomial features instead of Legendre features (ablation) | Legendre-LSVI on modified LQR environments · Modified LQR, both environments | episodic return | Hurt |
| Increase polynomial degree from 3 to 4 (ablation) | Legendre-LSVI · Modified LQR, first environment | episodic return | Helped |
| Increase polynomial degree from 3 to 4 (ablation) | Legendre-LSVI · Modified LQR, second environment | episodic return | No clear effect |
| Increase polynomial degree from 3 to 4 (ablation) | Legendre-LSVI · Modified LQR environments | learning speed | Hurt |
| Use Legendre-Eleanor rather than the compared prior methods | Weakly Smooth MDPs · Weakly Smooth MDPs | regret: K^{\frac{3d/2+\nu+1}{d+2(\nu+1)}} vs. K^{\frac{2\nu+3d+2}{4\nu+4}} | Helped |
| Use Legendre-Eleanor rather than the compared prior method | Lipschitz MDPs · Lipschitz MDPs | regret: K^{\frac{3d/2+1}{d+2}} vs. K^{\frac{3d+2}{4}} | Helped |
Surprising findings
- Standard polynomial bases fail to learn in the simulated experiments while Legendre bases with the same feature dimension succeed.
Limitations
- Regret grows exponentially in horizon H for Legendre-Eleanor, matching a lower bound for Lipschitz-rich classes.
- Legendre-LSVI requires the stronger strong-smoothness assumption and a more demanding ν ≥ d-1 condition.
- Authors state it is unclear whether the proposed algorithms are optimal for the general setting.
Experimental setup
Benchmarks: simulated modified LQR environments
Metrics: episodic return
Baselines: Eleanor GOLF LSVI-UCB Lipschitz MDP algorithms kernelized MDP algorithms (Matérn) Poly(3) Poly(4)
Builds on: Eleanor LSVI-UCB Lipschitz MDPs kernelized MDPs
Closest papers by meaning
- Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs (NeurIPS 2024 · similarity 0.93)
- RL for Latent MDPs: Regret Guarantees and a Lower Bound (NeurIPS 2021 · similarity 0.91)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.91)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.90)
- Dynamic Regret of Adversarial MDPs with Unknown Transition and Linear Function Approximation (AAAI 2024 · similarity 0.90)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 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.