Bellman Calibration for V-Learning in Offline Reinforcement Learning

The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.

40,892 characters

Bellman Calibration for $V$-Learning in Offline Reinforcement Learning



\maketitle


\begin{abstract}
Reliable long-horizon value prediction is difficult in offline reinforcement
learning because fitted value methods combine bootstrapping, function
approximation, and distribution shift, while standard guarantees often require
Bellman completeness or realizability. We introduce \emph{Bellman calibration},
a weak reliability criterion requiring that states assigned similar predicted
values have average Bellman targets that agree with those predictions. This
criterion yields a scalar calibration error for diagnosing systematic numerical
miscalibration, which we estimate from off-policy data using doubly robust
Bellman target estimates. We then propose \emph{Iterated Bellman Calibration}, a
model-agnostic post-hoc procedure that recalibrates any learned value predictor
by fitting a one-dimensional map of its original prediction, with histogram and
isotonic variants. We prove finite-sample guarantees showing that Bellman
calibration error is controlled at one-dimensional nonparametric rates without
Bellman completeness or value-function realizability. Our value-error bounds
separate statistical estimation, finite-iteration, and approximation errors, clarifying when calibration improves value prediction and when
its gains are limited by the information in the original predictor or insufficient coverage.
\end{abstract}
\section{Introduction}

Many applications require predicting the long-term consequences of a decision
policy in a sequential, stochastic environment. We study this problem in a
Markov decision process (MDP), where the goal is to estimate the long-run value
of a target policy~\(\pi\), possibly from data collected under a different
behavior policy. This off-policy value-prediction problem arises throughout RL
and in many application domains: clinicians anticipate long-term outcomes under
proposed treatment rules \citep{van2019calibration}; online platforms estimate
customer lifetime value and retention under alternative recommendation
strategies \citep{theocharous2015ad,maystre2022temporally,xue2025auro}; and
economists study downstream effects of counterfactual programs
\citep{rust1987optimal,cowgill2019economics}. In these settings, systematic
miscalibration can distort policy comparisons, misstate long-run effects, and
lead to poor decisions.

Modern predictors such as neural networks and gradient-boosted trees are often
miscalibrated: their numerical predictions may systematically differ from the
quantities they are intended to estimate because of misspecification, limited
data, or distribution shift
\citep{zadrozny2001obtaining,niculescu2005predicting,bella2010calibration,guo2017calibration}.
For long-horizon value prediction, this concern is amplified by bootstrapping:
fitted value methods regress on targets that themselves depend on previous
value estimates, so finite-iteration error, approximation error, and off-policy
shift can propagate into the final value scale
\citep{gordon1995stable,tsitsiklis1996analysis,munos2008finite,
farahmand2010error,agarwal2021deep}. Existing guarantees typically control
these errors by imposing strong structure, such as Bellman completeness,
realizability, linear approximation, or finite state spaces
\citep{chen2019information,xie2022role,meyn2024projected,xie2021batch}. Min--max
alternatives relax some aspects of fitted value iteration but introduce their
own challenges, including saddle-point optimization, rich critic or dual
classes, and strong coverage requirements
\citep{dai2018sbeed,uehara2020minimax,jin2021bellman,xie2021batch}.

Calibration is a classical reliability property: among units assigned the same
predicted value, the corresponding outcomes should agree with that value on
average. In population terms, a calibrated predictor satisfies
\(f(X) = E[Y \mid f(X)]\). This suggests an RL analogue. Informally, a value
predictor is calibrated if, among states assigned the same predicted value, the
average target-policy Bellman backup matches that value; that is,
\(v(S) = E_\pi\{R + \gamma v(S') \mid v(S)\}\). This is a weak but meaningful
form of Bellman consistency: it constrains only the scalar prediction rather
than the full state-to-value mapping, while still ruling out systematic under-
or overestimation within level sets of the prediction.

Despite its central role in supervised learning, where predictions are
calibrated against observed labels, empirical frequencies, or conditional means
\citep{lichtenstein1977calibration,platt1999probabilistic,zadrozny2001obtaining,
vovk2005algorithmic,gupta2020distribution,gupta2021distribution,
whitehouse2024orthogonal}, calibration remains comparatively underexplored for
long-horizon value prediction in RL. Table~\ref{tab:rl-calibration-motivation}
highlights why this is problematic: value estimates can be highly informative
yet numerically misaligned because of temporal shift, off-policy fitting, finite
Bellman iteration, or approximation and optimization error. Unlike in supervised
learning, however, the calibration target is not directly observed; long-run
returns must be inferred from one-step transitions through Bellman structure.
We therefore study post-hoc Bellman calibration: a restricted recalibration of a
pretrained value predictor that corrects systematic scale errors without a new
high-dimensional Bellman fit, with finite-sample guarantees that do not require
realizability or Bellman completeness.

\begin{table}[t]
\centering
\small
\setlength{\tabcolsep}{4pt}
\caption{Why RL value predictions can be informative but poorly calibrated.}
\label{tab:rl-calibration-motivation}
\begin{tabularx}{\linewidth}{p{0.47\linewidth} p{0.45\linewidth}}
\toprule
\textbf{Failure mode} & \textbf{Calibration correction} \\
\midrule

Temporal or distribution shift: value estimates reflect past rewards, policies,
or environments rather than the current target setting
\citep{kumar2020conservative}.
&
Update the value scale using recent or gold-standard trajectories, while
retaining signal from the historical model.
\\
\midrule

Off-policy fitting: a high-capacity value model trained on large
behavior-policy data can be informative but mis-scaled for the target-policy
state--action distribution \citep{fujimoto2019off}.
&
Use the large off-policy sample to learn the value predictor, then recalibrate its
scale on a smaller on-policy or target-policy reference sample.
\\
\midrule

Finite Bellman iteration: computational limits can force early stopping or a
shorter effective horizon, mis-scaling values for the intended return target
\citep{munos2008finite}.
&
Re-align predictions to the intended horizon without rerunning the full Bellman
iteration.
\\
\midrule

Approximation and optimization error: misspecified value classes, restricted
critics, or unstable saddle-point training can yield biased value predictions
\citep{uehara2021finite}.
&
Remap the biased but informative prediction to observed or Bellman-consistent values,
rather than requiring exact specification.
\\

\bottomrule
\end{tabularx}
\end{table}


\textbf{Contributions.}
We connect two largely separate literatures: post-hoc calibration for
supervised prediction and long-horizon value learning in RL. Existing work gives
rich methods for learning value functions, but much less theory for
model-agnostic reliability assessment and post-hoc correction of already learned
value predictors. Our contributions are:

\begin{enumerate}[leftmargin=1.5em,topsep=0.2em,itemsep=0.25em,parsep=0pt,partopsep=0pt]
\item We formalize \textbf{Bellman calibration}, a dynamic analogue of
supervised calibration for infinite-horizon value prediction. Bellman consistency
implies calibration, but calibration is weaker: predictions need only match
average Bellman backups among states assigned similar values.
\item We propose \textbf{\(\ell^2\)-Bellman calibration error} as a scalar
diagnostic for systematic value miscalibration and develop debiased off-policy
estimators of this error. We also prove a \textbf{calibration-refinement} bound
showing that value error decomposes into calibration error and the approximation
error of the best predictor based only on the original model output.
\item We introduce \textbf{post-hoc Bellman calibration} via histogram binning
and isotonic regression. The methods apply to any value predictor and use
doubly robust Bellman targets for off-policy data.
\item We prove \textbf{finite-sample guarantees} for histogram calibration,
controlling both \(\ell^2\)-Bellman calibration error and value error. The
bounds require neither Bellman completeness nor realizability and separate
statistical, auxiliary-model, and iteration errors.
\end{enumerate}

\subsection{Related work}

\textbf{Post-hoc calibration.}
Our work builds on post-hoc calibration for supervised prediction
\citep{zadrozny2001obtaining,zadrozny2002transforming,niculescu2005predicting,
bella2010calibration,guo2017calibration}; see \citet{roth2022uncertain} for an
overview. This literature calibrates static predictions against observed labels,
empirical frequencies, or conditional means. We study long-horizon value
predictions in MDPs, where returns are not directly observed and must be inferred
through Bellman structure. We are also related to causal calibration for static
treatment-effect prediction \citep{van2023causal,whitehouse2024orthogonal}, but
our setting is dynamic and long-horizon, with calibration targets defined by
value functions rather than one-step conditional effects. The closest work is \citep{van2025automaticDRL}, who use isotonic post-hoc
calibration of \(Q\)-functions inside Double RL policy-value estimators
\citep{kallus2020double,kallus2022efficiently}. Their calibration step is used
as an auxiliary-model correction for a global value estimator. We instead study calibrated value prediction directly and give finite-sample
guarantees for both Bellman calibration error and value error. The same framework also applies to \(Q\)-function calibration by replacing
importance-weighted FVI with unweighted FQE and treating each state-action pair
as the state.


\textbf{Relation to Bellman learning and fine-tuning.}
Bellman calibration complements methods that change value learning itself,
including minimax or adversarial Bellman objectives
\citep{uehara2020minimax,uehara2023offline,xie2021batch,di2023pessimistic},
conservative updates \citep{kumar2020conservative,an2021uncertainty}, and
structural assumptions such as linearity, low rank, representations, or
discretization
\citep{shah2020sample,chang2022learning,peng1993convergence,van2006performance}.
It can be applied after any such method because it only needs scalar value
predictions and a reference sample. Unlike offline-to-online transfer,
critic/policy fine-tuning, or safe policy improvement
\citep{rusu2016progressive,nair2020awac,lee2022offline,laroche2019safe},
Bellman calibration fixes the target policy, value model, representation, and
Bellman learner, and fits only a one-dimensional post-hoc map to the target
value scale. Thus it is an output-scale correction rather than RL fine-tuning,
with finite-sample guarantees for calibration and value error. Related work on
calibrated dynamics uncertainty, conformal sets, and distributional RL targets
concerns different objects
\citep{malik2019calibrated,zhang2023conformal,sun2023conformal,
bellemare2017distributional,dabney2018implicit}.

\section{Calibration for Value Functions}
\subsection{Setup and Notation}

We consider an MDP with state space \(\mathcal S\), discrete action space
\(\mathcal A\), initial-state distribution \(\rho\) for \(S_0\), transition kernel
\(P(s'\mid s,a)\), reward function \(r_0(s,a)\), and discount factor
\(\gamma\in[0,1)\). Data are collected under a behavior policy
\(b_0(a\mid s)\). Each calibration sample is an i.i.d.\ transition
\((S,A,R,S')\), where \((S,A)\sim \rho\times b_0\),
\(S'\sim P(\cdot\mid S,A)\), and
\(R=r_0(S,A)+\varepsilon\) with \(E[\varepsilon\mid S,A]=0\). We observe a calibration sample
\(\mathcal C_n:=\{(S_i,A_i,R_i,S_i')\}_{i=1}^n\).

Let \(\pi(a\mid s)\) be the target policy. The value function under \(\pi\) is \(v_0(s)
=
E_{\pi}[\sum_{t=0}^\infty \gamma^t R_t
\,|\, S_0=s]\), where \(E_\pi\) denotes the law induced by
\(A_t\sim\pi(\cdot\mid S_t)\) and
\(S_{t+1}\sim P(\cdot\mid S_t,A_t)\).

For a state-action function \(f\) and state function \(v\), define
\[
\begin{aligned}
(\pi f)(s)&:=\sum_{a\in\mathcal A}\pi(a\mid s)f(s,a),\\
(b_0 f)(s)&:=\sum_{a\in\mathcal A}b_0(a\mid s)f(s,a),\\
(Pv)(s,a)&:=E[v(S')\mid S=s,A=a].
\end{aligned}
\]
Write
\[
w_\pi:=\pi/b_0,\qquad
r_{0,\pi}:=\pi r_0,\qquad
P_\pi:=\pi P,\qquad
\mathcal T_\pi v := r_{0,\pi}+\gamma P_\pi v
\]
for the policy Bellman operator. The value function is the unique bounded fixed
point \citep{bellman1952theory,bellman1966dynamic}
\begin{equation}
\label{eqn::bellman}
v_0=\mathcal T_\pi v_0 .
\end{equation}
For a measure \(\mu\) on \(\mathcal S\), write
\[
\|f\|_{2,\mu}
:=
\left\{\int f(s)^2\,\mu(ds)\right\}^{1/2}.
\]
Let \(L^2(\rho)\) denote the space of square-integrable state functions under
\(\rho\). Let \(\|f\|_{n,S,A}\) and \(\|g\|_{n,S'}\) denote empirical \(L^2\)
norms over \(\{(S_i,A_i)\}_{i=1}^n\) and \(\{S_i'\}_{i=1}^n\), respectively.
We write \(\lesssim\) for inequalities up to absolute constants and
\([B]:=\{1,\ldots,B\}\).


\subsection{Bellman Calibration: A Minimal Requirement}

Let \(\hat v\) be an estimated value function for the target policy \(\pi\),
fit on data independent of the calibration sample \(\mathcal C_n\). Our goal is
not to replace the underlying value-learning procedure, but to impose a weak
post-hoc Bellman consistency requirement on its output. Throughout, we call the
scalar \(\hat v(S)\) the predicted value; in the supervised calibration
literature, this same scalar is often called a prediction score.

A natural starting point is \emph{statewise Bellman consistency}:
\[
\hat v(S)
\approx
E_\pi\!\left[R+\gamma \hat v(S')\mid S\right].
\]
Equivalently, the Bellman residual
\(R+\gamma \hat v(S')-\hat v(S)\) should have conditional mean zero given the
full state. In high-dimensional or continuous state spaces, this is a strong
requirement: checking or enforcing it requires estimating a state-dependent
conditional mean and is closely tied to structural assumptions such as Bellman
completeness \citep{chen2019information}.

We instead require Bellman consistency only after grouping states by their
predicted value:
\[
\hat v(S)
\approx
E_\pi\!\left[R+\gamma \hat v(S')\mid \hat v(S)\right].
\]
Thus, predictions should agree on average with their Bellman targets within
groups of states assigned the same predicted value \(\hat v(S)\). This is the
dynamic analogue of post-hoc calibration in supervised prediction, where
predictions are required to be correct on average conditional on their own
numerical output
\citep{zadrozny2002transforming,niculescu2005predicting,guo2017calibration}.
The benefit is that a high-dimensional Bellman moment is reduced to a
one-dimensional conditional moment, enabling post-hoc correction without
requiring the full fitted Bellman update to be correctly specified.

\textbf{Bellman calibration.}
For any candidate value function \(v\), define the Bellman-calibration map
\begin{equation}
\label{eqn::calibrationmap}
\Gamma_0(v)(s)
:=
E_\pi\!\left[R+\gamma v(S') \mid v(S)=v(s)\right].
\end{equation}
We say that \(v\) is \emph{Bellman calibrated} if
\(v(S)=\Gamma_0(v)(S)\) almost surely, or equivalently,
\[
E_\pi\!\left[R+\gamma v(S')-v(S)\mid v(S)\right]=0
\quad\text{almost surely}.
\]


\textbf{A necessary but weak condition.}
The true value function \(v_0\) is Bellman calibrated. The Bellman equation gives
\(v_0(S)=E_\pi[R+\gamma v_0(S')\mid S]\); conditioning on the coarser predicted value
\(v_0(S)\) yields
\[
v_0(S)
=
E_\pi[R+\gamma v_0(S')\mid v_0(S)]
=
\Gamma_0(v_0)(S).
\]
Thus Bellman consistency implies Bellman calibration. The converse need not
hold: because calibration only conditions on the scalar predicted value \(v(S)\),
state-level errors can average out within predicted-value groups
\citep{gupta2020distribution,van2023causal}. Hence Bellman calibration is a
minimal reliability requirement, not a guarantee of value accuracy.

\textbf{Reward-model interpretation.}
Define the reward implied by a value predictor \(v\) as
\[
r_{\pi,v}(s):=v(s)-\gamma P_\pi v(s).
\]
This is the one-step reward under which \(v\) would satisfy the Bellman
equation for policy \(\pi\). Bellman calibration is equivalent to
\[
E_\pi\!\left[R-r_{\pi,v}(S)\mid v(S)\right]=0.
\]
Thus, among states assigned the same predicted long-run value, the reward
implied by \(v\) matches the true one-step reward on average. When
\(\gamma=0\), this reduces to ordinary regression calibration
\citep{roth2022uncertain}.

\subsection{A Calibration--Refinement Bound for Value Error}

We next relate Bellman calibration to value prediction error. The key point is
that calibration is a post-processing operation: it can correct systematic
Bellman residuals among states with the same predicted value, but it cannot
recover information lost by reducing the state \(S\) to \(\hat v(S)\).

For a candidate value function \(v\), define the \(\ell^2\) \textbf{Bellman calibration
error}
\begin{equation}
\label{eqn::calerror}
\mathrm{Cal}_{\ell^2}^2(v)
:=
\|v-\Gamma_0(v)\|_{2,\rho}^2
=
E_\rho\!\left[
  \left\{
    E_\pi[R+\gamma v(S')-v(S)\mid v(S)]
  \right\}^2
\right].
\end{equation}
This criterion is zero exactly when \(v\) is Bellman calibrated, and measures
the remaining Bellman residuals conditional on the predicted value.

The value predictors generated by the original prediction \(\hat v(S)\) form the
class
\[
\mathcal V_{\hat v}
:=
\{g\circ\hat v:g:\mathbb R\to\mathbb R \text{ measurable}\},
\qquad
\Pi_{\hat v}
:=
\text{\(L^2(\rho)\)-projection onto }\mathcal V_{\hat v}.
\]
Define the projected transition by
\[
P_{\pi,\hat v}
:=
\Pi_{\hat v}P_\pi,
\qquad
P_{\pi,\hat v}f(s)
=
E_\pi[f(S')\mid \hat v(S)=\hat v(s)].
\]

Define the discounted projected concentrability by
\[
\mathcal C_{\hat v,\gamma}
:=
\left\{(1-\gamma)\sum_{t=0}^\infty
\gamma^t
\left\|
\frac{d(\rho P_{\pi,\hat v}^t)}{d\rho}
\right\|_\infty^{1/2}
\right\}^2 .
\]

\begin{enumerate}[label=\textbf{A\arabic*}, ref={A\arabic*}, leftmargin=1.5em, series=cond]
\item \label{cond::A1}
\textbf{Projected concentrability.}
\(\mathcal C_{\hat v,\gamma}<\infty\).
\end{enumerate}
When \(\rho\) is stationary under \(P_{\pi}\), it is also stationary under
\(P_{\pi,\hat v}\) by Lemma~\ref{lemma:aggregated-stationary}, so
\(\mathcal C_{\hat v,\gamma}=1\). More generally,
\(\mathcal C_{\hat v,\gamma}\) measures distribution drift from \(\rho\): it is
small when projected rollouts remain comparable to \(\rho\), and large when they
concentrate where \(\rho\) has little mass.

\begin{theorem}[Calibration--refinement bound]
\label{theorem::calrefine}
Under \ref{cond::A1},
\[
\|\hat v-v_0\|_{2,\rho}
\le
\frac{\sqrt{\mathcal C_{\hat v,\gamma}}}{1-\gamma}
\left\{
\mathrm{Cal}_{\ell^2}(\hat v)
+
\min_{\theta:\mathbb R\to\mathbb R}
\|\theta\circ\hat v-v_0\|_{2,\rho}
\right\}.
\]
\end{theorem}

Theorem~\ref{theorem::calrefine} gives a post-processing guarantee: value error
is controlled by Bellman calibration error \(\mathrm{Cal}_{\ell^2}(\hat v)\)
plus the refinement error $\min_{\theta:\mathbb R\to\mathbb R}
\|\theta\circ\hat v-v_0\|_{2,\rho},$ the error of the best value predictor that depends on the state only through
\(\hat v(S)\). The calibration error measures systematic Bellman residuals
within levels of \(\hat v(S)\), whereas the refinement error measures the
remaining value variation not captured by \(\hat v(S)\). Thus, calibration can
remove Bellman miscalibration using only a post-processing map of the original
prediction, but it cannot recover information about \(v_0(S)\) absent from
\(\hat v(S)\). In particular, when calibration error is driven to zero, value
error is controlled, up to the projected concentrability and discount factors,
by the refinement error. This mirrors classical calibration--refinement
decompositions in classification and regression
\citep{murphy1973new,degroot1983comparison,van2023causal,whitehouse2024orthogonal}.
The factor \(\sqrt{\mathcal C_{\hat v,\gamma}}/(1-\gamma)\) plays the same role
as the concentrability and discount penalties in classical FVI/FQE error bounds
\citep{munos2008finite}.

\subsection{Evaluating Bellman Calibration Error with Doubly Robust Bellman Targets}
\label{sec:bellman-calibration-error}

We now focus on estimating \(\mathrm{Cal}_{\ell^2}(\hat v)\), the component of
Theorem~\ref{theorem::calrefine} that can be evaluated from transition data
and improved without refitting the value predictor. This makes Bellman calibration error both
a diagnostic for systematic Bellman residuals within the level sets of a fixed
predictor \(\hat v\) and an objective for post-hoc calibration.

Because data are generated under the behavior policy \(b_0\), we estimate the
statewise Bellman target using a doubly robust Bellman pseudo-outcome, extending
the calibration target estimates of \citep{xu2022calibration,van2023causal} to
dynamic settings. Let \(\widehat w_\pi\) estimate \(w_\pi:=\pi/b_0\). For a
fixed \(v\), define
\[
q_v(s,a)
:=
E\{R+\gamma v(S')\mid S=s,A=a\}.
\]
Let \(\hat q_v\) estimate \(q_v\). For \(O=(S,A,R,S')\), set
\[
\widehat Y_v(O)
:=
(\pi \hat q_v)(S)
+
\widehat w_\pi(A\mid S)
\{R+\gamma v(S')-\hat q_v(S,A)\},
\qquad
\widehat{\mathcal T}_\pi v(s)
:=
E\{\widehat Y_v(O)\mid S=s\}.
\]
The next result gives the conditional bias of this pseudo-outcome.

\begin{theorem}[Doubly robust Bellman target]
\label{theorem::DRpseudo}
For any fixed \(v\),
\[
E\!\left[
\{\widehat{\mathcal T}_\pi v-\mathcal T_\pi v\}(S)
\mid v(S)=t
\right]
=
E\!\left[
  b_0\!\left\{(w_\pi-\widehat w_\pi)(\hat q_v-q_v)\right\}(S)
  \mid v(S)=t
\right].
\]
Consequently, \(E\{\widehat Y_v(O)\mid v(S)\}
=
E\{(\mathcal T_\pi v)(S)\mid v(S)\}\) if either
\(\widehat w_\pi=w_\pi\) or \(\hat q_v=q_v\).
\end{theorem}

This construction includes importance weighting \((\hat q_v=0)\) and
model-based Bellman-target evaluation \((\widehat w_\pi=0)\) as special cases.
The theorem shows that either nuisance estimator suffices to recover the
prediction-conditional Bellman target.

To estimate the proposed calibration error, we use a \textbf{cross-fitted debiased moment estimator}.
Let \(U_i:=v(S_i)\) and \(\widehat Y_i:=\widehat Y_v(O_i)\). Following
\citet{xu2022calibration}, we estimate the squared calibration error by
\[
\widehat{\mathrm{Cal}}_{\ell^2,\mathrm{db}}^2(v)
:=
\frac1n\sum_{i=1}^n
\{\widehat Y_i-U_i\}
\{\widehat m_{-i}(U_i)-U_i\},
\]
where \(\widehat m_{-i}\) is fit without observation \(i\) to estimate
\(u\mapsto E(\widehat Y_v\mid v(S)=u)\). The population identity behind this
estimator is
\[
E\!\left[
\{\widehat Y_v-v(S)\}
\left\{E(\widehat Y_v\mid v(S))-v(S)\right\}
\right]
=
E\!\left[
\left\{E(\widehat Y_v\mid v(S))-v(S)\right\}^2
\right].
\]
By Theorem \ref{theorem::DRpseudo}, this equals
\(\mathrm{Cal}_{\ell^2}^2(v)\), up to function approximation error.


\section{Post-hoc Bellman Calibration}
\label{sec:posthoc-calibration}

\subsection{Iterated Bellman Calibration}
\label{sec:iterated-bellman-calibration}

Algorithm~\ref{alg::cal-gen} gives a post-hoc FVI-style procedure that
transforms an initial value predictor \(\hat v\) into a calibrated predictor
\(V_{\mathrm{cal}}=V_K=g_K\circ\hat v\). Starting from \(V_0=\hat v\), each
iteration forms doubly robust Bellman targets \(\widehat Y_{V_k}(O_i)\) and
regresses them on the fixed one-dimensional inputs \(\hat v(S_i)\) over a
calibrator class \(\mathcal G\), yielding \(V_{k+1}=g_{k+1}\circ\hat v\).
Equivalently, for
\(\mathcal V_{\hat v}(\mathcal G):=\{g\circ\hat v:g\in\mathcal G\}\), the
algorithm is a projected Bellman update restricted to functions of the original
prediction. This avoids high-dimensional function approximation while correcting
Bellman miscalibration in \(\hat v\); the contraction results below imply that
\(O\{\log(1/\varepsilon)/(1-\gamma)\}\) iterations suffice to reach optimization
error \(\varepsilon\).

\begin{algorithm}[h]
\caption{\textbf{Iterated Bellman Calibration}}
\label{alg::cal-gen}
\begin{algorithmic}[1]
\STATE \textbf{Input: } \(\hat v\), \(\mathcal C_n=\{O_i=(S_i,A_i,R_i,S_i')\}_{i=1}^n\), pseudo-outcome \(v\mapsto\widehat Y_v\), class \(\mathcal G\), iterations \(K\)
\STATE Initialize \(V_0=\hat v\)
\FOR{\(k=0,\ldots,K-1\)}
  \STATE \(V_{k+1}=g_{k+1}\circ\hat v\), where $ g_{k+1}\in\arg\min_{g\in\mathcal G}\sum_{i=1}^n
  \{\widehat Y_{V_k}(O_i)-g(\hat v(S_i))\}^2 .$
\ENDFOR
\STATE \textbf{Output: } \(V_K\)
\end{algorithmic}
\end{algorithm}

At the population level, the iteration approximates the projected Bellman
operator \(\mathcal B_{\hat v} f
:=
\Pi_{\hat v} r_{0,\pi} + \gamma P_{\pi,\hat v} f\), whose fixed point over functions of \(\hat v(S)\) has zero Bellman calibration
error. Exact finite-sample recovery of this projected fixed point would
generally require realizability in \(\mathcal V_{\hat v}(\mathcal G)\) and
Bellman completeness of the fitted update \citep{munos2008finite}. We instead
seek post-hoc Bellman calibration guarantees without imposing these conditions.
We therefore instantiate Algorithm~\ref{alg::cal-gen} with one-dimensional
histogram and isotonic calibrators \citep{stone1977consistent,barlow1972isotonic}.
These are dynamic analogues of histogram binning
\citep{zadrozny2001obtaining,zadrozny2002transforming,gupta2021distribution}
and isotonic calibration
\citep{zadrozny2002transforming,niculescu2005predicting,van2023causal,
van2025generalized}, and they admit finite-sample Bellman calibration
guarantees without Bellman completeness.



\subsection{Histogram Calibration}
\label{sec:hist}

Histogram calibration instantiates Algorithm~\ref{alg::cal-gen} with a
piecewise-constant calibrator. Partition the initial values
\(\{\hat v(S_i)\}_{i=1}^n\) into ordered bins \(I_1,\ldots,I_B\), using either
empirical quantiles (\emph{equal-mass}) or uniform discretization
(\emph{equal-width}). We take
\[
\mathcal G_B
:=
\mathrm{span}\{\mathbf 1_{I_b}:b\in[B]\},
\qquad
\mathcal H_B(\hat v)
:=
\{g\circ\hat v:g\in\mathcal G_B\},
\]
so every \(h\in\mathcal H_B(\hat v)\) is a value predictor that is constant
within bins of the original prediction. The bins may be data-adaptive, but
\(B\) is deterministic and may grow with \(n\).

With this class, each iteration simply averages the fitted Bellman targets
within each bin:
\[
g_{k+1}(t)
=
\frac{1}{n_b}
\sum_{i:\hat v(S_i)\in I_b}
\widehat Y_i^{(k)},
\qquad
t\in I_b,
\]
where \(n_b:=\sum_{i=1}^n\mathbf 1\{\hat v(S_i)\in I_b\}\). Thus, histogram
calibration is fitted Bellman iteration on a finite aggregation of the initial
predicted value. At convergence, the output approximately satisfies the empirical aggregated
Bellman equation within each bin:
\[
V_K(s)
\approx
E_n\!\left[
\widehat Y_{V_K}(O)
\,\middle|\,
\hat v(S)\in I_b
\right],
\qquad \hat v(s)\in I_b .
\]
This is the empirical analogue of Bellman calibration and is the key property
used in the next result.

 \textbf{Calibration error.}
We next give finite-sample, finite-iteration bounds for the Bellman calibration
error \eqref{eqn::calerror}. The analysis uses the following regularity
conditions.

\begin{enumerate}[label=\textbf{C\arabic*}, ref={C\arabic*}, leftmargin=1.5em, series=cond]

\item \label{cond::C1}
\textbf{Boundedness.}
\(R\), \(w_\pi\), \(\widehat w_\pi\), \(\hat v\), the Bellman targets \(q_f\),
and their estimates \(\hat q_f\) are uniformly bounded by \(M<\infty\) for all
\(f\) considered.

\item \label{cond::C1b}
\textbf{Sample splitting.}
The auxiliary estimators \(\widehat w_\pi\) and \(v\mapsto\hat q_v\), and the
initial predictor \(\hat v\) are trained on data independent of
\(\mathcal C_n\).

\item \label{cond::C2}
\textbf{Stability of the Bellman-target regression.}
For all \(f,g\in\mathcal H_B(\hat v)\) with
\(\|f\|_\infty,\|g\|_\infty\le M\),
\[
\|\hat q_f-\hat q_g\|_{n,S,A}
\le
L\,\|f-g\|_{n,S'} .
\]
\end{enumerate}

These conditions are mainly technical. Boundedness can be enforced by clipping
or truncation, and sample splitting can be replaced by cross-fitting. Condition
\ref{cond::C2} controls the complexity introduced by the map
\(v\mapsto\hat q_v\); it holds trivially for the importance-weighted target
\((\hat q_v=0)\), and holds with \(L=1\) for cellwise estimates of
\(E\{R+\gamma f(S')\mid S,A\}\).

\begin{theorem}[Calibration error for histogram binning]
\label{theorem::Calerrorhist}
Assume \ref{cond::C1}--\ref{cond::C2}. Then there is a constant
\(C<\infty\) such that, for any \(K\in\mathbb N\), with probability at least
\(1-\delta\),
\begin{align*}
\mathrm{Cal}_{\ell^2}(V_K)
\le\;&
C\left\{
\sqrt{\frac{B}{n}\log\!\left(\frac{n}{B}\right)}
+
\sqrt{\frac{\log(1/\delta)}{n}}
\right\} \\
&+
\big\|b_0\{(\widehat w_\pi-w_\pi)
(\widehat q_{V_K}-q_{V_K})\}\big\|_{2,\rho}  +
\big\|
\widehat{\mathcal T}_\pi V_K
-
\widehat{\mathcal T}_\pi V_{K-1}
\big\|_{2,\rho}.
\end{align*}
\end{theorem}

The bound separates three errors: the statistical error of one-dimensional
histogram calibration, matching classical rates when the calibration target is
observed directly
\citep{gupta2020distribution,gupta2021distribution,van2025generalized}; the
doubly robust auxiliary-model error from Theorem~\ref{theorem::DRpseudo}; and
the finite-iteration error, which decays geometrically as \(\gamma^K\) under the
contraction conditions in Appendix~\ref{appendix::convergence}, as in fitted
value iteration \citep{munos2008finite}. The leading calibration rate does not
accumulate over the horizon: \(\gamma\) enters only through the finite-iteration
and auxiliary-model terms. This reflects that Bellman calibration is a one-step
conditional prediction problem, even though translating calibration into value
accuracy still depends on discounting and coverage
(Theorem~\ref{theorem::calrefine}).

\textbf{Value error.}
We next show that post-hoc calibration does not add error beyond the
information loss from restricting to the histogram calibrator class, while it can
remove Bellman miscalibration in the original predictor.

Let \(\Pi_B\) denote the \(L^2(\rho)\)-projection onto
\(\mathcal H_B(\hat v)\), i.e.,
\[
\Pi_B q:=\arg\min_{h\in\mathcal H_B(\hat v)}\|q-h\|_{2,\rho},
\qquad
\mathcal B_{\pi,B}:=\Pi_B\mathcal T_\pi,
\qquad
V_B^\star=\mathcal B_{\pi,B}V_B^\star .
\]
Write \(P_{\pi,B}:=\Pi_B P_\pi\), so that, for
\(\hat b(s)=b\) when \(\hat v(s)\in I_b\),
\[
P_{\pi,B}f(s)
=
E_\pi[f(S')\mid \hat v(S)\in I_{\hat b(s)}].
\]
Finally, define the aggregated discounted concentrability by
\[
\mathcal C_{B,\gamma}
:=
\left\{(1-\gamma)\sum_{t=0}^\infty
\gamma^t
\left\|
\frac{d(\rho P_{\pi,B}^t)}{d\rho}
\right\|_\infty^{1/2}
\right\}^2 .
\]

\begin{enumerate}[label=\textbf{C\arabic*}, ref={C\arabic*}, leftmargin=1.5em, resume=cond]
\item \label{cond::Ccoverage}
\textbf{Aggregated projected concentrability.}
\(\mathcal C_{B,\gamma} < \infty\).
\end{enumerate}


\begin{theorem}[Value error for histogram calibration]
\label{theorem::regretHist}
Assume \ref{cond::C1}--\ref{cond::Ccoverage}. Then there exists a constant
\(C<\infty\) such that, for any \(K\in\mathbb N\), with probability at least
\(1-\delta\),
{\small
\begin{align*}
\|V_K-v_0\|_{2,\rho}
\le\;&
\gamma^K\|\hat v-V_B^\star\|_{\infty}
+
\frac{\sqrt{\mathcal C_{B,\gamma}}}{1-\gamma}
\min_{h\in\mathcal H_B(\hat v)}\|h-v_0\|_{2,\rho}
\\
&+
C\frac{\sqrt{\mathcal C_{B,\gamma}}}{1-\gamma}
\Bigg[
  \sqrt{\frac{B}{n}\log\!\left(\frac{n}{B}\right)}
  +
  \sqrt{\frac{\log(K/\delta)}{n}}
 +
\max_{0\le j\le K}
\big\|
b_0\{
(\widehat w_\pi-w_\pi)
(\widehat q_{V_j}-q_{V_j})
\}
\big\|_{2,\rho}
\Bigg].
\end{align*}
}
\end{theorem}
\textbf{Proof idea.}
The result avoids realizability and Bellman completeness for the original value
class because completeness holds after aggregation. For any
\(f\in\mathcal H_B(\hat v)\), the aggregated transition \(P_{\pi,B}f\) is
binwise constant in \(\hat v\), so \(P_{\pi,B}f\in\mathcal H_B(\hat v)\)
and hence \(\mathcal B_{\pi,B}f\in\mathcal H_B(\hat v)\). The proof uses
sup-norm contraction to obtain the aggregated fixed point, then propagates
\(\rho\)-norm one-step regression errors through a discounted resolvent
controlled by \(\mathcal C_{B,\gamma}\). It also bounds
\(V_B^\star-v_0\) by a histogram analogue of
Theorem~\ref{theorem::calrefine}. Unlike prior discretization arguments for
Bellman consistency
\citep{whitt1978approximations,peng1993convergence,van2006performance,
chen2019information,xie2021batch}, we discretize \(\hat v(S)\) to
target Bellman calibration.

\textbf{Discussion.}
Theorems~\ref{theorem::Calerrorhist} and~\ref{theorem::regretHist} separate
calibration from value accuracy. With known importance weights and negligible
iteration error, histogram calibration drives Bellman calibration error to zero
at the one-dimensional rate \(\sqrt{(B/n)\log(n/B)}\). Value error contains the
same stochastic term, but also includes the prediction-only approximation error $(\sqrt{\mathcal C_{B,\gamma}})/(1-\gamma)
\min_{h\in\mathcal H_B(\hat v)}\|h-v_0\|_{2,\rho},$ the cost of restricting the calibrated predictor to binned transformations of
the original prediction. Thus \(B\) controls the usual bias--variance tradeoff:
coarse bins may discard information in \(\hat v\), while fine bins increase
variance. The coverage factor \(\mathcal C_{B,\gamma}\) is the histogram
analogue of FVI concentrability.

It suffices to choose \(B\) by predictive cross-validation. The prediction-only approximation term
satisfies
\[
\min_{h\in\mathcal H_B(\hat v)}\|h-v_0\|_{2,\rho}
\le
\|\hat v-v_0\|_{2,\rho}
+
\min_{h\in\mathcal H_B(\hat v)}\|h-\hat v\|_{2,\rho}.
\]
Thus binning is no worse than the original predictor, up to identity
approximation on the range of \(\hat v(S)\). For equal-mass bins, the histogram
bias--variance balance suggests \(B\asymp n^{1/3}\), yielding
\citep{gyorfi2002distribution}
\[
\|V_K-v_0\|_{2,\rho}
\le
\frac{\sqrt{\mathcal C_{B,\gamma}}}{1-\gamma}
\|\hat v-v_0\|_{2,\rho}
+
O_p\{(\log n/n)^{1/3}\},
\]
with Bellman calibration error vanishing at the same rate.





\subsection{Isotonic Calibration}

Histogram calibration requires choosing the number of bins \(B\). As a
low-tuning alternative, we consider \emph{isotonic iterated Bellman
calibration}, obtained by taking \(\mathcal G=\mathcal G_{\mathrm{iso}}\) in
Algorithm~\ref{alg::cal-gen}, where \(\mathcal G_{\mathrm{iso}}\) is the class
of nondecreasing functions on \(\mathbb R\). Each update isotonic-regresses the
fitted Bellman targets on the initial predictions \(\hat v(S_i)\), producing a
monotone calibrator computable in near-linear time by the pool-adjacent-violators
algorithm (PAVA) \citep{best1990active}. Like histogram calibration, isotonic
calibration averages Bellman targets over groups of nearby predicted values,
but the groups are chosen adaptively by the monotonicity constraint
\citep{barlow1972isotonic}. This regularizes the calibration map without
selecting \(B\); since the identity map is monotone, isotonic calibration can
preserve an already reliable predictor while correcting systematic monotone
distortions.

\begin{enumerate}[label=\textbf{C\arabic*}, ref={C\arabic*}, leftmargin=1.5em, resume=cond]
\item \label{cond::C3}
\textbf{Finite variation.}
There exists \(V<\infty\) such that, almost surely, the function $t
\mapsto
E\!\left[
(\mathcal T_\pi V_K)(S)
\mid
\hat v(S)=t,\mathcal C_n
\right]$
has total variation at most \(V\).
\end{enumerate}

Condition~\ref{cond::C3} is standard in isotonic calibration
\citep{van2023causal} and controls the complexity of the one-dimensional
calibration curve. For histogram binning, the analogous complexity is governed
by the number of bins \(B\).

\begin{theorem}[Calibration error for isotonic calibration]
\label{theorem::Calerroriso}
Assume \ref{cond::C1}, \ref{cond::C1b}, \ref{cond::C2}, and \ref{cond::C3}
with \(\mathcal G=\mathcal G_{\mathrm{iso}}\). Then there exists a constant
\(C<\infty\) such that, for any \(K\in\mathbb N\), with probability at least
\(1-\delta\),
{\small
\begin{align*}
\mathrm{Cal}_{\ell^2}(V_K)
\le\;&
C\left\{
n^{-1/3}
+
\sqrt{\frac{\log(1/\delta)}{n}}
\right\}  +
\big\|
b_0\{
(\widehat w_\pi-w_\pi)
(\widehat q_{V_K}-q_{V_K})
\}
\big\|_{2,\rho}  +
\big\|
\widehat{\mathcal T}_\pi V_K
-
\widehat{\mathcal T}_\pi V_{K-1}
\big\|_{2,\rho}.
\end{align*}
}
\end{theorem}

The isotonic analysis parallels the histogram case but uses the adaptive pooling
induced by PAVA. Monotonicity is only a pooling regularizer; we do not assume the
calibration target is monotone. The resulting \(n^{-1/3}\) rate matches classical
isotonic regression \citep{chatterjee2013improved} and histogram binning with
\(B\asymp n^{1/3}\), without choosing \(B\). However, fully iterated isotonic
calibration does not inherit our histogram value-error bound without Bellman
completeness, because the PAVA partition can change across iterations.

Appendix~\ref{appendix::hybrid} therefore introduces an isotonic-histogram
hybrid: learn the isotonic partition once, then run the histogram update on that
fixed partition. This preserves adaptive pooling while restoring the
fixed-partition structure required by our finite-sample value-error analysis,
and is the procedure we recommend in practice.

\section{Experimental investigation}
\label{sec:experiments}

We evaluate Bellman calibration as a post-hoc correction for fitted off-policy
value predictors. Each base learner estimates a \(Q\)-function and induces a
target-policy value predictor, which is then calibrated. We use linear and
random-feature FQE with linear, histogram, and isotonic calibrators. The
synthetic experiments isolate the failure mode in
Table~\ref{tab:rl-calibration-motivation}: informative but mis-scaled values.
We use 5-fold cross-calibration \citep{van2023causal}, except under temporal
shift, where FQE is trained on an old-regime batch and \(g\) is fit on a small
current-regime batch. All main results use 100 replications and independent
evaluation data; values below one indicate improvement. Details are in
Appendix~\ref{app:experiments}.

\begin{figure}[t]
  \centering
  \includegraphics[width=0.8\linewidth]{paper_import_bundle/figures/calibration_story_compact.pdf}
  \vspace{-0.25em}
  \caption{\textbf{Post-hoc calibration improves mis-scaled value predictions.}
  Value MSE and Bellman calibration error ratios across synthetic failure
  modes, relative to the matched raw baseline.}
  \vspace{-0.5em}
  \label{fig:calibration-story}
\end{figure}

Figure~\ref{fig:calibration-story} reports ratios to the matched raw baseline.
Linear calibration corrects affine scale errors, while histogram and
isotonic-histogram calibration give the strongest gains under nonlinear
monotone misspecification. With finite Bellman-iteration error, all three
post-hoc maps reduce true-\(V\) MSE by about \(20\%\).
Table~\ref{tab:main-simulation-results} (Appendix~\ref{app:tablemain}) gives
the complementary audit, including temporal reward shift.

As an external check, we calibrate frozen fitted \(Q\)-functions on Deep OPE
Hopper-medium. Each \(Q\)-function is trained once and held fixed; only the
one-dimensional map \(g\) is fit on calibration trajectories, with evaluation on
disjoint diagnostic trajectories. We calibrate \(\widehat Q(S,A)\) on logged
state-action pairs, and each Bellman backup averages over target-policy next
actions. Figure~\ref{fig:hopper-q-calibration} summarizes a neural-FQE run with
1000 gradient updates, 20 random trajectory splits, and all eleven target
policies. Isotonic-histogram calibration reduces plug-in and debiased Bellman
calibration error to 0.787 and 0.771 of the raw \(Q\)-function, while
\(Q\)-Bellman MSE and scalar OPE error are nearly unchanged (1.002 and 0.978).
Thus, for a stronger frozen \(Q\)-function, calibration mainly improves Bellman
reliability rather than inducing artificial MSE gains.
Appendix~\ref{app:hopper-q-calibration} also reports a 100-update neural-FQE
stress test, where the deliberately undertrained \(Q\)-function leaves
substantial scale/projection error that post-hoc calibration can correct.


\section{Conclusion}
Bellman calibration provides an estimable, post-hoc reliability criterion:
predictions should agree, on average, with target-policy Bellman backups among
states assigned similar values. Iterated Bellman Calibration turns this
criterion into a one-dimensional recalibration procedure that controls
calibration error without Bellman completeness or value-function realizability.
Appendix~\ref{app:concl} discusses takeaways, coverage and nuisance-estimation
limitations, and future directions.



\bibliographystyle{plainnat}
\bibliography{ref}