* Xie et al. (2021b) T. Xie, N. Jiang, H. Wang, C. Xiong, and Y. Bai.  Policy finetuning: Bridging sample-efficient offline and online reinforcement learning.  _Advances in neural information processing systems_ , 34:27395–27407, 2021b.
  * Xu et al. (2023) W. Xu, Y. Ma, K. Xu, H. Bastani, and O. Bastani.  Uniformly conservative exploration in reinforcement learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 10856–10870. PMLR, 2023.
  * Yadlowsky et al. (2018) S. Yadlowsky, H. Namkoong, S. Basu, J. Duchi, and L. Tian.  Bounds on the conditional and average treatment effect in the presence of unobserved confounders.  _arXiv preprint arXiv:1808.09521_ , 2018.
  * Yang and Lok (2018) S. Yang and J. J. Lok.  Sensitivity analysis for unmeasured confounding in coarse structural nested mean models.  _Statistica Sinica_ , 28(4):1703, 2018.
  * Yang et al. (2022) W. Yang, L. Zhang, and Z. Zhang.  Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics.  _The Annals of Statistics_ , 50(6):3223–3248, 2022.
  * Zhang and Bareinboim (2019) J. Zhang and E. Bareinboim.  Near-optimal reinforcement learning in dynamic treatment regimes.  In _Advances in Neural Information Processing Systems_ , pages 13401–13411, 2019.
  * Zhao et al. (2019) Q. Zhao, D. S. Small, and B. B. Bhattacharya.  Sensitivity analysis for inverse probability weighting estimators via the percentile bootstrap.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 81(4):735–761, 2019.
  * Zhao et al. (2015) Y.-Q. Zhao, D. Zeng, E. B. Laber, and M. R. Kosorok.  New statistical learning methods for estimating optimal dynamic treatment regimes.  _Journal of the American Statistical Association_ , 110(510):583–598, 2015.
  * Zhou et al. (2021) Z. Zhou, Z. Zhou, Q. Bai, L. Qiu, J. Blanchet, and P. Glynn.  Finite-sample regret bound for distributionally robust offline tabular reinforcement learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3331–3339. PMLR, 2021.

##### Table of contents

  * •

Appendix A includes proofs of results of the marginal MDP.

  * •

Appendix B includes additional variants of the main algorithm (cross-fitting,
infinite-horizon)

  * •

Appendix C includes additional discussion.

  * •

Appendix D includes proofs of analysis of robust FQI.

  * •

Appendix E contains additional detail on computational experiments.

  * •

LABEL:apx-high-dim contains additional experiments in high-dimensions.

##  Appendix A Proofs for Section 3, Marginal MDP

First, we give a reminder for the main notational device used for the
following proofs. We will use $P_{\pi}$ and $\mathbb{E}_{\pi}$ to denote the
joint probabilities (and expectations thereof) of the random variables
$S_{t},U_{t},A_{t},\forall t$ in the underlying MDP running policy $\pi$. For
example, in general due to the unobserved confounders, we will have that
$P_{\pi^{e}}(S_{t+1}|S_{t}=s,A_{t}=a)\neq
P_{\pi^{b}}(S_{t+1}|S_{t}=s,A_{t}=a)$. Since we are not conditioning on
$U_{t}$, without further assumptions, these are not Markovian, and so it’s
important to keep in mind that $S_{t+1}$ has a generally different
distribution under $\pi^{e}$ than it does under by $\pi^{b}$ even after
conditioning on $S_{t}$ and $A_{t}$.

Under Assumption 1, the setting with a policy $\pi^{e}$ that only depends on
the observed state is equivalent to a marginal MDP over the observed state
alone:

###### Proof.

Proof of Proposition 1 First, note that for any $\pi^{e}$ and all $t,s,a$:

$\displaystyle P_{\pi^{e}}(S_{t+1}|S_{t}=a,A_{t}=a)$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(S_{t+1}|S_{t}=s,A_{t}=a,U_{t}=u)P_{\pi^{e}}(U_{t}=u|S_{t}=s,A_{t}=a)du$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(S_{t+1}|S_{t}=s,A_{t}=a,U_{t}=u)P_{\pi^{e}}(U_{t}=u|S_{t}=s)du,$

where the second equality uses the fact that $\pi^{e}$ is independent of
$U_{t}$. To complete the proof, we need to show that this resulting value is
the same for all possible $\pi^{e}$ and equals Equation 2. This is always true
for the first probability, because it is equal to the transition probability
$P_{\pi^{e}}(S_{t+1}|S_{t},A_{t}=U_{t})=P_{t}(S_{t+1}|S_{t},A_{t},U_{t})$ from
the definition of the full-information MDP. Under Assumption 1, the second
term can also be written as a transition probability:
$P_{\pi^{e}}(U_{t}|S_{t})=P_{\pi^{e}}(U_{t}|S_{t},S_{t-1},A_{t-1},U_{t-1})=P_{t}(U_{t}|S_{t},S_{t-1},A_{t-1},U_{t-1})$.

∎

Note that the above proof may seem a little strange, but it is all about
establishing what probabilities are independent of the policy, and are only a
function of the transition probabilities
$P_{t}(S_{t+1},U_{t+1}|S_{t},U_{t},A_{t})$. We can use this same idea to prove
a more general version of Proposition 1 that _places assupmtions only on the
observed states and actions_ , but at the cost of substantially more
complexity.

For any $t$, let $H_{t}=\\{S_{j},A_{j}:j\leq t\\}$ be the history of the
_observed_ state and actions up to time $t$. In the rest of this section, we
will use shorthands like $P_{\pi}(s_{t+1}|s_{t},a_{t},h_{t-1})\coloneqq
P_{\pi}(S_{t+1}|S_{t}=s_{t},A_{t}=a_{t},H_{t-1}=h_{t-1})$ whenever clear from
the text.

We only require the following Markov assumption on observed states and
actions:

######  Assumption 13 (Observable Markov Property).

For all $\pi$ and for all $t,s,a,h$,

$\displaystyle P_{\pi}(s_{t+1}|s_{t},a_{t},h_{t-1})$
$\displaystyle=P_{\pi}(s_{t+1}|s_{t},a_{t})$ $\displaystyle
P_{\pi}(a_{t}|s_{t},h_{t-1})$ $\displaystyle=P_{\pi}(a_{t}|s_{t}).$

Note that Assumption 1 implies Assumption 13:

$\displaystyle P_{\pi}(s_{t+1}|s_{t},a_{t},h_{t-1})$
$\displaystyle=\int_{\mathcal{U}}P_{\pi}(s_{t+1}|s_{t},u_{t},a_{t},h_{t-1})P_{\pi}(u_{t}|s_{t},a_{t},h_{t-1})du$
$\displaystyle=\int_{\mathcal{U}}P_{\pi}(s_{t+1}|s_{t},u_{t},a_{t})P_{\pi}(u_{t}|s_{t},a_{t})du$
$\displaystyle=P_{\pi}(s_{t+1}|s_{t},a_{t}).$

We now prove the following general version of Proposition 1:

######  Proposition 8 (Marginal MDP, General).

Let $\chi^{\text{marg}}$ be the marginal distribution of $\chi$ over the
observed state. Given Assumption 13, there exists
$P^{\text{marg}}_{t}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$
such that for any policies $\pi^{e}$ and $\pi^{e^{\prime}}$ that do not depend
on $U_{t}$ and for all $s,a,t$:

$\displaystyle P^{\text{marg}}_{t}$
$\displaystyle(s,a)=P_{\pi^{e}}(S_{t+1}|S_{t}=s,A_{t}=a)=P_{\pi^{e^{\prime}}}(S_{t+1}|S_{t}=s,A_{t}=a).$

Furthermore, we can define a new MDP,
$(\mathcal{S},\mathcal{A},R,T^{\text{marg}},\chi^{\text{marg}},H)$, with
probabilities under policy $\pi^{e}$ denoted $P_{\pi^{e}}^{\text{marg}}$ such
that

$P_{\pi^{e}}^{\text{marg}}(S_{0},A_{0},...S_{H},A_{H})=P_{\pi^{e}}(S_{0},A_{0},...S_{H},A_{H}).$

The proof uses the following two lemmas:

######  Lemma 2 (Conditional Mean Independence with Respect to Transitions).

Given Assumption 13,

$\displaystyle\int_{\mathcal{U}}P_{\pi}(u_{t}|s_{t},h_{t-1})P_{\pi}(s_{t+1}|s_{t},a_{t},u_{t})du=\int_{\mathcal{U}}P_{\pi}(u_{t}|s_{t})P_{\pi}(s_{t+1}|s_{t},a_{t},u_{t})du.$

###### Proof.

Proof of Lemma 2 Note that the full-information state transitions are
Markovian by the definition of an MDP:

$P_{\pi}(s_{t+1}|s_{t},a_{t},u_{t},h_{t-1})=P_{\pi}(s_{t+1}|s_{t},a_{t},u_{t}).$

The lemma then follows by applying the tower property to both sides of
Assumption 1. ∎

######  Lemma 3.

Given Assumption 13, for any two $\pi^{e}$ and $\pi^{e^{\prime}}$ which do not
depend on $U$, $\forall s,a,$ and $t$:

$P_{\pi^{e}}(s_{t+1}|s_{t},a_{t})=P_{\pi^{e^{\prime}}}(s_{t+1}|s_{t},a_{t}).$

###### Proof.

Proof of Lemma 3 The proof proceeds by mutual induction on the statement above
and the following statement:

$P_{\pi^{e}}(u_{t}|s_{t},h_{t-1})=P_{\pi^{e^{\prime}}}(u_{t}|s_{t},h_{t-1}).$

We will consider $\pi^{e}$ and demonstrate the equality with
$\pi^{e^{\prime}}$ by showing that the relevant qualities do not depend on
$\pi^{e}$. First, consider $t=0$. From the definition of the initial state
distribution,

$\displaystyle P_{\pi^{e}}(u_{0}|s_{0})=\chi(u_{0}|s_{0}).$

which holds for all $\pi^{e}$.

From the definition of the MDP,
$P_{\pi}(s_{t+1}|s_{t},u_{t},a_{t})=P_{t}(s_{t+1}|s_{t},u_{t},a_{t})$ for any
$\pi$. Then we have:

$\displaystyle P_{\pi^{e}}(s_{1}|s_{0},a_{0})$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(u_{0}|s_{0},a_{0})P_{\pi^{e}}(s_{1}|s_{0},a_{0},u_{0})du$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(u_{0}|s_{0},a_{0})P_{0}(s_{1}|s_{0},a_{0},u_{0})du$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(u_{0}|s_{0})P_{0}(s_{1}|s_{0},a_{0},u_{0})du$
$\displaystyle=\int_{\mathcal{U}}\chi(u_{0}|s_{0})P_{0}(s_{0},a_{0},u_{0})du,$

where the third equality uses the fact that $\pi^{e}$ does not depend on $U$.
This equality also holds for all $\pi^{e}$ and so we have proven the base
case.

Now we consider a general $t$:

$\displaystyle P_{\pi^{e}}(u_{t}|s_{t},h_{t-1})$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(u_{t-1}|s_{t},h_{t-1})P_{\pi^{e}}(u_{t}|s_{t},h_{t-1},u_{t-1})du$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(u_{t-1}|s_{t-1},h_{t-2})\frac{P_{\pi^{e}}(s_{t},u_{t}|s_{t-1},u_{t-1},a_{t-1})}{P_{\pi^{e}}(s_{t}|s_{t-1},a_{t-1})}du,$

where the second equality follows from applying Bayes rule to both
probabilities in the second line. By the inductive hypothesis,
$P_{\pi^{e}}(u_{t-1}|s_{t-1},h_{t-2})$ does not depend on $\pi^{e}$. The
transition probabilities $P_{\pi^{e}}(s_{t},u_{t}|s_{t-1},u_{t-1},a_{t-1})$ do
not depend on $\pi^{e}$. And by the inductive hypothesis,
$P_{\pi^{e}}(s_{t}|s_{t-1},a_{t-1})$ does not depend on $\pi^{e}$. Therefore,
$P_{\pi^{e}}(u_{t}|s_{t},h_{t-1})$ does not depend on $\pi^{e}$.

Finally,

$\displaystyle P_{\pi^{e}}(s_{t+1}|s_{t},a_{t})$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(u_{t}|s_{t},a_{t})P_{\pi^{e}}(s_{t+1}|s_{t},u_{t},a_{t})du$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(u_{t}|s_{t},a_{t})P_{t}(s_{t+1}|s_{t},u_{t},a_{t})du$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(u_{t}|s_{t})P_{t}(s_{t+1}|s_{t},u_{t},a_{t})du$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{e}}(u_{t}|s_{t},h_{t-1})P_{t}(s_{t+1}|s_{t},u_{t},a_{t})du$

where the third equality follows from the fact that $\pi^{e}$ does not depend
on $U$ and the fourth equality follows from Lemma 1. We have already shown
that $P_{t}(s_{t+1}|_{\pi^{e}}(u_{t}|s_{t},h_{t-1})$ does not depend on
$\pi^{e}$ which concludes the proof.

∎

###### Proof.

Proof of Proposition 8 Define
$P^{\text{marg}}_{t}=P_{\pi^{e}}(s_{t+1}|s_{t},a_{t})$, which by Lemma 3 is
the same for any $\pi^{e}$. From the conditional independence structure of the
original MDP together with Assumption 13, we have

$\displaystyle P_{\pi^{e}}(S_{0},A_{0},...,S_{T-1},A_{T-1})$
$\displaystyle=P_{\pi^{e}}(S_{0})P_{\pi^{e}}(A_{0}|S_{0})\prod_{t=1}^{T-1}P_{\pi^{e}}(A_{t}|S_{t})P_{\pi^{e}}(S_{t}|S_{t-1},A_{t-1})$
$\displaystyle=\chi^{M}(S_{0})\pi^{e}(A_{0}|S_{0})\prod_{t=1}^{T-1}\pi^{e}(A_{t}|S_{t})P^{\text{marg}}_{t}(S_{t}|S_{t-1},A_{t-1})$
$\displaystyle=P_{\pi^{e}}^{M}(S_{0},A_{0},...S_{T-1},A_{T-1}).$

∎

###  A.1 Confounding for Regression

###### Proof.

Proof of Proposition 2

$\displaystyle\mathbb{E}_{P_{t}}$
$\displaystyle[f(S_{t},A_{t},S_{t+1})|S_{t}=s,A_{t}=a]$
$\displaystyle=\int_{\mathcal{S}}f(s,a,s^{\prime})P_{t}(s^{\prime}|s,a)ds^{\prime}$
$\displaystyle=\int_{\mathcal{S}}f(s,a,s^{\prime})\left(\int_{\mathcal{U}}P_{t}(u|s)P_{t}(s^{\prime}|s,a,u)du\right)ds^{\prime}$
$\displaystyle=\int_{\mathcal{S}}f(s,a,s^{\prime})\left(\int_{\mathcal{U}}\frac{\pi^{b}(a|s)}{\pi^{b}(a|s,u)}P_{\text{obs}}(U_{t}=u|S_{t}=s,A_{t}=a)P_{t}(s^{\prime}|s,a,u)du\right)ds^{\prime}$
$\displaystyle=\mathbb{E}_{\text{obs}}\left[\frac{\pi^{b}(A_{t}|S_{t})}{\pi^{b}(A_{t}|S_{t},U_{t})}f(S_{t},A_{t},S_{t+1})\Bigg{|}S_{t}=s,A_{t}=a\right].$

∎

We conjecture that the same result would hold replacing Assumption 1 with
Assumption 13, but it would require showing that

$\displaystyle\int_{\mathcal{U}}P_{\pi^{e}}(u|s)P_{t}(s^{\prime}|s,a,u)du$
$\displaystyle=\int_{\mathcal{U}}P_{\pi^{b}}(u|s)P_{t}(s^{\prime}|s,a,u)du$

Note that: $P_{\pi}(u|s)=P_{\pi}(u|s,h)$ when under the integral with the
transitions. So we need to use the fact that this is history-independent.

Proof of Proposition 4

###### Proof.

The result follows by applying Corollary 4 of Dorn and Guo [2022] to
Proposition 2. ∎

###  A.2 Realizability Counterexample

We’ll consider a highly simplified empirical distribution with only a single
state. We’ll drop all dependences on $S$ and $t$ for simplicity. The possible
outcomes $Y$ lie in a discrete set and each have equal probability. We have
three actions, the first with 4 data points, the second with 8 data points,
and the last with 12 data points:

$\displaystyle N=24$ $\displaystyle P(A=0)=4/24,P(A=1)=8/24,P(A=2)=12/24$

Let the outcomes for the four $A=0$ datapoints be $\\{Y_{i}=i:i\text{ from
}1\text{ to }4\\}$. Similarly $Y_{j}$ and $Y_{k}$ for $A=1$ and $A=2$
respectively. Then:

$\displaystyle P(Y_{i}|A=0)=1/4,P(Y_{j}|A=1)=1/8,P(Y_{k}|A=2)=1/12$

Let $\Lambda=3$, so that $1-\tau=1/4$. Denote the relevant lower bounds on the
weights as $\alpha(A)=P(A)+\frac{1}{\Lambda}(1-P(A))$ and
$\beta(A)=P(A)+\Lambda(1-P(A))$. Then from the Dorn and Guo result, we have
unique weights that achieve the infimum over the MSM ambiguity set:

$\displaystyle\text{For }A=0,w=\\{\beta(0),\alpha(0),\alpha(0),\alpha(0)\\},$
$\displaystyle\text{For
}A=1,w=\\{\beta(1),\beta(1),\alpha(1),\alpha(1),\alpha(1),\alpha(1),\alpha(1),\alpha(1)\\},$
$\displaystyle\text{For
}A=2,w=\\{\beta(2),\beta(2),\beta(2),\alpha(2),\alpha(2),\alpha(2),\alpha(2),\alpha(2),\alpha(2),\alpha(2),\alpha(2),\alpha(2)\\}$

Consider the first weight for $A=0$, $w=\beta(0)$. We know that there exists
some arbitrary $u$ such that $P(A=0)/P(A=0|U=u)=\beta(0)$. Bayes rule then
implies that:

$P(U=u)=P(U=u|A=0)\beta(0)$

Then we have:

$\displaystyle P(U=u)=P(U=u|A=0)\beta(0)=\sum_{a}p(A=a)p(U=u|A=a)$
$\displaystyle\implies$ $\displaystyle
P(U=u|A=0)\beta(0)-P(U=a|A=0)P(A=0)=\sum_{a\neq 0}P(A=a)P(U=u|A=a)$

and since $\beta(0)>p(A=0)$, the probability of $u$ occurring in the other
actions must be non-zero. We therefore know that
$P(A=1|U=u)\in\\{P(A=1)/\alpha(A=1),P(A=1)/\beta(a=1)\\}$ and similarly for
$P(A=2|U=u)$. But there does not exist any choice such that
$\sum_{a}P(A=a|U=u)=1$ given our choices of $\Lambda$ and $P(A)$.

##  Appendix B Algorithm Variants

###  B.1 With cross-fitting

Algorithm 3 Confounding-Robust Fitted-Q-Iteration

1: Initialize $\hat{\overline{Q}}_{T}=0$. Obtain index sets of cross-fitted
folds, $\\{\mathcal{I}_{k(i,t)}\\}_{i\in[K],t\in[T]}$

2: for $t=T-1,\dots,1$ do

3: Using data
$\\{\left(S^{i}_{t},A^{i}_{t},R^{i}_{t},S^{i}_{t+1}\right):k(i,t)=k^{\prime}\\}$:
Estimate the marginal behavior policy $\pi^{b}_{t}(a|s)$ and evaluate bounds
$\alpha_{t}(s_{t},a_{t}),\beta_{t}(s_{t},a_{t})$ as in Equation 7. Compute
nominal outcomes
$\\{Y_{t}^{(i)}(\hat{\bar{Q}}_{t+1}^{-k^{\prime}})\\}_{i=1}^{n}$ as in eq. 11.
For all $a\in\mathcal{A}$, fit $\hat{Z}^{1-\tau,k^{\prime}}_{t}(s,a)$ the
$(1-\tau)$th conditional quantile of the outcomes $Y_{t}^{(i)}$.

4: Using data
$\\{\left(S^{i}_{t},A^{i}_{t},R^{i}_{t},S^{i}_{t+1}\right):k(i,t)=-k^{\prime}\\}$:
Compute pseudo-outcomes
$\\{\tilde{Y}_{t}^{(i)}(\hat{Z}^{1-\tau,k^{\prime}}_{t},\hat{\bar{Q}}_{t+1}^{-k^{\prime}})\\}_{i=1}^{n}$
as in eq. 14. Fit $\hat{\bar{Q}}_{t}^{-k^{\prime}}$ via least-squares
regression of $\tilde{Y}_{t}^{(i)}$ against $(s_{t}^{(i)},a_{t}^{(i)})$.

5: Obtain the robust Q-function by averaging across folds:
$\hat{\overline{Q}}_{t}=\sum_{k^{\prime}=1}^{K}\hat{\bar{Q}}_{t}^{(k)}$

6: Compute $\pi^{*}_{t}(s)\in\arg\max_{a}\hat{\overline{Q}}_{t}(s,a)$.

7: end for

In the main text, we described sample splitting but omitted it from the
algorithmic description for a simpler presentation. In Algorithm 3 we discuss
the cross-fitting in detail. We use cross-time fitting and introduce folds
that partition trajectories and timesteps $k(i,t)$. For $K=2$ we consider
timesteps interleaved by parity (e.g. odd/even timesteps in the same fold). We
let $-k(i,t)$ denote that nuisance $\hat{\mu}^{-k(i,t)}$ is learned from
$\\{S_{t^{\prime}}^{(i)},A_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)}\\}_{i\in\mathcal{I}_{k(i)}}$,
where $t^{\prime}$ and $t$ have the same parity, e.g. from the $-k(i)$
trajectories and from timesteps of the same evenness or oddness but is only
used for evaluation in the other fold.

###  B.2 Infinite-horizon results

Algorithm 4 Confounding-Robust Fitted-Q-Iteration (Infinite Horizon)

1: Estimate the marginal behavior policy $\pi^{b}(a|s)$.

2: Compute $\\{\alpha_{k}(s^{(i)},a^{(i)})\\}_{i=1}^{n}$ as in Equation 7.

3: Initialize $\hat{\overline{Q}}_{k}=0$.

4: for $k=1,\dots,K$ do

5: Compute the nominal outcomes
$\\{Y_{k}^{(i)}(\hat{\overline{Q}}_{k-1})\\}_{i=1}^{n}$ as in Equation 11.

6: Fit $\hat{Z}^{1-\tau}_{k}(s,a)$ the $(1-\tau)$th conditional quantile of
the outcomes $Y_{k}^{(i)}$.

7: Compute pseudooutcomes
$\\{\tilde{Y}_{k}^{(i)}(\hat{Z}^{1-\tau}_{k},\hat{\overline{Q}}_{k-1})\\}_{i=1}^{n}$
as in Equation 14.

8: Fit $\hat{\overline{Q}}_{k}$ via least-squares regression of
$\tilde{Y}_{k}^{(i)}$ against $(s^{(i)},a^{(i)})$.

9: Compute $\pi^{*}_{k}(s)\in\arg\max_{a}\hat{\overline{Q}}_{k}(s,a)$.

10: end for

Results for the infinite-horizon setting follow readily from our analysis of
the finite-horizon setting and characterization of the uncertainty set. For
completeness we state results here, succinctly. First, the algorithm is
analogous except with $K$ iterations (restated in Algorithm 4).

In the infinite-horizon setting, we assume the data is generated from the
distribution $\mu\in\Delta(\mathcal{S}\times\mathcal{A})$. We instead assume
concentratability with respect to stationary distributions.

######  Assumption 14 (Infinite-Horizon concentratability coefficient ).

We assume that there exists $C<\infty$ s.t. for any admissible $\nu$,

$\forall(s,a)\in\mathcal{S}\times\mathcal{A},\frac{\nu(s,a)}{\mu(s,a)}\leq C$

We first list some helpful lemmas (i.e. infinite-horizon counterparts of the
finite-horizon versions).

Our analysis as in Theorem 1 can also be applied to the infinite-horizon case
via alternative lemmas standard in the infinite-horizon setting; below we use
results from [Chen and Jiang, 2019]. We introduce a discount factor,
$\gamma<1$.

######  Theorem 3 (Infinite-horizon FQI convergence).

Suppose Assumptions 4, 7, 3 and 14 and let
$\bar{V}_{\max}=\frac{1}{1-\gamma}B_{R}$ be the upper bound on $\bar{V}.$
Then, with probability $>1-\delta,$ under Assumption 9, we have that

$\left\|\hat{\overline{Q}}_{k}-\overline{Q}^{\star}\right\|_{2,\nu}\leq\frac{1-\gamma^{k}}{1-\gamma}\sqrt{C\left(\epsilon_{1}+\epsilon_{\mathcal{Q},\mathcal{Z}}\right)}+\gamma^{k}\bar{V}_{\max}+o_{p}(\gamma^{k}n^{-\frac{1}{2}}).$

where

$\epsilon_{1}=\frac{56\bar{V}_{\max}^{2}\log\left\\{{N(\epsilon,\mathcal{Q},\|\cdot\|)N(\epsilon,\mathcal{Z},\|\cdot\|)}/{\delta}\right\\}}{3n}+\sqrt{\frac{32\bar{V}_{\max}^{2}\log\left\\{{N(\epsilon,\mathcal{Q},\|\cdot\|)N(\epsilon,\mathcal{Z},\|\cdot\|)}/{\delta}\right\\}}{n}\epsilon_{\mathcal{Q},\mathcal{Z}}}.$

##  Appendix C Additional discussion

###  C.1 Related Work

Connections to pessimism in offline RL. Pessimism is an important algorithmic
design principle for offline RL in the absence of unobserved confounders [Xie
et al., 2021a, Rashidinejad et al., 2021, Jin et al., 2021]. Therefore, robust
FQI with lower-confidence-bound-sized $\Lambda$ gracefully degrades to a
pessimistic offline RL method if unobserved confounders were, contrary to our
method’s use case, not actually present in the data. Conversely, pessimistic
offline RL with state-wise lower confidence bounds confers some robustness
against unobserved confounders. But state-wise LCBs are viewed as overly
conservative relative to a profiled lower bound on the average value [Xie et
al., 2021a].

###  C.2 Derivation of the Closed-Form for the Robust Bellman Operator

###### Proof.

Proof of Proposition 5

Dorn et al. [2021] show that the linear program in Proposition 4 has a closed-
form solution corresponding to adversarial weights:

$\displaystyle\tilde{Y}_{f,t}^{-}(s,a)=\mathbb{E}_{\pi^{b}}\left[W^{*}_{t}Y_{t}|S_{t}=s,A_{t}=a\right]\text{
where
}W^{*}_{t}=\alpha_{t}\mathbb{I}\left[Y_{t}>Z^{1-\tau}_{t}\right]+\beta_{t}\mathbb{I}\left[Y_{t}\leq
Z^{1-\tau}_{t}\right].$

We can derive the form in Proposition 5 with a few additional transformations.
Define:

$\displaystyle\mu_{t}(s,a)$
$\displaystyle\coloneqq\mathbb{E}_{\pi^{b}}[Y_{t}|S_{t}=s,A_{t}=a],\;\;\text{CVaR}^{1-\tau}_{t}(s,a)\coloneqq\frac{1}{1-\tau}\mathbb{E}_{\pi^{b}}\left[Y_{t}\mathbb{I}\left[Y_{t}<Z^{1-\tau}_{t}\right]|S_{t}=s,A_{t}=a\right].$

We use the following identity for any random variables $Y$ and $X$:

$\displaystyle\mathbb{E}[Y|X]=\mathbb{E}[Y\mathbb{I}\left[Y>Z^{1-\tau}(Y|X)\right]|X]+\mathbb{E}[Y\mathbb{I}\left[Y\leq
Z^{1-\tau}(Y|X)\right]|X]$

to deduce that

$\tilde{Y}_{f,t}^{-}(s,a)=\alpha_{t}\mu_{t}(s,a)+(\beta_{t}-\alpha_{t})(1-\tau)\text{CVaR}^{1-\tau}_{t}(s,a),$

which gives the desired convex combination by noticing that
$(\beta_{t}-\alpha_{t})(1-\tau)=(1-\alpha_{t})$. ∎

###  C.3 Doubly robust estimation of the policy value

We briefly describe an estimation strategy for the off-policy value when we
seek to estimate the average policy value (rather than recover the entire
$\overline{Q}-$function as we do in this paper). We do so in order to
highlight the qualitative differences in estimation. See Jiang and Li [2016],
Thomas et al. [2015] for references for off-policy evaluation.

Recall the backward-recursive derivation of off-policy evaluation as in
standard presentations of off-policy evaluation for (non-Markovian) MDPs, as
in Jiang and Li [2016]. Let $\hat{V}^{-}_{t}$ denote the robust marginal off-
policy value (we superscript by $-$ to demarcate this from the $s$-conditional
value function we study in the rest of the paper). To summarize the derivation
intuitively, consider single-timestep robust IPW identification of
$\hat{V}^{-}_{T}=\sum_{a\in\mathcal{A}}\mathbb{E}\left[\frac{\pi^{e}(A_{T}\mid
S_{T})}{\pi^{b-}(A_{T}\mid
S_{T})}R_{T}\right]=\inf_{\pi^{b}\in\mathcal{U}}\mathbb{E}\left[\frac{\pi^{e}(A_{T}\mid
S_{T})}{\pi^{b}(A_{T}\mid S_{T})}R_{T}\right]$ by inverse-propensity weighting
by the robust counterpart $\pi_{t}^{b-}(a_{t}\mid s_{t})$ of the inverse
propensity score. The backwards-recursion proceeds by identifying
$\hat{V}^{-}_{t}=\inf_{\pi^{b}\in\mathcal{U}}\left\\{\sum_{a\in\mathcal{A}}\mathbb{E}[\frac{\pi^{e}(A_{t}\mid
S_{t})}{\pi^{b}(A_{t}\mid S_{t})}(R_{t}+\hat{V}^{-}_{t+1})]\right\\},$ where
notably $\hat{V}^{-}_{t+1}$ is a scalar. (The backward-recursive derivation is
discussed also in Namkoong et al. [2020], Bruns-Smith [2021]).

We first remark that sequential exogenous confounders result in a time-
rectangular robust decision problem, so that robust backward induction yields
a decision rule without issues of time-homogenous or time-inhomogenous
preferences (see Delage and Iancu [2015] for a discussion of these challenges
otherwise).

For the purpose of highlighting differences in estimation we briefly discuss
estimation of the off-policy value based on adversarial propensity weighting.
Let $Z^{u}_{1-\tau}$ denote the quantile function of some $u$ (the time
indexing will be clear from context). Unbiasedness for time $t=0$ follows
directly by backwards induction.

######  Proposition 9.

$\displaystyle V_{t}^{-}=\sum_{a}\mathbb{E}\left[\pi(a\mid
s)(R_{t}+\hat{V}_{t+1}^{-})(a_{t}\mathbb{I}\left[R_{t}>Z^{R_{t}}_{1-\tau}\right]+b_{t}\mathbb{I}\left[R_{t}<Z^{R_{t}}_{1-\tau}\right])\right]$
(18)

where

$\alpha_{t}(S,A)\coloneqq
1+\frac{1}{\Lambda}(\pi^{b}_{t}(A_{t}|S_{t})^{-1}-1),\\\
\beta_{t}(S,A)\coloneqq 1+\Lambda(\pi^{b}_{t}(A_{t}|S_{t})^{-1}-1).$

Let $(\cdot)^{*}$ denote a well-specified nuisance function and
$(\cdot)^{\dagger}$ denote a mis-specified nuisance function. Let
$\overline{Q}$ be attained via robust FQE. Define an estimate with an
additional control variate:

$\displaystyle\psi(\pi,Z,\overline{Q}_{t})$
$\displaystyle=\frac{\mathbb{I}\left[\pi^{e}=a\right]}{\pi^{b-}}(R_{t}^{+}+\hat{V}_{t+1}^{DR})+\left\\{1-\frac{\mathbb{I}\left[\pi^{e}=a\right]}{\pi^{b-}}\right\\}\overline{Q}_{t}(s,a).$
(19)

Then

$\displaystyle\mathbb{E}[\psi(\pi^{*},Z^{*},\overline{Q}_{t}^{\dagger})]=\mathbb{E}[\psi(\pi^{*},Z^{\dagger},\overline{Q}_{t}^{*})]=V_{t}^{-}.$

Equation 18 is notable because it shows how the assumption of sequentially
exogenous unobserved confounders (Assumption 1) leads to off-policy evaluation
that (sequentially) evaluates single-step quantile functions. Moreover, this
is qualitatively different than what arises in the fitted-Q-evaluation
setting. The proof of eq. 18 follows directly from previous results on the
closed-form solution (we follow a representation of [Tan, 2022] for
convenience) and linear equivariance to a constant shift of quantile
regression. More specifically, because

$Z^{R_{t}+v-q_{t}(s,a)}_{\tau}(s,a)=Z^{R_{t}}_{\tau}(s,a)+v-q_{t}(s,a)$ (20)

for any scalar constant $v$ and deterministic function $q(s,a)$. (Also note
that $a_{t},b_{t}$ differ from $\alpha_{t},\beta_{t}$ used in the main text by
a multiplicative factor of $\pi^{b}_{t}(a|s)$ because we evaluate marginal
policy values, rather than optimize with respect to the $(s,a)$-conditional
distribution).

###### Proof.

Proof of Proposition 9

Start from robust inverse propensity weighting and add the control variate
$\mathbb{E}\left[\left\\{1-\frac{\mathbb{I}\left[\pi^{e}=a\right]}{\pi^{b-}}\right\\}\overline{Q}_{t}(s,a)\right]$,
where $\overline{Q}_{t}$ is obtained via robust FQE:

$\epsilon_{t}^{-}=R_{t}+\hat{V}_{t+1}^{-}-\overline{Q}_{t},\qquad\hat{V}^{-}_{t}=\mathbb{E}\left[\overline{Q}_{t}+\frac{\mathbb{I}\left[A_{t}=a\right]}{\pi^{b-}}\epsilon_{t}^{-}\right]$

Expanding out the adversarial propensity and applying quantile equivariance
from Equation 20:

$\displaystyle\hat{V}^{-}_{t}$
$\displaystyle=\mathbb{E}\left[\overline{Q}_{t}+A\epsilon_{t}^{-}/\pi-(\Lambda-\Lambda^{-1})A\frac{1-\pi}{\pi}\left\\{\left((1-\tau)(\epsilon_{t}^{-}-Z^{\epsilon_{t}^{-}}_{1-\tau}(X,1))_{+}+\tau(\epsilon_{t}^{-}-Z^{\epsilon_{t}^{-}}_{1-\tau}(X,1))_{-}\right)\right\\}\right]$
$\displaystyle=\mathbb{E}\left[\overline{Q}_{t}+A\epsilon_{t}^{-}/\pi-(\Lambda-\Lambda^{-1})A\frac{1-\pi}{\pi}\left\\{\left((1-\tau)(R_{t}-Z^{R_{t}}_{1-\tau}(X,1))_{+}+\tau(R_{t}-Z^{R_{t}}_{1-\tau}(X,1))_{-}\right)\right\\}\right]$

Next we verify the proposed multiple robustness properties. Due to the
functional form of $\pi^{b-}_{*},$ we use $*,\dagger$ specification notation
on $\pi^{b-}$ to refer jointly to $(\pi^{*},Z^{*})$ or
$(\pi^{\dagger},Z^{\dagger}).$ When we have
$(\pi^{*},Z^{*},\overline{Q}_{t}^{\dagger}):$

$\displaystyle\mathbb{E}[\psi^{DR}(\pi^{*},Z^{*},\overline{Q}_{t}^{\dagger},\eta_{\overline{Q}_{t}}^{\dagger})]$
$\displaystyle=\mathbb{E}\left[\frac{\mathbb{I}\left[\pi^{e}=a\right]}{\pi^{b-}_{*}}(R_{t}^{+}+\hat{V}_{t+1}^{DR})+\left\\{1-\frac{\mathbb{I}\left[\pi^{e}=a\right]}{\pi^{b-}_{*}}\right\\}\overline{Q}_{t}^{\dagger}\right]$
(21) $\displaystyle=V_{t}^{-}.$ (22)

Under assumption of well-specified $\pi^{*},Z^{*},$ we have that
$\mathbb{E}\left[\frac{\mathbb{I}\left[\pi^{e}=a\right]}{\pi^{b-}_{*}}(R_{t}^{+}+\hat{V}_{t+1}^{DR})\right]=V_{t}$.
By iterated expectation,
$\mathbb{E}\left[\left\\{1-\frac{\mathbb{I}\left[\pi^{e}=a\right]}{\pi^{b-}_{*}}\right\\}\overline{Q}_{t}^{\dagger}\right]=0.$
Also,

$\displaystyle\mathbb{E}[\psi^{DR}(\pi^{*},Z^{\dagger},\overline{Q}_{t}^{*},\eta_{\overline{Q}_{t}}^{\dagger})]$
$\displaystyle=\mathbb{E}\left[\frac{\mathbb{I}\left[\pi^{e}=a\right]}{\pi^{b-}_{\dagger}}(R_{t}^{+}+\hat{V}_{t+1}^{DR})+\left\\{1-\frac{\mathbb{I}\left[\pi^{e}=a\right]}{\pi^{b-}_{*}}\right\\}\overline{Q}_{t}^{*}\right]$
$\displaystyle=\mathbb{E}\left[\overline{Q}_{t}^{*}+\frac{\mathbb{I}\left[\pi^{e}=a\right]}{\pi^{b-}_{\dagger}}(R_{t}^{+}+\hat{V}_{t+1}^{DR}-\overline{Q}_{t}^{*})\right]$
$\displaystyle=V_{t}^{-}.$

The second term is $0$ by iterated expectation. ∎

##  Appendix D Proofs for Robust FQE/FQI

####  D.0.1 Auxiliary lemmas for robust FQE/FQI

######  Lemma 4 (Higher-order quantile error terms).

Assume Assumption 4 (i.e. bounded conditional density by $M_{P}$), and that
$Z_{t}^{1-\tau}$ is differentiable with respect to $s$ and its gradient is
Lipschitz continuous. Then, for $f_{t}=R_{t}+\hat{\overline{Q}}_{t+1}$, if
$\hat{Z}_{t}^{1-\tau}$ is $O_{p}(w_{n})$ sup-norm consistent, i.e.
$\sup_{s\in\mathcal{S}}|Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau}|=O_{p}(w_{n}),$
uniformly over $s\in\mathcal{S}$,

$\displaystyle\textstyle|\mathbb{E}[(f_{t}-Z_{t}^{1-\tau})(\mathbb{I}[{f_{t}\leq\hat{Z}_{t}^{1-\tau}}]-\mathbb{I}[{f_{t}\leq
Z_{t}^{1-\tau}}])\mid S=s,A=1]|=O_{p}(w_{n}^{2}),$ (23)

and

$\displaystyle\mathbb{E}[(Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau})\left(\mathbb{I}[{f\leq
Z_{t}^{1-\tau}}]-(1-\tau)\right)\mid A=1]\leq
M_{P}\mathbb{E}[(Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau})^{2}\mid A=a].$ (24)

Lemma 4 is a technical lemma which summarizes the properties of the
orthogonalized target which lead to quadratic bias in the first-stage
estimation error of $\hat{Z}_{t}$. Equation 23 is a slight modification of
[Olma, 2021]/[Kato, 2012, A.3]; eq. 24 is a slight modification of Semenova
[2023, Lemma 4.1].

######  Lemma 5 (Bernstein concentration for least-squares loss (under
approximate realizability)).

Suppose Assumption 8 and that:

  1. 1.

Approximate realizability: $\mathcal{Q}$ approximately realizes
$\overline{\mathcal{T}}\mathcal{Q}$ in the sense that $\forall
f\in\mathcal{Q},z\in\mathcal{Z}$, let
$q_{f}^{\star}=\arg\min_{q\in\mathcal{Q}}\|q-\overline{\mathcal{T}}f\|_{2,\mu}$,
then
$\left\|q_{f}^{\star}-\overline{\mathcal{T}}f\right\|_{2,\mu}^{2}\leq\epsilon_{\mathcal{Q},\mathcal{Z}}$.

The dataset $\mathcal{D}$ is generated from $P_{\text{obs}}$ as follows:
$(s,a)\sim\mu,r=R(s,a),s^{\prime}\sim P(s^{\prime}\mid s,a)$. We have that
$\forall f\in\mathcal{Q}$, with probability at least $1-\delta$,

$\mathbb{E}_{\mu}[\ell(\widehat{\mathcal{T}}_{\mathcal{Z}}f;f)]-\mathbb{E}_{\mu}[\ell(g_{f}^{\star};f)]\leq\frac{56V_{\max}^{2}\ln\frac{|\mathcal{Q}||\mathcal{Z}|}{\delta}}{3n}+\sqrt{\frac{32V_{\max}^{2}\ln\frac{|\mathcal{Q}||\mathcal{Z}|}{\delta}}{n}\epsilon_{\mathcal{Q},\mathcal{Z}}}$

######  Lemma 6 (Stability of covering numbers).

We relate the covering numbers of the squared loss function class, denoted as
$\mathcal{L}_{q(z^{\prime}),z}(q_{t+1})$, to the covering numbers of the
function classes $\mathcal{Q},\mathcal{Z}.$ Define the squared loss function
class as:

$\mathcal{L}_{q(z^{\prime}),z}(q_{t+1})=\left\\{\ell(q(z^{\prime}),q_{t+1};z)-\ell({\overline{Q}}^{\dagger}_{t,Z_{t}},q_{t+1};z)\colon
q(z^{\prime})\in\\{\mathcal{Q}\otimes\mathcal{Z}\\},z\in\mathcal{Z}\right\\}$

Then

$N_{\text{[] }}(2\epsilon L,\mathcal{L}_{q(z^{\prime}),z},\|\cdot\|)\leq
N(\epsilon,\mathcal{Q}\times\mathcal{Z},\|\cdot\|).$

######  Lemma 7 (Difference of indicator functions).

Let $\widehat{f}$ and $f$ take any real values. Then
$\big{|}\mathbb{I}[\widehat{f}>0]-\mathbb{I}\left[f>0\right]\big{|}\leq\mathbb{I}[|f|\leq|\widehat{f}-f|]$

###  D.1 Proofs of theorems

###### Proof.

Proof of Theorem 1

The squared loss (with respect to a given conditional quantile function $Z$)
is:

$\displaystyle\ell(q,q_{t+1};Z)$
$\displaystyle=\left(\alpha({R+q_{t+1}})+(1-{\alpha}){\Big{(}Z_{t}^{1-\tau}+\frac{1}{1-\tau}\left((R+q_{t+1}-Z_{t}^{1-\tau})_{-}-Z_{t}^{1-\tau}\cdot(\mathbb{I}\left[R+q_{t+1}\leq
Z_{t}^{1-\tau}\right]-(1-\tau))\right)\Big{)}}-q_{t}\right)^{2}$

We let $\hat{Z}_{t,Q_{t+1}}$ and $Z_{t,Q_{t+1}}$ denote estimated and oracle
conditional quantile functions, respectively, with respect to a target
function that uses $Q_{t+1}$ estimate. Where the next-timestep $Q$ function is
fixed (as it is in the following analysis) we drop the $Q_{t+1}$ from the
subscript.

Define

$\hat{\overline{Q}}_{t,Z_{t}}\in\arg\min_{q}\mathbb{E}_{n}[\ell(q,\hat{\overline{Q}}_{t+1};Z_{t})]$

and for $z\in\\{\hat{Z}_{t},Z_{t}\\}$, define the following oracle Bellman
error projections $\overline{Q}_{t,z}^{\dagger}$ of the iterates of the
algorithm:

$\displaystyle\overline{Q}_{t,z}^{\dagger}=\arg\min_{q_{t}\in\mathcal{Q}_{t}}\lVert
q_{t}-\overline{\mathcal{T}}_{t,z}^{*}\hat{\overline{Q}}_{t+1}\rVert_{\mu_{t}}.$

##### Relating the Bellman error to FQE loss.

The bias-variance decomposition implies if $U,V$ are conditionally
uncorrelated given $W$, then

$\mathbb{E}[(U-V)^{2}\mid W]=\mathbb{E}[(U-\mathbb{E}[V\mid W])^{2}\mid
W]+{Var}[V\mid W].$

Hence a similar relationship holds for the robust Bellman error as for the
Bellman error:

$\mathbb{E}[\ell(q,\overline{Q}_{t+1};Z)^{2}]=\lVert
q-\overline{\mathcal{T}}^{*}\overline{Q}_{t+1}\rVert_{\mu}+{Var}[W^{*,\pi}_{t}(Z)(R_{t}+\bar{V}_{\overline{Q}_{t+1}}(S_{t+1}))\mid
S_{t},A].$

which is used to decompose the Bellman error as follows:

$\lVert\hat{\overline{Q}}_{t,\hat{Z}_{t}}-\overline{\mathcal{T}}_{t,Z_{t}}^{*}\hat{\overline{Q}}_{t+1}\rVert_{\mu_{t}}^{2}=\mathbb{E}_{\mu}[\ell(\hat{\overline{Q}}_{t,\hat{Z}_{t}},\hat{\overline{Q}}_{t+1};Z_{t})]-\mathbb{E}_{\mu}[\ell({\overline{Q}}^{\dagger}_{t,Z_{t}},\hat{\overline{Q}}_{t+1};Z_{t})]+\lVert{\overline{Q}}_{t,Z_{t}}^{\dagger}-\overline{\mathcal{T}}_{t}^{*}{\hat{\overline{Q}}}_{t+1}\rVert_{\mu_{t}}^{2}.$

Then,

$\displaystyle\lVert\hat{\overline{Q}}_{t,\hat{Z}_{t}}-\overline{\mathcal{T}}_{t,Z_{t}}^{*}\hat{\overline{Q}}_{t+1}\rVert_{\mu_{t}}^{2}$
$\displaystyle=\mathbb{E}_{\mu}[\ell(\hat{\overline{Q}}_{t,\hat{Z}_{t}},\hat{\overline{Q}}_{t+1};Z_{t})]-\mathbb{E}_{\mu}[\ell(\hat{\overline{Q}}_{t,Z_{t}},\hat{\overline{Q}}_{t+1};Z_{t})]$
(25)
$\displaystyle+\mathbb{E}_{\mu}[\ell(\hat{\overline{Q}}_{t,Z_{t}},\hat{\overline{Q}}_{t+1};Z_{t})]-\mathbb{E}_{\mu}[\ell({\overline{Q}}^{\dagger}_{t,Z_{t}},\hat{\overline{Q}}_{t+1};Z_{t})]$
(26)
$\displaystyle+\lVert{\overline{Q}}_{t,Z_{t}}^{\dagger}-\overline{\mathcal{T}}_{t}^{*}{\hat{\overline{Q}}}_{t+1}\rVert_{\mu_{t}}^{2}$
(27)

We bound eq. 25 by orthogonality and eq. 26 by Bernstein inequality arguments.

We bound the first term. Let $f$ denote the Bellman residual. Let $x=f$,
$(a-x)=Q-f$, $b=Q^{\prime}$. Since, by expanding the square and Cauchy-
Schwarz, we obtain the following elementary inequality:

$\displaystyle(a-x)^{2}-(b-x)^{2}$ $\displaystyle=(a-b)^{2}+2(a-b)(b-x)$
$\displaystyle\leq(a-b)^{2}+\sqrt{\mathbb{E}[(a-b)^{2}]\mathbb{E}[(b-x)^{2}]}$

Applying the above, we have that

$\displaystyle\mathbb{E}_{\mu}[\ell(\hat{\overline{Q}}_{t,Z_{t}},\hat{\overline{Q}}_{t+1};Z_{t})]-\mathbb{E}_{\mu}[\ell({\overline{Q}}^{\dagger}_{t,Z_{t}},\hat{\overline{Q}}_{t+1};Z_{t})]\leq\underbrace{\|(\hat{\overline{Q}}_{t,Z_{t}}-{\overline{Q}}^{\dagger}_{t,Z_{t}})\|_{2}^{2}}_{o_{p}(n^{-1})\text{
by }\lx@cref{creftypecap~refnum}{prop-cvar-
orthogonalized}}+\|(\hat{\overline{Q}}_{t,Z_{t}}-{\overline{Q}}^{\dagger}_{t,Z_{t}})^{2}\|\underbrace{\|\hat{\overline{Q}}_{t,Z_{t}}-\tilde{Y}_{t}(\hat{\overline{Q}}_{t+1};Z_{t})\|}_{=O_{p}(n^{-1/2})\text{
by realizability}}$

Therefore

$\mathbb{E}_{\mu}[\ell(\hat{\overline{Q}}_{t,Z_{t}},\hat{\overline{Q}}_{t+1};Z_{t})]-\mathbb{E}_{\mu}[\ell({\overline{Q}}^{\dagger}_{t,Z_{t}},\hat{\overline{Q}}_{t+1};Z_{t})]=o_{p}(n^{-1}).$

We bound eq. 26 by Lemma 5 directly.

Supposing Assumption 8, we obtain that

$\displaystyle\left\|\hat{Q}_{t}-\overline{\mathcal{T}}_{t}^{\star}\hat{Q}_{t+1}\right\|_{\mu_{t}}^{2}\leq\epsilon_{\mathcal{Q},\mathcal{Z}}+\frac{56V_{\max}^{2}\ln\frac{|\mathcal{Q}||\mathcal{Z}|}{\delta}}{3n}+\sqrt{\frac{32V_{\max}^{2}\ln\frac{|\mathcal{Q}||\mathcal{Z}|}{\delta}}{n}\epsilon_{\mathcal{Q},\mathcal{Z}}}+o_{p}(n^{-1}).$

Instead, supposing Assumption 9, instantiate the covering numbers choosing
$\epsilon=O(n^{-1}).$ Lemma 6 bounds the bracketing numbers of the (Lipschitz
over a bounded domain) loss function class with the covering numbers of the
primitive function classes $\mathcal{Q},\mathcal{Z}$. Supposing that Bellman
completeness holds with respect to $\mathcal{Q},\mathcal{Z}$, approximate
Bellman completeness holds over the $\epsilon$-net implied by the covering
numbers with $\epsilon_{\mathcal{Q},\mathcal{Z}}=O(n^{-1})$ and we obtain
that:

$\displaystyle\left\|\hat{Q}_{t}-\overline{\mathcal{T}}_{t}^{\star}\hat{Q}_{t+1}\right\|_{\mu_{t}}^{2}$
$\displaystyle\leq\epsilon_{\mathcal{Q},\mathcal{Z}}+\frac{56V_{t,\max}^{2}\log\\{{N(\epsilon,\mathcal{Q},\|\cdot\|)N(\epsilon,\mathcal{Z},\|\cdot\|)}/{\delta}\\}}{3n}$
$\displaystyle\qquad+\sqrt{\frac{32V_{t,\max}^{2}\log\\{{N(\epsilon,\mathcal{Q},\|\cdot\|)N(\epsilon,\mathcal{Z},\|\cdot\|)}/{\delta}\\}}{n}\epsilon_{\mathcal{Q},\mathcal{Z}}}+o_{p}(n^{-1}).$
$\displaystyle\leq\epsilon_{\mathcal{Q},\mathcal{Z}}+\frac{56V_{t,\max}^{2}\log\\{{N(\epsilon,\mathcal{Q},\|\cdot\|)N(\epsilon,\mathcal{Z},\|\cdot\|)}/{\delta}\\}}{3n}$

∎

###### Proof.

Proof of Theorem 3 Note that Lemma 13, [Chen and Jiang, 2019] establishes the
Bellman error as an upper bound to the policy suboptimality. It states: Let
$f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ and $\hat{\pi}=\pi_{f}$
be the policy of interest, we have

$\bar{V}^{\star}-\bar{V}^{\hat{\pi}}\leq\sum_{t=1}^{\infty}\gamma^{t-1}\left(\left\|\bar{Q}^{\star}-f\right\|_{2,\eta_{t}^{\hat{\pi}}\times\pi^{\star}}+\left\|\bar{Q}^{\star}-f\right\|_{2,\eta_{t}^{\hat{\pi}}\times\hat{\pi}}\right).$

Choosing $f=\hat{\overline{Q}}_{k}$ and $f^{\prime}=\hat{\overline{Q}}_{k-1}$
in [Chen and Jiang, 2019, Lemma 15] gives

$\left\|\hat{\overline{Q}}_{k}-\bar{Q}^{\star}\right\|_{2,\nu}\leq\sqrt{C}\left\|\hat{\overline{Q}}_{k}-\mathcal{T}\hat{\overline{Q}}_{k-1}\right\|_{2,\mu}+\gamma\left\|\hat{\overline{Q}}_{k-1}-\bar{Q}^{\star}\right\|_{2,P(\nu)\times\pi_{\hat{\overline{Q}}_{k-1},\bar{Q}^{\star}}}.$
(28)

Note that we can apply the same analysis with
$P(\nu)\times\pi_{\hat{\overline{Q}}_{k-1},\bar{Q}^{\star}}$ replacing the
$\nu$ distribution on the left hand side, and expand the inequality $k$ times.
Then it remains to upper bound
$\left\|\hat{\overline{Q}}_{k}-\mathcal{T}\hat{\overline{Q}}_{k-1}\right\|_{2,\mu}$,
which we can do via the same analysis of eqs. 25, 26 and 27. Following the
analysis of the proof of Theorem 1, we then obtain, with probability $\geq
1-\delta,$

$\displaystyle\left\|\hat{\overline{Q}}_{k}-\overline{\mathcal{T}}_{t}^{\star}\hat{\overline{Q}}_{k-1}\right\|_{\mu_{t}}^{2}\leq\epsilon_{\mathcal{Q},\mathcal{Z}}+\epsilon_{1}+o_{p}(n^{-1}),$

where

$\epsilon_{1}=\frac{56V_{t,\max}^{2}\log\\{{N(\epsilon,\mathcal{Q},\|\cdot\|)N(\epsilon,\mathcal{Z},\|\cdot\|)}/{\delta}\\}}{3n}+\sqrt{\frac{32V_{\max}^{2}\log\\{{N(\epsilon,\mathcal{Q},\|\cdot\|)N(\epsilon,\mathcal{Z},\|\cdot\|)}/{\delta}\\}}{n}\epsilon_{\mathcal{Q},\mathcal{Z}}}.$

Since $\epsilon_{1}$ and $\epsilon_{\mathcal{Q},\mathcal{Z}}$ are independent
of $k$, and the bound holds uniformly over $k$, we have that, plugging the
above back into the recursive expansion of Equation 28:

$\left\|\hat{\overline{Q}}_{k}-\overline{Q}^{\star}\right\|_{2,\nu}\leq\frac{1-\gamma^{k}}{1-\gamma}\sqrt{C\left(\epsilon_{1}+\epsilon_{\mathcal{Q},\mathcal{Z}}\right)}+\gamma^{k}\bar{V}_{\max}.$

∎

###  D.2 Proofs of intermediate results

####  D.2.1 Orthogonality

###### Proof.

Proof of Proposition 6 We first focus on the case of a single action, $a=1$.
First recall that in the population,
$\mathbb{E}[Z_{t}^{1-\tau}+\frac{1}{1-\tau}(f_{t}-Z_{t}^{1-\tau})\mid
s,a]=\frac{1}{1-\tau}\mathbb{E}[f_{t}\mathbb{I}\left[f_{t}\leq
Z_{t}^{1-\tau}\right]\mid s,a].$ In the analysis below we study this truncated
conditional expectation representation.

$\displaystyle\lVert\hat{\overline{Q}}_{t}(S,1)-\overline{Q}_{t}(S,1)\rVert$
$\displaystyle\lesssim\lVert\mathbb{E}[\tilde{Y}_{t}(\hat{Z}_{t},\hat{\overline{Q}}_{t+1})-\tilde{Y}_{t}(Z_{t},\hat{\overline{Q}}_{t+1})\mid
S,A=1]\rVert+\lVert\hat{\overline{Q}}_{t}(S,1)-{\overline{Q}}_{t}(S,1)\rVert$
by Prop. 1 of Kennedy [2020] (regression stability)

Prop. 1 of Kennedy [2020] provides bounds on how regression upon
pseudooutcomes with estimated nuisance functions relates to the case with
known nuisance functions.

It remains to relate
$\lVert\mathbb{E}[\tilde{Y}_{t}(\hat{Z}_{t},\hat{\overline{Q}}_{t+1})-\tilde{Y}_{t}(Z_{t},\hat{\overline{Q}}_{t+1})\mid
S,A=1]\rVert$ to the terms comprising the pointwise bias, which are bounded by
Lemma 4. We define these terms as:

$\displaystyle B_{1}^{1}(S)$
$\displaystyle=\mathbb{E}\left[\frac{1-\tilde{\alpha}}{1-\tau}\left\\{(f_{t}-Z_{t}^{1-\tau})\left(\mathbb{I}\left[f_{t}\leq\hat{Z}_{t}^{1-\tau})\right]-\mathbb{I}\left[f_{t}\leq
Z_{t}^{1-\tau})\right]\right)\right\\}\mid S,A=1\right]$ $\displaystyle
B_{2}^{1}(S)$
$\displaystyle=\mathbb{E}\left[\frac{1-\tilde{\alpha}}{1-\tau}\left\\{(Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau})\left(\mathbb{I}\left[f\leq
Z_{t}^{1-\tau}\right]-(1-\tau)\right)\right\\}\mid S,A=1\right].$

Lemma 4 bounds these terms as quadratic in the first-stage estimation error of
$\hat{Z}_{t}.$

We have that

$\mathbb{E}[\tilde{Y}_{t}(\hat{Z}_{t},\hat{\overline{Q}}_{t+1})-\tilde{Y}_{t}(Z_{t},\hat{\overline{Q}}_{t+1})\mid
S,1]=B_{1}^{1}(S)+B_{2}^{1}(S).$

To see this, note:

$\displaystyle\mathbb{E}[\tilde{Y}_{t}(\hat{Z}_{t},\hat{\overline{Q}}_{t+1})-\tilde{Y}_{t}(Z_{t},\hat{\overline{Q}}_{t+1})\mid
S,1]$
$\displaystyle=\mathbb{E}\left[\frac{1-\tilde{\alpha}}{1-\tau}\left\\{\left(f_{t}\mathbb{I}\left[f_{t}\leq\hat{Z}_{t}^{1-\tau})\right]-f_{t}\mathbb{I}\left[f_{t}\leq
Z_{t}^{1-\tau})\right]\right)\right.\right.$
$\displaystyle\qquad\left.\left.-\left(\hat{Z}_{t}^{1-\tau}\cdot(\mathbb{I}\left[f\leq\hat{Z}_{t}^{1-\tau}\right]-(1-\tau))-Z_{t}^{1-\tau}\cdot(\mathbb{I}\left[f\leq
Z_{t}^{1-\tau}\right]-(1-\tau))\right)\pm
Z_{t}^{1-\tau}\cdot\mathbb{I}\left[f\leq\hat{Z}_{t}^{1-\tau}\right]\right\\}\mid
S,A=1\right]$
$\displaystyle=\mathbb{E}\left[\frac{1-\tilde{\alpha}}{1-\tau}\left\\{(f_{t}-Z_{t}^{1-\tau})\mathbb{I}\left[f_{t}\leq\hat{Z}_{t}^{1-\tau})\right]-(f_{t}-Z_{t}^{1-\tau})\mathbb{I}\left[f_{t}\leq
Z_{t}^{1-\tau})\right]\right.\right.$
$\displaystyle\qquad\left.\left.+(Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau})\mathbb{I}\left[f\leq
Z_{t}^{1-\tau}\right]-(Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau})(1-\tau)\right\\}\mid
S,A=1\right]$
$\displaystyle=\mathbb{E}\left[\frac{1-\tilde{\alpha}}{1-\tau}\left\\{(f_{t}-Z_{t}^{1-\tau})\left(\mathbb{I}\left[f_{t}\leq\hat{Z}_{t}^{1-\tau})\right]-\mathbb{I}\left[f_{t}\leq
Z_{t}^{1-\tau})\right]\right)\right.\right.$
$\displaystyle\qquad\left.\left.+(Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau})\left(\mathbb{I}\left[f\leq
Z_{t}^{1-\tau}\right]-(1-\tau)\right)\right\\}\mid S,A=1\right]$
$\displaystyle=B_{1}^{1}(S)+B_{2}^{1}(S)$

Finally, we relate the root mean-squared conditional bias,

${\lVert\mathbb{E}[\tilde{Y}_{t}(\hat{Z}_{t},\hat{\overline{Q}}_{t+1})-\tilde{Y}_{t}(Z_{t},\hat{\overline{Q}}_{t+1})\mid
S,A=1]\rVert},$

to the above quadratic error as follows. Using the inequalities $(a+b)^{2}\leq
2(a^{2}+b^{2})$ and $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ (for nonnegative $a,b$),
we obtain that

$\displaystyle\lVert\mathbb{E}[\tilde{Y}_{t}(\hat{Z}_{t},\hat{\overline{Q}}_{t+1})-\tilde{Y}_{t}(Z_{t},\hat{\overline{Q}}_{t+1})\mid
S,A=1]\rVert$
$\displaystyle=\sqrt{\mathbb{E}[(B_{1}^{1}(S)+B_{2}^{1}(S))^{2}\mid A=1]}$
$\displaystyle\leq\sqrt{\mathbb{E}[2\\{(B_{1}^{1}(S))^{2}+(B_{2}^{1}(S))^{2}\\}\mid
A=1]}$ $\displaystyle\leq\sqrt{2\mathbb{E}[(B_{1}^{1}(S))^{2}\mid
A=1]}+\sqrt{2\mathbb{E}[(B_{2}^{1}(S))^{2}\mid A=1]}.$

The result follows by the uniform bounds of Lemma 4.

∎

###### Proof.

Proof of Lemma 4

Proof of eq. 23:

For $l>0$, define

$\mathcal{M}_{n}^{a}(l)=\left\\{g:\mathcal{S}\rightarrow\mathbb{R}\text{ s.t.
}\sup_{s\in\mathcal{S}}|g(s)-Z_{t}^{1-\tau}(s,a)|\leq lw_{n}\right\\}$

Define

$\displaystyle
U_{n}(g,s)\coloneqq|\mathbb{E}[(f_{t}-Z_{t}^{1-\tau})(\mathbb{I}\left[f_{t}\leq\hat{Z}_{t}^{1-\tau}\right]-\mathbb{I}\left[f_{t}\leq
Z_{t}^{1-\tau}\right])\mid S=s,A=1]|$

We will show that for every $l>0,s\in\mathcal{S}$:

$\sup_{g\in\mathcal{M}_{n}(l)}U_{n}(g,s)=O_{p}\left(w_{n}^{2}\right)$

Breaking up the absolute value,

$\displaystyle
U_{n}(g,s)\leq\mathbb{E}[(f_{t}-Z_{t}^{1-\tau})(\mathbb{I}\left[Z_{t}^{1-\tau}\leq
f_{t}\leq g\right])\mid
S=s,A=1]+\mathbb{E}[(Z_{t}^{1-\tau}-f_{t})(\mathbb{I}\left[g\leq f_{t}\leq
Z_{t}^{1-\tau}\right])\mid S=s,A=1]$

We will bound the first term, bounding the second term is analogous. Define

$U_{1,n}(g,s)\coloneqq\mathbb{E}[(f_{t}-Z_{t}^{1-\tau})(\mathbb{I}\left[Z_{t}^{1-\tau}\leq
f_{t}\leq g\right])\mid S=s,A=1]$

Observe that

$\displaystyle\sup_{g\in\mathcal{M}_{n}(l)}U_{1,n}(g,s)$
$\displaystyle=\mathbb{E}[(f_{t}-Z_{t}^{1-\tau})(\mathbb{I}\left[Z_{t}^{1-\tau}\leq
f_{t}\leq Z_{t}^{1-\tau}+lw_{n}\right])\mid S=s,A=1]$ $\displaystyle\leq
M_{P}l^{2}w_{n}^{2}$

The result follows.

Proof of eq. 24:

The argument follows that of Semenova [2017]. The difference of indicators is
nonzero on the events:

$\displaystyle\mathcal{E}^{-}\coloneqq\\{f_{t}-\hat{Z}_{t}^{1-\tau}<0<f_{t}-Z_{t}^{1-\tau}\\}$
$\displaystyle\mathcal{E}^{+}\coloneqq\\{f_{t}-Z_{t}^{1-\tau}<0<f_{t}-\hat{Z}_{t}^{1-\tau}\\}$

On these events, the estimation error upper bounds the exceedance

$\\{\mathcal{E}^{-}\cup\mathcal{E}^{+}\\}\implies\\{|Z-f|<|Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau}|\\}$
(29)

(since
$\mathcal{E}^{-}\implies\\{f-\hat{Z}_{t}^{1-\tau}<0<f-Z_{t}^{1-\tau}\\}$ and
$\mathcal{E}^{+}\implies\\{0<Z_{t}^{1-\tau}-f<Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau}\\}$.)

Then

$\displaystyle\mathbb{E}[(f_{t}-Z_{t}^{1-\tau})\mathbb{I}\left[\mathcal{E}^{-}\cup\mathcal{E}^{+}\right]\mid
S=s,A=1]$
$\displaystyle=\int_{-|Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau}|}^{|Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau}|}(f_{t}(s,a,s^{\prime})-Z_{t}^{1-\tau})P(s^{\prime}\mid
s,a)ds^{\prime}$ $\displaystyle\leq
M_{P}\mathbb{E}[(Z_{t}^{1-\tau}-\hat{Z}_{t}^{1-\tau})^{2}\mid S=s,A=1]$

Assumption 6 ensures the result holds for state distributions that could arise
during policy fitting. The above results hold conditionally on some action
$A=1$ but hold for all actions.

∎

####  D.2.2 Other lemmas

###### Proof.

Proof of Lemma 5

Recall that

$\displaystyle\ell(q,q_{t+1};Z)$
$\displaystyle=\left(\alpha({R+q_{t+1}})+(1-{\alpha}){\Big{(}Z_{t}^{1-\tau}+\frac{1}{1-\tau}\left((R+q_{t+1}-Z_{t}^{1-\tau})_{-}-Z_{t}^{1-\tau}\cdot(\mathbb{I}\left[R+q_{t+1}\leq
Z_{t}^{1-\tau}\right]-(1-\tau))\right)\Big{)}}-q_{t}\right)^{2}$

Define $f_{q^{\prime},z}=$ Define $X$ to be the difference of the integrands.

Step 1:

${Var}(X(g,f,z,g_{f}^{*}))\leq
4V^{2}_{\max}\|\hat{\overline{Q}}_{t,Z_{t}}-{\overline{Q}}_{t,Z_{t}}^{\dagger}\|_{2}^{2}$

(by similar arguments as in the original paper). By the same arguments (i.e.
adding and subtracting $\overline{\mathcal{T}}f$) we obtain that

$\|\hat{\overline{Q}}_{t,Z_{t}}-{\overline{Q}}_{t,Z_{t}}^{\dagger}\|_{2}^{2}\leq
2(\mathbb{E}[X(g,f,z,g_{f}^{*})]+2\epsilon_{\mathcal{Q},\mathcal{Z}})$

Therefore,

${Var}(X(g,f,z,g_{f}^{*}))\leq
8V^{2}_{\max}(\mathbb{E}[X(g,f,z,g_{f}^{*})]+2\epsilon_{\mathcal{Q},\mathcal{Z}}).$

Applying (one-sided) Bernstein’s inequality uniformly over
$\mathcal{Q},\mathcal{Z}$, we obtain:

$\displaystyle\mathbb{E}\left[X(g,f,z,g_{f}^{*})\right]-\mathbb{E}_{n}[X(g,f,z,g_{f}^{\star})]$
$\displaystyle\leq\sqrt{\frac{16V_{\max}^{2}\left(\mathbb{E}\left[X(g,f,z,g_{f}^{\star})\right]+2\epsilon_{\mathcal{F},\mathcal{Z}}\right)\ln\frac{|\mathcal{Q}||\mathcal{Z}|}{\delta}}{n}}+\frac{4V_{\max}^{2}\ln\frac{|\mathcal{Q}||\mathcal{Z}|}{\delta}}{3n}$

Note that $\hat{\overline{Q}}_{t,Z_{t}}$ minimizes both
$\mathbb{E}_{n}[\ell(q,\hat{\bar{Q}}_{t+1};Z_{t})]$ and
$\mathbb{E}[(q,\hat{\bar{Q}}_{t+1},Z_{t},\overline{Q}_{\hat{\bar{Q}}_{t+1}}^{*})]$
with respect to $q$. Therefore, by completeness since the Bayes-optimal
predictor is realizable,

$\mathbb{E}_{n}[\ell(\hat{\overline{Q}}_{t,Z_{t}},\hat{\bar{Q}}_{t+1};Z_{t})]\leq\mathbb{E}_{n}[\ell({\overline{Q}}_{t,Z_{t}}^{\dagger},\hat{\bar{Q}}_{t+1};Z_{t})]=0$

Therefore (solving for the quadratic formula),

$\mathbb{E}[X(\hat{\overline{Q}}_{t,Z_{t}},\hat{Q}_{t+1},Z_{t},{\overline{Q}}_{t,Z_{t}}^{\dagger})]\leq\frac{56V_{\max}^{2}\ln\frac{|\mathcal{Q}||\mathcal{Z}|}{\delta}}{3n}+\sqrt{\frac{32V_{\max}^{2}\ln\frac{|\mathcal{Q}||\mathcal{Z}|}{\delta}}{n}\epsilon_{\mathcal{F},\mathcal{Z}}}$

∎

###### Proof.

Proof of Lemma 6 We show this result by establishing Lipschitz-continuity of
the squared loss function class (with respect to the product function class of
$\mathcal{Q}\times\mathcal{Z}$).

We use a stability result on the bracketing number under Lipschitz
transformation. Classes of functions $x\mapsto f_{\theta}(x)$ that are
Lipschitz in the index parameter $\theta\in\Theta$ have bracketing numbers
readily related to the covering numbers of $\Theta$. Suppose that

$\left|f_{\theta^{\prime}}(x)-f_{\theta}(x)\right|\leq
d({\theta^{\prime}},\theta)F(x),$

for some metric $d$ on the index set, function $F$ on the sample space, and
every $x$. Then $(\operatorname{diam}\Theta)F$ is an envelope function for the
class $\left\\{f_{\theta}-f_{\theta_{0}}:\theta\in\right.$ $\Theta\\}$ for any
fixed $\theta_{0}$. We invoke Theorem 2.7.11 of van de Vaart and Wellner
[1996] which shows that the bracketing numbers of this class are bounded by
the covering numbers of $\Theta$.

######  Theorem 4 ([van de Vaart and Wellner, 1996], Theorem 2.7.11).

Let $\mathcal{F}=\left\\{f_{\theta}:\theta\in\Theta\right\\}$ be a class of
functions satisfying the preceding display for every $\theta^{\prime}$,
$\theta$ and some fixed function $F$. Then, for any norm $\|\cdot\|$,

$N_{\text{[] }}(2\epsilon\|F\|,\mathcal{F},\|\cdot\|)\leq
N(\epsilon,\Theta,d).$

Let $\mathcal{F}=\left\\{f_{\theta}:\theta\in\Theta\right\\}$ be a class of
functions satisfying the preceding display for every $s$ and $\theta$ and some
fixed envelope function $F$. Then, for any norm $\|\cdot\|$,

$N_{\text{[] }}(2\epsilon\|F\|,\mathcal{F},\|\cdot\|)\leq
N(\epsilon,\Theta,d).$

This shows that the bracketing numbers of the loss function class can be
expressed via the covering numbers of the estimated function classes
$\mathcal{Q},\mathcal{Z}$, which are the primitive function classes of
estimation, for which results are given in various references for typical
function classes.

Denote

$\displaystyle g(q_{t+1})$ $\displaystyle=\alpha(s,a)({R+q_{t+1}})$
$\displaystyle h(z)$
$\displaystyle=(1-{\alpha}){\Big{(}\frac{1}{1-\tau}\left(z+(R+q_{t+1}-z)_{-}-z\cdot(\mathbb{I}\left[R+q_{t+1}\leq
z\right]-(1-\tau))\right)\Big{)}}$

and notate

$\displaystyle\ell(q,q_{t+1};z)=(q-g(q_{t+1})+h(q_{t+1},z))^{2}.$

Note that $\frac{1}{1-\tau}=(1+\Lambda)$. Assuming bounded rewards, define
$D_{z,t},D_{q,t}$ as the diameters of $\mathcal{Q}_{t},\mathcal{Z}_{t}$,
respectively and note that $D_{z,t}\approx D_{q,t}$. Note that $h(q_{t+1},z)$
is $(1-\alpha_{\min})(3(1+\Lambda)+1)$-Lipschitz in $z$ (since the sum of
Lipschitz continuous functions is Lipschitz) and it is
$(1-\alpha_{\min})\left(1+(1+\Lambda)(\frac{D_{z,t}}{D_{q,t}}+1)\right)$-Lipschitz
in $q_{t+1}.$ Further, $g(q_{t+1})$ is $\alpha_{\max}$-Lipschitz in $q_{t+1}.$
Therefore, $\ell\left(q,q_{t+1};z\right)$ is $D_{q,t}$ Lipschitz in $q$,
$L_{q,t+1}^{C}$-Lipschitz in $q_{t+1}$ and $L_{z,t}^{C}$-Lipschitz in $z$,
with $L_{q,t+1}^{C},L_{z,t}^{C}$ defined as follows:

$\displaystyle
L_{q,t+1}^{C}=(2D_{q,t+1}+D_{z,t})(1-\alpha_{\min})\left(\left(1+(1+\Lambda)(\frac{D_{z,t}}{D_{q,t+1}}+1)\right)+\alpha_{\max}\right)$
$\displaystyle
L_{z,t}^{C}=(2D_{q,t+1}+D_{z,t})(1-\alpha_{\min})(3(1+\Lambda)+1).$

Therefore we have shown that restrictions of $\ell\left(q,q_{t+1};z\right)$ to
the $q_{t+1},z$ coordinates are individually Lipschitz. We leverage the fact
that a function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is Lipschitz if and
only if there exists a constant $L$ such that the restriction of $f$ to every
line parallel to a coordinate axis is Lipschitz with constant $L$. Choosing

$L_{t}=\sqrt{3}\max\\{D_{q},L_{q,t+1}^{C},L_{z,t}^{C}\\}$

gives that $\ell\left(q,q_{t+1};z\right)$ is $L_{t}$-Lipschitz.

∎

###### Proof.

Proof of Corollary 1

Lemma 6 gives that $\ell\left(q,q_{t+1};z\right)$ is $L_{t}$-Lipschitz with
$L_{t}=\sqrt{3}\max\\{D_{q},L_{q,t+1}^{C},L_{z,t}^{C}\\}$.

To interpret the scaling of the result, we can appeal to van de Vaart and
Wellner [1996, Thm. 2.6.4] which upper bounds the (log) covering numbers by
the VC-dimension. Namely, van de Vaart and Wellner [1996, Thm. 2.6.4] states
that there exists a universal constant $K$ such that

$N\left(\epsilon,\mathcal{F},L_{r}(Q)\right)\leq
KV(\mathcal{F})(4e)^{V(\mathcal{F})}\left(\frac{1}{\epsilon}\right)^{r(V(\mathcal{F})-1)}.$

Therefore, achieving an $\epsilon=cn^{-1}$ approximation error on the
bracketing numbers of robust $Q$ functions results in an $\log(2L_{t}n)$
dependence.

Lastly we remark on instantiating $L_{t}$. Note that under the assumption of
bounded rewards, $D_{q,t+1}=B_{r}(T-t+1).$ Focusing on leading-order
dependence in problem-dependent constants, we have that
$L_{t}=O(B_{r}(T-t)\Lambda).$ Then
$\hat{\mathcal{E}}(\hat{Q})\leq\epsilon+\sum_{t=1}^{T}K\frac{\log(2B_{r}(T-t)\Lambda
n)}{n}.$ Upper bounding the left Riemann sum by the integral, we obtain that

$\sum_{t=1}^{T}K\frac{\log(2KB_{r}(T-t)\Lambda
n/\epsilon)}{n}\leq\int_{1}^{T}K\frac{\log(2KB_{r}(T-x)\Lambda
n/\epsilon)}{n}dx=\frac{(T-1)}{n}(\log(2KB_{r}\Lambda(T-1)n/\epsilon)-1).$

∎

###  D.3 Confounding with infinite data

First, we prove the following useful result for confounded regression with
conditional Gaussian tails:

######  Lemma 8.

Define:

$C(\Lambda)\coloneqq\left(\frac{\Lambda^{2}-1}{\Lambda}\right)\phi\left(\Phi^{-1}\left(\frac{1}{1+\Lambda}\right)\right),$

where $\phi$ and $\Phi$ are the standard Gaussian density and CDF
respectively. Let $Y_{t}(Q)$ be conditionally Gaussian given $S_{t}=s$ and
$A_{t}=a$ with mean $\mu_{t}(s,a)$ and standard deviation $\sigma_{t}(s,a)$.
Then,

$\displaystyle(\bar{\mathcal{T}}_{t}^{*}Q)(s,a)$
$\displaystyle=\mu_{t}(s,a)-[1-\pi^{b}_{t}(a|s)]C(\Lambda)\sigma_{t}(s,a).$

###### Proof.

Proof of Lemma 8

The CVaR for Gaussians has a closed-form [Norton et al., 2021]:

$\displaystyle\frac{1}{1-\tau}\mathbb{E}_{\pi^{b}}\left[Y_{t}(Q)\mathbb{I}\left[Y_{t}(Q)<Z^{1-\tau}_{t}\right]|S_{t}=s,A_{t}=a\right]=\mu_{t}(s,a)-\sigma_{t}(s,a)\frac{\phi(\Phi^{-1}(1-\tau))}{1-\tau}.$

Applying this to Proposition 5 gives the desired result. ∎

###### Proof.

Proof of Proposition 7 First, note that $R_{t}$ is conditionally Gaussian
given $S_{t}$ and $A_{t}$ with mean $\theta_{R}\theta_{P}s$ and standard
deviation $\theta_{R}\sigma_{T}$. Define
$\beta_{i}\coloneqq\theta_{R}\sum_{k=1}^{i}\theta_{P}^{k}$. Using value
iteration, we can show that $V^{\pi^{e}}_{T-i}(s)=\beta_{i}s$ for $i\geq 1$.
E.g. by induction, $V^{\pi^{e}}_{T-1}(s)=\theta_{R}\theta_{P}s=\beta_{1}$ and
if $V^{\pi^{e}}_{T-t+1}(s)=\beta_{t-1}s$, then

$V^{\pi^{e}}_{T-t}(s)=\theta_{P}(\theta_{R}+\gamma\beta_{t-1})s=\beta_{t}s.$

Next we will derive the form of the robust value function by induction. For
the base case, $t={T-1}$, we have:

$\displaystyle Y_{T-1}=\theta_{R}s^{\prime}.$

Therefore, $Y_{T-1}$ is conditionally gaussian with mean
$\theta_{R}\theta_{P}s$ and standard deviation $\theta_{R}\sigma_{P}$.
Applying Lemma 8, we have:

$\displaystyle\bar{V}_{T-1}^{\pi^{e}}(s)$
$\displaystyle=\theta_{R}\theta_{P}s-0.5C(\Lambda)\theta_{R}\sigma_{P}.$

Now assume that $\bar{V}_{t+1}^{\pi^{e}}(s)=\theta_{V}s+\alpha_{V}$. Then

$\displaystyle Y_{t}$
$\displaystyle=\theta_{R}s^{\prime}+(\theta_{V}s^{\prime}+\alpha_{V})$
$\displaystyle=(\theta_{R}+\theta_{V})s^{\prime}+\alpha_{V}.$

Therefore, $Y_{t}$ is conditionally gaussian with mean
$(\theta_{R}+\theta_{V})\theta_{P}s+\alpha_{V}$ and standard deviation
$(\theta_{R}+\theta_{V})\sigma_{P}$. Applying Lemma 8, we have:

$\displaystyle\bar{V}_{t}^{\pi^{e}}(s)$
$\displaystyle=(\theta_{R}+\theta_{V})\theta_{P}s+\alpha_{V}-0.5C(\Lambda)(\theta_{R}+\theta_{V})\sigma_{P},$
(30)

which is linear in $s$ with new coefficients
$\theta_{V}^{\prime}\coloneqq(\theta_{R}+\theta_{V})\theta_{T}$ and
$\alpha_{V}^{\prime}\coloneqq\alpha_{V}-0.5C(\Lambda)(\theta_{R}+\theta_{V})\sigma_{P}$.

By rolling out the recursion defined in Equation 30, consolidating the
coefficients into $\beta_{i}$ terms, and then simplifying we get:

$\bar{V}^{\pi^{e}}_{0}(s)=V^{\pi^{e}}_{0}(s)-\frac{1}{2\theta_{P}}\left(\sum_{i=0}^{T-1}\beta_{i}\right)\sigma_{P}C(\Lambda).$

Finally, that $C(\Lambda)\leq\frac{1}{8}\log(\Lambda)$ can be verified
numerically.

∎

###  D.4 Proofs for warm-starting

###### Proof.

Proof of Theorem 2

We prove this via backwards induction.

We show asymptotic linearity, which follows from orthogonality. Define the
following:

$\displaystyle\theta_{t,a}^{*}$
$\displaystyle=\mathbb{E}[\phi_{t,a}\phi_{t,a}^{\top}]^{-1}\mathbb{E}[\phi_{t,a}^{\top}\overline{Q}_{t}(S_{t},a)]=\mathbb{E}[\phi_{t,a}\phi_{t,a}^{\top}]^{-1}\mathbb{E}[\phi_{t,a}^{\top}\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})]$
$\displaystyle\tilde{\theta}_{t,a}$
$\displaystyle=\mathbb{E}_{n}[\phi_{t,a}\phi_{t,a}^{\top}]^{-1}\mathbb{E}_{n}[\phi_{t,a}^{\top}\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{(k)})]=\mathbb{E}_{n}[\phi_{t,a}\phi_{t,a}^{\top}]^{-1}\sum_{k=1}^{K}\mathbb{E}_{k}[\phi_{t,a}^{\top}\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{(k)})]$
$\displaystyle\hat{\theta}_{t,a}$
$\displaystyle=\mathbb{E}_{n}[\phi_{t,a}\phi_{t,a}^{\top}]^{-1}\sum_{k=1}^{K}\mathbb{E}_{k}[\phi_{t,a}^{\top}\tilde{Y}_{t,a}(\zeta_{t}^{(k)},{\overline{\theta}}_{t+1,a}^{(k)})]$

Note that

$\displaystyle\sqrt{n}(\hat{\theta}_{t,a}-\theta_{t,a}^{*})$
$\displaystyle=\sqrt{n}(\hat{\theta}_{t,a}-\tilde{\theta}_{t,a})+{\sqrt{n}(\tilde{\theta}_{t,a}-\theta_{t,a}^{*})}$

Orthogonality and cross-fitting in Proposition 6 establish that the first term
is $o_{p}(1)$. The second term includes ${\overline{\theta}}_{t+1,a}^{(k)}$ as
a generated regressor term, and we establish its asymptotic variance by GMM.

Note that

$\displaystyle\sqrt{n}(\hat{\theta}_{t,a}-\tilde{\theta}_{t,a})$
$\displaystyle=\mathbb{E}_{n}[\phi_{t,a}\phi_{t,a}^{\top}]^{-1}\sum_{k=1}^{K}\left\\{\mathbb{E}_{k}[\phi_{t,a}^{\top}\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})]-\mathbb{E}_{k}[\phi_{t,a}^{\top}\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})]\right\\}$
$\displaystyle=\mathbb{E}_{n}[\phi_{t,a}\phi_{t,a}^{\top}]^{-1}\sum_{k=1}^{K}\left\\{\mathbb{E}\left[\phi_{t,a}^{\top}\left(\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})-\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})\right)\right]\right\\}$
$\displaystyle\qquad+\mathbb{E}_{n}[\phi_{t,a}\phi_{t,a}^{\top}]^{-1}\sum_{k=1}^{K}\left\\{(\mathbb{E}_{k}-\mathbb{E})\left[\phi_{t,a}^{\top}\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})-\phi_{t,a}^{\top}\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})\right]\right\\}$

We will show the first term is $o_{p}(n^{-\frac{1}{2}})$ by orthogonality.
Define

$\displaystyle S_{1,k}$
$\displaystyle:=\mathbb{E}\left[\phi_{t,a}^{\top}\left(\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})-\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})\right)\right]$

We consider elements of the vector-valued moment condition: for each
$j=1,\dots,p:$

$\displaystyle=\mathbb{E}\left[(\phi_{t,a}^{\top})_{j}\mathbb{E}\left[\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})-\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})\mid
S_{t},a\right]\right]$
$\displaystyle\leq\lVert(\phi_{t,a}^{\top})_{j}\rVert\lVert\mathbb{E}[\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})-\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})\mid
S_{t},a]\rVert$
$\displaystyle\leq\overline{C}\lVert\mathbb{E}[\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})-\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})\mid
S_{t},a]\rVert$ by Assumption 11 $\displaystyle=o_{p}(n^{-\frac{1}{2}})$ by
Proposition 6

Next we study the sampling/cross-fitting terms:

$\displaystyle
S_{2,k}:=\left\\{(\mathbb{E}_{k}-\mathbb{E})\left[\phi_{t,a}^{\top}\left(\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})-\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})\right)\right]\right\\}$

Since $\left|\mathcal{I}_{k}\right|\simeq n/K$, by the concentration of iid
terms, by Cauchy-Schwarz inequality, we have that

$S_{2,k}=o_{p}\left(n^{-1/2}\sum_{i=1}^{p}\mathbb{E}\left[\left(\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})-\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})\right)^{2}\left((\phi_{t,a})_{j}\right)^{2}\right]^{1/2}\right)$

Further,

$\displaystyle\sum_{i=1}^{p}\mathbb{E}\left[\left(\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})-\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})\right)^{2}\left((\phi_{t,a})_{j}\right)^{2}\right]^{1/2}$
$\displaystyle\leq\overline{C}\lVert\tilde{Y}_{t,a}(\hat{\zeta}_{t}^{(k)},\hat{\overline{\theta}}_{t+1,a}^{(k)})-\tilde{Y}_{t,a}(\zeta_{t}^{*},{\overline{\theta}}_{t+1,a}^{*})\rVert$
$\displaystyle=o_{p}(1)$ by consistency of nuisances

Therefore, by continuous mapping theorem, Slutsky’s theorem, and Assumption
11, $\sqrt{n}(\hat{\theta}_{t,a}-\tilde{\theta}_{t,a})=o_{p}(1)$.

Next we study ${\sqrt{n}(\tilde{\theta}_{t,a}-\theta_{t,a}^{*})}$. One
approach for establishing asymptotic variance under generated regressors is
via GMM, which we do so in this setting [Newey and McFadden, 1994]. We can
write $\overline{\theta}$ as the parameter vector satisfying the “stacked”
moment conditions (over timesteps and actions) at the true quantile parameter
$\zeta$ (via our previous orthogonality analysis).

The moment functions for the robust $Q$-function parameters of interest,
$\overline{\theta}_{t,\cdot}$, satisfy:

$\left\\{0=\mathbb{E}\left[\left\\{\tilde{Y}_{t,a}(\zeta_{t}^{*},\overline{\theta}_{t+1})-{\overline{\theta}^{\top}_{t,a}}\phi_{t,a}\right\\}\phi^{\top}_{t,a}\mid
A=a\right]\right\\}_{a\in\mathcal{A},t=1,\dots,T}$ (31)

We let these stacked moments be denoted as
$\\{0=\mathbb{E}[g_{t,a}(\zeta^{*},\bar{\theta})]\\}_{a\in\mathcal{A},t=0,\dots,T-1}.$

For GMM, the asymptotic covariance matrix is given by

$\sqrt{n}(\tilde{\theta}_{t,a}-\theta_{t,a}^{*})\stackrel{{\scriptstyle
d}}{{\longrightarrow}}-\left(G^{\prime}G\right)^{-1}G^{\prime}N(0,I)=N(0,V)$

where ${G}=\partial{g}(\zeta^{*},\bar{\theta})/\partial\theta$ and a
consistent estimator of the asymptotic variance is given by
$\hat{V}=\left(\hat{G}^{\prime}\hat{G}\right)^{-1},\hat{G}=\partial\hat{g}(\zeta^{*},{\bar{\theta}})/\partial{\bar{\theta}}$.

Note that $G$ is a block upper triangular matrix. The (blockwise) entries on
the time diagonal are given by the covariance matrix
$\phi_{t,a}\phi_{t,a}^{\top}$ (i.e., from linear regression). The lower
entries, i.e.
$\partial{g}_{t,a}(\zeta^{*},\overline{\theta})/\partial\overline{\theta}_{t+1,a^{\prime}}$
are given below, by differentiating under the integral:

$\displaystyle\frac{\partial
g_{t,a}(\zeta^{*},\overline{\theta})}{\partial\overline{\theta}_{t+1,a^{\prime}}}\left\\{\mathbb{E}\left[\left\\{\left(\alpha_{t,a}{Y}_{t,a}(\overline{\theta}_{t+1})+(1-{\alpha}_{t,a})\cdot\textstyle\frac{1}{1-\tau}\Big{(}{Y}_{t,a}(\overline{\theta}_{t+1})\mathbb{I}({Y}_{t,a}(\overline{\theta}_{t+1})\leq\zeta_{t,a}^{\top}\phi_{t,a})\right.\right.\right.\right.$
$\displaystyle\qquad\left.\left.\left.\left.-\zeta_{t,a}^{\top}\phi_{t,a}\cdot[\mathbb{I}\\{{Y}_{t,a}(\overline{\theta}_{t+1})\leq\zeta_{t,a}^{\top}\phi_{t,a}\\}-(1-\tau)]\Big{)}\right)-{\overline{\theta}_{t,a}}^{\top}\phi_{t,a}\right\\}\phi_{t,a}^{\top}\mid
A=a\right]\right\\}$
$\displaystyle=\mathbb{E}\left[\alpha_{t,a}(\phi(S_{t+1},a^{\prime})\phi(S_{t},A_{t})^{\top})+\frac{1-{\alpha}_{t,a}}{1-\tau}\left(\int_{-\infty}^{q}(\phi(S_{t+1},a_{t+1}))dP_{S_{t+1}\mid
S_{t},A_{t}}\right)\phi^{\top}(S_{t},A_{t})\mid A_{t}=a\right]$
$\displaystyle=\mathbb{E}[\alpha_{t,a}(\phi(S_{t+1},a^{\prime})\phi(S_{t},a)^{\top})]+\mathbb{E}\left[({1-{\alpha}_{t,a}})(\mathbb{E}[\phi(S_{t+1},a_{t+1})\mid
Y_{t+1}\leq\zeta_{t,a}^{\top}\phi_{t,a},S_{t},A_{t}=a]\phi^{\top}(S_{t},a)\right]$

Denote $Z^{\phi_{t+1}}_{a_{t+1}}(S_{t},a)=\mathbb{E}[\phi(S_{t+1},a_{t+1})\mid
Y_{t+1}\leq\zeta_{t,a}^{\top}\phi_{t,a},S_{t},A_{t}=a]$, then

$\displaystyle\frac{\partial
g_{t,a}(\zeta^{*},\overline{\theta})}{\partial\overline{\theta}_{t+1,a^{\prime}}}$
$\displaystyle=\mathbb{E}\left[\alpha_{t,a}(\phi(S_{t+1},a^{\prime})\phi(S_{t},a)^{\top})+({1-{\alpha}_{t,a}})(Z^{\phi}_{a^{\prime}}(S_{t},a)\phi^{\top}(S_{t},a))\right]$
$\displaystyle=\mathbb{E}\left[\alpha_{t,a}(\phi_{t+1,a^{\prime}}\phi_{t,a}^{\top})+({1-{\alpha}_{t,a}})(Z^{\phi}_{a^{\prime},t,a}\phi^{\top}_{t,a})\right]$
$\displaystyle=\tilde{\Sigma}^{t+1,a^{\prime}}_{t,a}+\tilde{\Omega}^{{a^{\prime},t,a}}_{t,a}$

So, $G$ is a block upper triangular matrix:

$\displaystyle\begin{bmatrix}\ddots&\ldots\\\
0&\mathbb{E}[\phi_{t,a}\phi_{t,a}^{\top}]&\\{\tilde{\Sigma}^{t+1,a^{\prime}}_{t,a}+\tilde{\Omega}^{{a^{\prime},t,a}}_{t,a}\\}_{a^{\prime}\in\mathcal{A}}\\\
0&0&\ddots&\\{\tilde{\Sigma}^{t+1,a^{\prime}}_{t,a_{k}}+\tilde{\Omega}^{{a^{\prime},t,a_{k}}}_{t,a_{k}}\\}_{a^{\prime}\in\mathcal{A}}\\\
0&0&0&\mathbb{E}[\phi_{t,a_{K}}\phi_{t,a_{K}}^{\top}]&\\{\tilde{\Sigma}^{t+1,a^{\prime}}_{t,a_{K}}+\tilde{\Omega}^{{a^{\prime},t,a_{K}}}_{t,a_{K}}\\}_{a^{\prime}\in\mathcal{A}}\end{bmatrix}$

∎

##  Appendix E Details on experiments

###  E.1 Low-Dimensional Parameter Values

$\theta_{A}=-0.05$, $\sigma=0.36$, $\gamma=0.9$, $H=4$.

The matrices $A$ and $B$ were chosen randomly with a fixed random seed:

        np.random.seed(1)
        B_sparse0 = np.random.binomial(1,0.3,size=d)
        B = 2.2*B_sparse0 * np.array( [ [ 1/(j+k+1) for j in range(d) ]
                                                    for k in range(d) ] )

        np.random.seed(2)
        A_sparse0 = np.random.binomial(1,0.6,size=d)
        A = 0.48*A_sparse0 * np.array( [ [ 1/(j+k+10) for j in range(d) ]
                                                      for k in range(d) ] )

Likewise for $\theta_{R}$:

        theta_R = 3 * np.random.normal(size=d) * np.random.binomial(1,0.3,size=d)

###  E.2 High-Dimensional Parameter Values

$\theta_{A}=-0.05$, $\sigma=0.1$, $\gamma=0.9$, $H=4$.

The matrices $A$ and $B$ were chosen randomly with a fixed random seed:

        np.random.seed(1)
        B_sparse0 = np.random.binomial(1,0.3,size=d)
        B = 2.2*B_sparse0 * np.array( [ [ 1/(j+k+1) for j in range(d) ]
                                                    for k in range(d) ] )/1.2

        np.random.seed(2)
        A_sparse0 = np.random.binomial(1,0.6,size=d)
        A = 0.48*A_sparse0 * np.array( [ [ 1/(j+k+10) for j in range(d) ]
                                                      for k in range(d) ] )/20

Likewise for $\theta_{R}$:

        theta_R = 2 * np.random.normal(size=d) * np.random.binomial(1,0.3,size=d)

###  E.3 Function Approximation

Conditional expectations were approximated with the Lasso using scikit-learn’s
implementation, with regularization hyperparameter $\alpha$ = 1e-4.
Conditional quantiles were approximated with scikit-learn’s
$\ell_{1}$-penalized quantile regression, regularization hyperparameter
$alpha$ = 1e-2, using the highs solver.

###  E.4 Calculating Ground Truth

To provide ground truth for our sparse linear setting, we analytically derive
the form of the robust Bellman operator. Consider the candidate $Q$ function,
$Q(s,0)=\beta^{\top}s+a_{0},Q(s,1)=\beta^{\top}s+a_{1}$. Then,

$\displaystyle Y_{t}$
$\displaystyle=\theta_{R}^{\top}S_{t+1}+\gamma\beta^{\top}S_{t+1}+\theta_{A}\gamma\max\\{1_{d}^{\top}\theta_{R},0\\}$
$\displaystyle=\theta_{R}^{\top}S_{t+1}+\gamma\beta^{\top}S_{t+1}+\theta_{A}\gamma
1_{d}^{\top}\theta_{R}$

where we chose simulation parameters such that
$\theta_{A}\gamma\max\\{1_{d}^{\top}\theta_{R},0\\}>0$. Therefore:

$Y_{t}|S_{t},A_{t}\sim\mathcal{N}\left((\theta_{R}+\gamma\beta)^{\top}(BS_{t}+\theta_{A}A_{t})+\theta_{A}\gamma
1_{d}^{\top}\theta_{R},\sqrt{\sum_{i=1}^{d}(\theta_{R}+\gamma\beta)_{i}^{2}(AS_{t}+\sigma)_{i}^{2}}\right)$

Since $Y_{t}$ is conditionally Gaussian, we apply Lemma 8:

$\displaystyle(\bar{\mathcal{T}}^{*}_{t}Q)(s,a)$
$\displaystyle=\mathbb{E}[Y_{t}|S_{t}=s,A_{t}=a]-0.5C(\Lambda)\sqrt{\text{Var}[Y_{t}|S_{t}=s,A_{t}=a]}$
$\displaystyle=(\theta_{R}+\gamma\beta)^{\top}(BS_{t}+\theta_{A}A_{t})+\theta_{A}\gamma
1_{d}^{\top}\theta_{R}-0.5C(\Lambda)\sqrt{\sum_{i=1}^{d}(\theta_{R}+\gamma\beta)_{i}^{2}(AS_{t}+\sigma)_{i}^{2}}$

First, note that the slope w.r.t. $S_{t}$ is not a function of $A_{t}$
validating our choice of an action-independent $\beta$. Second, note that only
the last term is non-linear in $S_{t}$. So the ground truth for FQI with Lasso
adds the first two terms to the closest linear approximation of this last
term. Since our object of interest is the average optimal value function at
the initial state, we perform this linear approximation in terms of mean
squared error at the initial state. In practice, we compute this by drawing
$200,000$ samples i.i.d. from the initial state distribution and then doing
linear regression on this last term. Plugging the slope and intercept back in
is extremely close to the best linear approximation of
$(\bar{\mathcal{T}}^{*}_{t}Q)(s,a)$.