# Tree-based Focused Web Crawling with Reinforcement Learning

Andreas Kontogiannis, Dimitrios Kelesis, Vasilis Pollatos, Georgios Paliouras
and George Giannakopoulos A. Kontogiannis and V. Pollatos are with the School
of Electrical and Computer Engineering, National Technical University of
Athens, Greece, 15780 .
E-mail<EMAIL_ADDRESS>D. Kelesis is with the School of Electrical and
Computer Engineering, National Technical University of Athens, Greece, 15780
and National Centre for Scientific Research (NCSR) “Demokritos”, Athens 15310,
Greece G. Paliouras is with the National Centre for Scientific Research (NCSR)
“Demokritos”, Athens 15310, Greece G. Giannakopoulos is with the National
Centre for Scientific Research (NCSR) “Demokritos”, Athens 15310, Greece and
SciFY PNPC, 153 41 Ag. Paraskevi, Greece This work has been submitted to the
IEEE for possible publication. Copyright may be transferred without notice,
after which this version may no longer be accessible.

###### Abstract

A focused crawler aims at discovering as many web pages relevant to a target
topic as possible, while avoiding irrelevant ones. Reinforcement Learning (RL)
has been utilized to optimize focused crawling. In this paper, we propose
TRES, an RL-empowered framework for focused crawling. We model the crawling
environment as a Markov Decision Process, which the RL agent aims at solving
by determining a good crawling strategy. Starting from a few human provided
keywords and a small text corpus, that are expected to be relevant to the
target topic, TRES follows a keyword set expansion procedure, which guides
crawling, and trains a classifier that constitutes the reward function. To
avoid a computationally infeasible brute force method for selecting a best
action, we propose Tree-Frontier, a decision-tree-based algorithm that
adaptively discretizes the large state and action spaces and finds only a few
representative actions. Tree-Frontier allows the agent to be likely to select
near-optimal actions by being greedy over selecting the best representative
action. Experimentally, we show that TRES significantly outperforms state-of-
the-art methods in terms of harvest rate (ratio of relevant pages crawled),
while Tree-Frontier reduces by orders of magnitude the number of actions
needed to be evaluated at each timestep.

###### Index Terms:

Focused Web Crawling, Reinforcement Learning, Decision Tree, Tree Based
Discretization, State and Action Spaces Discretization, URL Classification,
Markov Decision Process

##  1 Introduction

FOCUSED crawlers [8] are essentially intelligent agents which, given a topic
of interest, find a strategy to search for relevant web pages. Such agents are
widely used to collect vast amounts of topic-related data. Typically, a
focused crawler starts from an initial set of highly relevant data, in the
form of URLs, called _seeds_. The crawler utilizes seeds to bootstrap the
collection process, extracting their outgoing links, or _outlink URLs_ , and
storing them in a URL collection, called the crawl frontier [12]. The agent
selects the most promising URL from the frontier (based on an evaluation
function), visits the correspdoning web page and classifies it as relevant or
irrelevant to the user’s interests. Then, recursively, the outlinks of the
visited page are stored in the frontier. Based on relevance feedback by the
user, the evaluation function that scores the frontier URLs is adjusted. In a
typical focused crawling setting, the total number of visited or retrieved
URLs is user-defined and thus the whole process terminates when that number is
reached.

Many approaches, such as [13, 20, 33, 35], use classifiers to estimate whether
a given web page is related to the target topic, instead of requesting human
feedback. Such classifiers can be used to (a) identify the relevant web pages
(in the form of URLs) in the frontier, assigning them high evaluation values,
which imply high crawling priorities, (b) give relevance feedback to the
strategy of the crawler once a web page has been visited and (c) evaluate the
relevance of the crawled data at the end of the process.

An alternative approach is to model the crawling environment as a Markov
Decision Process (MDP) and employ Reinforcement Learning (RL). Unlike simple
classification-based methods, RL-based focused crawlers are able to identify
web pages (or websites), called hubs [34], which are possibly connected with
other relevant URLs on the Web. Thus, in cases where no high relevance URLs
exist in the frontier, a good RL strategy may prioritize hubs to reach highly
relevant web pages at a later step.

Another major challenge of focused crawling is how to deal with the large URL
collection that is stored in the frontier. At each crawling step, the crawler
must evaluate the URLs in the frontier and then fetch the URL estimated to be
the best for the crawling process. Under the assumption that the frontier has
a linear growth over time, the computational cost of a brute force method for
selecting the best URL at each timestep is infeasible for long crawling
sessions.

In this paper:

  * •

We propose a novel RL-based focused crawling framework called TRES (Tree
REinforcement Spider). The framework employs a novel, mathematically sound,
Markov Decision Process (MDP) formulation for focused crawling.

  * •

We introduce the Tree-Frontier algorithm, which provides efficient and
effective representation of the crawl frontier, through discretization of the
large state and action spaces.

  * •

We show that TRES outperforms other state-of-the-art focused crawlers in three
test domains, in terms of harvest rate of web pages, utilizing no more than a
single seed URL.

  * •

We show that the use of Tree-Frontier improves the time complexity of the
brute force method for calculating the Q-values of all available actions.

The remainder of the paper is organized as follows. In Section 2, we give a
brief overview of the related work. In Section 3, we present the problem
definition and the proposed framework. Our experimental evaluation and the
comparisons with baseline and state-of-the-art methods are presented in
Section 4. Section summarises the conclusions of this paper and provides some
future steps.

##  2 Related Work

Methods that discover Web content are often categorized in two classes: (a)
Search-based Discovery methods and (b) Crawling-based Discovery methods [32].
Search-based Discovery methods utilize queries on search engine APIs (e.g.
Google and Bing) and form a strategy for query improvement. Crawling-based
Discovery methods utilize the link structure to discover new content by
automatically fetching and iteratively selecting URLs extracted from the
visited web pages.

SeedFinder [39] belongs to the search-based approaches: it tries to find new
seeds in order to best bootstrap the crawling process of an arbitrary focused
crawler, by executing queries on search engines utilizing terms (keywords)
extracted from relevant texts. Liakos et al. [22] expanded a keyword
collection by selecting the keyword with the highest TF-IDF score to form a
query. By executing this query on a search engine, new candidate keywords were
retrieved and the ones with the highest scores were stored in the collection.

On the other hand, the crawling-based discovery methods can be divided into:
(a) backward and (b) focused (forward) crawling methods. Backward crawling
methods, e.g. the BIPARTITE crawler [3], explore URLs through backlink search,
i.e. by utlizing links that links towards a URL of reference. In this work, we
are not interested in evaluating backward crawling, since it requires paid
APIs for most real users.

Since the introduction of focused crawling by Chakrabarti et al. [8], several
improvements have been made to the basic process. One of the early
modifications was the use of two classifiers; an _apprentice_ and a _critic_
[7]. The critic classifies web pages, while the apprentice learns (from the
critic’s feedback) to identify the most promising outlink URLs. Suebchua et
al. [36] introduced the “Neighborhood feature” in focused crawling, which
utilizes the relevance of all already fetched web pages of the same domain
(web site), in order to more effectively select URLs belonging to the same
domain. This approach is based on the assumption that a web page is likely to
be relevant if relevant web pages have been discovered in its neighborhood,
which can also be attributed to the empirical evidence of topical locality on
the Web showed by Davison [10]. However, one limitation of this approach is
that the identification of hubs highly depends on how many relevant URLs have
been found on the already crawled web sites.

Du et al. [11] integrated the TF-IDF scores of the words with the semantic
similarities among the words to construct _topic and text semantic vectors_
and computed the cosine similarities between these vectors to select URLs.
ACHE [4] is an adaptive crawler aiming to maximize the harvest rate [8] of
fetched web pages through an online-learning policy. It learns to identify
promising URLs and, as the crawl progresses, it adapts its focus relying on
the relevant web sites that it has fetched.

Pham et al. [32] proposed DISCO, a framework which combines both Search-based
Discovery and Crawling-based Discovery methods. It uses a multi-armed bandit
strategy to combine different search operators (queries on APIs, forward and
backward crawling) as proxies to collect relevant web pages, and rank them,
based on their similarity to seeds.

Rennie and McCallum [34] introduced RL in focused crawling, but they
generalized over all possible states in order to deal with the huge state
space; thus each action (outlink URL) was immediately disconnected from its
state. To face these challenges, RLwCS [30] uses a tabular Q-learning policy
that selects the best classifier from a defined pool of classifiers, which
evaluate all available candidate URLs that the crawler can immediately fetch.
InfoSpiders [25, 26] approximate the Q-values of URLs in an online way, yet
they only take into account statistical features of keywords for the state
representation, without considering any experience samples.

Han et al. [18] proposed an online crawling algorithm, based on SARSA policy
approximation [37] introducing a shared state-action representation. They
manually discretized the state-action space into buckets according to value
ranges of statistical heuristic features. However, their MDP formulation
somewhat unnaturally allows the agent to deviate from the successive order of
states; i.e. it may select actions that do not really exist in a current
state. This way, given a current state, the agent may transition with positive
probability to states, for which the corresponding transition probabilities
are not explicitly in the state representation.

Moreover, to select URLs from the frontier, they introduced synchronous
updates; at each timestep they updated the Q-values of all actions (URLs) and
selected the URL with the highest one. To overcome the computational cost of
evaluating all available actions at each timestep, they also proposed a
heuristic asynchronous method which updates the Q-values of only those actions
belonging to the current state. However, the action values of all URLs in the
frontier are calculated at different timesteps making it diﬃcult for the
crawler agent to choose the best one.

From a more theoretical standpoint, Gouriten et al. [16] highlighted the
frontier batch disadvantage, considering that a batch is the number of
successive crawling timesteps in which the frontier has not been updated. They
showed that even in an offline setting, the problem of determining the optimal
sequence of fetched pages, is NP-hard. To tackle this problem, RL has been
employed to find a policy in order to select which web pages to fetch from the
frontier.

To face certain challenges arising in the above literature, we propose TRES, a
novel RL-based focused crawling framework. Similar to [18], we formulated the
focused crawling setting as an MDP, but we achieved to allow the agent to both
preserve the successive order of state transitions and avoid the “crawling
traps”, in which the agent only follows the URLs that are hyperlinks of the
last crawled web pages. Moreover, our shared state-action representation
allows the discovery of hubs that do not only depend on how many relevant URLs
have been found on the already crawled web sites, as in [36]. We encourage a
more exploratory crawling strategy through the use of statistical features
related to keywords, relevance estimation and the web path. Another
improvement over the examined related work is the use of word2vec embeddings,
as opposed to TF-IDF or other schemas, for the keyword set expansion, URL
representation and web page text representation. To deal with the large URL
collection that is stored in the frontier, we introduce the Tree-Frontier
approach that efficiently organizes this collection and allows subtle sampling
from it.

##  3 Problem and Method Overview

In the following paragraphs, we first describe the different aspects to which
this work contributes. To this end, we provide different sub-problem
definitions and suggest different approaches for each aspect, which all
together form the TRES111 https://github.com/ddaedalus/tres framework.

###  3.1 Problem Definition

####  3.1.1 Keyword Expansion Problem

Our aim is to find a set of keywords that is sufficient to identify any
document, belonging to a given topic. In order to do that, we start with a
small number of keywords and adopt a keyword expansion strategy in order to
identify as many keywords as possible. Formally, let $D_{C}$ be the set of all
web page topic-related text documents belonging to a target topic $C$. Also,
let $K_{C}=\\{k_{1},...,k_{N_{K}}\\}$ be the finite set of all keywords that
describe C. Given an initial small set of keywords,
$KS=\\{k_{1},...,k_{N_{KS}}\\}$, where $KS\subset K_{C}$, and a corpus of text
documents $D_{tr}=\\{t_{1},...,t_{N}\\}$ where each
$t_{i}=\\{w^{i}_{1},...,w^{i}_{n_{i}}\\}$ contains $n_{i}$ candidate keywords,
our goal is to expand $KS$ so that $KS=K_{C}$.

####  3.1.2 Web Page Classification Problem

Similar to [24], we deal with a binary web page classification problem, aiming
to decide whether a given web page is relevant to the topic of interest.
Specifically, let $D^{\prime}_{C}$ represent the set of all web page text
documents belonging to any topic, other than $C$. Also, let $P$ represent the
set of all web pages on the Web. Assuming (a) $P$ is finite, (b) each web page
$p\in P$ can be represented as a text document and (c) a word vector space
$\mathbb{R}^{N}$, then $p=\\{w_{1},...,w_{n_{p}}\\}$ is a collection of
$n_{p}$ words. Given a collection of web pages $D_{tr}\subseteq D_{C}\cup
D^{\prime}_{C}$, being represented as text documents of maximum word length
$M$, and a keyword set $K$, our goal is to find a function $f:K\times
P\rightarrow\\{0,1\\}$, so that for each input web page $p\in P$, $f(p)$
classifies $p$ correctly into $D_{C}$ or $D^{\prime}_{C}$. The above function
can be also written $f:K\times M\times\mathbb{R}^{N}\rightarrow\\{0,1\\}$.

####  3.1.3 Focused Crawling Problem

Let $U_{C}$ be the finite set of URLs corresponding to all web pages that
belong to the target topic $C$. Given $C$ and a small set of seeds $U_{S}$,
where $|U_{S}|<<|U_{C}|$, our goal is to expand $U_{S}$ over a $T$-timestep-
attempt-process of discovering URLs belonging to $U_{C}\setminus U_{S}$. Thus,
since the crawling process is terminated after $T$ timesteps, $U_{S}$ would be
expanded by $T$ new URLs. We will refer to these $U_{C}\setminus U_{S}$ URLs
discovered as relevant.

In the rest of this section, we describe our proposed TRES framework. First,
we formulate the focused crawling problem as an MDP. Then, we present the
keyword expansion strategy that our crawler adopts, in order to discover
keywords that are relevant to the target topic. Next, we describe KwBiLSTM, a
deep neural network estimating the reward function of our RL setting. Last but
not least, we present the proposed focused crawling algorithm, which utilizes
RL, in order to find good policies for selecting URLs, and the Tree-Frontier
algorithm for efficient sampling from the frontier.

###  3.2 Modeling Focused Crawling as an MDP

Similar to [18], we consider the focused crawler to be an agent, which acts in
an interactive environment. Within such an environment, the agent changes
states, takes actions and receives rewards, with the goal of maximizing the
cumulative reward. In this context, focused crawling can be modeled as an MDP
unifying the traditional use of the frontier with the action set of an RL
focused crawler agent.

####  3.2.1 Preliminaries

Let $U$ be the finite set of all URLs on the Web. Let Page: $U\rightarrow P$
be the function that maps URLs to corresponding web pages in $P$, which refers
to the set of existing pages on the Web. Let $\text{Outlink}:U\rightarrow
2^{U}$ be the function that matches a given URL $u\in U$ to a set containing
its outlink URLs.

Let $G$ be the directed graph of the Web. The node set of $G=(U,E)$ is
equivalent to the URL set $U$. The edge set $E$ of $G$ is defined as follows:
a node $u_{i}\in U$ has a directed edge to another node $u_{j}\in U$ if
$u_{j}\in Outlink(u_{i})$. We represent the corresponding edge with
$(u_{i},u_{j})\in E$.

During crawling, the crawler gradually traverses a subgraph of G. Each time it
fetches a new URL, the corresponding node is added to the subgraph. Let
$g_{t}$ be the directed subgraph of $G$ that the crawler has traversed until
timestep $t$. For $t=0$ it holds that $g_{0}=(U_{S},\emptyset)$; i.e. the
initial subgraph has its node set equal to the seed set $U_{S}$ and no edges.
We denote the URL fetched at $t$ as $u^{(t)}$. Then, $g_{t+1}$ is $g_{t}$
expanded by node $u^{(t+1)}$ and edge $(u^{(k)},u^{(t+1)})$, where $0\leq
k<t+1$. Therefore, $g_{t}$ contains all $u^{(k)}$ nodes, for $0\leq k\leq t$.
Note that for each timestep $t$, $g_{t}$ is a forest of $|U_{S}|$ ordered
trees.

Also, let closure, or crawled set as defined in [16], $C_{t}$ be the set of
fetched URLs until timestep $t$. Note that closure $C_{t}$ is equal to the
nodes fetched at timestep $t$; i.e. $U_{t}$. From the definition of closure,
the crawler fetches a URL at most once, so a URL has a unique web path for the
whole crawling process.

######  Definition 1 (Web Path).

We define the web path $path(t)$ of the URL $u^{(t)}$ fetched by the crawler
at timestep $t$ as the path of $g_{t}$ from a given seed URL in $U_{S}$ to
$u^{(t)}$.

Let frontier, or crawl frontier, $F_{t}$ be the set of all available outlink
URLs that the crawler has not fetched until timestep $t$, but were extracted
by web pages fetched before $t$. More formally:

######  Definition 2 (Frontier).

We define frontier $F_{t}$ at timestep $t$, given $C_{t}$, as:

$\displaystyle F_{t}=\left\\{(path(\tau),u):\tau\geq 0,u^{(\tau)}\in
C_{t},u\in\text{Outlink}(u^{(\tau)})\right\\}$

In the above definition, notice that we also include the corresponding web
paths of those URLs, from which we extract the available URLs to fetch at
timestep $t$.

####  3.2.2 MDP formulation

Based on the above, we formulate the crawling process as the MDP,
$(S,A,P_{t,a},R_{t+1})$. We denote a state $S_{t}\in S$ at timestep $t$ as the
directed subgraph of $G$ that the crawler has traversed at $t$; i.e.
$S_{t}=g_{t}$. We define actions $\tilde{A}_{t}\subset A$ at timestep $t$
given $S_{t}$ (and thus $g_{t}$ and $C_{t}$), as the set of all available
edges through which $g_{t}$ can be expanded by one new node; that is:

$\displaystyle\tilde{A}_{t}=\left\\{(v,u):v\in
C_{t},u\in\text{Outlink}(v),u\not\in C_{t}\right\\}$ (1)

Also, we define $P_{t,a}(s,s^{\prime})=\mathbb{P}[S_{t+1}=s^{\prime}\ |\
S_{t}=s,A_{t}=a]$ as the transition probability of selecting the edge $a$ to
expand state $s=g_{t}$ in order to transition to a state $s^{\prime}=g_{t+1}$.
In our setting, we utilize deterministic transitions. Furthermore, we define a
binary reward function $R\colon S\times A\times S\rightarrow\mathbb{R}$ that
equals $1$ if the web page of the URL $u^{(t+1)}$ crawled at timestep $t+1$ is
relevant and $0$ otherwise. For brevity, let $r_{t+1}$ be the reward observed
at timestep $t$, that is $r_{t+1}=R(s_{t},a_{t},s_{t+1})$.

The initial state $S_{0}=g_{0}$ consists of the seed URLs. A final state is
not naturally defined since crawling is a non episodic problem, where maximal
rewards are ideally observed most of the time. Assuming that the crawling
process stops after $T$ timesteps, $g_{T}$ is the final state.

From all the above, unlike previous approaches that regard action selection to
be related to URL relevance estimation, to our knowledge, our approach is the
first to preserve the successive order of state transitions by always
selecting actions that are explicitly available in the current state. Also,
observe that in our MDP, given a timestep $t$, selecting a $(path(\tau),u)$
from $F_{t}$ is equivalent to selecting action $(u^{(\tau)},u)$ from
$\tilde{A}_{t}$. Recall that $\tilde{A}_{t}$ is the set of all available
actions at timestep $t$. Now we can match these actions to the elements of
frontier $F_{t}$ with URLs not in closure $C_{t}$. Therefore, we can relate
the traditional use of the frontier to the action set of an RL focused crawler
agent for all timesteps.

The agent aims to maximize the expected discounted cumulative reward, which is
formulated as $G_{t}=\sum_{\tau=t}^{\infty}\gamma^{\tau-t}r_{\tau}$. Here,
$\gamma\in[0,1]$ is a discount factor which is used for trading-off the
importance of immediate and future rewards. Under a stochastic policy $\pi$,
the Q-function of a state-action pair $(s,a)$ is defined as follows

$Q^{\pi}(s,a)=\mathbb{E}\left[G_{t}\mid S_{t}=s,A_{t}=a,\pi\right]$

which can also be computed recursively with bootstrapping:

$Q^{\pi}(s,a)=\mathbb{E}\left[r_{t}+\gamma\mathbb{E}_{a^{\prime}\sim\pi(s^{\prime})}[Q^{\pi}(s^{\prime},a^{\prime})]\mid
S_{t}=s,A_{t}=a,\pi\right]\text{.}$

The Q-function measures the value of choosing a particular action when the
agent is in a given state. We define the optimal policy $\pi^{*}$ under which
we receive the optimal $Q^{*}(s,a)=max_{\pi}Q^{\pi}(s,a)$. At timestep $t$,
given a state $s_{t}$, under the optimal policy $\pi^{*}$, the agent selects
action $a_{t}=argmax_{a^{\prime}\in\tilde{A}_{t}}Q^{*}(s_{t},a^{\prime})$.
Therefore, it follows that the optimal Q-function satisfies the Bellman
equation:

$Q^{*}(s,a)=\mathbb{E}\left[r_{t}+\gamma{}\max_{a^{\prime}\in\tilde{A}_{t}}Q^{*}(s^{\prime},a^{\prime})\mid
S_{t}=s,A_{t}=a,\pi\right]$

###  3.3 Discovering Relevant Keywords

Keywords and seeds often play the role of a crawler’s only prior knowledge
about the target topic. Having a collection of keywords that are irrelevant to
the target topic can lead the crawler to follow URLs that diverge from the
topic of interest. In this paper, we assume that an initial small keyword set
$KS=\\{k_{1},...,k_{N_{K}}\\}$ is given as input, containing keywords that are
all highly related to the target topic $C$. We also propose a keyword
expansion method that discovers new keywords from a corpus of text documents,
$D_{tr}$.

We consider all words of the texts in $D_{tr}$ to be candidate keywords of the
target topic. Each word is represented as a vector in $\mathbbm{R}^{N}$, using
a word2vec222http://vectors.nlpl.eu/explore/embeddings/en/ [28] model, that
has been trained on the whole Wikipedia corpus. To decide whether a candidate
word $w$ is a new keyword, we measure a semantic score $CS(w)$, as the average
cosine similarity of $w$ with each of the existing keywords in $KS$.

If the semantic score exceeds a given threshold $b$, $CS(w_{i})>b$, then
$w_{i}$ is regarded as a keyword and is stored in another keyword set
$K^{\prime}$. At the end of this process, the selected keywords are combined
with those of the initial set: $K=KS\cup K^{\prime}$. In this paper, we set
the threshold $b$ to the average cosine similarity of all $k\in KS$. More
formally:

$\displaystyle
b=\frac{1}{N_{K}(N_{K}-1)}\sum\limits_{i=1}^{N_{K}}{\sum\limits_{j\neq
i}^{N_{K}}}{cos(k_{i},k_{j})}$ (2)

We present our keyword expansion strategy in Algorithm 1. The strategy is
highly selective, since a new keyword must have a greater $CS$ score than some
keywords in $KS$. This comes in contrast to the TF-IDF schema for crawling
[22] and TextRank [27], which are not as selective as ours and result in
retrieving many irrelevant keywords with low $CS$ scores, as we have seen in
some preliminary experiments.

Algorithm 1 Keyword Expansion Strategy

Input: Initial keyword set $KS$ of size $N_{K}$, a corpus of text documents
$d_{tr}$
Output: the expanded keyword set $K$

1:Initialize empty keyword set $K^{\prime}=\\{\\}$

2:Create a set $W$ of all words in $D_{tr}$

3:for $w\in W$ do

4: if $\frac{1}{N_{K}}\sum\limits_{k\in KS}cos(w,k)\geq b$ then
$\triangleright$ Equation (2)

5: append $w$ in $K^{\prime}$

6: else

7: continue

8: end if

9:end for

10:$K=KS\cup K^{\prime}$

###  3.4 Learning the Reward Function

In the RL setting, the agent adjusts its policy in order to learn the given
task which is equivalent to maximizing the expected reward. However, in order
for the agent to be able to learn the task, rewards must be accurate enough to
indicate the optimal state transitions. Given a dataset of web pages
$D_{tr}\subseteq D_{C}\cup D_{C^{\prime}}$, a keyword set $K$, a maximum text
length $M$ and the word embedding space $\mathbb{R}^{N}$, we seek a
classification function $f:K\times M\times\mathbb{R}^{N}\rightarrow\\{0,1\\}$
which plays the role of our reward function.

Let $D^{(C)}_{tr}\subset D_{C}$ be the set of relevant documents and
$D^{(C^{\prime})}_{tr}\subset D_{C^{\prime}}$ be the set of irrelevant
documents. In reality, the irrelevant documents are much more than the
relevant ones, and we therefore assume that
$|D^{(C)}_{tr}|<a|D^{(C^{\prime})}_{tr}|$, where $a<1$. In our experiments,
$a\leq 0.1$ and thus the majority (irrelevant) class has at least 9 times more
instances than the minority class. We also assign target label $1$ to
$D^{(C)}_{tr}$ and target label $0$ to $D^{(C^{\prime})}_{tr}$. To address
this web page classification task, we propose KwBiLSTM, which is a
Bidirectional Long short-term memory (BiLSTM) method [17], empowered by the a
priori knowledge of the expanded keyword set $K$. Our model structure is shown
in Fig. 1.

Figure 1: KwBiLSTM diagram

We start by pre-processing each text (web page) in $D_{tr}$: (a) we remove the
words/phrases belonging to a list of stopwords, (b) we tokenize the remaining
text, (c) we match each word token to a word2vec embedding vector in
$\mathbb{R}^{N}$, and (d) we create a text matrix $\boldsymbol{T}$ of $M$
rows, where $M$ is a parameter of the algorithm, specifying the length of the
documents. In texts that contain more than M words, we keep the first M of
them and discard the rest, on the grounds that a lot of useful information
(such as the web page title) is usually written first in the web page text. So
for each text, M embedding vectors are produced in total and gathered into
$\boldsymbol{T}$. Texts that are shorter than M words are zero-padded, using a
masking layer (before the BiLSTM layer).

KwBiLSTM takes two inputs; an array of word embeddings ($\boldsymbol{T}$),
which is the word2vec representation of the candidate web page text, and a
three-dimensional vector, the Keyword Vector $\boldsymbol{KV}$. Let $\mu$ be
the average number of keywords found in the text of the relevant documents of
the dataset ($D^{(C)}_{tr}$) and $count(p)$ be the number of keyword
appearances in a web page text $p$, which is of length $n_{p}$. For a document
(web page text) $p$, $\boldsymbol{KV}(p)$ contains (a)
$min\\{count(p)/\mu,1\\}$, (b) $count(p)/n_{p}$ and (c) a feature representing
a keyword appearance that are found as part of the URL of the web page.

Intuitively, the use of the Keyword Vector (Fig. 1) highlights the aggregated
information of keywords found during prediction. We found that even in cases
where the text length is relatively small, this is very useful: e.g. when
predicting a web page utilizing only its title or an anchor text. To train the
model we minimize the Cross-Entropy loss.

###  3.5 Focused Crawling with Reinforcement Learning

In this subsection, we describe our RL focused crawler agent and the process
of learning good Q-value approximations for selecting available URLs from the
frontier. Our approach is divided into three parts: (a) representing the
states and the actions, (b) efficiently selecting URLs from the frontier, and
(c) training the agent with an RL algorithm.

####  3.5.1 State-Action Representation

Similar to [18], we propose a shared state-action representation. Let
$\boldsymbol{x}(s_{,}a_{t})$ be the shared representation vector for a given
state $s_{t}$ and an action $a_{t}$ at timestep $t$. Recall that an available
action $a$ (at timestep $t$) is related to a URL $u$ in the corresponding
frontier, $F_{t}$, such that $a=(u^{(\tau)},u)$, where $\tau$ is the timestep
when the crawler fetched $u^{(\tau)}$ and $u$ is one of the outlinks of
$u^{(\tau)}$, that is $u\in\text{Outlink}(u^{(\tau)})$.

Figure 2: A simple state and action example: This state contains the nodes
Seed, A, B and C, while the edge (C, D) is an action for this state.

To represent the state $s_{t}$ in $\boldsymbol{x}(s_{t},a_{t})$ given the
action $a_{t}$ and the web page $u^{(\tau)}$ that was fetched by the crawler
at timestep $\tau$ and that extracted the URL of this action, we simply
aggregate information of $path(\tau)$; i.e. the web path leading to URL
$u^{(\tau)}$. Specifically, we use the following scalar state features: the
reward received at $\tau$, the inverse of the distance of $u^{(\tau)}$ from
the closest relevant node in $path(\tau)$ and the relevance ratio [18] of
$path(\tau)$. Intuitively, these features describe the relevance of the web
path that is related to a given outlink URL.

To represent $a_{t}$ in $\boldsymbol{x}(s_{t},a_{t})$, similar to [18], we use
the following scalar features: the existence of keywords in the URL text, the
existence of keywords in the anchor text of the source page and a probability
estimation of its relevance given by KwBiLSTM, based on the web page title. A
web page belonging to a relevant web site is likely to lead to other relevant
ones, even if this particular page is not relevant. The web pages with this
property are known as hubs [34]. We introduce two hub features, which are the
following scalar action features: (a) the ratio of the relevant webpages of
the URL domain found until timestep $t$ and (b) the unknown domain relevance
which is set to $0.5$ if the specific web site (domain) has not been visited
before, otherwise $1$. Hub features are used on the assumption that the
crawler is more likely to fetch more relevant web pages by trying to avoid
less relevant or unknown domains.

An example of a state-action pair is depicted in Fig. 2. In this example, we
examine crawling in the Sports domain. Starting from one seed URL, the crawler
has fetched two relevant web pages (A, C) and one irrelevant (B). The current
state is the Web subgraph containing the seed and the web pages A, B and C.
The crawler examines the candidate action of fetching web page D. We also
present the state-action representation of the current state and the candidate
action. In the state representation, the parent node reward is zero (C is not
relevant), the distance of last relevant node (A) is 2 and the relevance ratio
of the web path (seed, A, C) is $2/3$ (the relevant nodes in the web path are
the seed and A). In the action representation, no keywords are found in either
the anchor text or the URL text of D and this accounts for the first two zero
entries. Moreover, the estimation of relevance produced by the KwBiLSTM is
$0.3$. The hub features are $3/4$ and 1. The former is due to the fact that in
this domain (en.wikipedia.org) the crawler has identified 3 relevant URLs and
1 not relevant. The latter, which equals 1, implies that this domain
(en.wikipedia.org) has been fetched at least once. Otherwise, the second hub
feature would have been $0.5$.

####  3.5.2 Training with Reinforcement Learning

In our setting, the focused crawler is an RL agent operating on the MDP
described in Section 3.2. Here, we utilize the Double Deep Q-Network (DDQN)
[19] agent; though other model-free RL agents that estimate Q-values on a
state-action input could be also used in its place. Let $\hat{Q}$ be the
neural network estimation of the state-action value function of the agent’s
policy. Specifically, let $\boldsymbol{\theta}$ be the parameters of the
online Q-Network and $\boldsymbol{\theta}^{-}$ the parameters of the target
Q-Network of DDQN. Then, given a record
$(\boldsymbol{x}(s_{t},a_{t}),r_{t+1},s_{t+1})$ from Experience Replay $B$
[29], that is utilized in Deep Q-learning settings for sampling past state
transitions, the DDQN target [19] can be written as

$y_{t}=r_{t+1}+\gamma\hat{Q}_{\boldsymbol{\theta}^{-}}\Big{(}\boldsymbol{{x}}\big{(}s_{t+1},\operatorname*{arg\,max}_{a^{\prime}\in\tilde{A}_{s_{t+1}}}\hat{Q}_{\boldsymbol{\theta}}(\boldsymbol{{x}}(s_{t+1},a^{\prime}))\big{)}\Big{)}$

where $\tilde{A}_{s_{t+1}}$ is the set of actions extracted at timestep $t+1$;
i.e.
$\tilde{A}_{s_{t+1}}=\\{(u^{(t+1)},u^{\prime}):u^{\prime}=Outlink(u^{(t+1)})\\}$,
with $u^{(t+1)}$ being the web page fetched at timestep $t+1$. Also, let
$s_{-1}$ be the empty graph. Then, we initialize $B$ leveraging the experience
from seeds $U_{S}$, using zero state features in $\boldsymbol{x}(s_{-1},a)$
and positive rewards. Note that for each seed URL the action features in
$\boldsymbol{x}(s_{-1},a)$ are related to selecting this URL as the next
action. This initialization can speed up training, in cases where a lot of
seeds are given as input and/or positive rewards are sparse during
exploration. Next, we minimize
$\dot{L}={\mathbb{E}}_{U(B)}\left[y_{t}-\hat{Q}_{\boldsymbol{\theta}}\left(\boldsymbol{{x}}(s_{t},a_{t})\right)\right]^{2}$,
with respect to $\boldsymbol{\theta}$ by performing gradient descent steps on
mini-batches of size $B$. We note that the function approximators used to
produce $\hat{Q}$ for both the online and target Q-Networks are standard
Multilayer Perceptrons with two hidden layers.

###  3.6 Synchronous Frontier Update

In this section we discuss which action $a\in\tilde{A}_{t}$ is selected at a
given timestep $t$. In a common Deep Q-learning setting, an $\epsilon$-greedy
policy is often used [29, 19], which results in calculating the estimated
Q-values of all actions of a given state.

In a focused crawling setting, it is common to implement the frontier as a
priority queue, with the priority values being the estimated Q-values of all
actions. In that case, for each timestep, updating $\boldsymbol{\theta}$
requires a synchronous update [18]. Let $P_{DDQN}$ be the time of a single
DDQN prediction and $d(t)=\left|u:u\in Outlink(u^{(t)}),u\not\in C_{t}\right|$
be the number of new URLs inserted in the frontier at timestep $t$.

######  Theorem 1.

Assuming that for each timestep the frontier size grows at least by $e_{d}$
and $d(t)\geq e_{d}\geq 1$, let $F_{0}$ be the frontier instance because of
seeds $U_{S}$. Then a synchronous update has an overall time complexity at
least $P_{DDQN}[(F_{0}+\frac{e_{d}}{2})T+\frac{e_{d}}{2}T^{2})]$.

Theorem 1 (see proof in Appendix A) indicates that a synchronous update is
costly and, thus, impractical.

###  3.7 Updating and Sampling through Tree-Frontier

To reduce the time complexity of a synchronous update, we introduce Tree-
Frontier, a two-fold variation of the CART decision tree algorithm. In Tree-
Frontier, frontier $F_{t}$ has now a decision tree representation, where each
frontier element is assigned to a leaf. Decision trees have been used in RL to
find a discretization of a large state space by recursively growing a state
tree [38]. The set of tree leaves forms a partition of the initial state
space. By splitting tree nodes, narrower convex regions are created, in which
the agent behaves in a predictable way.

In our case, each partition corresponds to a group of frontier samples of the
form $\boldsymbol{x}(s,a)$. In order to arrive at a meaningful partitioning,
we borrow concepts from Explainable Reinforcement Learning (XRL), where
decision trees are often used to provide interpretable policy approximations
[40, 23, 6]. Specifically, Bewley and Lawry [6] proposed a binary decision
tree providing MDP state abstraction through a linear combination of three
impurity measures: the action selected, the expected sum of rewards, and the
estimated state temporal dynamics. This way, they identified convex regions of
the state space that are as pure as possible, in terms of the above criteria.
Furthermore, to address the problem of allocating memory for huge continuous
state spaces, Jiang et al. [21] utilized a decision tree for learning the
environment dynamics which also played the role of the experience replay
buffer [29] of an RL agent for generating simulated samples.

We are interested in discretizing simultaneously both the state and the action
spaces, which are defined in potentially continuous vector spaces. We
distinguish two different kinds of samples in the frontier. For a given
timestep $t$, let experience samples be those $\boldsymbol{x}$ representation
vectors that were selected at previous timesteps $\tau<t$, and thus we have
received their respective rewards $r_{\tau+1}$, and let frontier samples be
the $\boldsymbol{x}$ representation vectors belonging to $F_{t}$. Combining
the above, let $D_{E}(t)=\\{\left(\boldsymbol{x}(s_{0},a_{0i}),1\right)\colon
1\leq
i\leq|U_{S}|\\}\cup\\{\left(\boldsymbol{x}(s_{{\tau}},a_{{\tau}}),r_{{\tau+1}}\right)\colon\tau<t\\}$
be the set of experience samples (including seeds) at timestep $t$. Similarly,
let $D_{F}(t)=\\{\boldsymbol{x}\colon\boldsymbol{x}\in F_{t}\\}$ be the set of
frontier samples at timestep $t$ given $F_{t}$.

Algorithm 2 Tree-Frontier update at timestep $t$

Input: Tree-Frontier $F_{t}$, $D_{E}(t)$, $D_{F}(t)$, new experience sample
$e_{new}=\left(\boldsymbol{x}(s_{t},a_{t}),r_{{t+1}}\right)$, new frontier
samples $f_{new}$
Output: a state-action $\boldsymbol{x}$, $D_{E}(t+1)$ and $D_{F}(t+1)$

1:Update $D_{E}(t+1)=D_{E}(t)\cup e_{new}$

2:Update $F_{t+1}$ from $F_{t}$: check for split on leaf $P$, that contains
$e_{new}$, using equations (3) and (4)

3:Update $D_{F}(t+1)=D_{F}(t)\cup f_{new}$ by inserting each sample in
$f_{new}$ to a leaf in $F_{t+1}$ following the tree rules

4:Select a representantive frontier sample $\boldsymbol{x}_{i}$ from each leaf
through uniform sampling and remove it from the tree

5:if exploration mode: then $\boldsymbol{x}=$
$\text{UniformSampling}(\boldsymbol{x}_{i})$

6:else:
$\boldsymbol{x}=\operatorname*{arg\,max}_{i}\hat{Q}_{\boldsymbol{\theta}}(\boldsymbol{x}_{i})$

7:end if

Algorithm 3 Tree REinforcement Spider (TRES)

Input: Seed set $U_{S}$, initial keyword set $KS$, a dataset of web pages
$D_{tr}$, the total number of URL fetches $T$
the maximal number of domain visits $MAX$
Output: a list $\boldsymbol{res}$ of the fetched URLs

1:KS = KeywordExpansionStrategy($KS$, $D_{tr}$) $\triangleright$ Algorithm 1

2:Learn the reward function $R$, by training a KwBiLSTM using $D_{tr}$ and $K$

3:Initialize state $S_{0}=g_{0}$ leveraging the experience from the relevant
URLs in $U_{S}$

4:Initialize experience samples $D_{E}(0)$ and frontier samples $D_{F}(0)$
using the seed set $U_{S}$

5:Initialize closure $C_{0}$ and Tree-Frontier $F_{0}$ using $D_{E}(0)$ and
$D_{F}(0)$

6:Initialize timestep counter $t=0$

7:Initialize $e_{new}=\\{\\}$ and $f_{new}=\\{\\}$

8:Initialize Experience Replay buffer $B$ with experience samples $D_{E}(0)$

9:Initialize an empty list $\boldsymbol{res}$

10:while $t<T$ do

11: Train the DDQN agent on a minibatch of $B$

12: Get a state-action $\boldsymbol{x}(s_{t},a_{t})$, $D_{E}(t+1)$ and
$D_{F}(t+1)$ = TreeFrontierUpdate($F_{t}$, $D_{E}({t})$, $D_{F}({t})$,
$e_{new}$, $f_{new}$) s.t:

13: $a_{t}\rightarrow$ URL $u^{(t+1)}\not\in C_{t}$ and $MAX$ condition holds
$\triangleright$ Algorithm 2

14: Transition to a new state $S_{t+1}=g_{t+1}$ by expanding $g_{t}$ with the
edge $a_{t}$

15: Fetch URL $u^{(t+1)}$ and observe its reward $r_{t+1}$

16: Extract outlink URLs $Outlink(u^{(t+1)})$ to create new frontier samples
$f_{new}$

17: Create new experience sample
$e_{new}=(\boldsymbol{x}(s_{t},a_{t}),r_{t+1})$

18: Update experience replay buffer $B$ with $e_{new}$

19: Update closure $C_{t+1}$ with the new fetched URL $u^{(t+1)}$

20: Append $u^{(t+1)}$ to $\boldsymbol{res}$

21: $t=t+1$

22:end while

We propose a novel online binary decision tree algorithm, called Tree-
Frontier, in order to efficiently represent and manipulate the frontier. As
mentioned earlier, Tree-Frontier is two-fold; for a given timestep $t$, based
on the splitting rules, a tree node stores both a subset of $D_{E}(t)$ and a
subset of $D_{F}(t)$. These sets are effectively the labeled (“training”) and
unlabeled (“prediction”) ones. Tree-Frontier uses the experience samples,
$D_{E}(t)$, in order to split nodes, utilizing their rewards as target labels.
For a given frontier sample (a state-action vector), Tree-Frontier is used to
predict the agent’s reward. Let $I_{P}$ be the subset of experience samples of
$D_{E}(t)$ that belong to a tree leaf $P$. To split this leaf, we seek binary
partitions $I_{P}=\\{I_{L},I_{R}\\}$, such that for some state-action feature
$f$ and numerical threshold $c\in\mathbb{R}$:

$(\boldsymbol{x}^{(f)}<c:\forall\boldsymbol{x}\in
I_{L})\cap(\boldsymbol{x}^{(f)}\geq c:\forall\boldsymbol{x}\in I_{R})$ (3)

where $\boldsymbol{x}^{(f)}$ is the f-th element (feature) of the state-action
representation vector $x$. Let $V(P)$ be the reward sample variance of node
$P$. Borrowing from XRL [23] and unlike CART, we use as splitting criterion
the weighted sample variance reduction $VR(P,f,c)$ of the rewards in $P$. That
is:

$VR(P,f,c)=V(P)-\frac{|L|}{|P|}V(L)-\frac{|R|}{|P|}V(R)$ (4)

For each new experience sample in leaf $P$, Tree-Frontier checks for candidate
partitions only in $P$. If no partition with positive $VR(P,.,.)$ exists, no
split is made. Else, we select the partition of $P$ that causes the highest
reduction. In this sense, Tree-Frontier follows an online best-first strategy,
unlike CART that follows a depth-first growth strategy.

To partition the frontier samples of the splitting leaf $P$ into the two new
leaves derived from $P$, we simply follow the same splitting tree rules as the
experience samples. Similarly, we follow these rules to insert the new
frontier samples in Tree-Frontier. To sum up, we utilize the experience
samples to create splitting rules and we follow these rules to partition the
frontier samples.

Figure 3: An example of a Tree-Frontier update

At a given timestep $t$, instead of calculating the estimated Q-values of all
frontier samples, we select one representative from each leaf through uniform
sampling. Thus, we calculate the estimated Q-values of only those
representatives and select the action with the highest Q-value. We call this
procedure Tree-Frontier update. We present the Tree-Frontier update algorithm
for a given timestep $t$ in Algorithm 2. In Fig. 3, we demonstrate an example
of Tree-Frontier update. The three red nodes correspond to leaves. From each
leaf, we perform uniform sampling on frontier samples (F) and then select the
sample with the highest estimated Q-value (argmax operation).

######  Theorem 2.

A Tree-Frontier update has an overall time complexity at most
$P_{DDQN}(1+\frac{3}{2}T+\frac{1}{2}T^{2})$.

Theorem 2 (see proof in Appendix A) implies that a tree-frontier update has a
better time complexity than a synchronous update.

We present the mathematical analysis of TRES in Appendix B. The full focused
crawling procedure of the proposed TRES framework is presented in Algorithm 3.

##  4 Experimental Evaluation

In this section, we assess the effectiveness of TRES through experiments on
real-world data and comparisons with state-of-the-art crawlers. In particular,
the experiments are on the following topics: (a) Sports, (b) Food, (c)
Hardware, all belonging to Open Directory Project (Dmoz)333https://dmoz-
odp.org/, which has been used widely for crawling evaluation [22, 39, 13, 5].
Dmoz indexes about five million URLs covering a wide range of topics [22].
Note that each topic is not equally represented by URLs in Dmoz; we assume a
topic is as difficult to be crawled as it is to be found in Dmoz. Therefore,
we expect the Hardware domain to be the most difficult of the three.

Unlike common (but less realistic) experimental settings, such as [4, 36],
that use a lot of seeds, for each experiment we utilize a single seed and
average results from 10 different single-seed crawling runs. Seeds are
selected using Google search and are not connected to each other. In other
words, none of the seeds contains a hyperlink to any other seed.

The training set of irrelevant web pages, $D_{tr}^{(C^{\prime})}$, consists of
URLs from 10 Dmoz supertopics: Arts, Business, Computers, Health, News,
Recreation, Reference, Science and Sports. In cases where the relevant topic,
$C$, is one of the aforementioned supertopics (e.g. Sports), we remove its web
pages from the training set of irrelevant web pages. One the other hand,
similar to [32], if the relevant topic, $C$, is a subcategory of one of these
supertopics (e.g. Food and Hardware), there is only a small chance that the
web pages of the supertopics belong to the target topic. Specifically, we use
approximately $1200$ and $1800$ samples for the training set of relevant web
pages, $D_{tr}^{(C)}$, and for each supertopic in $D_{tr}^{(C^{\prime})}$,
respectively.

Classifier | Sports | Food | Hardware
---|---|---|---
| Precision | Recall | F-macro | Precision | Recall | F-macro | Precision | Recall | F-macro
Plain BiLSTM | 90.1 | 88.3 | 93.2 | 85.6 | 88.2 | 92.6 | 83.2 | 81.4 | 90.6
ACHE’s SVM | 76.9 | 88.5 | 90.4 | 68.5 | 81.8 | 86.7 | 62.6 | 77.0 | 83.9
KwBiLSTM | 91.3 | 90.7 | 95.4 | 87.0 | 90.8 | 94.2 | 80.0 | 86.2 | 90.8
TABLE I: Classication Results: Precision (%) (relevant class), Recall (%) (relevant class) and F-Macro (i.e. the arithmetic mean over the F1-scores of the two classes) (%) |  Sports |  Food |  Hardware
---|---|---|---
$C$ |  19.55 |  15.46 |  17.66
$C^{\prime}$ |  0.86 |  1.04 |  1.44
# $KS$ |  62 |  10 |  11
# $K^{\prime}$ |  32 |  205 |  129
TABLE II: Mean Keyword Count of Discovered Keywords, Initial Keywords ($KS$),
Discovered Keywords ($K^{\prime}$); $C$ is the relevant topic, $C^{\prime}$
are the irrelevant topics.

###  4.1 Evaluation Metrics

For the evaluation of the crawler, we rely on the widely used harvest rate
(HR) [8] of fetched web pages. More formally:

$\displaystyle HR=\frac{\text{Number of Relevant Web Pages
Fetched}}{\text{Number of All Web Pages Fetched}}$ (5)

Observe that in our binary reward function setting the harvest rate is
equivalent to the agent’s average cumulative reward, and thus to an RL metric
[2]; measuring the harvest rate of the focused crawler is equal to measuring
the average cumulative reward of the RL agent. We also evaluate the number of
unique crawled web sites (domains), considering that a web site is relevant if
it contains at least one relevant web page. Last but not least, we examine the
computational efficiency of Tree-Frontier, in comparison to the use of
synchronous updates [18] on selecting the best action from the frontier.

###  4.2 State-Of-The-Art and Baselines

We compare TRES to the following state-of-the-art methods:

  * •

ACHE [4]: is one of the most well-known focused crawlers, which aims to
maximize the harvest rate of fetched web pages through an online-learning
policy. ACHE has been widely used in crawling evaluation, such as in [32] and
[41], and in crawling applications [31].

  * •

SeedFinder (SF) [39]: extracts new seeds and keywords from relevant pages to
derive search queries.

Furthermore, the following baseline methods are included in our experiments:

  * •

Tree-Random (TR): we propose a simplified version of TRES; it selects a random
action from a random leaf. In other words, Tree-Random only uses exploration
and selects an action with uniform sampling from the leaf representantives
(line 5 in Algorithm 2). Note that Tree-Random’s frontier is the same as in
TRES. We are interested in measuring the performance of Tree-Random, in order
to measure the effectiveness of Tree-Frontier on discretizing the state and
action spaces.

  * •

Random (R): selects URLs from the frontier at random.

###  4.3 Keyword Expansion Evaluation

First, we evaluate the TRES strategy to identify relevant keywords from a
dataset of relevant documents. Recall that an initial small keyword set $KS$
is given as input to TRES, which aims to expand it with as many other relevant
keywords as possible.

In all settings, we initialize the starting keyword set $KS$ with the keywords
provided by the Dmoz topic subcategories. We initialize $KS$ with 62, 10 and
11 keywords for each of the Sports, Food and Hardware domains, respectively.
The results of keyword expansion are shown in Table II. We observe that the
discovered keywords (keyword set $K^{\prime}$) were orders of magnitude more
frequent (on average) in web pages of the target topic $C$ than in irrelevant
web pages of $C^{\prime}$. In Food and Hardware settings $C^{\prime}$ includes
their supertopics (Recreation and Computers) with respective mean keyword
counts equal to $0.89$ and $6.67$. Thus, the discovered keywords are orders of
magnitude more frequent in $C$ than in their supertopics (if existent).

Moreover, notice that the proposed keyword expansion method discovered many
new relevant keywords, especially in the Food and Hardware topics, despite the
relatively small number of initial given keywords. On the other hand, in the
Sports setting our method retrieved 32 new keywords, and thus enlarged $KS$
only by 50%. We attribute this to the fact that in the Sports setting the
number of the input keywords was six times bigger than in the other evaluated
settings, and as a result a candidate keyword was more difficult to produce a
mean cosine similarity score higher than the defined threshold. This also
supports the highly selective behavior of our keyword set expansion method,
when the number of the input keywords (selected by the user) is not too small.

###  4.4 Web Page Classification Evaluation

To evaluate the proposed web page classification model, KwBiLSTM, we performed
stratified 5-fold cross validation on data set $D_{tr}$. Recall that KwBiLSTM
plays the role of the reward function of the crawler agent. As shown in Table
I, we measure Precision and Recall of the relevant class and Macro-average
F-Score (F-Macro). We use ACHE’s SVM and a Plain BiLSTM (does not include a
Keyword Vector) as baseline methods. In all three settings, KwBiLSTM
outperforms both baselines in almost all evaluation metrics. Notice that our
model performs worse in the Hardware setting, than the other settings, because
the irrelevant class includes its supertopic, Computers, the web pages of
which consistently include relevant keywords (6.67 on average).

Focused Crawler |  Sports |  Food |  Hardware
---|---|---|---
|  HR |  Domains |  HR |  Domains |  HR |  Domains
ACHE |  54.43 |  2081 |  60.45 |  2153 |  49.25 |  940
SeedFinder |  56.05 |  1842 |  60.16 |  3642 |  38.68 |  1314
Random |  3.55 |  17 |  8.97 |  59 |  1.66 |  28
Tree-Random |  60.01 |  204 |  36.60 |  523 |  40.63 |  354
TRES |  97.43 |  83 |  95.59 |  78 |  93.64 |  55
ACHE_100 |  47.57 |  4574 |  50.85 |  3820 |  42.18 |  1923
SeedFinder_100 |  49.97 |  4032 |  57.49 |  5043 |  31.14 |  2255
TRES_100 |  94.19 |  286 |  97.55 |  301 |  88.40 |  420
ACHE_10 |  36.79 |  6084 |  - |  - |  - |  -
SeedFinder_10 |  37.70 |  5774 |  46.96 |  6742 |  19.63 |  2832
TRES_10 |  84.52 |  2335 |  94.56 |  2604 |  63.14 |  1977
TRES_5 |  78.56 |  4053 |  90.98 |  4324 |  46.57 |  2956
TABLE III: Focused Crawling Evaluation Results

(a)

(b)

(c)

Figure 4: Frontier Sampling: Number of Tree-Frontier leaves over time (a),
Frontier size over time (b), Frontier size to Tree-Frontier leaves number
ratio (c)

###  4.5 Focused Crawling Evaluation

For crawling evaluation, we use the trained KwBiLSTM as ground-truth to
classify the fetched web pages. Table III presents the focused crawling
results for all three topics, in terms of harvest rate and the number of
domains (different web sites) fetched. For all experiments, we set the total
number of fetched web pages equal to 20,000. Considering the constraint that
the crawler can fetch at most $MAX$ web pages from a domain (web site), we
divide our experiments into three categories: (a) $MAX=\infty$ (i.e. 20,000)
(rows: 1-5), (b) $MAX=100$ (rows: 6-8) and (c) $MAX=10$ (rows: 9-12). As shown
in Table III, for all evaluated values of $MAX$, our TRES consistently
outperforms by a large margin the other methods, in terms of harvest rate.
Specifically, it outperforms them by at least: 58% in $MAX=\infty$, 94% in
$MAX=100$ and 110% in $MAX=10$.

Additionally, our baseline Tree-Random performs on a par with both ACHE and
SeedFinder in harvest rate. In particular, Tree-Random outperforms both state-
of-the-art methods in the Sports domain and only SeedFinder in the Food
domain. The harvest rate score of Tree-Random reflects the relevance ratio of
the leaves of Tree-Frontier, which appears higher than the relevance ratio of
a traditional frontier. The lower harvest rate scores of the evaluated methods
could be attributed to the fact that these methods quickly level off when
fewer relevant web sites are found, since they rely on the relevant web sites
that are already discovered [32].

Comparing the harvest rates of Tree-Random and the Random crawler in the
Sports topic, we observe that the former achieves $60.01\%$ and the latter
$3.55\%$. This means that the true percentage of relevant URLs were on average
$3.55\%$ in the frontier, yet the probability of selecting a leaf of Tree-
Frontier leading to a relevant URL is $60.01\%$. Thus, in such a scenario,
Tree-Frontier generated a lot of leaves, in which the agent demonstrated on
average the desirable behavior, despite the fact that there were on average 27
times more actions (assuming a similar frontier distribution with Random
crawler), leading to irrelevant URLs, in the frontier.

Furthermore, we demonstrate the effect of $MAX$ on the trade-off between
harvest rate and the number of domains fetched. In particular, the state-of-
the-art methods proved to be more exploratory and discovered a greater number
of relevant domains than TRES. This is because our TRES was neither optimized
to fetch different domains, nor to discover further seeds, as SeedFinder does.
On the other hand, as $MAX$ decreases, TRES discovers more relevant domains
while retaining a good harvest rate. Specifically, in $MAX=10$, ACHE ended
pre-maturely, as it run out of URLs to crawl, and thus we could not provide
its average results, since it did not retrieve the defined number (20,000) of
web pages. We note that similar experimental problems of ACHE have been
observed in previous works [32], e.g. when the method is bootstrapped by a
small seed set.

We also include the experiments of $MAX=5$ for TRES. Notice that in the
Hardware topic, TRES (TRES_5) manages to outperform all evaluated methods,
with $MAX=10$, both in the harvest rate and in the number of fetched domains.
We note that both ACHE and SeedFinder failed to retrieve the defined number
(20,000) of web pages and again we could not provide the corresponding
results.

###  4.6 Tree-Frontier vs Synchronous Update

The use of the Tree-Frontier updates facilitate efficient sampling of the
frontier, improving by orders of magnitude the computationally infeasible
problem of synchronous updates, which exhaustively examines every frontier
sample in each timestep, while allowing a good performance. Fig. 4 illustrates
the behavior of TRES as the crawling progresses. The size of the subset of the
frontier that TRES examines at each timestep is orders of magnitude smaller
than the full frontier size. This leads to a corresponding reduction in
execution time, which however is hard to measure, due to the infeasible cost
of running the synchronous update method.

Focused Crawler |  Sports |  Food |  Hardware
---|---|---|---
|  HR |  Domains |  HR |  Domains |  HR |  Domains
TRES_10_NH |  82.17 |  2393 |  94.22 |  3189 |  58.89 |  2080
TRES_10 |  84.52 |  2335 |  94.56 |  2604 |  63.14 |  1977
TABLE IV: Evaluation of Hub Features in the state-action representation

In Fig. 4, we can also observe that the dependence of the frontier size and
the number of leaves (in Tree-Frontier) to the number of timesteps is not
exactly linear. In the case of the full frontier (synchronous update) this is
attributed to the variance in the number of outlinks that a web page could
contain. There is an oscillation around the mean outlink number, which would
ideally be equal to the slope of curve (see Fig. 4, subplot (b)), had there
been no variance in the random variable of the number of outlink URLs (of a
web page). In the case of Tree-Frontier (see Fig. 4, subplot (a) anc (c)), the
variance of the slope is due to the fact that at some timesteps no split is
performed and, thus, the number of leaves remains the same. At other
timesteps, binary splits may occur, increasing the size of the set of the
candidate frontier samples that we examine.

It is worth mentioning that the Tree-Frontier update approach could be also
employed in other RL settings. Tree-Frontier effectively tackles the
exponential increase in the size of the action space, by reducing the number
of actions that are examined at each timestep, that is the number of samples
for which Q-values are calculated. A Tree-Frontier update is performed in a
stratified way through an online discretization of both large state and action
spaces. Therefore, in an RL setting with rampant action space growth
(frontier), the Tree-Frontier algorithm could potentially be preferable to an
exhaustive calculation of Q-values.

###  4.7 Effect of hub features

The use of hub features is based on the intuition that the focused crawler is
more likely to fetch more relevant web pages by trying to avoid less relevant
or unknown web sites (domains). In Table IV, we show the trade-off between
maximizing the harvest rate of web pages and maximizing the number of
different domains. We evaluate TRES with $MAX=10$ with and without the hub
features (TRES_10 and TRES_10_NH, respectively). We present the evaluation on
the $MAX=10$ setting, where TRES performs on a par with the other methods in
the domain maximization task. We observe that the use of Hub features boosts
the harvest rate performance in all evaluated topic settings, while the
absence of these features helps increase the number of different domains.

Recall that hub features describe the expected relevance of a domain (web
site) for the current iteration of the algorithm. The use of hub features
leads the crawler to choose more likely relevant URLs from the frontier,
ignoring the fact that they may belong to a fetched domain. On the other hand,
their absence allows the crawler to be more explorative towards new domains,
trying to identify new relevant locations on the Web.

##  5 Conclusion

In this paper, we proposed an end-to-end reinforcement learning focused
crawling framework that outperforms state-of-the-art methods on the harvest
rate of web pages. We formalized focused crawling as a Markov Decision
Process, in which the agent necessarily follows the successive order of state
transitions and selects actions (related to URLs) that are explicitly
available in current state (related to the Web graph). In addition, we
improved the impractical time complexity of synchronous updates through the
use of Tree-Frontier that we introduced. A Tree-Frontier update handles the
large state and action spaces through adaptive discretization, while at the
same time facilitating efficient sampling of the frontier, improving by orders
of magnitude the computationally infeasible problem of a synchronous update.

As a future work, we would like to investigate the addition of an intrinsic
reward, in order to enhance agent’s exploration in order to visit a larger
number of relevant domains. An additional open question is the minimization of
the size of the labeled data set needed to train the classifier, which is used
in turn to estimate the reward function.

## Acknowledgments

This research has received no external funding.

## References

  * [1] W. Ali and M. Hassoun, “Artificial intelligence and automated journalism: Contemporary challenges and new opportunities,” _International journal of media, journalism and mass communications_ , vol. 5, no. 1, pp. 40–49, 2019\.
  * [2] E. Axiotis, A. Kontogiannis, E. Kalpoutzakis, and G. Giannakopoulos, “A personalized machine-learning-enabled method for efficient research in ethnopharmacology. the case of the southern balkans and the coastal zone of asia minor,” _Applied Sciences_ , vol. 11, no. 13, 2021. [Online]. Available: https://www.mdpi.com/2076-3417/11/13/5826
  * [3] L. Barbosa, S. Bangalore, and V. K. Rangarajan Sridhar, “Crawling back and forth: Using back and out links to locate bilingual sites,” in _Proceedings of 5th International Joint Conference on Natural Language Processing_. Chiang Mai, Thailand: Asian Federation of Natural Language Processing, Nov. 2011, pp. 429–437. [Online]. Available: https://aclanthology.org/I11-1048
  * [4] L. Barbosa and J. Freire, “An adaptive crawler for locating hidden-web entry points,” in _Proceedings of the 16th International Conference on World Wide Web_ , ser. WWW ’07. New York, NY, USA: Association for Computing Machinery, 2007, p. 441–450. [Online]. Available: https://doi.org/10.1145/1242572.1242632
  * [5] S. Batsakis, E. G. Petrakis, and E. Milios, “Improving the performance of focused web crawlers,” _Data & Knowledge Engineering_, vol. 68, no. 10, pp. 1001–1013, 2009. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0169023X0900055X
  * [6] T. Bewley and J. Lawry, “Tripletree: A versatile interpretable representation of black box agents and their environments,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 13, pp. 11 415–11 422, May 2021. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/17360
  * [7] S. Chakrabarti, K. Punera, and M. Subramanyam, “Accelerated focused crawling through online relevance feedback,” in _Proceedings of the 11th International Conference on World Wide Web_ , ser. WWW ’02. New York, NY, USA: Association for Computing Machinery, 2002, p. 148–159. [Online]. Available: https://doi.org/10.1145/511446.511466
  * [8] S. Chakrabarti, M. van den Berg, and B. Dom, “Focused crawling: a new approach to topic-specific web resource discovery,” _Computer Networks_ , vol. 31, no. 11, pp. 1623–1640, 1999. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1389128699000523
  * [9] M. Cui and D. Y. Zhang, “Artificial intelligence and computational pathology,” _Laboratory Investigation_ , vol. 101, no. 4, pp. 412–422, 2021\.
  * [10] B. D. Davison, “Topical locality in the web,” in _Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , ser. SIGIR ’00. New York, NY, USA: Association for Computing Machinery, 2000, p. 272–279. [Online]. Available: https://doi.org/10.1145/345508.345597
  * [11] Y. Du, W. Liu, X. Lv, and G. Peng, “An improved focused crawler based on semantic similarity vector space model,” _Appl. Soft Comput._ , vol. 36, no. C, p. 392–407, nov 2015. [Online]. Available: https://doi.org/10.1016/j.asoc.2015.07.026
  * [12] N. Eiron, K. S. McCurley, and J. A. Tomlin, “Ranking the web frontier,” in _Proceedings of the 13th International Conference on World Wide Web_ , ser. WWW ’04. New York, NY, USA: Association for Computing Machinery, 2004, p. 309–318. [Online]. Available: https://doi.org/10.1145/988672.988714
  * [13] M. Elaraby, S. M. Abuelenin, H. M. Moftah, and M. Z. Rashad, “A new architecture for improving focused crawling using deep neural network,” _J. Intell. Fuzzy Syst._ , vol. 37, pp. 1233–1245, 2019.
  * [14] G. Giannakopoulos, G. Kiomourtzis, N. Pittaras, and V. Karkaletsis, “Scaling and semantically-enriching language-agnostic summarization,” in _Trends and Applications of Text Summarization Techniques_. IGI Global, 2020, pp. 244–292.
  * [15] Y. Gil, M. Greaves, J. Hendler, and H. Hirsh, “Amplify scientific discovery with artificial intelligence,” _Science_ , vol. 346, no. 6206, pp. 171–172, 2014.
  * [16] G. Gouriten, S. Maniu, and P. Senellart, “Scalable, generic, and adaptive systems for focused crawling,” in _Proceedings of the 25th ACM Conference on Hypertext and Social Media_ , ser. HT ’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 35–45. [Online]. Available: https://doi.org/10.1145/2631775.2631795
  * [17] A. Graves, S. Fernández, and J. Schmidhuber, “Bidirectional lstm networks for improved phoneme classification and recognition,” in _Artificial Neural Networks: Formal Models and Their Applications – ICANN 2005_ , W. Duch, J. Kacprzyk, E. Oja, and S. Zadrożny, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 799–804.
  * [18] M. Han, P.-H. Wuillemin, and P. Senellart, “Focused crawling through reinforcement learning,” in _Web Engineering_ , T. Mikkonen, R. Klamma, and J. Hernández, Eds. Cham: Springer International Publishing, 2018, pp. 261–278.
  * [19] H. v. Hasselt, A. Guez, and D. Silver, “Deep reinforcement learning with double q-learning,” in _Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence_ , ser. AAAI’16. AAAI Press, 2016, p. 2094–2100.
  * [20] J. Jiang, X. Song, N. Yu, and C.-Y. Lin, “Focus: Learning to crawl web forums,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 25, no. 6, pp. 1293–1306, 2013.
  * [21] W.-C. Jiang, K.-S. Hwang, and J.-L. Lin, “An experience replay method based on tree structure for reinforcement learning,” _IEEE Transactions on Emerging Topics in Computing_ , vol. 9, pp. 972–982, 2021.
  * [22] P. Liakos, A. Ntoulas, A. Labrinidis, and A. Delis, “Focused crawling for the hidden web,” _World Wide Web_ , vol. 19, no. 4, p. 605–631, Jul. 2016. [Online]. Available: https://doi.org/10.1007/s11280-015-0349-x
  * [23] G. Liu, O. Schulte, W. Zhu, and Q. Li, “Toward interpretable deep reinforcement learning with linear model u-trees,” in _ECML/PKDD_ , 2018\.
  * [24] H. Lu, D. Zhan, L. Zhou, and D. He, “An improved focused crawler: Using web page classification and link priority evaluation,” _Mathematical Problems in Engineering_ , vol. 2016, pp. 1–10, 2016.
  * [25] F. Menczer, R. K. Belew, J. Carbonell, Y. Yang, and W. Cohen, “Adaptive retrieval agents: Internalizing local context and scaling up to the web,” in _Machine Learning_ , 1999, pp. 200–0.
  * [26] F. Menczer, G. Pant, and P. Srinivasan, “Topical web crawlers: Evaluating adaptive algorithms,” _ACM Trans. Internet Technol._ , vol. 4, no. 4, p. 378–419, Nov. 2004. [Online]. Available: https://doi.org/10.1145/1031114.1031117
  * [27] R. Mihalcea and P. Tarau, “TextRank: Bringing order into text,” in _Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing_. Barcelona, Spain: Association for Computational Linguistics, Jul. 2004, pp. 404–411. [Online]. Available: https://aclanthology.org/W04-3252
  * [28] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word representations in vector space,” in _1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 2013, Workshop Track Proceedings_ , Y. Bengio and Y. LeCun, Eds., 2013. [Online]. Available: http://arxiv.org/abs/1301.3781
  * [29] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. A. Riedmiller, A. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, “Human-level control through deep reinforcement learning,” _Nature_ , vol. 518, pp. 529–533, 2015.
  * [30] I. Partalas, G. Paliouras, and I. Vlahavas, “Reinforcement learning with classifier selection for focused crawling,” in _Proceedings of the 2008 Conference on ECAI 2008: 18th European Conference on Artificial Intelligence_. NLD: IOS Press, 2008, p. 759–760.
  * [31] K. Pham, A. Santos, and J. Freire, “Learning to discover domain-specific web content,” in _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_ , ser. WSDM ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 432–440. [Online]. Available: https://doi.org/10.1145/3159652.3159724
  * [32] ——, “Bootstrapping domain-specific content discovery on the web,” in _The World Wide Web Conference_ , ser. WWW ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 1476–1486. [Online]. Available: https://doi.org/10.1145/3308558.3313709
  * [33] S. Rajiv and C. Navaneethan, “Keyword weight optimization using gradient strategies in event focused web crawling,” _Pattern Recognition Letters_ , vol. 142, pp. 3–10, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167865520304335
  * [34] J. Rennie and A. McCallum, “Efficient web spidering with reinforcement learning,” in _Proceedings of the International Conference on Machine Learning_ , 1999.
  * [35] A. I. Saleh, A. E. Abulwafa, and M. F. Al Rahmawy, “A web page distillation strategy for efficient focused crawling based on optimized naïve bayes (onb) classifier,” _Applied Soft Computing_ , vol. 53, pp. 181–204, 2017. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1568494616306536
  * [36] T. Suebchua, B. Manaskasemsak, A. Rungsawang, and H. Yamana, “Efficient topical focused crawling through neighborhood feature,” _New Generation Computing_ , vol. 36, pp. 95–118, 2017.
  * [37] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_. Cambridge, MA, USA: A Bradford Book, 2018.
  * [38] W. T. B. Uther and M. M. Veloso, “Tree based discretization for continuous state space reinforcement learning,” in _Proceedings of the Fifteenth National/Tenth Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence_ , ser. AAAI ’98/IAAI ’98. USA: American Association for Artificial Intelligence, 1998, p. 769–774.
  * [39] K. Vieira, L. Barbosa, A. S. Silva, J. Freire, and E. Moura, “Finding seeds to bootstrap focused crawlers,” _World Wide Web_ , vol. 19, no. 3, p. 449–474, May 2016. [Online]. Available: https://doi.org/10.1007/s11280-015-0331-7
  * [40] M. Wu, M. C. Hughes, S. Parbhoo, M. Zazzi, V. Roth, and F. Doshi-Velez, “Beyond sparsity: Tree regularization of deep models for interpretability,” in _AAAI_ , 2018.
  * [41] S. Xu, H.-J. Yoon, and G. Tourassi, “A user-oriented web crawler for selectively acquiring online content in e-health research,” _Bioinformatics_ , vol. 30, no. 1, pp. 104–114, 09 2013. [Online]. Available: https://doi.org/10.1093/bioinformatics/btt571

|  Andreas Kontogiannis is an M.Sc. student in Data Science and Machine
Learning at National Technical University of Athens (NTUA). He obtained his
joint B.Sc./M.Eng. degree in Electrical and Computer Engineering from NTUA in
2021. His research interests include Reinforcement Learning, Decision-
Theoretic Planning and Deep Learning.
---|---
|  Dimitrios Kelesis obtained his joint B.Sc./M.Eng. degree in Electrical and
Computer Engineering from National Technical University of Athens (NTUA).
Currently pursuing a PhD in Graph Neural Networks at NTUA, while working as a
research assistant in NCSR ”Demokritos”. His research interests include Graph
Neural Networks, Representational Learning, Machine Learning and Optimization.
---|---
|  Vasilis Pollatos obtained his joint B.Sc./M.Eng degree in Electrical and
Computer Engineering from National Technical University of Athens (NTUA). He
is an incoming PhD candidate at Max Planck Institute. His research interests
include Algorithms, Machine Learning and Optimization.
---|---
|  Georgios Paliouras is a Research Director of the Institute of Informatics
and Telecommunications at NCSR “Demokritos” and head of the Artificial
Intelligence (AI) laboratory SKEL. He has performed basic and applied research
in AI for the last 30 years and he has been publishing in all of the related
conferences and journals. Among various contributions to the research
community, he has served as board member in national and international
scientific societies; he is serving in the editorial board of international
journals and has chaired international conferences. He is involved in many
European and national research projects and he has the role of scientific
coordinator in some of them. He has taught postgraduate courses and has co-
founded spin-off companies.
---|---
|  George Giannakopoulos is an Artificial Intelligence researcher in NCSR
”Demokritos”, with more than 15 years of experience in natural language
processing, machine learning and big data mining, and also the application of
AI to natural sciences. He is the founder and organizer of the international
community on multilingual summarization (MultiLing), a member of Hellenic
Artificial Intelligence Society (EETN) and EurAI, as well as a member of the
European Chapter of the ACL (EACL). He is a co-founder of SciFY PNPC, not-for-
profit company for technology transfer for social good. He is also a
contributor to the EU DigitalSME Focus Group of AI, has contributed to the
Greek national AI strategy and is a member of the Greek national Sectoral
Scientific Council on AI and Data Policy.
---|---

##  Appendix A Missing Proofs of Section 3

### Proof of Theorem 1

###### Proof.

The time complexity of the frontier prediction through a synchronous update
for the whole crawling process is equal to $P_{DDQN}\cdot F$, where
$F=\sum\limits_{t=0}^{T}|F_{t}|$, $|F_{t}|$ is the frontier size at timestep =
$t$ and $P_{DDQN}$ is the time complexity of a single DDQN state-action value
function prediction. Also, let $|F_{0}|$ be the frontier size because of the
seed outlink URLs. Assuming that for each timestep the frontier size grows at
least by $e_{d}$, we can lower-bound $|F_{t}|$:

$\displaystyle|F_{t}|$
$\displaystyle=|F_{0}|+\sum\limits_{\tau=1}^{t}{d(\tau)}\geq|F_{0}|+\sum\limits_{\tau=1}^{t}{e_{d}}=|F_{0}|+te_{d}$

Thus, we can lower-bound $F$:

$\displaystyle
F=\sum\limits_{t=0}^{T}|F_{t}|\geq\sum\limits_{t=1}^{T}(|F_{0}|+te_{d})=(F_{0}+\frac{e_{d}}{2})T+\frac{e_{d}}{2}T^{2}$

Therefore, the time complexity of the frontier prediction (through synchronous
update) for the whole crawling process is at least
$P_{DDQN}((F_{0}+\frac{e_{d}}{2})T+\frac{e_{d}}{2}T^{2})$. Similarly, assuming
that $d(t)\leq D$, where $D$ is the maximal number of outlink URLs from any
web page on the Web (and thus practically $D$ and $T$ can be within the same
order of magnitude), we can upper-bound
$F\leq(F_{0}+\frac{D}{2})T+\frac{D}{2}T^{2}$.

∎

### Proof of Theorem 2

###### Proof.

The time complexity of the frontier prediction through tree-frontier update
for the whole crawling process is equal to $P_{DDQN}\cdot F_{tree}$, where
$F_{tree}=\sum\limits_{t=0}^{T}F_{tree}^{t}$ and $F_{tree}^{t}$ represents the
number of leaves at timestep $t$. Also, let $F_{tree}^{0}$ represent the
number of leaves at timestep $0$; i.e. the leaves because of splits of seed
experience samples of unity rewards. Thus, $F_{tree}^{0}=1$. Let
$d_{leaves}(t)=F_{tree}^{t}-F_{tree}^{t-1}$ be the increase of the number of
tree leaves from timestep $t-1$ to timestep $t$. Observing that at a timestep
$t$ only the tree leaf that contains the experience sample of $u^{(t)}$ (the
URL visited at $t$) can be split (if a significant difference based on sample
variance reduction of its rewards is noticed),
$d_{leaves}(t)=\mathbbm{1}{\\{\textit{a split happened at t}\\}}\leq 1$. Then,
we can upper-bound $F_{tree}^{t}$:

$\displaystyle F_{tree}^{t}$
$\displaystyle=F_{tree}^{0}+\sum\limits_{\tau=1}^{t}{d_{leaves}(\tau)}\leq
1+t$

This way, we can upper-bound $F_{tree}$:

$\displaystyle F_{tree}=\sum\limits_{t=0}^{T}F_{tree}^{t}\leq
1+\sum\limits_{t=1}^{T}(1+t)=1+\frac{3}{2}T+\frac{1}{2}T^{2}$

∎

##  Appendix B Mathematical Analysis of TRES

###  B.1 Preliminaries

Let $X$ be the state-action space, i.e. the space corresponding to the URL
representation given its path. Let $x_{t}^{*}\in X$ be the state-action vector
corresponding to the URL with the best Q-value in tree-frontier, according to
a policy approximator function (e.g. a neural network with parameters
${\boldsymbol{\theta}}$) at timestep t. Let $n_{t}$ be the number of tree-
frontier leaves at timestep t. Let $p_{t}(x_{t}^{*})=\frac{1}{|L_{t}^{*}|}$ be
the probability that at timestep t the best $x_{t}^{*}$ (according to
$\hat{Q}_{\boldsymbol{\theta}}^{(t)}$) is selected, where $L_{t}^{*}$ is the
leaf containing $x_{t}^{*}$. For brevity, we write the state-action value
function of the agent’s policy at timestep $t$, produced by the function
approximator, $\hat{Q}_{\boldsymbol{\theta}}^{(t)}$ = $\hat{Q}_{t}$. Also, let
$d_{l_{i}}^{t}$ be the distribution of i-th leaf over frontier samples at
timestep t.

We define $J=\sum\limits_{t=1}^{T}\mathop{\mathbb{E}}_{x_{t}\sim
d_{t}}\left[\hat{Q}_{t}(x_{t})\right]$ as a utility function, where
$d_{t}=\frac{1}{n_{t}}\sum\limits_{i=1}^{n_{t}}d_{l_{i}}^{t}$, i.e. the state-
action distribution at timestep t. We note that $\hat{Q}_{t}$ corresponds to
different policies for different values of $t$, considering a different
version of the function approximator for each timestep. At timestep $t$, we
define $V_{R}^{t}(i)$ to be the variance of rewards of the experience samples
of the i-th leaf and $V_{q}^{t}(i)$ to be the variance of Q-values of the
frontier samples of the i-th leaf.

###  B.2 Objective

The utility function $J$ describes the total expected reward-to-go of
utilizing $\hat{Q}_{t}$ for all timesteps $t\in[0,T]$. We note that a high
value of J implies selections of higher Q-values per timestep, and thus
policies closer to greedy ones. Considering that the policy approximator
function $\hat{Q}_{t}$ is an oracle at timestep $t$, the greedy action
selection is to choose the state-action pair from the tree-frontier which
estimated Q-value at timestep $t$ is the highest among the others available,
that is $x^{*}_{t}$. Thus, oracle would always select $x^{*}_{t}$ from the
tree-frontier at each timestep $t$. We denote
$J^{*}=\sum\limits_{t=1}^{T}\left[\hat{Q}_{t}(x^{*}_{t})\right]$ as the
oracle’s utility function, i.e. the utility function in which always the best
$x^{*}_{t}$ is selected at timestep t.

We are interested in measuring how far from oracle our agent is. That is, we
are interested in finding a lower bound of $J-J^{*}$. Considering that there
will always be a chance to select the best $x^{*}_{t}$ at each timestep $t$,
it holds that $J\leq J^{*}$, i.e. $J^{*}$ is a tight upper bound of $J$. We
start by unrolling the closed form of utility function $J$.

$\displaystyle J$
$\displaystyle=\sum\limits_{t=1}^{T}\left[p_{t}(x_{t}^{*})\hat{Q}_{t}(x^{*}_{t})+(1-p_{t}(x_{t}^{*}))\max_{i\in
n_{t}}\left\\{\mathop{\mathbb{E}_{x_{t}\sim
d^{t}_{l_{i}}}}[\hat{Q}_{t}(x_{t})\mathbbm{1}\\{x^{*}_{t}\neq
x_{t}\\}]\right\\}\right]$
$\displaystyle=\sum\limits_{t=1}^{T}\left[\frac{1}{|L_{t}^{*}|}\hat{Q}_{t}(x^{*}_{t})+\left(1-\frac{1}{|L_{t}^{*}|}\hat{q}_{t}\right)\right]$
$\displaystyle=J^{*}-\sum\limits_{t=1}^{T}\left[\left(1-\frac{1}{|L_{t}^{*}|}\right)(\hat{Q}_{t}(x^{*}_{t})-\hat{q}_{t})\right]$
(6)

In the equations above, we have defined $\hat{q}_{t}=\max_{i\in
n_{t}}\left\\{\mathop{\mathbb{E}_{x_{t}\sim
d^{t}_{l_{i}}}}[\hat{Q}_{t}(x_{t})\mathbbm{1}\\{x^{*}_{t}\neq
x_{t}\\}]\right\\}$. Also, recall that the size of $L_{t}^{*}$ is bounded by
the maximum number of frontier samples at timestep $t$, and thus
$L_{t}^{*}\leq 1+Dt$, where $D$ is the maximum number of new frontier samples
(outlinks minus deleted frontier samples) at a single timestep.

###  B.3 Mathematical Analysis

We will try to find a lower bound for $J-J^{*}$. To achieve this we will need
to make some reasonable assumptions, as described below. The first assumption
is about the effectiveness of variance reduction. We assume that the splitting
rule uses a feature that is adequately correlated to the reward of the
elements in the node being split. This assumption is practically about the
quality of our data. If the web page features are weakly correlated to the
reward, we can not expect any learning algorithm to perform well. The second
assumption is about the relation between the reward variance ratio and the
Q-value variance ratio. Rewards are supposed to reflect real Q-values so we
assume that the noise between the reward variance ratio and the Q-value
variance ratio has small expectation. Our final assumption is that the leaf
containing $x^{*}_{t}$ has a splitting frequency greater or equal to some
value $1/M_{s}$. This way the height gradually increases and Q-value variance
is reduced. The first assumption guarantees that in each split effective
variance reduction is achieved. The third assumption implies that this
reduction takes place multiple times so that the overall reduction is high
enough. The second assumption translates reward variance reduction to Q-value
variance reduction. This implies that the Q-value variance in the leaf
containing $x^{*}_{t}$ is not very high, so random sampling from this leaf
could not select an element with a Q-value far from the optimal. This way the
cumulative utility is bounded with high probability.

The assumptions we make focus on some key steps of the learning algorithm and
supposing these steps are successful with high probability we can show that
the proposed algorithm approaches the optimal performance of the oracle. These
assumptions are admittedly strong, so the analysis we make here is more about
explaining the logic of the algorithm and interpreting the good experimental
performance rather than providing theoretical guarantees about its performance
on an arbitrary dataset. We now proceed to the mathematical analysis.

######  Assumption 1.

The squared Pearson product-moment correlation coefficient of reward R and
splitting rule S is greater than $1-\frac{\epsilon}{T\cdot h_{max}}$, where
$h_{max}$ is the height limit in the tree and $T$ the number of timesteps.

In each node of the decision tree let $R$ be the random variable of the reward
and $X$ the random vector corresponding to the representation of the node
elements. The splitting rule is a Bernoulli variable of the form
$S=\mathbbm{1}\\{X[i]>b\\}$, for some feature $i$ and some threshold $b$. In
particular, the rule is chosen which maximises the empirical variance
reduction calculated on the samples. Variance is calculated with respect to
the reward variable R. Let $V^{t}_{R}(Parent)$ be the reward variance of a
parent node on timestep t. The parent node is split into two child nodes. Let
$V^{t}_{R}(Child)$ be the reward variance of some child node on timestep t.
$V^{t}_{R}(Parent)=Var(R)$ and $V^{t}_{R}(Child)=Var(R|S)$. We will use an
inequality that holds for the conditional variance of two correlated variables
in order to bound the child variance from above. $\mathbb{E}[Var(y|R)]\leq
Var(R)-\frac{Cov^{2}(R,S)}{Var(S)}$. If $Var(R)=0$ then $\mathbb{E}[Var(R|S)]$
is zero as well. Else we have $\mathbb{E}[\frac{Var(R|S)}{Var(R)}]\leq
1-\frac{Cov^{2}(R,S)}{Var(S)\cdot Var(R)}\leq\delta$, assuming that the
squared Pearson product-moment correlation coefficient of R and S is greater
than $1-\delta$. This hypothesis is reasonable, because we expect that the
splitting rule which causes the greatest variance reduction is highly
correlated to the reward variable.
Applying Markov’s inequality we obtain $\mathbb{P}[\frac{Var(R|S)}{Var(R)}\geq
a]\leq\frac{\mathbb{E}[\frac{Var(R|S)}{Var(R)}]}{a}\leq\frac{\delta}{a}$. We
set $a=1$. Thus, with probability greater than $1-\delta$ the ratio of
variance between the child and the parent node is less than one. In order that
the complete algorithm execution is correct we want the variance ratio
condition to hold for all timesteps along the path leading to the optimal leaf
node. Let $h(t)$ be the height of the leaf containing $x^{*}_{t}$ at timestep
$t$. We set $T\cdot h_{max}\cdot\delta=\epsilon$ and from union bound the
condition is satisfied for all timesteps with probability greater than
$1-\epsilon$. This yields the following Proposition:

######  Proposition 1.

If assumption 1 holds, then with probability greater than $1-\epsilon$ it
holds that
$\frac{V^{t}_{R}(Child_{i})}{V^{t}_{R}(Parent_{i})}<1$ for all pairs of nodes
$V^{t}_{R}(Child_{i}),V^{t}_{R}(Parent_{i})$ that lie along the path from the
root to leaf $L_{t}^{*}$ for all t in $[1,2,...T]$.

######  Assumption 2 (The Split Q-Reward Assumption).

In each leaf split $s$, let $Child_{i}$ be a new leaf created because of s and
$Parent_{i}$ be the split node because of s. We consider the random noise
between the reward variance ratio and the Q-value variance ratio
$e_{i}=\frac{V^{t}_{q}(Child_{i})}{V^{t}_{q}(Parent_{i})}-\frac{V^{t}_{R}(Child_{i})}{V^{t}_{R}(Parent_{i})}$.
Then, $\mathbb{E}[e_{i}]<\lambda\cdot
exp\left(-\frac{w\sqrt{log(1/\epsilon_{1})}}{\sqrt{2h(t)}}\right)-1\quad\forall
i\in[1,h(t)]$, where $w$ is the range of $log(1+e_{i})$ and $\lambda$ is some
constant less than one.

The Split Q-Reward Assumption implies that inside a leaf, similar rewards
correspond to similar Q-values (produced by $\hat{Q}_{t}$). We consider that
all high rewards (ones if the reward function is binary) come from high
Q-values. In other words, in our crawling setting, we consider that our agent
has higher Q-values for the most URLs corresponding to relevant web pages.
From Assumption 1, considering that $Root$ is the tree root node and $h(t)$ is
the height of $Child$ at timestep t, it holds that

$\displaystyle V^{t}_{q}(Child)$
$\displaystyle=\left(\frac{V^{t}_{R}(Child)}{V^{t}_{R}(Parent)}+e_{h(t)}\right)\cdot
V^{t}_{q}(Parent)$
$\displaystyle=\prod_{i=1}^{h(t)}\left(\frac{V^{t}_{R}(Child_{i})}{V^{t}_{R}(Parent_{i})}+e_{i}\right)\cdot
V^{t}_{q}(Root)$
$\displaystyle=\prod_{i=1}^{h(t)}\left(\frac{Var(R_{i}|S_{i})}{Var(R_{i})}+e_{i}\right)\cdot
V^{t}_{q}(Root)$
$\displaystyle<\left(\prod_{i=1}^{h(t)}\left(1+e_{i}\right)\right)\cdot
V^{t}_{q}(Root),\text{ with probability greater than
}1-\frac{h(t)\cdot\epsilon}{h_{max}\cdot T}$

We want that with high probability $(1-\epsilon_{1})$

$\prod\limits_{i=1}^{h(t)}\left(1+e_{i}\right)<\lambda^{h(t)}\Leftrightarrow\sum\limits_{i=1}^{h(t)}log(1+e_{i})<h(t)\cdot
log(\lambda),\quad\lambda<1$ (2)

Parameter $\lambda$ corresponds to the decrease rate of variance along the
path from the root node to the leaf. It is natural to assume that even if
sometimes the variance increases from parent to child, the aggregated ratio
obtained by multiplying a series of ratios should be less than one with high
probability. This implies that groups of ratios tend to give products that are
less than one, so stacking these groups together results in a geometric
decrease. This is the intuition behind the assumption that
$\prod\limits_{i=1}^{h(t)}\left(1+e_{i}\right)<\lambda^{h(t)}$, with high
probability, for some rate $\lambda$, possibly very close to one, but less
than it.
Each one of the terms $l_{i}=log(1+e_{i})$ is a noise variable. We assume that
they are i.i.d. and each of them has expectation $\mathbb{E}[l_{i}]\leq l$,
where $l$ will be determined later. From Hoeffding’s inequality we have that
$\mathbb{P}[\sum\limits_{i=1}^{h(t)}l_{i}-h(t)l>s]\leq
exp\left(\frac{-2s^{2}}{h(t)w^{2}}\right)$, where $w$ is the range of $l_{i}$
and $s>0$.
To satisfy (2) we demand $s+h(t)l<h(t)\cdot log(\lambda)$ and
$exp\left(\frac{-2s^{2}}{h(t)w^{2}}\right)=\epsilon_{1}\Leftrightarrow
s=\frac{w\sqrt{h(t)\cdot log(1/\epsilon_{1})}}{\sqrt{2}}$.
Thus, we want
$l<log(\lambda)-\frac{w\sqrt{log(1/\epsilon_{1})}}{\sqrt{2h(t)}}\Leftrightarrow\mathbb{E}[log(1+e_{i})]<log(\lambda)-\frac{w\sqrt{log(1/\epsilon_{1})}}{\sqrt{2h(t)}}\forall
i\in[1,h(t)]$.
From Jensen’s inequality we have $\mathbb{E}[log(e_{i}+1)]\leq
log(\mathbb{E}[e_{i}]+1)$.
Thus, it suffices to demand
$log(\mathbb{E}[e_{i}]+1)<log(\lambda)-\frac{w\sqrt{log(1/\epsilon_{1})}}{\sqrt{2h(t)}}\Leftrightarrow\mathbb{E}[e_{i}]<\lambda\cdot
exp\left(-\frac{w\sqrt{log(1/\epsilon_{1})}}{\sqrt{2h(t)}}\right)-1\quad\forall
i\in[1,h(t)]$.
The condition should hold for the leaf containing $x^{*}_{t}$ at timestep $t$
at all timesteps so we set $T\cdot\epsilon_{1}=\epsilon$.

######  Proposition 2.

If the event described in Proposition 1 is true and assumption 2 holds , then
with probability greater than $1-\epsilon$ it holds that
$V_{q}(L_{t}^{*})<\lambda^{h(t)}{V_{q}}^{t}(Root)$ for all t in $[1,2,...T]$,
where $h(t)$ is the height of leaf $L_{t}^{*}$ containing $x^{*}_{t}$. The
event described in Proposition 1 is realised with probability greater than
$1-\epsilon$, given that assumption 1 holds, so from union bound the
probability that $V_{q}(L_{t}^{*})<\lambda^{h(t)}{V_{q}}^{t}(Root)$ for all t
in $[1,2,...T]$ is greater than $1-2\epsilon$, given that assumptions 1 and 2
hold.

######  Assumption 3.a.

The nodes of the path from the root node to the optimal leaf, $L_{t}^{*}$,
were former selected leaves for at least a fraction $1/M_{s}$ of the times
until timestep $t$. Moreover, each selection leads to a split.

This is quite a strong assumption. It demands that optimal leaf at $t$ has
height proportional to $t$. As the time grows, this allows the existence of a
constant number of long branches that repeatedly give optimal leaves. Leaves
that lie at small heights are expected to contain samples with small Q and R
values that are not selected. Such leaves end up having many samples, as
splits can only occur when a leaf is selected and splits are the only way to
reduce samples in a leaf. This is a key property of TRES, as samples with
small R and Q values are accumulated in few leaves and have a small
probability of being selected. The second part of the assumption, the fact
that each selection leads to a split, is a mild assumption that is made mainly
for technical reasons. If a selection does not lead to a split, then variance
inside the leaf is probably already very small (considering assumption 1 that
guarantees that with high probability there exists a splitting rule that
achieves variance reduction), which is an advantageous scenario. So, in the
context of variance reduction assuming that each selection leads to a split
does not change the worst case analysis. The following Proposition is a direct
consequence of Assumption 3.

######  Proposition 3.

Assumption 3.a implies for the height $h(t)$ of the optimal leaf $L_{t}^{*}$
that $h(t)\geq floor(t/M_{s})$, where $M_{s}$ is constant (independent of
$T$).

######  Theorem 3.a.

If Assumptions 1, 2 and 3.a hold, then
$\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon\lambda}}\cdot\frac{\bar{\lambda}(\bar{\lambda}+1)(\bar{\lambda}^{T}-1)}{(\bar{\lambda}-1)^{3}}\right\\}\geq
1-3\epsilon$, where $T$ is the total number of timesteps, $D$ is an upper
bound for the number of new URLs inserted in frontier at each timestep,
parameter $\lambda$ is introduced in Assumption 2 and
$\bar{\lambda}=\sqrt[2M_{s}]{\lambda}$.

###### Proof.

Let $d_{L^{*}_{t}}$ be the distribution Q-values of $L_{t}^{*}$, the leaf
which contains $x^{*}_{t}$ at timestep t. From Chebyshev’s inequality we
obtain:
$\mathbb{P}[|\hat{q}_{t}-\mu_{L^{*}_{t}}|\geq
k\sigma_{L^{*}_{t}}]\leq\frac{1}{k^{2}}$ Thus, from union bound, with
probability at least $1-\frac{|L^{*}_{t}|}{k^{2}}$ all frontier samples of
$L_{t}^{*}$ lie within the interval $[\mu_{L^{*}_{t}}-k\sigma_{L^{*}_{t}},\
\mu_{L^{*}_{t}}+k\sigma_{L^{*}_{t}}]$. The interval has length
$2k\sigma_{L^{*}_{t}}$, so the difference between any two elements of the
interval is at most $2k\sigma_{L^{*}_{t}}$. We set
$k=\sqrt{\frac{|L^{*}_{t}|}{\epsilon_{0}}}$, so the probability that
$\hat{Q}_{t}(x^{*}_{t})-\hat{q}_{t}\leq 2k\sigma_{L^{*}_{t}}$ is at least
$1-\epsilon_{0}$. We also set $T\cdot\epsilon_{0}=\epsilon$, so that the
condition holds for all timesteps with high probability (from union bound over
T timesteps).
$\mathbb{P}\left\\{\hat{Q}_{t}(x^{*}_{t})-\hat{q}_{t}\leq
2\sqrt{\frac{|L^{*}_{t}|}{\epsilon_{0}}}\sigma_{L^{*}_{t}}\right\\}\geq
1-\epsilon_{0}\Rightarrow\mathbb{P}\left\\{\hat{Q}_{t}(x^{*}_{t})-\hat{q}_{t}\leq
2\sqrt{\frac{T(D\cdot t+1)}{\epsilon}}\sigma_{L^{*}_{t}}\right\\}\geq
1-\frac{\epsilon}{T}$

Recall that
$J=J^{*}-\sum\limits_{t=1}^{T}\left[\left(1-\frac{1}{|L_{t}^{*}|}\right)(\hat{Q}_{t}(x^{*}_{t})-\hat{q}_{t})\right]$.
Using the probabilistic bound for $\hat{Q}_{t}(x^{*}_{t})-\hat{q}_{t}$ we
yield:
$\mathbb{P}\left\\{J-J^{*}\geq-\sum\limits_{t=1}^{T}\left[2\left(1-\frac{1}{|L_{t}^{*}|}\right)\sqrt{\frac{|L^{*}_{t}|}{\epsilon_{0}}}\sigma_{L^{*}_{t}}\right]\right\\}\geq
1-\epsilon\Rightarrow$
$\mathbb{P}\left\\{J-J^{*}\geq-\sum\limits_{t=1}^{T}\left[2\left(1-\frac{1}{Dt+1}\right)\sqrt{\frac{T(Dt+1)}{\epsilon}}\sigma_{L^{*}_{t}}\right]\right\\}\geq
1-\epsilon$,
because $|L_{t}^{*}|\leq Dt+1$ and function
$f(|L_{t}^{*}|)=\left(1-\frac{1}{|L_{t}^{*}|}\right)\sqrt{|L^{*}_{t}|}$ is
increasing on $|L_{t}^{*}|$.

From Assumption 2 with high probability we have that
$V^{t}_{q}(Leaf)<\lambda^{h(t)}V^{t}_{q}(Root)$, where $h(t)$ is the height of
the leaf node in the tree. Thus, for the leaf containing $x^{*}_{t}$ we have
$\sigma_{L^{*}_{t}}^{2}<\lambda^{h(t)}V^{t}_{q}(Root)\leq\frac{\lambda^{h(t)}\cdot
t^{2}}{4}$, where the second inequality follows from Popoviciu’s inequality on
variances and the fact that Q-values are in the range $[0,t]$. The probability
of success now falls to $1-3\epsilon$, because two additional potential causes
of error are introduced. Either the condition of Assumption 1 or the condition
of Assumption 2 may be violated. Each of these error events have probability
less than $\epsilon$ to occur. Thus we obtain:

$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\sum\limits_{t=1}^{T}\left[\left(1-\frac{1}{Dt+1}\right)\sqrt{\frac{T(Dt+1)}{\epsilon}}\sqrt{\lambda^{h(t)}\cdot
t^{2}}\right]\right\\}\geq 1-3\epsilon\xRightarrow{}$ (3.1)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T}}{\sqrt{\epsilon}}\cdot\sum\limits_{t=1}^{T}\left[\left(\sqrt{Dt^{3}+t^{2}}\right){\sqrt{\lambda}}^{h(t)}\right]\right\\}\geq
1-3\epsilon\xRightarrow{}$ (3.2)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon\lambda}}\cdot\sum\limits_{t=1}^{T}\left[t^{\frac{3}{2}}{\sqrt{\lambda}}^{\frac{t}{M_{s}}}\right]\right\\}\geq
1-3\epsilon\xRightarrow{}$ (3.3)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon\lambda}}\cdot\sum\limits_{t=1}^{T}t^{2}\cdot{\bar{\lambda}}^{t}\right\\}\geq
1-3\epsilon\Leftrightarrow$ (3.4)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon\lambda}}\cdot\frac{\bar{\lambda}[((\bar{\lambda}-1)^{2}T^{2}-2(\bar{\lambda}-1)T+\bar{\lambda}+1)\bar{\lambda}^{T}-\bar{\lambda}-1]}{(\bar{\lambda}-1)^{3}}\right\\}\geq
1-3\epsilon\xRightarrow{}$ (3.5)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon\lambda}}\cdot\frac{\bar{\lambda}(\bar{\lambda}+1)(\bar{\lambda}^{T}-1)}{(\bar{\lambda}-1)^{3}}\right\\}\geq
1-3\epsilon\xRightarrow{}$ (3.6)

The above calculations are based on the observation that for a random variable
$X$ the probability $P\\{X>a\\}$ is greater than $P\\{X>b\\}$ for $a<b$. Thus,
we can go from step to step by reducing the quantity that bounds $J-J^{*}$
from below. To go from step $(3.1)$ to $(3.2)$ we omit the term
$-\frac{1}{\sqrt{Dt+1}}$. The step from $(3.2)$ to $(3.3)$ follows from the
inequality $h(t)\geq\frac{t}{M_{s}}-1$, which is due to Proposition 3 and the
observation that $Dt^{3}+t^{2}$ is greater than $(D+1)t^{3}$ . The transition
from $(3.3)$ to $(3.4)$ can be made because $t^{\frac{3}{2}}<t^{2}$. Also, we
set $\bar{\lambda}:=\sqrt[2M_{s}]{\lambda}$. To go from $(3.4)$ to $(3.5)$ we
use a (classical) formula for the sums $\sum_{k=1}^{n}k^{2}\cdot a^{k}$ and
make an appropriate grouping of the terms, which will help us get rid of terms
proportional to $T$ and $T^{2}$ and thus overcome the polynomial dependence of
the error on $T$. The step from $(3.5)$ to $(3.6)$ follows from the fact that
$\bar{\lambda}<1$, so the coefficients of $T^{2}$ and $T$ are positive. ∎

We conclude that the absolute error is proportional to the square root of time
horizon $T$. It is also proportional to the square root of $D$, where $D$ is
the maximum number of new frontier samples at each timestep. Finally, there is
a dependence on $\frac{1}{\sqrt[2M_{s}]{\lambda}-1}$, where $\lambda$ is the
decrease rate of the variance of Q-values along a path from the root to a
leaf.

######  Assumption 3.b.

The height $h(t)$ of the optimal leaf $L_{t}^{*}$ is at least $\log_{2}(t)$

This is a mild assumption that can replace its stricter counterpart,
assumption 3.a. It allows the tree to have a balanced structure and not be
dominated by certain branches.

######  Theorem 3.b.

If Assumptions 1, 2 and 3.b hold and parameter $\lambda$ introduced in
Assumption 2 is less than $\frac{1}{8}$, then
$\mathbb{P}\left\\{J-J^{*}\geq-\frac{T\sqrt{T(D+1)}}{\sqrt{\epsilon}}\right\\}\geq
1-3\epsilon$, where $T$ is the total number of timesteps, $D$ is an upper
bound for the number of new URLs inserted in frontier at each timestep and
$\bar{\lambda}=\sqrt[2M_{s}]{\lambda}$.

###### Proof.

The proof follows the same steps as the proof of theorem 3.a up to step (3.2).
After that point we have:

$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T}}{\sqrt{\epsilon}}\cdot\sum\limits_{t=1}^{T}\left[\left(\sqrt{Dt^{3}+t^{2}}\right){\sqrt{\lambda}}^{h(t)}\right]\right\\}\geq
1-3\epsilon\xRightarrow[(D+1)t^{3}\geq Dt^{3}+t^{2}]{h(t)\geq\log_{2}(t)}$
(3.2)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon}}\cdot\sum\limits_{t=1}^{T}\left[t^{\frac{3}{2}}{\sqrt{\lambda}}^{\log_{2}(t)}\right]\right\\}\geq
1-3\epsilon\Leftrightarrow$ (3.3’)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon}}\cdot\sum\limits_{t=1}^{T}\left[t^{\frac{3}{2}}{t}^{\log_{2}(\sqrt{\lambda})}\right]\right\\}\geq
1-3\epsilon\xRightarrow{\lambda<\frac{1}{8}}$ (3.4’)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon}}\cdot\sum\limits_{t=1}^{T}\left[t^{\frac{3}{2}}{t}^{\log_{2}(\sqrt{\frac{1}{8}})}\right]\right\\}\geq
1-3\epsilon\Leftrightarrow$ (3.5’)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon}}\cdot\sum\limits_{t=1}^{T}[1]\right\\}\geq
1-3\epsilon\Leftrightarrow\mathbb{P}\left\\{J-J^{*}\geq-\frac{T\sqrt{T(D+1)}}{\sqrt{\epsilon}}\right\\}\geq
1-3\epsilon$ (3.6’)

∎

######  Theorem 3.c.

If Assumptions 1, 2 and 3.b hold and parameter $\lambda$ introduced in
Assumption 2 is less than $\frac{1}{32}$, then
$\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon}}\cdot(ln(T)+1)\right\\}\geq
1-3\epsilon$, where $T$ is the total number of timesteps, $D$ is an upper
bound for the number of new URLs inserted in frontier at each timestep and
$\bar{\lambda}=\sqrt[2M_{s}]{\lambda}$.

###### Proof.

The proof follows the same steps as the proof of theorem 3.b up to step
(3.4’). After that point we have:

$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon}}\cdot\sum\limits_{t=1}^{T}\left[t^{\frac{3}{2}}{t}^{\log_{2}(\sqrt{\lambda})}\right]\right\\}\geq
1-3\epsilon\xRightarrow{\lambda<\frac{1}{32}}$ (3.4’)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon}}\cdot\sum\limits_{t=1}^{T}\left[t^{\frac{3}{2}}{t}^{\log_{2}(\sqrt{\frac{1}{32}})}\right]\right\\}\geq
1-3\epsilon\Leftrightarrow$ (3.5”)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon}}\cdot\sum\limits_{t=1}^{T}\frac{1}{t}\right\\}\geq
1-3\epsilon\xRightarrow{H_{n}<ln(n)+1}$ (3.6”)
$\displaystyle\mathbb{P}\left\\{J-J^{*}\geq-\frac{\sqrt{T(D+1)}}{\sqrt{\epsilon}}\cdot(ln(T)+1)\right\\}\geq
1-3\epsilon$ (3.7”)

∎

Theorems 3.b and 3.c make the mild assumption 3.b about the leaf heights, but
they make strong assumptions about the decrease rate $\lambda$ of the variance
of Q-values along a path from the root to a leaf. Theorem 3.c guarantees a
sublinear dependence of the error on $T$ and Theorem 3.c an error
$O(T\sqrt{T\cdot D})$.

##  Appendix C Harvest Rate Diagrams

Figure 5: Harvest Rate diagrams: Sports (Up left), Food (Up right) and
Hardware (Down)