# Orthogonalized Estimation of Difference of $Q$-functions

Angela Zhou
University of Southern California
Data Sciences and Operations
<EMAIL_ADDRESS>
(6/12/2024)

###### Abstract

Offline reinforcement learning is important in many settings with available
observational data but the inability to deploy new policies online due to
safety, cost, and other concerns. Many recent advances in causal inference and
machine learning target estimation of “causal contrast" functions such as
CATE, which is sufficient for optimizing decisions and can adapt to
potentially smoother structure. We develop a dynamic generalization of the
R-learner (Nie et al., 2021; Lewis and Syrgkanis, 2021) for estimating and
optimizing the difference of $Q^{\pi}$-functions, $Q^{\pi}(s,1)-Q^{\pi}(s,0)$
(which can be used to optimize multiple-valued actions). We leverage
orthogonal estimation to improve convergence rates in the presence of slower
nuisance estimation rates and prove consistency of policy optimization under a
margin condition. The method can leverage black-box nuisance estimators of the
$Q$-function and behavior policy to target estimation of a more structured
$Q$-function contrast.

##  1 Introduction and Related Work

Learning optimal dynamic treatment rules, or sequential policies for taking
actions, is important, although often only observational data is available.
Many recent works in offline reinforcement learning develop methodology to
evaluate and optimize sequential decision rules, without the ability to
conduct online exploration.

An extensive literature on causal inference and machine learning establishes
methodologies for learning causal contrasts, such as the conditional average
treatment effect (CATE) (Wager and Athey, 2018; Foster and Syrgkanis, 2019;
Künzel et al., 2019; Kennedy, 2020), which is sufficient for making optimal
decisions. Methods that specifically estimate causal contrasts (such as the
CATE), can better adapt to potentially smoother or more structured contrast
functions, while methods that instead contrast estimates (by taking the
difference of outcome regressions or $Q$ functions) can not. Additionally,
estimation of causal contrasts can be improved via orthogonalization or double
machine learning (Kennedy, 2022; Chernozhukov et al., 2018). Estimating the
causal contrast is both sufficient for optimal decisions and statistically
favorable.

In this work, building on recent advances in heterogeneous treatment effect
estimation, we focus on estimating analogous causal contrasts for offline
reinforcement learning, namely
$\tau_{t}^{\pi}(s)=Q_{t}^{\pi}(s,1)-Q_{t}^{\pi}(s,0)$, and natural multiple-
action generalizations thereof.

The sequential setting offers even more motivation to target estimation of the
contrast: additional structure can arise from sparsity patterns induced by the
joint (in)dependence of rewards and transition dynamics on the (decompositions
of) the state variable. A number of recent works point out this additional
structure (Wang et al., ; Wang et al., 2022), for example of a certain
transition-reward factorization, first studied by (Dietterich et al., 2018),
that admits a sparse $Q$-function contrast (Pan and Schölkopf, 2023). (Zhou,
2024b) proposes a variant of the underlying blockwise pattern that also admits
sparse optimal policies, but proposes a special modification of LASSO. Our
method can adapt to such underlying sparsity structure when it is present in
the $Q$-function contrast, in addition to other scenarios where the contrast
is smoother than the $Q$-functions themselves.

The contributions of this work are as follows: We develop a dynamic
generalization of the R-learner (Nie and Wager, 2021; Lewis and Syrgkanis,
2021) for estimating the $Q$-function contrast. The method wraps around
standard estimation procedures in offline reinforcement learning via a
sequence of sequential loss minimization problems, which makes it appealingly
practical. We show theoretical guarantees of improved convergence rates.
Therefore our method leverages behavior policy estimation to improve
estimation without suffering from unstable propensity weights. We illustrate
benefits of adapting to structure in synthetic examples.

Related work. There is a large body of work on offline policy evaluation and
optimization in offline reinforcement learning (Jin et al., 2021; Xie et al.,
2021), including approaches that leverage importance sampling or introduce
marginalized versions (Jiang and Li, 2016; Thomas et al., 2015; Kallus and
Uehara, 2019a; Liu et al., 2018). For Markov decision processes, other papers
study statistically semiparametrically efficient estimation of the policy
value (Kallus and Uehara, 2019a, b; Xie et al., 2023; Kallus and Zhou, 2022).
The literature on dynamic treatment regimes (DTRs) studies a method called
advantage learning (Schulte et al., 2014), although DTRs in general lack
reward at every timestep, whereas we are particularly motivated on sparsity
implications that arise jointly from reward and transition structure. In
particular, beyond policy value estimation, we aim to recover the entire
contrast function. Prior works that consider policy optimization under a
restricted function class can require estimating difficult policy-dependent
nuisance functions; we maximize the advantage function without further
restricting functional complexity, which requries re-estimating nuisance
functions at every timestep (but not every iteration of policy optimization,
as in (Xu et al., 2021)).

At a high level, our method is similar to the dynamic DR learner studied in
(Lewis and Syrgkanis, 2021) in that we extend the R-learner identification
approach to a sequential setting, although the estimand is quite different. In
particular, they only consider heterogeneity based on a fixed initial state,
dynamic treatment regimes with terminal rewards, generalize structural nested-
mean models (SNMMs) by estimating “blip-to-zero” functions. Consequently, our
analysis is similar at a high level. Overall, the most closely related work
when it comes to estimating contrast functionals in reinforcement learning is
that of (Shi et al., 2022), which derives a pseudo-outcome for estimating the
$Q$-function contrast in the infinite horizon setting. We share the same
estimand, but in the finite-horizon setting. The estimation strategy is quite
different. Crucial differences include: we directly generalize the
residualized learning (R-learner) approach, and we work in finite-horizons
with the propensity score rather than the hard-to-estimate stationary
distribution density ratio (Liu et al., 2018). Note that the (single-stage)
R-learner loss function is an overlap-weighted (Li et al., 2019) regression
against the doubly-robust score (DR-learner (Kennedy, 2020)). (See (Morzywolek
et al., 2023; Chernozhukov et al., 2024) for more discussion).

Advantage functions are a contrast functional widely studied in classical RL
(less often in the offline setting) and dynamic treatment regimes (Neumann and
Peters, 2008; mur, 2003). However, which contrast it evaluates is policy-
dependent, and it requires further algorithmic development for policy
learning, unlike our approach that is simply greedy with respect to
difference-of-Q functions. (Pan and Schölkopf, 2023) note the analogy with
causal contrast estimation and derive a Q-function independent estimator, but
in the online setting. (Nie et al., 2021) studies OPE for advantage functions
in a special case of optimal stopping. We do make a margin assumption to
relate convergence of Q-function contrasts to policy value convergence,
analogous to (Shi et al., 2022). (Hu et al., 2024) studies consequences of the
margin assumption for fitted-Q-iteration with a tighter analysis. Our approach
is better suited for settings with highly structured difference-of-Qs since we
introduce auxiliary estimation at every timestep.

##  2 Method

Problem Setup:  We consider a finite-horizon Markov Decision Process on the
full-information state space comprised of a tuple
$\mathcal{M}=(\mathcal{S},\mathcal{A},r,P,\gamma,T)$ of states, actions,
reward function $r(s,a)$, transition probability matrix $P$, discount factor
$\gamma<1$, and time horizon of $T$ steps, where $t=1,\dots,T$. We let the
state spaces $\mathcal{S}\subseteq\mathbb{R}^{d}$ be continuous, and assume
the action space $\mathcal{A}$ is finite. A policy
$\pi:\mathcal{S}\mapsto\Delta(\mathcal{A})$ maps from the state space to a
distribution over actions, where $\Delta(\cdot)$ is the set of distributions
over $(\cdot)$, and $\pi(a\mid s)$ is the probability of taking action $a$ in
state $s$. (At times we overload notation a bit so that $\pi(s)\in\mathcal{A}$
indicates the action random variable under $\pi$ evaluated at state $s$).

The value function is
$V^{\pi}_{t}(s)=\mathbb{E}_{\pi}[\sum_{t^{\prime}=t}^{T}\gamma^{t^{\prime}-t}R_{t^{\prime}}\mid
s]$, where $\mathbb{E}_{\pi}$ denotes expectation under the joint distribution
induced by the MDP $\mathcal{M}$ running policy $\pi.$ The state-action value
function, or $Q$ function is
$Q^{\pi}_{t}(s)=\mathbb{E}_{\pi}[\sum_{t^{\prime}=t}^{T}\gamma
R_{t^{\prime}}\mid s,a]$. These satisfy the Bellman operator, e.g.
${Q^{\pi}_{t}(s,a)=r(s,a)+\gamma\mathbb{E}[V_{t+1}^{\pi}(s_{t+1})\mid s,a].}$
The optimal value and q-functions are denoted $V^{*},Q^{*}$ under the optimal
policy. We focus on estimating the difference of $Q$-functions (each under the
same policy), $\tau_{t}^{\pi}(s)=Q_{t}^{\pi}(s,1)-Q_{t}^{\pi}(s,0).$ (This
differs slightly from the conventional advantage function studied in RL,
defined as $Q^{\pi}(s,a)-V^{\pi}(s)$, where the contrast being estimated
depends on the policy). We focus on the offline reinforcement learning setting
where we have access to a dataset of $n$ offline trajectories,
$\textstyle\mathcal{D}=\\{(S_{t}^{(i)},A_{t}^{(i)},R_{t}^{(i)}S_{t+1}^{(i)})_{t=1}^{T}\\}_{i=1}^{n}$,
where actions were taken according to some behavior policy $\pi^{b}.$ We state
some notational conventions. For some generic function $f$ we define the norm
$\|f\|_{u}:=\mathbb{E}\left[\|\psi(X)\|_{u}\right]^{1/u}$. In the context of
estimation (rather than discussing identification), we denote the true
population functions with a $\circ$ subscript, i.e. $\tau_{t}^{\pi,\circ}$ and
so on.

Policy evaluation: Identification. First we overview deriving the estimating
moments of our approach. The arguments are broadly a generalization of the so-
called residualized R-learner (Nie and Wager, 2021); (Lewis and Syrgkanis,
2021) considers a similar generalization for structural nested mean models
without state-dependent heterogeneity. For the purposes of this section, we
discuss the true population $Q,m,\tau$ functions without notational
decoration, which we introduce later on when we discuss estimation.

Denote
$\underline{\pi}_{t+1}=\pi_{t+1:T}\coloneqq\\{\pi_{t+1},\dots,\pi_{T}\\}$ for
brevity. Then $Q_{t}^{\underline{\pi}_{t+1}}$ indicates the $Q_{t}$ function
under policy $\pi$. For brevity, we further abbreviate $Q_{t}^{\pi}\coloneqq
Q_{t}^{\underline{\pi}_{t+1}}$ when this is unambiguous. We seek to estimate:

$\tau_{t}^{\pi}(S_{t})=Q_{t}^{\pi}(S_{t},1)-Q_{t}^{\pi}(S_{t},0),$ (1)

Note that the $Q$-function satisfies:
$Q_{t}^{\pi}(S_{t},A_{t})=\mathbb{E}[R_{t}+\gamma
Q_{t+1}^{\pi}(S_{t+1},A_{t+1})\mid S_{t},A_{t}].$ Define

$\epsilon_{t}^{(i)}(A_{t})=R_{t}+\gamma
Q_{t+1}^{\pi}(S_{t+1},A_{t+1})-\\{Q_{t}^{\pi}(S_{t},0)+A_{t}\tau_{t}^{\pi}(S_{t})\\}.$

Under sequential unconfoundedness and Markovian properties, we obtain the
conditional moment:

$\mathbb{E}[\epsilon_{t}^{(i)}(A_{t})\mid S_{t},A_{t}]=0.$ (2)

Define the analogue to the marginal outcome function, which is the state-
conditional value function under the behavior policy:
$m^{\circ,\pi}(S_{t})=V_{t}^{\pi_{t}^{b},\underline{\pi}_{t+1}}=\mathbb{E}_{\pi^{b}_{t}}[R_{t}+\gamma
Q_{t+1}^{\pi}(S_{t+1},A_{t+1})\mid S_{t}]$. Under sequential unconfoundedness,

$\displaystyle R_{t}+\gamma Q_{t+1}^{\pi}(S_{t+1},A_{t+1})+\epsilon(A_{t})$
$\displaystyle=Q_{t}^{\pi}(S_{t},0)+A_{t}\tau_{t}^{\pi}(S_{t})$ $\displaystyle
m^{\pi}_{t}(S_{t})=\mathbb{E}_{\pi^{b}}[R_{t}+\gamma
Q_{t+1}^{\pi}(S_{t+1},A_{t+1})\mid S_{t}]$
$\displaystyle=Q_{t}^{\pi}(S_{t},0)+\pi^{b}(1\mid S_{t})\tau_{t}^{\pi}(S_{t})$

Hence,

$R_{t}+\gamma
Q_{t+1}^{\pi}(S_{t+1},A_{t+1})-m^{\pi}_{t}(S_{t})=(A-\pi^{b}(1\mid
S_{t}))\tau_{t}^{\pi}(S_{t})+\epsilon_{t}(A_{t}).$ (3)

#### Extension to multiple actions.

So far we presented the method with $\mathcal{A}\in\\{0,1\\}$ for simplicity,
but all methods in this paper will extend to the multi-action case. For
multiple actions, fix a choice $a_{0}\in\mathcal{A}$, and for
$a\in\mathcal{A}\setminus a_{0},$ define
$\tau_{t}^{\pi}(s,a)\coloneqq\tau_{a,t}^{\pi}(s)={Q^{\pi}_{t}(s,a)-Q^{\pi}_{t}(s,a_{0})}.$
For $k\in|\mathcal{A}|,$ let $\pi^{b}(k\mid S_{t})=P(A_{t}=k\mid S_{t})$.
Redefine $\epsilon_{t}^{(i)}(A_{t})=R_{t}+\gamma
Q_{t+1}^{\pi}(S_{t+1},A_{t+1})-\\{Q_{t}^{\pi}(S_{t},0)+\mathbb{I}[A_{t}=a]\tau_{t}^{\pi}(S_{t})\\}$.
Then the equivalent of eq. 3 is that $\tau_{a,t}^{\pi}(S_{t})$ satisfies:

$\displaystyle R_{t}+\gamma
Q_{t+1}^{\pi}(S_{t+1},A_{t+1})-m^{\pi}_{t}(S_{t})=(\mathbb{I}[A_{t}=a]-\pi^{b}(a\mid
S_{t}))\tau_{a,t}^{\pi}(S_{t})+\epsilon_{t}(A_{t})$

#### The loss function.

This motivates the approach based on (penalized) empirical risk minimization:

$\tau_{t}(\cdot)\in\operatornamewithlimits{argmin}_{\tau}\left\\{\mathbb{E}\left[\left(\\{R_{t}+\gamma
Q_{t+1}^{\pi}(S_{t+1},A_{t+1})-m^{\pi}_{t}(S_{t})\\}-\gamma\\{A-\pi^{b}_{t}(1\mid
S_{t})\\}\cdot\tau_{t}^{\pi}(S_{t})\right)^{2}\right]\right\\}$ (4)

Again, so far we have discussed identification assuming the true $Q,m,\pi^{b}$
functions, etc. Next we discuss feasible estimation, and outside of this
section we refer to the population-level true nuisance functions as
$Q^{\pi,\circ},m^{\pi,\circ},\pi^{b,\circ},\tau^{\pi,\circ}$.

Feasible estimation.  In practice, the nuisance functions need to be
estimated. We introduce some notation before defining the full estimation
algorithm. Let the nuisance vector be denoted
$\eta=[\\{Q_{t}^{\pi}\\}_{t=1}^{T},\\{m_{t}^{\pi}\\}_{t=1}^{T},\\{\pi_{t}^{b}\\}_{t=1}^{T}]$.
The fitted advantage R-learner for evaluation is a feasible version of the
sequential loss minimization approach implied by eq. 4: we describe the
algorithm in Algorithm 1. Given an evaluation policy $\pi^{e}$, first fit the
nuisance functions: a pilot estimate of the $Q$ function and the behavior
policy. Then, evaluate the loss function in eq. 4 and estimate $\tau_{t}.$

Estimating the nuisance functions.  The $Q$ function nuisance can be estimated
with a variety of approaches such as fitted-Q-evaluation (Le et al., 2019;
Chakraborty and Murphy, 2014; Duan et al., 2021), other approaches in offline
reinforcement learning, minimum-distance estimation for conditional moment
restrictions/GMM (Kallus and Uehara, 2019a), or the finite-horizon analogous
version of DR-learner suggested in (Shi et al., 2022). Estimating the behavior
policy is a classic probabilistic classification or multi-class classification
problem. Sometimes the offline trajectories might arise from a system with
known exploration probabilities, so that the behavior policy might be known.

Cross-fitting. We also introduce cross-fitting, which will differ slightly
between policy evaluation and optimization: splitting the dataset
$\mathcal{D}$ into $K$ many folds (preserving trajectories, i.e. randomizing
over trajectory index $i$), and learning the nuisance function $\eta^{-k}$ on
$\\{\mathcal{D}_{k^{\prime}}\\}_{k^{\prime}\in\\{[K]\setminus k\\}}$. (In
scenarios with possible confusion we denote the nuisance function
$\eta^{(-k)}$ instead. In evaluating the loss-function, we evaluate the
nuisance function $\eta^{-k}$ using data from the held-out $k$th fold. Given
the cross-fitting procedure, we introduce the empirical squared loss function:

$\displaystyle\hat{\mathcal{L}}_{t}(\tau,\eta)\textstyle=\textstyle\sum\limits_{k=1}^{K}\sum\limits_{i\in\mathcal{D}_{k}}\left(R_{t}^{(i)}+\gamma\hat{Q}_{t+1}^{\pi,-k}(S_{t+1}^{(i)},A_{t+1}^{(i)})-\hat{m}_{t}^{\pi,-k}(S_{t}^{(i)})-\\{A^{(i)}_{t}-\hat{\pi}^{b,-k}_{t}(1\mid
S_{t}^{(i)})\\}\tau_{t}(S_{t}^{(i)})\right)^{2}$

and let the population loss function $\mathcal{L}_{t}(\tau,\eta)$ be the
population expectation of the above.

Algorithm 1 Dynamic Residualized Difference-of-Q-Evaluation

1: Given: $\pi^{e}$, evaluation policy; and for sample splitting, partition of
$\mathcal{D}$ into $K$ folds, $\\{\mathcal{D}_{k}\\}_{k=1}^{K}.$

2: On $\mathcal{D}_{k},$ estimate $\hat{Q}^{\pi^{e},k}(s,a)$ and behavior
policy $\hat{\pi}_{t}^{b,k}(s)$. Evaluate the value function via
integrating/summing $\hat{Q}$ over the empirical distribution of actions,
$a\sim\pi^{b}$, observed in the data, so that
$\hat{m}(s)=\mathbb{E}_{\pi^{b}_{t}}[R_{t}+\gamma\hat{Q}_{t+1}^{\pi^{e}}(S_{t+1},A_{t+1})\mid
S_{t}=s].$

3: for timestep $t=T,\ldots,1$ do

4:
$\hat{\tau}_{t}\in\operatornamewithlimits{argmin}_{\tau}\left\\{\sum\limits_{k=1}^{K}\sum\limits_{i\in\mathcal{D}_{k}}\left(R_{t}^{(i)}+\gamma\hat{Q}_{t+1}^{\pi,-k}(S_{t+1}^{(i)},A_{t+1}^{(i)})-\hat{m}_{t}^{\pi,-k}(S_{t}^{(i)})-\\{A^{(i)}_{t}-\hat{\pi}^{b,-k}_{t}(1\mid
S_{t}^{(i)})\\}\tau_{t}(S_{t}^{(i)})\right)^{2}\right\\}$

5: end for

Finally, note that the expectation of the empirical squared loss will not in
general be an unbiased estimate of the true squared error, due to the squaring
and the expectation over the next transition. Nonetheless, as shown in other
works studying fitted Q evaluation/iteration, the resulting Q function
(contrast function here) can still be useful for policy optimization.

######  Lemma 1 (Proxy Sequential R-learner loss: Excess Variance ).

$\mathbb{E}[\hat{\mathcal{L}}_{t}(\tau^{\pi},\eta)]-{\mathcal{L}}_{t}(\tau^{\pi},\eta)=\operatorname{Var}[\max_{a^{\prime}}Q^{\pi}\left(S_{t+1},a^{\prime}\right)\mid\pi_{t}^{b}]$

Algorithm 2 Dynamic Residualized Difference-of-Q Optimization

1: Given: Partition of $\mathcal{D}$ into $3$ folds,
$\\{\mathcal{D}_{k}\\}_{k=1}^{3}.$

2: Estimate $\hat{\pi}^{b}_{t}$ on $\mathcal{D}_{1}$.

3: At time T: Set $\hat{Q}_{T}(s,a)=0.$ Estimate
$m_{T}=\mathbb{E}_{\pi^{b}}[R_{T}\mid S_{T}]$ on $\mathcal{D}_{1}$ and
$\hat{\tau}_{T}$ on $\mathcal{D}_{k(T)}$, where $k(t)=2$ if $t$ is odd and
$k(t)=3$ if $t$ is even. Optimize $\hat{\pi}_{T}(s)\in\arg\max\tau_{T}(s).$

4: for timestep $t=T-1,\ldots,1$ do

5: Estimate $Q^{\hat{\underline{\pi}}_{t+1}}$ on $\mathcal{D}_{1}$. Evaluate
$m_{t}^{\hat{\underline{\pi}}_{t+1}}$. Estimate
$\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}$ on $\mathcal{D}_{k(t)}$ by
minimizing the empirical loss:
$\textstyle\hat{\tau}_{t}(\cdot)\in\operatornamewithlimits{argmin}_{\tau}\sum\limits_{i\in\mathcal{D}_{k(t)}}\left(R_{t}^{(i)}+\gamma\hat{Q}_{t+1}^{\pi,(1)}(S_{t+1}^{(i)},A_{t+1}^{(i)})-\hat{m}_{t}^{\pi,(1)}(S_{t}^{(i)})-\\{A^{(i)}_{t}-\hat{\pi}^{b,(1)}_{t}(1\mid
S_{t}^{(i)})\\}\tau_{t}(S_{t}^{(i)})\right)^{2}$

6: Optimize
$\hat{\pi}_{t}(s)\in\arg\max\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}(s)$.

7: end for

Policy optimization. The sequential loss minimization approach also admits an
policy optimization procedure. The policy at every timestep is greedy with
respect to the estimated $\tau$. We describe the algorithm in Algorithm 2. We
use a slightly different cross-fitting approach for policy optimization. We
introduce an additional fold, upon which we alternate estimation of
$\hat{\tau}_{t}$. So, overall we use three folds: one for estimating nuisance
functions $\eta$, and the other two for estimating
$\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}$. On these two other folds,
between every timestep, we alternate estimation of $\hat{\tau}_{t}$ on one of
them, in order to break dependence between the estimated optimal forwards
policy $\hat{\underline{\pi}}_{t+1}$ and $\hat{\tau}_{t}$ (and therefore the
greedy policy $\hat{\pi}_{t}$).

##  3 Analysis

Our analysis generally proceeds under the following assumptions.

######  Assumption 1 (Independent and identically distributed trajectories).

We assume that the data was collected under a stationary behavior policy, i.e.
not adaptively collected from a policy learning over time.

######  Assumption 2 (Sequential unconfoundedness).

$r(A)\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A\mid S_{t}$ and
$S_{t+1}(a)\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A_{t}\mid S_{t}$

This assumption posits that the state space is sufficient for identification.
It is satisfied by design if actions were taken by a previous known behavior
policy, i.e. randome xplanation.

######  Assumption 3 (Boundedness).

$V_{t}\leq B_{V},\tau\leq B_{\tau}$

######  Assumption 4 (Bounded transition density).

Transitions have bounded density: $P(s^{\prime}\mid s,a)\leq c$. Let
$d_{\pi}(s)$ denote the marginal state distribution under policy $\pi$. Assume
that $d_{\pi^{b}_{t}}(s)<c,$ for $t=1,\dots,T.$

Next we establish convergence rates for $\hat{\tau}^{\pi}$, depending on
convergence rates of the nuisance functions. Broadly we follow the analysis of
(Foster and Syrgkanis, 2019; Lewis and Syrgkanis, 2021) for orthogonal
statistical learning. The analysis considers some $\hat{\tau}$ with small
excess risk relative to the projection onto the function class, i.e. as might
arise from an optimization algorithm with some approximation error.

For a fixed evaluation policy $\pi^{e}$, define the projection of the true
advantage function onto $\Psi^{n}$,

$\tau_{t}^{\pi^{e},n}=\arg\inf_{\tau_{t}\in\Psi_{t}^{n}}\|\tau_{t}-\tau_{t}^{\circ,\pi^{e}}\|_{2}.$
(5)

For a fixed evaluation policy $\pi^{e}$, define the error of some estimate
$\hat{\tau}_{t}^{\pi^{e}}$ to projection onto the function class:

$\textstyle\nu_{t}^{\pi^{e}}=\hat{\tau}_{t}^{\pi^{e}}-\tau_{t}^{n,\pi^{e}}.$

######  Theorem 1 (Policy evaluation ).

Suppose
$\left\\{\sup_{s,t}\mathbb{E}[(A_{t}-\pi_{t}^{b})(A_{t}-\pi_{t}^{b})\mid
s]\right\\}\leq C$ and Assumptions 1, 2, 3 and 4. Consider a fixed evaluation
policy $\pi^{e}.$ Consider any estimation algorithm that produces an estimate
$\hat{\tau}^{\pi^{e}}=\left(\tau_{1}^{\pi^{e}},\ldots,\tau_{T}^{\pi^{e}}\right)$,
with small plug-in excess risk at every $t$, with respect to any generic
candidate $\tilde{\tau}^{{\pi^{e}}}$, at some nuisance estimate $\hat{\eta}$,
i.e.,

$\mathcal{L}_{D,t}(\hat{\tau}_{t}^{\pi^{e}};\hat{\eta})-\mathcal{L}_{D,t}(\tilde{\tau}_{t}^{\pi^{e}};\hat{\eta})\leq\epsilon(\tau_{t}^{n},\hat{\eta}).$

Let $\rho_{t}$ denote product error terms:

$\displaystyle\rho_{t}^{\pi^{e}}(\hat{\eta})$
$\displaystyle={B_{\tau}}^{2}\lVert(\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ})^{2}\rVert_{u}+B_{\tau}\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{m}_{t}^{\pi^{e}}-m^{\pi^{e},\circ}_{t})\rVert_{u}$
$\displaystyle\qquad+\gamma(B_{\tau}\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{Q}_{t+1}^{\pi^{e}}-Q_{t+1}^{\pi^{e},\circ})\rVert_{u}+\lVert(\hat{m}_{t}^{\pi^{e}}-m^{\pi^{e},\circ}_{t})(\hat{Q}_{t+1}^{\pi^{e}}-Q_{t+1}^{\pi^{e},\circ})\rVert_{u}).$
(6)

Then, for $\sigma>0,$ and ${u}^{-1}+{\overline{u}}^{-1}=1,$

$\frac{\lambda}{2}\|\nu_{t}^{\pi^{e}}\|_{2}^{2}-\frac{\sigma}{4}\lVert\nu_{t}^{\pi^{e}}\rVert_{\overline{u}}^{2}\leq\epsilon(\hat{\tau}_{t}^{\pi^{e}},\hat{\eta})+\frac{2}{\sigma}\left(\lVert(\tau^{\pi^{e},\circ}-\tau_{t}^{\pi^{e},n})\rVert_{u}^{2}+\rho_{t}^{\pi^{e}}(\hat{\eta})^{2}\right).$

In the above theorem, $\epsilon(\hat{\tau}_{t}^{\pi^{e}},\hat{\eta})$ is the
excess risk of the empirically optimal solution. Note that in our setting,
this excess risk will be an approximation error incurred from the proxy loss
issue described in Lemma 1. The bias term is
$\lVert(\tau^{\pi^{e},\circ}-\tau_{t}^{\pi^{e},n})\rVert_{u}^{2},$ which
describes the model misspecification bias of the function class parametrizing
$Q-$function contrasts, $\Psi.$ The product error terms
$\rho_{t}^{\pi^{e}}(\hat{\eta})$ highlight the reduced dependence on
individual nuisance error rates. We will instantiate the previous generic
theorem for the projection onto $\Psi^{n}$, defined in Equation 5, also
accounting for the sample splitting. We will state the results with local
Rademacher complexity, which we now introduce. For generic 1-bounded functions
$f$ in a function space $f\in\mathcal{F},f\in[-1,1],$ the local Rademacher
complexity is defined as follows:

$\textstyle\mathscr{R}_{n}(\mathcal{F};\delta)=\mathbb{E}_{\epsilon_{1:n},X_{1:n}}\left[\sup_{f\in\mathcal{F}:\|f\|_{2}\leq\delta}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f\left(X_{i}\right)\right]$

The critical radius $\delta^{2}$ more tightly quantifies the statistical
complexity of a function class, and is any solution to the so-called basic
inequality, $\mathscr{R}_{n}(\mathcal{F};\delta)\leq\delta^{2}.$ The star hull
of a generic function class $\mathcal{F}$ is defined as
$\operatorname{star}(\mathcal{F})=\\{cf:f\in\mathcal{F},c\in[0,1]\\}$. Bounds
on the critical radius of common function classes like linear and polynomial
models, deep neural networks, etc. can be found in standard references on
statistical learning theory, e.g. (Wainwright, 2019). We can obtain mean-
squared error rates for policy evaluation via specializing Theorem 1 to the
$2$-norm and leveraging results from (Foster and Syrgkanis, 2019)

######  Theorem 2 (MSE rates for policy evaluation).

Suppose
$\left\\{\sup_{s,t}\mathbb{E}[(A_{t}-\pi_{t}^{b})(A_{t}-\pi_{t}^{b})\mid
s]\right\\}\leq C$ and Assumptions 1, 2, 3 and 4. Consider a fixed policy
$\pi^{e}.$ Suppose each of
$\mathbb{E}[\lVert(\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ})\rVert_{2}^{2}]$,
$\mathbb{E}[\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{m}_{t}^{\pi^{e}}-m^{\pi^{e},\circ}_{t})\rVert_{2}^{2}]$,
$\mathbb{E}[\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{Q}_{t+1}^{\pi^{e}}-Q_{t+1}^{\pi^{e},\circ})\rVert_{2}^{2}]$,
and
$\mathbb{E}[\lVert(\hat{m}_{t}^{\pi^{e}}-m^{\pi^{e},\circ}_{t})(\hat{Q}_{t+1}^{\pi^{e}}-Q_{t+1}^{\pi^{e},\circ})\rVert_{2}^{2}]$
are of order
$O(\delta_{n/2}^{2}+\|\tau^{\pi^{e},\circ}_{t}-\tau_{t}^{\pi^{e},n}\|_{2}^{2}).$
Then

$\mathbb{E}[\lVert\hat{\tau}_{t}^{\pi^{e}}-\tau_{t}^{\pi^{e},\circ}\rVert_{2}^{2}]=O\left(\delta_{n/2}^{2}+\|\tau^{\pi^{e},\circ}_{t}-\tau_{t}^{\pi^{e},n}\|_{2}^{2}\right)$

Working with the orthogonalized estimate results in the weaker product-error
rate requirements included above. However, our estimating moments do include
the $Q$ function nuisances, and quarter-root rates are required for estimating
both the $Q$ and $\pi^{b}$ functions.

Policy optimization. Convergence of $\tau_{t}$ implies convergence in policy
value. We quantify this with the margin assumption, which is a low-noise
condition that quantifies the gap between regions of different optimal action
(Tsybakov, 2004). It is commonly invoked to relate estimation error of plug-in
quantities to decision regions, in this case the difference-of-Q functions to
convergence of optimal decision values.

######  Assumption 5 (Margin (Tsybakov, 2004)).

Assume there exist some constants $\alpha,\delta_{0}>0$ such that

$\displaystyle
P\left(\max_{a}Q^{*}(s,a)-\max_{a^{\prime}\in\mathcal{A}\setminus\arg\max_{a}Q^{*}(s,a)}Q^{*}\left(s,a^{\prime}\right)\leq\epsilon\right)=O\left(\varepsilon^{\alpha}\right)$

The probability density in Assumption 5 is evaluated with respect to Lebesgue
measure over the state space.

######  Lemma 2 ( Advantage estimation error to policy value via margin.).

Suppose Assumptions 2, 4 and 5 (margin assumption holds with $\alpha$).
Suppose that with high probability $\geq 1-n^{-\kappa}$ for any finite
$\kappa>0$, the following sup-norm convergence holds with some rate $b_{*}>0$,

$\sup_{s\in\mathcal{S},a\in\mathcal{A}}|\hat{\tau}^{\hat{\underline{\pi}}_{t+1}}_{t}(s)-\tau^{\underline{\pi}^{*}_{t+1},\circ}_{t}(s)|\leq
Kn^{-b*},$

then
$\textstyle\left|\mathbb{E}[V^{*}_{t}(S_{t})-V^{\hat{\pi}_{\hat{\tau}}}_{t}(S_{t})]\right|\leq\frac{(1-\gamma^{T-t})}{1-\gamma}cK^{2}n^{-b*(1+\alpha)}+O(n^{-\kappa}),$

and
$\textstyle\left\\{\int\left(Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right)^{2}ds\right\\}^{1/2}\leq\frac{(1-\gamma^{T-t})}{1-\gamma}cK^{2}n^{-b*(1+\alpha)}+O(n^{-\kappa}).$

Else, assume that
$\textstyle{\left(\mathbb{E}\int_{s\in\mathbb{S}}\left|\hat{\tau}^{n}_{t}(s)-\tau^{\circ}_{t}(s)\right|^{2}ds\right)^{1/2}\leq
K\left(n^{-b_{*}}\right)},$ for some rate $b_{*}>0$. Then

$\textstyle\left|\mathbb{E}[V_{t}^{*}(S_{t})-V_{t}^{\hat{\pi}_{\hat{\tau}}}(S_{t})]\right|={O\left(n^{-b_{*}\left(\frac{2+2\alpha}{2+\alpha}\right)}\right)},\text{
and
}{\left\\{\int\left(Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right)^{2}ds\right\\}^{1/2}}={O\left(n^{-b_{*}\left(\frac{2+2\alpha}{2+\alpha}\right)}\right)}.$

Next we study policy optimization. Studying the convergence of policy
optimization requires conditions on convergence of advantage functions from
previous steps of the algorithm.

######  Theorem 3 (Policy optimization bound).

Suppose Assumptions 1, 2, 3 and 4. Further, suppose that $Q^{\circ}$ satisfies
Assumption 5 (margin) with $\alpha>0$. Suppose the product error rate
conditions hold for each $t$ for data-optimal policies evaluated along the
algorithm, i.e. for each $t$, for $\underline{\hat{\pi}}_{t+1},$ each of
$\mathbb{E}[\lVert(\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ})\rVert_{2}^{2}]$,
$\mathbb{E}[\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{m}_{t}^{\underline{\hat{\pi}}_{t+1}}-m_{t}^{\circ,\underline{\hat{\pi}}_{t+1}})\rVert_{2}^{2}]$,
$\mathbb{E}[\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{Q}_{t+1}^{\underline{\hat{\pi}}_{t+2}}-Q_{t+1}^{\circ,\underline{\hat{\pi}}_{t+2}})\rVert_{2}^{2}]$,
and
$\mathbb{E}[\lVert(\hat{m}_{t}-m^{\circ}_{t})(\hat{Q}_{t+1}^{\circ,\underline{\hat{\pi}}_{t+2}}-Q_{t+1}^{\circ,\underline{\hat{\pi}}_{t+2}})\rVert_{2}^{2}]$
are of order
$O(\delta_{n/2}^{2}+\|\tau^{\hat{\pi}_{t+1},\circ}_{t}-\tau_{t}^{\hat{\pi}_{t+1},n}\|_{2}^{2}).$

Suppose that for $\hat{\pi}_{t},$ under the above assumptions, Theorem 2
holds, and the critical radius $\delta_{n/2}$ and for time $t$, function class
specification error
$\|\tau^{\hat{\pi}_{t+1},\circ}_{t}-\tau_{t}^{\hat{\pi}_{t+1},n}\|_{2}$
satisfy the root-mean-squared-error rate conditions:
$\rho^{(c)}_{t},\rho^{(\Psi)}_{t}$

$\delta_{n/2}^{2}=K_{r}^{2}n^{-2\rho^{(c)}_{t}},\qquad\|\tau^{\hat{\pi}_{t+1},\circ}_{t}-\tau_{t}^{\hat{\pi}_{t+1},n}\|_{2}^{2}=K_{\Psi}^{2}n^{-2\rho^{(\Psi)}_{t}}.$

Further define for a generic $t$, $\overline{\rho}_{\geq
t}^{(\cdot)}=\min_{t^{\prime}\geq t}\\{\rho_{t^{\prime}}^{(\cdot)}\\}$, for
$(\cdot)\in\\{(c),(\Psi)\\}.$ Then, with high probability $\geq
n^{-\kappa}$,$\lVert\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{\circ,\underline{\pi}^{*}_{t+1}}\rVert\leq
O(\delta_{n/2}+\|\tau_{t}^{\circ,\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{n,\hat{\underline{\pi}}_{t+1}}\|_{2})+Kn^{-\mathcal{R}_{t}}.$
where

$\textstyle\mathcal{R}_{k}=\min\left(\rho_{k+1}^{(c)}\cdot\frac{2+2\alpha}{2+\alpha},\;\;\rho_{k+1}^{(\Psi)}\cdot\frac{2+2\alpha}{2+\alpha},\;\;\left\\{\min_{k^{\prime}\geq
k+1}(\rho_{k^{\prime}}^{(c)},\rho_{k^{\prime}}^{(\Psi)})\right\\}\cdot\frac{2+2\alpha^{T-k^{\prime}}}{2+\alpha}\right).$

Further suppose that $\alpha>0$ and that for $t^{\prime}\geq t,$ we have that
${\rho}_{t}^{(\cdot)}\leq{\rho}_{t^{\prime}}^{(\cdot)}$, for
$(\cdot)\in\\{(c),(\Psi)\\}$, i.e. the estimation error rate is nonincreasing
over time. Then,

$\lVert\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{\circ,\underline{\pi}^{*}_{t+1}}\rVert\leq
O(\delta_{n/2}+\|\tau_{t}^{\circ,\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{n,\hat{\underline{\pi}}_{t+1}}\|_{2}),$
(7)

and

$\displaystyle\left|\mathbb{E}[V_{1}^{\pi^{*}}(S_{1})-V_{1}^{\hat{\pi}_{\hat{\tau}}}(S_{1})]\right|=O(n^{-\min\\{\overline{\rho}^{(c)}_{\geq
1},\overline{\rho}_{\geq 1}^{(\Psi)}\\}\frac{2+2\alpha}{2+\alpha}}).$

Our method introduces auxiliary estimation at every timestep, so that the
exponentiated terms are higher-order relative to the difference-of-Q one-step
estimation error at every timestep. Note that (Hu et al., 2024) also
establishes margin constants for linear and tabular MDPs.

##  4 Experiments

Table 1: Validation: 1d example, linear FQE vs orthogonal $\tau$ estimation. Entries: Mean-squared error of estimated $\tau$ function, mean + 1.96 standard errors. Method (n) | $5.0\cdot 10^{1}$ | $1.3\cdot 10^{3}$ | $2.5\cdot 10^{3}$ | $3.8\cdot 10^{3}$ | $5.0\cdot 10^{3}$
---|---|---|---|---|---
FQE | $4\cdot 10^{-2}\pm 2\cdot 10^{-2}$ | $2\cdot 10^{-3}\pm 10^{-3}$ | $10^{-3}\pm 10^{-4}$ | $10^{-3}\pm 10^{-4}$ | $4\cdot 10^{-4}\pm 10^{-4}$
OrthDiff-Q | $6\cdot 10^{-2}\pm 3\cdot 10^{-2}$ | $3\cdot 10^{-3}\pm 10^{-3}$ | $2\cdot 10^{-3}\pm 10^{-3}$ | $2\cdot 10^{-3}\pm 10^{-3}$ | $2\cdot 10^{-3}\pm 10^{-4}$

$s^{\rho}_{0}$$s^{\rho_{c}}_{0}$$a_{0}$$r_{0}$$s^{\rho}_{1}$$a_{1}$$r_{1}$$s^{\rho_{c}}_{1}$

$s^{\rho}_{0}$$s^{\rho_{c}}_{0}$$a_{0}$$r_{0}$$s^{\rho}_{1}$$a_{1}$$r_{1}$$s^{\rho_{c}}_{1}$

Figure 1: (Left) Reward-relevant/irrelevant factored dynamics of (Zhou,
2024b). (Right) Exogenous-Endogenous MDP model of (Dietterich et al., 2018).
The dotted line from $a_{t}$ to $s_{t+1}^{\rho_{c}}$ indicates the presence or
absence is permitted in the model.

1d validation. In a very small 1d toy example (Sec 5.1, (Kallus and Uehara,
2019a)) we validate our method. See Appendix C of the appendix for more
details.

Adapting to structure in $\tau(s)$. Recent research highlights the joint
implications of blockwise conditional independence properties in RL, where
some components are considered "exogenous" or irrelevant to rewards and
actions (Wang et al., 2022; Wang et al., ; Dietterich et al., 2018). Most
papers employ a model-based approach to filter out irrelevant factors with
somewhat-intractable mutual information/black-box modified VAEs(Wang et al.,
2022). (An exception is (Efroni et al., 2022) which considers sparsity in
partially controllable linear models, but without orthogonality). Pretesting
approaches such as (Wang et al., ) warrant caution due to poor statistical
properties. Additionally, different underlying structures may lead to the same
sparsity pattern in the advantage function. (Pan and Schölkopf, 2023) studies
whether advantage function estimation can naturally recover the endogenous
component under the model of (Dietterich et al., 2018), in an online RL
setting. In a similar spirit, we assess the benefits of targeting estimation
of the difference-of-Qs in a set of data-generating processes closely related
to specific structural models proposed in the literature ((Zhou, 2024b;
Dietterich et al., 2018)). We find that orthogonal causal contrast estimation
is robust under noisy nuisance functions, as confirmed by our theory, and that
it can adapt to a variety of structures.

Figure 2: Adapting to structure. Simpler setting where $E[M_{1}-M_{0}]=0\cdot
I.$

Figure 3: Adapting to structure. Interacted setting where
$E[M_{1}-M_{0}]=0.1\cdot I.$

First we describe the modified Reward-Filtered DGP (left, figs. 2 and 3) of
(Zhou, 2024b). In the DGP, $|\mathcal{S}|=50$ though the first $|\rho|=10$
dimensions are the reward-relevant sparse component, where $\rho$ is the
indicator vector of the sparse support, and $\mathcal{A}=\\{0,1\\}$. The
reward and states evolve according to
$r_{t}(s,a)=\beta^{\top}\phi_{t}(s,a)+a*(s_{1}+s_{2})/2+\epsilon_{r},\;\;s_{t+1}(s,a)=M_{a}s+\epsilon_{s},$
satisfying the graphical restrictions of Figure 1. Therefore the transition
matrices satisfy the blockwise form
$M_{a}=\begin{bmatrix}M_{a}^{\rho\to\rho}&0\\\
M_{a}^{\rho\to{\rho_{c}}}&M_{a}^{{\rho_{c}}\to{\rho_{c}}}\end{bmatrix},$ we
generate the coefficient matrices $M_{0},M_{1}$ with independent normal random
variables $\sim N(0.2,1)$. The nonzero mean ensures the beta-min condition. We
normalize $M_{a}^{\rho\to\rho}$ to have spectral radius 1; recovering the
sparse component is stable while including distracting dimensions
destabilizes. The zero-mean noise terms are normally distributed with standard
deviations $\sigma_{s}=0.4,\sigma_{r}=0.6.$ In the estimation, we let
$\phi(s,a)=\langle s,s\dot{a},1\rangle$ be the interacted state-action space,
i.e. equivalent to fitting a $q$ function separately for every action. The
behavior policy is a mixture of logistic (with coefficients generated $\sim
N(0,0.3)$) and 20% probability of uniform random sampling. The evaluation
policy is logistic (with coefficients $\sim Unif[-0.5,0.5].$ (The coefficient
vector is fixed within each plot via the random seed).

In Figures 2 and 3 we compare against a strong set of baselines. In blue is
FQE-TL, i.e. naive fitted-Q-evaluation with thresholded Lasso (Zhou, 2010,
2009; Belloni and Chernozhukov, 2013). In dotted cyan is FQE-RF, the reward-
filtered method of (Zhou, 2024b). Note that with the state-action interacted
basis, it is essentially a “T-learner" estimate of reward-thresholded Lasso
$Q$ functions of the difference of $Q$-functions (in the parlance of CATE
meta-learners (Künzel et al., 2019)), a very strong baseline when the $Q$
functions are indeed linear. Next we have three variants of our framework: in
dot-dashed pink $\tau\textrm{-CV}$, orthogonal difference of $Q$ estimation
with loss-function cross-validated $l1$ norm regularization on $\tau$, in
dotted green $\tau\textrm{-TL}$ which uses reward-based thresholding to
estimate $\tau$ on the recovered support. We also investigate semi-synthetic
settings with noisy nuisance functions by adding $N(0,n^{-1/4})$ noise to
nuisance function predictions in dotted-red
$\tau\textrm{-TL-}\hat{\eta}_{\epsilon}$, which also includes sample
splitting. For comparison to illustrate a setting with slow nuisance function
convergence, we also include in dot-dashed purple $\textrm{FQE-
TL-}\hat{\eta}_{\epsilon}$, which adds the $n^{-1/4}$ noise to the first naive
FQE baseline. For our methods, we solve the loss function exactly with CVXPY
(and l1 norm regularization).

We describe the results left to right. We display the median over $100$
replications (fixing the coefficient matrices and vectors, etc. with the same
random seed). The y-axis is the normalized MSE (we divide by the square of the
range of the true difference of $Q$s), and the x axis is the number of
episodes from 100 to 1000 on a log-scale. First on the left, we consider the
previously mentioned reward-filtered DGP. Obviously the tailored method of
(Zhou, 2024a) that was designed for these graphical restrictions does well; it
is also well-specified. Nonetheless we see that our methods with thresholded
LASSO do well, although are slower because they are not tailored for this
graphical restriction. We do see that orthogonality can provide an estimation
rate speed up in the case of noisy nuisances, i.e. the red-dotted line with
noisy nuisance functions indicates the robustness of orthogonal estimation to
slower nuisance function convergence. (The additional sample splitting leads
to small-data concerns in the first plot, though as the difference-of-Q signal
becomes stronger as in the case with Figure 3, these finite sample concerns
lessen.)

In all the experiments, we see that naive cross-validation requires a lot more
data and converges slowly. This is expected due to 1) a large literature
showing how CV Lasso for predictive error doesn’t ensure support recovery
(while methods like thresholded lasso do ensure support recovery) (Belloni and
Chernozhukov, 2013; Hastie et al., 2015) and 2) additional challenges of
hyperparameter tuning in offline RL. This illustrates how recovering the exact
sparse support is crucial.

Next we instead consider a similar DGP in “Misaligned endo-exo", but change
the blockwise conditional independences to follow the exogeneous-endogenous
model of (Dietterich et al., 2018) (see Figure 1, right). We also introduce
some “misalignment" between reward and dynamic sparsity: the entries of
$\beta_{dense}$ are 1 w.p. 0.9 and we add $s^{\top}\beta_{dense}$ to the
reward. In this setting, reward sparsity of $R(s,a),a\in\\{0,1\\}$ alone is
less informative of the underlying sparse component (which is still the first
$|\rho|=10$ dimensions). We see that in small data regimes, this degrades the
performance of the reward-filtered thresholded LASSO method of (Zhou, 2024b):
it, and vanilla thresholded LASSO FQE (FQE-TL) simply includes too many
extraneous dimensions which destabilize estimation. In contrast for small-data
regimes, imposing thresholded LASSO on the difference of $Q$ functions, rather
than the $Q$ functions themselves remains stable. Again, in the large-sample
limit, linear models remain well-specified and performance differences wash
out.

The final DGP of “Nonlinear main effects" introduces nonlinear main effects:
again we generate a $50\%$ dense vector $\beta_{dense}$ and we add
$s^{\top}\beta_{dense}+3\sin(\pi
s_{49}s_{48})+0.5(s_{49}-0.5)^{2}+0.5(s_{48}-0.5)^{2}$. (These nonlinear main
effects are therefore disjoint from the sparse set and sparse difference-of-Q
terms). Our FQE baselines now use kernel ridge regression (KRR), a very strong
baseline for nonlinear regression. For small $n$, FQE wrongly includes
extraneous dimensions that destabilize estimation, and our methods directly
estimating $\tau$ with reward-thresholded-LASSO outperform even KRR for small
data sizes. (With large enough data, KRR is well-specified.)

Limitations.  To summarize limitations, as with other causal inference
approaches, our approach requires certain assumptions, such as causal
identification (which could be relaxed with sensitivity analysis). Our
approach was also motivated by settings with direct sparsity in contrasted
rewards and dynamics; instead this could be true in some representation of the
states/actions.

Conclusions We estimated the contrasts of $Q$ functions with orthogonal
estimation which adapts to structure. Important directions for future work
include methods that address the proxy loss issue (Antos et al., 2008), model
selection, representation-learning, and other techniques from machine learning
and causal inference that incorporate inductive bias of learning causal
contrasts.

## References

  * (1)
  * mur (2003) (2003).  Optimal dynamic treatment regimes.  Journal of the Royal Statistical Society Series B: Statistical Methodology 65(2), 331–355.
  * Antos et al. (2008) Antos, A., C. Szepesvári, and R. Munos (2008).  Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path.  Machine Learning 71, 89–129.
  * Belloni and Chernozhukov (2013) Belloni, A. and V. Chernozhukov (2013).  Least squares after model selection in high-dimensional sparse models.  Bernoulli.
  * Chakraborty and Murphy (2014) Chakraborty, B. and S. A. Murphy (2014).  Dynamic treatment regimes.  Annual review of statistics and its application 1, 447–464.
  * Chernozhukov et al. (2018) Chernozhukov, V., D. Chetverikov, M. Demirer, E. Duflo, C. Hansen, W. Newey, and J. Robins (2018).  Double/debiased machine learning for treatment and structural parameters.
  * Chernozhukov et al. (2024) Chernozhukov, V., C. Hansen, N. Kallus, M. Spindler, and V. Syrgkanis (2024).  Applied causal inference powered by ml and ai.  rem 12(1), 338.
  * Dietterich et al. (2018) Dietterich, T., G. Trimponias, and Z. Chen (2018).  Discovering and removing exogenous state variables and rewards for reinforcement learning.  In International Conference on Machine Learning, pp. 1262–1270. PMLR.
  * Duan et al. (2021) Duan, Y., C. Jin, and Z. Li (2021).  Risk bounds and rademacher complexity in batch reinforcement learning.  In International Conference on Machine Learning, pp. 2892–2902. PMLR.
  * Efroni et al. (2022) Efroni, Y., S. Kakade, A. Krishnamurthy, and C. Zhang (2022).  Sparsity in partially controllable linear systems.  In International Conference on Machine Learning, pp. 5851–5860. PMLR.
  * Foster and Syrgkanis (2019) Foster, D. J. and V. Syrgkanis (2019).  Orthogonal statistical learning.  arXiv preprint arXiv:1901.09036.
  * Hastie et al. (2015) Hastie, T., R. Tibshirani, and M. Wainwright (2015).  Statistical learning with sparsity.  Monographs on statistics and applied probability 143(143), 8.
  * Hu et al. (2024) Hu, Y., N. Kallus, and M. Uehara (2024).  Fast rates for the regret of offline reinforcement learning.  Mathematics of Operations Research.
  * Jiang and Li (2016) Jiang, N. and L. Li (2016).  Doubly robust off-policy value evaluation for reinforcement learning.  Proceedings of the 33rd International Conference on Machine Learning.
  * Jin et al. (2021) Jin, Y., Z. Yang, and Z. Wang (2021).  Is pessimism provably efficient for offline rl?  In International Conference on Machine Learning, pp. 5084–5096. PMLR.
  * Kallus and Uehara (2019a) Kallus, N. and M. Uehara (2019a).  Double reinforcement learning for efficient off-policy evaluation in markov decision processes.  arXiv preprint arXiv:1908.08526.
  * Kallus and Uehara (2019b) Kallus, N. and M. Uehara (2019b).  Efficiently breaking the curse of horizon: Double reinforcement learning in infinite-horizon processes.  arXiv preprint arXiv:1909.05850.
  * Kallus and Zhou (2022) Kallus, N. and A. Zhou (2022).  Stateful offline contextual policy evaluation and learning.  In International Conference on Artificial Intelligence and Statistics, pp. 11169–11194. PMLR.
  * Kennedy (2020) Kennedy, E. H. (2020).  Optimal doubly robust estimation of heterogeneous causal effects.  arXiv preprint arXiv:2004.14497.
  * Kennedy (2022) Kennedy, E. H. (2022).  Semiparametric doubly robust targeted double machine learning: a review.  arXiv preprint arXiv:2203.06469.
  * Künzel et al. (2019) Künzel, S. R., J. S. Sekhon, P. J. Bickel, and B. Yu (2019).  Metalearners for estimating heterogeneous treatment effects using machine learning.  Proceedings of the national academy of sciences 116(10), 4156–4165.
  * Le et al. (2019) Le, H., C. Voloshin, and Y. Yue (2019).  Batch policy learning under constraints.  In International Conference on Machine Learning, pp. 3703–3712. PMLR.
  * Lewis and Syrgkanis (2021) Lewis, G. and V. Syrgkanis (2021).  Double/debiased machine learning for dynamic treatment effects.  Advances in Neural Information Processing Systems 34.
  * Li et al. (2019) Li, F., L. E. Thomas, and F. Li (2019).  Addressing extreme propensity scores via the overlap weights.  American journal of epidemiology 188(1), 250–257.
  * Liu et al. (2018) Liu, Q., L. Li, Z. Tang, and D. Zhou (2018).  Breaking the curse of horizon: Infinite-horizon off-policy estimation.  In Advances in Neural Information Processing Systems, pp. 5356–5366.
  * Morzywolek et al. (2023) Morzywolek, P., J. Decruyenaere, and S. Vansteelandt (2023).  On a general class of orthogonal learners for the estimation of heterogeneous treatment effects.  arXiv preprint arXiv:2303.12687.
  * Neumann and Peters (2008) Neumann, G. and J. Peters (2008).  Fitted q-iteration by advantage weighted regression.  Advances in neural information processing systems 21.
  * Nie et al. (2021) Nie, X., E. Brunskill, and S. Wager (2021).  Learning when-to-treat policies.  Journal of the American Statistical Association 116(533), 392–409.
  * Nie and Wager (2021) Nie, X. and S. Wager (2021).  Quasi-oracle estimation of heterogeneous treatment effects.  Biometrika 108(2), 299–319.
  * Pan and Schölkopf (2023) Pan, H.-R. and B. Schölkopf (2023).  Learning endogenous representation in reinforcement learning via advantage estimation.  In Causal Representation Learning Workshop at NeurIPS 2023.
  * Schulte et al. (2014) Schulte, P. J., A. A. Tsiatis, E. B. Laber, and M. Davidian (2014).  Q-and a-learning methods for estimating optimal dynamic treatment regimes.  Statistical science: a review journal of the Institute of Mathematical Statistics 29(4), 640.
  * Shi et al. (2022) Shi, C., S. Luo, H. Zhu, and R. Song (2022).  Statistically efficient advantage learning for offline reinforcement learning in infinite horizons.  arXiv preprint arXiv:2202.13163.
  * Thomas et al. (2015) Thomas, P., G. Theocharous, and M. Ghavamzadeh (2015).  High confidence policy improvement.  In International Conference on Machine Learning, pp. 2380–2388.
  * Tsybakov (2004) Tsybakov, A. B. (2004).  Optimal aggregation of classifiers in statistical learning.  The Annals of Statistics 32(1), 135–166.
  * Wager and Athey (2018) Wager, S. and S. Athey (2018).  Estimation and inference of heterogeneous treatment effects using random forests.  Journal of the American Statistical Association 113(523), 1228–1242.
  * Wainwright (2019) Wainwright, M. J. (2019).  High-dimensional statistics: A non-asymptotic viewpoint, Volume 48.  Cambridge university press.
  * Wang et al. (2022) Wang, T., S. S. Du, A. Torralba, P. Isola, A. Zhang, and Y. Tian (2022).  Denoised mdps: Learning world models better than the world itself.  arXiv preprint arXiv:2206.15477.
  * (38) Wang, Z., X. Xiao, Y. Zhu, and P. Stone.  Task-independent causal state abstraction.
  * Xie et al. (2023) Xie, C., W. Yang, and Z. Zhang (2023).  Semiparametrically efficient off-policy evaluation in linear markov decision processes.  In International Conference on Machine Learning, pp. 38227–38257. PMLR.
  * Xie et al. (2021) Xie, T., C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal (2021).  Bellman-consistent pessimism for offline reinforcement learning.  Advances in neural information processing systems 34, 6683–6694.
  * Xu et al. (2021) Xu, T., Z. Yang, Z. Wang, and Y. Liang (2021).  Doubly robust off-policy actor-critic: Convergence and optimality.  In International Conference on Machine Learning, pp. 11581–11591. PMLR.
  * Zhou (2024a) Zhou, A. (2024a).  Optimal and fair encouragement policy evaluation and learning.  Advances in Neural Information Processing Systems 36.
  * Zhou (2024b) Zhou, A. (2024b).  Reward-relevance-filtered linear offline reinforcement learning.
  * Zhou (2009) Zhou, S. (2009).  Thresholding procedures for high dimensional variable selection and statistical estimation.  Advances in Neural Information Processing Systems 22.
  * Zhou (2010) Zhou, S. (2010).  Thresholded lasso for high dimensional variable selection and statistical estimation.  arXiv preprint arXiv:1002.1583.

##  Appendix A Proofs

###  A.1 Preliminaries

######  Lemma 3 (Excess Variance ).

$\mathbb{E}[\hat{\mathcal{L}}_{t}(\tau,\eta)]-{\mathcal{L}}_{t}(\tau,\eta)=\operatorname{Var}[\max_{a^{\prime}}Q\left(S_{t+1},a^{\prime}\right)\mid\pi_{t}^{b}]$

###### Proof.

$\displaystyle\mathbb{E}[\hat{\mathcal{L}}_{t}(\tau,\eta)]$
$\displaystyle=\mathbb{E}[\left(\\{R_{t}+\gamma
Q_{t+1}^{\pi^{e}}(S_{t+1},A_{t+1})-m^{\pi}_{t}(S_{t})\\}\pm\mathbb{E}[\gamma
Q_{t+1}^{\pi^{e}}\mid S_{t},\pi_{t}^{b}]-\\{A-\pi^{b}_{t}(1\mid
S_{t})\\}\cdot\tau(S_{t})\right)^{2}]$
$\displaystyle=\mathbb{E}[\left(\\{R_{t}+\gamma\mathbb{E}[Q_{t+1}^{\pi^{e}}\mid
S_{t},\pi_{t}^{b}]-m^{\pi}_{t}(S_{t})\\}-\\{A-\pi^{b}_{t}(1\mid
S_{t})\\}\cdot\tau(S_{t})+\gamma(Q_{t+1}^{\pi^{e}}(S_{t+1},A_{t+1})-\mathbb{E}[Q_{t+1}^{\pi^{e}}\mid
S_{t},\pi_{t}^{b}])\right)^{2}]$
$\displaystyle=\mathbb{E}[\left(\\{R_{t}+\gamma\mathcal{T}Q_{t+1}^{\pi^{e}}-m^{\pi}_{t}\\}-\\{A-\pi^{b}_{t}(1\mid
S_{t})\\}\cdot\tau(S_{t})\right)^{2}]$ (squared loss of identifying moment)
$\displaystyle\;\;+\mathbb{E}[\gamma(Q_{t+1}^{\pi^{e}}(S_{t+1},A_{t+1})-\mathbb{E}[Q_{t+1}^{\pi^{e}}\mid
S_{t},\pi_{t}^{b}])^{2}]$ (residual variance of $Q_{t}(s,a)-R_{t}(s,a)$)
$\displaystyle\;\;+\mathbb{E}[\left\\{R_{t}+\gamma\mathbb{E}[Q_{t+1}^{\pi^{e}}\mid
S_{t},\pi_{t}^{b}]-m^{\pi}_{t}(S_{t})-\\{A-\pi^{b}_{t}(1\mid
S_{t})\\}\cdot\tau(S_{t})\right\\}\cdot\gamma(Q_{t+1}^{\pi^{e}}(S_{t+1},A_{t+1})-\mathbb{E}[Q_{t+1}^{\pi^{e}}\mid
S_{t},\pi_{t}^{b}])]$

Note the last term $=0$ by iterated expectations and the pull-out property of
conditional expectation. ∎

###  A.2 Orthogonality

Below we will omit the $\pi$ superscript; the analysis below holds for any
valid $\pi$. Define
$\nu_{t}=\hat{\tau}_{t}-\tau_{t}^{n},\nu_{t}^{\circ}=\hat{\tau}_{t}-\tau_{t}^{{\circ}}$.
We define for any functional $L(f)$ the Frechet derivative as:

$D_{f}L(f)[\nu]=\left.\frac{\partial}{\partial t}L(f+t\nu)\right|_{t=0}$

Higher order derivatives are denoted as $D_{g,f}L(f,g)[\mu,\nu]$.

######  Lemma 4 (Universal Orthogonality).

$D_{\eta,\tau_{t}}\mathcal{L}_{t}(\tau_{t}^{n};\tau_{t+1}^{n},\eta^{*})[\eta-\eta^{*},\nu_{t}]=0$

###### Proof of Lemma 4.

For brevity, for a generic $f$, let $\\{f\\}_{\epsilon}$ denote
$f+\epsilon(f-f^{\circ})$. Then the first Frechet derivatives are:

$\displaystyle\frac{d}{d_{\epsilon_{\tau}}}\mathcal{L}_{t}(\tilde{\tau},\eta^{\circ})[\tau-\tilde{\tau},\eta-\eta^{\circ}]=\mathbb{E}\left[\left\\{R_{t}+\gamma\\{Q_{t+1}^{\pi^{e},\circ}\\}_{\epsilon}-\\{m_{t}^{\underline{\pi}^{e},\circ}\\}_{\epsilon}-(A_{t}-\\{\pi^{b,\circ}_{t}\\}_{\epsilon})\tau\right\\}(A_{t}-\\{\pi_{t}^{b,\circ}\\}_{\epsilon})(\tilde{\tau}-\tau)\right]$

$\displaystyle\frac{d}{d\epsilon_{e}}\frac{d}{d\epsilon_{\tau}}\mathcal{L}_{t}\left(\tilde{\tau},\eta^{\circ}\right)\left[\eta-\eta^{\circ},\tau-\tau\right]\Big{|}_{\epsilon=0}$
$\displaystyle\qquad=\mathbb{E}\left[\left(\pi_{t}^{b}-\pi_{t}^{b,\circ}\right)\tau(\tau-\tilde{\tau})(A_{t}-e_{t})]+\right.\mathbb{E}\left[\left\\{R+\gamma
Q_{t+1}^{\pi^{e}}-m_{t}^{\underline{\pi}^{e},\circ}-\left(A_{t}-e_{t}\right)\right\\}(\tau-\tilde{\tau})\cdot-\left(e_{t}-e_{t}^{\circ}\right)\right]$
$\displaystyle\qquad=0$
$\displaystyle\frac{d}{d\epsilon_{Q_{t+1}}}\frac{d}{d\epsilon_{\tau}}\mathcal{L}_{t}\left(\tilde{\tau},\eta^{\circ}\right)\left[\eta-\eta^{\circ},\tau-\tilde{\tau}\right]\Big{|}_{\epsilon=0}$
$\displaystyle\qquad=\mathbb{E}[\gamma(Q_{t+1}^{\pi^{e}}-Q_{t+1}^{\pi^{e},\circ})(A_{t}-\pi_{t}^{b,\circ})(\tau_{t}-\tilde{\tau}_{t})]]$
$\displaystyle\qquad=0$
$\displaystyle\frac{d}{d\epsilon_{m_{t}}}\frac{d}{d\epsilon_{\tau}}\mathcal{L}_{t}\left(\tilde{\tau},\eta^{\circ}\right)\left[\eta-\eta^{\circ},\tau-\tilde{\tau}\right]\Big{|}_{\epsilon=0}$
$\displaystyle\qquad=\mathbb{E}[-(m_{t}^{\underline{\pi}^{e}}-m_{t}^{\underline{\pi}^{e},\circ})(A_{t}-\pi_{t}^{b,\circ})(\tau_{t}-\tilde{\tau}_{t})]$
$\displaystyle\qquad=0$

∎

######  Lemma 5 (Second order derivatives).

For $Q_{t+1},Q_{t+1}^{\circ}$ evaluated at some fixed policy $\pi^{e}$:

$\displaystyle
D_{\eta_{t},\eta_{t}}\mathcal{L}_{t}[\hat{\eta}_{t}-\eta^{\circ}_{t},\hat{\eta}_{t}-\eta^{\circ}_{t}]$
$\displaystyle\qquad=\mathbb{E}\left[\tau_{t}^{2}\left(\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ}\right)^{2}\right]+\mathbb{E}\left[(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})\tau_{t}(\hat{m}_{t}-m^{\circ}_{t})\right]+\mathbb{E}\left[(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})\tau_{t}\gamma(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\right]$
$\displaystyle\qquad-\mathbb{E}\left[\left(\hat{m}_{t}-m^{\circ}_{t}\right)\gamma\left(\hat{Q}_{t+1}-Q_{t+1}^{\circ}\right)\right]$

###### Proof of Lemma 5.

Below, the evaluation policy $\pi^{e}$ is fixed and omitted for brevity. Note
that

$\displaystyle D_{e}\mathcal{L}_{D}[\hat{e}-e^{\circ}]$
$\displaystyle=\mathbb{E}[(R_{t}+\gamma
Q_{t+1}-\langle\pi^{b},Q_{t}\rangle+(A-\pi_{t}^{b})\tau_{t})(-\tau_{t})(\hat{e}-e^{\circ})]$
$\displaystyle D_{m_{t}}\mathcal{L}_{D}[\hat{m}_{t}-m_{t}^{\circ}]$
$\displaystyle=\mathbb{E}[(R_{t}+\gamma
Q_{t+1}-\langle\pi^{b},Q_{t}\rangle+(A-\pi_{t}^{b})\tau_{t})(-1)*(m_{t}-m^{\circ})]$

By inspection, note that the nonzero terms of the second-order derivatives are
as follows:

$\displaystyle
D_{\pi_{t}^{b},\pi_{t}^{b}}\mathcal{L}_{t}[\hat{\pi}_{t}^{b}-\pi^{b,\circ}_{t},\hat{\pi}_{t}^{b}-\pi^{b,\circ}_{t}]$
$\displaystyle=\mathbb{E}\left[\tau_{t}^{2}\left(\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ}\right)^{2}\right]$
$\displaystyle
D_{m_{t},Q_{t+1}}\mathcal{L}_{t}[\hat{Q}_{t+1}-Q^{\circ}_{t+1},\hat{m}_{t}-m^{\circ}_{t}]$
$\displaystyle=\mathbb{E}\left[-\left(\hat{m}_{t}-m^{\circ}_{t}\right)\gamma\left(\hat{Q}_{t+1}-Q_{t+1}^{\circ}\right)\right]$
$\displaystyle
D_{m_{t},\pi_{t}^{b}}\mathcal{L}_{t}[\hat{\pi}_{t}^{b}-\pi^{b,\circ}_{t},\hat{m}_{t}-m^{\circ}_{t}]$
$\displaystyle=\mathbb{E}\left[(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})\tau_{t}(\hat{m}_{t}-m^{\circ}_{t})\right]$
$\displaystyle
D_{Q_{t+1},\pi_{t}^{b}}\mathcal{L}_{t}[\hat{\pi}_{t}^{b}-\pi^{b,\circ}_{t},\hat{Q}_{t+1}-Q^{\circ}_{t+1}]$
$\displaystyle=\mathbb{E}\left[(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})\tau_{t}\gamma(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\right]$

By the chain rule for Frechet differentiation, we have that

$\displaystyle
D_{\eta_{t},\eta_{t}}\mathcal{L}_{t}[\hat{\eta}_{t}-\eta^{\circ}_{t},\hat{\eta}_{t}-\eta^{\circ}_{t}]=D_{\pi_{t}^{b},\pi_{t}^{b}}\mathcal{L}_{t}[\hat{\pi}_{t}^{b}-\pi^{b,\circ}_{t},\hat{\pi}_{t}^{b}-\pi^{b,\circ}_{t}]$
$\displaystyle\qquad+D_{m_{t},\pi_{t}^{b}}\mathcal{L}_{t}[\hat{\pi}_{t}^{b}-\pi^{b,\circ}_{t},\hat{m}_{t}-m^{\circ}_{t}]+D_{Q_{t+1},\pi_{t}^{b}}\mathcal{L}_{t}[\hat{\pi}_{t}^{b}-\pi^{b,\circ}_{t},\hat{Q}_{t+1}-Q^{\circ}_{t+1}]+D_{m_{t},Q_{t+1}}\mathcal{L}_{t}[\hat{Q}_{t+1}-Q^{\circ}_{t+1},\hat{m}_{t}-m^{\circ}_{t}]$

∎

###  A.3 Proof of sample complexity bounds

###### Proof of Lemma 2.

$\displaystyle V^{*}_{t}(s)-V^{\pi_{\hat{\tau}}}_{t}(s)$
$\displaystyle=V^{*}_{t}(s)-V^{\pi_{\hat{\tau}}}_{t}(s)\pm
Q^{\pi^{*}}(s,\pi_{\hat{\tau}})$
$\displaystyle=Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})+Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})-V^{\hat{\pi}_{\hat{\tau}}}_{t}(s)$
$\displaystyle\leq\gamma\mathbb{E}_{\hat{\pi}_{t}}\left[V_{t+1}^{\pi^{*}}-V_{t+1}^{\hat{\pi}_{\hat{\tau}}}\mid
s\right]+Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})$

Therefore for any $t$ and Markovian policy $\pi$ inducing a marginal state
distribution:

$\mathbb{E}[V^{*}_{t}(s)]-\mathbb{E}[V^{\pi_{\hat{\tau}}}_{t}(s)]\leq\gamma\mathbb{E}\left[\mathbb{E}_{\hat{\pi}_{t}}[V_{{t+1}}^{\pi^{*}}-V_{t+1}^{\hat{\pi}_{\hat{\tau}}}\mid
s]\right]+\mathbb{E}[Q_{t}^{*}(s,\pi^{*})-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})]$
(8)

Assuming bounded rewards implies that $P(s_{t+1}\mid s,a)\leq c$, which
remains true under the state-action distribution induced by any Markovian
policy $\pi(s,a)$, including the optimal policy. Therefore the second term of
the above satisfies:

$\mathbb{E}_{\pi}[Q_{t}^{*}(s_{t},\pi^{*})-Q_{t}^{*}(s_{t},\hat{\pi}_{\hat{\tau}})]\leq
c\int\left\\{Q_{t}^{*}(s,\pi^{*})-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}}\right\\}ds,$
(9)

and fixing $t=1$, we obtain:

$\mathbb{E}[Q_{1}^{*}(s_{1},\pi^{*})-Q_{1}^{*}(s_{1},\hat{\pi}_{\hat{\tau}})]\leq
c\int\left\\{Q_{1}^{*}(s,\pi^{*})-Q_{1}^{*}(s,\hat{\pi}_{\hat{\tau}}\right\\}ds.$

Next we continue for generic $t$ and bound the right hand side term of eq. 9.

First we suppose we have a high-probability bound on $\ell_{\infty}$
convergence of $\hat{\tau}$. Define the good event

$\mathcal{E}_{g}=\left\\{\sup_{s\in\mathcal{S},a\in\mathcal{A}}|\hat{\tau}^{\hat{\underline{\pi}}_{t+1}}(s)-\tau^{\underline{\pi}^{*}_{t+1},\circ}(s)|\leq
Kn^{-b*}\right\\}$

A maximal inequality gives that $P(\mathcal{E}_{g})\geq 1-n^{-\kappa}$. We
have that

$\int\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}ds=\int\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}\mathbb{I}\left[\mathcal{E}_{g}\right]ds+\int\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}\mathbb{I}\left[\mathcal{E}_{g}^{c}\right]ds$
(10)

Assuming boundedness, the bad event occurs with vanishingly small probability
$n^{-\kappa},$ which bounds the second term of eq. 14.

For the first term of eq. 14, note that on the good event, if mistakes occur
such that $\pi_{t}^{*}(s)\neq\hat{\pi}_{t}(s)$, then the true contrast
function is still bounded in magnitude by the good event ensuring closeness of
the estimate, so that
$\left|\tau_{t}^{\underline{\pi}^{*}_{t+1},\circ}(s)\right|\leq 2Kn^{-b_{*}}$.
And if no mistakes occur, at $s$ the contribution to the integral is $0$.
Denote the mistake region as

$\mathcal{S}_{m}=\\{s\in\mathcal{S}\colon\left|\tau_{t}^{\underline{\pi}^{*}_{t+1},\circ}(s)\right|\leq
2Kn^{-b_{*}}\\}$

Therefore

$\int\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}ds\leq\int_{s\in\mathcal{S}_{m}}\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}\mathbb{I}\left[s\in\mathcal{S}_{m}\right]\mathbb{I}\left[\mathcal{E}_{g}\right]ds+O(n^{-\kappa})$
(11)

Note also that (for two actions), if action mistakes occur on the good event
$\mathcal{E}_{g}$, the difference of $Q$ functions must be near the decision
boundaries so that we have the following bound on the integrand:

${|Q^{*}(s,\pi^{*})-Q^{*}(s,\hat{\pi})|\leq|\tau^{\underline{\pi}^{*}_{t+1},\circ}|\leq
2Kn^{-b*}}.$ (12)

Therefore,

$\displaystyle\int\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}ds$
$\displaystyle\leq
O(n^{-\kappa})+Kn^{-b*}\int\mathbb{I}\left[s\in\mathcal{S}_{m}\right]ds$
$\displaystyle\leq O(n^{-\kappa})+(Kn^{-b*})(Kn^{-b*\alpha})$
$\displaystyle=O(n^{-\kappa})+(K^{2}n^{-b*(1+\alpha)})$ (13)

where the first inequality follows from the above, and the second from
assumption 5 (margin).

Combining eqs. 13 and 8, we obtain:

$\displaystyle\mathbb{E}[V^{*}_{t}(S_{t})]-\mathbb{E}[V^{\hat{\pi}_{\hat{\tau}}}_{t}(S_{t})]$
$\displaystyle\leq\sum_{t=1}^{T}\gamma^{t}c\left\\{\int
Q_{t}^{\hat{\pi}_{\hat{\tau}}}(s,\pi^{*}(s))-Q_{t}^{\hat{\pi}_{\hat{\tau}}}(s,\hat{\pi}_{\hat{\tau}})ds\right\\}$
$\displaystyle\leq\frac{(1-\gamma^{T})}{1-\gamma}cT\\{O(n^{-\kappa})+(K^{2}n^{-b*(1+\alpha)})\\}$

We also obtain analogous results for norm bounds:

$\displaystyle\left\\{\int\left(Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right)^{u}ds\right\\}^{1/u}$
$\displaystyle\qquad\leq\left\\{\int_{s\in\mathcal{S}_{m}}(Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}}))^{u}\mathbb{I}\left[s\in\mathcal{S}_{m}\right]\mathbb{I}\left[\mathcal{E}_{g}\right]ds\right\\}^{1/u}+O(n^{-\kappa})$
$\displaystyle\qquad\leq\frac{(1-\gamma^{T})}{1-\gamma}cT\\{O(n^{-\kappa})+(K^{2}n^{-b*(1+\alpha)})\\}$

The results under an integrated risk bound assumption on convergence of $\tau$
follow analogously as (Shi et al., 2022), which we also include for
completeness. For a given $\varepsilon>0$, redefine the mistake region
parametrized by $\epsilon$:

$\mathcal{S}_{\epsilon}=\left\\{\max_{a}Q^{*}(s,a)-Q^{*}\left(s,\hat{\pi}(s)\right)\leq\varepsilon\right\\}.$

Again we obtain the bound by conditioning on the mistake region:

$\int\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}ds=\int\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}\mathbb{I}\left[\mathcal{S}_{\epsilon}\right]ds+\int\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}\mathbb{I}\left[\mathcal{S}_{\epsilon}^{c}\right]ds$
(14)

Using similar arguments as earlier, we can show by Assumption 5:

$\displaystyle\int\left\\{Q_{t}^{*}\left(s,\pi^{*}(s)\right)-Q_{t}^{*}\left(s,\hat{\pi}_{\hat{\tau}}\right)\right\\}\mathbb{I}(s\in\mathcal{S}_{*})ds\leq\varepsilon\int_{x}\mathbb{I}(s\in\mathcal{S}_{*})ds=O\left(\varepsilon^{1+\alpha}\right).$

As previously argued, we can show mistakes
$\pi_{t}^{*}(s)\neq\hat{\pi}_{t}(s)$ occur only when

$\max_{a}Q^{*}_{t}(s,a)-Q^{*}(s,\hat{\pi}(s))\leq
2\left|\hat{\tau}^{\hat{\pi}_{t+1}}(s)-\tau^{\pi_{t+1}^{*},\circ}(s)\right|.$
(15)

It follows that

$\displaystyle\int\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}\mathbb{I}\left[s\in\mathcal{S}_{\epsilon}^{c}\right]ds$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\int\frac{4\left|\hat{\tau}^{\hat{\pi}_{t+1}}(s)-\tau^{\pi_{t+1}^{*},\circ}(s)\right|^{2}}{\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}}\mathbb{I}\left[s\in\mathcal{S}_{\epsilon}^{c}\right]ds$
$\displaystyle\leq$
$\displaystyle\frac{4}{\varepsilon}\int\left|\hat{\tau}^{\hat{\pi}_{t+1}}(s)-\tau^{\pi_{t+1}^{*},\circ}(s)\right|^{2}ds=O\left(\varepsilon^{-1}|\mathcal{I}|^{-2b_{*}}\right).$

Combining this together with (E.106) and (E.107) yields that

$\int\left\\{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})\right\\}ds=O\left(\varepsilon^{1+\alpha}\right)+O\left(\varepsilon^{-1}|\mathcal{I}|^{-2b_{*}}\right).$

The result follows by choosing $\varepsilon=n^{-2b_{*}/(2+\alpha)}$ to balance
the two terms.

For the norm bound, the first term is analogously bounded as
$O\left(\varepsilon^{1+\alpha}\right)$:

$\left\\{\int(Q_{t}^{*}\left(s,\pi^{*}(s)\right)-Q_{t}^{*}\left(s,\hat{\pi}_{\hat{\tau}}\right))^{2}\mathbb{I}[s\in\mathcal{S}_{*}]ds\right\\}^{1/2}=O\left(\varepsilon^{1+\alpha}\right).$

For the second term,

$\displaystyle\left\\{\int(Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}}))^{2}\mathbb{I}\left[s\in\mathcal{S}_{\epsilon}^{c}\right]ds\right\\}^{1/2}\leq\left\\{\int\left(\frac{4\left|\hat{\tau}^{\hat{\pi}_{t+1}}(s)-\tau^{\pi_{t+1}^{*},\circ}(s)\right|^{2}}{Q_{t}^{*}(s,\pi^{*}(s))-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}})}\right)^{2}\mathbb{I}\left[s\in\mathcal{S}_{\epsilon}^{c}\right]ds\right\\}^{1/2}$
$\displaystyle\leq$
$\displaystyle\frac{4}{\varepsilon}\\{\int\left|\hat{\tau}^{\hat{\pi}_{t+1}}(s)-\tau^{\pi_{t+1}^{*},\circ}(s)\right|^{4}ds\\}^{1/2}=O\left(\varepsilon^{-1}|\mathcal{I}|^{-2b_{*}}\right).$

The result follows as previous. ∎

###### Proof of Theorem 1.

In the following, at times we omit the fixed evaluation policy $\pi^{e}$ from
the notation for brevity. That is, in this proof,
$\hat{\tau}_{t},\tau_{t}^{n}$ are equivalent to
$\hat{\tau}_{t}^{\pi^{e}},\tau_{t}^{n,\pi^{e}}.$ Further define

$\nu_{t}=\hat{\tau}_{t}-\tau_{t}^{n},\nu_{t}^{\circ}=\hat{\tau}_{t}-\tau_{t}^{{\circ}}$

Strong convexity of the squared loss implies that:

$D_{\tau_{t},\tau_{t}}\mathcal{L}\left(\tau_{t},\hat{\eta}\right)\left[\nu_{t},\nu_{t}\right]\geq\lambda\left\|\nu_{t}\right\|_{2}^{2}$

therefore

$\displaystyle\frac{\lambda}{2}\left\|\nu_{t}\right\|_{2}^{2}$
$\displaystyle\leq\mathcal{L}_{D}(\hat{\tau}_{t},\hat{\eta})-\mathcal{L}_{D}(\tau_{t}^{n},\hat{\eta})-D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\hat{\eta})[\nu_{t}]$
(16)
$\displaystyle\leq\epsilon(\hat{\tau}_{t},\hat{\eta})-D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\eta^{\circ})[\nu_{t}]$
$\displaystyle\qquad+D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\eta^{\circ})[\nu_{t}]-D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\hat{\eta})[\nu_{t}]$

We bound each term in turn.

To bound
$\left|D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\eta^{\circ})[\nu_{t}]\right|,$
note that

$D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\eta^{\circ})[\nu_{t}]=\mathbb{E}[(R+\gamma
Q_{t+1}-V_{t}^{\pi^{b},\pi_{t+1:T}}+\left(A-\pi_{t}^{b}\right)\mathcal{\tau}_{t}))\left(A-\pi_{t}^{b}\right)\nu_{t}]$

and by the properties of the conditional moment at the true $\tau^{\circ},$

$=\mathbb{E}[(R+\gamma
Q_{t+1}-V_{t}^{\pi^{b},\pi_{t+1:T}}+\left(A-\pi_{t}^{b}\right)\mathcal{\tau}_{t}^{\circ}))\left(A-\pi_{t}^{b}\right)\nu_{t}]=0$

Therefore,

$D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\eta^{\circ})[\nu_{t}]=-\mathbb{E}[(\tau^{\circ}-\tau_{t}^{n})(A-\pi_{t}^{b})(A-\pi_{t}^{b})(\hat{\tau}_{t}-\tau_{t}^{n})]$

Note that in general, for generic $p,q,r$ such that $1/p+1/q+1/r=1$ we have
that
$\mathbb{E}[fgh]\leq\|fg\|_{p^{\prime}}\|h\|_{r}\leq\|f\|_{p}\|g\|_{q}\|h\|_{r}$
where $p^{\prime}=\frac{pq}{p+q}$ or
$\frac{1}{p^{\prime}}=\frac{1}{p}+\frac{1}{q}$ or
$1=\frac{1}{p/p^{\prime}}+\frac{1}{q/p^{\prime}}$.

Therefore,

$\displaystyle
D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\eta^{\circ})[\nu_{t}]$
$\displaystyle\leq\left|D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\eta^{\circ})[\nu_{t}]\right|$
$\displaystyle\leq\mathbb{E}[(\tau^{\circ}-\tau_{t}^{n})\mathbb{E}[(A_{t}-\pi_{t}^{b})(A_{t}-\pi_{t}^{b})\mid
S_{t}](\hat{\tau}_{t}-\tau_{t}^{n})]$
$\displaystyle\leq\lVert(\tau^{\circ}-\tau_{t}^{n})\rVert_{u}\lVert(\hat{\tau}_{t}-\tau_{t}^{n})\rVert_{\overline{u}}\cdot\left\\{\sup_{s}\mathbb{E}[(A_{t}-\pi_{t}^{b})(A_{t}-\pi_{t}^{b})\mid
s]\right\\}$

where $u,\overline{u}$ satisfy $\frac{1}{u}+\frac{1}{\overline{u}}=1.$

Next we bound
$D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\eta^{\circ})[\nu_{t}]-D_{\tau_{t}}\mathcal{L}_{D}(\tau_{t}^{n},\hat{\eta})[\nu_{t}]$
by universal orthogonality. By a second order Taylor expansion, we have that,
where $\eta_{\epsilon}=\eta^{\circ}+\epsilon(\hat{\eta}-\eta^{\circ}).$

$\displaystyle
D_{\tau_{t}}\left(\mathcal{L}_{D}(\tau_{t}^{n},\eta^{\circ})-\mathcal{L}_{D}(\tau_{t}^{n},\hat{\eta})\right)[\nu_{t}]=\frac{1}{2}\int_{0}^{1}D_{\eta,\eta,\tau_{t}}(\tau_{t}^{n},\tau_{t+1}^{\circ},\eta_{\epsilon})[\hat{\eta}-\eta^{\circ},\hat{\eta}-\eta^{\circ},\nu_{t}]$

We can deduce from Lemmas 5 and 4 that the integrand is:

$\displaystyle\mathbb{E}\left[\tau_{t}^{2}\left(\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ}\right)^{2}\nu_{t}\right]+\mathbb{E}\left[(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})\tau_{t}(\hat{m}_{t}-m^{\circ}_{t})\nu_{t}\right]+\mathbb{E}\left[(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})\tau_{t}\gamma(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\nu_{t}\right]$
$\displaystyle\qquad-\mathbb{E}\left[\left(\hat{m}_{t}-m^{\circ}_{t}\right)\gamma\left(\hat{Q}_{t+1}-Q_{t+1}^{\circ}\right)\nu_{t}\right]$
$\displaystyle\leq$
$\displaystyle{B_{\tau}}^{2}\lVert\left(\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ}\right)^{2}\rVert_{u}\lVert\nu_{t}\rVert_{\overline{u}}+B_{\tau}\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{m}_{t}-m^{\circ}_{t})\rVert_{u}\lVert\nu_{t}\rVert_{\overline{u}}+\gamma
B_{\tau}\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\rVert_{u}\lVert\nu_{t}\rVert_{\overline{u}}$
$\displaystyle\qquad+\gamma\lVert(\hat{m}_{t}-m^{\circ}_{t})(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\rVert_{u}\lVert\nu_{t}\rVert_{\overline{u}}$

Putting the bounds together, we obtain:

$\displaystyle\frac{\lambda}{2}\left\|\nu_{t}\right\|_{2}^{2}$
$\displaystyle\leq\epsilon(\hat{\tau}_{t},\hat{\eta})+\lVert\nu_{t}\rVert_{\overline{u}}\lVert(\tau^{\circ}-\tau_{t}^{n})\rVert_{u}$
$\displaystyle\qquad+\lVert\nu_{t}\rVert_{\overline{u}}\left({B_{\tau}}^{2}\lVert\left(\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ}\right)^{2}\rVert_{u}+B_{\tau}\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{m}_{t}-m^{\circ}_{t})\rVert_{u}+\gamma
B_{\tau}\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\rVert_{u}\right.$
$\displaystyle\qquad\qquad\qquad\left.+\gamma\lVert(\hat{m}_{t}-m^{\circ}_{t})(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\rVert_{u}\right)$
(17)

Let $\rho_{t}^{\pi^{e}}(\hat{\eta})$ denote the collected product error terms,
e.g.

$\displaystyle\rho_{t}^{\pi^{e}}(\hat{\eta})$
$\displaystyle={B_{\tau}}^{2}\lVert\left(\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ}\right)^{2}\rVert_{u}+B_{\tau}\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{m}_{t}-m^{\circ}_{t})\rVert_{u}$
$\displaystyle\qquad+\gamma(B_{\tau}\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\rVert_{u}+\lVert(\hat{m}_{t}-m^{\circ}_{t})(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\rVert_{u})$

Analogously we drop the $\pi^{e}$ decoration from $\rho_{t}$ in this proof.
The AM-GM inequality implies that for $x,y\geq 0,$ $\sigma>0$, we have that
$xy\leq\frac{1}{2}(\frac{2}{\sigma}x^{2}+\frac{\sigma}{2}y^{2}).$ Therefore

$\frac{\lambda}{2}\left\|\nu_{t}\right\|_{2}^{2}-\frac{\sigma}{4}\lVert\nu_{t}\rVert_{\overline{u}}^{2}\leq\epsilon(\hat{\tau}_{t},\hat{\eta})+\frac{1}{\sigma}\left(\lVert(\tau^{\circ}-\tau_{t}^{n})\rVert_{u}+\rho_{t}(\hat{\eta})\right)^{2}$
(18)

and since $(x+y)^{2}\leq 2(x^{2}+y^{2}),$

$\frac{\lambda}{2}\left\|\nu_{t}\right\|_{2}^{2}-\frac{\sigma}{4}\lVert\nu_{t}\rVert_{\overline{u}}^{2}\leq\epsilon(\hat{\tau}_{t},\hat{\eta})+\frac{2}{\sigma}\left(\lVert(\tau^{\circ}-\tau_{t}^{n})\rVert_{u}^{2}+\rho_{t}(\hat{\eta})^{2}\right)$

∎

###### Proof of Theorem 2.

Let $\hat{\mathcal{L}}_{S,t},\hat{\mathcal{L}}_{S^{\prime},t}$ denote the
empirical loss over the samples in $S$ and $S^{\prime}$; analogously
$\hat{\eta}_{S},\hat{\eta}_{S^{\prime}}$ are the nuisance functions trained on
each sample split.

Define the loss function $\ell_{t}$ on observation
$O=\\{(S_{t},A_{t},R_{t},S_{t+1})\\}_{t=1}^{T}$:

$\ell_{t}(O;\tau_{t};\hat{\eta})=\left(\\{R_{t}+\hat{Q}_{t+1}^{\underline{\pi}^{e}_{t+1}}(S_{t+1},A_{t+1})-\hat{m}_{t}(S_{t})\\}-\\{A-\hat{\pi}^{b}_{t}(1\mid
S_{t})\\}\cdot\tau_{t}(S_{t})\right)^{2}$

and the centered loss function $\Delta\ell$, centered with respect to
$\hat{\tau}_{t}^{n}$:

$\Delta\ell_{t}(O;\tau_{t};\hat{\eta})=\ell_{t}(O;\tau_{t};\hat{\eta})-\ell_{t}(O;\hat{\tau}_{t}^{n};\hat{\eta}).$

Assuming boundedness, $\ell_{t}$ is $L-$Lipschitz constant in $\tau_{t}$:

$\left|\Delta\ell_{t}(O;\tau_{t};\hat{\eta})-\Delta\ell_{t}(O;\tau_{t}^{\prime};\hat{\eta})\right|\leq
L\lVert\tau_{t}-\tau_{t}\rVert_{2}.$

Note that $\ell(O,\hat{\tau}_{t}^{n},\hat{\eta})=0.$ Define the centered
average losses:

$\displaystyle\Delta\hat{\mathcal{L}}_{S,t}(\tau_{t},\hat{\eta})$
$\displaystyle=\hat{\mathcal{L}}_{S,t}(\tau_{t},\hat{\eta})-\hat{\mathcal{L}}_{S,t}(\hat{\tau}_{t}^{n},\hat{\eta})=\hat{\mathbb{E}}_{n/2}^{S}[\Delta\ell_{t}(O,\tau_{T},\hat{\eta})]$
$\displaystyle\Delta{\mathcal{L}}_{S,t}(\tau_{t},\hat{\eta})$
$\displaystyle={\mathcal{L}}_{S,t}(\tau_{t},\hat{\eta})-{\mathcal{L}}_{S,t}(\hat{\tau}_{t}^{n},\hat{\eta})=\mathbb{E}[\Delta\ell_{t}(O,\tau_{T},\hat{\eta})]$

Assume that $\delta_{n}$ is an upper bound on the critical radius of the
centered function class $\\{\Psi_{t,i}^{n}-\hat{\tau}_{t,i}^{n}$, with
$\delta_{n}=\Omega(\frac{r\log\log n}{n}),$ and define
$\delta_{n,\xi}=\delta_{n}+c_{0}\sqrt{\frac{\log(c_{1}T/\xi)}{n}}$ for some
$c_{0},c_{1}$.

By Lemma 7 (Lemma 14 of (Foster and Syrgkanis, 2019) on local Rademacher
complexity decompositions), with high probability 1-$\xi$, for all $t\in[T],$
and for $c_{0}$ a universal constant $\geq 1.$

$\displaystyle\left|\Delta\mathcal{L}_{S,t}(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})-\Delta\mathcal{L}_{D,t}(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})\right|$
$\displaystyle=\left|\Delta\mathcal{L}_{S,t}(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})-\Delta\mathcal{L}_{S,t}(\hat{\tau}_{t}^{n},\hat{\eta}_{S^{\prime}})-(\Delta\mathcal{L}_{D,t}(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})-\Delta\mathcal{L}_{D,t}(\hat{\tau}_{t}^{n},\hat{\eta}_{S^{\prime}}))\right|$
$\displaystyle\leq
c_{0}\left(rm\delta_{n/2,\xi}\lVert\hat{\tau}_{t}-\hat{\tau}^{n}_{t}\rVert_{2}^{2}+rm\delta_{n/2,\xi}^{2}\right)$

Assuming realizability of $\hat{\tau}_{t}$, we have that
$\frac{1}{2}\left(\Delta\hat{\mathcal{L}}_{S,t}(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})+\Delta\hat{\mathcal{L}}_{S^{\prime},t}(\hat{\tau}_{t},\hat{\eta}_{S})\right)\leq
0.$ Then with high probability $\geq 1-2\xi$:

$\displaystyle\frac{1}{2}\left(\Delta\mathcal{L}_{D,t}(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})+\Delta\mathcal{L}_{D,t}(\hat{\tau}_{t},\hat{\eta}_{S})\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\left|\Delta\mathcal{L}_{D,t}(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})-\Delta\mathcal{L}_{S,t}(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})+\Delta\mathcal{L}_{D,t}(\hat{\tau}_{t},\hat{\eta}_{S})-\Delta\mathcal{L}_{S^{\prime},t}(\hat{\tau}_{t},\hat{\eta}_{S})\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\left|\Delta\mathcal{L}_{D,t}(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})-\Delta\mathcal{L}_{S,t}(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})\right|+\left|\Delta\mathcal{L}_{D,t}(\hat{\tau}_{t},\hat{\eta}_{S})-\Delta\mathcal{L}_{S^{\prime},t}(\hat{\tau}_{t},\hat{\eta}_{S})\right|$
$\displaystyle\leq$ $\displaystyle
c_{0}\left(rm\delta_{n/2,\xi}\lVert\hat{\tau}_{t}-\hat{\tau}^{n}_{t}\rVert_{2}+rm\delta_{n/2,\xi}^{2}\right)$

The $\epsilon$ excess risk term in Theorem 1 indeed corresponds to one of the
loss differences defined here, i.e.
$\Delta\mathcal{L}_{D,t}\left({\hat{\tau}}_{t},\hat{\eta}_{S}\right):=\epsilon(\hat{\tau}_{t}^{n},\hat{\tau}_{t},\hat{h}_{S}).$
Therefore, applying Theorem 1 with $u=\overline{u}=2$ and $\sigma=\lambda$
with the above bound, and averaging the sample-split estimators, we obtain

$\frac{\lambda}{4}\left\|\nu_{t}\right\|_{2}^{2}\leq\frac{1}{2}\left(\epsilon(\hat{\tau}_{t},\hat{\eta}_{S})+\epsilon(\hat{\tau}_{t},\hat{\eta}_{S^{\prime}})\right)+\frac{2}{\lambda}\left(\left\|\tau^{\circ}_{t}-\hat{\tau}_{t}^{n}\right\|_{2}^{2}+\sum_{s\in\\{S,S^{\prime}\\}}\rho_{t}(\hat{\eta}_{s})^{2}\right)$

We further decompose the excess risk of empirically-optimal $\hat{\tau}_{t}$
relative to the population minimizer to instead bound by the error of
$\hat{\tau}_{t}$ to the projection onto $\Psi$, $\hat{\tau}_{t}^{n}$, since
$\left\|\hat{\tau}_{t}-\tau_{t}^{\circ}\right\|_{2}^{2}\leq\left\|\hat{\tau}_{t}-\hat{\tau}_{t}^{n}\right\|_{2}^{2}+\left\|\hat{\tau}_{t}^{n}-\tau_{t}^{\circ}\right\|_{2}^{2},$
we obtain

$\displaystyle\frac{\lambda}{4}\lVert\hat{\tau}_{t}-\tau_{t}^{\circ}\rVert_{2}^{2}\leq{c_{0}}\left(rm\delta_{n/2,\xi}\lVert\hat{\tau}_{t}-\hat{\tau}^{n}_{t}\rVert_{2}+rm\delta_{n/2,\xi}^{2}\right)+\frac{8+\lambda^{2}}{4\lambda}\left\|\tau^{\circ}_{t}-\tau_{t}^{n}\right\|_{2}^{2}+\frac{2}{\lambda}\sum_{s\in\\{S,S^{\prime}\\}}\rho_{t}(\hat{\eta}_{s})^{2}$

Again using the AM-GM inequality
$xy\leq\frac{1}{2}\left(\frac{2}{\sigma}x^{2}+\frac{\sigma}{2}y^{2}\right)$,
we bound

$\displaystyle{c_{0}}\left(rm\delta_{n/2,\xi}\lVert\hat{\tau}_{t}-\hat{\tau}^{n}_{t}\rVert_{2}+rm\delta_{n/2,\xi}^{2}\right)$
$\displaystyle\leq\frac{c_{0}}{2}r^{2}m^{2}(1+\frac{2}{\epsilon})\delta_{n/2,\xi}^{2}+\frac{\epsilon}{4}\lVert\hat{\tau}_{t}-\hat{\tau}^{n}_{t}\rVert_{2}^{2}$
$\displaystyle\leq{c_{0}}r^{2}m^{2}(1+\frac{1}{\epsilon})\delta_{n/2,\xi}^{2}+\frac{\epsilon}{4}(\lVert\hat{\tau}_{t}-\tau^{\circ}_{t}\rVert_{2}^{2}+\lVert\tau^{\circ}_{t}-\hat{\tau}^{n}_{t}\rVert_{2}^{2})$

Therefore,

$\displaystyle\frac{\lambda-\epsilon}{4}\lVert\hat{\tau}_{t}-\tau_{t}^{\circ}\rVert_{2}^{2}\leq{c_{0}}r^{2}m^{2}(1+\frac{1}{\epsilon})\delta_{n/2,\xi}^{2}+\left(\frac{8+\lambda^{2}}{4\lambda}+\frac{\epsilon}{4}\right)\left\|\tau^{\circ}_{t}-\tau_{t}^{n}\right\|_{2}^{2}+\frac{2}{\lambda}\sum_{s\in\\{S,S^{\prime}\\}}\rho_{t}(\hat{\eta}_{s})^{2}$

Choose $\epsilon\leq\lambda/8$ so that

$\displaystyle\frac{\lambda}{8}\lVert\hat{\tau}_{t}-\tau_{t}^{\circ}\rVert_{2}^{2}$
$\displaystyle\leq{c_{0}}r^{2}m^{2}(1+\frac{8}{\lambda})\delta_{n/2,\xi}^{2}+\left(\frac{4+\lambda^{2}}{2\lambda}\right)\left\|\tau^{\circ}_{t}-\tau_{t}^{n}\right\|_{2}^{2}+\frac{2}{\lambda}\sum_{s\in\\{S,S^{\prime}\\}}\rho_{t}(\hat{\eta}_{s})^{2}$
$\displaystyle\leq\left(1+\frac{8}{\lambda}+\frac{\lambda}{2}\right)({c_{0}}r^{2}m^{2}\delta_{n/2,\xi}^{2}+\left\|\tau^{\circ}_{t}-\tau_{t}^{n}\right\|_{2}^{2}+\sum_{s\in\\{S,S^{\prime}\\}}\rho_{t}(\hat{\eta}_{s})^{2})$

and therefore

$\lVert\hat{\tau}_{t}-\tau_{t}^{\circ}\rVert_{2}^{2}\leq\left(\frac{8}{\lambda}(1+\frac{8}{\lambda})+4\right)({c_{0}}r^{2}m^{2}\delta_{n/2,\xi}^{2}+\left\|\tau^{\circ}_{t}-\tau_{t}^{n}\right\|_{2}^{2}+\sum_{s\in\\{S,S^{\prime}\\}}\rho_{t}(\hat{\eta}_{s})^{2})$

Taking expectations:

$\mathbb{E}[\lVert\hat{\tau}_{t}-\tau_{t}^{\circ}\rVert_{2}^{2}]\leq\left(\frac{8}{\lambda}(1+\frac{8}{\lambda})+4\right)({c_{0}}r^{2}m^{2}\delta_{n/2}^{2}+\left\|\tau^{\circ}_{t}-\tau_{t}^{n}\right\|_{2}^{2}+\max_{s\in\\{S,S^{\prime}\\}}\mathbb{E}[\rho_{t}(\hat{\eta}_{s})^{2}])$

Therefore, if the product error rate terms are all of the same order as the
estimation order terms:

$\displaystyle\mathbb{E}[\lVert\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ}\rVert_{2}^{2}]=O(\delta_{n/2}^{2}+\left\|\tau^{\circ}_{t}-\tau_{t}^{n}\right\|_{2}^{2})$
$\displaystyle\mathbb{E}[\lVert(\hat{\pi}_{t}^{b}-\pi^{b,\circ}_{t})(\hat{m}_{t}-m^{\circ}_{t})\rVert_{2}^{2}]=O(\delta_{n/2}^{2}+\left\|\tau^{\circ}_{t}-\tau_{t}^{n}\right\|_{2}^{2})$
$\displaystyle\mathbb{E}[\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\rVert_{2}^{2}]=O(\delta_{n/2}^{2}+\left\|\tau^{\circ}_{t}-\tau_{t}^{n}\right\|_{2}^{2})$
$\displaystyle\mathbb{E}[\lVert(\hat{m}_{t}-m^{\circ}_{t})(\hat{Q}_{t+1}-Q_{t+1}^{\circ})\rVert_{2}^{2}]=O(\delta_{n/2}^{2}+\left\|\tau^{\circ}_{t}-\tau_{t}^{n}\right\|_{2}^{2})$

∎

###### Proof of Theorem 3.

Preliminaries We introduce some additional notation. For the analysis of
implications of policy optimization, we further introduce notation that
parametrizes the time-$t$ loss function with respect to the time-$(t+1)$
policy. In analyzing the policy optimization, this will be used to decompose
the policy error arising from time steps closer to the horizon. Define

$\mathcal{L}_{D}(\tau_{t}^{n},\tau_{t+1}^{\prime},\hat{\eta})=\mathbb{E}\left[\left(\\{R_{t}+\gamma
Q_{t+1}^{\pi_{\tau_{t+1}^{\prime}}}(S_{t+1},A_{t+1})-V_{\pi_{t}^{b},\pi_{\tau_{t+1}}^{\prime}}(S_{t})\\}-\\{A-\pi^{b}_{t}(1\mid
S_{t})\\}\cdot\tau(S_{t})\right)^{2}\right]$

where
$\pi_{\tau_{t+1}^{\prime}}(s)\in\operatornamewithlimits{argmax}\tau_{t+1}^{\prime}(s).$
That is, the second argument parameterizes the difference-of-$Q$ function that
generates the policy that oracle nuisance functions are evaluated at.

Then, for example, the true optimal policy satisfies that
$\pi^{*}_{t}\in\arg\max\tau^{\circ}_{t}(s)$. We define the oracle loss
function with nuisance functions evaluated with respect to the optimal policy
$\pi^{*}$.

$\mathcal{L}_{D}(\tau_{t}^{n},\tau^{\circ},\hat{\eta})=\mathbb{E}\left[\left(\\{R_{t}+\gamma
Q_{t+1}^{\pi^{*}_{\tau^{\circ}_{t+1}}}(S_{t+1},A_{t+1})-m^{\circ}(S_{t})\\}-\gamma\\{A-\pi^{b}_{t}(1\mid
S_{t})\\}\cdot\tau(S_{t})\right)^{2}\right]$

In contrast, the empirical policy optimizes with respect to a next-stage
estimate of the empirical best next-stage policy
$\hat{\pi}_{\hat{\tau}_{t+1}}.$ That is, noting the empirical loss function:

$\mathcal{L}_{D}(\tau_{t}^{n},\hat{\tau}_{t+1},\hat{\eta})=\mathbb{E}\left[\left(\\{R_{t}+\gamma
Q_{t+1}^{\hat{\pi}_{\hat{\tau}_{t+1}}}(S_{t+1},A_{t+1})-m^{\circ}(S_{t})\\}-\gamma\\{A-\pi^{b}_{t}(1\mid
S_{t})\\}\cdot\tau(S_{t})\right)^{2}\right]$

#### Step 1: Applying advantage estimation results.

At every timestep, the first substep is to estimate the $Q$-function contrast,
$\hat{\tau}_{t}^{\hat{\pi}_{t+1}}.$ The assumptions on product error nuisance
rates imply that for a fixed $\hat{\pi}_{t+1}$ that we would obtain estimation
error

$\mathbb{E}\left[\|\hat{\tau}_{t}^{\hat{\pi}_{t+1}}-\tau_{t}^{\hat{\pi}_{t+1},\circ}\|_{2}^{2}\right]=O\left(\delta_{n/2}^{2}+\left\|\tau_{t}^{\pi^{e},\circ}-\tau_{t}^{\pi^{e},n}\right\|_{2}^{2}\right)$

#### Step 2: Establishing policy consistency.

Applying Lemma 2 requires a convergence rate of
$\hat{\tau}^{\hat{\pi}_{t+1}}_{t}$ to $\hat{\tau}^{\pi^{*}_{t+1}}_{t}$. The
estimation error guarantees on the contrast function, however, are for the
policy $\hat{\pi}_{t+1}$. We obtain the required bound via induction. At a
high level, the estimation error arising from $\hat{\pi}_{t+1}$ vs
$\pi_{t+1}^{*}$ too eventually is integrated; so when the margin exponent
$\alpha>0$, these policy error terms are higher-order and vanish at a faster
rate.

Importantly, we suppose the product error rate conditions hold for each $t$
for data-optimal policies evaluated along the algorithm, i.e. for each $t$,
for each $t$, for $\underline{\hat{\pi}}_{t+1},$ each of
$\mathbb{E}[\lVert(\hat{\pi}_{t}^{b}-\pi_{t}^{b,\circ})\rVert_{2}^{2}]$,
$\mathbb{E}[\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{m}_{t}^{\underline{\hat{\pi}}_{t+1}}-m_{t}^{\circ,\underline{\hat{\pi}}_{t+1}})\rVert_{2}^{2}]$,
$\mathbb{E}[\lVert(\hat{\pi}^{b}_{t}-\pi^{b,\circ}_{t})(\hat{Q}_{t+1}^{\underline{\hat{\pi}}_{t+2}}-Q_{t+1}^{\circ,\underline{\hat{\pi}}_{t+2}})\rVert_{2}^{2}]$,
and
$\mathbb{E}[\lVert(\hat{m}_{t}-m^{\circ}_{t})(\hat{Q}_{t+1}^{\circ,\underline{\hat{\pi}}_{t+2}}-Q_{t+1}^{\circ,\underline{\hat{\pi}}_{t+2}})\rVert_{2}^{2}]$
are of order
$O(\delta_{n/2}^{2}+\|\tau^{\hat{\pi}_{t+1},\circ}_{t}-\tau_{t}^{\hat{\pi}_{t+1},n}\|_{2}^{2}).$

Step 2a: induction hypothesis.

Next we show the induction hypothesis.

First we consider the base case: When $t=T$, $\tau_{T}$ is independent of the
forward policy so that
$\lVert\hat{\tau}_{T}^{\hat{\pi}}-\tau_{T}^{\circ,\pi^{*}}\rVert=\lVert\hat{\tau}_{T}-\tau_{T}^{\circ}\rVert$.
Then the base case follows by Theorem 2.

Suppose it is true that for timesteps $k\geq t+1,$ we have that

$\lVert\hat{\tau}_{k}^{\hat{\underline{\pi}}_{k+1}}-\tau_{k}^{\circ,\underline{\pi}^{*}_{k+1}}\rVert=O(\delta_{n/2}+\|\tau_{k}^{\circ,\hat{\underline{\pi}}_{k+1}}-\tau_{k}^{n,\hat{\underline{\pi}}_{k+1}}\|_{2})+Kn^{-\mathcal{R}_{k}},$
(19)

where

$\mathcal{R}_{k}=\min\left(\rho^{(c)}_{k+1}\cdot\frac{2+2\alpha}{2+\alpha},\;\rho^{(\Psi)}_{k+1}\cdot\frac{2+2\alpha}{2+\alpha},\;-\\{\min_{k^{\prime}\geq
k+1}(\rho^{(c)}_{k^{\prime}},\rho^{(\Psi)}_{k^{\prime}})\\}\cdot\frac{2+2\alpha}{2+\alpha}^{T-{k^{\prime}}}\right).$
(20)

And therefore, applying Lemma 2, that

$\left|\mathbb{E}[V_{k}^{\pi^{*}}-V_{k}^{\hat{\pi}_{\hat{\tau}}}]\right|=O(n^{-\min\\{\rho^{(c)}_{k},\rho^{(\Psi)}_{k}\\}\frac{2+2\alpha}{2+\alpha}})+o(n^{-\min\\{\rho^{(c)}_{k},\rho^{(\Psi)}_{k}\\}\frac{2+2\alpha}{2+\alpha}}).$
(21)

We will show that the induction hypothesis implies

$\lVert\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{\circ,\underline{\pi}^{*}_{t+1}}\rVert\leq
O(\delta_{n/2}+\|\tau_{t}^{\circ,\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{n,\hat{\underline{\pi}}_{t+1}}\|_{2})+Kn^{-\mathcal{R}_{t}}.$

and

$\left|\mathbb{E}[V_{k}^{\pi^{*}}-V_{k}^{\hat{\pi}_{\hat{\tau}}}]\right|=O(n^{-\min\\{\rho^{(c)}_{k},\rho^{(\Psi)}_{k}\\}\frac{2+2\alpha}{2+\alpha}})+o(n^{-\min\\{\rho^{(c)}_{k},\rho^{(\Psi)}_{k}\\}\frac{2+2\alpha}{2+\alpha}})$

First decompose the desired error
$\lVert\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{\circ,\underline{\pi}^{*}_{t+1}}\rVert$
as:

$\lVert\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{\circ,\underline{\pi}^{*}_{t+1}}\rVert\leq\lVert\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{\circ,\hat{\underline{\pi}}_{t+1}}\rVert+\lVert\tau_{t}^{\circ,\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{\circ,\underline{\pi^{*}}_{t+1}}\rVert$
(22)

The first term is the policy evaluation estimation error, and under the
product error rate assumptions , Theorems 1 and 2 give that
$\mathbb{E}[\|\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{\circ,\hat{\underline{\pi}}_{t+1}}\|_{2}^{2}]={O(\delta_{n/2}^{2}+\|\tau_{t}^{\circ,\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{n,\hat{\underline{\pi}}_{t+1}}\|_{2}^{2}).}$
The second term of the above depends on the convergence of the empirically
optimal policy $\hat{\pi}$; we use our analysis from Lemma 2 to bound the
impact of future estimates of difference-of-$Q$ functions using the induction
hypothesis. The following analysis will essentially reveal that the margin
assumption of Assumption 5 implies that the error due to the empirically
optimal policy is higher-order, and the first term (time$-t$ estimation error
of $\hat{\tau}_{t}$) is the leading term.

As in eq. 8, we have that:

$\displaystyle
V^{*}_{t}(s)-V^{\pi_{\hat{\tau}}}_{t}(s)\leq\gamma\mathbb{E}_{\hat{\pi}_{t}}\left[V_{t+1}^{\pi^{*}}-V_{t+1}^{\hat{\pi}_{\hat{\tau}}}\mid
s_{t}\right]+Q_{t}^{*}(s,\pi^{*})-Q_{t}^{*}(s,\hat{\pi}_{\hat{\tau}}).$

Decompose:

$\lVert\tau_{t}^{\circ,\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{\circ,\underline{\pi}^{*}_{t+1}}\rVert\leq\sum_{a}\lVert
Q_{t}^{\underline{\pi}^{*}_{t+1}}(s,a)-Q_{t}^{\hat{\underline{\pi}}_{t+1}}(s,a)\rVert$

By definition of $\tau$ and $\pm
V_{t+1}^{\hat{\pi}_{t+1},\underline{\pi}^{*}_{t+2}}$, for each $a$, we have
that

$\displaystyle\lVert
Q_{t}^{{\underline{\pi}}^{*}_{t+1}}(s,a)-Q_{t}^{\hat{\underline{\pi}}_{t+1}}(s,a)\rVert$
$\displaystyle=\lVert\mathbb{E}_{\pi_{t}^{a}}[V_{t+1}^{\underline{\pi}^{*}_{t+1}}-V_{t+1}^{\hat{\underline{\pi}}_{t+1}}\mid
S_{t}]\rVert$
$\displaystyle\leq\lVert\mathbb{E}_{\pi_{t}^{a}}[V_{t+1}^{\underline{\pi}^{*}_{t+1}}-V_{t+1}^{\hat{\pi}_{t+1},\underline{\pi}^{*}_{t+2}}\mid
S_{t}]\rVert+\lVert\mathbb{E}_{\pi_{t}^{a}}[V_{t+1}^{\hat{\pi}_{t+1},\underline{\pi}^{*}_{t+2}}-V_{t+1}^{\hat{\underline{\pi}}_{t+1}}\mid
S_{t}]\rVert$
$\displaystyle=\lVert\mathbb{E}_{\pi_{t}^{a}}[Q_{t+1}^{\underline{\pi}^{*}_{t+2}}(S_{t+1},{\pi}^{*}_{t+1})-Q_{t+1}^{\underline{\pi}^{*}_{t+2}}(S_{t+1},\hat{\pi}_{t+1})\mid
S_{t}]\rVert+\gamma\lVert\mathbb{E}_{\pi_{t}^{a}}[\mathbb{E}_{\hat{\underline{\pi}}_{t+1}}[V_{t+2}^{\underline{\pi}^{*}_{t+2}}-V_{t+2}^{\hat{\underline{\pi}}_{t+2}}\mid
S_{t}]]\rVert$ (23) $\displaystyle\leq
c\left\\{\int(Q_{t+1}^{\underline{\pi}^{*}_{t+2}}(s,{\pi}^{*}_{t+1})-Q_{t+1}^{\underline{\pi}^{*}_{t+2}}(s,\hat{\pi}_{t+1}))^{2}ds\right\\}^{1/2}+\gamma\lVert\mathbb{E}_{\pi_{t}^{a}}[\mathbb{E}_{\hat{\underline{\pi}}_{t+1}}[V_{t+2}^{\underline{\pi}^{*}_{t+2}}-V_{t+2}^{\hat{\underline{\pi}}_{t+2}}\mid
S_{t}]]\rVert$ (24)

where the last inequality follows by Assumption 4 and the policy-convolved
transition density.

Next we bound the first term using the margin analysis of Lemma 2 and the
inductive hypothesis. Supposing the product error rates are satisfied on the
nuisance functions for estimation of $\hat{\tau}_{t+1}$, the induction
hypothesis gives that

$\mathbb{E}[\|\hat{\tau}_{t+1}^{\hat{\underline{\pi}}_{t+2}}-\tau_{t+1}^{\circ,\underline{\pi}^{*}_{t+2}}\|_{2}]=O\left(\delta_{n/2}+\|\tau_{t}^{\pi^{e},\circ}-\tau_{t}^{n}\|_{2}+n^{-\mathcal{R}_{t+1}}\right).$

The induction hypothesis gives the integrated risk rate assumption on
$\hat{\tau}_{t+1}$ to apply Lemma 2,

$\displaystyle\left\\{\int(Q_{t+1}^{\underline{\pi}^{*}_{t+2}}(s,{\pi}^{*}_{t+1})-Q_{t+1}^{\underline{\pi}^{*}_{t+2}}(s,\hat{\pi}_{t+1}))^{2}ds\right\\}^{1/2}$
$\displaystyle\qquad\leq\frac{(1-\gamma^{T-t-1})}{1-\gamma}c(T-t-1)\\{O(n^{-\kappa})+Kn^{-\min\\{r_{t+1}^{(c)},r_{t+1}^{(\Psi)},\mathcal{R}_{t+1}\\}(1+\alpha)}\\}.$

Combining with the previous analysis, we obtain:

$\displaystyle\lVert\hat{\tau}_{t}^{\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{\circ,\underline{\pi}^{*}_{t+1}}\rVert_{2}^{2}$
$\displaystyle\leq
O(\delta_{t,n/2}^{2}+\|\tau_{t}^{\circ,\hat{\underline{\pi}}_{t+1}}-\tau_{t}^{n,\hat{\underline{\pi}}_{t+1}}\|_{2}^{2})+O(n^{-\min\left\\{\rho_{t+2}^{(c)},\rho_{t+2}^{(\Psi)},\mathcal{R}_{t+2}\right\\}\frac{2+2\alpha}{2+\alpha}})\\}$
$\displaystyle\qquad\qquad+\frac{(1-\gamma^{T-t-1})}{1-\gamma}c(T-t-1)\\{O(n^{-\kappa})+Kn^{-\min\\{\rho_{t+1}^{(c)},\rho_{t+1}^{(\Psi)},\mathcal{R}_{t+1}\\}\frac{2+2\alpha}{2+\alpha}}\\}$
(25)

from eq. 23 and section A.3.

Hence we obtain the inductive step and the result follows.

If we further assume that for $t^{\prime}\geq t,$ we have that
${\rho}_{t}^{(\cdot)}\leq{\rho}_{t^{\prime}}^{(\cdot)}$, for
$(\cdot)\in\\{(c),(\Psi)\\}$, i.e. the estimation error rate is nonincreasing
over time, and that $\alpha>0$ (i.e. Assumption 5, the margin assumption,
holds with exponent $\alpha>0$, then we can see from the result that the
integrated risk terms obtain faster rates, hence are higher-order, and the
leading term is the auxiliary estimation error of the $Q$-function contrast.

∎

##  Appendix B Results used from other works

Here we collect technical lemmas from other works, stated without proof.

######  Lemma 6 (Lemma 18 of (Lewis and Syrgkanis, 2021)).

Consider any sequence of non-negative numbers $a_{1},\ldots,a_{m}$ satisfying
the inequality:

$a_{t}\leq\mu_{t}+c_{t}\max_{j=t+1}^{m}a_{j}$

with $\mu_{t},c_{t}\geq 0$. Let $c:=\max_{t\in[m]}c_{t}$ and
$\mu:=\max_{t\in[m]}\mu_{t}$. Then it must also hold that:

$a_{t}\leq\mu\frac{c^{m-t+1}-1}{c-1}$

######  Lemma 7 (Lemma 14 of (Foster and Syrgkanis, 2019), see also results on
local Rademacher complexity (Wainwright, 2019)).

Consider a function class $\mathcal{F}$, with
$\sup_{f\in\mathcal{F}}\|f\|_{\infty}\leq 1$, and pick any
$f^{\star}\in\mathcal{F}$. Let
$\delta_{n}^{2}\geq\frac{4d\log\left(41\log\left(2c_{2}n\right)\right)}{c_{2}n}$
be any solution to the inequalities:

$\forall
t\in\\{1,\ldots,d\\}:\mathcal{R}\left(\operatorname{star}\left(\left.\mathcal{F}\right|_{t}-f_{t}^{\star}\right),\delta\right)\leq\delta^{2}.$

Moreover, assume that the loss $\ell$ is L-Lipschitz in its first argument
with respect to the $\ell_{2}$ norm. Then for some universal constants
$c_{5},c_{6}$, with probability
$1-c_{5}\exp\left(c_{6}n\delta_{n}^{2}\right)$,

$\left|\mathbb{P}_{n}\left(\mathcal{L}_{f}-\mathcal{L}_{f^{\star}}\right)-\mathbb{P}\left(\mathcal{L}_{f}-\mathcal{L}_{f^{\star}}\right)\right|\leq
18Ld\delta_{n}\left\\{\left\|f-f^{\star}\right\|_{2}+\delta_{n}\right\\},\quad\forall
f\in\mathcal{F}.$

Hence, the outcome $\hat{f}$ of constrained ERM satisfies that with the same
probability,

$\mathbb{P}\left(\mathcal{L}_{\hat{f}}-\mathcal{L}_{f^{\star}}\right)\leq
18Ld\delta_{n}\left\\{\left\|\hat{f}-f^{\star}\right\|_{2}+\delta_{n}\right\\}.$

If the loss $\mathcal{L}_{f}$ is also linear in $f$, i.e.
$\mathcal{L}_{f+f^{\prime}}=\mathcal{L}_{f}+\mathcal{L}_{f^{\prime}}$ and
$\mathcal{L}_{\alpha f}=\alpha\mathcal{L}_{f}$, then the lower bound on
$\delta_{n}^{2}$ is not required.

##  Appendix C Experimental details

All experiments were ran either on a Macbook Pro M1 with 16gb RAM and 8 CPU
cores or on a computer cluster with 64 CPU cores of 8gb RAM each. Experiments
were run in Python using native Python, CVXPY, and scikit-learn. Each figure
took approximately 3-10 minutes to generate.

1d validation example (Table 1). Following the specification of (Kallus and
Uehara, 2019a, Sec 5.1), we consider a small MDP of $T=30$, binary actions,
univariate continuous state, initial state distribution
$p\left(s_{0}\right)\sim\mathcal{N}(0.5,0.2)$, transition probabilities
$P_{t}\left(s_{t+1}\mid s_{t},a_{t}\right)\sim\mathcal{N}(s+0.3a-0.15,0.2)$.
The target and behavior policies we consider are $\pi^{e}(a\mid
s)\sim\operatorname{Bernoulli}\left(p_{e}\right),p_{e}=0.2/(1+\exp(-0.1s))+0.2U,U\sim\operatorname{Uniform}[0,1]$
and $\pi^{b}(a\mid
s)\sim\operatorname{Bernoulli}\left(p_{b}\right),p_{b}=0.9/(1+\exp(-0.1s))+0.1U,U\sim\text{
Uniform }[0,1]$. We consider the interacted state-action basis, i.e. fit $Q$
on $s+s*a$ with an intercept. When $Q$ is well-specified, we do nearly exactly
recover the right contrast function; although in such a small and well-
specified example we do not see benefits of orthogonality.