Value Function Estimation

Fitted $Q$-evaluation (FQE) is a standard regression-based method for off-policy evaluation, but under distribution shift, value-function realizability alone does not ensure convergence, and existing analyses often require Bellman completeness. We trace this instability to a geometric mismatch: standard FQE projects Bellman targets in the norm induced by the offline distribution, which need not preserve Bellman contraction. We therefore study occupancy-weighted FQE, which changes only the regression weights. Weighting by a target-policy discounted occupancy ratio aligns the projection norm with the target-policy dynamics and restores contraction of the population projected Bellman operator. We derive finite-sample guarantees with estimated occupancy ratios and function-class misspecification, separating finite-iteration, statistical, approximation, and ratio-estimation errors. Exact occupancy weighting removes the need for Bellman completeness; with estimated weights, approximate completeness and value-function realizability reduce sensitivity to ratio-estimation error, with exact realizability yielding higher-order dependence. Combining occupancy-weighted FQE with fitted occupancy-ratio evaluation gives an end-to-end guarantee governed by the complexities and direct approximation errors of the value-function and occupancy-ratio classes. Under coverage, joint realizability of these two classes suffices for consistent estimation without Bellman or critic-side completeness. Controlled experiments illustrate the projection-norm mechanism and the finite-sample tradeoff between contraction and coverage.

Reliable value estimation serves as the cornerstone of reinforcement learning (RL) by evaluating long-term returns and guiding policy improvement, significantly influencing the convergence speed and final performance. Existing works improve the reliability of value function estimation via multi-critic ensembles and distributional RL, yet the former merely combines multi point estimation without capturing distributional information, whereas the latter relies on discretization or quantile regression, limiting the expressiveness of complex value distributions. Inspired by flow matching's success in generative modeling, we propose a generative paradigm for value estimation, named FlowCritic. Departing from conventional regression for deterministic value prediction, FlowCritic leverages flow matching to model value distributions and generate samples for value estimation.

With origins in game theory, probabilistic values like Shapley values, Banzhaf values, and semi-values have emerged as a central tool in explainable AI. They are used for feature attribution, data attribution, data valuation, and more. Since exact computation can require exponential time, research has focused on efficient approximation methods using two techniques: Monte Carlo sampling and linear regression formulations. In this work, we present a new way of combining both of these techniques. Our approach is more flexible than prior algorithms, allowing for linear regression to be replaced with any function family whose probabilistic values can be computed efficiently. This allows us to harness the accuracy of tree-based models like XGBoost; with cross-fitting, the method also produces unbiased estimates. From experiments across eight datasets, we find that our methods give state-of-the-art performance for estimating probabilistic values. For Shapley values, the error of our methods can be $11\times$ lower than Permutation SHAP (the most popular Monte Carlo method), $6.5\times$ lower than Kernel SHAP (the most popular linear regression method), and $3.4\times$ lower than Leverage SHAP (the prior state-of-the-art Shapley value estimator). For more general probabilistic values, we can obtain error $390\times$ lower than the best estimator from prior work.

We propose a novel k-step return estimation method (called KETCHUP) for Reinforcement Learning(RL)-based knowledge distillation (KD) in text generation tasks. Our idea is to induce a K-step return by using the Bellman Optimality Equation for multiple steps. Theoretical analysis shows that this K-step formulation reduces the variance of the gradient estimates, thus leading to improved RL optimization especially when the student model size is large. Empirical evaluation on three text generation tasks demonstrates that our approach yields superior performance in both standard task metrics and large language model (LLM)-based evaluation. These results suggest that our K-step return induction offers a promising direction for enhancing RL-based KD in LLM research.

This paper develops a model-based framework for continuous-time policy evaluation (CTPE) in reinforcement learning, incorporating both Brownian and Lévy noise to model stochastic dynamics influenced by rare and extreme events. Our approach formulates the policy evaluation problem as solving a partial integro-differential equation (PIDE) for the value function with unknown coefficients. A key challenge in this setting is accurately recovering the unknown coefficients in the stochastic dynamics, particularly when driven by Lévy processes with heavy tail effects. To address this, we propose a robust numerical approach that effectively handles both unbiased and censored trajectory datasets. This method combines maximum likelihood estimation with an iterative tail correction mechanism, improving the stability and accuracy of coefficient recovery. Additionally, we establish a theoretical bound for the policy evaluation error based on coefficient recovery error. Through numerical experiments, including a real-data BTC price experiment, we demonstrate the effectiveness and robustness of our method in recovering heavy-tailed Lévy dynamics and verify the theoretical error analysis in policy evaluation.

Temporal difference (TD) and Monte Carlo (MC) are two fundamental principles for value function estimation in reinforcement learning. TD is asymptotically efficient for value estimation, whereas MC requires only adequate target visitation. We show that these advantages are automatically combined by ordinary TD in the tabular setting. We identify the subgraph Bellman variance, arising from bootstrapping within a subgraph and rollouts outside it, as a fundamental quantity connecting the MC and efficient TD benchmarks. With independent trajectories, we prove a non-asymptotic oracle inequality: the mean squared error of full TD is bounded by this variance divided by the sample size for every sufficiently covered subgraph containing the target, up to a higher-order remainder whose occupancy dependence is confined to that subgraph. No subgraph is supplied to the algorithm. TD thus adapts without selecting a subgraph or requiring global coverage. A finite-sample minimax lower bound shows that the asymptotic variance of TD need not be attainable before rare states are adequately observed. Experimental studies examine the transition between these variance scales and its dependence on visitation structure.

We investigate the statistical properties of Temporal Difference (TD) learning with Polyak-Ruppert averaging, arguably one of the most widely used algorithms in reinforcement learning, for the task of estimating the parameters of the optimal linear approximation to the value function. Assuming independent samples, we make three theoretical contributions that improve upon the current state-of-the-art results: (i) we establish refined high-dimensional Berry-Esseen bounds over the class of convex sets, achieving faster rates than the best known results, and (ii) we propose and analyze a novel, computationally efficient online plug-in estimator of the asymptotic covariance matrix; (iii) we derive sharper high probability convergence guarantees that depend explicitly on the asymptotic variance and hold under weaker conditions than those adopted in the literature. These results enable the construction of confidence regions and simultaneous confidence intervals for the linear parameters of the value function approximation, with guaranteed finite-sample coverage. We demonstrate the applicability of our theoretical findings through numerical experiments.

Offline reinforcement learning enables evaluation and optimization of sequential decisions from historical data, when it is not possible to deploy new policies online due to safety, cost, and other concerns. Big data advances enable rich state information, but may naively include reward- and action- irrelevant dynamics that are ultimately unnecessary for learning optimal actions. We introduce state abstractions that target preservation of the difference-of-Q functions, and we propose to learn these abstractions via causal machine learning of the difference-of-Q function and standard statistical sparse learning. Under a nonparametric additive-rewards model, we characterize when decision-centered abstractions are simpler than the full state space, motivating our estimation procedure. We develop a dynamic generalization of the R learner (Nie et al. 2021, Lewis and Syrgkanis 2021) for estimating difference of Q-functions, for discrete-valued actions a, a0. We leverage orthogonal estimation to improve convergence rates, even if the required estimates of Q and behavior policy converge at slower rates and prove consistency of policy optimization under a margin condition. The method can leverage black-box estimators of the Q-function and behavior policy to target estimation of a more structured Q-function contrast, and uses simple squared-loss minimization. We demonstrate variance improvements from our estimator and how our approach enables us to isolate the information needed for sequential decision-making, which can be less than that for state prediction, in simulated data and simulator-augmented real data.