<figure><img src="image_1.png" /></figure>

HAL
open science

# Online Search With a Hint

## Spyros Angelopoulos

► To cite this version:

Spyros Angelopoulos. Online Search With a Hint. 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), Jan 2021, Online Event, United States. pp.51:1–51:16, 10.4230/LIPIcs.ITCS.2021.51 . hal-02986250

HAL Id: hal-02986250

https://hal.science/hal-02986250

Submitted on 22 Nov 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Online Search with a Hint

**Spyros Angelopoulos**

Sorbonne Université, CNRS, Laboratoire d'informatique de Paris 6, LIP6, 75252 Paris, France

http://lip6.fr/Spyros.Angelopoulos

spyros.angelopoulos@lip6.fr

## Abstract

The *linear search* problem, informally known as the *cow path* problem, is one of the fundamental problems in search theory. In this problem, an immobile target is hidden at some unknown position on an unbounded line, and a mobile searcher, initially positioned at some specific point of the line called the *root*, must traverse the line so as to locate the target. The objective is to minimize the worst-case ratio of the distance traversed by the searcher to the distance of the target from the root, which is known as the *competitive ratio* of the search.

In this work we study this problem in a setting in which the searcher has a *hint* concerning the target. We consider three settings in regards to the nature of the hint: i) the hint suggests the exact position of the target on the line; ii) the hint suggests the direction of the optimal search (i.e., to the left or the right of the root); and iii) the hint is a general *k*-bit string that encodes some information concerning the target. Our objective is to study the *Pareto*-efficiency of strategies in this model. Namely, we seek optimal, or near-optimal tradeoffs between the searchers' performance if the hint is correct (i.e., provided by a trusted source) and if the hint is incorrect (i.e., provided by an adversary).

**2012 ACM Subject Classification** Theory of computation → Online algorithms

**Keywords and phrases** Search problems, searching on the line, competitive analysis, predictions

**Digital Object Identifier** 10.4230/LIPIcs.ITCS.2021.51

**Related Version** A full version of this paper is available at https://arxiv.org/pdf/2008.13729.pdf.

**Funding** Spyros Angelopoulos: Research benefited from the support of the FMJH Program PGMO and from the support to this program from EDF-THALES-ORANGE. Also partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).

**Acknowledgements** I am thankful to Thomas Lidbetter for his comments on an early version of this paper.

# 1 Introduction

Searching for a target is a common task in everyday life, and an important computational problem with numerous applications. Problems involving search arise in such diverse areas as drilling for oil in multiple sites, the forest service looking for missing backpackers, search-and-rescue operations in the open seas, and navigating a robot between two points on a terrain. All these problems involve a mobile *searcher* which must locate an immobile *target*, often also called *hider*, that lies in some unknown point in the *search domain*, i.e., the environment in which the search takes place. The searchers starts from some initial placement within the domain, denoted by *O*, which we call the *root*. There is, also, some underlying concept of quality of search, in the sense that we wish, in informal terms, for the searchers to be able to locate the target as efficiently as possible.

One of the simplest, yet fundamental search problems is searching on an infinite line that is unbounded both to the left and to the right of the root. In this problem, which goes back to Bellman [17] and Beck and Newman [10], the objective is to find a search strategy that

<figure><img src="image_3.png" /></figure>

© Spyros Angelopoulos;

licensed under Creative Commons License CC-BY

12th Innovations in Theoretical Computer Science Conference (ITCS 2021).

Editor: James R. Lee; Article No. 51; pp. 51:1–51:16

<figure><img src="image_4.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
51:2 Online Search with a Hint

minimizes the competitive ratio of search. More precisely, let S denote the search strategy, i.e., the sequence of moves that the searcher performs on the line. Given a target t, let d(S, t) denote the total distance that the searcher has traveled up to the time it locates the target, and d(t) the distance of t from O. We define the competitive ratio of S as

$$cr(S) = \sup_t \frac{d(S, t)}{d(t)}.$$

A strategy of minimum competitive ratio is called optimal. The problem of optimizing the competitive ratio of search on the line is known as the linear search problem (mostly within Mathematics and Operations Research), but is also known in Computer Science as the cow path problem.

It has long been known that the optimal (deterministic) competitive ratio of linear search is 9 [15], and is derived by a simple doubling strategy. Specifically, let the two semi-infinite branches of the line be labeled with 0, 1 respectively. Then in iteration i, with i ∈ N, the searcher starts from O, traverses branch i mod 2 to distance 2^i, and returns to the root.

Linear search, and its generalization, the m-ray search problem, in which the search domain consists of m semi-infinite branches have been studied in several settings. Substantial work on linear search was done in the '70s and '80s predominantly by Beck and Beck, see e.g., [11, 16, 12, 13, 14]. Gal showed that a variant of the doubling strategy is optimal for m-ray search [25, 26]. These results were later rediscovered and extended in [9].

Other related work includes the study of randomization [41] and [30]; multi-searcher strategies [35]; searching with turn cost [23, 3]; the variant in which some probabilistic information on the target is known [27, 28]; the related problem of designing hybrid algorithms [29]; searching with an upper bound on the distance of the target from the root [34] and [20]; fault tolerant search [22, 33]; and performance measures beyond the competitive ratio [31, 38, 4]. Competitive analysis has been applied beyond the linear and star search, for example in searching within a graph [32, 24, 6].

1.1 Searching with a hint

Previous work on competitive analysis of deterministic search strategies has mostly assumed that the searcher has no information about the target, whose position is adversarial to the search. In practice, however, we expect that the searcher may indeed have some information concerning the target. For instance, in a search-and-rescue mission, there may be some information on the last sighting of the missing person, or the direction the person had taken when last seen. The question then is: how can the searcher leverage such information, and to what possible extent?

If the hint comes from a source that is trustworthy, that is, if the hint is guaranteed to be correct, then the performance of search can improve dramatically. For example, in our problem, if the hint is the branch on which the target lies, then the optimal search is to explore that branch until the target is found, and the competitive ratio is 1. There is, however, an obvious downside: if the hint is incorrect, the search may be woefully inefficient since the searcher will walk eternally on the wrong branch, and the competitive ratio in this case is unbounded.

We are thus interested in analyzing the efficiency of search strategies in a setting in which the hint may be compromised. To this end, we first need to define formally the concept of the hint, as well as an appropriate performance measure for the search strategy. In general, the hint h is a binary string of size k, where the i-th bit is a response to a query $Q_i$. For example, one can define a single query Q as “Is the target within distance at most 100 from
O?” and a one-bit hint, so that the hint answers a range query. For another example, if $Q$=“Is the target to the left or to the right of O?”, then a 1-bit hint informs the researcher about the direction it should pursue. From the point of view of upper bounds (positive results), we are interested in settings in which the queries and the associated hints have some natural interpretation, such as the ones given above. From the point of view of lower bounds (impossibility results), we are interested on the limitations of general k-bit hint strings which may be associated with any query, as we will discuss in more detail later.

Concerning the second issue, namely evaluating the performance of a search strategy $S$ with a hint $h$, note first that $S$ is a function of $h$. We will analyze the competitiveness of $S(h)$ in a model in which the competitive ratio is not defined by a single value, but rather by a pair $(c_{S,h}, r_{S,h})$. The value $c_{S,h}$ describes the competitive ratio of $S(h)$ assuming that $h$ is trusted, and thus guaranteed to be correct. The value $r_{S,h}$ describes the competitive ratio of $S(h)$ when the hint is given by an adversarial source. More formally, we define

$$c_{S,h} = \sup_t \inf_h \frac{d(S(h), t, h)}{d(t)}, \quad \text{and} \quad r_{S,h} = \sup_t \sup_h \frac{d(S(h), t, h)}{d(t)}, \qquad (1)$$

where $d(S(h), t, h)$ denotes the distance traversed in $S(h)$ for locating a target $t$ with a hint $h$. We will call $c_{S,h}$ the consistency of $S(h)$, and $r_{S,h}$ the robustness of $S(h)$. To simplify notation, we will often write $S$ instead of $S(h)$ when it is clear from context that we refer to a strategy with a hint $h$.

For example, if the hint $h$ is the branch on which the target lies, then the strategy that always trusts the hint is $(1, \infty)$ competitive, whereas the strategy that ignores the hint entirely is $(9, 9)$-competitive. Our objective is then to find strategies that are provably Pareto-optimal or Pareto-efficient in this model, and thus identify the strategies with the best tradeoff between robustness and consistency.

Our model is an adaptation, to search problems, of the untrusted advice framework for online algorithms proposed by Angelopoulos et al. [5]. In their work, the online algorithm is given some additional information, or advice which may, or may not be correct. To the best of our knowledge, our setting is a first attempt to quantify, in an adversarial setting, the impact of general types of predictions in search games. It is also in line with recent advances on improving the performance of online algorithms using predictions, such as the work of Lykouris and Vassilvitskii [36], who introduced the concepts of consistency and robustness in the context of paging, and the work of Purohit et al. [39], who applied it to general online problems. Our framework for the k-bit hint is also related to other work in Machine Learning, such as clustering with k noisy queries, e.g., the work of Mazumdar and Saha [37].

It should be emphasized that there is previous work that has studied the impact of specific types of hints on the performance of search strategies, such as bounds on the maximum or the minimum distance of the target from the root, e.g., [34, 20, 27]. However, the hint in these works is always assumed to be trusted and correct.

## 1.2 Contribution

In this work we study the power of limitations of linear search with hints. Let $r \ge 9$ be a parameter that in general will denote the robustness of a search strategy, and let $b_r$ be defined as

$$b_r = \frac{\rho_r + \sqrt{\rho_r^2 - 4\rho_r}}{2}, \quad \text{where } \rho_r = (r - 1)/2.$$

We consider the following classes of hints:
51:4 Online Search with a Hint

■ The hint is the position of the target. Here, the hint describes the exact location of the target on the line: its distance from O, along with the branch (0 or 1) on which it lies. We present a strategy that is $(\frac{b_r-1}{b_r+1}, r)$-competitive, and we prove it is Pareto-optimal.

■ The hint is the branch on which the target lies. Here, the hint is information on whether the searcher is to the left or to the right of the root. We present a strategy that, given parameters $b > 1$ and $\delta \in (0, 1)$, has consistency $c = 1 + 2 \cdot (\frac{b^2}{b^2-1} + \delta \frac{b^3}{b^2-1})$, and robustness $r = 1 + 2 \cdot (\frac{b^2}{b^2-1} + \frac{1}{\delta}\frac{b^3}{b^2-1})$. Again, we prove that this strategy is Pareto-optimal.

■ The hint is a general k-bit string. In the previous settings, the hint is a single bit, which answers the corresponding query. Here we address the question: how powerful can be a single-bit hint, or more generally a k-bit hint? In other words, how powerful can k binary queries be for linear search? We give several upper and lower bounds on the competitiveness of strategies in this setting. First, we look at the case of a single-bit hint. Here, we give a 9-robust strategy that has consistency at most $1 + 4\sqrt{2}$, whereas we show that no 9-robust strategy can have consistency less than 5, for any associated query. For general robustness $r$, we give upper and lower bounds that apply to some specific, but broadly used class of strategies, including geometric strategies (see Section 2 for a definition and Theorem 10 for the statement of the result). For general $k$, and for a given $r \ge 9$, we give an r-robust strategy whose consistency decreases rapidly as function of $k$ (Proposition 11).

In terms of techniques, for the first setting described above (in which the hint is the position of the target), the main idea is to analyze a geometric strategy with “large” base, namely $b_r$, for $r \ge 9$. The technical difficulty here is the lower bound; to this end, we prove a lemma that shows, intuitively, that for any r-robust strategy, the search length of the i-th iteration cannot be too big compared to the previous search lengths (Lemma 2). This technical result may be helpful in more broad settings (e.g., we also apply it in the setting in which the advice is a general k-bit string).

Concerning the second setting, in which the hint describes the branch, we rely on tools developed by Schuierer [40] for lower-bounding the performance of search strategies; more precisely on a theorem for lower-bounding the supremum of a sequence of functionals. But unlike [40], we use the theorem in a parameterized manner, that allows us to express the tradeoffs between the consistency and the robustness of a strategy, instead of their average.

Concerning the third, and most general setting, our upper bounds (i.e., the positive results) come from a strategy that has a natural interpretation: it determines a partition of the infinite line into $2^k$ subsets, and the hint describes the partition in which the target lies. The lower bounds (negative results) come from information-theoretic arguments, as is typical in the field of advice complexity of online algorithms (see, e.g., the survey [21]).

The broader objective of this work is to initiate the study of search games with some limited, but potentially untrusted information concerning the target. As we will show, the problem becomes challenging even in a simple search domain such as the infinite line. The framework should be readily applicable to other search games, and the analysis need not be confined to the competitive ratio, or to worst-case analysis. For example, search games in bounded domains are often studied assuming a probability distribution on the target, with the objective to minimize the expected search time (for several such examples see the book [1]). However, very little work has addressed the setting in which the searcher may have access to hints, such as the High-Low search games described in Section 5.2 of [1], in which a searcher wants to locate a hider on the unit interval by a sequence of guesses. Again, our model is applicable, in that one would like to find the best tradeoff on the expected time to locate the target assuming a trusted or untrusted hint.
## 2 Preliminaries

In the context of searching on the line, a search strategy $X$ can be defined as an infinite set of pairs $(x_i, s_i)$, with $i \in \mathbb{N}$, $x_i \in \mathbb{R}_{\ge 1}$ and $s_i \in \{0, 1\}$. We call $i$ an *iteration* and $x_i$ the *length* of the $i$-th search *segment*. More precisely, in the $i$-th iteration, the searcher starts from the root $O$, traverses branch $s_i$ up to distance $x_i$ from $O$, then returns to $O$. It suffices to focus on strategies for which $x_{i+2} \ge x_i$, i.e., in any iteration the searcher always searches a new part of the line. We will sometimes omit the $s_i$'s from the definition of the strategy, if the direction is not important, i.e., the searcher can start by moving either to the left or to the right of $O$. In this case, there is the implicit assumption that $s_i$ and $s_{i+1}$ have complementary parities, since any strategy that revisits the same branch in consecutive iterations can be transformed to another strategy that is no worse, and upholds the assumption. We make the standing assumption that the target lies within distance at least a fixed value, otherwise every strategy has unbounded competitive ratio. In particular, we will assume that $t$ is such that $d(t) \ge 1$.

Given a strategy $X = (x_0, x_1, \dots)$ (which we will denote by $X = (x_i)$, for brevity), its competitive ratio is given by the expression

$$ \mathrm{cr}(X) = 1 + 2 \sup_{i \ge 0} \frac{\sum_{j=1}^{i} x_j}{x_{i-1}}, \qquad (2) $$

where $x_{-1}$ is defined to be equal to 1. This expression is obtained by considering all the worst-case positions of the target, namely immediately after the turn point of the $i$-th segment (see e.g., [40]).

Geometric sequences are important in search problems, since they often lead to efficient, or optimal strategies (see, e.g., Chapters 7 and 9 in [1]). We call the search strategy $G_b = (b^i)$ geometric with base $b$. From (2), we obtain that

$$ \mathrm{cr}(G_b) = 1 + 2 \frac{b^2}{b-1}. \qquad (3) $$

For example, for the standard doubling strategy in which $x_i = 2^i$, hence $b = 2$, the above expression implies a competitive ratio of 9.

For any $r \ge 4$ define $\rho_r$ to be such that $r = 1 + 2\rho_r$, thus $\rho_r = (r - 1)/2$. Moreover, from (3) and the definition of $b_r$, we have that $\mathrm{cr}(G_{b_r}) = r$.

In the context of searching with a hint, we will say that a strategy is $(c, r)$-competitive if it has consistency at most $c$ and robustness at most $r$; equivalently we say that the strategy is $c$-consistent and $r$-robust. Clearly, an $r$-robust strategy gives rise to a strategy with no hints, and with competitive ratio at most $r$.

We conclude with some definitions that will be useful in Section 4. Let $X = (x_0, x_1, \dots)$ denote a sequence of positive numbers. We define $\alpha_X$ as

$$ \alpha_X = \overline{\lim}_{n \to \infty} x_n^{1/n}. $$

We also define as $X^{+i}$ the subsequence of $X$ starting at $i$, i.e, $X^{+i} = (x_i, x_{i+1}, \dots)$. Last, we define the sequence $G_b(\gamma_0, \dots, \gamma_{n-1})$ as

$$ G_b(\gamma_0, \dots, \gamma_{n-1}) = (\gamma_0, \gamma_1 a, \gamma_2 a^2, \dots, \gamma_{n-1} a^{n-1}, \gamma_0 a^n, \gamma_1 a^{n+1}, \dots). $$
### 3 Hint is the position of the target

In this section we study the setting in which the hint is related to the exact position of the target. Namely, the hint $h$ describes the distance $d(t)$ of the target $t$ from the root, as well as the branch on which it hides. For any $r \ge 9$, we will give a strategy that is $(\frac{b_r+1}{b_r-1}, r)$-competitive. Moreover, we will show that this is Pareto-optimal. We begin with the upper bound.

**Theorem 1.** For any $r \ge 9$ there exists a $(\frac{b_r+1}{b_r-1}, r)$-competitive strategy for linear search in which the hint is the position of the target.

**Proof.** From the hint $h$, we have as information the distance $d(t)$ as well as the branch $t$ on which the target $t$ lies; without loss of generality, suppose that this branch is the branch 0. Recall that this information may or may not be correct, and the searcher is oblivious to this.

Consider the geometric strategy $G_{b_r} = (b_r^i)$, with $i \in \mathbb{N}$, and recall that $G_{b_r}$ is $r$-robust (as discussed in Section 2). There must exist an index $j_t$ such that $b_r^{j_t-2} < d(t) \le b_r^{j_t}$. Define $\lambda = b_r^{j_t}/d(t) \ge 1$, and let $G'$ denote the strategy $G' = (\{\frac{1}{\lambda}b_r^i, s_i\})$, where the $s_i$'s are defined such that that $s_{i+1} \ne s_i$, for all $i$, and $s_{j_t} = 0$.

In words, $G'$ is obtained by “shrinking” the search lengths of $G_{b_r}$ by a factor equal to $\lambda$, and by choosing the right parity of branch for starting the search, in a way that, if the hint is trusted, then in $G'$ the searcher will locate the target right as it is about to turn back to $O$ at the end of the $j_t$-th iteration.

Since $G_{b_r}$ is $r$-robust, so is the scaled-down strategy $G'$; this is because the worst-case competitive ratio is attained for targets hiding right after the turn points of the segments. It remains then to bound the consistency $c_{G'}$ of $G'$. Suppose that the hint is trusted. We have that

$$d(G', t) = \frac{1}{\lambda} \left( 2 \sum_{i=0}^{j_t-1} b_r^i + b_r^{j_t} \right),$$

and since $d(t) = b_r^{j_t}/\lambda$ we can bound $c_{G'}$ from above by

$$\frac{d(G', t)}{d(t)} = 1 + 2 \frac{b_r^{j_t} - 1}{b_r^{j_t}(b_r - 1)} \le 1 + \frac{2}{b_r - 1} = \frac{b_r + 1}{b_r - 1}.$$

We conclude that $G'$ is $(\frac{b_r+1}{b_r-1}, r)$-competitive.

<figure><img src="image_5.png" /></figure>

Next, we will show that the strategy of Theorem 1 is Pareto-optimal. To this end, we will need a technical lemma concerning the segment lengths of any $r$-robust strategy.

**Lemma 2.** For any $r$-robust strategy $X = (x_i)$, it holds that

$$x_i \le \left( b_r + \frac{b_r}{i+1} \right) x_{i-1},$$

for all $i \ge 1$, where $x_{-1}$ is defined to be equal to 1.

We obtain a useful corollary concerning the sum of the first $i-1$ search lengths of an $r$-robust strategy.

**Corollary 3.** For any $r$-robust strategy $X = (x_i)$, it holds that

$$\sum_{j=0}^{i-1} x_j \ge \frac{x_i}{1 + \frac{1}{i+1}} \left( \frac{b_r}{b_r - 1} - \frac{i+2}{i+1} \right),$$

and for every $\epsilon \in (0, 1]$, there exists $i_0$ such that for all $i > i_0$, $\sum_{j=0}^{i-1} x_j \ge (\frac{1}{b_r-1} - \epsilon)x_i$.
We can now show a lower bound on the competitiveness of every strategy that matches the upper bound of Theorem 1.

**Theorem 4.** For every $(c, r)$-competitive strategy for linear search in which the hint is the position of the target, it holds that $c \ge \frac{b_r+1}{b_r-1} - \epsilon$, for any $\epsilon > 0$.

**Proof.** Let $X = (x_i)$ denote an $r$-robust strategy, with a hint that specifies the position of a target $t$. Suppose that $X$ locates the target at the $j_t$-th iteration. We have that

$$c = \frac{d(X, t)}{d(t)} = \frac{2 \sum_{i=0}^{j_t-1} x_i + d(t)}{d(t)} \ge \frac{2 \sum_{i=0}^{j_t-1} x_i + x_{j_t}}{x_{j_t}} = 1 + 2 \frac{\sum_{i=0}^{j_t-1} x_i}{x_{j_t}}.$$

Note that the target $t$ can be chosen to be arbitrarily far from $O$, which means that $j_t$ can be unbounded (otherwise the strategy would not have bounded robustness). From Corollary 3 this implies that $\sum_{i=0}^{j_t-1} x_i$ can be arbitrarily close to $x_{j_t} \frac{1}{b_r-1}$, and therefore $c$ is arbitrarily close to $1 + 2 \frac{1}{b_r-1} = \frac{b_r+1}{b_r-1}$, which concludes the proof. ◀

## 4 Hint is the direction of search

In this section we study the setting in which the hint is related to the direction of the search. More precisely, the hint is a single bit that dictates whether the target is to the left or to the right of the root $O$. Again, we are interested in Pareto-optimal strategies with respect to competitiveness: namely, for any fixed $r \ge 9$, what is the smallest $c$ such that there exist $(c, r)$-competitive strategies?

A related problem was studied by Schuierer [40], which is called biased search. One defines the left and right competitive ratios, as the competitive ratio of a search, assuming that the target hides to the left of the root, or to the right of the root, respectively. However, the researcher does not know the target's branch. Of course we know that the maximum of the left and the right competitive ratios is at least 9 (and for the doubling strategy, this is tight). [40] shows that for any search strategy on the line (not necessarily 9-robust), the average of the left and the right competitive ratios is at least 9. At first glance, one may think that this could be an unsurprising, and perhaps even trivial result; however this is not the case. The proof in [40] is not straightforward, and relies in a generalization of a theorem of [25] which lower bounds the supremum of a sequence of functionals by the supremum of much simpler, geometric functionals. We will discuss this theorem shortly.

The problem studied in [40] is related to our setting: the left and right competitive ratios correspond to the consistency $c$ and the robustness $r$ of the strategy. Hence from [40] we know that $c + r \ge 18$. However, there is a lot of room for improvement. In this section we will show a much stronger tradeoff between $c$ and $r$, and we will further prove that it is tight. For example, we will show that for any $(c, r)$-competitive strategy, if $c$ approaches 5 from above, then $r$ approaches infinity (in contrast, in this case, the lower bound of [40] yields $r \ge 13$). In fact, we will show that $c + r$ is minimized when $c = r = 9$. To this end, we will apply a parameterized analysis based on Schuierer's approach. We begin with the upper bound, by analyzing a specific strategy.

**Theorem 5.** For every $b \ge 1$, and $\delta \in (0, 1]$, there is a $(c, r)$-competitive strategy for linear search with the hint being the direction of search, in which

$$c = 1 + 2 \cdot \left( \frac{b^2}{b^2 - 1} + \delta \frac{b^3}{b^2 - 1} \right) \text{ and } r = 1 + 2 \cdot \left( \frac{b^2}{b^2 - 1} + \frac{1}{\delta} \frac{b^3}{b^2 - 1} \right).$$
51:8 Online Search with a Hint

**Proof.** Suppose, without loss of generality, that the hint points to branch 0. Consider a strategy $X = (\{x_i, i \text{ mod } 2\})$, which starts with branch 0, and alternates between the two branches. This strategy has consistency and robustness given by the following expressions, as a consequence of (2):

$$c = 1 + 2 \cdot \sup_{k \ge 0} \left\{ \frac{\sum_{i=0}^{2k+1} x_i}{x_{2k}} \right\} \quad \text{and} \quad r = 1 + 2 \cdot \sup_{k \ge 0} \left\{ \frac{\sum_{i=0}^{2k} x_i}{x_{2k-1}} \right\}, \qquad (4)$$

where $x_{-1}$ is defined to be equal to 1.

In addition, the search lengths of $X$ are defined by

$$x_i = b^i, \text{ if } i \text{ even and } x_i = \delta b^i, \text{ if } i \text{ is odd},$$

where we require that $b > 1$, and $\delta \in (0, 1]$. Note that $X$ is “biased” with respect to branch 0, which makes sense since the hint points to that branch.

Substituting these values into (4), we obtain that

$$c = 1 + 2 \cdot \sup_{k \ge 0} \left\{ \frac{\sum_{i=0}^{k} b^{2i}}{b^{2k}} + \delta \frac{\sum_{i=0}^{k} b^{2i+1}}{b^{2k}} \right\} = 1 + 2 \cdot \sup_{k \ge 0} \left\{ \frac{b^{2(k+1)} - 1}{(b^2 - 1)b^{2k}} + \delta \frac{b^{2k+3} - 1}{(b^2 - 1)b^{2k}} \right\} \\ \le 1 + 2 \cdot \left( \frac{b^2}{b^2 - 1} + \delta \frac{b^3}{b^2 - 1} \right).$$

Similarly, we have that

$$r = 1 + 2 \cdot \sup_{k \ge 0} \left\{ \frac{1}{\delta} \frac{\sum_{i=0}^{k} b^{2i}}{b^{2k-1}} + \frac{\sum_{i=0}^{k-1} b^{2i+1}}{b^{2k-1}} \right\} = 1 + 2 \cdot \sup_{k \ge 0} \left\{ \frac{1}{\delta} \frac{b^{2(k+1)} - 1}{(b^2 - 1)b^{2k-1}} + \frac{b^{2k+1} - 1}{(b^2 - 1)b^{2k-1}} \right\} \\ \le 1 + 2 \cdot \left( \frac{1}{\delta} \frac{b^3}{b^2 - 1} + \frac{b^2}{b^2 - 1} \right). \quad \blacksquare$$

For example, if $\delta = 1$, and $b = 2$, then Theorem 5 shows that there exists a (9,9)-competitive strategy. Interestingly, the theorem shows that as the consistency $c$ approaches 5 from above, the robustness $r$ of the strategy must approach infinity. This is because the function $\frac{b^2}{b-1}$ is minimized for $b = 2$, and hence for $c$ to approach 5 from above, it must be that $b$ approaches 2, and $\delta$ approaches 0. But then $\frac{1}{\delta}$ must approach infinity, and so must $r$.

We will show that the strategy of Theorem 5 is Pareto-optimal. To this end, we will use the following theorem of [40]. Recall the definitions of $\alpha_X$, $X^{+i}$ and $G_a(\gamma_0, \dots, \gamma_{n-1})$ given in Section 2.

**► Theorem 6 (Theorem 1 in [40]).** Let $p, q$ be two positive integers, and $X = (x_0, x_1, \dots)$ a sequence of positive numbers with $\sup_{n \ge 0} x_{n+1}/x_n < \infty$ and $\alpha_X > 0$. Suppose that $F_k$ is a sequence of functionals that satisfy the following properties:

(1) $F_k(X)$ depends only on $x_0, x_1, \dots, x_{pk+q}$,

(2) $F_k(X)$ is continuous in every variable, for all positive sequences $X$,

(3) $F_k(aX) = F_k(X)$, for all $a > 0$,

(4) $F_k(X + Y) \le \max(F_k(X), F_k(Y))$, for all positive sequences $X, Y$, and

(5) $F_{k+i}(X) \ge F_k(X^{+ip})$, for all $i \ge 1$.

Then there exist $p$ positive numbers $\gamma_0, \gamma_1, \gamma_{p-1}$ such that

$$\sup_{0 \le k < \infty} F_k(X) \ge \sup_{0 \le k < \infty} F_k(G_{\alpha_X}(\gamma_0, \dots, \gamma_{p-1})).$$
We will use Theorem 6 to prove a tight lower bound on the competitiveness of any strategy X.

**Theorem 7.** For every $(c, r)$-competitive strategy, there exists $\alpha > 1$, and $\delta \in (0, 1]$ such that $c \ge 1 + 2 \cdot (\frac{\alpha^2}{\alpha^2-1} + \delta \frac{\alpha^3}{\alpha^2-1})$, and $r \ge 1 + 2 \cdot (\frac{\alpha^2}{\alpha^2-1} + \frac{1}{\delta} \frac{\alpha^3}{\alpha^2-1})$.

**Proof.** Let $X = (x_0, x_1, \dots)$ denote a $(c, r)$-competitive strategy, and suppose, without loss of generality, that the hint specifies that the target is in the branch labeled 0. There are two cases concerning $X$: either the first exploration is on the branch labeled 0, or on the branch labeled 1. Let us assume the first case; at the end, we will argue that the second case follows from a symmetrical argument. As we argued in the proof of Theorem 5, in this case the competitiveness of $X$ is described by (4). Let us define the functionals

$$C_k = \frac{\sum_{i=0}^{2k+1} x_i}{x_{2k}} \quad \text{and} \quad R_k = \frac{\sum_{i=0}^{2k} x_i}{x_{2k-1}}.$$

Then we have that

$$c = 1 + 2 \cdot \sup_{k \ge 0} C_k \quad \text{and} \quad r = 1 + 2 \cdot \sup_{k \ge 0} R_k. \qquad (5)$$

The functional $C_k$ satisfies the conditions of Theorem 6 with $p = 2$, as shown in [40] therefore there exist $\gamma_0, \gamma_1 > 0$ such that

$$\sup_{k \ge 0} C_k \ge \sup_{k \ge 0} C_k(G_{\alpha_X}(\gamma_0, \gamma_1)) = \sup_{k \ge 0} \frac{\gamma_0 + \gamma_1 \alpha_X + \gamma_0 \alpha_X^2 + \dots + \gamma_0 \alpha_X^2 k + \gamma_1 \alpha_X^{2k+1}}{\gamma_0 \alpha_X^{2k}} \\ = \sup_{k \ge 0} \left\{ \frac{\sum_{i=0}^k \alpha_X^{2i}}{\alpha_X^{2k}} + \frac{\gamma_1}{\gamma_0} \frac{\sum_{i=0}^k \alpha_X^{2i+1}}{\alpha_X^{2k}} \right\}.$$

If $\alpha_X \le 1$, then the above implies that $\sup_{k \ge 0} C_k = \infty$ (another way of dismissing this case is that if $\alpha_X \le 1$, then $X$ is bounded and the two branches are not explored to infinity, as required by any strategy of bounded consistency). We can thus assume that $\alpha_X > 1$, and we obtain that

$$\sup_{k \ge 0} C_k \ge \sup_{k \ge 0} \left\{ \frac{\alpha_X^{2k+2} - 1}{(\alpha_X^2 - 1)\alpha_X^{2k}} + \frac{\gamma_1}{\gamma_0} \frac{\alpha_X^{2k+3} - 1}{(\alpha_X^2 - 1)\alpha_X^{2k}} \right\} = \frac{\alpha_X^2}{\alpha_X^2 - 1} + \frac{\gamma_1}{\gamma_0} \frac{\alpha_X^3}{\alpha_X^2 - 1}. \qquad (6)$$

We can lower-bound $r$ using a similar argument, and obtain

$$\sup_{k \ge 0} R_k \ge \sup_{k \ge 0} \left\{ \frac{\gamma_0}{\gamma_1} \frac{\alpha_X^{2k+2} - 1}{(\alpha_X^2 - 1)\alpha_X^{2k-1}} + \frac{\alpha_X^{2k+1} - 1}{(\alpha_X^2 - 1)\alpha_X^{2k-1}} \right\} = \frac{\gamma_0}{\gamma_1} \frac{\alpha_X^3}{\alpha_X^2 - 1} + \frac{\alpha_X^2}{\alpha_X^2 - 1}. \qquad (7)$$

Let us define $\delta = \frac{\gamma_1}{\gamma_0} > 0$. The result follows then by combining (5), (6) and (7). Note that if we require that $c \le r$, it must be that $\delta \le 1$, since $\alpha_X > 1$.

It remains to consider the symmetric case, in which in $X$, the first explored branch is branch 1. In this case the analysis is essentially identical: in (5) we substitute $C_k$ with $R_k$ and vice versa, in the expressions of $c$ and $r$, and in the resulting lower bounds we require that $\delta > 1$. ◀

It is important to note that in the proof of Theorem 7 we used the fact that the values $\gamma_0$ and $\gamma_1$ depend only on $X$ and not on any functionals defined over $X$, as follows from the proof of Theorem 6 in [40].
51:10 Online Search with a Hint

Theorem 7 implies that any (c, r)-competitive strategy X is such that

$$c+r \geq 2+4\frac{\alpha_X^2}{\alpha_X^2-1}+2(\delta+\frac{1}{\delta})\frac{\alpha_X^3}{\alpha_X^2-1},$$

which is minimized at $\delta = 1$, hence $c+r$ is minimized only if $c = r = 1 + 2\frac{\alpha_X^2}{\alpha_X^2-1} \geq 9$. We conclude that the average of a strategy's consistency and robustness (or the average of the left and right competitive ratio, in the terminology of [40]) is minimized only by strategies that are 9-robust.

5 Hint is a k-bit string

In this section we study the setting in which the researcher has access to a *hint string* of k bits. We first consider the case $k = 1$. In Section 5.1 we will study the more general case.

It should be clear that even a single-bit hint is quite powerful, and that the setting is non-trivial. For example, the bit can indicate the right direction for search, as discussed in Section 4, but it allows for other possibilities, such as whether the target is at distance at most D from the root, for some chosen D. The latter was studied in [27], assuming that the hint is correct. More generally, the hint can induce a partition of the infinite line into two subsets $L_1$ and $L_2$, such that the hint dictates whether the target is hiding on $L_1$ or $L_2$.

We begin with the upper bound, namely we describe a specific search strategy, and the corresponding hint bit (as well as the query which it responds). Consider two strategies of the form

$$X_1 = (b_r^i) \text{ and } X_2 = (b_r^{i+\frac{1}{2}}).$$

Note that both $X_1$ and $X_2$ are r-robust: $X_1$ is geometric with base $b_r$, whereas $X_2$ is obtained from $X_1$ by scaling the search lengths by a factor equal to $b_r^{1/2}$. We also require that the two strategies start by searching the same branch, hence in every iteration, they likewise search the same branch.

We can now define a strategy Z with a single bit hint, which indicates whether the researcher should choose strategy $X_1$ or strategy $X_2$. For any given target, one of the two strategies will outperform the other, assuming the hint is trusted. Thus, an equivalent interpretation of the hint is in the form of a partition of the infinite line into two sets $L_1$ and $L_2$, such that if the target is in $L_i$, then $X_i$ is the preferred strategy, with $i \in [1, 2]$. See Figure 1 for an illustration.

The following result bounds the performance of this strategy, and its proof will follow as a corollary of a more general theorem concerning k-bit strings that we show in Section 5.1 (Theorem 11).

**Proposition 8.** For given $r \geq 9$, the above-defined strategy Z is r-robust and has consistency at most $1 + 2^{\frac{a^{3/2}}{a-1}}$, where $a = b_r$, if $r \leq 10$, and $a = 3$, otherwise.

Note that if $r = 9$, then Z has consistency $1+4\sqrt{2} \approx 6.657$. For $r \in [9, 10]$, the consistency of Z is decreasing in r, as one expects. For $r \geq 10$, the consistency is $1+3\sqrt{3} \approx 6.196$.

We now turn our attention to lower bounds. To this end, we observe that a single-bit hint $h$ has only the power to differentiate between two fixed strategies, say $X = (x_i)$, and $Y = (y_i)$, i.e., two strategies that are not defined as functions of $h$. We say that Z is determined by strategies X and Y, and the bit $h$.
<figure><img src="image_6.png" /><figcaption>Figure 1 Illustration of strategy Z, using the first four segments of strategies $X_1$ and $X_2$. Blue (dark) and orange (faded) segments correspond to the search segments of strategies $X_1$ and $X_2$, respectively. The parts of the line in blue (resp. orange) indicate the hiding intervals for the target such that $X_1$ (resp. $X_2$) is preferred, and thus chosen by the hint.</figcaption></figure>

## Setting up the lower-bound proofs

We give some definitions and notation that will be used in the proofs of Theorems 9 and 10. Let $Z$ be determined by strategies $X$ and $Y$, and a single-bit hint $h$. Let $C$ denote the lower bound on the consistency of $Z$ that we wish to show. For given $i$, define $T_X^i = 2 \sum_{j=0}^i x_j + x_{i-1}$, and similarly for $T_Y^i$. Define also $q = r/C$.

Note that a searcher that follows strategy $X$ will turn towards the root at iteration $i-1$, after having explored some branch $\beta_i \in \{0, 1\}$ up to distance $x_{i-1}$. Thus, $X$ barely misses a target that may be hiding at branch $\beta_i$, and at distance $x_{i-1} + \epsilon$ from $O$, with $\epsilon > 0$ infinitesimally small, and thus requires time $T_X^i$ to discover it. We will denote this hiding position of a potential target by $P_i$. If, on the other hand, the searcher follows $Y$, then it can locate a target at position $P_i$ at a time that may be smaller than $T_X^i$; let $\tau_i$ denote this time. When strategy $Y$ locates a target hiding at $P_i$, it does so by exploring branch $\beta_i$ to a length greater than $x_{i-1}$. Let $j_i$ be the iteration at which $Y$ locates $P_i$, thus $y_{j_i} \ge x_{i-1}$. Last, let $Q_i$ denote the position in branch $\beta_i$ and at distance $y_{j_i} + \epsilon$ from $O$. In words, if a target hides at $Q_i$, then strategy $Y$ barely misses it when executing the search segment $y_{j_i}$.

We first show a lower bound on the consistency of 9-robust strategies. In the proof we will not replace all parameters with the corresponding values (e.g., we will sometimes use $r$ to refer to robustness, instead of the value 9). We do so because the arguments in the proof can be applied to other settings, as will become clear in the proof of Theorem 10.

**Theorem 9.** For any $(c, 9)$-competitive strategy with single-bit hint, it holds that $c \ge 5$.

**Proof.** We will prove the result by way of contradiction. Let $C = 5$, and suppose that there is a strategy $Z$ of consistency strictly less than $C$. Let $Z$ be determined by two fixed strategies $X$ and $Y$. Both $X$ and $Y$ must be $r$-robust (i.e., 9-robust), otherwise $Z$ cannot be $r$-robust.

Fix $i_0 \in \mathbb{N}$. Suppose first that $i_0$ is such that for all $i \ge i_0$, we have $\tau_i \ge \frac{1}{q} T_X^i$. In this case, for a target at position $P_i$, defined earlier, $X$ requires time $T_X^i$ to locate it, whereas $Y$ requires time at least $\tau_i \ge \frac{1}{q} T_X^i$ to locate it, thus the minimum time $X$ or $Y$ can locate this target is $\frac{1}{q} T_X^i$. Therefore, the consistency of $Z$ is at least

$$c \ge \sup_{i \ge i_0} \frac{T_X^i}{q \cdot x_{i-1}} = \frac{1}{q} \sup_{i \ge i_0} \frac{T_X^i}{x_{i-1}} \ge \frac{C}{r} \cdot r = C, \quad (8)$$
51:12 Online Search with a Hint

which is a contradiction. Here, we used crucially the fact that $\sup_{i \ge i_0} \frac{T_X^i}{x_{i-1}} \ge 9$, for any 9-robust strategy $X$ and any $i_0^1$. Specifically, there exists sufficiently large $i$ such that $T_X^i$ is arbitrarily close to $9x_{i-1}$.

It must then be that $i_0$ does not obey the property described above, namely for some $i \ge i_0$ we have that $\tau_i \le \frac{1}{q} T_X^i$. Since $X$ is $r = 9$-robust, it must also be that $\frac{T_X^i}{x_{i-1}} \le r$, as can be seen if a target hides at $P_i$. We therefore obtain that

$$ \tau_i \le \frac{1}{q} T_X^i \le \frac{1}{q} \cdot r \cdot x_{i-1} = C x_{i-1}. \qquad (9) $$

We can also give a lower bound on $\tau_i$, as follows. Recall that we denote by $y_{j_i}$ the segment at which strategy $Y$ locates a target at position $P_i$. For arbitrarily small $\epsilon > 0$, we can choose $i_0$ sufficiently large, which also implies that $j_i$ can also be sufficiently large (since otherwise $Y$ would not have finite robustness), so that Corollary 3 applies. To simplify the arguments, in the remainder of the proof we will assume that the corollary applies with $\epsilon = 0$; this has no effect on correctness, since we want to show a lower bound of the form $C - \delta$ on the consistency, and $\epsilon$ can be made as small as we want in comparison to $\delta$. More precisely, we obtain that

$$ \tau_i = 2 \sum_{l=0}^{j_i} y_l + x_{i-1} \ge \frac{2}{b_r - 1} y_{j_i} + x_{i-1}. \qquad (10) $$

Combining (9) and (10) we have

$$ y_{j_i} \le \frac{C-1}{2}(b_r - 1)x_{i-1}. \qquad (11) $$

In particular, since $r = 9$ and $C = 5$, we have that $y_{j_i} \le 2x_{i-1}$.

Consider now a target at position $Q_i$, and recall that this position is at distance infinitesimally larger than $y_{j_i}$. We will show that in both $X$ and $Y$, there exists an $i \ge i_0$ such that the searchers walks distance at least $C \cdot y_{j_i}$ before reaching this position, which implies that $Z$ has consistency at least $C$, and which yields the contradiction.

Consider first strategy $Y$. In this case, the searchers walks distance at least $T_Y^{j_i}$, to reach $Q_i$, from the definition of $T_Y$. Since $r = 9$, we know that $\sup_{i \ge i_0} \frac{T_Y^{j_i}}{y_{j_i}} \ge 9$, for any $i_0$, hence there exists an $i \ge i_0$ such that the distance walked by the searchers is at least $r \cdot y_{j_i}$, and hence at least $C \cdot y_{j_i}$.

Consider now strategy $X$. In this case, in order to arrive at position $Q_i$, the searchers needs to walk distance $T_X^i$, then at least an additional distance $y_{j_i} - x_{i-1}$ to reach $Q_i$. Let us denote by $D_X^i$ this distance. We have

$$ \begin{aligned} D_X^i &= T_X^i + y_{j_i} - x_{i-1} \\ &\ge 9x_{i-1} + y_{j_i} - x_{i-1} \quad (\text{From Corollary 3 and since } T_X^i \text{ is arbitrarily close to } 9x_{i-1}) \\ &= 8x_{i-1} + y_{j_i}. \end{aligned} \qquad (12) $$

We then bound the ratio $D_X^i / y_{j_i}$ from below as follows.

$$ \begin{aligned} \frac{D_X^i}{y_{j_i}} &\ge \frac{8x_{i-1} + y_{j_i}}{y_{j_i}} = 1 + 8 \frac{x_{i-1}}{y_{j_i}} \\ &\ge 1 + 8 \frac{x_{i-1}}{2 \cdot x_{i-1}} \qquad (\text{From the fact that } y_{j_i} \le 2 \cdot x_{i-1}) \\ &= 5. \end{aligned} \qquad (13) $$

We thus conclude that $C \ge 5$, which yields the contradiction, and completes the proof. ◀

<footnote n="1">¹ In general, this statement is not immediately true for arbitrary $r > 9$.</footnote>
Showing a lower bound on the consistency, as a function of general $r > 9$ is quite hard, even for the case of a single-bit hint. The reason is that as $r$ increases, so does the space of $r$-robust strategies. For example, any geometric strategy $G_b$ has robustness $r$, as long as $b \in [\frac{\rho_r - \sqrt{\rho_r^2 - 4\rho_r}}{2}, \frac{\rho_r + \sqrt{\rho_r^2 - 4\rho_r}}{2}]$. In what follows we will show a lower bound for a class of strategies which we call asymptotic. More precisely, recall the definition of $T_X^i$. We call an $r$-robust strategy $S$ asymptotic if $\sup_{i \ge i_0} \frac{T_X^i}{x_{i-1}} = r$, for all fixed $i_0$. In words, in an asymptotic strategy, the worst-case robustness (i.e., the worst case competitive ratio without any hint) can always be attained by targets placements sufficiently far from the root. All geometric strategies, including the doubling strategy, have this property, and this holds for many strategies that solve search problems on the line and the star, such as the ones described in the introduction. Note also that the strategies $X_1$ and $X_2$ that determine the strategy $Z$ in the statement of Proposition 8 are asymptotic, since they are near-geometric. Thus, the lower bound we show in the next theorem implies that in order to substantially improve consistency, one may have to resort to much more complex, and most likely irregular strategies.

**Theorem 10.** Let $Z$ denote a strategy with 1-bit hint which is determined by two $r$-robust, asymptotic strategies $X$ and $Y$. Then $Z$ is $(c, r)$-competitive, with $c \ge 1 + \frac{2b_r}{b_r - 1}$.

## 5.1 k-bit hints

Here we consider the general setting in which the hint is a $k$-bit string, for some fixed $k$. First, we give an upper bound that generalizes Proposition 8. We will adapt an algorithm proposed in [5] for the online bidding problem with untrusted advice. Consider $2^k$ strategies $X_0, \dots, X_{2^k-1}$, where

$$X_j = (a^{i+\frac{j}{2^k}})_{i \ge 0},$$

for some $a$ to be determined later, and where all the $X_j$ have the same parity: they all search the same branch in their first iteration and, therefore in every iteration as well. Define a strategy $Z$, which is determined by $X_0, \dots, X_{2^k-1}$, and in which the $k$-bit hint $h$ dictates the index $j$ of the chosen strategy $X_j$. In other words, $h$ answers the query $Q_h=\text{"which strategy among } X_0, \dots, X_{2^k-1} \text{" should the searcher choose?"}$. An equivalent interpretation is that the statements of the $X_j$'s induce a partition of the line, such that for every given target position, one of the $X_j$'s is the preferred strategy. Thus every bit $i$ of the hint can be thought, equivalently, as the answer to a partition query $Q_i$ of the line, i.e., of the form "does the target belong in a subset $L_i$ of the line or not?".

**Theorem 11.** For every $r \ge 9$, the strategy $Z$ defined above is $(c, r)$-competitive with $c \le 1 + 2\frac{a^{\frac{1+1}{2^k}}}{a-1}$, where $a = b_r$, if $\rho_r \le \frac{(1+2^k)^2}{2^k}$, and $a = 1 + 2^k$, otherwise.

For example, for $r = 9$, we obtain a strategy that is $(1 + 2^{2+\frac{1}{2^k}}, 9)$-competitive. Thus, the consistency decreases rapidly, as function of $k$, and approaches 5.

Last, it is easy to see that no 9-robust strategy with hint string of any size can have consistency better than 3. To see this, let $X$ be any 9-robust strategy, and let $i_t$ be the iteration in which it locates a target $t$. Since $t$ can be arbitrarily far from $O$, $i_t$ is unbounded, and thus Corollary 3 applies. We thus have that

$$\frac{d(X, t)}{d(t)} = \frac{\sum_{j=0}^{i_t-1} x_j + d(t)}{d(t)} = 1 + 2 \frac{\sum_{j=0}^{i_t-1} x_j}{d(t)} \ge 1 + 2 \frac{\sum_{j=0}^{i_t-1} x_j}{x_{i_t}} \ge 1 + 2 \frac{(1-\epsilon)x_{i_t}}{x_{i_t}},$$

thus the consistency of $X$ cannot be smaller that $3 - \epsilon$, for any $\epsilon$. The same holds then for any strategy that is determined by any number of 9-robust strategies, and thus for any hint.
## 6 Conclusion

We introduced a model that allows us to analyze the performance of search strategies with some information on the target. As explained in the introduction, the eventual goal is to apply this model to many other search problems, within or beyond competitive analysis, and for deterministic or randomized strategies. A good starting point is the generalization of linear search, namely the *m*-ray star problem, which has a long history of research, and has a broad connection to resource allocation problems (see, e.g. [33, 8, 18]). In this context, there are *m* tasks and the goal is to allocate resources to each of them, without knowing ahead of time which task will be the crucial one. The hint can be interpreted as some information concerning the instance (e.g., the index of the crucial task, or the time we may have to allocate to each one of the tasks in order to guarantee some good solution).

Another direction is to consider the case in which the hint comes with some error $\eta$, as in recent works in Machine Learning [36, 39, 37]. The ultimate goal would be to describe Pareto-efficient solutions in which the competitive ratio of the search also degrades gently as $\eta$ increases. This is a challenging task, since one will have to strike a balance between the robustness, the consistency, and the competitive ratio, both from the point of upper and lower bounds. But there is a major obstacle as far as linear search is concerned. That is, unlike other online problems, the competitive ratio of linear search is not necessarily an increasing function of the error $\eta$. For example, consider the case in which there is a prediction of the position of the target, and suppose that we have a “bad” search strategy, which does not perform well if the error is small (i.e., turns right before discovering the target). However, it is possible that with significant error, the target happens to be found just as the searcher is about to turn and return to *O*, in one of the iterations. In this case, the strategy is quite efficient. These are counterintuitive complications that need to be taken into consideration in terms of defining efficiency in this setting.

In very recent work [7], we addressed the above questions in the context of a related problem in AI, namely the problem of *contract scheduling* under the *acceleration ratio*. There are interesting connections between searching on the line and contract scheduling [19, 2], and the techniques we developed and the results we showed in [7] should be readily applicable in searching on the line with noisy predictions.

## References

1. Steve Alpern and Shmuel Gal. *The theory of search games and rendezvous*. Kluwer Academic Publishers, 2003.

2. Spyros Angelopoulos. Further connections between contract-scheduling and ray-searching problems. In *Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI)*, pages 1516–1522, 2015.

3. Spyros Angelopoulos, Diogo Arsénio, and Christoph Dürr. Infinite linear programming and online searching with turn cost. *Theoretical Computer Science*, 670:11–22, 2017.

4. Spyros Angelopoulos, Christoph Dürr, and Shendan Jin. Best-of-two-worlds analysis of online search. In *36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019*, volume 126 of *LIPIcs*, pages 7:1–7:17, 2019.

5. Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc P. Renault. Online computation with untrusted advice. In *11th Innovations in Theoretical Computer Science Conference, ITCS 2020*, pages 52:1–52:15, 2020.

6. Spyros Angelopoulos, Christoph Dürr, and Thomas Lidbetter. The expanding search ratio of a graph. *Discrete Applied Mathematics*, 260:51–65, 2019.
7 Spyros Angelopoulos and Shahin Kamali. Contract scheduling with predictions, 2020. Available as arXiv:2011.12439.

8 Yossi Azar, Andrei Z. Broder, and Mark S. Manasse. On-line choice of on-line algorithms. In Vijaya Ramachandran, editor, *Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA*, pages 432-440. ACM/SIAM, 1993.

9 Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory G.E. Rawlins. Searching in the plane. *Information and Computation*, 106:234-244, 1993.

10 Anatole Beck. On the linear search problem. *Naval Research Logistics*, 2:221-228, 1964.

11 Anatole Beck. More on the linear search problem. *Israel Journal of Mathematics*, 3(2):61-70, 1965.

12 Anatole Beck and Micah Beck. Son of the linear search problem. *Israel Journal of Mathematics*, 48(2-3):109-122, 1984.

13 Anatole Beck and Micah Beck. The linear search problem rides again. *Israel Journal of Mathematics*, 53(3):365-372, 1986.

14 Anatole Beck and Micah Beck. The revenge of the linear search problem. *SIAM journal on control and optimization*, 30(1):112-122, 1992.

15 Anatole Beck and D.J. Newman. Yet more on the linear search problem. *Israel Journal of Mathematics*, 8:419-429, 1970.

16 Anatole Beck and Peter Warren. The return of the linear search problem. *Israel Journal of Mathematics*, 14(2):169-183, 1973.

17 R. Bellman. An optimal search problem. *SIAM Review*, 5:274, 1963.

18 Daniel S. Bernstein, Lev Finkelstein, and Shlomo Zilberstein. Contract algorithms and robots on rays: unifying two scheduling problems. In *Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI)*, pages 1211–1217, 2003.

19 Daniel S. Bernstein, Theodore J. Perkins, Shlomo Zilberstein, and Lev Finkelstein. Scheduling contract algorithms on multiple processors. In *Proceedings of the Eighteenth AAAI Conference on Artificial Intelligence (AAAI)*, pages 702–706, 2002.

20 Prosenjit Bose, Jean-Lou De Carufel, and Stephane Durocher. Searching on a line: A complete characterization of the optimal solution. *Theoretical Computer Science*, 569:24-42, 2015.

21 Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. Online algorithms with advice: A survey. *SIGACT News*, 47(3):93-129, 2016.

22 Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil M. Shende. Search on a line by byzantine robots. In *27th International Symposium on Algorithms and Computation, ISAAC*, volume 64 of *LIPIcs*, pages 27:1-27:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.

23 Erik D. Demaine, Sándor Fekete, and Shmuel Gal. Online searching with turn cost. *Theoretical Computer Science*, 361:342-355, 2006.

24 Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen. Competitive online approximation of the optimal search ratio. *SIAM Journal on Computing*, 38(3):881-898, 2008.

25 Shmuel Gal. A general search game. *Israel Journal of Mathematics*, 12:32-45, 1972.

26 Shmuel Gal. Minimax solutions for linear search problems. *SIAM Journal on Applied Mathematics*, 27:17-30, 1974.

27 Patrick Jaillet and Matthew Stafford. Online searching. *Operations Research*, 49:234-244, 1993.

28 Ming-Yang Kao and Michael Littman. Algorithms for informed cows. In *Proceedings of the AAAI 1997 Workshop on Online Search*, 1997.

29 Ming-Yang Kao, Yuan Ma, Michael Sipser, and Yiqun Yin. Optimal constructions of hybrid algorithms. *Journal of Algorithms*, 29(1):142-164, 1998.
51:16 Online Search with a Hint

30 Ming-Yang Kao, John H Reif, and Stephen R Tate. Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. *Information and Computation*, 131(1):63–80, 1996.

31 David G. Kirkpatrick. Hyperbolic dovetailing. In *Proceedings of the 17th European Symposium on Algorithms (ESA)*, pages 616–627, 2009.

32 Elias Koutsoupias, Christos H. Papadimitriou, and Michalis Yannakakis. Searching a fixed graph. In *Proc. of the 23rd Int. Colloq. on Automata, Languages and Programming (ICALP)*, pages 280–289, 1996.

33 Andrey Kupavskii and Emo Welzl. Lower bounds for searching robots, some faulty. In *Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing*, pages 447–453, 2018.

34 Alejandro López-Ortiz and Sven Schuierer. The ultimate strategy to search on m rays? *Theoretical Computer Science*, 261(2):267–295, 2001.

35 Alejandro López-Ortiz and Sven Schuierer. On-line parallel heuristics, processor scheduling and robot searching under the competitive framework. *Theoretical Computer Science*, 310(1–3):527–537, 2004.

36 Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In *Proceedings of the 35th International Conference on Machine Learning*, ICML, pages 3302–3311, 2018.

37 Arya Mazumdar and Barna Saha. Clustering with noisy queries. In *Advances in Neural Information Processing Systems 30*, pages 5788–5799. Curran Associates, Inc., 2017.

38 Andrew McGregor, Krzysztof Onak, and Rina Panigrahy. The oil searching problem. In *Proceedings of the 17th European Symposium on Algorithms (ESA)*, pages 504–515, 2009.

39 Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In *Advances in Neural Information Processing Systems*, volume 31, pages 9661–9670, 2018.

40 Sven Schuierer. Lower bounds in online geometric searching. *Computational Geometry: Theory and Applications*, 18(1):37–53, 2001.

41 Sven Schuierer. A lower bound for randomized searching on m rays. In *Computer Science in Perspective*, pages 264–277, 2003.