Research map / Reinforcement learning / MDPs and planning
A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear 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.
Proposes γ-DC-LSCVI-UCB, a value iteration algorithm for infinite-horizon average-reward linear MDPs that clips values using only visited states and controls value deviation across clipping thresholds, achieving Õ(sp(v*)√(d³T)) regret with computation independent of state-space size.
Problem
Computationally efficient regret minimization for infinite-horizon average-reward linear MDPs, where prior span-clipped value iteration requires minimizing values over the entire (possibly infinite) state space.
Approach
Replace the global minimum in value clipping with a threshold computed from visited states only (m_{t+1} = min of the visited-state value and m_t), and add a deviation-control clipping of Q-values against previous value chains so that value sequences computed under different thresholds stay close, enabling the telescoping analysis.
Key results
- Regret bound Õ(sp(v*)√(d³T log T)) with discount γ = 1 - 1/√T, matching the prior γ-LSCVI-UCB regret.
- Computational complexity O(T³d²A), independent of state-space size, versus prior algorithm whose clipping needs minimum over all states.
- Shows naive adaptation of γ-LSCVI-UCB fails to control value deviation in linear MDPs via a lemma constructing a regression counterexample.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace clipping over the entire state space with clipping using visited states and deviation-controlled value iteration | γ-LSCVI-UCB · Infinite-horizon average-reward linear MDPs | computation complexity: T, S, A, d -> T, A, d | Helped |
| replace clipping over the entire state space with visited-state clipping and deviation control | γ-LSCVI-UCB · Infinite-horizon average-reward linear MDPs | regret bound: sp(v*) √(d^3 T) -> sp(v*) √(d^3 T) | No clear effect |
| remove deviation-control clipping of Q (ablation) | γ-LSCVI-UCB+ · Tabular infinite-horizon average-reward MDPs | deviation between value-function sequences: m_t - m_{t + 1} | No clear effect |
| use regression-based transition estimates rather than empirical transition probabilities | value iteration in linear MDPs · Linear MDPs | deviation control | Hurt |
Surprising findings
- A naive value-iteration clipping with visited-state thresholds fails to control value deviation in linear MDPs, even though it works in the tabular case.
Limitations
- Computational complexity is still super-linear in T (T^3 d^2 A).
- Requires known span bound sp(v*) and assumes Bellman optimality equation.
- Regret is not improved beyond prior work's sqrt(d^3 T) by a factor of sqrt(d).
Experimental setup
Metrics: regret computational complexity
Baselines: γ-LSCVI-UCB FOPO OLSVI.FH MDP-EXP2 LOOP
Builds on: γ-LSCVI-UCB OLSVI.FH Jin et al. linear MDP regression Wei et al. discounted approximation
Closest papers by meaning
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.89)
- A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs (ICML 2024 · similarity 0.89)
- Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes (ICLR 2025 · similarity 0.89)
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.89)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.89)
- A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach (ICML 2025 · similarity 0.88)
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.