Rémi Azouit
email: remi.azouit@lss.supelec.fr

Antoine Chaillet
email: antoine.chaillet@supelec.fr

Yacine Chitour
email: yacine.chitour@lss.supelec.fr

Luca Greco
email: luca.greco@lss.supelec.fr

Strong iISS for a class of systems under saturated feedback

Keywords: Stability and robustness of nonlinear systems, input-to-state stability, saturated feedback

come

Introduction

It is well known that a necessary and sufficient condition for the stabilizability of a linear time-invariant (LTI) plant by saturated feedback is that the internal dynamics has no pole with positive real part (Sontag, 1998b). Several works in the literature have proposed bounded stabilizing feedback for particular classes of systems whose internal dynamics exhibits no exponential instability. For LTI systems having no eigenvalues with positive real parts, it has been shown in [START_REF] Nistri | Nonlinear output feedback design for linear systems with saturating controls[END_REF] that global stabilization by bounded output feedback can be achieved if and only if the system is both detectable and stabilizable. For neutrally stable systems (meaning LTI systems whose internal dynamics exhibits no unbounded solutions), it is also known that stabilization can be achieved using a saturated linear static feedback.

Nonetheless some classes of systems, although having no poles with positive real parts, cannot be stabilized by saturated linear static state-feedback; this class includes chains of three or more integrators [START_REF] Fuller | In-the-large stability of relay and saturating control systems with linear controllers[END_REF][START_REF] Sussmann | On the stabilizability of multiple integrators by means of bounded feedback controls[END_REF]. Nested saturations [START_REF] Teel | Global stabilization and restricted tracking for multiple integrators with bounded controls[END_REF]; [START_REF] Sussmann | A general result on the stabilization of linear systems using bounded controls[END_REF] have been proposed to stabilize such systems. Stabilization by bounded control has also proved useful for nonlinear dynamics, especially in the context of systems in feedforward form [START_REF] Mazenc | Adding integrators, saturated controls and global asymptotic stabilization of feedforward systems[END_REF][START_REF] Teel | A nonlinear small gain theorem for the analysis of control systems with saturation[END_REF] or by relying on the so-called "universal constructions" [START_REF] Lin | A universal formula for stabilization with bounded controls[END_REF].

Beyond stabilization, it is often desirable to ensure some robustness properties in order to cope, for instance, with parameter uncertainty, measurement noise or exogenous disturbances. L p -stabilization with respect to disturbances acting inside the saturation was achieved in [START_REF] Saberi | On simultaneous global external and global internal stabilization of critically unstable linear systems with saturating actuators[END_REF] based on the low-and-high gain control law introduced in [START_REF] Megretski | l 2 bibo output feedback stabilization with saturated control[END_REF]. This robust stabilization has been extended to disturbances acting outside the saturation in [START_REF] Wang | Control of a chain of integrators subject to actuator saturation and disturbances[END_REF] for chains of integrators under matching conditions. Also, explicit estimates of L p input/output gains have been obtained for neutrally stable systems based on a saturated linear static feedback [START_REF] Liu | On finite-gain stabilizability of linear systems subject to input saturation[END_REF]. Another natural candidate for the evaluation of robustness to exogenous inputs is the framework of input-to-state stability (ISS, Sontag (1989a[START_REF] Sontag | Input to state stability: Basic concepts and results[END_REF]) and its weaker variant integral ISS (iISS, Sontag (1998a)). In [START_REF] Angeli | Robust stabilization via saturated feedback[END_REF], a saturated linear state-feedback is proposed that ensures ISS with respect to sufficiently small disturbances despite parameter uncertainty for systems of dimension smaller than or equal to three, as well as feedforward systems. ISS of neutrally stable systems with respect to disturbances acting outside the saturation have been proposed in [START_REF] Arcak | Input-to-state stability for a class of Lurie systems[END_REF] under matching conditions. Other approaches guarantee ISS and iISS with bounded control to nonlinear systems based on the aforementioned "universal constructions" [START_REF] Liberzon | ISS and integral-ISS disturbance attenuation with bounded controls[END_REF].

Among other robustness features, ISS ensures a bounded response to any bounded disturbance. Intuitively, one may expect that bounded controls fail in general at guaranteeing the solutions' boundedness if the disturbance acts outside the saturation with a too large amplitude (unless matching conditions between the saturated actuator and the disturbance are imposed: seee.g. [START_REF] Arcak | Input-to-state stability for a class of Lurie systems[END_REF]; [START_REF] Wang | Control of a chain of integrators subject to actuator saturation and disturbances[END_REF]). At first sight, for these systems, nothing more than ISS with respect to small inputs can be established, thus providing no information on the system's behavior for larger inputs. In this note, we provide sufficient conditions under which a more interesting property, namely Strong iISS, can be achieved by saturated feedback. This property, introduced in Chaillet et al. (2014a), not only guarantees ISS with respect to small inputs but also iISS. In particular, it ensures a bounded response to any disturbance whose amplitude is below a given threshold, but also the existence of solutions at all times even for disturbances above that threshold. It also guarantees that the state converges to zero in response to any vanishing disturbance, and is known to be preserved under cascade interconnection [START_REF] Chaillet | Strong iISS is preserved under cascade interconnection[END_REF].

In this paper, we identify two classes of systems for which Strong iISS can be achieved by saturating feedback. The first one is made of input-affine systems that can be internally stabilized by the "universal construction" of [START_REF] Lin | A universal formula for stabilization with bounded controls[END_REF] and for which a specific growth rate condition holds. The second one is the class of neutrally stable LTI systems, for which a saturated linear state feedback is shown to ensure Strong iISS. In both cases, the considered disturbances act outside the saturation, and no matching condition between the actuation and the disturbances is assumed. We start by formulating the problem and motivating it through an example (Section 2). Then, in Section 3, we provide a sufficient condition under which Strong iISS is achieved by saturated feedback and provide growth rate conditions under which the "universal construction" originally proposed to ensure global asymptotic stability of the disturbance-free system also guarantees Strong iISS in presence of perturbations. We provide an explicit estimate of the maximal disturbance amplitude that can be tolerated without compromising solutions' boundedness. We illustrate our findings through the stabilization of the Euler equations of a rotating spacecraft. Finally, focusing on LTI systems whose internal dynamics is neutrally stable, we propose in Section 4 a simple linear state feedback that ensures Strong iISS to additive disturbance despite actuator saturation. Here also, we provide an explicit estimate of the maximum tolerable disturbance amplitude and compare it to numerical observations in an example. Proofs are provided in Section 5. Conclusive remarks and perspectives are given in Section 6.

Notation. For a nondecreasing continuous function

γ : R ≥0 → R ≥0 , γ(∞) ∈ R ≥0 ∪ {∞} denotes the quantity lim s→+∞ γ(s). A function α : R ≥0 → R ≥0 is of class PD if it is continuous and positive definite. It is of class K if, in addition, it is increasing. It is of class K ∞ if it is of class K and α(∞) = ∞. β : R ≥0 × R ≥0 → R ≥0 belongs to class KL if,
given any fixed t ≥ 0, β(•, t) ∈ K and, given any fixed s ≥ 0, β(s, •) is continuous, nonincreasing and tends to zero as its argument tends to infinity. Given x ∈ R n , |x| denotes its Euclidean norm. Given a positive integer p, U p denotes the set of all measurable locally essentially bounded functions d : R ≥0 → R p . For a given d ∈ U p , d := ess sup t≥0 |d(t)|. Given a constant R > 0, we let U p <R denote the set {d ∈ U p : d < R}. sat : R n → R n is the vector saturation function defined as sat(x) = (sat 0 (x 1 ), . . . , sat 0 (x n )) T , where sat 0 (s) := min{1; |s|}sign(s) for each s ∈ R. A function V : R n → R ≥0 is called a storage function if it is continuously differentiable and satisfies V (0) = 0 and V (x) > 0 for all x = 0. A storage function is said to be proper if, in addition, lim |x|→∞ V (x) = ∞. Given a storage function V and a vector field f :

R n → R n , L f V (x) := ∂V (x) ∂x f (x).
2 Problem statement Consider a nonlinear system of the form ẋ = f (x, u, d), where x ∈ R n is the state, u ∈ R m is the control input, d ∈ R p the exogenous disturbance and f : R n × R m × R p → R n denotes a locally Lipschitz function satisfying f (0, 0, 0) = 0. If the system is stabilized through a static state feedback u = k(x), the system takes the form

ẋ = f (x, d) , (1)
where f (x, d) := f (x, k(x), d). Given x 0 ∈ R n and an input signal d ∈ U m , the solution of (1) starting at x 0 at time t = 0 is referred to as x(•, x 0 , d) (or simply x(•)) on the time domain where it is defined.

Assume that the state feedback k(x) is nominally designed to ensure input-to-state stability (ISS, Sontag (1989a[START_REF] Sontag | Input to state stability: Basic concepts and results[END_REF]) of the closed-loop system (1). Such a control law may be designed using existing techniques from the literature, such as [START_REF] Sontag | Further facts about Input-to-State stabilization[END_REF]; [START_REF] Krstic | Inverse optimal design of Input-to-State Stabilizing nonlinear controllers[END_REF]; [START_REF] Teel | On assigning the derivative of a disturbance attenuation Control Lyapunov Function[END_REF]; [START_REF] Liberzon | Universal construction of feedback laws achieving ISS and integral-ISS disturbance attenuation[END_REF]; [START_REF] Malisoff | Global asymptotic controllability implies Input-to-State stabilization[END_REF].

Then, a natural question is to know what kind of robustness can be guaranteed to (1) in the presence of actuator saturation. Intuitively, we can expect that the applied control input u = sat(k(x)) fails at guaranteeing a bounded state in response to disturbance of too large magnitude, thus compromising ISS. Nonetheless a weaker robustness property, namely iISS (Sontag, 1998a), can reasonably be expected.

Definition 1 (iISS) The system (1) is said to be integral input-to-state stable if there exist a class KL function β and class K ∞ functions µ 1 , µ 2 such that, for all x 0 ∈ R n and all d ∈ U p , its solution satisfies, for all t ≥ 0,

|x(t; x 0 , d)| ≤ β(|x 0 | , t) + µ 1 t 0 µ 2 (|d(s)|)ds .
Unfortunately, even if iISS systems prove robust with respect to classes of inputs with finite energy (in particular, if the energy ∞ 0 µ 2 (|d(s)|)ds is finite, then the state converges to the origin), solutions can run unbounded in the presence of arbitrary small and even vanishing inputs (Chaillet et al., 2014a). Generically, we may expect a bounded state property at most for disturbances whose amplitudes are below a specific threshold. That is, we could consider systems which are ISS with respect to small inputs.

Definition 2 (ISS wrt small inputs) The system (1) is said to be input-to-state stable with respect to small inputs if there exist a constant R > 0, a class KL function β and a class K ∞ function µ such that, for all x 0 ∈ R n and all d ∈ U p , its solution satisfies

d < R ⇒ |x(t; x 0 , d)| ≤ β(|x 0 | , t) + µ( d ), ∀t ≥ 0.
In the case when R = +∞, we recover the classical definition of ISS (Sontag, 1989a[START_REF] Sontag | Input to state stability: Basic concepts and results[END_REF]. However, given a finite R, no guarantee on the behavior of the system can be given when the disturbance magnitude overpasses the threshold R. The very solution of the system may fail to exist if d ≥ R. Hence, a good candidate to evaluate the robustness to exogenous disturbances of systems with saturated feedback seems to be the Strong iISS, recently introduced in Chaillet et al. (2014a).

Definition 3 (Strong iISS) The system (1) is said to be Strongly iISS if it is both ISS wrt small inputs and iISS. In other words, there exist R > 0, β ∈ KL and µ 1 , µ 2 , µ ∈ K ∞ such that, for all d ∈ U p , all x 0 ∈ R n and all t ≥ 0, its solution satisfies the two properties:

|x(t)| ≤ β(|x 0 | , t) + µ 1 t 0 µ 2 (|d(s)|)ds (2) d < R ⇒ |x(t)| ≤ β(|x 0 | , t) + µ( d ) .
(3) The constant R is then called an input threshold.

Nonetheless, the link between Strong iISS and systems with saturated control is not straightforward. For instance, elementary considerations convince that not every nominal ISS-stabilizing feedback ensures Strong iISS once saturated. Indeed, saturated feedback may be insufficient to compensate for unbounded sources of instability, thus compromising even the internal stability of the plant. Since iISS, and consequently Strong iISS, imply global asymptotic stability in the absence of disturbance (this property will be called 0-GAS in the rest of the article), only systems that can be globally stabilized by saturated feedback can be expected to yield Strong iISS in the presence of actuator saturation. In other words, Strong iISS stabilization through saturated feedback faces all the challenges of global asymptotic stabilization by bounded control. In particular, for LTI systems, necessary requirements include stabilizability and the absence of eigenvalues with positive real parts [START_REF] Sussmann | A general result on the stabilization of linear systems using bounded controls[END_REF]. Based on these observations, a more reasonable hypothesis would be that any ISS-stabilizing nominal feedback that ensures 0-GAS when saturated, also ensures Strong iISS. The following example shows that this conjecture is not true in general.

Example 1 Consider the scalar system ẋ = x 2 u + x 3 d.

(4) The nominal feedback law u = k(x) = -x 5 makes the closed-loop system ISS. Indeed, the total derivative of the storage function

V (x) = x 2 /2 reads V (x) = -x 8 + x 4 d ≤ -x 8 + x 4 |d| ≤ - x 8 2 + d 2 2 ,
which guarantees ISS by its classical Lyapunov characterization [START_REF] Sontag | On characterizations of the Input-to-State Stability property[END_REF]. In the presence of actuator saturation, the closed-loop system becomes ẋ = -x 2 sat 0 (x 5 ) + x 3 d. Clearly, this system remains 0-GAS. Nonetheless it can be seen that, given any constant input d * > 0, any solution starting from x 0 ≥ max{1; 2/d * } grows unbounded, and even presents finite escape times).

The above example highlights the necessity to conduct a more careful study on how the Strong iISS property may be ensured by saturated feedback. This is the purpose of this paper.

3 Nonlinear systems: "universal" construction

We start by focusing on nonlinear input-affine systems:

ẋ = f (x) + g(x)u + h(x)d (5)
where x ∈ R n is the state, u ∈ R m is the control input, and d ∈ R p is the perturbation. The functions f : R n → R n , g : R n → R n×m and h : R n → R n×p are assumed locally Lipschitz and zero at zero. In the presence of actuator saturation, the system reads ẋ = f (x) + g(x)sat(u) + h(x)d.

(6) We stress that, if each control entries u i saturates at a value ūi = 1, considering ũ := (u 1 /ū 1 , . . . , u n /ū n ) T as the new control input allows to fit the framework (6).

Sufficient conditions for Strong iISS

We start by stating an analysis result, which provides sufficient conditions under which a generic control guarantees Strong iISS to (6). This result will serve as a basis to design saturated control laws in the next subsections. This first result relies on the following two assumptions, involving a proper storage function V : R n → R ≥0 and a locally Lispschitz state feedback k : R n → R m .

Assumption 1 There exists a class K function γ such that, for all x = 0,

L f V (x) + L g V (x)k(x) < 0 (7) L h V = 0 ⇒ L f V + L g V k(x) L h V ≥ γ(|x|). (8)
Assumption 1 contains two ingredients: (7) guarantees the 0-GAS of (5) in closed loop with u = k(x), and, as we will see in the proof of Theorem 1 below, the combination of ( 7) and ( 8) ensures ISS wrt small inputs.

Assumption 2 It holds that

lim sup |x|→∞ |L h V (x)| 1 + V (x) < +∞. (9)
Assumption 2 essentially guarantees that the perturbation does not yield finite escape times that a saturated feedback would not be able to tackle. This can be seen by observing that, by the continuity of the function x

→ |L h V (x)| 1+V (x) , (9) ensures that |L h V (x)| 1 + V (x) ≤ K, ∀x ∈ R n , (10)
for some positive constant K. Consequently, all the terms induced by the perturbation term in the total derivative of V is at most linear in V (x). This, combined with Assumption 1, constitutes a sufficient condition for forward completeness [START_REF] Angeli | Forward completeness, unboundedness observability, and their Lyapunov characterizations[END_REF].

Based on these assumptions, we can state the following.

Lemma 1 Assume that there exists a proper storage function V : R n → R ≥0 , a function γ ∈ K, and a locally Lipschitz state feedback k : R n → R ≥0 satisfying Assumptions 1 and 2. Then the control law u = k(x) makes the system (5) Strongly iISS with input threshold R = γ(∞).

The proof is rather straightforward, but is provided in Section 5.1 for the sake of completeness. It is worth stressing that Lemma 1 would not hold if either Assumption 1 or 2 was removed. Assumption 2 alone does not provide any information on the system in the absence of exogenous perturbations. Moreover, it can easily be seen that the system (4) of Example 1 satisfies Assumption 1, but fails at fulfilling Assumption 2. It results as a non Strongly iISS system, since the system is not forward complete in the presence of arbitrary small (and even vanishing) perturbations.

Strong iISS by "universal" construction

Although Lemma 1 gives some hints on when a state feedback yields Strong iISS, it does not provide any constructive way to design the corresponding control law. In this section, we rely on the so-called "universal" construction of Arstein's theorem to construct a bounded static state feedback ensuring Strong iISS. This construction relies on the knowledge of a control Lyapunov function (CLF), whose definition is recalled below [START_REF] Lin | A universal formula for stabilization with bounded controls[END_REF].

Definition 4 (CLF) A smooth proper storage function V : R n → R ≥0 is called a control Lyapunov function with controls in the unit ball for the (disturbance-free) system ẋ = f (x) + g(x)u if it satisfies:

inf |u|<1 {L f V (x) + L g V (x)u} < 0, ∀x = 0.
In other words, a CLF with controls in the unit ball is a storage function whose total derivative can be point-wisely assigned to a negative value for each non-zero state by a control with amplitude lower than 1. We may also require that this point-wise assignment be achievable by arbitrarily small control values, provided that the state is sufficiently close to the origin: this property is known as the small control property (SCP, Sontag (1989b)).

Definition 5 (SCP) A CLF V : R n → R ≥0 is said to satisfy the small control property for the (disturbance-free) system ẋ = f (x) + g(x)u if, given any ε > 0, there exists δ > 0 such that, if |x| < ε and x = 0, then there exists

|u| < δ such that L f V (x) + L g V (x)u < 0.
We stress that, unlike other robust CLF proposed in the literature [START_REF] Freeman | Robust Nonlinear control design: State-space and Lyapunov control techniques[END_REF][START_REF] Teel | On assigning the derivative of a disturbance attenuation Control Lyapunov Function[END_REF][START_REF] Liberzon | Universal construction of feedback laws achieving ISS and integral-ISS disturbance attenuation[END_REF][START_REF] Liberzon | ISS and integral-ISS disturbance attenuation with bounded controls[END_REF], the above definitions are given for disturbance-free systems: the goal here is to provide a growth restriction on the function h so that the bounded control law proposed in [START_REF] Lin | A universal formula for stabilization with bounded controls[END_REF] ensures Strong iISS for (6).

More precisely, the main contribution of the work [START_REF] Lin | A universal formula for stabilization with bounded controls[END_REF] is to propose an explicit continuous state feedback law, smooth out of the origin and of amplitude smaller than 1, that globally asymptotically stabilizes the disturbance-free system ẋ = f (x) + g(x)u. This state-feedback law reads k

(x) = κ(L f V (x), |L g V (x)| 2 )L g V (x) T , where κ is defined, for each (a, b) ∈ R × R ≥0 , as κ(a, b) :=    -a+ √ a 2 +b 2 b(1+ √ 1+b) if b > 0 0 if b = 0. ( 11
)
The following result, proved in Section 5.2, states that this control law may be used as such to make the system (6) Strongly iISS provided a growth restriction on the function h.

Theorem 1 Let V be a CLF with controls in the unit ball, satisfying the SCP for the disturbance-free system ẋ = f (x) + g(x)u. Assume that there exists α ∈ K such that, for all x = 0,

lim inf |x|→∞ |L f V (x)| + |L g V (x)| |L h V (x)| > 0. ( 12
)
Assume also that lim inf

|x|→∞ L f V (x)>0 |L g V (x)| > 0 (13) and lim sup |x|→∞ |L g V (x)| |L f V (x)| = 1. ( 14
)
Then, under Assumption 2, the feedback law proposed in [START_REF] Lin | A universal formula for stabilization with bounded controls[END_REF], namely

u = k(x) = κ(L f V (x), |L g V (x)| 2 )L g V (x) T , ( 15
)
where κ is defined in (11), is continuous on R n , smooth on R n \ {0}, has norm smaller than 1 and makes the saturated-actuation system (6) Strongly iISS.

Condition (12) and Assumption 2 express a growth rate limitation on the term h(x) through which the perturbation acts on the system. Condition ( 13) is fairly intuitive: in the presence of a non-vanishing perturbation term and when the drift term is not dissipating, the control field needs to be non-vanishing as well in order to compensate these disturbances and ensure the state boundedness (hence Strong iISS). Condition ( 14) is far less intuitive; this technical assumption is required to prevent the dissipation rate to vanish when the state norm tends to infinity: see the proof for more details.

ISS stabilization by "universal" constructions

If α ∈ K ∞ in the above statement, then it can be seen along the proof that the system (6) in closed loop with the same static feedback k(x) results ISS. This observation complements the results in the literature that rely on the notion of ISS-CLF [START_REF] Liberzon | Universal construction of feedback laws achieving ISS and integral-ISS disturbance attenuation[END_REF][START_REF] Liberzon | ISS and integral-ISS disturbance attenuation with bounded controls[END_REF][START_REF] Teel | On assigning the derivative of a disturbance attenuation Control Lyapunov Function[END_REF].

Corollary 1 If the assumptions of Theorem 1 hold with a K ∞ function α, then the static state feedback law (15) makes the system (6) ISS.

iISS stabilization by "universal" constructions

The assumptions of Theorem 1 can be considerably relaxed if only iISS is needed. We state this fact in the following corollary, whose proof is provided in Section 5.3.

Corollary 2 Let V be a CLF with controls in the unit ball satisfying the SCP for the disturbance-free system ẋ = f (x) + g(x)u and let Assumption 2 hold. Then the static state feedback law (15) makes the system (6) iISS.

Similarly to Theorem 1, this result provides a growth rate limitation on the term h(x) in such a way that the control law originally proposed in [START_REF] Lin | A universal formula for stabilization with bounded controls[END_REF] for disturbance-free systems, also yields a robustness property to exogenous disturbances. We stress, however, that the robustness property ensured by Corollary 2 (namely, iISS) is much weaker than that guaranteed by Theorem 1 (namely, Strong iISS) as it implies neither solutions' boundedness in response to sufficiently small disturbances nor state convergence in response to a vanishing perturbations.

Example: spacecraft velocity control

We now provide an illustration of the results obtained so far by considering the control of a rotating spacecraft through limited-thrust actuators. Letting x := (x 1 , x 2 , x 3 ) T denote its the angular velocity and u := (u 1 , u 2 , u 3 ) T the control torques, the dynamics is ruled by the following equations [START_REF] Khalil | Nonlinear systems[END_REF]:

J 1 ẋ1 = (J 2 -J 3 )x 2 x 3 + ūsat 0 (u 1 /ū) + d 1 (16a) J 2 ẋ2 = (J 3 -J 1 )x 3 x 1 + ūsat 0 (u 2 /ū) + d 2 (16b) J 3 ẋ3 = (J 1 -J 2 )x 1 x 2 + ūsat 0 (u 3 /ū) + d 3 , (16c)
where d := (d 1 , d 2 , d 3 ) T represents exogenous perturbations (e.g. actuation errors) and ū denotes the maximum thrust that can be delivered by each actuator. We use the Lyapunov function V (x) = 1 2 x T P x, where P := diag(J 1 , J 2 , J 3 ). Using the notation of ( 6), straightforward computations lead to

L f V (x) = 0, L g V (x) = -(ūx 1 , ūx 2 , ūx 3 ) and L h V (x) = (x 1 , x 2 , x 3
). It can easily be seen that V is a CLF with controls in the unit ball for ( 16) and that it satisfies the SCP. It is also straightfoward to show that ( 12), ( 13) and ( 14) hold for this system. Theorem 1 can thus be invoked to design a bounded continuous feedback for Strong iISS, of the form u = k univ (x) := κ(0, |L g V |

2 )L g V T , where κ is given in (11). In other words:

k univ (x) = -ūx 1 + 1 + ū2 |x| 2 . ( 17
)
The fact that L f V (x) = 0 allows in this case to make use of another control law, namely a saturated linear control:

u = k lin (x) := (-k 1 x 1 , -k 2 x 2 , -k 3 x 3 ) T , (18)
where k 1 , k 2 , k 3 denote positive gains. It can easily be shown that this linear control law makes the system (16) ISS in the absence of actuator saturation. We claim that, in the presence of limited thrust (namely |u i | ≤ ū for each i ∈ {1, 2, 3}), the system results Strongly iISS with input threshold R = ū/ √ 3. Indeed, in the presence of such saturating thrusters, the dynamics reads

J 1 ẋ1 = (J 2 -J 3 )x 2 x 3 -ū sat 0 ( k1 x 1 ) + d 1 (19a) J 2 ẋ2 = (J 3 -J 1 )x 3 x 1 -ū sat 0 ( k2 x 2 ) + d 2 (19b) J 3 ẋ3 = (J 1 -J 2 )x 1 x 2 -ū sat 0 ( k3 x 3 ) + d 3 , (19c)
where ki := k i /ū for each i ∈ {1, 2, 3}. Consequently, noticing that |L h V (x)| = 0 for all x = 0, it holds that

L f V + L g V sat(k(x)/ū) |L h V | = - x 1 sat( k1 x 1 ) + x 2 sat( k2 x 2 ) + x 3 sat( k3 x 3 ) |x| ū,
which is clearly a negative definite function, thus establishing (7). Moreover, letting |x| ∞ := max{|x 1 | , |x 2 | , |x 3 |} and k := min{ k1 , k2 , k3 }, it holds that

x 1 sat 0 ( k1 x 1 ) + x 2 sat 0 ( k2 x 2 ) + x 3 sat 0 ( k3 x 3 ) |x| ≥ |x| ∞ sat 0 (k |x| ∞ ) |x| .
Observing that |x| ≤ |x| ∞ √ 3, we obtain that

L f V + L g V sat(k lin (x)/ū) |L h V | ≤ -ū √ 3 sat 0 (k |x| / √ 3),
which makes (8) fulfilled with γ(s) = sat 0 (ks/ √ 3)ū/ √ 3. Thus, Assumption 1 is satisfied. Assumption 2 being trivially satisfied in this case (since |L h V | = |x|), we conclude from Lemma 1 that, as claimed, the system is Strongly iISS with input threshold γ(∞) = ū/ √ 3.

We tested numerically the performance of both the feedback law k univ (x) proposed in ( 17) and the saturated linear control law k lin (x) provided in ( 18), for the following parameter values: J 1 = J 2 = 5 kg.m 2 , J 3 = 10 kg.m 2 , ū = 1 kg.m 3 .s -2 , and k 1 = k 2 = k 3 = 5 kg.m 2 .s -1 . As expected, as long as the disturbance norm |d| is below 1/ √ 3 kg.m 3 .s -2 the satellite angular velocities reaches the desired configuration x 1 = x 2 = x 3 = 0 m.s -1 up to a steady-state error proportional to the disturbance amplitude, with both control laws: see Figure 1. Both the control amplitudes remain below ū. A better performance is achieved by the saturated linear controller, but this is at the price of more solicitation of the thrusters. Simulations also show that the input threshold of 1/ √ 3 is a reasonable estimate of the actual disturbance amplitude that can be tolerated by the spacecraft. For instance, when considering zero disturbances on the x 1 and x 2 axes (d 1 = d 2 = 0), the systems keeps on having a bounded steady-state response for a constant disturbance d 3 below 1/ √ 3 kg.m 3 .s -2 with both the control laws, while the universal control law (17) yields unbounded response above that value. However, for the saturated linear state feedback (18), the system seems to stand disturbances up to d 3 = 1 kg.m 3 .s -2 . The corresponding plots are omitted due to space constraints.

LTI systems: the neutrally stable case

As illustrated by the spacecraft example of Section 3.5, saturated linear feedback may provide better performance than the "universal" constructions studied in the previous section. Among the systems that can be stabilized by saturated linear state feedback, we next focus on the class of neutrally stable systems affected by actuator saturation and exogenous disturbances:

ẋ = Ax -Bσ(u) + d. (20)
We recall that a neutrally stable matrix is any matrix A such that the solutions of ẋ = Ax are bounded. This is equivalent to requiring that there exists a symmetric positive definite matrix P such that A T P + P A is a positive semi-definite matrix. For the sake of generality, the function σ : R m → R m is assumed to belong to the class S m , as defined below [START_REF] Liu | On finite-gain stabilizability of linear systems subject to input saturation[END_REF].

Definition 6 (S and S m functions) S denotes the set of all locally Lipschitz bounded function S : R → R satisfying: S(0) = 0, S(s)s > 0 for all s = 0, lim inf s→0 S(s)/s > 0, and lim inf |s|→∞ |S(s)| > 0. A vector function σ : R m → R m is said to be in the class S m if it reads σ(u) = (S 1 (u 1 ), . . . , S m (u m )) T , for all u ∈ R m , where S i ∈ S for each i ∈ {1, . . . , m}.

We stress that the class S m includes, but is not limited to, sat functions. For more details about the functions included in this class, the reader is invited to refer to [START_REF] Liu | On finite-gain stabilizability of linear systems subject to input saturation[END_REF]. We state the following useful property of S m -functions. It is a straightforward m-dimensional extension of (Liu et al., 1996, Remark 2).

Fact 1 If σ ∈ S m , then there exist constants a, b, K > 0 and a measurable diagonal-matrix valued function τ : R m → R m×m such that, for all u ∈ R m ,

aI ≤ τ (u) ≤ bI, |σ(u) -τ (u)u| ≤ Kuσ(u). ( 21
)
4.1 From neutral stability to skew-symmetry Reasoning as in (Liu et al., 1996, Section 3.2) the question of robustly stabilizing (20) when A is neutrally stable boils down to the case when A is skew-symmetric. This comes from the fact that any neutrally stable matrix is similar to diag(A H , A S ) where A H is a Hurwitz matrix and A S is skew-symmetric. This lets us consider that A is skew-symmetric without loss of generality.

Strong iISS by saturated linear feedback

Beyond L p -stability results for disturbances entering the function σ, it was shown in [START_REF] Liu | On finite-gain stabilizability of linear systems subject to input saturation[END_REF] that the linear state feedback u = B T x globally asymptotically stabilizes the saturated system (20) in the absence of exogenous disturbances. Theorem 2 in [START_REF] Liu | On finite-gain stabilizability of linear systems subject to input saturation[END_REF] also shows that solutions are bounded if the disturbance d is of sufficiently low amplitude. The following result unifies and goes further these observations, by establishing that the same feedback law ensures Strong iISS to the system (20).

Theorem 2 Let σ ∈ S m and assume that A ∈ R n×n is skew-symmetric and that the pair (A, B) is controllable.

Then the linear static state feedback u = B T x makes the saturated system (20) Strongly iISS.

The proof of this result, provided in Section 5.4, relies on the following technical result.

Lemma 2 Let A ∈ R n×n be a skew-symmetric matrix and B ∈ R n×m be such that the pair (A, B) is controllable. Let D : R ≥0 → R m×m be any bounded measurable matrix-valued function satisfying D(t) + D(t) T ≥ εI for almost all t ∈ R ≥0 , where ε denotes a positive constant. Then, there exists a symmetric positive definite matrix P ∈ R n×n such that, for almost all t ∈ R ≥0 , (A -BD(t)B T ) T P + P (A -BD(t)B T ) ≤ -I.

Moreover, this matrix P can be picked as P = P 0 + χI, where P 0 ∈ R n×n denotes any symmetric positive definite matrix satisfying

(A -εBB T ) T P 0 + P 0 (A -εBB T ) ≤ -2I, ( 22
)
as ensured by the controllability of (A, B), and χ denotes any constant satisfying

χ ≥ 1 ε sup t≥0 |P 0 B(εI -D(t))| . ( 23
)
The proof of Lemma 2 can be found along the lines of (Liu et al., 1996, Lemma 3.2 and Corollary 1) and is therefore omitted.

Estimate of the input threshold

The proof of Theorem 2 is constructive: once a matrix P such as the one generated by Lemma 2 is known, we can estimate the resulting input threshold for (20). These findings are summarized by the following result.

Corollary 3 Let σ ∈ S m and let A ∈ R n×n be a skew-symmetric matrix such that the pair (A, B) is controllable. Let a, b and K be any positive constants such that ( 21) holds for all u ∈ R m , where τ : R m → R m×m is the measurable diagonal-matrix valued function. Let P 0 ∈ R n×n be any symmetric positive definite matrix such that

(A -2aBB T ) T P 0 + P 0 (A -2aBB T ) ≤ -2I. ( 24
)
Finally, let χ be the positive constant defined as

χ = |2a -b| 2a |P 0 B| , ( 25
)
and let P := P 0 + χI. Then (20) in closed loop with the control law u = B T x is Strongly iISS with input threshold

R = 1 2K |P B| + |P | (4K |P B| /3) 1/3 . ( 26
)
Note that the existence of such constants a, b, k and such a function τ is ensured by Fact 1. The existence of a matrix P 0 satisfying ( 24) is guaranteed by the controllability of the pair (A, B). The proof of this result follows straightforwardly from that of Theorem 2. We provide its main steps in Section 5.5 for the sake of completeness.

For some particular saturations, the function τ of Fact 1 can be picked as a constant matrix. This includes for instance saturation functions of the form:

S i (s) = sat ℓ (s) := sign(s) min{ℓ |s| ; 1}, ∀s ∈ R, (27)
where ℓ denotes its linear slope (note that, when ℓ = 1, we recover the sat 0 function used all along Section 3). For such functions, the expression of the input threshold estimate is slightly simpler. We summarize this in the following corollary.

Corollary 4 Let S ∈ S m and let A ∈ R n×n be a skew-symmetric matrix such that the pair (A, B) is controllable.

Assume that there exist τ , K > 0 such that

|σ(u) -τ u| ≤ Kuσ(u), ∀u ∈ R m . ( 28
)
Let P 0 ∈ R n×n be any symmetric positive definite matrix such that

(A -2τ BB T ) T P 0 + P 0 (A -2τ BB T ) ≤ -2I, (29)
as ensured by the controllability of the pair (A, B). Finally, let P := P 0 + 1 2 |P 0 B| I. Then the system (20) in closed loop with the control law u = B T x is Strongly iISS with the input threshold given in (26).

Example: the harmonic oscillator

We finally illustrate the above results with the following planar system:

ẋ1 ẋ2 = 0 1 -1 0 x 1 x 2 - 0 1 sat ℓ (u) + d, (30)
where ℓ > 0. This system is in the form of (20) with

A = 0 1 -1 0 , B = 0 1 , σ(s) = sat ℓ (s).
Note that the perturbation is not matching, as it affects the dynamics of x 1 although no control is available in that direction. The pair (A, B) being controllable, we conclude with Theorem 2 that the state feedback u = B T x = x 2 makes the system (30) Strong iISS. In addition, we can estimate its input threshold by invoking Corollary 4. To that end, notice that |sat ℓ (s) -ℓs| ≤ ℓssat ℓ (s) for all s ∈ R, meaning that ( 28) is satisfied with τ = K = ℓ. Furthermore, the Lyapunov equation ( 29) is satisfied with the following symmetric positive definite matrix:

P 0 = 1 2 2ℓ + 1/ℓ 1 1 1/ℓ . Noticing that |P 0 B| = 1 2 √ 1 + ℓ 2
, the input threshold of (30) in closed loop with u = B T x = x 2 can be computed as a function of the slope ℓ of the saturation according to the estimate (26). We obtain the curve reported in Figure 2. This plot shows that the estimate of R provided by Corollary 4 is not accurate for this specific example, as it tends to zero for large values of the slope ℓ (meaning when sat ℓ tends to the sign function). Simulations suggest that the actual input threshold rather tends to 1. Although providing an explicit estimate of the input threshold, the tools employed in this paper fail at providing a tighter bound. The authors believe that a better choice of the feedback law than merely u = B T x would allow a better estimate of the guaranteed input threshold, but this goes beyond the scope of the paper.

Proofs

Proof of Lemma 1

The total derivative of V along the solutions of (6) in closed loop with u = k(x) reads

V = L f V (x) + L g V (x)k(x) + L h V (x)d ≤ L f V (x) + L g V (x)k(x) + |L h V (x)| |d| .
In view of (8) in Assumption 1 it holds that, for all x = 0,

L h V (x) = 0 |d| ≤ γ(|x|) ⇒ V < 0.
Moreover, from (7), it holds that, for all x = 0,

L h V (x) = 0 ⇒ V < 0.
Therefore, noticing that V = 0 for x = 0, there exists a PD function ρ such that, for all x ∈ R n and all d ∈ R p ,

|d| ≤ γ(|x|) ⇒ V ≤ -ρ(|x|). (31)
We now rely on the following result.

Proposition 1 Assume that there exist a proper storage function V : R n → R ≥0 , a class K function γ and a PD function ρ such that, for all x ∈ R n and all d ∈ R p ,

|d| ≤ γ(|x|) ⇒ ∂V ∂x (x)f (x, d) ≤ -ρ(|x|).
Then ( 20) is ISS with respect to inputs d ∈ U p <γ(∞) .

The proof of this proposition follows from typical manipulations on ISS Lyapunov functions and is therefore omitted. We stress that, in the case when γ ∈ K ∞ , we recover a classical ISS characterization [START_REF] Sontag | On characterizations of the Input-to-State Stability property[END_REF].

Invoking Proposition 1 we conclude from (31) that, under the control law u = k(x), the system ( 6) is ISS with respect to all d ∈ U p <γ(∞) . Consequently, there is only left to prove that this system is iISS. To this aim, let W (x) := ln(1 + V (x)). Noticing that Assumption 1 ensures the existence of a PD function ρ such that

L f V (x) + L g V (x)k(x) ≤ -ρ(|x|), we get that Ẇ = L f V (x) + L g V (x)k(x) + L h V (x)d 1 + V (x) ≤ - ρ(|x|) 1 + V (x) + |L h V (x)| 1 + V (x) |d|.
In view of (10), which is ensured by Assumption 2, we obtain that Ẇ ≤ -ρ(|x|) 1 + V (x) + K|d|.

Noting that x → ρ(|x|) 1+V (x) is a PD function we can thus deduce by [START_REF] Angeli | A characterization of integral input to state stability[END_REF] that the system is iISS. We conclude that the system is indeed Strongly iISS with input threshold γ(∞).

Proof of Theorem 1

For notation simplicity, let a(x)

:= L f V (x) and b(x) := |L g V (x)|
2 . The smoothness and magnitude properties of the feedback law k(x) are established in [START_REF] Lin | A universal formula for stabilization with bounded controls[END_REF]. Moreover, since |k(x)| ≤ 1, it holds that

L f V + L g V sat(k(x)) = L f V + L g V k(x) = a(x) + b(x)κ(a(x), b(x)).
In view of Lemma 1, since Assumption 2 holds, only Assumption 1 needs to be checked. Since the feedback law proposed in [START_REF] Lin | A universal formula for stabilization with bounded controls[END_REF] ensures a(x) + b(x)κ(a(x), b(x)) < 0 for all x = 0, all we need to show is (8

), that is |a(x) + b(x)κ(a(x), b(x))| > α(|x|) |L h V (x)| , (32
) for some K function α. To that end, first notice that |a(x)| + b(x) = 0, ∀x = 0; indeed, if a(x) = 0 this holds trivially, and if a(x) = 0 it holds that b(x) = 0 since V is a CLF. Recalling that b(x) ≥ 0, this in turn implies that

|a(x)| + b(x) 1 + b(x) = 0, ∀x = 0. (33)
Moreover, (12) ensures that lim inf

|x|→∞ 1 |L h V (x)| |a(x)| + b(x) 1 + b(x) > 0. ( 34
)
To see this, notice that (12) implies that either lim inf

|x|→∞ |a(x)| |L h V (x)| > 0 or lim inf |x|→∞ |b(x)| |L h V (x)| > 0.
In the first case, (34) trivially holds. In the second case, it holds that lim inf |x|→∞ |b(x)| / |L h V (x)| 1 + b(x) > 0, which also makes (34) fulfilled. Combining ( 33) and ( 34) ensures the existence of a class K function α such that

|L h V (x)| α(|x|) < |a(x)| + b(x) 1 + b(x) , ∀x = 0. ( 35
)
Furthermore, omitting the x-dependency in the notation and recalling that a + bκ(a, b) < 0, it holds that

|a + bκ(a, b)| = a √ 1 + b - √ a 2 + b 2 1 + √ 1 + b = √ 1 + b 1 + √ 1 + b a - a 2 + b 2 1 + b > 1 2 a - a 2 + b 2 1 + b , (36)
where the last bound comes from the fact that b → √ 1 + b/(1 + √ 1 + b) is greater than 1/2 over R >0 . Now, pick any x = 0 and consider the following cases. (37)

Case 2: b(x) = 0, a(x) ≤ 0. Then we have from (36) that

|a + bκ(a, b)| > 1 2 a 2 + b 2 1 + b + |a| > 1 2 b √ 1 + b + |a| .
We thus obtain from (35) that

|a + bκ(a, b)| > α(|x|) 2 |L h V (x)| . ( 38
)
Case 3: b(x) = 0 and a(x) > 0 . The fact that V is a CLF with u constrained in the unit ball guarantees that a(x) < b(x) for all x = 0 (see Definition 4). Considering separately the cases b(x) ≥ 1 and b(x) ∈ (0; 1], we can easily deduce that the following bound holds:

It follows from (35) that 3 max(b; √ b) √ 1 + b > α(|x|) |L h V (x)| . (39)
Moreover, from (36), we have that

|a + bκ(a, b)| > 1 2 a 2 + b 2 1 + b -a = 1 2 a 2 + b 2 1 + b 1 - a 2 + a 2 b a 2 + b 2 > b 2 √ 1 + b 1 - 1 + b 1 + b 2 /a 2 . ( 40
)
First consider the case when b(x) ≥ 1. Then (39) reads 3b/

√ 1 + b > α(|x|) |L h V (x)| and we get that b 2 √ 1 + b > α(|x|) |L h V (x)| 6 . (41)
On the other hand, if b(x) ∈ (0; 1], then (39) reads 3

√ b/ √ 1 + b > α(|x|) |L h V (x)| and we get from (40) that b 2 √ 1 + b > α(|x|) |L h V (x)| 6 √ b. (42)
The assumption (13) implying the existence of a class

K function µ such that √ b = |L g V (x)| ≥ µ(|x|)
, we obtain from ( 40) and ( 41)-( 42

) that |a + bκ(a, b)| > ᾱ(|x|) |L h V | 1 - 1 + b 1 + b 2 /a 2 , (43)
where ᾱ(•) := α(•) min{µ(•); 1}/6 is a class K function. We claim that there exists α ′ ∈ K such that

1 - 1 + b(x) 1 + b(x) 2 /a(x) 2 ≥ α ′ (|x|). ( 44
)
To see this first notice that, since a(x) < b(x), the above function is positive on R n \ {0}. Moreover, condition ( 14) together with the fact that 0 < a(x) < b(x) ensures that lim sup |x|→∞ b(x)/a(x) 2 > 1. Consequently:

lim inf |x|→∞ 1 - 1 + b(x) 1 + b(x) 2 /a(x) 2 > 0.
We conclude that there indeed exists a function α ′ ∈ K satisfying (44). We get from ( 44) and (43) that

|a(x) + b(x)κ(a(x), b(x))| > α ′′ (|x|) |L h V (x)| , (45)
where α ′′ (•) := ᾱ(•)α ′ (•) is also class K.

Combining (37), ( 38) and ( 45), we conclude that (32) holds. The conclusion then follows from the application of Lemma 1.

Proof of Corollary 2

Since V is a CLF with controls in the unit ball satisfying the SCP for the disturbance-free system ẋ = f (x) + g(x)u, it was shown in [START_REF] Lin | A universal formula for stabilization with bounded controls[END_REF] that the control law (15) satisfies L f V (x) + L g V (x)k(x) < 0 for all x = 0. Equivalently, there exists a continuous positive definite function ρ ∈ PD such that L f V (x) + L g V (x)k(x) ≤ -ρ(|x|) for all x ∈ R n . Hence, the derivative of W := ln(1 + V ) along the solutions of (6) satisfies

Ẇ = V 1 + V (x) = 1 1 + V (x) (L f V (x) + L g V (x)k(x) + L h V (x)d) ≤ - ρ(|x|) 1 + V (x) + |L h V (x)| 1 + V (x) |d| .
As already stressed, Assumption 2 implies the existence of a constant K > 0 such that (10) holds. Consequently:

Ẇ ≤ - ρ(|x|) 1 + V (x) + K |d| .
The conclusion then follows by the classical Lyapunov characterization of iISS [START_REF] Angeli | A characterization of integral input to state stability[END_REF] after noticing that x → ρ(|x|)/(1 + V (x)) is a PD function.

Proof of Theorem 2

In order to establish Theorem 2, we make use of the Lyapunov function proposed in [START_REF] Liu | On finite-gain stabilizability of linear systems subject to input saturation[END_REF]. More precisely, letting

V (x) := c 3 |x| 3 + x T P x, ∀x ∈ R n ,
where P ∈ R n×n is a convenient symmetric positive definite matrix, and c > 0 denotes some well chosen constant, we claim that the proper C 1 Lyapunov function candidate

Ṽ (x) := 1 3 (1 + V (x)) 1/3 -1 (46)
satisfies, along the solutions of (20) in closed loop with u = B T x,

V (x) ≤ -W (x) + γ(|d|), (47)
where γ denotes a class K ∞ function and W is a continuous positive definite function satisfying lim inf x→∞ W (x) > 0.

According to (Chaillet et al., 2014a, Theorem 1), this establishes Strong iISS, as claimed in the statement.

To that aim, we start by decomposing the function V as V (x) = cV 1 (x) + V 2 (x), where V 1 (x) := |x| 3 /3 and V 2 (x) := x T P x. We will study the time derivative of V 1 and V 2 along the solutions of (20) separately. We start by the function V 1 : recalling that x T Ax = 0 for all x ∈ R n (as A is skew-symmetric), direct computations show that

V1 = |x| x T ẋ = -|x| x T Bσ(B T x) + |x| x T d. (48)
In order to study the derivative of V 2 , consider any initial state x 0 ∈ R n and any input signal d ∈ U n . Let τ be the function generated by Fact 1 and let

Ã(t) := A -Bτ (B T x(t))B T , ∀t ≥ 0,
where x(•) denotes the solution of (20) starting from x 0 . Note that the saturation function σ being locally Lipschitz and bounded, the existence of the solutions of ( 20) is ensured at all forward time, which makes the above matrix Ã(t) well defined at all times t ≥ 0. With this notation, the system (20) in closed loop with u = B T x can be rewritten as ẋ = Ã(t)x + B τ (B T x)B T x -σ(B T x) + d.

(49)

Now, in view of Fact 1 and recalling that τ (u) is a diagonal matrix for each u ∈ R m , it holds that τ (B T x(t)) + τ (B T x(t)) T ≥ 2aI, ∀t ≥ 0, for some constant a > 0 independent of x 0 . It follows that all the conditions of Lemma 2 are fulfilled with D(t) = τ (B T x(t)) and ε = 2a. Consequently, there exists a symmetric positive definite matrix P = P T such that Ã(t) T P + P Ã(t) ≤ -I, ∀t ≥ 0.

The derivative of the function V 2 (x) = x T P x with this particular matrix P along the solutions of ( 49

where the last inequality follows form the fact that the function s → s/(1 + cs 2 /3) reaches its maximum 3/4c at s = 3/c. Plugging ( 52)-( 53

Proof of Corollary 3

Since aI ≤ τ (u) ≤ bI, the constant χ introduced in (25) satisfies condition (23). By Lemma 2, the proof of Theorem 2 can be repeated with P = P 0 + χI. The rest of the proof is identical.

Conclusion

After having presented a sufficient condition for Strong iISS under saturated feedback, we have shown that Lin and Sontag's bounded control law for disturbance-free systems also ensures Strong iISS provided that a condition on the growth rate of the input term is satisfied. We have also shown that iISS can be obtained under relaxed conditions. We have illustrated the applicability of our results on a spacecraft velocity control example. Focusing on the specific class of LTI systems with skew-symmetric matrix, we have shown that a simple linear static state-feedback ensures Strong iISS. This result was illustrated on an academic example, that underlined the limits of the input threshold estimate and suggests that further work is needed to choose the feedback gains in order to obtain a tighter input threshold estimate. Finally, further research can be envisioned to check the robustness properties of saturated stabilization of chains of integrators.

Fig. 1 .

 1 Fig. 1. State and control magnitude of the spacecraft for a random disturbance with magnitude below 1/ √ 3 kg.m 3 .s -2 . Blue: saturated linear feedback k lin (x) in (18), red: universal law kuniv(x) in (17).

Fig. 2 .

 2 Fig. 2. Input threshold estimate of the planar system (30) as a function of the slope ℓ of the saturation.

  Case 1: b(x) = 0. Then (35) implies that |a(x)| > α(|x|) |L h V (x)|. Consequently |a(x) + b(x)κ(a(x), b(x))| = |a(x)| > α(|x|) |L h V (x)| .

[

  ) reads V2 = x T Ã(t) T P + P Ã(t) x+ 2x T P B τ (B T x)B T x -σ(B T x) + 2x T P d ≤ -|x| 2 + 2 |x| |P B| τ (B T x)B T x -σ(B T x) + 2x T P d. Recalling that, in view of Fact 1, τ (B T x)B T x -σ(B T x) ≤ Kx T Bσ(B T x), it follows that V2 ≤ -|x| 2 + 2K |x| |P B| x T Bσ(B T x) + 2x T P d.(50)Combining (48) and (50) and picking c = 2K |P B|, we obtain that the derivative ofV (x) = cV 1 (x) + V 2 (x) along the solutions of (20) satisfies V ≤ -|x| 2 + c |x| 2 |d| + 2 |P | |x| |d| .Thus the function Ṽ , defined in (46the two nonnegative term of this upper bound separately. First, it holds that |x| 2

.

  ) into (51) leads, as claimed, toV (x) ≤ -W (x) + γ(|d|),where γ denotes the following K ∞ function:γ(s) := (9c) 1/3 + |P | 6 c 1/3 s, ∀s ≥ 0. and W : R n → R ≥0 is the function defined as , ∀x ∈ R n ,where we recall that c = 2K |P B|. Notice that W is continuous and positive definite and Thus, we can apply(Chaillet et al., 2014a, Theorem 1) to conclude that (20) is Strongly iISS with input thresholdγ -1 (3/c) 2/3 = 1 c + |P | (2c/3) 1/3 = 1 2K |P B| + |P | (4K |P B| /3) 1/3 .

max(b; √ b) √ 1 + b > a + b √ 1 + b .

This work has received funding from the European Union Seventh Framework Programme [FP7/2007-2013] under grant agreement n257462 HYCON2 Network of excellence, and from the iCODE institute, research project of the IDEX Paris-Saclay.


J.-B Hoock

O Teytaud
email: teytaud@lri.fr

Bandit-Based Genetic Programming with Application to Reinforcement Learning

Keywords: Reinforcement learning, Monte-Carlo Tree Search, Genetic Programming, Bernstein races

When looking for relevant mutations of a learning program, a main trouble is that evaluating a mutation is noisy; we can have a precise estimate of a mutation, if we test it many times, but this is quite expensive; or we can have a rough estimate, which is much faster. This is a load balancing problem: on which mutations should we spend more effort ? Bandit algorithms have been used for this load balancing: they choose the computational effort spent on various possible mutations, depending on the current estimate of the quality of a mutation and on the precision of this estimate. However, in many cases, we want to validate some possible mutations; when should we stop the bandit mutation, and analyze new mutations ? Racing algorithms are aimed at combining the load balancing and the statistical validation; we here mathematically analyze and experiment racing algorithms in the context of mutations of programs, i.e. genetic programming.

As an application, we consider Monte-Carlo Tree Search. Monte-Carlo Tree Search is a recent very successful algorithm for reinforcement learning, successfully applied in games and Markov decision Processes. We consider the validation of randomly generated patterns in a Monte-Carlo Tree Search program. Our bandit-based genetic programming (BGP) algorithm, with proved mathematical properties, outperformed a highly optimized handcrafted module of a well-known computer-Go program with several world records in the game of Go.

Introduction

Genetic Programming (GP) is the automatic building of programs for solving a given task. In this paper, we investigate a bandit-based approach for selecting fruitful modifications in genetic programming, and we apply the result to our reinforcement learning program MoGo.

When learning patterns in a reinforcement learning algorithms with limited ressources in an uncertain framework, there are two issues:

• which modifications of the policy are to be tested now ?

• when we have no more resources (typically no more time), we must decide which modifications are accepted.

The second issue is often addressed through statistical tests. However, when many modifications are tested, it is a problem of multiple simultaneous hypothesis testing: this is far from being straightforward; historically, this was poorly handled in many old applications. CournotDesrosières (2000) stated that if we consider a significance threshold of 1% for differences between two sub-populations of a population, then, if we handcraft plenty of splittings in two sub-populations, we will after a finite time find a significant difference, whenever the two populations are similar. This was not for genetic programming, but the same thing holds in GP: if we consider 100 random mutations of a program, all of them being worst than the original program, and if we have a 1% risk threshold in the statistical validation of each of them, then with probability (1 -1/100)) 100 ≃ 37% we can have a positive validation of at least one harmful mutation. Cournot concluded, in the 19th century, that this effect was beyond mathematical analysis; nonetheless this effect is clearly understood today, with the theory of multiple hypothesis testing -papers cited below clearly show that mathematics can address this problem.

The first issue is also non trivial, but a wide literature has been devoted to it: so-called bandit algorithms. This is in particular efficient when no prior information on the modifications is available, and we can only evaluate the quality of a modification through statistical results. Whereas bandits handle the first problem, and multiple simultaneous hypotehsis testing handles both cases, races are aimed at handling both problems simultaneously. Races can be based on arbitrary confidence intervals; however, in the general case (i.e. when variances might be small or not), the best tool is usually Bernstein's confidence intervals. However, when variance is never small, Hoeffding's bounds are equivalent and simpler.

Usually the principles of a Bernstein race are as follows:

• decide a risk threshold δ 0 ;

• then, modify the parameters of all statistical tests so that all confidence intervals are simultaneously true with probability ≥ 1δ 0 ;

• then, as long as you have computational resources, apply a bandit algorithm for choosing which modification to test, depending on statistics; typically, a bandit algorithm will choose to spend computational resources on the modification which has the best statistical upper bound on its average efficiency;

• at the end, select the modifications which are significant.

A main reference, with theoretical justifications, is [START_REF] Mnih | Empirical Bernstein stopping[END_REF]. A main difference here is that we will not assume that all modifications are cumulative: here, whenever two modifications A and B are statistically good, we can't select both modifications -maybe, the baseline + A + B will be worse than the baseline, whenever both baseline+A and baseline+B are better than the baseline. Also, in [START_REF] Mnih | Empirical Bernstein stopping[END_REF], the authors have no baseline; we are not aware of a framework which exactly matches our case (see however [START_REF] Even-Dar E | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF]).

In section 2, we present non-asymptotic confidence bounds. In section 3 we present racing algorithms. Then, section 4 presents our algorithm and its theoretical analysis. Section 5 is devoted to experiments.

Non-asymptotic confidence bounds

In all the paper, we consider fitness values between 0 and 1 for simplifying the writing. The most classical bound is Hoeffding's bound. Hoeffding's bound states that with probability at least 1δ, the empirical average r verifies |r -Er| ≤ deviation Hoeffding (δ, n) where n is the number of simulations and where deviation Hoeffding (δ, n) = log(2/δ)/(2n).

(

deviation Bernstein = σ 2 log(3/δ)/n + 3 log(3/δ)/n (2)
where σ is the empirical standard deviation. Bernstein's version will not be used in our experiments, because the variance is not small in our case; nonetheless, all theoretical results also hold with Bernstein's variant.

Racing algorithms

Racing algorithms are typically (and roughly, we'll be more formal below) as follows: Let S be equal to S 0 , some given set of admissible modifications. while S = ∅ do Select s = select() ∈ S with some algorithm Perform one Monte-Carlo evaluation of s. if s is statistically worse than the baseline then S ← S \ {s} s is discarded else if s is statistically better than the baseline then Accept s; S ← S \ {s} s is accepted end if end while With relevant statistical tests, we can ensure that this algorithm will select all "good" modifications (to be formalized later), reject all bad modifications, and stop after a finite time if all modifications have a non-zero effect. We refer to [START_REF] Mnih | Empirical Bernstein stopping[END_REF] for more general informations on this, or [START_REF] Koza | Genetic Programming: On the Programming of Computers by means of Natural Evolution[END_REF]; [START_REF] Holland | Genetic algorithms and the optimal allocation of trials[END_REF] for the GP case; we will here focus on the most relevant (relevant for our purpose) case. In genetic programming, it's very clear that even if two modifications are, independently, good, the combination of these two modifications is not necessarily good. We will therefore provide a different algorithm in section 4 with a proof of consistency.

Theoretical analysis for genetic programming

We will assume here that for a modification s, we can define:

• e(s), the (of course unknown) expected value of the reward when using modification s. This expected value is termed the efficiency of s. We will assume in the sequel that the baseline is 0.5 -an option is good if and only if it performs better than 0.5, and the efficiency is the average result on experiments.

• n(s), the number of simulations of s already performed.

• r(s) the total reward of s, i.e. the sum of the rewards of the n(s) simulations with modification s.

• ub(s), an upper bound on the efficiency of s, to be computed depending on the previous trials (ub(s) will be computed thanks to Bernstein bounds or Hoeffding bounds).

• lb(s), a lower bound on the efficiency of s (idem).

The two following properties will be proved for some specific functions lb and ub; the results around our BGP (bandit-based genetic programming) algorithm below hold whenever lb and ub verify these assumptions.

• Consistency: with probability at least 1δ 0 , for all calls to ub and lb, the efficiency of s is between lb(s) and ub(s):

e(s) ∈ [lb(s), ub(s)]. (3)
• Termination: when the number of simulations of s goes to infinity, then

ub(s) -lb(s) → 0. (4)
These properties are exactly what is ensured by Bernstein's bounds or Hoeffding's bounds. They will be proved for some variants of ub and lb defined below (Lemma 4.1, using Hoeffding's bound); they will be assumed in results about the BGP algorithm below. Therefore, our results about BGP (Theorem 4.2) will hold for our variants of lb and ub. Our algorithm and proof do not need a specific function ub or lb, provided that these assumptions are verified. However, we precise below a classical form of ub and lb, in order to point out that there exists such ub and lb; moreover, they are easy to implement. lb and ub are computed by a function with a memory (i.e. with static variables):

Function computeBounds(s) (variant 1) Static internal variable: nbT est(s), initialized at 0.

Let n be the number of times s has been simulated. Let r be the total reward over those s simulations.

nbT est(s) = nbT est(s) + 1 Let lb(s) = r/n -deviation Hoeffding δ 0 /(#S × 2 nbT est(s) ), n . Let ub(s) = r/n + deviation Hoeffding δ 0 /(#S × 2 nbT est(s) ), n .
What is important in these formula is that the sum of the δ 0 /(#S × 2 nbT ests(s) ), for s ∈ S and nbT est(s) ∈ {1, 2, 3 . . .}, is at most δ 0 . By union bound1 , this implies that the overall risk is at most δ 0 . The proof of the consistency and of the termination assumptions are therefore immediate consequences of Hoeffding's bounds (we could use Bernstein's bounds if we believed that small standard deviations matter). A (better) variant, based on n≥1 1/n 2 = π 2 /6 is Function computeBounds(s) (variant 2) Static internal variable: nbT est(s), initialized at 0. Let n be the number of times s has been simulated. Let r be the average reward over those s simulations.

nbT est(s) = nbT est(s) + 1 Let lb(s) = r/n-deviation Hoeffding δ 0 /(#S × π 2 nbT est(s) 2 6 ), n . Let ub(s) = r/n+deviation Hoeffding δ 0 /(#S × π 2 nbT est(s) 2 6 ), n .
We show precisely the consistency of computeBounds below. Lemma 4.1 (Consistency of computeBounds.) For all S finite, for all algorithms calling computeBounds and simulating modifications in arbitrary order, with probability at least 1 -δ 0 , for all s and after each simulation, lb(s) ≤ e(s) ≤ ub(s).

Proof:

We do the proof for the first variant of the algorithm; the case of the second variant is similar. This is an immediate consequence of Hoeffding's bound. The risk of a confidence interval [lb(s), ub(s)] is δ 0 /(#S ×2 n bT est(s)) by Hoeffding's bound. By union bound, the risk for all confidence intervals simultaneously is therefore the sum over #S patterns of ∞ nbT ests=1 δ 0 /(#S × 2 nbT ests ), i.e. δ 0 . Our algorithm, BGP (Bandit-based Genetic Programming), based on the computeBounds function above, is as follows:

BGP algorithm. S = S 0 = some initial set of modifications.

while S = ∅ do Select s ∈ S // the selection rule is not specified here // (the result is independent of it) Let n be the number of simulations of modification s. Simulate s n more times (i.e. now s has been simulated 2n times).

//this ensures nbT ests(s) = O(log(n(s))) computeBounds(s) if lb(s) > 0.501 then Accept s; exit the program. else if ub(s) < 0.504 then S = S \ {s} s is discarded.

end if end while

We do not specify the selection rule. The result below is independent of the particular rule.

Theorem 4.2 (Consistency of BGP)

When using variant 1 or variant 2 of computeBounds, or any other version ensuring consistency (Eq. 3) and termination (Eq. 4), BGP is consistent in the sense that:

1. if at least one modification s has efficiency > .504, then with probability at least 1δ 0 a modification with efficiency > .501 will be selected (and the algorithm terminates).

2. if no modification has efficiency > .504, then with probability at least 1δ 0 the algorithm will (a) either select a modification with efficiency > .501 (and terminate); (b) or select no modification and terminate.

Remark: The constants 0.501 and 0.504 are arbitrary provided that the latter is greater or equal to the former. Our results are only for consistency; we have no bounds on rates. This is the main further work.

Proof: First, the algorithm necessarily terminates. This is proved as follows:

• Assume, in order to get a contradiction, that the algorithm does not terminate.

• Then, at least one modification s is tested infinitely often.

• By the strong law of large numbers, applied to the finitely many modifications of S and in particular to s, r(s)/n(s) → e(s) almost surely.

(5)

• The following holds for all s which are simulated infinitely often:

nbT ests(s) = O(log(n(s))) (6)
(see the pseudocode of BGP and remarks therein for the proof of Eq. 6).

• Eq. 5 and Eq. 6 together imply that (for both variants of computeBounds) that lb(s)r(s)/n(s) → 0 and ub(s)r(s)/n(s) → 0. As a consequence, lb(s) → e(s) and ub(s) → e(s).

(7)

• Necessarily, e(s) > 0.501 or e(s) < 0.504. This and Eq. 7 imply that one of the halting condition is met or s is discarded; this is a contradiction with the fact that s is simulated infinitely often.

Second, thanks to Lemma 4.1, we can claim that with probability 1δ 0 ,

∀s, e(s)

∈ [lb(s), ub(s)]. (8)
In the rest of this proof, we consider only what happens in this case (the result is only claimed with probability 1δ 0 , and therefore we do not have to consider the other case which occurs with probability ≤ δ 0 ). Thanks to Eq. 8, the proof of the remaining part (i.e. the properties 1 and 2, given that termination is established) is easy:

• By construction of the algorithm, a modification s can't be discarded if its upper bound is > .504; as e(s) < ub(s), it can't be discarded if e(s) > .504.

• By construction of the algorithm, a modification can't be accepted it its lower bound is < .501; as lb(s) < e(s), it can't be accepted if e(s) < .501.

We have only considered |S| < ∞. The extension to S = {s 1 , s 2 , s 3 , . . .} countable is straightforward with the following variant of computeBounds: Function computeBounds(s) (variant 3, for countable S) Static internal variable: nbT est(s), initialized at 0. Let n be the number of times s has been simulated. Let r be the average reward over those s simulations. nbT est(s) = nbT est(s) + 1 Let i be such that s i = s and δ i = 6δ 0 /(π2 i 2 ).

Let lb(s) = r/ndeviation Hoeffding δ i /( π 2 nbT est(s) 2 6 ), n . Let ub(s) = r/n + deviation Hoeffding δ i /( π 2 nbT est(s) 2 6 ), n .

The proof of Lemma 4.1 still holds, with this adapted lb and ub, with S countable. For Theorem 4.2, we have to ensure the termination criterion (Eq. 4). For this, we can use the following select algorithm: select = s i0 with i 0 minimum such that s i ∈ S. This means that we validate or invalidate patterns one at a time 2 . This solution, which ensures that all possible modifications are tested iteratively and that the performance is non-decreasing, will not be further discussed in this paper. Jouandeau (2007); [START_REF] Kato | Parallel monte-carlo tree search with simulation servers[END_REF], automatic building of huge opening books [START_REF] Audouard | Grid coevolution for adaptive simulations; application to the building of opening books in the game of go[END_REF]. Thanks to all these improvements, our implementation MoGo already won even games against a professional player in 9x9 (Amsterdam, 2007;Paris, 2008;Taiwan 2009), and recently won with handicap 6 against a professional player (Tainan, 2009), and with handicap 7 against a top professional player, Zhou Junxun, winner of the LG-Cup 2007(Tainan, 2009). Besides impressive results for the game of Go, MCTS/UCT have been applied to non-linear optimization Auger & Teytaud (2010), optimal sailing [START_REF] Kocsis | several improvements have appeared like First-Play Urgency Wang & Gelly[END_REF], active learning [START_REF] Rolet | Optimal active learning through billiards and upper confidence trees in continous domains[END_REF]. The formula used in the bandit is incredibly complicated, and it is now very hard to improve the current best formula [START_REF] Wang M.-H | The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments[END_REF].

Here we will consider only mutations consisting in adding patterns in our program MoGo. Therefore, accepting a mutation is equivalent to accepting a pattern. We experiment random patterns for biasing UCT. The reader interested in the details of this is referred to [START_REF] Wang M.-H | The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments[END_REF]. Our patterns contain jokers, black stones, empty locations, white stones, locations out of the goban, and are used as masks over all the board: this means that for a given location, we consider patterns like "there is a black stone at coordinate +2,+1, a stone (of any color) at coordinate +3,0, and the location at coordinate -1,-1 is empty". This is a very particular form of genetic programming.

We consider here the automatic generation of patterns for biasing the simulations in 9x9 and 19x19 Go. Please note that:

• When we speak of good or bad shapes here, it is in the sense of "shapes that should be more simulated by a UCT-like algorithm", or "shapes that should be less simulated by a UCT-like algorithm". This is not necessarily equivalent to "good" or "bad" shapes for human players (yet, there are correlations).

• In 19x19 Go, MoGoCVS is based on tenths of thousands of patterns as in [START_REF] Chaslot | Progressive strategies for monte-carlo tree search[END_REF]. Therefore, we do not start from scratch. A possible goal would be to have similar results, with less patterns, so that the algorithm is faster (the big database of patterns provides good biases but it is very slow).

• In 9x9 Go, there are no big library of shapes available; yet, human expertise has been encoded in MoGo, and we are far from starting from scratch. Engineers have spent hundreds of hours manually optimizing patterns. The goals are both (i) finding shapes that should be more simulated (ii) finding shapes that should be less simulated.

Section 5.1 presents our experiments for finding good shapes in 9x9 Go. Section 5.2 presents our experiments for finding bad shapes in 9x9 Go. Section 5.3 presents our unsuccessful experiments for finding both good and bad shapes in 19x19, from MoGoCVS and its database of patterns as in [START_REF] Chaslot | Progressive strategies for monte-carlo tree search[END_REF]. Section 5.4 presents results on MoGoCVS with patterns removed, in order to improve the version of MoGoCVS without the big database of pattern.

Finding good shapes for simulations in 9x9 Go

Here the baseline is MoGo CVS. All programs are run on one core, with 10 000 simulations per move. All experiments are performed on Grid5000. The selection rule, not specified in BGP, is the upper bound as in UCBLai & Robbins (1985); [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF]: we simulate s such that ub(s) is maximal. We here test modifications which give a positive bias to some patterns, i.e. we look for shapes that should be simulated more often.

For each iteration, we randomly generate some individuals, and test them with the BGP algorithm. For the three first iterations, 10 patterns were randomly generated; the two first times, one of these 10 patterns was validated; the third time, no pattern was validated. Therefore, we have three version of MoGo: MoGoCVS, MoGoCVS+P1, and MoGoCVS+P1+P2, where P1 is the pattern validated at the first iteration and P2 is the pattern validated at the second iteration. We then tested the relative efficiency of these MoGos as follows:

Tested code Opponent Success rate MoGoCVS + P1 MoGoCVS 50.78% ± 0.10% MoGoCVS + P1 + P2 MoGoCVS +P1 51.2% ± 0.20% MoGoCVS + P1 + P2 MoGoCVS 51.9% ± 0.16%

We also checked that this modification is also efficient for 100 000 simulations per move, with success rate 52.1 ± 0.6% for MoGoCVS+P1+P2 against MoGoCVS.

There was no pattern validated during the third iteration, which was quite expensive (one week on a cluster). We therefore switched to another variant; we tested the case |S 0 | = 1, i.e. we test one individual at a time.We launched 153 iterations with this new version. There were therefore 153 tested patterns, and none of them was validated.

Finding bad shapes for simulations in 9x9 Go

We now switched to the research of negative shapes, i.e. patterns with a negative influence of the probability, for a move, to be simulated. We kept |S 0 | = 1, i.e. only one pattern tested at each iteration. There were 173 iterations, and two patterns P3 and P4 were validated. We verified the quality of these negative patterns as follows, with mogoCVS the version obtained in the section above: This leads to an overall success of 53.5% against MoGoCVS, obtained by BGP.

Improving 19x19 Go with database of patterns

In 19x19 Go, all tests are performed with 3500 simulations per move. Here also, we tested the case |S 0 | = 1, i.e. we test one individual at a time. We tested only positive biases. The algorithm was launched for 62 iterations. Unfortunately, none of these 62 iterations was accepted. Therefore, we concluded that improving these highly optimized version was too difficult. We switched to another goal: having the same efficiency with faster simulations and less memory (the big database of patterns strongly slowers the simulations and takes a lot of simulations), as discussed below.

Improving 19x19 Go without database of patterns

We therefore removed all the database of patterns; the simulations of MoGo are much faster in this case, but the resulting program is nonetheless weaker because simulations are far less efficient (see e.g. [START_REF] Wang M.-H | The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments[END_REF]). Fig. 2 presents a known (from Senseis http://senseis.xmp.net/?GoodEmptyTriangle#toc1) difficult case for patterns: move 2 is a good move in spite of the fact that locally (move 2 and locations at the east, north, and north east) form a known very bad pattern (termed empty triangle), termed empty triangle, and is nonetheless a good move due to the surroundings. Figure 2: An example from Senseis of good large pattern in spite of a very bad small pattern. The move 2 is a good move.

We keep |S 0 | = 1, and we have 443 iterations. There were ten patterns validated, validated at iterations 16, 22, 31, 57, 100, 127, 136, 260, 285 and 331. We could validate these patterns Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,Q9 and Q10 as follows. MoGoCVS+AE means MoGoCVS equipped with the big database of patterns extracted from games between humans. An important property of BGP is that all validated patterns are confirmed by these independent experiments. We see however that in 19x19, we could reach roughly 30% of success rate against the big database built on human games (therefore our BGP version uses far less memory than the other version); we will keep this experiment running, so that maybe we can go beyond 50 %. Nonetheless, we point out that we already have 60 % against the version without the database, and the performance is still increasing (improvements were found at iterations 16,22,57,100,122,127, with regular improvements -we have no plateau yet) -therefore we successfully improved the version without patterns, which is lighter (90% of the size of MoGoCVS is in the database).

We proposed an original tool for genetic programming and applied it in a reinforcement learning problem. This tool is quite conservative: the learning is based on a set of admissible modifications, and has strong theoretical guarantees. Interestingly, the application of this theory to GP was successful in experiments, with in particular the nice property that all patterns selected during the GP run could be validated in independent experiments. We point out that when humans test modifications of MoGo, they usually test their algorithms based on simple confidence intervals, without taking into account the fact that, as they test multiple variants, one of these variants might succeed just by chance -it happened quite often that modifications accepted in the CVS were later removed, causing big delays and many non-regression tests. This is in particular true for this kind of applications, because the big noise in the results, the big computational costs of the experiments, imply that people can't use p-values like 10 -10 -with BGP, the confidence intervals can be computed at a reasonnable confidence level, and the algorithm takes care by itself of the risk due to the multiple simultaneous hypothesis testing.

In 9x9 Go, BGP outperformed human development, and the current CVS of MoGo is the version developped by BGP. In 19x19 Go, we have an improvement over the default version of MoGo, using a big database learnt offline in supervised learning, but not against the version enabling the use of big databases -we nonetheless keep running the experiments as the success rate is still increasing and we had a big improvement for light versions.

Further work: The main further work is the analysis of the number of iterations before finding a good modification when such a good modification exists, depending on the number of patterns tested. This should in particular clarify the differences between the different versions of "computeBounds". We are very grateful to reviewer # 2 for pointing out interesting remarks around that.

Using something better than the union bound is probably possible as the tests over several patterns are independent; yet, this is not straightforward as independence holds between the patterns, but not for the several tests on a same pattern.

Other solutions are possible, provided that, if the algorithm does not stop, then log(nbT ests(s i )i) = o(n(i)) for all i.

Acknowledgements

Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).