Research map / Reinforcement learning / MDPs and planning
Finite-Time Bounds for Average-Reward Fitted Q-Iteration
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 Anchored Fitted Q-Iteration (and a relative variant) for offline average-reward RL with general function approximation, giving the first finite-sample bounds under weakly communicating MDPs for IID and beta-mixing single-trajectory data.
Problem
Sample complexity of offline average-reward RL with function approximation has only been analyzed under restrictive assumptions (ergodicity, unichain, or linear MDPs), so finite-time guarantees under weaker structure are missing.
Approach
Combine fitted Q-iteration with an anchor (Halpern-style weight decay toward the initial function f_0) so that the iterates converge in finite time for average-reward MDPs; add relative normalization (subtracting the mmidpoint of max and min) to bound function ranges and improve the sample complexity exponent.
Key results
- With IID data under weakly communicating MDPs, Anc-F-QI achieves tilde-O(1/epsilon^6) sample complexity; relative variant improves it to tilde-O(1/epsilon^4).
- With beta-mixing single-trajectory data, Anc-F-QI achieves tilde-O(1/epsilon^12), and relative variant tilde-O(1/epsilon^8).
- Under Bellman completeness, the IID bound is the first finite-sample result for average-reward offline RL assuming only the Bellman optimality equation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add relative normalization to anchored fitted Q-iteration | Anchored Fitted Q-Iteration · Average-reward offline RL, IID data | sample complexity: \tilde{\mathcal{O}}(1/\epsilon^{6}) to \tilde{\mathcal{O}}(1/\epsilon^{4}) | Helped |
| Add relative normalization to anchored fitted Q-iteration | Anchored Fitted Q-Iteration · Average-reward offline RL, single-trajectory data | sample complexity: \tilde{\mathcal{O}}(1/\epsilon^{12}) to \tilde{\mathcal{O}}(1/\epsilon^{8}) | Helped |
| Add the anchor mechanism to fitted Q-iteration | Average-reward fitted Q-iteration · Average-reward offline RL | finite-time analysis | Helped |
Limitations
- Relies on full coverage coefficients, unlike partial-coverage prior work.
- Requires Bellman completeness and the Bellman optimality equation; no experiments are provided.
- Single-trajectory sample complexity is quite loose (epsilon^-12 and epsilon^-8).
Experimental setup
Metrics: policy error (sup-norm of gain difference) sample complexity order in epsilon
Baselines: Ozdaglar et al. primal-dual offline average-reward method Gabbianelli et al. unichain linear offline method
Builds on: Fitted Q-Iteration Anchored Value Iteration Halpern iteration relative value iteration
Closest papers by meaning
- Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs (NeurIPS 2024 · similarity 0.90)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.90)
- Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes (ICLR 2025 · similarity 0.90)
- Near-Optimal Sample Complexity for MDPs via Anchoring (ICML 2025 · similarity 0.88)
- Policy Gradient Algorithms in Average-Reward Multichain MDPs (NeurIPS 2026 · similarity 0.86)
- Gap-Dependent Bounds for Federated $Q$-Learning (ICML 2025 · similarity 0.86)
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.