PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Surrogate Based Dequantization of Quantum Reinforcement Learning

Pablo Rodriguez-Grasa, Sofiene Jerbi, Mikel Sanz, Ryan Sweke

arXiv:2609.16266v1quant-phcs.LG

TL;DR

Whether quantum Q-learning can offer a provable advantage over classical methods for practically relevant reinforcement-learning problems remains open. The paper analyzes kernelized Fitted Q-Iteration under uniform state-action sampling and identifies sufficient conditions for matching the best policy achievable with quantum Q-learning. Under those conditions, it rules out an exponential advantage in that simplified setting.

  • Problem

    Whether quantum Q-learning can be dequantized, and under what conditions classical methods can provably match it, had not been addressed despite promising empirical results and advantages in artificial environments.

    Source: §1 · p. 4

  • Method

    The paper analyzes classical kernelized Fitted Q-Iteration with a PQC-inspired kernel under uniform generative-model sampling.

    Source: §1 · p. 4, §4.3 · p. 13

  • Results

    With polynomial time and environment queries, the algorithm outputs with high probability a policy 𝜖-close to the best policy achievable with quantum Q-learning when the sufficient conditions hold.

    Source: §1 · p. 5

  • Takeaways & Limitations

    Under the identified conditions and uniform sampling, the result rules out an exponential quantum advantage via quantum Q-learning.

    Source: §1 · p. 5, §8 · p. 24

    The dequantization guarantees are proven only with a uniform generative model, and in practice it is unclear how to ensure the kernel is aligned with the unknown regression functions encountered during learning.

    Source: §1 · p. 5, §8 · p. 26

Abstract

from arXiv · show

In recent years, the utility of parameterized quantum circuits as function approximators has been widely studied. In the context of reinforcement learning, this approach has led to variational quantum algorithms such as quantum Q-learning. While these methods show promising empirical results, and can provide provable advantages for artificial problems, it remains unclear whether they can provide a provable quantum advantage over classical approaches for problems of practical relevance. A natural way to investigate this question is through the lens of dequantization: The construction of efficient classical algorithms capable of matching the performance of quantum variational methods. Building on recent kernel-based dequantization results for supervised learning, we take steps towards extending this surrogate-based dequantization program to reinforcement learning. Specifically, we study the simplified setting of reinforcement learning with a uniform generative model in which uniformly random state-action samples are available, which models the regime of sampling from a large experience replay buffer after sufficient exploration. Within this setting, we provide finite sample guarantees for classical kernelized Fitted Q-Iteration, with classical kernels designed to match the inductive bias of particular parameterized quantum circuits. Using these results, we then provide a set of sufficient conditions, on the data-encoding strategy of a parameterized quantum circuit, the corresponding classical kernel, and the problem structure, under which kernelized Fitted Q-Iteration provides a meaningful dequantization of quantum Q-learning, in this simplified setting. Apart from providing rigorous dequantization guarantees when these conditions are met, these results also motivate the use of kernelized fitted Q-iteration as a dequantization heuristic when these sufficient conditions cannot be verified.

1 Introduction

Whether quantum Q-learning can be dequantized for practically relevant reinforcement-learning problems remains unresolved. The paper analyzes a kernelized classical surrogate under uniform state-action sampling and identifies conditions under which it efficiently matches the best quantum-model policy.

1 Introduction

  • Prior work had not addressed whether quantum Q-learning can be dequantized or identified conditions under which classical algorithms provably match its performance.Quantum Q-learning uses a parameterized quantum circuit as the action-value function approximator; empirical studies report promising results in simulation, with provable advantages in artificial environments.Source: §1 · p. 4
  • The proposed surrogate uses Fitted Q-Iteration with Kernel Ridge Regression and a kernel whose RKHS contains every function expressible by the quantum circuit model.The conditions include sufficiently rapid kernel-eigenvalue decay, alignment with optimal value functions encountered during learning, and efficient kernel implementation.Source: §1 · pp. 4–5
  • With polynomial time and environment queries, the classical algorithm outputs with high probability a policy 𝜖-close to the best policy achievable with quantum Q-learning, under the stated conditions.In the uniform generative-model setting, this rules out an exponential quantum advantage via quantum Q-learning when those conditions hold.Source: §1 · p. 5
  • The guarantees apply only with a uniform generative model providing uniformly random state-action samples, a setting modeled on sampling a large replay buffer after sufficient exploration.The authors present the result as groundwork for broader reinforcement-learning dequantization and as motivation for practical heuristic use beyond verified conditions.Source: §1 · pp. 4–5

2 Dequantization of Variational Quantum Machine Learning

The section distinguishes ways to dequantize variational quantum machine learning and explains the relative-to-best benchmark. It motivates surrogate-based optimization and states the paper's contribution: sufficient conditions for its use in reinforcement learning with uniform sampling.

2 Dequantization of Variational Quantum Machine Learning

  • Relative-to-best dequantization compares a classical solution with the best solution in the quantum model class, rather than with the output of the quantum optimizer.The benchmark is useful when the quantum optimizer's achieved quality is difficult to quantify; polynomial resource bounds can rule out exponential advantages in time or samples.Source: §2 · p. 6

2.1 Surrogation vs Simulation

  • Dequantization approaches either simulate the quantum algorithm directly or optimize a classical model class chosen to share its inductive bias.The paper focuses on the surrogate-based approach, which uses knowledge of the quantum model class rather than the details of its optimizer.Source: §2.1 · p. 7, §2.1.2 · p. 7

2.1.1 Simulation-based dequantization

  • Simulation-based dequantization directly simulates the variational quantum algorithm, aiming to bound the resource overhead of simulating its iterations.The section cites tensor networks and Pauli Path Propagation as simulation techniques [16] [17] [19] [20] [21] [22] [23] [24] [25] [26].Source: §2.1.1 · p. 7

2.1.2 Surrogate-based dequantization

  • Surrogate-based dequantization identifies a related model class that can be optimized classically, then bounds optimization resources and solution quality relative to the quantum class.For PQCs, the approach uses their RKHS characterization and kernel algorithms; related surrogate work addressed regression [7] [9], classification, and quantum kernel methods [10].Source: §2.1.2 · p. 7

2.2 Our Contribution

  • The paper gives sufficient conditions for surrogate-based relative-to-best dequantization of variational quantum reinforcement-learning algorithms with a uniform generative model.The result follows from finite-sample guarantees for the proposed classical surrogate algorithm.Source: §2.2 · p. 7

3 Reinforcement Learning Preliminaries

The section introduces reinforcement-learning value functions and the Q-learning family. It moves from classical tabular updates to deep neural approximators and then to quantum circuits, whose theoretical guarantees remain limited.

3 Reinforcement Learning Preliminaries

  • Reinforcement learning seeks a strategy maximizing expected return through sequential interaction with an environment.The preliminaries model this interaction as a discounted Markov Decision Process, with bounded rewards and a finite action set.Source: §3 · p. 8

3.1 (Parameterized) Q-learning

  • Q-learning estimates the optimal action-value function directly from environment interaction, without a model of transition dynamics or rewards.The section introduces classical and parameterized Q-learning as value-based approaches, deriving a policy by greedy action selection.Source: §3.1 · p. 9, §3 · p. 9, §3.1.1 · p. 10

3.1.1 Q-learning

  • Tabular Q-learning stores a value for each state-action pair and updates it from observed rewards and transitions.Its update is a stochastic approximation of the Bellman optimality operator; under suitable conditions, it converges to Q* in finite MDPs.Source: §3.1.1 · p. 10

3.1.2 Deep Q-learning

  • Because tabular Q-learning becomes impractical for large state and action spaces, deep Q-learning uses neural networks to approximate the Q-function.DQN uses experience replay and a periodically updated target network to improve sample efficiency and stabilize regression targets; it has achieved superhuman performance in Atari games.Source: §3.1.2 · p. 10

3.1.3 Quantum Q-learning

  • Quantum Q-learning replaces the classical neural network with a parameterized quantum circuit to approximate the action-value function.Training uses gradient-based optimization on a temporal-difference loss, often with replay and target circuits; theoretical guarantees remain limited by nonconvex-optimization challenges.Source: §3.1.3 · p. 11

4 PQC Model Classes and Associated Kernels

The paper characterizes PQC models through the Fourier features induced by their data encoding, then uses those features to construct classical kernels whose RKHS contains the circuit model class. Kernel evaluation and the scope of the analysis depend on additional structural assumptions.

4.1 PQC Models

  • PQC models use Hamiltonian data encoding with component-wise state and action gates, yielding finite Fourier features determined by the encoding strategy.The frequency coefficients depend on circuit gates, while the encoding assumptions exclude some strategies, including time evolution of parameterized linear combinations of Hamiltonians.Source: §4.1 · pp. 11–12

4.2 Linearity of PQC models

  • PQC models are linear in the encoding feature map, but circuit constraints and bounded outputs can make their class a strict subset of all feature-map linear functions.The paper notes that some architectures could equal the bounded linear-function class.Source: §4.2 · p. 13

4.3 PQC-inspired kernels and the PQC-RKHS

  • The PQC-RKHS is the RKHS of a kernel built from the encoding feature map, and it contains every function expressible by the corresponding PQC model.This containment motivates using the RKHS as a surrogate model class for PQC optimization.Source: §4.3 · pp. 13–14
  • Naive evaluation of the PQC-inspired kernel is inefficient because its feature dimension can grow exponentially with state-action dimension.Random Fourier features approximate the kernel when its weight distribution can be sampled efficiently; symmetric polynomial-bond-dimension MPS weights permit exact efficient tensor-network evaluation.Source: §4.3 · p. 14

4.4 Generalized PQC Models

  • The analysis does not immediately cover all PQC architectures: incompatible action-observable spectra and trainable data-encoding strategies fall outside its assumptions.The authors say trainable output scaling can still be handled by modifying the observable, and that their assumptions cover most models proposed and used in practice.Source: §4.4 · p. 15

5 A Dequantization Algorithm for Quantum Q-learning

The section develops a classical surrogate for quantum Q-learning by pairing Fitted Q-Iteration with Kernel Ridge Regression in a PQC-inspired RKHS. Its analysis relies on uniform state-action sampling and efficient kernel evaluation.

5.1 The Idea

  • The surrogate uses the PQC-RKHS because it contains every function expressible by the circuit, and KRR and PQC optimization use the same feature map.KRR replaces stochastic-gradient updates by identifying an optimal Q-function in the associated RKHS at each iteration.Source: §5.1 · pp. 15–16

5.2 Some Problems

  • The analysis must address efficient kernel evaluation and relative performance guarantees; the algorithm assumes weights induced by a symmetric polynomial-bond-dimension MPS for exact efficient evaluation.This is the tensor-network route selected instead of randomized kernel approximation.Source: §5.2 · p. 16

5.3 A Simplifying Assumption: Uniform Environment Samples

  • Uniform state-action samples idealize sampling a large replay buffer after sufficient exploration, but do not directly represent standard trajectory-based sampling.The generative-model assumption makes the regression samples independent and isolates statistical analysis from trajectory correlations.Source: §5.3 · pp. 16–17

5.4 Fitted Q-Iteration

  • Fitted Q-Iteration repeatedly solves supervised regression problems approximating Bellman updates, separating sampling, approximation, and optimization for provable analysis under the fixed-distribution assumption.The regression targets use immediate rewards and the discounted maximum next-state Q estimate.Source: §5.4 · p. 17

5.5 The Dequantization Algorithm

  • Each iteration uses regularized KRR on Bellman targets in the PQC-RKHS, then clips the Q estimate to the reward-derived value range before producing the greedy policy.The per-iteration regression uses L2 regularization, while policy loss is measured with an L1 norm.Source: §5.5 · p. 18
  • The proposed algorithm replaces optimization over the PQC model class with classical KRR in its associated RKHS, using classical resources when the kernel can be evaluated classically.It repeats fitted Q updates and outputs a greedy policy.Source: §5.5 · p. 18

6 The Dequantization Question

Section 6 frames dequantization as a question about when classical FQI with PQC-inspired kernels can match quantum Q-learning. It separates the classical learning guarantee from the conditions that let it imply a relative-to-best dequantization.

6 The Dequantization Question

  • The section asks when Algorithm 1 can efficiently produce a policy whose loss is within ε of the best achievable with the specified PQC model.The question is posed in terms of a data-encoding strategy, observable, and a chosen kernel weight vector.Source: §6 · p. 19
  • The stated problem size is the state-space dimension and the number of actions.These quantities frame the efficiency question.Source: §6 · p. 19
  • Answering the corresponding FQI question is purely classical, but its sufficient conditions also establish an efficient relative-to-best dequantization of quantum Q-learning.The implication applies to Algorithm 1 with PQC-inspired kernels.Source: §6 · p. 20

7 Complexity Bounds for FQI with Kernel Ridge Regression and PQC Kernels

Section 7 gives assumptions and complexity bounds for kernelized FQI with PQC-inspired kernels. Under the stated conditions, the method is a time- and sample-efficient PAC learner; the assumptions are sufficient for the analysis, not necessary for practical success.

7.1 Assumptions

  • Bellman-target realizability requires targets from clipped RKHS predictors to remain in the hypothesis class; Bellman closure is a stronger sufficient condition, not a necessary one.The finite-dimensional PQC-RKHS need not be universal, so this structural requirement can be nontrivial; Appendix H sketches a relaxation with an added approximation-error term.Source: §7.1 · pp. 20–21
  • Bounded transition density controls mismatch between uniform training samples and policy evaluation, keeping the concentrability coefficient at most |A| p_max.For finite state spaces the condition holds with p_max = |S| and permits deterministic transitions; for continuous spaces it is a regularity assumption.Source: §7.1 · pp. 21–22
  • Inverse-polynomial decay of the ordered kernel weights controls kernel eigenvalue decay, which supports polynomial query complexity.The weight vector is chosen by the algorithm user and can be made to satisfy this assumption by design.Source: §7.1 · p. 22
  • The assumptions are sufficient for rigorous bounds, not necessary for practical success; classical and quantum Q-learning may work heuristically when they are violated.The paper notes Bellman-operator non-closure as one example of a possible violation.Source: §7.1 · p. 22

7.2 Complexity Bounds

  • The assumptions include uniform state-action sampling, Bellman closure for the clipped RKHS, bounded transition density, polynomial decay of kernel weights, and encoding and alignment conditions.The theorem lists these conditions as sufficient for its PAC guarantee.Source: §7.2 · p. 23
  • Under the theorem’s sufficient conditions, Algorithm 1 yields a high-probability policy guarantee and has polynomial sample and time complexity when the kernel is efficiently evaluable.A polynomial-bond-dimension symmetric matrix product state for the weights provides the stated efficient kernel evaluation.Source: §7.2 · pp. 23–24
  • The proof bounds information gain, frequency norm, and Bellman-target RKHS norms, then combines these bounds with FQI error propagation to obtain polynomial complexity.The kernel’s information gain is bounded using polynomial weight decay, while efficient tensor-network contractions support polynomial-time evaluation for the stated matrix-product-state weights.Source: §7.2 · p. 24

8 Sufficient Conditions for Dequantization of Quantum Q-learning (with Uniform Sampling)

Under uniform state-action sampling, Theorem 7.8 gives sufficient conditions for Algorithm 1 to dequantize quantum Q-learning efficiently. The conditions combine kernel-design requirements with alignment to the regression functions encountered during learning.

Sufficient Conditions for Dequantization of Quantum Q-learning (with Uniform Sampling)

  • The reweighting vector must have polynomial decay and a structure enabling efficient kernel evaluation, such as a symmetric matrix product state with polynomial bond dimension.Tensor-network contractions then evaluate the kernel exactly and efficiently; random Fourier features are an alternative if their approximation error is handled.Source: §8 · p. 25
  • The problem-dependent condition requires the reweighting vector to align with the frequency decomposition of every regression function encountered during learning.This condition is not efficiently checkable before solving the problem, and polynomial decay may conflict with alignment unless the target-function spectrum also decays polynomially.Source: §8 · p. 26
  • When all three conditions hold, Algorithm 1 has polynomial time and sample complexity and rules out an exponential quantum advantage in the uniform-sampling setting.The guarantee is relative to the best solution and applies under the theorem’s assumptions.Source: §8 · pp. 24, 26
  • The authors offer Algorithm 1 as a dequantization heuristic even when the sufficient conditions are unmet or cannot be verified, without guarantees in those cases.The weight-decay conditions resemble those in supervised-learning dequantization, but reinforcement learning requires alignment across the changing sequence of Bellman targets [9] [10].Source: §8 · p. 26

AI Disclosure

The appendix reports how generative AI contributed to manuscript revision, illustrates action encodings for PQC models, and explains how data-encoding Hamiltonians determine a frequency set.

AI Disclosure

  • Claude Opus 4.8 (Max) generated a critical referee report on the first draft; interaction with the model led to fixes across proofs, especially Lemma C.2.Source: AI Disclosure · p. 27

A On encoding of actions into PQC models

  • Binary action encoding is presented as an improvement over the preceding method, while examples show how prior action-dependent-observable models can be rewritten using Hamiltonian data encoding.The conversion is not guaranteed in general; a necessary condition is that all action observables have the same spectrum.Source: A On encoding of actions into PQC models · pp. 28–29

B From Data-Encoding Strategy to Frequency Set

  • For each coordinate, the frequency set consists of pairwise differences between possible sums of eigenvalues from its data-encoding Hamiltonians.The graphical construction uses a tree whose depth is the number of encoding gates and whose leaves contain the eigenvalue sums.Source: B From Data-Encoding Strategy to… · p. 30

C Proof of Theorem 7.8

The proof of Theorem 7.8 turns intermediate FQI–KRR error bounds into polynomial complexity by bounding information gain, frequency norms, and kernel-evaluation cost. Its guarantees depend on assumptions including bounded target complexity and efficient kernel structure.

C Proof of Theorem 7.8

  • The proof overview identifies sublinear information gain, controlled frequency norms, efficient kernel evaluation, and alignment as the ingredients for polynomial complexity.The intermediate bound also uses a conditionally sub-Gaussian regression-noise result.Source: C Proof of Theorem 7.8 · pp. 30–31

C.1 A starting observation

  • At each FQI–KRR iteration, regression noise is conditionally sub-Gaussian with parameter τ = 2Rmax/(1−γ), enabling standard kernel ridge regression error bounds.The errors are also conditionally independent and centered.Source: C Proof of Theorem 7.8 · p. 30, §C.1 · p. 31

C.2 Intermediate Complexity Bound via RKHS Norm, 𝐿, and Maximum Information Gain

  • The intermediate guarantee bounds policy error using maximum information gain, the largest frequency-vector norm, and the maximum RKHS norm of the Bellman targets across iterations.The proof combines FQI error propagation, pointwise KRR bounds, discretization over the continuous state space, and a probability bound for the training-set draw.Source: C Proof of Theorem 7.8 · p. 30, §C.2 · pp. 32–33

C.4 Bounding the Frequency Norm 𝐿

  • For typical Pauli encodings, Nmax = O(1) and λmax = 1, yielding a frequency norm L_D = O(√d).This keeps the logarithmic dependence on L_D in the sample complexity polynomial in the problem parameters.Source: C Proof of Theorem 7.8 · p. 31

C.3 Bounding the Maximum Information Gain

  • Γ(m+1) = o(m) for p > 1 under polynomial weight decay, supporting an explicit sufficient sample-size bound and polynomial sample complexity when the other complexity quantities are polynomial.The information-gain bound comes from splitting the kernel into a finite-rank truncation and a tail, then choosing the truncation rank to balance their contributions.Source: C Proof of Theorem 7.8 · p. 31, §C.3 · pp. 34–35

C.5 Time Complexity: Efficient Kernel Evaluation

  • Random Fourier features approximate the kernel efficiently when the weights define an efficiently samplable distribution; a polynomial-bond-dimension symmetric MPS permits exact evaluation by tensor-network contractions.The latter avoids the added approximation error associated with random Fourier features.Source: §C.5 · p. 36

C.6 Combining the Bounds

  • Under the theorem’s conditions, polynomial sample complexity, efficient kernel evaluation, and a polynomial number of iterations establish polynomial time and sample complexity.The iteration count is O(log(1/ε)); the result combines the sample bound, frequency-norm bound, and alignment condition.Source: §C.6 · p. 36

D Proof of Lemma C.2

The proof extends Lemma C.2 to kernels whose RKHS satisfies the stated assumptions, establishing a high-probability integrated-error guarantee for fitted Q-iteration. It controls FQI error using concentrability, regression-error bounds, and discretization, and derives a kernel log-determinant bound by truncating the feature decomposition.

D Proof of Lemma C.2

  • The proof generalizes Lemma C.2 to kernels satisfying Section 7.1 assumptions, especially realizable clipped Bellman targets and independent τ²-sub-Gaussian noise.Without target realizability, the analysis requires an additional approximation-error term.Source: D Proof of Lemma C.2 · pp. 37, 39
  • FQI’s error-propagation result is applied with uniform sampling and evaluation; bounded transition density yields a finite uniform concentrability coefficient.The proof measures error in the sampling-distribution-weighted L2 norm.Source: D Proof of Lemma C.2 · p. 37
  • At each fixed query, regression error is split into RKHS bias and sub-Gaussian noise, with both controlled using predictive uncertainty.The bias bound uses Bellman-target realizability; the noise bound is conditional on a fixed training set.Source: D Proof of Lemma C.2 · pp. 38–41
  • Lipschitz continuity and a finite covering net extend pointwise regression bounds across the continuous state-action space.The net is fixed independently of the noise so a union bound applies over its grid points.Source: D Proof of Lemma C.2 · pp. 42–44
  • A Lipschitz bound on predictive variance supports extending the fixed-grid error bound to all inputs, with corrections for grid discretization.The argument uses an RKHS covariance-operator representation and a push-through identity; the grid approximation is controlled using the variance’s Lipschitz continuity.Source: D Proof of Lemma C.2 · pp. 44–46
  • The expected integrated predictive uncertainty is bounded by relating it to cumulative predictive variances and applying a cumulative uncertainty bound.The proof uses i.i.d. training points, exchangeability, and the fact that predictive variance decreases as observations are added.Source: D Proof of Lemma C.2 · pp. 46–47
  • The proof gives a uniform high-probability integrated squared-error bound across iterations, which also applies when the target F_k is replaced by the clipped estimate Q̂_k.The bound’s right-hand side is independent of the iteration index; its leading K factor comes from a union bound over iterations.Source: D Proof of Lemma C.2 · p. 48
  • When all three conditions hold, the maximum per-iteration root-mean-square residual is at most ε; the algorithmic term is at most ε/2 by choice of K, with probability at least 1−δ over joint randomness.Source: D Proof of Lemma C.2 · p. 49

E Proof of Lemma C.3

  • The log-determinant proof splits the kernel into its T largest reweighted features and a residual, then bounds the contributions of both parts.The finite-feature term is bounded using a determinant identity and a trace inequality; the residual term uses its diagonal bound.Source: E Proof of Lemma C.3 · pp. 49–51

F Proof of Lemma C.4

Under polynomial Mercer-eigenvalue decay with exponent p > 1, the proof bounds both contributions at the same sublinear rate, yielding an o(m) term for sufficiently large m.

F Proof of Lemma C.4

  • Polynomial Mercer eigenvalue decay with exponent p > 1 supplies the condition used to bound the terms.The ordered eigenvalues decay polynomially up to multiplicity.Source: F Proof of Lemma C.4 · p. 51
  • Both contributions scale as O((m + 1)^(1/p)(log(m + 1))^((p - 1)/p)), which is o(m) for p > 1.The first contribution has this order, and the proof states the other scales the same way.Source: F Proof of Lemma C.4 · p. 51
  • The resulting bound holds for all sufficiently large m, with its constant depending only on C, p, and λ.The proof also states that the bound applies for any choice of T.Source: F Proof of Lemma C.4 · pp. 51–52

G Proof of Corollary C.5

The proof verifies the sufficient conditions for Corollary C.5 and identifies the dominant asymptotic sample-complexity term. It then relaxes Bellman closure, separating estimation from approximation error and showing that nonzero approximation bias can limit accuracy.

G Proof of Corollary C.5

  • The network complexity bound used in the proof is B_net(m) ≤ G_K + √m V_max/λ.Substituting this bound yields an upper bound proportional to m^(3/2) for the displayed expression.Source: G Proof of Corollary C.5 · p. 52
  • The sufficient sample size satisfies m ≥ 2A_inv log A_inv, which by Lemma G.2 implies (m/log m)^α ≥ A + B′ log m and, by Step 2, condition (G.1).The term 2A_inv log A_inv determines the asymptotic sample complexity.Source: G Proof of Corollary C.5 · pp. 55–56

H.1 Setup: Two Distinct Function Classes

  • Without Assumption 7.1, Bellman targets may fall outside the model class, so finite-sample guarantees require Bellman completeness or an explicit approximation-error term.The analysis distinguishes the class optimized over from a possibly larger class containing the Bellman updates.Source: §H.1 · p. 57

H.2 Decomposing the Per-Iteration Error

  • The relaxed analysis separates estimation error from approximation error; the former remains analyzable using the earlier regression bounds.The best realizable approximation lies in the hypothesis class, making that regression problem realizable.Source: §H.2 · p. 58
  • When Bellman closure fails, β_K is positive irreducible approximation bias that limits achievable accuracy regardless of sample size or iteration count.Under Bellman closure, β_K = 0 and the original theorem is recovered.Source: §H.2 · p. 58

H.3 Propagating the Error through FQI

The relaxed FQI bound separates estimation error, approximation bias, and finite-iteration error when Assumption 7.1 is dropped. A conservative bound confirms the bias is finite under stated conditions, but meaningful guarantees require it to be small.

H.3 Propagating the Error through FQI

  • Dropping Assumption 7.1 yields a relaxed FQI suboptimality bound with statistical error, irreducible approximation bias, and geometrically decaying algorithmic error.When the assumption holds, the bias is zero and the bound reduces to Theorem D.1.Source: §H.3 · p. 58

H.4 A Conservative Upper Bound on β_K

  • Assuming Q* ∈ H(D,w) and ‖Qhat_{k−1}‖∞ ≤ Vmax for every k, Proposition H.2 confirms βK is finite; its bound is a sanity check, not a useful quantitative guarantee.Source: §H.4 · p. 59

H.5 Summary

  • The approximation bias reflects Bellman-target mismatch with the hypothesis class and cannot be removed by increasing sample size or iteration count alone.It must instead be controlled through structural assumptions or a problem-specific argument; tighter bounds are proposed as future work.Source: §H.5 · p. 59

Related papers

Loading 2609.16266v1…