# Rethinking the objectives of extractive question answering

Martin Fajcik, Josef Jon, Santosh Kesiraju, Pavel Smrz
Brno University of Technology
<EMAIL_ADDRESS>
###### Abstract

This paper describes two generally applicable approaches towards significant
improvement of performance of state-of-the-art extractive question answering
(EQA) systems.
Firstly, contrary to a common belief, it demonstrates that using the objective
with independence assumption for span probability
$P(a_{s},a_{e})=P(a_{s})P(a_{e})$ of span starting at position $a_{s}$ and
ending at position $a_{e}$ may have adverse effects. Therefore we propose a
new compound objective that models joint probability $P(a_{s},a_{e})$
directly, while still keeping the objective with independency assumption as an
auxiliary objective.
Our second approach shows the beneficial effect of distantly semi-supervised
shared-normalization objective known from Clark and Gardner (2017). We show
that normalizing over set of documents similar to golden passage, and
marginalizing over all ground-truth answer string positions leads to
improvement of results from smaller statistical models.
Our results are supported via experiments with three QA models (BidAF, BERT,
ALBERT) over six datasets. The proposed approaches do not use any additional
data.
Our code, analysis, pretrained models and individual results will be available
online.

##  1 Introduction

The common goal of extractive question answering (EQA) is to find the span
boundaries – the start and the end of span from text evidence, which answers a
given question. Therefore, a natural choice of objective to this problem is to
model the probabilities of the span boundaries. In last years, there was a lot
of effort put into building better neural models underlying the desired
probability distributions. However, there has been a little progress seen
towards the change of the objective itself. For instance, the “default“ choice
of objective for modeling the probability over spans in SQuAD Rajpurkar et al.
(2016) – maximization of independent span boundary probabilities
$P(a_{s})P(a_{e})$ for answer at position $\langle a_{s}$,$a_{e}\rangle$ – has
stayed the same over the course of years in many influential works Xiong et
al. (2016); Seo et al. (2016); Chen et al. (2017); Yu et al. (2018); Devlin et
al. (2019) since the earliest work on this dataset – the submission of Wang
and Jiang (2016). Based on the myths of worse performance of different
objectives, these works adopt the deeply rooted assumption of independency.
This assumption may lead to obviously wrong predictions, as showed in Figure
1. In addition, this assumption leads to degenerate distribution
$P(a_{s},a_{e})$, as high probability mass is assigned to many trivially
wrong111We define ’trivially wrong’ as not resembling any string form human
would answer, e.g., the first or the second last answer of Figure 1. answers.

P |  Predictions from BERT-base
---|---
33.3 |  little boy uranium gun-type bomb on Hiroshima. three days later, on August 9, a fat man
32.15 |  little boy
23.51 |  fat man
3.60 |  a fat man
2.08 |  a little boy uranium gun - type bomb on hiroshima. three days later, on august 9, a fat man
1.03 |  a little boy

Figure 1:  An example of an error which comes with an independency assumption.
The model assigns high probability mass to boundaries around “little boy“, and
“fat man“ answers. However, during decoding the start of one and the end of
another answer is picked up.

Only recently, large language representation models (LRMs) like XLNet Yang et
al. (2019), ALBERT Lan et al. (2019) or ELECTRA Clark et al. (2020) started
modeling the span probability via conditional probability factorization
$P(a_{e}|a_{s})P(a_{s})$. However, is it unknown whether this objective
improves any performance at all, as none of the works reported results on its
effect, not even described its existence (except from ELECTRA paper).
Additionally, this objective requires beam search which slows down inference
in test time. In this work, we try to break the myths about the objectives
that have been widely used previously. We also introduce a new compound
objective, that deals with modeling joint probability $P(a_{s},a_{e})$
directly, while keeping the traditional independent objective as an auxiliary
objective. Conducted experiments demonstrate that our objective is superior to
previously used objectives across the various choices of models or datasets.

Secondly, orthogonal to first approach, this work explores the possibility of
distant semi-supervised training of EQA systems. Our approach is based on
multi-passage shared-normalization training objective (SNO) of Clark and
Gardner (2017). The authors demonstrate that training EQA model with the SNO
damages its performance in closed-domain setting222See Table 4 in Clark and
Gardner (2017).. Their results support the belief that closed-domain EQA
system cannot benefit from distant semi-supervision with SNO. However, we
disprove this belief, by showing that fine-tuning EQA models by including
topically similar passages from the closed-domain dataset and using distantly
supervised ground truth annotation can be beneficial towards improving EQA
performance in closed-domain setting by improving its performance and also its
robustness for smaller models.

In summary our work contributions are:

  * •

introduction of the novel compound objective and its comparison with the
traditional objectives based on assumption of independency or conditional
factorization,

  * •

we show that multi-passage shared normalization objective improves the closed-
domain EQA robustness and performance for smaller models,

  * •

a thorough evaluation on the wide spectrum of models and datasets comparing
different objectives supported by statistical tests.

##  2 Compound Objective

This section describes the common approach to the EQA, with its independent
modeling of the answer span start and end positions. We propose an extension
towards relieving this assumption by defining a compound objective.

The EQA can be defined as follows: Given a question $q$ and a passage or a set
of passages $D$, find an answer string $a$ from $D$ such that $a$ answers the
question $q$. This can be expressed by modeling a categorical probability mass
function (PMF) that has its maximum in the answer endpoint indices $a=\langle
a_{s},a_{e}\rangle$ from the passage $D$ as $P(a_{s},a_{e}|q,D)$ for each
question-passage-answer triplet $(q,D,a)$ from dataset $\mathcal{D}$. During
inference, the most probable answer span $\langle a_{s},a_{e}\rangle$ is
predicted. Although there are works that were able to explicitly model the
joint probability Lee et al. (2016), modeling it directly results in number of
categories which is quadratic to the passage’s length. Optimizing such models
with the amount of data available today may lead toward poor parameter
estimates. Therefore, state-of-the-art approaches modeling the answer span PMF
introduce the independence assumption
$P(a_{s},a_{e}|q,D)=P(a_{s}|q,D)P(a_{e}|q,D)$. The factorized PMFs are usually
computed by the shared model, as introduced in Wang and Jiang (2016).

Our work proposes an extension to the described approach, replacing the
standard independent objective, that maximizes the probability
$P(a_{s}|q,D)P(a_{e}|q,D)$, with the multi-task compound objective (1)
computed via a shared model333For brevity, $q,D$ dependencies were omitted..

$\sum_{(q,D,a)\in\mathcal{D}}\log
P_{\theta}(a_{s},a_{e})P_{\theta}(a_{s})P_{\theta}(a_{e})$ (1)

The auxiliary independent objective $P(a_{s})P(a_{e})$ can be seen as a form
of regularization for the joint objective $P_{\theta}(a_{s},a_{e})$, which is
used in test time.

For most of the systems modeling the independent objective with neural
networks, the final endpoint probabilities are derived from start/end position
passage representations
$\boldsymbol{H}_{s}$,$\boldsymbol{H}_{e}\in\mathbb{R}^{d\times L}$ as showed
for $b\in\\{s,e\\}$.

$P_{\theta}(a_{b})=\mathrm{softmax}(\boldsymbol{w}_{b}^{\top}\boldsymbol{H}_{b}+\boldsymbol{b}_{b})$
(2)

The passage representations $\boldsymbol{H}_{s}$,$\boldsymbol{H}_{e}$ are
often pre-softmax layer representations from neural network with passage and
question at the input. Symbols $d$ and $L$ denote the model-specific dimension
and the passage length, respectively.

For the joint objective $P_{\theta}(a_{s},a_{e})$, an arbitrary vector-to-
vector similarity function $f_{sim}$ can be used for obtaining each span score
(e. g., the dot product $\boldsymbol{H}_{s}^{\top}\boldsymbol{H}_{e}$)444Here,
we slightly abuse the notation for the sake of generality. See Subsection 4.2
for specific applications..

$P_{\theta}(a_{s},a_{e})=\mathrm{softmax}(\mathrm{vec}(f_{sim}(\boldsymbol{H}_{s},\boldsymbol{H}_{e})))$
(3)

##  3 Training with Distant Semi-Supervision

We follow the shared normalization objective (SNO) introduced in Clark and
Gardner (2017) for multi-paragraph answer selection. Given a set of topically
close passages $D$, with each passage containing its set of position indices
$p$, ground truth span annotating function555The function returns all
positions of an answer string in the passage. This is the distant supervision.
$GT(p)\subseteq p$ that returns a set of answer indices for span boundary type
$b\in\\{start,end,joint\\}$ and scores for each span boundary $s$, the shared
normalization objective can be generally defined as:

$P(a_{b})=\frac{\sum_{p\in D}\sum_{a_{b}\in GT(p)}e^{s_{a_{b}}}}{\sum_{p\in
D}\sum_{a_{b}\in p}e^{s_{a_{b}}}}$ (4)

The passage set $D$ of context size $|D|$ for question $q$ in this experiment
is obtained from a top-K most probable passages scored via passage retrieval
model $P(p|q)$ over all passages in the dataset.

##  4 Experimental Setup

We use Transformers Wolf et al. (2019) for LRM implementation. Our experiments
were done on a machine with four 16GB GPUs using PyTorch Paszke et al. (2019).
We used the Adam optimizer with a decoupled weight decay Loshchilov and Hutter
(2017). For experiments with LRMs, the SQuAD1.1 default hyperparameters and
scheduler settings were used, as proposed by specific LRM authors.

###  4.1 Datasets

Dataset | Train | Test
---|---|---
SQuAD1.1 | 87,599 | 10,570
SQuAD2.0 | 130,319 | 11,873
Adversarial SQuAD | - | 3,560
Natural Questions | 104,071 | 12,836
NewsQA | 74,160 | 4,212
TriviaQA | 61,688 | 7,785
Table 1: Number of examples per each dataset used in this paper.

We evaluate our approaches on wide spectrum of datasets. The statistics to all
datasets are shown in Table 1. To focus only on the extractive part of QA and
to keep the format the same, we use curated versions of the last 3 datasets as
released in MrQA shared task Fisch et al. (2019).

SQuAD v1.1 Rajpurkar et al. (2016), is a popular dataset composed from
question, paragraphs and answer span annotation collected from the subset of
Wikipedia passages.

SQuAD v2.0 Rajpurkar et al. (2018) is an extension of SQuAD v1.1 with
additional 50k questions and passages, which are topically similar to the
question, but do not contain an answer.

Adversarial SQuAD Jia and Liang (2017) tests, whether the system can answer
questions about paragraphs that contain adversarially inserted sentences,
which are automatically generated to distract computer systems without
changing the correct answer or misleading humans. In particular, our system is
evaluated in AddSent adversary setting, which runs the model as a black box
for each question on several paragraphs containing different adversarial
sentences and picks the worst answer.

Natural Questions Kwiatkowski et al. (2019) dataset consists of real users
queries obtained from Google search engine. Each example is accompanied by a
relevant Wikipedia article found by the search engine, and human annotation
for long/short answer. Long answer is typically the most relevant paragraph
from the article, while short answer consists of one or multiple entities or
short text spans. We only consider short answers in this work.

NewsQA Trischler et al. (2017) is a crowd-sourced dataset based on CNN news
articles. Answers are short text spans and the questions are designed such
that they require reasoning and inference besides simple text matching.

TriviaQA Joshi et al. (2017) consists of question-answer pairs from 14
different trivia quiz websites and independent evidence passages collected
using Bing search from various sources such as news, encyclopedias, blog posts
and others. Additional evidence is obtained from Wikipedia through entity
linker.

###  4.2 Applied models

Our experiments are based on three EQA models:

BERT Devlin et al. (2019) and ALBERT Lan et al. (2019) are LRMs based on the
self-supervised pretraining objective. During fine-tuning, each model is
applied on the concatenation of question and passage representations. Outputs
$\boldsymbol{H}\in\mathbb{R}^{d\times L}$ corresponding to the passage inputs
of length $L$ are then reduced to boundary probabilities by two vectors
$\boldsymbol{w_{s}}$, $\boldsymbol{w_{e}}$ as
$P(a_{b})=\mathrm{softmax}(\boldsymbol{w}_{b}^{\top}\boldsymbol{H}+\boldsymbol{b}_{b})$.
To compute joint probability $P(a_{s},a_{e})$, start representations are
computed using $\boldsymbol{W}\in\mathbb{R}^{d\times d}$ and
$\boldsymbol{b}\in\mathbb{R}^{d}$ (broadcasted) as
$\boldsymbol{H}_{s}=\boldsymbol{W}\boldsymbol{H}+\boldsymbol{b}$ and end
representations as $\boldsymbol{H}_{e}=\boldsymbol{H}$. A dot product is used
as the similarity measure.

$P(a_{s},a_{e})=\mathrm{softmax}(\mathrm{vec}(\boldsymbol{H}_{s}^{\top}\boldsymbol{H}_{e}))$
(5)

See Appendix B for experiments with different similarity measures. For
modeling conditional probability factorization objective, we closely follow
the implementation from Lan et al. (2019), and provide exact details in the
Appendix C.

Model | Obj | SQ1 | SQ2 | AdvSQ | TriviaQA | NQ | NewsQA
---|---|---|---|---|---|---|---
| I | 81.31/88.65 |  73.89/76.74 | 47.04/52.62 | 62.88/69.85 | 65.66/78.20 | 52.39/67.17
| J | 81.33/88.13 | 72.66/75.04 | 48.10/53.54 |  63.93/69.90 |  67.82/78.72 | 52.71/66.43
BERT | JC | 80.96/87.86 | * | 45.33/50.59 | 62.68/69.81 | 65.66/78.33 | 52.39/67.05
| I+J |  81.83/88.52 | 73.53/76.14 |  48.32/53.47 |  63.68/69.71 |  67.73/78.78 |  52.90/66.79
| I+J(DSS) |  82.15 /88.90 |  74.77/77.29 |  49.91/55.32 | * | 67.85/78.94 | *
| I | 88.55/94.62 | 87.07/90.02 | 68.12/73.54 | 74.72/80.34 | 70.79/83.39 | 59.91/74.97
| J | 88.84/94.64 | 86.87/89.71 | 68.90/74.17 | * | * | *
ALBERT | JC | 88.50/94.51 | * | 66.75/72.03 | * | * | *
| I+J |  89.02/94.77 |  87.13/89.98 |  69.57/74.76 |  75.36/80.48 |  73.36/84.12 |  60.45/74.48
| I+J(DSS) | 89.04/94.82 | 87.16/89.95 | 68.20/73.60 | - | - | -
Table 2:  Results of different objectives through the spectrum of datasets.
Bold results mark best EM across the objectives. Cursive on I+J row marks
results, which are improved significantly over independent objective.
Underscore on I+J(DSS) row marks results which improve significantly over
compound results (I+J row). We are still obtaining results marked with * and
we plan to release them in paper’s final version.

BiDAF Seo et al. (2016) dominated the state-of-the-art systems in 2016 and
motivated a lot of following research work Clark and Gardner (2017); Yu et al.
(2018). Question and passage inputs are represented via the fusion of word-
level embeddings from GloVe Pennington et al. (2014) and character-level word
embeddings obtained via a convolutional neural network. Independently
represented questions and passages are then combined into a common
representation via two directions of attention over their similarity matrix
$\boldsymbol{S}$. The similarity matrix is computed via multiplicative-
additive interaction (6) between each pair of question vector
$\boldsymbol{q_{i}}$ and passage vector $\boldsymbol{p_{j}}$, where ; denotes
concatenation and $\circ$ stands for the Hadamard product.

$\boldsymbol{S_{ij}}=f_{sim_{ma}}(\boldsymbol{q_{i}},\boldsymbol{p_{j}})=\boldsymbol{w}^{\top}[\boldsymbol{q_{i}};\boldsymbol{p_{j}};\boldsymbol{q_{i}}\circ\boldsymbol{p_{j}}]$
(6)

Common representations are then concatenated together with document
representations and passed towards two more recurrent layers – first to obtain
answer-start representations
$\boldsymbol{H}_{s}=[\boldsymbol{G};\boldsymbol{M}]$ and second to obtain
answer-end representations666For details, see formulae 2 to 4 in Seo et al.
(2016). $\boldsymbol{H}_{e}=[\boldsymbol{G};\boldsymbol{M}^{2}]$. The joint
probability $P(a_{s},a_{e})$ is then computed over scores from vectorized
similarity matrix of $\boldsymbol{H}_{s}$ and $\boldsymbol{H}_{e}$ using the
same similarity function $f_{sim_{ma}}$ between each two column vectors.

###  4.3 Passage retrieval

The passage set $D$ of context size $|D|$ for question $q$ in experiment with
distant semi-supervision is obtained from a top-K most probable passages
scored via passage retrieval model $P(p|q)$ over all passages in the dataset.
For passage retrieval $P(p|q)$, we separately train passage encoder and
question encoder, producing passage vector $\boldsymbol{p}$ and question
vector $\boldsymbol{q}$ representations.

To represent passages, we have used Bayesian subspace multinomial model (BSMM)
Kesiraju et al. (2019). BSMM is generative log-linear model that learns to
represent passages in the form of Gaussian distributions and achieves state-
of-the-art results in topic identification. In our experiments, we use 100
dimensional means of the Gaussian distributions as the document
embeddings.777To profit from co-variance information, we have also
experimented with KL-divergence based retrieval, gaining only negligible
improvement.. The model is trained on dataset’s training passages and used to
extract representations for all passages in the training and validation data,
therefore creating a matrix $\boldsymbol{D}\in\mathbb{R}^{\mathcal{L}\times
d}$ of $\mathcal{L}$ passages each of dimension $d$.

Our question encoder is based on RoBERTa Liu et al. (2019) LRM. Given a
question $y=(y_{1},y_{2},...,y_{n})$, vector
$\boldsymbol{q}=\boldsymbol{W}(LRM(y)[CLS])$ is extracted as a linear
projection $\boldsymbol{W}$ of CLS-level output of RoBERTa. The encoder is
trained via log-bilinear objective (7), defined on the set of dataset’s
questions $Q$, using default RoBERTa parameters and scheduler. We use dropout
$\delta$ set to 0.35.

$\sum_{q\in Q}P(p|q)=\sum_{q\in
Q}\mathrm{softmax}(\boldsymbol{D}\delta(\boldsymbol{q}))$ (7)

In test time, the nearest passages are scored via cosine similarity of
$\boldsymbol{p}$ and $\boldsymbol{q}$. To include passages with distant
supervision more often in the context, we discard 50% of passages which do not
contain exact answer overlap from the total ranking before taking top-K
passages for distant semi-supervision.

###  4.4 Prediction filtering

In recent literature, there are two common ways of filtering the prediction
probabilities:

Length filtering. Probabilities $P(a_{s}=i,a_{e}=j)$ are set to $0$ iff
$j-i>\zeta$, where $\zeta$ is a length threshold. Following Devlin et al.
(2019), we set $\zeta=30$.

Top-K surface form filtering. Following Das et al. (2019), the top-K
probabilities are aggregated for the top-$K$ span predictions for all their
surface forms (same strings) in the text. This is done by summing all
probabilities bound to same surface form into the most probable position of
that surface form and setting rest to 0. We use $K=100$.

Model |  | I | J | JC | I+J | I+J (DSS)
---|---|---|---|---|---|---
| - | 65.22/75.01 | 61.77/71.24 | - | 66.02/75.54 | 68.02/76.97
BiDAF | LF | 65.66/75.55 | 61.77/71.24 | - | 66.03/75.53 | 68.04/76.99
| SF |  65.73/75.58 | 61.78/71.23 | - |  66.05/75.55 |  68.06/77.00
| - | 80.98/88.40 | 81.30/88.11 | * | 81.80/88.50 | 82.13/88.89
BERT | LF | 81.31/88.65 |  81.33/88.13 | 80.96/87.86 |  81.83/88.52 |  82.15/88.90
| SF |  81.38/88.68 | 81.23/87.97 | - | 81.65/88.36 | 82.04/88.80
| - | 88.39/94.51 | 88.82/94.64 | * | 89.01/94.77 | 89.02/94.82
ALBERT | LF |  88.55/94.63 |  88.84/94.64 | 88.50/94.51 |  89.02/94.77 |  89.04/94.82
| SF | 88.53/94.00 | 88.28/94.10 | - | 88.68/94.49 | 88.69/94.50
Table 3:  Achieved results with different filtering approaches. We are still
obtaining results marked with * and we plan to release them in paper’s final
version.

###  4.5 Statistical testing

To improve the soundness of presented results, we use several statistical
tests. An exact match (EM) metric can be viewed as average of samples from
Bernoulli distribution. As stated via central limit theorem, a good assumption
might be the EM comes from the normal distribution. We train 10 models for
each presented LRM’s result, obtaining 10 EMs for each sample. Anderson-
Darling normality test Stephens (1974) is used to check this assumption –
whether sample truly comes from the normal distribution. Then we use the one-
tailed paired t-test to check whether case of improvement for compound
objective w.r.t. independent objective is significant and analogically whether
the improvement of compound objective with DSS w.r.t. compound objective is
significant. The improvement is significant iff p-value<0.05. We use the
reference implementation from Dror et al. (2018).

##  5 Results and Discussion

We now show the effectiveness of proposed approaches. Our main results – the
performance of independent (I), joint (J), joint-conditional (JC) and compound
(I+J) objectives – are shown in Table 2. We also train models with compound
objective inside DSS framework (see equation 4); denoted as I+J(DSS). Each of
the presented results is averaged from 10 training runs888We will release each
result measurement along with result statistics..

Firstly, we note that largest improvements can be seen for an exact match (EM)
performance metric. In fact, in some cases joint or compound objective lead to
degradation of F1, while improving EM (e.g., on SQuAD and NewsQA datasets for
BERT). Upon manual analysis, we have repeatedly identified cases where
independent model chose larger span encompassing multiple potential answers,
thus obtaining non-zero F1 score. However, we failed to identify such cases
for joint and compound models. Instead we have found these models to pick just
one of these potential answers, obtaining either full match or no F1 score at
all999We plan to add specific result of our human evaluation here..

Next, we remark that compound objective outperformed others in most of our
experiments. In BERT case, the compound objective performed significantly
better than independent objective on 5 out of 6 datasets. In ALBERT case, the
compound objective performed significantly better than independent objective 5
from 6 times and its was on par in the last case. Comparing compound to joint
objective in BERT case, the two behave almost equally, with compound objective
significantly outperforming joint objective on the two SQuAD datasets and no
significant differences for the other 4 datasets. However, we found the
convergence of joint objective to be very sensitive to hyperparameter choice
(all experiments of our preliminary results failed to converge), while we have
never observed this behaviour with compound objective. However, in ALBERT
case, the compound objective significantly improves results over joint
objective in all but one case and is on par in this last case.

Considering the results of DSS objective framework, we found it to improve the
results of smaller models in all cases for BERT and BidAF (see Table 3).
Interestingly, we found it not beneficial at all in ALBERT’s case, indicating
that the ALBERT’s pre-training captures all relevant knowledge to be obtained
from distant semi-supervision.

Upon closer inspection of results, we found possible reasons for result
degradation of the compound model on SQuAD2, and also its large improvements
gained on NQ dataset. For SQuAD2, the accuracies of no-answer detection for
indepedent/joint/compound objectives in case of BERT models are
79.89/78.12/79.32. We found the same trend for ALBERT. We hypothesize, that
this inferior performance of joint and compound models may be caused by their
higher probability space complexity. To confirm that compound model is better
at answer extraction step, we run models trained on SQuAD2 data with answer,
while masking model’s no-answer option. The results shown in Table 4 support
this hypothesis. On the other side, we found the large improvements over NQ
might be exaggerated by evaluation approach of MRQA, where in case of multi-
span answers, choosing one of the spans from multi-span answer counts as
correct. Upon closer result inspection, we found that independent model here
was prone to select start of one start of span from multi-span answer and end
from another answer from multi-span.

In addition we found that models trained via compound objective does not
benefit from previously used heuristics such as length filtering (LF) or
surface form filtering (SF) significantly, as shown in Table 3. Therefore, we
find it unnecessary to use these heuristics anymore. Note that results from SF
already include LF. In this experiment, we also include our preliminary
results with BiDAF, which show significant improvement of its performance on
SQuADv1.1 dataset from both presented approaches.

| Objective | EM | F1
---|---|---|---
BERT | I | 80.70 | 88.71
J | 81.38 | 81.51
I+J | 81.51 | 88.69
DSS | 81.85 | 88.99
ALBERT | I | 87.40 | 94.10
J | 87.74 | 94.31
I+J | 87.90 | 94.38
DSS | 87.97 | 94.31
Table 4:  Performance of SQuADv2.0 models on answerable examples of SQuADv2.0.

##  6 Analysis

Question | Passage |  Independent |  Compound |  Ground Truth
---|---|---|---|---
What company won a free advertisement due to the QuickBooks contest? |  QuickBooks sponsored a "Small Business Big Game" contest, in which Death Wish Coffee had a 30-second commercial aired free of charge courtesy of QuickBooks. Death Wish Coffee beat out nine other contenders from across the United States for the free advertisement. |  Death Wish Coffee had a 30-second commercial aired free of charge courtesy of QuickBooks. Death Wish Coffee |  Death Wish Coffee |  Death Wish Coffee
In what city’s Marriott did the Panthers stay? |  The Panthers used the San Jose State practice facility and stayed at the San Jose Marriott. The Broncos practiced at Stanford University and stayed at the Santa Clara Marriott. |  San Jose State practice facility and stayed at the San Jose |  San Jose |  San Jose
What was the first point of the Reformation? |  Luther’s rediscovery of "Christ and His salvation" was the first of two points that became the foundation for the Reformation. His railing against the sale of indulgences was based on it. |  Christ and His salvation" |  Christ and His salvation |  Christ and His salvation
How many species of bird and mammals are there in the Amazon region? |  The region is home to about 2.5 million insect species, tens of thousands of plants, and some 2,000 birds and mammals. To date, at least 40,000 plant species, 2,200 fishes, 1,294 birds, 427 mammals, 428 amphibians, and 378 reptiles have been scientifically classified in the region. One in five of all the bird species in theworld live in the rainforests of the Amazon, and one in five of the fishspecies live in Amazonian rivers and streams. Scientists have describedbetween 96,660 and 128,843 invertebrate species in Brazil alone. |  2,000 birds and mammals. To date, at least 40,000 plant species, 2,200 fishes, 1,294 birds, 427 |  427 |  2,000
What was found to be at fault for the fire in the cabin on Apollo 1 regarding the CM design? |  NASA immediately convened an accident review board, overseen by both houses of Congress. While the determination of responsibility for the accident was complex, the review board concluded that "deficiencies existed in Command Module design, workmanship and quality control." At the insistence of NASA Administrator Webb, North American removed Harrison Storms as Command Module program manager. Webb also reassigned Apollo Spacecraft Program Office (ASPO) Manager Joseph Francis Shea, replacing him with George Low. |  deficiencies existed in Command Module design, workmanship and quality control." |  Harrison Storms |  deficiencies

Table 5:  Examples of predictions from SQuAD using BERT trained with
independent and compound objective.

Apart from example in Figure 1, we provide more examples of different
predictions between models trained with independent and compound objective in
Table 5. In general, by doing manual analysis of errors, we noticed three
types of errors being fixed by the compound objective model in BERT:

  1. 1.

The model assigns high probability to answer surrounded with the paired tags
(e. g. quotes). It chooses the answer without respecting the symmetry between
paired tags (third row of Table 5).

  2. 2.

Uncertainty of the model causes it to assign high probabilities to two spans
containing same answer string. During decoding the start/end boundaries of two
same answers are picked up (first row of Table 5). This can be alleviated with
the surface form filtering.

  3. 3.

Uncertainty of the model causes it to assign high probabilities of two
different answer boundaries. During decoding the start/end boundaries of two
different answers are picked up (fourth row in Table 5).

Interestingly, we found it hard to directly identify any of the mentioned
error types in ALBERT’s predictions101010The full difference of BERT’s and
ALBERT’s predictions can be found at https://tinyurl.com/y5f5uevc..

To show, that spans retrieved with compound objective approach differ from the
ones retrieved when using independent objective, we took top 20 most probable
spans from each model and averaged their length. This was done for each
example in the development data. The histogram of these averages is showed in
Figure 2. For fair comparison, these predictions were filtered via length
filtering.

Figure 2: Histograms of average character length of top-20 predicted answers
from BERT trained with different objectives compared with character length of
ground-truth answers.

##  7 Related work

Learning objective. One of the earliest works in EQA from Wang and Jiang
(2016) experimented with generative models based on index sequence generation
via pointer networks Vinyals et al. (2015) and now traditional boundary models
that focus on prediction of start/end of an answer span. Their work showed
substantial improvement of boundary models over the index sequence generative
models.

Xiong et al. (2016) explored an iterative boundary model. They used RNN and a
highway maxout network to decode start/end of span independently in multiple
timesteps, each time feeding the RNN with predictions from the previous time
step until the prediction was not changing anymore. In their following work
Xiong et al. (2017) combined their objective with reinforcement learning
approach, in which the decoded spans from each timestep were treated as a
trajectory. They argued that cross-entropy is not reflecting F1 performance
well enough, and defined a reward function equal to F1 score. Finally, they
used policy gradients as their auxiliary objective, showing 1% improvement in
the terms of F1 score.

Authors of recent LRMs like XLNet Yang et al. (2019), ALBERT Lan et al. (2019)
or ELECTRA Clark et al. (2020) started modeling conditional probability
factorization $P(a_{e}|a_{s})P(a_{s})$ for answer extraction in some
cases111111For instance, ALBERT uses conditional objective for SQuADv2.0, but
not for SQuADv1.1.. Although the objective is not described in mentioned
papers (except for ELECTRA), we follow the recipe for modeling the conditional
probability from their implementation in this work. We believe this is the
first official comparison of this objective w.r.t. others.

The most similar to our work is RaSoR system Lee et al. (2016). In their work,
authors compared various objectives including binary answer classification of
every input token, BIO sequence classification with CRF layer on top of their
model, and most importantly joint objective, which turns out to work the best.
However, in our experiments, training with the joint objective alone does not
perform that well, while also being less stable to the choice of
hyperparameters. Also, we use dot product as similarity function while Lee et
al. (2016) used feed-forward neural network.

Semi-supervision and distant supervision. Dhingra et al. (2018) exploit the
structure of dataset passages to create cloze-style questions. They pretrain a
powerful neural network on the cloze-style pseudo-questions and fine-tune the
model on the labeled examples.

Chen et al. (2017) shows an improvement in open-domain QA when using distantly
supervised ground truths with the same surface form as the original ground
truth.

Clark and Gardner (2017) present a shared normalization objective (SNO) to
alleviate the problems with multi-paragraph answer selection. Using a model
trained via SNO, and TF-IDF based retrieval system retrieving passages from
whole Wikipedia, they show a significant improvement in open-domain question
answering. However, when evaluating the model trained with their objective in
the closed-domain setting over paragraphs from the same article of Wikipedia
as the golden paragraph, they found a slight decrease in performance.
Contrarily, using different retrieval approach, we even found that their
objective can significantly improve closed-domain performance.

Concurrently with our work, Cheng et al. (2020) explored different objective
assumptions for BERT on multi-paragraph QA datasets TriviaQA and NarrativeQA.
They have also experimented with DSS (in their paper called as maximum
marginal likelihood over document space) and SF during the inference (referred
to as max inference in their work). However, the distant supervision over all
answer occurrences damaged the performance in their work, and they found it
useful to use only 1 answer per paragraph. In our case however, we only used
labels matching single ground truth, no aliases are provided. Also we retrieve
our own set via retrieval model that considers BSMM paragraph representations
over golden paragraphs, not via TF-IDF over document’s texts splitted into
paragraphs. Finally, our TriviaQA is slightly different as we use MRQA version
of the dataset.

##  8 Conclusion

The paper looks back at the last years of progress in QA and finds two
understudied phenomena which relate to common beliefs that do not necessarily
hold true. Two new approaches in the paper show the new directions that can be
applied in order to improve statistical EQA systems, without using any
additional data. Firstly, we experimentally demonstrated that introducing the
compound objective as a new objective for EQA improves results of state-of-
the-art systems. Secondly, we showed that the distant semi-supervised
objective, known from open-domain EQA, is beneficial towards performance of
closed-domain EQA systems too, without the need for additional data. Using the
proposed approaches, we were able to reach significant improvements through
wide spectrum of datasets, including +2.87 EM on Adversarial SQuAD and +2.07
EM on NaturalQuestions. In addition, we also identified the reason for
performance decrease with compound objective on SQuADv2.0 – no-answer
classifier trained within the same model performs worse – and we leave the
solution for this deficiency for future work.

## References

  * Chen et al. (2017) Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. 2017.  Reading wikipedia to answer open-domain questions.  _arXiv preprint arXiv:1704.00051_.
  * Cheng et al. (2020) Hao Cheng, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2020.  Probabilistic assumptions matter: Improved models for distantly-supervised document-level question answering.  _arXiv preprint arXiv:2005.01898_.
  * Clark and Gardner (2017) Christopher Clark and Matt Gardner. 2017.  Simple and effective multi-paragraph reading comprehension.  _arXiv preprint arXiv:1710.10723_.
  * Clark et al. (2020) Kevin Clark, Minh-Thang Luong, Quoc V Le, and Christopher D Manning. 2020.  Electra: Pre-training text encoders as discriminators rather than generators.  _arXiv preprint arXiv:2003.10555_.
  * Das et al. (2019) Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, and Andrew McCallum. 2019.  Multi-step retriever-reader interaction for scalable open-domain question answering.  _arXiv preprint arXiv:1905.05733_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186.
  * Dhingra et al. (2018) Bhuwan Dhingra, Danish Pruthi, and Dheeraj Rajagopal. 2018.  Simple and effective semi-supervised question answering.  _arXiv preprint arXiv:1804.00720_.
  * Dror et al. (2018) Rotem Dror, Gili Baumer, Segev Shlomov, and Roi Reichart. 2018.  The hitchhiker’s guide to testing statistical significance in natural language processing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1383–1392.
  * Fisch et al. (2019) Adam Fisch, Alon Talmor, Robin Jia, Minjoon Seo, Eunsol Choi, and Danqi Chen. 2019\.  Mrqa 2019 shared task: Evaluating generalization in reading comprehension.  _arXiv preprint arXiv:1910.09753_.
  * Jia and Liang (2017) Robin Jia and Percy Liang. 2017.  Adversarial examples for evaluating reading comprehension systems.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2021–2031.
  * Joshi et al. (2017) Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. 2017.  Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1601–1611.
  * Kesiraju et al. (2019) Santosh Kesiraju, Oldřich Plchot, Lukaš Burget, and Suryakanth V Gangashetty. 2019.  Learning document embeddings along with their uncertainties.  _arXiv preprint arXiv:1908.07599_.
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. 2019.  Natural questions: A benchmark for question answering research.  _Transactions of the Association for Computational Linguistics_ , 7:453–466.
  * Lan et al. (2019) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2019.  Albert: A lite bert for self-supervised learning of language representations.  _arXiv preprint arXiv:1909.11942_.
  * Lee et al. (2016) Kenton Lee, Shimi Salant, Tom Kwiatkowski, Ankur Parikh, Dipanjan Das, and Jonathan Berant. 2016.  Learning recurrent span representations for extractive question answering.  _arXiv preprint arXiv:1611.01436_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Loshchilov and Hutter (2017) Ilya Loshchilov and Frank Hutter. 2017.  Fixing weight decay regularization in adam.  _arXiv preprint arXiv:1711.05101_.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems_ , pages 8024–8035.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543.
  * Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang. 2018.  Know what you don’t know: Unanswerable questions for squad.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 784–789.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  Squad: 100,000+ questions for machine comprehension of text.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2383–2392.
  * Seo et al. (2016) Minjoon Seo, Aniruddha Kembhavi, Ali Farhadi, and Hannaneh Hajishirzi. 2016.  Bidirectional attention flow for machine comprehension.  _arXiv preprint arXiv:1611.01603_.
  * Stephens (1974) Michael A Stephens. 1974.  Edf statistics for goodness of fit and some comparisons.  _Journal of the American statistical Association_ , 69(347):730–737.
  * Trischler et al. (2017) Adam Trischler, Tong Wang, Xingdi Yuan, Justin Harris, Alessandro Sordoni, Philip Bachman, and Kaheer Suleman. 2017.  Newsqa: A machine comprehension dataset.  In _Proceedings of the 2nd Workshop on Representation Learning for NLP_ , pages 191–200.
  * Vinyals et al. (2015) Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015.  Pointer networks.  In _Advances in Neural Information Processing Systems_ , pages 2692–2700.
  * Wang and Jiang (2016) Shuohang Wang and Jing Jiang. 2016.  Machine comprehension using match-lstm and answer pointer.  _arXiv preprint arXiv:1608.07905_.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _ArXiv_ , pages arXiv–1910.
  * Xiong et al. (2016) Caiming Xiong, Victor Zhong, and Richard Socher. 2016.  Dynamic coattention networks for question answering.  _arXiv preprint arXiv:1611.01604_.
  * Xiong et al. (2017) Caiming Xiong, Victor Zhong, and Richard Socher. 2017.  Dcn+: Mixed objective and deep residual coattention for question answering.  _arXiv preprint arXiv:1711.00106_.
  * Yang et al. (2019) Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. 2019.  Xlnet: Generalized autoregressive pretraining for language understanding.  In _Advances in neural information processing systems_ , pages 5753–5763.
  * Yu et al. (2018) Adams Wei Yu, David Dohan, Minh-Thang Luong, Rui Zhao, Kai Chen, Mohammad Norouzi, and Quoc V Le. 2018.  Qanet: Combining local convolution with global self-attention for reading comprehension.  _arXiv preprint arXiv:1804.09541_.

##  Appendix A Examples of answer span distribution

This section provides a deeper insight towards most probable elements of
answer span PMF.

Question: What was the first point of the Reformation?
Passage: Luther’s rediscovery of "Christ and His salvation" was the first of
two points that became the foundation for the Reformation. His railing against
the sale of indulgences was based on it.
Ground Truth: Christ and His salvation

Confidence |  Predictions from BERT-base
---|---
59.7 |  Christ and His salvation"
35.4 |  Christ and His salvation
2.3 |  Christ
1.3 |  "Christ and His salvation"
0.8 |  "Christ and His salvation
0.1 |  Christ and His salvation" was
0.1 |  "Christ

Figure 3: Example of answer span distribution from model trained via
independent objective.

Confidence |  Predictions from BERT-base-compound
---|---
71.8 |  Christ and His salvation
10.9 |  "Christ and His salvation"
4.7 |  Christ and His salvation"
4.6 |  Luther’s rediscovery of "Christ and His salvation
3.1 |  "Christ and His salvation
1.2 |  Luther’s rediscovery of "Christ and His salvation"
0.8 |  Luther’s rediscovery

Figure 4: Example of answer span distribution from model trained via compound
objective.

Question: How many species of bird and mammals are there in the Amazon region?
Passage: The region is home to about 2.5 million insect species, tens of
thousands of plants, and some 2,000 birds and mammals. To date, at least
40,000 plant species, 2,200 fishes, 1,294 birds, 427 mammals, 428 amphibians,
and 378 reptiles have been scientifically classified in the region. One in
five of all the bird species in the world live in the rainforests of the
Amazon, and one in five of the fish species live in Amazonian rivers and
streams. Scientists have described between 96,660 and 128,843 invertebrate
species in Brazil alone.
Ground Truth: 2,000

Confidence |  Predictions from BERT-base
---|---
37.0 |  2,000 birds and mammals. To date, at least 40,000 plant species, 2,200 fishes, 1,294 birds, 427
34.6 |  427
27.7 |  2,000
0.2 |  1,294 birds, 427
0.2 |  427 mammals
0.1 |  2,000 birds
0.1 |  2,000 birds and mammals

Figure 5: Example of answer span distribution from model trained via
independent objective.

Confidence |  Predictions from BERT-base-compound
---|---
71.7 |  427
21.5 |  2,000
5.1 |  2,000 birds and mammals. To date, at least 40,000 plant species, 2,200 fishes, 1,294 birds, 427
0.8 |  some 2,000
0.2 |  427 mammals
0.1 |  1,294 birds, 427
0.1 |  2,000 birds and mammals. To date, at least 40,000 plant species, 2,200 fishes, 1,294

Figure 6: Example of answer span distribution from model trained via compound
objective.

##  Appendix B Exploration of similarity functions

We have experimented with 4 types of similarity functions in our experiments.
For each start representation $\boldsymbol{h_{s}}\in\mathbb{R}^{d}$ and end
representation $\boldsymbol{h_{e}}\in\mathbb{R}^{d}$, both column vectors from
the matrix of boundary vectors $\boldsymbol{H}_{s}$,
$\boldsymbol{H}_{e}\in\mathbb{R}^{d\times L}$ respectively. Note that $d$ here
is model specific dimension and $L$ is passage length. The similarity
functions above these representations are defined as:

  * •

A dot product:

$f_{dot}(\boldsymbol{h_{s}},\boldsymbol{h_{e}})=\boldsymbol{h_{s}}^{\top}\boldsymbol{h_{e}}$
(8)

  * •

A weighted dot product:

$f_{wdot}(\boldsymbol{h_{s}},\boldsymbol{h_{e}})=\boldsymbol{w}^{\top}[\boldsymbol{h_{s}}\circ\boldsymbol{h_{e}}]$
(9)

  * •

An additive similarity:

$f_{add}(\boldsymbol{h_{s}},\boldsymbol{h_{e}})=\boldsymbol{w}^{\top}[\boldsymbol{h_{s}};\boldsymbol{h_{e}}]$
(10)

  * •

An additive-similarity combined with weighted product:

$f_{add-
wdot}(\boldsymbol{h_{s}},\boldsymbol{h_{e}})=\boldsymbol{w}^{\top}[\boldsymbol{h_{s}};\boldsymbol{h_{e}};\boldsymbol{h_{s}}\circ\boldsymbol{h_{e}}]$
(11)

Our results are presented in Table 6.

| BidAF-IJ | BERT-IJ
---|---|---
$f_{dot}$ | 64.4 | 74.35 | 81.83 | 88.52
$f_{add}$ | 66.28 | 75.25 | 81.52 | 88.47
$f_{wdot}$ | 65.73 | 75.03 | 81.35 | 88.29
$f_{add-wdot}$ | 66.02 | 75.54 | 81.45 | 88.44
Table 6: A comparison of similarity functions in the models trained via
compound objective.

##  Appendix C Conditional objective

Some of recent LRMs also predict start and end indices of a span jointly. For
comparison with our joint objective, we reimplemented the conditional
objective used in ALBERT Lan et al. (2019).

First, the probabilities $\boldsymbol{P}(a_{s})$ for the start position are
computed in a same manner as for the independent objective – by applying a
linear transformation layer on top of representations
$\boldsymbol{H}\in\mathbb{R}^{d\times L}$ from the last layer of the LRM,
where $d$ is the model dimension an $L$ denotes the input sequence length.

$\boldsymbol{P}(a_{s})=\boldsymbol{w}_{s}^{\top}\boldsymbol{H}+\boldsymbol{b_{s}}$
(12)

During the validation, top $k$ ($k=10$ in our experiments) start positions $i$
are selected from these probabilities, while in the training phase, we apply
teacher forcing by only selecting the correct start position. Representations
$\boldsymbol{H}_{i}$ from the last layer of the LRM corresponding to the
selected positions are concatenated with representations corresponding to all
the other positions $k={0..L}$ into matrix $\boldsymbol{C}$.

$\boldsymbol{C}=\begin{bmatrix}\text{---}&[\boldsymbol{h_{0}};\boldsymbol{h_{i}}]&\text{---}\\\
\text{---}&[\boldsymbol{h_{1}};\boldsymbol{h_{i}}]&\text{---}\\\
\lx@intercol\hfil$\vdots$\hfil\lx@intercol\\\
\text{---}&[\boldsymbol{h_{n}};\boldsymbol{h_{i}}]&\text{---}\end{bmatrix}$
(13)

Subsequently, a layer with $\tanh$ activation is applied on this matrix
$\boldsymbol{C}$, followed by a linear transformation to obtain the end
probabilities:

$\boldsymbol{P}(a_{e}|a_{s}=i)=\boldsymbol{w}_{c}^{\top}\tanh{(\boldsymbol{W}\boldsymbol{C}+\boldsymbol{b})}$
(14)

For each start position we again select top k end positions, to obtain
$k^{2}$-best list of answer spans. In contrast to the official ALBERT
implementation, we omitted a layer normalization after tanh layer.


calculation. Then we need only consider the primary and secondary masses, and
draw them from the previously defined physical priors to compute $F_{\gamma}$.

Finally, with the weightings $w_{\rm i}$ accounting for the physical prior
distributions and $F_{\gamma}$ normalising each event per unit star forming
mass, we have a weighting which we can apply to each simulated event. This
weighting simultaneously accounts for deviations in our sample distribution
from an assumed physical prior for the birth distribution of systems and
normalising each event per unit star forming mass:

$w_{\rm sfm}=w_{\rm i}\cdot F_{\gamma}$ (16)

With this new weighting, we can construct delay-time distributions such as
those shown in Figure 12, where the height of each bin represents the number
of events per unit star forming mass at time 0 for that time bin. These
normalised delay-time distributions can then be used to approximate the event
rates in astrophysical environments such as galaxies or star clusters,
provided an appropriate star formation history is known. In this work we
present galactic rates using delay-time distributions for solar metallicity
models only, thus galactic chemical evolution is not accounted for.

To account for the evolution of metallicity over cosmic time, multiple delay-
time distributions for different metallicities should be computed in the
manner previously described, and then combined with an age-metallicity
relation for the desired galaxy or cluster so that the correct metallicity
delay-time distribution is employed for the appropriate period of star
formation. The computation of such a set of delay-time distributions is beyond
the scope of the current work, and it should be noted that observed age-
metallicity relations have enormous scatter (Casagrande et al., 2011; Hayden
et al., 2015).

##  Appendix B Critical ignition mass distributions

(a) H novae: white dwarf mass vs critical ignition mass

(b) H novae: accretion rate vs critical ignition mass

(c) He novae∗: white dwarf mass vs critical ignition mass

(d) He novae∗: accretion rate vs critical ignition mass

  * a

Including H donors

Figure 16: Distributions of the critical ignition mass against the white dwarf
mass and the accretion rate, all sampled at the time of each nova eruption.
The ignition mass is found to depend more strongly on the white dwarf mass
than the accretion rate, particularly as the white dwarf mass approaches
$M_{\rm Ch}$. "∗": Including H donors.

The critical ignition mass ($M_{\rm ig}$) determines how much material must be
accreted prior to nova eruption, directly affecting the rate of novae. In our
model we compute $M_{\rm ig}$ as a function of the WD mass and mass accretion
rate (see Section 2, also Figure 2). The computed distributions of $M_{\rm
ig}$ versus $M_{\rm WD}$ and $\dot{M}$ are shown in Figure 16.

As previously discussed, the expectation is that increasing $M_{\rm WD}$ leads
to lower critical ignition masses, driven by increased compressional heating
of the accreted layer. Likewise, increasing $\dot{M}$ should also lead to
lower $M_{\rm ig}$ due to the higher rates of gravothermal energy transfer
causing increased heating at the base of the layer.

It is observed in Figures 16(a) and 16(b) that, for H novae, $M_{\rm ig}$ is
extremely sensitive to $M_{\rm WD}$, while being only weakly sensitive to
$\dot{M}$. This is quite different to the distribution of $M_{\rm ig}$ for He
novae. The He novae distribution is more strongly correlated with $M_{\rm WD}$
than with $\dot{M}$, but there remains a significant correlation between
$\dot{M}$ and $M_{\rm ig}$ that is only barely discernible for H novae.

The reason for this discrepancy is the more extreme conditions required for
the nuclear burning of He compared to H. This results in He novae being more
reliant on the gravothermal energy released from the accreted material, the
contribution of which scales directly with the accretion rate.

The distribution of critical ignition masses for H novae varies substantially
from that of He novae, as expected due to the much greater difficulty of
initiating He fusion. He novae are found to have $M_{\rm ig}$ ranging from
$\approx 10^{-5}-0.1$ M⊙777Double-detonation type Ia supernovae are neglected
here. It is possible that the ‘He novae’ with the most massive He shells may
manifest as such., but most He novae occur with critical ignition masses
between $\approx 10^{-5}-10^{-3}$ M⊙. This is very different to the case for H
novae, where the distribution is spread out more evenly throughout between
$\approx 10^{-7}\ \mathrm{to}\ 3\times 10^{-4}$ M⊙.

##  Appendix C Accretion efficiency distributions

(a) H Novae

(b) H Novae

(c) He Novae, including H donors

Figure 17: Accretion efficiency distribution, coloured by the accretor and
donor stellar types. The highest accretion efficiencies for H novae are
obtained only at the highest accretion rates, driven by giant donor stars
overflowing their Roche lobes.

(a) White dwarf mass vs accretion efficiency, including H donors

(b) Mass accretion rate vs accretion efficiency, including H donors

Figure 18: Distributions of accretion efficiency for He novae against the
white dwarf mass and accretion rate. The accretion efficiency is only weakly
dependent on the white dwarf mass, but strongly dependent on the mass
accretion rate. The large peak around perfect efficiency is driven by the huge
number of systems which experience extremely high accretion rates shortly
before merging with their He main sequence donor star.

The range of permissible $\eta$ according to our fits to data from Wu et al.
(2017) and Wang (2018) is shown in Figure 3. The actual distribution of $\eta$
according to our simulations is shown in Figure 17. Both H and He novae have
interesting features in their distributions, the discussion of which provides
useful insight into the physics of these events.

First addressing H novae, it can be seen that there are two peaks around
$\eta\approx 0.1$ and $\eta\approx 0.2$, with a significant tail up to
$\eta\approx 0.6$. Interestingly, while the distribution of nova events from
C/O WDs are firmly centered around the peak at $\eta\approx 0.2$, O/Ne WD
accretors are responsible for both the lower $\eta\approx 0.1$ peak and the
high $\eta$ tail. The distinction between the two populations of O/Ne WD
systems lies in the donor stars. The O/Ne WD systems responsible for the high
efficiency tail are those accreting rapidly ($\dot{M}$$\gtrapprox 10^{-7}$
M${}_{\odot}\,\textrm{yr}^{-1}$ from TPAGB donor stars, while those that form
the peak around $\eta\approx 0.1$ are accreting more slowly
($\dot{M}$$\gtrapprox 10^{-8}$ M${}_{\odot}\,\textrm{yr}^{-1}$), primarily
from FGB donor stars.

The distribution of He nova efficiencies reveals a distribution peaking around
$\eta\approx 0.25$, similar to H novae, which drops quickly by $\eta\approx
0.15$ and decays more gradually to $\eta\approx 0.55$, before a large,
dominant peak at $\eta=1$. The distribution shows no significant variation
between C/O and O/Ne accretors.

The most interesting feature in the He nova distribution is the dominant peak
at $\eta=1$. The reason for its presence is partially revealed in Figure 18,
which shows that this peak is primarily driven by events at the highest mass
accretion rates, but is relatively unconstrained in its distribution versus
$M_{\rm WD}$. The question becomes: why are there so many events at these
exceptionally high accretion rates in the first place? Many of these events
are at the limit of what is, in our model, considered the boundary between
stable and unstable surface He burning.

The answer lies in the final fates of the He-nova systems, the vast majority
of which merge with their donor star. As they inspiral, the rate of mass
transfer increases and these systems undergo multiple perfect efficiency
eruptions, driven by the substantial reduction in ignition mass caused by the
increased accretion rate (see Figure 16(d)).


H\sqrt{C^{\widecheck{\pi}_{r}^{(t)}}(\pi)}\left(2(HR_{\max})^{1/3}(\epsilon_{\rm
S}+3\epsilon_{\mathcal{F}})^{1/3}+\sqrt{8\epsilon_{\rm
S}+12\epsilon_{\mathcal{F}}+3\epsilon_{\mathcal{F},\mathcal{F}}}\right).$

Notice that the distribution shift coefficient is changed from $C^{\pi}(\pi)$
to $C^{\widecheck{\pi}_{r}^{(t)}}(\pi)$, as the policy specific Bellman
operator ${\mathcal{T}}$ is now induced by policy $\widecheck{\pi}_{r}^{(t)}$
rather than $\pi$. Taking the average over $t$ and applying the triangle
inequality give us

$\displaystyle\left|\frac{1}{T}\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\pi}\left[\widecheck{Q}^{(t)}_{h,r}-{\mathcal{T}}_{h,r}^{\widecheck{\pi}_{r}^{(t)}}\widecheck{Q}_{h+1,r}^{(t)}\right]\right|$
$\displaystyle\qquad\leq
H\left(\frac{1}{T}\sum_{t=1}^{T}\sqrt{C^{\widecheck{\pi}^{(t)}_{r}}({\pi})}\right)\left(2(HR_{\max})^{1/3}(\epsilon_{\rm
S}+3\epsilon_{\mathcal{F}})^{1/3}+\sqrt{8\epsilon_{\rm
S}+12\epsilon_{\mathcal{F}}+3\epsilon_{\mathcal{F},\mathcal{F}}}\right).$

Combining the bounds, we have

$\displaystyle
V_{1}^{\pi}(s_{0};r)-\frac{1}{T}\sum_{t=1}^{T}\widecheck{Q}_{1,r}^{(t)}(s_{0},\widecheck{\pi}^{(t)}_{1,r})\leq
2H^{2}R_{\max}\sqrt{\frac{2\log|\mathcal{A}|}{T}}$
$\displaystyle\qquad+H\left(\frac{1}{T}\sum_{t=1}^{T}\sqrt{C^{\widecheck{\pi}^{(t)}_{r}}({\pi})}\right)\left(2(HR_{\max})^{1/3}(\epsilon_{\rm
S}+3\epsilon_{\mathcal{F}})^{1/3}+\sqrt{8\epsilon_{\rm
S}+12\epsilon_{\mathcal{F}}+3\epsilon_{\mathcal{F},\mathcal{F}}}\right),$

which completes the proof. ∎

##  Appendix F Concentration Analysis

In this section, we prove the concentration lemmas used in Section D.

###  F.1 Proof of Lemma D.2

We start by including a minor adaptation of a useful result from Györfi et al.
(2002).

######  Theorem F.1 (Adaptation of Theorem 11.6 from Györfi et al. (2002)).

Let $B\geq 1$ and let $\mathcal{G}$ be a class of functions
$g:\mathbb{R}^{d}\to[0,B]$. Let $Z_{1},Z_{2},\ldots,Z_{K}$ be i.i.d.
$\mathbb{R}^{d}$-valued random variables. Assume $\alpha>0$, $0<\epsilon<1$,
and $K\geq 1$. Then

$\Pr\left(\sup_{g\in\mathcal{G}}\frac{\frac{1}{K}\sum_{j=1}^{K}g(Z_{j})-\mathbb{E}[Z_{j}]}{\alpha+\frac{1}{K}\sum_{j=1}^{K}g(Z_{j})+\mathbb{E}[Z_{j}]}>\epsilon\right)\leq
4\mathcal{N}_{\infty}\left(\frac{\alpha\epsilon}{5},\mathcal{G}\right)\exp\left(-\frac{3\epsilon^{2}\alpha
K}{40B}\right).$

###### Proof.

By Theorem 11.6 from Györfi et al. (2002), we know that

$\displaystyle\Pr\left(\sup_{g\in\mathcal{G}}\frac{\frac{1}{K}\sum_{j=1}^{K}g(Z_{j})-\mathbb{E}[Z_{j}]}{\alpha+\frac{1}{K}\sum_{j=1}^{K}g(Z_{j})+\mathbb{E}[Z_{j}]}>\epsilon\right)\leq
4\mathbb{E}\left[\mathcal{N}_{1}\left(\frac{\alpha\epsilon}{5},\mathcal{G},\\{Z_{j}\\}_{j=1}^{K}\right)\right]\exp\left(-\frac{3\epsilon^{2}\alpha
K}{40B}\right),$

where
$\mathcal{N}_{1}\left(\frac{\alpha\epsilon}{5},\mathcal{G},\\{Z_{j}\\}_{j=1}^{K}\right)$
is the cardinality of the smallest set of functions $\\{g^{l}\\}_{l=1}^{L}$
such that for all $g\in\mathcal{G}$ there exists some $l\in[L]$ where

$\frac{1}{K}\sum_{j=1}^{K}\left|g(Z_{j})-g^{l}(Z_{j})\right|\leq\frac{\alpha\epsilon}{5}.$

See Section 11.4 from Györfi et al. (2002) for a detailed proof of the
statement above. We then show that for any $\\{Z_{j}\\}_{j=1}^{K}$,
$\mathcal{N}_{1}\left(\frac{\alpha\epsilon}{5},\mathcal{G},\\{Z_{j}\\}_{j=1}^{K}\right)\leq\mathcal{N}_{\infty}\left(\frac{\alpha\epsilon}{5},\mathcal{G}\right)$.
Let $\\{\widetilde{g}^{l}\\}_{l=1}^{L}$ be an
$\frac{\alpha\epsilon}{5}$-covering of $\mathcal{G}$ with respect to the
$\ell_{\infty}$-norm. We then know that for any $g\in\mathcal{G}$, there
exists some $l\in[L]$ such that

$\displaystyle\frac{1}{K}\sum_{j=1}^{K}|g(Z_{j})-\tilde{g}^{l}(Z_{j})|\leq\frac{1}{K}\sum_{j=1}^{K}\frac{\alpha\epsilon}{5}=\frac{\alpha\epsilon}{5}.$

Therefore $\\{\widetilde{g}^{l}\\}_{l=1}^{L}$ satisfies the requirement above,
concluding our proof. ∎

Let $h\in[H],r\in\tilde{\mathcal{R}}$ be arbitrary and fixed. First, we show

$\displaystyle\Pr\Bigl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\mathbb{E}_{\mu_{h}}\left[\|f_{h}-{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}\|^{2}\right]-\mathcal{L}_{h,r}(f_{h},f^{\prime}_{h+1},\pi;\mathcal{D})+$
$\displaystyle\hskip
120.00018pt\mathcal{L}_{h,r}({\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1},f^{\prime}_{h+1},\pi;\mathcal{D})\geq\epsilon\bigl{(}\alpha+\beta+\mathbb{E}_{\mu_{h}}\left[\|f_{h}-{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}\|^{2}\right]\bigr{)}\Bigr{)}$
$\displaystyle\qquad\leq
14\left(\mathcal{N}_{\infty}\left(\frac{\epsilon\beta}{140HR_{\max}},\mathcal{F}\right)\right)^{2}\mathcal{N}_{\infty,1}\left(\frac{\epsilon\beta}{140H^{2}R^{2}_{\mathrm{max}}},\Pi\right)\exp\left(-\frac{\epsilon^{2}(1-\epsilon)\alpha
K}{214(1+\epsilon)H^{4}R_{\max}^{4}}\right).$

for all $\alpha,\beta>0$, $0<\epsilon\leq 1/2$.

Let $Z$ be the random vector $(s_{h},a_{h},r_{h}(s_{h},a_{h}),s_{h+1})$ where
$(s_{h},a_{h},s_{h+1})\sim\mu_{h}$. Let $Z_{j}$ be its realization for any
$j\in[K]$ drawn independently from $\mathcal{D}_{h}$. For any
$f,f^{\prime}\in\mathcal{F}$, and $\pi\in\Pi$, we further define the random
variable

$g_{f,f^{\prime}}^{\pi}(Z)=(f_{h}(s_{h},a_{h})-r_{h}-f^{\prime}_{h+1}(s_{h+1},\pi_{h+1}))^{2}-({\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}(s_{h},a_{h})-r_{h}-f^{\prime}_{h+1}(s_{h+1},\pi_{h+1}))^{2},$

and $g_{f,f^{\prime}}^{\pi}(Z_{j})$ its empirical counterpart evaluated on
$Z$’s realization, $Z_{j}$. We begin by showing some basic properties of the
random variable $g_{f,f^{\prime}}^{\pi}(Z)$. Recall that by definition of the
Bellman evaluation operator

${\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}(s_{h},a_{h})=\mathbb{E}_{\mathcal{P}}\left[r_{h}+f^{\prime}_{h+1}(s_{h+1},\pi_{h+1})|s_{h},a_{h}\right].$
(F.1)

Since
${\mathcal{T}}_{h,r}^{\pi}f_{h+1}(s_{h},a_{h})=\mathbb{E}_{\mu_{h}}\left[r_{h}+f^{\prime}_{h+1}(s_{h+1},\pi_{h+1})|s_{h},a_{h}\right]$,
by the law of total probability

$\displaystyle\mathbb{E}_{Z\sim\mu_{h}}$
$\displaystyle[g_{f,f^{\prime}}^{\pi}(Z)]$
$\displaystyle={\mathbb{E}_{s_{h},a_{h}\sim\mu_{h}}}\Big{[}{\mathbb{E}_{s_{h+1}\sim\mu_{h}|s_{h},a_{h}}}[(f_{h}(s_{h},a_{h})-r_{h}-f^{\prime}_{h+1}(s_{h+1},\pi_{h+1}))^{2}-$
$\displaystyle\hskip
90.00014pt({\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}(s_{h},a_{h})-r_{h}-f^{\prime}_{h+1}(s_{h+1},\pi_{h+1}))^{2}|s_{h},a_{h}]\Big{]}$
$\displaystyle={\mathbb{E}_{\mu_{h}}}\Big{[}{\mathbb{E}}_{s_{h+1}\sim\mu_{h}|s_{h},a_{h}}[(f_{h}(s_{h},a_{h})+{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}(s_{h},a_{h})-2(r_{h}+f^{\prime}_{h+1}(s_{h+1},\pi_{h+1})))\times$
$\displaystyle\hskip
210.00032pt(f_{h}(s_{h},a_{h})-{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}(s_{h},a_{h}))|s_{h},a_{h}]\Big{]}$
$\displaystyle=\mathbb{E}_{\mu_{h}}\left[\|f_{h}(s_{h},a_{h})-{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}(s_{h},a_{h})\|^{2}\right].$

Additionally, recalling that $r_{h}\in[-R_{\max},R_{\max}]$,
$f^{\prime}_{h+1}\in[-(H-h)R_{\max},(H-h)R_{\max}]$,
$f_{h}\in[-(H-h+1)R_{\max},(H-h+1)R_{\max}]$, we know that
$g_{f,f^{\prime}}^{\pi}(Z)\in[-16H^{2}R_{\max}^{2},16H^{2}R_{\max}^{2}]$.
Lastly, notice that

$\begin{split}\operatorname{{\rm
Var}}(g_{f,f^{\prime}}^{\pi}(Z))&\leq\mathbb{E}[(g_{f,f^{\prime}}^{\pi}(Z))^{2}]\\\
&={\mathbb{E}}\Big{[}{\mathbb{E}}[(f_{h}(s_{h},a_{h})+{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}(s_{h},a_{h})-2(r_{h}+f^{\prime}_{h+1}(s_{h+1},\pi_{h+1})))^{2}\times\\\
&\hskip
160.00024pt(f_{h}(s_{h},a_{h})-{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}(s_{h},a_{h}))^{2}|s_{h},a_{h}]\Big{]}\\\
&\leq\mathbb{E}[16H^{2}R_{\max}^{2}(f_{h}(s_{h},a_{h})-{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}(s_{h},a_{h}))^{2}]=16H^{2}R_{\max}^{2}\mathbb{E}[g_{f,f^{\prime}}^{\pi}(Z)],\end{split}$
(F.2)

where for the last inequality we noticed that
$f_{h}(s_{h},a_{h})+{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}(s_{h},a_{h})-2(r_{h}+f^{\prime}_{h+1}(s_{h+1},\pi_{h+1}))$
is bounded by $[-4HR_{\max},4HR_{\max}]$.

Our ensuing proof largely follows the structure of Section 11.5 of Györfi et
al. (2002) and we reproduce the proof below for completeness. Let
$\alpha,\beta>0$ and $0<\epsilon\leq\frac{1}{2}$ be arbitrary and fixed
constants. We now proceed with the proof.

Symmetrization by Ghost Sample. Consider some
$(f_{n},f^{\prime}_{n},\pi_{n})\in\mathcal{F}\times\mathcal{F}\times\Pi$
depending on $\\{Z_{j}\\}_{j=1}^{K}$ such that

$\mathbb{E}[g_{f_{n},f^{\prime}_{n}}^{\pi_{n}}(Z)|\\{Z_{j}\\}_{j=1}^{K}]-\frac{1}{K}\sum_{j=1}^{K}g_{f_{n},f^{\prime}_{n}}^{\pi_{n}}(Z_{j})\geq\epsilon(\alpha+\beta+\mathbb{E}[g_{f_{n},f^{\prime}_{n}}^{\pi_{n}}(Z)|\\{Z_{j}\\}_{\tau=1}^{K}]),$

if such $(f_{n},f^{\prime}_{n},\pi_{n})$ exists. If not, choose some arbitrary
$(f_{n},f^{\prime}_{n},\pi_{n})$. As a shorthand notation, let
$g_{n}=g_{f_{n},f^{\prime}_{n}}^{\pi_{n}}$. Finally, introduce ghost samples
$\\{Z_{j}^{\prime}\\}_{j=1}^{K}\sim\mu_{h}$, drawn i.i.d. from the same
distribution as $\\{Z_{j}\\}_{j=1}^{K}$. Recalling that the variance of
$g_{n}$ is bounded by $16\mathbb{E}[g_{n}(Z)]$, by Chebyshev’s inequality we
have

$\displaystyle\Pr\biggl{(}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]-\frac{1}{K}\sum_{j=1}^{K}g_{n}({Z_{j}^{\prime}})\geq\frac{\epsilon}{2}(\alpha+\beta)+\frac{\epsilon}{2}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]|\\{Z_{j}\\}_{j=1}^{K}\biggr{)}$
$\displaystyle\qquad\leq\frac{\operatorname{{\rm
Var}}(g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K})}{K(\frac{\epsilon}{2}(\alpha+\beta)+\frac{\epsilon}{2}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}])^{2}}$
$\displaystyle\qquad\leq\frac{16H^{2}R_{\max}^{2}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]}{K(\frac{\epsilon}{2}(\alpha+\beta)+\frac{\epsilon}{2}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}])^{2}}$
$\displaystyle\qquad\leq\frac{16H^{2}R_{\max}^{2}}{\epsilon^{2}(\alpha+\beta)K},$

where the last inequality comes from the fact that
$\frac{s_{0}}{(a+s_{0})^{2}}\leq\frac{1}{4a}$ for all $s_{0}\geq 0$ and $a>0$.
Thus, for all $K\geq\frac{128H^{2}R_{\max}^{2}}{\epsilon^{2}(\alpha+\beta)}$,

$\Pr\biggl{(}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]-\frac{1}{K}\sum_{j=1}^{K}g_{n}({Z^{\prime}}_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)+\frac{\epsilon}{2}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]|\\{Z_{j}\\}_{j=1}^{K}\biggr{)}\leq\frac{7}{8}.$

We then know that

$\displaystyle\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{i}^{\prime})-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)+\frac{\epsilon}{2}\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)]\biggr{)}$
$\displaystyle\ \
\geq\Pr\biggl{(}\frac{1}{K}\sum_{j=1}^{K}g_{n}(Z_{i}^{\prime})-\frac{1}{K}\sum_{j=1}^{K}g_{n}(Z_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)+\frac{\epsilon}{2}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]\biggr{)}$
$\displaystyle\ \
\geq\Pr\biggl{(}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]-\frac{1}{K}\sum_{j=1}^{K}g_{n}(Z_{j})\geq\epsilon(\alpha+\beta)+\epsilon\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]$
$\displaystyle\hskip
80.00012pt\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]-\frac{1}{K}\sum_{j=1}^{K}g_{n}(Z_{i}^{\prime})\geq\epsilon(\alpha+\beta)+\epsilon\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]\biggr{)}$
$\displaystyle\ \
=\mathbb{E}\Biggl{(}\operatorname{\mathds{1}}\biggl{\\{}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]-\frac{1}{K}\sum_{j=1}^{K}g_{n}(Z_{j})\geq\epsilon(\alpha+\beta)+\epsilon\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]\biggr{\\}}$
$\displaystyle\hskip
80.00012pt\Pr\biggl{(}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]-\frac{1}{K}\sum_{j=1}^{K}g_{n}(Z_{i}^{\prime})\geq\epsilon(\alpha+\beta)+\epsilon\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]\biggr{)}\Biggr{)}$
$\displaystyle\ \
\geq\frac{7}{8}\Pr\biggl{(}\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]-\frac{1}{K}\sum_{j=1}^{K}g_{n}(Z_{j})\geq\epsilon(\alpha+\beta)+\epsilon\mathbb{E}[g_{n}(Z)|\\{Z_{j}\\}_{j=1}^{K}]\biggr{)}$
$\displaystyle\ \ =\frac{7}{8}\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)]-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\epsilon(\alpha+\beta)+\epsilon\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)]\biggr{)}.$

In other words, for
$K\geq\frac{128H^{2}R_{\max}^{2}}{\epsilon^{2}(\alpha+\beta)}$,

$\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)]-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\epsilon(\alpha+\beta)+\epsilon\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)]\biggr{)}\\\
\leq\frac{8}{7}\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j}^{\prime})\\\
-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)+\frac{\epsilon}{2}\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)]\biggr{)}.$
(F.3)

Replacement of Expectation by Empirical Mean of Ghost Sample We begin by
noticing

$\begin{split}&\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{i}^{\prime})-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)+\frac{\epsilon}{2}\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)]\biggr{)}\\\
&\qquad\leq\Pr\biggl{(}\exists f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\\\
&\hskip
50.00008pt\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{i}^{\prime})-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)+\frac{\epsilon}{2}\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)],\\\
&\hskip
50.00008pt\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{i}^{\prime})-\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]\leq\\\
&\hskip
100.00015pt\epsilon\Bigl{(}\alpha+\beta+\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j})+\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]\Bigr{)},\\\
&\hskip
50.00008pt\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{i}^{\prime})-\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]\leq\\\
&\hskip
150.00023pt\epsilon\Bigl{(}\alpha+\beta+\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{i}^{\prime})+\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]\Bigr{)}\biggr{)}\\\
&\hskip 30.00005pt+2\Pr\left(\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j})-\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]}{\left(\alpha+\beta+\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j})+\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]\right)}\right).\end{split}$
(F.4)

Citing Theorem F.1, we may bound the second probability term on the right hand
side as

$\displaystyle\Pr\left(\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j})-\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]}{\left(\alpha+\beta+\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j})+\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]\right)}\right)$
$\displaystyle\qquad\leq
4\mathcal{N}_{\infty}\left(\frac{(\alpha+\beta)\epsilon}{5},\\{g_{f_{h},f^{\prime}_{h+1}}^{\pi}:f,f^{\prime}\in\mathcal{F},\pi\in\Pi\\}\right)\exp\left(-\frac{3\epsilon^{2}(\alpha+\beta)K}{40(16H^{2}R_{\max}^{2})}\right).$

For the first probability term, notice that the second event in the
conjunction implies

$(1+\epsilon)\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]\geq(1-\epsilon)\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j})-\epsilon(\alpha+\beta),$

which is equivalent to

$\frac{1}{32H^{2}R_{\max}^{2}}\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]\geq\frac{1-\epsilon}{32H^{2}R_{\max}^{2}(1+\epsilon)}\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j})-\epsilon\frac{(\alpha+\beta)}{32H^{2}R_{\max}^{2}(1+\epsilon)}.$

A similar bound may be obtained for the term involving $Z_{i}^{\prime}$.
Noticing that by equation (F.2), we have
$\mathbb{E}[g^{\pi}_{f_{h},f^{\prime}_{h+1}}(Z)]\geq\frac{1}{16H^{2}R_{\max}^{2}}\mathbb{E}[(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z)]$,
and we know the first probability term in (F.4) can be bounded by

$\displaystyle\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{i}^{\prime})-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)+$
$\displaystyle\hskip
60.00009pt\frac{\epsilon}{2}\Bigl{(}\frac{1-\epsilon}{32H^{2}R_{\max}^{2}(1+\epsilon)}\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j})-\frac{\epsilon(\alpha+\beta)}{32H^{2}R_{\max}^{2}}+$
$\displaystyle\hskip
120.00018pt\frac{1-\epsilon}{32H^{2}R_{\max}^{2}(1+\epsilon)}\frac{1}{K}\sum_{j=1}^{K}(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j})-\frac{\epsilon(\alpha+\beta)}{32H^{2}R_{\max}^{2}}\Bigr{)}\biggr{)}$
$\displaystyle\qquad=\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{i}^{\prime})-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)-$
$\displaystyle\hskip
60.00009pt\frac{\epsilon^{2}(\alpha+\beta)}{32H^{2}R_{\max}^{2}(1+\epsilon)}+\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)}\left(\frac{1}{K}\sum_{j=1}^{K}((g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z^{\prime}_{j})+(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j}))\right)\biggr{)}.$

Additional Randomization by Random Signs Let $\\{U_{j}\\}_{j=1}^{K}$ be i.i.d.
Rademacher random variables drawn independently from $\\{Z_{j}\\}_{j=1}^{K}$
and $\\{Z^{\prime}_{j}\\}_{j=1}^{K}$. Because $\\{Z_{j}\\}_{j=1}^{K}$ and
$\\{Z^{\prime}_{j}\\}_{j=1}^{K}$ are i.i.d., we know that

$\begin{split}&\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z^{\prime}_{j})-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)-\\\
&\hskip
60.00009pt\frac{\epsilon^{2}(\alpha+\beta)}{32H^{2}R_{\max}^{2}(1+\epsilon)}+\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)}\left(\frac{1}{K}\sum_{j=1}^{K}((g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{i}^{\prime})+(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j}))\right)\biggr{)}\\\
&\qquad=\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{1}{K}\sum_{j=1}^{K}U_{j}\bigl{(}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z^{\prime}_{j})-g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\bigr{)}\geq\frac{\epsilon}{2}(\alpha+\beta)-\\\
&\hskip
60.00009pt\frac{\epsilon^{2}(\alpha+\beta)}{32H^{2}R_{\max}^{2}(1+\epsilon)}+\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)}\left(\frac{1}{K}\sum_{j=1}^{K}((g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{i}^{\prime})+(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j}))\right)\biggr{)}\\\
&\qquad\leq 2\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{1}{K}\sum_{j=1}^{K}\left|U_{j}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\right|\geq\frac{\epsilon}{4}(\alpha+\beta)-\\\
&\hskip
60.00009pt\frac{\epsilon^{2}(\alpha+\beta)}{64H^{2}R_{\max}^{2}(1+\epsilon)}+\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)}\frac{1}{K}\sum_{j=1}^{K}((g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j}))\biggr{)}.\end{split}$
(F.5)

Conditioning and Covering We then condition the probability on
$\\{Z_{j}\\}_{j=1}^{K}$. Fix some $z_{1},\ldots,z_{K}$ and we consider instead

$\displaystyle\Pr\Biggl{\\{}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\left|\frac{1}{K}\sum_{j=1}^{K}U_{j}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(z_{j})\right|\geq$
$\displaystyle\hskip
80.00012pt\frac{\epsilon(\alpha+\beta)}{4}-\frac{\epsilon^{2}(\alpha+\beta)}{64H^{2}R_{\max}^{2}(1+\epsilon)}+\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)}\frac{1}{K}\sum_{j=1}^{K}(g_{f_{h},f^{\prime}_{h+1}}^{\pi})^{2}(z_{j})\Biggr{\\}}.$

Let $\delta>0$ and let $\mathcal{G}_{\delta}$ be an $\ell_{\infty}$
$\delta$-cover of
$\mathcal{G}_{\mathcal{F},\Pi}=\\{g_{f_{h},f^{\prime}_{h+1}}^{\pi}:f,f^{\prime}\in
F,\pi\in\Pi\\}$. Fix some
$(f,f^{\prime},\pi)\in\mathcal{F}\times\mathcal{F}\times\Pi$ and there exists
some $g\in\mathcal{G}_{\delta}$ such that
$\sup_{z}|g(z)-g_{f_{h},f^{\prime}_{h+1}}^{\pi}(z)|<\delta$. We then know that

$\displaystyle\left|\frac{1}{K}\sum_{j=1}^{K}U_{j}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(z_{j})\right|\leq\left|\frac{1}{K}\sum_{j=1}^{K}U_{j}g(z_{j})\right|+\frac{1}{K}\sum_{j=1}^{K}\left|g_{f_{h},f^{\prime}_{h+1}}^{\pi}(z_{j})-g(z_{j})\right|\leq\left|\frac{1}{K}\sum_{j=1}^{K}U_{j}g(z_{j})\right|+\delta$

and

$\displaystyle\frac{1}{K}\sum_{j=1}^{K}(g_{f_{h},f^{\prime}_{h+1}}^{\pi})^{2}(z_{j})$
$\displaystyle=\frac{1}{K}\sum_{j=1}^{K}g^{2}(z_{j})+\frac{1}{K}\sum_{j=1}^{K}((g_{f_{h},f^{\prime}_{h+1}}^{\pi})^{2}(z_{j})-g^{2}(z_{j}))$
$\displaystyle=\frac{1}{K}\sum_{j=1}^{K}g^{2}(z_{j})+\frac{1}{K}\sum_{j=1}^{K}(g_{f_{h},f^{\prime}_{h+1}}^{\pi}(z_{j})-g(z_{j}))(g_{f_{h},f^{\prime}_{h+1}}^{\pi}(z_{j})+g(z_{j}))$
$\displaystyle\geq\frac{1}{K}\sum_{j=1}^{K}g^{2}(z_{j})-8H^{2}R_{\max}^{2}\frac{1}{K}\sum_{j=1}^{K}|g_{f_{h},f^{\prime}_{h+1}}^{\pi}(z_{j})-g(z_{j})|$
$\displaystyle\geq\frac{1}{K}\sum_{j=1}^{K}g^{2}(z_{j})-8H^{2}R_{\max}^{2}\delta.$

Set $\delta=\frac{\beta\epsilon}{enumerate5}$. Notice that as $HR_{\max}\geq
1$, $0<\epsilon\leq\frac{1}{2}$, we have

$\displaystyle\frac{\epsilon\beta}{4}-\frac{\epsilon^{2}\beta}{64H^{2}R_{\max}^{2}(1+\epsilon)}-\delta-\delta\frac{\epsilon(1-\epsilon)}{8(1+\epsilon)}=\frac{\epsilon\beta}{2}-\frac{\epsilon^{2}\beta}{64H^{2}R_{\max}^{2}(1+\epsilon)}-\frac{\epsilon^{2}(1-\epsilon)\beta}{40(1+\epsilon)}\geq
0.$

Therefore we have

$\displaystyle\Pr\Biggl{\\{}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\left|\frac{1}{K}\sum_{j=1}^{K}U_{j}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(z_{j})\right|\geq$
$\displaystyle\hskip
80.00012pt\frac{\epsilon(\alpha+\beta)}{4}-\frac{\epsilon^{2}(\alpha+\beta)}{64H^{2}R_{\max}^{2}(1+\epsilon)}+\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)}\frac{1}{K}\sum_{j=1}^{K}(g_{f_{h},f^{\prime}_{h+1}}^{\pi})^{2}(z_{j})\Biggr{\\}}$
$\displaystyle\quad\leq|\mathcal{G}_{{\epsilon\beta}/{5}}|\max_{g\in\mathcal{G}_{{\epsilon\beta}/{5}}}\Pr\Biggl{\\{}\left|\frac{1}{K}\sum_{j=1}^{K}U_{j}g(z_{j})\right|\geq\frac{\epsilon\alpha}{4}-\frac{\epsilon^{2}\alpha}{64H^{2}R_{\max}^{2}(1+\epsilon)}+$
$\displaystyle\hskip
180.00027pt\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)}\frac{1}{K}\sum_{j=1}^{K}g^{2}(z_{j})\Biggr{\\}}.$
(F.6)

We then apply Bernstein’s inequality to bound

$\Pr\Biggl{\\{}\left|\frac{1}{K}\sum_{j=1}^{K}U_{j}g(z_{j})\right|\geq\frac{\epsilon\alpha}{4}-\frac{\epsilon^{2}\alpha}{64H^{2}R_{\max}^{2}(1+\epsilon)}+\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)}\frac{1}{K}\sum_{j=1}^{K}g^{2}(z_{j})\Biggr{\\}}$

for any $g\in\mathcal{G}_{\epsilon\beta/5}$. We begin by relating the variance
of $U_{j}g(z_{j})$ with $\frac{1}{K}\sum_{j=1}^{k}g^{2}(z_{j})$. Notice that
as $U_{j}$ is i.i.d. Rademacher,

$\frac{1}{K}\sum_{j=1}^{K}\operatorname{{\rm
Var}}(U_{j}g(z_{j}))=\frac{1}{K}\sum_{j=1}^{k}g^{2}(z_{j})\operatorname{{\rm
Var}}(U_{i})=\frac{1}{K}\sum_{j=1}^{k}g^{2}(z_{j}).$

Perform a simple change of variable and let $V_{j}=g(z_{j})U_{j}$. As
$g(z_{j})\in[-4H^{2}R_{\max}^{2},4H^{2}R_{\max}^{2}]$ for all $z_{j}$, we know
$|V_{j}|\leq 4H^{2}R_{\max}^{2}$. For convenience, further let
$A_{1}=\frac{\epsilon\alpha}{4}-\frac{\epsilon^{2}\alpha}{64H^{2}R_{\max}^{2}(1+\epsilon)},A_{2}=\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)},$
and $\sigma^{2}=\frac{1}{K}\sum_{j=1}^{K}\operatorname{{\rm
Var}}(U_{j}g(z_{j}))=\frac{1}{K}\sum_{j=1}^{k}g^{2}(z_{j})$. We then have for
any $g\in\mathcal{G}_{\epsilon\beta/5}$

$\displaystyle\Pr\Biggl{\\{}\left|\frac{1}{K}\sum_{j=1}^{K}U_{j}g(z_{j})\right|\geq\frac{\epsilon\alpha}{4}-\frac{\epsilon^{2}\alpha}{64H^{2}R_{\max}^{2}(1+\epsilon)}+\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)}\frac{1}{K}\sum_{j=1}^{K}g^{2}(z_{j})\Biggr{\\}}$
$\displaystyle\qquad=\Pr\left(\left|\frac{1}{K}\sum_{j=1}^{k}V_{j}\right|\geq
A_{1}+A_{2}\sigma^{2}\right)$ $\displaystyle\qquad\leq
2\exp\left(-\frac{K(A_{1}+A_{2}\sigma^{2})^{2}}{2\sigma^{2}+2(A_{1}+A_{2}\sigma^{2})\frac{8H^{2}R^{2}}{3}}\right)$
$\displaystyle\qquad=2\exp\left(-\frac{3KA_{2}}{16H^{2}R_{\max}^{2}}\frac{\left(\frac{A_{1}}{A_{2}}+\sigma^{2}\right)^{2}}{\frac{A_{1}}{A_{2}}+\left(1+\frac{3}{8H^{2}R_{\max}^{2}A_{2}}\right)\sigma^{2}}\right)$
$\displaystyle\qquad\leq 2\exp\left(-\frac{\epsilon^{2}(1-\epsilon)\alpha
K}{140H^{2}R_{\max}^{2}(1+\epsilon)}\right),$

where the last inequality follows a series of manipulations discussed in
greater detail in page 218 of Györfi et al. (2002) that we omit here for
brevity. Plugging the result back into equations (F.5) and (F.6) gives us

$\displaystyle\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z^{\prime}_{j})-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)-$
$\displaystyle\hskip
60.00009pt\frac{\epsilon^{2}(\alpha+\beta)}{32H^{2}R_{\max}^{2}(1+\epsilon)}+\frac{\epsilon(1-\epsilon)}{64H^{2}R_{\max}^{2}(1+\epsilon)}\left(\frac{1}{K}\sum_{j=1}^{K}((g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{i}^{\prime})+(g^{\pi}_{f_{h},f^{\prime}_{h+1}})^{2}(Z_{j}))\right)\biggr{)}$
$\displaystyle\qquad\leq
2\mathcal{N}_{\infty}\left(\frac{\epsilon\beta}{5},\\{g_{f_{h},f^{\prime}_{h+1}}^{\pi}:f,f^{\prime}\in
F,\pi\in\Pi\\}\right)\exp\left(-\frac{\epsilon^{2}(1-\epsilon)\alpha
K}{140H^{2}R_{\max}^{2}(1+\epsilon)}\right).$

Recalling equations (F.4) and (F.5), we have

$\displaystyle\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{i}^{\prime})-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\frac{\epsilon}{2}(\alpha+\beta)+\frac{\epsilon}{2}\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)]\biggr{)}$
$\displaystyle\qquad\leq
4\mathcal{N}_{\infty}\left(\frac{\epsilon\beta}{5},\\{g_{f_{h},f^{\prime}_{h+1}}^{\pi}:f,f^{\prime}\in
F,\pi\in\Pi\\}\right)\exp\left(-\frac{\epsilon^{2}(1-\epsilon)\alpha
K}{140H^{2}R_{\max}^{2}(1+\epsilon)}\right)$ $\displaystyle\hskip
30.00005pt+8\mathcal{N}_{\infty}\left(\frac{(\alpha+\beta)\epsilon}{5},\\{g_{f_{h},f^{\prime}_{h+1}}^{\pi}:f,f^{\prime}\in\mathcal{F},\pi\in\Pi\\}\right)\exp\left(-\frac{3\epsilon^{2}(\alpha+\beta)K}{640H^{2}R_{\max}^{2}}\right).$

Plugging the result back into equation (F.3) and we finally know for
$K\geq\frac{128H^{2}R_{\max}^{2}}{\epsilon^{2}(\alpha+\beta)}$,

$\displaystyle\Pr\biggl{(}\exists
f,f^{\prime}\in\mathcal{F},\pi\in\Pi:\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)]-\frac{1}{K}\sum_{j=1}^{K}g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z_{j})\geq\epsilon(\alpha+\beta)+\epsilon\mathbb{E}[g_{f_{h},f^{\prime}_{h+1}}^{\pi}(Z)]\biggr{)}$
$\displaystyle\qquad\leq\frac{32}{7}\mathcal{N}_{\infty}\left(\frac{\epsilon\beta}{5},\\{g_{f_{h},f^{\prime}_{h+1}}^{\pi}:f,f^{\prime}\in
F,\pi\in\Pi\\}\right)\exp\left(-\frac{\epsilon^{2}(1-\epsilon)\alpha
K}{140H^{2}R_{\max}^{2}(1+\epsilon)}\right)$ $\displaystyle\hskip
30.00005pt+\frac{64}{7}\mathcal{N}_{\infty}\left(\frac{(\alpha+\beta)\epsilon}{5},\\{g_{f_{h},f^{\prime}_{h+1}}^{\pi}:f,f^{\prime}\in\mathcal{F},\pi\in\Pi\\}\right)\exp\left(-\frac{3\epsilon^{2}(\alpha+\beta)K}{640H^{2}R_{\max}^{2}}\right)$
$\displaystyle\qquad\leq
14\mathcal{N}_{\infty}\left(\frac{\epsilon\beta}{5},\\{g_{f_{h},f^{\prime}_{h+1}}^{\pi}:f,f^{\prime}\in
F,\pi\in\Pi\\}\right)\exp\left(-\frac{\epsilon^{2}(1-\epsilon)\alpha
K}{214(1+\epsilon)H^{4}R_{\max}^{4}}\right).$

When $K<\frac{128H^{2}R_{\max}^{2}}{\epsilon^{2}(\alpha+\beta)}$,
$\exp\left(-\frac{\epsilon^{2}(1-\epsilon)\alpha
K}{214(1+\epsilon)H^{4}R_{\max}^{4}}\right)\geq\exp\left(-\frac{128}{214}\right)\geq\frac{1}{14}$
and the claim trivially holds. Bounding the Covering Number. Our final task is
bounding
$\mathcal{N}_{\infty}\left(\frac{\epsilon\beta}{5},\\{g_{f_{h},f^{\prime}_{h+1}}^{\pi}:f,f^{\prime}\in
F,\pi\in\Pi\\}\right)$ using the covering numbers of $\Pi$ and $\mathcal{F}$.
Let $\mathcal{F}_{0}$ be a $\frac{\epsilon\beta}{140HR_{\max}}$-covering of
$\mathcal{F}$ with respect to $\ell_{\infty}$ and $\Pi_{0}$ a
$\frac{\epsilon\beta}{140H^{2}R^{2}_{\mathrm{max}}}$-covering of $\Pi$ with
respect to $\|\cdot\|_{\infty,1}$. We then know that for any
$f,f^{\prime}\in\mathcal{F},\pi\in\Pi$, there exits some
$f^{\dagger},f^{\ddagger}\in\mathcal{F}_{0},\pi^{\dagger}\in\Pi_{0}$ such that

$\displaystyle\sup_{(s,a)\in{\mathcal{S}}\times\mathcal{A}}|f_{h}(s,a)-f_{h}^{\dagger}(s,a)|\leq\frac{\epsilon\beta}{140HR_{\max}},$
$\displaystyle\sup_{(s,a)\in{\mathcal{S}}\times\mathcal{A}}|f^{\prime}_{h+1}(s,a)-f_{h+1}^{\ddagger}(s,a)|\leq\frac{\epsilon\beta}{140HR_{\max}},$
$\displaystyle\sup_{s\in{\mathcal{S}}}\int_{a\in\mathcal{A}}|\pi_{h+1}(a|s)-\pi_{h+1}^{\dagger}(a|s)|\leq\frac{\epsilon\beta}{140H^{2}R^{2}_{\mathrm{max}}}.$

Consider any arbitrary $z=(s,a,r,s^{\prime})\sim\mu_{h}$. We know that

$\displaystyle\left|g_{f_{h},f^{\prime}_{h+1}}^{\pi_{h+1}}(z)-g_{f^{\dagger}_{h},f^{\ddagger}_{h+1}}^{\pi^{\dagger}_{h+1}}(z)\right|$
$\displaystyle\qquad=\biggl{|}(f_{h}(s,a)-r-f^{\prime}_{h+1}(s^{\prime},\pi_{h+1}))^{2}-({\mathcal{T}}_{h,r}^{\pi_{h+1}}f^{\prime}_{h+1}(s,a)-r-f^{\prime}_{h+1}(s^{\prime},\pi_{h+1}))^{2}-$
$\displaystyle\hskip
70.0001pt(f_{h}^{\dagger}(s,a)-r-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1}))^{2}+({\mathcal{T}}_{h,r}^{\pi^{\dagger}_{h+1}}f^{\ddagger}_{h+1}(s,a)-r-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1}))^{2}\biggr{|}$
$\displaystyle\qquad\leq\biggl{|}(f_{h}(s,a)-r-f^{\prime}_{h+1}(s^{\prime},\pi_{h+1}))^{2}-(f_{h}^{\dagger}(s,a)-r-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1}))^{2}\biggr{|}$
$\displaystyle\hskip
30.00005pt+\biggl{|}({\mathcal{T}}_{h,r}^{\pi_{h+1}}f^{\prime}_{h+1}(s,a)-r-f^{\prime}_{h+1}(s^{\prime},\pi_{h+1}))^{2}-({\mathcal{T}}_{h,r}^{\pi^{\dagger}_{h+1}}f^{\ddagger}_{h+1}(s,a)-r-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1}))^{2}\biggr{|}$
$\displaystyle\qquad\leq\biggl{|}f_{h}(s,a)+f_{h}^{\dagger}(s,a)-2r-f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})\biggr{|}$
$\displaystyle\hskip
30.00005pt\times\biggl{|}f_{h}(s,a)-f_{h}^{\dagger}(s,a)+f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})\biggr{|}$
$\displaystyle\hskip
30.00005pt+\biggl{|}{\mathcal{T}}_{h,r}^{\pi_{h+1}}f^{\prime}_{h+1}(s,a)+{\mathcal{T}}_{h,r}^{\pi^{\dagger}_{h+1}}f^{\ddagger}_{h+1}(s,a)-2r-f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})\biggr{|}$
$\displaystyle\hskip
30.00005pt\times\biggl{|}{\mathcal{T}}_{h,r}^{\pi_{h+1}}f^{\prime}_{h+1}(s,a)-{\mathcal{T}}_{h,r}^{\pi^{\dagger}_{h+1}}f^{\ddagger}_{h+1}(s,a)+f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})\biggr{|}$
$\displaystyle\qquad\leq
4HR_{\max}\biggl{|}f_{h}(s,a)-f_{h}^{\dagger}(s,a)+f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})\biggr{|}$
$\displaystyle\hskip
30.00005pt+4HR_{\max}\biggl{|}{\mathcal{T}}_{h,r}^{\pi_{h+1}}f^{\prime}_{h+1}(s,a)-{\mathcal{T}}_{h,r}^{\pi^{\dagger}_{h+1}}f^{\ddagger}_{h+1}(s,a)+f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})\biggr{|},$
(F.7)

where for the last inequality we used the boundedness of functions in
$\mathcal{F}_{h}$ and $\mathcal{F}_{h+1}$. We then notice that

$\displaystyle\biggl{|}f_{h}(s,a)-f_{h}^{\dagger}(s,a)+f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})\biggr{|}$
$\displaystyle\qquad\leq|f_{h}(s,a)-f_{h}^{\dagger}(s,a)|+|f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})|$
$\displaystyle\qquad\leq\frac{\epsilon\beta}{140HR_{\max}}+|f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\prime}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})|+|f^{\prime}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})|$
$\displaystyle\qquad\leq\frac{\epsilon\beta}{140HR_{\max}}+\|\pi_{h+1}-\pi^{\dagger}_{h+1}\|_{1}\|f^{\prime}_{h+1}\|_{\infty}+|f^{\prime}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})|$
$\displaystyle\qquad\leq\frac{\epsilon\beta}{140HR_{\max}}+\frac{\epsilon\beta}{140H^{2}R^{2}_{\mathrm{max}}}HR_{\max}+|f^{\prime}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})|$
$\displaystyle\qquad\leq\frac{\epsilon\beta}{140HR_{\max}}+\frac{\epsilon\beta}{140HR_{\max}}+\mathbb{E}_{a^{\prime}\sim\pi^{\dagger}_{h+1}(\cdot|s^{\prime})}[|f^{\prime}_{h+1}(s^{\prime},a^{\prime})-f^{\ddagger}_{h+1}(s^{\prime},a^{\prime})|]$
$\displaystyle\qquad\leq\frac{3\epsilon\beta}{140HR_{\max}},$

where the third inequality uses Holder’s inequality, the fourth definition of
$\Pi_{0}$ and boundedness of $\mathcal{F}_{h}$, the fifth Jensen’s inequality,
and the last inequality the definition of $\mathcal{F}_{0}$. Additionally we
have

$\displaystyle|{\mathcal{T}}_{h,r}^{\pi_{h+1}}f^{\prime}_{h+1}(s,a)-{\mathcal{T}}_{h,r}^{\pi^{\dagger}_{h+1}}f^{\ddagger}_{h+1}(s,a)+f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})|$
$\displaystyle\qquad\leq|{\mathcal{T}}_{h,r}^{\pi_{h+1}}f^{\prime}_{h+1}(s,a)-{\mathcal{T}}_{h,r}^{\pi^{\dagger}_{h+1}}f_{h+1}^{\ddagger}(s,a)|+|f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})|$
$\displaystyle\qquad\leq|{\mathcal{T}}_{h,r}^{\pi_{h+1}}f^{\prime}_{h+1}(s,a)-{\mathcal{T}}_{h,r}^{\pi^{\dagger}_{h+1}}f_{h+1}^{\ddagger}(s,a)|+\frac{2\epsilon\beta}{140HR_{\max}}$
$\displaystyle\qquad\leq\mathbb{E}_{s^{\prime\prime}\sim\mathcal{P}_{h}(\cdot|s,a)}|f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})|+\frac{2\epsilon\beta}{140HR_{\max}}$
$\displaystyle\qquad\leq\frac{4\epsilon\beta}{140HR_{\max}},$

where the second inequality uses the same reasoning as above to bound
$|f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})|$,
the third Jensen’s inequality, and the last inequality reuses the bound for
$|f^{\prime}_{h+1}(s^{\prime},\pi_{h+1})-f^{\ddagger}_{h+1}(s^{\prime},\pi^{\dagger}_{h+1})|$
over arbitrary $s^{\prime}$. Plugging these back into equation (F.1) shows

$\left|g_{f_{h},f^{\prime}_{h+1}}^{\pi_{h+1}}(z)-g_{f^{\dagger}_{h},f^{\ddagger}_{h+1}}^{\pi^{\dagger}_{h+1}}(z)\right|\leq\frac{7\epsilon\beta}{140HR_{\max}}\times
4HR_{\max}=\frac{\epsilon\beta}{5}.$

Thus

$\mathcal{N}_{\infty}\left(\frac{\epsilon\beta}{5},\\{g_{f_{h},f^{\prime}_{h+1}}^{\pi}:f,f^{\prime}\in
F,\pi\in\Pi\\}\right)\leq\left(\mathcal{N}_{\infty}\left(\frac{\epsilon\beta}{140HR_{\max}},\mathcal{F}\right)\right)^{2}\mathcal{N}_{\infty,1}\left(\frac{\epsilon\beta}{140H^{2}R^{2}_{\mathrm{max}}},\Pi\right),$

showing one side of the inequality holds.

To show the other side holds, simply replace $g_{f,f^{\prime}}^{\pi}(Z)$
defined in equation 5.1 with its negative and repeat the analysis above. We
then complete the proof by taking a union bound over both halves.

###  F.2 Proofs of “Good Event”

With the help of the previous theorem, we are able to show that
$\mathcal{G}(\Pi_{\rm SPI})$ occurs with high probability.

###### Proof of Lemma D.3.

Taking a union bound over all $h\in[H]$ and reported reward
$r\in\widetilde{\mathcal{R}}$ recalling that $|\widetilde{\mathcal{R}}|\leq
n+1\leq 2n$, by Lemma D.2, we have

$\displaystyle\Pr\Bigl{(}\exists
h\in[H],r\in\widetilde{\mathcal{R}},f,f^{\prime}\in\mathcal{F},\pi\in\Pi:$
$\displaystyle\hskip
60.00009pt\left|\mathbb{E}_{\mu_{h}}\left[\|f_{h}-{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}\|^{2}\right]-\mathcal{L}_{h,r}(f_{h},f^{\prime}_{h+1},\pi;\mathcal{D})+\mathcal{L}_{h,r}({\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1},f^{\prime}_{h+1},\pi;\mathcal{D})\right|$
$\displaystyle\hskip
240.00037pt\geq\epsilon\left(\alpha+\beta+\mathbb{E}_{\mu_{h}}\left[\|f_{h}-{\mathcal{T}}_{h,r}^{\pi}f^{\prime}_{h+1}\|^{2}\right]\right)\Bigr{)}$
$\displaystyle\qquad\leq
56nH\left(\mathcal{N}_{\infty}\left(\frac{\epsilon\beta}{140HR_{\max}},\mathcal{F}\right)\right)^{2}\mathcal{N}_{\infty,1}\left(\frac{\epsilon\beta}{140H^{2}R^{2}_{\mathrm{max}}},\Pi\right)\exp\left(-\frac{\epsilon^{2}(1-\epsilon)\alpha
K}{214(1+\epsilon)H^{4}R_{\max}^{4}}\right).$

Letting $\alpha=\beta$ and $\epsilon=\frac{1}{2}$, setting the right hand side
to $\delta$, and solving for $\alpha$ gives us

$\alpha\leq\frac{1}{K}\max\left\\{5136H^{4}R^{4}_{\max},5136H^{4}R^{4}_{\max}\log\frac{56nH\mathcal{N}_{\infty}\left(\frac{HR_{\max}}{K},\mathcal{F}\right)\mathcal{N}_{\infty,1}\left(\frac{1}{K},\Pi\right)}{\delta}\right\\}.$

As $\log 56\geq 1$, $n,H\geq 1$, and $0<1<\delta$, the second term always
dominates the first and we can simplify the inequality as

$\alpha\leq\frac{5136H^{4}R^{4}_{\max}}{K}\log\frac{56nH\mathcal{N}_{\infty}\left(\frac{19H^{3}R^{3}_{\max}}{K},\mathcal{F}\right)\mathcal{N}_{\infty,1}\left(\frac{19H^{4}R^{4}_{\max}}{K},\Pi\right)}{\delta},$

completing the proof. ∎

###### Proof of Corollary D.4.

For convenience, let $\widehat{g}^{\pi}_{h,r}=\mathop{\text{\rm
arg\,min}}_{g\in\mathcal{F}_{h}}\mathcal{L}_{h,r}(g,f_{h+1,r}^{\pi,*},\pi;\mathcal{D})$.
We then know that

$\displaystyle\mathcal{E}_{h,r}(f_{h,r}^{\pi,*},\pi;\mathcal{D})$
$\displaystyle=\mathcal{L}_{h,r}(f_{h,r}^{\pi,*},f_{h+1,r}^{\pi,*},\pi;\mathcal{D})-\mathcal{L}_{h,r}(\widehat{g}^{\pi}_{h,r},f_{h+1,r}^{\pi,*},\pi;\mathcal{D})$
$\displaystyle=\mathcal{L}_{h,r}(f_{h,r}^{\pi,*},f_{h+1,r}^{\pi,*},\pi;\mathcal{D})-\mathcal{L}_{h,r}({\mathcal{T}}_{h,r}^{\pi,*}f_{h+1,r}^{\pi,*},f_{h+1,r}^{\pi,*},\pi;\mathcal{D})$
$\displaystyle\quad-\left(\mathcal{L}_{h,r}(\widehat{g}^{\pi}_{h,r},f_{h+1,r}^{\pi,*},\pi;\mathcal{D})-\mathcal{L}_{h,r}({\mathcal{T}}_{h,r}^{\pi,*}f_{h+1,r}^{\pi,*},f_{h+1,r}^{\pi,*},\pi;\mathcal{D})\right).$

By Lemma D.3, conditionally on the event $\mathcal{G}(\Pi)$ we have the
following simultaneously:

$\displaystyle\mathcal{L}_{h,r}(f_{h,r}^{\pi,*},f_{h+1,r}^{\pi,*},\pi;\mathcal{D})-\mathcal{L}_{h,r}({\mathcal{T}}_{h,r}^{\pi,*}f_{h+1,r}^{\pi,*},f_{h+1,r}^{\pi,*},\pi;\mathcal{D})$
$\displaystyle\leq\epsilon_{\rm
S}+\frac{3}{2}\mathbb{E}_{\mu_{h}}\left[\|f_{h,r}^{\pi,*}-{\mathcal{T}}_{h,r}^{\pi,*}f_{h+1,r}^{\pi,*}\|^{2}\right],$
$\displaystyle-\mathcal{L}_{h,r}(\widehat{g}^{\pi}_{h,r},f_{h+1,r}^{\pi,*},\pi;\mathcal{D})+\mathcal{L}_{h,r}({\mathcal{T}}_{h,r}^{\pi,*}f_{h+1,r}^{\pi,*},f_{h+1,r}^{\pi,*},\pi;\mathcal{D})$
$\displaystyle\leq\epsilon_{\rm S},$

where the second inequality uses the fact that $\|\cdot\|^{2}$ is non-
negative. Finally, noticing that

$\displaystyle\mathbb{E}_{\mu_{h}}\left[\|f_{h,r}^{\pi,*}-{\mathcal{T}}_{h,r}^{\pi,*}f_{h+1,r}^{\pi,*}\|^{2}\right]$
$\displaystyle\leq
2\mathbb{E}_{\mu_{h}}\left[\|f_{h,r}^{\pi,*}-Q_{h}^{\pi}(\cdot,\cdot;r)\|^{2}\right]+2\mathbb{E}_{\mu_{h}}\left[\|{\mathcal{T}}_{h,r}^{\pi,*}f_{h+1,r}^{\pi,*}-{\mathcal{T}}_{h,r}^{\pi,*}Q_{h}^{\pi}(\cdot,\cdot;r)\|^{2}\right]$
$\displaystyle\leq
2\epsilon_{\mathcal{F}}+2\mathbb{E}_{\mu_{h+1}^{\prime}}\left[\|f_{h+1,r}^{\pi,*}-Q_{h+1}^{\pi}(\cdot,\cdot;r)\|^{2}\right]$
$\displaystyle\leq 4\epsilon_{\mathcal{F}},$

where $\mu_{h+1}^{\prime}$ shares the marginal distribution over
${\mathcal{S}}$ with $\mu_{h+1}$ but the conditional distribution over
$\mathcal{A}$ given $s\in{\mathcal{S}}$ is given by $\pi_{h+1}(\cdot|s)$. The
final inequality comes from the fact that $\mu_{h+1}^{\prime}$ is an
admissible distribution under Assumption 2.3. ∎

###### Proof of Corollary D.5.

Let $\widehat{g}^{\pi}_{h,r}=\mathop{\text{\rm
arg\,min}}_{g\in\mathcal{F}_{h}}\mathbb{E}_{\mu_{h}}[\|g-{\mathcal{T}}_{h,r}^{\pi}f_{h+1,r}^{\pi}\|^{2}]$.
Recalling the definition of $\mathcal{E}_{h,r}$, we have

$\displaystyle\mathcal{E}_{h,r}(f_{h,r}^{\pi},\pi;\mathcal{D})$
$\displaystyle=\mathcal{L}_{h,r}(f_{h,r}^{\pi},f_{h+1,r}^{\pi},\pi;\mathcal{D})-\min_{g\in\mathcal{F}_{h}}\mathcal{L}_{h,r}(g,f_{h+1,r}^{\pi},\pi;\mathcal{D})$
$\displaystyle\geq\mathcal{L}_{h,r}(f_{h,r}^{\pi},f_{h+1,r}^{\pi},\pi;\mathcal{D})-\mathcal{L}_{h,r}(\widehat{g}^{\pi}_{h,r},f_{h+1,r}^{\pi},\pi;\mathcal{D})$
$\displaystyle=\mathcal{L}_{h,r}(f_{h,r}^{\pi},f_{h+1,r}^{\pi},\pi;\mathcal{D})-\mathcal{L}_{h,r}({\mathcal{T}}_{h,r}^{\pi}f_{h+1,r}^{\pi},f_{h+1,r}^{\pi},\pi;\mathcal{D})$
$\displaystyle\quad-\left(\mathcal{L}_{h,r}(\widehat{g}^{\pi}_{h,r},f_{h+1,r}^{\pi},\pi;\mathcal{D})-\mathcal{L}_{h,r}({\mathcal{T}}_{h,r}^{\pi}f_{h+1,r}^{\pi},f_{h+1,r}^{\pi},\pi;\mathcal{D})\right).$

By Lemma D.3, conditionally on the event $\mathcal{G}(\Pi)$ we have the
following:

$\displaystyle\mathcal{L}_{h,r}(f_{h,r}^{\pi},f_{h+1,r}^{\pi},\pi;\mathcal{D})-\mathcal{L}_{h,r}({\mathcal{T}}_{h,r}^{\pi}f_{h+1,r}^{\pi},f_{h+1,r}^{\pi},\pi;\mathcal{D})$
$\displaystyle\geq-\epsilon_{\rm
S}+\frac{1}{2}\mathbb{E}_{\mu_{h}}\left[\|f_{h,r}^{\pi}-{\mathcal{T}}_{h,r}^{\pi}f_{h+1,r}^{\pi}\|^{2}\right],$
$\displaystyle-\mathcal{L}_{h,r}(\widehat{g}^{\pi}_{h,r},f_{h+1,r}^{\pi},\pi;\mathcal{D})+\mathcal{L}_{h,r}({\mathcal{T}}_{h,r}^{\pi}f_{h+1,r}^{\pi},f_{h+1,r}^{\pi},\pi;\mathcal{D})$
$\displaystyle\geq-\epsilon_{\rm
S}-\frac{3}{2}\mathbb{E}_{\mu_{h}}\left[\|\widehat{g}_{h,r}^{\pi}-{\mathcal{T}}_{h,r}^{\pi}f_{h+1,r}^{\pi}\|^{2}\right].$

Recalling that $\mathcal{E}_{h,r}(f,\pi;\mathcal{D})\leq\epsilon_{0}$, we have

$\mathbb{E}_{\mu_{H}}\left[\|f_{h,r}^{\pi}-{\mathcal{T}}_{h,r}^{\pi}f_{h+1,r}^{\pi}\|^{2}\right]\leq
4\epsilon_{\rm
S}+3\mathbb{E}_{\mu_{h}}\left[\|\widehat{g}_{h,r}^{\pi}-{\mathcal{T}}_{h,r}^{\pi}h_{h+1,r}^{\pi}\|^{2}\right]+2\epsilon_{0}.$

We conclude our proof by reminding ourselves of Assumption 2.4. ∎