PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Value Inference for Reinforcement Learning

Nan Lu, Ethan Lee, James M. Robins, David Simchi-Levi, Junwei Lu

arXiv:2609.09981v1stat.MLcs.LGstat.ME

TL;DR

The paper asks how offline trajectories can support valid uncertainty quantification for the optimal long-run average reward when action maximization is embedded in recursive Bellman equations. It smooths the Bellman operator through a self-induced fixed point and applies Neyman-orthogonal debiasing, obtaining asymptotic normality under diverging horizons and time-varying behavior policies when nuisance rates are sufficient.

  • Problem

    Offline policy evaluation and policy learning do not directly provide valid uncertainty quantification for the unknown optimal long-run average reward, whose Bellman recursion contains nonsmooth action maximization.

  • Method

    The method replaces the Bellman maximum with softmax, estimates the resulting fixed-point nuisances and adjoint weight, and constructs a Neyman-orthogonal score for debiased optimal-value inference.

  • Results

    Asymptotic normality holds when NH diverges under the stated assumptions, including time-varying behavior policies and nuisance estimation at sufficient statistical rates.

  • Takeaways & Limitations

    The framework provides a unified route to optimal-value inference under fixed and diverging horizons without requiring a consistent optimal-policy estimator.

  • Takeaways & Limitations

    The approach relies on assumptions for the MDP, smoothing parameter, and nuisance rates, while extensions to other state spaces, objectives, and finite horizons remain future directions.

Abstract

from arXiv · show

We study offline inference for the optimal value in reinforcement learning. Two new nuisances are derived as fixed points of a self-induced Bellman equation, in which we approximate the maximum Bellman operator by its softmax correspondence. We propose a debiased estimator through the Neyman orthogonality and establish its asymptotic normality under diverging horizons even when the behavior policy changes with time, as long as the nuisances have the statistical rates that can be achieved by many machine learning methods. We provide a concrete estimating procedure for these nuisances and show they can lead to valid inference. Synthetic experiments validate the numerical performance of our inference method, and we implement it in real-life decision-making problems, including bike repositioning and AI agentic tool use.

1 Introduction

The paper develops offline inference for the optimal long-run average reward, addressing nonsmooth action maximization within recursive Bellman equations. It introduces a self-induced softmax Bellman equation, orthogonal inference, and nuisance estimators supporting asymptotic normality under diverging horizons and changing behavior policies.

  • Motivation: Offline reinforcement learning methods do not directly provide valid uncertainty quantification for the optimal long-run average reward.The target is the best long-run average reward attainable by a stationary Markov policy.
  • Motivation: Optimal value inference is nonregular when actions are tied or nearly tied, and Bellman recursion propagates maximization through continuation values.This makes optimal policy estimation a difficult upstream nuisance for inference.
  • Method: The method replaces the Bellman maximum with a softmax correspondence and estimates (Qβ, Jβ) as fixed points of a self-induced Bellman equation.These fixed-point nuisances jointly encode policy generation and continuation-value evaluation.
  • Theory: A Neyman-orthogonal score yields asymptotic normality when the nuisance functions achieve an op((NH)^−1/4) rate, without requiring a consistent optimal-policy estimator.The result uses the martingale structure of decision-making processes and applies when NH diverges.
  • Estimation: The paper develops a regularized minimax estimator for the nonlinear Bellman nuisances and a plug-in empirical risk minimization estimator for the adjoint weight.Finite-sample nuisance rates are established that suffice for valid inference.
  • Positioning: The framework differs from fixed-policy evaluation by making the optimized long-run average reward itself the inferential target while allowing time-varying behavior policies.It provides inference under both fixed and diverging trajectory horizons.

2 Problem Setup

The setup observes independent finite-horizon trajectories from a possibly time-varying behavior policy in a finite tabular Markov decision process. The target is the optimal average reward, represented through anchored relative action values and a Bellman optimality equation.

  • Observed data: The data consist of N independent trajectories, each containing H observed transitions of states, actions, rewards, and next states.The trajectories are generated under a common initial-state law and behavior-induced trajectory law.
  • MDP: The environment is time-homogeneous and Markov, so the next reward and state depend on the history only through the current state and action.The transition kernel and conditional mean reward specify the finite tabular MDP.
  • Behavior policy: The behavior policy may vary across time, although each time-specific decision rule is Markov.Stationarity is the special case in which the decision rules are identical across time.
  • Value representation: Relative action values are anchored by requiring zero arithmetic mean, removing the additive-constant ambiguity in the Bellman representation.The resulting Qπ is the zero-average representative of the probabilistic relative action value.
  • Target parameter: The target J∗ is the maximum average reward over stationary Markov policies, and an optimal stationary policy exists under the stated setup.Under irreducibility, the average reward is independent of the initial state.
  • Optimality equation: All optimal stationary policies share the same anchored relative action-value function Q∗, which satisfies the Bellman optimality equation.This common function remains uniquely defined even when the optimal policy is not unique.

3 Self-Induced Bellman Equation

This section replaces post-hoc softmax policy learning and evaluation with a self-induced Bellman equation that jointly determines the softened policy and its continuation values. Under identification conditions, the anchored solution exists uniquely and approximates the optimal value with bounds controlled by the smoothing parameter and optimality gap.

  • Motivation: Post-hoc softmax changes future action probabilities without recomputing continuation values, creating a separate policy-evaluation problem and an additional inferential error.The mismatch is not automatically removed by fixed-policy orthogonality because upstream policy-learning error remains.
  • Construction: The proposed method jointly determines policy generation and continuation-value evaluation through one action-value function and a self-consistent softmax Bellman recursion.The smoothed recursion is closed through a stationary fixed point, producing the pair (Qβ, Jβ).
  • Construction: A self-induced Bellman solution is a pair (Qβ, Jβ) satisfying the smoothed Bellman equation, with πβ induced by Qβ.The action-value function is identifiable only up to an additive constant, motivating an anchored function space.
  • Identification: For every β > 0, an anchored self-induced solution exists, and under Assumptions 2.1 and 3.4 it is unique.Existence uses Brouwer’s fixed-point theorem, while Assumption 3.4 rules out nontrivial perturbation directions after removing additive-constant ambiguity.
  • Interpretation: The self-induced solution is also the ordinary Bellman evaluation pair for its induced softmax policy, so Jβ is that policy’s long-run average reward under the original objective.The same Qβ both induces πβ and evaluates its continuation values, eliminating the population-level split of the post-hoc route.
  • Approximation: When every action is optimal at every state, the smoothed value equals the optimal value exactly for every β > 0; otherwise, Theorem 3.8 gives a β-dependent bound.The theorem’s bound uses a constant independent of β and the smallest positive optimality gap Γ.

4 Inference for the Optimal Value

The paper constructs orthogonal inference for the smoothed optimal value using an adjoint weight tied to the self-induced Bellman operator. Under nuisance-rate, variance, overlap, and mixing conditions, the estimator supports asymptotically valid inference for fixed and diverging horizons, including time-varying behavior processes.

  • Adjoint weights: The derivative operator Dβ captures both direct action-value perturbations and softmax-policy changes, while its signed action weights sum to one.The weights need not be nonnegative, but their row-sum and signed-envelope bounds make Dβ an allowable aggregation operator.
  • Adjoint weights: A unique adjoint weight exists under the identification and overlap assumptions, and it annihilates the combined first-order effect of perturbing Qβ.The orthogonality condition accounts for both continuation-value perturbations and induced changes in the softened policy.
  • Orthogonal scores: The orthogonal score combines the smoothed Bellman residual with an adjoint weight to remove first-order nuisance-estimation effects.The score is φβ(Z; J, Q, λ) := J + λ(S, A)(R − J + Vβ(Q)(S′) − Q(S, A)), and the adjoint weight cancels first-order sensitivity to nuisance perturbations.
  • Conditions: The cross-fitted estimator requires second-order nuisance-rate conditions, bounded rewards, positive conditional variation, and uniformly summable mixing for diverging horizons.The fixed-horizon remainder condition is op(N^-1/2), while the diverging-horizon analysis adds conditions controlling time dependence and nuisance replacement.
  • Asymptotic inference: Theorem 4.11 establishes inference under fixed and diverging horizons, with the diverging-horizon result achieving the stated √(NH) rate when the mixing condition controls additional dependence.The Bellman equation makes leading score increments martingale differences, so cross-time covariances vanish despite temporal dependence and H transitions contribute first-order information.
  • Limits and confidence intervals: As β → ∞, the smoothed policy and adjoint quantities converge to those for the uniform policy over tied optimal actions, and the same estimator studentizes both horizon regimes.The resulting confidence interval is asymptotically valid for J∗ in either fixed- or diverging-horizon regimes.

5 Nuisances Estimation

The paper estimates the self-induced Bellman nuisances from one-step transition data using regularized minimax methods, then estimates the adjoint weight with a stabilized empirical criterion. The resulting nuisance rates support valid optimal-value inference when the smoothing parameter balances smoothing bias and statistical error.

  • 5.1 Estimation of the Nuisances: The nuisance pair (Qβ, Jβ) is estimated by minimizing a regularized minimax criterion over test functions of the realized Bellman residual.The residual is nonlinear because the next-state value map Vβ(Q) is self-induced.
  • 5.1 Estimation of the Nuisances: The self-induced Bellman equation is converted into the conditional moment restriction mQβ,Jβ(s, a) = 0 for every state-action pair.The conditional residual compares reward minus J, the self-induced next-state value, and the current action value.
  • 5.1 Estimation of the Nuisances: The nuisance estimator achieves a finite-sample rate under the stated assumptions through residual identification and a regularized empirical criterion.The rate is established with probability at least 1 − δ for n ≥ 2.
  • 5.2 Estimation of the Adjoint Weight: The adjoint weight is estimated by minimizing a feasible empirical criterion over a uniformly bounded class Λ.The criterion replaces unknown derivative weights evaluated at Qβ with estimated quantities, while stabilization prevents degeneracy along poorly sampled directions.
  • 5.2 Estimation of the Adjoint Weight: Replacing Qβ with an estimator contributes error of order βrQ because the derivative-weight map is O(β)-Lipschitz on bounded sets.Combining this bound with the Bellman estimator yields the stated adjoint-weight rate.
  • 5.2 Estimation of the Adjoint Weight: β ≫ log n makes the exponential smoothing bias o(n^-1/2), while the nuisance-rate conditions additionally require β to remain below the relevant statistical scale.These conditions connect smoothing-bias control with the rates needed for valid inference.

6 Numerical Results

Synthetic experiments show that Proposed maintains valid coverage and favorable error behavior as trajectory length, sample size, and behavior-policy complexity increase. In bike repositioning and agentic tool-use applications, Proposed is more stable and closer to reference values than Hardmax-DR.

  • Synthetic Experiments: Hardmax-DR shows persistent undercoverage, while the sequential Hardmax comparator has substantially larger errors and confidence intervals.The sequential comparator can become orders of magnitude more variable.
  • Synthetic Experiments: Across stationary, linear time-varying, and polynomial time-varying behavior mixtures, Proposed remains close to Oracle with stable coverage and decreasing RMSE and interval length as H grows.The behavior-policy regimes have comparable average overlap.
  • Synthetic Experiments: At N = 32,000 and H = 4,000, Proposed’s studentized errors are centered near zero and closely follow the standard normal benchmark across all three behavior-policy regimes.This pattern supports the method’s asymptotic normal approximation.
  • Bike Repositioning: In bike repositioning, Proposed estimates stabilize as N increases, approach the reference optimum, and achieve higher value than Hardmax-DR and Behavior while moving fewer bikes and leaving less demand unmet.At the selected β = 16, the gain in value corresponds to more efficient repositioning rather than simply more intervention.
  • AI Agentic Tool Use: In ToolSandbox, Proposed stays near the empirical reference for Lmin = 1, whereas Hardmax-DR is substantially below the benchmark and exhibits unstable fitted action values and larger Bellman residuals.The instability becomes more severe for the harder Lmin ≥2 tasks.

7 Discussion

The paper builds optimal-value inference around a smooth, self-consistent Bellman fixed point, combining orthogonal scoring with smoothing-bias control. This yields a unified cross-fitted route for fixed and diverging horizons, while motivating extensions beyond the current settings.

  • A self-induced Bellman equation jointly smooths policy generation and continuation-value evaluation into one inferential fixed point.The adjoint weight produces an orthogonal score that removes combined first-order effects, while approximation analysis controls smoothing bias.
  • Estimable Bellman and adjoint-weight nuisances achieve rates sufficient for a cross-fitted inference procedure.
  • The framework provides a unified route to optimal-value inference under both fixed and diverging horizons.
  • Promising extensions include alternative smooth maximum approximations, richer state-action spaces, learned rewards, discounted or finite-horizon objectives, and online deployment.Applications are also suggested for pricing, recommendation, and agentic systems with exploitable domain structure.

Supplementary Material to “Optimal Value Inference for Reinforcement Learning”

The supplementary notation defines the finite-state reinforcement-learning objects and the nuisance quantities used by the orthogonal optimal-value score. These include policies, anchored action values, derivative weights, pooled data laws, and score components.

  • The notation distinguishes state and action spaces, transition and reward functions, stationary policies, and observed one-step trajectory transitions.
  • Jπ denotes long-run average reward, while Qπ is the zero-average fixed-policy relative action-value function.
  • J∗ and Q∗ represent the optimal average reward and common anchored relative action-value function of optimal stationary policies.
  • The orthogonal score φβ, adjoint weight λβ, martingale increment ξi,t, and nuisance remainder bk organize inference for Jβ.

B Proof for Section 2

The appendix proves that optimal policies share a unique anchored relative action-value function satisfying the Bellman optimality equation, then establishes existence and identification under softmax aggregation. The argument uses unichain structure, continuity, compactness, and span contraction.

  • Optimal-policy Bellman characterization: Every optimal stationary policy shares a unique anchored relative action-value function Q∗ satisfying the Bellman optimality equation.The proof uses unichain assumptions, stationary distributions, and the fact that optimal policies select only maximizing actions.
  • Optimal-policy Bellman characterization: The proof identifies Q∗ by constructing a bias function whose greedy actions attain the optimal average reward and satisfy the fixed-policy equation for every optimal policy.
  • Softmax fixed-point existence: Under irreducibility, every stationary policy induces a unichain with an initial-state-independent average reward, and its anchored evaluation is unique and continuous.
  • Softmax fixed-point existence: Continuity and compactness make the softmax evaluation map self-mapping, so Brouwer’s theorem yields an anchored fixed point (Qβ,Jβ).The fixed point corresponds to the policy induced by Qβ and satisfies the self-induced Bellman equation.
  • Derivative aggregation: The derivative aggregation weights have unit row sums and a uniform signed envelope bounded by 1+2 log |A|.
  • Signed aggregation identification: If CAρ(P) < 1, span contraction forces the only anchored solution of the signed aggregation equation to be q=0 and j=0.This establishes uniform signed aggregation identification under the Dobrushin overlap condition.
  • Signed aggregation identification: The contraction argument combines Dobrushin span contraction for P with a CA bound on the span of the aggregation operator.

C.3.3 Proof of Proposition 3.6

The proof establishes uniqueness and quantitative stability of the anchored self-induced Bellman solution, then bounds its approximation error relative to the optimal Bellman pair. Under a positive suboptimality gap, the value bias decays exponentially in the softmax parameter.

  • Uniqueness and stability: The derivative of the softmax value induces an allowable signed aggregation operator, enabling uniqueness arguments for two self-induced Bellman solutions.The path-averaged derivative preserves unit row sums and the signed envelope required by the identification condition.
  • Uniqueness and stability: Assumption 3.4 implies that the anchored self-induced solution is unique through a difference equation involving the path-averaged derivative operator.
  • Uniform bounds: The self-induced Bellman solutions Qβ and Jβ remain uniformly bounded over β under the unichain assumption.This follows because each solution equals the fixed-policy evaluation of its induced stationary policy.
  • Uniform bounds: The quantitative inverse bound is uniform over allowable aggregation operators and independent of β, n, N, and H.
  • Approximation to the optimal Bellman pair: When the minimum suboptimality gap is Γ, the approximation error between the self-induced and optimal Bellman pairs is controlled by the softmax error at Q∗.
  • Approximation to the optimal Bellman pair: 0 ≤ J∗−Jβ ≤ Ce^−βΓ, and when Γ=+∞ the self-induced and optimal pairs coincide exactly for every β>0.

C.4.3 Convergence of the Induced Objects

The smoothed continuation value and induced policy converge toward the optimal continuation value and a uniform policy over maximizing actions. The derivative operator, adjoint weights, and orthogonal score tools are well-defined under the stated assumptions, enabling the inference analysis.

  • Policy-evaluation connection: The optimal pair (Q∗, J∗) is the policy-evaluation pair for the uniform policy over maximizing actions.Thus Qπunif = Q∗ and Jπunif = J∗.
  • Continuation value: The smoothed continuation value Vβ(Qβ) converges to the optimal continuation value V∗ at a bound controlled by β and the action gap Γ.When Γ = +∞, Vβ(Qβ) = V∗ exactly for every β > 0.
  • Induced policy: The induced policy converges to the uniform distribution over actions maximizing Q∗(s, ·).If the action gap Γ is infinite, this convergence is exact for every β > 0.
  • Derivative operator: The derivative operator Dπunif is allowable, and Dβ converges to Dπunif with an error controlled by (1 + β)e^−βΓ.For Γ = +∞, Dβ = Dπunif exactly for every β > 0.
  • Orthogonality tools: The smoothed value map admits a uniform second-order remainder bound, supporting control of nuisance-estimation error in the cross-fitted score.The remainder is quadratic in the Q-estimation error, while the derivative and Hessian bounds are uniform in the smoothing parameter up to the stated β factor.
  • Adjoint weight: The adjoint weight is uniquely identified through the finite-dimensional adjoint equation and normalization under full support.The construction uses the one-dimensional left nullspace of the deterministic adjoint operator.

D.5 Proof of the Inference Theorem

The inference theorem is proved by decomposing the debiased estimator into a leading martingale term and nuisance-dependent remainders. The remainders are negligible in both fixed-horizon and diverging-horizon regimes, yielding a studentized normal limit.

  • Remainder control: The estimator decomposes into a leading term, a nuisance-dependent remainder, and an empirical remainder.Under fixed H, the nuisance-dependent remainder is op(N^−1/2).
  • Central limit argument: In the fixed-horizon regime, bounded independent trajectory contributions satisfy a triangular-array central limit theorem.Slutsky’s theorem then yields the smoothed-value inference result.
  • Remainder control: Under growing H, both principal remainder terms are op((NH)^−1/2).The variance lower bound keeps these remainders negligible after studentization.
  • Central limit argument: The leading array satisfies a martingale-difference structure with uniformly bounded increments and vanishing normalized quadratic-variation error.This supports application of McLeish’s martingale central limit theorem.
  • Inference conclusion: Slutsky’s theorem transfers the central limit result from the smoothed value to the optimal value in the growing-horizon regime.The transfer uses √(NH)(Jβ − J∗)/σ → 0.

D.6 Convergence to Uniform Optimal-Policy Evaluation

As the smoothing parameter increases, the induced inference objects approach those for evaluating the uniform policy over Bellman-optimal actions. The variance estimator is consistent in both fixed- and growing-horizon regimes, supporting unified studentized inference.

  • Uniform-policy connection: The derivative operator and adjoint weight converge to those of the uniform policy over maximizing actions.The adjoint weight λunif exists uniquely, and the convergence rate is controlled by (1 + β)e^−βΓ.
  • Variance connection: The smoothed variance converges to the ordinary fixed-policy-evaluation variance under the uniform optimal policy.When Γ = +∞, λβ = λunif and σ2 = σ2_PE exactly for every β > 0.
  • Variance estimation: The variance estimator is consistent in the fixed-horizon regime, with bσ/σ →p 1.The proof combines nuisance-rate control, quadratic-variation control, and a positive lower bound on σ2.
  • Variance estimation: The same variance consistency conclusion holds in the growing-horizon regime.The growing-horizon nuisance conditions make the replacement and quadratic-variation errors op(1).

D.7.3 Proof of Corollary 4.13

The corollary follows from a studentized asymptotic normality result and supporting uniform identification and empirical-process bounds. These bounds establish stability of the residual-based estimation procedure over the allowable aggregation-operator class.

  • Inference conclusion: The studentized statistic converges in distribution to N(0, 1) in both horizon regimes, yielding a unified Wald interval.The interval follows by inversion of the studentized limit.
  • Allowable operators: The path-averaged derivative operator remains allowable because its weights satisfy the required row-sum and signed-envelope constraints.This allows the residual identity to use derivatives averaged along the segment from Qβ to Q.
  • Identification: Uniform quantitative identification lower-bounds the Bellman residual by the combined Q- and J-deviation over every allowable aggregation operator.The constant is independent of n and β.
  • Empirical control: The empirical criterion is controlled through bounds for the empirical norm, the criterion at (Qβ, Jβ), and residual-increment processes.The constants are uniform over relevant horizons under the pooled support condition.
  • Empirical control: The quadratic test-function penalty absorbs localized empirical fluctuations and leaves an O(η_n^2) remainder.This controls the empirical process contribution in the fast-rate argument.
  • Residual stability: Residual increments are bounded in L2 and almost surely by the combined Q- and J-estimation error.Finite support and full support convert the weighted L2 Q-error into uniform coordinatewise control.

E.3 Proof of Theorem 5.1

The proof establishes quantitative identification and uniform nuisance bounds, then combines empirical criterion comparisons with optimization arguments to obtain the stated rates. Compactness, full support, and localization provide constants uniform over relevant sample and horizon parameters.

  • Quantitative identification: Quantitative identification follows because the operator T_D is bijective under injectivity and full support, making the adjoint criterion strictly positive on the unit sphere.Compactness and continuity convert pointwise positivity into a uniform lower bound for allowable aggregation operators.
  • Uniform adjoint-weight bounds: The adjoint equation and normalization imply a uniform L2 bound for λ_β, with the constant independent of n and β and, under pooled-law support, N and H.The proof then converts the L2 bound into an L∞ bound using the support lower bound.
  • Quantitative identification: The softmax derivative aggregation D_β is allowable, so the identification bound applies to the adjoint equation at the softmax weights.The row-sum identity and signed ℓ1 envelope establish allowability.
  • Empirical control: The proof localizes the unbounded inner optimizations to a deterministic ball, after which finite-dimensional covering and concentration arguments control the empirical criteria.Quadratic penalties dominate linear terms outside the ball, while finite-support empirical norm comparisons hold with probability tending to one.

F.3 Proof of Theorem 5.2 and Corollary 5.3

The proof of Theorem 5.2 compares the population, reference empirical, and feasible criteria, while quantitative identification converts criterion error into an L2 error bound. The resulting stochastic rate follows from the deviation lemmas.

  • Criterion comparisons: The population criterion is compared with a reference empirical criterion and a feasible plug-in criterion, whose discrepancies are Δ_n and Π_n.Δ_n measures sampling deviation, while Π_n measures the additional replacement of Q_β by the estimate bQ.
  • Criterion comparisons: Empirical optimality gives G_β(bλ_β) ≤ 2Δ_n + 2Π_n, after chaining the population and feasible criteria through the reference criterion.The comparison uses λ_β as the population benchmark and the definitions of both discrepancy terms.
  • Rate conclusion: The identification inequality yields an L2 error bound of c^-1(2Δ_n + 2Π_n), and the stochastic rate follows from Lemmas F.4 and F.5.Thus criterion deviations directly control the error of the estimated adjoint weight.
Loading 2609.09981v1…