Nahla Ben Amor
email: nahla.benamor@gmx.com

Zeineb El Khalfi
email: zeineb.khalfi@gmail.com

Hélène Fargier
email: fargier@irit.fr

Régis Sabbadin
email: regis.sabbadin@inra.fr

Alessandro Antonucci

Laurence Cholvy

Odile Papini

Lexicographic refinements in stationary possibilistic Markov Decision Processes ✩

Keywords:

 for non-sequential decision problems. We propose a value iteration algorithm and a policy iteration algorithm to compute policies that are optimal for these new criteria. The practical feasibility of these algorithms is then experimented on different samples of possibilistic MDPs.

Introduction

The classical paradigm for sequential decision making under uncertainty is the expected utility-based Markov Decision Processes (MDPs) framework [START_REF] Bellman | A Markovian decision process[END_REF][START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF], which assumes that the uncertain effects of actions can be represented by probability distributions and that utilities are additive. But the EU model does no suit problems where uncertainty and preferences are ordinal in essence.

Alternatives to the EU-based model have been proposed to handle ordinal preferences/uncertainty. Remaining within the probabilistic, quantitative, framework while considering ordinal preferences has led to quantile-based approaches [START_REF] Gilbert | Optimizing quantiles in preference-based Markov decision processes[END_REF][START_REF] Montes | Decision making with imprecise probabilities and utilities by means of statistical preference and stochastic dominance[END_REF][START_REF] Szörényi | Qualitative multi-armed bandits: a quantile-based approach[END_REF][START_REF] Weng | Markov decision processes with ordinal rewards: reference point-based preferences[END_REF][START_REF] Yue | The k-armed dueling bandits problem[END_REF]. Purely ordinal approaches to sequential decision under uncertainty have also been considered. In particular, possibilistic MDPs [START_REF] Bauters | Anytime algorithms for solving possibilistic MDPs and hybridMDPs[END_REF][START_REF] Drougard | Qualitative possibilistic mixed-observable MDPs[END_REF][START_REF] Sabbadin | Possibilistic Markov decision processes[END_REF][START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF] form a purely qualitative decision model with an ordinal evaluation of plausibility and preference. In this model, uncertainty about the consequences of actions is represented by possibility distributions and utilities are also ordinal. The decision criteria are either the pessimistic qualitative utility or its optimistic counterpart [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF]. Such degrees can be either elicited from experts, or by automatic learning approaches [START_REF] Sabbadin | Towards possibilistic reinforcement learning algorithms[END_REF]. However, it is now well known that possibilistic decision criteria suffer from a drowning effect [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF]: plausible enough bad or good consequences may completely blur the comparison between policies, that would otherwise be clearly differentiable.

In [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF], Fargier and Sabbadin have proposed lexicographic refinements of possibilistic criteria for the one-step decision case, in order to remedy the drowning effect. This work has recently been extended for (finite horizon) possibilistic decision trees [START_REF] Ben Amor | Lexicographic refinements in possibilistic decision trees[END_REF]. In the present paper, we propose to study the interest of the lexicographic preference relations to stationary possibilistic Markov Decision Processes, a model that is more compact than decision trees and not limited to a finite horizon.

The paper is structured as follows: The next Section recalls the background about possibilistic decision theory and stationary possibilistic MDPs, including the drowning effect problem. Section 3 defines the lexicographic comparison of policies and presents a value iteration algorithm which computes a nearly optimal strategy in a limited number of iterations. Then, Section 4 proposes a lexicographic value iteration algorithm and a lexicographic policy iteration algorithm using approximation of utility functions. Lastly, Section 5 presents our experimental results.

Background and notations

Basics of possibilistic decision theory

Most of available decision models refer to probability theory for the representation of uncertainty [START_REF] Neumann | Theory of Games and Economic Behavior[END_REF][START_REF] Savage | The Foundations of Statistics[END_REF]. Despite its success, probability theory is not appropriate when numerical information is not available. When information about uncertainty cannot be quantified in a probabilistic way, possibilistic theory [START_REF] Dubois | Possibility Theory: An Approach to Computerized Processing of Uncertainty[END_REF][START_REF] Zadeh | Fuzzy sets as a basis for theory of possibility[END_REF] is a natural field to consider. The basic component of this theory is the notion of possibility distribution. It is a representation of a state of knowledge of an agent about the state of the world. A possibility distribution π is a mapping from the universe of discourse S (the set of all the possible worlds) to a bounded linearly ordered scale L exemplified (without loss of generality) by the unit interval [0, 1],

we denote the function by: π : S → [0, 1].

For state s ∈ S, π(s) = 1 means that realization s is totally possible and π(s) = 0 means that s is an impossible state. It is generally assumed that there exists at least one state s which is totally possible: π is then said to be normalized.

In the possibilistic framework, extreme forms of knowledge can be captured, namely:

• Complete knowledge i.e. ∃ s s.t. π(s) = 1 and ∀ s ′ = s, π(s ′ ) = 0.

• Total ignorance i.e. ∀s ∈ S, π(s) = 1 (all values in S are possible).

From π one can compute the possibility measure (A) and the necessity measure N( A) of any event A ⊆ S:

(A) = sup s∈ A π(s) N( A) = 1 -( Ā) = 1 -sup s / ∈A π(s)
Measure (A) evaluates to which extent A is consistent with the knowledge represented by π while N( A) corresponds to the extent to which ¬A is impossible and thus evaluates at which level A is certainly implied by the knowledge.

In decision theory acts are functions f : S → X , where X is a finite set of outcomes. In possibilistic decision making, an act f can be viewed as a possibility distribution π f over X [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF], where π f (x) = ( f -1 (x)). In a single stage decision making problem, a utility function u : X → U maps outcomes to utility values in a totally ordered scale U = {u 1 , ..., u n }.

This function models the attractiveness of each outcome for the decision-maker.

Under the assumption that the utility scale and the possibility scale are commensurate and purely ordinal (i.e. U = L),

Dubois and Prade [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Dubois | On the possibilistic decision model: from decision under uncertainty to case-based decision[END_REF] have proposed pessimistic and optimistic decision criteria. First, the pessimistic criterion was originally proposed by Whalen [START_REF] Whalen | Decision making under uncertainty with various assumptions about available information[END_REF] and it generalizes the Wald criterion [START_REF] Wald | Statistical Decision Functions[END_REF]. It suits cautious decision makers who are happy when bad consequences are hardly plausible. It summarizes to what extent it is certain (i.e. necessary according to measure N) that the act reaches a good utility. The definition of the pessimistic criterion is as follows [START_REF] Dubois | Qualitative decision theory with Sugeno integrals[END_REF]: Definition 1. Given a possibility distribution π over a set of states S and a utility function u on the set of consequences X , the pessimistic utility of an act f is defined by: u pes ( f ) = min x j ∈X max(u(x j ), 1 -π f (x j )), = min s i ∈S max(u( f (s i )), 1 -π(s i )).

(1) Therefore, we can compare two acts f and g on the basis of their pessimistic utilities: f u pes g ⇔ u pes ( f ) ≥ u pes (g).

The second criterion is the optimistic possibilistic criterion originally proposed by Yager [START_REF] Yager | Possibilistic decision making[END_REF][START_REF]The Ordered Weighted Averaging Operators: Theory and Applications[END_REF]. This criterion captures the behavior of an adventurous decision maker who is happy as soon as at least one good consequence is highly plausible. It summarizes to what extent it is possible that an act reaches a good utility. The definition of this criterion is as follows [START_REF] Dubois | Qualitative decision theory with Sugeno integrals[END_REF]: Definition 2. Given a possibility distribution π over a set of states S and a utility function u on a set of consequences X , the optimistic utility of an act f is defined by:

u opt ( f ) = max x j ∈X min(u(x j ), π f (x j )), = max s i ∈S min(u( f (s i )), π(s i )). (2)
Hence, we can compare two acts f and g on the basis of their optimistic utilities:

f u opt g ⇔ u opt ( f ) ≥ u uopt (g).
Example 1. Let S = {s 1 , s 2 } and f and g be two acts whose utilities of consequences in the states s 1 and s 2 are listed in the following table, as well as the degrees of possibility of s 1 and s 2 :

s 1 s 2 u( f (s)) 0.3 0.5 u(g(s)) 0.4 0.6 π 1 0.2
Comparing f and g with respect to the pessimistic criterion, we get:

• u pes ( f ) = min(max(0.3, 0), max(0.5, 0.8)) = 0.3, • u pes (g) = min(max(0.4, 0), max(0.6, 0.8)) = 0.4.
Thus, g u pes f . Let us now compare the two acts with respect to the optimistic criterion:

• u opt ( f ) = max(min(0.3, 1), min(0.5, 0.2)) = 0.3,

• u opt (g) = max(min(0.4, 1), min(0.6, 0.2)) = 0.4.

Thus, g u opt f .

It is important to note that while transition probabilities can be estimated through simulations of the process, transition possibilities may not. On the other hand, experts may be involved for the elicitation of the possibility degrees and utilities of transitions. In the possibilistic framework, utility and uncertainty levels can be elicited jointly, by comparison of possibilistic lotteries, for example (e.g. by using certainty equivalents, as in [START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF]). Simulation can also be used jointly with expert evaluation when the underlying process is too costly to simulate a large number of times: simulation may be used to generate samples on which expert elicitation is applied. Another option is to use possibilistic reinforcement learning procedure (for more details see [START_REF] Sabbadin | Towards possibilistic reinforcement learning algorithms[END_REF]), in particular model-based reinforcement learning algorithm. The latter uses a uniform simulation of trajectories (with random choice of actions) in order to generate an approximation of the possibilistic decision model.

Stationary Possibilistic Markov Decision Processes

A stationary Possibilistic Markov Decision Process ( MDP ) [START_REF] Sabbadin | Possibilistic Markov decision processes[END_REF] is defined by:

• A finite set S of states; • A finite set A of actions, A s denotes the set of actions available in state s;

• A possibilistic transition function: for each action a ∈ A s and each state s ∈ S the possibility distribution π(s ′ |s, a)

evaluates to what extent each s ′ is a possible successor of s when action a is applied;

• A utility function µ: µ(s) is the intermediate satisfaction degree obtained in state s.

The uncertainty about the effect of an action a taken in state s is captured by a possibility distribution π(.|s, a). In the present paper, we consider stationary problems, i.e. problems in which the states, the actions and the transition functions do not depend on the stage of the problem. Such a possibilistic MDP may define a graph where states are represented by circles and each state "s" is labeled with a utility degree, and actions are represented by squares. An edge linking an action to a state denotes a possible transition and is labeled by the possibility of that state given the action is executed. Example 2. Let us suppose that a "Rich and Unknown" person runs a startup company. Initially, s/he must choose between Saving money (Sav) or Advertising ( Adv) and may then get Rich (R) or Poor ( P ) and Famous (F ) or Unknown (U ). In the other states, Sav is the only possible action. Fig. 1 shows the stationary MDP that captures this problem, formally described as follows:

S = {RU , R F , P U }, A RU = {Adv, Sav}, A R F = A P U = {Sav}, π(P U |RU , Sav) = 0.2, π(RU |RU , Sav) = π(R F |RU , Adv) = π(R F |R F , Sav) = π(RU |R F , Sav) = 1, µ(RU ) = 0.5, µ(R F ) = 0.7, µ(P U ) = 0.3.
Solving a stationary MDP consists in finding a (stationary) policy, i.e. a function δ: S → A which is optimal with respect to a decision criterion. In the possibilistic case, as in the probabilistic case, the value of a policy depends on the utility and on the likelihood of its trajectories. Formally, let be the set of all policies that can be built for the MDP (the set of all the functions that associate an element of A s to each s). Each δ ∈ defines a list of scenarios called trajectories. Each trajectory τ is a sequence of states and actions i.e. τ = (s 0 , a 0 , s 1 , . . . , s t-1 , a t-1 , s t ).

To simplify notations, we will associate the vector v τ = (µ 0 , π 1 , µ 1 , π 2 , . . . , π t-1 , µ t ) to each trajectory τ , where π i+1 = π(s i+1 |s i , a i ) is the possibility degree to reach the state s i+1 at t = i + 1, applying the action a i at t = i and µ i = µ(s i ) is the utility obtained in the i-th state s i of the trajectory.

The possibility and the utility of trajectory τ given that δ is applied from s 0 are defined by:

π(τ |s 0 , δ) = min i=1...t π(s i |s i-1 , δ(s i-1 )) and µ(τ ) = min i=0...t µ(s i ). (3)
Two criteria, an optimistic and a pessimistic one, can then be used to evaluate δ [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF][START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF]:

u opt (δ, s 0 ) = max τ min{π (τ |s 0 , δ), µ(τ )}, (4)
u pes (δ, s 0 ) = min τ max{1 -π(τ |s 0 , δ), µ(τ )}. (5)
The policies optimizing these criteria can be computed by applying, for every state s and time step i = 0, ..., t, the following counterparts of the Bellman updates [START_REF] Sabbadin | Possibilistic Markov decision processes[END_REF]:

u opt (s, i) ← max a∈ A s min{µ(s), max s ′ ∈S min(π (s ′ |s, a), u opt (s ′ , i + 1))}, ( 6
)
u pes (s, i) ← max a∈ A s min{µ(s), min s ′ ∈S max(1 -π(s ′ |s, a), u pes (s ′ , i + 1))}, (7) δ opt (s, i) ← arg max a∈ A s min{µ(s), max s ′ ∈S min(π (s ′ |s, a), u opt (s ′ , i + 1))}, (8) δ pes (s, i) ← arg max a∈ A s min{µ(s), min s ′ ∈S max(1 -π(s ′ |s, a), u pes (s ′ , i + 1))}. ( 9
)
There we set, arbitrarily, u opt (s ′ , t + 1)) = 1 and u pes (s

′ , t + 1)) = 1.
It has allowed the definition of a (possibilistic) value iteration algorithm (see Algorithm 1 for the optimistic variant of this algorithm) which converges to an optimal policy in polytime [START_REF] Sabbadin | Possibilistic Markov decision processes[END_REF]. This algorithm proceeds by iterated modifications of a possibilistic value function Q (s, a) which evaluates the "utility" (pessimistic or optimistic) of performing a in s.

Another algorithm, (possibilistic) Policy Iteration (Algorithm 2 for the optimistic variant) is proposed in [START_REF] Sabbadin | Possibilistic Markov decision processes[END_REF] for solving possibilistic stationary, infinite horizon MDPs. Policy Iteration alternates steps of evaluation of the current policy with steps of greedy improvement of the current policy.

The drowning effect in stationary sequential decision problems

Unfortunately, possibilistic utilities suffer from an important drawback called the drowning effect: plausible enough bad or good consequences may completely blur the comparison between acts that would otherwise be clearly differentiated; as a consequence, an optimal policy δ is not necessarily Pareto efficient. Recall that a policy δ is Pareto efficient when no other policy δ ′ dominates it (i.e. there is no policy δ ′ such that (i) ∀ s ∈ S, u pes (δ ′ , s) u pes (δ, s) and (ii) ∃ s ∈ S s.t. u pes (δ ′ , s) ≻ u pes (δ, s)). The following example shows that it can simultaneously happen that δ ′ dominates δ and u pes (δ) = u pes (δ ′ ).

Example 3. The MDP of Example 2 admits two policies δ and δ ′ :

• δ(RU ) = Sav; δ(P U ) = Sav; δ(R F ) = Sav; • δ ′ (RU ) = Adv; δ ′ (P U ) = Sav; δ ′ (R F ) = Sav.
Consider a fixed horizon H = 2:

• δ has 3 trajectories: τ 1 = (RU , P U , P U ) with v τ 1 = (0.5, 0.2, 0.3, 1, 0.3); τ 2 = (RU , RU , P U ) with v τ 2 = (0.5, 1, 0.5, 0.2, 0.3); τ 3 = (RU , RU , RU ) with v τ 3 = (0.5, 1, 0.5, 1, 0.5).

• δ ′ has 2 trajectories: τ 4 = (RU , R F , R F ) with v τ 4 = (0.5, 1, 0.7, 1, 0.7); τ 5 = (RU , R F , RU ) with v τ 5 = (0.5, 1, 0.7, 1, 0.5).

Thus u opt (δ, RU ) = u opt (δ ′ , RU ) = 0.5. However δ ′ seems better than δ since it provides utility 0.5 for sure while δ provides a bad utility (0.3) in some non-impossible trajectories (τ 1 and τ 2 ). τ 3 which is good and totally possible "drowns" τ 1 and τ 2 : δ is considered as good as δ ′ .

Bounded iterations solutions to lexicographic finite horizon MDPs

Possibilistic decision criteria, especially pessimistic and optimistic utilities, are simple and realistic as illustrated in Section 2, but they have an important shortcoming: the principle of Pareto efficiency is violated since these criteria suffer from the drowning effect. Indeed, one decision may dominate another one while not being strictly preferred. In order to overcome the drowning effect, some refinements of possibilistic utilities have been proposed in the non-sequential case such as lexicographic refinements, proposed by [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF][START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF]. These refinements are fully in accordance with ordinal utility theory and satisfy the principle of Pareto dominance, that is why we have chosen to focus on them.

The present section defines an extension of lexicographic refinements to finite horizon possibilistic Markov decision processes and proposes a value iteration algorithm that looks for policies optimal with respect to these criteria.

Lexi-refinements of ordinal aggregations

In ordinal (i.e. min-based and max-based) aggregation a solution to the drowning effect based on leximin and leximax comparisons has been proposed by [START_REF] Moulin | Axioms of Cooperative Decision Making[END_REF]. It has then been extended to non-sequential decision making under uncertainty [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF] and, in the sequential case, to decision trees [START_REF] Ben Amor | Lexicographic refinements in possibilistic decision trees[END_REF]. Let us first recall the basic definition of these two preference relations. For any two vectors t and t ′ of length m built on the scale L:

t lmin t ′ iff ∀i, t σ (i) = t ′ σ (i) or ∃i * , ∀i < i * , t σ (i) = t ′ σ (i) and t σ (i * ) > t ′ σ (i * ) , (10)
t lmax t ′ iff ∀i, t µ(i) = t ′ µ(i) or ∃i * , ∀i < i * , t µ(i) = t ′ µ(i) and t µ(i * ) > t ′ µ(i * ) , (11)
where, for any vector v (here, v = t or v = t ′ ), v µ(i) (resp. v σ (i) ) is the i-th best (resp. worst) element of v. [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF][START_REF] Ben Amor | Lexicographic refinements in possibilistic decision trees[END_REF] have extended these procedures to the comparison of matrices built on L, defining preference relations lmin(lmax) and lmax(lmin) :

A lmin(lmax) B ⇔ ∀ j, a (lmax, j) ∼ = b (lmax, j) or ∃i s.t. ∀ j > i, a (lmax, j) ∼ lmin b (lmax, j) and a (lmax,i) ≻ lmin b (lmax,i) ,

A lmax(lmin) B ⇔ ∀ j, a (lmin, j) ∼ lmax b (lmin, j) or ∃i s.t. ∀ j < i, a (lmin, j) ∼ lmax b (lmin, j) and a (lmin,i) ≻ lmax b (lmin,i) , [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF] where a (☎,i) (resp. b (☎,i) ) is the i-th largest sub-vector of A (resp. B) according to ☎ ∈ {lmax, lmin}.

Like in (finite-horizon) possibilistic decision trees [START_REF] Ben Amor | Lexicographic refinements in possibilistic decision trees[END_REF] our idea is to identify the strategies of the MDP with the matrices of their trajectories, and to compare such matrices with a lmax(lmin) (resp. lmin(lmax) ) procedure for the optimistic (resp. pessimistic) case.

Lexicographic comparisons of policies

Let us first define lexicographic comparisons of policies over a given horizon E.

A trajectory over horizon E being a sequence of states and actions, any stationary policy can be identified with a matrix where each line corresponds to a distinct trajectory of length E. In the optimistic case each line corresponds to a vector

v τ = (µ 0 , π 1 , µ 1 , π 2 , . . . , π E-1 , µ E ) and in the pessimistic case to w τ = (µ 0 , 1 -π 1 , µ 1 , 1 -π 2 , . . . , 1 -π E-1 , µ E ).
This allows us to define the comparison of trajectories using leximax and leximin as follows:

τ lmin τ ′ iff (µ 0 , π 1 , . . . , π E , µ E ) lmin (µ ′ 0 , π ′ 2 , . . . , π ′ E , µ ′ E ), (14)
τ lmax τ ′ iff (µ 0 , 1 -π 1 , . . . , 1 -π E , µ E ) lmax (µ ′ 0 , 1 -π ′ 1 , . . . 1 -π ′ E , µ ′ E ). (15)
Note that the above preference relations implicitly depend on the horizon E and the same holds for stationary policies comparison. We leave aside any reference to E as the dependence will be clear from the context. Using ( 14) and ( 15), we can compare policies by:

δ lmax(lmin) δ ′ iff ∀i, τ µ(i) ∼ lmin τ ′ µ(i) or ∃i * , ∀i < i * , τ µ(i) ∼ lmin τ ′ µ(i) and τ µ(i * ) ≻ lmin τ ′ µ(i * ) , (16)
δ lmin(lmax) δ ′ iff ∀i, τ σ (i) ∼ lmax τ ′ σ (i) or ∃i * , ∀i < i * , τ σ (i) ∼ lmax τ ′ σ (i) and τ σ (i * ) ≻ lmax τ ′ σ (i * ) , (17)
where τ µ(i) (resp. τ ′ µ(i) ) is the i-th best trajectory of δ (resp. δ ′ ) according to lmin and τ σ (i) (resp. τ ′ σ (i) ) is the i-th worst trajectory of δ (resp. δ ′ ) according to lmax . Hence, the utility degree of a policy δ can be represented by a matrix U δ with n lines, s.t. n is the number of trajectories, and m = 2E + 1 columns. Indeed, comparing two policies w.r.t. lmax(lmin) (resp. lmin(lmax) ) consists in first ordering the two corresponding matrices of trajectories as follows:

• order the elements of each trajectory (i.e. the elements of each line) in increasing order w.r.t. lmin (resp. in decreasing order w.r.t. lmax ),

• then order all the trajectories. The lines of each policy are arranged lexicographically top-down in decreasing order (resp. top-down in increasing order).

Then, it is enough to lexicographically compare the two new matrices of trajectories, denoted U δ (resp. U δ ′ ), element by element. The first pair of different elements determines the best matrix/policy. Note that the ordered matrix U δ (resp. U δ ′ ) can be seen as the utility of applying policy δ (resp. δ ′ ) over a length E horizon.

Example 4.

Let us consider the Counter-Example 3 with the same MDP of Example 2. We consider, once again, the policies δ and δ ′ defined by:

• δ(RU ) = Sav; δ(P U ) = Sav; δ(R F ) = Sav; • δ ′ (RU ) = Adv; δ ′ (P U ) = Sav; δ ′ (R F ) = Sav.
For horizon H = 2:

• δ has 3 trajectories: τ 1 = (RU , P U , P U ) with v τ 1 = (0.5, 0.2, 0.3, 1, 0.3); τ 2 = (RU , RU , P U ) with v τ 2 = (0.5, 1, 0.5, 0.2, 0.3); τ 3 = (RU , RU , RU ) with v τ 3 = (0.5, 1, 0.5, 1, 0.5).

The matrix of trajectories is:

U δ =   0.5 0.2 0.3 1 0.3 0.5 1 0.5 0.2 0.3 0.5 1 0.5 1 0.5   ∼   0.2 0.3 0.3 0.5 1 0.2 0.3 0.5 0.5 1 0.5 0.5 0.5 1 1   .
So, the ordered matrix of trajectories is:

U δ =   0.5 0.5 0.5 1 1 0.2 0.3 0.3 0.5 1 0.2 0.3 0.5 0.5 1   .
• δ ′ has 2 trajectories:

τ 4 = (RU , R F , R F ) with v τ 4 = (0.5, 1, 0.7, 1, 0.7); τ 5 = (RU , R F , RU ) with v τ 5 = (0.5, 1, 0.7, 1, 0.5).
The ordered matrix of trajectories is: U δ ′ = 0.5 0.7 0.7 1 1 0.5 0.5 0.7 1 1 .

Given the two ordered matrices U δ and U δ ′ , δ and δ ′ are indifferent for optimistic utility since the two first (i.e. top-left) elements of the matrices are equal i.e. u opt (δ) = u opt (δ ′ ) = 0.5. For lmax(lmin) we compare successively the next elements (left to right then top to bottom) until we find a pair of different values. In particular, we have the second element of the first (i.e. the best) trajectory of δ ′ is strictly greater than the second element of the first trajectory of δ (0.7 > 0.5). So, the first trajectory of δ ′ is strictly preferred to the first trajectory of δ according to lmin . We deduce that δ ′ is strictly preferred to δ: δ ′ ≻ lmax(lmin) δ since (0.5, 0.7, 0.7, 1, 1) ≻ lmin (0.5, 0.5, 0.5, 1, 1).

The following propositions can be shown, concerning the fixed horizon comparison of stationary policies. Note again that the dependence on E is left implicit.

Proposition 1.

If u opt

(δ) > u opt (δ ′ ) then δ ≻ lmax(lmin) δ ′ . If u pes (δ) > u pes (δ ′ ) then δ ≻ lmin(lmax) δ ′ .

Proposition 2. lmax(lmin) and lmin(lmax) satisfy the principle of Pareto efficiency.

Now, in order to design dynamic programming algorithms, i.e. to extend the value iteration algorithm to lexi comparison, we show that the comparison of policies is a preorder and satisfies the principle of strict monotonicity defined as follows for any optimization criterion O by: ∀δ, δ ′ , δ ′′ ∈ ,

δ O δ ′ ⇐⇒ δ + δ ′′ O δ ′ + δ ′′ ,
where δ (resp. δ ′ ) and δ ′′ denote two disjoint sets of trajectories and δ + δ ′′ (resp. δ ′ + δ ′′ ) is the set of trajectories that gathers the ones of δ (resp. δ ′ ) and the ones of δ ′′ .

Then, adding or removing identical trajectories to two sets of trajectories does not change their comparison by lmax(lmin) (resp. lmin(lmax) ).

Proposition 3. Relations lmin(lmax) and lmax(lmin) are complete, transitive and satisfy the principle of strict monotonicity.

Note that u opt and u pes satisfy only a weak form of monotonicity since the addition or the removal of trajectories may transform a strict preference into an indifference if u opt or u pes is used.

Let us define the complementary MDP (S, A, π, μ) of a given MDP (S, A, π, µ) where μ(s) = 1 -µ(s), ∀s ∈ S. The complementary MDP simply gives complementary utilities. From the definitions of lmax and lmin , we can check that:

Proposition 4. τ lmax τ ′ ⇔ τ ′ lmin τ and δ lmin(lmax) δ ′ ⇔ δ′ lmax(lmin) δ.
There τ and δ are obtained by replacing µ with μ in the trajectory/ MDP. Therefore, all the results which we will prove for lmax(lmin) also hold for lmin(lmax) , if we take care to apply them to complementary policies. Since considering lmax(lmin) involves less cumbersome expressions (no 1 -•), we will give the results for this criterion. A consequence of Proposition 4 is that the results hold for the pessimistic criterion as well.

This monotonicity of the lmin(lmax) and lmax(lmin) criteria is sufficient to allow us to use a dynamic programming algorithm such as value iteration or policy iteration [START_REF] Bellman | Dynamic Programming[END_REF]. The algorithms we propose in the present paper perform explicit Bellman updates in the lexicographic framework (lines 12-13 of Algorithms 3 and 4, line 11 of Algorithm 5); the correctness of their use is proved in Propositions 6 to 10.

Basic operations on matrices of trajectories

Before going further, in order to give more explicit and compact descriptions of the algorithms and the proofs, let us introduce the following notations and some basic operations on matrices (typically, on the matrix U (s) representing trajectories issued from state s). Abusing notations slightly, we identify trajectories τ (resp. policies) with their v τ vectors (resp. matrices of v τ vectors) when there is no ambiguity. For any matrix U , [U ] l,c denotes the restriction of U to its first l lines and first c columns and U i, j denotes the element at line i and column j.

• Composition: Let U be a a × b matrix and N 1 , . . . , N a be a series of a matrices of dimension n i × c (they all share the same number of columns). The composition of U with (N 1 , . . . , ((π (s ′ |s, a), µ(s ′ )), s ′ ∈ succ(s, a)) with the matrices N s ′ = U (s ′ ). This procedure adds two columns to each matrix U (s ′ ), filled with π(s ′ |s, a) and µ(s ′ ) the possibility degrees and the utility of reaching s ′ ; then the matrices are vertically concatenated to get the matrix U (s) when making decision a. Then it is possible to lexicographically compare the resulting matrices in order to get the optimal action in state s.

N a ) denoted U × (N 1 , . . . , N a ) is a matrix of dimension ( 1≤i≤a n i ) × (b + c). For any i ≤ a, j ≤ n j , the (( i ′ <i n i ′ ) + j)-th line of U × (N 1 , . . . , N a )
• Ordering matrices: Let U be a n × m matrix, U lmaxlmin is the matrix obtained by ordering the elements of the lines of U in increasing order and the lines of U according to lmax in decreasing order (see Example 4). This operation allows to compare matrices of trajectories Q (s, a) of every action in order to compare them and choose the optimal decision.

The complexity of the operation depends on the sorting algorithm: if we use QuickSort then ordering the elements within a line is performed in O (m • log(m)), and the inter-ranking of the lines is done in O (n

• log(n) • m) operations. Hence, the overall complexity is O (n • m • log(n • m)).
• Comparison of ordered matrices: Given two ordered matrices U lmaxlmin and V lmaxlmin , we say that

U lmaxlmin > V lmaxlmin iff ∃i, j such that ∀i ′ < i, ∀ j ′ , U lmaxlmin i ′ , j ′ = V lmaxlmin i ′ , j ′ and ∀ j ′ < j, U lmaxlmin i, j ′ = V lmaxlmin i, j ′ and U lmaxlmin i, j > V lmaxlmin i, j
.

U lmaxlmin ∼ V lmaxlmin iff they are identical (comparison complexity: O (n • m)). Once matrices Q (s, a) are ordered, the lexicographic comparison of two decisions is performed by scanning the elements of their matrices, line by line from the first one. The first pair of different values determines the best matrix and the best corresponding action a is selected (see Example 4).

If the policies (or sub-policies) have different numbers of trajectories, the comparison of two matrices is based on the number of trajectories of the shortest matrix. Two cases may arise:

• If we have a strict preference between the two matrices before reaching the last line of the shortest matrix, we get a strict preference between the policies (or between the sub-policies).

• If we have an indifference up to the last line, the shortest matrix is the best for the lexicographic criterion, since it expresses less uncertainty in the corresponding policy (or in the sub-policy).

Bounded iterations lexicographic value iteration

In this section, we propose an iterative value iteration-type algorithm (Algorithm 3). This algorithm follows the same principle as in the possibilistic case (Eqs. ( 6)-( 9)). Repeated Bellman updates are performed successively E times. This algorithm will provide an approximation of a lexi optimal strategy in the infinite horizon case (by considering the policy returned for the first time step). This algorithm is sub-optimal for any fixed E, but we will see in Section 4 that letting E grow, an optimal lexicographic policy will be obtained for finite E.

We propose two versions of the value iteration algorithm: The first one computes the optimal policy with respect to the lmax(lmin) criterion and the second one provides the optimal policy with respect to the lmin(lmax) criterion. In this paper, we present and detail only the first algorithm, since the second is very similar. Future ← (U old (s ′ ), s ′ ∈ succ(s, a)); // Gather the matrices provided by the successors of s;

13 Q (s, a) ← T U s,a × Future lmaxlmin ; 14 if Q * ≤ lmaxlmin Q (s, a) then 15 Q * ← Q (s, a); 16 δ(s) ← a 17 U (s) ← Q * (s, δ(s)) 18 until e == E; 19 δ(s) ← argmax a Q (s, a) 20 return δ E = δ;
This algorithm is an iterative procedure that performs a prescribed number of updates, E, of the utility of each state, represented by a finite matrix of trajectories, using the utilities of the neighboring states.

At stage 1 ≤ e ≤ E, the procedure updates the utility of every state s ∈ S as follows:

• For each action a ∈ A, a matrix Q (s, a) is built to evaluate the "utility" of performing a in s at stage e: this is done by combining T U s,a (combination of the transition matrix T s,a = π(•|s, a) and the utilities µ(s ′ ) of the states s ′ that may follow s when a is executed) with the matrices U old (s ′ ) of trajectories provided by these s ′ at the previous stage. The matrix Q (s, a) is then ordered (the operation is made less complex by the fact that the matrices U old (s ′ ) have already been ordered at e -1).

• The lmax(lmin) comparison is performed on the fly to memorize the best Q (s, a).

• The value of state s at stage e, U (s), is the one given by the action a which provides the best Q (s, a). δ is updated, U is memorized (and U old can be discarded).

Time and space complexities of this algorithm are nevertheless expensive, since it eventually memorizes all the trajectories. At each step e its size may grow to b e • (2 • e + 1), where b is the maximal number of possible successors of an action; the overall complexity of the algorithm is

O (|S| • |A| • E • b E ), which is a problem.
Algorithm 3 is provided with a number of iterations, E. Does it converge when E tends to infinity? That is, are the returned policies identical for any E exceeding a given threshold? Before answering (positively) this question in Section 4.4, we are going to define bounded utility matrices solutions to lexicographic possibilistic MDPs. These solution concepts will be useful to answer the above question.

Bounded utility solutions to lexicographic MDPs

We have just proposed a lexicographic value iteration algorithm for the computation of lexicographic policies based on the whole matrices of trajectories. As a consequence, the spatial/temporal complexity of the algorithm is exponential in the number of iterations. This section presents an alternative way to get lexicographic policies. Rather than limiting the size of the matrices of trajectories by limiting the number of iterations, we propose to "forget" the less significant part of the matrices of utility and to decide only based on the most significant (l, c) sub-matrices -we "bound" the utility matrices. We propose in the present section two algorithms based on this idea, namely a value iteration and a policy iteration algorithms.

Bounded lexicographic comparisons of utility matrices

Recall that, for any matrix U , [U ] l,c denotes the restriction of U to its first l lines and first c columns. Notice now that, at any stage e and for any state s [U (s)] 1,1 (i.e. the top left value in U (s)) is precisely equal to u opt (s). We have seen that making the choices on this basis is not discriminant enough. On the other hand, taking the whole matrix into account is discriminant, but exponentially costly. Hence the idea of considering more than one line and one column, but less than the whole matrix -namely the first l lines and c columns of U t (s) lmaxlmin ; hence the definition of the following preference:

δ ≥ lmaxlmin,l,c δ ′ iff [δ lmaxlmin ] l,c ≥ [δ ′ lmaxlmin ] l,c . (18)
≥ lmaxlmin,1,1 corresponds to opt and ≥ lmaxlmin,+∞,+∞ corresponds to ≥ lmaxlmin .

The following proposition shows that this approach is sound and that ≻ lmaxlmin,l,c refines u opt : Proposition 5.

• For any l, l ′ , c such that l ′ > l, δ ≻ lmaxlmin,l,c δ ′ ⇒ δ ≻ lmaxlmin,l ′ ,c δ ′ . • For any l, c δ ≻ opt δ ′ ⇒ δ ≻ lmaxlmin,l,c δ ′ .
In other words, the order over the policies is refined for a fixed c when l increases. It tends to ≻ lmaxlmin when c = 2.E + 1 and l tends to b E . Notice that the combinatorial explosion is due to the number of lines (the number of columns is bounded by 2 • E + 1), hence we shall bound the number of considered lines only.

Up to this point, the comparison by ≥ lmaxlmin,l,c is made on the basis of the first l lines and c columns of the full matrices of trajectories. This does obviously not reduce their size. The important following Proposition allows us to make the l, c reduction of the ordered matrices at each step (after each composition), and not only at the very end, thus keeping space and time complexities polynomial. Proposition 6. Let U be a a × b matrix and N 1 , . . . , N a be a series of a matrices of dimension a i × c. It holds that:

[(U × (N 1 , . . . , N a )) lmaxlmin ] l,c = [(U × ([N lmaxlmin 1 ] l,c , . . . , [N lmaxlmin a ] l,c )) lmaxlmin) ] l,c .

Bounded utility lexicographic value iteration

It is now easy to design a generalization of the possibilistic algorithm of value iteration (Algorithm 1) by keeping a submatrix of each current value matrix -namely the first l lines and c columns. We call this algorithm Bounded Utility Value Iteration (BU -V I) (see Algorithm 4).

Algorithm 4: Bounded Utility Lmax(lmin) Value Iteration (BU-VI).

Data: A possibilistic MDP, bounds (l, c); δ, the policy built by the algorithm, is a global variable Result: A policy δ optimal for lmaxlmin,l,c 1 begin 2 foreach s ∈ S do U (s) ← ((µ(s)));

3 foreach s ∈ S, a ∈ A do 4 T U s,a ← T s,a × ((µ(s ′ )), s ′ ∈ succ(s, a));
Q (s, a) ← [ T U s,a × Future lmaxlmin ] l,c ; 13 if Q * ≤ lmaxlmin Q (s, a) then 14 Q * ← Q (s, a); 15 δ(s) ← a 16 U (s) ← Q * (s, δ(s)) 17 δ(s) ← argmax a Q (s, a); 18 U (s) ← max a Q (s, a) 19 return δ;
When the horizon of the MDP is finite this algorithm provides in polynomial time a policy that is always at least as good as the one provided by u opt (according to lmax(lmin)) and tends to lexicographic optimality when c = 2 • E +

(|S| • |A| • E • b • (l • c) • log(l • c)).
When the horizon of the MDP is not finite, equations ( 16) and [START_REF] Howard | Dynamic Programming and Markov Processes[END_REF] are not enough to rank-order the policies. The length of the trajectories may be infinite, as well as their number. This problem is well known in classical probabilistic MDPs where a discount factor is used to attenuate the influence of later utility degrees -thus allowing the convergence of the algorithm [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. On the contrary, classical MDP s do not need any discount factor and Value Iteration, based on the evaluation for l = c = 1, converges for infinite horizon case [START_REF] Sabbadin | Possibilistic Markov decision processes[END_REF]. In a sense, this limitation to l = c = 1 plays the role of a discount factor -but a very drastic one. Extending the comparison by using ≥ lmaxlmin,l,c with larger (l, c) as shown below allows to use a less drastic discount.

In other terms, ≥ lmaxlmin,l,c can be used in the infinite case, as shown by the following proposition.

Proposition 7 (Bounded utility lmax(lmin)-policy evaluation converges). Let U t (s) be the matrix issued from s at instant t when a strategy δ is executed. It holds that:

∀ l, c, ∃ t, such that ∀ t ′ ≥ t, (U t ) lmaxlmin l,c (s) = (U t ′ ) lmaxlmin l,c
(s) ∀s.

Hence there exists a stage t, where the value of a policy becomes stable if computed with the bounded utility lmax(lmin) evaluation algorithm. This criterion is thus soundly defined and can be used in the infinite horizon case (and of course in the finite horizon case).

The number of iterations of Algorithm 4 is not explicitly bounded but the convergence of the algorithm is guaranteedthis is a direct consequence of Proposition 7.

Corollary 1 (Bounded utility lmax(lmin)-value iteration converges

). ∀ l, c, ∃ t such that, ∀ t ′ ≥ t, (U t ) lmaxlmin l,c (s) = (U t ′ ) lmaxlmin l,c
(s) ∀s.

The overall complexity of bounded utility lmax(lmin)-value iteration (Algorithm 4) is bounded by

O (|S| • |A| • |L| • b • (l • c) • log(l • c)) since the number of iterations is O (|S| • |A| • |L|
and all matrices are of size (l, c).

Bounded utility lexicographic-policy iteration

In Ref. [START_REF] Howard | Dynamic Programming and Markov Processes[END_REF], Howard shows that a policy often becomes optimal long before the convergence of the value estimates. That is why Puterman [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] has proposed a policy iteration algorithm. This algorithm has been adapted to possibilistic MDPs by [START_REF] Sabbadin | Possibilistic Markov decision processes[END_REF].

Likewise, we propose a (bounded utility) lexicographic policy iteration algorithm (Algorithm 5), denoted here BU -P I that alternates improvement and evaluation phases, as any policy iteration algorithm. In line 3 of Algorithm 5, an arbitrary initial policy is chosen. The algorithm then proceeds by evaluating the current policy, through successive updates of the value function (lines 8 to 11); the convergence of this evaluation is easily derived from that of the bounded utility lmax(Lmin)-value iteration algorithm. Then the algorithm enters the improvement phase: Lines 17-18 compute Q (s, a), the (bounded lexicographic) utility of playing action a in state s and then applying policy δ old in subsequent states (the policy computed during the last iteration); as usual in Policy Iteration style algorithms, the updated policy (δ) is then obtained by greedily improving the current action, which is done in line 20. Since the actions considered at line 20 do include the one prescribed by δ old , either nothing is changed, and the algorithm stops, or the new policy, δ, is better than the previous one δ old .

Proposition 8. Bounded utility lmax(lmin)-policy iteration converges to an optimal policy for lmaxlmin,l,c in finite time.

Policy iteration (Algorithm 5) converges and is guaranteed to find a policy optimal for the (l, c) lexicographic criterion in finite time and usually in a few iterations. As for the algorithmic complexity of the classical, stochastic, policy iteration algorithm (which is still not well understood [START_REF] Gupta | Improved strong worst-case upper bounds for MDP planning[END_REF]), a tight bound worst-case complexity of lexicographic policy iteration is hard to obtain. Therefore, we provide an upper-bound of this complexity.

The policy iteration algorithm never visits a policy twice: in the worst case, the number of trial iterations before convergence is exponential but it is dominated by the number of distinct policies. So, the complexity of this algorithm is dominated by (| A| |S| ). Besides, each iteration has a cost, the evaluation phase relying on a bounded utility value itera-

tion algorithm that costs O (|S| • |A| • |L| • b • (l • c) • b • log(l • c))
when many actions are possible at a given step, and cost

O (|S| • |L| • b • (l • c) • b • log(l • c))
here because one action is selected (by the current policy) for each state. Thus, the overall complexity of the algorithm is in

O (|A| |S| • |S| • |L| • b • (l • c) • b • log(l • c)).
Thus, the overall complexity of the algorithm is in

O (|A| |S| • |L| • (l • c) 2 • |S| • b • log(l • c)).

Back to lexicographic-value iteration: from finite to infinite horizon -MDPs

The bounded iterations algorithm defined in section 3 (Algorithm 3, (B I-V I)) can be used for both finite horizon and infinite horizon MDPs, because it fixes a number of iterations E; if E is low, the policy reached in not necessarily optimalthe algorithm is an approximation algorithm. Now, exploiting the above propositions, we are able to show that the bounded iterations Lmax(lmin) value iteration algorithm (Algorithm 3) converges when E tends to infinity. To do so, we first prove the following proposition: Proposition 9. Let an arbitrary stationary MDP be given. Then, there exist two positive natural numbers (l * , c * ), such that for any pair (δ, δ ′ ) of arbitrary policies and any state s ∈ S, and for any pair (l, c) such that l ≥ l * and c ≥ c * ,

δ(s) ≻ lmaxlmin,l * ,c * δ ′ (s) ⇔ δ(s) ≻ lmaxlmin,l,c δ ′ (s)
Now, this proposition can be used to prove the convergence of the bounded iterations Lmax(lmin)-value iteration algorithm. For this, let us define ≻ lmaxlmin = de f ≻ lmaxlmin,l * ,c * , the unique preference relation between policies that results from Proposition 9.

Proposition 10. If we let δ E be the policy returned by Algorithm 3 for any fixed E, we can show that the sequence (δ E ) converges and that there exists a finite E * , such that:

lim E→∞ δ E = δ E * .
Furthermore, δ E * is optimal with respect to ≻ lmaxlmin .

The sequence of policies obtained for (B I-V I) (Algorithm 3) when E tends to infinity converges. Furthermore, the limit is attained for a finite (but unknown in advance) E * . Alternately, it is also attained for the (BU -V I) and (BU -P I) algorithms, with finite but unknown (l * , c * ). Now, let us summarize the theoretical results that we have obtained so far. We have shown that possibilistic utilities (optimistic and pessimistic) are special cases of bounded lexicographic utilities, which can be represented by matrices.

Possibilistic utilities are obtained when l = c = 1.

The possibilistic value iteration and policy iteration algorithms can be extended to compute policies which are optimal according to ≻ lmaxlmin,l,c . Finally, if infinite horizon lexicographic optimal policies are defined as the limiting policies obtained from a non-bounded lexicographic value-iteration algorithm, we have shown that such policies can be computed by applying our bounded utility lmax(lmin) value iteration algorithm and that only a finite number of iterations (even though not known in advance) is required.

Experiments

In order to evaluate the previous algorithms, we propose, in the following, two experimental analyses: in the first one we will compare the bounded iterations algorithm of value iteration (Algorithm 3) with the bounded utility one and in the second we propose to compare the bounded utility lexicographic policy iteration algorithm with the bounded utility lexicographic value iteration one. The algorithms have been implemented in Java and the experiments have been performed on an Intel Core i5 processor computer (1.70 GHz) with 8GB DDR3L of RAM.

Bounded utility vs bounded iterations value iteration

Experimental protocol. We now compare the performance of bounded utility lexicographic value iteration (BU -V I) as an approximation of lexicographic value iteration (B I-V I) for finite horizon problems, in the Lmax(lmin) variant. Because the horizon is finite, the number of steps of (B I-V I) can be set equal to the horizon and the algorithm provides a solution optimal according to Lmax(lmin). (BU -V I) on the other side limits the size on the matrices, and can lead to sub-optimal solutions.

We evaluate the performance of the algorithms by carrying out simulations on randomly generated finite horizon the more important the effectiveness of cutting matrices with BU -V I ; the lower this rate, the more important the drowning effect.

Results. Fig. 2(a) presents the average execution CPU time for the two algorithms. Obviously, for both B I-V I and BU -V I , the execution time increases with the horizon. Also, we observe that the CPU time of BU -V I increases according to the values of (l, c) but it remains affordable, as the maximal CPU time is lower than 1 s for MDPs with 25 states and 4 actions when (l, c) = (40, 40) and E = 25. Unsurprisingly, we can check that the BU -V I (regardless of the values of (l, c)) is faster than B I-V I especially when the horizon increases: the manipulation of l, c-matrices is obviously less expensive than the one of full matrices. The saving increases with the horizon.

As with the success rate, the results are described in Fig. 2(b). It appears that BU -V I provides a very good approximation especially when increasing (l, c). It provides the same optimal solution as the B I-V I in about 90% of cases, with an (l, c) = (200, 200). Moreover, even when the success rate of BU -V I decreases (when E increases), the quality of approximation is still good: never less than 70% of optimal actions returned, with E = 25. These experiments conclude in favor of bounded value iteration: the quality of its approximated solutions are comparable with those of the unbounded version for high (l, c) and increases when (l, c) increase, while it is much faster.

Bounded utility lexicographic policy iteration vs bounded utility lexicographic value iteration

Experimental protocol.

In what follows we evaluate the performances of bounded utility lexicographic policy iteration (BU -P I) and bounded lexicographic value iteration (BU -V I), in the lmax(lmin) variant. We evaluate the performance of the algorithms on randomly generated MDP s as those of Section 5.1 with |S| = 25 and |A s | = 4, ∀s.

We ran the two algorithms for different values of (l, c) (100 MDPs are considered in each sample). For each of the two algorithms we measure the CPU time needed to converge. We also measure the average number of value iterations for (BU -V I) and the average number of policy iterations for (BU -P I).

Results. Table 1 presents the average execution CPU time and the average number of iterations for the two algorithms.

Obviously, for both BU -P I and BU -V I , the execution time increases according to the values of (l, c) but it remains affordable, as the maximal CPU time is lower than 0.1 s for MDPs with 25 states and 4 actions when (l, c) = (10, 10). It appears that BU -P I (regardless of the values of (l, c)) is slightly faster than BU -V I .

Consider now the number of iterations. At each iteration, BU -P I considers one policy, explicitly, and updates it at line 20. And so does value iteration: for each state, the current policy is updated at line 15. Table 1 shows that BU -P I always considers fewer policies than BU -V I . This experiment provides an empirical evidence in favor of policy iteration over value iteration, as the former converges to the approximate solution faster. However, this conclusion may vary with the experiments, so both algorithms are worth considering when tackling a given problem.

Conclusion

In order to overcome the drowning effect in possibilistic stationary sequential decision problems, we have proposed two lexicographic criteria, initially introduced by Fargier and Sabbadin in [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF] for non-sequential problems, that compare policies based on their corresponding matrices of trajectories. We have shown that these decision criteria satisfy the principle of efficiency and strict monotonicity.

Because the sizes of the matrices of trajectories grow exponentially with the number of iterations, such comparisons cannot lead to a finite time algorithm except if the horizon of the problem is finite. That is why we have proposed bounded utility lexicographic algorithms as approximations of the full lexicographic ones.

First, we have proposed a Lexicographic Value Iteration algorithm for stationary MDPs with two variants: (i) an algorithm that compare full matrices but halts in a finite number of steps, (ii) an algorithm which bounds the size of the saved matrices and refines the possibilistic criteria, whatever the choice of the bounds.

Then, we have proposed a bounded Lexicographic Policy iteration algorithm and we have shown that this algorithm converges in a finite number of iterations.

The convergence of these algorithms has been shown and their efficiency has been assessed experimentally. In particular, the algorithm of Policy Iteration appears to be experimentally faster than the algorithm of Bounded Utility Value Iteration (which is also usual in the stochastic case [START_REF] Gupta | Improved strong worst-case upper bounds for MDP planning[END_REF]).

Future work includes two research tracks. First, as far as the infinite horizon case is concerned, other types of lexicographic refinements could be proposed. One of these options could be to avoid the duplication of the set of transitions that occur several times in a single trajectory and only record once the observed transitions.

A second line of research of this work will be to define reinforcement learning [START_REF] Sutton | Introduction to Reinforcement Learning[END_REF] type algorithms for MDP s. Such algorithms would use observed samples (s, a, s ′ , π, µ) of the trajectories to compute an approximate lexicographic policy, instead of using full dynamic programming over all possible trajectories. This would offer an alternative to existing quantilebased reinforcement learning approaches [START_REF] Gilbert | Quantile reinforcement learning[END_REF] for ordinal MDPs.

Appendix A. Proofs of propositions

Proof of Proposition 1.

• We prove that lmax(lmin) refines u opt in stationary MDP. We consider two policies δ and δ ′ .

If

u opt (δ, s 0 ) > u opt (δ ′ , s 0 ) ⇔ max τ ∈δ min{π (τ |s 0 , δ), u(τ )} > max τ ′ ∈δ ′ min{π (τ ′ |s 0 , δ ′ ), u(τ ′ )} ⇒ max τ ∈δ min{ min i=1..h π(s i |s i-1 , δ(s i-1 )), min i=1..h u(s i )} > max τ ′ ∈δ ′ min{ min i=1..h π ′ (s i |s i-1 , δ ′ (s i-1 )), min i=1..h u ′ (s i )} ⇒ max τ ∈δ min(µ 0 , π 1 , µ 1 , π 2 , . . . , π h-1 , µ h ) > max τ ′ ∈δ ′ min(µ ′ 0 , π ′ 1 , µ ′ 1 , π ′ 2 , . . . , π ′ h-1 , µ ′ h ). Since min(µ 0 , π 1 , µ 1 , π 2 , . . . , π h-1 , µ h ) > min(µ ′ 0 , π ′ 1 , µ ′ 1 , π ′ 2 , . . . , π ′ h-1 , µ ′ h ) ⇒ (µ 0 , π 1 , µ 1 , π 2 , . . . , π h-1 , µ h ) ≻ lmin (µ ′ 0 , π ′ 1 , µ ′ 1 , π ′ 2 , . . . , π ′ h-1 , µ ′
h ) (as leximin ordering refines min ordering), then τ λ(1) ≻ lmin τ ′ λ(1) ⇒ δ ≻ lmax(lmin) δ ′ where τ λ(1) (resp. τ ′ λ(1) ) is the best trajectory of δ (resp. δ ′ ) according to lmin . Using the definition of lmax(lmin) (Eq. ( 16)) we have δ ≻ lmax(lmin) δ ′ . Thus, lmax(lmin) refines u opt .

• We prove in the same way that lmin(lmax) refines u pes . Considering two policies δ and δ ′ s.t. u pes (δ, s 0 ) > u pes (δ ′ , s 0 ) ⇔ min

τ ∈δ max{1 -π(τ |s 0 , δ), u(τ )} > min τ ′ ∈δ ′ max{1 -π(τ ′ |s 0 , δ ′ ), u(τ ′ )} ⇔ min τ ∈δ max{ min i=1..h (1 -π(s i |s i-1 , δ(s i-1 ))), min i=1..h u(s i )} > min τ ′ ∈δ ′ max{ min i=1..h (1 -π ′ (s i |s i-1 , δ ′ (s i-1 ))), min i=1..h u ′ (s i )} ⇔ min τ ∈δ max{min(µ 0 , 1 -π 1 , µ 1 , 1 -π 2 , . . . , 1 -π h-1 , µ h )} > min τ ′ ∈δ ′ max{(µ ′ 0 , 1 -π ′ 1 , µ ′ 1 , 1 -π ′ 2 , . . . , 1 -π ′ h-1 , µ ′ h )}. Since max(µ 0 , 1 -π 1 , µ 1 , 1 -π 2 , . . . , 1 -π h-1 , µ h ) > max(µ ′ 0 , 1 -π ′ 1 , µ ′ 1 , 1 -π ′ 2 , . . . , 1 -π ′ h-1 , µ ′ h ) ⇒ (µ 0 , 1 -π 1 , µ 1 , 1 -π 2 , . . . , 1 -π h-1 , µ h ) ≻ lmax (µ ′ 0 , 1 -π ′ 1 , µ ′ 1 , 1 -π ′ 2 , . . . , 1 -π ′ h-1 , µ ′ h ) (as leximax ordering refines max ordering).
Then τ σ (1) ≻ lmax τ ′ σ (1) ⇒ δ ≻ lmin(lmax) δ ′ where τ σ (1) (resp. τ ′ σ (1) ) is the worst trajectory of δ (resp. δ ′ ) according to lmax . So, by definition of lmin(lmax) (Eq. ( 17)) we have δ ≻ lmin(lmax) δ ′ . We deduce that lmin(lmax) refines u pes . ✷ Proof of Proposition 2. (i) We prove that lmax(lmin) satisfy the principle of Pareto efficiency. So, suppose that δ lmax(lmin) δ ′ . Two cases arise:

• if ∀N, δ N ∼ lmax(lmin) δ ′ N i.e. ∀i, τ λ(i) ∼ lmin τ ′ λ(i) and then δ ∼ lmax(lmin) δ ′ , • if ∀N, δ N lmax(lmin) δ ′ N and ∃N * , δ N * ≻ lmax(lmin) δ ′ N * i.e. if ∃i * , s.t. ∀i < i * , τ λ(i) ∼ lmin τ ′ λ(i) and τ λ(i * ) ≻ lmin τ ′ λ(i * ) . Then, τ λ(i * ) ≻ lmin τ ′ λ(i * ) implies that there exist a pair of different (β i * ,k , β ′ i * ,k ), where β i * ,k (resp. β ′ i * ,k
) is an element of τ λ(i * ) (resp. τ ′ λ(i * ) ), that determines the best policy. Here we get β i * ,k > β ′ i * ,k i.e. τ λ(i * ) ≻ lmin τ ′ λ(i * ) and thus δ N * ≻ lmax(lmin) δ ′ N * then δ ≻ lmax(lmin) δ ′ . In summary, if we have δ lmax(lmin) δ ′ and ∃i * , s.t. τ λ(i * ) ≻ lmin τ ′ λ(i * ) we get δ ≻ lmax(lmin) δ ′ which expresses exactly the principle of Pareto efficiency in the case lmax(lmin) .

(ii) Let us prove lmin(lmax) satisfy the principle of Pareto efficiency. When considering the lmin(lmax) order, the same kind of result can be obtained.

So, suppose that δ lmin(lmax) δ ′ . Two cases arise:

• if ∀N, δ N ∼ lmin(lmax) i.e. ∀i, τ σ (i) ∼ lmax τ ′ σ (i) and then δ ∼ lmin(lmax) δ ′ , • if ∀N, δ N lmin(lmax) δ ′ N and ∃N * , δ N * ≻ lmax(lmin) δ ′ N * i.e. ∃i * , s.t. ∀i < i * , τ σ (i) ∼ lmax τ ′ σ (i) and τ σ (i * ) ≻ lmax τ ′ σ (i * ) . Then, τ σ (i * ) ≻ lmax τ ′ σ (i * ) implies that there exist a pair of different (β i * ,k , β ′ i * ,k ), where β i * ,k (resp. β ′ i * ,k
) is an element of τ σ (i * ) (resp. τ ′ σ (i * ) ), determining the best policy. We get β i * ,k > β ′ i * ,k i.e. τ σ (i * ) ≻ lmax τ ′ σ (i * ) and thus δ ≻ lmin(lmax) δ ′ .

In summary, if we have δ lmin(lmax) δ ′ and ∃i * , s.t. τ σ (i * ) ≻ lmax τ ′ σ (i * ) we get δ ≻ lmin(lmax) δ ′ which expresses exactly the principle of Pareto efficiency in the case of lmin(lmax) . ✷ Proof of Proposition 3.

• Completeness. It is a consequence of the completeness of lmax and lmin .

• Transitivity. We prove that lmax(lmin) is transitive. The proof relies on the transitivity of lmin . Let us consider three policies, δ, δ ′ and δ ′′ and assume δ lmax(lmin) δ ′ and δ ′ lmax(lmin) δ ′′ . Since δ lmax(lmin) δ ′ and δ ′ lmax(lmin) δ ′′ , then we are in either following cases:

1. ∀i, τ λ(i) ∼ lmin τ ′ λ(i) ∼ lmin τ ′′ λ(i) . This happens when δ ∼ lmax(lmin) δ ′ ∼ lmax(lmin) δ ′′ . And then, by transitivity of lmin , we have ∀i, τ λ(i) ∼ lmin τ ′′ λ(i) ⇔ δ ∼ lmax(lmin) δ ′′ . 2. When either δ ≻ lmax(lmin) δ ′ or δ ′ ≻ lmax(lmin) δ ′′ , then, by definition of lmax(lmin) , there exists i * , such that:

(a) ∀i < i * , τ λ(i) ∼ lmin τ ′ λ(i) ∼ lmin τ ′′ λ(i) , (b) τ λ(i * ) lmin τ ′ λ(i * ) lmin τ ′′ λ(i * ) and (c) either τ λ(i * ) ≻ lmin τ ′ λ(i * ) or τ ′ λ(i * ) ≻ lmin τ ′′ λ(i * ) , or both.
Then, once again by transitivity of lmin , τ λ(i * ) ≻ lmin τ ′′ λ(i * ) .

So, δ ≻ lmax(lmin) δ ′′ . So, points 1 and 2 imply, together, that δ lmax(lmin) δ ′ and δ ′ lmax(lmin) δ ′′ imply δ lmax(lmin) δ ′′ .

• Similarly, it can be checked that lmin(lmax) is transitive. Let us consider three policies, δ, δ ′ and δ ′′ and assume δ lmin(lmax) δ ′ and δ ′ lmin(lmax) δ ′′ . Since δ lmin(lmax) δ ′ and δ ′ lmin(lmax) δ ′′ , then we are in either following cases:

1. ∀i, τ σ (i) ∼ lmax τ ′ σ (i) ∼ lmax τ ′′ σ (i) .
This happens when δ ∼ lmin(lmax) δ ′ ∼ lmin(lmax) δ ′′ . And then, by transitivity of lmax , we have ∀i, τ σ (i) ∼ lmax τ ′′ σ (i) ⇔ δ ∼ lmin(lmax) δ ′′ . 2. When either δ ≻ lmin(lmax) δ ′ or δ ′ ≻ lmin(lmax) δ ′′ , then, by definition of lmin(lmax) , there exists i * , such that:

(a) ∀i < i * , τ σ (i) ∼ lmax τ ′ σ (i) ∼ lmax τ ′′ σ (i) , (b) τ σ (i * ) lmax τ ′ σ (i * ) lmax τ ′′ σ (i * ) and (c) either τ σ (i * ) ≻ lmax τ ′ σ (i * ) or τ ′ σ (i * ) ≻ lmax τ ′′ σ (i * ) , or both.
Then, once again by transitivity of lmax , τ σ (i * ) ≻ lmax τ ′′ σ (i * ) .

So, δ ≻ lmin(lmax) δ ′′ . So, points 1 and 2 imply, together, that δ lmin(lmax) δ ′ and δ ′ lmin(lmax) δ ′′ imply δ lmin(lmax) δ ′′ .

• Monotonicity. δ + δ ′′ contains two disjoint sets of trajectories (i.e. vectors): the ones of δ and the ones of δ ′′ (and similarly for δ ′ + δ ′′ ).

Then, adding or removing identical trajectories (i.e. vectors) to two sets of trajectories does not change their comparison by lmax(lmin) (resp. lmin(lmax) ) -while it may transform a strict preference into an indifference if u opt (resp. u pes ) were used.

To be more precise, assume, for example, that δ ≻ lmax(lmin) δ ′ .

Then, ∃i * , ∀i < i * , τ λ(i) ∼ lmin τ ′ λ(i) and τ λ(i * ) ≻ lmin τ ′ λ(i * ) . The trajectories corresponding to δ ′′ are composed of trajectories which rank before τ λ(i * ) , and after τ λ(i * ) . Obviously, the ones that rank before τ λ(i * ) are added to both lists of trajectories, and thus simply delay i * while not inducing a new preference. And the ones that rank after τ λ(i * ) are not taken into consideration in the comparison of δ + δ ′′ and δ ′ + δ ′′ . In the same way, by definition of lmin(lmax) we get δ ≻ lmin(lmax) δ ′ i.e. ∃i * , ∀i < i * , τ σ (i) ∼ lmax τ ′ σ (i) and τ σ (i * ) ≻ lmax τ ′ σ (i * ) . The same result as for τ λ(i * ) handles for τ σ (i * ) . Thus, lmax(lmin)

and lmin(lmax) are strictly monotonic. ✷ Proof of Proposition 4. It is sufficient to show that:

δ MDP lmax(lmin) δ ′ ⇔ δ ′ MDP inv lmin(lmax) δ, (19)
where MDP inv lmin(lmax) is the pessimistic lexicographic comparison of policies in the MDP where the utilities of all states have been reversed (u ′ (N) = 1 -u(N)).

For any two policies δ and δ ′ :

• If δ ≻ MDP lmax(lmin) δ ′ then ∃i * , ∀i ≤ i * , τ λ(i) ∼ lmin τ ′ λ(i) and τ λ(i * ) ≻ lmin τ ′ λ(i * ) ⇔ (µ 0 , π 1 , µ 1 , π 2 , . . . , π h-1 , µ h ) ≻ lmin (u ′ 0 , π ′ 1 , µ ′ 1 , π ′ 2 , . . . , π ′ h-1 , µ ′ h ).
Now let inverse each degree in both trajectories, we get:

((1 -µ 0 ), (1 -π 1 ), (1 -µ 1 ), (1 -π 2 ), . . . , (1 -π h-1 ), (1 -µ h )) ≺ lmax ((1 -µ ′ 0 ), (1 -π ′ 1 ), (1 -µ ′ 1 ), (1 -π ′ 2 ), . . . , (1 -π ′ h-1 ), (1 -µ ′ h )) ⇔ (µ 0 , (1 -π 1 ), µ 1 , (1 -π 2 ), . . . , (1 -π h-1 ), µ h ) ≺ lmax (µ ′ 0 , (1 -π ′ 1 ), µ ′ 1 , (1 -π ′ 2 ), . . . , (1 -π ′ h-1 ), µ ′ h ) i.e. τ σ (i * ) ≺ lmax τ ′ σ (i * )
which is the lmax relation when considering MD P inv . We get δ ′ MDP inv lmin(lmax) δ.

• If δ ∼ MDP lmax(lmin) δ ′ then ∀i, τ λ(i) ∼ lmin τ ′ λ(i) ⇔ (µ 0 , π 1 , µ 1 , π 2 , . . . , π h-1 , µ h ) ∼ lmin (µ ′ 0 , π ′ 1 , µ ′ 1 , π ′ 2 , . . . , π ′ h-1 , µ ′ h ).
If we inverse each degree in both trajectories, we get:

((1 -µ 0 ), (1 -π 1 ), (1 -µ 1 ), (1 -π 2 ), . . . , (1 -π h-1 ), (1 -µ h )) ∼ lmax ((1 -µ ′ 0 ), (1 -π ′ 1 ), (1 -µ ′ 1 ), (1 -π ′ 2 ), . . . , (1 -π ′ h-1 ), (1 -µ ′ h )) ⇔ (µ 0 , (1 -π 1 ), µ 1 , (1 -π 2 ), . . . , (1 -π h-1 ), µ h ) ∼ lmax ((1 -π ′ 1 ), . . . , (1 -π ′ h ), µ ′ h ) i.e. τ σ (i) ∼ lmax τ ′ σ (i) . We get δ ′ ∼ MDP inv lmin(lmax) δ. ✷ Proof of Proposition 5.
• Note that, for any t, s, we have:

U t (s) lmaxlmin l,c has the form              . . . π(s ′ i |s, a), u(s ′ i ) . . . π(s ′ i |s, a), u(s ′ i ) U t-1 (s ′ i ) lmaxlmin . . .       lmaxlmin        l,c
Formally,

U t (s) lmaxlmin l,c = [((π (s ′ 1 |s, a), u(s ′ 1 )) ⊗ U t-1 (s ′ 1 ) lmaxlmin ) ⊕ ((π (s ′ 2 |s, a), u(s ′ 2 )) ⊗ U t-1 (s ′ 2 ) lmaxlmin ) ⊕ ... ⊕ ((π (s ′ k |s, a), u(s ′ k )) ⊗ U t-1 (s ′ k ) lmaxlmin )].
Let A be a n × m matrix, A lmaxlmin (i,x:y) denote the part of the line i, of A, having yx elements from column x to y s.t. x < y ≤ m. Now, note that, if A and B are two matrices with exactly c columns:

A lmaxlmin l,c > lmaxlmin B lmaxlmin l,c if and only if ∃i * ≤ l, such that ∀i < i * , A lmaxlmin (i) = lmin B lmaxlmin (i)
and A lmaxlmin

(i * ) > lmin B lmaxlmin (i * )
.

Clearly, in this case replacing A and B with U t (s) lmaxlmin when considering δ and U ′ t (s) lmaxlmin when considering δ ′ , if such a i * ≤ l exists for a given l, the same i * works for l ′ > l. Thus, ≻ lmaxlmin,l ′ ,c refines ≻ lmaxlmin,l,c .

Remark that the property does not hold for c. Increasing c does not refine the order ≻ lmaxlmin,l,c,t,s . Indeed, given c < c ′ , we can find a pair of matrices for which it holds all together that:

-A lmaxlmin (1,1:c) = lmin B lmaxlmin (1,1:c) , -A lmaxlmin (2,1:c) > lmin B lmaxlmin (2,1:c) and -A lmaxlmin (1,1:c ′ ) < lmin B lmaxlmin (i * ,1:c ′ ) .
Thus, A lmaxlmin ≻ lmaxlmin,l=2,c B lmaxlmin and B lmaxlmin ≻ lmaxlmin,l=2,c ′ A lmaxlmin . One can easily build a decision problem and two policies corresponding to matrices A and B satisfying the above. Thus, increasing c does not lead to a more refined order.

• From the first point, above, it holds that ≻ lmaxlmin,l=1,c refines ≻ lmaxlmin,l=1,c=1 and that ≻ lmaxlmin,l,c refines ≻ lmaxlmin,l=1,c . So, ≻ lmaxlmin,l,c refines ≻ lmaxlmin,l=1,c=1 , which is equivalent to the order induced by u opt . Thus, optimal solutions of ≻ lmaxlmin,l,c are also optimal for u opt , in all steps of the stationary MDP . ✷ Proof of Proposition 6. Note that

(U ⊗ (N 1 , . . . , N a )) lmaxlmin l,c = [(U 1 ⊗ N 1 ) ⊕ (U 2 ⊗ N 2 ) ⊕ ... ⊕ (U k ⊗ N k )] lmaxlmin .
Now, note the two following facts:

Fact 1. (A ⊕ B) lmaxlmin = (A) lmaxlmin ⊕ (B) lmaxlmin lmaxlmin .
The reason is that: A lmaxlmin first reorders each line in lmin order, which can be done independently for each line and then all ordered lines are ordered through lmax. This second step can be done separately for each submatrix, provided that the lines are leximax-reordered once more, which is done by the external lmax(lmin) operator.

Fact 2. U

(i) ⊗ A lmaxlmin = U (i) ⊗ (A) lmaxlmin lmaxlmin .
This second fact holds since adding identical elements to each line of a matrix does not modify the leximin ordering of the lines. In the right hand term of the equality, the outer lmaxlmin operator only inserts the terms of U (i) in all lines of matrix A lmaxlmin . Now, from Fact 1, we get:

(U ⊗ (N 1 , . . . , N a )) lmaxlmin = [(U 1 ⊗ N 1 ) lmaxlmin ⊕ (U 2 ⊗ N 2 ) lmaxlmin ⊕ ...⊕ (U k ⊗ N k ) lmaxlmin ] lmaxlmin .
And then, from Fact 2: . Now, notice that:

(U ⊗ (N 1 , . . . , N a )) lmaxlmin = [(U 1 ⊗ (N 1 ) lmaxlmin ) lmaxlmin ⊕ (U 2 ⊗ (N 2 ) lmaxlmin ) lmaxlmin ⊕ ... ⊕ (U k ⊗ (N k ) lmaxlmin
• the N lmaxlmin i are lmax(min)-ordered, as well as the lines U (i) ,

• the N lmaxlmin i have exactly c columns and

• since the resulting (reordered) matrix has l lines, it cannot contain more than l lines of any of the N lmaxlmin i matrices.

We can safely replace the inner N lmaxlmin i matrices with their sub-matrices N lmaxlmin i l,c and get the result. ✷ As t increases all (v i,α t ), which are non-decreasing sequences, converge toward a finite or infinite limit. We let lim(i, α) = lim t→∞ (v i,α t ), s.t. lim(i, α) ∈ N ∪ {+∞}, ∀ τ i t , α.

Thus, if we denote U i , the limit of the line vector in U t (s) corresponding to trajectory τ i t when t tends to infinity, we have: • We show that for any pair of successive policies (δ old , δ) computed by the algorithm, we have: U δ l,c (s) ≥ lmaxlmin U δ old l,c (s), ∀s ∈ S.

U i =  
As a consequence, and since the set of matrices U l,c is finite, the algorithm converges.

To prove this, just notice that since δ(s) ← arg max lmax(lmin) a Q δ old l,c (s, a), U δ l,c (s) ≥ lmaxlmin Q δ old l,c (s, a), ∀a. Thus, U δ l,c (s) ≥ lmaxlmin Q δ old l,c (s, δ old (s)) = U δ old l,c (s).

• In a second step, we show that the fixed-points of Lmax(lmin)-BU -P I are also fixed points of Lmax(lmin)-BU -V I , which is enough to prove the correctness of the Lmax(lmin)-BU -P I algorithm (we have already shown the correctness of Lmax(lmin)-BU -V I ).

Let δ be a fixed-point of Lmax(lmin)-BU -P I . We have possibilistic MDP the number of stationary policies is bounded, so is the number of possible different preorderings over the set of bounded matrix utilities of policies in any state.

Thus, for any sequence ( t ) such that t+1 (strictly) refines t converges in a finite number of iterations. This is the case for any sequence t ≡ lmaxlmin,l t ,c t with strictly increasing sequences (c t ), (l t ). Proposition 9 results. ✷ Proof of Proposition 10. From Proposition 9, there exist a pair (l * , c * ) of finite positive integers, such that, ∀l > l * , c > c * , ∀δ, δ ′ , s, δ(s) lmaxlmin,l,c δ ′ (s) ⇔ δ(s) lmaxlmin,l * ,c * δ ′ (s).

Now, if we focus on the bounded iterations lmax(lmin) Value iteration algorithm, then for any E > 0, there obviously exist (l E , c E ) such that δ(s) lmaxlmin,E δ ′ (s) ⇔ δ(s) lmaxlmin,l E ,c E δ ′ (s).

It is enough to take l E as the maximum number of possible trajectories of length E for any policy and starting state, and to choose c E = 2E + 1, as the length of trajectories.

Note that (l E ) and (c E ) can be chosen as strictly increasing functions of E. Thus, for the above defined pair (l * , c * ), there exist E * such that, ∀E > E * , l E > l E * > l * and c E > c E * > c * .

Thanks to Proposition 9, we get that, ∀E > E * , δ(s) lmaxlmin,E δ ′ (s) ⇔ δ(s) lmaxlmin,l * ,c * δ ′ (s).

This means that the bounded iterations lmax(lmin) value iteration algorithm converges after a finite number of steps (E * , here). ✷

Fig. 1 .

 1 Fig. 1. The stationary MDP of Example 2.

Algorithm 1 :

 1 V I-M D P : Possibilistic (Optimistic) Value iteration.

  is the concatenation of the i-th line of U and the j-th line of N i . The composition of U × (N 1 , . . . , N a ) is done in O (n • m) operations, where n = 1≤i≤a n i and m = b + c. The matrix U (s), matrix of trajectories out of state s when making decision a, is typically the concatenation of the matrix U =

2

 2

Algorithm 3 : 2 e 6 repeat 7 e

 3267 Bounded iterations lmax(lmin)-value iteration (BI-VI).Data: A possibilistic MDP and maximum number of iterations EResult:The δ E strategy obtained after E iterations 1 begin ← 0; 3 foreach s ∈ S do U (s) ← ((µ(s))); 4 foreach s ∈ S, a ∈ A do 5 T U s,a ← T s,a × ((µ(s ′ )), s ′ ∈ succ(s, a)); ← e + 1; 8 foreach s ∈ S do 9 U old (s) = U (s); 10 Q * ← ((0)); 11 foreach a ∈ A do 12

7 foreach s ∈ S do 8 U 9 Q 10 foreach a ∈ A do 11 Future

 7891011 s) == U old (s) for each s; old (s) ← U (s); * ← ((0)); ← (U old (s ′ ), s ′ ∈ succ(s, a)); // Gather the matrices provided by the successors of s;

12

 12

  1 and l tends to b E . Let us now study the time complexity. The number of iterations is bounded by the size of the set of possible matrices of trajectories which is in O (|S| • |A| • E). One iteration of the algorithm requires composition, ordering and comparing operations on b matrices of size (l, c). Since the composition and comparison of matrices are linear operations, the complexity of one iteration in worst case is in b • (l • c) • log(l • c). Therefore, the complexity of the algorithm is in O

Algorithm 5 :begin 2 / 4 repeat 5 // Evaluation of δ 6 foreach 7 repeat 8 foreach s ∈ S do 9 U 13 δ old ← δ; 14 // Improvement of δ 15 foreach s ∈ S do 16 / 17 foreach a ∈ A do 18 Future,c 19 /

 5245678913141516171819 Lmax(lmin)-Bounded Utility Policy Iteration. Data: A possibilistic MDP, bounds (l, c) Result: A policy δ * optimal when l, c grows 1 / Arbitrary initialization of δ on S 3 foreach s ∈ S do δ(s) ← choose any a s ∈ A s ; s ∈ S do U (s) ← µ(s); old (s) ← U (s); 10 // Gather the matrices of the successors of s given δ 11 Future ← (U (s ′ ), s ′ ∈ succ(s, δ(s))); U (s) ← T U s,δ(s) × Future lmaxlmin l,c ; 12 until U (s) == U old (s) for each s; / Compute the utility of the strategy playing a (for each a), given what was chosen for the other states ← (U (s ′ ), s ′ ∈ succ(s, δ old (s))); Q (s, a) ← T U s,a × Future lmaxlmin l/ Update the choice of an action for S 20 δ(s) ← arg max lmax(lmin)

MDPs with 25 Fig. 2 .

 252 Fig. 2. Bounded utility lexicographic value iteration vs lexicographic value iteration.

20 )From ( 20 )

 2020 ) lmaxlmin ] lmaxlmin . Now, using Fact 1 again, in the other direction of the equality:(U ⊗ (N 1 , . . . , N a )) lmaxlmin = [(U 1 ⊗ (N 1 ) lmaxlmin ) lmaxlmin ⊕ (U 2 ⊗ (N 2 ) lmaxlmin ) lmaxlmin ⊕ ... ⊕ (U k ⊗ (N k ) lmaxlmin ) lmaxlmin ] lmaxlmin= U ⊗ ((N 1 ) lmaxlmin , . . . , (N a ) lmaxlmin ) lmaxlmin (, we have, of course, (U ⊗ (N 1 , . . . , N a )) lmaxlmin l,c = U ⊗ ((N 1 ) lmaxlmin , . . . , (N a ) lmaxlmin )

Future t+1 = 8 .

 t+18 (U t (s ′ ), s ′ ∈ succ(s, a)) = Future t , → Q t+1 (s, a) = [ T U s,a ⊗ Future t lmaxlmin ] l,c = [ T U s,a ⊗ Future t-1 lmaxlmin ] l,c = Q t (s, a).We deduce that, We prove the convergence in two steps:

  (s, a), ∀s.

Let us now set U t- 1 lProof of Proposition 9 .

 19 ,c = U δ l,c in the Lmax(lmin)-BU -V I algorithm, and let us compute U t l,c :U t l,c (s) = max lmax(lmin) a [(T U s,a × Future) lmaxlmin ] l,c , ∀s. But, Future = de f U t-1 l,c (s ′ ), s ′ ∈ succ(s, a) = U δ l,c (s ′ ), s ′ ∈ succ(s, a) = Future δ . (s) = max lmax(lmin) a [(T U s,a × Future δ ) lmaxlmin ] l,c = max lmax(lmin) a Q δ l,c (s, a), ∀s = U δ l,c (s), ∀s.Thus, U δ l,c (s) is a fixed-point of Lmax(lmin)-bounded Value Iteration. ✷ Note that Proposition 5 proves the right implication (⇒) for any l > l * , c > c * . Now, since for any

Data: A stationary MDP Result: A policy δ optimal for u opt 1 begin 2 foreach s

  ∈ S do u opt (s) ← µ(s);

	3	repeat
	4	foreach s ∈ S do
	5	u old (s) ← u opt (s);
	6	foreach a ∈ A do
	7	Q (s, a) ← min µ(s), max s ′ ∈S min{(π (s ′ |s, a), u opt (s ′ )} ;
	8	u opt (s) ← max a Q (s, a);
	9	δ(s) ← arg max a Q (s, a);
	10	until u opt (s) == u old (s) for each s;
	11	return δ;
	Algorithm 2: P I-M D P : Possibilistic (Optimistic) Policy iteration.

Data

: A stationary MDP Result: A policy δ optimal for u opt 1 begin 2 // Initialization of δ and u opt 3 foreach s ∈ S do 4 δ

  (s) ← choose any a s ∈ A s ;

	5	u opt (s) ← µ(s);

6 repeat 7 // Evaluation of δ until stabilization of u opt 8 repeat 9 foreach s ∈ S do 10 u old

  (s) ← u opt (s);

	11	u opt (s) ← min µ(s), max s ′ ∈S min{π (s ′ |s, δ(s)).u old (s ′ )} ;

12 until u opt == u old ; 13 // Improvement of δ 14 foreach s ∈ S do 15

  ← arg max a∈ A min µ(s), max s ′ ∈S min{π (s ′ |s, a).u opt (s ′ )}

		δ old (s) ← δ(s);
	16	δ(s)

; 17 until δ(s) == δ old (s) for each s; 18 // stabilization of δ 19 return δ;

Table 1

 1 Average CPU time (in seconds) and average number of iterations.

		Bounded utility policy iteration
	(l, c)	(2, 2)	(4, 4)	(6, 6)	(10, 10)
	CPU time (s)	0.029	0.042	0.064	0.091
	Average number of iterations	3.2	4.33	5.6	9.7
		Bounded utility value iteration
	(l, c)	(2, 2)	(4, 4)	(6, 6)	(10, 10)
	CPU time (s)	0.03	0.052	0.082	0.1
	Average number of iterations	6.75	9.25	16.11	20.2

  In bounded utility lexicographic value iteration, at each time step, U t (s) is composed of a set of trajectories τ i t = s i 0 , a i 0 , s i 1 , . . . , s i t , a i t , s i t+1 , which can be identified with the set of possibilities/utilities of each transition (s i t ′ , a i t ′ , s ′ i t ′ +1 ) s.t. t ≥ t ′ ≥ 0, these are obtained from { π i t ′ , u i t ′ } t ′ =0,t . Thus, τ i t has 2t elements. Let v i,α t count the number of times a level α ∈ V has been obtained by π i t ′ or u i t ′ during the trajectory τ i t . Statistics < v i,1 t , . . . , v

Proof of Proposition 7.

i,|V | t > can be maintained for every trajectory.

  Let us now consider U * l,c , the l × c matrix made from the l first (in leximax order) line vectors [U i ] 1,c . Thus, bounded utility lexicographic value iteration algorithm converges.Besides, we show now that if[U t (s) lmaxlmin ] l,c = [U t-1 (s) lmaxlmin ] l,c , thus, ∀ t ′ ≥ t, we have [U t ′ (s) lmaxlmin ] l,c = [U t (s) lmaxlmin ] l,c :Let us consider the following hypothesis:H : [U t (s) lmaxlmin ] l,c = [U t-1 (s) lmaxlmin ] l,c . H , let us calculate [U t+1 (s) lmaxlmin ] l,c :

					
		α1, . . . , α 1	, α 2 , . . . , α 2	, . . .	  .
		lim(i,1)		lim(i,2)
	Then, obviously,
	lim t→∞	U t (s) lmaxlmin	l,c	= U * l,c .
	Considering

Indeed, it just amounts to order and compare the matrices (of the sub-policies) using lmin(lmax) instead of lmax(lmin).


Y Kokar

K Rachedi

A Ourir

J De Rosny

D.-T Phan-Huy

J.-C Prévotet

M Hélard

Demo Abstract: Spatial modulation based transmission using a reconfigurable antenna

Keywords: 5G, spatial modulation, Internet of Things

This demonstration presents a spatial modulation based scheme between a transmitter connected to a compact reconfigurable antenna and a receiver connected to 4 omnidirectional antennas. The reconfigurable antenna used to perform spatial modulation is able to generate 8 uniformly distributed radiation patterns. First, a Radio Wave Display will show the 8 radiation patterns of the reconfigurable antenna. In a next step, the BER will be displayed after spatial demodulation at the receiver side to evaluate the communication performance.

I. INTRODUCTION

The fifth generation of mobile network (5G) will become the backbone of the Internet of Things (IoT). Among the different studied technologies for IoT, Spatial Modulation (SM) MIMO appears as a good candidate for a transmission from a connected object to an access point. Indeed, by taking benefit from spatial diversity, SM-MIMO provides a high data rate while leading to low complexity and low power connected objects.

SM-MIMO may transmit two distinct data bit streams per symbol. The first is transmitted trough a conventional modulation, while the second bit stream is sent by selecting one antenna among the N t antennas of the transmitter, at each symbol period. Each transmit antenna is thus associated to a bit sequence value of length log 2 (N t ).

Increasing N t leads to improve the data rate of the SM stream. Unfortunately, a large number of antennas cannot be easily implemented in small connected objects. To circumvent this issue, the use of a compact reconfigurable antenna has been proposed in [START_REF] Ourir | Compact reconfigurable antenna with radiation pattern diversity for spatial modulation[END_REF]. A reconfigurable antenna is capable of selecting one Radiation Pattern (RP) among N t available. Thus, each RP may now be associated to a different bits sequence.

In [START_REF] Serafimovski | Practical implementation of spatial modulation[END_REF], a SM-MIMO 2x2 testbed, which uses a RF chain per transmit antenna (2 RF in total), has been presented. In this demonstration, we present a SM-MIMO testbed with only one RF chain at the transmitter side. The unique RF chain feeds a reconfigurable antenna which is capable of generating 8 distinct RP.

II. TESTBED DESCRIPTION

As illustrated in Fig. 1, the proposed testbed is composed of two WARP v3 boards and a reconfigurable antenna. One

The authors would like to thank the SPATIAL MODULATION project funded by the French National Research Agency (ANR). A. The reconfigurable split ring antenna

fl th ij = | s (E ◊ i • E s |E i | 2
The integration is performe is presented on Fig.

fl th ij = | s (E ◊ i • E ◊ú j + s |E i | 2 d
The integration is performed o is presented on Fig. 8. It show The highest value is like 73% w The other values varie from 10

B. Eigenvalue of the decompos based on the 8 electric fields

The cornerstone of MIMO co diversity. Indeed, the dramati only due to this last. Spatial div appears in the MIMO Shanno way to asses the spatial dive compute the diversity measure system[6]. This analysis is bas the probability distribution of channel matrix obeys to a Naka easily show that the diversity

fl th ij = | s (E ◊ i • E s |E i |
The integration is perform is presented on Fig. 8.

It s The highest value is like 73

The other values varie from

B. Eigenvalue of the decom based on the 8 electric field

The cornerstone of MIM diversity. Indeed, the dra only due to this last. Spati appears in the MIMO Sha way to asses the spatial compute the diversity mea system[6]. This analysis is the probability distributio

A. Envelope corre

One way to eval formance consists coe cient ECC [4 of the antenna di ECC, the better w of uncorrelated rad the correlation co phase and the po Here, we assume t We compute the co j from the two com

E " and E ◊ in all of the ECC fl th ij is fl th ij = |
The integration is is presented on Fi The highest value The other values v

B. Eigenvalue of t based on the 8 elec

The cornerstone diversity. Indeed, only due to this las appears in the MI

fl th ij = | s (E ◊ i • s |E
The integration is perform is presented on Fig. 8. It The highest value is like 7

The other values varie fro

B. Eigenvalue of the deco based on the 8 electric fie

The cornerstone of MIM diversity. Indeed, the dr only due to this last. Spat appears in the MIMO Sh way to asses the spatia compute the diversity mea system[6]. This analysis i the probability distributi channel matrix obeys to a

fl th ij = | s (E ◊ i • s |E
The integration is perfor is presented on Fig. 8.

I The highest value is like

The other values varie fr

B. Eigenvalue of the dec based on the 8 electric fi

The cornerstone of MI diversity. Indeed, the d only due to this last. Spa appears in the MIMO S way to asses the spatia compute the diversity me system[6]. This analysis the probability distribut channel matrix obeys to The presented reference antenna is not well matched. We propose to take advantage of coupling e ects between resonators in order to simultaneously enhance the matching of the antenna and modify the radiation pattern.

B. Re-configurable Antenna

One can take advantage of the couplings between the double SRR and parasitic loops to tune the radiation pattern at a given frequency. Here, the study has been

State D1 D2 D3 D4 1 1 0 0 0 1-2 1 1 0 0 2 0 1 0 0 2-3 0 1 1 0 3 0 0 1 0 3-4 0 0 1 1 4 0 0 0 1 4-1 1 0 0 1

TABLE I: Configuration of the Pin diodes

The four parasitic loops around the reference antenna with the 4 pin diodes are shown on Fig. 5. The main element of the reconfigurable SRR antenna shown in Fig. 2 is a double closed rings. In order to deliver different RP, the double closed rings is surrounded by four parasitic loops whose resonant frequency is controlled by a pin diode (in blue) placed in the gap of the loop. By controlling the modes of the 4 pin diodes (ON or OFF), the SRR antenna is able to steer in 8 uniformly distributed directions as depicted in Fig. 2. Each RP is associated to 3 bits values which will be transmitted by the SM. The RP mapping is done such that only one bit differs for 2 adjacent RP.

B. Baseband processing

As shown in Fig. 3, the structure of the transmitted frame is composed of 4 parts which correspond to the 4 phases required for SM based transmission. The first phase is to AGC seq.

Sync. seq. Pilot Symbols Data Symbols Fig. 3. Structure of transmitted frame determine, thanks to a transmitted Automatic Gain Control (AGC) sequence, the appropriate gain at the receiver which suits for all SRR antenna RP. The next phase is to accurately evaluate the beginning of the pilot and data symbols. To that end, a synchronization sequence is inserted in the transmitted frame before the pilot symbols and a cross-correlation is performed at the receiver between the received signal and the synchronization sequence. Pilot symbols are then used in order to estimate the channels between each SRR antenna RP and the receiver antennas. Data symbols are generated trough a conventional modulation, and SM is performed by selecting the RP (via GPIO pins) corresponding to the 3 SM bits value that have to be transmit on the current sent symbol. At the receiver side, spatial demodulation consists in detecting, for each received symbol, which RP has sent the current symbol in order to retrieve the SM bits. To that end, we use the maximum likelihood detector as described in [START_REF] Serafimovski | Practical implementation of spatial modulation[END_REF].

III. DEMONSTRATION

In this demonstration, we will present a transmit SM based wireless transmission. The setup of our demonstration is depicted in Fig. 4. The carrier frequency and the bandwidth The demonstration is conducted in two steps. In a first step, we show to participants how it is possible to visually distinguish the 8 different RP of the SRR antenna. For this purpose, we use the Radio Wave Display (RWD) [3] as a real time receiver which allows to display the radiation of a transmitting antenna that is placed in front of it. The RWD comprises 400 (20 by 20) power sensors operating between 50 MHz and 3 GHz. The power measured by each sensor is then converted into a gradient of colors following a thermal color scale. Fig. 5 provides pictures of the RWD for the 8 RP of the SRR antenna corresponding to the bits transmitted using SM. We can clearly observe that the 8 patterns of the SRR antenna are visually distinct. The presented reference antenna is not well matched. We propose to take advantage of coupling e ects between resonators in order to simultaneously enhance the matching of the antenna and modify the radiation pattern.

B. Re-configurable Antenna

One can take advantage of the couplings between the double SRR and parasitic loops to tune the radiation pattern at a given frequency. Here, the study has been done at 2.45 GHz. The basic idea is to use resonators which the resonant frequency can be driven by a pin diode. The pin diode is placed in the gap of the parasitic loops.

The Pin diode diode has two modes (ON/OFF). According to the voltage bias applied, the equivalent circuit of the pin diode changes. One can thus change here the resonant frequency of the loop connected to the diode. Figs. 4(a) and (b) present the equivalent circuit of the Pin diode for both modes (ON/OFF).

State D1 D2 D3 D4 1 1 0 0 0 1-2 1 1 0 0 2 0 1 0 0 2-3 0 1 1 0 3 0 0 1 0 3-4 0 0 1 1 4 0 0 0 1 4-1 1 0 0 1

TABLE I: Configuration of the Pin diodes

The four parasitic loops around the reference antenna with the 4 are Fig. 5. II. The values of the gain at 2.45 GHz oscillate around 3dB (up to 3.62 dB). The antenna presents a good radiation e ciency (around -0.2 dB) for the 8 states. The radiation e ciency has been optimized by choosing an appropriate substrate NELCO (low loss). The next section deals with the performance of the antenna.

IV. Performance of the antenna

The SM-MIMO e ciency is based on the ability of the transmitter to generate distinguishable radiation patterns. The more decorrelated they are each other, the better would be the robustness of the radio link. These di erent In a second step of the demonstration, we will perform a transmission of 900 data bits using SM between the transmitter board (acting as the connected object) and the receiver board (representing the access point). After the demodulation of the received frame, the Bit Error Rate (BER) of the transmission is displayed on the workstation. Participants are then be able to observe the effect of changing the SRR antenna and/or receiving antennas positions (few centimetres to few meters) on the quality of the communication (BER). A demonstration video is available online in [4].

Fig. 1 .

 1 Fig. 1. Testbed description

Fig. 8 :

 8 Fig. 8: Envelope correlation between the 8 states of the

Fig. 8 :

 8 Fig. 8: Envelope correlation coe between the 8 states of the reco we also analyze the eigenvalues correlation matrix (or covarian A. Envelope correlation coe c One way to evaluate the spat formance consists in estimatin coe cient ECC [4]. It gives a of the antenna diversity perfo ECC, the better would be the of uncorrelated radiation patte the correlation coe cients dep phase and the polarization of Here, we assume two di erent We compute the correlation fac j from the two component far E " and E ◊ in all the direction of the ECC fl th ij is given by

Fig. 6 :

 6 Fig. 6: Reflection Coe cient S 11 of the tunable SRR antenna

Fig. 7 :

 7 Fig. 7: 8 Radiation Patterns in gain at2.45 GHz at 2.45 GHz State S11 (dB) Gain (dB) Rad. E (dB) 1 -8.96 3.03 -0.23 1-2 -21.65 3.62 -0.29 2 -8.10 3.06 -0.22 2-3 -13.51 3.22 -0.26 3 -15.96 2.87 -0.25 3-4 -9.54 3.5 -0.26 4 -15.67 2.85 -0.27 4-1 -11.27 3.25 -0.30

Fig. 8 :

 8 Fig. 8: Envelope correlatio between the 8 states of the

Fig. 6 :

 6 Fig. 6: Reflection Coe cient S 11 of the tunable SRR antenna

Fig. 8 :

 8 Fig. 8: Envelope co between the 8 state

Fig. 6 :

 6 Fig. 6: Reflection Coe cient S 11 of the tunable SRR antenna

Fig. 7 :

 7 Fig. 7: 8 Radiation Patterns in gain at 2.45 GHz at 2.45 GHz

Fig. 8 :

 8 Fig. 8: Envelope correlatio between the 8 states of th

Fig. 6 :

 6 Fig. 6: Reflection Coe cient S 11 of the tunable SRR antenna

Fig. 7 :

 7 Fig. 7: 8 Radiation Patterns in gain at2.45 GHz at 2.45 GHz State S11 (dB) Gain (dB) Rad. E (dB) 1 -8.96 3.03 -0.23 1-2 -21.65 3.62 -0.29 2 -8.10 3.06 -0.22 2-3 -13.51 3.22 -0.26 3 -15.96 2.87 -0.25 3-4 -9.54 3.5 -0.26 4 -15.67 2.85 -0.27 4-1 -11.27 3.25 -0.30

Fig. 8 :

 8 Fig. 8: Envelope cor between the 8 states

Fig. 7 :

 7 Fig. 7: 8 Radiation Patterns in gain at2.45 GHz at 2.45 GHz State S11 (dB) Gain (dB) Rad. E (dB) 1 -8.96 3.03 -0.23 1-2 -21.65 3.62 -0.29 2 -8.10 3.06 -0.22 2-3 -13.51 3.22 -0.26 3 -15.96 2.87 -0.25 3-4 -9.54 3.5 -0.26 4 -15.67 2.85 -0.27 4-1 -11.27 3.25 -0.30

Fig. 8 :Fig. 6 :

 86 Fig. 8: Envelope c between the 8 stat

Fig. 7 :

 7 Fig. 7: 8 Radiation Patterns in gain at 2.45 GHz at 2.45 GHz

Fig. 8 :

 8 Fig. 8: Envelope correlat between the 8 states of th

Fig. 2 :

 2 Fig. 2: Reflection Coe cient S11 of the reference antenna

Fig. 3 :

 3 Fig. 3: Radiation Pattern at 2.58 GHz of the reference antenna

Fig. 5 :Fig. 2 .

 52 Fig. 5: Tunable Split Ring Antenna with the 4 Pin diodesIII. Spatial DiversityWe take benefit of 8 di erent states of the reconfigurable antenna. Thus 8 di erent radiation patterns at 2.45 GHz are obtained. Table I recaps the 8 configurations according to the states of the pin diodes D1,D2, D3 and D4 shown on the Fig.5. The computed reflection coe cient S11 for all the configurations provided by the antenna are plotted on the Fig.6. A relative good impedance matching is obtained for all the states because the reflection coe cient is bellow -10dB. The 8 radiation patterns at 2.45 GHz are presented on the Fig.7. It clearly appears that the reconfigurable antenna is able to steer in 8 uniformly distributed directions. Some fundamental parameters of the antenna (S11 parameter, gain and radiation e ciency) are listed on TableII. The values of the gain at 2.45 GHz oscillate around 3dB (up to 3.62 dB). The antenna presents a good radiation e ciency (around -0.2 dB) for the 8 states. The radiation e ciency has been optimized by choosing an

  Fig. 4. Demonstration setup

Fig. 2 :Fig. 4 :

 24 Fig. 2: Reflection Coe cient S11 of the reference antenna

Fig. 5 :

 5 Fig. 5: Tunable Split Ring Antenna with the 4 Pin diodesIII. Spatial DiversityWe take benefit of 8 di erent states of the reconfigurable antenna. Thus 8 di erent radiation patterns at 2.45 GHz are obtained. TableIrecaps the 8 configurations according to the states of the pin diodes D1,D2, D3 and D4 shown on the Fig.5. The computed reflection coe cient S11 for all the configurations provided by the antenna are plotted on the Fig.6. A relative good impedance matching is obtained for all the states because the reflection coe cient is bellow -10dB. The 8 radiation patterns at 2.45 GHz are presented on the Fig.7. It clearly appears that the reconfigurable antenna is able to steer in 8 uniformly distributed directions. Some fundamental parameters of the antenna (S11 parameter, gain and radiation e ciency) are listed on TableII. The values of the gain at 2.45 GHz oscillate around 3dB (up to 3.62 dB). The antenna presents a good radiation e ciency (around -0.2 dB) for the 8 states. The radiation e ciency has been optimized by choosing an appropriate substrate NELCO (low loss). The next section deals with the performance of the antenna.

Fig. 5 .

 5 Fig. 5. Visualisation of the SRR antenna radiation patterns on the RWD

TABLE II :

 II Parameters

of the tunable SRR antenna at 2.45 GHz radiation patterns are then decoded by the receiver as digital symbols in the IQ constellation.

First to assess the spatial diversity, we compute the

: Reflection Coe cient S 11 of the tunable SRR antenna Fig. 7: 8 Radiation Patterns in gain at 2.45 GHz at 2.45 GHz State S11 (dB) Gain (dB) Rad. E (dB) 1

	Fig. 6-8.96 1-2 -21.65 2 -8.10 2-3 -13.51 3 -15.96 3-4 -9.54 4 -15.67 4-1 -11.27	3.03 3.62 3.06 3.22 2.87 3.5 2.85 3.25	-0.23 -0.29 -0.22 -0.26 -0.25 -0.26 -0.27 -0.30	The cornerstone of MIMO diversity. Indeed, the dram easily show that the dive channel matrix obeys to a N the probability distribution system[6]. This analysis is compute the diversity meas way to asses the spatial appears in the MIMO Sha only due to this last. Spatia

8. It s The highest value is like 73 The other values varie from B. Eigenvalue of the decom based on the 8 electric field

TABLE II :

 II Parameters

of the tunable SRR antenna at 2.45 GHz radiation patterns are then decoded by the receiver as digital symbols in the IQ constellation.

First to assess the spatial diversity, we compute the

TABLE II :

 II Parameters

of the tunable SRR antenna at 2.45

  in gain at 2.45 GHz at 2.45 GHz

	State S11 (dB) 1 -8.96 1-2 -21.65 2 -8.10 2-3 -13.51 3 -15.96 3-4 -9.54 4 -15.67 4-1 -11.27	Gain (dB) 3.03 3.62 3.06 3.22 2.87 3.5 2.85 3.25	Rad. E (dB) -0.23 -0.29 -0.22 -0.26 -0.25 -0.26 -0.27 -0.30

TABLE II :

 II Parameters

of the tunable SRR antenna at 2.45 GHz radiation patterns are then decoded by the receiver as digital symbols in the IQ constellation.

TABLE II :

 II Parameters

of the tunable SRR antenna at 2.45 GHz

TABLE II :

 II Parameters

of the tunable SRR antenna at 2.45 GHz

  in gain at 2.45 GHz at 2.45 GHz

	State S11 (dB) 1 -8.96 1-2 -21.65 2 -8.10 2-3 -13.51 3 -15.96 3-4 -9.54 4 -15.67 4-1 -11.27	Gain (dB) 3.03 3.62 3.06 3.22 2.87 3.5 2.85 3.25	Rad. E (dB) -0.23 -0.29 -0.22 -0.26 -0.25 -0.26 -0.27 -0.30

TABLE II :

 II Parameters

of the tunable SRR antenna at 2.45 GHz radiation patterns are then decoded by the receiver as digital symbols in the IQ constellation.