{'fraction_non_alphanumeric': 0.036938001368074125, 'fraction_numerical': 0.00907903737329768, 'mean_word_length': 4.280647985989492, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robustification of Online Graph Exploration Methods

Exploring unknown environments is a fundamental task in many domains, e.g., robot navigation, network security, and internet search. We initiate the study of a learning-augmented variant of the classical, notoriously hard online graph exploration problem by adding access to machine-learned predictions. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm and significantly outperforms any known online algorithm if the prediction is of high accuracy while maintaining good guarantees when the prediction is of poor quality. We provide theoretical worst-case bounds that gracefully degrade with the prediction error, and we complement them by computational experiments that confirm our results. Further, we extend our concept to a general framework to robustify algorithms. By interpolating carefully between a given algorithm and NN, we prove new performance bounds that leverage the individual good performance on particular inputs while establishing robustness to arbitrary inputs.


Introduction
In online mapping problems, a searcher is tasked to explore an unknown environment and create a complete map of its topology. However, the searcher has only access to local information, e.g., via optical sensors, and must move through the environment to obtain new data. Such problems emerge in countless real-life scenarios with a prominent example being the navigation of mobile robots, be it a search-and-rescue robot, an autonomous vacuum cleaner, or a scientific exploration robot in the deep sea or on Mars. Less obvious but equally important applications include crawling the Internet or social networks for information and maintaining security of large networks [14,56,33].
We investigate the online graph exploration problem on an undirected connected graph G = (V, E) with n vertices. Every edge e ∈ E has a non-negative cost c(e), and every vertex v ∈ V a unique label. Starting in a designated vertex s ∈ V , the task of the searcher is to find a tour that visits all vertices of G and returns to s. A priori, the searcher does not know the graph. Instead, she gains local information when traversing it: When for the first time visiting (exploring) a vertex, all incident edges, as well as their costs, and the labels of their end points are revealed. This exploration model is also known as fixed graph scenario [38]. In order to explore a vertex v, the searcher may traverse a path consisting of known edges that starts in the searcher's current location and ends in v. When the searcher traverses an edge e, she pays its cost c(e). The goal is to minimize the total cost.
Due to the lack of information, the searcher cannot expect to find an optimal tour. We resort to standard competitive analysis to measure the quality of our search algorithms. That is, we compare the length of the tour found by the searcher with the optimal tour that can be found if the graph is known in advance. If the ratio between the costs of these two tours is bounded by ρ ≥ 1 for every instance, then we say that the online algorithm is ρ-competitive. The competitive ratio of an algorithm is the minimum ρ for which it is ρ-competitive. The offline problem of finding an optimal tour on a known graph is the well-known Traveling Salesperson Problem (TSP), which is NP-hard [46].
Indeed, it appears extremely difficult to obtain solutions of cost within a constant factor of an optimal tour. The best known competitive ratio for arbitrary graphs is O(log n), attained by the following two algorithms. The Nearest Neighbor algorithm (NN) [59] greedily explores the unknown vertex closest to the current position. While its performance is usually good in practice [3], a matching lower bound of Ω(log n) holds even for very simple graphs, e.g., unweighted graphs [36] or trees [32]. The second algorithm is the hierarchical Depth First Search algorithm (HDFS) [51] that, roughly speaking, executes depth-first searches (DFS) on subgraphs with low edge costs, thereby limiting its traversal to a minimum spanning tree (MST). Here, a matching lower bound is attained on a weighted path.
Only for rather special graph classes it is known how to obtain constant-competitive tours. Notable examples are planar graphs, with a competitive ratio of 16 [38,51], graphs of bounded genus g with a ratio of 16(1 + 2g) and graphs with k distinct weights with a ratio of 2k [51]. The latter emerges as somewhat of an exception since the HDFS algorithm achieves a performance that is both, good on a specific yet interesting graph class and still acceptable on arbitrary instances. Beyond the above, results are limited to the most basic kind of graphs, such as unweighted graphs [53], cycles and tadpole graphs [53,21], and cactus and unicyclic graphs [32]. Conversely, the best known lower bound on the competitive ratio of an online algorithm is 10/3 [16]. Despite ongoing efforts, it remains a major open question whether there exists an O(1)-competitive exploration algorithm for general graphs.
The assumption of having no prior knowledge about the graph may be overly pessimistic. Given the tremendous success of artificial intelligence, we might have access to predictions about good exploration decisions. Such predictions, e.g., machine-learned ones, are typically imperfect; they usually have a good quality but may be arbitrarily bad.
A new line of research is concerned with the design of online algorithms that have access to predictions of unknown quality [48,55,50]. Ideally, algorithms have the following properties: (i) good predictions lead to a better performance than the best worst-case bound achievable when not having access to predictions; (ii) the algorithm never performs (asymptotically) worse than the best worst-case algorithm even if the prediction is of poor quality; and (iii) the performance gracefully degrades with decreasing prediction quality. More formally, we define a parameter η ≥ 0, called prediction error, that measures the quality of a given prediction, where η = 0 refers to the case that the prediction is correct, we also say perfect. We assess an algorithm's performance by the competitive ratio as a function of the prediction error. If an algorithm is ρ(η)-competitive for some function ρ, we call it α-consistent for α = ρ(0) and β-robust if ρ(η) ≤ β for any prediction error η ≥ 0 [55].
For the online graph exploration problem, we consider predictions that suggest a known, but unexplored vertex as next target to a learning-augmented algorithm. In other words, a prediction is a function that, given the current state of the exploration, outputs an explorable vertex. Predictions may be computed dynamically and use all data collected so far, which is what one would expect in practice. This rather abstract requirement allows the implementation of various prediction models. In this paper, we consider two kinds of predictions, namely tour predictions and tree predictions, where the suggested vertex is the next unexplored vertex of a TSP tour or of a Depth First Search (DFS) tour corresponding to some predicted spanning tree, respectively. The prediction error η is the difference between the total exploration cost of following these per-step suggestions blindly and that of following a perfect prediction w.r.t. the given prediction model (tour resp. tree predictions).

Our results
Our contribution is twofold. Firstly, we present a learning-augmented online algorithm for the graph exploration problem that has a constant competitive ratio when the prediction error is small, while being robust to poor-quality predictions. Our algorithm interpolates carefully between the algorithms NN and Follow the Prediction (FP), where the latter blindly follows a given prediction. Theorem 1. For any λ > 0, there is an algorithm for the online graph exploration problem that uses a predicted spanning tree or tour such that the algorithm is κ(3 + 4λ)-consistent and 1 + 1 2λ ( log(n) + 1)robust, where κ = 1, for tour predictions, and κ = 2, for tree predictions. With growing prediction error, the competitive ratio degrades gracefully with linear dependence on η.
The parameter λ can steer the algorithm towards one of the underlying algorithms, e.g., towards NN when λ → ∞. It reflects our trust in the quality of the provided predictions.
Further, we show that our predictions (tour and tree) are learnable in the sense of PAC learnability [62,65] under the assumptions that the given graph is complete and its size known. We show a bound on the sample complexity that is polynomial in the number of nodes and give learning algorithms with a polynomial running time in the case of tree predictions and an exponential running time for tour predictions. The learnability results also approximately bound the expected prediction error η, which potentially can be taken into account when setting λ.
Our second main result is a general framework to robustify algorithms. Given an online algorithm A with a certain worst-case performance for particular classes of instances but unknown, possibly unbounded, performance in general, the robustification framework produces an algorithm with the same good performance on special instances while guaranteeing the best-known worst-case performance O(log n) on general instances. As it turns out, the idea of interpolating between two algorithms that we used to design a learning-augmented algorithm can be generalized to interpolating between the actions of an arbitrary algorithm A and NN, again using the parameter λ.
Theorem 2. For any λ > 0, there is a robustification framework R for the online graph exploration problem that, given an online algorithm A and an instance I = (G, s), produces a solution of cost at most R I = min{(3 + 4λ) · A I , 1 + 1 2λ ( log(n) + 1) · OPT I }, where OPT I and A I denote the cost of an optimal solution and of the one obtained by A on instance I, respectively.
This seems useful in situations where one may suspect that an instance is of a certain type for which there exist good algorithms. One would like to use a tailored algorithm without sacrificing the general upper bound and good average-case performance of NN in case the suspicion is wrong. Two illustrative examples are as follows. (i) Planar graphs: Many spatial networks, e.g., urban street networks, can often be assumed to be (almost) planar [12,20]. Here, the graph exploration algorithm BLOCKING [51,38] seems the best choice, given its competitive ratio of 16. Yet, on general instances, the competitive ratio may be unbounded and is known to be worse than ω(log n) [51], underlining the need for robustification. (ii) Bounded number of weights: Here, HDFS [51] is the logical choice with a competitive ratio proportional to the number of weights and an asymptotically best-known competitive ratio on general instances. Even here, robustification is useful as it provides the good average-case performance of NN and the slightly better competitive ratio for general instances.
Interestingly, when considering the surprisingly good average-case performance of NN in practice, our robustification framework may also be interpreted to be robustifying NN and not the specifically tailored algorithm. Either algorithm can possibly make up for the other's shortcomings.
Our robustification scheme is conceptually in line with other works combining algorithms with different performance characteristics [49,31,17,4]. However, it is nontrivial to implement such concept for online graph exploration with the particular way in which information is revealed. Since the graph is revealed depending on an algorithm's decisions, the key difficulty lies in handling the cost of different algorithms in different metrics. This fact also prohibits the application of previous learning-augmented algorithms, e.g., for metrical task systems, in our setting.
We complement our theoretical results by empirically evaluating the performance of our algorithms on several real-world instances as well as artificially generated instances. The results confirm the power of using predictions and the effectivity of the robustification framework.
Several works empirically study the use of machine learning to solve TSP [39,66,13,42] without showing theoretical guarantees. For example, Khalil et al. [39] use a combination of reinforcement learning, deep learning, and graph embedding to learn a greedy policy for TSP. As the policy might depend on information that is not accessible online, e.g., the degree of an unexplored vertex, and constructs the tour in an offline manner, the results do not directly transfer to our online setting. However, similar approaches are conceivable and might be an application for the robustification framework, especially since there already exist empirical results in related settings for the exploration of unknown environments. For example, one approach [47] uses constructive machine learning tools to predict unknown indoor environments, and another approach [24] considers online graph exploration as a reinforcement learning problem and solves it using graph neural networks (cf. [67]). Since those approaches do not give theoretical guarantees, they are potential applications for the robustification framework. Dai et al. [27] consider reinforcement learning for a related problem, where the goal is to explore a maximum number of states in a (possibly unknown) environment using a limited budget. In contrast to these algorithmic results, Elmiger et al. [30] use reinforcement learning to find instances that yield a high competitive ratio for NN.
A recent line of research considers data-driven algorithm design [9,8,10,7,15,23,35]. Usually, the task is to select the algorithm with the best expected performance for an unknown distribution over instances from a fixed set of algorithms; see [6] for a survey of recent results. Lavastida et al. [45] combine learningaugmentation with data-driven algorithm design. We are not aware of data-driven methods for online graph exploration. While our results with regards to PAC learnability of predictions have a similar flavor as the data-driven algorithm design above, there are some major differences. In contrast to data-driven algorithms, we learn predictions with the goal of minimizing the error η. This error is related to the worst-case guarantees of our algorithms but it does not directly transfer to their expected objective function values. Instead, a function depending on the error (cf. Theorem 1) only upper bounds the expected objective values. While this may be seen as a disadvantage, it also means that our learned predictions are independent of the used algorithm.
Another line of research studies the graph exploration problem with advice [18,28,41]. In this model, an algorithm is also equipped with advice that can convey arbitrary information and the goal is to find a competitive solution while using advice of small encoding size. Here, the advice is assumed to be correct which is crucially different from our model.

A general robustification scheme
In this section, we introduce the robustification scheme R from Theorem 2 that, given an algorithm A for the online graph exploration problem, robustifies its worst-case performance guarantee. In the course of the exploration, the set of vertices known to the searcher can be partitioned into explored and unexplored vertices, i.e., vertices that have already been visited by the searcher, or not, respectively. The robustification scheme uses the algorithm A as a blackbox. That is, we treat A as a function that, given the current position, currently known subgraph, and set of already explored vertices, returns the next vertex to explore. The learning-augmented algorithm from Theorem 1 emerges as an application of the robustification scheme and is discussed in Section 3.

The robustification scheme
Intuitively, the robustification scheme R, summarized in Algorithm 1, balances the execution of algorithm A with that of NN by executing the algorithms in alternating phases. These phases are budgeted so that their costs are roughly proportional to each other, with a parameter λ > 0 dictating the proportionality. Specifically, whenever A is at position v and about to explore a vertex u via some path P A u , we interrupt A and, instead, start from v a phase of exploration via NN. This phase ends when the cost incurred by NN reaches λc(P A u ) or when NN is about to explore u (Lines 6 to 9). Only afterwards does the scheme explore the vertex u and resumes exploration via A (Line 10).

Algorithm 1: Robustification scheme R.
Input: Partially explored graph G, start vertex s, algorithm A, and parameter λ > 0 1 G A ← G // subgraph revealed to A 2 while G has an unexplored vertex do 3 u ← next unexplored node to be visited by A, computed via Algorithm 2 u ← nearest unexplored neighbor of s 10 traverse a shortest known path to u, set s ← u and update G 11 update G A to reflect exploration of u 12 traverse a shortest path in G to the start vertex Note that we do not reveal to A information gained by exploring vertices during the nearest-neighbor phase (Lines 6 to 9). If A decides to explore a vertex u next that is already known to R, we only simulate A without actually executing any traversals (Line 3 resp. Algorithm 2). This is possible since the new information that A would obtain by exploring u is already known to R.
Recall that, given an online algorithm A and a graph exploration instance I, the terms A I and OPT I refer to the costs incurred by A and an optimal solution on instance I, respectively. To prove Theorem 2, we bound the cost incurred by R during the NN phases in terms of OPT I . Lemma 3. The cost κ N of all traversals in Line 7 is at most 1 2 ( log n + 1)OPT I . The lemma can be shown by following the approach of [59]. While there one consecutive nearest-neighbor search is considered, our algorithm starts and executes multiple (incomplete) nearest-neighbor searches with Algorithm 2: Computes next unexplored node visited by A and updates G A .
Input: Partially explored graph G, blackbox graph G A , start vertex s and algorithm A 1 while next vertex u explored by A, given G A and s, is explored in G do 2 update G A by adding previously unknown edges incident to u, and mark u as explored 3 s ← u 4 return u, G A different starting points. In the adapted proof of the lemma, we use the following auxiliary result.
Lemma 4 (Lemma 1 in [59]). Let l ∈ R V be such that for an instance I of the graph exploration problem the following properties hold: We assign to each v ∈ V a value l v such that κ N i = v∈V l v and both conditions of Lemma 4 hold, which then implies the statement of Lemma 3.
Consider a current vertex s before a traversal in the NN phase, i.e., a traversal in Line 7. Observe that in this manner no vertex is considered twice since s is always the most recently newly explored vertex in G (or, in case of the very first iteration, the initially given start vertex). Let l s = c(P ), where P is the shortest v-u -path traversed by NN in Line 7 and l v = 0 for all remaining vertices. Then, κ N i = v∈V l v . It remains to show that both conditions of Lemma 4 are satisfied.
Condition (i): Suppose l v , l u > 0 as otherwise the condition trivially holds. Moreover, assume without loss of generality that v was explored before u. Thus, when traversing to the nearest neighbor u of v, the vertex u was still unexplored. By definition, l v corresponds to the cost of a shortest v-u -path. Since u was still unexplored but u was selected as the nearest neighbor of v, it follows that the shortest path between v and u cannot be shorter than the shortest path between v and u . Thus, the shortest path between v and u has cost at least l v .
Condition (ii): Again, assume l v > 0. The value l v corresponds to the cost of the shortest path between v and some vertex u. The condition easily follows when viewing OPT I as two paths connecting v and u.
Using Lemma 3, we show the theorem.
Proof of Theorem 2. Fix λ > 0, an algorithm A for the graph exploration problem, and an instance I. Denote by R I the cost incurred on instance I by the robustification scheme R applied to A with parameter λ. We show R I ≤ (3 + 4λ)A I and R I ≤ 1 + 1 2λ ( log(n) + 1)OPT I separately. For each iteration i of the outer while loop, denote by κ N i the traversal cost incurred by the inner while loop (Line 7), and by κ A i the cost of the traversal in Line 10. Then, For iteration i of the outer while loop, in which A wants to explore u, let P A i be the shortest s-u-path in Line 4. Since Line 3 resp. Algorithm 2 only simulate traversals, the P A i may not match the actual traversals that are due to algorithm A. Specifically, it might be the case that i c(P A i ) = A I . However, since P A i is a shortest path in the currently known graph G which contains G A after executing the simulated traversals, it cannot exceed the sum of the corresponding simulated traversals. Thus, i c(P A i ) ≤ A I . Consider an iteration i and the traversal cost κ N i + κ A i incurred during this iteration. We start by upper bounding κ N i . Let κ i be the cost of the inner while loop (Lines 6 to 9) excluding the last iteration. By definition, κ i < λ · c(P A i ).
Let P i be the path traversed in the last iteration of the inner while loop, s its start vertex, and u its end vertex. Recall that u is the endpoint of P A i . Before executing the inner while loop, the cost of the shortest path from the current vertex to u was c(P A i ). By executing the inner while loop, excluding the last iteration, the cost of the shortest path from the new current vertex to u can only increase by at most κ i < λ · c(P A i ) compared to the cost of P A i . Since P i is the path to the nearest neighbor of the current vertex, c(P i ) cannot be larger than the cost of the shortest path to vertex u.
i , consider the traversal of the shortest s-u-path in Line 10. Before executing the inner while loop, the cost of the shortest path from the current vertex to u was c(P A i ). By executing the while loop, the cost of the shortest path from the new current vertex to u can increase by at most

Reducing the overhead for switching algorithms
The robustification scheme R balances between the execution of a blackbox algorithm A and a nearestneighbor search with the parameter λ, that allows us to configure the proportion at which the algorithms are executed. Even for arbitrarily small λ > 0, the worst-case cost of R on instance I is still (3 + 4λ)A I ≈ 3A I . The loss of the factor 3 is due to the overhead created by switching between the execution of algorithm A and the nearest-neighbor search. Hence, we modify R to reduce this overhead. For a fixed λ, this leads to a slighly worse worst-case guarantee. However, instances leading to a cost of roughly 3A I are very particular, and here the modification significantly improves the average-case performance as our experimental results in Section 4 show. We first describe how the modified robustification scheme R (cf. Algorithm 3) differs from Algorithm 1. Intuitively, the modified robustification scheme R reduces the overhead for switching between algorithms by extending the individual phases. Specifically, to not continuously interrupt A, we introduce a budget for its execution that is now proportional to the cost of all past nearest neighbor phases. In turn, we also increase the budget for NN to match these larger phases of executing A: The modified scheme uses the budget variable b N to keep track of the total cost incurred by following NN (cf. Lines 2 and 21). At the beginning of each iteration of the outer while loop, the algorithm exploits this budget to follow A until the next traversal would surpass the parametrized budget 1 λ · b N (cf. Lines 7 and 11). The cost incurred by those traversals in the current iteration of the outer while loop is stored in variable b A (cf. Lines 4 and 9).
In order to compensate for this additional phase of following A, the while loop of Line 13 follows NN until either the cost is at least λ · (b A + c(P A u )) or the cost is at least λ · b A and the last explored vertex is the previous target vertex of both NN and A. In contrast to the original robustification scheme, it can happen that the target vertex u of A is explored during the execution of NN but we still need to continue following NN in order to reach a cost of at least λ · b A . To handle those situations, the algorithm recomputes the next target vertex u of A and the corresponding path P A u (cf. Lines 16 to 19). Finally, again in contrast to the original version, the modified robustification scheme might explore the final vertex of the graph before the end of the current iteration of the outer while loop. Thus, the algorithm ensures to not execute further traversals if the graph is already fully explored, except for the return to the start vertex in Line 25. Input: Partially explored graph G, start vertex s, algorithm A, and parameter λ > 0 u ← next unexplored node to be visited by A, computed via Algorithm 2 u ← next unexplored node to be visited by A, computed via Algorithm 2 ) and s = u) or (b < λ · b A and s = u)) and G has an unexplored vertex do 14 traverse a shortest s-u -path P u and update G The analysis of the modified robustification scheme R remains essentially the same. The second term in the minimum of the worst-case guarantee is slightly higher since the algorithm might terminate directly after executing an extended phase of A without giving NN a chance to compensate for possible errors. The first term, i.e., (3 + 4λ)A I , remains the same since the cost of an iteration of the outer while loop remains bounded by (3 + 4λ) times the cost of an extended phase of A plus the cost of reaching the next target of A after that phase.
Theorem 5. Given an algorithm A for the online graph exploration problem and λ > 0, the modified robustification scheme R solves a graph exploration instance I with cost Proof. Fix λ > 0, an algorithm A for the graph exploration problem, and an instance I. Denote by R I the cost incurred on instance I by the modified robustification scheme R applied to A with parameter λ. We show R I ≤ (3 + 4λ)A I and R I ≤ 1 2 (1 + 1 λ )( log(n) + 1)OPT I separately.
For each iteration i of the outer while loop, denote by κ N i the traversal cost incurred by the inner while loop (Line 7), and by κ A i the cost of the traversal in Lines 8 and 23. Then, R I = i (κ A i + κ N i ). Proof of R I ≤ (3 + 4λ)A I : For each iteration i of the outer while loop, let P A i be the shortest s-u-path P A u that is considered in the last execution of one of the Lines 6, 11 or 19. Further, let b i A denote the traversal cost incurred by all executions of Line 8 in iteration i.
Since Algorithm 2 only simulates traversals and not all traversals of A are considered due to the recomputation of P A u (cf. Lines 6, 11 and 19), the cost b i A + c(P A i ) may not match the actual traversal cost that are due to algorithm A in the iteration. Specifically, it might be the case that i b i A + c(P A i ) = A I . However, since P A i is a shortest path in the currently known graph G which contains G A after executing the simulated traversals, it must be shorter than the sum of the corresponding simulated traversals.
Consider an arbitrary iteration i and the traversal cost incurred during this iteration, i.e., κ N i + κ A i . We start by upper bounding κ N i . Let κ i be the cost of the inner while loop (Lines 13 to 20) excluding the last iteration. By definition, κ i < λ · (b i A + c(P A i )) Let P i be the path traversed in the last iteration of the inner while loop, s its start vertex, and u its end vertex. Recall that u is the endpoint of P A i . Before executing the iterations of the inner while loop that remain to be executed after P A i was computed, the cost of the shortest path from the current vertex to u was c(P A i ). By executing the remaining iterations of the inner while loop, excluding the last iteration, the cost of the shortest path from the new current vertex to u can only increase by at most κ i < λ · (b i A + c(P A i )) compared to the cost of P A i . Since P i is the path to the nearest neighbor of the current vertex, c(P i ) cannot be larger than the cost of the shortest path to vertex u. Thus, c( Note that, if the iteration is aborted early because all vertices are explored, the bound on κ A i + κ N i in terms of c(P A i ) + b i A only improves. We conclude Observe that the worst-case of R I ≈ (3 + 4λ) · A I can only occur if the cost i c(P A i ) dominates the cost i b i A , i.e., if the cost incurred by the last traversals of A per iteration dominates the cost of all other traversals by A. For larger i b i A , the bound on R I improves, which is a possible explanation for the success of R in the experimental analysis.
Proof of R I ≤ 1 + 1 λ ( log(n) + 1)OPT I : Consider an arbitrary iteration i of the outer while loop that is not the last one, i.e., i is a full iteration, and consider again κ A i = b i A + l i where l i denotes the traversal cost of Line 23.
As argued before, we have l i ≤ c(P A i ) + κ N i . If the inner while loop was aborted because s = u and κ N i ≥ λ · b i A , then l i = 0. This implies ignoring the last iteration j of the outer while loop. Then, When bounding R I in terms of κ N , the worst-case occurs if κ A j is as large as possible and κ N j is as small as possible. Thus, the worst-case occurs if the graph is explored before the last iteration executes the second inner while loop. In that case, κ N j = 0 and, by definition of the first inner while loop (cf. Line 7), κ A j ≤ 1 λ ·κ N . We can conclude that Since the proof of Lemma 3 is not affected by the modifications of R, we can apply Lemma 3 on κ N . This implies the desired result.

Online graph exploration with untrusted predictions
In this section, we apply the previously introduced robustification scheme in the context of learning-augmented algorithms and present an algorithm that satisfies the criteria in Theorem 1. This algorithm is provided with untrusted predictions that come in the form of a fixed exploration order of the vertices, given by a spanning tree or a tour. The learnability of such predictions is discussed in Section 3.2.

A learning-augmented online algorithm
We consider prediction models which upfront fix an exploration order τ p of the vertices. Such an order can be predicted directly (tour predictions) or is given by the traversal order of a Depth First Search (DFS) on a predicted spanning tree T p (tree predictions). Recall that a prediction is a function that outputs for a given exploration state an explorable vertex, and, given an order τ p , this vertex is the first unexplored vertex in τ p w.r.t. the current state. Due to this mapping, we also call τ p a prediction. Denote by c(τ p ) the cost of executing FP with the prediction τ p . A perfect prediction τ * is in the case of tour predictions an optimal tour, and in the case of tree predictions the DFS traversal order of a Minimum Spanning Tree (MST) T * . The prediction error is defined as η = c(τ p ) − c(τ * ). Regarding tree predictions, the definition of DFS ensures that each edge in T * is traversed at most twice, thus c(τ * ) ≤ 2c(T * ). Using c(T * ) ≤ OPT I , this implies the following lemma. Lemma 6. For an instance I, following tree predictions has cost FP I ≤ 2OPT I + η.
Naively calling FP might lead to an arbitrarily bad competitive ratio of FP. Luckily, Theorem 2 provides us with a tool to mitigate this possibility and cure FP of its naivety. Using FP within the robustification scheme of Algorithm 1 allows us to bound the worst-case performance. Denote by R(FP, G) the performance of this strategy. With Lemma 6, and given an instance I with tree predictions, we can upper bound R(FP, G) by with κ = 2. Observe that, when considering tour predictions, FP I = OPT I + η. Thus, we obtain the same bound on R(FP, G) but with κ = 1. This concludes the proof of Theorem 1.

PAC learnability of the predictions
We now discuss the learnability of tree and tour predictions. To allow for predicted tours or trees that are consistent with the graph to be explored, we assume that the set of n (labeled) vertices is fixed and the graph G is complete. This may seem like a strong restriction of general inputs to the graph exploration problem. However, notice that the cost c(e) of an edge e is still only revealed when the first endpoint of e is explored. There is no improved online algorithm known for this special case.
Firstly, we show PAC learnability of tree predictions. Our goal is to predict a spanning tree in G of low expected cost when edge costs are drawn randomly from an unknown distribution D. We assume that we can sample cost vectors c efficiently and i.i.d. from D to obtain a training set. Denote by H the set of all labeled spanning trees in G, and, for each T ∈ H, let η(T, c) = c(T ) − c(T * ) denote the error of T with respect to the edge costs c, where T * is an MST of G with respect to the edge costs c. As c is drawn randomly from D, the value η(T, c) is a random variable. Our goal is to learn a prediction T p ∈ H that (approximately) minimizes the expected error E c∼D [η(T, c)] over all T ∈ H.
We show that there is an efficient learning algorithm that determines a tree prediction that has nearly optimal expected cost with high probability and has a sample size polynomial in n and η max , an upper bound on η(T, c). The existence and value of such an upper bound depends on the unknown distribution D. Thus, to select the correct value of η max when determining the training set size, we require such minimal prior knowledge of D, which does not seem unreasonable in applications.
Theorem 7. Let η max be an upper bound on η(T, c) andT = arg min T ∈H E c∼D [η(T, c)]. Under the assumptions above (in particular, that the graph is complete and has a fixed number n of vertices), and for any ε, δ ∈ (0, 1), there exists a learning algorithm that returns a T p ∈ H such that Proof. We show how to adapt the classical Empirical Risk Minimization (ERM) algorithm (see, e.g., [63]). ERM first i.i.d. samples a trainingset S = {c 1 , . . . , c m } of m edge weight vectors from D. Then, it returns a tree T p ∈ H that minimizes the empirical error η S ( Recall that H is the set of all labeled spanning trees in a complete graph of n vertices. By Cayley's formula [22], |H| = n n−2 . Since H is finite, it satisfies the uniform convergence property (cf. [60], or observe that H has finite VC-dimension and cf. [63]). Given a sample of size it holds that E c∼D [η(T p , c)] ≤ E c∼D [η(T , c)] + ε with probability at least (1 − δ), where T p is the spanning tree learned by ERM (cf. [60,64]). It remains to bound the running time of ERM. While the sampling stage of ERM is polynomial in m, naively computing a T p ∈ H that minimizes the empirical error η S (T p ) might be problematic because of H's exponential size. However, we show that computing T p corresponds to an MST problem, well-known to be solvable in polynomial time.
Denote by T * i an MST for cost vector c i . By definition of η(T, c), we can write the empirical error as for each T ∈ H. Since 1 m and m i=1 c i (T * i ) are independent of T , the problem of computing a T ∈ H that minimizes η S (T ) corresponds to minimizing η S (T ) = We show a similar result for learning a predicted tour. Again, assume that G = (V, E) is complete and has a fixed number n of vertices. Let T be the set of all tours, i.e., the set of all permutations of V . Let η(τ, c) = c(τ ) − c(τ * ), where τ ∈ T , τ * is an optimal tour w.r.t. cost vector c, and c(τ ) is the cost of tour τ assuming that the next vertex v in τ is always visited via a shortest path in the graph induced by the previous vertices in τ and v. Our goal is to learn a predicted tour τ p ∈ T that (approximately) minimizes the expected error E c∼D [η(τ, c)] over all τ ∈ T . As |T | = n! ∈ O(n n ), and assuming an upper bound η max on η(τ, c), we apply ERM with the same sample complexity as in Theorem 7. However, the problem of computing a τ ∈ T that minimizes the empirical error in trainingset S contains TSP. Thus, unless P = N P , we settle for an exponential running time.
Theorem 8. Let η max be an upper bound on η(τ, c) andτ = arg min τ ∈T E c∼D [η(τ, c)]. Under the assumptions above (in particular, that the graph is complete and has a fixed number n of vertices), and for any ε, δ ∈ (0, 1), there exists a learning algorithm that returns a τ p ∈ T such that E c∼D [η(τ p , c)] ≤ E c∼D [η(τ , c)] + ε with probability at least (1 − δ). It does so using a training set of size m ∈ O( (n·log n−log δ)·η 2 max ε 2 ) and in time polynomial in m but exponential in n.
Proof. Since |T | = n! ∈ O(n n ), and assuming an upper bound η max on η(τ, c), we again apply ERM with the same sample complexity as in Theorem 7.
Using the same argumentation as in the proof of Theorem 7, we can show that, for a training set S = Thus, it remains to argue about the computation of the τ p ∈ T that minimizes where τ * i is the optimal tour for cost vector c i . Since 1 m and m i=1 c i (τ * i ) are independent of the actual predicted tour τ p , a tour τ p minimizes the empirical error if and only if it minimizes m i=1 c i (τ p ). Since the problem of computing this tour contains TSP, it is NP-hard and we settle for an exponential running time. We can find τ p by computing m i=1 c i (τ ) for each τ ∈ T . This can be done in running time O(m · |T |) = O(m · n n ) by iterating through all elements of S × T .

Experimental analysis
We present the main results of our empirical experiments and discuss their significance with respect to our algorithms' performance.
We analyze the performance of the robustification scheme for various instances, namely, real world city road networks, symmetric graphs of the TSPlib library [57,61], and special artificially generated graphs. We use the empirical competitive ratio as performance measure; for an algorithm A, it is defined as the average of the ratio A I /OPT I over all input instances I in our experiments. Since the offline optimum OPT I is the optimal TSP tour which is NP-hard to compute, we lower bound this value by the cost of an MST for instance I, which we can compute efficiently. This leads to larger empirical competitive ratios, but the relative differences between any two algorithms remains the same.
To evaluate learning-augmented algorithms, we compute a (near) perfect prediction and iteratively worsen it to get further predictions. Again, due to the intractability of the underlying TSP problem, we use heuristics to determine a "perfect" prediction, namely Christofides' algorithm [25] and 2-opt [26]. Such weaker input disfavors our algorithms as having better predictions can only improve the performance of our learningaugmented algorithms. The relative prediction error is defined as the ratio between the prediction error and the cost of an MST for the instance.
For the experiments, we consider the classical exploration algorithms depth first search (DFS), nearest neighbor (NN), and hierarchical depth first search (HDFS), as well as the constant-competitive algorithm for graphs of bounded genus, including planar graphs, called BLOCKING [38,51]. Regarding learningaugmented algorithms we look at the algorithm that follows a prediction (FP). We denote by R(A, λ) the modified robustification scheme with parameter λ > 0 applied to an algorithm A.

Implementation details
The simulation software is written in Rust (2018 edition) and available on GitHub 1 . There are also instructions to reproduce all presented experiments, as well as generated predictions and simulation outputs which were used to create the figures in this document. We executed all experiments in Ubuntu 18.04.5 on a machine with two AMD EPYC ROME 7542 CPUs (64 cores in total) and 1.96 TB RAM.
General implementation details We first note that edge costs are represented as unsigned integers. We use Prim's algorithm to compute an MST of a graph. For computing a minimum cost perfect matching in a general graph, as required in Christofides' algorithm, we use the Blossom V [40] implementation of a modified variant of Edmonds' Blossom algorithm to solve this problem efficiently. Regarding the exploration algorithms, the implementation of DFS always explores the cheapest unexplored edge first. The nodes in the input graphs are indexed by integers, and all algorithms use this total order to break ties. The exploration always starts at the vertex with index 0.
Prediction Generation We compute perfect predictions using Christofides' algorithm [25] and further improve these by the 2-opt local search heuristic [26]. Given such a "perfect" prediction, we generate worse predictions by iteratively increasing its total cost using the reversed 2-opt algorithm. That is, we reverse a subsequence of length at least 2 such that this reversion increases the total cost.

Experimental results
In the following, we describe the results of our experiments.
Comparison of robustification schemes For our experiments, we use the modified robustification scheme over the basic scheme. This is because we observed that the former performs overall better in our experiments although it has a slightly worse theoretic robustness guarantee. We present the results for both variants for the learning-augmented setting for the city of Stockholm, which is the largest city graph we consider, in Figure 1. The basic robustification scheme does not improve over NN even for small prediction errors, whereas the modified variant gives a significantly better performance for this case. For large errors, the modified robustification scheme with λ = 0.5 does indeed perform worse than the basic scheme. For λ = 0.75, it performs as good as the basic scheme for large errors, while it still improves upon NN for the case of good predictions.
TSPLib instances We consider the 72 graphs of the TSPlib library with at most 600 nodes (for performance reasons) and evaluate the classical exploration algorithms as well as their robustified variants. We construct instances directly from the provided XML files and round all edge weights to integers. The results are displayed in Figure 2. Observe that NN outperforms HDFS and BLOCKING. While for small values of λ the performance of the robustified algorithms stays close to that of their base variants, it improves quickly with an increasing λ and eventually converges to that of NN. This illustrates that if NN performs well, our robustification scheme exploits this and improves algorithms performing worse. Note that TSPlib provides complete graphs and our implementation of DFS explores a closest unexplored child first. Thus, DFS and NN act identically. We display the standard deviations of this experiment in Table 1.   Rosenkrantz graphs This experiment looks at graphs on which NN is known to perform badly. Specifically, we consider a family of graphs that are artificially constructed in [59] in order to show a lower bound of Ω(log n) on the competitive ratio. Each member of the family corresponds to a size parameter i and consists of n = Θ(2 i ) nodes. The cost of a NN tour increases linearly with i. Forcing NN to incur a large exploration cost in these graphs requires a specific tie breaking [59]. We accomplish this by scaling up all edge costs and then breaking ties by slightly modifing these costs appropriately. We refer to this family as Rosenkrantz graphs. There exist variations of the Rosenkrantz construction, that suggest that we can expect similar experimental results, even for Euclidean graphs and unit weights [36]. Besides NN, we consider the algorithms BLOCKING, HDFS and FP (relative error of 5) with robustification parameters 0, 1, and 20, respectively. Again, DFS acts like NN on these graphs.
The results (Figure 3) show that the slight robustification R(FP, 1) improves FP's performance significantly. This remains true for large i, even though NN is performing increasingly bad here. If we increase the amount of robustification, i.e., R(FP, 20), the slope is equal to NN's slope, but it still outperforms NN and FP. Surprisingly, for HDFS, this drawback does not appear: R(HDFS, 20) does indeed perform worse than for smaller λ's, but its competitive ratio does not grow as i increases. For R(HDFS, 1) there is almost no drop in performance when compared to HDFS. In summary, we have indications that even a slight robustification clearly improves algorithms that otherwise perform badly without the performance degrading too much when NN performs poorly. Even more interestingly, these experiments actually show that the robustification scheme applied to an online algorithm robustifies NN as well. Since NN generally performs notably well, c.f. Figure 2, this may be     useful in practice as protection against unlikely but possible bad scenarios for NN; in particular, in safety relevant applications where solutions have to satisfy strict performance bounds.
City road networks Finally, we provide experiments to evaluate our learning-augmented algorithm in the context of the real-world task of exploring a city road network. To this end, we consider the ten largest (by population) capitals in Europe with a population less than one million. Our instances represent the road networks of these cities, built with OSMnx [19] from OpenStreetMap data [54]. 2 We used the name of the city and the network type drive as input. The sizes of the resulting city graphs are displayed in Table 2. The observed standard deviations in this experiment are given in Table 3. The generated graphs are connected.
For each instance, we generate 150 predictions with relative errors ranging from 0 up to 30. The average results (Figures 4a and 4b) indicate that, for relative errors less than 2.5, we improve upon the best performing classical algorithms NN and DFS by using R(FP, λ) with λ < 1, while the increase of FP for large errors is significantly smaller after robustification. Moreover, R(FP, 0.5) and R(FP, 0.75) perform only slightly worse than HDFS and BLOCKING for large relative errors.
We conclude that, given predictions of somewhat reasonable quality, it is possible to beat the best known online algorithms in terms of solution quality, while still providing the security that, even if some predictions turn out to be bad, the consequences are not too harsh. While "somewhat reasonable" appears to be a relative error of roughly 2.5, recall that our perfect predictions are only approximate tours, which may be a constant factor away from the optimal tour. With logistic companies in mind, where margins are tight and every potential for optimization needs to be taken advantage of (while still making sure that trucks do arrive eventually), this seems to be a potentially useful outcome.

Conclusion
We initiate the study of learning-augmented algorithms for the classical online graph exploration problem. By carefully interpolating between the algorithm that blindly follows any given prediction and Nearest Neighbor, we are able to give a learning-augmented online algorithm whose theoretical worst-case bound linearly depends on the prediction error. In particular, if the prediction is close to perfect, this substantially improves upon any known online algorithm without sacrificing the worst-case bound. We complement these theoretical results by computational experiments on various instances, ranging from symmetric graphs of the TSPLib library and Rosenkrantz graphs to city road networks. Moreover, we design a framework to robustify any given online algorithm by carefully interpolating between this algorithm and Nearest     Neighbor. This is potentially very interesting also in the area of stochastic optimization or when designing data-driven algorithms, that typically provide probabilistic guarantees but may perform very poorly in the worst case. It remains open whether online graph exploration (without additional information) allows for any constant-competitive algorithm.