Spyros Angelopoulos
email: spyros.angelopoulos@lip6.fr

Christoph Dürr
email: christoph.durr@lip6.fr

Shendan Jin
email: shendan.jin@lip6.fr

Best-Of-Two-Worlds Analysis of Online Search

Keywords: 2012 ACM Subject Classification Theory of computation → Online algorithms Online computation, search problems, linear search, performance measures Digital Object Identifier 10.4230/LIPIcs.STACS.2019.7

Introduction

Searching for a hidden target is an important paradigm in computer science and operations research, with numerous applications. A typical search problem involves an environment, a mobile searcher (who may, or may not, have knowledge of the environment) and a hider (sometimes also called target) who hides at some position within the environment that is oblivious to the searcher. The objective is to define a search strategy, i.e., a traversal of the environment, that optimizes a certain efficiency criterion. A standard approach to the latter is by means of competitive analysis, in which we seek to minimize the worst-case cost for

7:2

Best-Of-Two-Worlds Analysis of Online Search locating the target, divided by some concept of "optimal" solution; e.g., the minimum cost to locate the target once its position is known. Even prior to the advent of online computation and competitive analysis, search games had already been studied under such normalized measures within operations research [START_REF] Beck | Yet more on the linear search problem[END_REF]. Explicit studies of the competitive ratio and the closely related search ratio were given in [START_REF] Baeza-Yates | Searching in the plane[END_REF] and [START_REF] Koutsoupias | Searching a fixed graph[END_REF], respectively, and led to the development of online searching [START_REF] Jaillet | Online searching[END_REF][START_REF] Berman | Online Algorithms: The State of the Art, chapter Online searching and navigation[END_REF] as a subfield of online computation. See also [START_REF] Alpern | The theory of search games and rendezvous[END_REF] for an in-depth treatment of search games, including the role of payoff functions that capture the competitive ratio.

In this work we revisit one of the simplest, yet fundamental search problems, namely the linear search, or, informally, cow-path problem. The setting involves an infinite (i.e., unbounded) line, with a point O designated as its origin, a searcher which is initially placed at the origin, and an immobile target which is at some position on the line that is unknown to the searcher. More specifically, the searcher does not know whether the hider is at the left branch or at the right branch of the line. The searcher's strategy S defines its exploration of the line, whereas the hider's strategy H is determined by its placement on the line. Given strategies S, H, the cost of locating the hider, denoted by c(S, H) is the total distance traversed by the searcher at the first time it passes over H. Let |H| denote the distance of the hider from the origin. The competitive ratio of S, denoted by cr(S), is the worst-case normalized cost of S, among all possible hider strategies. Formally,

cr(S) = sup H c(S, H) |H| . ( 1
)
It has long been known [START_REF] Beck | On the linear search problem[END_REF][START_REF]A general search game[END_REF] that the competitive ratio of linear search is 9, and is achieved by a simple doubling strategy: in iteration i, the searcher starts from O, explores branch i mod 2 at a length equal to 2 i , and then returns to O. However, this strategy is not uniquely optimal; in fact, it is known that there is an infinite number of competitively optimal strategies for linear search (see Lemma 6 in Section 3). In particular, consider an "aggressive" strategy, which in each iteration searches a branch to the maximum possible extent, while maintaining a competitive ratio equal to 9. This can be achieved by searching, in iteration i, branch i mod 2 to a length equal to (i + 2)2 i+1 (see Corollary 8).

While both doubling and aggressive are optimal in terms of competitive ratio, there exist realistic situations in which the latter may be preferable to the former. Consider, for example, a search-and-rescue mission for a missing backpacker who has disappeared in one of two (very long) concurrent, hiking paths. Assuming that we select our search strategy from the space of 9-competitive strategies, it makes sense to choose one that is tuned to discovering new territory, rather than a conservative strategy that tends to often revisit already explored areas.

With the above observation in mind, we first need to quantify what constitutes efficiency in exploration. To this end, given a strategy S and l ∈ R + , we define D(S, l) as the cost incurred by S the first time the searcher has explored an aggregate length equal to l, combined in both branches. An efficient strategy should be such that D(S, l) is small, for all l. Unfortunately, this criterion by itself is insufficient: Consider a strategy that first searches one branch to a length equal to L, where L is very large. Then D(S, l) is as small as possible for all l < L; however, this is hardly a good strategy, since it all but ignores one of the branches (and thus its competitive ratio becomes unbounded as L → ∞).

To remedy this situation, we will instead use the above definition in a way that will allow us a pairwise comparison of strategies, which also considers all possible explored lengths. More formally, we define the following: Definition 1. Let S 1 , S 2 denote two search strategies, we define the discovery ratio of S 1 against S 2 , denoted by dr(S 1 , S 2 ), as

dr(S 1 , S 2 ) = sup l∈R + D(S 1 , l) D(S 2 , l) .
Moreover, given a class S of search strategies, the discovery ratio of S against the class S is defined as dr(S, S) = sup S ∈S dr(S, S ).

In the case S is the set Σ of all possible strategies, we simply call dr(S, S) the discovery ratio of S, and we denote it by dr(S).

Intuitively, the discovery ratio preserves the worst-case nature of competitive analysis, and at the same time bypasses the need for an "offline optimum" solution. Note that if a strategy S has competitive ratio c then it also has discovery ratio c; this follows easily from the fact that for every hider position H, c(S, H) ≥ D(S, |H|). However, the opposite is not necessarily true.

It is worth pointing out that one could have defined the discovery ratio over a discrete, countable space (i.e., the target hides at some integer distance from the origin), which turns out to be identical to the bijective ratio. This performance measure was introduced in [START_REF] Angelopoulos | Stochastic dominance and the bijective ratio of online algorithms[END_REF] as an extension of (exact) bijective analysis of online algorithms [START_REF] Angelopoulos | On the Separation and Equivalence of Paging Strategies[END_REF], and which in turn is based on the pairwise comparison of the costs induced by two online algorithms over all request sequences of a certain size. Bijective analysis has been applied in fundamental online problems (with a discrete, finite set of requests) such as paging and list update [START_REF] Angelopoulos | Paging and List Update under Bijective Analysis[END_REF], k-server [START_REF] Boyar | A Comparison of Performance Measures for Online Algorithms[END_REF][START_REF] Angelopoulos | Stochastic dominance and the bijective ratio of online algorithms[END_REF], and online search1 [START_REF] Boyar | A comparison of performance measures via online search[END_REF].

In what concerns linear search, in this work we choose to present the analysis over a "continuous" space of requests for two reasons. First, we demonstrate that this is indeed possible, which can be useful for other online problems which are defined over a continuous setting of requests (e.g., k-server problems defined over a metric space rather than over a finite graph). Second, the discretization introduces certain unnecessary and undesirable technical issues, e.g., in the choice of the "right" t for strategy R t ( see Lemma 11). While the analysis is still tractable for our problem, for more complex search domains such as star search, the discrete analysis may be too complicated to yield results. We further discuss the connections between the discovery and the bijective ratios in Section 4.

The above observation implies that the discovery ratio inherits the appealing properties of bijective analysis, which further motivate its choice. In particular, note that bijective analysis has helped to identify theoretically efficient algorithms which also tend to perform well in practice (such as Least-Recently-Used for paging [START_REF] Angelopoulos | Paging and List Update under Bijective Analysis[END_REF], and greedy-like k-server policies for certain types of metrics [START_REF] Angelopoulos | Stochastic dominance and the bijective ratio of online algorithms[END_REF]). Furthermore, if an algorithm has bijective ratio c, then its average cost, assuming a uniform distribution over all request sequences of the same length, is within a factor c of the average cost of any other algorithm. Thus, bijective analysis can be used to establish "best of both worlds" types of performance comparisons. In fact, assuming again uniform distributions, much stronger conclusions can be obtained, in that bijective analysis implies a stochastic dominance relation between the costs of the two algorithms [START_REF] Angelopoulos | Stochastic dominance and the bijective ratio of online algorithms[END_REF]. However, since the search domain is infinite, one must be careful in defining a uniform distribution of requests. More specifically, one could fix L ≥ 1 and consider the uniform density function on the space [-L, -1] ∪ [1, L] (where the origin is assumed to be at 0). Thus, the probability that a request is at distance at most x from the origin is (x -1)/(L -1). Our results then correspond to the setting in which L is unknown to the algorithm, and thus can be arbitrarily large. For known, and thus bounded L, the situation is much more complicated, since the optimal competitive ratio now depends on L and does not have a closed formula [START_REF] Bose | Searching on a line: A complete characterization of the optimal solution[END_REF]. Our overall techniques still apply but the results unavoidably will be much more technical, and probably not tight.

It should be noted that the central question we study in this work is related to a phenomenon that is not unusual in the realm of online computation. Namely, for certain online problems, competitive analysis results in very coarse performance classification of algorithms. This is due to the pessimistic, worst-case nature of the competitive ratio. The definitive example of an online problem in which this undesired situation occurs is the (standard) paging problem in a virtual memory system, which motivated the introduction of several analysis techniques alternative to the competitive ratio (see [START_REF] Dorrigiv | A Survey of Performance Measures for On-Line Algorithms[END_REF] for a survey). In our paper we demonstrate that a similar situation arises in the context of online search, and we propose a remedy by means of the discovery ratio. We emphasize, however, that in our main results, we apply the discovery ratio as supplementary to the competitive ratio, instead of using it antagonistically as a measure that replaces the competitive ratio altogether.

Contribution

We begin, in Section 2, by identifying the optimal tradeoff between the competitive ratio of a strategy and its discovery ratio (against all possible strategies). The result implies that there are strategies of discovery ratio 2 + , for arbitrarily small > 0, which is tight. As corollary, we obtain that strategy doubling has discovery ratio equal to 3. These results allow us to set up the framework and provide some intuition for our main results, but also demonstrate that the discovery ratio, on itself, does not lead to a useful classification of strategies, when one considers the entire space of strategies.

Our main technical results are obtained in Section 3. Here, we apply synthetically both the competitive and the discovery ratios. More precisely, we restrict our interest to the set of competitively optimal strategies, which we further analyze using the discovery ratio as a supplementary measure. We prove that the strategy aggressive, which explores the branches to the furthest possible extent while satisfying the competitiveness constraint, has discovery ratio 8 5 ; moreover, we show that this is the optimal discovery ratio in this setting. In contrast, we show that the strategy doubling has discovery ratio 7 3 . In addition, we provide evidence that such "aggressiveness" is requisite. More precisely, we show that any competitively optimal strategy that is also optimal with respect to the discovery ratio must have the exact same behavior as the aggressive strategy in the first five iterations.

In terms of techniques, the main technical difficulty in establishing the discovery ratios stems from answering the following question: given a length l ∈ R + , what is the strategy S that minimizes D(S, l), and how can one express this minimum discovery cost? This is a type of inverse or dual problem that can be of independent interest in the context of search problems, in the spirit of a concept such as the reach of a strategy [START_REF] Hipke | How to find a point in the line within a fixed distance[END_REF], also called extent in [START_REF] Jaillet | Online searching[END_REF] (and which is very useful in the competitive analysis of search strategies). We model this problem as a linear program for whose objective value we first give a lower bound; then we show this bound is tight by providing an explicit 9-competitive strategy which minimizes D(S, l).

Related work

The linear search problem was first introduced and studied in works by Bellman [START_REF] Bellman | An optimal search problem[END_REF] and Beck [START_REF] Beck | On the linear search problem[END_REF]. The generalization of linear search to m concurrent, semi-infinite branches is known as star search or ray search; thus linear search is equivalent to star search for m = 2. Optimal strategies for linear search under the (deterministic) competitive ratio were first given by [START_REF] Beck | Yet more on the linear search problem[END_REF]. Moreover [START_REF]Minimax solutions for linear search problems[END_REF] gave optimal strategies for the generalized problem of star search, a result that was rediscovered later [START_REF] Baeza-Yates | Searching in the plane[END_REF]. Some of the related work includes the study of randomization [START_REF] Kao | Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem[END_REF]; multi-searcher strategies [START_REF] López-Ortiz | On-line parallel heuristics, processor scheduling and robot searching under the competitive framework[END_REF]; multi-target searching [START_REF] Kirkpatrick | Hyperbolic dovetailing[END_REF][START_REF] Mcgregor | The oil searching problem[END_REF]; searching with turn cost [START_REF] Demaine | Online searching with turn cost[END_REF][START_REF] Angelopoulos | Infinite linear programming and online searching with turn cost[END_REF]; searching with an upper bound on the target distance [START_REF] Hipke | How to find a point in the line within a fixed distance[END_REF][START_REF] Bose | Searching on a line: A complete characterization of the optimal solution[END_REF]; fault-tolerant search [START_REF] Czyzowicz | Search on a Line by Byzantine Robots[END_REF]; and the variant in which some probabilistic information on target placement is known [START_REF] Jaillet | Online searching[END_REF][START_REF] Kao | Algorithms for informed cows[END_REF]. This list is not exclusive; see also Chapter 8 in the book [START_REF] Alpern | The theory of search games and rendezvous[END_REF].

Linear search and its generalization can model settings in which we seek an intelligent allocation of resources to tasks under uncertainty. For this reason, the problem and its solution often arises in the context of diverse fields such as AI (e.g., in the design of interruptible algorithms [START_REF] Bernstein | Contract algorithms and robots on rays: unifying two scheduling problems[END_REF][START_REF]Further connections between contract-scheduling and ray-searching problems[END_REF]) and databases (e.g., pipeline filter ordering [START_REF] Condon | Algorithms for Distributional and Adversarial Pipelined Filter Ordering Problems[END_REF]).

Strategy aggressive has been studied in [START_REF] Hipke | How to find a point in the line within a fixed distance[END_REF][START_REF] Jaillet | Online searching[END_REF] in the special case of maximizing the reach of a strategy (which informally is the maximum possible extent to which the branches can be searched without violating competitiveness) when we do not know the distance of the target from the origin. Although this gives some intuition that aggressive is indeed a good strategy, to the best of our knowledge, our work is the first that quantifies this intuition, in terms of comparing to other competitively optimal strategies using a well-defined performance measure.

Due to space limitations, some proofs are omitted or only sketched.

Preliminaries

In the context of linear search, the searcher's strategy can be described as an (infinite) sequence of lengths at which the two branches (numbered 0,1, respectively) are searched. Formally, a search strategy is determined by an infinite sequence of search segments {x 0 , x 1 , . . .} such that x i > 0 and x i+2 > x i for all i ∈ N, in the sense that in iteration i, the searcher starts from the origin, searches branch i mod 2 to distance x i from the origin, and then returns back to O. We require that the search segments induce a complete exploration of both branches of the line, in that for every d ∈ R + , there exist i, j ∈ N such that x 2i ≥ d, and x 2j+1 ≥ d.

The constraint x i+2 > x i implies that the searcher explores a new portion of the line in each iteration. It is easy to see that any other strategy X that does not conform to the above (namely, a strategy such that iterations i, i + 1 search the same branch, or a strategy in which x i+2 ≤ x i can be transformed to a conforming strategy X such that for any hider H, c(X , S) ≤ c(X, H)). For convenience of notation, we will define x i to be equal to 0, for all i < 0. Given a strategy X, we define T n (X) (or simply T n , when X is clear from context) to be equal to n i=0 x i . For n < 0, we define T n := 0. We say that the searcher turns in iteration i at the moment it switches directions during iteration i, namely when it completes the exploration of length x i and returns back to the origin. Moreover, at any given point in time t (assuming a searcher of unit speed), the number of turns incurred by time t is defined accordingly.

We will denote by Σ the set of all search strategies, and by Σ c the subset of Σ that consists of strategies with competitive ratio c. Thus Σ 9 is the set of competitively optimal strategies, and Σ ∞ ≡ Σ. When evaluating the competitive ratio, we will make the standard assumption that the target must be at distance at least 1 from O, since no strategy can have bounded competitive ratio if this distance can be arbitrarily small.

Strategies of optimal discovery ratio in Σ

We begin, by establishing the optimal tradeoff between the competitive ratio and the discovery ratio against all possible strategies. This will allow us to obtain strategies of optimal discovery ratio, and also setup some properties of the measure that will be useful in Section 3. Let X, Y , denote two strategies in Σ, with X = (x 0 , x 1 , . . .). From the definition of the discovery ratio we have that

dr(X, Y ) = sup i∈N sup δ∈(0,xi-xi-2] D(X, x i-1 + x i-2 + δ) D(Y, x i-1 + x i-2 + δ) .
Note that for i = 0, we have

D(X, x i-1 + x i-2 + δ) D(Y, x i-1 + x i-2 + δ) = D(X, δ) D(Y, δ) ≤ δ δ = 1.
This is because for all δ ≤ x 0 , D(X, δ) = δ, and for all δ > 0, D(Y, δ) ≥ δ. Therefore,

dr(X, Y ) = sup i∈N * sup δ∈(0,xi-xi-2] D(X, x i-1 + x i-2 + δ) D(Y, x i-1 + x i-2 + δ) . ( 2
)
The following theorem provides an expression of the discovery ratio in terms of the search segments of the strategy.

Theorem 2. Let X = (x 0 , x 1 , . . .). Then dr(X, Σ) = sup i∈N * 2 i-1 j=0 x j + x i-2 x i-1 + x i-2 .
Proof. Fix Y ∈ Σ. From the definition of search segments in X, we have that

D(X, x i-1 + x i-2 + δ) = 2 i-1 j=0 x j + x i-2 + δ, for δ ∈ (0, x i -x i-2 ]. (3)
Moreover, for every Y , we have

D(Y, x i-1 + x i-2 + δ) ≥ x i-1 + x i-2 + δ. ( 4
)
Substituting ( 3) and ( 4) in ( 2) we obtain

dr(X, Y ) ≤ sup i∈N * sup δ∈(0,xi-xi-2] 2 i-1 j=0 x j + x i-2 + δ x i-1 + x i-2 + δ ≤ sup i∈N * 2 i-1 j=0 x j + x i-2 x i-1 + x i-2 . ( 5
)
For the lower bound, consider a strategy Y i = (y i 0 , y i 1 , . . .), for which y i 0 = x i-1 + x i-2 + δ (the values of y i j for j = 0 are not significant, as long as Y i is a valid strategy). Clearly,

D(Y i , x i-1 + x i-2 + δ) = x i-1 + x i-2 + δ. Therefore, (2) implies dr(X, Y i ) ≥ sup δ∈(0,xi-xi-2] 2 i-1 j=0 x j + x i-2 + δ x i-1 + x i-2 + δ = 2 i-1 j=0 x j + x i-2 x i-1 + x i-2 . ( 6
)
The lower bound on dr(X, Σ) follows from dr(X, Σ) ≥ sup i∈N * dr(X, Y i ).

In particular, note that for i = 2, Theorem 2 shows that for any strategy X,

dr(X, Σ) ≥ 3x 0 + 2x 1 x 0 + x 1 ≥ 2.
We will show that there exist strategies with discovery ratio arbitrarily close to 2, thus optimal for Σ. To this end, we will consider the geometric search strategy defined as G α = (1, α, α 2 , . . .), with α > 1.

Lemma 3. For G α defined as above, we have dr(G α , Σ) = 2α 2 +α-1 α 2 -1 . In particular, Lemma 3 shows that the discovery ratio of G α tends to 2, as α → ∞, hence G α has asymptotically optimal discovery ratio. However, we can show a stronger result, namely that G α achieves the optimal trade-off between the discovery ratio and the competitive ratio. This is established in the following theorem. Note that the competitive ratio of G α is easily verified to be 1 + 2 α 2 α-1 (and is minimized for α = 2).

Theorem 4. For every strategy X ∈ Σ, there exists α > 1 such that dr(X, Σ) ≥ 2α 2 +α-1

α 2 -1
and cr(X) ≥ 1 + 2 α 2 α-1 . In order to prove Theorem 4, we will use of a result by Gal [START_REF]Search Games[END_REF] and Schuierer [START_REF] Schuierer | Lower bounds in online geometric searching[END_REF] which, informally, lower-bounds the supremum of an infinite sequence of functionals by the supremum of simple functionals of a certain geometric sequence, and which we state here in a simplified form. This result will allow us to lower bound the supremum of a sequence of functionals by the supremum of simple functionals of a geometric sequence. Given an infinite sequence X = (x 0 , x 1 , . . .), define X +i = (x i , x i+1 , . . .) as the suffix of the sequence X starting at x i . Theorem 5 ([22, 31]). Let X = (x 0 , x 1 , . . .) be a sequence of positive numbers, r an integer, and α = lim sup n→∞ (x n ) 1/n , for α ∈ R ∪ {+∞}. Let F i , i ≥ 0 be a sequence of functionals which satisfy the following properties: 1. F i (X) only depends on x 0 , x 1 , . . . , x i+r , 2. F i (X) is continuous for all x k > 0, with 0

≤ k ≤ i + r, 3. F i (λX) = F i (X), for all λ > 0, 4. F i (X + Y ) ≤ max(F i (X), F i (Y )), and 5. F i+1 (X) ≥ F i (X k+1 ), for all k ≥ 1, then sup 0≤i<∞ F i (X) ≥ sup 0≤i<∞ F i (G α ).
Proof of Theorem 4. Let X = (x 0 , x 1 , . . .) denote a strategy in Σ. From [START_REF] Angelopoulos | Paging and List Update under Bijective Analysis[END_REF] we know that dr(X, Σ)

≥ sup i F i (X),
where F i (X) is defined as the functional

2 i-1 j=0 xj +xi-2 xi-1+xi-2
. Moreover, the competitive ratio of X can be lower-bounded by cr(X)

≥ sup i F i (X), where F i (X) = 1 + 2 i+1 j=0 x j x i .
This follows easily by considering a hider placed at distance x i + , with → 0, at the branch that is searched by X in iteration i.

S TA C S 2 0 1 9 7:8

Best-Of-Two-Worlds Analysis of Online Search

It is easy to see that both F i (X) and F i (X) satisfy the conditions of Theorem 5 (this also follows from Example 7.3 in [START_REF] Alpern | The theory of search games and rendezvous[END_REF]). Thus, there exists α defined as in the statement of Theorem 5 such that dr(X, Σ)

≥ sup i F i (G α ) = 2 i-1 j=0 α j + α i-2 α i-1 + α i-2 , and (7)
cr(X, Σ)

≥ sup i F i (G α ) = 1 + 2 i+1 j=0 α j α i . ( 8
)
It is easy to verify that if α = 1, then dr(X, Σ), cr(X, Σ) = ∞. We can thus assume that α > 1, and thus obtain from ( 7), ( 8), after some manipulations, that dr(X, Σ)

≥ sup i 2(α 2 -1 α i-2 ) + α -1 α 2 -1 = 2α 2 + α -1 α 2 -1 , and cr(X, Σ) ≥ 1 + sup i 2 i+1 j=0 α j α i = sup i 1 + 2 α 2 -1 α i α -1 = 1 + 2 α 2 α -1 ,
which concludes the proof.

Note, however, that although G α , with α → ∞ has optimal discovery ratio, its competitive ratio is unbounded. Furthermore, strategy doubling ≡ G 2 has optimal competitive ratio equal to 9, whereas its discovery ratio is equal to 3. This motivates the topic of the next section.

The discovery ratio of competitively optimal strategies

In this section we focus on strategies in Σ 9 , namely the set of competitively optimal strategies. For any strategy X ∈ Σ 9 , it is known that there is an infinite set of linear inequalities that relate its search segments, as shown in the following lemma (see, e.g, [START_REF] Jaillet | Online searching[END_REF]).

Lemma 6.

The strategy X = (x 0 , x 1 , x 2 , . . .) is in Σ 9 if and only if its segments satisfy the following inequalities

1 ≤ x 0 ≤ 4, x 1 ≥ 1 and x n ≤ 3x n-1 - n-2 i=0
x i , for all n ≥ 1.

We now define a class of strategies in Σ 9 as follows. For given t ∈ [START_REF] Alpern | The theory of search games and rendezvous[END_REF][START_REF] Angelopoulos | On the Separation and Equivalence of Paging Strategies[END_REF], let R t denote the strategy whose search segments are determined by the linear recurrence

x 0 = t, and x n = 3x n-1 - n-2 i=0 x i , for all n ≥ 1.
In words, R t is such that for every n > 1, the inequality relating x 0 , . . . , x n is tight. The following lemma determines the search lengths of R t as function of t. The lemma also implies that R t is indeed a valid search strategy, for all t ∈ [START_REF] Alpern | The theory of search games and rendezvous[END_REF][START_REF] Angelopoulos | On the Separation and Equivalence of Paging Strategies[END_REF], in that x n > x n-2 , for all n, and x n → ∞, as n → ∞.

Lemma 7. The strategy R t is defined by the sequence

x n = t(1+ n 2 )2 n , for n ≥ 0. Moreover, T n (R t ) = t(n + 1)2 n .

7:9

Proof. The lemma is clearly true for n ∈ {0, 1}. For n ≥ 2, the equality

x n = 3x n-1 - n-2 i=0 x i implies that T n = n i=0 x i = 4x n-1 . Therefore, T n -T n-1 = 4x n-1 -4x n-2 ⇒ x n = 4(x n-1 -x n-2 ).
The characteristic polynomial of the above linear recurrence is ξ 2 -4ξ + 4, with the unique root ξ = 2. Thus, x n is of the form x n = (a + bn)2 n , for n ≥ 0, where a and b are determined by the initial conditions x 0 = t and x 1 = 3t. Summarizing, we obtain that for n ≥ 0 we have that x n = t(1 + n 2 )2 n , and

T n = 4x n-1 = t(n + 1)2 n .
Among all strategies in R t we are interested, in particular, in the strategy R 4 . This strategy has some intuitively appealing properties: It maximizes the search segments in each iteration (see Lemma 9) and minimizes the number of turns required to discover a certain length (as will be shown in Corollary 10). Using the notation of the introduction, we can say that R 4 ≡ aggressive. In this section we will show that aggressive has optimal discovery ratio among all competitively optimal strategies. Let us denote by xi the search segment in the i-th iteration in aggressive.

Corollary 8. The strategy aggressive can be described by the sequence xn = (n + 2)2 n+1 , for n ≥ 0. Moreover, T n (aggressive) = (n + 1)2 n+2 , for n ≥ 0.

The following lemma shows that, for any given n, the total length discovered by any competitively optimal strategy X at the turning point of the n-th iteration cannot exceed the corresponding length of aggressive. Its proof can also be found in [START_REF] Jaillet | Online searching[END_REF], but we give a different proof using ideas that we will apply later (Lemma 11). Lemma 9. For every strategy X = (x 0 , x 1 , . . .) with X ∈ Σ 9 , it holds that x n ≤ xn , for all n ∈ N, where xn is the search segment in the n-th iteration of aggressive. Hence, in particular, we have

x n + x n-1 ≤ xn + xn-1 , for all n ∈ N.
Proof. For a given n ≥ 0, let P n denote the following linear program.

max x n subject to 1 ≤ x 0 ≤ 4, x 1 ≥ 1, x i ≤ 3x i-1 - i-2 j=0 x j , 1 ≤ i ≤ n.
We will show, by induction on i, that for all i ≤ n,

x n ≤ (i + 2)2 i-1 x n-i -i2 i-1 T n-i-1 (X).
The lemma will then follow, since for i = n we have

x n ≤ (n + 2)2 n-1 x 0 ≤ (n + 2)2 n-1 • 4 = (n + 2)2 n+1 = xn ,
where the last equality is due to Corollary 8. We will now prove the claim. Note that, the base case, namely i = 1, follows directly from the LP constraint. For the induction hypothesis, suppose that for i ≥ 1, it holds that

x n ≤ (i + 2)2 i-1 x n-i -i2 i-1 T n-i-1 (X). (9)
S TA C S 2 0 1 9

7:10

Best-Of-Two-Worlds Analysis of Online Search

We will show that the claim holds for i + 1. Since

x n-i ≤ 3x n-i-1 -T n-i-2 (X), (10)
then 10) in ( 9))

x n ≤ (i + 2)2 i-1 (3x n-i-1 -T n-i-2 (X)) -i2 i-1 T n-i-1 (X) (subst. (
= (i + 2)2 i-1 (3x n-i-1 -T n-i-2 (X)) -i2 i-1 (T n-i-2 (X) + x n-i-1 ) (def. T n-i-1 ) = (i + 3)2 i x n-i-1 + (i + 1)2 i T n-i-2 (X), ( arranging terms)
which completes the proof of the claim.

Given strategy X and l ∈ R + , define m(X, l) as the number of turns that X has performed by the time it discovers a total length equal to l. Also define

m * (l) = inf X∈Σ9 m(X, l),
that is, m * (l) is the minimum number of turns that a competitively optimal strategy is required to perform in order to discover length equal to l. From the constraint x 0 ≤ 4, it follows that clearly m * (l) = 0, for l ≤ 4. The following corollary to Lemma 9 gives an expression for m * (l), for general values of l.

Corollary 10. For given l > 4, m * (l) = m(aggressive, l) = min{n ∈ N ≥1 : (3n + 5)2 n ≥ l}.
Proof. From Lemma 9, the total length discovered by any X ∈ Σ 9 at the turning point of the n-th iteration cannot exceed xn + xn-

1 for n ≥ 1, which implies that m * (l) = n, if l ∈ (x n-1 + xn-2 , xn + xn-1 ] for n ≥ 1. In other words, m * (l) = min{n ∈ N ≥1 : xn + xn-1 ≥ l}.
From Corollary 8, we have xn = (n + 2)2 n+1 , for n ≥ 0. Hence, m * (l) = min{n ∈ N ≥1 : (3n + 5)2 n ≥ l}.

The following lemma is a central technical result that is instrumental in establishing the bounds on the discovery ratio. For a given l ∈ R + , define

d * (l) = inf X∈Σ9 D(X, l).
In words, d * (l) is the minimum cost at which a competitively optimal strategy can discover a length equal to l. Trivially, d * (l) = l if l ≤ 4. Lemma 11 gives an expression of d * (l) for l > 4 in terms of m * (l); it also shows that there exists a t ∈ [START_REF] Alpern | The theory of search games and rendezvous[END_REF][START_REF] Angelopoulos | On the Separation and Equivalence of Paging Strategies[END_REF] such that the strategy R t attains this minimum cost.

We first give some motivation behind the purpose of the lemma. When considering general strategies in Σ, we used a lower bound on the cost for discovering a length l as given by ( 4), and which corresponds to a strategy that never turns. However, this lower bound is very weak when one considers strategies in Σ 9 . This is because a competitive strategy needs to turn sufficiently often, which affects considerably the discovery costs.

We also give some intuition about the proof. We show how to model the question by means of a linear program. Using the constraints of the LP, we first obtain a lower bound on its objective in terms of the parameters l and m * (l). In this process, we also obtain a lower bound on the first segment of the strategy (x 0 ); this is denoted by t in the proof. In the next step, we show that the strategy R t has discovery cost that matches the lower bound on the objective, which suffices to prove the result. Lemma 11. For l > 4, it holds

d * (l) = D(R t , l) = l • 6m * (l) + 4 3m * (l) + 5 , where t = l • 2 2-m * (l) 3m * (l) + 5 ∈ (1, 4].
Proof. Let X = (x 0 , x 1 , . . .) ∈ Σ 9 denote the strategy which minimizes the quantity D(X, l).

Then there must exist a smallest n ≥ m * (l) such that the searcher discovers a total length l during the n-th iteration. More precisely, suppose that this happens when the searcher is at branch n mod 2, and at some position p (i.e., distance from O), with p ∈ (x n-2 , x n ]. Then we have x n-1 + p = l, and

d * (l) = D(X, l) = 2 n-1 i=0 x i + p = 2 n-1 i=0 x i + (l -x n-1 ) = 2 n-2 i=0 x i + x n-1 + l.
Therefore, d * (l) is the objective of the following linear program.

min 2 n-2 i=0 x i + x n-1 + l subject to x n + x n-1 ≥ l, 1 ≤ x 0 ≤ 4, x i-2 ≤ x i , i ∈ [2, n] 1 ≤ x i ≤ 3x i-1 - i-2 j=0 x j , i ∈ [1, n].
Recall that n ≥ m * (l) is a fixed integer. Let Obj denote the objective value of the linear program. We claim that, for 1

≤ i ≤ n, x n-i ≥ 2 2-i 3i + 5 l + 3i -1 3i + 5 T n-i-1 and Obj ≥ 6i + 4 3i + 5 l + 9 • 2 i 3i + 5 T n-i-1 .
The claim provides a lower bound of the objective, since for i = n it implies that

x 0 ≥ 2 2-n 3n + 5 l and Obj ≥ 6n + 4 3n + 5 l ≥ 6m * (l) + 4 3m * (l) + 5 l,
where the last inequality follows from the fact n ≥ m * (l). We will argue later that this lower bound is tight. First, we prove the claim, by induction on i, for all i ≤ n. We first show the base case, namely i = 1. Since x n ≤ 3x n-1 -T n-2 and x n + x n-1 ≥ l, it follows that

x n-1 ≥ l -x n ≥ l -(3x n-1 -T n-2 ) ⇒ x n-1 ≥ l 4 + T n-2 4 , hence Obj = l + 2T n-2 + x n-1 ≥ l + 2T n-2 + l 4 + T n-2 4 = 5 4 l + 9 4 T n-2 ,
thus the base case holds. For the induction step, suppose that

x n-i ≥ 2 2-i 3i + 5 l + 3i -1 3i + 5 T n-i-1 and Obj ≥ 6i + 4 3i + 5 l + 9 • 2 i 3i + 5 T n-i-1 .
S TA C S 2 0 1 9

7:12

Best-Of-Two-Worlds Analysis of Online Search Then,

3x n-i-1 -T n-i-2 ≥ x n-i (by LP constraint) ≥ 2 2-i 3i + 5 l + 3i -1 3i + 5 T n-i-1 (ind. hyp.) = 2 2-i 3i + 5 l + 3i -1 3i + 5 (T n-i-2 + x n-i-1 ) (def. T n-i-1 )
By rearranging terms in the above inequality we obtain

(3 - 3i -1 3i + 5 )x n-i-1 ≥ 2 2-i 3i + 5 l + (1 + 3i -1 3i + 5 )T n-i-2 ⇒ 6i + 16 3i + 5 x n-i-1 ≥ 2 2-i 3i + 5 l + 6i + 4 3i + 5 T n-i-2 ⇒ x n-i-1 ≥ 2 1-i 3i + 8 l + 3i + 2 3i + 8 T n-i-2 ,
and

Obj ≥ 6i + 4 3i + 5 l + 9 • 2 i 3i + 5 T n-i-1 (ind. hyp.) = 6i + 4 3i + 5 l + 9 • 2 i 3i + 5 (T n-i-2 + x n-i-1 ) (def. T n-i-1 ) ≥ 6i + 4 3i + 5 l + 9 • 2 i 3i + 5 T n-i-2 + 9 • 2 i 3i + 5 ( 2 1-i 3i + 8 l + 3i + 2 3i + 8 T n-i-2 ) (ind. hyp.) = 6i + 10 3i + 8 l + 9 • 2 i+1 3i + 8 T n-i-2 .
This concludes the proof of the claim, which settles the lower bound on d * (l). It remains to show that this bound is tight. Consider the strategy R t , with t = 2 2-m * (l) 3m * (l)+5 l. In what follows we will show that R t is a feasible solution of the LP, and that D(R t , l) = 6m * (l)+4 3m * (l)+5 l. First, we show that t ∈ [START_REF] Alpern | The theory of search games and rendezvous[END_REF][START_REF] Angelopoulos | On the Separation and Equivalence of Paging Strategies[END_REF]. For the upper bound, from Corollary 10, we have (3m * (l) + 5)2 m * (l) ≥ l, which implies that

1 ≥ l • 2 -m * (l) 3m * (l) + 5 ⇒ 4 ≥ l • 2 2-m * (l) 3m * (l) + 5 ⇒ 4 ≥ t.
In order to show that t > 1, consider first the case l ∈ (4, 5]. Then m * (l) = 1, which implies that

t = 2 2-m * (l) 3m * (l) + 5 l = l 4 ≥ 1.
Moreover, if l > 5, by Corollary 10, m * (l) is the smallest integer solution of the inequality (3n + 5)2 n ≥ l, then (3m

* (l) + 2)2 m * (l)-1 < l, hence t = 2 2-m * (l) 3m * (l) + 5 l = 4l (3m * (l) + 5)2 m * (l) = 2l (3m * (l) + 2)2 m * (l)-1 • 3m * (l)+5 3m * (l)+2 > 2l l • 3m * (l)+5 3m * (l)+2 = 6m * (l) + 4 3m * (l) + 5 > 1.
The last inequality holds since we have m * (l) ≥ 1, for l > 5. This concludes that t ∈ (1, 4], and R t is a feasible solution of the LP since R t satisfies all other constraints by its definition.

It remains thus to show that D(R t , l) = 6m * (l)+4 3m * (l)+5 l. By Lemma 7, we have

x m * (l) + x m * (l)-1 = t 1 + m * (l) 2 2 m * (l) + t 1 + m * (l) -1 2 2 m * (l)-1 = t • 2 m * (l) • 3m * (l) + 5 4 = 2 2-m * (l) 3m * (l) + 5 l • 2 m * (l) • 3m * (l) + 5 4 = l.
Then R t has exactly discovered a total length l right before the m * (l)-th turn. Hence,

D(R t , l) = 2T m * (l)-2 + x m * (l)-1 + l = t • (m * (l) -1) 2 m * (l)-1 + t • 1 + m * (l) -1 2 2 m * (l)-1 + l (by Lemma 7) = t • (3m * (l) -1)2 m * (l) 4 + l (arranging terms) = 2 2-m * (l) 3m * (l) + 5 l • (3m * (l) -1)2 m * (l) 4 + l (substituting t) = 3m * (l) -1 3m * (l) + 5 + 1 • l = 6m * (l) + 4 3m * (l) + 5 • (arranging terms)
This concludes the proof of the lemma.

We are now ready to prove the main results of this section. Recall that for any two strategies X, Y , dr(X, Y ) is given by (2). Combining with (3), as well as with the fact that for Y ∈ Σ 9 , we have that D(Y, l) ≥ d * (l), (from the definition of d * ), we obtain that dr(X, Σ 9 ) = sup

i∈N * sup δ∈(0,xi-xi-2] F i (X, δ), where F i (X, δ) = 2 i-1 j=0 x j + x i-2 + δ d * (x i-1 + x i-2 + δ) . (11)
Recall that for the strategy aggressive ≡ R 4 = (x 0 , x1 , . . .), its segments xi are given in Corollary 8.

Theorem 12.

For the strategy aggressive it holds that dr(aggressive, Σ 9 ) = 8/5.

Proof. We will express the discovery ratio using [START_REF] Berman | Online Algorithms: The State of the Art, chapter Online searching and navigation[END_REF]. For i = 1, and δ ∈ (0, x1 ], we have that Substituting with the values of the search segments as well as T i-1 , we obtain that Combining ( 11), ( 12) and ( 13) yields the proof of the theorem.

F i (aggressive, δ) = i • 2 i+2 + i • 2 i-1 + δ ((i + 1)2 i + i • 2 i-1 + δ) • 6i+4 3i+5 = 9i • 2 i-1 + δ ((3i + 2)2 i-1 + δ) • 6i+4
The following theorem shows that aggressive has optimal discovery ratio among all competitively optimal strategies. Theorem 13. For every strategy X ∈ Σ 9 , we have dr(X, Σ 9 ) ≥ 8 5 . Proof. Let X = (x 0 , . . .). We will consider two cases, depending on whether x 0 < 4 or x 0 = 4. Suppose, first, that x 0 < 4. In this case, for sufficiently small , we have m * (x 0 + ) = 0, which implies that d * (x 0 + ) = x 0 + , and therefore. F 1 (X, δ) ≥ F 1 (X, ) ≥ 2x 0 + x 0 + → 2, as → 0 + .

Next, suppose that x 0 = 4. In this case, for δ ∈ (0, x 1 ], it readily follows that F 1 (X, δ) = F 1 (aggressive, δ). Therefore, from [START_REF] Bernstein | Contract algorithms and robots on rays: unifying two scheduling problems[END_REF], we have that The lower bound follows directly from [START_REF] Berman | Online Algorithms: The State of the Art, chapter Online searching and navigation[END_REF].

Recall that doubling ≡ G 2 = (2 0 , 2 1 , 2 2 , . . .). The following theorem shows that within Σ 9 , doubling has worse discovery ratio than aggressive. The proof follows along the lines of the proof of Theorem 12, where instead of using the search segments xi of aggressive, we use the search segment x i = 2 i of doubling. Theorem 14. We have dr(doubling, Σ 9 ) = 7 3 .

F 1 ( 4 ;F 1 (For given i ≥ 2 ,

 1412 aggressive, δ) = 2x 0 + δ d * (x 0 + δ) = 8 + δ d * (4 + δ) . From Lemma 11, d * (4 + δ) = (4 + δ) • 6•1+4 3•1+5 = 5(4+δ) this is because 1 ≤ m * (4 + δ) ≤ m * (16) = 1.Then, and δ ∈ (0, xixi-2 ], we have

F 5 ,

 5 i (aggressive, δ) = 2T i-1 + xi-2 + δ d * (x i-1 + xi-2 + δ) ,where T i-1 is given by Corollary 8. Moreover, from Lemma 11 we have thatd * (x i-1 + xi-2 +δ) = (x i-1 + xi-2 +δ)• 6m * (x i-1 + xi-2 + δ) + 4 3m * (x i-1 + xi-2 + δ) + 5 = (x i-1 + xi-2 +δ)• 6i + 4 3i + -Two-Worlds Analysis of Online Searchwhere the last equality follows from the fact that m * (x i-1 + xi-2 + δ) = i. This is because i ≤ m * (x i-1 + xi-2 + δ) ≤ m * (x i-1 + xi-2 + xixi-2 ) = m * (x i + xi-1 ) = i.

  3i+5.Since ∂F i (aggressive, δ) ∂δ = -2 i+1 (3i -1)(3i + 5) (3i + 2)(2 n (3i + 2) + 2δ) 2 ≤ 0, then F i (aggressive, δ) is monotone decreasing in δ. Thus sup δ∈(0,xi-xi-2]

F

  i (aggressive, δ) = 9i • 2 i-1 ((3i + 2)2 i-1 ) • 6i+4 3i+5 = 9i(3i + 5) (3i + 2)(6i +4) , and then sup i∈N i≥2 sup δ∈(0,xi-xi-2]

F

  i (aggressive, δ) = (9 • 2)(3 • 2 + 5) (3 • 2 + 2)(6 • 2 + 4

F 1 (

 1 X, ) = 2x 0 + d * (x 0 + ) = 2x 0 + x 0 + ,from which we obtain that sup δ∈(0,x1]

In[START_REF] Boyar | A comparison of performance measures via online search[END_REF], online search refers to the problem of selling a specific item at the highest possible price, and is not related to the problem of searching for a target.

Acknowledgements

We are thankful to Elmar Langetepe for discussions on the literature of online search, as well as to Pascal Schweitzer for comments on an early draft of this paper.

Funding Supported by ANR OATA, ANR ENERGUMEN, DIM RFSI DACM and Labex Mathématique Hadamard. This research also benefited from the support of the FMJH Program PGMO and from the support of EDF-Thales-Orange. Shendan Jin; licensed under

A natural question arises: Is aggressive the unique strategy of optimal discovery ratio in Σ 9 ? The following theorem provides evidence that optimal strategies cannot be radically different than aggressive, in that they must mimic it in the first few iterations. Theorem 15. Strategy X = (x 0 , x 1 , . . .) ∈ Σ 9 , has optimal discovery ratio in Σ 9 only if

Proof. Consider a strategy X(x 0 , x 1 , . . .) ∈ Σ 9 . Recall that the discovery ratio of X is given by Equation [START_REF] Berman | Online Algorithms: The State of the Art, chapter Online searching and navigation[END_REF]. We will prove the theorem by induction on i.

We first show the base case, namely i = 0. The base case holds by the argument used in the proof of Theorem 13 which shows that if x 0 < 4, then dr(X, Σ 9 ) ≥ 2. For the induction step, suppose that, if X has optimal discovery ratio then for j ∈ [0, i], x j = xj , with i < 4. We will show x i+1 = xi+1 by contradiction, hence assume x i+1 < xi+1 . For sufficiently small > 0, we have

Therefore

(Equation ( 14))

(Corollary 8)

which is greater than 8 5 if i ≤ 3. We conclude, from (11) that dr(X, Σ 9 ) > 8/5, which is a contradiction.

Connections between the discovery and the bijective ratios

In this last section we establish a connection between the discovery and the bijective ratios. Bijective analysis was introduced in [START_REF] Angelopoulos | On the Separation and Equivalence of Paging Strategies[END_REF] in the context of online computation, assuming that each request is drawn from a discrete, finite set. For instance, in the context of the paging

Consider in contrast, the linear search problem. Here, there is only one request: the unknown position of the hider (i.e., n = 1). However, the set of all requests is not only infinite, but uncountable. Thus, the above definitions do not carry over to our setting, and we need to seek alternative definitions. One possibility is to discretize the set of all requests (as in [START_REF] Angelopoulos | Stochastic dominance and the bijective ratio of online algorithms[END_REF]). Namely, we may assume that the hider can hide only at integral distances from the origin. Then given strategies S 1 , S 2 , one could define the bijective ratio of S 1 against S 2 as sup i

, where S(i) denotes the i-th least costly request (hider position) in strategy S.

While the latter definition may indeed be valid, it is still not a faithful representation of the continuous setting. For instance, for hiding positions "close" to the origin, the discretization adds overheads that should not be present, and skews the expressions of the ratios. For this reason, we need to adapt the definition so as to reflect the continuous nature of the problem. Specifically, note that while the concept "the cost of the i-th least costly request in S" is not well-defined in the continuous setting, the related concept of "the cost for discovering a total length equal to l in S" is, in fact, well defined, and is precisely the value D(S, l). We can thus define the bijective ratio of S 1 against S 2 as br(S 1 , S 2 ) = sup l D(S 1 , l) D(S 2 , l) , which is the same as the definition of the discovery ratio (Definition 1).


J.-V Blanc

S Mouchabac

P Nuss

L Malandain

N Lapidus

F Ferreri

The effects of education in psychiatry on attitudes towards antidepressants in nursing students: a cross-sectional study

Keywords: antidepressant, stigma, depression, nurse, student, psychiatry, belief

Background: Stigma associated with depression and antidepressants is strong among the general population but also among patients and health professionals.

Objectives: This cross-sectional study is aimed at: 1) evaluating the knowledge and attitude towards antidepressant by nursing student; 2) exploring the association between instruction in psychiatry and representation of depression and antidepressants.

Participants: 2037 undergraduate students from 10 French nursing schools were invited to participate in 2017, 1475 (73%) completed the questionnaire.

Methods: The self-report questionnaire included the Drug Attitude Inventory (DAI) and questions about representation on depression and antidepressant. Four groups of students were built: 1) pre-teaching group (PT) as a reference group, 2) clinical training in psychiatry (CT), 3) receiving mental health theoretical education (TE), 4) receiving both (CT+TE).

Results: The mean (standard deviation) DAI score was negative: -1.9 (± 4.4) with only 40% of the nursing students conveying a positive attitude towards antidepressant. A combination of CT and TE was associated with a more positive attitude towards antidepressant in comparison with the PT condition. The CT+TE group was more prone to view antidepressants as effective and safe.

Conclusion: There is strong stigma against depression/antidepressants among nursing student. Education combined with clinical experiences in psychiatry improved these representations.

Contribution of the Paper

What is already known about the topic?  Stigma linked to depression and antidepressants is strong among the general population but also within health professionals  Unfavorable attitudes to treatment among nurses are associated with poorer quality of care What does this paper adds?

 Only 40% of the nursing students express a positive attitude towards antidepressant  An association of theoretical education and clinical training improve these attitudes

Introduction

Major depression is a chronic and recurrent disorder, affecting 350 million people worldwide [START_REF] Whiteford | Global burden of disease attributable to mental and substance use disorders: findings from the Global Burden of Disease Study 2010[END_REF]. It is the third leading cause of global disability in 2015 [START_REF] Vos | Global, regional, and national incidence, prevalence, and years lived with disability for 310 diseases and injuries, 1990-2015: a systematic analysis for the Global Burden of Disease Study 2015[END_REF], depressive disorders are expected to become first by 2030 according to the World Health Organization. In contrast, only 44% of individuals that meet the criteria for Major Depressive Episode (MDE) benefit from an appropriated care [START_REF] Marcus | Depression-A global public health concern 2012[END_REF]. Despite guidelines and available effective treatments (in particular antidepressants), the recommended duration of treatment (4 to 9 months after clinical remission) is rarely observed. In France, according to the National Health Insurance, the duration of antidepressant treatment is shorter than one month in more than 60% of the treated individuals [START_REF] Tournier | Duration of antidepressant drug treatment and its determinants in France[END_REF].

Converging studies point out that negative representations, beliefs and concerns about antidepressants are associated with poor treatment adherence [START_REF] Acosta | Creencias sobre la depresión y sus tratamientos: variables asociadas e influencia de las creencias en la adherencia[END_REF][START_REF] Burnett-Zeigler | The association between race and gender, treatment attitudes, and antidepressant treatment adherence: Attitudes and antidepressant adherence[END_REF][START_REF] Lu | Beliefs about antidepressant medication and associated adherence among older Chinese patients with major depression: A cross-sectional survey: antidepressant and medication adherence[END_REF]. Stigma associated with mental health is thus a strong factor in the low rate of appropriate care of depression [START_REF] Thornicroft | Stigma and discrimination limit access to mental health care[END_REF]. Dudley defined stigma as stereotypes or negative views attributed to a person or groups of people when their characteristics or behaviors are viewed as different from or inferior to societal norms [START_REF] Dudley | Confronting stigma within the services system[END_REF]. In this context, depressive manifestations in individuals are often ascribed to personal weakness and strongly seen as a direct consequence of environmental stress; both interpretations associated with decreased likelihood of proper care. A nationwide survey examined the French general population's conceptions about depression in 2005 [START_REF] Chee | La dépression en France[END_REF]. A subgroup of the sample declared being in agreement with a psychological (25.3%) or biological (31.8%) explanation of depression. Conversely, another 13.4% emphasized on the global negative outcome of depression while 7.3%

viewed depression as a response to some psychosocial stress; 6.1% clearly stigmatized the disease, while 6.1% rejected the validity of depression as a medical category. Younger age, low academic achievement and low income were found in groups with the worst opinion on depression. Lack of information on depression or refutation of depression as a valid category predominates in this subgroup (Chan [START_REF] Chee | La dépression en France[END_REF].

Among careers, nurses are key to depression identification, acceptation and medication administration. They are usually the closest interlocutors of patients, supporting them on a daily basis, listening to their preoccupations about their disorder and medication. Nurses are thus significant facilitators for disease acceptation and medication adherence [START_REF] Roh | Factors influencing treatment for depression among medical students: a nationwide sample in South Korea[END_REF][START_REF] Spoelstra | Interventions combining motivational interviewing and cognitive behaviour to promote medication adherence: a literature review[END_REF][START_REF] Wu | Health Care Provider-Delivered Adherence Promotion Interventions: A Meta-Analysis[END_REF]. As individuals, nurses are influenced by the prevailing negative representations towards individuals with mental illness prevailing in the general population [START_REF] Nordt | Attitudes of Mental Health Professionals Toward People With Schizophrenia and Major Depression[END_REF]. Interestingly, Caldwell et al. showed that mental health nurses are more convinced than the general population of the utility of interventions to treat depression, including antidepressants, [START_REF] Caldwell | Mental Health Nurses' Beliefs About Interventions for Schizophrenia and Depression: A Comparison with Psychiatrists and the Public[END_REF]. A positive attitude of health professionals towards health issues is crucial to improve access, adherence, and quality of care of patients with mental illnesses. An evidence-based and accurate information about the severity of depression and benefit/risk ratio of antidepressant treatment is thus likely to be indirectly beneficial to depressed patients [START_REF] Wu | Communication of potential benefits and harm to patients and payers in psychiatry: a review and commentary[END_REF]. Treatment optimization encompasses issues such as identification of the need for help, but also information on depression via psychoeducation, in particular regarding the duration of treatment and undesirable therapeutic effects [START_REF] Wu | Communication of potential benefits and harm to patients and payers in psychiatry: a review and commentary[END_REF]. In this context, the negative opinion held by healthcare professionals on depression may lead to decreased quality of care in depression [START_REF] Suwalska | Medical students and stigma of depression. Part I. Stigmatization of patients[END_REF] on line with other stigmatized conditions such as obesity [START_REF] Phelan | Impact of weight bias and stigma on quality of care and outcomes for patients with obesity[END_REF] and HIV infection [START_REF] Wagner | Health Care Provider Attitudes and Beliefs About People Living with HIV: Initial Validation of the Health Care Provider HIV/AIDS Stigma Scale (HPASS)[END_REF], by affecting the objectivity of the given information.

More specifically, few studies evaluated the knowledge and representation of the treatment of depression in undergraduate health professionals. Istilli et al. found that 52% of participants expressed doubts about antidepressant effectiveness, even after they have received instruction on this topic [START_REF] Istilli | Antidepressants: knowledge and use among nursing students[END_REF].

The influence of training on stigma among mental health professionals still remains unclear. For instance, opportunity to interact with mental health patients during induction training is arguably expected to improve the representation of the disease. This is supported by the "contact hypothesis", described by Allport in the early 1950s, suggesting that specific social contact under certain conditions creates a positive intergroup coalescence, which will improve intergroup relations (Ewalds-Kvist et al 2012, Forbes H. 2008). This beneficial effect has been questioned. Several studies could find no change in mental illness prejudice of medical and nursing students after a clinical practicum in psychiatry service (Callagan et al., 1997[START_REF] Chang | Stigma towards mental illness among medical and nursing students in Singapore: a crosssectional study[END_REF][START_REF] Choi | Clinical Education In psychiatric mental health nursing: Overcoming current challenges[END_REF]. To our knowledge, no study addressed the role of psychiatry teaching on attitude towards depression and antidepressant among nursing students (Blanc et al., 2017a).

The present study was conducted in a nursing student population: its aim was to evaluate knowledge and attitude towards depression and antidepressant, and explore the influence of clinical training and instruction on the representation on both topics. Our assumption was that a better knowledge regarding depression and antidepressants in nursing students is likely to change their attitude and, consequently, decrease stigma on depression, ultimately leading to an indirect benefit for patients.

Methodology

Setting

This cross-sectional study took place in April 2017 in 10 nursing schools in the Paris area. Subjects were asked to complete the Drug Attitude Inventory (DAI) and a complementary questionnaire. Online data was collected and anonymized. The research was approved by the Nurse Monitoring Educational Committee and ethical approval from the institutional review board (IRB) at the Sorbonne University; in addition, approval was obtained from the school department of nursing in the eleven universities before data collection. Students were informed that they were free to not answer and gave written consent. Questionnaires were anonymous.

Participants and design

The investigated population was composed of nursing students in their either first, second or third year of training.

Subgroup analyses were conducted among 4 groups: 1) pre-teaching group (PT) who had received neither training nor education, 2) had a only clinical training (CT) in psychiatry, 3) received only a theoretical education (TE) about mental health and depression, and 4) received both (CT+TE). Clinical training in psychiatry took place in various settings, both psychiatric hospitals and community mental health centers.

The training lasted 5 to 10 weeks. The daily contact with patients suffering from various mental disorders was supervised by a senior nurse; theoretical education consisted of 40 hours of courses by teaching psychiatrists. The educational program included a nurse's role in mental health as well as specific information on mental disorders (including depression and its treatment). Education did not specifically address issues such as stigma about depression or beliefs about antidepressants.

To build these four groups, students were asked to give information about the psychiatric education they received: clinical training (CT) and/or theoretical education (TE). This educational status allowed us to determine the four categories of students.

According to the large number of students solicited, we were expecting to obtain homogeneous groups.

Evaluation tools

The Drug Attitude Inventory (DAI) was the main assessment tool of the study. It is a commonly used evaluation instrument to measure the attitudes of patients but also the general population (De las Cuevas and Sanz, 2007) towards psychotropic drugs [START_REF] Hogan | A self-report scale predictive of drug compliance in schizophrenics: reliability and discriminative validity[END_REF] including antidepressants (Blanc et al., 2017b[START_REF] Brook | Impact of coaching by community pharmacists on drug attitude of depressive primary care patients and acceptability to patients; a randomized controlled trial[END_REF]. Validated in French, concise and easy to administer, DIA-10 has wellestablished psychometric properties with good test-retest reliability (0.92) and homogeneity (0.71) [START_REF] Droulout | Relationships between insight and medication adherence in subjects with psychosis[END_REF][START_REF] Nielsen | DAI-10 is as good as DAI-30 in schizophrenia[END_REF]. This self-report scale has ten items rated as True or False. A True response for six of the items (1, 3, 4, 7, 9, 10) and a False response for the other four items (2, 5, 6, 8) reflect a positive attitude towards the medication (fig. 1). They are scored +1. Otherwise, the response is scored -1. The final score is the sum of the ten items.

Sets of complementary questions were also designed to explore student specific knowledge and opinions about depression and antidepressants (see table 2) and were purposelessly discussed by a focus group. Authors built this group to respond to the problem studied. To not hinder the quality of discussions, we avoided the presence of any hierarchical links between the members. The focus group was made up of 3 psychiatrists (lead authors of the study), 3 nurse directors of Nursing Training

Institutes and 3 nursing students from different schools of these directors. Questions were sources derived from literature as followed:

-Questions based on selected items of the Beliefs about Medicine Questionnaire [START_REF] Samalin | Exploratory analysis of the French version of the beliefs about medicines questionnaire in patients with severe mental disorders: Factorial structure and reliability in specific populations of schizophrenic, bipolar and depressive patients[END_REF].This eighteen-item questionnaire has strong and replicated psychometric properties. It rates on Lickert scales and explores four aspects of perceptions and beliefs about medical treatments:

beliefs about their harmfulness, perception of doctors' overconfidence in these treatments, links with expected side effects and the need to adhere to the prescription.

-A list of common beliefs found in general population about depression and treatment [START_REF] Angermeyer | Attitudes and beliefs of the French public about schizophrenia and major depression: results from a vignette-based population survey[END_REF]. Using a "vignette method" originally -Level of basic knowledge about antidepressants [START_REF] Roh | Factors influencing treatment for depression among medical students: a nationwide sample in South Korea[END_REF]. In this study, Roh et al. didn't use psychometrics instruments, but select questions to evaluate dispositions towards using psychiatric services or receiving psychiatric drugs. Participants were able to choose responses from supplied answers.

developed
-Probability to recommend the prescription of an antidepressant for oneself or a relative [START_REF] Roh | Factors influencing treatment for depression among medical students: a nationwide sample in South Korea[END_REF] ;

Data analysis

The study examined the rate of positive attitude toward antidepressants (defined by Hogan et al. as DAI score ≥ 0), as a function of the level of instruction received or clinical experience acquired [START_REF] Hogan | A self-report scale predictive of drug compliance in schizophrenics: reliability and discriminative validity[END_REF]. After removing missing data, the three subgroups (CT, TE, and CT+TE) were compared to the reference (PT) condition and between themselves in terms of: frequencies and percentages of positive attitude toward antidepressants. In addition, answers on the complementary questions were compared between groups.

Reference characteristics were compared among groups with chi-square tests.

Positive attitude toward antidepressants and responses to DAI items for groups CT, TE and CT+TE were compared to the reference group with univariable logistic regression, using DAI items as the response variable and students group as the explanatory covariate. Odds ratios (OR) are given with their 95% confidence interval (CI).

Assuming two unbalanced groups of 400 and 200 students, the sample size permitted to detect for instance a 3.2 OR for a 10% proportion in the first group or a 1.1 OR for a 30% proportion, with an 80% power and a 5% type I error.

A p-value below 0.05 was considered significant for all tests. All analyses were conducted using statistical software R 3.4 (R Core Team, 2017).

Results

Among the 2037 students invited to participate in the study, 1475 (73%) fully completed the questionnaire. No statistical difference was found between the 4 groups regarding baseline characteristics. Most students were female (85.3%; n = 1225) and 76.8% (n=1301) were in the 18 to 25 age group (table 1).

Relation between DAI scores and psychiatric education

The mean (+/-SD) DAI score of the overall student population was negative -1.9 (4.4). An overall positive attitude towards antidepressants was found only in 40% of the population (table 2). A more positive attitude towards antidepressants was found in the group that received the combination of clinical training and theoretical education (CT+TE) (45%, OR = 1.67 [95% CI: 1.31, 2.15], p < 0.0001) and TE only (40%, OR= 1.35 (1.00, 1.83) p< 0.05) compared with the PT group (32%) (Table 2).

DAI improvement was also observed in TE and CT groups versus PT, but did not reach statistical significance.

Beliefs and knowledge modified by psychiatric education

An improvement in knowledge about onset of action of antidepressants, beliefs about effectiveness of antidepressant and rate of recommendation of treatment for a relative was observed in the TE, CT and CT+TE groups compared with the PT condition. Belief that a patient with depression is a not a "real" patient as well as "antidepressants do more harm than good" was lower only for the CT+TE group compared to the PT condition (with 6% and 33% for CT+TE vs. 10% and 46% in PT, respectively, p < 0.001 for both). Regarding the assumptions: "consider taking antidepressants for oneself or others in case of prescription", "that antidepressant do not treat the cause of depression", and "that doctors prescribe too much

antidepressants" an increased opinion was observed only in the CP + TE group (48%, 70% and 72 % vs. 41%, 64% and 66% in PT, respectively; p = 0.03, 0.02 and 0.01).

Beliefs and knowledge not modified by psychiatric instruction

Belief that psychotherapies are more effective than antidepressant were not modified by any CT, TE, or CT + TE compared with the PT condition (respectively, p=0.74; p=0.52 and p=0.09). Belief that a patient with depression is different from a patient with another illness were not modified either by any CT, TE, or CT + TE compared with the PT condition (respectively, p=0.72; p=0.75 and p=0.15). This opinion is quite frequent, shared by 44% of the overall student population.

Discussion

The main result of our study is the identification of a strong mistrust towards antidepressants and the presence of stigma concerning depression in a large proportion of nursing students.

This negative attitude, evaluated with the global DAI score, is comparable to the result of studies made on similar samples (score of -1.9 in 229 French nursing students (Blanc et al., 2017a). De las Cuevas et al. found less negative attitude towards antidepressant in patients compared to the general population (mean DAI of -0.7 vs. +3.6) (De las [START_REF] De Las Cuevas | Attitudes toward psychiatric drug treatment: the experience of being treated[END_REF]. In our study the attitudes towards antidepressants are worse compared to both groups.

The literature shows mixed results on the influence of theoretical and clinical education on knowledge, attitudes to antidepressants and representation of depression [START_REF] Arrue | Nursing students' alternative beliefs regarding care for patients suffering from depression[END_REF]Blanc et al., 2017a ;[START_REF] Chang | Stigma towards mental illness among medical and nursing students in Singapore: a crosssectional study[END_REF][START_REF] Choi | Clinical Education In psychiatric mental health nursing: Overcoming current challenges[END_REF][START_REF] Simon | Impact of education program and clinical posting in psychiatry on medical students' stigmatizing attitudes towards psychiatry and psychiatric disorders[END_REF]. Choi et al. showed no significant change in mental health prejudice before and after clinical training in 63 nursing students [START_REF] Choi | Clinical Education In psychiatric mental health nursing: Overcoming current challenges[END_REF], and Chang et al found more negative attitudes after a clinical placement [START_REF] Chang | Stigma towards mental illness among medical and nursing students in Singapore: a crosssectional study[END_REF]. In line with the present study, association of general psychiatric education and clinical training in the psychiatry ward was associated with a reduction of stigmatizing attitudes about mental health disorders in a medical student population [START_REF] Simon | Impact of education program and clinical posting in psychiatry on medical students' stigmatizing attitudes towards psychiatry and psychiatric disorders[END_REF].

Nevertheless, most studies indicate that appropriate knowledge about depression and antidepressants correlate with more positive attitude towards antidepressants [START_REF] Roh | Factors influencing treatment for depression among medical students: a nationwide sample in South Korea[END_REF]. A bidirectional effect is observed between stigma to depression and negative attitude towards antidepressants [START_REF] Allara | Are mass-media campaigns effective in preventing drug use? A Cochrane systematic review and meta-analysis[END_REF][START_REF] Gronholm | Interventions to reduce discrimination and stigma: the state of the art[END_REF]).

Among the various information conveyed during teaching, retention varies according to the taught topics in the studied population. Issues such as onset of action and effectiveness of antidepressants were seemingly easy to be correctly addressed in the TE and CT + TE subgroups. Yet, as much as half of the questioned students mentioned that patients with depression differ from those with another medical condition. Furthermore, despite specific psychiatric teaching, a majority of nursing students still considers antidepressants as harmful and with addictive potential. Of concern too, is the fact that there is no observed change in opinion about alleged excess in antidepressant prescriptions by psychiatrists. We cannot but confront this result with studies showing that 75% of patient suffering from major depressive disorder do not receive adequate treatment [START_REF] Grolleau | Congruence between diagnosis of recurrent major depressive disorder and psychotropic treatment in the general population[END_REF][START_REF] Hämäläinen | Treatment of major depressive disorder in the Finnish general population[END_REF].

Adequate mental health in future nurses is crucial as a nurse's career unavoidably confronts highly emotional situations as well as institutional pressure. Increasing the knowledge about depression and antidepressants could benefit the mental health of nursing students. As mentioned by Roh et al. in a population of medical students, psychiatric education about depression increasing the student's ability to seek treatment for themselves in the case of psychological distress [START_REF] Roh | Factors influencing treatment for depression among medical students: a nationwide sample in South Korea[END_REF].

In The overall negative opinion about major depression, patients with depression, and antidepressants in future health professionals are likely to play a role in poorer patient outcomes. A conjunction of prejudice and negative attitude towards mental problems in general [START_REF] Schafer | A survey into student nurses' attitudes towards mental illness: Implications for nurse training[END_REF] along with suspicion of antidepressant efficacy and tolerance in health professionals is likely to reduce proper access to care and optimal outcome in people suffering from depression.

Study limitations

The cross sectional design does not allow for the examination of the direct effect of education on a prospective manner on the same group of individuals over time. A randomized procedure allocating specific educational programs would have also been ideal. Nevertheless, the socio-demographic characteristics of the 4 groups are identical over the teaching years as well as variables affecting DAI, indicative of a good comparability between groups. A post-graduation study after some years of nurse practice using the same questionnaire will also be of interest. It will look at the remanence effect of the positive attitude changes observed during the training years as well as later changes in the more reluctant students. The use of another tool, as the Beliefs about Medicine Questionnaire (BMQ), could also be useful to complete the DAI [START_REF] Samalin | Exploratory analysis of the French version of the beliefs about medicines questionnaire in patients with severe mental disorders: Factorial structure and reliability in specific populations of schizophrenic, bipolar and depressive patients[END_REF], but was not available in French at the time the study was designed. The BMQ explore general beliefs about medication, as well as concerns and necessity. Thus, it could be interesting to administer both tools. As 73% of the students accepted to participate to the study, it shows an interest for mental health issue.

Recommendations and pedagogical proposals (fig. 2)

The present study emphasizes the critical and beneficial role of clinical practice combined with teaching in psychiatry to improve attitude towards antidepressants and reduce the stigma of depression. This advocates for an appropriate and intentional educational program during the induction-training period about mental health issues, reinforced by well-supervised psychiatric clinical training.

Erroneous preconception about depression and antidepressants were found in a quite high proportion of nurse students. Psychiatric education was shown to be able to improve knowledge and decrease stigma. We assume that specific teaching in psychiatry, emphasizing on major depression frequency, causes, manifestations, treatment, somatic impact, and handicap is likely to decrease stigma and misconceptions, as shown by education given to college students [START_REF] Yamaguchi | Effects of Short-Term Interventions to Reduce Mental Health-Related Stigma in University or College Students: A Systematic Review[END_REF]. In particular, information about the underlying biological causes of mental disorders -with its subsequent rational for a medication usewas shown to lead to better acceptance for both in the general population [START_REF] Schomerus | Evolution of public attitudes about mental illness: a systematic review and meta-analysis: Evolution of public attitudes[END_REF].

Communication about the benefit/risk ratio of antidepressants is also likely to be useful in this context [START_REF] Wu | Communication of potential benefits and harm to patients and payers in psychiatry: a review and commentary[END_REF].

Obviously, a greater impact for de-stigmatization will be obtained via association of theoretical and in-site education combined with proactive and small group learning.

International recommendations such as CANMAT (Canadian Network for Mood and Anxiety Treatments) also advocates for an optimistic attitude during teaching towards treatment of individuals with mental health problems [START_REF] Murrihy | Testing an empirically derived mental health training model featuring small groups, distributed practice and patient discussion[END_REF][START_REF] Piette | Simulation-based learning in psychiatry for undergraduates at the University of Zimbabwe medical school[END_REF].

While social contact with mental health patients is an effective way to reduce stigma [START_REF] Yamaguchi | Effects of Short-Term Interventions to Reduce Mental Health-Related Stigma in University or College Students: A Systematic Review[END_REF], that was not the case in our study: clinical practice alone failed to reduce stigma. We can hypothesize that during their practice in psychiatric wards, nursing students focused mostly in the more acute, severe and relapsing patients. To benefit from the "contact hypothesis", it may be effective to include interaction with patients in a recovery process during their nurse training.

Specific research on mental health issues in the nursing community will also be able to raise awareness on that topic, not only among nurses but also the general population. Seen as "trustful, ethical and honest" [START_REF] Pinto-Foltz | Reducing Stigma Related to Mental Disorders: Initiatives, Interventions, and Recommendations for Nursing[END_REF], nurses are in a unique position to positively impact mental health issues in the general population. In France, nursing students, as well as most healthcare professionals during, their training years, are about to be in charge of a public health prevention program called "sanitary service" [START_REF] Vaillant | Mise en oeuvre du service sanitaire pour les étudiants en santé Retrieved March 18[END_REF]. Thus, an important prerequisite before initiating this program is to investigate stigma towards mental health problems in nursing students and ways to decrease it is.

Conclusion

In nursing students, level of stigma against depression and negative attitude towards antidepressants are strong and higher compared to the general population.

Knowledge on mental health issues combined with clinical experiences in general psychiatric wards have been shown to be the key to improving these representations.

Both high levels of induction training in psychiatry -because of the complexity of mental illness -and individualized support for students are needed to achieve professional excellence among nursing students.

This research is independent with no subsidy of any sort, either specific grant from public, commercial Funding Agencies, or non-profit Association.

  in Germany, Angermeyer and al. measured on a five points Lickert scales the causal attributions of twelve possible causes of depression in four domains (psychosocial stress, childhood adversity, biogenetics causes and intra-psychic causes) in general population. They assessed opinions about different treatment methods: three evidence-based psychiatric treatments (psychotropic medication, psychotherapy, relaxations techniques) and three 'alternative' treatments (natural remedies, mediation, acupuncture).

  France, Nursing Training Institutes have partnerships with Universities. Nurse training is available for postgraduate students. It takes place over 3 years. Candidates must be at least 17 years old to be admitted to training. The nursing diploma certifies that the student has obtained 180 European Credit Transfer System (ECTS): 120 ECTS for teaching units and 60 ECTS for clinical nursing practice. Among the different clinical trainings, a 10-week clinical practice in psychiatry (internship) is compulsory. Advanced Practice Nurses (APN) (i.e. Psychiatric & Mental Health Clinical Nurse Specialist or Psychiatric & Mental Health Nurse Practitioner, in the US) could certainly have a sub-specialization in management of mood disorders. In France, regarding the drug treatment, the APN should be able to perform the renewal of the drug prescription or dosage adjustment for mood stabilizers or antidepressants. Recently promoted by the Ministry of Health, a specific teaching module on antidepressants and the stigma surrounding depression will be included in the training course of APN in psychiatry.