Bruno Scherrer
email: bruno.scherrer@inria.fr

Improved and Generalized Upper Bounds on the Complexity of Policy Iteration

Given a Markov Decision Process (MDP) with n states and m actions per state, we study the number of iterations needed by Policy Iteration (PI) algorithms to converge to the optimal γ-discounted optimal policy. We consider two variations of PI: Howard's PI that changes the actions in all states with a positive advantage, and Simplex-PI that only changes the action in the state with maximal advantage. We show that Howard's PI terminates after at most n(m -1)

, in which τ t ≤ n and τ r ≤ n. We explain why similar results seem hard to derive for Howard's PI. Finally, under the additional (restrictive) assumption that the state space is partitioned in two sets, respectively states that are transient and recurrent for all policies, we show that Howard's PI terminates after at most n(m -1) (⌈τ t log nτ t ⌉ + ⌈τ r log nτ r ⌉) = Õ(nm(τ t + τ r )) iterations while Simplex-PI terminates after n(m -1) (⌈nτ t log nτ t ⌉ + ⌈τ r log nτ r ⌉) = Õ(n 2 m(τ t + τ r )) iterations.

Introduction

We consider a discrete-time dynamic system whose state transition depends on a control. We assume that there is a state space X of finite size n. At state i ∈ {1, .., n}, the control is chosen from a control space A of finite size 1 m. The control a ∈ A specifies the transition probability p ij (a) = P(i t+1 = j|i t = i, a t = a) to the next state j. At each transition, the system is given a reward r(i, a, j) where r is the instantaneous reward function. In this context, we look for a stationary deterministic policy (a function π : X → A that maps states into controls2 ) that maximizes the expected discounted sum of rewards from any state i, called the value of policy π at state i:

v π (i) := E ∞ k=0 γ k r(i k , a k , i k+1 ) i 0 = i, ∀k ≥ 0, a k = π(i k ), i k+1 ∼ P(•|i k , a k )
where γ ∈ (0, 1) is a discount factor. The tuple X, A, p, r, γ is called a Markov Decision Process (MDP) [START_REF] Puterman | Markov Decision Processes[END_REF][START_REF] Bertsekas | Neurodynamic Programming[END_REF], and the associated problem is known as optimal control.

The optimal value starting from state i is defined as

v * (i) := max π v π (i).
For any policy π, we write P π for the n × n stochastic matrix whose elements are p ij (π(i)) and r π the vector whose components are j p ij (π(i))r(i, π(i), j). The value functions v π and v * can be seen as vectors on X. It is well known that v π is the solution of the following Bellman equation: v π = r π + γP π v π , that is v π is a fixed point of the affine operator T π : v → r π + γP π v. It is also well known that v * satisfies the following Bellman equation:

v * = max π (r π + γP π v * ) = max π T π v *
where the max operator is componentwise. In other words, v * is a fixed point of the nonlinear operator T : v → max π T π v. For any value vector v, we say that a policy π is greedy with respect to the value v if it satisfies:

π ∈ arg max π ′ T π ′ v or equivalently T π v = T v.
With some slight abuse of notation, we write G(v) for any policy that is greedy with respect to v. The notions of optimal value function and greedy policies are fundamental to optimal control because of the following property: any policy π * that is greedy with respect to the optimal value v * is an optimal policy and its value v π * is equal to v * .

Let π be some policy. We call advantage with respect to π the following quantity:

a π = max π ′ T π ′ v π -v π = T v π -v π .
We call the set of switchable states of π the following set

S π = {i, a π (i) > 0}.
Assume now that π is non-optimal (this implies that S π is a non-empty set). For any non-empty subset Y of S π , we denote switch(π, Y ) a policy satisfying:

∀i, switch(π, Y )(i) = G(v π )(i) if i ∈ Y π(i) if i ∈ Y.
The following result is well known (see for instance [START_REF] Puterman | Markov Decision Processes[END_REF]).

Lemma 1.

Let π be some non-optimal policy. If π ′ = switch(π, Y ) for some non-empty subset Y of S π , then v π ′ ≥ v π and there exists at least one state i such that v π ′ (i) > v π (i).

This lemma is the foundation of the well-known iterative procedure, called Policy Iteration (PI), that generates a sequence of policies (π k ) as follows.

π k+1 ← switch(π k , Y k ) for some set Y k such that ∅ Y k ⊆ S π k .
The choice for the subsets Y k leads to different variations of PI. In this paper we will focus on two specific variations:

• When for all iterations k, Y k = S π k , that is one switches the actions in all states with positive advantage with respect to π k , the above algorithm is known as Howard's PI; it can be seen then that

π k+1 ∈ G(v π k ). • When for all k, Y k is a singleton containing a state i k ∈ arg max i a π k (i), that is if
we only switch one action in the state with maximal advantage with respect to π k , we will call it Simplex-PI3 .

Since it generates a sequence of policies with increasing values, any variation of PI converges to the optimal policy in a number of iterations that is smaller than the total number of policies m n . In practice, PI converges in very few iterations. On random MDP instances, convergence often occurs in time sub-linear in n. The aim of this paper is to discuss existing and provide new upper bounds on the number of iterations required by Howard's PI and Simplex-PI that are much sharper than m n .

In the next sections, we describe some known results-see [START_REF] Ye | The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate[END_REF] for a recent and comprehensive review-about the number of iterations required by Howard's PI and Simplex-PI, along with some of our original improvements and extensions. 42 Bounds with respect to a Fixed Discount Factor γ < 1

A key observation for both algorithms, that will be central to the results we are about to discuss, is that the sequence they generate satisfies some contraction property5 . For any vector u ∈ R n , let u ∞ = max 1≤i≤n |u(i)| be the max-norm of u. Let 1 be the vector of which all components are equal to 1. Lemma 2 (Proof in Section A). The sequence

( v * -v π k ∞ ) k≥0 built by Howard's PI is contracting with coefficient γ. Lemma 3 (Proof in Section B). The sequence (1 T (v * -v π k )) k≥0 built by Simplex-PI is contracting with coefficient 1 -1-γ n .
Though this observation is widely known for Howard's PI, it was to our knowledge never mentionned explicitly in the literature for Simplex-PI. These contraction properties have the following immediate consequence 6 .

Corollary 1. Let V max = maxπ rπ ∞ 1-γ
be an upper bound on v π ∞ for all policies π. In order to get an ǫ-optimal policy, that is a policy

π k satisfying v * -v π k ∞ ≤ ǫ, Howard's PI requires at most log Vmax ǫ 1-γ iterations, while Simplex-PI requires at most n log nVmax ǫ 1-γ iterations.
These bounds depend on the precision term ǫ, which means that Howard's PI and Simplex-PI are weakly polynomial for a fixed discount factor γ. An important breakthrough was recently achieved by [START_REF] Ye | The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate[END_REF] who proved that one can remove the dependency with respect to ǫ, and thus show that Howard's PI and Simplex-PI are strongly polynomial for a fixed discount factor γ. Theorem 1 ([11]). Simplex-PI and Howard's PI both terminate after at most n(m -

1) n 1-γ log n 2 1-γ iterations. for v * -vπ k ∞ < ǫ is γ k Vmax < ǫ, which is implied by k ≥ log Vmax ǫ 1-γ > log Vmax ǫ log 1 γ . For Simplex-PI, we have v * -vπ k ∞ ≤ v * -vπ k 1 ≤ 1 -1-γ n k v * -vπ 0 1 ≤ 1 -1-γ n k nVmax
, and the conclusion is similar to that for Howard's PI.

The proof is based on the fact that PI corresponds to the simplex algorithm in a linear programming formulation of the MDP problem. Using a more direct proof, [START_REF] Hansen | Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor[END_REF] recently improved the result by a factor O(n) for Howard's PI.

Theorem 2 ([3]

). Howard's PI terminates after at most (nm + 1) 1 1-γ log n 1-γ iterations.

Our first two results, that are consequences of the contraction properties (Lemmas 2 and 3), are stated in the following theorems. Theorem 3 (Proof in Section C). Howard's PI terminates after at most n(m -1) 1 1-γ log 1 1-γ iterations.

Theorem 4 (Proof in Section D). Simplex-PI terminates after at most n(m -

1) n 1-γ log n 1-γ iterations.
Our result for Howard's PI is a factor O(log n) better than the previous best result of [START_REF] Hansen | Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor[END_REF].

Our result for Simplex-PI is only very slightly better (by a factor 2) than that of [START_REF] Ye | The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate[END_REF], and uses a proof that is more direct. Using more refined argument, we managed to also improve the bound for Simplex-PI by a factor O(log n). Theorem 5 (Proof in Section E). Simplex-PI terminates after at most n 2 (m -

1) 1 + 2 1-γ log 1 1-γ iterations.
Compared to Howard's PI, our bound for Simplex-PI is a factor O(n) larger. However, since one changes only one action per iteration, each iteration may have a complexity lower by a factor n: the update of the value can be done in time O(n 2 ) through the Sherman-Morrisson formula, though in general each iteration of Howard's PI, which amounts to compute the value of some policy that may be arbitrarily different from the previous policy, may require O(n 3 ) time. Overall, both algorithms seem to have a similar complexity.

It is easy to see that the linear dependency of the bound for Howard's PI with respect to n is optimal. We conjecture that the linear dependency of both bounds with respect to m is also optimal. The dependency with respect to the term 1 1-γ may be improved, but removing it is impossible for Howard's PI and very unlikely for Simplex-PI. [START_REF] Fearnley | Exponential lower bounds for policy iteration[END_REF] describes an MDP for which Howard's PI requires an exponential (in n) number of iterations for γ = 1 and [START_REF] Hollanders | The complexity of policy iteration is exponential for discounted markov decision processes[END_REF] argued that this holds also when γ is in the vicinity of 1. Though a similar result does not seem to exist for Simplex-PI in the literature, [START_REF] Melekopoglou | On the complexity of the policy improvement algorithm for markov decision processes[END_REF] consider four variations of PI that all switch one action per iteration, and show through specifically designed MDPs that they may require an exponential (in n) number of iterations when γ = 1.

Bounds for Simplex-PI that are independent of γ

In this section, we will describe some bounds that do not depend on γ but that will be based on some structural assumptions of the MDPs. On this topic, [START_REF] Post | The simplex method is strongly polynomial for deterministic markov decision processes[END_REF] recently showed the following result for deterministic MDPs.

Theorem 6 ([8]). If the MDP is deterministic, then Simplex-PI terminates after at most

O(n 5 m 2 log 2 n) iterations.
Given a policy π of a deterministic MDP, states are either on cycles or on paths induced by π. The core of the proof relies on the following lemmas that altogether show that cycles are created regularly and that significant progress is made every time a new cycle appears; in other words, significant progress is made regularly. Lemma 4. If the MDP is deterministic, after at most nm⌈2(n -1) log n⌉ iterations, either Simplex-PI finishes or a new cycle appears. Lemma 5. If the MDP is deterministic, when Simplex-PI moves from π to π ′ where π ′ involves a new cycle, we have

1 T (v π * -v π ′ ) ≤ 1 - 1 n 1 T (v π * -v π ).
Indeed, these observations suffice to prove7 that Simplex-PI terminates after O(n 4 m 2 log n 1-γ ) = Õ(n 4 m 2 ). Removing completely the dependency with respect to the discount factor γ-the term in O(log 1 1-γ )-requires a careful extra work described in [START_REF] Post | The simplex method is strongly polynomial for deterministic markov decision processes[END_REF], which incurs an extra term of order O(n log(n)).

At a more technical level, the proof of [START_REF] Post | The simplex method is strongly polynomial for deterministic markov decision processes[END_REF] critically relies on some properties of the vector x π = (I -γP T π ) -1 1 that provides a discounted measure of state visitations along the trajectories induced by a policy π starting from a uniform distribution:

∀i ∈ X, x π (i) = n ∞ t=0 γ t P(i t = i | i 0 ∼ U, a t = π(i t )),
where U denotes the uniform distribution on the state space X. For any policy π and state i, we trivially have x π (i) ∈ 1, n 1-γ . The proof exploits the fact that x π (i) belongs to the set (1, n) when i is on a path of π, while x π (i) belongs to the set ( 11-γ , n 1-γ ) when i is on a cycle of π. As we are going to show, it is possible to extend the proof of [START_REF] Post | The simplex method is strongly polynomial for deterministic markov decision processes[END_REF] to stochastic MDPs. Given a policy π of a stochastic MDP, states are either in recurrent classes or transient classes (these two categories respectively generalize those of cycles and paths). We will consider the following structural assumption. Assumption 1. Let τ t ≥ 1 and τ r ≥ 1 be the smallest constants such that for all policies π and all states i,

(1 ≤ )x π (i) ≤ τ t if i is transient for π, and n (1 -γ)τ r ≤ x π (i) ≤ n 1 -γ if i is recurrent for π.
The constant τ t (resp. τ r ) can be seen as a measure of the time needed to leave transient states (resp. the time needed to revisit states in recurrent classes). In particular, when γ tends to 1, it can be seen that τ t is an upper bound of the expected time L needed to "Leave the set of transient states", since for any policy π,

lim γ→1 τ t ≥ 1 n lim γ→1 i transient for π x π (i) = ∞ t=0 P(i t transient for π | i 0 ∼ U, a t = π(i t )) = E [ L | i 0 ∼ U, a t = π(i t )] .
Similarly, when γ is in the vicinity of 1, 1 τr is the minimal asymptotic frequency8 in recurrent states given that one starts from a random uniform state, since for any policy π and recurrent state i:

lim γ→1 1 -γ n x π (i) = lim γ→1 (1 -γ) ∞ t=0 γ t P(i t = i | i 0 ∼ U, a t = π(i t )) = lim T →∞ 1 T T -1 t=0 P(i t = i | i 0 ∼ U, a t = π(i t )).
With

1 T (v π * -v π ′ ) ≤ 1 - 1 τ r 1 T (v π * -v π ).
From these generalized observations, we can deduce the following original result.

Similar results for Howard's PI?

One may then wonder whether similar results can be derived for Howard's PI. Unfortunately, and as quickly mentionned by [START_REF] Post | The simplex method is strongly polynomial for deterministic markov decision processes[END_REF], the line of analysis developped for Simplex-PI does not seem to adapt easily to Howard's PI, because simultaneously switching several actions can interfere in a way that the policy improvement turns out to be small. We can be more precise on what actually breaks in the approach we have described so far. However, on the other hand, we did not manage to adapt Lemma 5 nor Lemma 7. In fact, it is unlikely that a result similar to that of Lemma 5 will be shown to hold for Howard's PI. In a recent deterministic example due to [START_REF] Hansen | Lower bounds for howard's algorithm for finding minimum mean-cost cycles[END_REF] to show that Howard's PI may require at most O(n 2 ) iterations, new cycles are created every single iteration but the sequence of values satisfies9 for all iterations k < n 2 4 + n 4 and states i,

v * (i) -v π k+1 (i) ≥ 1 - 2 n k (v * (i) -v π k (i)).
Contrary to Lemma 5, as k grows, the amount of contraction gets (exponentially) smaller and smaller. With respect to Simplex-PI, this suggests that Howard's PI may suffer from subtle specific pathologies. In fact, the problem of determining the number of iterations required by Howard's PI has been challenging for almost 30 years. It was originally identified as an open problem by [START_REF] Schmitz | How good is howard's policy improvement algorithm[END_REF]. In the simplest-deterministic-case, the question is still open: the currently best known lower bound is the O(n 2 ) bound by [START_REF] Hansen | Lower bounds for howard's algorithm for finding minimum mean-cost cycles[END_REF] we have just mentionned, while the best known upper bound is O( m n n ) (valid for all MDPs) due to [START_REF] Mansour | On the complexity of policy iteration[END_REF].

On the positive side, an adaptation of the line of proof we have considered so far can be carried out under the following assumption.

Assumption 2. The state space X can be partitioned in two sets T and R such that for all policies π, the states of T are transient and those of R are recurrent.

Indeed, under this assumption, we can prove for Howard's PI a variation of Lemma 7 introduced for Simplex-PI.

Lemma 10. For an MDP satisfying Assumptions 1-2, suppose Howard's PI moves from π to π ′ and that π ′ involves a new recurrent class. Then

1 T (v π * -v π ′ ) ≤ 1 - 1 τ r 1 T (v π * -v π ).
And we can deduce the following original bound (that also applies to Simplex-PI).

A Contraction property for Howard's PI (Proof of Lemma 2)

For any k, using the facts that {∀π,

T π v π = v π }, {T π * v π k-1 ≤ T π k v π k-1 }
and {Lemma 1 and P π k is positive definite}, we have

v π * -v π k = T π * v π * -T π * v π k-1 + T π * v π k-1 -T π k v π k-1 + T π k v π k-1 -T π k v π k ≤ γP π * (v π * -v π k-1 ) + γP π k (v π k-1 -v π k ) ≤ γP π * (v π * -v π k-1 ).
Since v π *v π k is non negative, we can take the max norm and get:

v π * -v π k ∞ ≤ γ v π * -v π k-1 ∞ .

B Contraction property for Simplex-PI (Proof of Lemma 3)

By using the fact that {v π = T π v π ⇒ v π = (I -γP π ) -1 r π }, we have that for all pairs of policies π and π ′ .

v π ′ -v π = (I -γP π ′ ) -1 r π ′ -v π = (I -γP π ′ ) -1 (r π ′ + γP π ′ v π -v π ) = (I -γP π ′ ) -1 (T π ′ v π -v π ). (1)
On the one hand, by using this lemma and the fact that

{T π k+1 v π k -v π k ≥ 0}, we have for any k: v π k+1 -v π k = (I -γP k+1 ) -1 (T π k+1 v π k -v π k ) ≥ T π k+1 v π k -v π k , which implies that 1 T (v π k+1 -v π k ) ≥ 1 T (T π k+1 v π k -v π k ). (2)
On the other hand, using Equation ( 1) and the facts that

{ (I -γP π * ) -1 ∞ = 1 1-γ and (I -γP π * ) -1 is positive definite}, {max s T π k+1 v π k (s) = max s,π T π v π k (s)} and
{∀x ≥ 0, max s x(s) ≤ 1 T x}, we have:

v π * -v π k = (I -γP π * ) -1 (T π * v π k -v π k ) ≤ 1 1 -γ max s T π * v π k (s) -v π k (s) ≤ 1 1 -γ max s T π k+1 v π k (s) -v π k (s) ≤ 1 1 -γ 1 T (T π k+1 v π k -v π k ), which implies (using {∀x, 1 T x ≤ n x ∞ }) that 1 T (T π k+1 v π k -v π k ) ≥ (1 -γ) v π * -v π k ∞ ≥ 1 -γ n 1 T (v π * -v π k ). (3)
Combining Equations ( 2) and (3), we get:

1 T (v π * -v π k+1 ) = 1 T (v π * -v π k ) -1 T (v π k+1 -v π k ) ≤ 1 T (v π * -v π k ) - 1 -γ n 1 T (v π * -v π k ) = 1 - 1 -γ n 1 T (v π * -v π k ).

C A bound for Howard's PI when γ < 1 (Proof of Theorem 3)

For any k, by using Equation ( 1) and the fact {v *v π k ≥ 0 and P π k positive definite}, we have:

v * -T π k v * = (I -γP π k )(v * -v π k ) ≤ v * -v π k . Since v * -T π k v * is
non negative, we can take the max norm and, using Lemma 2, Equation ( 1) and the fact that

{ (I -γP π0 ) -1 ∞ = 1 1-γ }, we get: v * -T π k v * ∞ ≤ v * -v π k ∞ ≤ γ k v π * -v π0 ∞ = γ k (I -γP π0 ) -1 (v * -T π0 v * ) ∞ ≤ γ k 1 -γ v * -T π0 v * ∞ . ( 4
)
By definition of the max-norm, there exists a state

s 0 such that v * (s 0 ) -[T π0 v * ](s 0 ) = v * -T π0 v * ∞ .
From Equation (4), we deduce that for all k,

v * (s 0 ) -[T π k v * ](s 0 ) ≤ v * -T π k v * ∞ ≤ γ k 1 -γ v * -T π0 v * ∞ = γ k 1 -γ (v * (s 0 ) -[T π0 v * ](s 0 )).
As a consequence, the action π k (s 0 ) must be different from π 0 (s 0 ) when

γ k 1-γ < 1, that is for all values of k satisfying k ≥ k * = log 1 1-γ 1-γ > log 1 1-γ log 1 γ .
In other words, if some policy π is not optimal, then one of its non-optimal actions will be eliminated for good after at most k * iterations. By repeating this argument, one can eliminate all non-optimal actions (they are at most n(m -1)), and the result follows.

D A bound for Simplex-PI when γ < 1 (Proof of Theorem 4)

Using {∀x ≥ 0, x ∞ ≤ 1 T x}, Lemma 3, {∀x, 1 T x ≤ n x ∞ }, Equation (1) and { (I - γP π0 ) -1 ∞ = 1 1-γ }, we have for all k, v π * -T π k v π * ∞ ≤ v π * -v π k ∞ ≤ 1 T (v π * -v π k ) ≤ 1 - 1 -γ n k 1 T (v π * -v π0 ) ≤ n 1 - 1 -γ n k v π * -v π0 ∞ = n 1 - 1 -γ n k (I -γP π0 ) -1 (v * -T π0 v * ) ∞ ≤ n 1 -γ 1 - 1 -γ n k v π * -T π0 v π * ∞
Similarly to the proof for Howard's PI, we deduce that a non-optimal action is eliminated

after at most k * = n 1-γ log n 1-γ ≥ log n 1-γ log(1-1-γ n )
, and the overall number of iterations is obtained by noting that there are at most n(m -1) non optimal actions to eliminate.

Supplementary Material

E Another bound for Simplex-PI when γ < 1 (Proof of Theorem 5)

This second bound for Simplex-PI is a factor O(log n) better, but requires a slightly more careful analysis.

At each iteration k, let s k be the state in which an action is switched. We have (by definition of the algorithm):

Tπ k+1 vπ k (s k ) -vπ k (s k ) = max π,s Tπvπ k (s) -vπ k (s).
Starting with arguments similar to those for the contraction property of Simplex-PI, we have:

vπ * -vπ k = (I -γPπ * ) -1 (Tπ * vπ k -vπ k ) {Lemma 1} ≤ 1 1 -γ max s Tπ * vπ k (s) -vπ k (s) { (I -γPπ * ) -1 ∞ = 1 1 -γ and (I -γPπ * ) -1 ≻ 0} ≤ 1 1 -γ (Tπ k+1 vπ k (s k ) -vπ k (s k )), {By definition of s k } which implies that vπ * -vπ k ∞ ≤ 1 1 -γ (Tπ k+1 vπ k (s k ) -vπ k (s k )). (5)
On the other hand, we have:

vπ k+1 -vπ k = (I -γPπ k+1 ) -1 (Tπ k+1 vπ k -vπ k ) {Lemma 1} ≥ Tπ k+1 vπ k -vπ k , {(I -γPπ k+1 ) -1 ≻ 0 and Tπ k+1 vπ k -vπ k ≥ 0} which implies that vπ k+1 (s k ) -vπ k (s k ) ≥ Tπ k+1 vπ k (s k ) -vπ k (s k ). ( 6
)
Write ∆ k = vπ *vπ k . From Equations ( 5) and ( 6), we deduce that:

∆ k+1 (s k ) ≤ ∆ k (s k ) -(1 -γ) ∆ k ∞ = 1 -(1 -γ) ∆ k ∞ ∆ k (s k ) ∆ k (s k ).
This implies in particular that

∆ k+1 (s k ) ≤ γ∆ k (s k ), but also-since ∆ k (s k ) and ∆ k+1 (s k ) are non-negative-that ∆ k ∞ ≤ 1 1 -γ ∆ k (s k ).
Now, write n k the vector on the state space such that n k (s) is the number of times state s has been switched until iteration k (including k). Since by Lemma 1 the sequence (∆ k ) k≥0 is non-increasing, we have

∆ k ∞ ≤ 1 1 -γ ∆ k (s k ) ≤ γ n k-1 (s k ) 1 -γ ∆0(s k ) ≤ γ n k-1 (s k ) 1 -γ ∆0 ∞.
At any iteration k, let s * k = arg maxs n k-1 (s). Since at each iteration k, one of the n component is increased by 1, we necessarily have

n k-1 (s * k ) ≥ k -1 n .
Write k * ≤ k -1 the last iteration when the state s * k was updated, such that we have

n k-1 (s * k ) = n k * -1 (s k * ). Since ( ∆ k ∞)k≥0
is non-increasing (using again Lemma 1), we have

∆ k ∞ ≤ ∆ k * ∞ ≤ γ n k * -1 (s k * ) 1 -γ ∆0 ∞ = γ n k-1 (s * k ) 1 -γ ∆0 ∞ ≤ γ ⌊ k-1 n ⌋ 1 -γ ∆0 ∞ .
We are now ready to finish the proof. We have

vπ * -Tπ k vπ * ∞ ≤ ∆ k ∞ ≤ γ ⌊ k-1 n ⌋ 1 -γ ∆0 ∞ ≤ γ ⌊ k-1 n ⌋ (1 -γ) 2 vπ * -Tπ 0 vπ * ∞ .
Using the relation n k-1 n ≥ kn and arguments similar to the previous proofs, we deduce that a non-optimal action is eliminated after at most n 1 + 2 1-γ log 1 1-γ iterations, and the result follows from the fact that there are at most n(m -1) non-optimal actions.

F A general bound for Simplex-PI (Proof of Theorem 7)

The proof we give here is strongly inspired by that for the deterministic case of [START_REF] Post | The simplex method is strongly polynomial for deterministic markov decision processes[END_REF]: the steps (a series of lemmas) are similar. There are essentially two differences. First our arguments are somewhat more direct in that we do not refer to linear programming. Second, it is more general: for any policy π, we need to consider the set of transient states (respectively recurrent classes) instead of the set of path states (respectively cycles).

For any policy π, write R(π) for the set of states that are recurrent for π. Recall that xπ = (I -γPπ T ) -1 1. A useful corollary of Lemma 1 is that for any pair of policies π and π ′ ,

1 T (v π ′ -vπ) = x π ′ T (T π ′ vπ -vπ). ( 7
)
With some slight abuse of notation, we will write that s ∈ R(π) if there exists a recurrent class R ∈ R(π) that contains s. We will repeatedly exploit Assumption 1, that we restate here for clarity:

∀s ∈ R(π), n (1 -γ)τr ≤ xπ(s) ≤ n 1 -γ , ( 8
)
∀s ∈ R(π), xπ(s) ≤ τt. ( 9
)
As mentioned, before, the proof is structured in two steps: first, we will show that recurrent classes are created often; then we will show that significant progress is made every time a new recurrent class appears.

F.1 Part 1: Recurrent classes are created often

Lemma 11. Suppose one moves from policy π to policy π ′ without creating any recurrent class. Let π † be the final policy before either a new recurrent class appears or the algorithm terminates. Then

Proof. The arguments are similar to those for the proof of Theorem 4. On the one hand, we have:

1 T (v π ′ -vπ) ≥ 1 T (T π ′ vπ -vπ).
(10) On the other hand, we have

1 T (vπ † -vπ) = 1 T (I -γPπ † ) -1 (Tπ † vπ -vπ) = x T π † (Tπ † vπ -vπ) = s ∈R(π † ) xπ † (s)(Tπ † vπ(s) -vπ(s)) + s∈R(π † ) xπ † (s)(Tπ † vπ(s) -vπ(s)) ≤ nτt max s ∈R(π † ) Tπ † vπ(s) -vπ(s) + n 2 1 -γ max s∈R(π † )
Tπ † vπ(s)vπ(s). {Equations (8)-( 9)} Since by assumption cycles of π † are also cycles of π, we deduce that for all s ∈ R(π † ), π † (s) = π(s), so that max s∈R(π † ) Tπ † vπ(s)vπ(s) = 0. Thus, the second term of the above r.h.s. is null and

1 T (vπ † -vπ) ≤ nτt max s Tπ † vπ(s) -vπ(s) ≤ nτt max s T π ′ vπ(s) -vπ(s) {max s T π ′ vπ(s) = s,π Tπvπ(s)} = nτt1 T (T π ′ vπ -vπ).
(11) Combining Equations ( 10) and ( 11), we get:

1 T (vπ † -v π ′ ) = 1 T (vπ † -vπ) -1 T (v π ′ -vπ) ≤ 1 - 1 nτt 1 T (vπ † -vπ).
Lemma 12. While Simplex-PI does not create any recurrent class nor finishes:

• an action is eliminated from policies after at most ⌈nτt log(nτt)⌉ iterations;

• a recurrent class is broken after at most ⌈nτt log(n 2 τt)⌉ iterations.

Proof. Let π be the policy in some iteration, π † be the last policy before a new recurrent class appears, and π ′ any policy between π and π † . Since

0 ≤ 1 T (vπ † -vπ) {vπ † ≥ vπ} = xπ T (vπ † -Tπvπ † ) {Equation (7)} = s ∈R(π) xπ(s)(vπ † (s) -Tπvπ † (s)) + C∈R(π) s∈C xπ(s)(vπ † (s) -Tπvπ † (s)),
there must exist either a state s0 ∈ R(π) such that

xπ(s0)(vπ † (s0) -Tπvπ † (s0)) ≥ 1 n xπ T (vπ † -Tπvπ † ) ≥ 0. ( 12
)
or a recurrent class R0 such that

s∈R 0 xπ(s)(vπ † (s) -Tπvπ † (s)) ≥ 1 n xπ T (vπ † -Tπvπ † ) ≥ 0. ( 13
)
We consider these two cases separately below.

• case 1: Equation (12) holds for some s0 ∈ R(π). If π ′ (s0) = π(s0), then

1 T (vπ † -v π ′ ) ≥ vπ † (s0) -v π ′ (s0) {vπ † ≥ v π ′ } = vπ † (s0) -T π ′ v π ′ (s0) {v π ′ = T π ′ v π ′ } ≥ vπ † (s0) -T π ′ vπ † (s0) {vπ † ≥ v π ′ } = vπ † (s0) -Tπvπ † (s0) {π(s0) = π ′ (s0)} ≥ 1 τt xπ(s0)(vπ † (s0) -Tπvπ † (s0)) {Equation (9)} ≥ 1 nτt xπ T (vπ † -Tπvπ † ) {Equation (12)} = 1 nτt 1 T (vπ † -vπ). {Equation (7)}
If there is no recurrent class creation, the contraction property given in Lemma 11 implies that after k = ⌈nτt log(nτt)⌉ > log(nτt) log 1 1-1 nτ t iterations we have

1 T (vπ † -v π ′ ) < 1 nτt 1 T (vπ † -vπ),
and thus π ′ (s0) = π(s0).

• case 2: Equation (13) holds for some R0 ∈ R(π). Write T be the set of states that are transient for π (formally, T = X\R(π)). For any subset Y of the state space X, write P Y π for the stochastic matrix of which the i th row is equal to that of Pπ if i ∈ Y , and is 0 otherwise, and write 1Y the vectors of which the i th component is equal to 1 if i ∈ Y and 0 otherwise. Using the fact that P R 0 π P T π = 0, one can first observe that

(I -γP R 0 π )(I -γP T π ) = I -γ(P R 0 π + P T π ),
from which we can deduce that

1T ∪R 0 T (I -γP ) -1 = 1T ∪R 0 T (I -γ(P R 0 π + P T π )) -1 = 1T ∪R 0 T (I -γP T π ) -1 (I -γP R 0 π ) -1 . ( 14
)
Also, writing hT = (I -γP T π T ) -1 1T , that satisfies

hT = 1T + γP T π T hT ,
we can see that:

∀s ∈ R0, hT (s) = γ s ′ ∈T p s ′ s (π(s ′ ))hT (s ′ ), {s ∈ R0 ⇒ 1T (s) = 0} (15)
and thus:

(I -γP T π T ) -1 1T ∪R 0 (s) = (I -γP T π T ) -1 1T (s) + 1 {P T π T 1R 0 = 0} = hT (s) + 1 ≤ γ s ′ ∈T p s ′ s (π(s ′ ))hT (s ′ ) + 1 {Equation (15)} ≤ s ′ ∈T hT (s ′ ) + 1 = s ′ ∈T xπ(s ′ ) + 1 {∀s ′ ∈ T , hT (s ′ ) = xπ(s ′ )} ≤ (n -1)τt + 1 {|T | ≤ (n -1) and Equation (9)} ≤ nτt. {τt ≥ 1} (16)
Writing δ the vector that equals vπ † -Tπvπ † on R0 and that is null everywhere else, we have

s∈R 0 xπ(s)(vπ † (s) -Tπvπ † (s)) = s∈R 0 [(I -γP T π ) -1 1](s)δ(s) = s∈R 0 [(I -γP T π ) -1 1T ∪R 0 ](s)δ(s) ∀s ∈ R0, [(I -γP T π ) -1 1 X\(T ∪R 0 ) (s) = 0 = s [(I -γP T π ) -1 1T ∪R 0 ](s)δ(s) {∀s ∈ R0, δ(s) = 0} = 1T ∪R 0 T (I -γPπ) -1 δ = 1T ∪R 0 T (I -γP T π ) -1 (I -γP R 0 π ) -1 δ {Equation (14)} = s [(I -γP T π T ) -1 1T ∪R 0 ](s)[(I -γP R 0 π ) -1 δ](s) = s∈R 0 [(I -γP T π T ) -1 1T ∪R 0 ](s)[(I -γP R 0 π ) -1 δ](s) {∀s ∈ R0, δ(s) = 0} = s∈R 0 [(I -γP T π T ) -1 1T ∪R 0 ](s)(vπ † (s) -vπ(s)) {Lemma 1} ≤ nτt1R 0 (vπ † -vπ). {Equation (16)} (17)
Now, one can deduce from this that if R0 is also a recurrent class of π ′ , which implies

1R 0 T vπ = 1R 0 T v π ′ , then 1 T (vπ † -v π ′ ) ≥ 1R 0 T (vπ † -v π ′ ) {vπ † ≥ v π ′ } = 1R 0 T (vπ † -vπ) {1R 0 T vπ = 1R 0 T v π ′ } ≥ 1 nτt s∈R 0 xπ(s)(vπ † (s) -Tπvπ † (s)) {Equation (17)} ≥ 1 n 2 τt xπ T (vπ † -Tπvπ † ) {Equation (13)} = 1 n 2 τt 1 T (vπ † -vπ). {Equation (7)}
If there is no recurrent class creation, the contraction property given in Lemma 11 implies that after k = ⌈nτt log(n 2 τt)⌉ > log(n 2 τt)

log 1 1-1 nτ t iterations we have 1 T (vπ † -v π ′ ) < 1 n 2 τt 1 T (vπ † -vπ),
and thus R0 cannot be a recurrent class of π ′ .

A direct consequence of the above result is Lemma 6 that we originally stated page 5, and that we restate for clarity. Lemma 6. After at most n (m -1)⌈nτt log(nτt)⌉ + ⌈nτt log(n 2 τt)⌉ iterations, either Simplex-PI finishes or a new recurrent class appears.

Proof. Before a recurrent class is created, at most n recurrent classes need to be broken and n(m-1) actions to be eliminated, and the time required by these events is bounded thanks to the previous lemma.

F.2 Part 2: A new recurrent class implies a significant step towards the optimal value

We now proceed to the second part of the proof, and begin by proving Lemma 7 (originally stated page 6). Lemma 7. Suppose Simplex-PI moves from π to π ′ and that π ′ involves a new recurrent class. Then

1 T (vπ * -v π ′ ) ≤ 1 - 1 τr 1 T (vπ * -vπ).
Proof. Let s0 be the state such that π ′ (s) = π(s). On the one hand, since π ′ contains a new recurrent class R (necessarily containing s0), we have

1 T (v π ′ -vπ) = x π ′ T (T π ′ vπ -vπ) {Equation (7)} = x π ′ (s0)(T π ′ vπ(s0) -vπ(s0)) {Simplex-PI switches 1 action} ≥ n (1 -γ)τr (T π ′ vπ(s0) -vπ(s0)). {Equation 8 with s0 ∈ R ⊂ R(π ′ )} (18)
On the other hand,

vπ * -vπ = (I -γPπ * ) -1 (Tπ * vπ -vπ) {Lemma 1} ≤ 1 1 -γ max s Tπ * vπ(s) -vπ(s) { (I -γPπ * ) -1 ∞ ≤ 1 1 -γ and (I -γPπ * ) -1 ≻ 0} ≤ 1 1 -γ max s T π ′ vπ(s) -vπ(s) {max s T π ′ vπ(s) = max s,π Tπvπ(s)} = 1 1 -γ (T π ′ vπ(s0) -vπ(s0)). {Simplex-PI switches 1 action} (19)
Combining these two observations, we obtain:

1 T (vπ * -v π ′ ) = 1 T (vπ * -v π ′ ) -1 T (v π ′ -vπ) ≤ 1 T (vπ * -v π ′ ) - n (1 -γ)τr (T π ′ vπ(s0) -vπ(s0)) {Equation (18)} ≤ 1 T (vπ * -v π ′ ) - n τr max s vπ * (s) -v π ′ (s) {Equation (19)} ≤ 1 - 1 τr 1 T (vπ * -v π ′ ). {∀x, 1 T x ≤ n max s x(s)}
Lemma 14. While the algorithm does not terminate,

• some non-optimal action is eliminated from recurrent states after at most ⌈τr log(nτr)⌉ recurrent class creations;

• some non-optimal action is eliminated from policies after at most ⌈τr log(nτt)⌉ recurrent class creations.

Proof. Let π be the policy in some iteration and π ′ be any policy between π and π * . Let s0 = arg maxs xπ(s)(vπ * (s) -Tπvπ * (s)). We have

xπ(s0)(vπ * (s0) -Tπvπ * (s0)) ≥ 1 n xπ T (vπ * -Tπvπ * ) {∀x, 1 T x ≤ n max s x(s)} = 1 T (vπ * -vπ). {Equation (7)
} (20) We now consider two cases. This implies that π ′ (s0) = π(s0).

• case 1: s0 ∈ R(π). If π ′ (s0) = π(s0), then 1 T (vπ * -v π ′ ) = x π ′ T (vπ * -T π ′ vπ * ) {Equation (7)} ≥ x π ′ (s0)(vπ * (s0) -T π ′ vπ * ( s0
• case 2: s0 ∈ R(π). If π ′ (s0) = π(s0) and s0 ∈ R(π ′ ), then This implies that π ′ (s0) = π(s0) if s0 is recurrent for π ′ .

1 T (vπ * -v π ′ ) = x π ′ T (vπ * -T π ′ vπ * ) {Equation (7)
We are ready to conclude: At most, the n(m-1) non-optimal actions may need to be eliminated from recurrent and transient states, requiring at most a total of n(m -1)(⌈τr log(nτr)⌉ + ⌈τr log(nτt)⌉) recurrent classes creations. The result follows from the fact that each class creation requires at most n (m -1)⌈nτt log(nτt)⌉ + ⌈nτt log(n 2 τt)⌉ iterations. Since the MDP is deterministic and has n states, (Pπ l ) n will only have non-zero values on columns that correspond to R(π l ). Furthermore, since no cycle is created, R(π l ) ⊂ R(π0), which implies that vπ l (s)vπ 0 (s) = 0 for all s ∈ R(π l ). As a consequence, we have (Pπ l ) n (vπ lvπ 0 ) = 0. By Equation (21), this implies that vπ l = vπ n . If l > n, then the algorithm must have terminated.

G Cycle and recurrent classes creations for

1 nτt 1 T 1 T

 111 )) {vπ * ≥ T π ′ vπ * } ≥ vπ * (s0) -T π ′ vπ * (s0) {x π ′ (s0) ≥ 1} = vπ * (s0) -Tπvπ * (s0) {π(s0) = π ′ (s0)} ≥ 1 τt xπ(s0)(vπ * (s0) -Tπvπ * (s0)) {Equation(9)} ≥ (vπ *vπ). {Equation (20)} After k = ⌈τr log nτt⌉ > log nτt are created, we have by the contraction property of Lemma 7 that 1 T (vπ *v π ′ ) < 1 nτt (vπ *vπ).

1 nτr 1 T 1 T

 111 } = s x π ′ (s)(vπ * (s) -T π ′ vπ * (s)) ≥ s∈R 0 x π ′ (s)(vπ * (s) -T π ′ vπ * (s)) {vπ * ≥ T π ′ vπ * } ≥ n (1γ)τr s∈R 0 vπ * (s) -T π ′ vπ * (s) {Equation 8} ≥ n (1γ)τr vπ * (s0) -T π ′ vπ * (s0) {vπ * ≥ T π ′ vπ * } = n (1γ)τr vπ * (s0) -Tπvπ * (s0) {π(s0) = π ′ (s0)} = 1 τr xπ(s0)(vπ * (s0) -Tπvπ * (s0)) {xπ(s0) ≤ n 1γ } ≥ (vπ *vπ). {Equation(20)} After k = ⌈τr log nτr⌉ > log nτr are created, we have by the contraction property of Lemma 7 that 1 T (vπ *v π ′ ) < 1 nτr (vπ *vπ).

Howard's PI (Proofs of Lemmas 8 and 9 ) 8 .

 98 Lemma If the MDP is deterministic, after at most n iterations, either Howard's PI finishes or a new cycle appears.Proof. Consider a sequence of l generated policies π1, • • • , π l from an initial policy π0 such that no new cycle appears. By induction, we havevπ lvπ k = Tπ l vπ l -Tπ l vπ k-1 + Tπ l vπ k-1 -Tπ k vπ k-1 + Tπ k vπ k-1 -Tπ k vπ k {∀π, Tπvπ = vπ} ≤ γPπ l (vπ lvπ k-1 ) + γPπ k (vπ k-1vπ k ) {Tπ l vπ k-1 ≤ Tπ k vπ k-1 } ≤ γPπ l (vπ lvπ k-1). {Lemma 1 and Pπ k ≻ 0} ≤ (γPπ l ) k (vπ lvπ 0 ). {by induction on k} (21)

  Assumption 1 in hand, we can generalize Lemmas 4-5 as follows. -1)⌈nτ t log(nτ t )⌉ + ⌈nτ t log(n 2 τ t )⌉ iterations either Simplex-PI finishes or a new recurrent class appears. If the MDP satisfies Assumption 1, when Simplex-PI moves from π to π ′ where π ′ involves a new recurrent class, we have

	Lemma n (m Lemma 7.	6. If	the	MDP	satisfies	Assumption	1,	after	at	most

  Theorem 7 (Proof in Appendix F of the Supp. Material). If the MDP satisfies Assumption 1, then Simplex-PI terminates after at most n 2 (m -1) (⌈τ r log(nτ r )⌉ + ⌈τ r log(nτ t )⌉) (m -1)⌈nτ t log(nτ t )⌉ + ⌈nτ t log(n 2 τ t )⌉ This new result is a strict generalization of the result for deterministic MDPs. Indeed, in the deterministic case, we have τ t ≤ n and τ r ≤ n, and it is is easy to see that Lemmas 6, 7 and Theorem 7 respectively imply Lemmas 4, 5 and Theorem 6.An immediate consequence of the above result is that Simplex-PI is strongly polynomial for sets of MDPs that are much larger than the deterministic MDPs mentionned in Theorem 6.

	iterations.
	Remark 1.

Corollary 2. For any family of MDPs indexed by n and m such that τ t and τ r are polynomial functions of n and m, Simplex-PI terminates after a number of steps that is polynomial in n and m.

  Theorem 8 (Proof in Appendix H of the Supp. Material). If the MDP satisfies Assumptions 1-2, then Howard's PI terminates after at most n(m -1) (⌈τ t log nτ t ⌉ + ⌈τ r log nτ r ⌉) iterations, while Simplex-PI terminates after at most n(m -1) (⌈nτ t log nτ t ⌉ + ⌈τ r log nτ r ⌉) iterations.It should however be noted that Assumption 2 is rather restrictive. It implies that the algorithms converge on the recurrent states independently of the transient states, and thus the analysis can be decomposed in two phases: 1) the convergence on recurrent states and then 2) the convergence on transient states (given that recurrent states do not change anymore). The analysis of the first phase (convergence on recurrent states) is greatly facilitated by the fact that in this case, a new recurrent class appears every single iteration (this is in contrast with Lemmas 4, 6, 8 and 9 that were designed to show under which conditions cycles and recurrent classes are created). Furthermore, the analysis of the second phase (convergence on transient states) is similar to that of the discounted case of Theorems 3 and 4. In other words, if this last result sheds some light on the practical efficiency of Howard's PI and Simplex-PI, a general analysis of Howard's PI is still largely open, and constitutes our main future work.

Lemma 9 .

 9 If the MDP satisfies Assumption 1, after at most nm⌈τt log nτt⌉ iterations, either Howard's PI finishes or a new recurrent class appears.Proof. It can be seen that the proof of Lemma 6 also applies to Howard's PI.

H A

bound for Howard's PI and Simplex-PI under Assumption 2 (proof of Theorem 8)

In the works of[START_REF] Ye | The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate[END_REF][START_REF] Post | The simplex method is strongly polynomial for deterministic markov decision processes[END_REF][START_REF] Hansen | Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor[END_REF] that we reference, the integer "m" denotes the total number of actions, that is nm with our notation. When we restate their result, we do it with our own notation, that is we replace their ′′ m ′′ by ′′ nm ′′ .

Restricting our attention to stationary deterministic policies is not a limitation. Indeed, for the optimality criterion to be defined soon, it can be shown that there exists at least one stationary deterministic policy that is optimal[START_REF] Puterman | Markov Decision Processes[END_REF].

In this case, PI is equivalent to running the simplex algorithm with the highest-pivot rule on a linear program version of the MDP problem[START_REF] Ye | The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate[END_REF].

For clarity, all proofs are deferred to the Appendix. The first proofs about bounds for the case γ < 1 are given in the Appendix of the paper. The other proofs, that are more involved, are provided in the Supplementary Material.

A sequence of non-negative numbers (x k ) k≥0 is contracting with coefficient α if and only if for all k ≥ 0, x k+1 ≤ αx k .

For Howard's PI, we have:v * -vπ k ∞ ≤ γ k v * -vπ 0 ∞ ≤ γ k Vmax. Thus, a sufficient condition

This can be done by using arguments similar to the proof of Theorem 4 in Section D.

If the MDP is aperiodic and irreducible, and thus admits a stationary distribution νπ for any policy π, one can see that 1 τr = min π, i recurrent for π νπ(i).

This MDP has an even number of states n = 2p. The goal is to minimize the long term expected cost. The optimal value function satisfies v * (i) = -p N for all i, with N = p 2 + p. The policies generated by Howard's PI have values vπ k (i) ∈ (p N-k-1 , p N-k ). We deduce that for all iterations k and states i,v * (i)-vπ k+1 (i) v * (i)-vπ k (i) ≥ 1+p -k-2 1+p -k = 1 -p -k -p -k-2 1+p -k ≥ 1p -k (1p -2 ) ≥ 1p -k .

T (vπ †v π ′ ) ≤ 1 -1 nτt 1 T (vπ †vπ).

We here consider that the state space is decomposed into 2 sets: T is the set of states that are transient under all policies, and R is the set of states that are recurrent under all policies. From this assumption, it can be seen that when running Howard's PI or Simplex-PI, the values and actions chosen on T have no influence on the evolution of the values and policies on R. So we will study the convergence of both algorithms in two steps: We will first bound the number of iterations to converge on R. We will then add the number of iterations for converging on T given that convergence has occurred on R.

Convergence on the set R of recurrent states Without loss of generality, we consider that the state space is only made of the set of recurrent states.

First consider Simplex-PI. If all states are recurrent, new recurrent classes are created at every iteration, and Lemma 6 holds. Then, in a way similar to the proof of Lemma 14, it can be shown that every ⌈τr log nτr⌉ iterations, a non-optimal action can be eliminated. As there are at most n(m -1) non-optimal actions, we deduce that Simplex-PI converges in at most n(m -1)⌈τr log nτr⌉ iterations on R. Now consider Howard's PI. We can prove Lemma 10, that we restate for clarity. Lemma 10. For an MDP satisfying Assumptions 1-2, suppose Howard's PI moves from π to π ′ and that π ′ involves a new recurrent class. Then

Proof. In the case we focus on the convergence on the set R of recurrent states, new recurrent classes are created at every iteration. So we will prove that the inequality holds for every k. On the one hand, we have for all iterations k,

On the other hand,

By combining Equations ( 22) and (23), we obtain:

Then, similarly to Simplex-PI, we can prove that after every ⌈τr log nτr⌉ iterations a non-optimal action must be eliminated. And as there are at most n(m -1) non-optimal actions, we deduce that Howard's PI converges in at most n(m -1)⌈τr log nτr⌉ iterations on R.

Convergence on the set T of transient states Consider now that convergence has occurred on the recurrent states R. A simple variation of the proof of Lemma 6/Lemma 9 (where we use the fact that we don't need to consider the events where recurrent classes are broken since recurrent classes do not evolve anymore) allows to show that the extra number of iterations to converge on the transient states is n(m -1)⌈τt log nτt⌉ for Howard's PI and n 2 (m -1)⌈τt log nτt⌉ for Simplex-PI, and the result follows.


Mirko Fiacchini
email: mirko.fiacchini@gipsa-lab.fr

Marc Jungers
email: marc.jungers@univ-lorraine.fr

Necessary and sufficient condition for stabilizability of discrete-time linear switched systems: a set-theory approach ⋆

Keywords: Switched linear systems, set-theory, stabilization policy, invariance

Necessary and sufficient condition for stabilizability of discrete-time linear switched systems: a set-theory approach

Mirko Fiacchini, Marc Jungers

INTRODUCTION

Switched systems are systems for which the current dynamic, specified by the so-called switching law, belongs at each instant to a finite set of modes (see [START_REF] Liberzon | Switching in Systems and Control, volume in series Systems and Control: Foundations and Applications[END_REF]). These last decades, a large literature has been devoted to study switched systems for practical reasons: they model complex systems like embedded ones; and for theoretical reasons: their behavior and associated properties like their stability are neither intuitive nor trivial, as it has been emphasized in Liberzon and Morse (1999). Due to the large variety of assumptions related to the switching law, several frameworks are distinguished. The most common approaches consider the switching law as a perturbation or as a part of the control inputs.

When the switching law is a perturbation, that is an arbitrary function, sufficient but conservative conditions to ensure the stability have been provided (see for overviews [START_REF] Lin | Stability and stabilizability of switched linear systems: a survey of recent results[END_REF]; [START_REF] Sun | Stability Theory of Switched Dynamical Systems[END_REF]), with common Lyapunov function, Lie algebra and differential (or difference) inclusions [START_REF] Gurvits | Stability of discrete linear inclusion[END_REF]Liberzon et al., 1999;[START_REF] Agrachev | Lie-algebraic stability criteria for switched systems[END_REF], multiple Lyapunov functions [START_REF] Branicky | Multiple Lyapunov functions and other analysis tools for switched and hybrid systems[END_REF], switched quadratic Lyapunov functions [START_REF] Daafouz | Stability analysis and control synthesis for switched systems : A switched Lyapunov function approach[END_REF]. In addition several refinements have been proposed in order to obtain necessary and sufficient conditions for stability of switched systems. Among these conditions, one can cite the joint spectral radius approach [START_REF] Bauer | A necessary and sufficient condition for robust asymptotic stability of time-variant discrete systems[END_REF][START_REF] Lin | Persistent disturbance attenuation properties for networked control systems[END_REF][START_REF] Jungers | The Joint Spectral Radius: Theory and Applications[END_REF]; the formulation of a polyhedral Lyapunov function [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encounterd in control theory[END_REF] or a path-depend switched Lyapunov one (Lee and Dullerud, ⋆ Corresponding author M. Fiacchini. 2007). It should be also mentioned that for specific classes of switched systems, necessary and sufficient conditions could be obtained: for two-dimensional systems [START_REF] Boscain | Stability of planar switched systems: the linear single input case[END_REF], for positive ones [START_REF] Gurvits | On the stability of switched positive linear systems[END_REF].

In the case where the switching law is a part of the control inputs, sufficient conditions for stabilizability have been provided, mainly by using a min-switching policy (Liberzon, 2003, Chapter 3) introduced in [START_REF] Wicks | Construction of piecewise Lyapunov functions for stabilizing switched systems[END_REF], developed in [START_REF] Kruszewski | Converging algorithm for a class of BMI applied on state-dependent stabilization of switched systems[END_REF] via BMI and leading to Lyapunov-Metzler inequalities [START_REF] Geromel | Stability and stabilization of discrete-time switched systems[END_REF]. Based on the set-induced Lyapunov functions introduced in [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF], sufficient conditions for stabilization or more precisely uniformly ultimate boundedness has been proposed for uncertain switched linear systems in [START_REF] Lin | Synthesis of uniformly ultimate boundedness switching laws for discrete-time uncertain switched linear systems[END_REF]. Nevertheless to the best knowledge of the authors, there does not exist in the literature necessary and sufficient conditions for the stabilizability of discrete-time switched linear system. The aim of this paper is to provide necessary and sufficient conditions for stabilizability of linear discrete time switched systems. The set-theory will be used and will offer a numerically sound algorithm to check the stabilizability and also the switching control law stabilizing the switched system.

The outline of the paper follows. In Section 2, preliminaries and tools issued from the set-theory are presented. Results on stability for arbitrary switching laws are recalled in Section 3. Necessary and sufficient conditions for stabilizability of switched systems are provided in Section 4. The efficiency and suitability of our approach are underlined on academic examples in Section 5, before concluding remarks in Section 6.

Notation:

The set of positive integers smaller than or equal to the integer n ∈ N is denoted as N n , i.e.

N n = {x ∈ N : 1 ≤ x ≤ n}. Given D, E ⊆ R n , α ≥ 0 and M ∈ R m×n , define D + E = {z = x+ y ∈ R n : x ∈ D, y ∈ E}, define D-E = {x ∈ R n : x+ E ⊆ D}, αD = {αx ∈ R n : x ∈ D} and MD = {Mx ∈ R m : x ∈ D}. Given a set D ⊆ R n , co(D) denoted the convex hull of D, int(D)
its interior and ∂ D its boundary. The set B n is the unitary Euclidean ball in R n . The i-th element of a finite sets of matrices is denoted as A i , of a set of sets as Ω i .

PRELIMINARIES

Consider the discrete-time autonomous switched system

x k+1 = A σ (k) x k , (1)
where x k ∈ R n is the state at time k ∈ N and σ : N → N q is the switching law that, at any instant, selects the transition matrix among the finite set {A i } i∈N q , with A i ∈ R n×n for all i ∈ N q . Given the initial state x 0 and a switching law σ (•), we denote with x σ N (x 0 ) the state of the system (1) at time N starting from x 0 by applying the switching law σ (•). In some cases σ can be a function of the state, for instance in the case of switching control law, as shown later.

A concept widely employed in the context of set-theory and invariance is the C-set, see [START_REF] Blanchini | Ultimate boundedness control for uncertain discrete-time systems via set-induced Lyapunov functions[END_REF][START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF]; [START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF]. A C-set is a compact, convex set containing the origin in its interior. We define an analogous concept usefull for our purpose. For this, we first recall that a set Ω is a star-convex set if there exists x 0 ∈ Ω such that every convex combination of x and x 0 belongs to Ω for every x ∈ Ω. Definition 1. A set Ω ⊆ R n is a C * -set if it is compact, starconvex with respect to the origin and 0 ∈ int(Ω).

Define also the analogous of the gauge function of a C * -set as

Ψ Ω (x) = min α {α ∈ R : x ∈ αΩ}, (2)
for the C * -set Ω ⊆ R n . In what follows, we will refer to Ψ Ω (x) as the Minkowski function of Ω at x, with a slight abuse as the Minkowski function is usually defined for C-sets (or symmetric C-sets), [START_REF] Rockafellar | Convex Analysis[END_REF]; [START_REF] Schneider | Convex bodies: The Brunn-Minkowski theory[END_REF]; [START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF].

Some basic properties of the C * -sets and their Minkowski functions are listed below. The proof is avoided, since they follow directly from the definition. Property 1. Any C-set is a C * -set. Given a C * -set Ω ⊆ R n , we have that αΩ ⊆ Ω for all α ∈ [0, 1], and the Minkowski function Ψ Ω (•) is: homogenous of degree one, i.e. Ψ Ω (αx) = αΨ Ω (x) for all α ≥ 0 and x ∈ R n ; positive definite; defined on R n and radially unbounded.

Then, given a C * -set Ω, its Minkowski function is a Lyapunov function if there exists N ≥ 1 and a switching law defined on R n such that its value is not increasing and it decreases after N steps for all x ∈ R n . Although this is not the classical definition of Lyapunov functions, it can be proved that there exists a Lyapunov function if and only if there is a function of this kind.

Notice that this is equivalent to impose that the smaller level set containing x σ N (x) is contained in the interior of the smaller one containing x for all x, which is equivalent to contractivity of Ω after N steps.

RECALL OF THE ARBITRARY SWITCHING LAW FRAMEWORK

In this section, we recall in Theorem 1 necessary and sufficient conditions for the stability of a switched linear system with arbitrary switching law σ . Several statements are then declined in Proposition 1 and links with the literature are discussed. Theorem 1. [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encounterd in control theory[END_REF]). There exists a Lyapunov function for the switching system (1) if and only if there exists a C-set Ω ⊆ R n and a scalar λ ∈ [0, 1) such that

A i Ω ⊆ λ Ω, ∀i ∈ N q .
(3)

Proof: The proof is inspired by the one of Lemma 4.1 in [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF] and extended to the case of switched systems without loss of genericity. It is based on the linearity with respect to the state of the system (1) and on the convexification of the set induced by the stability definition of the system.

The condition (3) could be reformulated in several forms, which are more suitable for the switched nature of the system (1). Proposition 1. The three following statements are equivalent:

a) There exists a C-set Ω ⊆ R n , such that A i Ω ⊆ λ Ω, ∀i ∈ N q . (4) b) There exist q C-sets Ωi ⊆ R n , with i ∈ N q , such that A i Ωi ⊆ λ ∩ j∈N q Ω j , ∀i ∈ N q . (5) c) There exist q C-sets Ω j ⊆ R n , with i ∈ N q , such that A i Ωi ⊆ λ Ω j , ∀(i, j) ∈ N q × N q . ( 6
)
Proof: The proof is made circularly. The implication a)⇒b) is true by choosing Ωi = Ω, ∀i ∈ N q . The inclusion j∈N q Ω j ⊆ Ωi , ∀i ∈ N q leads to b)⇒c). The implication c)⇒a) is obtained by considering Ω = j∈N q Ω j , which is a C-set because Ωi are C-sets. More precisely, the inclusion (6) being true for all j ∈ N q , we have A i Ωi ∈ λ j∈N q Ω j and A i j∈N q Ω j ∈ λ j∈N q Ω j .

The relation ( 4) is more convenient for theoretical and computational aspects because it is closer to the set-induced Lyapunov function proposed in [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF]. When Ω is assumed to be an ellipsoid, we obtain sufficient conditions for stability with a common quadratic Lyapunov function. We recover the result of [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encounterd in control theory[END_REF] concerning necessary and sufficient conditions with a polyhedral Lyapunov function by assuming that Ω is a polytope, due to the fact that a C-set admits and arbitrarly close polytopic approximation. When Ω i , i ∈ N q are ellipsoids, the relation ( 6) writes as the sufficient conditions for stability in the framework of quadratic switched Lyapunov functions [START_REF] Daafouz | Stability analysis and control synthesis for switched systems : A switched Lyapunov function approach[END_REF]. Finally the relation ( 5) is adapted to design an algorithm based on pre-image modal operators. This last approach will be privileged in the following for the case of switching control law.

SWITCHING CONTROL LAW

It is proved in [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encounterd in control theory[END_REF] that for an autonomous linear switched system (called therein difference inclusion), the origin is asymptotically stable if and only if there exists a polyhedral Lyapunov function, see also [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF]; [START_REF] Lin | Stability and stabilizability of switched linear systems: a survey of recent results[END_REF]. It can be proved that analogous results can be stated in the case that the switching sequence is supposed to be a properly chosen selection, that is considering it as a control law.

We recall that in the switching stabilization literature, the system (1) is asymptotically stabilizable if there exists a switching law and a continuous positive definite and radially unbounded non-increasing function converging to zero when the law is applied. Hence, the function is a Lyapunov function and standard reasoning for guaranteeing asymptotically stability hold for the resulting time-varying system. The switching law will belong to the class of state-dependent one, that is σ (k) = g(x k ), (7) where g : R n → N q . With a slight abuse of notation we define in the sequel the state-dependent switching law as σ (k) = σ (x k ). Assumption 1. The matrices A i , with i ∈ N q , are non-singular. Remark 1. Notice that this assumption is not restrictive at all. In fact, the stable eigenvalues of the matrices A i are beneficial from the stability point of view of the switched systems and poles in zero are related to the more contractive dynamics. Moreover, the results presented in the following can be extended to the general case with appropriate considerations. Finally, recall that sampled linear systems do not present poles in the origin and then real systems satisfy Assumption 1.

Consider the following algorithm: Algorithm 1. Computation of a contractive C * -set for the system (1) such that Assumption 1 holds.

• Initialization: given the C * -set Ω ⊆ R n , define Ω 0 = Ω and k = 0; • Iteration for k ≥ 0: Ω i k+1 = A -1 i Ω k , ∀i ∈ N q , Ω k+1 = i∈N q Ω i k+1 ; (8) • Stop if Ω ⊆ int j∈N k+1 Ω j ; denote Ň = k + 1 and Ω = j∈N ŇΩ j . (9)
From the geometrical point of view, notice that the set Ω i k+1 is the set of points mapped in Ω k through A i . Then Ω k+1 are those points x ∈ R n for which there exists a selection i(x) ∈ N q such that A i(x) x ∈ Ω k . Therefore, Ω k is the set of points that can be driven in Ω in k step and hence Ω the set of those which can reach Ω in Ň or less steps, by an adequate switching law. Remark 2. The symbol A -1 i should be intended to denote, with a slight abuse of notation, the operator that associates to a set its inverse image, rather than the inverse of matrix A i . That is, given the set D ⊆ R n one have

A -1 i D = {x ∈ R n : A i x ∈ D}.
Indeed, it is worth pointing out that the inverse image of a set exists and can be computed also for linear transformations given by non-invertible matrices. This has to remarked because the algorithm applies also for the general case for which Assumption 1 is not satisfied, although it is not the case so far. Proposition 2. The sets Ω i k and Ω k with i ∈ N q and for all k ≥ 0 are C * -sets.

Proof:

Clearly Ω 0 is a C * -set. It is sufficient to prove that A -1 D and D ∪ E are C * -sets, for all nonsingular A ∈ R n and every C * -sets D and E to prove the results by induction. By definition αx ∈ D for all x ∈ D and α ∈ [0, 1]. Then given α ∈ (0, 1] we have

αA -1 D = {αx ∈ R n : Ax ∈ D} = {y ∈ R n : Ay ∈ αD} ⊆ ⊆ {x ∈ R n : Ax ∈ D} = A -1 D, since D is a C * -set. For α = 0, αA -1 D = {0} ⊆ A -1 D, trivially.
Then A -1 D is a star-convex set and it is also compact from Assumption 1. The fact that it contains the origin in its interior follows from the fact that A -1 i are continuous operators under Assumption 1. Then A -1 D is a C * -set. The property on the union follows from the definition of C * -set.

It can be proved that Algorithm 1 provides a C * -set Ω contractive in Ň steps, for every initial C * -set Ω ∈ R n , if and only if the switching system (1) is asymptotically stable. Such necessary and sufficient condition, which is the main contribution of the paper, is stated in the theorem below. Theorem 2. There exists a Lyapunov function for the switching system (1) if and only if the Algorithm 1 ends with finite Ň.

Proof: Necessity follows from the fact that, if the algorithm ends with finite Ň, then Ω induces a Lypaunov function. Indeed, Ω being a C * -set from Proposition 2, its Minkowski function is defined. Moreover, considering λ

= λ (Ω) = min λ {λ ≥ 0 : Ω ⊆ λ Ω}, (10)
we have that λ < 1, since Ω ⊆ int( Ω) and Ω is a C * -set. Since by construction Ω is the set of points x such that x σ k (x) are in Ω for k = k(x) ≤ Ň and an appropriate switching sequence, then we have

x σ k(x) (x) ∈ Ω ⊆ λ Ω, (11)
for all x ∈ Ω and in particular for x ∈ ∂ Ω. This means that there exist a switching σ (x) and k(x) ≤ Ň such that

Ψ Ω(x σ k(x) (x)) ≤ λ Ψ Ω(x), (12)
for all x ∈ ∂ Ω. Then the value of the Minkowski function decreases after k(x) steps, for all x on the boundary. Moreover, it does not increase, for all j ≤ k(x). In fact, given x ∈ ∂ Ω, the elements x σ j (x) can be stirred in Ω in k(x)j steps for all j ≤ k(x), being elements of the same sequence whose last element is in Ω. This means that x σ j (x) ∈ Ω and then

Ψ Ω(x σ j (x)) ≤ Ψ Ω(x), ∀ j ∈ N k(x) . ( 13
)
for all x ∈ ∂ Ω. Then for every x ∈ ∂ Ω there exists a switching sequence of length k(x) such that the Ψ Ω is not increasing for the first k(x) -1 steps and it decreases of at least a proportional value λ at the instant k(x), from ( 12) and ( 13).

Since every x is on the boundary of a level set of Ψ Ω(x), in particular x ∈ ∂ Ψ Ω(x) Ω , and from the homogeneity of the Minkowski function and the linearity of the switched system, we have that ( 12) and ( 13) hold for every x ∈ R n . Thus from ( 12) and ( 13) valid on the whole state space, we have

Ψ Ω(x σ Ň (x)) ≤ λ Ψ Ω(x), ( 14
)
for all x ∈ R n which proves that Ψ Ω is a Lyapunov function.

Then, if the Algorithm 1 ends with finite Ň, a Lyapunov function exists, in particular Ψ Ω(x).

To prove sufficiency, we suppose that there exists a Lyapunov function for the switched linear system (1) and we demonstrate that the Algorithm 1 ends with finite Ň. By definition, there exist a switching law σ (x), a value N ∈ N and a continuous positive definite function V : R n → R such that for every x we have V (x σ N (x)) < V (x). Consider the set

Ω V = {x ∈ R n : V (x) ≤ 1}, ( 15
) which is closed from continuity of V and bounded from its radially unboundedness. Hence Ω V is compact and 0 ∈ int(Ω V ), since V is continuous and positive definite. Thus for every C *set Γ, there exists ε > 0 such that the C * -set εΓ satisfies εΓ ∈ int(Ω V ). Posing Ω = εΓ in Algorithm 1, we have Ω ⊆ int(Ω V ). From the gobally asymptotic stability of the system (1), there exist a switching law σ (x) defined on R n and a finite N V ∈ N such that for all x ∈ Ω V there exists k(x) ≤ N V for which

x σ k(x) (x) ∈ Ω.
Consider Ω N V obtained by applying the Algorithm 1 with Ω defined above, supposing that the stop condition has not been satisfied, otherwise the result would be directly proved. Since the set Ω j is the set of states that can be stirred in Ω in j steps, then Ω V ⊆ j∈N N V Ω j and then we have

Ω ⊆ int(Ω V ) ⊆ int j∈N N V Ω j ,
which contradicts the fact that the stop condition has not been satisfied. Then the Algorithm 1 ends with finite Ň with Ň ≤ N V .

The fact that Algorithm 1 ends with finite Ň is a necessary and sufficient condition for global asymptotic stability of the switched system (1). Moreover, Algorithm 1 provides a Lyapunov function and a stabilizing switching control law, or better a family of stabilizing control laws, for the linear switched system (1). Notice that the complexity of the algorithm, which we think should deserve further analysis, depends on the complexity intrinsic to the Lyapunov functions and then on the nature proper of the system. Proposition 3. If Algorithm 1 ends with finite Ň then Ψ Ω : R n → R is a Lyapunov function for the switched system (1) and given the set valued map Σ(x) = arg min

(i,k) {Ψ Ω i k (x) : i ∈ N q , k ∈ N Ň } ⊆ N q × N Ň, (16)
any switching law defined as

( σ (x), ǩ(x)) ∈ Σ(x), (17)
is a stabilizing switching law and such that

Ψ Ω(x σ ǩ(x) (x)) ≤ λ Ψ Ω(x), Ψ Ω(x σ j (x)) ≤ Ψ Ω(x), ∀ j ∈ N ǩ(x) ,
with λ as in (10).

Proof: The fact that Ψ Ω(•) is a Lyapunov function has been proved in the proof of necessity for Theorem 2. Denote α = Ψ Ω(x), to easy the notation. Then x ∈ ∂ (α Ω) by definition.

Moreover, from definition of Ω, there are some values

(i, k) ∈ N q ×N Ň such that x ∈ ∂ (αΩ i k ), since Ω is the union of Ω i k for all i ∈ N q and k ∈ N Ň . Concerning the (i, k) for which x ∈ ∂ (αΩ i k ) is not satisfied, we have that x / ∈ (αΩ i k ) and then Ψ Ω i k (x) > α.
This because x is either on the boundary or in the complement of every αΩ i k , for all i ∈ N q and k ∈ N Ň , otherwise α would not be the minimal value such that x ∈ α Ω. Then for every i ∈ N q and k ∈ N Ň we have that

Ψ Ω i k (x) = α, if x ∈ ∂ (αΩ i k ), Ψ Ω i k (x) > α, if x / ∈ (αΩ i k )
. Remind that by construction Ω i k is the set that can be stirred in Ω, and then also in the contracted set λ Ω, in k steps by means of a sequence of modes whose first element is i. Moreover, as demonstrated in the proof of Theorem 2, the Minkowski function does not increase along the first k -1 elements of the generated trajectory. Then from homogeneity of the Minkowski functions, the set Σ(x) is composed by the pairs (i, k) where i is the first element of a control sequence σ (x) that leads to have x σ k (x) ∈ λ α Ω and x σ j (x) ∈ α Ω for all j ∈ N k . As ( σ (x), ǩ(x)) is a selection of the set Σ(x), the result follows.

It could be reasonable, to speed up the convergence, to select among the elements of Σ(x), those whose k is minimal.

Corollary 1. If Algorithm 1 ends with finite Ň then the switching law defined by ( 16) and ( 17) is such that

Ψ Ω(x σ p Ň (x)) ≤ λ p Ψ Ω(x), (18)
for every p ∈ N and all x ∈ R n .

Proof: From Proposition 3 we have that, if Algorithm 1 ends with finite Ň, then there exist a switching law σ (x) and the related ǩ(x) ≤ Ň such that the Minkowski function of Ω does not increase for k ≤ ǩ(x) and it decreases of a proportional value of λ after ǩ(x) steps, for all x ∈ R n . Since ǩ(x) ≤ Ň, then the value of Ψ Ω(x) decreases at least one time within the next Ň steps, that means that

Ψ Ω(x σ Ň (x)) ≤ λ Ψ Ω(x),
which implies (18) since the property applies over the whole space R n . Remark 3. It is worth pointing out that if the system is asymptotically stabilizable, then the algorithm ends with finite Ň for all initial C * -set Ω. Clearly, the value of Ň and the complexity of the set Ω depends on the choice of Ω. In particular, if Ω is the euclidean norm ball (or the union of full dimensional ellipsoids), the sets Ω i k and Ω k , with i ∈ N q and k ∈ N Ň , are union of ellipsoids, and so is Ω. Then, the switching law computation reduces to check the minimal value of among x T P j x with j ∈ M, where {P j } j∈ M are the M positive definite matrices that define Ω, with M = ∑ k∈N Ň q k = q + • • • + q Ň = (q Ň+1q)/(q -1).

Moreover, if Ω is a (the union of) polytope contaning the origin in its interior, also Ω i k , Ω k , with i ∈ N q and k ∈ N Ň , and Ω are so. In this case, the switching law is obtained by evaluating the set linear inequalities defining those polytopes.

ILLUSTRATION

In order to illustrate the suitability of the algorithm, consider the example with q = n = 2:

A 1 = 1.2 0 -1 0.8 , A 2 = -0.6 -2 0 -1.2 .
Both the matrices A 1 and A 2 are not Schur, which implies that this is not possible to stabilize the system (1) with a constant switching law. In order to apply the Algorithm 1, we have to choose a particular initial C * -set Ω. Firstly we consider Ω = B 2 . The induced sets Ω k , k ∈ N will be thus unions of ellipsoids. The result at the first step is depicted in Figure 1, left. Ω 1 is the union of two ellipsoids (A -1 1 B 2 and A -1 2 B 2 ). It is clear that B 2 does not belong to Ω 1 . The next step of the algorithm leads to a set k∈N 2 Ω k given by the union of six ellipsoids (A -1 i B 2 with i ∈ N 2 and A -1 j A -1 i B 2 , for all (i, j) ∈ N 2 × N 2 ). Since B 2 does not belong to k∈N 2 Ω k , see Figure 1 right, the termination condition is not satisfied. The algorithm stops at the fourth iteration. The zoom in Figure 2 emphasizes that B 2 is included in k∈N 4 Ω k .

A stabilizing switching law, satisfying the relation ( 17) is given in Figure 3 for the initial condition x 0 = (-3, 3) T . The Lyapunov function converges to zero (Figure 3). It is also noteworthy that the Lyapunov function is not a decreasing function, but only a non-increasing one which is strictly decreasing at least every four (the number of steps of the algorithm) instants, as proved in the main result. The algorithm could also be applied by considering other initial C * -set Ω. For instance, we consider the unit square. The algorithm terminates at the fourth step. The related k∈N 4 Ω k is depicted in Figure 4. The trajectory starting from x 0 = (-3, 3) T is also plotted in this figure.

As a second example, consider for q = n = 2:

A 1 = 0 -1.01 1 -1 , A 2 = 0 -1.01 1 -0.5 .
Due to the structure of A 1 and A 2 , the product of eigenvalues of every convex combination of these both matrices is equal to 1.01. That is every convex combination of A 1 and A 2 is not Schur. The technique based on Lyapunov-Metzler inequalities is then not applicable. Nevertheless this switched system is

Fig. 1 .

 1 Fig. 1. Ball B 2 in dashed line and induced sets Ω 1 and k∈N 2 Ω k in solid line.

Fig. 2 .

 2 Fig. 2. Ball B 2 in dashed line and k∈N 4 Ω k in solid one.Trajectory starting from x 0 = (-3, 3) T in starry line.

Fig. 3 .

 3 Fig. 3. Lyapunov function and switching control laws in time.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Unitary square in dashed line and k∈N 2 Ω k in solid one.Trajectory starting from x 0 = (-3, 3) T in starry line.stabilizable. Our algorithm stops at the third step. It is shown in Figure5that B 2 ⊆ k∈N 3 Ω k . The Lyapunov function and the switching law are given in Figure6. Notice that also in this case, the Lyapunov function decreases after Ň steps.

Fig. 6 .

 6 Fig. 6. Lyapunov function and switching control laws in time.

ACKNOWLEDGEMENTS

This work was partially supported by ANR project ArHyCo, Programme "Systèmes Embarqués et Grandes Infrastructures" -ARPEGE, contract number ANR-2008 SEGI 004 01-30011459. The research leading to these results has received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n • 257462: HYCON2 Network of Excellence "Highly-Complex and Networked Control Systems". The authors would like to thank Professor Jamal Daafouz for helpful discussions concerning this paper.

CONCLUSION

The issue of the stabilizability of a switched discrete-time linear autonomous system has been studied in this paper. Via a settheory approach, necessary and sufficient conditions for the stabilizability have been provided. These conditions are based on an algorithm using pre-image modal operators over compact, star-convex sets containing the origin in their interior, which provides in addition the switching laws stabilizing the switched system. The method is applied to numerical examples by employing ellipsoids or polytopes as the initial sets. Our approach allows moreover to stabilize counter-examples of Lyapunov-Metzler approach based on the existence of a Schur convex combination of the matrices. Several academic illustrations are proposed to strengthen the discussions and to emphasize the efficiency of our approach.