Research map / Learning theory and algorithms / Sample complexity
A Fine-grained Analysis of Fitted Q-evaluation: Beyond Parametric Models
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.
Analyzes fitted Q-evaluation (FQE) with linear (parametric) and linear-sieve (nonparametric) Q-function models, showing n^{-1/2} rates are achievable and that horizon dependence improves from T^{1.5} to T with a realizability condition on probability ratio functions.
Problem
Understanding the statistical error of fitted Q-evaluation for off-policy evaluation in finite-horizon MDPs: whether the optimal n^{-1/2} rate holds under nonparametric Q-models, how the error scales with horizon T, and what role probability ratio functions play.
Approach
Decomposes the FQE error into a first-order martingale term plus higher-order terms, and shows the first-order variance is a sum of T conditional-variance terms, giving T^{1.5}/sqrt(n); with realizability of ratio functions (a "double-rate" style property), the first-order term improves to T/sqrt(n) without explicitly estimating the ratios. Nonparametric Q-functions are handled via linear sieves (
Key results
- Parametric FQE achieves the n^{-1/2} rate with first-order term T^{1.5}/sqrt(n) (linear Q-model, fixed K).
- With realizability of ratio functions (Assumption on w_t^pi), the first-order term improves from T^{1.5}/sqrt(n) to T/sqrt(n), matching the best known tabular MIS rate.
- Nonparametric FQE with linear sieves attains n^{-1/2} when Q-function smoothness beta_Q > 1; simulations show roughly linear dependence of error on T.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Assume probability ratio functions are realizable by the linear function class | Parametric FQE · Finite-horizon MDP | first-order policy value estimation error bound: T^{1.5}/\sqrt{n} -> T/\sqrt{n} | Helped |
| Assume probability ratio functions are approximated well by the Q-function sieve basis | Nonparametric FQE · Finite-horizon MDP | first-order policy value estimation error bound: T^{1.5}/\sqrt{n} -> T/\sqrt{n} | Helped |
| Use nonparametric Q-function modeling with β_Q > 1 and fixed T, without ratio-function realizability | FQE · Finite-horizon MDP, fixed T | policy value estimation error bound: n^{-\beta_Q/(1 + 2\beta_Q)} -> n^{-1/2} | Helped |
| Use nonparametric Q-function modeling with β_Q = β_w = β > 1/2 and ratio-function realizability | FQE · Finite-horizon MDP, fixed T | policy value estimation error bound: n^{-1/2} | Helped |
Surprising findings
- Nonparametric FQE attains the n^{-1/2} rate for policy value even though Q-functions are estimated at slower nonparametric rates, when smoothness is sufficient.
Limitations
- Higher-order term scales as T^3/n (or T^3 K log n log T / n) with stronger assumptions (uniform convergence, Holder-continuous basis) than the first-order analysis.
- Unclear whether the T^{1.5} higher-order dependence can be improved to match the tabular T^{1.5}/n rate; bias terms from continuous state and nonparametric modeling remain.
- Simulation is a simple 1-D homogeneous MDP treated as inhomogeneous, with limited empirical scope.
Experimental setup
Metrics: absolute error of policy value estimate |nu_hat - nu|
Baselines: linear FQE (T^2/sqrt(n) analyses) nonparametric FQE bounds with feed-forward ReLU networks tabular MIS estimator (T/sqrt(n))
Builds on: fitted Q-evaluation marginal importance sampling estimator
Closest papers by meaning
- Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes (NeurIPS 2024 · similarity 0.84)
- QuEst: Enhancing Estimates of Quantile-Based Distributional Measures Using Model Predictions (ICML 2025 · similarity 0.84)
- Off-policy estimation with adaptively collected data: the power of online learning (NeurIPS 2024 · similarity 0.84)
- A Principled Path to Fitted Distributional Evaluation (NeurIPS 2025 · similarity 0.84)
- Demystifying the Paradox of Importance Sampling with an Estimated History-Dependent Behavior Policy in Off-Policy Evaluation (ICML 2025 · similarity 0.84)
- A Perspective of Q-value Estimation on Offline-to-Online Reinforcement Learning (AAAI 2024 · similarity 0.83)
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.