Mathieu Granzotto

Romain Postoyan
email: romain.postoyan@univ-lorraine.fr

Dragan Nešić

Lucian Buşoniu
email: lucian.busoniu@aut.utcluj.ro

Jamal Daafouz
email: jamal.daafouz@univ-lorraine.fr

When to stop value iteration: stability and near-optimality versus computation

Value iteration (VI) is a ubiquitous algorithm for optimal control, planning, and reinforcement learning schemes. Under the right assumptions, VI is a vital tool to generate inputs with desirable properties for the controlled system, like optimality and Lyapunov stability. As VI usually requires an infinite number of iterations to solve general nonlinear optimal control problems, a key question is when to terminate the algorithm to produce a "good" solution, with a measurable impact on optimality and stability guarantees. By carefully analysing VI under general stabilizability and detectability properties, we provide explicit and novel relationships of the stopping criterion's impact on near-optimality, stability and performance, thus allowing to tune these desirable properties against the induced computational cost. The considered class of stopping criteria encompasses those encountered in the control, dynamic programming and reinforcement learning literature and it allows considering new ones, which may be useful to further reduce the computational cost while endowing and satisfying stability and near-optimality properties. We therefore lay a foundation to endow machine learning schemes based on VI with stability and performance guarantees, while reducing computational complexity.

Introduction

Value iteration (VI) is an established method for optimal control, which plays a key role in reinforcement learning (Sutton and Barto, 2017;[START_REF] Lewis | Reinforcement learning and adaptive dynamic programming for feedback control[END_REF][START_REF] Buşoniu | Reinforcement learning for control: Performance, stability, and deep approximators[END_REF][START_REF] Pang | Adaptive dynamic programming for finite-horizon optimal control of linear time-varying discrete-time systems[END_REF]. This algorithm consists in iteratively constructing approximations of the optimal value function, based on which near-optimal control inputs are derived for a given dynamical nonlinear systems and a given stage cost. The convergence of said approximations to the optimal value function is established in, e.g., [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF][START_REF] Bertsekas | Value and policy iterations in optimal control and adaptive dynamic programming[END_REF] under mild conditions. To benefit from this convergence property, VI often needs to be iterated infinitely many times. However, in practice, we cannot do so and must stop iterating the algorithm before to manage the computational burden, which may be critical in online applications. Heuristics are often used in the literature to stop iterating by comparing the mismatch between the value functions obtained at the current step and at the previous one, see, e.g., [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]Sutton and Barto, 2017;[START_REF] Pang | Adaptive dynamic programming for finite-horizon optimal control of linear time-varying discrete-time systems[END_REF][START_REF] Kiumarsi | H∞ control of linear discrete-time systems: Off-policy reinforcement learning[END_REF][START_REF] Liu | Error bounds of adaptive dynamic programming algorithms for solving undiscounted optimal control problems[END_REF]. An important question is then how far the obtained approximate value function is to the optimal one. To the best of our knowledge, this is only analysed in general when the cost is discounted and the stage cost takes values in a bounded set [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]). An alternative consists in asking for a sufficiently large number of iterations, as the near-optimality gap vanishes as the number of iterations increases, e.g. [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF][START_REF] Heydari | Stability analysis of optimal adaptive control using value iteration with approximation errors[END_REF][START_REF] Heydari | Revisiting approximate dynamic programming and its convergence[END_REF][START_REF] Heydari | Analysis of stabilizing value iteration for adaptive optimal control[END_REF][START_REF] Liu | Error bounds of adaptive dynamic programming algorithms for solving undiscounted optimal control problems[END_REF]Granzotto et al., 2020a), but the issue is then the computational cost. Indeed, any estimate of the number of iterations is in general subject to conservatism, and, as a result, we may iterate many more times than what is truly required to ensure "good' ' near-optimality properties. There is therefore a need for stopping criteria for VI whose impact on near-optimality is analytically established, and which are not too computationally demanding.

Our main goal is to use VI to simultaneously ensure near-optimal control and stability properties for physical systems. Stability is critical in many applications, as: (i) it provides analytical guarantees on the behavior of the controlled system solutions as time evolves; (ii) endows robustness properties and is thus associated to safety considerations, see, e.g., [START_REF] Berkenkamp | Safe model-based reinforcement learning with stability guarantees[END_REF]. We therefore consider systems and costs where general stability properties are bestowed by VI based schemes, which follows from assumed general stabilizability and detectability properties of the plant model and the stage cost as in [START_REF] Grimm | Model predictive control: for want of a local control Lyapunov function, all is not lost[END_REF][START_REF] Postoyan | Stability analysis of discrete-time infinite-horizon optimal control with discounted cost[END_REF]Granzotto et al., 2020a).

In this context, we consider state-dependent stopping criteria for VI and we analyse their impact on the near-optimality and stability properties of the obtained policies for general deterministic nonlinear plant models and stage costs, where no discount factor is employed. Instead of relying on a uniform contraction property as in, e.g., [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF][START_REF] Liu | Error bounds of adaptive dynamic programming algorithms for solving undiscounted optimal control problems[END_REF], our analysis is centered on and exploits Lyapunov stability properties. Our work covers the state-independent stopping criteria considered in the control, dynamical programming and reinforcement learning literature (Sutton and Barto, 2017;[START_REF] Lewis | Reinforcement learning and adaptive dynamic programming for feedback control[END_REF][START_REF] Buşoniu | Reinforcement learning for control: Performance, stability, and deep approximators[END_REF], but provides analytical guarantees for undiscounted stage costs taking values in unbounded sets. By carefully analysing the stopping criterion's impact on near-optimality, stability and closed-loop cost guarantees, we provide means to tune these properties against the induced computational cost, thus clarifying the tradeoff between "good enough" convergence of VI and "good properties" of generated inputs. Considering that VI is, via Q-learning, the basis of many state-of-the-art reinforcement learning methods, we believe the results of this paper contribute to the (near)-optimality analysis for reinforcement learning, as we lay a foundation to endow such schemes with stability and performance guarantees, while reducing computational complexity.

The paper and its contributions are organized as follows. In Section 2, we formally state the problem and the main assumptions. We introduce the design of stopping criteria for VI in Section 3, and show that the VI stopping criterion is indeed verified with a finite number of iterations. Our main results are found in Section 4. There, we provide near-optimal guarantees, i.e. a bound on the mismatch between the approximated value function and the true optimal value function. The bound can be easily and directly tuned by the designed stopping criterion. Additionally, stability and performance guarantees of the closed-loop system with inputs generated by VI are provided, given that the stopping criterion is appropriately chosen. In Section 5, we provide an example to illustrate our results. Concluding remarks are drawn in Section 6. The proofs are provided in this technical report in Section 7. Prior literature. The classical stopping criterion is analysed in [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF], albeit restricted to when the cost is discounted and the stage cost takes values in a bounded set. Concerning stability, works like (Granzotto et al., 2020a;[START_REF] Heydari | Stability analysis of optimal adaptive control under value iteration using a stabilizing initial policy[END_REF]Wei et al., 2015) provide conditions to ensure that the feedback law obtained ensures a stability property for a dynamical system. In particular, it is required in (Granzotto et al., 2020a) that the number of iteration d be sufficiently large, and lower bounds on d are provided, but these are subject to some conservatism. As explained above, by adapting the number of iterations with data available during computations, the algorithm avoids the conservatism often incurred by offline estimations for stability and near-optimality guarantees. This is indeed the case in an example (see Section 5), where we observe 91% fewer iterations for comparable guarantees. Similar ideas related to the stopping criterion were exploited in (Granzotto et al., 2020b), for a different purpose, namely for the redesign of optimistic planning [START_REF] Hren | Optimistic planning of deterministic systems[END_REF] to address the near-optimal control of switched systems. We are also aware of work of [START_REF] Pavlov | Early termination of NMPC interior point solvers: Relating the duality gap to stability[END_REF], which adapts the stopping criterion with stability considerations for interior point solvers for reduced computational complexity for nonlinear model predictive control applications.

Notation. Let R := (-∞, ∞), R ≥0 := [0, ∞), Z ≥0 := {0, 1, 2, . . .} and Z >0 := {1, 2, . . .}. We use (x, y) to denote [x , y ] , where (x, y) ∈ R n × R m and n, m ∈ Z >0 . A function χ : R ≥0 → R ≥0 is of class K if it
is continuous, zero at zero and strictly increasing, and it is of class K ∞ if it is of class K and unbounded. A continuous function β : R ≥0 × R ≥0 → R ≥0 is of class KL when β(•, t) is of class K for any t ≥ 0 and β(s, •) is decreasing to 0 for any s ≥ 0. The notation I stands for the identity map from R ≥0 to R ≥0 . For any sequence u = [u 0 , u 1 , . . . ] of length d ∈ Z ≥0 ∪ {∞} where u i ∈ R m , i ∈ {0, . . . , d}, and any k ∈ {0, . . . , d}, we use u| k to denote the first k elements of u, i.e. u| k = [u 0 , . . . , u k-1 ] and u| 0 = ∅ by convention. Let g : R ≥0 → R ≥0 , we use g (k) for the composition of function g with itself k times, where k ∈ Z ≥0 , and g (0) = I.

Problem Statement

Consider the system

x + = f (x, u), (1)
with state x ∈ R n , control input u ∈ U(x) where U(x) ⊆ R m is the set of admissible inputs, and f : W → R n where W := {(x, u) : x ∈ R n , u ∈ U(x)}. We use φ(k, x, u| k ) to denote the solution to system (1) at time k ∈ Z ≥0 with initial condition x and inputs sequence u| k = [u 0 , u 1 , . . . , u k-1 ], with the convention φ(0, x, u| 0 ) = x.

We consider the infinite-horizon cost

J ∞ (x, u) := ∞ k=0 (φ(k, x, u| k ), u k ), (2)
where x ∈ R n is the initial state, u is an infinite sequence of admissible inputs, : W → R ≥0 is the stage cost. Finding an infinite sequence of inputs which minimizes (2) given x ∈ R n is very difficult in general. Therefore, we instead generate sequences of admissible inputs that nearly minimize (2), in a sense made precise below, while ensuring the stability of the closed-loop system. For this purpose, we consider VI, see e.g. [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]. VI is an iterative procedure based on Bellman equation, which we briefly recall next. Assuming the optimal value function, denoted V ∞ , exists for any x ∈ R n , the Bellman equation is

V ∞ (x) = min u∈U (x) (x, u) + V ∞ (f (x, u)) . (3)
If we could solve (3) and find V ∞ , it would then be easy to derive an optimal policy, by computing the arg min corresponding to the right hand-side of (3). However, it is in general very difficult to solve (3). VI provides an iterative procedure based on (3) instead, which allows obtaining value functions (and associated control inputs), which converge to V ∞ . Hence, given an initial cost function V -1 : R n → R ≥0 , VI generates a sequence of value functions V d , d ∈ Z ≥0 , for any x ∈ R n , by iterating

V d (x) := min u∈U (x) (x, u) + V d-1 (f (x, u)) . (4)
For any d ∈ Z ≥0 , the associated input, also called policy, is defined as, for any x ∈ R n ,

u * d (x) ∈ arg min u∈U (x) (x, u) + V d-1 (f (x, u)) , (5)
which may be set-valued. The convergence of 3) is ensured under mild conditions in [START_REF] Bertsekas | Value and policy iterations in optimal control and adaptive dynamic programming[END_REF]. In the sequel we make assumptions that ensure that the arg min in (5) exists for each x ∈ R n .

V d , d ∈ Z ≥0 , to V ∞ in (
In practice, we often stop iterating VI when a stopping criterion is verified, such as, for instance, when for any

x ∈ R n , V d (x) -V d-1 (x) ≤ ε, (6)
where ε ∈ R >0 , see, e.g., [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]Sutton and Barto, 2017;[START_REF] Pang | Adaptive dynamic programming for finite-horizon optimal control of linear time-varying discrete-time systems[END_REF][START_REF] Kiumarsi | H∞ control of linear discrete-time systems: Off-policy reinforcement learning[END_REF]. However, this stopping criterion leaves much to be desired in control applications, for the following reasons: (i) it is not yet established how ε impacts the stability properties of the closed-loop system; (ii) tools to bound the mismatch between V d and V ∞ for this stopping criterion often requires a discount factor in cost function (2), which impacts stability, as shown in [START_REF] Postoyan | Stability analysis of discrete-time infinite-horizon optimal control with discounted cost[END_REF][START_REF] Postoyan | Stability guarantees for nonlinear discrete-time systems controlled by approximate value iteration[END_REF]; (iii) when V d is radially unbounded, i.e. V d (x) → ∞ when |x| → ∞, this stopping criterion is in general impossible to verify for all x ∈ R n . When the system is linear and the cost quadratic, as in [START_REF] Arnold | Generalized eigenproblem algorithms and software for algebraic riccati equations[END_REF][START_REF] Anderson | Optimal control: linear quadratic methods[END_REF][START_REF] Jiang | Computational adaptive optimal control for continuous-time linear systems with completely unknown dynamics[END_REF][START_REF] Bian | Value iteration and adaptive dynamic programming for data-driven adaptive optimal control design[END_REF], the convergence to the optimal cost function is shown to be quadratic and often the stopping criterion is instead of the form V d (x) -V d-1 (x) ≤ |ε||x| 2 . However, the link between the value of ε and resulting near-optimality and stability guarantees is not established, and in practice it is implicitly assumed that parameter ε is small enough. We consider VI terminated by a general stopping criterion. That is, for any

x ∈ R n , V d (x) -V d-1 (x) ≤ c stop (ε, x), (7)
where c stop (ε, x) ≥ 0 is a stopping function, which we design and which may depend on state vector x and a vector of tuneable parameters ε ∈ R nε with n ε ∈ Z >0 . The design of c stop is explained in Section 3. In that way, we cover the above examples as particular cases, namely c stop (x, ε) = |ε| and c stop (ε, x) = |ε||x| 2 and allow considering more general ones, e.g.

c stop (ε, x) = max{|ε 1 |, |ε 2 ||x| 2 } where (ε 1 , ε 2 ) := ε ∈ R 2 or c stop (ε, x) = x S(ε)x for some positive definite matrix S(ε) with ε ∈ R nε and n ε ∈ Z >0 .
The main novelty of this work is the provided explicit link between c stop (ε, x), near-optimality and stability guarantees. As a result, we can tune ε for the desired near-optimality and stability properties, and the algorithm stops when the cost (hence, the generated inputs) are such that these properties are verified. The analysis relies on the next assumption1 like in e.g., [START_REF] Grimm | Model predictive control: for want of a local control Lyapunov function, all is not lost[END_REF][START_REF] Postoyan | Stability analysis of discrete-time infinite-horizon optimal control with discounted cost[END_REF]Granzotto et al., 2020a).

Standing Assumption 1 (SA1)

There exist α V , α W ∈ K ∞ and continuous function σ : R n → R ≥0 such that the following conditions hold.

(i) For any x ∈ R n , there exists an infinite sequence of admissible inputs u * ∞ (x), called optimal input sequence, which minimizes (2

), i.e. V ∞ (x) = J ∞ (x, u * * * ∞ (x)), and V ∞ (x) ≤ α V (σ(x)). (ii) For any (x, u) ∈ W, α W (σ(x)) ≤ (x, u).
Function σ : R n → R ≥0 in SA1 is a "measuring" function that we use to define stability, which depends on the problem. For instance, by defining

σ = | • |, σ = | • | 2 or σ : x → x Qx with Q = Q > 0,
one would be studying the stability of the origin, and by taking σ = | • | A , one would study stability of non-empty compact set A ⊂ R n . General conditions to ensure the first part of item (i), i.e. the fact that V ∞ (x) is finite for any x ∈ R n and the existence of optimal inputs, can be found in [START_REF] Keerthi | An existence theorem for discrete-time infinite-horizon optimal control problems[END_REF]. The second part of item (i) is related to the stabilizability of system (1) with respect to stage cost in relation to σ. Indeed, it is shown in [START_REF] Grimm | Model predictive control: for want of a local control Lyapunov function, all is not lost[END_REF], Lemma 1) that, for instance, when the stage cost (x, u) is uniformly globally exponentially controllable to zero with respect to σ for system (1), see [START_REF] Grimm | Model predictive control: for want of a local control Lyapunov function, all is not lost[END_REF], Definition 2), then item (i) of SA1 is satisfied. We do not need to know V ∞ to guarantee the last inequality in item (i) of SA1. Indeed, it suffices to find, for any x ∈ R n , a sequence of inputs u(x), such the associated infinite-horizon costs verifies

J(x, u(x)) ≤ α V (σ(x)) for some α V ∈ K ∞ . Then, since V ∞ is the optimal value function, for any x ∈ R n , V ∞ (x) ≤ J(x, u(x)) ≤ α V (σ(x)
). On the other hand, item (ii) of SA1 is a detectability property of the stage cost with respect to σ, as when (x, u) is small, so is σ(x).

We are ready to explain how to design the stopping criterion in (7).

Stopping criterion design

Key observation

We start with the known observation [START_REF] Granzotto | Near-optimal control of discrete-time nonlinear systems with stability guarantees[END_REF][START_REF] Bertsekas | Dynamic programming and suboptimal control: A survey from ADP to MPC[END_REF] that, given2 V -1 = 0, at each iteration d ∈ Z ≥0 , VI generates the optimal value function for the finite-horizon cost

J d (x, u d ) := d k=0 (φ(k, x, u d | k ), u k ), (8)
where u d = [u 0 , u 1 , ..., u d ] are admissible inputs. We assume below that the minimum of ( 8) exists with relation to

u d for any x ∈ R n and d ∈ Z ≥0 . Standing Assumption 2 (SA2) For every d ∈ Z ≥0 , x ∈ R n , there exists u * * * d (x) such that V d (x) = J d (x, u * * * d ) = min u d J d (x, u d ). (9)
SA2 is for instance verified when f and are continuous and U(x) = U is a compact set. More general conditions to verify SA2 can be found in e.g. [START_REF] Keerthi | An existence theorem for discrete-time infinite-horizon optimal control problems[END_REF]. For the sake of convenience, we employ the following notation for the technical aspects of this paper.

For any k ∈ {0, 1, . . . , d} and x ∈ R n , we denote *

d (k, x) := (φ(k, x, u * * * d (x)| k ), u k ), where φ(k, x, u * * * d (x)| k )
is the solution to system (1) with optimal inputs for cost V d (x), so that

V d (x) = d k=0 * d (k, x). ( 10
)
The next property plays a key role in the forthcoming analysis.

Proposition 1 For any x ∈ R n and d ∈ Z ≥0 , * d (d, x) ≤ V d (x) -V d-1 (x).
When the stopping criterion ( 7) is verified, i.e.

V d (x) -V d-1 (x) ≤ c stop (ε, x), then * d (d, x) ≤ c stop (ε, x) in view of Proposition 1. Therefore, c stop (ε, x) is
(x)| d )), namely σ(φ(d, x, u * * * d (x)| d )) ≤ α -1 W (c stop (ε, x))
, which can be made as small as desired by reducing c stop (ε, x), which, again, we design. We exploit this property to analyse the near-optimality and the stability of the closed-loop system. Having said that, the challenges are: (i) to show that condition ( 7) is indeed verified for any x ∈ R n and some d ∈ Z ≥0 ; (ii) to select c stop to ensure stability properties when closing the loop of system (1) with inputs ( 5); (iii) to study the impact of c stop on the performance, that is, the cost along solutions, of the closed-loop system.

Satisfaction of the stopping criterion

We make the next assumption without loss of generality as we are free to design c stop .

Assumption 1 One of the next properties is verified.

(i) For any ε ∈ R nε , there is > 0 such that, for any x ∈ R n , c stop (ε, x) ≥ .

(ii) There exist L, āV , a W > 0, such that SA1 holds with α V (s) ≤ āV s, α W (s) ≤ āW s and α W (s) ≥ a W s for any s ∈ [0, L]. Furthermore, for any ε ∈ R nε , there is > 0 such that for any

x ∈ R n , c stop (ε, x) ≥ σ(x).
Item (i) of Assumption 1 can be ensured by taking c stop (ε, x) = |ε|+c stop (x, ε) with cstop (x, ε) ≥ 0 for any x ∈ R n , ε ∈ R nε , which covers (6), to give an example. Item (ii) of Assumption 1 means that the functions α V , α W , α W in SA1 can be upper-bounded, respectively lower-bounded, by linear functions on the interval [0, L]. These conditions allow to select c stop such that c stop (ε, x) → 0 when σ(x) → 0 with x ∈ R n , contrary to item (i) of Assumption 1, that is, c stop may vanish on set {x : σ(x) = 0}. This is important to provide stronger stability and performance properties for systems whose inputs are given by our VI scheme as shown in Section 4. Under item (ii) of Assumption 1, we can design c stop as, e.g.,

c stop (ε, x) = |ε|σ(x), c stop (ε, x) = min{|ε 1 |, |ε 2 ||x| 2 } where (ε 1 , ε 2 ) =: ε ∈ R 2 or c stop (ε, x) = x S(ε)
x for some positive definite matrix S(ε) as mentioned before.

The next theorem ensures the existence of d ∈ Z ≥0 such that, for any x ∈ R n , (7) holds based on Assumption 1.

Theorem 2 Suppose Assumption 1 holds. Then, for any ∆ > 0 there exists d ∈ Z ≥0 such that, for any x ∈ {z ∈ R n : σ(z) ≤ ∆}, (7) holds. Moreover, when item (ii) of Assumption 1 holds with L = ∞, there exists d ∈ Z ≥0 such that, for any x ∈ R n , (7) is satisfied.

Theorem 2 guarantees the stopping condition in ( 7) is always satisfied by iterating the VI algorithm sufficiently many times, and that the required number of iterations is uniform over sets of initial conditions of the form {x : σ(x) ≤ ∆} for given ∆ > 0 in general, unless item (ii) of Assumption 1 holds with L = ∞, in which case there exists a common, global, d for any x ∈ R n . Note that, while the proof of Theorem 2 provides a conservative estimate of d such that ( 7) is verified, this horizon estimate is not utilized in the stopping criterion, which in turn implies that VI stops with smaller horizon, in general, as illustrated in Section 5.

In the following, we denote the cost calculated at iteration d as V ε (x) := V d (x), like in (Granzotto et al., 2020b), to emphasize that the cost returned is parameterized by ε via c stop (ε, •), and denote by u * * * ε (x) an associated optimal sequence of inputs, i.e.

V ε (x) = J d (x, u * * * ε (x)). (11)
We are ready to state the main results.

Main results

In this section, we analyze the near-optimality properties of VI with the stopping criterion in (7). We then provide conditions under which system (1), whose inputs are generated by applying the state-feedback u * * * ε (x) in receding-horizon fashion, exhibits stability properties. Afterwards, the cost function ( 8) along the solutions of the induced closed-loop system are analysed, which we refer to by performance or running-cost [START_REF] Grüne | On the infinite horizon performance of receding horizon controllers[END_REF].

Relationship between V ε and V ∞

A key question is how far is V ε from V ∞ when we stop VI using (7). Since (x, u) is not constrained to take values in a given compact set, and we do not consider discounted costs, the tools found in the dynamic programming literature to analyze this relationship are no longer applicable, see [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]. We overcome this issue by exploiting SA1, and adapting the results of (Granzotto et al., 2020a) with the stopping criterion and Proposition 1 in the next theorem.

Theorem 3 Suppose Assumption 1 holds. For any ε ∈ R nε , ∆ > 0 and x ∈ {z ∈ R n , σ(z) ≤ ∆},

V ε (x) ≤ V ∞ (x) ≤ V ε (x) + v ε (x), (12)
where

v ε (x) := α V •α -1 W (c stop (ε, x)) with α V , α W from SA1. Moreover, when item (ii) of Assumption holds with L = ∞, we accept ∆ = ∞ and v ε (x) ≤ āV a W c stop (ε, x).
The lower-bound in (12) trivially holds from the optimality of V ε (x) = V d (x) for some d < ∞, and the fact that (x, u) ≥ 0 for any x ∈ R n and u ∈ U(x). The upper-bound, on the other hand, implies that the infinite-horizon cost is at most v ε (x) away from the finite-horizon V ε (x). The error term v ε (x) is small when c stop (ε, x) is small as α

V • α -1 W ∈ K ∞ .
Given that we know α V , α -1 W a priori, and we are free to design c stop as wanted, we can therefore directly make V ε (x) as close as desired to V ∞ (x) by adjusting c stop ; the price to pay will be more computations. Moreover, when item (ii) of Assumption holds with L = ∞, inequality ( 12) is verified for every x ∈ R n .

Stability

We now consider the scenario where system (1) is controlled in a receding-horizon fashion by inputs that calculate cost (11). That is, at each time instant k ∈ Z ≥0 , the first element of optimal sequence u * * * ε (x k ), calculated by VI, is then applied to system (1). This leads to the closed-loop system

x + ∈ f (x, U * ε (x)) =: F * ε (x), (13)
where

f (x, U * ε (x)) is the set {f (x, u) : u ∈ U * ε (x)} and U * ε (x) := u 0 : ∃u 1 , . . . , u d ∈ U(x) such that V ε (x) = J d (x, [u 0 , . . . , u d ])
is the set of the first input of d-horizon optimal input sequences at x, with d as defined in (7). We denote by φ(k, x) a solution to (13) at time k ∈ Z ≥0 with initial condition x ∈ R n , with some abuse of notation.

We assume next that c stop can be made as small as desirable by taking |ε| sufficiently small. As we are free to design c stop as wanted, this is without loss of generality.

Assumption 2 There exists θ : R ≥0 × R ≥0 → R ≥0 , with θ(•, s) ∈ K and θ(s, •) non-decreasing for any s > 0, such that c stop (ε, x) ≤ θ(|ε|, σ(x)) for any x ∈ R n and ε ∈ R nε .

Example of functions c stop which satisfy Assumption

2 are c stop (ε, x) = |ε|σ(x), c stop (ε, x) = max{|ε 1 |α(σ(x)), |ε 2 |} for ε = (ε 1 , ε 2 ) ∈ R 2 , α ∈ K and x ∈ R n to give a few.
The next theorem provides stability guarantees for system (13).

Theorem 4 Consider system (13) and suppose c stop verifies Assumptions 1 and 2. There exists β ∈ KL such that, for any δ, ∆ > 0, there exists ε * > 0 such that for any x ∈ {z ∈ R n : σ(z) ≤ ∆} and ε ∈ R nε with |ε| < ε * , any solution φ(•, x) to system (13) satisfies, for all k ∈ Z ≥0 , σ(φ(k, x)) ≤ max{β(σ(x), k), δ}.

Theorem 4 provides a uniform semiglobal practical stability property for the set {z : σ(z) = 0}. This implies that solutions to (13), with initial state x such that σ(x) ≤ ∆, where ∆ is any given (arbitrarily large) strictly positive constant, will converge to the set {z : σ(z) ≤ δ}, where δ is any given (arbitrarily small) strictly positive constant, by taking ε * sufficiently close to 0, thereby making c stop sufficiently small. An explicit formula for ε * is given in the proof of Theorem 4, which is nevertheless subject to some conservatism. The result should rather be appreciated qualitatively, in the sense that Theorem 4 holds for small enough ε * .

Under stronger assumptions, global exponential stability is ensured as shown in the next corollary.

Corollary 5 Suppose item (ii) of Assumption 1 holds and that c stop (ε, x) ≤ |ε|σ(x) for any

x ∈ R n and ε ∈ R nε . Let ε * > 0 be such that ε * < a 2 W āV . Then, for any x ∈ R n and ε ∈ R nε such that |ε| ≤ ε * , any solution φ(•, x) to system (13) satisfies σ(φ(k, x)) ≤ āV a W 1 - a 2 W -|ε|a V āV a W k σ(x) for all k ∈ Z ≥0 .
Corollary 5 ensures a uniform global exponential stability property of set {x : σ(x) = 0} for system (13). Indeed, in Corollary 5, the decay rate is given by 1 -

a 2 W -|ε|ā V āV a W
and take values in (0, 1)

as |ε| ≤ ε * < a 2 W
āV as required by Corollary 5, hence 1 -

a 2 W -|ε| āV a W k → 0 as k → ∞. Furthermore,
the estimated decay rate can be tuned via ε from 1 to 1 -a W āV as |ε| decreases to zero. We can therefore make the decay smaller by adjusting c stop , as in Theorem 3. Hence, by tuning ε, we can tune how fast the closed-loop converges to the attractor {x : σ(x) = 0}, and the price to pay is more computations in general.

Policy performance guarantees

In Section 4.1, we have provided relationships between the finite-horizon cost V ε and the infinitehorizon cost V ∞ . This is an important feature of VI, but this does not directly provide us with information on the actual value of the cost function (2) along solutions to (13). Therefore, we analyse the running cost [START_REF] Grüne | On the infinite horizon performance of receding horizon controllers[END_REF]) defined as

V run ε (x) := ∞ k=0 U * ε (φ(k,x)) (φ(k, x)) : φ(•, x) is a solution to (13) , (14)
where

U * ε (φ(k,x)) (φ(k, x))
is the actual stage cost incurred at time step k. It has to be noted that V run ε (x) is a set, since solutions of ( 13) are not necessarily unique. Each element V run ε (x) ∈ V run ε (x) corresponds then to the cost of a solution of (13). Clearly, V run ε (x) is not necessarily bounded, as the stage costs may not decrease to 0 in view of Theorem 4. Indeed, only practical convergence is ensured in Theorem 4 in general. On the other hand, when the set {x ∈ R n : σ(x) = 0} is globally exponentially stable as in Corollary 5, the elements of V run ε (x) in ( 14) are bounded and satisfy the next property. Theorem 6 Consider system (13) and suppose the conditions of Corollary 5 hold. For any ε such that |ε| < ε * , x ∈ R n , and

V run ε (x) ∈ V run ε (x), it follows that, V ∞ (x) ≤ V run ε (x) ≤ V ∞ (x) + w ε σ(x), (15)
with

w ε := ā3 V a W |ε| a 2 W -āV |ε|
, where the constants come from Corollary 5.

The inequality V ∞ (x) ≤ V run ε (x) of Theorem 6 directly follows from the optimality of V ∞ . The inequality V run ε (x) ≤ V ∞ (x) + w ε σ(x) provides a relationship between the running cost V run ε (x) and the infinite-horizon cost at state x, V ∞ (x). The inequality V run ε (x) ≤ V ∞ (x) + w ε σ(x) confirms the intuition coming from Theorem 3 that a smaller stopping criterion leads to tighter near-optimality guarantees. That is, when |ε| → 0, w ε → 0 and V run ε (x) → V ∞ (x) for any x ∈ R n , provided that Corollary 5 holds. In contrast with Theorem 3, stability of system ( 13) is essential in Theorem 6. Indeed, the term 1 a 2 W -ā V |ε| in the expression of w ε shows that the running cost is large when |ε| is close to a 2 W āV , hence, when stability is not guaranteed, the running cost might be unbounded.

Illustrative Example

We consider the discrete cubic integrator, also seen in [START_REF] Grimm | Model predictive control: for want of a local control Lyapunov function, all is not lost[END_REF]Granzotto et al., 2020a), which is given by

x + 1 = x 1 + u x + 2 = x 2 + u 3 , (16)
where

(x 1 , x 2 ) := x ∈ R 2 and u ∈ R. Let σ(x) = |x 1 | 3 + |x 2 | and consider cost (8) with (x, u) = |x 1 | 3 + |x 2 | + |u| 3 for any (x, u) ∈ R 2 × R.
It is shown in (Granzotto et al., 2020a) that SA1 holds with α V = 14I and α W := I.

Because it is notoriously difficult to exactly compute V d (x) and associated sequence of optimal inputs for every x ∈ R 2 , we use an approximate scheme. In particular, we rely on a simple finite Table 1: Required iterations to fulfill each stopping criteria for N = 340 2 points equally distributed in {z ∈ R n : σ(z) ≤ 2000}.

difference approximation, with N = 340 2 points equally distributed in [-10, 10] × [-10 3 , 10 3 ] for the state space or, equivalently, {x ∈ R n : σ(x) ≤ 2000}, and 909 equally distributed quantized inputs in [-20, 20] centered at 0. We consider three types of stopping criteria for which ε is a scalar. For each stopping criterion, we discuss the type of guaranteed stability and we provide in Table 1 the corresponding horizon for different values of ε, which is related to the computation cost. Then, for each horizon, we give in Table 2 estimates of the running cost for initial condition x = (10, -10 3 ), by computing the sum in ( 14) up to k = 40 instead of k = ∞, as well as the value of σ(φ(40, x)) to evaluate the convergence accuracy of the corresponding policy.

We first take the uniform stopping criterion uniform stopping criterion as in ( 6), like in, e.g., [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]Sutton and Barto, 2017;[START_REF] Pang | Adaptive dynamic programming for finite-horizon optimal control of linear time-varying discrete-time systems[END_REF][START_REF] Kiumarsi | H∞ control of linear discrete-time systems: Off-policy reinforcement learning[END_REF][START_REF] Liu | Error bounds of adaptive dynamic programming algorithms for solving undiscounted optimal control problems[END_REF], i.e. c stop (ε, x) := |ε|, with different values of ε. In this case, we have no global exponential stability or performance guarantees like in Corollary 5 and Theorem 6 a priori. Only near-optimal guarantees as in Theorem 3 and semiglobal practical stability as in Theorem 4 hold. For instance, by taking ε = 0.01, Theorem 3 holds with v ε (x) = 14 • 0.01 = 0.14 for any x ∈ R n .

We also consider the following relative stopping criterion, for any x ∈ R n and ε ∈ R, c stop (ε, x) := |ε|σ(x). The exponential stability of Corollary 5 holds for any ε ∈ R such that |ε| < a 2 W āV = 1 14 in this case. Moreover, we have near-optimality and performance properties as in Theorems 3 and 6, which were not available for the previous stopping criterion c stop (ε, x) = |ε|. Moreover, for ε = 0.01 < 1 14 , Theorem 3 holds with v ε (x) = 14 • 0.01 • σ(x) = 0.14σ(x) for any x ∈ R n , which is small when σ(x) is small, and vice versa. Compared to the previous stopping criterion, which leads to constant guaranteed near-optimality bound, here we have better guarantees when σ(x) is small (and worse ones when σ(x) is large). We observe less computations for better a priori near-optimality properties for states near the attractor, i.e. when σ(x) < 1, when compared to the previous stopping criterion. We finally consider the mixed stopping criterion c stop (ε, x) := |ε| min{σ(x), 1}, which provides better near-optimality guarantees than both considered stopping criteria. We see from Table 1, andTable 2, that by increasing iterations, we usually obtain smaller and thus better running costs as well as tighter convergence properties.

Compared to previous work (Granzotto et al., 2020a), where stability properties to (approximate) value iteration are given, we require a smaller number of iterations. Indeed, in view of (Granzotto et al., 2020a, Corollary 2), d ≥ d = 0-ln 14 2 ln 13-ln 14 = 71. Of course, this analysis is conservative and a different derivation of α V might provide different bounds on d. Here, as the algorithm is free to choose the required number of iterations via the stopping criterion, we significantly reduce its conservatism. This induces smaller computational complexity, as, e.g. for ε = 0.01 < 1 14 , exponential stability is ensured with the stoping criterion verified at d = 6, that is, 8.5% of iterations required by the lower bound d = 71 of (Granzotto et al., 2020a Table 2: Estimation of the running cost V run d (x) for x = (10, -10 3 ) and the value of σ(φ(40, x)).

Concluding remarks

Future work includes relaxing the initial condition for VI and the main assumptions. Another direction is extending the work towards stochastic problems and online algorithms, towards the final goal of stability-based computational-performance tradeoffs in reinforcement learning.

7. Proofs

7.1. Proof of Proposition 1 Let x ∈ R n and d ∈ Z >0 . Since V d-1 (x)
is the optimal value function associated to the (d -1)-

horizon cost (9), it follows V d-1 (x) ≤ d-1 k=0 * d (k, x), and by definition of * d , V d (x) = d k=0 * d (k, x). Hence * d (d, x) = d k=0 * d (k, x) - d-1 k=0 * d (k, x) ≤ V d (x) -V d-1 (x)
, which gives the desired result.

Proof of Theorem 2

We first consider the case when item (i) of Assumption 1 holds. Let ∆ > 0 and x ∈ R n such that σ(x) ≤ ∆, ε ∈ R nε and > 0 as in item (i) of Assumption 1. In view of (Granzotto et al., 2020a, Theorem 3) with γ = 1, it follows that

V d (x) ≤ V ∞ (x) ≤ V d (x) + α V • α -1 Y • I -α Y • α -1 Y d • α Y (σ(x)), (17)
for all d ∈ Z >0 and x ∈ R n , where

α Y := α V and α Y , α Y := α W . Hence -V d-1 (x) -α V • α -1 Y • I -α Y • α -1 Y d-1 • α Y (σ(x)) ≤ -V ∞ (x) and since V d (x) ≤ V ∞ (x), we derive that V d (x) -V d-1 (x) -α V • α -1 Y • I -α Y • α -1 Y d-1 • α Y (σ(x)) ≤ V ∞ (x) -V ∞ (x) = 0, (18) thus V d (x) -V d-1 (x) ≤ α V • α -1 Y • I -α Y • α -1 Y d-1 • α Y (σ(x)). ( 19
) When σ(x) = 0, V d (x) -V d-1 (x) ≤ α V (0) = 0. Hence, V d (x) -V d-1 (x) ≤ c stop (ε, x) for any d ∈ Z >0 since c stop (ε, x) ≥ 0. When σ(x) > 0, α V • α -1 Y • I -α Y • α -1 Y d-1 • α Y (σ(x)) is upper-bounded by α V • α -1 Y • I -α Y • α -1 Y d-1 • α Y (σ(∆)) as σ(x) ≤ ∆ since the considered function is non-decreasing. The term α V • α -1 Y • I -α Y • α -1 Y d-1 • α Y (σ(∆)
) can be made arbitrarily close to 0 by increasing d, according to (Granzotto et al., 2020a, Lemma 3) as γ = 1 and σ(x) ≤ ∆. In particular, we take d * sufficiently large such that α

V • α -1 Y • I -α Y • α -1 Y d * -1 • α Y (σ(∆))
≤ where comes from item (i) of Assumption 1 and is such that ≤ c stop (ε, x). Hence

V d (x) -V d-1 (x) ≤ α V • α -1 Y • I -α Y • α -1 Y d-1 • α Y (σ(x)) ≤ c stop (ε, x) for any d ≥ d * and
d * depends on ∆ a priori, but not on x. We have proved the desired result. Consider now the case when item (ii) of Assumption 1 holds with L < ∞. Let ∆ > 0 and x ∈ R n such that σ(x) ≤ ∆, ε ∈ R nε and > 0 as in item (ii) of Assumption 1 and is such that σ(x) ≤ c stop (ε, x). It follows from the inequalities of item (ii) of Assumption 1 that there exists some δ > 0 such that α (Granzotto et al., 2020a, proof of Corollary 1, equation (47)). Note that 1 -a W āV ∈ (0, 1), hence 1 -a W āV d-1 can be made as small as desired. Therefore, there exists d such that

V • α -1 Y • I -α Y • α -1 Y d • α Y (s) ≤ ā2 V a W 1 -a W āV d s for any s ∈ [0, δ], see
ā2 V a W 1 -a W āV d-1
≤ where . Thus, when σ(x) ∈ [0, δ] and in view of ( 19), it follows that

V d (x) -V d-1 (x) ≤ α V • α -1 Y • I -α Y • α -1 Y d • α Y (σ(x)) ≤ ā2 V a W 1 -a W āV d σ(x) ≤ σ(x) ≤ c stop (ε, x) for any d ≥ d. When σ(x) ∈ [δ, ∆],
we have c stop (ε, x) ≥ δ > 0, and we recover

d * such that V d (x) -V d-1 (x) ≤ c stop (ε, x) for σ(x) ∈ [δ, ∆
] by applying the steps made above, for when item (i) of Assumption 1 holds. Therefore, it follows that, for any

d ≥ min{ d, d * }, V d (x) -V d-1 (x) ≤ c stop (ε, x) holds for any σ(x) ∈ [0, ∆].
We have proved the desired result. Suppose now that item (ii) of Assumption 1 holds with

L = ∞. Let x ∈ R n , ε ∈ R nε and > 0 as in item (ii) of Assumption 1. It follows then that α V • α -1 Y • I -α Y • α -1 Y d • α Y (σ(x)) ≤ ā2 V a W 1 -a W āV d σ(x) for all x ∈ R n .
Hence, by invoking the same arguments as above when item (ii) of Assumption 1 holds, there exists

d > 0 such that V d (x) -V d-1 (x) ≤ c stop (ε, x) for any d ≥ d.
The proof is complete.

Proof of Theorem 3

Let x ∈ R n such that σ(x) ≤ ∆ and ε ∈ R nε , d ∈ Z ≥0 as in (7), which exists since Theorem 2 holds. Hence, optimal sequence [u * 0 , u * 1 , . . . , u * d ] := u * * * ε (x) and cost V ε (x) defined in (11) are well-defined. Since V ε is a finite-horizon optimal cost, V ε (x) ≤ V ∞ (x). On the other hand, consider the infinite-

horizon sequence u = [u * 0 , u * 1 , . . . u * d-1 , u * * * ∞ (φ(d, x, u * * * ε (x)| d ))], where u * * * ∞ (φ(d, x, u * * * ε (x)| d )) exists in view of item (i) of SA1. It follows from the optimality of V ∞ (x) that V ∞ (x) ≤ J ∞ (x, u), and from the definition of u that J ∞ (x, u) = V ε (x)+V ∞ (φ(d, x, u * * * ε (x)| d )), which is finite. By invoking item (i) of SA1, we derive V ∞ (x) ≤ V ε (x)+α V (σ(φ(d, x, u * * * ε (x)| d ))). In view of Lemma 1 and item (ii) of SA1, σ(φ(d, x, u * * * ε (x)| d )) ≤ α -1 W (c stop (ε, x)), thus V ∞ (x) ≤ V ε (x) + α V • α -1 W (c stop (ε, x)
) and the proof is complete.

Proof of Theorem 4

First, we prove the following result, which provides Lyapunov properties for system (13) that we use to derive the main stability result afterwards.

Theorem 7 Let Y := V ∞ , the following holds.

(i) For any x ∈ R n , α Y (σ(x)) ≤ Y(x) ≤ α Y (σ(x)), (20)
where α Y := α W , α Y := α V , with α W , α V from SA1.

Item (i) states that Y is positive definite and radially unbounded with respect to the set {x : σ(x) = 0}. Item (ii) of Theorem 7 shows that Y strictly decreases along the solutions to (13) up to a perturbative term α V • α -1 W (c stop (ε, x)), which can be made as small as desired by selecting |ε| close to 0 as α

V • α -1 W (c stop (ε, x)) ≤ α V • α -1 W (θ(|ε|, σ(x)
)), per Assumption 2. We are ready to prove Theorem 4. The proof heavily borrows from (Granzotto et al., 2019, Theorem2) and (Granzotto, 2019, Theorem 3.3), we nevertheless include it in this technical report for self-completeness. Let ∆, δ > 0. We select ε * > 0 such that

θ(ε * , α -1 Y ( ∆)) < α W • α -1 V ( 1 2 α Y ( δ)), (28)
where

α Y := α W • α -1 Y , ∆ := α Y (∆), δ := I -α Y 2 -1 • α Y (δ) and θ comes from Assumption 2. Note that I -α Y 2 -1
is indeed of class K ∞ as we assume without loss of generality that3

I -α Y ∈ K ∞ , hence I -α Y + α Y 2 ∈ K ∞
and so is its inverse. Inequality (30) can always be verified by taking ε * sufficiently small since θ(

•, α -1 Y ( ∆)) ∈ K, and α W • α -1 V ( 1 2 α Y ( δ)) > 0. It follows from θ(•, s) ∈ K for any s > 0 and θ(s, •) is non-decreasing for any s ≥ 0, that θ(|ε|, α -1 Y (s)) ≤ θ(ε * , α -1 Y ( ∆))
for any s ∈ [0, ∆] and |ε| < ε * . Furthermore, from Assumption 2 and item (i) of Theorem 7, we derive c stop (ε, x) ≤ θ(|ε|, α -1 Y (Y(x))). Thus, in view of (28),

c stop (ε, x) ≤ α W • α -1 V 1 2 α Y ( δ) (29)
for any x such that Y(x) ≤ ∆. On the other hand, we have α

W •α -1 V ( 1 2 α Y ( δ)) ≤ α W •α -1 V ( 1 2 α Y (s)) for any s ∈ [ δ, ∞). Hence, for any x ∈ R n such that Y(x) ∈ [ δ, ∆] and |ε| < ε * , α V • α -1 W (c stop (ε, x)) ≤ α Y ( δ) 2 ≤ α Y (Y(x)) 2 . ( 30
) Let x ∈ R n with σ(x) ≤ ∆ and v ∈ F * ε (x).
In view of (29) and items (i) and (ii) of Theorem 7,

Y(v) -Y(x) ≤ -α Y (Y(x)) + α V • α -1 W (c stop (ε, x)). ( 31
) Since σ(x) ≤ ∆, Y(x) ≤ α Y (σ(x)) ≤ α Y (∆) = ∆. Consider Y(x) ∈ [0, δ). Since c stop (ε, x) ≤ α W • α -1 V ( 1 2 α Y ( δ)
) holds for Y(x) ≤ ∆, it holds here. Furthermore, since I -α Y ∈ K ∞ holds without loss of generality, and in view of (31),

Y(v) ≤ Y(x) -α Y (Y(x)) + α V (θ(ε * , σ(x))) ≤ (I -α Y ) ( δ) + 1 2 α Y ( δ). (32)
Given the definition of δ,

Y(v) ≤ I - α Y 2 ( δ) = α Y (δ). ( 33
) When Y(x) ≥ δ, we derive from (30) that -α Y (Y(x)) + α V (c stop (ε, x)) ≤ -1 2 α Y (Y(x)). Thus, from (31), Y(v) -Y(x) ≤ -1 2 α Y (Y(x)). (34)
In view of ( 33) and ( 34), it follows for any k ∈ Z ≥0 that

Y(φ(k + 1, x)) ≤ max (I -1 2 α Y )(Y(x)), α Y (δ) , (35)
where φ(k, x) is a solution starting at x for system (13). Furthermore, when Y

(x) ≤ α Y (δ), Y(v) ≤ α Y (δ) follows. Indeed, if Y(x) ∈ [ δ, ∆], Y(v) ≤ Y(x) ≤ α Y (δ) from (34), and if Y(x) ∈ [0, δ), we deduce Y(v) ≤ α Y (δ) from (33). Hence the set {z ∈ R n : Y(z) ≤ α Y (δ)
} is forward invariant for system (13). By iterating (35), we obtain

Y(φ(k, x)) ≤ max β(Y(x), k), α Y (δ) , (36)
where

β(s, k) = I -1 2 α Y (k) (s) for any s ≥ 0, with β ∈ KL as lim k→∞ I -1 2 α Y (k) (s) = 0
for any s ≥ 0, since 4 I -1 2 α Y (s) < s for s > 0 and I -1 2 α Y (0) = 0.

Proof of Corollary 5

We follow the steps made in (Granzotto, 2019, Corollary 3.2). Let x ∈ R n . We select ε * < a 2 W a V as in Corollary 5 and let ε ∈ R nε such that |ε| ≤ ε * and v ∈ F * ε (x). In particular, from item (i) of Theorem 7, α W (σ(x) ≤ Y(x) ≤ α V (σ(x)), and since item (ii) of Assumption 1 holds with L = ∞ and a W s ≤ α W (s), α V (s) ≤ a V s with a W , a V > 0 for any s > 0, we obtain a W σ(x) ≤ Y (x) ≤ āV σ(x).

(38)

Similarly, in view of item (ii) of Theorem 7, Y(v) -Y(x) ≤ -α W (σ(x)) + α V • α -1 W (c stop (ε, x)), and since c stop (ε, x) ≤ |ε|σ(x) holds, we derive

Y(v) -Y(x) ≤ - a 2 W -|ε|ā V a W σ(x). (39)
Note that for |ε| ≤ ε * ,

a 2 W -|ε|ā V a W > 0.
Hence, in view of ( 39) and (38),

Y(v) -Y(x) ≤ - a 2 W -|ε|ā V āV a W Y(x) (40)
holds for any σ(x) ≥ 0. Let x ∈ R n and denote φ(k, x) be a corresponding solution to (13) at time k ∈ Z ≥0 , it holds that Y(φ(k, x)) ≤ 1 -

a 2 W -|ε|ā V āV a W k Y(x).
In view of (38), it follows from Y(φ(k, x)) ≤ 1 -

a 2 W -|ε|ā V āV a W k Y(x) that a W σ(φ(k, x)) ≤ 1 - a 2 W -|ε|ā V āV a W k āV σ(x) hence σ(φ(k, x)) ≤ āV a W σ(x) 1 - a 2 W -|ε|ā V āV a W k
and the proof is concluded.

4. See (Granzotto, 2019, Lemma B.1) 7.6. Proof of Theorem 6

Let x ∈ R n , ε ∈ R nε such that |ε| < ε * where ε * is selected as in Corollary 5, φ(k + 1, x) ∈ F * ε (φ(k, x)) for any k ∈ Z ≥0 where φ is a solution to (13) initialized at x. Let u r k ∈ U * ε (φ(k, x)) such that φ(k + 1, x) = f (φ(k, x), u r k ), and note, since inputs from (13) are the first input of u * * * ε applied in a receding horizon fashion, u r k = u * * * ε (φ(k, x))| 0 and therefore (φ(k, x), u r k ) = (φ(k, x), u * * * ε (φ(k, x))| 0 ) = * d (0, φ(k, x)) by definition of (10). Consider then

V run ε (x) = ∞ k=0 * d (0, φ(k, x)), (41)
Note that indeed V run ε (x) ∈ V run ε (x). It follows from the proof of Theorem 7, in particular ( 27), that

V ∞ (φ(k + 1, x)) ≤ V ∞ (φ(k, x)) - * d (0, φ(k, x)) + α V • α -1 W (c stop (ε, φ(k, x))), (42)
from which we deduce, for any N ≥ 0,

N k=0 * d (0, φ(k, x)) ≤ V ∞ (φ(0, x)) -V ∞ (φ(1, x)) + α V • α -1 W (c stop (ε, φ(0, x))) + V ∞ (φ(1, x)) -V ∞ (φ(2, x)) + α V • α -1 W (c stop (ε, φ(1, x))) + . . . + V ∞ (φ(N, x)) -V ∞ (φ(N + 1, x)) + α V • α -1 W (c stop (ε, φ(N, x))) ≤ V ∞ (φ(0, x)) + N k=0 α V • α -1 W (c stop (ε, φ(k, x))), (43)
Hence, when N → ∞,

V run ε (x) ≤ V ε (φ(0, x)) + ∞ k=0 α V • α -1 W (c stop (ε, φ(k, x))). (44)
All that remains is to compute a bound on ∞ k=0 α V • α -1 W (c stop (ε, φ(k, x))), which is possible by recalling that σ(φ(k, x)) ≤ āV a W σ(x) 1 -

α V • α -1 W (c stop (ε, φ(k, x))) ≤ |ε| ā2 V a 2 W σ(x) ∞ k=0 1 - a 2 W -|ε|ā V āV a W k
, which provides (15) as ∞ k=0 1 -

a 2 W -|ε|ā V āV a W k = āV a W a 2
W -ā V |ε| . The lower bound V ∞ (x) ≤ V run ε (x) follows from the optimality of V ∞ (x). Since (44) holds for an arbitrary solution of (13), φ(k + 1, x) = f (φ(k, x), u r k ) for any k ∈ Z ≥0 , the resulting bound holds for any V run ε (x) ∈ V run ε (x).

c

  stop (ε, x) : |ε| d = 6 d = 7 d = 8 d = 8 d = 8 d = 8 d = 9 |ε|σ(x) d = 0 d = 1 d = 3 d = 4 d = 5 d = 6 d = 7 |ε| min{σ(x), 1} d = 6 d = 7 d = 8 d = 8 d = 8 d = 8 d = 9

  Finally, invoking α Y (σ(x)) ≤ Y(x) ≤ α Y (σ(x)), we deduce σ(φ(k, x)) ≤ max α -1 Y β(α Y (σ(x)), k) , δ .(37)Thus Theorem 4 holds withβ(s, k) = α -1 Y β(α Y (s), k)for any s ≥ 0 and k ∈ Z ≥0 .

  stop (ε, φ(k, x))) ≤ āV a W |ε|σ(φ(k, x))as the conditions of Corollary 5 are assumed to hold. Specifically, ∞ k=0

  an upper-bound on the value of stage cost * d (d, x). By item (ii) of SA1, this implies that we also have an upper-bound for d-horizon state measure σ(φ(d, x, u * * * d

  ).

						d
		0	1	3	4	5	6	7	8	9
	V run d (x)	77313 45497 19931 19965 19802 20090 20359 20261 20261
	σ(φ(40, x)) 1982	1138	2.56	2.84	1.71	2.25	1.84	1.62	1.62

The assumption is stated globally, for any x ∈ R n and u ∈ U(x). We leave for future work the case where the assumption holds on compact sets.

The case where V-1 = 0 will be investigated in further work.

See[START_REF] Granzotto | Near-optimal control of discrete-time nonlinear systems with stability guarantees[END_REF] for details.

where α Y = α W , with α W and α V from SA1, and c stop comes from (7).

Proof. Let ε ∈ R nε , x ∈ R n and v ∈ F * ε (x), which is well-defined in view of Theorem 2. There exists

is an optimal input sequence for system (1) and cost (8) with horizon d, hence

] and φ denotes the solution of system (1). The sequence û consists of the first d elements of u * ε (x) after u * 0 , followed by an optimal input sequence of infinite length at state φ(d, x, u * * * ε (x)| d ), which exists according to item (i) of SA1. Sequence ū minimizes

From Bellman optimality principle, we have

Moreover, by item (i) of SA1,

Consequently, in view of ( 22), ( 23) and ( 24),

By invoking item (ii) of SA1, we derive


Laurent Cleret De Langavant
email: laurent.cleret@gmail.com

Charlotte Jacquemot
email: charlotte.jacquemot@gmail.com

Anne-Catherine Bachoud-Lévi

Emmanuel Dupoux
email: emmanuel.dupoux@gmail.com

Second person social cognition cannot be restricted to dyadic interactions between two persons (the I and the you ). Many instances of social communication are triadic, and involve a third person (the him/her/it ), which is the object of the interaction. We discuss neuropsychological and brain imaging data showing that triadic interactions involve dedicated brain networks distinct from those of dyadic interactions.

M ain Text

Schilbach and collaborators defend the idea that social cognition research would benefit from bridge the gap between the solipsist view of first person perspective, and third person social psychology. We agree with this idea, but we point out that second person studies cannot be restricted to dyadic relationships between two persons. Indeed, communicative or collaborative interactions always involve a third component: an object, a person, an event or even the goal of the interaction itself. Therefore, many social interactions are intrinsically triadic ('I' talk to 'you' about 'him/her/it').

Dyadic interactions are present very early in human infants as can be seen in the emotional domain (emotional contagion, attachment, etc; see [START_REF] Hobson | Joint Attention or Joint Engagement? Insights from Autism[END_REF]) and in the communicative domain (turn taking, see [START_REF] Kugiumutzakis | Neonatal imitation in the intersubjective companion space[END_REF]. They are also present in social animals in a variety of behaviors (feeding, grooming, courting, dominance/submission displays, etc. [START_REF] De Waal | A century of getting to know the chimpanzee[END_REF]). Yet, they are distinct from triadic interactions (see Figure 1), which emerge in humans only at the end of the first year and are considered to play a pivotal role in the development of human social cognition [START_REF] Baron-Cohen | The Empathizing System: a revision of the 1994 model of the Mindreading System[END_REF][START_REF] Charman | Why is joint attention a pivotal skill in autism?[END_REF]).

Impairment or delay in the acquisition of these triadic interactions has been observed in patients with autism whose social and communicative skills are severely affected [START_REF] Baron-Cohen | Perceptual role taking and protodeclarative pointing in autism[END_REF]. In non-human primates only some limited abilities for triadic interactions are observed, for example instrumental pointing, in which the addressee is used to get an object of interest [START_REF] Gómez | Joint Attention and the Notion of Subject: Insights from Apes, Normal Children, and Children with Autism[END_REF], or limited cooperation in hunting (de Waal & Malini 2010), but not communicative pointing in which the addressee is invited to share the perceptual experience about an object [START_REF] Tomasello | The emergence of social cognition in three young chimpanzees[END_REF], or fully fledged cooperation [START_REF] Rekers | Children, but not chimpanzees, prefer to collaborate[END_REF]. Neuropsychological studies enable the disentanglement of triadic from dyadic interactions.

Heterotopagnosia is a puzzling acquired deficit which only arises in triadic situations where the target object is a human person: patients cannot point at although they can grasp or touch them. They can also point correctly at videos of humans, at pieces of clothing and at their own body, thus indicating a specific difficulty for communicative pointing directed to the physical body of another human (Cleret de [START_REF] Cleret De Langavant | Heterotopagnosia: When I point at parts of your body[END_REF][START_REF] Degos | Selective inability to point to extrapersonal targets after left posterior parietal lesion: an objectivisation disorder?[END_REF][START_REF] Felician | Pointing to body parts: a double dissociation study[END_REF]. Interestingly, most of the errors consist of pointing at their own body parts, which they rationalize by stating that the body parts of the target individual occupy the same space as their own body parts.

Heterotopagnosia cannot be explained by a simple impairment of a human body representation or by other current theories in social cognition [START_REF] Cleret De Langavant | Heterotopagnosia: When I point at parts of your body[END_REF], but this syndrome reveals a crucial difference between dyadic and triadic interactions. d the target of the gesture. In contrast pointing involves the triadic relationship of communication where 'I' show to 'you' the object 'it' or the person 'him/her'. Comparing the kinematics of pointing at objects in both communicative and non-communicative situations in healthy participants, we showed a spatial reshaping of the pointing gesture according to the communicative interaction with a second person and to his/her position relative to the first person. This suggests that in communicative pointing, we use a "heterocentric" reference frame encoding the body and perspective of the second person who is addressed ('I' represent how 'you' represent 'this'). Such a reference is not used when pointing is dyadic or in grasping or touching. PET-scan imaging shows that this reference frame involves the right posterior superior temporal sulcus region and the right medial prefrontal cortex (Cleret de [START_REF] Cleret De Langavant | Behavioral and neural correlates of communication via pointing[END_REF].

In addition, because performance in heterotopagnosia differs according to the object of the pointing (a real human or a figure of human), we compared pointing at a living human's body, ipants. Reaction times for pointing at was slower than pointing at artifacts. This demonstrated the specificity of the body of other persons: only a real person -parietal sulcus region (Cleret de Langavant et al. in press). Presumably, damage in this area explains why patients with het neuroscience should assess communicative/collaborative triadic interactions, as they offer a richer situation, including the switching of perspectives or frame of references between 'you' and 'him/her' perspectives. In a triadic interaction, the roles of the second and third persons are constantly dynamically redefined. This requirement should be taken into account in experimental designs using computerized avatars as opposed to real life participants.

A cknowledgment

The authors thank Laura Robotham for editing the English of this commentary.

Figure 1 :

 1 Figure 1: Four distinct perspectives in social cognition: a. first person perspective, b. third


Dalel El-Marrouki

Sabrina Touchet
email: sabrina.touchet@univ-lorraine.fr

Abderrahmen Abdelli

Hédi M'rabet

Mohamed Lotfi Efrit

Philippe C Gros
email: philippe.gros@univ-lorraine.fr.

Tuneable access to indole, indolone and cinnoline derivatives from a common 1,4-diketone Michael acceptor

Keywords: N-heterocycle, 1,4-diketone, indole, indolone, cinnoline

A convergent strategy is reported for the construction of nitrogen-containing heterocycles from common substrates: 1,4-diketones and primary amines. Indeed, by just varying substrates, substituents or heating mode it is possible to selectively synthesize indole, indolone (1,5,6,7-tetradihydroindol-4-one) or cinnoline (5,6,7,8-tetrahydrocinnoline) derivatives in moderate to excellent yields.

Introduction

Nitrogen heterocycles are widespread in plenty of molecules of interest, either in materials science, optics, electronics or biology [1][2][3][4]. They are also very useful building blocks to create more sophisticated organic molecules. Therefore the search for efficient methods for the synthesis of nitrogen-containing heterocycles is crucial to both organic and medicinal chemists. Among these, indole, indolone (1,5,6,7-tetrahydroindol-4-one) and cinnoline (5,6,7,8-tetrahydrocinnoline) derivatives are an important class of functionalized compounds having biological and medicinal activities of interest (Figure 1) [5][6][7][8].

Figure 1:

Examples of bioactive nitrogen-containing heterocycles (indole [9], indolone [10] and cinnoline [11] derivatives). Indeed, indole ring-containing compounds have various biological and pharmacological activities and are part of many marketed drugs used as anticancer, antiemetics, antihypertensives, antidepressants, anti-inflammatory, or anti-HIV, among others [9]. In contrast, concerning indolone and cinnoline derivatives, there are very few marketed drugs but many molecules are under investigations for their activities as antibacterial, antifungal, anticancer, anti-inflammatory agents or even on the central nervous system [7,12,13].

Several routes have been reported to access these key compounds, the most developed being for the indole [14] derivatives with the Fischer indole synthesis involving sigmatropic rearrangements [15][16][17][18], nucleophilic and electrophilic cyclization [19][20][21][22][23][24][25] reductive and oxidative cyclization [26,27] and by using transition-metal catalysis [28][29][30][31][32][33][34][35][36][37]. There are fewer ways to access indolone derivatives mainly based on the use of di- [12,38,39] or tri-ketones [10,13] and enaminones [40][41][42][43] as starting materials. For the synthesis of cinnoline derivatives, aryldiazenes and aryltriazenes are substrates of choice for transition-metal catalyzed (Rh, Pd, Cu) cross-coupling reactions followed by intramolecular cyclizations [44][45][46][47]. Moreover arylhydrazones and arylhydrazines/hydrazines car be used as well respectively as partners in 4+2 cyclization reaction [48][49][50][51] or by reacting mostly with carbonyl derivatives [52][53][54][55].

From the state-of-the-art, a strategy that promotes the synthesis of indole, indolone or cinnoline derivatives from the same starting material is not yet available. To reach this goal, the Michael reaction between 1,4-diketones and primary amines seems particularly attractive because of its straightforward, metal-free and under air character. Herein, we report our investigations on this reaction and we have shown that it can be selectively directed towards the synthesis of indole, indolone or cinnoline derivatives by just changing substrates, substituents or heating mode (Schema 1).

Results and Discussion

The synthesis of the target compounds required the prior preparation of a panel of variously substituted 1,4-diketones 5. 1,4-Diketones 5 have been prepared either by a Nef reaction [56] from the corresponding nitroenone 3 or a Wittig reaction [START_REF] Mawaziny | Sulfur[END_REF] from 1,2-cyclohexanedione and the corresponding ylide 4 (Scheme 2).

Scheme 2: Synthesis of 1,4-diketones 5a-k via Nef reaction or Wittig reaction

The nitrenones 3a-d were obtained in three steps from the appropriate commercially available cyclohexenones (Scheme 2). First, a Baylis-Hillman reaction between cyclohexanone and formaldehyde led to the formation of the corresponding Baylis-Hillman alcohols in good yield [58] followed by a DMAP-catalyzed acetylation of these alcohols gave the corresponding acetates [59]. Nitrenones 3a-d were finally obtained in acceptable yield by reacting the acetates derivatives with the appropriate nitroalkanes [60]. The next step was the transformation of the nitro group of 3a-d via a Nef reaction using sodium ethoxide in ethanol, followed by hydrolysis with concentrated sulfuric acid at low temperature [56], leading to the corresponding new γ-diketones 5a-d in 61-87 % yields (Scheme 2).

Despite the efficiency of the Nef reaction, the diversity at the R 1 position via this synthesis route remains limited in terms of chemical diversity as it dependent on the availability of the corresponding nitro derivative. It was thus decided to move to the Wittig reaction [START_REF] Mawaziny | Sulfur[END_REF] offering a much more straightforward and efficient route to a panel of new diketones 5e-k from 1,2-cyclohexanedione and the corresponding Wittig ylides 4a-g (readily accessible from the corresponding halogenated derivatives) (Scheme 2). Indeed, the Wittig reaction leads exclusively to the isomerized product 5.

With 1,4-diketones 5 in hand, we first investigated the synthesis of indole and indolone derivatives. The reaction mechanism shown in Scheme 3 involves the formation of an imine upon reaction of the primary amine with the most reactive carbonyl moiety (non-conjugated and exocyclic carbonyl function). Then, depending on the reaction conditions, the imine can react following a 1,2 or 1,4 addition process leading respectively to an indole 6 (after dehydration and aromatization) or an indolone 7. The reaction was first investigated by mixing diketone 5b as the Michael acceptor and benzylamine under various conditions (Table 1). Scheme 3: Mechanism of formation of indole and indolone derivatives. We first investigated the reactivity in the presence of a set of catalysts with different acidities (Entries 1-5 -Table 1). Among them only acetic acid afforded reaction products while the others only produced complex mixtures of degradation products. In the conditions of entry 5, indole 6b was isolated in 47 % and indolone 7b was also formed concomitantly in 10% yield.

Entries 6-11 were next performed with the aim to favour the 1,4-addition process and thus the formation of indolone 7b. Removing the acid catalyst from the reaction mixture (Entry 6) did not affect the 6b:7b ratio obtained in entry 5. While in aprotic solvents, other than toluene (Entries 7-8), the reaction produced complex mixtures of degradation products, using alcohols had a notable impact on the reaction contents. Indeed, going from ethanol to propanol and thus increasing the refluxing temperature led to indolone 7b as the main product, the best yield being obtained in butanol (43%, Entry 11) with however the formation of 6b in 10% yield. Switching to a microwave irradiation formed exclusively 7b in 60% yield after 3h (Entry 13). Note that to check the effect of a shorter reaction time on the reaction outcome, we have reduced the time to 3h also under the classical refluxing conditions of entry 11 and obtained a partial conversion of the starting diketone 5b. Despite the side formation of indolone 7b in entry 5, these conditions were applied to several amines producing the corresponding substituted indoles 6a and 6c-f in 41-52% yields (Scheme 4). The yield of indolones 7a and 7c-f was found almost constant (10-14%) whatever the amine involved. It is worthy of note that the two compounds were easily separated using usual chromatographic techniques.

Scheme 4: Synthesis of indoles 6a-f and corresponding side product indolones 7a-f.

The reaction was also applied to a diamine (Scheme 5). When 1,3-diaminopropane was used the bis-indole 6g was isolated in 46% yield. Interestingly, the mixed indolone/indole compound 9 was also obtained as the side product. However no traces of the bis-indolone derivative were detected.

Scheme 5: Reaction of 5b with a diamine.

We then succeeded in directing the reaction exclusively towards the indole formation by reacting the diketone with substrates combining a primary and a tertiary amine separated by several spacer arms (Scheme 6).

conditions, the expected cinnoline 8a was obtained in low yield of 20 % that could be increased up to 40% upon refluxing the mixture (entry 2 -Table 2). Switching to toluene (entry 3 -Table 2) did not improve the reaction outcome. However, the addition of a catalytic amount of acetic acid in refluxing ethanol while shortening the reaction time, dramatically increased the yield of 8a up to 82% (entry 4 -Table 2). These optimized conditions were then applied to the previously synthesized 1,4-diketones 5ak (Scheme 9). As a general observation, the reaction was found efficient producing the expected cinnoline derivatives 8a-k in good to excellent yields (77 -92 %) and tolerate alkyl, aromatic and heteroaromatic group at R 1 position.

Conclusion

In summary, we have successfully developed a straightforward and metal-free strategy for the synthesis of nitrogen-containing heterocycles moieties of biological interested; indole 6, indolone 7 and cinnoline 8 derivatives; starting from common substrates: 1,4-diketones 5 and primary amines. The protocols developed here use mild conditions, are functional-group tolerant, transition metal-free, proceeds in moderate to good yields and therefore can be easily used in medicinal chemistry projects for rapid access to a wide range of variously substituted compounds for structure-activity relationship studies. The biological activity of the molecules is currently being studied.

Scheme 1 :

 1 Scheme 1: General strategy to access indole, indolone and cinnoline derivatives from 1,4-

Scheme 9 : 7 .Scheme 10 :

 9710 Scheme 9: Synthesis of cinnoline derivatives 8a-k.

Table 1 :

 1 Effects of solvent and heating mode on the 6b:7b ratio.

	Entry a	Catalyst	Solvent	Time	6b (%) b	7b (%) b	6b:7b
	1	TfOH (3%)	Toluene	16h	-	-	-
	2	AgOTf (3%)	Toluene	16h	-	-	-
	3	TFA (3%)	Toluene	16h	-	-	-
	4	pTsOH (3%)	Toluene	16h	-	-	-
	5	AcOH (3%)	Toluene	16h	47	10	83:17
	6		Toluene	16h	33	8	80:20
	7		CH2Cl2	16h	-	-	-
	8		THF	16h	-	-	-
	9		Ethanol	16h	13	16	45:55
	10		Propanol	16h	6	31	16:84
	11		Butanol	16h	10	43	19:81
	12		Pentanol	16h	7	28	20:80
	13 c		Butanol	MWI 3h	-	60	0:100
	a reaction conditions: 5b (0.54 mmol), primary amine (0.81 mmol), 4 mL of solvent and
	catalyst (0.02 mmol) unless otherwise specified (in column 2 the catalyst percentage it is
	always reported and it exactly corresponds to 0.02 mmol); b isolated yield; c 13 mL of butanol,
	MWI 100°C.

Table 2

 2 Optimization of the reaction conditions for synthesis of cinnolines 8.

	Entry a	Catalyst	Solvent	T°C	time (h)	8a (%) b
	1	-	EtOH	r.t.	48	20
	2	-	EtOH	reflux	48	40
	3	-	Toluene	reflux	48	35
	4	AcOH (3%)	EtOH	reflux	16	82
	a reaction conditions: 5a (1 mmol), hydrazine monohydrate (1.5 mmol), solvent (6 mL) and a
	catalyst (0.03 mmol) unless otherwise specified (in column 2 the reported catalyst percentage
	exactly corresponds to 0.03 mmol).

b isolated yield.

Acknowledgements

The authors would like to thank François Dupire (UMR 7053 -L2CM) and Fabien Lachaud (UMR 7053 -L2CM) for the HRMS and GC-MS experiments and related discussions. They thank also the Université de Lorraine and the CNRS for their support. The University of Tunis El Manar and the Tunisian Ministry of Higher Education and Scientific Research are also acknowledged for a grant to D.M.

Scheme 6: Synthesis of indoles 6h-l.

Under these conditions, the functional indoles 6h-l were obtained exclusively in 45-55% yield. We assumed that the tertiary amine would interact with the protonated intermediate, thus promoting the 1,2-addition (Scheme 7). We next examined the preparation of a set of indolones under the microwave conditions determined in entry 13 of Table 1. These conditions were applied to several amines producing the exclusively the corresponding substituted indolones 7d and 7g-k in 48-56% yields (Scheme 8). Scheme 8: Synthesis of indolone derivatives 7b, 7d and 7g-k.

Here again, the amount of indolone was found almost constant whatever the amine involved, suggesting that the reaction is not dependant of the nature of the amine. It is worth notice that, in case of a substrate combining a primary and a tertiary amine separated by a spacer arm only the indolone derivative is obtained in those conditions as well (compound 7i -Scheme 8).

Based on these results, we found it important to check that indole 6b resulted from a 1,2addition and not from a degradation of indolone 7b. For this purpose, indolone 7b was refluxed overnight with acetic acid in toluene under the conditions producing mainly the indole (Table 1, entry 5). The indolone 7b was found unchanged, with no trace of indole 6b detected (see Supporting Information File 1 -I), indicating that the indole was formed intramolecularly by 1,2-addition of the intermediately formed imine to the Michael acceptor (Scheme 3).

We then investigated the synthesis of cinnoline derivatives by mixing diketone 5a and hydrazine monohydrate under various conditions (Table 2). We first investigated the reactivity in ethanol as protic solvent, at room temperature (entry 1 -Table 2). Under these

Supporting Information

Experimental procedures, characterization data and copies of spectra of all compounds. Supporting Information File 1: File Name: Supporting Information BJOC File Format: pdf Title: Experimental data