Offline reinforcement learning seeks optimal decision rules from previously collected data. In some applications, a decision can be an entire function, such as a fluence map in radiation therapy or a smooth movement trajectory in robotics. In this paper, we study the finite-sample theory for fitted Q-iteration (FQI) with functional actions in a discounted infinite-horizon setting. Three major difficulties arise in this setting: first, the absence of a Lebesgue probability density for functional actions complicates coverage descriptions; second, conventional coverage requirements can be restrictive; and third, the large functional action space makes greedy optimization in FQI challenging. To address these difficulties, we study smoothness-regularized policy search under a critic-relative coverage condition. This condition measures how well logged data distinguish relevant action-value differences without requiring an action density. Our main theorem gives finite-sample guarantees for learned-policy regret relative to the best value within a fixed smooth class of functional-action policies. The results allow trajectory lengths to be either bounded or growing and Q-functions to be fitted by either functional-input kernel ridge regression or adaptive functional neural networks. For a few examples, we can obtain polynomially decaying regret bounds in the number of logged transitions, up to logarithmic factors, with logarithmically many FQI iterations. Numerical experiments show gains of learned functional-action policies over constant-action policies and support our adoption of a critic-relative coverage condition.
Figures & tables
Figure 1: AdaFNN policy value and critic-relative diagnostics versus the number n of offline transitions. (a) Mean normalized policy value for functional- and constant-action policies. (b) Median nearest-action L2 distance. (c) Median critic-energy ratio ERh ; the dotted line marks equal energy. Bars are pointwise 95% percentile-bootstrap intervals across 20 independent datasets.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure S1: Nyström KRR normalized policy value across the sample sizes in Figure 1 (a), with independent evaluation after Monte Carlo validation of the curvature coefficient. Points are means across the 20 datasets with pointwise 95% percentile-bootstrap intervals. Landmark rank also increases with n as specified in Appendix O ; the curve describes the implemented learning procedure, not an isolated effect of sample size.
Figure S2: AdaFNN functional-minus-constant difference in normalized policy value, paired within seed using common random numbers for evaluation. Points are mean differences; bars are pointwise 95% percentile intervals from 10,000 whole-seed bootstrap resamples. All sample sizes from a seed are resampled together, but the displayed intervals are not a simultaneous confidence band.
Figure S3: AdaFNN nearest-action L2 distances across sample sizes for (a) k=16 , (b) k=32 , (c) k=64 , and (d) k=128 nearest training states. Each fit contributes the median nearest-action L2 distance over its independent q=n evaluation states; points are medians across 20 independent datasets, with pointwise 95% percentile intervals from 10,000 whole-seed bootstrap resamples. Panel (b) reproduces Figure 1 (b). All panels use the same vertical scale.
Figure S4: Nyström KRR policy-action diagnostics across the five sample sizes: (a) nearest-action L2 distance, (b) relative feature leverage, and (c) critic-energy ratio. Every fit uses an independent cohort of q=n evaluation states. Points are medians over the 20 datasets with pointwise 95% percentile-bootstrap intervals across whole seeds. The offline state–action design and critic iterations 19 and 20 are common to AdaFNN and KRR; the critic representation and ridge geometry are approximator-specific. Panels (b)–(c) use logarithmic vertical scales.
Figure S5: Absolute adjacent-critic energies on independent held-out learned-policy state–action pairs and the logged design. The held-out mean evaluates the learned action at q=n states for every fit. Points are medians of the energies from the 20 datasets with pointwise 95% percentile-bootstrap intervals across whole seeds. Each panel uses a logarithmic vertical scale. The median of the per-fit ratios in Figure 1 (c) is generally not the ratio of these plotted medians.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
Fitted Q-iteration (FQI) is well understood when the data come from a fixed distribution and the action set is finite, whereas value-based continuous control collects its data adaptively and maximizes over continuous actions. Both features break the standard analysis: the regression data are dependent, and every density-ratio concentrability coefficient of a deterministic greedy policy is infinite when the exploration has no atoms. Conditioning on the history freezes the regression target, so each round of FQI is a regression with martingale noise, and we obtain localized rates that are fast for classes of polylogarithmic metric entropy. We transfer the regression error to the loss of the greedy policy by smoothing the measures on which this loss is evaluated, at a price that depends on the action dimension and the smoothness of the residuals in the action. Under deterministic dynamics the state is smoothed as well, and the state dimension enters the price. Minimax lower bounds with the same exponents in the sample size show that no learner avoids these prices, for restart data in the case of the state dimension. The coverage conditions do not involve the unknown greedy policies; they hold under exploration floors with restarts and, for action smoothing, bounded transition densities.
Manuel Haußmann, Mustafa Mert Çelikok, Melih Kandemir
Department of Mathematics and Computer Science University of Southern Denmark
Fitted Q-iteration (FQI) is a standard regression-based method for optimal control in offline reinforcement learning, but its stability under function approximation often relies on Bellman completeness, which requires Bellman images of the fitted class to remain in the class. We study Kullback--Leibler (KL)-regularized, or soft, FQI relative to a fixed reference policy without this assumption. Our key insight is that soft control locally inherits the contraction of policy evaluation in a discounted-occupancy norm. At the soft-optimal fixed point, the linearization of the soft Bellman operator is exactly the Bellman operator for the soft-optimal policy, which contracts in its discounted-occupancy norm; projection in the same norm preserves this contraction. Standard soft FQI instead projects under the offline state-action distribution and need not preserve this property. Motivated by this observation, we propose occupancy-reweighted soft FQI, which retains standard Bellman targets and least-squares updates while reweighting regressions by discounted-occupancy ratios induced by the current soft policy. Under Q-function realizability and local regularity, we establish local contraction and finite-sample convergence with estimated ratios, without Bellman completeness. We then use temperature annealing to convert the local result into global convergence from arbitrary initialization: sufficiently high temperature provides a globally contractive starting regime, while gradual cooling connects successive local contraction regions to any prescribed positive target temperature. Under an action-gap margin condition, switching at a fixed positive temperature to hard FQI with refreshed occupancy weights also yields population and finite-sample convergence to the unregularized optimum.
Lars van der Laan, Nathan Kallus
Department of Statistics, University of Washington · Netflix · Cornell University
We present a novel theoretical framework, Q-MMR, for off-policy evaluation in finite-horizon MDPs. Q-MMR learns a set of scalar weights, one for each data point, such that the reweighted rewards approximate the expected return under the target policy. The weights are learned inductively in a top-down manner via a moment matching objective against a value-function discriminator class. Notably, and perhaps surprisingly, a data-dependent finite-sample guarantee for general function approximation can be established under only the realizability of Qπ, with a dimension-free bound -- that is, the error does not depend on the statistical complexity of the function class. We also establish connections to several existing methods, such as importance sampling and linear FQE. Further theoretical analyses shed new light on the nature of coverage, a concept of fundamental importance to offline RL.