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

HAL
open science

# Robust stability and near-optimality for policy iteration: for want of recursive feasibility, all is not lost

Mathieu Granzotto, Olivier Lindamulage De Silva, Romain Postoyan, Dragan

Nešić, Zhong-Ping Jiang

► To cite this version:

Mathieu Granzotto, Olivier Lindamulage De Silva, Romain Postoyan, Dragan Nešić, Zhong-Ping Jiang. Robust stability and near-optimality for policy iteration: for want of recursive feasibility, all is not lost. IEEE Transactions on Automatic Control, In press, 10.1109/TAC.2024.3402941. hal-04581472

HAL Id: hal-04581472

https://hal.science/hal-04581472

Submitted on 21 May 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Robust stability and near-optimality for policy iteration: for want of recursive feasibility, all is not lost

Mathieu Granzotto, Olivier Lindamulage De Silva, Romain Postoyan, Dragan

Nešić, Zhong-Ping Jiang

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

► To cite this version:

Mathieu Granzotto, Olivier Lindamulage De Silva, Romain Postoyan, Dragan Nešić, Zhong-Ping Jiang. Robust stability and near-optimality for policy iteration: for want of recursive feasibility, all is not lost. IEEE Transactions on Automatic Control, 2024, 69 (12), pp.8247-8262. 10.1109/TAC.2024.3402941. hal-04581472

HAL Id: hal-04581472

https://hal.science/hal-04581472v1

Submitted on 21 May 2024

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

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

<figure><img src="image_2.png" /></figure>
# Robust stability and near-optimality for policy iteration: for want of recursive feasibility, all is not lost

Mathieu Granzotto, Olivier Lindamulage De Silva, Romain Postoyan, Dragan Nešić, and Zhong-Ping Jiang

**Abstract**— We consider deterministic nonlinear discrete-time systems whose inputs are generated by PI for undiscounted cost functions. We first assume that PI is recursively feasible, in the sense that the optimization problems solved at each iteration admit a solution. In this case, we provide novel conditions to establish recursive robust stability properties for a general attractor, meaning that the policies generated at each iteration ensure a robust KL-stability property with respect to a general state measure. We then derive novel explicit bounds on the mismatch between the (suboptimal) value function returned by PI at each iteration and the optimal one. However, we show by a counter-example that PI may fail to be recursively feasible, disallowing the mentioned stability and near-optimality guarantees. We therefore also present a modification of PI so that recursive feasibility is guaranteed a priori under mild conditions. This modified algorithm, called $PI^+$, is shown to preserve the recursive robust stability when the attractor is compact. Additionally, $PI^+$ enjoys the same near-optimality properties as its PI counterpart under the same assumptions.

## I. INTRODUCTION

Policy iteration (PI) is an optimization algorithm that forms one of the pillars of dynamic programming [2]. PI iteratively generates control laws, also called policies, that converge to an optimal control law for general dynamical systems and cost functions under mild conditions, see, e.g., [2,5,15,17]. Also, PI may exhibit the attractive feature of converging faster to the optimal value function than its counterpart value iteration (VI) [15] at the price of more computations. For these reasons, PI attracts a lot of attention both in terms of theoretical investigations see, e.g., [3,5,7,15,23,24], and practical applications e.g., [14,22,29,30]. Nevertheless, several fundamental questions remain largely open regarding the properties of PI in a control context: (i) its recursive feasibility; (ii) general conditions for recursive robust stability when the attractor is

not necessarily a single point but a more general set; (iii) near-optimality guarantees, in particular when the cost function is not discounted. We explain each of these challenges next.

It is essential that PI is recursively feasible in the sense that the optimization problem admits a solution at each iteration. If this is not the case, the algorithm eventually stops generating policies thereby failing its purpose to provide policies, whose cost asymptotically converge to the optimal value function. This, by extension, raises questions on the guarantees of practical implementations of PI. Surprisingly, we have not been able to find general conditions for the recursive feasibility of PI in the literature when dealing with deterministic nonlinear discrete-time systems with general cost functions, whose state and inputs evolves on a Euclidean space. The only results we came across concentrate on special cases like when the input set is finite [3] or the system is linear and the cost is quadratic [2]. The dominant approach in the literature for nonlinear discrete-time systems on Euclidean spaces is thus to assume that the algorithm is recursively feasible, see, e.g., [15,23], or to rely on conditions that are hard to verify a priori in general as they employ feasibility tests at each iteration [3]. Model predictive control literature recognised a long time ago the importance of recursive feasibility. Hence we believe that the recursive feasibility of PI is a property of major importance in view of the burgeoning literature on dynamic programming and reinforcement learning where PI plays a major role [4,6].

A second challenge for PI is related to its application in a control context. In many applications, the closed-loop system must exhibit stability guarantees as: (i) it provides analytical guarantees on the behavior of the controlled system solutions as time evolves; (ii) it endows the system with robustness properties and is thus associated to safety considerations, see, e.g., [1]. Available results on the stability of systems controlled by PI concentrate on the case where the attractor is a single point, as in, e.g., [5,7,23,24]. They exclude set stability, which is inevitable for instance in presence of clock or toggle variables [9, Examples 3.1-3.2], and more generally when the desired operating behaviour of the closed-loop system is given by a set and not a point. Moreover, the commonly used assumptions imposed on the plant model and the stage cost are also subject to some conservatism, like requiring the stage cost to satisfy positive definiteness properties. In addition, it is essential to ensure that these stability properties are robust, which is not automatically guaranteed, as pointed out in [12,21], and this matter is often eluded in the literature at the exception of the recent work in [25] in the linear quadratic case. There is therefore a need for general conditions allowing to conclude robust set stability properties for systems controlled by PI. We

Mathieu Granzotto and Dragan Nešić are with the Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, VIC 3010, Australia (e-mail: {mgranzotto, dnesic}@unimelb.edu.au). Their work was supported by the Australian Research Council under the Discovery Project DP210102600.

Olivier Lindamulage De Silva and Romain Postoyan are with the Université de Lorraine, CNRS, CRAN, F-54000 Nancy, France (e-mails: {name.surname}@univ-lorraine.fr). Work supported by the ANR under grant OLYMPIA, number ANR-23-CE48-0006.

Zhong-Ping Jiang is with the Department of Electrical and Computer Engineering, New York University, 370 Jay Street, Brooklyn, NY 11201, USA. email: zjiang@nyu.edu. His work was supported partly by the National Science Foundation under Grant ECCS-2210320.

This work was supported by the France-Australia collaboration project IRP-ARS CNRS.
# Robust stability and near-optimality for policy iteration: for want of recursive feasibility, all is not lost

Mathieu Granzotto, Olivier Lindamulage De Silva, Romain Postoyan, Dragan Nešić, and Zhong-Ping Jiang

**Abstract**— We consider deterministic nonlinear discrete-time systems whose inputs are generated by PI for undiscounted cost functions. We first assume that PI is recursively feasible, in the sense that the optimization problems solved at each iteration admit a solution. In this case, we provide novel conditions to establish recursive robust stability properties for a general attractor, meaning that the policies generated at each iteration ensure a robust KL-stability property with respect to a general state measure. We then derive novel explicit bounds on the mismatch between the (suboptimal) value function returned by PI at each iteration and the optimal one. However, we show by a counter-example that PI may fail to be recursively feasible, disallowing the mentioned stability and near-optimality guarantees. We therefore also present a modification of PI so that recursive feasibility is guaranteed a priori under mild conditions. This modified algorithm, called $PI^+$, is shown to preserve the recursive robust stability when the attractor is compact. Additionally, $PI^+$ enjoys the same near-optimality properties as its PI counterpart under the same assumptions.

## I. INTRODUCTION

Policy iteration (PI) is an optimization algorithm that forms one of the pillars of dynamic programming [2]. PI iteratively generates control laws, also called policies, that converge to an optimal control law for general dynamical systems and cost functions under mild conditions, see, e.g., [2,5,15,17]. Also, PI may exhibit the attractive feature of converging faster to the optimal value function than its counterpart value iteration (VI) [15] at the price of more computations. For these reasons, PI attracts a lot of attention both in terms of theoretical investigations see, e.g., [3,5,7,15,23,24], and practical applications e.g., [14,22,29,30]. Nevertheless, several fundamental questions remain largely open regarding the properties of PI in a control context: (i) its recursive feasibility; (ii) general conditions for recursive robust stability when the attractor is

not necessarily a single point but a more general set; (iii) near-optimality guarantees, in particular when the cost function is not discounted. We explain each of these challenges next.

It is essential that PI is recursively feasible in the sense that the optimization problem admits a solution at each iteration. If this is not the case, the algorithm eventually stops generating policies thereby failing its purpose to provide policies, whose cost asymptotically converge to the optimal value function. This, by extension, raises questions on the guarantees of practical implementations of PI. Surprisingly, we have not been able to find general conditions for the recursive feasibility of PI in the literature when dealing with deterministic nonlinear discrete-time systems with general cost functions, whose state and inputs evolves on a Euclidean space. The only results we came across concentrate on special cases like when the input set is finite [3] or the system is linear and the cost is quadratic [2]. The dominant approach in the literature for nonlinear discrete-time systems on Euclidean spaces is thus to assume that the algorithm is recursively feasible, see, e.g., [15,23], or to rely on conditions that are hard to verify a priori in general as they employ feasibility tests at each iteration [3]. Model predictive control literature recognised a long time ago the importance of recursive feasibility. Hence we believe that the recursive feasibility of PI is a property of major importance in view of the burgeoning literature on dynamic programming and reinforcement learning where PI plays a major role [4,6].

A second challenge for PI is related to its application in a control context. In many applications, the closed-loop system must exhibit stability guarantees as: (i) it provides analytical guarantees on the behavior of the controlled system solutions as time evolves; (ii) it endows the system with robustness properties and is thus associated to safety considerations, see, e.g., [1]. Available results on the stability of systems controlled by PI concentrate on the case where the attractor is a single point, as in, e.g., [5,7,23,24]. They exclude set stability, which is inevitable for instance in presence of clock or toggle variables [9, Examples 3.1-3.2], and more generally when the desired operating behaviour of the closed-loop system is given by a set and not a point. Moreover, the commonly used assumptions imposed on the plant model and the stage cost are also subject to some conservatism, like requiring the stage cost to satisfy positive definiteness properties. In addition, it is essential to ensure that these stability properties are robust, which is not automatically guaranteed, as pointed out in [12,21], and this matter is often eluded in the literature at the exception of the recent work in [25] in the linear quadratic case. There is therefore a need for general conditions allowing to conclude robust set stability properties for systems controlled by PI. We

Mathieu Granzotto and Dragan Nešić are with the Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, VIC 3010, Australia (e-mail: {mgranzotto, dnesic}@unimelb.edu.au). Their work was supported by the Australian Research Council under the Discovery Project DP210102600.

Olivier Lindamulage De Silva and Romain Postoyan are with the Université de Lorraine, CNRS, CRAN, F-54000 Nancy, France (e-mails: {name.surname}@univ-lorraine.fr). Work supported by the ANR under grant OLYMPIA, number ANR-23-CE48-0006.

Zhong-Ping Jiang is with the Department of Electrical and Computer Engineering, New York University, 370 Jay Street, Brooklyn, NY 11201, USA. email: zjiang@nyu.edu. His work was supported partly by the National Science Foundation under Grant ECCS-2210320.

This work was supported by the France-Australia collaboration project IRP-ARS CNRS.
further would like these stability properties to be preserved at each iteration; that is, we want to ensure recursive robust stability.

Finally, it is important to understand when and how the sequence of value functions generated by PI at each iteration converges to the optimal value function; we talk of near-optimality guarantees. The literature stands in two ways on this issue. On the one hand, the value functions are known to converge monotonically and point-wisely to the optimal value function under mild conditions on the model and the cost [5,15]; uniform convergence properties are only ensured, as far as we know, for discounted costs functions [2]. On the other hand, it is important to be able to evaluate the mismatch between the returned value function at each iteration and the optimal one. These computable or explicit bounds on the mismatch of generated value functions are vital to decide when to stop iterating the algorithm. Existing results concentrate on discounted costs [2], which are not always natural in control applications. In the discounted setting, the provided near-optimality bounds explode when the discount factor $\gamma \in (0, 1)$ converges to one [2], while to ensure stability, in opposition, $\gamma$ should be close enough to one in view of [11,26]. Hence, there is a need for stronger near-optimality guarantees for PI. In particular, we seek to develop results that provide computable near-optimality bounds, without relying on a discount factor, and to provide conditions under which the sequence of constructed value functions satisfies a uniform monotonic convergence property towards the optimal one.

In this context, we consider deterministic nonlinear discrete-time systems, whose inputs are generated by PI for an undiscounted infinite-horizon cost function. We first assume that PI is recursively feasible and we provide general conditions inspired from the model predictive control literature [13] to ensure the recursive robust stability of the closed-loop system at each iteration, where the attractor is a set. These conditions relate to the detectability of the system with respect to the stage cost and the stabilizing property of the initial policy. We then exploit these stability properties to derive explicit and computable bounds on the mismatch between the optimal value function and the value function obtained by PI at each iteration. We also show that the sequence of value functions satisfies a uniform convergence property towards the optimal value function by exploiting stability.

Afterwards, we show via a counter-example that PI may actually fail to be recursively feasible under commonly used assumptions. We thus propose to modify the original formulation of PI so that we can guarantee the recursive feasibility of the algorithm under mild conditions on the model, the stage cost and the input set. We call this new algorithm PI plus (PI$^+$). PI$^+$ differs from PI in two aspects. First, an (outer semicontinuous) regularization is performed at the so-called improvement step, which is a common technique in the discontinuous/hybrid systems literature [9]. Second, instead of letting the algorithm select any policy that minimizes the (regularized) improvement step, we select any of those generating the smallest cost that we aim to minimize thereby requiring an extra layer of computation. In this paper, we do not address the question of the practical implementation of

PI$^+$, which is left for future work. Instead, we concentrate on the methodological challenges raised by the algorithm. We then prove that PI$^+$ is indeed recursively feasible, and that it preserves the recursive robust stability when the attractor is compact as well as the near-optimality properties established for PI. Compared to our preliminary work in [10], novel elements include the results for PI, the robust stability analysis, the fact that the admissible input set can be state-dependent, and new technical developments to derive less conservative near-optimality bounds. Moreover, the full proofs are provided.

The rest of the paper is organized as follows. Preliminaries are given in Section II. The analysis of PI is carried out in Section III. The new algorithm PI$^+$ and its properties are presented in Section IV. We defer the robustness analysis of the stability properties ensured by PI and PI$^+$ in Section V. Concluding remarks are provided in Section VI. The proofs are given in the appendices, to streamline the presentation.

## II. PRELIMINARIES

In this section, we define the notation, provide important definitions and formalize the problem.

### A. Notation

Let $\mathbb{R} := (-\infty, \infty)$, $\mathbb{R}_{\ge 0} := [0, \infty)$, $\bar{\mathbb{R}} := [-\infty, \infty]$, $\mathbb{Z}_{\ge 0} := \{0, 1, 2, ...\}$ and $\bar{\mathbb{Z}}_{> 0} := \{1, 2, ...\}$. The notation $(x, y)$ stands for $[x^{\top}, y^{\top}]^{\top}$, with $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$, $n, m \in \mathbb{Z}_{> 0}$. The Euclidean norm of a vector $x \in \mathbb{R}^n$ with $n \in \mathbb{Z}_{> 0}$ is denoted by $|x|$ and the distance of $x \in \mathbb{R}^n$ to a non-empty set $\mathcal{A} \subseteq \mathbb{R}^n$ is denoted by $|x|_{\mathcal{A}} := \inf\{|x - y| : y \in \mathcal{A}\}$. The unit closed ball of $\mathbb{R}^n$ for $n \in \mathbb{Z}_{> 0}$ centered at the origin is denoted by $\mathbb{B}$. We consider $\mathcal{K}$, $\mathcal{K}_{\infty}$ and $\mathcal{KL}$ functions as defined in [9, Section 3.5]. We write $\beta \in \exp-\mathcal{KL}$ when $\beta(s_1, s_2) = \lambda_1 s_1 e^{-\lambda_2 s_2}$ for some $\lambda_1 \in [1, \infty)$ and $\lambda_2 > 0$ for any $(s_1, s_2) \in \mathbb{R}_{\ge 0}^2$. Given $\mathcal{A} \subseteq \mathbb{R}^n$, the indicator function $\delta_{\mathcal{A}} : \mathbb{R}^n \to \bar{\mathbb{R}}$ is defined as $\delta_{\mathcal{A}}(x) = 0$ when $x \in \mathcal{A}$ and $\delta_{\mathcal{A}}(x) = \infty$ when $x \notin \mathcal{A}$ as in [27]. In contrast, given $\mathcal{A} \subseteq \mathbb{R}^n$ closed, we say $\sigma : \mathbb{R}^n \to \mathbb{R}_{\ge 0}$ is a proper indicator of set $\mathcal{A}$ whenever $\sigma$ is continuous and there exist $\underline{\alpha}_{\sigma}, \bar{\alpha}_{\sigma} \in \mathcal{K}_{\infty}$ such that $\underline{\alpha}_{\sigma}(|x|_{\mathcal{A}}) \le \sigma(x) \le \bar{\alpha}_{\sigma}(|x|_{\mathcal{A}})$ for any $x \in \mathbb{R}^n$. The identity map from $\mathbb{R}_{\ge 0}$ to $\mathbb{R}_{\ge 0}$ is $\mathbb{I}$, and the zero map from $\mathbb{R}_{\ge 0}$ to $\mathbb{I}$ is $0$. Let $\tilde{f} : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$. We use $f^{(k)}$ for the composition of function $f$ to itself $k$ times, where $k \in \mathbb{Z}_{\ge 0}$ and $f^{(0)} := \mathbb{I}$. Given a set-valued map $S : \mathbb{R}^n \rightrightarrows \mathbb{R}^m$, a selection of $S$ is a single-valued mapping $s : \text{dom} S \to \mathbb{R}^m$ such that $s(x) \in S(x)$ for any $x \in \text{dom} S$. For the sake of convenience, we write $s \in S$ to denote a selection $s$ of $S$. We have the next definition from [27, Def. 1.16].

**Definition 1:** A function $f : \mathbb{R}^n \times \mathbb{R}^m \to \bar{\mathbb{R}}$ where $n, m \in \mathbb{Z}_{> 0}$ with values $f(x, u)$ is level-bounded in $u$, locally uniform in $x$ if for each $x \in \mathbb{R}^n$ and $\alpha \in \mathbb{R}$ there is a neighborhood $S$ of $x$ along a bounded set $B \subset \mathbb{R}^n$ such that $\{u \in \mathbb{R}^m : f(z, u) \le \alpha\} \subset B$ for any $z \in S$. $\square$

### B. Plant model and cost function

Consider the plant model

$$x(k+1) = f(x(k), u(k)), \quad (1)$$
further would like these stability properties to be preserved at each iteration; that is, we want to ensure recursive robust stability.

Finally, it is important to understand when and how the sequence of value functions generated by PI at each iteration converges to the optimal value function; we talk of near-optimality guarantees. The literature stands in two ways on this issue. On the one hand, the value functions are known to converge monotonically and point-wisely to the optimal value function under mild conditions on the model and the cost [5,15]; uniform convergence properties are only ensured, as far as we know, for discounted costs functions [2]. On the other hand, it is important to be able to evaluate the mismatch between the returned value function at each iteration and the optimal one. These computable or explicit bounds on the mismatch of generated value functions are vital to decide when to stop iterating the algorithm. Existing results concentrate on discounted costs [2], which are not always natural in control applications. In the discounted setting, the provided near-optimality bounds explode when the discount factor $\gamma \in (0, 1)$ converges to one [2], while to ensure stability, in opposition, $\gamma$ should be close enough to one in view of [11,26]. Hence, there is a need for stronger near-optimality guarantees for PI. In particular, we seek to develop results that provide computable near-optimality bounds, without relying on a discount factor, and to provide conditions under which the sequence of constructed value functions satisfies a uniform monotonic convergence property towards the optimal one.

In this context, we consider deterministic nonlinear discrete-time systems, whose inputs are generated by PI for an undiscounted infinite-horizon cost function. We first assume that PI is recursively feasible and we provide general conditions inspired from the model predictive control literature [13] to ensure the recursive robust stability of the closed-loop system at each iteration, where the attractor is a set. These conditions relate to the detectability of the system with respect to the stage cost and the stabilizing property of the initial policy. We then exploit these stability properties to derive explicit and computable bounds on the mismatch between the optimal value function and the value function obtained by PI at each iteration. We also show that the sequence of value functions satisfies a uniform convergence property towards the optimal value function by exploiting stability.

Afterwards, we show via a counter-example that PI may actually fail to be recursively feasible under commonly used assumptions. We thus propose to modify the original formulation of PI so that we can guarantee the recursive feasibility of the algorithm under mild conditions on the model, the stage cost and the input set. We call this new algorithm PI plus (PI$^+$). PI$^+$ differs from PI in two aspects. First, an (outer semicontinuous) regularization is performed at the so-called improvement step, which is a common technique in the discontinuous/hybrid systems literature [9]. Second, instead of letting the algorithm select any policy that minimizes the (regularized) improvement step, we select any of those generating the smallest cost that we aim to minimize thereby requiring an extra layer of computation. In this paper, we do not address the question of the practical implementation of

PI$^+$, which is left for future work. Instead, we concentrate on the methodological challenges raised by the algorithm. We then prove that PI$^+$ is indeed recursively feasible, and that it preserves the recursive robust stability when the attractor is compact as well as the near-optimality properties established for PI. Compared to our preliminary work in [10], novel elements include the results for PI, the robust stability analysis, the fact that the admissible input set can be state-dependent, and new technical developments to derive less conservative near-optimality bounds. Moreover, the full proofs are provided.

The rest of the paper is organized as follows. Preliminaries are given in Section II. The analysis of PI is carried out in Section III. The new algorithm PI$^+$ and its properties are presented in Section IV. We defer the robustness analysis of the stability properties ensured by PI and PI$^+$ in Section V. Concluding remarks are provided in Section VI. The proofs are given in the appendices, to streamline the presentation.

## II. PRELIMINARIES

In this section, we define the notation, provide important definitions and formalize the problem.

### A. Notation

Let $\mathbb{R} := (-\infty, \infty)$, $\mathbb{R}_{\ge 0} := [0, \infty)$, $\bar{\mathbb{R}} := [-\infty, \infty]$, $\mathbb{Z}_{\ge 0} := \{0, 1, 2, ...\}$ and $\bar{\mathbb{Z}}_{> 0} := \{1, 2, ...\}$. The notation $(x, y)$ stands for $[x^{\top}, y^{\top}]^{\top}$, with $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$, $n, m \in \mathbb{Z}_{> 0}$. The Euclidean norm of a vector $x \in \mathbb{R}^n$ with $n \in \mathbb{Z}_{> 0}$ is denoted by $|x|$ and the distance of $x \in \mathbb{R}^n$ to a non-empty set $\mathcal{A} \subseteq \mathbb{R}^n$ is denoted by $|x|_{\mathcal{A}} := \inf\{|x - y| : y \in \mathcal{A}\}$. The unit closed ball of $\mathbb{R}^n$ for $n \in \mathbb{Z}_{> 0}$ centered at the origin is denoted by $\mathbb{B}$. We consider $\mathcal{K}$, $\mathcal{K}_{\infty}$ and $\mathcal{KL}$ functions as defined in [9, Section 3.5]. We write $\beta \in \exp-\mathcal{KL}$ when $\beta(s_1, s_2) = \lambda_1 s_1 e^{-\lambda_2 s_2}$ for some $\lambda_1 \in [1, \infty)$ and $\lambda_2 > 0$ for any $(s_1, s_2) \in \mathbb{R}_{\ge 0}^2$. Given $\mathcal{A} \subseteq \mathbb{R}^n$, the indicator function $\delta_{\mathcal{A}} : \mathbb{R}^n \to \bar{\mathbb{R}}$ is defined as $\delta_{\mathcal{A}}(x) = 0$ when $x \in \mathcal{A}$ and $\delta_{\mathcal{A}}(x) = \infty$ when $x \notin \mathcal{A}$ as in [27]. In contrast, given $\mathcal{A} \subseteq \mathbb{R}^n$ closed, we say $\sigma : \mathbb{R}^n \to \mathbb{R}_{\ge 0}$ is a proper indicator of set $\mathcal{A}$ whenever $\sigma$ is continuous and there exist $\underline{\alpha}_{\sigma}, \bar{\alpha}_{\sigma} \in \mathcal{K}_{\infty}$ such that $\underline{\alpha}_{\sigma}(|x|_{\mathcal{A}}) \le \sigma(x) \le \bar{\alpha}_{\sigma}(|x|_{\mathcal{A}})$ for any $x \in \mathbb{R}^n$. The identity map from $\mathbb{R}_{\ge 0}$ to $\mathbb{R}_{\ge 0}$ is $\mathbb{I}$, and the zero map from $\mathbb{R}_{\ge 0}$ to $\mathbb{I}$ is $\mathbb{0}$. Let $\tilde{f} : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$. We use $f^{(k)}$ for the composition of function $f$ to itself $k$ times, where $k \in \mathbb{Z}_{\ge 0}$ and $f^{(0)} := \mathbb{I}$. Given a set-valued map $S : \mathbb{R}^n \rightrightarrows \mathbb{R}^m$, a selection of $S$ is a single-valued mapping $s : \text{dom} S \to \mathbb{R}^m$ such that $s(x) \in S(x)$ for any $x \in \text{dom} S$. For the sake of convenience, we write $s \in S$ to denote a selection $s$ of $S$. We have the next definition from [27, Def. 1.16].

**Definition 1:** A function $f : \mathbb{R}^n \times \mathbb{R}^m \to \bar{\mathbb{R}}$ where $n, m \in \mathbb{Z}_{> 0}$ with values $f(x, u)$ is level-bounded in $u$, locally uniform in $x$ if for each $x \in \mathbb{R}^n$ and $\alpha \in \mathbb{R}$ there is a neighborhood $\mathcal{S}$ of $x$ along a bounded set $B \subset \mathbb{R}^n$ such that $\{u \in \mathbb{R}^m : f(z, u) \le \alpha\} \subset B$ for any $z \in \mathcal{S}$. $\square$

### B. Plant model and cost function

Consider the plant model

$$x(k+1) = f(x(k), u(k)), \quad (1)$$
where $x \in \mathbb{R}^{n_x}$ is the state, $u \in \mathcal{U}(x) \subseteq \mathbb{R}^{n_u}$ is the control input, the time-step is $k \in \mathbb{Z}_{\ge 0}$, $\mathcal{U}(x)$ is a non-empty set of admissible inputs for state $x \in \mathbb{R}^{n_x}$, and $n_x, n_u \in \mathbb{Z}_{>0}$. We wish to find, for any given $x \in \mathbb{R}^{n_x}$, an infinite-length sequence of admissible inputs $\mathbf{u} = (u(0), u(1), \dots)$, that minimizes the infinite-horizon cost

$$J(x, \mathbf{u}) := \sum_{k=0}^{\infty} \ell(\phi(k, x, \mathbf{u}|_k), u(k)), \quad (2)$$

where $\ell: \mathbb{R}^{n_x} \times \mathbb{R}^{n_u} \to \mathbb{R}_{\ge 0}$ is a non-negative stage cost and $\phi(k, x, \mathbf{u}|_k)$ is the solution to (1) at the $k^{\text{th}}$-step, initialized at $x$ at time 0 with inputs $\mathbf{u}|_k := (u(0), \dots, u(k-1))$. The minimum of $J(x, \cdot)$ is denoted as

$$V^*(x) := \min_{\mathbf{u}} J(x, \mathbf{u}) \quad (3)$$

for any $x \in \mathbb{R}^{n_x}$, where $V^*$ is the optimal value function associated to the minimization of (2).

**Standing Assumption 1 (SA1):** For any $x \in \mathbb{R}^{n_x}$, there exists an optimal sequence of admissible inputs $\mathbf{u}^*(x)$ such that $V^*(x) = J(x, \mathbf{u}^*(x)) < +\infty$ and for any infinite-length sequence of admissible inputs $\mathbf{u}$, $V^*(x) \le J(x, \mathbf{u})$. $\square$

Conditions to ensure SA1 can be found in, e.g., [19]. Given (3), we define the set of optimal inputs as

$$H^*(x) := \underset{u \in \mathcal{U}(x)}{\operatorname{argmin}} \{\ell(x, u) + V^*(f(x, u))\}. \quad (4)$$

To compute $H^*$ in (4) for the general dynamics in (1) is notoriously hard. Dynamic programming provides algorithms to iteratively obtain feedback laws, which instead converge to $H^*$ [4]. A fundamental algorithm of dynamic programming is PI, which is presented and analysed in the next section. Before that, we introduce some notation, which will be convenient in the sequel. Given a feedback law $h: \mathbb{R}^{n_x} \to \mathbb{R}^{n_u}$ that is admissible, i.e., $h \in \mathcal{U}$, we denote the solution to system (1) in closed-loop with feedback law $h$ at time $k \in \mathbb{Z}_{\ge 0}$ with initial condition $x$ at time 0 as $\phi(k, x, h)$. Likewise, $J(x, h)$ is the cost induced by $h$ at initial state $x$, i.e., $J(x, h) = \sum_{k=0}^{\infty} \ell(\phi(k, x, h), h(\phi(k, x, h)))$. In this way, we have that for any selection $h^* \in H^*$, $V^*(\cdot) = J(\cdot, h^*)$, as $H^*(x)$ is non-empty for any $x \in \mathbb{R}^{n_x}$ by SA1.

### III. POLICY ITERATION

We recall in this section the original formulation of PI and we assume the algorithm is feasible at any iteration. We then establish novel recursive stability and near-optimality guarantees, assuming a detectability property is satisfied and the initial policy is stabilizing. Finally, we present an example where PI is not recursively feasible despite supposedly favorable properties, thereby motivating the need to modify PI to overcome this issue, which will be the topic of Section IV. As mentioned in the introduction, the robustness of the stability properties is analyzed in Section V.

#### A. The algorithm

PI is presented in Algorithm 1. Given an initial admissible policy $h^0$, PI generates at each iteration $i \in \mathbb{Z}_{\ge 0}$ a policy $h^{i+1}$ with cost $V^{i+1}(x) := J(x, h^{i+1})$ and it can be proved that $V^{i+1}(x) \le V^i(x)$ for all $x \in \mathbb{R}^{n_x}$ [28, Section 4.2]. This

#### Algorithm 1 Policy Iteration (PI)

**Input:** $f$ in (1), $\ell$ in (2), initial policy $h^0 \in \mathcal{U}$

**Output:** Policy $h^\infty$, cost $V^\infty$

1. **Initial evaluation step:** for all $x \in \mathbb{R}^{n_x}$,

$$V^0(x) := J(x, h^0). \quad (\text{PI.1})$$

2. **for** $i \in \mathbb{Z}_{\ge 0}$ **do**

3. **Policy improvement step:** for all $x \in \mathbb{R}^{n_x}$,

$$H^{i+1}(x) := \underset{u \in \mathcal{U}(x)}{\operatorname{argmin}} \{\ell(x, u) + V^i(f(x, u))\}. \quad (\text{PI.2})$$

4. Select $h^{i+1} \in H^{i+1}$.

5. **Policy evaluation step:** for all $x \in \mathbb{R}^{n_x}$,

$$V^{i+1}(x) := J(x, h^{i+1}). \quad (\text{PI.3})$$

6. **end for**

7. **return** $h^\infty \in H^\infty$ and $V^\infty$.

is done via the improvement step in (PI.2). The policy $h^{i+1}$ obtained at iteration $i+1$ is an arbitrary selection of $H^{i+1}$ in (PI.2) where $H^{i+1}$ may be set-valued. We then evaluate the cost induced by $h^{i+1}$, namely $V^{i+1} = J(\cdot, h^{i+1})$, this is the evaluation step in (PI.3). By doing so repeatedly, $V^i$ converges to the optimal value function $V^\infty = V^*$ under mild conditions, see [2].

**Remark 1:** In practice, PI is often stopped at some iteration, typically by looking at the difference between $V^i$ and $V^{i-1}$ for some $i \in \mathbb{Z}_{>0}$. We will return to this point in Remark 2 in Section III-D.2. $\square$

#### B. Desired properties

For the remainder of this section, we proceed as is often done in the literature and assume Algorithm 1 is recursively feasible, see, e.g., [15,23], in the sense that the optimization problem in (PI.2) admits a solution for any $x \in \mathbb{R}^{n_x}$ at any iteration $i \in \mathbb{Z}_{>0}$, which is formalized below.

**Assumption 1:** Set-valued map $H^i(x)$ is non-empty for any $i \in \mathbb{Z}_{>0}$ and $x \in \mathbb{R}^{n_x}$. $\square$

We note that verifying Assumption 1 is hard in general. At a given iteration $i+1$ with $i \in \mathbb{Z}_{\ge 0}$, a sufficient condition for $H^{i+1}(x)$ to be non-empty for any $x \in \mathbb{R}^{n_x}$ is establishing the lower semicontinuity of map $(x, u) \mapsto \ell(x, u) + V^i(f(x, u)) + \delta_{\mathcal{U}(x)}(u)$ on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$, see, e.g., [3]. However, this is hard to check in advance as $V^i$ is not known a priori. We will return to the question of the recursive feasibility of PI in Section III-E.

Under Assumption 1, the goal of this section is to establish the recursive stability and near-optimality bounds for PI, in particular we aim at showing that PI is

* **recursively stabilizing**, i.e., if $h^0$ stabilizes system (1), then this property is also ensured by any $h^i \in H^i$ for any $i \in \mathbb{Z}_{>0}$, in the sense that the difference inclusion

$$x(k+1) \in f(x(k), H^i(x(k))) := F^i(x(k)) \quad (5)$$

exhibits desirable set stability properties;

* **near-optimal** in the sense that we have guaranteed bounds on $V^i - V^*$ for any $i \in \mathbb{Z}_{\ge 0}$, despite the fact that $V^*$ in (3) is typically unknown.

These results rely on assumptions given in the next section. For convenience, solutions to system (5) are denoted in the
where $x \in \mathbb{R}^{n_x}$ is the state, $u \in \mathcal{U}(x) \subseteq \mathbb{R}^{n_u}$ is the control input, the time-step is $k \in \mathbb{Z}_{\ge 0}$, $\mathcal{U}(x)$ is a non-empty set of admissible inputs for state $x \in \mathbb{R}^{n_x}$, and $n_x, n_u \in \mathbb{Z}_{> 0}$. We wish to find, for any given $x \in \mathbb{R}^{n_x}$, an infinite-length sequence of admissible inputs $\mathbf{u} = (u(0), u(1), \dots)$, that minimizes the infinite-horizon cost

$$J(x, \mathbf{u}) := \sum_{k=0}^{\infty} \ell(\phi(k, x, \mathbf{u}|_k), u(k)), \quad (2)$$

where $\ell: \mathbb{R}^{n_x} \times \mathbb{R}^{n_u} \to \mathbb{R}_{\ge 0}$ is a non-negative stage cost and $\phi(k, x, \mathbf{u}|_k)$ is the solution to (1) at the $k^{th}$-step, initialized at $x$ at time 0 with inputs $\mathbf{u}|_k := (u(0), \dots, u(k-1))$. The minimum of $J(x, \cdot)$ is denoted as

$$V^*(x) := \min_{\mathbf{u}} J(x, \mathbf{u}) \quad (3)$$

for any $x \in \mathbb{R}^{n_x}$, where $V^*$ is the optimal value function associated to the minimization of (2).

**Standing Assumption 1 (SA1):** For any $x \in \mathbb{R}^{n_x}$, there exists an optimal sequence of admissible inputs $\mathbf{u}^*(x)$ such that $V^*(x) = J(x, \mathbf{u}^*(x)) < +\infty$ and for any infinite-length sequence of admissible inputs $\mathbf{u}$, $V^*(x) \le J(x, \mathbf{u})$. $\square$

Conditions to ensure SA1 can be found in, e.g., [19]. Given (3), we define the set of optimal inputs as

$$H^*(x) := \underset{u \in \mathcal{U}(x)}{\operatorname{argmin}} \{\ell(x, u) + V^*(f(x, u))\}. \quad (4)$$

To compute $H^*$ in (4) for the general dynamics in (1) is notoriously hard. Dynamic programming provides algorithms to iteratively obtain feedback laws, which instead converge to $H^*$ [4]. A fundamental algorithm of dynamic programming is PI, which is presented and analysed in the next section. Before that, we introduce some notation, which will be convenient in the sequel. Given a feedback law $h: \mathbb{R}^{n_x} \to \mathbb{R}^{n_u}$ that is admissible, i.e., $h \in \mathcal{U}$, we denote the solution to system (1) in closed-loop with feedback law $h$ at time $k \in \mathbb{Z}_{\ge 0}$ with initial condition $x$ at time 0 as $\phi(k, x, h)$. Likewise, $J(x, h)$ is the cost induced by $h$ at initial state $x$, i.e., $J(x, h) = \sum_{k=0}^{\infty} \ell(\phi(k, x, h), h(\phi(k, x, h)))$. In this way, we have that for any selection $h^* \in H^*$, $V^*(\cdot) = J(\cdot, h^*)$, as $H^*(x)$ is non-empty for any $x \in \mathbb{R}^{n_x}$ by SA1.

### III. POLICY ITERATION

We recall in this section the original formulation of PI and we assume the algorithm is feasible at any iteration. We then establish novel recursive stability and near-optimality guarantees, assuming a detectability property is satisfied and the initial policy is stabilizing. Finally, we present an example where PI is not recursively feasible despite supposedly favorable properties, thereby motivating the need to modify PI to overcome this issue, which will be the topic of Section IV. As mentioned in the introduction, the robustness of the stability properties is analyzed in Section V.

#### A. The algorithm

PI is presented in Algorithm 1. Given an initial admissible policy $h^0$, PI generates at each iteration $i \in \mathbb{Z}_{\ge 0}$ a policy $h^{i+1}$ with cost $V^{i+1}(x) := J(x, h^{i+1})$ and it can be proved that $V^{i+1}(x) \le V^i(x)$ for all $x \in \mathbb{R}^{n_x}$ [28, Section 4.2]. This

#### Algorithm 1 Policy Iteration (PI)

**Input:** $f$ in (1), $\ell$ in (2), initial policy $h^0 \in \mathcal{U}$

**Output:** Policy $h^\infty$, cost $V^\infty$

1. **Initial evaluation step:** for all $x \in \mathbb{R}^{n_x}$,

$$V^0(x) := J(x, h^0). \quad (\text{PI.1})$$

2. **for** $i \in \mathbb{Z}_{\ge 0}$ **do**

3. **Policy improvement step:** for all $x \in \mathbb{R}^{n_x}$,

$$H^{i+1}(x) := \underset{u \in \mathcal{U}(x)}{\operatorname{argmin}} \{\ell(x, u) + V^i(f(x, u))\}. \quad (\text{PI.2})$$

4. Select $h^{i+1} \in H^{i+1}$.

5. **Policy evaluation step:** for all $x \in \mathbb{R}^{n_x}$,

$$V^{i+1}(x) := J(x, h^{i+1}). \quad (\text{PI.3})$$

6. **end for**

7. **return** $h^\infty \in H^\infty$ and $V^\infty$.

is done via the improvement step in (PI.2). The policy $h^{i+1}$ obtained at iteration $i+1$ is an arbitrary selection of $H^{i+1}$ in (PI.2) where $H^{i+1}$ may be set-valued. We then evaluate the cost induced by $h^{i+1}$, namely $V^{i+1} = J(\cdot, h^{i+1})$, this is the evaluation step in (PI.3). By doing so repeatedly, $V^i$ converges to the optimal value function $V^\infty = V^*$ under mild conditions, see [2].

**Remark 1:** In practice, PI is often stopped at some iteration, typically by looking at the difference between $V^i$ and $V^{i-1}$ for some $i \in \mathbb{Z}_{> 0}$. We will return to this point in Remark 2 in Section III-D.2. $\square$

#### B. Desired properties

For the remainder of this section, we proceed as is often done in the literature and assume Algorithm 1 is recursively feasible, see, e.g., [15,23], in the sense that the optimization problem in (PI.2) admits a solution for any $x \in \mathbb{R}^{n_x}$ at any iteration $i \in \mathbb{Z}_{> 0}$, which is formalized below.

**Assumption 1:** Set-valued map $H^i(x)$ is non-empty for any $i \in \mathbb{Z}_{> 0}$ and $x \in \mathbb{R}^{n_x}$. $\square$

We note that verifying Assumption 1 is hard in general. At a given iteration $i+1$ with $i \in \mathbb{Z}_{\ge 0}$, a sufficient condition for $H^{i+1}(x)$ to be non-empty for any $x \in \mathbb{R}^{n_x}$ is establishing the lower semicontinuity of map $(x, u) \mapsto \ell(x, u) + V^i(f(x, u)) + \delta_{\mathcal{U}(x)}(u)$ on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$, see, e.g., [3]. However, this is hard to check in advance as $V^i$ is not known a priori. We will return to the question of the recursive feasibility of PI in Section III-E.

Under Assumption 1, the goal of this section is to establish the recursive stability and near-optimality bounds for PI, in particular we aim at showing that PI is

* **recursively stabilizing**, i.e., if $h^0$ stabilizes system (1), then this property is also ensured by any $h^i \in H^i$ for any $i \in \mathbb{Z}_{> 0}$, in the sense that the difference inclusion

$$x(k+1) \in f(x(k), H^i(x(k))) := F^i(x(k)) \quad (5)$$

exhibits desirable set stability properties;

* **near-optimal** in the sense that we have guaranteed bounds on $V^i - V^*$ for any $i \in \mathbb{Z}_{\ge 0}$, despite the fact that $V^*$ in (3) is typically unknown.

These results rely on assumptions given in the next section. For convenience, solutions to system (5) are denoted in the
sequel as $\phi^i(\cdot, x)$ when initialized at some $x \in \mathbb{R}^{n_x}$ for any $i \in \mathbb{Z}_{\ge 0}$.

### C. Standing assumptions

To define stability, we use a continuous function $\sigma : \mathbb{R}^{n_x} \to \mathbb{R}_{\ge 0}$ that serves as a state “measure” relating the distance of the state to a given attractor where $\sigma$ vanishes. By stability, we mean that there exists $\beta \in \mathcal{KL}$ (independent of $i$) such that, for any $x \in \mathbb{R}^{n_x}$, $i \in \mathbb{Z}_{\ge 0}$, any solution $\phi^i$ to (5) verifies, for any $k \in \mathbb{Z}_{\ge 0}$,

$$ \sigma(\phi^i(k, x)) \le \beta(\sigma(x), k). \quad (6) $$

Property (6) is a $\mathcal{KL}$-stability property of system (5) with respect to $\sigma$. When $\sigma$ is a proper indicator function of a closed set $A \subseteq \mathbb{R}^{n_x}$, the uniform global asymptotic stability of set $A = \{x \in \mathbb{R}^{n_x} : \sigma(x) = 0\}$ is guaranteed by (6). When $\sigma(x) = |x|^a$ for any $x \in \mathbb{R}^{n_x}$ with $a \ge 1$, the uniform global asymptotic stability of the origin $x = 0$ is ensured by (6), for instance. Function $\sigma$ is thus convenient to address stability properties for general attractors.

We make the next detectability assumption on system (1) and stage cost $\ell$ consistently with e.g., [11,13,18,26].

**Standing Assumption 2 (SA2):** There exist a continuous function $W : \mathbb{R}^{n_x} \to \mathbb{R}_{\ge 0}$, $\alpha_W, \chi_W \in \mathcal{K}_\infty$ and $\bar{\alpha}_W : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$ continuous, nondecreasing and zero at zero, such that, for any $(x, u) \in W := \{(x, u) \in \mathbb{R}^n \times \mathbb{R}^m : u \in \mathcal{U}(x)\}$,

$$ \begin{aligned} W(x) &\le \bar{\alpha}_W(\sigma(x)) \\ W(f(x, u)) - W(x) &\le -\alpha_W(\sigma(x)) + \chi_W(\ell(x, u)). \end{aligned} \quad (7) $$

SA2 is a detectability property of system (1) and stage cost $\ell$, see [13,16] for more details. SA2 holds for instance with $W = 0$ when $\{x \in \mathbb{R}^{n_x} : \sigma(x) = 0\}$ is compact, $\ell(x, u) = \ell_1(x) + \ell_2(x, u)$ with $\ell_1$ continuous, positive definite with respect to the set $\{x \in \mathbb{R}^{n_x} : \sigma(x) = 0\}$, $\ell_1(x) \to \infty$ as $|x| \to \infty$, and $\ell_2(x, u) \ge 0$ for any $(x, u) \in W$. Note that SA2 relaxes the requirement that $\ell(\cdot, u)$ be positive definite for any $u \ne 0$ as found in, e.g., [5,7,23,24], and $\ell$ is not required to satisfy convexity properties.

Finally, like in e.g., [3,15,23], we assume that we initialize the algorithm with a stabilizing feedback law $h^0$. In particular, we make the next assumption.

**Standing Assumption 3 (SA3):** There exists $\bar{\alpha}_V \in \mathcal{K}_\infty$ such that, for any $x \in \mathbb{R}^{n_x}$, $V^0(x) = J(x, h^0) \le \bar{\alpha}_V(\sigma(x))$. □

SA2 and SA3 are related to the stability property of system (1) in closed-loop with $h^0$ as in (6). This is established below.

### D. Results

We now establish the desired properties listed in Section III-D. The proofs of the forthcoming results follow very similar lines as the equivalent ones stated in Section IV for $\mathrm{PI}^+$. For this reason, the proofs are carried out in details for the results of Section IV in Appendices I and II, and their application to the results of the present section is discussed in Appendix III.

1) **Recursive stability:** The next theorem establishes recursive stability.

**Theorem 1:** Suppose Assumption 1 holds. For any $i \in \mathbb{Z}_{\ge 0}$, for any $x \in \mathbb{R}^{n_x}$, solution $\phi^i$ to (5) and $k \in \mathbb{Z}_{\ge 0}$,

$$ \sigma(\phi^i(k, x)) \le \beta(\sigma(x), k), \quad (8) $$

where $\beta : (k, s) \mapsto \bar{\alpha}_Y^{-1} \circ (\mathbb{I} - \tilde{\alpha}_Y)^{(k)} \circ \bar{\alpha}_Y(s) \in \mathcal{KL}$ with $\bar{\alpha}_Y, \bar{\alpha}_Y, \alpha_Y$ in Table I. □

Theorem 1 ensures the desired $\mathcal{KL}$-stability property of system (5) with respect to $\sigma$ at any iteration $i \in \mathbb{Z}_{\ge 0}$, and thus at $i = 0$, which confirms that $h^0$ is stabilizing as mentioned above. It is important to note that $\beta$ in (8) is independent of the number of iterations $i$, which makes the stability property uniform with respect to $i$.

Under extra conditions, we can derive an exponential stability result.

**Corollary 1:** Suppose Assumption 1 holds and that there exist $c_W, a_W, \bar{a}_V > 0$ and $\bar{a}_W \ge 0$ such that $\chi_W(s) \le c_W s$, $\alpha_W(s) \ge a_W s$, $\bar{\alpha}_V(s) \le \bar{a}_V s$, $\bar{\alpha}_W(s) \le \bar{a}_W s$ for any $s \ge 0$, where $\chi_W, \alpha_W, \bar{\alpha}_W$ come from SA2 and $\bar{\alpha}_V$ comes from SA3. Then, Theorem 1 holds with $\beta : (s, k) \mapsto \frac{\bar{a}_Y}{\bar{a}_Y}(1 - \tilde{a}_Y)^k s \in \exp(-\mathcal{KL})$, and $\tilde{a}_Y, \bar{a}_Y, \bar{a}_Y$ in Table I. □

2) **Near-optimality properties:** Next, we establish near-optimality properties of PI.

**Theorem 2:** Suppose Assumption 1 holds. For any $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$,

$$ (V^i - V^*)(x) \le (V^0 - V^*)(\phi(i, x, h^*)), \quad (9) $$

where $h^* \in H^*$ from (4). Moreover, for any $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$,

$$ V^i(x) - V^*(x) \le \tilde{\alpha}(\beta(\sigma(x), i)), \quad (10) $$

where $\beta \in \mathcal{KL}$ comes from Theorem 1 and $\tilde{\alpha} = \max_{\hat{s} \in [0, s]} \hat{\alpha}(\hat{s})$ is non-decreasing and positive definite function with $\hat{\alpha}$ in Table I. □

Theorem 2 provides novel characterisations of the near-optimality properties of PI. In (9), $(V^i - V^*)(x)$ is the near-optimality error term at iteration $i \in \mathbb{Z}_{\ge 0}$ and state $x \in \mathbb{R}^{n_x}$. This error is upper-bounded in (9) by $(V^0 - V^*)(\phi(i, x, h^*))$, which is the “initial” near-optimality error term for $i = 0$, but evaluated at state $\phi(i, x, h^*)$ instead of $x$. In its turn, state $\phi(i, x, h^*)$ corresponds to the $i^{th}$ time-step of the solution of (1) initialized at $x$ in closed-loop with an optimal (and typically unknown) policy $h^* \in H^*$. This bound decreases to zero point-wisely as $i \to \infty$ thanks for the stability property of system (1) in closed-loop with (4), which follows similarly as Theorem 1. However, the upper-bound in (9) is typically unknown. To overcome this possible issue, a conservative upper-bound of $(V^0 - V^*)(\phi(i, x, h^*))$ in the form of $\tilde{\alpha}(\beta(\sigma(x), i))$ is given in (10), where $\beta$ and $\tilde{\alpha}$ come from Theorems 1 and 2 and can be both computed. The fact that function $\beta$ in (8) is independent of the number of iterations $i$ is vital for (10). Indeed, as a result, the upper-bound is ensured to converge to zero as $i$ increases to infinity. We emphasize that the above near-optimality properties exploit stability to provide explicit bounds as in (10). This is in contrast to the literature, which

<footnote n="1">¹To simplify presentation, we assume $\mathbb{I} - \tilde{\alpha}_Y$ is non-decreasing. If this is not the case, we can always replace $\mathbb{I} - \tilde{\alpha}_Y$ by $s \mapsto \max_{\hat{s} \in [0, s]} (\mathbb{I} - \tilde{\alpha}_Y)(\hat{s})$.</footnote>
sequel as $\phi^i(\cdot, x)$ when initialized at some $x \in \mathbb{R}^{n_x}$ for any $i \in \mathbb{Z}_{\ge 0}$.

### C. Standing assumptions

To define stability, we use a continuous function $\sigma : \mathbb{R}^{n_x} \to \mathbb{R}_{\ge 0}$ that serves as a state “measure” relating the distance of the state to a given attractor where $\sigma$ vanishes. By stability, we mean that there exists $\beta \in \mathcal{KL}$ (independent of $i$) such that, for any $x \in \mathbb{R}^{n_x}$, $i \in \mathbb{Z}_{\ge 0}$, any solution $\phi^i$ to (5) verifies, for any $k \in \mathbb{Z}_{\ge 0}$,

$$ \sigma(\phi^i(k, x)) \le \beta(\sigma(x), k). \quad (6) $$

Property (6) is a $\mathcal{KL}$-stability property of system (5) with respect to $\sigma$. When $\sigma$ is a proper indicator function of a closed set $A \subseteq \mathbb{R}^{n_x}$, the uniform global asymptotic stability of set $A = \{x \in \mathbb{R}^{n_x} : \sigma(x) = 0\}$ is guaranteed by (6). When $\sigma(x) = |x|^a$ for any $x \in \mathbb{R}^{n_x}$ with $a \ge 1$, the uniform global asymptotic stability of the origin $x = 0$ is ensured by (6), for instance. Function $\sigma$ is thus convenient to address stability properties for general attractors.

We make the next detectability assumption on system (1) and stage cost $\ell$ consistently with e.g., [11,13,18,26].

**Standing Assumption 2 (SA2):** There exist a continuous function $W : \mathbb{R}^{n_x} \to \mathbb{R}_{\ge 0}$, $\alpha_W, \chi_W \in \mathcal{K}_{\infty}$ and $\bar{\alpha}_W : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$ continuous, nondecreasing and zero at zero, such that, for any $(x, u) \in W := \{(x, u) \in \mathbb{R}^n \times \mathbb{R}^m : u \in U(x)\}$,

$$ \begin{aligned} W(x) &\le \bar{\alpha}_W(\sigma(x)) \\ W(f(x, u)) - W(x) &\le -\alpha_W(\sigma(x)) + \chi_W(\ell(x, u)). \end{aligned} \quad (7) $$

SA2 is a detectability property of system (1) and stage cost $\ell$, see [13,16] for more details. SA2 holds for instance with $W = 0$ when $\{x \in \mathbb{R}^{n_x} : \sigma(x) = 0\}$ is compact, $\ell(x, u) = \ell_1(x) + \ell_2(x, u)$ with $\ell_1$ continuous, positive definite with respect to the set $\{x \in \mathbb{R}^{n_x} : \sigma(x) = 0\}$, $\ell_1(x) \to \infty$ as $|x| \to \infty$, and $\ell_2(x, u) \ge 0$ for any $(x, u) \in W$. Note that SA2 relaxes the requirement that $\ell(\cdot, u)$ be positive definite for any $u \ne 0$ as found in, e.g., [5,7,23,24], and $\ell$ is not required to satisfy convexity properties.

Finally, like in e.g., [3,15,23], we assume that we initialize the algorithm with a stabilizing feedback law $h^0$. In particular, we make the next assumption.

**Standing Assumption 3 (SA3):** There exists $\bar{\alpha}_V \in \mathcal{K}_{\infty}$ such that, for any $x \in \mathbb{R}^{n_x}$, $V^0(x) = J(x, h^0) \le \bar{\alpha}_V(\sigma(x))$. □

SA2 and SA3 are related to the stability property of system (1) in closed-loop with $h^0$ as in (6). This is established below.

### D. Results

We now establish the desired properties listed in Section III-D. The proofs of the forthcoming results follow very similar lines as the equivalent ones stated in Section IV for $\mathrm{PI}^+$. For this reason, the proofs are carried out in details for the results of Section IV in Appendices I and II, and their application to the results of the present section is discussed in Appendix III.

**1) Recursive stability:** The next theorem establishes recursive stability.

**Theorem 1:** Suppose Assumption 1 holds. For any $i \in \mathbb{Z}_{\ge 0}$, for any $x \in \mathbb{R}^{n_x}$, solution $\phi^i$ to (5) and $k \in \mathbb{Z}_{\ge 0}$,

$$ \sigma(\phi^i(k, x)) \le \beta(\sigma(x), k), \quad (8) $$

where $\beta : (k, s) \mapsto \bar{\alpha}_Y^{-1} \circ (\mathbb{I} - \tilde{\alpha}_Y)^{(k)} \circ \bar{\alpha}_Y(s) \in \mathcal{KL}$ with $\bar{\alpha}_Y, \bar{\alpha}_Y, \alpha_Y$ in Table I. □

Theorem 1 ensures the desired $\mathcal{KL}$-stability property of system (5) with respect to $\sigma$ at any iteration $i \in \mathbb{Z}_{\ge 0}$, and thus at $i = 0$, which confirms that $h^0$ is stabilizing as mentioned above. It is important to note that $\beta$ in (8) is independent of the number of iterations $i$, which makes the stability property uniform with respect to $i$.

Under extra conditions, we can derive an exponential stability result.

**Corollary 1:** Suppose Assumption 1 holds and that there exist $c_W, a_W, \bar{a}_V > 0$ and $\bar{a}_W \ge 0$ such that $\chi_W(s) \le c_W s$, $\alpha_W(s) \ge a_W s$, $\bar{\alpha}_V(s) \le \bar{a}_V s$, $\bar{\alpha}_W(s) \le \bar{a}_W s$ for any $s \ge 0$, where $\chi_W, \alpha_W, \bar{\alpha}_W$ come from SA2 and $\bar{\alpha}_V$ comes from SA3. Then, Theorem 1 holds with $\beta : (s, k) \mapsto \frac{\bar{a}_Y}{\bar{a}_Y}(1 - \tilde{a}_Y)^k s \in \exp(-\mathcal{KL})$, and $\tilde{a}_Y, \bar{a}_Y, \bar{a}_Y$ in Table I. □

**2) Near-optimality properties:** Next, we establish near-optimality properties of PI.

**Theorem 2:** Suppose Assumption 1 holds. For any $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$,

$$ (V^i - V^*)(x) \le (V^0 - V^*)(\phi(i, x, h^*)), \quad (9) $$

where $h^* \in H^*$ from (4). Moreover, for any $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$,

$$ V^i(x) - V^*(x) \le \tilde{\alpha}(\beta(\sigma(x), i)), \quad (10) $$

where $\beta \in \mathcal{KL}$ comes from Theorem 1 and $\tilde{\alpha} = \max_{\hat{s} \in [0, s]} \hat{\alpha}(\hat{s})$ is non-decreasing and positive definite function with $\hat{\alpha}$ in Table I. □

Theorem 2 provides novel characterisations of the near-optimality properties of PI. In (9), $(V^i - V^*)(x)$ is the near-optimality error term at iteration $i \in \mathbb{Z}_{\ge 0}$ and state $x \in \mathbb{R}^{n_x}$. This error is upper-bounded in (9) by $(V^0 - V^*)(\phi(i, x, h^*))$, which is the “initial” near-optimality error term for $i = 0$, but evaluated at state $\phi(i, x, h^*)$ instead of $x$. In its turn, state $\phi(i, x, h^*)$ corresponds to the $i^{th}$ time-step of the solution of (1) initialized at $x$ in closed-loop with an optimal (and typically unknown) policy $h^* \in H^*$. This bound decreases to zero point-wisely as $i \to \infty$ thanks for the stability property of system (1) in closed-loop with (4), which follows similarly as Theorem 1. However, the upper-bound in (9) is typically unknown. To overcome this possible issue, a conservative upper-bound of $(V^0 - V^*)(\phi(i, x, h^*))$ in the form of $\tilde{\alpha}(\beta(\sigma(x), i))$ is given in (10), where $\beta$ and $\tilde{\alpha}$ come from Theorems 1 and 2 and can be both computed. The fact that function $\beta$ in (8) is independent of the number of iterations $i$ is vital for (10). Indeed, as a result, the upper-bound is ensured to converge to zero as $i$ increases to infinity. We emphasize that the above near-optimality properties exploit stability to provide explicit bounds as in (10). This is in contrast to the literature, which

<footnote n="1">¹To simplify presentation, we assume $\mathbb{I} - \tilde{\alpha}_Y$ is non-decreasing. If this is not the case, we can always replace $\mathbb{I} - \tilde{\alpha}_Y$ by $s \mapsto \max_{\hat{s} \in [0, s]} (\mathbb{I} - \tilde{\alpha}_Y)(\hat{s})$.</footnote>
relies on discount factors to derive contractive properties of the sequence of value functions generated by PI [2].

**Remark 2:** The bound in (10) can be used to design stopping criteria for PI for a given near-optimality guarantee. To see this, consider a desired near-optimality target $\varepsilon_{\text{target}} : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$, which may only vanish at the origin. It suffices to iterate PI until $i \ge i^*$, where $i^*$ is such that

$$ \tilde{\alpha} (\beta(\sigma(x), i^*)) \le \varepsilon_{\text{target}}(\sigma(x)) \quad (11) $$

for every $x \in \mathbb{R}^{n_x}$. As a result, for any $i \ge i^*$ and $x \in \mathbb{R}^{n_x}$, it holds that $V^i(x) - V^*(x) \le \varepsilon_{\text{target}}(\sigma(x))$ as desired. Moreover, $\varepsilon_{\text{target}}(\sigma(x))$ may be as small as desired for $x$ in a given compact set, provided $i^*$ is sufficiently large. $\square$

A direct consequence of Theorem 2 is that the sequence of cost functions $V^i$ satisfies a uniform convergence property towards $V^*$, as formalized next.

**Proposition 1:** Suppose Assumption 1 holds. The sequence of functions $V^i$ monotonically uniformly converges to $V^*$ on level-sets of $\sigma$, i.e.,;

(i) for all $x \in \mathbb{R}^{n_x}$, $V^{i+1}(x) \le V^i(x)$;

(ii) for any $\Delta, \delta > 0$, there exists $i^* \in \mathbb{Z}_{>0}$ such that, for all $x \in \{z \in \mathbb{R}^{n_x} : \sigma(z) \le \Delta\}$ and $i \ge i^*$, $V^i(x) - V^*(x) \le \delta$. $\square$

Proposition 1 implies a monotonic uniform convergence property of $V^i$ to $V^*$. This is an additional benefit of our analysis compared to the existing PI literature, for which only monotonic point-wise convergence of the value functions to the optimal one is guaranteed in general [3,15] when the cost is not discounted as in (2).

The results of this section rely on Assumption 1, namely that PI is recursively feasible. We show next that Assumption 1 may fail to hold even when the system and the cost satisfy supposedly favorable properties.

General case

$$
\begin{align*}
\tilde{\alpha}_Y &= \alpha_Y \circ \bar{\alpha}_Y^{-1} \\
\alpha_Y &= q_W(\frac{1}{4}\alpha_W)\frac{1}{4}\alpha_W \\
\bar{\alpha}_Y &= \rho_V \circ \bar{\alpha}_V + \rho_W \circ \bar{\alpha}_W \\
\underline{\alpha}_Y &= \min \{ \rho_V \circ \chi_W^{-1}(\frac{1}{2}\alpha_W), \rho_W(\frac{1}{2}\alpha_W) \} \\
q_V &= 2\chi_W(2\mathbb{I}) \\
q_W &= \frac{1}{2}[\chi_W + (\bar{\alpha}_W + \mathbb{I}) \circ \alpha_W^{-1}(2\chi_W)]^{-1} \\
\rho_V(s) &= \int_0^s q_V(\tau)d\tau \quad \forall s \ge 0 \\
\rho_W(s) &= \int_0^s q_W(\tau)d\tau \quad \forall s \ge 0 \\
\hat{\alpha} &= \bar{\alpha}_V - \chi_W^{-1}(\max\{0, \alpha_W - \bar{\alpha}_W\})
\end{align*}
$$

<table><caption>TABLE I: Functions in Theorems 1 and 2.</caption>
  <thead>
    <tr>
      <th>When &chi;<sub>W</sub> &le; I</th>
      <th>Under the conditions of Corollary 1</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>&alpha;&#773;<sub>Y</sub> = &alpha;<sub>Y</sub> &circ; &alpha;&#773;<sub>Y</sub><sup>-1</sup></td>
      <td>&alpha;&#773;<sub>Y</sub> = <sup>a<sub>Y</sub></sup>&frasl;<sub>&alpha;&#773;<sub>Y</sub></sub></td>
    </tr>
    <tr>
      <td>&alpha;<sub>Y</sub> = &alpha;<sub>W</sub></td>
      <td>a<sub>Y</sub> = a<sub>W</sub></td>
    </tr>
    <tr>
      <td>&alpha;&#773;<sub>Y</sub> = &alpha;&#773;<sub>V</sub> + &alpha;&#773;<sub>W</sub></td>
      <td>&alpha;&#773;<sub>Y</sub> = &alpha;&#773;<sub>V</sub> + &alpha;&#773;<sub>W</sub></td>
    </tr>
    <tr>
      <td>&alpha;&#773;<sub>Y</sub> = &alpha;<sub>W</sub></td>
      <td>a<sub>Y</sub> = a<sub>W</sub></td>
    </tr>
    <tr>
      <td>&alpha;&#773; = min{&alpha;&#773;<sub>V</sub>, &alpha;&#773;<sub>Y</sub> &minus; a<sub>Y</sub>}</td>
      <td>&alpha; = min{&alpha;&#773;<sub>V</sub>, &alpha;&#773;<sub>Y</sub> &minus; a<sub>Y</sub>} &middot; I</td>
    </tr>
  </tbody>
</table>

## E. Recursive feasibility: a counter-example for PI

Consider the input-affine system

$$ x(k+1) = (1-u(k)) \max\{0, |x(k)| - 1\}, \quad (12) $$

with $x \in \mathbb{R}$, $u \in \mathcal{U}(x) = [-\delta, 1]$ with $\delta = 1/100$. Notice that $f : (x, u) \mapsto (1 - u(k)) \max\{0, |x(k)| - 1\}$ is continuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and that the admissible set

<figure><img src="image_3.png" /><figcaption>Fig. 1: $u \mapsto \ell(\bar{x} + 1, u) + V^1(f(\bar{x} + 1, u))$ has no minimum.</figcaption></figure>

of input is compact and convex. Stage cost $\ell$ is defined as $\ell(x, u) = 3|x|g_1(u) + (|x| + \frac{7}{4}|x|^2) g_2(u)$, where $g_1(u) := \max\{\min\{2(1-u), 1\}, 0\}$ and $g_2(u) := \max\{\min\{2u, 1\}, 0\}$, for any $x \in \mathbb{R}$ and $u \in \mathcal{U}(x)$. Note that $\ell(x, u) \ge 0$ for any $x \in \mathbb{R}$, $u \in \mathcal{U}(x)$ and $\ell(0, u) = 0$ for any $u \in \mathcal{U}(0)$.

Let $h^0(x) = 0$ for all $x \in \mathbb{R}$. We obtain from Algorithm 1 that $V^0(x) = 3|x|$ for $|x| \in [0, 1]$, $V^0(x) = 6|x| - 3$ for $|x| \in [1, 2]$, $V^0(x) = 9|x| - 9$ for $|x| \in [2, 3]$ and so on, hence $V^0$ is continuous. As a result, since $\mathcal{U}(x)$ is compact, $H^1(x)$ in (PI.2) is non-empty for any $x \in \mathbb{R}$. Consider $\bar{x} = \frac{18}{7}$, we have that $H^1(\bar{x}) = \{0, 1\}$: $H^1$ is set-valued at $\bar{x}$. This implies that we can consider two distinct policies $h^1, h^{1'} \in H^1$ such that $h^1(\bar{x}) = 1$ and $h^{1'}(\bar{x}) = 0$. For $x \in (\bar{x}, \infty)$, $H^1(x) = 0$, for $x \in (0, \bar{x}) \setminus \{2\}$, $H^1(x) = 1$, $H(2) = \{0, 1\}$, $H^1(0) = \mathcal{U}(0)$ and $H(x) = H(-x)$ for $x < 0$.

Let $V^1(x) := J(x, h^1)$ and $V^{1'}(x) := J(x, h^{1'})$. We note that $V^1(\bar{x}) = \ell(\bar{x}, 1) = \frac{396}{28} > \frac{381}{28} = \ell(\bar{x}, 0) + \ell(\bar{x} - 1, 1) = V^{1'}(\bar{x})$. Hence the policies $h_1$ and $h_1'$ lead to different value functions. Consider $h^1$ and $V^1$. We see in Figure 1 that $u \mapsto \ell(\bar{x} + 1, u) + V^1(f(\bar{x} + 1, u))$ has no minimum over $\mathcal{U}(\bar{x} + 1)$, but only an infimum at $u = 0$. As a result, the minimization step in (PI.2) is not feasible in this case at step $i = 2$. Algorithm 1 can thus not proceed although $f, \ell, h^0$ and $V^0$ are continuous and $\mathcal{U}(x)$ is compact and independent of $x$. Thus, $V^i$ and $h^i$ are undefined for $i \ge 2$.

To overcome this issue, we present in the next section a modification of PI that ensures recursive feasibility.

**Remark 3:** The conditions in [3] for the feasibility of (PI.2) are not satisfied in this example. Indeed, [3] requires the set $\mathcal{U}_{\lambda}^2(x) = \{u \in \mathcal{U}(x) : \ell(x, u) + V^1(f(x, u)) \le \lambda\}$ to be compact for any $x, \lambda \in \mathbb{R}$, see the discussion following [3, (7) and Proposition 3]. However, $\mathcal{U}_{\lambda}^2(\bar{x} + 1)$ is not compact for any $\lambda \ge 681/28$, as seen in Figure 1. We also note that the other condition for feasibility provided in [3, Propositions 3-4], namely $\{u \in \mathcal{U}(x) : \ell(x, u) \le \lambda\}$ compact for any $x, \lambda \in \mathbb{R}$, is verified for the considered example but does not guarantee feasibility here. $\square$

**Remark 4:** Contrary to model predictive control problems where the main obstacles for recursive feasibility are state constraints, we see via this example that the issue arises with PI even when no restriction is imposed on the set where the state lies. $\square$

## IV. POLICY ITERATION PLUS

In this section we modify PI to enforce recursive feasibility under mild conditions, and we call the modified algorithm
relies on discount factors to derive contractive properties of
the sequence of value functions generated by PI [2].

**Remark 2:** The bound in (10) can be used to design stopping criteria for PI for a given near-optimality guarantee. To see this, consider a desired near-optimality target $\varepsilon_{\text{target}} : \mathbb{R}_{\ge 0} \to \mathbb{R}_{\ge 0}$, which may only vanish at the origin. It suffices to iterate PI until $i \ge i^*$, where $i^*$ is such that

$$ \tilde{\alpha} (\beta(\sigma(x), i^*)) \le \varepsilon_{\text{target}}(\sigma(x)) \quad (11) $$

for every $x \in \mathbb{R}^{n_x}$. As a result, for any $i \ge i^*$ and $x \in \mathbb{R}^{n_x}$, it holds that $V^i(x) - V^*(x) \le \varepsilon_{\text{target}}(\sigma(x))$ as desired. Moreover, $\varepsilon_{\text{target}}(\sigma(x))$ may be as small as desired for $x$ in a given compact set, provided $i^*$ is sufficiently large. $\square$

A direct consequence of Theorem 2 is that the sequence of cost functions $V^i$ satisfies a uniform convergence property towards $V^*$, as formalized next.

**Proposition 1:** Suppose Assumption 1 holds. The sequence of functions $V^i$ monotonically uniformly converges to $V^*$ on level-sets of $\sigma$, i.e.,;

(i) for all $x \in \mathbb{R}^{n_x}$, $V^{i+1}(x) \le V^i(x)$;

(ii) for any $\Delta, \delta > 0$, there exists $i^* \in \mathbb{Z}_{>0}$ such that, for all $x \in \{z \in \mathbb{R}^{n_x} : \sigma(z) \le \Delta\}$ and $i \ge i^*$, $V^i(x) - V^*(x) \le \delta$. $\square$

Proposition 1 implies a monotonic uniform convergence property of $V^i$ to $V^*$. This is an additional benefit of our analysis compared to the existing PI literature, for which only monotonic point-wise convergence of the value functions to the optimal one is guaranteed in general [3,15] when the cost is not discounted as in (2).

The results of this section rely on Assumption 1, namely that PI is recursively feasible. We show next that Assumption 1 may fail to hold even when the system and the cost satisfy supposedly favorable properties.

General case

$$
\begin{align*}
\tilde{\alpha}_Y &= \alpha_Y \circ \bar{\alpha}_Y^{-1} \\
\alpha_Y &= q_W(\frac{1}{4}\alpha_W) \frac{1}{4}\alpha_W \\
\bar{\alpha}_Y &= \rho_V \circ \bar{\alpha}_V + \rho_W \circ \bar{\alpha}_W \\
\underline{\alpha}_Y &= \min \left\{ \rho_V \circ \chi_W^{-1}(\frac{1}{2}\alpha_W), \rho_W(\frac{1}{2}\alpha_W) \right\} \\
q_V &= 2\chi_W(2\mathbb{I}) \\
q_W &= \frac{1}{2}[\chi_W + (\bar{\alpha}_W + \mathbb{I}) \circ \alpha_W^{-1}(2\chi_W)]^{-1} \\
\rho_V(s) &= \int_0^s q_V(\tau)d\tau \quad \forall s \ge 0 \\
\rho_W(s) &= \int_0^s q_W(\tau)d\tau \quad \forall s \ge 0 \\
\hat{\alpha} &= \bar{\alpha}_V - \chi_W^{-1}(\max\{0, \alpha_W - \bar{\alpha}_W\})
\end{align*}
$$

<table><caption>TABLE I: Functions in Theorems 1 and 2.</caption>
  <thead>
    <tr>
      <th>When &chi;<sub>W</sub> &le; I</th>
      <th>Under the conditions of Corollary 1</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>&alpha;&#770;<sub>Y</sub> = &alpha;<sub>Y</sub> &circ; &alpha;&#770;<sub>Y</sub><sup>-1</sup></td>
      <td>&alpha;&#770;<sub>Y</sub> = <sup>a<sub>Y</sub></sup>&frasl;<sub>&alpha;&#770;<sub>Y</sub></sub></td>
    </tr>
    <tr>
      <td>&alpha;<sub>Y</sub> = &alpha;<sub>W</sub></td>
      <td>a<sub>Y</sub> = a<sub>W</sub></td>
    </tr>
    <tr>
      <td>&alpha;&#770;<sub>Y</sub> = &alpha;&#770;<sub>V</sub> + &alpha;&#770;<sub>W</sub></td>
      <td>&alpha;&#770;<sub>Y</sub> = &alpha;&#770;<sub>V</sub> + &alpha;&#770;<sub>W</sub></td>
    </tr>
    <tr>
      <td>&alpha;&#770;<sub>Y</sub> = &alpha;<sub>W</sub></td>
      <td>a<sub>Y</sub> = a<sub>W</sub></td>
    </tr>
    <tr>
      <td>&alpha;&#770; = min{&alpha;&#770;<sub>V</sub>, &alpha;&#770;<sub>Y</sub> &minus; a<sub>Y</sub>}</td>
      <td>&alpha; = min{&alpha;&#770;<sub>V</sub>, &alpha;&#770;<sub>Y</sub> &minus; a<sub>Y</sub>} &middot; I</td>
    </tr>
  </tbody>
</table>

E. Recursive feasibility: a counter-example for PI

Consider the input-affine system

$$ x(k+1) = (1-u(k)) \max\{0, |x(k)| - 1\}, \quad (12) $$

with $x \in \mathbb{R}$, $u \in \mathcal{U}(x) = [-\delta, 1]$ with $\delta = 1/100$. Notice that $f : (x, u) \mapsto (1 - u(k)) \max\{0, |x(k)| - 1\}$ is continuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and that the admissible set

<figure><img src="image_3.png" /><figcaption>Fig. 1: $u \mapsto \ell(\bar{x} + 1, u) + V^1(f(\bar{x} + 1, u))$ has no minimum.</figcaption></figure>

of input is compact and convex. Stage cost $\ell$ is defined as $\ell(x, u) = 3|x|g_1(u) + (|x| + \frac{7}{4}|x|^2) g_2(u)$, where $g_1(u) := \max\{\min\{2(1-u), 1\}, 0\}$ and $g_2(u) := \max\{\min\{2u, 1\}, 0\}$, for any $x \in \mathbb{R}$ and $u \in \mathcal{U}(x)$. Note that $\ell(x, u) \ge 0$ for any $x \in \mathbb{R}$, $u \in \mathcal{U}(x)$ and $\ell(0, u) = 0$ for any $u \in \mathcal{U}(0)$.

Let $h^0(x) = 0$ for all $x \in \mathbb{R}$. We obtain from Algorithm 1 that $V^0(x) = 3|x|$ for $|x| \in [0, 1]$, $V^0(x) = 6|x| - 3$ for $|x| \in [1, 2]$, $V^0(x) = 9|x| - 9$ for $|x| \in [2, 3]$ and so on, hence $V^0$ is continuous. As a result, since $\mathcal{U}(x)$ is compact, $H^1(x)$ in (PI.2) is non-empty for any $x \in \mathbb{R}$. Consider $\bar{x} = \frac{18}{7}$, we have that $H^1(\bar{x}) = \{0, 1\}$: $H^1$ is set-valued at $\bar{x}$. This implies that we can consider two distinct policies $h^1, h^{1'} \in H^1$ such that $h^1(\bar{x}) = 1$ and $h^{1'}(\bar{x}) = 0$. For $x \in (\bar{x}, \infty)$, $H^1(x) = 0$, for $x \in (0, \bar{x}) \setminus \{2\}$, $H^1(x) = 1$, $H(2) = \{0, 1\}$, $H^1(0) = \mathcal{U}(0)$ and $H(x) = H(-x)$ for $x < 0$.

Let $V^1(x) := J(x, h^1)$ and $V^{1'}(x) := J(x, h^{1'})$. We note that $V^1(\bar{x}) = \ell(\bar{x}, 1) = \frac{396}{28} > \frac{381}{28} = \ell(\bar{x}, 0) + \ell(\bar{x} - 1, 1) = V^{1'}(\bar{x})$. Hence the policies $h_1$ and $h_1'$ lead to different value functions. Consider $h^1$ and $V^1$. We see in Figure 1 that $u \mapsto \ell(\bar{x} + 1, u) + V^1(f(\bar{x} + 1, u))$ has no minimum over $\mathcal{U}(\bar{x} + 1)$, but only an infimum at $u = 0$. As a result, the minimization step in (PI.2) is not feasible in this case at step $i = 2$. Algorithm 1 can thus not proceed although $f, \ell, h^0$ and $V^0$ are continuous and $\mathcal{U}(x)$ is compact and independent of $x$. Thus, $V^i$ and $h^i$ are undefined for $i \ge 2$.

To overcome this issue, we present in the next section a modification of PI that ensures recursive feasibility.

**Remark 3:** The conditions in [3] for the feasibility of (PI.2) are not satisfied in this example. Indeed, [3] requires the set $\mathcal{U}_{\lambda}^2(x) = \{u \in \mathcal{U}(x) : \ell(x, u) + V^1(f(x, u)) \le \lambda\}$ to be compact for any $x, \lambda \in \mathbb{R}$, see the discussion following [3, (7) and Proposition 3]. However, $\mathcal{U}_{\lambda}^2(\bar{x} + 1)$ is not compact for any $\lambda \ge 681/28$, as seen in Figure 1. We also note that the other condition for feasibility provided in [3, Propositions 3-4], namely $\{u \in \mathcal{U}(x) : \ell(x, u) \le \lambda\}$ compact for any $x, \lambda \in \mathbb{R}$, is verified for the considered example but does not guarantee feasibility here. $\square$

**Remark 4:** Contrary to model predictive control problems where the main obstacles for recursive feasibility are state constraints, we see via this example that the issue arises with PI even when no restriction is imposed on the set where the state lies. $\square$

IV. POLICY ITERATION PLUS

In this section we modify PI to enforce recursive feasibility under mild conditions, and we call the modified algorithm
**Algorithm 2 Policy Iteration Plus (PI<sup>+</sup>)**

**Input:** f in (1), ℓ in (2), initial policy h<sup>0</sup> ∈ U

**Output:** Policy h<sup>*</sup><sub>r</sub><sup>,∞</sup>, cost V<sup>∞</sup><sub>r</sub>

1: **Initial evaluation step:** for all x ∈ ℝ<sup>n<sub>x</sub></sup>,

$$V_r^0(x) := J(x, h^0). \qquad (\text{PI}^+.1)$$

2: **Let** H<sup>0</sup> := H<sup>0</sup><sub>r</sub> := H<sup>*</sup><sub>r</sub><sup>,0</sup> := {h<sup>0</sup>}.

3: **for** i ∈ Z<sub>≥0</sub> **do**

4: **Policy improvement step:** for all x ∈ ℝ<sup>n<sub>x</sub></sup>,

$$H^{i+1}(x) := \underset{u \in \mathcal{U}(x)}{\operatorname{argmin}} \left\{ \ell(x, u) + V_r^i(f(x, u)) \right\}. \quad (\text{PI}^+.2)$$

5: **Policy regularization step:** for all x ∈ ℝ<sup>n<sub>x</sub></sup>,

$$H_r^{i+1}(x) := \bigcap_{\delta > 0} \overline{H^{i+1}(x + \delta \mathbb{B})}. \qquad (\text{PI}^+.3)$$

6: **Policy evaluation step:** for all x ∈ ℝ<sup>n<sub>x</sub></sup>,

$$V_r^{i+1}(x) := \min_{h_r^{i+1} \in H_r^{i+1}} J(x, h_r^{i+1}). \qquad (\text{PI}^+.4)$$

7: **Select** h<sup>*</sup><sub>r</sub><sup>,i+1</sup> ∈ H<sup>*</sup><sub>r</sub><sup>,i+1</sup> where, for all x ∈ ℝ<sup>n<sub>x</sub></sup>,

$$H_r^{*,i+1}(x) := \underset{u \in H_r^{i+1}(x)}{\operatorname{argmin}} \{\ell(x, u) + V_r^{i+1}(f(x, u))\}. \quad (\text{PI}^+.5)$$

8: **end for**

9: **return** h<sup>*</sup><sub>r</sub><sup>,∞</sup> ∈ H<sup>*</sup><sub>r</sub><sup>,∞</sup> and V<sup>∞</sup><sub>r</sub>.

PI<sup>+</sup>. We show PI<sup>+</sup> preserves the recursive (robust) stability and near-optimality properties stated for PI in Section III.

## A. The algorithm

PI<sup>+</sup> is given in Algorithm 2. At any iteration i ∈ Z<sub>≥0</sub>, to enforce the existence of a minimizer to ℓ(x, u) + V<sup>i</sup>(f(x, u)) over u ∈ U(x) in (PI.2) for any given x ∈ ℝ<sup>n<sub>x</sub></sup>, we regularize the set-valued map H<sup>i+1</sup> in (PI<sup>+</sup>.3), see [9, Def. 4.13]. For x ∈ ℝ<sup>n<sub>x</sub></sup>, the set H<sup>i+1</sup><sub>r</sub>(x) is the intersection for all δ > 0 of the closures of sets H<sup>i+1</sup>(x + δB). As a result, H<sup>i+1</sup><sub>r</sub> in (PI<sup>+</sup>.3) is outer semicontinuous<sup>2</sup> [9, Lemma 5.16]. Notice that H<sup>i+1</sup>(x) ⊆ H<sup>i+1</sup><sub>r</sub>(x) for any x ∈ ℝ<sup>n<sub>x</sub></sup> and i ∈ Z<sub>≥0</sub>.

The second modification compared to PI is on the evaluation step in (PI<sup>+</sup>.4). Given i ∈ Z<sub>≥0</sub>, for any x ∈ ℝ<sup>n<sub>x</sub></sup>, instead of (PI.3), we define V<sup>i+1</sup><sub>r</sub>(x) as the minimum cost over all selections h<sup>i+1</sup><sub>r</sub> of H<sup>i+1</sup><sub>r</sub>, see (PI<sup>+</sup>.4). Note that all selections do not necessarily lead to the same cost V<sup>i+1</sup>, see Section III-E for an example. The differences with the evaluation step in PI are that we consider H<sup>i+1</sup><sub>r</sub>, instead of H<sup>i+1</sup>, and that we do not take an arbitrary selection of this set-valued map, but only those policies which give the minimum cost, see (PI<sup>+</sup>.5). Therefore, V<sup>i+1</sup><sub>r</sub>(·) = J(·, h<sup>*</sup><sub>r</sub><sup>,i+1</sup>) for any h<sup>*</sup><sub>r</sub><sup>,i+1</sup> ∈ H<sup>*</sup><sub>r</sub><sup>,i+1</sup>.

We will show that these two modifications are essential to ensure the recursive feasibility of PI<sup>+</sup>, and we illustrate these differences by revisiting the counter-example of Section III-E. It can also be already noted that, when H<sup>i</sup> is non-empty, outer semicontinuous and single-valued at any iteration i ∈ Z<sub>≥0</sub>, e.g., H<sup>i</sup>(x) = {h<sup>i</sup>(x)} with h<sup>i</sup> continuous<sup>3</sup>, PI<sup>+</sup> reduces to PI; we elaborate more on the links between PI and PI<sup>+</sup> in Section V-D.

## B. Counter-example revisited

We consider the example in Section III-E to compare Algorithms 1 and 2. Given the problem data, V<sup>0</sup> generated by (PI.1) is equal to V<sup>0</sup><sub>r</sub> generated by (PI<sup>+</sup>.1). At iteration i = 1, we find H<sup>1</sup> by (PI.2) is equal to H<sup>1</sup> by (PI<sup>+</sup>.2). Note that H<sup>1</sup> as calculated in Section III-E is actually outer semicontinuous<sup>4</sup>, hence H<sup>1</sup> = H<sup>1</sup><sub>r</sub> in (PI<sup>+</sup>.3). Given that PI in Line 4 of Algorithm 1 is free to choose any selection of H<sup>1</sup> for the evaluation step in (PI.3), whereas PI<sup>+</sup> selects the best cost-wise policies in H<sup>1</sup><sub>r</sub> via the evaluation step (PI<sup>+</sup>.4) and selection step (PI<sup>+</sup>.5), in Section III-E we let PI select h<sup>1</sup> such that V<sup>1</sup> = J(·, h<sup>1</sup>) be upper semicontinuous for ¯x = 18/7. At iteration i = 2, such choice led to H<sup>2</sup>(¯x + 1) empty, hence the step is unfeasible and the algorithm cannot proceed. With PI<sup>+</sup>, however, step (PI<sup>+</sup>.4) finds that the best cost at ¯x is given by V<sup>1</sup> as V<sup>1</sup>(¯x) = J(¯x, h<sup>1</sup>) < J(¯x, h<sup>1</sup>) = V<sup>1</sup>(¯x). Step (PI<sup>+</sup>.5) thus selects h<sup>1</sup>. As V<sup>1</sup> = V<sup>1</sup> = J(·, h<sup>1</sup>) is in fact lower semicontinuous at ¯x, PI<sup>+</sup> at iteration i = 2 obtains H<sup>2</sup>(¯x + 1) non-empty, as desired: the step is feasible for PI<sup>+</sup>. We will see in the following how PI<sup>+</sup> formally guarantees feasibility at every iteration, i.e., that H<sup>i</sup>(x), H<sup>i</sup><sub>r</sub>(x) and H<sup>*</sup><sub>r</sub><sup>,i</sup>(x) are all non-empty for every x ∈ ℝ<sup>n<sub>x</sub></sup> and i ∈ Z<sub>≥0</sub>.

**Remark 5:** Lower semicontinuous regularizations are often considered in the optimal control literature for continuous-time systems, see, e.g., [8]. If we would consider a lower semi-continuous regularization of (x, u) ↦→ ℓ(x, u) + V<sup>i</sup>(f(x, u)) in (PI.2), instead of (PI<sup>+</sup>.3), to guarantee H<sup>i+1</sup>(x) is non-empty for any x ∈ ℝ<sup>n<sub>x</sub></sup>, it remains unclear whether: (i) V<sup>*</sup> ≤ V<sup>i+1</sup> ≤ V<sup>i</sup>; and (ii) that V<sup>i+1</sup> is the induced cost of some policy h<sup>i+1</sup>. Both are key properties that allow for V<sup>i</sup> to converge to V<sup>*</sup> when i → ∞. □

## C. Desired properties

Like in Section III-B, the objectives in this section are to provide conditions under which PI<sup>+</sup> is such that at any iteration i ∈ Z<sub>≥0</sub>:

* (recursive feasibility) for any x ∈ ℝ<sup>n<sub>x</sub></sup>, H<sup>i</sup>(x), H<sup>*</sup><sub>r</sub><sup>,i</sup>(x) are non-empty;

* (recursive stability) system (1) whose inputs are generated by PI<sup>+</sup>, i.e.,

$$x(k+1) \in f(x(k), H_r^{*,i}(x(k))) := F_r^i(x(k)), \quad (13)$$

exhibits desirable set stability properties;

* (near-optimality guarantees) explicit bounds on V<sup>i</sup><sub>r</sub>(x) - V<sup>*</sup>(x) for any x ∈ ℝ<sup>n<sub>x</sub></sup> can be derived, which asymptotically go to zero as i increases.

For convenience, we abuse notation to denote solutions to system (13) in the sequel as φ<sup>i</sup>(·, x) when initialized at some x ∈ ℝ<sup>n<sub>x</sub></sup> for any i ∈ Z<sub>≥0</sub>. As for PI, the robustness of the stability properties is deferred to Section V.

## D. Recursive feasibility

The recursive feasibility analysis rests on the next assumptions in addition to the ones from Section III-C, which are all checkable a priori.

<footnote n="2"><sup>2</sup>See [27, Definition 5.4].</footnote>

<footnote n="3"><sup>3</sup>See [27, Corollary 5.20].</footnote>

<footnote n="4"><sup>4</sup>Verified either by inspection or by invoking [27, Theorem 7.41(b)]</footnote>
**Algorithm 2 Policy Iteration Plus (PI<sup>+</sup>)**

**Input:** f in (1), ℓ in (2), initial policy h<sup>0</sup> ∈ U

**Output:** Policy h<sup>*<sub>r</sub></sup>,∞, cost V<sup>∞</sup><sub>r</sub>

1: **Initial evaluation step:** for all x ∈ ℝ<sup>n<sub>x</sub></sup>,

$$V_r^0(x) := J(x, h^0). \qquad (\text{PI}^+.1)$$

2: **Let** H<sup>0</sup> := H<sup>0</sup><sub>r</sub> := H<sup>*<sub>r</sub></sup>,0 := {h<sup>0</sup>}.

3: **for** i ∈ Z<sub>≥0</sub> **do**

4: **Policy improvement step:** for all x ∈ ℝ<sup>n<sub>x</sub></sup>,

$$H^{i+1}(x) := \underset{u \in \mathcal{U}(x)}{\operatorname{argmin}} \left\{ \ell(x, u) + V_r^i(f(x, u)) \right\}. \quad (\text{PI}^+.2)$$

5: **Policy regularization step:** for all x ∈ ℝ<sup>n<sub>x</sub></sup>,

$$H_r^{i+1}(x) := \bigcap_{\delta > 0} \overline{H^{i+1}(x + \delta \mathbb{B})}. \qquad (\text{PI}^+.3)$$

6: **Policy evaluation step:** for all x ∈ ℝ<sup>n<sub>x</sub></sup>,

$$V_r^{i+1}(x) := \min_{h_r^{i+1} \in H_r^{i+1}} J(x, h_r^{i+1}). \qquad (\text{PI}^+.4)$$

7: **Select** h<sup>*<sub>r</sub></sup>,i+1 ∈ H<sup>*<sub>r</sub></sup>,i+1 where, for all x ∈ ℝ<sup>n<sub>x</sub></sup>,

$$H_r^{*i+1}(x) := \underset{u \in H_r^{i+1}(x)}{\operatorname{argmin}} \{\ell(x, u) + V_r^{i+1}(f(x, u))\}. \quad (\text{PI}^+.5)$$

8: **end for**

9: **return** h<sup>*<sub>r</sub></sup>,∞ ∈ H<sup>*<sub>r</sub></sup>,∞ and V<sup>∞</sup><sub>r</sub>.

PI<sup>+</sup>. We show PI<sup>+</sup> preserves the recursive (robust) stability and near-optimality properties stated for PI in Section III.

A. The algorithm

PI<sup>+</sup> is given in Algorithm 2. At any iteration i ∈ Z<sub>≥0</sub>, to enforce the existence of a minimizer to ℓ(x, u) + V<sup>i</sup>(f(x, u)) over u ∈ U(x) in (PI.2) for any given x ∈ ℝ<sup>n<sub>x</sub></sup>, we regularize the set-valued map H<sup>i+1</sup> in (PI<sup>+.3</sup>), see [9, Def. 4.13]. For x ∈ ℝ<sup>n<sub>x</sub></sup>, the set H<sup>i+1</sup><sub>r</sub>(x) is the intersection for all δ > 0 of the closures of sets H<sup>i+1</sup>(x + δB). As a result, H<sup>i+1</sup><sub>r</sub> in (PI<sup>+.3</sup>) is outer semicontinuous<sup>2</sup> [9, Lemma 5.16]. Notice that H<sup>i+1</sup>(x) ⊆ H<sup>i+1</sup><sub>r</sub>(x) for any x ∈ ℝ<sup>n<sub>x</sub></sup> and i ∈ Z<sub>≥0</sub>.

The second modification compared to PI is on the evaluation step in (PI<sup>+.4</sup>). Given i ∈ Z<sub>≥0</sub>, for any x ∈ ℝ<sup>n<sub>x</sub></sup>, instead of (PI.3), we define V<sup>i+1</sup><sub>r</sub>(x) as the minimum cost over all selections h<sup>i+1</sup><sub>r</sub> of H<sup>i+1</sup><sub>r</sub>, see (PI<sup>+.4</sup>). Note that all selections do not necessarily lead to the same cost V<sup>i+1</sup>, see Section III-E for an example. The differences with the evaluation step in PI are that we consider H<sup>i+1</sup><sub>r</sub>, instead of H<sup>i+1</sup>, and that we do not take an arbitrary selection of this set-valued map, but only those policies which give the minimum cost, see (PI<sup>+.5</sup>). Therefore, V<sup>i+1</sup><sub>r</sub>(·) = J(·, h<sup>*<sub>r</sub></sup>,i+1) for any h<sup>*<sub>r</sub></sup>,i+1 ∈ H<sup>*<sub>r</sub></sup>,i+1.

We will show that these two modifications are essential to ensure the recursive feasibility of PI<sup>+</sup>, and we illustrate these differences by revisiting the counter-example of Section III-E. It can also be already noted that, when H<sup>i</sup> is non-empty, outer semicontinuous and single-valued at any iteration i ∈ Z<sub>≥0</sub>, e.g., H<sup>i</sup>(x) = {h<sup>i</sup>(x)} with h<sup>i</sup> continuous<sup>3</sup>, PI<sup>+</sup> reduces to PI; we elaborate more on the links between PI and PI<sup>+</sup> in Section V-D.

B. Counter-example revisited

We consider the example in Section III-E to compare Algorithms 1 and 2. Given the problem data, V<sup>0</sup> generated by (PI.1) is equal to V<sup>0</sup><sub>r</sub> generated by (PI<sup>+.1</sup>). At iteration i = 1, we find H<sup>1</sup> by (PI.2) is equal to H<sup>1</sup> by (PI<sup>+.2</sup>). Note that H<sup>1</sup> as calculated in Section III-E is actually outer semicontinuous<sup>4</sup>, hence H<sup>1</sup> = H<sup>1</sup><sub>r</sub> in (PI<sup>+.3</sup>). Given that PI in Line 4 of Algorithm 1 is free to choose any selection of H<sup>1</sup> for the evaluation step in (PI.3), whereas PI<sup>+</sup> selects the best cost-wise policies in H<sup>1</sup><sub>r</sub> via the evaluation step (PI<sup>+.4</sup>) and selection step (PI<sup>+.5</sup>), in Section III-E we let PI select h<sup>1</sup> such that V<sup>1</sup> = J(·, h<sup>1</sup>) be upper semicontinuous for ¯x = 18/7. At iteration i = 2, such choice led to H<sup>2</sup>(¯x + 1) empty, hence the step is unfeasible and the algorithm cannot proceed. With PI<sup>+</sup>, however, step (PI<sup>+.4</sup>) finds that the best cost at ¯x is given by V<sup>1</sup> as V<sup>1</sup>(¯x) = J(¯x, h<sup>1</sup>) < J(¯x, h<sup>1</sup>) = V<sup>1</sup>(¯x). Step (PI<sup>+.5</sup>) thus selects h<sup>1</sup>. As V<sup>1</sup> = V<sup>1</sup> = J(·, h<sup>1</sup>) is in fact lower semicontinuous at ¯x, PI<sup>+</sup> at iteration i = 2 obtains H<sup>2</sup>(¯x + 1) non-empty, as desired: the step is feasible for PI<sup>+</sup>. We will see in the following how PI<sup>+</sup> formally guarantees feasibility at every iteration, i.e., that H<sup>i</sup>(x), H<sup>i</sup><sub>r</sub>(x) and H<sup>*<sub>r</sub></sup>,i(x) are all non-empty for every x ∈ ℝ<sup>n<sub>x</sub></sup> and i ∈ Z<sub>≥0</sub>.

**Remark 5:** Lower semicontinuous regularizations are often considered in the optimal control literature for continuous-time systems, see, e.g., [8]. If we would consider a lower semi-continuous regularization of (x, u) ↦→ ℓ(x, u) + V<sup>i</sup>(f(x, u)) in (PI.2), instead of (PI<sup>+.3</sup>), to guarantee H<sup>i+1</sup>(x) is non-empty for any x ∈ ℝ<sup>n<sub>x</sub></sup>, it remains unclear whether: (i) V<sup>*</sup> ≤ V<sup>i+1</sup> ≤ V<sup>i</sup>; and (ii) that V<sup>i+1</sup> is the induced cost of some policy h<sup>i+1</sup>. Both are key properties that allow for V<sup>i</sup> to converge to V<sup>*</sup> when i → ∞. □

C. Desired properties

Like in Section III-B, the objectives in this section are to provide conditions under which PI<sup>+</sup> is such that at any iteration i ∈ Z<sub>≥0</sub>:

* (recursive feasibility) for any x ∈ ℝ<sup>n<sub>x</sub></sup>, H<sup>i</sup>(x), H<sup>*<sub>r</sub></sup>,i(x) are non-empty;

* (recursive stability) system (1) whose inputs are generated by PI<sup>+</sup>, i.e.,

$$x(k+1) \in f(x(k), H_r^{*i}(x(k))) := F_r^i(x(k)), \quad (13)$$

exhibits desirable set stability properties;

* (near-optimality guarantees) explicit bounds on V<sup>i</sup><sub>r</sub>(x) - V<sup>*</sup>(x) for any x ∈ ℝ<sup>n<sub>x</sub></sup> can be derived, which asymptotically go to zero as i increases.

For convenience, we abuse notation to denote solutions to system (13) in the sequel as φ<sup>i</sup>(·, x) when initialized at some x ∈ ℝ<sup>n<sub>x</sub></sup> for any i ∈ Z<sub>≥0</sub>. As for PI, the robustness of the stability properties is deferred to Section V.

D. Recursive feasibility

The recursive feasibility analysis rests on the next assumptions in addition to the ones from Section III-C, which are all checkable a priori.

<footnote n="2"><sup>2</sup>See [27, Definition 5.4].</footnote>

<footnote n="3"><sup>3</sup>See [27, Corollary 5.20].</footnote>

<footnote n="4"><sup>4</sup>Verified either by inspection or by invoking [27, Theorem 7.41(b)]</footnote>
**Assumption 2:** The following holds.

(i) The function $f$ and the stage cost function $\ell$ are continuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$.

(ii) $\ell$ is level-bounded in $u$, locally uniform in $x$.

(iii) $\mathcal{U}$ is outer semicontinuous on $\mathbb{R}^{n_x}$.

(iv) $V_r^0 = J(x, h^0)$ is lower semicontinuous on $\mathbb{R}^{n_x}$.

(v) For all $\Delta > 0$, the set $\{x \in \mathbb{R}^{n_x} : \sigma(x) \le \Delta\}$ is compact. $\square$

Item (i) of Assumption 2 imposes regularity conditions on model $f$ and stage cost $\ell$. Item (ii) of Assumption 2 is satisfied when $\ell(x, u) = \ell_1(x, u) + \ell_2(u)$ for any $(x, u) \in \mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ with $\ell_1(x, u) \ge 0$ and $\ell_2$ radially unbounded, i.e., $\ell_2(u) \to +\infty$ as $|u| \to +\infty$ for instance. A typical example of $\ell_2$ radially unbounded being $\ell_2(u) = u^\top Ru$ with $R \in \mathbb{R}^{n_u \times n_u}$ symmetric and positive definite; note that this property also trivially holds when $\mathcal{U}$ is independent of $x$ and compact. On the other hand, item (iii) of Assumption 2 is satisfied when $\mathcal{U}(\cdot) = \mathbb{R}^{n_u}$ or $\mathcal{U}(\cdot)$ is independent of $x$ and compact for example. Item (iv) of Assumption 2 is a mild regularity assumption on the initial cost function, which holds when $V_r^0$ is continuous on $\mathbb{R}^{n_x}$. Finally, item (v) of Assumption 2 implies $\sigma$ is radially unbounded, which implies that the attractor $\{x \in \mathbb{R}^{n_x} : \sigma(x) = 0\}$ is compact.

**Remark 6:** The example in Section III-E verifies SA1-3 and Assumption 2 with $\sigma(\cdot) = |\cdot|$, $W = \bar{\alpha}_W = 0$, $\alpha_W = \chi_W = I$ and $\bar{\alpha}_V = V_r^0 \circ \sigma$ where $V_r^0 = V^0$. As a consequence, the objectives stated for $\mathrm{PI}^+$ in Section IV-C are satisfied for this example in view of the results presented next. $\square$

The next theorem ensures recursive feasibility for $\mathrm{PI}^+$. For technical reasons, we prove recursive feasibility in conjunction with recursive stability for $\mathrm{PI}^+$ in Appendix I.

**Theorem 3:** Suppose Assumption 2 holds, $H^i(x), H_r^i(x)$ and $H_r^{*,i}(x)$ are non-empty for any $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$. $\square$

Given the recursive feasibility of $\mathrm{PI}^+$ in Theorem 3, we now establish that the properties of $\mathrm{PI}$ in Section III-D also hold for $\mathrm{PI}^+$.

## E. Recursive stability

The next theorem ensures recursive stability for $\mathrm{PI}^+$. Its proof is given in Appendix I.

**Theorem 4:** Suppose Assumption 2 holds. For any $i \in \mathbb{Z}_{\ge 0}$, for any $x \in \mathbb{R}^{n_x}$, solution $\phi^i$ to (13) and $k \in \mathbb{Z}_{\ge 0}$,

$$ \sigma(\phi^i(k, x)) \le \beta(\sigma(x), k) \quad (14) $$

where $\beta : (k, s) \mapsto \underline{\alpha}_Y^{-1} \circ (I - \tilde{\alpha}_Y)^{(k)} \circ \bar{\alpha}_Y(s) \in \mathcal{KL}$ with $\underline{\alpha}_Y, \bar{\alpha}_Y, \tilde{\alpha}_Y$ in Table I. $\square$

Similar to Theorem 1, Theorem 4 is a $\mathcal{KL}$-stability property of system (13) with respect to $\sigma$, with $\beta$ in (14). As previously mentioned, when $\sigma$ is a proper indicator of a compact set $A$, (14) ensures that this set is uniformly globally asymptotically stable.

As in Corollary 1, when some of the functions in SA1-3 satisfy stronger conditions, the stability property in Theorem 4 becomes exponential. A sketch of the proof is given in Appendix I-H.

**Corollary 2:** Suppose Assumption 2 holds and that there exist $c_W, a_W, \bar{a}_V > 0$ and $\bar{a}_W \ge 0$ such that $\chi_W(s) \le c_W s$, $\alpha_W(s) \ge a_W s$, $\bar{\alpha}_V(s) \le \bar{a}_V s$, $\bar{\alpha}_W(s) \le \bar{a}_W s$ for any $s \ge 0$, where $\chi_W, \alpha_W, \bar{\alpha}_W$ come from SA2 and $\bar{\alpha}_V$ comes from SA3. Then, Theorem 4 holds with $\beta : (s, k) \mapsto \frac{\bar{a}_Y}{\bar{a}_Y}(1 - \tilde{a}_Y)^k s \in \exp(-KL)$, and $\tilde{a}_Y, \bar{a}_Y, \underline{a}_Y$ in Table I. $\square$

## F. Near-optimality properties

Similar to Theorem 2, the next theorem provides near-optimality guarantees for $\mathrm{PI}^+$. Its proof is given in the Appendix II-A.

**Theorem 5:** Suppose Assumption 2 holds. For any $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$,

$$ (V_r^i - V^*)(x) \le (V_r^0 - V^*)(\phi(i, x, h^*)) \quad (15) $$

where $h^* \in H^*$ from (4). Moreover, for any $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$

$$ V_r^i(x) - V^*(x) \le \tilde{\alpha} (\beta(\sigma(x), i)) \quad (16) $$

where $\beta \in KL$ comes from Theorem 4 and $\tilde{\alpha} = \max_{\hat{s} \in [0, s]} \hat{\alpha}(\hat{s})$ is non-decreasing and positive definite function with $\hat{\alpha}$ in Table I. $\square$

Similar to Theorem 2, Theorem 5 provides near-optimality guarantees to $\mathrm{PI}^+$. We conclude that $V_r^i \to V^*$ as $i \to \infty$ point-wisely, as $\beta \in KL$ and $\lim_{i \to \infty} \sigma(\phi(i, x, h^*)) = 0$ by following similar lines as in the proof of Theorem 4. This qualitative property of $\mathrm{PI}^+$ is strengthened in (16) by employing a conservative bound for (15) in the form of $\tilde{\alpha}(\beta(\sigma(x), i))$, whose formulas for $\beta$ and $\tilde{\alpha}$ are given in Theorems 4 and 5 in terms of functions in Table I and are thus known. Again, the fact that function $\beta$ in (14) is independent of the number of iterations $i$ ensures that the upper-bound converges to zero as $i$ increases to infinity.

**Remark 7:** As in Remark 1, the bound in (16) can be used to design stopping criteria for $\mathrm{PI}^+$ to ensure a desired level of near-optimality. $\square$

A direct consequence of Theorem 5 is that the sequence of cost functions $V_r^i$ converge compactly to $V^*$, as formalized next.

**Proposition 2:** Suppose Assumption 2 holds. The sequence of functions $V_r^i$ monotonically compactly converges to $V^*$, i.e.:

(i) for all $x \in \mathbb{R}^{n_x}$, $V_r^{i+1}(x) \le V_r^i(x)$;

(ii) for any compact set $K \subset \mathbb{R}^{n_x}$ and $\delta > 0$ there exists $i^* \in \mathbb{Z}_{\ge 0}$ such that for any $x \in K$ and $i \ge i^*$, $V_r^i(x) - V^*(x) \le \delta$ holds. $\square$

Proposition 2 establishes the uniform convergence of $V_r^i$ to $V^*$ on any compact set $K \subset \mathbb{R}^{n_x}$, which, compared to Proposition 1, comes from the fact that level sets of $\sigma$ are compact in view of item (iv) of Assumption 2.

## V. ROBUST STABILITY

So far, we have established stability properties for system (1), whose inputs are generated either by $\mathrm{PI}$ or $\mathrm{PI}^+$. However, it is not clear yet whether these stability properties are robust to uncertainties and perturbations. Indeed, the corresponding closed-loop systems are given by difference inclusions and it

<footnote n="5">⁵See footnote 1 in page 4 in Section III-D.</footnote>
**Assumption 2:** The following holds.

(i) The function $f$ and the stage cost function $\ell$ are continuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$.

(ii) $\ell$ is level-bounded in $u$, locally uniform in $x$.

(iii) $\mathcal{U}$ is outer semicontinuous on $\mathbb{R}^{n_x}$.

(iv) $V_r^0 = J(x, h^0)$ is lower semicontinuous on $\mathbb{R}^{n_x}$.

(v) For all $\Delta > 0$, the set $\{x \in \mathbb{R}^{n_x} : \sigma(x) \le \Delta\}$ is compact. $\square$

Item (i) of Assumption 2 imposes regularity conditions on model $f$ and stage cost $\ell$. Item (ii) of Assumption 2 is satisfied when $\ell(x, u) = \ell_1(x, u) + \ell_2(u)$ for any $(x, u) \in \mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ with $\ell_1(x, u) \ge 0$ and $\ell_2$ radially unbounded, i.e., $\ell_2(u) \to +\infty$ as $|u| \to +\infty$ for instance. A typical example of $\ell_2$ radially unbounded being $\ell_2(u) = u^\top Ru$ with $R \in \mathbb{R}^{n_u \times n_u}$ symmetric and positive definite; note that this property also trivially holds when $\mathcal{U}$ is independent of $x$ and compact. On the other hand, item (iii) of Assumption 2 is satisfied when $\mathcal{U}(\cdot) = \mathbb{R}^{n_u}$ or $\mathcal{U}(\cdot)$ is independent of $x$ and compact for example. Item (iv) of Assumption 2 is a mild regularity assumption on the initial cost function, which holds when $V_r^0$ is continuous on $\mathbb{R}^{n_x}$. Finally, item (v) of Assumption 2 implies $\sigma$ is radially unbounded, which implies that the attractor $\{x \in \mathbb{R}^{n_x} : \sigma(x) = 0\}$ is compact.

**Remark 6:** The example in Section III-E verifies SA1-3 and Assumption 2 with $\sigma(\cdot) = |\cdot|$, $W = \bar{\alpha}_W = 0$, $\alpha_W = \chi_W = \mathbb{I}$ and $\bar{\alpha}_V = V_r^0 \circ \sigma$ where $V_r^0 = V^0$. As a consequence, the objectives stated for $\mathrm{PI}^+$ in Section IV-C are satisfied for this example in view of the results presented next. $\square$

The next theorem ensures recursive feasibility for $\mathrm{PI}^+$. For technical reasons, we prove recursive feasibility in conjunction with recursive stability for $\mathrm{PI}^+$ in Appendix I.

**Theorem 3:** Suppose Assumption 2 holds, $H^i(x)$, $H_r^i(x)$ and $H_r^{*,i}(x)$ are non-empty for any $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$. $\square$

Given the recursive feasibility of $\mathrm{PI}^+$ in Theorem 3, we now establish that the properties of $\mathrm{PI}$ in Section III-D also hold for $\mathrm{PI}^+$.

## E. Recursive stability

The next theorem ensures recursive stability for $\mathrm{PI}^+$. Its proof is given in Appendix I.

**Theorem 4:** Suppose Assumption 2 holds. For any $i \in \mathbb{Z}_{\ge 0}$, for any $x \in \mathbb{R}^{n_x}$, solution $\phi^i$ to (13) and $k \in \mathbb{Z}_{\ge 0}$,

$$ \sigma(\phi^i(k, x)) \le \beta(\sigma(x), k) \quad (14) $$

where $\beta : (k, s) \mapsto \frac{1}{\bar{\alpha}_Y^{-1}} \circ (\mathbb{I} - \tilde{\alpha}_Y)^{(k)} \circ \bar{\alpha}_Y(s) \in \mathcal{KL}$ with $\bar{\alpha}_Y, \tilde{\alpha}_Y, \tilde{\alpha}_Y$ in Table I. $\square$

Similar to Theorem 1, Theorem 4 is a $\mathcal{KL}$-stability property of system (13) with respect to $\sigma$, with $\beta$ in (14). As previously mentioned, when $\sigma$ is a proper indicator of a compact set $A$, (14) ensures that this set is uniformly globally asymptotically stable.

As in Corollary 1, when some of the functions in SA1-3 satisfy stronger conditions, the stability property in Theorem 4 becomes exponential. A sketch of the proof is given in Appendix I-H.

**Corollary 2:** Suppose Assumption 2 holds and that there exist $c_W, a_W, \bar{a}_V > 0$ and $\bar{a}_W \ge 0$ such that $\chi_W(s) \le c_W s$, $\alpha_W(s) \ge a_W s$, $\bar{\alpha}_V(s) \le \bar{a}_V s$, $\bar{\alpha}_W(s) \le \bar{a}_W s$ for any $s \ge 0$, where $\chi_W, \alpha_W, \bar{\alpha}_W$ come from SA2 and $\bar{\alpha}_V$ comes from SA3. Then, Theorem 4 holds with $\beta : (s, k) \mapsto \frac{\bar{a}_Y}{\bar{a}_Y}(1 - \tilde{a}_Y)^k s \in \exp(-KL)$, and $\tilde{a}_Y, \bar{a}_Y, \underline{a}_Y$ in Table I. $\square$

## F. Near-optimality properties

Similar to Theorem 2, the next theorem provides near-optimality guarantees for $\mathrm{PI}^+$. Its proof is given in the Appendix II-A.

**Theorem 5:** Suppose Assumption 2 holds. For any $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$,

$$ (V_r^i - V^*)(x) \le (V_r^0 - V^*)(\phi(i, x, h^*)), \quad (15) $$

where $h^* \in H^*$ from (4). Moreover, for any $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$

$$ V_r^i(x) - V^*(x) \le \tilde{\alpha} (\beta(\sigma(x), i)), \quad (16) $$

where $\beta \in KL$ comes from Theorem 4 and $\tilde{\alpha} = \max_{\hat{s} \in [0, s]} \hat{\alpha}(\hat{s})$ is non-decreasing and positive definite function with $\hat{\alpha}$ in Table I. $\square$

Similar to Theorem 2, Theorem 5 provides near-optimality guarantees to $\mathrm{PI}^+$. We conclude that $V_r^i \to V^*$ as $i \to \infty$ point-wisely, as $\beta \in KL$ and $\lim_{i \to \infty} \sigma(\phi(i, x, h^*)) = 0$ by following similar lines as in the proof of Theorem 4. This qualitative property of $\mathrm{PI}^+$ is strengthened in (16) by employing a conservative bound for (15) in the form of $\tilde{\alpha}(\beta(\sigma(x), i))$, whose formulas for $\beta$ and $\tilde{\alpha}$ are given in Theorems 4 and 5 in terms of functions in Table I and are thus known. Again, the fact that function $\beta$ in (14) is independent of the number of iterations $i$ ensures that the upper-bound converges to zero as $i$ increases to infinity.

**Remark 7:** As in Remark 1, the bound in (16) can be used to design stopping criteria for $\mathrm{PI}^+$ to ensure a desired level of near-optimality. $\square$

A direct consequence of Theorem 5 is that the sequence of cost functions $V_r^i$ converge compactly to $V^*$, as formalized next.

**Proposition 2:** Suppose Assumption 2 holds. The sequence of functions $V_r^i$ monotonically compactly converges to $V^*$, i.e.:

(i) for all $x \in \mathbb{R}^{n_x}$, $V_r^{i+1}(x) \le V_r^i(x)$;

(ii) for any compact set $K \subset \mathbb{R}^{n_x}$ and $\delta > 0$ there exists $i^* \in \mathbb{Z}_{> 0}$ such that for any $x \in K$ and $i \ge i^*$, $V_r^i(x) - V^*(x) \le \delta$ holds. $\square$

Proposition 2 establishes the uniform convergence of $V_r^i$ to $V^*$ on any compact set $K \subset \mathbb{R}^{n_x}$, which, compared to Proposition 1, comes from the fact that level sets of $\sigma$ are compact in view of item (iv) of Assumption 2.

## V. ROBUST STABILITY

So far, we have established stability properties for system (1), whose inputs are generated either by $\mathrm{PI}$ or $\mathrm{PI}^+$. However, it is not clear yet whether these stability properties are robust to uncertainties and perturbations. Indeed, the corresponding closed-loop systems are given by difference inclusions and it

<footnote n="5">⁵See footnote 1 in page 4 in Section III-D.</footnote>
has been shown in [12] in the context of model predictive control that difference inclusion may have zero robustness despite them satisfying so-called KL-stability properties like in Theorems 1 and 4, in the sense that a vanishing arbitrarily small perturbation, may destroy asymptotic stability properties established for the unperturbed system. It is thus vital that the stability properties stated in Section IV-E come with some nominal robustness properties. This is the focus of this section. The results are derived for system (13) controlled by PI+, but the same results follow when the inputs are generated by PI as explained in Section V-D.

A. Nominal robustness definition

We consider the notion of nominal robustness in [21], which we recall below in the context of this paper. Let $\mathcal{X} \subseteq \mathbb{R}^{n_x}$ be open and such that $F_r^i(x) \subseteq \mathcal{X}$, where $F_r^i$ comes from (13), for any $x \in \mathcal{X}$ and $i \in \mathbb{Z}_{\ge 0}$. We introduce a continuous function $\rho: \mathcal{X} \to \mathbb{R}_{\ge 0}$ to perturb the set-valued map $F_r^i$ in (13) for $i \in \mathbb{Z}_{\ge 0}$ as

$$F_{r,\rho}^{i}(x) := \{\eta \in \mathbb{R}^{n_x} : \eta \in \{v\} + \rho(v)\mathbb{B}, v \in F_{r}^{i}(x + \rho(x)\mathbb{B})\}. \quad (17)$$

We say that $F_{r,\rho}^i$ is the $\rho$-perturbation of $F_r^i$. Given $F_{r,\rho}^i$, we have the next difference inclusion

$$x(k+1) \in F_{r,\rho}^{i}(x(k)). \quad (18)$$

System (18) corresponds to system (13) perturbed by $\rho$, in the sense of (17). Note that $F_r^i = F_{r,0}^i$ and $F_r^i \subseteq F_{r,\rho}^i$. We denote solutions to system (18) as $\phi_\rho^i(\cdot, x)$ when initialized at $x \in \mathbb{R}^{n_x}$ for $i \in \mathbb{Z}_{\ge 0}$.

Theorem 4 establishes a KL-stability property with respect to $\sigma$ for which the attractor is $\mathcal{A} = \{x \in \mathbb{R}^{n_x} : \sigma(x) = 0\}$ when $\sigma$ is a proper indicator of $\mathcal{A}$. To define robust stability as in [21], we consider instead a two-measure KL-stability property with respect to $(\sigma_1, \sigma_2)$ where $\sigma_1, \sigma_2: \mathcal{X} \to \mathbb{R}_{\ge 0}$ are continuous. Given $\rho$ in (17), the attractor of perturbed system (18) becomes

$$\mathcal{A}_{\rho}^{i} := \{ \xi \in \mathcal{X} : \sup_{k \in \mathbb{Z}_{\ge 0}} \sigma_{1}(\phi_{\rho}^{i}(k, \xi)) = 0 \}. \quad (19)$$

We are ready to define robust KL-stability.

Definition 2 ([21]): Given $i \in \mathbb{Z}_{\ge 0}$ and $\sigma_1, \sigma_2: \mathcal{X} \to \mathbb{R}_{\ge 0}$ continuous, system (13) is robustly KL-stable with respect to $(\sigma_1, \sigma_2)$ on $\mathcal{X}$ if there exists a continuous function $\rho: \mathcal{X} \to \mathbb{R}_{\ge 0}$ such that the following holds.

(i) For all $x \in \mathcal{X}$, $\{x\} + \rho(x)\mathbb{B} \subset \mathcal{X}$.

(ii) For all $x \in \mathcal{X} \setminus \mathcal{A}_0^i$, $\rho(x) > 0$.

(iii) $\mathcal{A}_{\rho}^i = \mathcal{A}_0^i$.

(iv) System (18) is KL-stable with respect to $(\sigma_1, \sigma_2)$ on $\mathcal{X}$, i.e., there exists $\beta \in \mathcal{KL}$ such that $\sigma_1(\phi_\rho^i(k, x)) \le \beta(\sigma_2(x), k)$ for every $x \in \mathcal{X}$ and $k \in \mathbb{Z}_{\ge 0}$. When $\sigma_1 = \sigma_2 = \sigma$, (13) is KL-stable with respect to $\sigma$. $\square$

Item (i) of Definition 2 imposes a condition on $\rho$ so that $F_{r,\rho}^i(\mathcal{X}) \subseteq \mathcal{X}$ for any $i \in \mathbb{Z}_{\ge 0}$, as $F_r^i(x) \subseteq \mathcal{X}$ for all $x \in \mathcal{X}$. Item (ii) of Definition 2 in turn requires that $\rho$ is non-zero outside the attractor $\mathcal{A}_0^i$ corresponding to (19) with $\rho = 0$. Then, item (iii) of Definition 2 states that the perturbed attractor $\mathcal{A}_{\rho}^i$ is the same as the unperturbed one $\mathcal{A}_0^i$. Finally,

item (iv) of Definition 2 says that the perturbed system is KL-stable with respect to $(\sigma_1, \sigma_2)$.

As advocated in [12], if a difference inclusion is KL-stable with respect to some measures $(\sigma_1, \sigma_2)$, it is not necessarily robustly KL-stable. In other words, the (unperturbed) system may have zero robustness. In the context of this paper, sufficient conditions to conclude robust KL-stability with respect to some pair $(\sigma_1, \sigma_2)$ on $\mathcal{X}$ for system (13) with $i \in \mathbb{Z}_{\ge 0}$ are that:

(a) $F_r^i(x)$ is non-empty and compact for any $x \in \mathcal{X}$;

(b) the Lyapunov function used to establish the stability of the unperturbed system is continuous.

The next lemma states that item (a) above holds.

Lemma 1: Suppose Assumption 2 holds. For any $i \in \mathbb{Z}_{\ge 0}$, $F_r^i(x)$ is compact and non-empty for any $x \in \mathbb{R}^{n_x}$. $\square$

Proof: Let $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$, since $f$ is continuous by item (i) of Assumption 2, the compactness of $F_r^i(x) = f(x, H_{r,i}^*(x))$ follows from the compactness of $H_{r,i}^*$, which we now show. To this end, we prove that the conditions of [27, Theorem 1.17(a)] are verified by invoking similar arguments to those employed in the proof of Lemma 4 in Appendix I-E. Consider $g_r^i: (x, u) \mapsto \ell(x, u) + V_r^i(f(x, u)) + \delta_{H_r^i(x)}(u)$. On the one hand, $g_r^i$ is proper and level-bounded in $u$, locally uniform in $x$, for the same reasons as stated in the proof of Lemma 4. On the other hand, $(x, u) \mapsto \ell(x, u) + V_r^i(f(x, u))$ is lower semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$, in view of the lower semicontinuity of $V_r^i$ on $\mathbb{R}^{n_x}$ from Lemma 9 in Appendix I and the continuity of $f$ and $\ell$ by Assumption 2. Moreover, $\delta_{H_r^i(\cdot)}(\cdot)$ is lower semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$, as this holds from Lemma 12 in Section V since $H_r^i$ is an outer semicontinuous set-valued in view of [9, Lemma 5.16]. Thus $g_r^i$ is lower semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and all the conditions of [27, Theorem 1.17(a)] hold, we can therefore apply it to conclude $H_r^{*,i+1}(x)$ in (PI$^+$.2) is non-empty and compact at $x \in \mathbb{R}^{n_x}$. Since $x$ has been selected arbitrarily, the desired result follows. $\blacksquare$

Regarding item (b), it turns out that the Lyapunov function used to establish KL-stability in Section IV-E, namely $Y^i = \rho_V(V_r^i) + \rho_W(W)$, is only guaranteed to be lower semicontinuous. Indeed, while $W$, $\rho_V$ and $\rho_W$ are continuous, $V_r^i$ is only shown to be lower semicontinuous in Lemma 9 given in Appendix I. Thus we will require a different analysis or extra assumptions as presented next.

B. Robust semi-global practical stability

An alternative Lyapunov function to analyse the stability of (13) is $Y^* := \rho_V(V^*) + \rho_W(W)$, where $V^*$ is the optimal value function defined in (3), which is known to be continuous in view of [26, Theorem 3] under a mild additional assumption on $\mathcal{U}$ that can be checked a priori$^6$.

Assumption 3: Set-valued map $\mathcal{U}$ is continuous and locally bounded$^7$ on $\mathbb{R}^{n_x}$. $\square$

However, function $Y^*$ only allows to establish a semiglobal practical KL-stability property under SA1–3 for $i$ is sufficiently large so that, somehow, $V_r^i$ is sufficiently close to $V^*$

<footnote>$^6$SA1 is implied by SA2, SA3 and Assumptions 2-3, see [26, Theorem 3].</footnote>

<footnote>$^7$See [27, Definition 5.4] and [27, Definition 5.14], respectively.</footnote>
has been shown in [12] in the context of model predictive control that difference inclusion may have zero robustness despite them satisfying so-called KL-stability properties like in Theorems 1 and 4, in the sense that a vanishing arbitrarily small perturbation, may destroy asymptotic stability properties established for the unperturbed system. It is thus vital that the stability properties stated in Section IV-E come with some nominal robustness properties. This is the focus of this section. The results are derived for system (13) controlled by PI+, but the same results follow when the inputs are generated by PI as explained in Section V-D.

A. Nominal robustness definition

We consider the notion of nominal robustness in [21], which we recall below in the context of this paper. Let $\mathcal{X} \subseteq \mathbb{R}^{n_x}$ be open and such that $F_r^i(x) \subseteq \mathcal{X}$, where $F_r^i$ comes from (13), for any $x \in \mathcal{X}$ and $i \in \mathbb{Z}_{\ge 0}$. We introduce a continuous function $\rho: \mathcal{X} \to \mathbb{R}_{\ge 0}$ to perturb the set-valued map $F_r^i$ in (13) for $i \in \mathbb{Z}_{\ge 0}$ as

$$F_{r,\rho}^{i}(x) := \{\eta \in \mathbb{R}^{n_x} : \eta \in \{v\} + \rho(v)\mathbb{B}, v \in F_{r}^{i}(x + \rho(x)\mathbb{B})\}. \quad (17)$$

We say that $F_{r,\rho}^i$ is the $\rho$-perturbation of $F_r^i$. Given $F_{r,\rho}^i$, we have the next difference inclusion

$$x(k+1) \in F_{r,\rho}^{i}(x(k)). \quad (18)$$

System (18) corresponds to system (13) perturbed by $\rho$, in the sense of (17). Note that $F_r^i = F_{r,0}^i$ and $F_r^i \subseteq F_{r,\rho}^i$. We denote solutions to system (18) as $\phi_\rho^i(\cdot, x)$ when initialized at $x \in \mathbb{R}^{n_x}$ for $i \in \mathbb{Z}_{\ge 0}$.

Theorem 4 establishes a KL-stability property with respect to $\sigma$ for which the attractor is $\mathcal{A} = \{x \in \mathbb{R}^{n_x} : \sigma(x) = 0\}$ when $\sigma$ is a proper indicator of $\mathcal{A}$. To define robust stability as in [21], we consider instead a two-measure KL-stability property with respect to $(\sigma_1, \sigma_2)$ where $\sigma_1, \sigma_2: \mathcal{X} \to \mathbb{R}_{\ge 0}$ are continuous. Given $\rho$ in (17), the attractor of perturbed system (18) becomes

$$\mathcal{A}_{\rho}^{i} := \{ \xi \in \mathcal{X} : \sup_{k \in \mathbb{Z}_{\ge 0}} \sigma_{1}(\phi_{\rho}^{i}(k, \xi)) = 0 \}. \quad (19)$$

We are ready to define robust KL-stability.

**Definition 2 ([21]):** Given $i \in \mathbb{Z}_{\ge 0}$ and $\sigma_1, \sigma_2: \mathcal{X} \to \mathbb{R}_{\ge 0}$ continuous, system (13) is robustly KL-stable with respect to $(\sigma_1, \sigma_2)$ on $\mathcal{X}$ if there exists a continuous function $\rho: \mathcal{X} \to \mathbb{R}_{\ge 0}$ such that the following holds.

(i) For all $x \in \mathcal{X}$, $\{x\} + \rho(x)\mathbb{B} \subset \mathcal{X}$.

(ii) For all $x \in \mathcal{X} \setminus \mathcal{A}_0^i$, $\rho(x) > 0$.

(iii) $\mathcal{A}_{\rho}^i = \mathcal{A}_0^i$.

(iv) System (18) is KL-stable with respect to $(\sigma_1, \sigma_2)$ on $\mathcal{X}$, i.e., there exists $\beta \in \mathcal{KL}$ such that $\sigma_1(\phi_\rho^i(k, x)) \le \beta(\sigma_2(x), k)$ for every $x \in \mathcal{X}$ and $k \in \mathbb{Z}_{\ge 0}$. When $\sigma_1 = \sigma_2 = \sigma$, (13) is KL-stable with respect to $\sigma$. $\square$

Item (i) of Definition 2 imposes a condition on $\rho$ so that $F_{r,\rho}^i(\mathcal{X}) \subseteq \mathcal{X}$ for any $i \in \mathbb{Z}_{\ge 0}$, as $F_r^i(x) \subseteq \mathcal{X}$ for all $x \in \mathcal{X}$. Item (ii) of Definition 2 in turn requires that $\rho$ is non-zero outside the attractor $\mathcal{A}_0^i$ corresponding to (19) with $\rho = 0$. Then, item (iii) of Definition 2 states that the perturbed attractor $\mathcal{A}_{\rho}^i$ is the same as the unperturbed one $\mathcal{A}_0^i$. Finally,

item (iv) of Definition 2 says that the perturbed system is KL-stable with respect to $(\sigma_1, \sigma_2)$.

As advocated in [21], if a difference inclusion is KL-stable with respect to some measures $(\sigma_1, \sigma_2)$, it is not necessarily robustly KL-stable. In other words, the (unperturbed) system may have zero robustness. In the context of this paper, sufficient conditions to conclude robust KL-stability with respect to some pair $(\sigma_1, \sigma_2)$ on $\mathcal{X}$ for system (13) with $i \in \mathbb{Z}_{\ge 0}$ are that:

(a) $F_r^i(x)$ is non-empty and compact for any $x \in \mathcal{X}$;

(b) the Lyapunov function used to establish the stability of the unperturbed system is continuous.

The next lemma states that item (a) above holds.

**Lemma 1:** Suppose Assumption 2 holds. For any $i \in \mathbb{Z}_{\ge 0}$, $F_r^i(x)$ is compact and non-empty for any $x \in \mathbb{R}^{n_x}$. $\square$

**Proof:** Let $i \in \mathbb{Z}_{\ge 0}$ and $x \in \mathbb{R}^{n_x}$, since $f$ is continuous by item (i) of Assumption 2, the compactness of $F_r^i(x) = f(x, H_{r,i}^*(x))$ follows from the compactness of $H_{r,i}^*$, which we now show. To this end, we prove that the conditions of [27, Theorem 1.17(a)] are verified by invoking similar arguments to those employed in the proof of Lemma 4 in Appendix I-E. Consider $g_r^i: (x, u) \mapsto \ell(x, u) + V_r^i(f(x, u)) + \delta_{H_r^i(x)}(u)$. On the one hand, $g_r^i$ is proper and level-bounded in $u$, locally uniform in $x$, for the same reasons as stated in the proof of Lemma 4. On the other hand, $(x, u) \mapsto \ell(x, u) + V_r^i(f(x, u))$ is lower semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$, in view of the lower semicontinuity of $V_r^i$ on $\mathbb{R}^{n_x}$ from Lemma 9 in Appendix I and the continuity of $f$ and $\ell$ by Assumption 2. Moreover, $\delta_{H_r^i(\cdot)}(\cdot)$ is lower semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$, as this holds from Lemma 12 in Section V since $H_r^i$ is an outer semicontinuous set-valued in view of [9, Lemma 5.16]. Thus $g_r^i$ is lower semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and all the conditions of [27, Theorem 1.17(a)] hold, we can therefore apply it to conclude $H_r^{*,i+1}(x)$ in (PI$^+$.2) is non-empty and compact at $x \in \mathbb{R}^{n_x}$. Since $x$ has been selected arbitrarily, the desired result follows. $\blacksquare$

Regarding item (b), it turns out that the Lyapunov function used to establish KL-stability in Section IV-E, namely $Y^i = \rho_V(V_r^i) + \rho_W(W)$, is only guaranteed to be lower semicontinuous. Indeed, while $W$, $\rho_V$ and $\rho_W$ are continuous, $V_r^i$ is only shown to be lower semicontinuous in Lemma 9 given in Appendix I. Thus we will require a different analysis or extra assumptions as presented next.

B. Robust semi-global practical stability

An alternative Lyapunov function to analyse the stability of (13) is $Y^* := \rho_V(V^*) + \rho_W(W)$, where $V^*$ is the optimal value function defined in (3), which is known to be continuous in view of [26, Theorem 3] under a mild additional assumption on $\mathcal{U}$ that can be checked a priori$^6$.

**Assumption 3:** Set-valued map $\mathcal{U}$ is continuous and locally bounded$^7$ on $\mathbb{R}^{n_x}$. $\square$

However, function $Y^*$ only allows to establish a semiglobal practical KL-stability property under SA1–3 for $i$ is sufficiently large so that, somehow, $V_r^i$ is sufficiently close to $V^*$

<footnote>$^6$SA1 is implied by SA2, SA3 and Assumptions 2-3, see [26, Theorem 3].</footnote>

<footnote>$^7$See [27, Definition 5.4] and [27, Definition 5.14], respectively.</footnote>
in view of Proposition 2. The next theorem provides a first robustness guarantee for the stability property established in Theorem 4. Its proof is given in Appendix IV-A.

**Theorem 6:** For any $\delta, \Delta > 0$, let $\sigma_1 = \max\{\sigma - \delta, 0\}$, $\sigma_2 = \sigma$, $\mathcal{X} = \{x \in \mathbb{R}^{n_x} : \sigma(x) < \Delta\}$ and suppose Assumptions 2 and 3 hold. There exists $i^* \in \mathbb{Z}_{\ge 0}$ such that, for any $i \ge i^*$, system (13) is robustly $\mathcal{KL}$-stable with respect to $(\sigma_1, \sigma_2)$ on $\mathcal{X}$.

Theorem 6 implies that the stability property of system (13) established in Theorem 4 is robust in a semiglobal practical sense after sufficiently many iterations $i$ with $i \ge i^*$ and $i^*$ depends on $\delta, \Delta$. It is a semiglobal property as we consider the set of initial conditions as $\{x \in \mathbb{R}^{n_x} : \sigma(x) < \Delta\}$ instead of $\mathbb{R}^{n_x}$, and it is practical as $\sigma_1$ is given by $\max\{\sigma(\cdot) - \delta, 0\}$ instead of $\sigma$.

By strengthening the assumptions given in Section III-C, we can ensure stronger robustness guarantees as shown in the next corollaries.

**Corollary 3:** For any $\Delta > 0$, let $\mathcal{X} = \{x \in \mathbb{R}^{n_x} : \sigma(x) < \Delta\}$ and suppose Assumptions 2 and 3 hold. There exists $i^* \in \mathbb{Z}_{\ge 0}$ such that, for any $i \ge i^*$, system (13) is robustly $\mathcal{KL}$-stable with respect to $\sigma$ on $\mathcal{X}$ when there exist $l \in \mathbb{R}_{>0}$, $c_W, a_W, \bar{a}_V > 0$ and $\bar{a}_W, \tilde{a} \ge 0$ such that, for any $s \in [0, l)$, $\chi_W(s) \le c_W s$, $\alpha_W(s) \ge a_W s$, $\bar{a}_V(s) \le \bar{a}_V s$, $\bar{a}_W(s) \le \bar{a}_W s$, $\tilde{a}(s) \le \tilde{a}_s$.

Corollary 3 extends Theorem 6 to allow $\delta = 0$, thus enabling robust semiglobal asymptotic stability guarantees. The proof follows by the same manipulations as in the proofs of [11, Corollary 1] or [13, Corollary 2] and is thus omitted. The next corollary ensures a robust global practical stability property under different conditions.

**Corollary 4:** For any $\delta > 0$, let $\sigma_1 = \max\{\sigma(\cdot) - \delta, 0\}$ and suppose Assumptions 2 and 3 hold. There exists $i^* \in \mathbb{Z}_{\ge 0}$ such that, for any $i \ge i^*$, system (13) is robustly $\mathcal{KL}$-stable with respect to $(\sigma_1, \sigma)$ on $\mathcal{X} = \mathbb{R}^{n_x}$ when there exist $L \in \mathbb{R}_{\ge 0}$, $c_W, a_W, \bar{a}_V > 0$ and $\bar{a}_W, \tilde{a} \ge 0$ such that, for any $s \in [L, \infty)$, $\chi_W(s) \le c_W s$, $\alpha_W(s) \ge a_W s$, $\bar{a}_V(s) \le \bar{a}_V s$, $\bar{a}_W(s) \le \bar{a}_W s$, $\tilde{a}(s) \le \tilde{a}_s$.

Corollary 4 extends Theorem 6 to allow $\Delta = \infty$, thus indeed enabling for robust global practical stability guarantees. The proof also follows by similar manipulations as in the proofs of [11, Corollary 1] or [13, Corollary 2] and is thus omitted. Finally, we can combine the conditions of Corollaries 3 and 4 to provide robust global and asymptotic stability properties. Its proof is omitted as it follows from Theorem 6, Corollaries 3 and 4.

**Corollary 5:** Suppose Assumptions 2 and 3 hold. There exists $i^* \in \mathbb{Z}_{\ge 0}$ such that, for any $i \ge i^*$, system (13) is robustly $\mathcal{KL}$-stable with respect to $\sigma$ on $\mathcal{X} = \mathbb{R}^{n_x}$ when both conditions at the end of Corollaries 3 and 4 hold.

The results of this section establish robust stability properties only when sufficiently many iterations of $\mathrm{PI}^+$ have been performed. When $V_r^0$ is sufficiently close to $V^*$, the required number of iterations for robust stability may be as low as 0. In general, however, we might not have robust stability at the first iterations. In order to establish robustness of the global asymptotic stability of $\mathrm{PI}^+$ at any iteration, we require extra assumptions, which are presented in the next section.

### C. Robust global asymptotic stability

It is possible to ensure robust stability at any iteration by adding an assumption on the problem, thanks to which $V_r^i$ can be shown to be continuous so that the desired robustness property follows from [21].

**Assumption 4:** For any iteration $i \in \mathbb{Z}_{\ge 0}$, for any two selections $h, h' \in H^i$, $J(\cdot, h) = J(\cdot, h')$.

Assumption 4 implies that all selections at any given iteration have the same induced cost. This arises, for example, when $H^i$ is single-valued at any $i \in \mathbb{Z}_{\ge 0}$, which for instance occurs when the plant dynamics is linear and the cost is quadratic under mild conditions. While verifying Assumption 4 a priori is not trivial, we can check this condition at each iteration for certain classes of optimal control problems, e.g., when the set of different selections of $H^i$ is finite.

We establish the next key result that follows from Assumption 4, whose proof is given in Appendix IV-B.

**Proposition 3:** Suppose Assumptions 2 and 4 hold and $h^0 \in \mathcal{U}$ be such that $J(\cdot, h^0)$ is continuous. Then, for any $i \in \mathbb{Z}_{\ge 0}$, $V_r^i$ is continuous on $\mathbb{R}^{n_x}$.

Proposition 3 gives a condition for $V_r^i$ to be continuous.

**Remark 8:** While Proposition 3 is vital for the subsequent robustness analysis, its consequences are interesting in their own right. Indeed, knowing that $V_r^i$ is continuous is useful when $f$ is unknown, which is not the case in this paper, as it allows using a variety of techniques to learn the value function and an associated policy at each iteration on any given compact set.

We provide the next robustness analysis for $\mathrm{PI}^+$ under Assumption 4. The proof follows by application of [21, Theorem 2.8] as all the required conditions hold by Lemma 1, Theorem 4 and Proposition 3.

**Theorem 7:** Suppose Assumptions 2 and 4 hold and $h^0 \in \mathcal{U}$ be such that $J(\cdot, h^0)$ is continuous. Then, for any $i \in \mathbb{Z}_{\ge 0}$ system (13) is robustly $\mathcal{KL}$-stable with respect to measure $\sigma$ on $\mathcal{X} = \mathbb{R}^{n_x}$ for any $i \in \mathbb{Z}_{\ge 0}$.

In contrast to Theorem 6, Theorem 7 shows that the stability guarantee given by Theorem 4 is indeed robust at any iteration.

### D. Robustness for $\mathrm{PI}$

The robustness properties established for $\mathrm{PI}^+$ also apply to $\mathrm{PI}$. Indeed, when $F^i$ is compact and non-empty on $\mathbb{R}^{n_x}$ for every $i \in \mathbb{Z}_{\ge 0}$, we can draw corresponding robustness guarantees for $\mathrm{PI}$. In turn, $F^i$ compact and non-empty on $\mathbb{R}^{n_x}$ for every $i \in \mathbb{Z}_{\ge 0}$ holds when Assumption 2 holds and $V^i$ is lower semicontinuous for every $i \in \mathbb{Z}_{\ge 0}$.

Moreover, $\mathrm{PI}^+$ reduces to $\mathrm{PI}$ under Assumption 4 is satisfied, i.e., $V_r^i = V^i$ when $V_r^0 = V^0$ and continuous. To see this, note that $V_r^0$ continuous implies that $H^1$ is outer semicontinuous, hence $H^1 = H_r^1$. Then, Assumption 4 guarantees that any selection of $H_r^1$ produces the same induced cost, hence $H_r^1 = H_r^{*,1}$. Thus $H_r^{*,1} = H^1$ and $V_r^1 = V^1$, which are also continuous in view of Proposition 3 for $i = 1$. The above reasoning allows to obtain $V_r^i = V^i$ holds for any $i \in \mathbb{Z}_{\ge 0}$ by induction. In conclusion, we also endow classical $\mathrm{PI}$ with robustness guarantees as in Section V-C when Assumption 4 holds.
in view of Proposition 2. The next theorem provides a first robustness guarantee for the stability property established in Theorem 4. Its proof is given in Appendix IV-A.

**Theorem 6:** For any $\delta, \Delta > 0$, let $\sigma_1 = \max\{\sigma - \delta, 0\}$, $\sigma_2 = \sigma$, $\mathcal{X} = \{x \in \mathbb{R}^{n_x} : \sigma(x) < \Delta\}$ and suppose Assumptions 2 and 3 hold. There exists $i^* \in \mathbb{Z}_{\ge 0}$ such that, for any $i \ge i^*$, system (13) is robustly $\mathcal{KL}$-stable with respect to $(\sigma_1, \sigma_2)$ on $\mathcal{X}$.

Theorem 6 implies that the stability property of system (13) established in Theorem 4 is robust in a semiglobal practical sense after sufficiently many iterations $i$ with $i \ge i^*$ and $i^*$ depends on $\delta, \Delta$. It is a semiglobal property as we consider the set of initial conditions as $\{x \in \mathbb{R}^{n_x} : \sigma(x) < \Delta\}$ instead of $\mathbb{R}^{n_x}$, and it is practical as $\sigma_1$ is given by $\max\{\sigma(\cdot) - \delta, 0\}$ instead of $\sigma$.

By strengthening the assumptions given in Section III-C, we can ensure stronger robustness guarantees as shown in the next corollaries.

**Corollary 3:** For any $\Delta > 0$, let $\mathcal{X} = \{x \in \mathbb{R}^{n_x} : \sigma(x) < \Delta\}$ and suppose Assumptions 2 and 3 hold. There exists $i^* \in \mathbb{Z}_{\ge 0}$ such that, for any $i \ge i^*$, system (13) is robustly $\mathcal{KL}$-stable with respect to $\sigma$ on $\mathcal{X}$ when there exist $l \in \mathbb{R}_{>0}$, $c_W, a_W, \bar{a}_V > 0$ and $\bar{a}_W, \tilde{a} \ge 0$ such that, for any $s \in [0, l)$, $\chi_W(s) \le c_W s$, $\alpha_W(s) \ge a_W s$, $\bar{a}_V(s) \le \bar{a}_V s$, $\bar{a}_W(s) \le \bar{a}_W s$, $\tilde{a}(s) \le \tilde{a}_s$.

Corollary 3 extends Theorem 6 to allow $\delta = 0$, thus enabling robust semiglobal asymptotic stability guarantees. The proof follows by the same manipulations as in the proofs of [11, Corollary 1] or [13, Corollary 2] and is thus omitted. The next corollary ensures a robust global practical stability property under different conditions.

**Corollary 4:** For any $\delta > 0$, let $\sigma_1 = \max\{\sigma(\cdot) - \delta, 0\}$ and suppose Assumptions 2 and 3 hold. There exists $i^* \in \mathbb{Z}_{\ge 0}$ such that, for any $i \ge i^*$, system (13) is robustly $\mathcal{KL}$-stable with respect to $(\sigma_1, \sigma)$ on $\mathcal{X} = \mathbb{R}^{n_x}$ when there exist $L \in \mathbb{R}_{\ge 0}$, $c_W, a_W, \bar{a}_V > 0$ and $\bar{a}_W, \tilde{a} \ge 0$ such that, for any $s \in [L, \infty)$, $\chi_W(s) \le c_W s$, $\alpha_W(s) \ge a_W s$, $\bar{a}_V(s) \le \bar{a}_V s$, $\bar{a}_W(s) \le \bar{a}_W s$, $\tilde{a}(s) \le \tilde{a}_s$.

Corollary 4 extends Theorem 6 to allow $\Delta = \infty$, thus indeed enabling for robust global practical stability guarantees. The proof also follows by similar manipulations as in the proofs of [11, Corollary 1] or [13, Corollary 2] and is thus omitted. Finally, we can combine the conditions of Corollaries 3 and 4 to provide robust global and asymptotic stability properties. Its proof is omitted as it follows from Theorem 6, Corollaries 3 and 4.

**Corollary 5:** Suppose Assumptions 2 and 3 hold. There exists $i^* \in \mathbb{Z}_{\ge 0}$ such that, for any $i \ge i^*$, system (13) is robustly $\mathcal{KL}$-stable with respect to $\sigma$ on $\mathcal{X} = \mathbb{R}^{n_x}$ when both conditions at the end of Corollaries 3 and 4 hold.

The results of this section establish robust stability properties only when sufficiently many iterations of $\mathrm{PI}^+$ have been performed. When $V_r^0$ is sufficiently close to $V^*$, the required number of iterations for robust stability may be as low as 0. In general, however, we might not have robust stability at the first iterations. In order to establish robustness of the global asymptotic stability of $\mathrm{PI}^+$ at any iteration, we require extra assumptions, which are presented in the next section.

### C. Robust global asymptotic stability

It is possible to ensure robust stability at any iteration by adding an assumption on the problem, thanks to which $V_r^i$ can be shown to be continuous so that the desired robustness property follows from [21].

**Assumption 4:** For any iteration $i \in \mathbb{Z}_{\ge 0}$, for any two selections $h, h' \in H^i$, $J(\cdot, h) = J(\cdot, h')$.

Assumption 4 implies that all selections at any given iteration have the same induced cost. This arises, for example, when $H^i$ is single-valued at any $i \in \mathbb{Z}_{\ge 0}$, which for instance occurs when the plant dynamics is linear and the cost is quadratic under mild conditions. While verifying Assumption 4 a priori is not trivial, we can check this condition at each iteration for certain classes of optimal control problems, e.g., when the set of different selections of $H^i$ is finite.

We establish the next key result that follows from Assumption 4, whose proof is given in Appendix IV-B.

**Proposition 3:** Suppose Assumptions 2 and 4 hold and $h^0 \in \mathcal{U}$ be such that $J(\cdot, h^0)$ is continuous. Then, for any $i \in \mathbb{Z}_{\ge 0}$, $V_r^i$ is continuous on $\mathbb{R}^{n_x}$.

Proposition 3 gives a condition for $V_r^i$ to be continuous.

**Remark 8:** While Proposition 3 is vital for the subsequent robustness analysis, its consequences are interesting in their own right. Indeed, knowing that $V_r^i$ is continuous is useful when $f$ is unknown, which is not the case in this paper, as it allows using a variety of techniques to learn the value function and an associated policy at each iteration on any given compact set.

We provide the next robustness analysis for $\mathrm{PI}^+$ under Assumption 4. The proof follows by application of [21, Theorem 2.8] as all the required conditions hold by Lemma 1, Theorem 4 and Proposition 3.

**Theorem 7:** Suppose Assumptions 2 and 4 hold and $h^0 \in \mathcal{U}$ be such that $J(\cdot, h^0)$ is continuous. Then, for any $i \in \mathbb{Z}_{\ge 0}$ system (13) is robustly $\mathcal{KL}$-stable with respect to measure $\sigma$ on $\mathcal{X} = \mathbb{R}^{n_x}$ for any $i \in \mathbb{Z}_{\ge 0}$.

In contrast to Theorem 6, Theorem 7 shows that the stability guarantee given by Theorem 4 is indeed robust at any iteration.

### D. Robustness for $\mathrm{PI}$

The robustness properties established for $\mathrm{PI}^+$ also apply to $\mathrm{PI}$. Indeed, when $F^i$ is compact and non-empty on $\mathbb{R}^{n_x}$ for every $i \in \mathbb{Z}_{\ge 0}$, we can draw corresponding robustness guarantees for $\mathrm{PI}$. In turn, $F^i$ compact and non-empty on $\mathbb{R}^{n_x}$ for every $i \in \mathbb{Z}_{\ge 0}$ holds when Assumption 2 holds and $V^i$ is lower semicontinuous for every $i \in \mathbb{Z}_{\ge 0}$.

Moreover, $\mathrm{PI}^+$ reduces to $\mathrm{PI}$ under Assumption 4 is satisfied, i.e., $V_r^i = V^i$ when $V_r^0 = V^0$ and continuous. To see this, note that $V_r^0$ continuous implies that $H^1$ is outer semicontinuous, hence $H^1 = H_r^1$. Then, Assumption 4 guarantees that any selection of $H_r^1$ produces the same induced cost, hence $H_r^1 = H_r^{*,1}$. Thus $H_r^{*,1} = H^1$ and $V_r^1 = V^1$, which are also continuous in view of Proposition 3 for $i = 1$. The above reasoning allows to obtain $V_r^i = V^i$ holds for any $i \in \mathbb{Z}_{\ge 0}$ by induction. In conclusion, we also endow classical $\mathrm{PI}$ with robustness guarantees as in Section V-C when Assumption 4 holds.
# VI. CONCLUSION

One of the messages of this work is that $PI^+$ should be considered in place of PI when recursive feasibility cannot be guaranteed. Because $PI^+$ may be difficult to implement in an exact fashion (just like PI), this new algorithm calls for the development of novel approximation schemes to cope with steps PI+3 to PI+5 in Algorithm 2 which we plan to investigate in future work. Other relevant research directions are to provide similar guarantees to non-stationary versions of PI, to study the conservatism of the given near-optimality bounds in applications, and to extend the current robustness properties to address more general non-vanishing perturbations, possibly in a data-driven case, as recently done in [25] for linear systems.

# APPENDIX I

## PROOFS OF THEOREMS 3 AND 4

### A. Proof outline

We prove Theorems 3 and 4 together by invoking the next proposition.

**Proposition 4:** For all $i \in \mathbb{Z}_{\ge 0}$, the following holds.

(i) For any $x \in \mathbb{R}^{n_x}$, $H^i(x)$, $H_r^i(x)$ and $H_r^{*,i}(x)$ are non-empty.

(ii) For any $x \in \mathbb{R}^{n_x}$ and $k \in \mathbb{Z}_{\ge 0}$, $\sigma(\phi^i(k, x)) \le \beta(\sigma(x), k)$ holds with $\beta \in \mathcal{KL}$ in Theorem 4.

(iii) For any $h_r^{*,i} \in H_r^{*,i}$ and $x \in \mathbb{R}^{n_x}$, $V_r^i(x) = J(x, h_r^{*,i}(x)) \le \bar{\alpha}_V(\sigma(x))$.

(iv) $V_r^i$ is lower semicontinuous on $\mathbb{R}^{n_x}$. $\square$

Item (i) of Proposition 4 corresponds to Theorem 3, item (ii) of Proposition 4 in turn corresponds to Theorem 4, while items (iii) and (iv) of Proposition 4 are technical properties used in the proof of Proposition 4.

Proposition 4 is proved by induction in this appendix. We first analyse the base case, i.e., $i = 0$. We establish items (i)-(iv) Proposition 4 for $i = 0$ by virtue of SA2-3 and Assumption 2, (PI$^+$.1) and Line 2 of Algorithm 2. In particular, for $i = 0$, items (i), (iii) and (iv) of Proposition 4 follow immediately from SA3, Assumption 2 and Algorithm 2, while item (ii) of Proposition 4 is a consequence of SA2 and SA3. Afterwards, we will proceed with the induction step, namely we consider $i \in \mathbb{Z}_{\ge 0}$ and we assume that (i)-(iv) of Proposition 4 hold for $i$, we then show that they also hold for $i+1$. We proceed in steps. First feasibility of the improvement step is proved, in the sense that $H^{i+1}(x)$ and $H_r^{i+1}(x)$ are non-empty for any $x \in \mathbb{R}^{n_x}$, and we also show $H^{i+1}$ in (PI$^+$.2) and $H_r^{i+1}$ in (PI$^+$.3) are locally bounded on $\mathbb{R}^{n_x}$ by virtue of the inductive hypothesis. Next, we study the feasibility of the evaluation step, and show that $V_r^{i+1}$ in (PI$^+$.4) is well defined and is upper-bounded by $V_r^i$, hence by $\bar{\alpha}_V \circ \sigma$. This in turn allows us to provide stability guarantees for system (13) for $i+1$, which is given by (1) in closed-loop with $H_r^{*,i+1}$ from (PI$^+$.5). As a consequence, we prove that $V_r^{i+1}$ is lower semicontinuous, and conclude that items (i)-(iv) of Proposition 4 hold for $i+1$ thereby completing the proof.

### B. Proof of Proposition 4

We first verify the base case, which is that items (i)-(iv) of Proposition 4 hold for $i = 0$, and we then address the induction step.

1) Base case ($i = 0$): In view of SA3, item (iv) of Assumption 2, (PI$^+$.1) and Line 2 of Algorithm 2, we have that items (i), (iii) and (iv) of Proposition 4 hold for $i = 0$.

We now show that item (ii) of Proposition 4 holds for $i = 0$. For this purpose, we establish in the next lemma the existence of a strict Lyapunov function for system (13) for $i = 0$, whose proof is given in Appendix I-C.

**Lemma 2:** There exist $\underline{\alpha}_Y$, $\bar{\alpha}_Y$, $\alpha_Y$, $\rho_V$, $\rho_W \in \mathcal{K}_\infty$ such that $Y^0 := \rho_V(V_r^0) + \rho_W(W)$ satisfies

$$ \begin{aligned} \underline{\alpha}_Y(\sigma(x)) &\le Y^0(x) \le \bar{\alpha}_Y(\sigma(x)) \\ Y^0(v) - Y^0(x) &\le -\alpha_Y(\sigma(x)) \end{aligned} \quad (20) $$

for any $x \in \mathbb{R}^{n_x}$ and $v \in F_r^0(x)$. $\square$

The next lemma formalizes the uniform global asymptotic stability property for system (13) at iteration $i = 0$ based on Lemma 2. Its proof is given in Appendix I-D.

**Lemma 3:** For any $x \in \mathbb{R}^{n_x}$, the corresponding solution $\phi^0$ to (13) for $i = 0$ verifies $\sigma(\phi^0(k, x)) \le \beta(\sigma(x), k)$ with $\beta \in \mathcal{KL}$ in Theorem 4. $\square$

As item (ii) of Proposition 4 holds for $i = 0$ in view of Lemma 3, we have proved that Proposition 4 holds at $i = 0$. It is important for the following to note that $\beta$ is constructed in terms of $\bar{\alpha}_V$, $\bar{\alpha}_W$, $\chi_W$ and $\alpha_W$, so that we can establish later that $\beta$ is independent of $i$.

2) Induction step ("i ⇒ i + 1"): We now proceed to the induction step, and assume Proposition 4 holds for $i \in \mathbb{Z}_{\ge 0}$. $\square$

**Inductive Hypothesis (IH):** Items (i)-(iv) of Proposition 4 hold for $i$. $\square$

Under IH, we show items (i)-(iv) of Proposition 4 holds for $i+1$. $\square$

**Feasibility of the improvement step:** The following lemma ensures that $H^{i+1}$ in (PI$^+$.2) and $H_r^{i+1}$ in (PI$^+$.3) are non-empty and locally bounded on $\mathbb{R}^{n_x}$. Its proof is given in Appendix I-E.

**Lemma 4:** Set-valued maps $H^{i+1}$ in (PI$^+$.2) and $H_r^{i+1}$ in (PI$^+$.3) are non-empty and locally bounded on $\mathbb{R}^{n_x}$. $\square$

We now seek to evaluate $V_r^{i+1}$.

**Feasibility of the evaluation step:** For the $(i+1)^{th}$ evaluation step of $PI^+$ in (PI$^+$.4), we need to show that the minimum cost over any selection of $H_r^{i+1}$ is well-defined. In other words, that $H_r^{*,i+1}(x)$ in (PI$^+$.5) is non-empty for any $x \in \mathbb{R}^{n_x}$. For the sake of convenience, we extend the state vector as $\chi := (x, u) \in \mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and we write

$$ \chi(k+1) \in (f(x, u), H_r^{i+1}(f(x, u))) := G^{i+1}(\chi(k)). \quad (21) $$

Given any $x \in \mathbb{R}^{n_x}$, we consider initial conditions to (21) of the form $(x, u)$ with $u \in H_r^{i+1}(x)$ with $H_r^{i+1}$ defined in (PI$^+$.3), and we denote the associated set of solutions to (21) by $S^{i+1}(x)$, which only depends on $x$. To extend the state vector as in (21) allows to write the stage cost as a function of $\chi$ only, i.e., $\ell(x, u) = \ell(\chi)$, which is convenient in the sequel. We now evaluate the cost of solutions to (21), that is, in view of (PI$^+$.4), for any $x \in \mathbb{R}^{n_x}$,

$$ V_r^{i+1}(x) = \min_{\psi^{i+1} \in S^{i+1}(x)} \sum_{k=0}^{\infty} \ell(\psi^{i+1}(k, x)), \quad (22) $$

where $\psi^{i+1} = (\phi^{i+1}, v^{i+1}) \in S^{i+1}(x)$ is a solution to system (21) initialized at $(x, h_r^{i+1}(x))$ with $h_r^{i+1}(x) \in H_r^{i+1}(x)$. To
# VI. CONCLUSION

One of the messages of this work is that $PI^+$ should be considered in place of PI when recursive feasibility cannot be guaranteed. Because $PI^+$ may be difficult to implement in an exact fashion (just like PI), this new algorithm calls for the development of novel approximation schemes to cope with steps PI+3 to PI+5 in Algorithm 2 which we plan to investigate in future work. Other relevant research directions are to provide similar guarantees to non-stationary versions of PI, to study the conservatism of the given near-optimality bounds in applications, and to extend the current robustness properties to address more general non-vanishing perturbations, possibly in a data-driven case, as recently done in [25] for linear systems.

# APPENDIX I

## PROOFS OF THEOREMS 3 AND 4

### A. Proof outline

We prove Theorems 3 and 4 together by invoking the next proposition.

**Proposition 4:** For all $i \in \mathbb{Z}_{\ge 0}$, the following holds.

(i) For any $x \in \mathbb{R}^{n_x}$, $H^i(x)$, $H_r^i(x)$ and $H_r^{*,i}(x)$ are non-empty.

(ii) For any $x \in \mathbb{R}^{n_x}$ and $k \in \mathbb{Z}_{\ge 0}$, $\sigma(\phi^i(k, x)) \le \beta(\sigma(x), k)$ holds with $\beta \in \mathcal{KL}$ in Theorem 4.

(iii) For any $h_r^{*,i} \in H_r^{*,i}$ and $x \in \mathbb{R}^{n_x}$, $V_r^i(x) = J(x, h_r^{*,i}(x)) \le \bar{\alpha}_V(\sigma(x))$.

(iv) $V_r^i$ is lower semicontinuous on $\mathbb{R}^{n_x}$. □

Item (i) of Proposition 4 corresponds to Theorem 3, item (ii) of Proposition 4 in turn corresponds to Theorem 4, while items (iii) and (iv) of Proposition 4 are technical properties used in the proof of Proposition 4.

Proposition 4 is proved by induction in this appendix. We first analyse the base case, i.e., $i = 0$. We establish items (i)-(iv) Proposition 4 for $i = 0$ by virtue of SA2-3 and Assumption 2, (PI$^+$.1) and Line 2 of Algorithm 2. In particular, for $i = 0$, items (i), (iii) and (iv) of Proposition 4 follow immediately from SA3, Assumption 2 and Algorithm 2, while item (ii) of Proposition 4 is a consequence of SA2 and SA3. Afterwards, we will proceed with the induction step, namely we consider $i \in \mathbb{Z}_{\ge 0}$ and we assume that (i)-(iv) of Proposition 4 hold for $i$, we then show that they also hold for $i+1$. We proceed in steps. First feasibility of the improvement step is proved, in the sense that $H^{i+1}(x)$ and $H_r^{i+1}(x)$ are non-empty for any $x \in \mathbb{R}^{n_x}$, and we also show $H^{i+1}$ in (PI$^+$.2) and $H_r^{i+1}$ in (PI$^+$.3) are locally bounded on $\mathbb{R}^{n_x}$ by virtue of the inductive hypothesis. Next, we study the feasibility of the evaluation step, and show that $V_r^{i+1}$ in (PI$^+$.4) is well defined and is upper-bounded by $V_r^i$, hence by $\bar{\alpha}_V \circ \sigma$. This in turn allows us to provide stability guarantees for system (13) for $i+1$, which is given by (1) in closed-loop with $H_r^{*,i+1}$ from (PI$^+$.5). As a consequence, we prove that $V_r^{i+1}$ is lower semicontinuous, and conclude that items (i)-(iv) of Proposition 4 hold for $i+1$ thereby completing the proof.

### B. Proof of Proposition 4

We first verify the base case, which is that items (i)-(iv) of Proposition 4 hold for $i = 0$, and we then address the induction step.

1) Base case ($i = 0$): In view of SA3, item (iv) of Assumption 2, (PI$^+$.1) and Line 2 of Algorithm 2, we have that items (i), (iii) and (iv) of Proposition 4 hold for $i = 0$.

We now show that item (ii) of Proposition 4 holds for $i = 0$. For this purpose, we establish in the next lemma the existence of a strict Lyapunov function for system (13) for $i = 0$, whose proof is given in Appendix I-C.

**Lemma 2:** There exist $\underline{\alpha}_Y$, $\bar{\alpha}_Y$, $\alpha_Y$, $\rho_V$, $\rho_W \in \mathcal{K}_\infty$ such that $Y^0 := \rho_V(V_r^0) + \rho_W(W)$ satisfies

$$ \begin{aligned} \underline{\alpha}_Y(\sigma(x)) &\le Y^0(x) \le \bar{\alpha}_Y(\sigma(x)) \\ Y^0(v) - Y^0(x) &\le -\alpha_Y(\sigma(x)) \end{aligned} \quad (20) $$

for any $x \in \mathbb{R}^{n_x}$ and $v \in F_r^0(x)$. □

The next lemma formalizes the uniform global asymptotic stability property for system (13) at iteration $i = 0$ based on Lemma 2. Its proof is given in Appendix I-D.

**Lemma 3:** For any $x \in \mathbb{R}^{n_x}$, the corresponding solution $\phi^0$ to (13) for $i = 0$ verifies $\sigma(\phi^0(k, x)) \le \beta(\sigma(x), k)$ with $\beta \in \mathcal{KL}$ in Theorem 4. □

As item (ii) of Proposition 4 holds for $i = 0$ in view of Lemma 3, we have proved that Proposition 4 holds at $i = 0$. It is important for the following to note that $\beta$ is constructed in terms of $\bar{\alpha}_V$, $\bar{\alpha}_W$, $\chi_W$ and $\alpha_W$, so that we can establish later that $\beta$ is independent of $i$.

2) Induction step ("i ⇒ i + 1"): We now proceed to the induction step, and assume Proposition 4 holds for $i \in \mathbb{Z}_{\ge 0}$. □

**Inductive Hypothesis (IH):** Items (i)-(iv) of Proposition 4 hold for $i$. □

Under IH, we show items (i)-(iv) of Proposition 4 holds for $i+1$. □

**Feasibility of the improvement step:** The following lemma ensures that $H^{i+1}$ in (PI$^+$.2) and $H_r^{i+1}$ in (PI$^+$.3) are non-empty and locally bounded on $\mathbb{R}^{n_x}$. Its proof is given in Appendix I-E.

**Lemma 4:** Set-valued maps $H^{i+1}$ in (PI$^+$.2) and $H_r^{i+1}$ in (PI$^+$.3) are non-empty and locally bounded on $\mathbb{R}^{n_x}$. □

We now seek to evaluate $V_r^{i+1}$. □

**Feasibility of the evaluation step:** For the $(i+1)^{th}$ evaluation step of $PI^+$ in (PI$^+$.4), we need to show that the minimum cost over any selection of $H_r^{i+1}$ is well-defined. In other words, that $H_r^{*,i+1}(x)$ in (PI$^+$.5) is non-empty for any $x \in \mathbb{R}^{n_x}$. For the sake of convenience, we extend the state vector as $\chi := (x, u) \in \mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and we write

$$ \chi(k+1) \in (f(x, u), H_r^{i+1}(f(x, u))) := G^{i+1}(\chi(k)). \quad (21) $$

Given any $x \in \mathbb{R}^{n_x}$, we consider initial conditions to (21) of the form $(x, u)$ with $u \in H_r^{i+1}(x)$ with $H_r^{i+1}$ defined in (PI$^+$.3), and we denote the associated set of solutions to (21) by $S^{i+1}(x)$, which only depends on $x$. To extend the state vector as in (21) allows to write the stage cost as a function of $\chi$ only, i.e., $\ell(x, u) = \ell(\chi)$, which is convenient in the sequel. We now evaluate the cost of solutions to (21), that is, in view of (PI$^+$.4), for any $x \in \mathbb{R}^{n_x}$,

$$ V_r^{i+1}(x) = \min_{\psi^{i+1} \in S^{i+1}(x)} \sum_{k=0}^{\infty} \ell(\psi^{i+1}(k, x)), \quad (22) $$

where $\psi^{i+1} = (\phi^{i+1}, v^{i+1}) \in S^{i+1}(x)$ is a solution to system (21) initialized at $(x, h_r^{i+1}(x))$ with $h_r^{i+1}(x) \in H_r^{i+1}(x)$. To
guarantee the existence of a minimum in (22), we invoke similar arguments as in [20, Claim 24]. For this purpose, we first state the next properties of $G^{i+1}$ in (21).

**Lemma 5:** Function $G^{i+1}$ in (21) is outer semicontinuous, locally bounded on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and $G^{i+1}(\chi)$ is non-empty for any $\chi \in \mathcal{W}^{i+1} := \{(x, u) \in \mathbb{R}^{n_x} \times \mathbb{R}^{n_u} : u \in H_r^{i+1}(x)\}$. $\square$

**Proof:** Since single-valued $f$ is continuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ by item (i) of Assumption 2, it is locally bounded and outer-semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ by [27, Corollary 5.20]. Moreover, as $H_r^{i+1}$ in (PI$^+$.3) is locally bounded by Lemma 4 and outer semicontinuous on $\mathbb{R}^{n_x}$ by [9, Lemma 5.16], we deduce that $G^{i+1}$ is locally bounded and outer semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ by [27, Proposition 5.52(a) and (b)]. Finally, $G^{i+1}(\chi)$ is non-empty for any $\chi \in \mathcal{W}^{i+1}$ as $H_r^{i+1}(x)$ is non-empty for $x \in \mathbb{R}^{n_x}$ by Lemma 4. ■

We verify the existence of a policy as in (PI$^+$.5) for $i+1$, and we provide key properties of such policy in the next proposition, whose proof is in Appendix I-F.

**Lemma 6:** There exists $h_r^{*,i+1} \in H_r^{*,i+1}$ such that $V_r^{i+1}(x) = J(x, h_r^{*,i+1})$ for all $x \in \mathbb{R}^{n_x}$. Furthermore, the following holds for any $x \in \mathbb{R}^{n_x}$,

$$ (i) \quad V_r^{i+1}(x) = \ell(x, h_r^{*,i+1}(x)) + V_r^{i+1}(f(x, h_r^{*,i+1}(x))), $$

$$ (ii) \quad V_r^{i+1}(x) \le V_r^i(x) \le \bar{\alpha}_V(\sigma(x)). \quad \square $$

In view of Lemmas 4 and 6, items (i) and (iii) of Proposition 4 are verified at $i+1$. We now establish stability properties as in item (ii) of Proposition 4 at $i+1$, which then allows to show the lower semicontinuity of $V_r^{i+1}$, which is the final item (iv) of Proposition 4.

**Stability:** We follow similar lines as in Appendix I-B.1 to analyze the stability of system (13) at iteration $i+1$. The next result establish the existence of a strict Lyapunov function for the $(i+1)^{th}$-step of PI$^+$, similar to the one found in Lemma 2. The proof relies on similar arguments as the proof of Lemma 2 in Appendix I-C, and is hence omitted.

**Lemma 7:** For any $x \in \mathbb{R}^{n_x}$ and $v \in F_r^{i+1}(x)$,

$$ \begin{aligned} \underline{\alpha}_Y(\sigma(x)) &\le Y^{i+1}(x) \le \bar{\alpha}_Y(\sigma(x)) \\ Y^{i+1}(v) - Y^{i+1}(x) &\le -\alpha_Y(\sigma(x)) \end{aligned} \quad (23) $$

with $Y^{i+1} := \rho_V(V_r^{i+1}) + \rho_W(W)$ and $\underline{\alpha}_Y, \bar{\alpha}_Y, \alpha_Y, \rho_V, \rho_W \in \mathcal{K}_\infty$ as in Lemma 2. $\square$

The next result follows from Lemma 7. Its proof is very similar to the proof of Lemma 3 in Appendix I-D, it is therefore omitted.

**Lemma 8:** For any $x \in \mathbb{R}^{n_x}$, any solution $\phi^{i+1}$ to (13) verifies $\sigma(\phi^{i+1}(k, x)) \le \beta(\sigma(x), k)$ with $\beta \in \mathcal{KL}$ in Theorem 4. $\square$

Since, in Lemma 3, we have $\beta$ only constructed in terms of $\bar{\alpha}_V, \bar{\alpha}_W, \chi_W$ and $\alpha_W$, we therefore obtain $\beta$ independent of $i+1$ in Lemma 8. This establishes item (ii) of Proposition 4 at $i+1$. All that remains to prove is item (iv) of Proposition 4 for $i+1$.

**Lower semicontinuity of $V_r^{i+1}$:** The next lemma establishes the lower semicontinuity of $V_r^{i+1}$, whose proof is given in Appendix I-G and is inspired by [20, Theorem 6].

**Lemma 9:** $V_r^{i+1}$ is lower semicontinuous on $\mathbb{R}^{n_x}$. $\square$

We have obtained lower semicontinuous $V_r^{i+1}$ and items (i)-(iv) of Proposition 4 holds for $i+1$. Therefore Proposition 4

holds for $i+1$ and the induction proof of Proposition 4 is complete. We then deduce that Theorems 3 and 4 hold.

### C. Proof of Lemma 2

The proof follows similar lines as the proofs of [13, Theorem 1] and [26, Theorem 1]. We distinguish two cases.

**Case where $\chi_W \le I$:** Let $\rho_V := \rho_W := I$, thus $Y^0 = \rho_V(V_r^0) + \rho_W(W) = V_r^0 + W$. By SA2 and SA3, $Y^0(x) \le \bar{\alpha}_V(\sigma(x)) + \bar{\alpha}_W(\sigma(x))$ for any $x \in \mathbb{R}^{n_x}$, therefore $\bar{\alpha}_Y := \bar{\alpha}_V + \bar{\alpha}_W$. On the other hand, by SA2 and since $\chi_W \le I$, $\alpha_W(\sigma(x)) \le \ell(x, u) + W(x)$ for any $(x, u) \in W$, hence $Y^0(x) = V_r^0(x) + W(x) \ge \ell(x, h^0(x)) + W(x) \ge \alpha_W(\sigma(x))$, therefore $\underline{\alpha}_Y := \alpha_W$. Moreover, since $V_r^0(x) = J(x, h^0) = \ell(x, h^0(x)) + J(f(x, h^0(x)), h^0) = \ell(x, h^0(x)) + V_r^0(f(x, h^0(x)))$, we have for $v = f(x, h^0(x))$ that

$$ V_r^0(v) - V^0(x) = -\ell(x, h^0(x)). \quad (24) $$

Again by SA2 as $\chi_W \le I$ and $u = h^0(x)$,

$$ W(v) - W(x) \le -\alpha_W(\sigma(x)) + \ell(x, u). \quad (25) $$

Summing (24) and (25), we obtain $Y^0(v) - Y(x) \le -\alpha_W(\sigma(x))$, therefore $\alpha_Y := \alpha_W$. The case is complete.

**Case where $\chi(s) > s$ for some $s > 0$:** We define $q_V := 2\chi_W(2I)$ and $q_W := \frac{1}{2}[\chi_W + (\bar{\alpha}_W + I) \circ \alpha_W^{-1}(2\chi_W)]^{-1}$, where the involved functions come from SA2. Note that $q_W$ is well-defined as $\chi_W + (\bar{\alpha}_W + I) \circ \alpha_W^{-1}(2\chi_W)$ is invertible, being a class-$\mathcal{K}_\infty$ function. Moreover, both $q_V$ and $q_W$ are of class-$\mathcal{K}_\infty$. We further define $\rho_V(s) := \int_0^s q_V(\tau)d\tau$ and $\rho_W(s) := \int_0^s q_W(\tau)d\tau$ for any $s \ge 0$. Note that $\rho_V$ and $\rho_W$ are also of class-$\mathcal{K}_\infty$. We are ready to define the Lyapunov function used to prove stability.

Let $x \in \mathbb{R}^{n_x}$ and $v \in F_r^0(x)$. According to SA2 and SA3, $Y^0(x) \le \rho_V \circ \bar{\alpha}_V(\sigma(x)) + \rho_W \circ \bar{\alpha}_W(\sigma(x)) =: \bar{\alpha}_Y(\sigma(x))$ and $\bar{\alpha}_Y$ is of class-$\mathcal{K}_\infty$ in view of the properties of the functions $\rho_V, \rho_W, \bar{\alpha}_V$ and $\bar{\alpha}_W$. On the other hand, from (24), for any $x \in \mathbb{R}^{n_x}$,

$$ V_r^0(x) \ge \ell(x, h^0(x)) \quad (26) $$

and in view of SA2, $Y^0(x) \ge \rho_V(\ell(x, h^0(x))) + \rho_W(\max\{\alpha_W(\sigma(x)) - \chi_W(\ell(x, h^0(x))), 0\})$. When $\frac{1}{2}\alpha_W(\sigma(x)) \le \chi_W(\ell(x, h^0(x)))$, it follows $Y^0(x) \ge \rho_V \circ \chi_W^{-1}(\frac{1}{2}\alpha_W(\sigma(x)))$. When $\frac{1}{2}\alpha_W(\sigma(x)) \ge \chi_W(\ell(x, h^0(x)))$ then $Y^0(x) \ge \rho_W \circ \frac{1}{2}\alpha_W(\sigma(x))$. Hence $Y^0(x) \ge \underline{\alpha}_Y(\sigma(x))$ with $\underline{\alpha}_Y := \min\{\rho_V \circ \chi_W^{-1}(\frac{1}{2}\alpha_W), \rho_W(\frac{1}{2}\alpha_W)\} \in \mathcal{K}_\infty$. We have proved the first line in (20).

In view of (24), (26) and SA3, the conditions of [13, Lemma 3] are satisfied with $h(x) = \ell(x, h^0(x))$, $\alpha_1 = \bar{\alpha}_V$ and $\alpha_2 = 0$. Thus, we derive that

$$ \rho_V(V_r^0(v)) - \rho_V(V_r^0(x)) \le -\chi_W(\ell(x, h^0(x)))\ell(x, h^0(x)). \quad (27) $$

On the other hand, the conditions of [13, Lemma 4] are verified with$^8 \alpha_1 = \bar{\alpha}_W + I$, $\alpha_2 = \chi_W$ and $\alpha_3 = \alpha_W$, according to

<footnote>$^8I$ is added to ensure $\alpha_1 \in \mathcal{K}_\infty$.</footnote>
guarantee the existence of a minimum in (22), we invoke similar arguments as in [20, Claim 24]. For this purpose, we first state the next properties of $G^{i+1}$ in (21).

**Lemma 5:** Function $G^{i+1}$ in (21) is outer semicontinuous, locally bounded on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and $G^{i+1}(\chi)$ is non-empty for any $\chi \in \mathcal{W}^{i+1} := \{(x, u) \in \mathbb{R}^{n_x} \times \mathbb{R}^{n_u} : u \in H_r^{i+1}(x)\}$. $\square$

**Proof:** Since single-valued $f$ is continuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ by item (i) of Assumption 2, it is locally bounded and outer-semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ by [27, Corollary 5.20]. Moreover, as $H_r^{i+1}$ in (PI$^+$.$3$) is locally bounded by Lemma 4 and outer semicontinuous on $\mathbb{R}^{n_x}$ by [9, Lemma 5.16], we deduce that $G^{i+1}$ is locally bounded and outer semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ by [27, Proposition 5.52(a) and (b)]. Finally, $G^{i+1}(\chi)$ is non-empty for any $\chi \in \mathcal{W}^{i+1}$ as $H_r^{i+1}(x)$ is non-empty for $x \in \mathbb{R}^{n_x}$ by Lemma 4. ■

We verify the existence of a policy as in (PI$^+$.$5$) for $i+1$, and we provide key properties of such policy in the next proposition, whose proof is in Appendix I-F.

**Lemma 6:** There exists $h_r^{*,i+1} \in H_r^{*,i+1}$ such that $V_r^{i+1}(x) = J(x, h_r^{*,i+1})$ for all $x \in \mathbb{R}^{n_x}$. Furthermore, the following holds for any $x \in \mathbb{R}^{n_x}$,

$$ (i) \quad V_r^{i+1}(x) = \ell(x, h_r^{*,i+1}(x)) + V_r^{i+1}(f(x, h_r^{*,i+1}(x))), $$

$$ (ii) \quad V_r^{i+1}(x) \le V_r^i(x) \le \bar{\alpha}_V(\sigma(x)). \quad \square $$

In view of Lemmas 4 and 6, items (i) and (iii) of Proposition 4 are verified at $i+1$. We now establish stability properties as in item (ii) of Proposition 4 at $i+1$, which then allows to show the lower semicontinuity of $V_r^{i+1}$, which is the final item (iv) of Proposition 4.

**Stability:** We follow similar lines as in Appendix I-B.1 to analyze the stability of system (13) at iteration $i+1$. The next result establish the existence of a strict Lyapunov function for the $(i+1)^{th}$-step of PI$^+$, similar to the one found in Lemma 2. The proof relies on similar arguments as the proof of Lemma 2 in Appendix I-C, and is hence omitted.

**Lemma 7:** For any $x \in \mathbb{R}^{n_x}$ and $v \in F_r^{i+1}(x)$,

$$ \begin{aligned} \underline{\alpha}_Y(\sigma(x)) &\le Y^{i+1}(x) \le \bar{\alpha}_Y(\sigma(x)) \\ Y^{i+1}(v) - Y^{i+1}(x) &\le -\alpha_Y(\sigma(x)) \end{aligned} \quad (23) $$

with $Y^{i+1} := \rho_V(V_r^{i+1}) + \rho_W(W)$ and $\underline{\alpha}_Y, \bar{\alpha}_Y, \alpha_Y, \rho_V, \rho_W \in \mathcal{K}_\infty$ as in Lemma 2. $\square$

The next result follows from Lemma 7. Its proof is very similar to the proof of Lemma 3 in Appendix I-D, it is therefore omitted.

**Lemma 8:** For any $x \in \mathbb{R}^{n_x}$, any solution $\phi^{i+1}$ to (13) verifies $\sigma(\phi^{i+1}(k, x)) \le \beta(\sigma(x), k)$ with $\beta \in \mathcal{KL}$ in Theorem 4. $\square$

Since, in Lemma 3, we have $\beta$ only constructed in terms of $\bar{\alpha}_V, \bar{\alpha}_W, \chi_W$ and $\alpha_W$, we therefore obtain $\beta$ independent of $i+1$ in Lemma 8. This establishes item (ii) of Proposition 4 at $i+1$. All that remains to prove is item (iv) of Proposition 4 for $i+1$.

**Lower semicontinuity of $V_r^{i+1}$:** The next lemma establishes the lower semicontinuity of $V_r^{i+1}$, whose proof is given in Appendix I-G and is inspired by [20, Theorem 6].

**Lemma 9:** $V_r^{i+1}$ is lower semicontinuous on $\mathbb{R}^{n_x}$. $\square$

We have obtained lower semicontinuous $V_r^{i+1}$ and items (i)-(iv) of Proposition 4 holds for $i+1$. Therefore Proposition 4

holds for $i+1$ and the induction proof of Proposition 4 is complete. We then deduce that Theorems 3 and 4 hold.

### C. Proof of Lemma 2

The proof follows similar lines as the proofs of [13, Theorem 1] and [26, Theorem 1]. We distinguish two cases.

**Case where $\chi_W \le I$:** Let $\rho_V := \rho_W := I$, thus $Y^0 = \rho_V(V_r^0) + \rho_W(W) = V_r^0 + W$. By SA2 and SA3, $Y^0(x) \le \bar{\alpha}_V(\sigma(x)) + \bar{\alpha}_W(\sigma(x))$ for any $x \in \mathbb{R}^{n_x}$, therefore $\bar{\alpha}_Y := \bar{\alpha}_V + \bar{\alpha}_W$. On the other hand, by SA2 and since $\chi_W \le I$, $\alpha_W(\sigma(x)) \le \ell(x, u) + W(x)$ for any $(x, u) \in W$, hence $Y^0(x) = V_r^0(x) + W(x) \ge \ell(x, h^0(x)) + W(x) \ge \alpha_W(\sigma(x))$, therefore $\underline{\alpha}_Y := \alpha_W$. Moreover, since $V_r^0(x) = J(x, h^0) = \ell(x, h^0(x)) + J(f(x, h^0(x)), h^0) = \ell(x, h^0(x)) + V_r^0(f(x, h^0(x)))$, we have for $v = f(x, h^0(x))$ that

$$ V_r^0(v) - V^0(x) = -\ell(x, h^0(x)). \quad (24) $$

Again by SA2 as $\chi_W \le I$ and $u = h^0(x)$,

$$ W(v) - W(x) \le -\alpha_W(\sigma(x)) + \ell(x, u). \quad (25) $$

Summing (24) and (25), we obtain $Y^0(v) - Y(x) \le -\alpha_W(\sigma(x))$, therefore $\alpha_Y := \alpha_W$. The case is complete.

**Case where $\chi(s) > s$ for some $s > 0$:** We define $q_V := 2\chi_W(2I)$ and $q_W := \frac{1}{2}[\chi_W + (\bar{\alpha}_W + I) \circ \alpha_W^{-1}(2\chi_W)]^{-1}$, where the involved functions come from SA2. Note that $q_W$ is well-defined as $\chi_W + (\bar{\alpha}_W + I) \circ \alpha_W^{-1}(2\chi_W)$ is invertible, being a class-$\mathcal{K}_\infty$ function. Moreover, both $q_V$ and $q_W$ are of class-$\mathcal{K}_\infty$. We further define $\rho_V(s) := \int_0^s q_V(\tau)d\tau$ and $\rho_W(s) := \int_0^s q_W(\tau)d\tau$ for any $s \ge 0$. Note that $\rho_V$ and $\rho_W$ are also of class-$\mathcal{K}_\infty$. We are ready to define the Lyapunov function used to prove stability.

Let $x \in \mathbb{R}^{n_x}$ and $v \in F_r^0(x)$. According to SA2 and SA3, $Y^0(x) \le \rho_V \circ \bar{\alpha}_V(\sigma(x)) + \rho_W \circ \bar{\alpha}_W(\sigma(x)) =: \bar{\alpha}_Y(\sigma(x))$ and $\bar{\alpha}_Y$ is of class-$\mathcal{K}_\infty$ in view of the properties of the functions $\rho_V, \rho_W, \bar{\alpha}_V$ and $\bar{\alpha}_W$. On the other hand, from (24), for any $x \in \mathbb{R}^{n_x}$,

$$ V_r^0(x) \ge \ell(x, h^0(x)) \quad (26) $$

and in view of SA2, $Y^0(x) \ge \rho_V(\ell(x, h^0(x))) + \rho_W(\max\{\alpha_W(\sigma(x)) - \chi_W(\ell(x, h^0(x))), 0\})$. When $\frac{1}{2}\alpha_W(\sigma(x)) \le \chi_W(\ell(x, h^0(x)))$, it follows $Y^0(x) \ge \rho_V \circ \chi_W^{-1}(\frac{1}{2}\alpha_W(\sigma(x)))$. When $\frac{1}{2}\alpha_W(\sigma(x)) \ge \chi_W(\ell(x, h^0(x)))$ then $Y^0(x) \ge \rho_W \circ \frac{1}{2}\alpha_W(\sigma(x))$. Hence $Y^0(x) \ge \underline{\alpha}_Y(\sigma(x))$ with $\underline{\alpha}_Y := \min\{\rho_V \circ \chi_W^{-1}(\frac{1}{2}\alpha_W), \rho_W(\frac{1}{2}\alpha_W)\} \in \mathcal{K}_\infty$. We have proved the first line in (20).

In view of (24), (26) and SA3, the conditions of [13, Lemma 3] are satisfied with $h(x) = \ell(x, h^0(x))$, $\alpha_1 = \bar{\alpha}_V$ and $\alpha_2 = 0$. Thus, we derive that

$$ \rho_V(V_r^0(v)) - \rho_V(V_r^0(x)) \le -\chi_W(\ell(x, h^0(x)))\ell(x, h^0(x)). \quad (27) $$

On the other hand, the conditions of [13, Lemma 4] are verified with$^8$ $\alpha_1 = \bar{\alpha}_W + I$, $\alpha_2 = \chi_W$ and $\alpha_3 = \alpha_W$, according to

<footnote>$^8$I is added to ensure $\alpha_1 \in \mathcal{K}_\infty$.</footnote>
SA2. Hence, we deduce from [13, Lemma 4]

$$
\begin{align}
& \rho_W(W(v)) - \rho_W(W(x)) \nonumber \\
& \le 2q_W \left( \chi_W(\ell(x, h^0(x))) + \alpha_1 \circ \alpha_W^{-1}(2\chi_W(\ell(x, h^0(x)))) \right) \nonumber \\
& \qquad \times \chi_W(\ell(x, h^0(x))) - q_W(1/4\alpha_W(\sigma(x)))^{1/4}\alpha_W(\sigma(x)) \nonumber \\
& = \ell(x, h^0(x))\chi_W(\ell(x, h^0(x))) - \tilde{\alpha}_W(\sigma(x)) \tag{28}
\end{align}
$$

where $\tilde{\alpha}_W = q_W(\frac{1}{4}\alpha_W)^{\frac{1}{4}}\alpha_W \in \mathcal{K}_\infty$. In view of (27) and (28), it follows that $Y^0(v) - Y^0(x) \le -\chi_W(\ell(x, h^0(x)))\ell(x, h^0(x)) + \ell(x, h^0(x))\chi_W(\ell(x, h^0(x))) - \tilde{\alpha}_W(\sigma(x)) \le -\tilde{\alpha}_W(\sigma(x))$. We have shown that the second line in (20) holds with $\alpha_Y = \tilde{\alpha}_W \in \mathcal{K}_\infty$. The case is complete.

### D. Proof of Lemma 3

The proof follows by application of Lemma 2 and Lemma 14 in Appendix V. Indeed, we apply Lemma 14 with $\alpha = \mathbb{I} - \tilde{\alpha}_Y$, where $\tilde{\alpha}_Y := \alpha_Y \circ \bar{\alpha}_Y^{-1}$. For any $x \in \mathbb{R}^{n_x}$, we consider the sequence $s_k(x)$, $k \in \mathbb{Z}_{\ge 0}$, defined as $s_k(x) = Y^0(\phi(k, x))$. We note that $s_{k+1}(x) \le \alpha(s_k(x))$ as required. This property follows from (20), which implies $\tilde{\alpha}_Y(Y^0(x)) = \alpha_Y \circ \bar{\alpha}_Y^{-1}(Y^0(x)) \le \alpha_Y(\sigma(x))$ hence $Y^0(\phi(k+1, x)) \le Y^0(\phi(k, x)) - \tilde{\alpha}_Y(Y^0(\phi(k, x)))$ for any $x \in \mathbb{R}^{n_x}$ and $k \in \mathbb{Z}_{\ge 0}$. Note moreover that $\mathbb{I} - \tilde{\alpha}_Y$ is indeed continuous, zero at zero, $\alpha(s) < s$ for all $s > 0$ and non-negative. Hence Lemma 14 generates $\tilde{\beta}_x \in \mathcal{KL}$ such that $Y^0(\phi^0(k, x)) \le \tilde{\beta}_x(Y^0(x), k)$ for any $x \in \mathbb{R}^{n_x}$ and $k \in \mathbb{Z}_{\ge 0}$, and since $\alpha$ is uniform in $x$, $\tilde{\beta}_x := \tilde{\beta}$. Again by (20), we obtain that $\alpha_Y(\sigma(\phi^0(k, x))) \le \tilde{\beta}(\bar{\alpha}_Y(\sigma(x)), k)$. Hence the result of Lemma 3 holds with $\tilde{\beta} = \bar{\alpha}_Y^{-1}(\tilde{\beta}(\bar{\alpha}_Y(\cdot), \cdot)) \in \mathcal{KL}$.

### E. Proof of Lemma 4

We prove that the conditions of [27, Theorem 1.17(a)] are verified to first show that $H^{i+1}(x)$ is non-empty for any $x \in \mathbb{R}^{n_x}$. Let $g^{i+1} : (x, u) \mapsto \ell(x, u) + V_r^i(f(x, u)) + \delta_{\mathcal{U}(x)}(u)$ be defined on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$. The map $g^{i+1}$ is lower semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ by item (i) of Assumption 2; (ii) $V_r^i$ is lower semicontinuous on $\mathbb{R}^{n_x}$ by IH; (iii) $(x, u) \mapsto \delta_{\mathcal{U}(x)}(u)$ is lower semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ by Lemma 12 in Appendix V as $\mathcal{U}$ is outer semicontinuous on $\mathbb{R}^{n_x}$ by item (iii) of Assumption 2. Moreover, $g^{i+1}$ is proper as $g^{i+1}(x, u) > -\infty$ for any $(x, u) \in \mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and $g^{i+1}(x, u) < \infty$ for any $(x, u) \in \mathcal{W}$, as $\mathcal{U}(x)$ is non-empty for any $x \in \mathbb{R}^{n_x}$. In addition, as $g^{i+1}(x, u) \ge \ell(x, u)$ for any $(x, u) \in \mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and $\ell$ is level-bounded in $u$, locally uniform in $x$ by item (ii) of Assumption 2, $(x, u) \mapsto g^{i+1}(x, u)$ is level-bounded in $u$, locally uniform in $x$ for any $x \in \mathbb{R}^{n_x}$ by Lemma 13 in Appendix V. All the conditions of [27, Theorem 1.17(a)] thus hold, we can therefore apply this result to deduce that $H^{i+1}(x)$ in (PI$^+$.2) is non-empty and compact for any $x \in \mathbb{R}^{n_x}$. Since $H^{i+1}(x) \subseteq H_r^{i+1}(x)$ for any $x \in \mathbb{R}^{n_x}$ by definition from (PI$^+$.3), $H_r^{i+1}(x)$ is also non-empty for any $x \in \mathbb{R}^{n_x}$.

On the other hand, $H_r^{i+1}$ is outer semicontinuous by [9, Lemma 5.16]. Furthermore, again by [9, Lemma 5.16], $H_r^{i+1}$ is locally bounded when $H^{i+1}$ also is, which we now show by applying [27, Theorem 7.41(a)]. Indeed, let $x \in \mathbb{R}^{n_x}$ and denote $\bar{V}^{i+1}(x) := \min_{u \in \mathcal{U}(x)} \{\ell(x, u) + V_r^i(f(x, u))\}$,

which is well-defined as $H^{i+1}$ is non-empty. Since $\bar{V}^{i+1}(x) \le \ell(x, h_r^{*,i}(x)) + V_r^i(f(x, h_r^{*,i}(x))) = V_r^i(x)$ for $h_r^{*,i} \in H_r^{*,i}$ (recall that $H_r^{*,i}(x)$ is non-empty for any $x \in \mathbb{R}^{n_x}$ by IH) and $V_r^i(x) \le \bar{\alpha}_V(\sigma(x))$ again by the IH, we have $\bar{V}^{i+1}(x) \le \bar{\alpha}_V(\sigma(x))$. $\bar{V}^{i+1}(x)$ is thus bounded from above at any $x \in \mathbb{R}^{n_x}$. To see this, let $\mathcal{V}$ be a neighborhood of $x$, and since $\sigma$ and $\bar{\alpha}_V$ are continuous by SA3, there exists some finite $M > 0$ such that $\bar{V}^{i+1}(x) \le \sup_{x' \in \mathcal{V}} \{\bar{\alpha}_V(\sigma(x'))\} = M$. Hence $\bar{V}^{i+1}$ is bounded from above in a neighborhood of $x$. By invoking [27, Theorem 7.41(a)], it follows that $H^{i+1}$ is locally bounded in $\mathcal{V}$. Since $x$ is arbitrary, it follows that $H^{i+1}$ is locally bounded on $\mathbb{R}^{n_x}$ and so is $H_r^{i+1}$.

### F. Proof of Lemma 6

First, we show there exists $h_r^{i+1} \in H_r^{i+1}$ such that $J(\cdot, h_r^{i+1}) \le V_r^i$. For this purpose, since $H_r^{i+1} \subseteq H_r^{i+1}$ by definition of $H_r^{i+1}$ in (PI$^+$.3), it is sufficient to show $J(\cdot, h^{i+1}) \le V_r^i$ for any $h^{i+1} \in H^{i+1}$. To do so, we proceed like in [28, Section 4.2]. Let $x \in \mathbb{R}^{n_x}$. We have $V_r^i(x) = J(x, h_r^{*,i}) \le \bar{\alpha}_V(\sigma(x))$ for any $h_r^{*,i} \in H_r^{*,i}$ by IH and let $h^{i+1} \in H^{i+1}$, which is possible in view of Lemma 4. It follows that $V_r^i(x) = \ell(x, h_r^{*,i}(x)) + V_r^i(f(x, h_r^{*,i}(x))) \ge \ell(x, h^{i+1}(x)) + V_r^i(f(x, h^{i+1}(x)))$. By repeating the same reasoning on $V_r^i(f(x, h^{i+1}(x)))$ and denoting $v = f(x, h^{i+1}(x))$, we derive that $V_r^i(x) \ge \ell(x, h^{i+1}(x)) + V_r^i(v) = \ell(x, h^{i+1}(x)) + \ell(v, h_r^{*,i}(v)) + V_r^i(f(v, h_r^{*,i}(v))) \ge \ell(x, h^{i+1}(x)) + \ell(v, h^{i+1}(v)) + V_r^i(f(v, h^{i+1}(v)))$. We can continue this process infinitely many times to obtain an infinite sum, which is bounded as such sum is: (i) upper-bounded by $V_r^i(x)$, which itself is finite in view of $V_r^i(x) \le \bar{\alpha}_V(\sigma(x))$ by IH; (ii) lower-bounded by 0, since it is a sum of non-negative terms. In this manner, we derive that

$$V_r^i(x) \ge J(x, h^{i+1}) \quad (29)$$

for any $h^{i+1} \in H^{i+1} \subseteq H_r^{i+1}$. Thus, we can apply the steps of [20, Claim 24] and derive that there exists $h_r^{*,i+1} \in H_r^{i+1}$ such that $V_r^{i+1}(x) = J(x, h_r^{*,i+1})$ in view of the outer semicontinuity and local boundedness of $H_r^{i+1}$. Hence, $H_r^{*,i+1}(x)$ is non-empty for all $x \in \mathbb{R}^{n_x}$. Furthermore, by definition of $V_r^{i+1}$ in (PI$^+$.4), we have that $V_r^{i+1}(x) \le J(x, h_r^{i+1})$ for any $h_r^{i+1} \in H_r^{i+1}$, and by (29), we conclude that $V_r^{i+1}(x) \le J(x, h^{i+1}) \le V_r^i(x) \le \bar{\alpha}_V(\sigma(x))$. On the other hand, $J(x, h_r^{*,i+1}) = \ell(x, h_r^{*,i+1}(x)) + J(f(x, h_r^{*,i+1}(x)), h_r^{*,i+1})$ for $h_r^{*,i+1} \in H_r^{*,i+1}$ and hence items (i)-(ii) of Lemma 6 are verified and the proof is complete.

### G. Proof of Lemma 9

To prove the lower semicontinuity of $V_r^{i+1}$, we show that, for any $\varepsilon > 0$, for any $x \in \mathbb{R}^{n_x}$ and any sequence$^9 x_n \to x$, there exists $N \in \mathbb{Z}_{>0}$ such that for any $n \ge N$, $V_r^{i+1}(x_n) \ge V_r^{i+1}(x) - \varepsilon$.

Since $H_r^{*,i+1}(x) \subseteq H_r^{i+1}(x)$ for any $x \in \mathbb{R}^{n_x}$, by Lemma 8 there exists $\psi = (\phi, v) \in S^{i+1}(x)$ with $S^{i+1}$ defined after (21), such that for any $x \in \mathbb{R}^{n_x}$ and $k \in \mathbb{Z}_{\ge 0}$,

$$\sigma(\phi(k, x)) \le \beta(\sigma(x), k) \quad (30)$$

<footnote>$^9$The limits of sequences in the appendices are understood for $n \to \infty$.</footnote>
SA2. Hence, we deduce from [13, Lemma 4]

$$
\begin{align}
& \rho_W(W(v)) - \rho_W(W(x)) \nonumber \\
& \le 2q_W \left( \chi_W(\ell(x, h^0(x))) + \alpha_1 \circ \alpha_W^{-1}(2\chi_W(\ell(x, h^0(x)))) \right) \nonumber \\
& \qquad \times \chi_W(\ell(x, h^0(x))) - q_W(1/4\alpha_W(\sigma(x)))^{1/4}\alpha_W(\sigma(x)) \nonumber \\
& = \ell(x, h^0(x))\chi_W(\ell(x, h^0(x))) - \tilde{\alpha}_W(\sigma(x)) \tag{28}
\end{align}
$$

where $\tilde{\alpha}_W = q_W(\frac{1}{4}\alpha_W)^{\frac{1}{4}}\alpha_W \in \mathcal{K}_\infty$. In view of (27) and (28), it follows that $Y^0(v) - Y^0(x) \le -\chi_W(\ell(x, h^0(x)))\ell(x, h^0(x)) + \ell(x, h^0(x))\chi_W(\ell(x, h^0(x))) - \tilde{\alpha}_W(\sigma(x)) \le -\tilde{\alpha}_W(\sigma(x))$. We have shown that the second line in (20) holds with $\alpha_Y = \tilde{\alpha}_W \in \mathcal{K}_\infty$. The case is complete.

### D. Proof of Lemma 3

The proof follows by application of Lemma 2 and Lemma 14 in Appendix V. Indeed, we apply Lemma 14 with $\alpha = \mathbb{I} - \tilde{\alpha}_Y$, where $\tilde{\alpha}_Y := \alpha_Y \circ \bar{\alpha}_Y^{-1}$. For any $x \in \mathbb{R}^{n_x}$, we consider the sequence $s_k(x)$, $k \in \mathbb{Z}_{\ge 0}$, defined as $s_k(x) = Y^0(\phi(k, x))$. We note that $s_{k+1}(x) \le \alpha(s_k(x))$ as required. This property follows from (20), which implies $\tilde{\alpha}_Y(Y^0(x)) = \alpha_Y \circ \bar{\alpha}_Y^{-1}(Y^0(x)) \le \alpha_Y(\sigma(x))$ hence $Y^0(\phi(k+1, x)) \le Y^0(\phi(k, x)) - \tilde{\alpha}_Y(Y^0(\phi(k, x)))$ for any $x \in \mathbb{R}^{n_x}$ and $k \in \mathbb{Z}_{\ge 0}$. Note moreover that $\mathbb{I} - \tilde{\alpha}_Y$ is indeed continuous, zero at zero, $\alpha(s) < s$ for all $s > 0$ and non-negative. Hence Lemma 14 generates $\tilde{\beta}_x \in \mathcal{KL}$ such that $Y^0(\phi^0(k, x)) \le \tilde{\beta}_x(Y^0(x), k)$ for any $x \in \mathbb{R}^{n_x}$ and $k \in \mathbb{Z}_{\ge 0}$, and since $\alpha$ is uniform in $x$, $\tilde{\beta}_x := \tilde{\beta}$. Again by (20), we obtain that $\alpha_Y(\sigma(\phi^0(k, x))) \le \tilde{\beta}(\bar{\alpha}_Y(\sigma(x)), k)$. Hence the result of Lemma 3 holds with $\tilde{\beta} = \bar{\alpha}_Y^{-1}(\tilde{\beta}(\bar{\alpha}_Y(\cdot), \cdot)) \in \mathcal{KL}$.

### E. Proof of Lemma 4

We prove that the conditions of [27, Theorem 1.17(a)] are verified to first show that $H^{i+1}(x)$ is non-empty for any $x \in \mathbb{R}^{n_x}$. Let $g^{i+1} : (x, u) \mapsto \ell(x, u) + V_r^i(f(x, u)) + \delta_{\mathcal{U}(x)}(u)$ be defined on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$. The map $g^{i+1}$ is lower semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ by item (i) of Assumption 2; (ii) $V_r^i$ is lower semicontinuous on $\mathbb{R}^{n_x}$ by IH; (iii) $(x, u) \mapsto \delta_{\mathcal{U}(x)}(u)$ is lower semicontinuous on $\mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ by Lemma 12 in Appendix V as $\mathcal{U}$ is outer semicontinuous on $\mathbb{R}^{n_x}$ by item (iii) of Assumption 2. Moreover, $g^{i+1}$ is proper as $g^{i+1}(x, u) > -\infty$ for any $(x, u) \in \mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and $g^{i+1}(x, u) < \infty$ for any $(x, u) \in \mathcal{W}$, as $\mathcal{U}(x)$ is non-empty for any $x \in \mathbb{R}^{n_x}$. In addition, as $g^{i+1}(x, u) \ge \ell(x, u)$ for any $(x, u) \in \mathbb{R}^{n_x} \times \mathbb{R}^{n_u}$ and $\ell$ is level-bounded in $u$, locally uniform in $x$ by item (ii) of Assumption 2, $(x, u) \mapsto g^{i+1}(x, u)$ is level-bounded in $u$, locally uniform in $x$ for any $x \in \mathbb{R}^{n_x}$ by Lemma 13 in Appendix V. All the conditions of [27, Theorem 1.17(a)] thus hold, we can therefore apply this result to deduce that $H^{i+1}(x)$ in (PI$^+$.2) is non-empty and compact for any $x \in \mathbb{R}^{n_x}$. Since $H^{i+1}(x) \subseteq H_r^{i+1}(x)$ for any $x \in \mathbb{R}^{n_x}$ by definition from (PI$^+$.3), $H_r^{i+1}(x)$ is also non-empty for any $x \in \mathbb{R}^{n_x}$.

On the other hand, $H_r^{i+1}$ is outer semicontinuous by [9, Lemma 5.16]. Furthermore, again by [9, Lemma 5.16], $H_r^{i+1}$ is locally bounded when $H^{i+1}$ also is, which we now show by applying [27, Theorem 7.41(a)]. Indeed, let $x \in \mathbb{R}^{n_x}$ and denote $\bar{V}^{i+1}(x) := \min_{u \in \mathcal{U}(x)} \{\ell(x, u) + V_r^i(f(x, u))\}$,

which is well-defined as $H^{i+1}$ is non-empty. Since $\bar{V}^{i+1}(x) \le \ell(x, h_r^{*,i}(x)) + V_r^i(f(x, h_r^{*,i}(x))) = V_r^i(x)$ for $h_r^{*,i} \in H_r^{*,i}$ (recall that $H_r^{*,i}(x)$ is non-empty for any $x \in \mathbb{R}^{n_x}$ by IH) and $V_r^i(x) \le \bar{\alpha}_V(\sigma(x))$ again by the IH, we have $\bar{V}^{i+1}(x) \le \bar{\alpha}_V(\sigma(x))$. $\bar{V}^{i+1}(x)$ is thus bounded from above at any $x \in \mathbb{R}^{n_x}$. To see this, let $\mathcal{V}$ be a neighborhood of $x$, and since $\sigma$ and $\bar{\alpha}_V$ are continuous by SA3, there exists some finite $M > 0$ such that $\bar{V}^{i+1}(x) \le \sup_{x' \in \mathcal{V}} \{\bar{\alpha}_V(\sigma(x'))\} = M$. Hence $\bar{V}^{i+1}$ is bounded from above in a neighborhood of $x$. By invoking [27, Theorem 7.41(a)], it follows that $H^{i+1}$ is locally bounded in $\mathcal{V}$. Since $x$ is arbitrary, it follows that $H^{i+1}$ is locally bounded on $\mathbb{R}^{n_x}$ and so is $H_r^{i+1}$.

### F. Proof of Lemma 6

First, we show there exists $h_r^{i+1} \in H_r^{i+1}$ such that $J(\cdot, h_r^{i+1}) \le V_r^i$. For this purpose, since $H_r^{i+1} \subseteq H_r^{i+1}$ by definition of $H_r^{i+1}$ in (PI$^+.3)$, it is sufficient to show $J(\cdot, h^{i+1}) \le V_r^i$ for any $h^{i+1} \in H^{i+1}$. To do so, we proceed like in [28, Section 4.2]. Let $x \in \mathbb{R}^{n_x}$. We have $V_r^i(x) = J(x, h_r^{*,i}) \le \bar{\alpha}_V(\sigma(x))$ for any $h_r^{*,i} \in H_r^{*,i}$ by IH and let $h^{i+1} \in H^{i+1}$, which is possible in view of Lemma 4. It follows that $V_r^i(x) = \ell(x, h_r^{*,i}(x)) + V_r^i(f(x, h_r^{*,i}(x))) \ge \ell(x, h^{i+1}(x)) + V_r^i(f(x, h^{i+1}(x)))$. By repeating the same reasoning on $V_r^i(f(x, h^{i+1}(x)))$ and denoting $v = f(x, h^{i+1}(x))$, we derive that $V_r^i(x) \ge \ell(x, h^{i+1}(x)) + V_r^i(v) = \ell(x, h^{i+1}(x)) + \ell(v, h_r^{*,i}(v)) + V_r^i(f(v, h_r^{*,i}(v))) \ge \ell(x, h^{i+1}(x)) + \ell(v, h^{i+1}(v)) + V_r^i(f(v, h^{i+1}(v)))$. We can continue this process infinitely many times to obtain an infinite sum, which is bounded as such sum is: (i) upper-bounded by $V_r^i(x)$, which itself is finite in view of $V_r^i(x) \le \bar{\alpha}_V(\sigma(x))$ by IH; (ii) lower-bounded by 0, since it is a sum of non-negative terms. In this manner, we derive that

$$V_r^i(x) \ge J(x, h^{i+1}) \quad (29)$$

for any $h^{i+1} \in H^{i+1} \subseteq H_r^{i+1}$. Thus, we can apply the steps of [20, Claim 24] and derive that there exists $h_r^{*,i+1} \in H_r^{i+1}$ such that $V_r^{i+1}(x) = J(x, h_r^{*,i+1})$ in view of the outer semicontinuity and local boundedness of $H_r^{i+1}$. Hence, $H_r^{*,i+1}(x)$ is non-empty for all $x \in \mathbb{R}^{n_x}$. Furthermore, by definition of $V_r^{i+1}$ in (PI$^+.4)$, we have that $V_r^{i+1}(x) \le J(x, h_r^{i+1})$ for any $h_r^{i+1} \in H_r^{i+1}$, and by (29), we conclude that $V_r^{i+1}(x) \le J(x, h^{i+1}) \le V_r^i(x) \le \bar{\alpha}_V(\sigma(x))$. On the other hand, $J(x, h_r^{*,i+1}) = \ell(x, h_r^{*,i+1}(x)) + J(f(x, h_r^{*,i+1}(x)), h_r^{*,i+1})$ for $h_r^{*,i+1} \in H_r^{*,i+1}$ and hence items (i)-(ii) of Lemma 6 are verified and the proof is complete.

### G. Proof of Lemma 9

To prove the lower semicontinuity of $V_r^{i+1}$, we show that, for any $\varepsilon > 0$, for any $x \in \mathbb{R}^{n_x}$ and any sequence$^9 x_n \to x$, there exists $N \in \mathbb{Z}_{\ge 0}$ such that for any $n \ge N$, $V_r^{i+1}(x_n) \ge V_r^{i+1}(x) - \varepsilon$.

Since $H_r^{*,i+1}(x) \subseteq H_r^{i+1}(x)$ for any $x \in \mathbb{R}^{n_x}$, by Lemma 8 there exists $\psi = (\phi, v) \in S^{i+1}(x)$ with $S^{i+1}$ defined after (21), such that for any $x \in \mathbb{R}^{n_x}$ and $k \in \mathbb{Z}_{\ge 0}$,

$$\sigma(\phi(k, x)) \le \beta(\sigma(x), k) \quad (30)$$

<footnote>$^9$The limits of sequences in the appendices are understood for $n \to \infty$.</footnote>
where $\beta \in \mathcal{KL}$ as in Lemma 8. From now on, we designate such solutions as “optimal” and we follow similar lines as in the proof of [20, Theorem 6]. Let $x \in \mathbb{R}^{n_x}$ and consider an arbitrary sequence $x_n \in \mathbb{R}^{n_x}$, $n \in \mathbb{Z}_{\ge 0}$, which converges to $x$, as well as an arbitrary sequence $u_n$, which converges to $u \in \mathbb{R}^{n_u}$ with $u_n \in H_r^{i+1}(x_n)$. We have $u \in H_r^{i+1}(x)$ by outer semicontinuity of $H_r^{i+1}$ in Lemma 4. Let $\varepsilon > 0$ and $\overline{N} \in \mathbb{Z}_{\ge 0}$ be sufficiently big such that

$$ \beta(\sigma(x) + 1, \overline{N}) \le \varepsilon_1 := \min\{\frac{1}{2} \cdot \bar{\alpha}_V^{-1}(\varepsilon/4), 1\}, \quad (31) $$

with $\bar{\alpha}_V$ from SA3. We assume without loss of generality that $n \in \mathbb{Z}_{\ge 0}$ is sufficiently large such that $\sigma(x_n) \le \sigma(x) + 1$, which is possible since $\sigma$ is continuous and the sequence $x_n$ converges to $x$ as $n$ tends to $\infty$. In view of (30), we have for all $k \in \mathbb{Z}_{\ge 0}$ and any optimal solution $(\phi, v) \in S^{i+1}(x_n)$,

$$ \begin{aligned} \sigma(\phi(k, x_n)) &\le \beta(\sigma(x_n), k) \le \beta(\sigma(x_n), 0) \\ &\le \beta(\sigma(x) + 1, 0). \end{aligned} \quad (32) $$

By item (iv) of Assumption 2 and continuity of $\beta$ and $\sigma$,

$$ \mathcal{M}(x) := \{z \in \mathbb{R}^{n_x} : \sigma(z) \le \beta(\sigma(x) + 1, 0) + 1\} \quad (33) $$

is compact. Moreover, $H_r^{i+1}(\mathcal{M}(x))$ is also compact. Indeed, $H_r^{i+1}$ is outer semicontinuous according to Lemma 4, hence $H_r^{i+1}(\mathcal{M}(x))$ is closed according to [27, Theorem 5.25(a)]. On the other hand, $H_r^{i+1}(\mathcal{M}(x))$ is bounded since $\mathcal{M}(x)$ itself is bounded and $H_r^{i+1}$ is locally bounded, according to [27, Proposition 5.15]. Hence, $\mathcal{M}(x) \times H_r^{i+1}(\mathcal{M}(x))$ is compact and, therefore, the continuity of $\sigma$ and $\ell$ ensured by SA2 and Assumption 2 is uniform by Heine theorem. As a result, for $\varepsilon/2\overline{N} > 0$, there exists $\delta_1 > 0$ such that for any $\chi_1, \chi_2 \in \mathcal{M}(x) \times H_r^{i+1}(\mathcal{M}(x))$,

$$ |\chi_1 - \chi_2| \le \delta_1 \Rightarrow |\ell(\chi_1) - \ell(\chi_2)| \le \varepsilon/2\overline{N}. \quad (34) $$

On the other hand, for $\varepsilon_1 > 0$, which is defined in (31), there exists $\delta_2 > 0$ such that for any $(x_1, x_2) \in \mathcal{M}(x) \times (\mathcal{M}(x) + \delta_2\mathbb{B})$,

$$ |x_1 - x_2| \le \delta_2 \Rightarrow |\sigma(x_1) - \sigma(x_2)| \le \varepsilon_1. \quad (35) $$

Let $\chi := (x, u)$ with $u \in H_r^{i+1}(x)$. In view of Lemma 5, $G^{i+1}$ is outer semicontinuous and locally bounded, it follows that system (21) is (nominally) well-posed according to [9, Theorem 6.30, Assumption 6.5 (A3)]. Consequently, the conditions of [9, Proposition 6.14] are verified, we thus apply this result with the triple $K = \{\chi\}$, $\tau = \overline{N}$, $\varepsilon = \min\{\delta_1, \delta_2\}$. As a result, there exists $\delta_3 > 0$ such that for any optimal solution $\psi_{i+1,n} = (\phi_{i+1,n}, v_{i+1,n}) \in S^{i+1}(x_n)$ with $n$ sufficiently large such that $|x-x_n| \le \delta_3$, there exists a solution $\tilde{\psi}_{i+1,n} = (\tilde{\phi}_{i+1,n}, \tilde{v}_{i+1,n}) \in S^{i+1}(x)$, not necessarily optimal, such that $\tilde{\psi}_{i+1,n}$ and $\psi_{i+1,n}$ are $(\tau, \varepsilon)$-close, see [9, Definition 5.23], i.e., for all $k \in \{0, \dots, \overline{N}\}$,

$$ |\psi_{i+1,n}(k, x_n) - \tilde{\psi}_{i+1,n}(k, x)| \le \min\{\delta_1, \delta_2\}. \quad (36) $$

Given $\psi_{i+1,n}$ and $\tilde{\psi}_{i+1,n}$, we now ensure that they lie in $\mathcal{M}(x) \times H_r^{i+1}(\mathcal{M}(x))$ for $k \in \{0, \dots, \overline{N}\}$ in order to exploit (34). For $k \in \{0, \dots, \overline{N}\}$, as $\tilde{\psi}_{i+1,n}$ is optimal and in view of (32), $\phi_{i+1,n}(k, x_n) \in \mathcal{M}(x)$ and it follows that $H_r^{i+1}(\phi_{i+1,n}(k, x_n)) \subseteq H_r^{i+1}(\mathcal{M}(x))$. Therefore, for $k \in \{0, \dots, \overline{N}\}$, in view of (36), $\phi_{i+1,n}(k, x) \in \mathcal{M}(x) + \delta_2\mathbb{B}$, and from (35) we deduce that

$$ |\sigma(\phi_{i+1,n}(k, x_n)) - \sigma(\tilde{\phi}_{i+1,n}(k, x))| \le \varepsilon_1. \quad (37) $$

In view of (31), $\varepsilon_1 \in (0, 1]$ and from (32) and (37), it follows that $\sigma(\hat{\phi}_{i+1,n}(k, x)) \le \sigma(\phi_{i+1,n}(k, x_n)) + \varepsilon_1 \le \beta(\sigma(x) + 1, 0) + \varepsilon_1 \le \beta(\sigma(x) + 1, 0) + 1$. We derive that, for all $k \in \{0, \dots, \overline{N}\}$, $\hat{\phi}_{i+1,n}(k, x)$ belongs to $\mathcal{M}(x)$ in view of (33) and $H_r^{i+1}(\hat{\phi}_{i+1,n}(k, x)) \subseteq H_r^{i+1}(\mathcal{M}(x))$. Hence, from (34), we have for all $k \in \{0, \dots, \overline{N}\}$,

$$ |\ell(\psi_{i+1,n}(k, x_n)) - \ell(\tilde{\psi}_{i+1,n}(k, x))| \le \varepsilon/2\overline{N}. \quad (38) $$

We now define $\overline{\psi}_{i+1}(k, x) = \hat{\psi}_{i+1,n}(k, x)$ for $k \in \{0, \dots, \overline{N} - 1\}$ and optimal $\overline{\psi}_{i+1}(k, x) = \psi_{i+1}(k - \overline{N}, \hat{\phi}_{i+1,n}(\overline{N}, x))$ for $k \in \{\overline{N}, \dots\}$. We note that $\overline{\psi}_{i+1} \in S^{i+1}(x)$. As a result, from (22),

$$ \begin{aligned} V_r^{i+1}(x) &\le \sum_{k=0}^{\infty} \ell(\overline{\psi}_{i+1}(k, x)) \\ &= \sum_{k=0}^{\overline{N}-1} \ell(\hat{\psi}_{i+1,n}(k, x)) + V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)). \end{aligned} \quad (39) $$

From (38), we deduce that

$$ V_r^{i+1}(x_n) \ge \sum_{k=0}^{\overline{N}-1} \ell(\psi_{i+1,n}(k, x_n)) \ge \sum_{k=0}^{\overline{N}-1} \ell(\tilde{\psi}_{i+1,n}(k, x)) - \varepsilon/2. \quad (40) $$

By adding and subtracting $V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x))$ to (40), in view of (39),

$$ \begin{aligned} V_r^{i+1}(x_n) &\ge \sum_{k=0}^{\infty} \ell(\overline{\psi}_{i+1}(k, x)) - \varepsilon/2 - V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)) \\ &\ge V_r^{i+1}(x) - \varepsilon/2 - V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)). \end{aligned} \quad (41) $$

The next inequality comes from $V_r^{i+1}(z) \le \bar{\alpha}_V(\sigma(z))$ for any $z \in \mathbb{R}^{n_x}$ by Lemma 6 as well as (37),

$$ \begin{aligned} V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)) &\le \bar{\alpha}_V(\sigma(\hat{\phi}_{i+1,n}(\overline{N}, x))) \le \bar{\alpha}_V(\sigma(\phi_{i+1,n}(\overline{N}, x_n)) + \varepsilon_1). \end{aligned} \quad (42) $$

Since $\bar{\alpha}_V \in \mathcal{K}_\infty$, then for all $a, b \ge 0$, $\bar{\alpha}_V(a + b) \le \bar{\alpha}_V(2a) + \bar{\alpha}_V(2b)$. Given $n \in \mathbb{Z}_{\ge 0}$ sufficiently big so that (32) holds, it follows from (31), (42) that $V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)) \le \bar{\alpha}_V(2\sigma(\phi_{i+1,n}(\overline{N}, x_n))) + \bar{\alpha}_V(2\varepsilon_1) \le \bar{\alpha}_V(2\beta(\sigma(x_n), \overline{N})) + \bar{\alpha}_V(2\varepsilon_1) \le \bar{\alpha}_V(2\beta(\sigma(x) + 1, \overline{N})) + \bar{\alpha}_V(2\varepsilon_1) \le 2\bar{\alpha}_V(2\varepsilon_1)$. By definition of $\varepsilon_1$ in (31) and the result just above, we deduce $V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)) \le \varepsilon/2$. Finally, the combination of the previous inequality and (41) leads to $V_r^{i+1}(x_n) \ge V_r^{i+1}(x) - \varepsilon$. We have proved that $V_r^{i+1}$ is lower semicontinuous at $x$, it is thus lower semicontinuous on $\mathbb{R}^{n_x}$ as $x$ has been arbitrarily selected.

## H. Sketch of proof of Corollary 2

Given Theorem 4, it suffices to show that Theorem 4 holds with $\beta := (s, k) \mapsto \frac{\overline{\alpha}_Y}{\overline{\alpha}_Y}(1 - \tilde{a}_Y)^k s$, which is $\exp(-\mathcal{KL})$. This is the case in view of the conditions of Corollary 2. To see this, note the following. First, Lemma 7 is verified with $\rho_V = \mathbb{I}$ and $\rho_W = \frac{1}{c_W}\mathbb{I}$ with the functions given in the case where $\chi_W \le \mathbb{I}$ in the proof of Lemma 7. Then, by following the steps in the proof of Lemma 3, we derive $\bar{\beta}(s, k) = (1 - \tilde{a}_Y)^k s$ such that $Y^i(\phi^i(k, x)) \le \bar{\beta}(Y^i(x), k)$ for all $x \in \mathbb{R}^{n_x}$. The desired result is derived by using the conditions of Corollary 2.
where $\beta \in \mathcal{KL}$ as in Lemma 8. From now on, we designate such solutions as “optimal” and we follow similar lines as in the proof of [20, Theorem 6]. Let $x \in \mathbb{R}^{n_x}$ and consider an arbitrary sequence $x_n \in \mathbb{R}^{n_x}$, $n \in \mathbb{Z}_{\ge 0}$, which converges to $x$, as well as an arbitrary sequence $u_n$, which converges to $u \in \mathbb{R}^{n_u}$ with $u_n \in H_r^{i+1}(x_n)$. We have $u \in H_r^{i+1}(x)$ by outer semicontinuity of $H_r^{i+1}$ in Lemma 4. Let $\varepsilon > 0$ and $\overline{N} \in \mathbb{Z}_{\ge 0}$ be sufficiently big such that

$$ \beta(\sigma(x) + 1, \overline{N}) \le \varepsilon_1 := \min\{1/2 \cdot \bar{\alpha}_V^{-1}(\varepsilon/4), 1\}, \quad (31) $$

with $\bar{\alpha}_V$ from SA3. We assume without loss of generality that $n \in \mathbb{Z}_{\ge 0}$ is sufficiently large such that $\sigma(x_n) \le \sigma(x) + 1$, which is possible since $\sigma$ is continuous and the sequence $x_n$ converges to $x$ as $n$ tends to $\infty$. In view of (30), we have for all $k \in \mathbb{Z}_{\ge 0}$ and any optimal solution $(\phi, v) \in S^{i+1}(x_n)$,

$$ \begin{aligned} \sigma(\phi(k, x_n)) &\le \beta(\sigma(x_n), k) \le \beta(\sigma(x_n), 0) \\ &\le \beta(\sigma(x) + 1, 0). \end{aligned} \quad (32) $$

By item (iv) of Assumption 2 and continuity of $\beta$ and $\sigma$,

$$ \mathcal{M}(x) := \{z \in \mathbb{R}^{n_x} : \sigma(z) \le \beta(\sigma(x) + 1, 0) + 1\} \quad (33) $$

is compact. Moreover, $H_r^{i+1}(\mathcal{M}(x))$ is also compact. Indeed, $H_r^{i+1}$ is outer semicontinuous according to Lemma 4, hence $H_r^{i+1}(\mathcal{M}(x))$ is closed according to [27, Theorem 5.25(a)]. On the other hand, $H_r^{i+1}(\mathcal{M}(x))$ is bounded since $\mathcal{M}(x)$ itself is bounded and $H_r^{i+1}$ is locally bounded, according to [27, Proposition 5.15]. Hence, $\mathcal{M}(x) \times H_r^{i+1}(\mathcal{M}(x))$ is compact and, therefore, the continuity of $\sigma$ and $\ell$ ensured by SA2 and Assumption 2 is uniform by Heine theorem. As a result, for $\varepsilon/2\overline{N} > 0$, there exists $\delta_1 > 0$ such that for any $\chi_1, \chi_2 \in \mathcal{M}(x) \times H_r^{i+1}(\mathcal{M}(x))$,

$$ |\chi_1 - \chi_2| \le \delta_1 \Rightarrow |\ell(\chi_1) - \ell(\chi_2)| \le \varepsilon/2\overline{N}. \quad (34) $$

On the other hand, for $\varepsilon_1 > 0$, which is defined in (31), there exists $\delta_2 > 0$ such that for any $(x_1, x_2) \in \mathcal{M}(x) \times (\mathcal{M}(x) + \delta_2\mathbb{B})$,

$$ |x_1 - x_2| \le \delta_2 \Rightarrow |\sigma(x_1) - \sigma(x_2)| \le \varepsilon_1. \quad (35) $$

Let $\chi := (x, u)$ with $u \in H_r^{i+1}(x)$. In view of Lemma 5, $G^{i+1}$ is outer semicontinuous and locally bounded, it follows that system (21) is (nominally) well-posed according to [9, Theorem 6.30, Assumption 6.5 (A3)]. Consequently, the conditions of [9, Proposition 6.14] are verified, we thus apply this result with the triple $K = \{\chi\}$, $\tau = \overline{N}$, $\varepsilon = \min\{\delta_1, \delta_2\}$. As a result, there exists $\delta_3 > 0$ such that for any optimal solution $\psi_{i+1,n} = (\phi_{i+1,n}, v_{i+1,n}) \in S^{i+1}(x_n)$ with $n$ sufficiently large such that $|x-x_n| \le \delta_3$, there exists a solution $\tilde{\psi}_{i+1,n} = (\tilde{\phi}_{i+1,n}, \tilde{v}_{i+1,n}) \in S^{i+1}(x)$, not necessarily optimal, such that $\tilde{\psi}_{i+1,n}$ and $\psi_{i+1,n}$ are $(\tau, \varepsilon)$-close, see [9, Definition 5.23], i.e., for all $k \in \{0, \dots, \overline{N}\}$,

$$ |\psi_{i+1,n}(k, x_n) - \tilde{\psi}_{i+1,n}(k, x)| \le \min\{\delta_1, \delta_2\}. \quad (36) $$

Given $\psi_{i+1,n}$ and $\tilde{\psi}_{i+1,n}$, we now ensure that they lie in $\mathcal{M}(x) \times H_r^{i+1}(\mathcal{M}(x))$ for $k \in \{0, \dots, \overline{N}\}$ in order to exploit (34). For $k \in \{0, \dots, \overline{N}\}$, as $\tilde{\psi}_{i+1,n}$ is optimal and in view of (32), $\phi_{i+1,n}(k, x_n) \in \mathcal{M}(x)$ and it follows that $H_r^{i+1}(\phi_{i+1,n}(k, x_n)) \subseteq H_r^{i+1}(\mathcal{M}(x))$. Therefore, for $k \in \{0, \dots, \overline{N}\}$, in view of (36), $\phi_{i+1,n}(k, x) \in \mathcal{M}(x) + \delta_2\mathbb{B}$, and from (35) we deduce that

$$ |\sigma(\phi_{i+1,n}(k, x_n)) - \sigma(\tilde{\phi}_{i+1,n}(k, x))| \le \varepsilon_1. \quad (37) $$

In view of (31), $\varepsilon_1 \in (0, 1]$ and from (32) and (37), it follows that $\sigma(\hat{\phi}_{i+1,n}(k, x)) \le \sigma(\phi_{i+1,n}(k, x_n)) + \varepsilon_1 \le \beta(\sigma(x) + 1, 0) + \varepsilon_1 \le \beta(\sigma(x) + 1, 0) + 1$. We derive that, for all $k \in \{0, \dots, \overline{N}\}$, $\hat{\phi}_{i+1,n}(k, x)$ belongs to $\mathcal{M}(x)$ in view of (33) and $H_r^{i+1}(\hat{\phi}_{i+1,n}(k, x)) \subseteq H_r^{i+1}(\mathcal{M}(x))$. Hence, from (34), we have for all $k \in \{0, \dots, \overline{N}\}$,

$$ |\ell(\psi_{i+1,n}(k, x_n)) - \ell(\tilde{\psi}_{i+1,n}(k, x))| \le \varepsilon/2\overline{N}. \quad (38) $$

We now define $\overline{\psi}_{i+1}(k, x) = \hat{\psi}_{i+1,n}(k, x)$ for $k \in \{0, \dots, \overline{N} - 1\}$ and optimal $\overline{\psi}_{i+1}(k, x) = \psi_{i+1}(k - \overline{N}, \hat{\phi}_{i+1,n}(\overline{N}, x))$ for $k \in \{\overline{N}, \dots\}$. We note that $\overline{\psi}_{i+1} \in S^{i+1}(x)$. As a result, from (22),

$$ \begin{aligned} V_r^{i+1}(x) &\le \sum_{k=0}^{\infty} \ell(\overline{\psi}_{i+1}(k, x)) \\ &= \sum_{k=0}^{\overline{N}-1} \ell(\hat{\psi}_{i+1,n}(k, x)) + V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)). \end{aligned} \quad (39) $$

From (38), we deduce that

$$ V_r^{i+1}(x_n) \ge \sum_{k=0}^{\overline{N}-1} \ell(\psi_{i+1,n}(k, x_n)) \ge \sum_{k=0}^{\overline{N}-1} \ell(\tilde{\psi}_{i+1,n}(k, x)) - \varepsilon/2. \quad (40) $$

By adding and subtracting $V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x))$ to (40), in view of (39),

$$ \begin{aligned} V_r^{i+1}(x_n) &\ge \sum_{k=0}^{\infty} \ell(\overline{\psi}_{i+1}(k, x)) - \varepsilon/2 - V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)) \\ &\ge V_r^{i+1}(x) - \varepsilon/2 - V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)). \end{aligned} \quad (41) $$

The next inequality comes from $V_r^{i+1}(z) \le \bar{\alpha}_V(\sigma(z))$ for any $z \in \mathbb{R}^{n_x}$ by Lemma 6 as well as (37),

$$ \begin{aligned} V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)) &\le \bar{\alpha}_V(\sigma(\hat{\phi}_{i+1,n}(\overline{N}, x))) \le \bar{\alpha}_V(\sigma(\phi_{i+1,n}(\overline{N}, x_n)) + \varepsilon_1). \end{aligned} \quad (42) $$

Since $\bar{\alpha}_V \in \mathcal{K}_\infty$, then for all $a, b \ge 0$, $\bar{\alpha}_V(a + b) \le \bar{\alpha}_V(2a) + \bar{\alpha}_V(2b)$. Given $n \in \mathbb{Z}_{\ge 0}$ sufficiently big so that (32) holds, it follows from (31), (42) that $V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)) \le \bar{\alpha}_V(2\sigma(\phi_{i+1,n}(\overline{N}, x_n))) + \bar{\alpha}_V(2\varepsilon_1) \le \bar{\alpha}_V(2\beta(\sigma(x_n), \overline{N})) + \bar{\alpha}_V(2\varepsilon_1) \le \bar{\alpha}_V(2\beta(\sigma(x) + 1, \overline{N})) + \bar{\alpha}_V(2\varepsilon_1) \le 2\bar{\alpha}_V(2\varepsilon_1)$. By definition of $\varepsilon_1$ in (31) and the result just above, we deduce $V_r^{i+1}(\hat{\phi}_{i+1,n}(\overline{N}, x)) \le \varepsilon/2$. Finally, the combination of the previous inequality and (41) leads to $V_r^{i+1}(x_n) \ge V_r^{i+1}(x) - \varepsilon$. We have proved that $V_r^{i+1}$ is lower semicontinuous at $x$, it is thus lower semicontinuous on $\mathbb{R}^{n_x}$ as $x$ has been arbitrarily selected.

## H. Sketch of proof of Corollary 2

Given Theorem 4, it suffices to show that Theorem 4 holds with $\beta := (s, k) \mapsto \frac{\overline{\alpha}_Y}{\overline{\alpha}_Y}(1 - \tilde{a}_Y)^k s$, which is $\exp(-\mathcal{KL})$. This is the case in view of the conditions of Corollary 2. To see this, note the following. First, Lemma 7 is verified with $\rho_V = \mathbb{I}$ and $\rho_W = \frac{1}{c_W}\mathbb{I}$ with the functions given in the case where $\chi_W \le \mathbb{I}$ in the proof of Lemma 7. Then, by following the steps in the proof of Lemma 3, we derive $\bar{\beta}(s, k) = (1 - \tilde{a}_Y)^k s$ such that $Y^i(\phi^i(k, x)) \le \bar{\beta}(Y^i(x), k)$ for all $x \in \mathbb{R}^{n_x}$. The desired result is derived by using the conditions of Corollary 2.