Research map / Bandits and online learning / RL theory and MDPs
Horizon-Free Regret for Linear Markov Decision Processes
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.
Gives the first horizon-free regret bound, Õ(d^5.5 √K + d^6.5), for episodic linear MDPs under a total-bounded-reward assumption, via multiple weighted least-squares value estimators and a total-variation lemma.
Problem
Regret of RL in linear MDPs with time-inhomogeneous value functions: whether horizon-free (poly-log in H) regret bounds are achievable when the transition model size is exponential or uncountable.
Approach
Directly estimates value functions and confidence sets with multiple variance-aware weighted least-squares estimators (instead of explicit transition models), and splits the horizon into doubling segments; a structural lemma bounds the maximal total variation of inhomogeneous optimal value functions by a polynomial in d.
Key results
- Proves regret Õ(d^5.5 √K + d^6.5) for linear MDPs with only poly-log dependence on horizon H under bounded total reward.
- Structural lemma: maximal total variation of inhomogeneous optimal value functions is bounded by O(d/(H-h+1)), yielding per-segment variance sums of order Kd^2.
- Algorithm is computationally inefficient (confidence sets over epsilon-nets of value functions).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed horizon-free algorithm instead of LSVI-UCB | Linear MDP · Linear MDP | regret bound dependence on planning horizon: $\tilde{O}(\sqrt{d^3HK})$ -> $\tilde{O}(d^{5.5}\sqrt{K}+d^{6.5})$ | Helped |
| Use the proposed horizon-free algorithm instead of LSVI-UCB++ | Linear MDP · Linear MDP | regret bound dependence on planning horizon: $\tilde{O}(\sqrt{d^2K}+d^7H^6)$ -> $\tilde{O}(d^{5.5}\sqrt{K}+d^{6.5})$ | Helped |
| Use the proposed horizon-free algorithm instead of VOQL | Linear MDP · Linear MDP | regret bound dependence on planning horizon: $\tilde{O}(\sqrt{d^2K}+d^6H^4)$ -> $\tilde{O}(d^{5.5}\sqrt{K}+d^{6.5})$ | Helped |
Surprising findings
- Algorithm is computationally inefficient due to epsilon-net over value functions, though statistically horizon-free.
Limitations
- Algorithm is not poly-time computable (confidence regions over exponentially large epsilon-nets).
- Regret polynomial in d is large (d^5.5), far from the lower bound Omega(d sqrt K).
- Assumes bounded total reward (sum of rewards <= 1) rather than per-step bounds.
Experimental setup
Metrics: regret
Baselines: LSVI-UCB LSVI-UCB++ VARLin VOQL
Builds on: VOFUL LSVI-UCB VARLin UCRL-VTR
Closest papers by meaning
- Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes (ICML 2023 · similarity 0.93)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.92)
- No-Regret Reinforcement Learning in Smooth MDPs (ICML 2024 · similarity 0.91)
- Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback (ICML 2025 · similarity 0.90)
- Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs (NeurIPS 2024 · similarity 0.90)
- Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs (ICLR 2024 · similarity 0.90)
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.