Wafa, Ismail, Rami, Sleh, Manel... François

Keywords: Décision séquentielle, théorie de possibilités, critères lexicographiques, arbres de décision, processus décisionnels de Markov Sequential decision theory, possibility theory, lexicographic criteria, decision trees, Markov decision processes

À la fin de la rédaction de cette thèse, je suis convaincue que la thèse est loin d'être un travail solitaire. En effet, je n'aurais jamais pu réaliser ce travail sans le soutien d'un grand nombre de personnes dont la bonne humeur et l'intérêt manifestés à l'égard de ma thèse m'ont permis de progresser dans cette phase délicate.

Je voudrais tout d'abord remercier grandement mes directrices de thèse, Nahla Ben Amor et Hélène Fargier, pour toutes leurs aides. Je suis ravie d'avoir travaillé en leur compagnie car outre leurs appuis scientifiques, elles ont toujours été là pour me soutenir et me conseiller au cours de l'élaboration de cette thèse. Leur contact a d'ailleurs été très enrichissant tant au niveau humain qu'au niveau professionnel. Il peut être assuré de mon sincère respect et de ma profonde gratitude. Je remercie également Régis Sabaddin avec qui j'ai eu la chance de pouvoir travailler. Sa rigueur, sa capacité d'analyse des problèmes et ses très nombreuses connaissances m'ont permis de progresser et de répondre à plusieurs de mes préoccupations. Les conseils et le soutien reçus étaient essentiels à la réussite du projet.

Je tiens à remercier Jérome Lang et Olivier Spanjaard qui m'ont fait l'honneur d'être rapporteurs de ma thèse. Leurs remarques m'ont permis de voir mon travail sous un autre angle. J'adresse aussi mes remerciements à Didier Dubois et Zied Elouadi pour avoir accepté de participer à mon jury de thèse et pour leurs apports scientifiques et l'honneur qu'ils me font d'être dans mon jury thèse.

Je remercie également l'ensemble des membres de l'IRIT et du LARODEC pour leur soutien logistique et moral ainsi que pour la très bonne ambiance que j'ai toujours trouvée. Je remercie particulièrement : Fayçal, Maroua, Pierre-

Résumé

Ce travail contribue à la théorie de la décision possibiliste et plus précisément à la prise de décision séquentielle dans le cadre de la théorie des possibilités, à la fois au niveau théorique et pratique. Bien qu'attrayante pour sa capacité à résoudre les problèmes de décision qualitatifs, la théorie de la décision possibiliste souffre d'un inconvénient important: les critères d'utilité qualitative possibilistes comparent les actions avec les opérateurs min et max, ce qui entraîne un effet de noyade. Pour surmonter ce manque de pouvoir décisionnel, plusieurs raffinements ont été proposés dans la littérature. Les raffinements lexicographiques sont particulièrement intéressants puisqu'ils permettent de bénéficier de l'arrière-plan de l'utilité espérée, tout en restant «qualitatifs». Cependant, ces raffinements ne sont définis que pour les problèmes de décision non séquentiels.

Dans cette thèse, nous présentons des résultats sur l'extension des raffinements lexicographiques aux problèmes de décision séquentiels, en particulier aux Arbres de Décision et aux Processus Décisionnels de Markov possibilistes. Dans un premier temps, nous présentons des relations de préférence lexicographiques optimistes et pessimistes entre les politiques avec et sans utilités intermédiaires, qui raffinent respectivement les utilités possibilistes optimistes et pessimistes. Nous prouvons que les critères proposés satisfont le principe de l'efficacité de Pareto ainsi que la propriété de monotonie stricte. Cette dernière garantit la possibilité d'application d'un algorithme de programmation dynamique pour calculer des politiques optimales. Nous étudions tout d'abord l'optimisation lexicographique des politiques dans les Arbres de Décision possibilistes et les Processus Décisionnels de Markov à horizon fini. Nous fournissons des adaptations de l'algorithme de programmation dynamique qui calculent une politique optimale en temps polynomial. Ces algorithmes sont basés sur la comparaison lexicographique des matrices de trajectoires associées aux sous-politiques. Ce travail algorithmique est complété par une étude expérimentale qui montre la faisabilité et l'intérêt de l'approche proposée. Ensuite, nous prouvons que les critères lexicographiques bénéficient toujours d'une fondation en termes d'utilité espérée, et qu'ils peuvent être capturés par des utilités espérées infinitésimales.

La dernière partie de notre travail est consacrée à l'optimisation des politiques dans les Processus Décisionnels de Markov (éventuellement infinis) stationnaires. Nous proposons un algorithme d'itération de la valeur pour le calcul des politiques optimales lexicographiques. De plus, nous étendons ces résultats au cas de l'horizon infini. La taille des matrices augmentant exponentiellement (ce qui est particulièrement problématique dans le cas de l'horizon infini), nous proposons un algorithme d'approximation qui se limite à la partie la plus intéressante de chaque matrice de trajectoires, à savoir les premières lignes et colonnes. Enfin, nous rapportons des résultats expérimentaux qui prouvent l'efficacité des algorithmes basés sur la troncation des matrices.

INTRODUCTION General introduction

In classical decision-making under uncertainty frameworks, one has to select an action among several alternatives according to Expected utility [START_REF] Neumann | [END_REF]Morgenstern, 1944, Savage, 1954], considering that uncertainty is modeled via a probability distribution.

When the decisions are spread over time, a decision maker can choose between several punctual actions with incapacity to predict, with certainty, the outcome event. This problem of sequential decision-making under uncertainty exists in multiple domains such as automatic control, robot control, medical diagnosis, in-time stock management, modeling games etc. Several representation formalisms can be used for sequential decision problems, such as influence diagrams [START_REF] Howard | Influence diagrams[END_REF], Markov decision processes [Bellman, 1957b] and decision trees [Raiffa, 1968] etc. Despite its success, the expected utility framework presents some limitations concerning the representation of total ignorance and the handling of qualitative information. It is appropriate when all probabilities are available or can be easily elicited from the decision-maker, which is not always possible. Several generalizations or alternatives to classical probability theory have been suggested in order to deal with imperfect information, including imprecise probabilities [Walley, 1991], evidence theory [Shafer, 1976] and possibility theory [Zadeh, 1978]. In the present work, we are interested in possibility theory that offers a natural and simple framework to handle qualitative information, and especially in possibilistic qualitative decision theory [START_REF] Giang | Two axiomatic approaches to decision making using possibility theory[END_REF], Weng, 2005[START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF], Godo and Zapico, 2001, Dubois et al., 1998a, Dubois and Prade, 1995, Godo and Zapico, 2001]. The development of possibilistic decision theory has led to the proposition of a series of possibilistic decision criteria, and in particular: optimistic and pessimistic possibilistic qualitative criteria (the qualitative counterparts of expected utility) [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF], possibilistic likely dominance [START_REF] Dubois | Qualitative decision theory with preference relations and comparative uncertainty: An axiomatic approach[END_REF], binary possibilistic utility [START_REF] Giang | A comparison of axiomatic approaches to qualitative decision making using possibility theory[END_REF] and possibilistic Choquet integrals [Rebille, 2006, Dubois andRico, 2016a].

Possibilistic (qualitative) decision theory is relevant, among other fields, for applications to sequential decision-making under uncertainty, where a suitable policy (i.e. a set of actions) is to be found w.r.t. a qualitative decision criterion, starting from a qualitative description of the initial world, of the available actions, of their uncertain effects and of the goal to reach (see e.g. [START_REF] Bauters | Anytime algorithms for solving possibilistic MDPs and hybridMDPs[END_REF], Ben Amor et al., 2014, Drougard et al., 2014, Drougard et al., 2013, Sabbadin, 2001, Sabbadin et al., 1998]). It is important to note that, in compact sequential decision models, like Markov decision processes and influence diagrams, the set of potential policies is combinatorial and it may grow exponentially. The computation of an optimal policy for a given representation and a given decision criterion is an algorithmic issue. In this thesis, we are interested to the optimization of the possibilistic counterparts of decision trees and Markov decision processes, which assume that the uncertain effects of actions can be represented by possibility distributions and that utilities are qualitative.

Even though appealing for its ability to handle qualitative problems, possibilistic decision theory suffers from an important drawback: the lack of discrimination power of its decision criteria. As many of possibilistic decision criteria, optimistic and pessimistic qualitative utilities, compare acts, and policies in sequential decision problems, through min and max operators, which leads to a drowning effect: plausible enough bad or good consequences may blur the comparison between acts that would otherwise be clearly differentiable. As a consequence, it appears that these criteria do not respect the Pareto efficiency and the sure thing principle.

To overcome the lack of decision power of possibility theory, several refinements of possibilistic decision criteria have been proposed for the non-sequential case decision problems [START_REF] Dubois | Advances in qualitative decision theory: Refined rankings[END_REF], Giang and Shenoy, 2001, Fargier and Sabbadin, 2003, Fargier and Sabbadin, 2005, Weng, 2005]. In particular, [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF] have proposed lexicographic refinements of possibilistic qualitative utilities that are appealing since they allow to benefit from the Expected Utility background, while remaining "qualitative". However, the latter is limited to non-sequential decision problems, and cannot take into account the fact that the drowning effect can also appear due to the reduction of compound possibilistic policies into simple possibility distributions on the consequences.

The aim of this thesis is to study and solve the problem of drowning effect in sequential decision problems, in particular in possibilistic decision trees and possibilistic Markov decision processes. We propose to extend the lexicographic refinements of qualitative utilities to sequential problems-thus providing lexicographic possibilistic decision criteria that compare full policies (and not simply their reductions). This thesis is decomposed into two main parts:

The first part offers necessary background on sequential decision-making under uncertainty in various aspects:

1. Chapter 1 recalls the expected utility decision model and introduces the basic concepts relative to decision theory. We present possibility theory and we detail optimistic and pessimistic utilities as well as the shortcoming of these criteria. Then we evoke their refine-ments in non-sequential decision-making: first, we present a brief overview of approaches that try to remedy the drowning effect problem, then EU-based refinements and lexicographic refinements are developed.

2. Chapter 2 is devoted to sequential decision-making models. We especially focus on possibilistic decision trees and possibilistic Markov decision processes. These graphical models are presented in the possibilistic (qualitative) version and their solving algorithms w.r.t. qualitative criteria are described.

The second part of the thesis represents our main contributions. It is structured as follows:

1. Chapter 3 presents the drowning effect in possibilistic decision trees, finite-horizon Markov decision processes and also in stationary Markov decision processes. We then define lexicographic refinements of possibilistic decision criteria on policies without intermediate utilities and with intermediate utilities. Besides, we study the properties of these criteria. Indeed, we prove that these criteria satisfy Pareto efficiency as well as strict monotonicity.

2. Chapter 4 extends the lexicographic comparisons to possibilistic decision trees and possibilistic finite-horizon Markov decision processes. We propose an algorithmic solution, based on Dynamic Programming approach, for each model. Moreover, we provide an experimental study to validate and discuss the proposed algorithms.

3. The primary aim of chapter 5 is to show how to relate the theory of expected utility with that of possibilistic qualitative utilities by refinement relations in the case of sequential decision-making (obviously when considering finite-horizon possibilistic decision trees and possibilistic finite-horizon). We propose a special form of expected utility (based on bigstepped probability distributions) as a refinement of possibilistic qualitative utilities, using a transformation function of the scale. Then we establish formal results of equivalence between lexicographic refinements of qualitative utilities and these expected utility criteria proposed. Thus we prove that it is possible to construct stochastic models inducing an order on policies that refines the order induced on the same policies in the given possibilistic model. We define a dynamic programming algorithm, for calculating optimal policies with respect to the so-obtained criteria with an experimental study in the end.

4. Finally, Chapter 6 is devoted to stationary Markov decision processes in which the set of states, the available actions and the transition functions are assumed not do depend on the stage (time step) of the problem. First, we propose a lexicographic variant of the value iteration algorithm for the finite-horizon case, with an approximation algorithm in order to decrease the complexity of the fist. We present then an experimental comparative analysis of these algorithms. In addition, we provide a value iteration algorithm to compute an approximate lexicographic optimal policy when the horizon is infinite.

The main results of this thesis are published in [Ben Amor et al., 2015[START_REF] Amor | Lexicographic refinements in possibilistic markov decision processes : The finite horizon case[END_REF], Ben Amor et al., 2016a, Ben Amor et al., 2017].

CHAPTRE 1

One-stage Possibilistic Decision-Making

Introduction

Decision theory is a multidisciplinary domain that concerns economy, psychology, social sciences, operational research and artificial intelligence. Many important problems involve decision-making under uncertainty, that is choosing an act (also called decision or action) or, in sequential decisionmaking, a policy among many different available alternatives, considering decision maker's limited knowledge about states of nature (states of the world) and his preferences.

In real world several types of uncertainty should be considered. Most available decision models refer to probability theory for the representation of uncertainty [START_REF] Neumann | [END_REF]Morgenstern, 1944, Savage, 1954]. Despite its success, probability theory is appropriate when all numerical information is available or can be easily elicited. When information about uncertainty cannot be quantified in a probabilistic way, several non-classical theories of uncertainty can be considered in order to deal with imperfect, ordinal information namely, fuzzy sets theory [Zadeh, 1965], evidence theory [Shafer, 1976] and possibility theory [Zadeh, 1978, Dubois andPrade, 1988] etc. In this work, we will focus on qualitative decision-making, especially on possibility theory suitable for handling uncertain and imprecise knowledge.

This chapter provides the theoretical background of possibilistic decision theory: Section 1.2 presents classical probabilistic decision theory. Section 1.3 reviews the possibilistic decision theory, in particular, it introduces the basics of possibility theory and details the most commonly used possibilistic decision criteria: optimistic and pessimistic qualitative utilities. Section 1.4 exposes the drowning effect problem in these latter criteria. Finally, Section 1.5 defines refinements of qualitative utilities proposed for the one-step decision problems.

Decision-making under probabilistic uncertainty

Decision-making under uncertainty is primarily the identification and the choice of some alternatives, that most commonly are expressed implicitly, based on preferences of the decision maker. Thus, solving a decision problem amounts to providing an optimal act with respect to the available knowledge about the environment and the decision maker preferences relative to possible consequences of different alternatives.

In this Section, we present the probabilistic decision theory, considered as the standard quantitative decision model, and also the Expected Utility (EU) criterion first introduced by Bernoulli [Bernoulli, 1738], and then axiomatized by Von Neumann and Morgenstern [START_REF] Neumann | Theory of games and economic behavior[END_REF] and Savage [Savage, 1954]. We first detail subjective expected utility and Savage's axiomatic system, then we present the expected utility criterion in the Von Neumann and Morgenstern's framework and its axiomatization.

Subjective Expected Utility: Savage's approach

Expected utility theory based on subjective probability has been well developed and axiomatized by Savage [Savage, 1954]. In Savage's framework, subjective probability is used to model uncertainty. Formally, a decision problem under uncertainty using the Savage approach is defined by a 4-tuple (S, X, A, ), where:

• S is the set of states of nature,

• X is the set of consequences, formally, the preference between two consequences x and y ∈ X is denoted by x y. It means that "x is at least as good as y" for the decision maker.

• A = X S is the set of possible acts, an act is thus a function f : S → X,

• is a preference relation on A satisfying two main crucial properties:

-Completeness: ∀f, g ∈ A either f g or g f .

-Transitivity: If f is at least as good as g and g is at least as good as q, then f is at least as good as q.

If (f g and g q) then (f q). f g denotes the preference between two acts f and g. It means that "f is at least as good as g" for the decision maker. denotes the asymmetric part of and ∼ its symmetrical part:

• The strict preference relation is defined by f g if and only if f g and g f and it means that" f is strictly preferred to g ".

• The indifference relation ∼ is defined by f ∼ g if and only if f g and g f and it means that " f and g are indifferently preferred ".

Considering probability theory, the information pertaining to the state of nature and the preferences on X are encoded as follows: uncertainty is represented by a probability distribution p over S and the preferences on X are encoded by a utility function µ : X → U .

Acts are then ranked (for any two acts, either one is better than the other, or the two are equivalent) by Subjective Expected Utility, denoted by SEU [Savage, 1954]: Definition 1.1. Given a probability distribution p over S and a utility function µ on X, the SEU of an act h is defined by: SEU (h) = s∈S p(s) . µ(h(s)).

(1.1)

Example 1.1. Suppose that you are thinking about taking out fire insurance on your home. Perhaps it costs $100 to take out insurance on a house worth $100,000, and you ask: Is it worth it? Let us formalize this decision problem: Let S = {Severe f ire, M inor f ire, N o f ire} be the set of states of nature s.t.:

• Severe f ire is the state in which your house catches on a severe fire,

• M inor f ire is the state in which your house catches on a negligible fire,

• N o f ire is the state in which your house doesn't catch on fire.

Using fire occurrence data, we have p(Severe f ire) = 0.2, p(M inor f ire) = 0.3 and p(N o F ire) = 0.5. Consider the two acts Insurance (take an insurance) and N o insurance (do not take an insurance) and the consequences given in Table 1.1.

Acts/States

Severe f ire M inor f ire N ot f ire Insurance

No house+($100) House+($100-$50) House+(-$100)

N oinsurance

No house+($0) House+(-$50) House+($0) The utility value associated to each consequence is defined as follows:

• µ(N o house + $100) = 3, µ(House + ($100 -$50))=6, µ(House + (-$100))=7, • µ(N o house + $0)=0, µ(House + (-$50))=5, µ(House + $0)=10.
Using Equation 1.1, we have:

• SEU (Insurance) = (0.2 × 3) + (0.3 × 6) + (0.5 × 7) = 5.9 and

• SEU (N o insurance) = (0.2 × 0) + (0.3 × 5) + (0.5 × 10) = 6.5.
So, the act N o insurance is preferred to Insurance.

Savage has provided an axiomatic system that gives necessary conditions that should be satisfied by a preference relation between acts to be represented by an EU [Savage, 1954]. First, we define f Ah as the act which gives the same consequence f on A ⊆ S and as h on S \ A. A constant act is defined by: Definition 1.2. (Constant act) A constant act f x ∈ A provides the same consequence x ∈ X, whatever the state of nature i.e.:

∀s ∈ S, f x (s) = x.

Savage's axiomatic system is based on the five following axioms [Savage, 1954]:

Axiom. (SAV 1: Complete Pre-order) The preference relation is complete and transitive.

Axiom. (SAV 2: Sure Thing Principle (STP)) For all acts f, g, h, h ∈ A and for every event

E ⊆ S: f Eh gEh iff f Eh gEh .
Axiom. (SAV 3: Conditioning over constant acts) Thus, for any not null event E ⊆ S, and any constant acts f x , g y ∈ A it holds that:

∀E ⊆ S, f x g y iff ∀h ∈ A, f x Eh g y Eh.
Axiom. (SAV 4: Projection from acts over events) For any consequences x, y, x , y ∈ X, for any constant acts f x , g y , f x , g y ∈ A. If x y and x y , then ∀E, D ⊆ S we have:

f x Eg y f x Dg y iff f x Eg y f x Dg y .
Axiom. (SAV 5: Non triviality) ∃ f, g ∈ A, such that f g.

The principle axiom of Savage is the Sure Thing Principle (SAV2), it is interpreted by the fact that if an act is preferred to another when an event E is occurred then it will still preferred whatever the act in the case of complementary event.

If a preference relation satisfies axioms SAV 1 to SAV 5, as well as two technical axioms of continuity and monotonicity, then this preference relation can be represented by an expected utility from the set of act to the reals: Theorem 1.1. If the preference relation satisfies Savage axioms then it exists a utility function µ: X → R and a probability distribution p deduced from the preference relation between acts such that :

∀f, g ∈ A, f g ⇔ SEU (L) ≥ SEU (L ). (1.2)

Expected Utility: Von Neumann and Morgenstern's approach

In the present Section, we present the expected utility model in the Von Neumann and Morgenstern's framework [START_REF] Neumann | Theory of games and economic behavior[END_REF], the most known framework to deal with decision-making problems under risk. In this framework, an act is represented by a probability distribution over the set of possible outcomes. It is called a simple probabilistic lottery and it is denoted by L = λ 1 /x 1 , . . . , λ n /x n , where λ i = p(x i ) is the probability that the decision leads to outcome x i . A utility µ function maps each outcome x i to a utility value in a totally ordered numerical set U . This function models the attractiveness of each outcome for the decision maker. Thus, a simple probabilistic lottery can be seen also as a probability distribution over the set of utilities denoted by L = λ 1 /µ 1 , . . . , λ n /µ n .

A probabilistic compound lottery denoted by λ 1 /L 1 , . . . , λ m /L m is a probability distribution over a set of lotteries where λ i is the probability to obtain lottery L i .

Formally, a decision-making problem under risk can be represented using:

• X the set of consequences,

• L the set of probabilistic lotteries, where each lottery L i is a probability distribution p over the set of consequences X,

• µ : X → U the utility function, a mapping from the set of consequences X to a numerical scale.

Note that, it is possible to transform a Savage act into a lottery, since we can calculate the probability p of getting each utility level from the probabilities of states:

∀µ i ∈ U, p(µ i ) = s∈S,µ(f (s))=µ i p(s).
We get then a probability distribution over the set of utilities, i.e. simple probabilistic lottery.

Solving a decision problem under risk amounts to evaluating alternatives and choosing an optimal one among them. The computation of the expected utility of a lottery L is performed as follows:

Definition 1.3. Given a probabilistic lottery L = λ 1 /x 1 , . . . , λ n /x n and a utility function u, the expected utility of L (denoted by EU (L)) is computed by:

EU (L) = x i ∈X λ i . µ(x i ).
(1.3)

Example 1.2. Consider the same decision problem as in Example 1.1. The two acts Insurance and N o insurance can be represented, respectively, using the two following probabilistic lotteries L = 0.2/3, 0.3/6, 0.5/7 and L = 0.2/0, 0.3/5, 0.5/10 .

Using Equation 1.3, we have the same values as in Example 1.1 i.e. EU (Insurance) = 5.9 and EU (N o insurance) = 6.5.

Von Neumann and Morgenstern have provided an axiomatic system to characterize a preference relation between probabilistic lotteries [START_REF] Neumann | Theory of games and economic behavior[END_REF]:

Axiom. (V N M 1: Weak order) The preference relation is complete and transitive.

Axiom. (V N M 2: Continuity) Let L, L and L be three probabilistic lotteries, if L is at least good as L and L is at least good as L then there is a probability p for which the decision maker will be indifferent between lottery L and the compound lottery in which L comes with probability p, and L with probability (1 -p). Formally:

L L L ⇒ ∃ p ∈ ]0, 1[ s.t. p/L, (1 -p)/L ∼ L .
Axiom. (V N M 3: Independence) Let L, L and L be three probabilistic lotteries, we have:

L L ⇔ ∃ p ∈]0, 1] s.t. p/L, (1 -p)/L p/L , (1 -p)/L .
The fundamental axiom of the (objective) expected utility model is the independence axiom. It can be interpreted as follows: If the decision maker prefers L to L and he has to choose between p/L, (1 -p)/L and p/L , (1 -p)/L then he will prefer the compound lottery p/L, (1p)/L to p/L , (1 -p)/L whatever the probability of the event that happens.

Thus, if the preference relation satisfying completeness, transitivity, continuity and independence axioms, then it can be represented by an expected utility. This is the meaning of the following representation theorem: Theorem 1.2. If the preference relation satisfies V N M axioms, then it is exists a utility function µ: X → R over the set of lotteries L such that:

∀L, L , L L ⇔ EU (L) ≥ EU (L ).
(1.4)

Beyond Expected Utility decision theories

Despite its success, the Expected Utility theory has some limitations such as:

• The behavior of total ignorance is represented by equiprobability, so it formalizes randomness instead of ignorance.

• EU is not able to capture certain behaviors that appear rational such as those shown in the paradoxes of Allais [Allais, 1953] and Ellsberg [Ellsberg, 1961]: In 1953, Allais paradox has shown that the independence axiom of the VNM's system is violated [Allais, 1953] and in 1961, Ellsberg has shown the behavior of people in the face of ignorance is in contradiction with the Sure Thing Principle of SEU.

• EU-theory supposes that all the numerical information is available or that it can be elicited from the decision maker. In some situations, decision makers are unable to express their uncertainty and preferences numerically for all comparisons.

In order to overcome EU-based model limitations, some extensions of EU, that use quantitative representation of uncertainty, have been developed. Most of them are based on the most well-known criterion Choquet integral [Choquet, 1954] which is based on generalized measure of uncertainty. Quiggin has developed the Rank-Dependent Utility criterion (RDU) (which is a particular case of Choquet integral) that have received an axiomatic justification [Quiggin, 1982].

When uncertainty and/or preferences are ordinal in nature, one can use alternatives to probability theory. So, considering qualitative preferences but remaining within a probabilistic quantification of uncertainty has led to quantile-based approaches [START_REF] Montes | Decision making with imprecise probabilities and utilities by means of statistical preference and stochastic dominance[END_REF], Szörényi et al., 2015]. In several cases, especially when the representation of both uncertainty and preferences by additive quantitative values is inappropriate, purely ordinal approaches have been considered to handle qualitative uncertainty and preferences. Qualitative decision models have been introduced with emergence of the rule of Sugeno integrals [Sugeno, 1974], that is considered as an ordinal counterpart of Choquet integrals.

Possibilistic decision theory

Possibility theory [Zadeh, 1978, Dubois and[START_REF] Dubois | [END_REF] is the fundamental purely ordinal uncertainty theory. For many years, it has received much interest in the Artificial Intelligence community [Pearl, 1993, Dubois and Prade, 1995, Dubois et al., 1998a[START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF], Godo and Zapico, 2001, Giang and Shenoy, 2005, Weng, 2005].

In this Section, we are interested in qualitative decision theory by using possibility theory for the representation of uncertainty. The development of possibilistic decision theory has led to the proposition of several possibilistic decision criteria, in particular qualitative utilities : optimistic and pessimistic utilities. These criteria are used to identify a preference relation on simple possibilistic lotteries, associated to acts, defined in what follows.

Possibility theory

Possibility theory, issued from Fuzzy Sets theory, offers a natural and flexible model to represent and handle uncertain information, especially qualitative uncertainty and total ignorance. It was introduced by Zadeh [Zadeh, 1978] and further developed by Dubois and Prade [START_REF] Dubois | Possibility Theory: An Approach to Computerized Processing of Uncertainty[END_REF].

The basic component of possibility theory is the notion of possibility distribution. It is a representation of the knowledge of an agent regarding the state of the world. A possibility distribution is denoted by π and it is a mapping from the universe of discourse S to a finite ordinal scale V = {α 0 = 0 V < α 1 < . . . < α l = 1 V }, we denote the function by: π : S → V . For each state s ∈ S, π(s) = 1 means that realization of the state s is totally possible and π(s) = 0 means that s is an impossible state. π(s) > π(s ) expresses that s is preferred to s (or is more plausible). It is generally assumed that there exist at least one state s which is totally possible i.e. π(s) = 1: π is said then to be normalized.

The possibilistic scale V can be interpreted in two manners:

• Quantitative manner, or numerical, using possibility degrees i.e. the values of the possibility distribution make sense in the possibilistic scale.

• Qualitative manner, or ordinal, using total pre-order on the universe of discourse. This order can be represented by numerical values which have no sense but which express only the order.

In the possibilistic framework, extreme forms of partial 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 states in S are possible).

In possiblistic theory, for any used scale V , there are two essential measures:

• Possibility measure: Π(A) = max ω∈A π(ω). Π(A) is the possibility degree evaluating at which level the event A is consistent with the knowledge represented by π.

• Necessity measure:

N (A) = 1 -Π( Ā) = 1 -sup ω /
∈A π(ω). N(A) expresses the necessity degree evaluating at which level the event A is certainly implied by the knowledge.

Example 1.3. Let us consider the possibility distribution π which shows the opinion of a doctor concerning the diagnosis of a patient. The universe of discourse related to this problem is a set of three diseases and a healthy case: S = {d1, d2, d3, h}.

π(d1) = 0.5, π(d2) = 1, π(d3) = 0.7, π(h) = 0.
Note that this distribution is normalized since max(0.5, 1, 0.7, 0) = 1.

If we consider the event A: "The patient suffers from d1 or d3", then we have: Π(A) = max(0.5, 0.7) = 0.7 and N (A) = 1 -max(1, 0) = 0.0.

Possibilistic lotteries

Dubois et al. [Dubois andPrade, 1995, Dubois et al., 1998a] have proposed a possibilistic counterpart of VNM's notion of lottery to represent a one stage decision problem. In the possibilistic framework, an act can be represented by a possibility distribution on V = {u 1 , . . . , u p }, also called a possibilistic lottery, and denoted by λ 1 /u 1 , . . . , λ p /u p i.e. λ i = π(u i ) is the possibility that the decision leads to an outcome of utility u i .

A possibilistic compound lottery λ 1 /L 1 , . . . , λ r /L r is a normalized possibility distribution over the set of lotteries. The possibility π i,j of getting an utility degree u j ∈ V from one of its sub-lotteries L i depends on the possibility λ i of getting L i and on the conditional possibility

λ i j = Π(u j | L i ) of getting u j from L i i.e. Π i,j = min(λ j , λ i j ).
Thus, [Dubois andPrade, 1995,Dubois et al., 1998a] have proposed to reduce a compound lottery (over a set of simple lotteries) λ 1 /L 1 , ..., λ r /L r into an equivalent simple lottery. Formally we have:

Reduction( λ 1 /L 1 , . . . , λ r /L r ) = max j=1..r (min(λ j 1 , λ j ))/u 1 , . . . , max j=1..r
(min(λ j p , λ j ))/u p .

(1.5)

Example 1.4. Let L 1 = 1/0.5, 0.7/0.3 and L 2 = 1/0.5, 0.6/0.3 be two simple possibilistic lotteries, and let L = 1/L 1 , 0.8/L 2 be th compound lottery represented in Figure 1.1 (a). The reduction of L into a simple lottery L , presented by (b) in Figure 1.1, can be calculated using Equation 1.5 as follows:

• L (0.5) = max(min(1, 1), min(0.8, 0.6)) = 1 and

• L (0.3) = max(min(1, 0.7), min(0.8, 1)) = 0.8, So, L = Reduction (L ) = 1/0.5, 0.8/0.3 . Note that, the reduction of a simple lottery is the simple lottery itself. Furthermore, the reduction of a compound lottery is a polynomial operation, because min and max are also polynomial operations.

The development of possibility theory has led to the emergence of several possibilistic criteria depending on the nature of the utility scale. These criteria allow to compare simple lotteries associated to acts as detailed in what follows.

Possibilistic decision criteria

Possibilistic decision criteria can be gathered into three classes:

• Utility and possibility scales are commensurate and purely ordinal: contains possibilistic qualitative criteria such as optimistic utility (denoted by u opt ) and pessimistic utility (denoted by u pes ) [Dubois andPrade, 1995, Dubois et al., 1999] that are qualitative counterparts of the EU criterion, besides possibilistic binary utilities (denoted by P U ) [START_REF] Giang | A comparison of axiomatic approaches to qualitative decision making using possibility theory[END_REF].

• Utility and possibility scales are commensurate and utilities are quantitative: in this class we have possibility-based Choquet integrals (denoted by Ch Π ) and Necessity-based Choquet integrals (denoted by Ch N ) [Rebille, 2006, Ben Amor et al., 2010[START_REF] Dubois | Axiomatisation of discrete fuzzy integrals with respect to possibility and necessity measures[END_REF]].

• Utility and possibility scales are not commensurate: we have possibility-based likely dominance (denoted by LΠ) and Necessity-based likely dominance (denoted by LN ) [Fargier andPerny, 1999, Dubois et al., 2003].

In this Thesis, we are interested in the first class, especially in the well-known qualitative utilities: optimistic and pessimistic utilities that are qualitative counterparts of the EU criterion.

Possibilistic qualitative utilities

Under the assumption that the utility scale and the possibility scale are commensurate and purely ordinal, Dubois and Prade [Dubois andPrade, 1995,Dubois et al., 1999] have proposed pessimistic and optimistic criteria. These two qualitative criteria are actually particular cases of a more general criterion based on the Sugeno integral [Sugeno, 1974].

Pessimistic utility

The pessimistic criterion was originally defined by Whalen [Whalen, 1984] and it generalizes the Wald criterion [Wald, 1971]. It supposes that the decision maker is happy when bad consequences are hardly plausible i.e. considers the bad and plausible consequences. It estimates to what extent it is certain (i.e. necessary according to measure N) that L reaches a good utility.

Definition 1.4. Let L = λ 1 /u 1 , . . . , λ n /u n be a possibilistic lottery, the pessimistic utility of L, denoted by u pes is computed as follows:

u pes (L) = min i=1..n max(u i , n(λ i )).
(1.6)

where n is an order reversing function (e.g. n(λ i ) = 1 -λ i ).

Example 1.5. Let L = 1/0.2, 0.7/0.5, 0.4/0.6 and L = 1/0.8, 0.3/0.7, 0.5/0.9 be two possibilistic lotteries. Using Equation 1.6 we have:

• u pes (L) = min(max(0.2, 0), max(0.5, 0.3), max(0.6, 0.6)) = 0.2

• u pes (L ) = min(max(0.8, 0), max(0.7, 0.7), max(0.9, 0.5)) = 0.7 which means that L upes L.

Dubois and Prade have proposed an adaptation of qualitative utilities to evaluate acts in the style of Savage [START_REF] Dubois | Qualitative decision theory with sugeno integrals[END_REF]. Using this framework, the definition of the pessimistic decision rule is as follows:

Definition 1.5. Given a possibilistic distribution π over 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 s i ∈S max(u(f (s i )), 1 -π(s i )).
(1.7) Therefore, we can compare two acts f and gon the basis of their pessimistic utilities:

f upes g ⇔ u pes (f ) ≥ u pes (g).

Optimistic utility

The optimistic criterion was originally proposed by Yager [Yager, 1979, Yager, 1997] and it captures the optimistic behavior of the decision maker that makes at least one of the good consequences highly plausible. So, this criterion estimates to what extent it is possible that a possibilistic lottery reaches a good utility.

Definition 1.6. Let L = λ 1 /x 1 , . . . , λ n /x n be a possibilistic lottery, the optimistic utility of L, denoted by u opt is computed as follows:

u opt (L) = max i=1..n min(u i , λ i ).
(1.8)

Example 1.6. Let L = 1/0.2, 0.7/0.5, 0.4/0.6 and L = 1/0.8, 0.3/0.7, 0.5/0.9 be two possibilistic lotteries. Using Equation 1.8 we have:

• u opt (L) = max(min(0.2,1),min(0.5,0.7),min(0.4,0.6)) = 0.5.

• u opt (L ) = max(min(1,0.8),min(0.3,0.7),min(0.5,0.9)) = 0.8. which means that L uopt L.

Similar to its pessimistic counterpart, this criterion was also defined in Savage framework to choose among acts rather than lotteries. Its definition is as follows:

Definition 1.7. Given a possibilistic distribution π over a set 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 s i ∈S min(u(f (s i )), π(s i )).
(1.9)

The pessimistic and optimistic utilities represent particular cases of Sugeno integrals, a more general criterion, in the context of possibility theory [Sugeno, 1974, Grabisch et al., 2000, Dubois et al., 2001a, Marichal, 2001]:

S γ,u (L) = max λ∈[0,1] min(λ, γ(F λ )).
(1.10)

where

F λ = {s i ∈ S, u(f (s i ))
≥ λ}, is a set of preferred states for act f. γ captures knowledge (necessity or possibility measures) and reflects the decision maker attitude toward uncertainty.

u opt is recovered when γ is the possibility measure Π and u pes is recovered when γ corresponds to necessity measure N.

Limitations of possibilistic qualitative utilities

Qualitative decision criteria in general, and qualitative utilities in particular, suffer from a lack of discrimination called the "drowning effect" due to the use of idempotent operations-max and min. This shortcoming is explicit when considering the Savage's formalism. Indeed, two acts f and g can be considered as indifferent even if they give an identical and extreme (either good or bad) consequence in some plausible state. As a consequence the principle of Pareto efficiency also called strict Pareto dominance: ∀ s, u(f (s)) ≥ u(g(s)) and ∃ s * , π(s * ) > 0 and u(f (s * )) > u(g(s * )) does not imply that f is strictly preferred to g (i.e. g f ), as shown in the following example borrowed from [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF]:

Example 1.7. Let S = {s 1 , s 2 } and V = {0, 0.1, 0.2, 0.3, 0.4, 1}. Let f and g be two acts whose utility 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 : Table 1.2: Drowning effect

s 1 s 2 u(f (s)) 0.3 0.4 u(g(s)) 0.3 0.1 π 1 0.2
Thus u opt (f ) = u opt (g) = 0.3 (and u pes (f ) = u pes (g) = 0.3) although f strictly dominates g in the state s 2 and that the two acts are equivalent in s 1 . This is due to the fact that the good performance of the two acts on the most plausible state (min(u(f (s 1 )), π(s 1 )) = min(3, 5) = min(u(g(s 1 )), π(s 1 )) = 3) blurs the comparison.

Moreover, it has been shown that optimistic and pessimistic qualitative utilities do not fully satisfy the fundamental property of decision criteria: the Sure Thing Principle (STP) (axiom. SAV2) that insures that identical consequences do not influence the relative preference between two acts. In fact, it has been shown that qualitative utilities respect the STP only if there is no uncertainty at all [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF]. Note that when is complete and transitive, the principle of Pareto efficiency is a direct consequence of the Sure thing principle.

Refinements of possibilistic qualitative utilities

Contrary to the EU approach, possibilistic qualitative preference relations u opt and u pes suffer from a lack of decisiveness, since they do not satisfy the STP. In this section, we present some approaches that try to remedy this problem.

Refining qualitative decision criteria

As a solution to qualitative criteria's drawbacks, it seems to be interesting to stay in the pure qualitative framework and escape the drowning effect by satisfying the STP. For this purpose, many papers have proposed some tools to cope with the drowning effect of possibilistic decision criteria. The idea is to propose discriminating criteria i.e. refinements of the possibilistic criteria. Formally: Definition 1.8. (Refinement) Let and be any two complete preference relations on the set of acts A. We say that refines if and only if ∀ f, g ∈ A, f g ⇒ f g, where and are the strict parts of and respectively.

Definition 1.9. A relation is said to be more specific than a relation if and only if refines and = .

Thus, a refinement agrees with when provides a strict preference. So, the two preference relations are perfectly compatible. Obviously, when refines , either they provide the same decisions, or the former is more specific.

The idea of refining qualitative possibilistic criteria has first been proposed by [START_REF] Dubois | Advances in qualitative decision theory: Refined rankings[END_REF]: when two acts result indifferent w.r.t. a possibilistic criterion, the ties are broken by sequentially considering the ranking w.r.t. another qualitative criteria. Hence, the refined ordering is obtained by sequentially applying additional qualitative criteria to the original one. For instance, when the pessimistic utility criterion is indifferent, it is possible to decide based on the optimistic utility ordering or a T-norm aggregation. This refinement allows to evaluate acts based on a lexicographic ordering of a set of different qualitative criteria, instead of an order induced by one criterion. In fact, [START_REF] Dubois | Advances in qualitative decision theory: Refined rankings[END_REF]]'s approach is purely qualitative, since it uses min and max but it does not obey the STP.

Then, in [START_REF] Giang | A comparison of axiomatic approaches to qualitative decision making using possibility theory[END_REF], the authors have improved the discrimination power of possibilistic utilities by proposing Binary possibilistic utility in order to compare special kind of qualitative lotteries: totally ordered set of possibility measures on a two element set {0, 1} containing the utilities (i.e. the scale of utilities) of the best and the worst consequences. Such possibility distribution represents a qualitative lottery. Note that the pessimistic and optimistic utilities are special cases of this bipolar criterion. The decision rule of [START_REF] Giang | A comparison of axiomatic approaches to qualitative decision making using possibility theory[END_REF] can capture the lexicographic use of the optimistic and pessimistic utilities when the pessimistic one cannot discriminate and vice-versa [START_REF] Godo | Lexicographic refinements in the context of possibilistic decision theory[END_REF]. Besides, the proposed criterion satisfies the STP but it has a major shortcoming: Consider two acts with contrasted consequences, i.e. respectively a bad or neutral one, and a good or neutral one, and that the two acts have maximal possibility. It appears that the binary possibilistic utility may be indifferent because of the drowning effect of min and max: neutral consequences (possibility and utility equal to 1) hide all other consequences and make all such lotteries equivalent. A refinement of binary possibilistic utility has been proposed in [Weng, 2005]. In this work indeed, two similar possibilities of the same lottery are merged, using new operators, in a lexicographical ordered sequence of values instead of one possibility degree that we get after the reduction. The resulting criterion thus suffers from a drowning effect since it deletes all doubles of branches in each lottery.

In [Lehmann, 2002], Lehmann adds some qualitative notions to the classical expected utility framework. He has axiomatized a refined criterion, based on the qualitative maximin criterion of [Wald, 1971], in the VNM style: it breaks ties between equivalent worst states by considering their respective likelihoods (the probabilities). This criterion takes the form of an expected utility criterion with standard probabilities and qualitative infinitesimal utilities. In this model, two situations can be considered: nonstandard (lexicographic) probabilities with standard utilities or standard probabilities with nonstandard (lexicographic) utilities. Note that in this model the lexicographic characteristic is used only on one of the two dimensions (either the probability level, or the utility level).

In addition, [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF] proposed refinements of monotonic utilities (they are based on Sugeno integral): when comparing two acts, every state in which both acts give identical results being neglected (by forcing the two acts to take a fixed value α). This refinement obeys the STP but it claims to forget the transitivity of the indifference relation.

In order to overcome the lack of decisiveness of the possibilistic optimistic and pessimistic utilities, Fargier and Sabbadin show that possibilistic utilities can be refined by an EU criterion [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF]. Choosing an EU-model is advantageous, since EU satisfies the STP and the principle of Pareto dominance. The authors show that these EU-based Refinements of qualitative utilities can be understood as a generalization of the leximin and leximax criteria. We have chosen these refinements since they ensure optimal discrimination in accordance with Pareto efficiency, especially they respect the STP. In the sequel of this Chapter, we detail these latter refinements that constitute the basis of our contribution.

Expected utility-based refinements of qualitative utilities

The EU-based refinements of qualitative utilities criteria proposed in [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF] satisfy the Sure Thing Principle -and thus escape the drowning effect. They are based on the use of a probability distribution p and a utility function µ such that the obtained preference relation EU,p,µ refines the preference relation that corresponds to the decision rule u opt when considering a possibility distribution π and a utility function u, denoted in this Section OP T,π,u . The idea is to construct the expected utility criterion by a transformation function χ : V → [0, 1] which transforms each possibility distribution π into a probability distribution p: Definition 1.10. (Probabilistic transformation of an ordinal scale) A transformation of the scale V is a strictly increasing function χ : V → [0, 1] such that χ(0 V ) = 0; χ is a probabilistic transformation with respect to the possibility distribution π if s∈S χ(π(s)) = 1.

Note that χ(0 V ) = 0 means that the impossibility of an event is expressed by a null probability. However the most plausible events (possibility degrees of 1 V , do not receive probability degree 1, since they are mutually exclusive. Note that χ is a unique function for transforming the scale V , thus both p and µ will be built upon this transformation. This is due to the fact that preference and uncertainty levels are commensurate and belong to the same scale. In the refined decision model, no undesirable arbitrary information is introduced by χ, so, p and µ are as close as possible to the original information about π and u: transformations of V is said to be "unbiased". Formally:

Definition 1.11. (Unbiased transformation of a scale) χ is unbiased iff ∀ α, α ∈ V, α ≥ α ⇔ χ(α) ≥ χ(α ).
This property ensures that π and p = χ • π, the transformation of the distribution π using χ, (resp. u and µ = χ • u) are ordinarily equivalent.

From χ, it is possible to define a decision model of the expected utility type, transformed from the optimistic one S, X, A, EU,χ•π,χ•u , by exhibiting a sufficient condition on the χ function (named H) so that the obtained preference relation refines the optimistic possibilistic preference relation:

H : ∀α, α ∈ V such that α > α : χ(α) 2 > |S|. χ(1 V ).χ(α ).
Then formally, EU,χ•π,χ•u refines OP T,π,u whenever χ satisfies H.

If χ respects H, the probability distribution p = χ • π obtained by transforming π is a big-step probability [Snow, 1999,Benferhat et al., 1999], i.e verifying: ∀s ∈ S, p(s) > s ,p(s)>p(s ) p(s ).

Note that the condition H concerns only the scale V and the size of the state space and not the distributions π or utilities u, hence, p and µ will be built using the transformation function of the scale. If S, X, A, OP T,π,u ranks an optimistic possibilistic model, all expected utility type preference relations defined from χ satisfying H are equivalent.

Example 1.8. Let us return to Example 1.7 and write χ * : V = (α 0 = 5 > ... > α k = 0) the probabilistic transformation defined by: χ * (0

) = 0; χ * (α i ) = v N 2 i+1 , i = 0, k -1; where v = 1 i=0,k-1 n i N 2 i+1 , N = |S| and n i = |{s ∈ S, π(s) = i}|. In Example 1.7, N = 2 and L = {5, 4, 3, 2, 1, 0}. χ * (V ) is the series v N 2 , v N 4 , v N 8 , v N 16 , v N 32 , 0; where v = 1 1 N 2 + 1 N 16
.

So:

• EU (f ) = χ * (5).χ * (3) + χ * (4).χ * (2) = v 2 N 10 + v 2 N 20 , • EU (g) = χ * (5).χ * (3) + χ * (2).χ * (1) = v 2 N 10 + v 2 N 48 . Hence, f EU,χ * •π,χ * •u g
In the sequel of this Section, χ * will denote the transformation function χ

* (α i ) = v N 2 i+1 , i = 0, k -1 obtained with v = 1 i=0,k-1 n i N 2 i+1
. Fargier et Sabbadin have shown that χ * is not a unique generator for the expected utilities: there may exist other unbiased and specific functions, for instance χ * * , that attach different numbers to states i.e. (χ

* * • π = χ * • π) or to consequences (χ * * • u = χ * • u).
The two obtained models are ordinally equivalent i.e. they make the same decisions and rank acts in the same way. The following theorem presents a summary for optimistic transformation:

Theorem 1.3. (Optimistic transformation) For any qualitative possibilistic model, there exists a probabilistic transformation χ * of V such that:

• EU,χ * •π,χ * •u is an unbiased, optimistic refinement of OP T,π,u . • If EU,p,µ is an unbiased and optimistic refinement OP T,π,u then EU,p,µ = EU,χ * •π,χ * •u .
It has been shown that an EU-based refinement of the same type (but somewhat more complex to express) could be obtained in the case of the pessimistic utility criterion, since OP T,π,u and P ES,π,u are dual relations. It is possible to use the transformation χ * (that allows to get probability degrees) coupled with a transformation function ψ * to get the utilities s.

t. ψ * (α) = χ * (1 V ) -χ * (n(α)).
This lead to the following pessimistic counterpart of Theorem 1.3: Theorem 1.4. (Pessimistic transformation) For any qualitative possibilistic model, there exists at least one pair of transformations (χ * , ψ * ) of V satisfying H such that:

• EU,χ * •π i ,ψ * •u is an unbiased refinement of P ES,π,u .
• If EU,p,µ is an unbiased and pessimistic refinement pes,π,u then EU,p,µ is equivalent to

EU,χ * •π i ,ψ * •u .

Lexicographic refinements of qualitative utilities

The possibilistic qualitative utilities can be refined using the leximin and leximax orderings proposed by [Moulin, 1988] to compare vectors [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF]. In fact, the preference relation leximin (resp. leximax) has been proposed as refinement relation of min (resp. max), as well as discrimin order [START_REF] Dubois | Refinements of the maximin approach to decision-making in fuzzy environment[END_REF], Cayrol et al., 2014]

defined below: Let f denotes a vector of N elements of V i.e. f ∈ V N . ∀i ∈ 1..N , f i denotes the i th element of f .
Definition 1.12. To compare two vectors u, v ∈ V N (two vectors of N elements of V ) using discrimin order, we first delete all pairs (u i , v j ) from u and v s.t.

u i = v i . let D be the set of indices of elements not deleted. Then, u discrimin v iff min i∈D u i > min i∈D v i .
Hence, leximax denoted lmin (resp. leximax denoted lmax ) allows to escape the lack of decisive power of min and discrimin orderings (resp. max order): Definition 1.13. (Leximax, Leximin) Let us consider u, v ∈ V N (vectors of N elements of V ), and let ∀i ∈ 1..N , u i (resp. v i ) denotes the i th element of u (resp. v). The leximax and the leximin relations on u and v denoted ≥ lmax and ≥ lmin , respectively are defined as follows:

u lmax v ⇔ (∀j, u (j) = v (j) ) or (∃ i s.t. ∀ j < i, u (j) = v (j) and u (j) > v (j) ), u lmin v ⇔ (∀j, u (j) = v (j) ) or (∃ i s.t. ∀ j > i, u (j) = v (j) and u (j) > v (j) ).
where for any w ∈

V N , w (k) is the k th biggest element of w (i.e. w (1) ≥ ... ≥ w (N ) ).
Indeed, the leximax (resp. leximin) comparison consists in ordering both vectors in increasing (resp. decreasing) order and then lexicographically comparing them element by element. Moreover, both relations escape the drowning effect and are very efficient: the only pair of ties is vectors that are identical up to a permutation of their elements.

Example 1.9. Let u = (3, 2, 6) and v = (2, 2, 6).

u lmax v since u (1) = v (1) = 6 and u (2) = 3 > v (2) = 2. u lmin v since u (3) = v (3) = 2 and u (2) = 3 > v (2) = 2.
Then, when S is finite, the comparison of acts can indeed be seen as a comparison of vectors of pairs of elements of V using 2 dimensions (V M ) N , instead of simple vectors in (V N ). Hence, an act can be represented by a matrix with N lines of pairs, s.t. N is the number of states, and M = 2 columns (one for possibility degree and one for the corresponding utility):

Definition 1.14. The representative matrix of any act f ∈ A is:

f = ((π 1 , u 1 ), ..., (π i , u i ), ..., (π N , u N )),
where π i corresponds to π(s i ) and u i to u(f (s i )).

Example 1.10. Let us return to Example 1.7. The representative matrices of f and g are:

F = ((1, 0.3), (0.2, 0.4)) and G = ((1, 0.3), (0.2, 0.1)).
Therefore, [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF] proposed an extension of the lexicographic relations to acts using a complete pre-order ¤ on lines of V 2 instead of the classical relation on V . So, to compare two matrices representing two acts it is sufficient to order the lines of each matrix according to ¤ and to apply then any of the two previous leximax and leximin procedures:

First, let F denotes a N × M matrix of elements of V i.e. F ∈ (V M ) N (s.t. M ≥ 2). ∀i ∈ 1..M ; ∀j ∈ 1..N , f ij denotes an element (or coefficient) of F in line i and column j. Definition 1.15. (Leximax(¤); Leximin(¤)) Let ¤ be a complete pre-order on V M , is its strict part and ∼ = is its symmetric part. Let F, G
be two matrices of (V M ) N , the leximax and leximin relations on F and G denoted lmax(¤) and lmin(¤) , respectively, are defined as follows:

• F lmax(¤) G ⇔ (∀j, f (¤,j) ∼ = g (¤,j) ) or (∃ i s.t. ∀ j < i, f (¤,j) = g (¤,j) and f (¤,i) g (¤,i) ) • F lmin(¤) G ⇔ (∀j, f (¤,j) ∼ = g (¤,j) ) or (∃ i s.t. ∀ j > i, f (¤,j) = g (¤,j) and f (¤,i) g (¤,i) )
where ∀i ∈ 1, .., N , f (¤,i) (resp. g (¤,i) ) is the i th biggest line of F (resp. G) according to ¤.

When ¤ = lmin , the comparison consists in first ordering the elements of each line in increasing order w.r.t lmin , then in ordering the lines in decreasing order (w.r.t. lmax ). It is then enough to lexicographically compare the two new matrices. This preference relation, denoted lmax(lmin) , is a refinement of max(min) and also OP T,π,u .

Example 1.11. Let us consider Example 1.10. We can compare the representative matrices of f (F = ((1, 0.3), (0.2, 0.4))) and g (G = ((1, 0.3), (0.2, 0.1))) using lmax(lmin) as follows: We have (1, 0.3) ∼ = lmin (1, 0.3) and (0.4, 0.2) lmin (0.2, 0.1) so f max(min) g.

For pessimistic utility, Fargier et Sabbadin have proposed a lexicographic refinement lmin(lmax)

to the π-reverse matrix. More precisely, given a matrix F , it π-reverse matrix is denoted n F such that: n F = ((n(π(s 1 )), u(s 1 )), ..., (n(π(s N )), u(s N ))). So, refining u pes leads to the application of leximin(leximax) comparison to π-reverse matrix. However, refining u opt leads to leximax(leximin) comparison directly to the representative vectors.

Finally, they have proved that the ordinal lexicographic refinements are equivalent to probabilistic EU-based refinements defined in Section 1.5.2, More formally: Theorem 1.5. For any possibilistic model, it holds that:

• EU,χ * •π,χ * •u ≡ lmax(lmin) • EU,χ * •π,ψ * •u ≡ lmin(lmax)
where χ * and ψ * are two transformation functions as shown in Section 1.5.2.

Hence, these lexicographic refinements obey to the Sure Thing Principle.

In this thesis, we aim to extend these efficient refinements (leximax(leximin) and leximin(leximax)) to sequential decision-making problems, presented in the next Chapter.

Summary

In this Chapter, we have presented an overview of probabilistic decision model that is well developed and axiomatized. This framework is appropriate when all numerical data are available or can be elicited from the decision maker, which is not always the case. Possibilistic decision theory offers a flexible and simple framework to represent qualitative uncertainty. We especially detailed main decision criteria based on possibility theory namely optimistic and pessimistic qualitative utilities. These two possibilistic criteria suffer from the drowning effect problem and fail to satisfy the principle of Pareto efficiency, in contrast to the classical numerical criterion-expected utility. [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF] show that possibilistic utilities can be refined by an expected utility criterion. Choosing an EU-model is advantageous, since it both leads to an EU refinement of the original rule that overcomes the lack of decisiveness of the possibilistic criteria, and it satisfies the Sure thing principle and the principle of Pareto dominance. These refinements are equivalent to lexicographic procedures in the one stage procedures described in [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF].

In next chapter, we will present the foundation of sequential decision problems in possibilistic decision trees and possibilistic Markov decision process where the decision maker should choose a sequence of decisions instead of one decision.

CHAPTRE 2

Possibilistic sequential decision-making models

Introduction

In the first chapter, we have been investigating non-sequential decision problems. In real world problems, the decision maker is often facing a succession of actions to be taken over time, i.e. sequential decision problems. In these problems a suitable policy is to be found, that associates a decision to each state of the world. Many graphical models have been proposed to represent such problems, such as influence diagrams [START_REF] Howard | Influence diagrams[END_REF], Markov decision processes [Bellman, 1957b] and decision trees [Raiffa, 1968].

In this work, we are interested in the formalism of decision trees and Markov decision processes since they allow an explicit representation of a sequential decision problem.

In classical sequential decision-making models uncertainty is stochastic and the satisfaction of the decision maker is expressed by a numerical, additive utility function [Raiffa, 1968, Puterman, 1994]. In fact, considering ordinal preferences but remaining within a probabilistic quantification of uncertainty in sequential decision-making has led to quantile-based approaches [START_REF] Gilbert | Optimizing quantiles in preferencebased markov decision processes[END_REF], to the use of reference points [Weng, 2011] or to approaches by pairwise comparison [START_REF] Yue | The k-armed dueling bandits problem[END_REF]. In this thesis, we are interested in the main purely ordinal decision graphical models: Possibilistic sequential decision models (e.g. see [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF], Sabbadin, 1999, Garcia and Sabbadin, 2006, Drougard et al., 2013, Ben Amor et al., 2014, Drougard et al., 2014, Bauters et al., 2016]). This chapter is organized as follows: Section 2.2 formally defines possibilistic decision trees and reviews existing algorithms to find optimal policies with a reasonable complexity. Section 2.3 gives an overview on possibilistic Markov decision processes and then details the optimization of these graphical models w.r.t. possibilistic optimistic and pessimistic utilities i.e. how to find an optimal policy.

Possibilistic decision trees (ΠDT s)

Decision trees (DT s) provide an explicit modeling of sequential decision problems by representing each possible scenario by a path from the root to the leaves of the tree [Raiffa, 1968]. In this Section, we study the optimization problem in possibilistic decision trees, denoted ΠDT s. where we aim to find an optimal policy w.r.t. a decision criterion: optimistic or pessimistic utilities shown in the previous Chapter.

Definition

A DT is composed of a graphical component and a numerical one as detailed below. The graphical component of a DT is a labelled graph DT = (N , E), where N = N D ∪ N C ∪ N LN is the set of nodes composed of three three kinds of nodes (see Figure 2.1):

• N D is the set of decision nodes (represented by squares);

• N C is the set of chance nodes (represented by circles);

• N LN is the set of leaves, also called utility nodes.

The set E contains the directed edges between nodes, forming a tree where each edge links a parent node to its child node. For any node N ∈ N , Out(N ) ⊆ E denotes its outgoing edges, Succ(N ) the set of its children nodes and Succ(N, e) the child of N that is reached by edge e ∈ Out(N ).

A DT represents a sequential decision problem in the following way:

• Leaf nodes correspond to states of the world in which a utility is obtained (for the sake of simplicity we assume that utilities are attached to leaves only); the utility of a leaf node

LN i ∈ N LN is denoted u(LN i ).
• Decision nodes correspond to states of the world in which a decision is to be made: D i ∈ N D represents a decision variable Y i . Its domain corresponds to the labels a of the edges starting from D i .These edges lead to chance nodes, i.e. Succ(D i ) ⊆ N C .

• A state variable X j is assigned to each chance node C j ∈ N C . Its domain corresponds to the labels x of the edges starting from that node. Each edge starting from a chance node C j represents an event X j = x. For any

C j ∈ N C , Succ(C j ) ⊆ N LN ∪ N D i.e.
after the execution of a decision, either a leaf node or a decision node is reached.

Given a decision tree DT , Start(DT ) denotes the set of its first decision nodes (it is a singleton containing the root of the tree if this root is a decision node, or its successors if the root is a chance node). For the sake of simplicity, we suppose that all the paths from the root to a leaf in the tree have the same length. The horizon of the decision tree, denoted by h, is the number of decision nodes along these paths. The branching factor, denoted by b, is the number of children at each node. Given a node N ∈ N , we shall also consider the subproblem DT N defined by the tree rooted in N .

The joint knowledge on the state variables is not given in extenso, but through the labeling of the edges issued from chance nodes. In a possibilistic context, the uncertainty pertaining to the possible outcomes of each X j is represented by a possibility distribution: each edge starting from a chance node C j , representing an event X j = x, is endowed with a number π C j (x), the possibility π(X j = x|past(C j ))1 . A possibilistic ordered scale, V , is used to evaluate the utilities and possibilities.

Example 2.1. Let us suppose that a "Rich and Unknown" person runs a startup company. In every state s/he must choose between Saving money (Sav) or Advertising (Adv) and s/he may then get Rich (R) or Poor (P) and Famous (F) or Unknown (U). Figure 2.1 shows the ΠDT (with horizon h = 2) that represents this sequential decision problem. This ΠDT contains 10 chance nodes

N C = {C 1 , C 2 , C 3 , C 4 , C 5 , C 6 , C 7 , C 8 , C 9 , C 10 }, 5 decision nodes N D = {D 0 , D 1 , D 2 , D 3 , D 4 } and 16 leaf nodes N LN = {LN 1 , . . . , LN 16 }.
Solving a decision tree amounts to building a policy (and thus, a succession of chance node) for each reachable decision node. Formally, we define a policy as a function δ : N D → A, where A is the set of possible actions, including a special "undefined" action ⊥, chosen for decision nodes which are left unexplored by a given policy. δ(D i ) is the action to be executed when a decision node D i is reached.

Admissible policies assign a chance node to each reachable decision node, i.e. must be: • complete:

• sound: ∀D i ∈ N D , δ(D i ) ∈ Out(D i ) ∪ {⊥} ⊆ A,
(i) ∀D i ∈ Start(DT ), δ(D i ) = ⊥ and (ii) ∀D i s.t. δ(D i ) = ⊥, ∀N ∈ Succ(Succ(D i , δ(D i ))) either δ(N ) = ⊥ or N ∈ N LN .
We denote by ∆ N (or simply ∆, when there is no ambiguity) the set of admissible policies built from a tree rooted in N . Each policy δ in ∆ defines a connected subtree of DT , the branches of which represent possible scenarios, or trajectories. Formally, a trajectory is a sequence of value assignments to decision and chance variables along a path from a starting decision node (a node in Start(DT )) to a leaf:

τ = (a j 0 , x i 1 , a j 1 , . . . , a j h-1 , x i h ),
where Y 0 = a j 0 is the first decision in the trajectory, x i 1 the value taken by its first chance variable, X j 0 in this scenario, Y i 1 = a j 1 is the second decision, etc.

We often identify a policy δ, the corresponding subtree and the set of its trajectories (hence the notation τ ∈ δ to mean that τ is a trajectory of δ). We also consider subtrees of the original DT , and thus sub-policies: let C j be a chance node, D i 1 , . . . , D i k its successors and, for l = 1, k, the policies δ i l ∈ ∆ D i l which solve the subproblem rooted in D i l .

δ i 1 + • • • + δ i k is the policy of ∆ C j resulting from the composition of the δ i l : (δ i 1 + • • • + δ i k )(N ) = δ i l (N ) iff N belongs to the subtree rooted in D i l .
Example 2.2. Let us consider the ΠDT of example 2.1. This ΠDT encodes 16 trajectories:

• τ 1 = (Adv, R&U, Adv, R&U ),
• τ 2 = (Adv, R&U, Adv, R&F ),

• τ 3 = (Adv, R&U, Sav, P &U ),

• τ 4 = (Adv, R&U, Sav, R&U ),

• τ 5 = (Adv, R&F, Adv, R&U ),

• τ 6 = (Adv, R&F, Adv, R&F ) etc.
The possibilistic evaluation of a policy, as proposed by [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF]], relies on the qualitative optimistic and pessimistic decision criteria axiomatized by [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF]. The utility of the policy is computed on the basis of the transition possibilities and the utilities of its trajectories. For each trajectory τ = (a j 0 , x i 1 , a j 1 , . . . , x i h )

• Its utility, u(τ ), is the utility u(x i h ) of its leaf x i h .

• The possibility of τ given that a policy δ is applied from initial node D 0 is defined by:

π(τ |δ, D 0 ) = min π k ∈πτ π k if τ ∈ δ, 0 otherwise.
Following [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF], [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF]] define as follows , the optimistic and pessimistic utility degrees of a policy δ ∈ ∆:

u opt (δ) = max τ ∈δ min(π(τ |δ, D 0 ), u(τ ))
(2.1)

u pes (δ) = min τ ∈δ max (1 -π(τ |δ, D 0 ), u(τ )) (2.2)
This approach is purely ordinal (only min and max operations are used to aggregate the evaluations of the possibility of events and the utility of states). We can check that the preference orderings O between policies, derived either from u opt (O = u opt ) or from u pes (O = u pes ), satisfy the principle of weak monotonicity:

∀C j ∈ N C , ∀D i ∈ Succ(C j ), δ, δ ∈ ∆ D i , δ" ∈ ∆ Succ(C j )\D i : δ O δ =⇒ δ + δ" O δ + δ
where δ + δ" (resp. δ + δ ) is the policy resulting from the composition δ (resp. δ ) with δ".

Optimization of ΠDT s: Backward induction

Since optimistic and pessimistic utilities satisfy the crucial property of weak monotonicity, an optimal policy can be computed in polytime with respect to the size of the tree (the total number of nodes) using a recursive method of Dynamic programming called backward search method or backward induction method. [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF], Sabbadin, 2001] have proposed qualitative counterparts of the stochastic dynamic programming algorithm backwards induction, denoted BI-DT , for ΠDT s (see Algorithm 2.1, written in a recursive style) that optimizes the decisions from the leaves of the tree to its root. Note that this algorithm does not generate all the best policies but returns only one among them. This backwards reasoning procedure is depicted in a recursive manner:

• when a chance node N ∈ N C is reached, optimistic (resp. pessimistic) utility is calculated for each of its children (i.e. each successor decision node or leaf node). Note that the optimistic utility of a leaf node is its utility. The optimistic utility obtained in N is then calculated using the possibility degrees on all successors and their optimistic utility.

• When a decision node N ∈ N D is reached, we select a decision C j among all the possible ones leading to an optimal sub-policy w.r.t. uopt . The choice is performed by comparing the optimistic utilities obtained in each successor chance node of N .

Decision trees represent sequential decision problems under the assumption of complete observation. However, they have serious limitations in their ability to model complex situations, especially when outcomes or events occur over a long time horizon. As a result, decision trees are often replaced with the use of Markov Decision Processes (MDPs) [Puterman, 1994] which are compact representations of sequential decision problems. They explicitly account for timing of events, whereas time usually is less explicitly accounted in decision trees.

Algorithm 2.1: BI-DT : Backward-Induction-ΠDT -u opt (N :Node) Data: A ΠDT ; the policy, δ, is memorized as global variable Result: Set δ for the tree rooted in N and returns its optimistic utility

1 begin 2 // Leaves 3 if N ∈ N LN then u opt ← u(N ); 4 // Chance nodes 5 if N ∈ N C then 6 foreach N i ∈ Succ(N ) do 7 u i opt ← Backward-Induction-ΠDT -uopt(N i ); 8 u opt ← max N i ∈Succ(N ) min(π N (D i ), u i opt ); 9 // Decision nodes 10 if N ∈ N D then 11 u opt ← 0; 12 foreach C j ∈ Succ(N ) do 13 u ← Backward-Induction-ΠDT -uopt(C j ); 14 if u > u opt then 15 u opt ← u; 16 δ(N ) ← label((N, C j )); 17 return u opt ;

Possibilistic Markov Decision Processes (ΠMDPs)

Possibilistic Markov decision processes (ΠMDPs) represents a qualitative version of probabilistic MDPs. In these models, uncertainty about the consequences of actions is represented by possibility distributions and rewards are qualitative [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF], Sabbadin, 1999, Sabbadin, 2001, Perny et al., 2005].

Solving a ΠMDP amounts to finding an 'optimal' action for any state of the world encountered, with respect to optimization criteria: optimistic and pessimistic utilities. In finite-horizon ΠMDPs an optimal policy can be provided, using a possibilistic backwards induction algorithm, proposed by [Sabbadin, 1999] as an adaptation of the classical stochastic one [Bellman, 1957a,Puterman, 1994]. However, in infinite-horizon ΠMDPs the most often used algorithms are possibilistic policy iteration algorithm [Sabbadin, 2001] (the possibilistic counterpart of stochastic policy iteration [Howard, 1960]) and possibilistic value iteration algorithm [Sabbadin, 2001] (the possibilistic counterpart of stochastic value iteration [Bellman, 1957a]).

Finite-horizon possibilistic Markov decision processes (Finitehorizon ΠMDPs)

Finite-horizon ΠMDP is a mathematical framework for representing complex multi-stage decision problems with finite time horizon.

Definition

A Finite-horizon MDP [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF], Sabbadin, 2001] is defined by:

• A finite set of stages T = {0, . . . , h}. h is called the horizon of the problem.

• Finite state spaces, S t , for each t = 0 . . . h ; S = S 0 ∪...∪S h denotes the set of all possible states at every time steps.

• Sets A s of available actions in state s ∈ S t ; A = A S 0 ∪ ... ∪ A S h denotes the full action space.

• The rewards u(s) that are obtained in the final states s ∈ S h . In this Section we do not consider intermediate satisfaction degrees.

In a possibilistic context, the uncertainty of the agent about the effect of an action a taken in state s ∈ S t-1 is represented by a possibility distribution π(.|s, a) : S t → V . For s ∈ S t , π(s |s, a) measures to what extent s is a plausible consequence of a in s. In the same way, consequences are ordered in terms of levels of satisfaction by a qualitative utility function u :

S h → V .
Such a ΠMDP can be represented by a labeled graph, where states are represented by circles, actions by squares and each final state has an attached utility. Each edge linking an action to a state denotes a transition, and is labeled by the possibility of that transition given the action is executed.

DT s and finite-horizon MDP are two close frameworks. A decision tree is a particular finitehorizon Markov decision process, up to the notations. Decision nodes are states, and the chance nodes that follow a decision node are the actions available in this state.

Example 2.3. Let us consider the problem introduced in Example 2.1 -it is possible to represent it as a Finite-horizon ΠMDP. Figure 2.2 represents the ΠMDP, in the form of an acyclic graph, when the horizon h = 2 (here, utilities are also shown). We have:

S 0 = {R&U 0 }, S 1 = {R&F 1 , R&U 1 , P &U 1 } and S 2 = {R&F 2 , R&U 2 , P &F 2 , P &U 2 } also ∀t = 0, 2, A s∈St = {Adv, Sav}.
A policy in a Finite-horizon MDP is a function that maps each state to an admissible action δ : S → A, s.t. δ(s) ∈ A s . When applied from a state s i0 ∈ S 0 , such a policy defines a list of trajectories, as for the decision trees case. A trajectory τ is a sequence of actions and states along a path following (and excluding) a first state s i0 to a final state s ih ∈ S h . Formally, τ = (a j0 , . . . , s ik , a jk , . . . , s ih ),

where s ik ∈ S k and a jk = δ(s ik ). We suppose, without loss of generality, that all trajectories have the same length h. If a trajectory has shorter length than h, neutral elements (0 or 1 as appropriate) are added at the end.

Note that s i0 is not part of the trajectory but given alongside the MDP model. a j0 is the first action in the trajectory -the one prescribed by δ for s i0 -etc. The reward associated to τ is the utility u(s ih ) obtained in the final state of the trajectory s ih .

The evaluation of a policy δ in state s 0 using qualitative pessimistic utility is defined by the qualitative minmax expectation of the degrees of satisfaction of the final states of the possible trajectories, and the optimistic utility as the maxmin expectation of the same:

u pes (s 0 , δ) = min τ ∈δ max{1 -π(τ |s 0 , δ), u(s ih )} (2.3) u opt (s 0 , δ) = max τ ∈δ min{π(τ |s 0 , δ), u(s ih )} (2.4)
The possibility π(τ |s 0 , δ) of τ given that policy δ is applied from initial state s 0 is defined by:

π(τ |s 0 , δ) = min π k ∈πτ π k if τ ∈ δ, 0 otherwise.
These criteria can be optimized by choosing, for each state, an action that maximizes the following counterparts of the Bellman equations [Sabbadin, 2001]:

• In the pessimistic case        u pes (s) = max a∈As min{u(s), min s ∈S t+1 max{1 -π(s |s, a), u t+1 pes (s )}∀t < h, s ∈ S t u pes (s) = u(s) ∀s ∈ S h (2.5)
• In the optimistic case:

       u opt (s) = max a∈As min{u(s), max s ∈S t+1 min(π(s |s, a), u opt (s ))}∀t < h, s ∈ S t u opt (s) = u(s) ∀s ∈ S h . (2.6)
2.3.1.2 Optimization of finite-horizon ΠMDPs: Backward Induction [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF], Sabbadin, 1999] have shown that any policy computed backwards by successive applications of Equation 2.5 (resp. 2.6) is optimal according to u pes (resp. u opt ).

The principle of the optimistic version of this algorithm denoted BI-M DP (Algorithm 2.2, the pessimistic version is similar) can be described as follows:

• Envision being in the last time stage, for all the possible states, it decides the best action for each state by calculating the maximal optimistic utility of that state,

• Then, suppose being in the next-to-last stage, for all the possible states, it decides the best action for each state, given we know the optimal optimistic utility of being in various states at the next time stage,

• This process is continued until reaching the present time stage.

Algorithm 2.2: BI-M DP : Backward-Induction-ΠMDP-u opt Data: A ΠMDP Result: Computes and returns an optimal policy δ 1 begin

2 t ← h; 3 for s ∈ S h do u opt (s) ← u(s); 4 while t ≥ 1 do 5 t ← t -1; 6 foreach s ∈ S t do 7 u opt (s) ← max a∈As max s ∈S t+1 min{π(s |s, a), u opt (s )}; 8 δ(s) ← arg max a∈As max s ∈S t+1 min{π(s |s, a), u opt (s ) ; 9 return δ;

Stationary Possibilistic Markov decision processes (stationary

ΠMDPs)

The previous section was devoted to the finite-horizon version of the MDP framework. In some situations, we do not know when the process will end, or to control the system forever: the MDP problem has to be expressed whatever the horizon h, or, more generally, for an infinite horizon. In the present Section, we consider stationary problems, i.e. problems in which the set of states, the available actions and the transition functions do not depend on the stage of the problem.

Definition

A stationary possibilistic Markov Decision Process (stationary ΠMDP) [Sabbadin, 2001] 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 utility function u: u(s) is the intermediate satisfaction degree obtained in state s ∈ S.

The uncertainty about the effect of an action a taken in state s, i.e. the transition function, is represented by possibility distribution π(.|s, a): for any s ∈ S, π(s |s, a) describing the uncertainty about the possible next state s when the current state is s and the action taken is a (and then getting the associated reward u(s ) ∈ V , the utility of being in state s ).

Example 2.4. Let us consider Figure 2.3 that shows a stationary ΠMDP that captures the problem of Example 2.1, formally described as follows:

• S = {R&U, R&F, P &U },

• A R&U = {Adv, Sav}, A R&F = {Sav}, A P &U = {Sav}, • π(P &U |R&U, Sav) = 0.2, π(R&U |R&U, Sav) = 1, π(R&F |R&U, Adv) = 1, π(R&F |R&F, Sav) = 1, π(R&U |R&F, Sav) = 1, • u(R&U ) = 0.5, u(R&F ) = 0.7, u(P &U ) = 0.3. R&U R&F Adv Sav π =1 π =1 π =1 Sav P&U π =0.2 π =1 π =1 Figure 2.3: The stationary ΠMDP of Example 2.4
Solving a stationary ΠMDP consists in finding a (stationary) policy, i.e. a function δ : S → A s , mapping states to actions, which is optimal with respect to a decision criterion. In the possibilistic case, as in the probabilistic case, the idea is to compute the value of a policy from the utility and the likelihood of its trajectories. Formally, let ∆ be the set of all policies encoded by a possibilistic MDP. First, when the horizon is finite, each δ ∈ ∆ defines a list of scenarios called trajectories. Each trajectory τ is a sequence of states and actions that can be written as follows:

τ = (s 0 , a 0 , s 1 , . . . , s h-1 , a h-1 , s h ),
where s i (i = 0..h) is the i th state in the trajectory (i.e. s i ∈ S at stage t = i), a i (i = 0..h-1) is the i th action in the trajectory i.e. a i ∈ A S at stage t = i (i = 0..h -1).

As in the case of finite-horizon ΠMDP, the possibility (resp. the utility) of τ given that policy δ is applied from s 0 is expressed by:

π(τ |s 0 , δ) = min i=1..h π(s i |s i-1 , δ(s i-1 )) (2.7) u(τ ) = min i=0..h u(s i ) (2.8)
Optimistic and pessimistic utilities criteria [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF]] can be optimized by choosing, for each state, an action that maximizes the following counterparts of the Bellman equations [Bellman, 1957a, Sabbadin, 2001]:

u opt (s) = max a∈As min{u(s), max s ∈S min(π(s |s, a), u opt (s ))}
(2.9)

u pes (s) = max a∈As min{u(s), min s ∈S max(1 -π(s |s, a), u pes (s ))} (2.10)
This formulation is more general than the first one (finite-horizon ΠMDP) in the sense that it applies to both the finite and the infinite case. It has allowed the definition of a (possibilistic) value iteration algorithm and a policy iteration algorithm which converges to an optimal policy in polytime.

Optimization of stationary ΠMDPs: Value iteration

In [Sabbadin, 2001], Sabbadin assumes the existence of an additional action stay that keeps the system in the same state (or equivalently, an action do-nothing if the system does not evolve by itself without any action applied). Under this assumption, possibilistic counterpart of the value iteration algorithm is defined, denoted V I-M DP . It computes optimal policies from iterated modifications of possibilistic value function Qopt (s, a) (resp. Qpes (s, a)) that evaluates the optimistic utility (resp. the pessimistic utility) of performing a in s.

The optimal possibilistic policy can be obtained from the solution of dynamic programming equations expressed by: • In the optimistic case:

Qopt (s, a) = max s ∈S min{(u(s ), π(s |s, a)), u opt (s )} (2.11)
where u opt (s) = max a Q opt (s, a) and Q opt (s, stay) = u(s).

• In the pessimistic case: Qpes (s, a) = min s ∈S min{u(s ), max{(1 -π(s |s, a)), u pes (s )}} (2.12)

where u pes (s) = max a Q pes (s, a) and Q pes (s, stay) = u(s).

Therefore, a possibilistic version of the Value Iteration algorithm (Algorithm 2.3), that computes Qopt (s, a) or Qpes (s, a), has been defined [Sabbadin, 2001]. This algorithm converges to the actual value of Qopt (resp. Qpes ) in a finite number of steps. R. Sabbadin has proposed a possibilistic policy iteration algorithm (Algorithm 2.4), denoted here P I-M DP , that alternates evaluation and improvement phases, as for its stochastic counter-part [Sabbadin, 2001] (a pessimistic counterpart of Algorithm 2.4 is obtained by the use of the pessimistic utility evaluations, instead of the optimistic ones). First of all, this algorithm chooses an initial policy arbitrary, then two steps follow:

• policy evaluation: it calculates the optimistic utility of each state given the current policy δ until convergence,

• policy improvement: it updates the policy if an improvement is possible.

The stopping criterion for the possibilistic policy iteration algorithm is the equality of the optimistic values of two successive policies δ and δ (Line 14).

Summary

In this chapter we have proposed a short review of the possibilistic sequential decision-making based on the possibilistic counterparts of decision trees and Markov decision processes. First, we have presented possibilistic decision trees that offer a natural and explicit model to handle possibilistic sequential decision problems. We have studied the optimization of policies for optimistic or pessimistic utilities, in such models, using backward induction algorithm. Besides, we have focused on the possibilistic Markov Decision Processes framework, and the three algorithms for optimizing possibilistic utilities criteria: Backward induction, value iteration and policy iteration.

In the next Chapter, we detail the problem of drowning effect when comparing policies in sequential problems. We define lexicographic refinements that compare full policies, and not simply their reductions. Chapter 4 provides a backward induction algorithm to compute a lexicographic optimal policy in possibilistic decision trees as well as a backward induction algorithm to optimize possibilistic (finite-horizon) Markov decision processes. We show also that these refinements can be represented by infinitesimal expected utilities (Chapter 5). The case of stationary ΠMDP is handled in Chapter 6.

Introduction

Possibilistic decision criteria, especially pessimistic and optimistic utilities, are simple and realistic as presented in Chapter 1, but they have some shortcomings: the principle of Pareto efficiency is violated since these criteria suffer from the drowning effect [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF].

In order to overcome the drowning effect, some refinements of possibilistic decision criteria have been proposed in the non-sequential case i.e. one-step decision case (see Chapter 1). In particular, [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF] have proposed lexicographic refinements of possibilistic utilities which can be represented by a form of expected utility. But, these refinements are limited to one-step decision problems and do not apply to the sequential decision problems that interest us. The present Chapter provides an extension of lexicographic refinements to sequential decision-making, in order to apply them to decision trees and Markov decision processes. This chapter is structured as follows: Section 3.2 exposes the problem of drowning effect when optimizing possibilistic utilities criteria in sequential decision-making models. Section 3.3 proposes a way to compare policies using lexicographic procedures: first we detail the case of evaluating decision models with utilities on final stage i.e. ΠDT s and finite-horizon ΠMDPs, and then the case of models with intermediate utilities i.e. stationary ΠMDPs.

Drowning effect in possibilistic sequential decisionmaking

As mentioned in Chapter 1, the pessimistic and optimistic utilities present a severe drawback, known as the "drowning effect", due to the use of idempotent operations.

In this Section, we first illustrate the drowning effect of qualitative utilities, as well as its consequences, in possibilistic decision trees and finite-horizon possibilistic Markov decision processes. Then, we focus on stationary possibilistic Markov decision processes. When possibilistic qualitative utilities are used, two policies that give an identical and extreme utility (either good, for u opt or bad, for u pes ) in some plausible trajectory, may be undistinguished although having given significantly different consequences in other possible trajectories. As shown by the following counter-example.

Counter-example 3.1. Let us consider ΠDT of Example 2.1 (we recall it in Figure 3.1).

Let δ and δ be the two policies defined by:

• δ(D 0 ) = Adv; δ(D 1 ) = Adv; δ(D 2 ) = Adv. • δ (D 0 ) = Adv; δ (D 1 ) = Sav; δ (D 2 ) = Adv,
We can check that δ has 4 trajectories (τ 1 , τ 2 , τ 5 , τ 6 ):

• τ 1 = (Adv, R&U, Adv, R&U ) with π(τ 1 |δ, D 0 ) = 0.5 and u(τ 1 ) = 0.5,

• τ 2 = (Adv, R&U, Adv, R&F ) with π(τ 2 |δ, D 0 ) = 0.5 and u(τ 2 ) = 0.7,

• τ 5 = (Adv, R&F, Adv, R&U ) π(τ 5 |δ, D 0 ) = 0.5 and u(τ 5 ) = 0.5,

• τ 6 = (Adv, R&F, Adv, R&F ) π(τ 6 |δ, D 0 ) = 1 and u(τ 6 ) = 0.5, Using Equation 2.1 and 2.2, we get:

• u opt (δ) = max(min(0.5, 0.5), min(0.5, 0.7), min(0.5, 0.5), min(1, 0.5)) = 0.5,

• u pes (δ) = min(max(0.5, 0.5), max(0.5, 0.7), max(0.5, 0.5), max(0, 0.5)) = 0.5. The policy δ has also 4 trajectories (τ 3 , τ 4 , τ 5 , τ 6 ):

• τ = (Adv, R&U, Sav, P &U ) with π(τ 3 |δ , D 0 ) = 0.2 and u(τ 3 ) = 0.3,

• τ = (Adv, R&U, Sav, R&U ) with π(τ 4 |δ , D 0 ) = 0.5 and u(τ 2 ) = 0.5,

• τ = (Adv, R&F, Adv, R&U ) with π(τ 5 |δ , D 0 ) = 0.5 and u(τ 5 ) = 0.5,

• τ = (Adv, R&F, Adv, R&F ) with π(τ 6 |δ , D 0 ) = 1 and u(τ 6 ) = 0.5, Hence, we have:

• u opt (δ ) = max(min(0.2, 0.3), min(0.5, 0.5), min(0.5, 0.5), min(1, 0.5)) = 0.5, CHAPTER 3. EXTENDING LEXICOGRAPHIC REFINEMENTS TO POSSIBILISTIC SEQUENTIAL DECISION-MAKING 42

• u pes (δ) = min(max(0.8, 0.3), max(0.5, 0.5), max(0.5, 0.5), max(0, 0.5)) = 0.5.

Thus u opt (δ) = u opt (δ ) and u pes (δ) = u pes (δ ): δ, which provides at least utility 0.5 in all trajectories, is not preferred to δ that provides clearly a bad utility (0.3) in some non-impossible trajectory (τ 3 ). τ 4 , which is good and totally possible "drowns" the bad consequence of δ in τ 3 in the optimistic comparison; in the pessimistic one, the bad utility of τ 3 is drowned by its low possibility, hence a global degree u pes (δ ) that is equal to the one of δ (which, once again, guarantees a utility degree of 0.5 at least).

The two possibilistic optimistic and pessimistic utilities thus may fail to satisfy the principle of Pareto efficiency, which may be written as follows:

Definition 3.1. (Pareto efficiency) For any optimization criterion O (here u pes or u opt ),∀δ, δ ∈ ∆,

δ O δ if: (i) ∀N ∈ Common(δ, δ ), δ N O δ N and (ii) ∃N ∈ Common(δ, δ ), δ N O δ N .
where Common(δ, δ ) is the set of situations (decision nodes in DT s, states in the MDP framework) for which both δ and δ provide an action and δ N (resp. δ N ) is the restriction of δ (resp. δ ) to the subtree rooted in N .

Moreover, neither u opt nor u pes fully satisfy the classical, Strict monotonicity principle, that can be written as follows: Definition 3.2. (Strict monotonicity) For any optimization criterion O (here u pes or u opt ),

∀C j ∈ N C , D i ∈ Succ(C j ), δ, δ ∈ ∆ D i , δ" ∈ ∆ Succ(C j )\D i , δ O δ ⇐⇒ δ + δ" O δ + δ .
It may, indeed, happen that u pes (δ) > u pes (δ ) while u pes (δ + δ") = u pes (δ + δ") (or that u opt (δ) > u opt (δ ) while u opt (δ + δ") = u opt (δ + δ")), as shown in the following Counterexample.

Counter-example 3.2. Let us consider three policies δ, δ and δ , represented with the following simple possibilistic lotteries, respectively:

• L δ = 1/0.5, 1/0.4 , • L δ = 1/0.4, 1/0.4 , • L δ = 1/0.5, 1/0.1 . Let us consider L 1 = 1/L δ , 1/L δ and L 2 = 1/L δ , 1/L δ .
Using the reduction of compound lotteries (see Section 1.3.2), we get:

• Reduction(L 1 ) = 1/0.5, 1/0.4, 1/0.1 and • Reduction(L 2 ) = 1/0.4, 1/0.5, 1/0.1 .

Then using Equation 1.8, we have u opt (L δ ) = 0.5 and u opt (L δ ) = 0.4 i.e. δ uopt δ .

But u opt (Reduction(L 1 )) = 0.5 and u opt (Reduction(L 2 )) = 0.5, i.e. δ + δ ≡ uopt δ + δ . This contradicts the strict monotonicity property. Now, let us present an example that shows the drowning effect in finite-horizon ΠMDPs.

Counter-example 3.3. Figure 3.2 shows the finite-horizon ΠMDPs (with the horizon h = 2) that represents an adaptation of the decision problem of Example 2.1. Note that here being Poor and Unknown is an absorbing state (i.e. a state that, once entered, cannot be left). Let us consider the following two policies, δ and δ :

• δ(R&U 0 ) = Adv; δ(R&U 1 ) = Sav; δ(R&F 1 ) = Sav, CHAPTER 3. EXTENDING LEXICOGRAPHIC REFINEMENTS TO POSSIBILISTIC SEQUENTIAL DECISION-MAKING 44 • δ (R&U 0 ) = Adv; δ (R&U 1 ) = Adv; δ (R&F 1 ) = Sav.
δ has 4 trajectories, τ 1 , τ 2 , τ 5 , τ 6 with:

• τ 1 = (Adv, R&U , Sav, P &U 2 ) with π(τ 1 |R&U, δ) = 0.2 and u(τ 1 ) = 0.3,

• τ 2 = (Adv, R&U 1 , Sav, R&U 2 ) with π(τ 2 |R&U, δ) = 0.4 and u(τ 2 ) = 0.5,

• τ 5 = (Adv, R&F 1 , Sav, R&U 2 ) with π(τ 5 |R&U, δ) = 1 and u(τ 5 ) = 0.5;

• τ 6 = (Adv, R&F 1 , Sav, R&F 2 ) with π(τ 6 |R&U, δ) = 1 and u(τ 6 ) = 0.5.

Hence u opt (δ) = 0.5.

δ is also composed of 4 trajectories (τ 3 , τ 4 , τ 5 , τ 6 ) each leading to utility 0.5. Hence u opt (δ ) = 0.5.

Thus u opt (δ) = u opt (δ ). However δ seems better than δ since it provides utility 0.5 for sure while δ provides a bad utility (0.3) in some non impossible trajectory (τ 1 ). τ 2 , which is good and totally possible "drowns" the preference for δ in the optimistic comparison.

In the pessimistic case, δ and δ are still equivalent (u pes (δ) = u pes (δ ) = 0.5) and the pessimistic criterion is not able to pick up the best one i.e. that is δ .

We finally provide a counter-example that exemplifies the drowning effect in stationary ΠMDPs.

Counter-example 3.4. Consider the stationary ΠMDPs of Example 2.4 (we recall it in Figure 3.3); recall that u(R&U ) = 0.5, u(R&F ) = 0.7, u(P &U ) = 0.3. It admits two policies δ and δ :

• δ(R&U ) = Sav; δ(P &U ) = Stay; δ(R&F ) = Sav;

• δ (R&U ) = Adv; δ (P &U ) = Stay; δ (R&F ) = Sav;

For horizon E = 2, δ has 3 trajectories (τ 1 , τ 2 , τ 3 ) and δ has 2 trajectories (τ 4 , τ 5 ) such that:

• τ 1 = (R&U, Sav, P &U, Stay, P &U ) with π(τ 1 |R&U, δ) = 0.2 and u(τ 1 ) = 0.3,

• τ 2 = (R&U, Sav, R&U, Sav, P &U ) with π(τ 2 |R&U, δ) = 0.2 and u(τ 2 ) = 0.3, • τ 3 = (R&U, Sav, R&U, Sav, R&U ) with π(τ 3 |R&U, δ) = 1 and u(τ 3 ) = 0.5,
• τ 4 = (R&U, Adv, R&F, Sav, R&F ) with π(τ 4 |R&U, δ ) = 1 and u(τ 4 ) = 0.5,

• τ 5 = (R&U, Adv, R&F, Sav, R&U ) with π(τ 5 |R&U, δ ) = 1 and u(τ 5 ) = 0.5.

Thus u opt (δ) = u opt (δ ) = 0.5 although δ provides a good 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 , thus δ is considered as good as δ .

R&U R&F Adv

Sav

π =1 π =1 π =1 Sav P&U π =0.2 π =1 π =1
Figure 3.3: The stationary πMDP of Counter-example 3.4

Lexicographic refinements in sequential decision-making problems

As we have seen in Chapter 1, [Fargier andSabbadin, 2003,Fargier and[START_REF] Fargier | [END_REF] have proposed lexicographic refinements in order to overcome the drowning effect of possibilistic criteria in one-stage decision problems. However, these refined criteria cannot be used in sequential decision problems, where the drowning effect is also due to the reduction of compound possibilistic policies into simple possibility distributions or into numbers i.e. optimistic or pessimistic utilities.

The purpose of the present work is to build efficient preference relations on policies, that agree with the qualitative utilities when the latter can make a decision, and break ties when not -to build refinements that satisfy the principle of Pareto efficiency.

Formally, in sequential decision framework, a preference relation refines a preference relation if and only if whatever δ, δ , if δ δ then δ δ .

In this section, we propose an extension of the lexicographic refinements to policies in sequential decision models, i.e. ΠDT s and ΠMDPs. We will first consider the case where we do not have intermediate utilities, then the case of policies with intermediate utilities.

Problems without intermediate utilities

A straightforward way of applying lexicographic comparisons to sequential decision problem is to associate to any policy δ the possibility distribution that it induces on the utility rewards (i.e. the reduction of δ), as usually done in possibilistic (and probabilistic) DT s.

First, for any policy δ (or a sub policy) and any of its trajectories, τ = (a j 0 , x i 1 , a j 1 , . . . , x i h ) in a ΠDT or τ = (a j0 , ..., s ik , a jk , s ih ) in a finite-horizon ΠMDPs, we associate a vector defined by: π τ = (π 1 , . . . , π h , u h ).

This vector gathers the possibility and utility degrees encountered on the trajectory, formally:

• For the case of ΠDT s, u h is the utility u(x i h ) of the leaf of τ and π k = π C j k-1 (x i k ) (where π C j k-1 is the possibility distribution at chance node C j k-1 ) is the possibility of x i k given that action a j h-1 is executed.

• For the case of ΠMDPs, u h is the utility u(s ih ) obtained in the final state of the trajectory s ih . π k = π(s ik |s ik-1 , a jk-1 ) denotes the possibility degree to reach s k applying action a jk-1 from state s ik-1 .

Since a policy δ can be seen as a compound lottery, following the reduction of compound lotteries procedure (see Equation 1.5), it is possible to reduce δ to a distribution π δ on the utility degrees (i.e a simple lottery) defined by:

π δ (u) = max πτ ,τ ∈δ and u h =u min π k ∈πτ π k .
This principle of reduction is used, when qualitative decision theory is considered, by [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF], Sabbadin, 2001] to compare policies: the pessimistic (resp. optimistic) utility of a policy is simply the one of its reduction. Because the π δ are single stepped, one can think on applying lexicographic comparisons as such, and can write:

δ lmax(lmin) δ iff π δ lmax(lmin) π δ , δ lmin(lmax) δ iff π δ lmin(lmax) π δ .
lmax(lmin) (resp. lmin(lmax) ) refines uopt (resp. upes ), but neither lmax(lmin) nor lmin(lmax) do satisfy the principle of Pareto efficiency, as shown by the following counter-example.

Counter-example 3.5. Consider the ΠDT in Figure 3.4 that is a modified version of the problem of Example 2.1.

Let us consider the two policies δ and δ defined by:

• δ(D 0 ) = Adv, δ(D 1 ) = Sav, δ(D 2 ) = Adv, • δ (D 0 ) = Adv, δ = (D 1 ) = Adv, δ D 2 = Adv.
We have: lmax(lmin), since ((1, 0.1), (1, 0.9)) lmax(lmin) ((1, 0.1)(0.5, 0.9)).

Common(δ, δ ) = {D 0 , D 1 , D 2 }, δ D 0 = δ D 0 , δ D 2 = δ D 2 and δ D 1 dominates δ D 1 w.r.t.
So, δ should be strictly preferred to δ .

Let us compute the reduction of δ: • π δ (0.9) = π δ (0.1) = min(0.4, 1) = 0.4 and

• π δ (0.8) = min(1, 1) = 1,
and for δ we have:

• π δ (0.9) = min(0.4, 0.5) = 0.4,

• π δ (0.1) = min(0.4, 1) = 0.4 and

• π δ (0.8) = min(1, 1) = 1.
Thus, δ and δ are indifferent for lmax(lmin) , since both of them have the same reduction. This contradicts Pareto efficiency.

The drowning effect here is due to the reduction of the policies, namely to the fact that the possibility of a trajectory is drowned by the one of the least possible of its transitions. That is why we propose to give up the principle of reduction and to build lexicographic comparisons on policies considered in extenso.

Definition 3.3. (Leximax, Leximin relations on trajectories)

The comparison of trajectories can be seen as a comparison of vectors associated to trajectories. For any π τ = (π 1 , . . . , π h , u h ) and π τ = (π 1 , . . . , π h , u h ), we define lmin and lmax orders by:

τ lmin τ iff (π 1 , . . . , π h , u h ) lmin (π 1 , . . . , π h , u h ) (3.1) τ lmax τ iff (1 -π 1 , . . . , 1 -π h , u h ) lmax (1 -π 1 , . . . , 1 -π h , u h ) (3.2)
Hence the proposition of the following preference relations1 : Definition 3.4. (Leximax(leximin), Leximin(leximax) relations on policies) Let δ, δ ∈ ∆. Then:

δ lmax(lmin) δ iff ∀i, τ λ(i) ∼ lmin τ λ(i) or ∃i * , ∀i ≤ i * , τ λ(i) ∼ lmin τ λ(i) and τ λ(i * ) lmin τ λ(i * ) , (3.3) δ lmin(lmax) δ iff ∀i, τ σ(i) ∼ lmax τ σ(i) or ∀i, τ σ(i) ∼ lmax τ σ(i) or ∃i * , ∀i ≤ i * , τ σ(i) ∼ lmax τ σ(i) and τ σ(i * ) lmax τ σ(i * ) , (3.4)
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, a policy can be represented by a matrix with N lines, s.t. N is the number of trajectories, and M = h + 1 columns (h being the horizon of the decision model). Indeed, comparing two policies w.r.t. lmax(lmin) (resp. lmin(lmax) ) consists in first ordering the two corresponding matrices of trajectories as follows:

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

• then all the trajectories 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 ρ δ (resp. ρ δ ), element by element. The first pair of different elements determines the best matrix/policy. Note that the ordered matrix ρ δ (resp. ρ δ ) can be seen as the utility of applying the policy δ (resp. δ ).

Formally, let ρ denotes a N × M matrix of elements of V . ∀ i ∈ 1..M ; ∀ j ∈ 1..N , ρ ij denotes an element of ρ in line i and column j. Given two ordered matrices ρ and ρ , we say that ρ lmaxlmin ρ iff ∃ i, j such that ∀ i < i, ∀ j , ρ i ,j = ρ i ,j and ∀ j < j, ρ i,j = ρ i,j and ρ i,j > ρ i,j . ρ ∼ ρ iff they are identical.

As a matter of fact, once the matrix of trajectories ρ δ is reordered, the first element is always equal to u opt (δ) (resp. to u pes (δ) when applying lmin(lmax)): Proposition 3.1. Let δ be a policy and ρ be its ordered matrix w.r.t. lmaxlmin . Then:

u opt (δ) = ρ 1,1
Proof of Proposition 3.1. Let ρ be the ordered matrix of δ. Since lmax(lmin) refines maxmin [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF], we have:

ρ 1,1 = max i min j ρ i,j = max i=1,n min(π 1 , . . . , π h , u h ) = max i=1,n min(π 1 , min(π 2 , min(π h-1 , min(π h , u h )))) = u opt (δ).
Example 3.1. Let us consider the Counter-example 3.1 with the same ΠDT (we recall it in Figure 3.5) and let us optimize it using the proposed lexicographic comparisons. We consider, once again, the policies δ and δ defined by:

• δ(D 0 ) = Adv; δ(D 1 ) = Adv; δ(D 2 ) = Adv. • δ (D 0 ) = Adv; δ (D 1 ) = Sav; δ (D 2 ) = Adv,
As we have seen, δ has 4 trajectories (τ 1 , τ 2 , τ 5 , τ 6 ):

• τ 1 = (Adv, R&U, Adv, R&U ) with π τ 1 = (0.5, 0.5, 0.5),

• τ 2 = (Adv, R&U, Adv, R&F ) with π τ 2 = (0.5, 1, 0.7),

• τ 5 = (Adv, R&F, Adv, R&U ) with π τ 5 = (1, 0.5, 0.5),

• τ 6 = (Adv, R&F, Adv, R&F ) with π τ 6 = (1, 1, 0.5).

So, the ordered matrix of trajectories is:

ρ δ =     
0.5 1 1 0.5 0.7 1 0.5 0.5 1 0.5 0.5 0.5

     .
δ has also 4 trajectories (τ 3 , τ 4 , τ 5 , τ 6 ):

• τ 3 = (Adv, R&U, Sav, P &U ) with π τ 3 = (0.5, 0.2, 0.3),

• τ 4 = (Adv, R&U, Sav, R&U ) with π τ 4 = (0.5, 1, 0.5),

• τ 5 = (Adv, R&F, Adv, R&U ) with π τ 5 = (1, 0.5, 0.5), • τ 6 = (Adv, R&F, Adv, R&F ) with π τ 6 = (1, 1, 0.5),

The ordered matrix of trajectories is:

ρ δ =      0.5 1 1 0.5 0.5 1 0.5 0.5 1 0.2 0.3 0.5      .
Given the two ordered matrices ρ δ and ρ δ , δ and δ are indifferent for optimistic utility since the two first elements of the matrices are equal i.e. u opt (δ) = u opt (δ ) = 0.5. For lmax(lmin) we compare the successive next elements until we find a pair of different values. In particular, we have the second element of the second best trajectory of δ is strictly greater than the second element of the second best trajectory of δ i.e. 0.7 > 0.5, while all the former elements are equal. So, the second best trajectory of δ is strictly preferred to the second best trajectory of δ according to lmin . We deduce that δ is strictly preferred to δ : CHAPTER 3. EXTENDING LEXICOGRAPHIC REFINEMENTS TO POSSIBILISTIC SEQUENTIAL DECISION-MAKING 51 δ lmax(lmin) δ since (0.5, 0.7, 1) lmin (0.5, 0.5, 1).

We show now that, the proposed lexicographic criteria are relevant refinements and escape the drowning effect: Proposition 3.2. ( lmax(lmin) and lmin(lmax) orders)

• lmax(lmin) is complete, transitive and refines uopt ;

• lmin(lmax) is complete, transitive and refines upes .

Proof of Proposition 3.2.

• 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) δ . SEQUENTIAL DECISION-MAKING 52 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) δ .

• Refinement.

-We prove that lmax(lmin) refines uopt . Let us consider two policies δ and δ . If Proof of Proposition 3.3. (i) We first prove that lmax(lmin) and lmin(lmax) are strictly monotonic.

u opt (δ) > u opt (δ ) ⇔ max τ ∈δ min{ min π k ∈πτ π k , u h } > max τ ∈δ min{ min π k ∈π τ π k , u h } ⇒ max τ ∈δ min(π 1 , . . . , π h , u h ) > max τ ∈δ min(π 1 , . . . , π h , u h ). Since min(π 1 , . . . , π h , u h ) > min(π 1 , . . . , π h , u h ) ⇒ (π 1 , . . . , π h , u h ) lmin (π 1 , . . . ,
π k ∈πτ (1 -π k ), u h } > min τ ∈δ max{ min π k ∈π τ (1 -π k ), u h } ⇔ min τ ∈δ max(1 -π 1 , . . . , 1 -π h , u h ) > min τ ∈δ max(1 -π 1 , . . . , 1 -π h , u h ). Since max(1 -π 1 , . . . , 1 -π h , u h ) > max(1 -π 1 , . . . , 1 -π h , u h ) ⇒ (1 -π 1 , . . . , 1 -π h , u h ) lmax (1 -π 1 , . . . , 1 -π h , u h ) (leximax

Problems with intermediate utilities

Let h be the horizon of the stationary ΠMDP, as in the previous Section a trajectory is a sequence of states and actions. A policy can thus be viewed as a matrix where each line corresponds to a distinct trajectory τ = (s 0 , a 0 , s 1 , . . . , s h-1 , a h-1 , s h ) i.e. to a vector v τ = (u 0 , π 1 , u 1 , π 2 , . . . , π h-1 , u h ). This allow us to define the comparison of trajectories and policies by2 :

τ lmin τ iff (u 0 , π 1 , . . . , π h , u h ) lmin (u 0 , π 2 , . . . , π h , u h ) (3.5) τ lmax τ iff (u 0 , 1 -π 1 , . . . , 1 -π h , u h ) lmax (u 0 , 1 -π 1 , . . . 1 -π h , u h ) (3.6) δ lmax(lmin) δ iff ∀i, τ λ(i) ∼ lmin τ u(i) or ∃i * , ∀i < i * , τ λ(i) ∼ lmin τ λ(i) and τ λ(i * ) lmin τ λ(i * ) (3.7) δ lmin(lmax) δ iff ∀i, τ σ(i) ∼ lmax τ σ(i) or ∃i * , ∀i < i * , τ σ(i) ∼ lmax τ σ(i) and τ σ(i * ) lmax τ σ(i * ) (3.8)
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 .

It is easy to show that using these definitions, we also get efficient refinements of u opt and u pes : Proposition 3.4.

• If u opt (δ) > u opt (δ ) then δ lmax(lmin) δ , • If u pes (δ) > u pes (δ ) then δ lmin(lmax) δ .
Proof of Proposition 3.4.

• We prove that lmax(lmin) refines uopt in sequential decision models with intermediate utilities (stationary ΠMDP). Following Proof of Proposition 3.2, we consider two policies

δ and δ . If u opt (δ) > u opt (δ ) ⇔ 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(u 0 , π 1 , u 1 , π 2 , . . . , π h-1 , u h ) > max τ ∈δ min(u 0 , π 1 , u 1 , π 2 , . . . , π h-1 , u h ). Since min(u 0 , π 1 , u 1 , π 2 , . . . , π h-1 , u h ) > min(u 0 , π 1 , u 1 , π 2 , . . . , π h-1 , u h ) ⇒ (u 0 , π 1 , u 1 , π 2 , . . . , π h-1 , u h ) lmin (u 0 , π 1 , u 1 , π 2 , . . . , π h-1 , u 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) (Equation 3.3) we have δ lmax(lmin) δ . Thus, lmax(lmin) refines uopt .

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

⇔ 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(u 0 , 1 -π 1 , u 1 , 1 -π 2 , . . . , 1 -π h-1 , u h )} > min τ ∈δ max{(u 0 , 1 -π 1 , u 1 , 1 -π 2 , . . . , 1 -π h-1 , u h )}. Since max(u 0 , 1 -π 1 , u 1 , 1 -π 2 , . . . , 1 -π h-1 , u h ) > max(u 0 , 1 -π 1 , u 1 , 1 -π 2 , . . . , 1 -π h-1 , u h ) ⇒ (u 0 , 1 -π 1 , u 1 , 1 -π 2 , . . . , 1 -π h-1 , u h ) lmax (u 0 , 1 -π 1 , u 1 , 1 -π 2 , . . . , 1 -π h-1 , u h ) (as leximax ordering refines max ordering).
Then τ σ(1) lmax τ σ(1)1 ⇒ δ lmin(lmax) δ where τ σ(1) (resp. τ σ( 1) ) is the worst trajectory of δ (resp.δ ) according to lmax . So, by definition of lmin(lmax) (Equation 3.4) we have δ lmin(lmax) δ . We deduce that lmin(lmax) refines upes .

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

Proof of Proposition 3.5.

Summary

In this Chapter, we have discussed the limitations of possibilistic qualitative utilities, i.e. the drowning effect in sequential decision-making. It appears that these criteria do not satisfy the principle of Pareto efficiency nor the strict monotonicity. However, we have shown that it is possible to define an extended version of lexicographic comparisons, (initially proposed for the one-step decision problem), to improve discrimination in sequential decision-making. Properties of the proposed lexicographic comparisons have important consequences; from a prescriptive point of view, they highlight the rationality of lmax(lmin) and lmin(lmax) and suggest a probabilistic interpretation presented Chapter 5. These properties allow us to define Dynamic Programming algorithms for calculating lexicographic optimal policies-this is the topic of the next Chapter.

CHAPTRE 4

Optimizing Lexicographic criteria in ΠDT s and finite-horizon ΠMDPs

Introduction

In the previous Chapter, we have proposed lexicographic criteria that satisfy the crucial properties of strict monotonicity and transitivity which allow us to define solving algorithms based on Dynamic Programming to get lexicographic optimal policies. In the present Chapter, we propose backward induction algorithms to compute lexicographic optimal strategies policies in ΠDT s and finite-horizon ΠMDPs.

This Chapter is organized as follows: the next Section is devoted to the adaptation of Dynamic Programming algorithm, namely backward induction, to the lexicographic criteria in ΠDT s. Section 4.3 details the lexicographic backward induction algorithm to optimize policies in possibilistic finite-horizon ΠMDPs. Finally, Section 4.4 presents an experimental study of these algorithms.

CHAPTER 4. OPTIMIZING LEXICOGRAPHIC CRITERIA IN ΠDT S AND FINITE-HORIZON ΠMDPS

58

The main results of this chapter are published in [Ben Amor et al., 2016a[START_REF] Amor | Lexicographic refinements in possibilistic markov decision processes : The finite horizon case[END_REF].

Optimizing lexicographic criteria in ΠDT s

This Section rises the question of the policy optimization of lexicographic criteria (Definition 3.4) in ΠDT s .

Lexicographic backward induction algorithm in ΠDT s

Our aim here is to adapt the backward induction for optimizing possibilistic utilities in ΠDT s (see section 2.2.2) to lexicographic criteria.

The proposed lexicographic backward induction algorithm, so-called (LexBI-DT ), (Algorithm 4.1 for the lmax(lmin) variant; the lmin(lmax) variant is similar) proceeds in the classical way, by backward induction:

• When a chance node is reached, an optimal sub-policy is recursively built for each of its children; these subpolicies are combined but the resulting policy is NOT reduced, contrarily to what is classically done.

• When a decision node is reached, the program is called for each child and the best of them is selected.

The difference between the lexicographic backward induction algorithm and the classical version of Sabaddin (Algorithm 2.1) is that for the first one the lexicographic comparison of policies is done on the basis of their trajectories, rather than optimistic or pessimistic utilities. To this extent, the algorithm needs for each possible policy the matrix ρ that contains the following vectors:

• π τ = (π 1 , . . . , π h , u h ), in the optimistic case, or

• π τ = (1 -π 1 , . . . , 1 -π h , u h ), in the pessimistic case.
Hence, for line z corresponding to the z-th trajectory and stage t s.t. t = 0..h we define an element of the matrix denoted by ρ z,t as: Indeed, this algorithm is written in a recursive manner, and proceeds as follows:

ρ z,t =        π t if t ≤ h and O = lmax lmin 1 -π t if t ≤ h and O = lmin lmax u h if t = h + 1.
• When node N reached is a chance node, an optimal sub-policy is recursively built for each of its children N i : successors of a chance node may be decision nodes D i or leaf nodes LN i . These recursive calls return for each N i a matrix ρ N i that contains the π τ vectors of the trajectories τ of this sub-policy. To make the lexicographic comparison of trajectories, and thus of policies, we only need to compare their π τ vectors -hence we memorize the matrices of numbers rather than explicit trajectories. The matrix corresponding to the trajectories beginning at N , ρ is obtained by combining the ρ N i according to π N , the possibility distribution associated to N ; (this matrix is not reduced).

• When node N reached is a decision node, an optimal sub-policy is computed for every child C j . The best of them is selected, δ(N ) receives the action corresponding to this chance node and the corresponding ρ matrix is returned.

Algorithm 4.1: LexBI-DT : Backward-Induction-ΠDT -lmax(lmin)(N :Node) Data: A ΠDT ; the policy, δ, is memorized as global variable Result: Set δ for the tree rooted in N and returns the matrix ρ of the π τ vectors corresponding its trajectories 1 begin 2 // Leaves When N is a chance node, its matrix depends on N 1 , . . . , N k (on the ρ N i , recursively computed) the successors of N , and on the possibility distribution on them. It is built by a call to the function ConcatAndOrder(π N , ρ N 1 , . . . , ρ N k ) (outlined by Algorithm 4.2). This function adds a column to each ρ N i , filled with π N (N i ) the possibility degrees of getting N i ; the matrices are vertically concatenated. In order to get faster lexicographic comparisons, the elements in the lines are then ordered in decreasing (resp. increasing) order, and the lines are reordered by decreasing (resp. increasing) order w.r.t. to lmax (resp. lmin). Once ρ has been reordered, ρ 1,1 , the first element of ρ is equal to the optimistic utility (resp. the pessimistic utility) of the sub-policy represented by ρ. • Initially, we have N = D 0 with Succ(D 0 ) = {C 1 }.

3 if N ∈ N U then ρ = [u(N )]; 4 // Chance nodes 5 if N ∈ N C then 6 k = |Succ(N )|; 7 foreach N i ∈ Succ(N ) do 8 ρ N i ← Backward-Induction-ΠDT -lmax(lmin)(N i ) 9 ρ ← ConcatAndOrder(π N , ρ N 1 , ..., ρ n k ); 10 // Decision nodes 11 if N ∈ N D then 12 ρ ← [0]; 13 foreach C j ∈ Succ(N ) do 14 ρ C j ← Backward-Induction-ΠDT -lmax(lmin)(C j ); 15 if ρ C j lmax(lmin) ρ then 16 ρ ← ρ C j ; 17 δ(N ) ← label(N, C j );
• For C 1 , ρ C 1 = Backward-Induction-ΠDT -lmax(lmin)(C 1 ) and Succ(C 1 ) = {D 1 , D 2 } • For N 1 = D 1 , we have ρ D 1 = Backward-Induction-ΠDT -lmax(lmin)(D 1 ) and Succ(D 1 ) = {C 2 , C 3 }: -For C 2 , we have ρ C 2 = ConcatAndOrder(π C 2 , ρ LN 1 , ρ LN 2 ) = ((1, 1), 0.9 , 0.1 ) ρ C 2 = 0.9 1 0.1 1 -For C 3 , we have ρ C 3 = ConcatAndOrder(π C 3 , ρ LN 3 , ρ LN 4 ) = ((0.5, 1
), 0.9 , 0.1 )

ρ C 3 = 0.5 0.9 0.1 1 . ⇒ Since ρ C 2 lmax(lmin) ρ C 3 , So ρ D 1 = 0.9 1 0.1 1 and δ(D 1 ) = {D 1 , Sav, C 2 }.

Lexicographic backward induction algorithm in finite-horizon ΠMDPs

The lexicographic variant of the backward induction algorithm, so-called (LexBI-M DP ), (see Algorithm 4.3) performs the optimization of lmax(lmin) (the lmin(lmax) variant is similar) in finite-horizon ΠMDPs.

As in the case of ΠDT s, the comparison of decisions (here, of actions a) is done on the basis of the trajectories they induce, given the decisions made for the future state. To this extent, one memorizes, for each state s for which a decision has been made, the matrix ρ(s) corresponding to the trajectories obtained when the current policy is applied from s. For s ∈ S t , ρ(s) is defined as follows: for lmax(lmin) each line gathers the possibility degrees π(s |a, s) of reaching the following state s ∈ S t+1 , given that δ(s) = a is executed (resp. 1 -π(s |s, a) for lmin(lmax)), combined with a trajectory in the matrix of the next state s . Of course the matrices corresponding to the final states simply contain their utilities. The principle of the backward induction algorithm can be summarized as follows:

• suppose being at period t (e.g. t = h -1). Since the algorithm proceeds backwards, a decision δ(s ) has been made for all future states (the s in S t , t > t). We have to decide • for each state s ∈ S t and each action a ∈ A s we build the matrix M corresponding to trajectories that would be obtained if a was chosen for s, using the ConcatAndOrder procedure described in the previous Section -M is built from π(.|s, a) and from the matrices already computed for the s .

• the matrix M is then compared with the best matrix ρ(s) found so far : if better, a become the current best decision for s (δ(s) ← a) and M becomes the new ρ(s). The lexicographic comparison of matrices is the one described in Section 3.3.1 and is made easier by the fact that the matrices have been ordered on the fly.

• the process is continued for each S t , t = t -1, . . . , 0 (by moving backward in time) until we reach the present time period (t=0) and get an optimal policy. • t=2 (Initialization):

ρ(P &U 2 ) = [0.3], ρ(R&U 2 ) = [0.5], ρ(R&F 2 ) = [0.5].
CHAPTER 4. OPTIMIZING LEXICOGRAPHIC CRITERIA IN ΠDT S AND FINITE-HORIZON ΠMDPS 66

• t=1: S 1 = {R&U 1 , R&F 1 } * s = R&U 1 : A R&U 1 ,1 = {Sav, Adv} and ρ(R&U 1 ) ← [0],
• for a = Sav : M ← ConcatAndOrder((0.2, 1), ρ(P &U 2 ), ρ(R&U 2 ))

= ConcatAndOrder((0.2, 1), [0.3], [0.5]) = 0.5 1 0.2 0.3 .

Since M > lmax(lmin) ρ(R&U 1 ), ρ(R&U 1 ) ← M and δ 1 (R&U 1 ) ← Sav.

• for a = Adv :

M ← ConcatAndOrder((0.4, 1), ρ(R&U 2 ), ρ(R&F 2 ))
= ConcatAndOrder((0.4, 1), [0.5], [0.5]) = 0.5 1 0.4 0.5 .

Thus M > lmax(lmin) ρ(R&U 1 ), ρ(R&U 1 ) ← M and δ 1 (R&U 1 ) ← Adv. * s = R&F 1 , A S R&F 1 ,1 = {Sav} and ρ(R&F 1 ) ← [0],
• for a = Sav :

M ← ConcatAndOrder((1, 1), ρ(R&U 2 ), ρ(R&F 2 )) = ConcatAndOrder((1, 1), [0.5], [0.5]) = 0.5 1 0.5 1 . Since M > lmax(lmin) ρ(R&F 1 ), ρ(R&F 1 ) ← M and δ 1 (R&F 1 ) ← Sav. • t=0: S 0 = {R&U 0 } * s = R&U 0 , A R&U 0 ,0 = {Sav, Adv} and ρ(R&U 0 ) ← [0],
• for a = Sav :

M ← ConcatAndOrder((1, 0.2), ρ(R&U 1 ), ρ(P &U 1 )) = ConcatAndOrder((1, 0.2), 0.5 1 0.4 0.5 , [0.3]) =      0.5 1 1 0.4 0.5 1 0 0.2 0.3 0 0 0.2      . Since M > lmax(lmin) ρ(R&U 0 ), ρ(R&U 0 ) ← M and δ 0 (R&U 0 ) ← Sav. • for a = Adv : M ← ConcatAndOrder((0.4, 1), ρ(R&U 1 ), ρ(R&F 1 )) = ConcatAndOrder((0.4, 1), 0.5 1 0.4 0.5 , 0.5 1 0.5 1 ) =      0.5 1 1 0.5 1 1 0.4 0.5 1 0.4 0.4 0.5      . Since M > lmax(lmin) ρ(R&U 0 ), ρ(R&U 0 ) ← M and δ 0 (R&U 0 ) ← Adv.

67

=⇒ The optimal policy computed by lexicographic backward induction w.r.t. lmax(lmin) is:

δ(R&U 0 )Adv; δ(R&U 1 ) = Adv; δ(R&F 1 ) = Sav.

Complexity analysis

The backwards induction algorithm only makes a polynomial number (in the size of the MDP definition) of calls to the ConcatAndOrder function: there are as many calls to this function as the number of actions in the MDP, which is

h-1 t=1 s∈St |A s |. At each step t, for each state s in S t : for each action in |A s |, b matrices of size b h-t-1 • (h -t -1) are received, Concatenated as a b h-t •(h-t) matrix, ordered -which costs b h-t •(h-t)log(b h-t .(h-t))
and compared with the best matrix found so far -which costs b

h-t •(h-t). Hence a time complexity in U = h-1 t=1 s∈St |A s |• b h-t •(h-t)log(b h-t •(h-t)).
Denote n the (maximal) number of states in S t and a the (maximal) number of actions in

|A s |, we get U = n • a h-1 t=1 b h-t • (h -t) • log(b h-t • (h -t)) i.e. a time complexity in O(n • a • (h -1) 2 • b 2h-2 • log((h -1) • b h-1 )) 1 .
If we consider a constant branching factor, each A s contains b actions which in turn can lead to b non-impossible states. Then we get a time complexity in

O(b 2h • (h -1) 2 • log((h -1) • b h-1 ):
unsurprisingly, it is similar to the one got for ΠDT s. But recall that the DT corresponding to a MDP can be exponential in the size of the MDP.

Bounded backward induction for lexicographic criteria

In fact, lexicographic comparisons, which take into account the whole matrix of subsequent trajectories, overcome the drowning effect but are very costly -exponential in the size of the finite-horizon ΠMDP. On the other hand selecting decisions on the basis of their sole optimistic/pessimistic utility is cheap but not discriminant enough. Hence the idea to restrict the reasoning to a sub-matrix -namely to the first l lines of the matrices of trajectories ρ(s), i.e. π τ vectors of the l most important trajectories (the l best for the optimistic case, the l worst for the pessimistic ones). Bounding the number of columns is not necessary, since the combinatorial explosion in Algorithm 4.3 is due to the number of lines in the matrices (because for the finite horizon, the number of columns is bounded by h+1). Hence we propose the following preference:

δ(s) ≥ lmaxlmin,l δ (s) iff [ρ(s)] l ≥ [ρ (s)] l (4.2)
≥ lmaxlmin,+∞ corresponds to ≥ lmaxlmin .

Proposition 4.1.

Let M be a matrix of trajectories, and l and l be any lines of M such that l > l, then δ lmaxlmin,l δ ⇒ δ lmaxlmin,l δ .

Proof of Proposition 4.1. Note that, for any t ∈ T , s ∈ S t , we have:

[ρ(s)] l =               . . . π(s i |s, a) . . . π(s i |s, a) ρ(s i ) . . .               l Let A be an ordered N × M matrix (w.r.t. lmaxlmin ) s.t. A (i) denotes the line i.
Now, note that, if A and B are two ordered matrices:

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

A (i * ) > lmin B (i * ) .
Clearly, in this case replacing A and B with ρ(s) when considering δ and ρ (s) when considering δ , if such a i * ≤ l exists for a given l, the same i * works for l > l.

Thus, lmaxlmin,l refines lmaxlmin,l .

It is interesting to use this procedure in the backward induction algorithm; that is why we propose a variant of of Algorithm 4.3, which we call "Bounded Lexicographic Backward Induction" (BLex-BI-M DP ) by simply replacing line 14 by line 14':

14 : ρ(s) ← [M ] l
where [M ] l denotes the restriction of M to its first l lines.

Clearly, this algorithm is not guaranteed to provide a lexi-optimal solution, but the policy is always at least as good as the one provided by u opt (according to lmax(lmin)). Indeed, bounding the matrices is done after they have been ordered. Hence M 1,1 is equal to u opt in the unbounded case and because the bounding is done after reordering, this property still holds when using bounded lexicographic backward induction. We deduce that the order on matrices (and thus on policies) refines the one provided by classical optimistic backward induction algorithm. The optimal policy for bounded lexicographic backward induction is optimal for the optimistic utility. Actually, the greater l, the more refined the comparison over the policies. This comparison goes to lmax(lmin) when l goes to b h . The same behavior obviously holds in the pessimistic case: the optimal policy for bounded lexicographic backward induction is optimal for the pessimistic utility and the greater l, the more refined the comparison over the policies and the comparison goes to lmin(lmax) when l goes to b h . Figure 4.3 presents the average execution CPU time for the four criteria, the two optimistic ones (Figure 4.5 (a)) and the two pessimistic ones (Figure 4.5 (a)). We observe that, whatever the optimized criterion, the CPU time increases linearly w.r.t. the number of decision nodes, which is in line with what we could expect. Furthermore, it remains affordable with big trees: the maximal CPU time is lower than 1s for a ΠDT with 5461 decision nodes. It appears that u opt is always faster than lmax(lmin). The same conclusions are drawn when comparing lmin(lmax) to u pes . These results are easy to explain: the manipulation of matrices is obviously more demanding than the one of numbers. As to the success rate, the results are described in Figure 4.4. The percentage of solutions optimal w.r.t. u opt (resp. for u pes ) that are also optimal w.r.t. lmax(lmin) (resp. lmin(lmax)) is never more than 82%, and decreases when the horizon increases: the drowning effect is not negligible and increases with the length of the trajectories.

These experiments conclude in favor of the lexicographic refinements: the longer the horizon the more significant the drowning effect of u opt and u pes . LexBI-DT algorithm computes the optimal solutions even when the horizon increases contrary to the classical BI-DT algorithm.

Experimental results in finite-horizon ΠMDPs

For finite-horizon ΠMDPs, we propose to compare the performance of Bounded Lexicographic Backward Induction, so-called BLex-BI-M DP , as an approximation of (unbounded) Lexicographic Backward Induction (Algorithm 4.3), so-called LexBI-M DP , and also Backward Induction (Algorithm 2.2), so-called (BI-M DP ) for pessimistic and optimistic utilities (u opt and u pes ), in randomly generated finite-horizon ΠMDPs for h = 2 to h = 7. In each stage, the MDP contains 20 states and the number of actions in each state is equal to 4. The output of each action is a distribution on two states randomly drawn (i.e. the branching factor is equal to 2). The utility values are uniformly randomly drawn in the set V = {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}.

Conditional possibilities relative to decisions should be normalized. To this end, one choice is fixed to possibility degree 1 and the possibility degree of the remaining one is uniformly drawn in L. For each value of h, 100 finite-horizon ΠMDPs are generated.

Figure 4.5 presents the average execution CPU time for the three algorithms. We observe that the CPU time increases linearly w.r.t. the horizon for BI-M DP for both u opt (Figure 4.5 (a)) and u pes (Figure 4.5 (b)). It seems to be also the case for BLex-BI-M DP . On the other hand, it increases exponentially for LexBI-M DP .

We also observe that BLex-BI-M DP , with l = 20, is slower than BI-M DP but the CPU time remains affordable, as the maximal CPU time is 5ms for 100 finite-horizon ΠMDPs with 25 states when l = 20 and h = 7. Unsurprisingly, we can check that the BLex-BI-M D is faster than LexBI-M DP especially when the horizon increases: the manipulation of l × (h + 1)-matrices is obviously less expensive than the one of full matrices. The saving increases with the horizon. As to the success rate, the results of the optimistic versions of the algorithms are described in Figure 4.6. The percentage of optimal solutions for u opt that are also optimal for lmax(lmin) when considering the whole matrices is never more than 60%, and decreases when the horizon increases. Indeed, if we take an arbitrary optimistic optimal policy, the higher the problem size the lower its chance of being lexi-optimal. We observe that the drowning effect increases with the length of the trajectories.

It also appears that BLex-BI-M DP provides a very good approximation for reasonable values of l. Of course, the greater l the greater the quality of the approximation. BLex-BI-M DP provides the same optimal solution as the LexBI-M DP in about 80% of cases, with l = 100. Moreover, even when the success rate of BLex-BI-M DP decreases (when h increases), the quality of approximation is still good: never less than 70% of optimal actions returned, with l = 100.

These experiments conclude in favor of bounded lexicographic backward induction: its approximated solutions are comparable with the optimal policy in terms of quality for high l and increase when l increases, while it is much faster than the classical unbounded version.

propose an adaptation of backward induction algorithm in order to optimize these new EU-based refinements. Finally, Section 5.4 is dedicated to the experimental study in order to verify the quality of this latter algorithm comparing to the lexicographic backward induction one.

The main results of this chapter are published in [Ben Amor et al., 2015, Ben Amor et al., 2016a].

EU-refinements in decision trees

In this section we aim to extend the work of [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF], on the refinements of qualitative utilities by expected utilities, to the sequential case i.e. to decision trees.

In order to refine possibilistic utilities in decision trees, we present here two criteria based on infinitesimal expected utilities as refinements of optimistic and pessimistic utilities, in lotteries. Thus we propose to transform the ΠDT into a probabilistic one and then we optimize the probabilistic tree using a backward induction algorithm. The graphical components of the two trees are identical and so are the sets of admissible policies.

EU-refinement of optimistic utility

In the optimistic case the probability and utility distributions are chosen in such a way that the lmax(lmin) and EU criteria do provide the same preference on ∆. To this extent, we build a transformation of the scale L, φ : V ⊆ [0, 1] → [0, 1], that maps each possibility distribution to an additive distribution and each utility level into an additive one; this transformation is required to satisfy the following condition:

(R) : ∀α, α ∈ V such that α > α : φ(α) h+1 > b h φ(α ),
where b is the branching factor of the tree and h its depth. Then, For any chance node C j , a local transformation φ j is then derived from φ, such that φ j satisfies both condition (R) and the normalization condition of probability theory.

Using φ and φ j , we define the two following functions:

• φ -s.t. ∀α ∈ V , φ -(α) = min{φ(α), min j φ j (α))}, • φ + s.t. ∀α ∈ V , φ + (α) = max{φ(α), max j φ j (α))}.
φ -and φ + are required to satisfy the condition:

(R ) : ∀α, α ∈ V such that α > α : φ -(α) h+1 > b h φ + (α ), CHAPTER 5. EXPECTED UTILITY REFINEMENTS IN SEQUENTIAL DECISION-MAKING 76
Then condition (R ) guarantees that if u opt (δ) = α > u opt (δ ) = α , then a comparison based on a sum-product approach on the new tree will also decide in favor of δ.

EU opt denotes the preference relation provided by the EU-criterion on the probabilistic tree obtained by replacing each π j by φ j • π j and the utility function u by φ • u. We show that: Proposition 5.1. If φ satisfies (R) and the derived φ + , φ -satisfy (R'), then EUopt refines uopt .

Proof of Proposition 5.1.

For any transformation function

φ s.t. ∀(α, α ) ∈ V, α > α it holds that (R) : φ(α) h+1 > b h φ(α ). Note that, by definition, φ + (α) ≥ φ(α) ≥ φ -(α), ∀α ∈ V . Thus, by (R'), φ -(α) h+1 > b h φ + (α ) ≥ b h φ -(α ), ∀(α, α ) ∈ V, α > α .
Let δ and δ be two strategies. Assume that u opt (δ) = α > u opt (δ ) = α and let us show that EU opt (δ) > EU opt (δ ).

• u opt (δ) = α ⇒ ∃τ * = (π j 0 (x i 1 ), . . . , π j h-1 (x i h ), u(x i h )) in δ s.t. min(π j 0 (x i 1 ), . . . , π j h-1 (x i h ), u(x i h )) ≥ α. Since EU opt (δ) = τ ( h k=1 φ k (π j k-1 (x i k )) * φ(µ(x i k ))
) and all terms of the sum are positive or zero, by keeping only trajectory τ * in the sum, we get:

EU opt (δ) ≥ h k=1 φ k (π j k-1 (x i k )) * φ(µ(x i k )) ≥ h k=1 φ k (α) * φ(α). Since 1 φ -(α) ≤ φ k (α), ∀k, ∀α ∈ L, EU opt (δ) ≥ h k=1 φ -(α) * φ(α). Then, since φ -(α) ≤ φ(α), EU opt (δ) ≥ h k=1 φ -(α) * φ -(α)
. Thus, we get:

EU opt (δ) ≥ φ -(α) h+1
(5.1)

• u opt (δ ) = α ⇒ ∀τ, min(π j 0 (x i 1 ), . . . , π j h-1 (x i h ), u(x i h )) ≤ α .
Let us denote EU τ the term of EU opt (δ ) corresponding to trajectory τ . We have

EU τ ≤ h k=1 φ k (α ) * φ(α ) ≤ h k=1 φ + (α ) * φ(α ) ≤ h k=1 φ + (α ) * φ + (α ), since φ + (α ) = max {φ(α ), max k φ k (α )} , ∀α ∈ V . Then, EU τ ≤ φ + (α ) h+1 ≤ φ + (α ) since 0 ≤ φ + (α ) ≤ 1. Since δ generates at most b h trajectories, EU opt (δ ) ≤ b h EU τ and EU opt (δ ) ≤ b h .φ + (α ).
(5.2)

1 Recall that φ -(α) = min {φ(α), min k φ k (α)} . CHAPTER 5. EXPECTED UTILITY REFINEMENTS IN SEQUENTIAL DECISION-MAKING 77
Finally, using (5.1), (5.2) and (R ), we get u opt (δ) > u opt (δ ) ⇒ EU opt (δ) > EU opt (δ ).

Proposition 5.2.

δ lmax(lmin) δ iff δ EUopt δ , ∀(δ, δ ) ∈ ∆.
Proof of Proposition 5.2.

For the sake of notational simplicity, we will associate any trajectory τ (resp. τ ) with the vector τ Ord (resp. τ Ord ) consisting in reordering (π 1 , . . . , π h , u h ) (resp. (π 1 , . . . , π h , u h )) in increasing order.

Obviously, τ lmin τ iff τ Ord lmin τ Ord . Note that δ lmax(lmin) δ iff either

1. ∀i, τ λ(i) ∼ lmin τ λ(i) or 2. ∃i * , ∀i ≤ i * , τ λ(i) ∼ lmin τ λ(i) and τ λ(i * ) lmin τ λ(i * ) . ∀ α k ∈ τ Ord (resp. α k ∈ τ Ord ) s.t. k = 1, h + 1
, note the following facts concerning pairs of trajectories (τ, τ ):

1. τ ∼ lmin τ ⇔ h+1 k=1 φ(α k ) = h+1 k=1 φ(α k ), since τ ∼ lmin τ ⇔ τ Ord ∼ lmin τ Ord . Then: δ ∼ lmax(lmin) δ ⇔ τ λ(i) ∼ lmin τ λ(i) , ∀i. ⇒ t ( h+1 k=1 φ(α k )) = t ( h+1 k=1 φ(α k )) ⇔ EU opt (δ) = EU opt (δ ). Thus δ ∼ lmax(lmin) δ ⇔ EU opt (δ) = EU opt (δ ).
2. if δ > lmax(lmin) δ , then ∃i * s.t. τ λ(i * ) lmin τ λ(i * ) , then ∃j * , ∀j < j * , α j = α j and α j * > α j * . Then, let us compare the product of transformed possibilities/utilities along τ and τ :

h+1 k=1 φ(α k ) φ(α k ) = h+1 k=j * φ(α k ) φ(α k ) ≥ φ(α j * ) φ(α j * ) * φ(α j * ) h-j * φ(φ(1 V ) h-j * )
(5.3) (lower and upper bounds on trajectories degrees)

≥ φ(α j * ) h-j * +1 φ(α j * ) (φ(1 V ) ≤ 1) ≥ φ(α j * ) h φ(α j * ) (φ(α j * ) ≤ 1) > b h . (From R) CHAPTER 5. EXPECTED UTILITY REFINEMENTS IN SEQUENTIAL DECISION-MAKING 78
Then, since trajectories are ordered along lmax(lmin) , τ λ(i * ) lmin τ λ(i) , ∀i > i * , and since there are no more than b h such trajectories τ λ(i) , we get that EU opt (δ) > EU opt (δ ).

Thus δ lmax(lmin) δ ⇒ EU opt (δ) > EU opt (δ ).

So, we have just proved that δ lmax(lmin) δ ⇒ δ EUopt δ . Thus, lmax(lmin) is equivalent to EUopt .

Example 5.1. We illustrate in the following an example of transformation of the decision tree of Figure 5.1 with h = b = 2.

First, let us build a function φ satisfying (R'). For this purpose, it is sufficient to construct the function φ : V → R as follows : Applying this function φ on the scale V = {0, 0.1, 0.4, 0.5, 0.8, 0.9, 1} we obtain:

φ(1 V ) = 1, φ(α i ) < φ(α i+1 ) 3 4 (if V = 1 V , α 1 , . . . , α k = 0 V ).

Sav

• φ(1) = 1,

• φ(0.9) = 0.2,

• φ(0.8) = 0.001,

• φ(0.5) = 10 -10 ,

• φ(0.4) = 10 -30 ,

• φ(0.1) = 10 -91 .

We obtain the transformed probabilistic decision tree of Figure 5.2, by normalizing the transformed conditional distributions obtained in each node. For instance:

• for node C 1 =      φ 1 (10 -30 ) = 10 -30
1+10 -30 , and

φ 1 (1) = 1 1+10 -30 . • for node C 2 =      φ 2 (1) = 1 1+1 ,

EU-refinement of pessimistic utility

In what follows, we focus on the pessimistic case. Consider the lmin(lmax) comparison, the utility degrees are not directly compared to possibility degrees π but to degrees 1 -π. Hence, it is possible to show that:

Proposition 5.3.

Let DT inv the tree obtained from DT by using utility function u = 1 -u on leaves. It holds that: u pes,DT (δ) ≥ u pes,DT (δ ) iff u opt,DT inv (δ ) ≥ u opt,DT inv (δ)

Proof of Proposition 5.3. Let L δ (resp. L δ ) be the equivalent simple lottery of the compound lottery representing the strategy δ. L δ = π 1 /u 1 , ..., π i /u i , ..., π p /u p (resp. L δ = π 1 /u 1 , ..., π i /u i , ..., π p /u p ) i.e.

π i = π(u i ) (resp. π i = π(u i ))
is the possibility that the strategy leads to the outcome utility u i (resp. u i ).

Let us show that u pes,DT (δ) ≥ u pes,DT (δ ) ⇔ u opt,DT inv (δ) ≤ u opt,DT inv (δ ) where u pes,DT (δ) denotes the pessimistic utility of δ when considering the original decision tree DT and u opt,DT inv (δ) denotes the optimistic utility of δ when considering the decision tree DT inv , obtained from DT by using utility function u = 1 -u.

We have, u pes,DT (δ) ≥ u pes,DT (δ ) ⇔ u pes,DT (L δ ) ≥ u pes,DT (L δ ).

It has been shown in [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF] that:

u pes,DT (L δ ) ≥ u pes,DT (L δ ) ⇔ u opt,DT inv (L δ ) ≥ u opt,DT inv (L δ ).
Hence, we deduce that: u opt,DT inv (δ ) ≥ u opt,DT inv (δ).

As a consequence, we build an EU-based equivalent of lmin(lmax) , denoted by EUpes , by replacing each possibility distribution π i in DT by the probability distribution φ i • π i , as for the optimistic case and each utility degree u byφ(1) -φ(u). It is then possible to show that: Proposition 5.4. δ lmin(lmax) δ iff δ EUpes δ , ∀(δ, δ ) ∈ ∆.

Proof of Proposition 5.4. It is sufficient to show that:

δ DT lmax(lmin) δ ⇔ δ DT inv lmin(lmax) δ, (5.4)
where DT inv lmin(lmax) is the pessimistic lexicographic comparison of strategies in the decision tree where the utilities of all leaves have been reversed (u (N ) = 1 -u(N )).

For any two strategies δ and δ :

• if δ DT lmax(lmin) δ then ∃i * , ∀i ≤ i * , τ λ(i) ∼ lmin τ λ(i) and τ λ(i * ) lmin τ λ(i * ) ⇔ (π 1 , . . . , π h , u h ) lmin (π 1 , . . . , π h , u h ).
Now let invert each degree in both trajectories, we get:

((1 -π 1 ), . . . , (1 -π h ), (1 -u h )) ≺ lmax ((1 -π 1 ), . . . , (1 -π h ), (1 -u h ))
• When each chance node is reached, an optimal sub-strategy is built for each of its children:

the EU of each sub-strategy is returned and the probability degree of having this children is computed, it is simply the probability in V p that matches π N (Y i ) the possibilistic degree of having Y i in chance node N . We also update the sum of the probability degrees in this chance node (we will use it for normalizing the probability distribution). Then it is possible to compute the expected utility of the current chance node: the sum-product of the normalized probability of each children and the corresponding expected utility in next stage.

• When a decision node N is reached, a decision δ(N ) leading to a sub-strategy optimal is selected among all the possible decisions C j ∈ Succ(N ), by compared the expected utility of each sub-strategy.

Algorithm 5.1: EU -BI: Backward-Induction-DT -EU(N :Node) Data: A probabilistic DT ; the policy, δ, is memorized as global variable Result: Set δ for the tree rooted in N and returns its expected utility In a perfect world, the lexicographic approach and the big-stepped EU one solve the problem in the same way and provide the same optimal policies -the difference being that the lexicographic backward induction is based on the comparison of matrices and the EU-backward induction is based on the computation of expected utilities in R + . The point is that the latter handles very small numbers; then either the program is based on an explicit handling of infinitesimals, and proceeds just like the matrix-based comparison, or it lets the programming language handle these numbers in its own way -and, given the precision of the computation, provides approximations.

1 begin 2 V p ← transf orm(V, b, h) 3 // Leaves 4 if N ∈ N U then EU ← u Vp (N ); 5 // Chance nodes 6 if N ∈ N C then 7 k ← |Succ(N )|; 8 foreach Y i ∈ Succ(N ) do 9 EU i ← Backward-Induction-DT -EU (Y i ); 10 p i ← π Vp (Y i ); 11 Sum ← Sum + p i ; 12 EU ← i=1,k ((p i /Sum) × EU i );

Experimental study

In this Section we propose to compare the lexicographic criteria, and the EU approximations presented in the previous section. We compare the 2 variants of algorithms with two measures: the CPU time and the pairwise success rate (Success A B where A and B are two decision criteria). We use the same experimental data of Chapter 4: 100 complete binary decision trees, for h = 2 to h = 7, that are randomly generated.

The backward induction algorithms corresponding to the optimistic and pessimistic criteria have been implemented in Java. As to the EU-based approaches, the transformation function depends on the horizon h and the branching factor b (here b = 2). We used φ(1 V ) = 1, and

φ(α i ) = φ(α i+1 ) h+1 b h * 1.1 .
Tables 5.1 and 5.2 present the execution CPU time of the proposed algorithms for respectively the optimistic criteria and the pessimistic criteria. Clearly, u opt is always faster than EU opt , which is 1.5 or 2 times faster than lmax(lmin) The same conclusion is drawn when comparing lmin(lmax) to u pes and EU pes . These results are easy to explain: (i) the manipulation of matrices is obviously more expensive than the one of numbers and (ii) the handling of numbers by min and max operations is faster than sum-product manipulations of very small numbers (infinitesimal). Results relative to the success rate are presented in Figure 5.3. We can see that EU opt (resp. EU pes ) performs well, as an approximation of lmax(lmin) (resp. lmin(lmax)), indeed the percentage of solutions optimal for the former which are also optimal for the latter is greater than 65% in all cases, it is about 80% for h = 3 but it decreases when h increases. This is easily explained by the fact that the probabilities are infinitesimals and converge to 0 when the length of the branches (and thus the number of factors in the products) increases. These experiments conclude in favor of the lexicographic refinements in their full definition. When space and time are limited (or when h increases), it is interesting to use their approximations by expected utilities: they are better in terms of CPU time average and comparable in terms of average accuracy, but note that we lose about 20% of precision. The expected utilities criteria, nevertheless, are more decisive than possibilistic utilities (u opt and u pes ), in all cases, and they are as fast as these latter.

Summary

This Chapter is devoted to the extension of the work of [START_REF] Fargier | Qualitative decision under uncertainty: Back to expected utility[END_REF]] on the refinement of the qualitative utilities by the expected utility to the case of the sequential decision. This refinement allows to establish a link between the possibilistic decision trees and probabilistic decision trees. The calculation of optimal policies by the refined expected utility can then be done by a backward induction algorithm, on the probabilistic transformed tree.

In the context of MDPs, the comparison of policies of a ΠMDP can be refined using the same method. The decision tree corresponding to the MDP is constructed; the trajectories of the MDP and those of the decision tree are in bijection. The rewards obtained in step h -1 are associated to the leaves of the tree. Then, it is possible to transform this decision tree using the same φ satisfying φ(α) h+1 > b h+1 φ(α ). The optimistic utility of a ΠMDP policy is equal to its utility in the decision tree. For instance, if δ uopt δ in the possibilistic MDP, δ uopt δ in the decision tree, and thus δ EUopt δ which implies δ EUopt δ in the MDP.

The next Chapter focuses on the optimization of stationary MDPs w.r.t. lexicographic criteria. We propose solving algorithms, based on the value iteration algorithm, to handle the finitehorizon case as well as the infinite-horizon case.

Refresher on stationary possibilistic Markov decision processes

Before describing optimizing algorithms in detail, we recall some definitions from Chapter 2 and 3 on stationary ΠMDP and the basic notions of lexicographic criteria in this framework.

• Stationary ΠMDP is defined by:

-A finite set S of states.

- In this model the states, the actions and the transition functions do not depend on the stage of the problem.

• Given a stationary ΠMDP with horizon h, we can associate to any of its trajectories τ = (s 0 , a 0 , s 1 , . . . ,

s h-1 , a h-1 , s h ) the vector v τ = (u 0 , π 1 , u 1 , π 2 , . . . , π h-1 , u h ).
Different trajectories can be compared using lexicographic comparisons (Equation 3.3 and 3.3) as follows:

τ lmin τ iff (u 0 , π 1 , u 1 , . . . , π h , u h ) lmin (u 0 , π 1 , u 1 , . . . , π h , u h ) τ lmax τ iff (u 0 , 1 -π 1 , u 1 , . . . , 1 -π h , u h ) lmax (u 0 , 1 -π 1 , u 1 , . . . 1 -π h , u h )
The lexicographic criteria on policies are then defined by:

δ lmax(lmin) δ iff ∀i, τ λ(i) ∼ lmin τ u(i) or ∃i * , ∀i < i * , τ λ(i) ∼ lmin τ λ(i) and τ λ(i * ) lmin τ λ(i * ) δ lmin(lmax) δ iff ∀i, τ σ(i) ∼ lmax τ σ(i) or ∃i * , ∀i < i * , τ σ(i) ∼ lmax τ σ(i) and τ σ(i * ) lmax τ σ(i * )
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 .

• The complementary ΠMDP, of a given ΠMDP (S, A, π, u), is defined by (S, A, π, ū) where ū(s) = 1 -u(s), ∀s ∈ S. It simply gives complementary utilities. From the definitions of lmax and lmin and using Proof of Proposition 5.4, we can check that:

τ lmax τ ⇔ τ lmin τ and δ lmin(lmax) δ ⇔ δ lmax(lmin) δ
where τ and δ are obtained by replacing u with ū in the trajectory/ΠMDP.

Therefore, all results which we will prove in the following for lmax(lmin) also hold for lmin(lmax) , if we take care to apply them to complementary strategies. Since considering lmax(lmin) involves less cumbersome expressions (no 1 -•), we will give the results for this criterion.

Lexicographic value iteration for finite-horizon stationary ΠMDPs

We propose, in the following, a value iteration algorithm for the computation of lexicographic optimal policies in the finite-horizon stationary ΠMDPs.

Fixed-horizon lexicographic value iteration

It is possible propose a Lexicographic Value Iteration Algorithm, denoted Lex-V I, (Algorithm 6.1 for the lmax(lmin) variant; the lmin(lmax) variant is similar) that computes a lexicographic optimal policy in a finite number of iterations. This algorithm is an iterative procedure that updates the utility of each state, represented by a finite matrix of trajectories, using the utilities of the neighboring states, until a halting condition is reached.

At stage t, the procedure updates the utility of any states s ∈ S as follows:

• For each a ∈ A s , a matrix Q(s, a), that evaluates the "utility" of performing a in s at stage t, is built by a call to obtained by calling ConcatAndOrder-S( π, u, {ρ 1 , . . . , ρ k }), outlined by Algorithm 6.2. This function combines the possibility π(s |s, a) and the utilities u(s ), of the states s that may follows s when a is executed, with the matrices U t-1 (s ) of trajectories provided by these s . The obtained matrix is then ordered.

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

• The value of s at t, U t (s), is the one given by the action δ t (s) = a which provides the best Q(s, a). U t and δ t are memorized (and U t-1 can be forgotten). Example 6.1. The main steps for the evaluation of the finite-horizon stationary ΠMDP (see Figure 6.1) of Counter-example 3.4 using lexicographic value iteration (Algorithm 6.1) w.r.t. lmax(lmin) criterion are as follows.

if Q * ≤ lmaxlmin Q(s, a) then 14 Q * ← Q(s, a); 15 δ t (s) ← a 16 U t (s) ← Q * 17 until t == h; 18 δ * (s) ← argmax a Q(s,
(b • b h • (2 • h + 1) • log(b h • (2 • h + 1))) = O(b h • log(b h )).
• We have:

-S = {R&U, R&F, P &U }, for a = Adv: Future = 0.7 0.7 1 0.5 0.5 1 , Q(R&U, Adv) = ConcatAndOrder-S( π = (1), u = (0.7), 0.7 0.7 1 0.5 0.5 1 ) = 0.7 0.7 1 1 0.5 0.5 0.7 1 .

→ Since Q(R&U, Adv) lmax(lmin) Q(R&U, Sav), so δ 2 (R&U ) = Adv and U 2 (R&U ) = 0.7 0.7 0.7 1 1 0.5 0.5 0.7 1 1 .

* for s = R&F

Bounded lexicographic value iteration

We have seen that making the choices based on the qualitative utility functionals is not discriminant enough. Note that, at any stage t and for any state s, [U t (s)] 1,1 (i.e. the top left value in U t (s)) is precisely equal to u opt (s) at horizon t for the optimal policy. on the other hand, taking the whole matrix is discriminant, but exponentially costly (O(|S|

• |A| • |h| • b h • log(b h )).
Hence we propose to consider more than one line and one column, but less than the whole matrix -namely the first l lines and c columns of the ordered matrix U t (s); hence the definition of the following preference:

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

The combinatorial explosion in Algorithm 6.1 is due to the number of lines only, because at finite horizon, the number of columns is bounded by 2 • h + 1. Hence we should bound the number of considered lines. The following proposition shows that this approach is sound: Proposition 6.1. (Refinement relations)

• For any l, c, l such that l > l, δ lmaxlmin,l,c δ ⇒ δ lmaxlmin,l ,c δ .

• For any l, c, δ opt δ ⇒ δ lmaxlmin,l,c δ . Proposition 6.1 means that lmaxlmin,l,c refines u opt and the order over the policies is refined for a fixed c when l increases. It tends to lmaxlmin when c = 2.h + 1 and l tends to b h . Proof of Proposition 6.1. In order to make the proofs more explicit and compact, let us introduce the following notations and operations defined on matrices of trajectories (typically, on U (s) representing trajectories issued from s).

• Composition operation denoted ⊗:

U ⊗ (N 1 , . . . , N a ): 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 , . . . , 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 ) is the concatenation of the i th line of U and the j th line of N i . The matrix U (s) is typically the concatenation of the matrix U = ((π(s |s, a), u(s )), s ∈ succ(s, a)) with the matrices N s = U (s ).

• Combination operation denoted ⊕: U ⊕ V : Let U be a a ⊗ b matrix and V be a n ⊗ b matrix. The combination of U with V is the matrix

W = U ⊕ V of dimension (a + n) × b s.t. ∀ i ∈ {1..(a + n)}, ∀ j ∈ {1..b}: W i,j =      U i,j if i ∈ {1..a}, V (i-a),j if i ∈ {(a + 1)..(a + n)}.
• Ordering operation: Let U be a n × m matrix, U lmaxlmin is the matrix obtained by the operation lmax(lmin): ordering the elements of the lines of U in increasing order and the lines of U according to lmax (in decreasing order).

ConcatAndOrder-S function is simply defined as follows:

ConcatAndOrder-S( π, u, {ρ 1 , . . . , ρ k }) = (π, u) ⊗ (ρ 1 , . . . , ρ k ) = (((π 1 , u 1 ) ⊗ ρ 1 ) ⊕ ... ⊕ ((π k , u k ) ⊗ ρ k )).
Let us now give the Proof of Proposition 6.1:

• 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 y -x 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. 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.2. (Concatenation of reduced matrices of trajectories) 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 .
Proof of Proposition 6.2. 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:

(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 ,
Now, using Fact 1 again, in the other direction of the equality: We can safely replace the inner N lmaxlmin i matrices with their sub-matrices

(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
N lmaxlmin i l,c
and get the result.

In summary, the idea of our Algorithm, that we call Bounded Lexicographic Value Iteration (BLex-V I), see Algorithm 6.3, is to compute policies that are close to lexi-optimality, by keeping a sub matrix of each current value matrix -namely the first l lines and c columns.

Following the complexity analysis of Algorithm 6.1, the time complexity of (BLex-V I) is:

O(|S| • |A| • |h| • b • (l • c) • log(l • c)).
Hence, this algorithm provides in in polynomial time a policy that is always as least as good as the one provided by u opt (according to lmax(lmin)) and tends to lexicographic optimality when c = 2 • h + 1 and l tends to b h . Algorithm 6.3: BLex-V I: Bounded-lmax(lmin)-Value Iteration Data: A stationary ΠMDP and an horizon h δ * , the policy built by the algorithm, is a global variable 1 // δ a global variable starts as an empty set

Result: Computes and returns δ * for ΠMDP 2 begin 3 t ← 0; s,a)); // Gather the matrices provided by the successors of s;

4 foreach s ∈ S do U t (s) ← ((u(s))); 5 foreach s ∈ S, a ∈ A s do T U s,a ← T s,a ⊗ ((u(s )), s ∈ succ(s, a)) ; 6 repeat 7 t ← t + 1; 8 foreach s ∈ S do 9 Q * ← ((0)); 10 foreach a ∈ A do 11 F uture ← (U t-1 (s ), s ∈ succ(
12 Q(s, a) ← [ConcatAndOrder-S( π, u, F uture)] l,c ; 13 if Q * ≤ lmaxlmin Q(s, a) then 14 Q * ← Q(s, a); 15 δ t (s) ← a 16 U t (s) ← Q * 17 until t == h; 18 δ * (s) ← argmax a Q(s, a)
19 return δ * ;

Experimental study

In this Section, we compare the performance of Bounded lexicographic value iteration so-called BLex-V I (Algorithm 6.3) as an approximation of (unbounded) lexicographic value iteration socalled Lex-V I (Algorithm 6.1), in the lmax(lmin) variant.

We evaluate the performance of the algorithms by carrying out simulations on randomly generated stationary ΠMDP with |S| = 25. The number of actions in each state is equal to 4. The output of each action is a distribution on two states randomly drawn (i.e. the branching factor is equal to 2). The utility values are uniformly randomly drawn in the set L = {0.1, 0.3, 0.5, 0.7, 1}. Conditional possibilities relative to decisions should be normalized. To this end, one choice is fixed to possibility degree 1 and the possibility degree of the other one is uniformly drawn in L. For each experience, 100 stationary ΠMDP are generated.

The two algorithms are compared w.r.t. 2 measures: (i) CPU time and (ii) Pairwise success rate (the same of the previous experiments): here it presents the percentage of optimal solutions provided by Bounded value iteration with fixed (l, c) w.r.t. the lmax(lmin) criterion in its full generality. The higher Success, the more important the effectiveness of cutting matrices with BLex-V I; the lower this rate, the more important the drowning effect. Figure 6.2 presents the average execution CPU time for the two algorithms. Obviously, for both Lex-V I and BLex-V I, the execution time increases with the horizon. Also, we observe that the CPU time of BLex-V I increases according to the values of (l, c) but it remains affordable, as the maximal CPU time is lower than 1s for stationary ΠMDPs with 25 states and 4 actions when (l, c) = (40, 40) and h = 25. Unsurprisingly, we can check that the BLex-V I (regardless of the values of (l, c)) is faster than Lex-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 Figure 6.3. It appears that BLex-V I provides a very good approximation especially when increasing (l, c). It provides the same optimal solution as the Lex-V I in about 90% of cases, with an (l, c) = (200,200). So, the bigger the matrices the more efficient is the approximation, and the smaller the matrices the further the drowning effect is present. Moreover, even when the success rate of BLex-V I decreases (when h increases), the quality of approximation is still good: never less than 70% of optimal actions returned, with h = 25.

These experiments conclude in favor of bounded lexicographic value iteration: its approximated solutions are comparable in terms of quality for high (l, c) and increase when (l, c) increase, while it is much faster than the unbounded version. In the infinite-horizon case, the comparison of matrices of trajectories does not apply to rank-order the policies. The length of the trajectories may be infinite, and also their number infinite as well.

This problem is well known in classical probabilistic MDPs where a discount factor is used that attenuates the influence of later utility degrees -thus allowing the convergence of the solving algorithm (value iteration or policy iteration) [Puterman, 1994]. On the contrary, classical ΠMDPs, proposed by [Sabbadin, 2001], do not need any discount factor. Indeed, the limitation of u opt and u pes to one number as a utility of a policy (i.e. l = c = 1) plays the role of a discount factor and possibilistic Value Iteration (see Algorithm 2.3), based on the evaluation of qualitative utilities, converges for infinite horizon ΠMDPs [Sabbadin, 2001]. However, decide using u opt and u pes (based on the first element of the matrix) is too drastic; it is nevertheless possible to make the comparison using ≥ lmaxlmin,l,c with l, c > 1. Thus, we propose below a Bounded Lexicographic Value Iteration algorithm for infinite-horizon stationary ΠMDPs, denoted BLex-IH-V I (see Algorithm 6.4). This algorithm converges when from a given stage t, the value of a policy is stable if computed with the bounded lmax(lmin) criterion. Let us denote U t (s) the matrix issued from s at horizon t when δ is executed, it holds that: Proposition 6.3. (Convergence of Bounded lexicographic value iteration) ∀ l, c, ∃ t such that, ∀ t ≥ t, (U t ) lmaxlmin l,c (s) = (U t ) lmaxlmin l,c (s) ∀s. Hence, bounded lexicographic value iteration converges for infinite-horizon stationary ΠMDPs.

Proof of Proposition 6.3. In, bounded 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 > can be maintained for every trajectory.

As t increases all (v i,α t ), which are non-decreasing sequences, converge toward a finite or infinite limit. We let lim(i, α) = def lim t→∞ (v i,α t ), s.t. lim(i, α) ∈ N ∪ {+∞}, ∀ τ i t , α.

Thus, if we denote by U i , the limit of the line vector in U t (s) corresponding to trajectory τ i t when t goes to infinity, we have:

U i =  

Summary

In this Chapter, we have studied the lexicographic optimization of policies in stationary possibilistic Markov decision processes.

First, considering finite-horizon stationary possibilistic Markov decision processes, we have proposed a lexicographic value iteration algorithm for the computation of lexicographic optimal policies, based on the whole matrices of trajectories. Since this algorithm is computationally expensive, we have proposed a bounded lexicographic value iteration algorithm as an approximation of the full lexicographic procedure. The principle of this algorithm is to forget the less useful part of the matrix of trajectories and to decide based on the best part i.e. the (l, c) sub-matrix. When we fix the size of the matrices, the complexity of the algorithm becomes polynomial. We have compared the bounded lexicographic algorithm and the classical lexicographic one on randomly generated problems with different horizons and different values of (l, c). It appears that the bounded variant is an interesting algorithm: it is very fast and it provides a good approximation, with large (l, c).

For the infinite-horizon case, using the classical lexicographic value iteration algorithm, the matrices of trajectories increase infinitely. Hence, we use the same idea of bounding matrices and the only thing that changes is the condition of convergence, since we do not know the number of iteration in advance. Moreover, we have proved that, using this algorithm, the complexity remains polynomial in (l, c), even when the horizon is infinite. Note that it is possible to extend this work to the pessimistic case, so we compute the pessimistic utility of each trajectory and compare these utilities using lmin(lmax) criterion whereas lmax(lmin).

CONCLUSION General conclusion

The contributions of this thesis are mainly related to the preliminary works of Fargier et Sabbadin [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF]. They have proposed refinements of optimistic and pessimistic qualitative utilities using a special form of classical expected utility equivalent to qualitative lexicographic ordering. The main objective of our work was to extend these criteria for the sequential decision-making framework.

The problematic of this work, exposed in Chapter 3, is how to overcome the drowning effect of qualitative utilities when comparing policies. Therefore, we have proposed two lexicographic criteria that compare policies based on their corresponding matrices of trajectories. These comparisons satisfy the principle of efficiency and strict monotonicity. These properties allow us to define lexicographic backward induction algorithms for possibilistic decision trees and for the finite-horizon possibilistic Markov decision processes. We have proved that, for the two sequential models, the lexicographic algorithms are discriminant and avoid the drowning effect of classical possibilistic algorithms. The algorithms proposed are polynomial in the size of the model and allow to get an optimal discriminant policy. But the matrices of trajectories grow exponentially with the horizon, so it is possible to bound the number of lines and to decide only using the bounded part of the matrices. Hence, we propose a bounded version of the lexicographic backward induction which has polynomial complexity in the horizon and the number of lines and columns of the bounded matrices. Then, we have experimentally compared the lexicographic algorithms (the two version) proposed and the classical possibilistic algorithms. It appears that the backward induction algorithm with bounded matrices is fast and provides very good approximations, especially when the number of lines kept is high. This approximation algorithm has been extended (in Chapter 6) to stationary possibilistic Markov decision processes that have intermediate utilities, when the horizon is finite or infinite.

On the theoretical side, we have proved that lexicographic criteria encode expected utility criteria based on the transformation of the possibilistic model to probabilistic one, using big stepped probabilities.

As short term future work, various algorithmic extensions should be concerned such as:

• We may think about the adaptation of the classical Possibilistic Policy Iteration algorithm (see Algorithm 2.4) [Sabbadin, 2001] for the lexicographic procedures, which is not too difficult to realize

• In addition, 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 consider only those which are observed.

• The next step is obviously to develop simulation-based algorithms for finding lexicographic solutions in Markov decision process. Reinforcement Learning algorithms [START_REF] Sutton | Reinforcement Learning:An Introduction[END_REF]] allow to solve large size (probabilistic) Markov decision process by making use of simulated trajectories of states to optimize a strategy. It is not immediate to develop reinforcement learning algorithms for possibilistic Markov decision processes, since no unique stochastic transition function corresponds to a possibility distribution. However, uniform simulation of trajectories (with random choice of actions) may be used to generate an approximation of the possibilistic decision tree (provided that both transition possibilities and utility of the leaf are given with the simulated trajectory). So, interleaving simulations and lexicographic dynamic programming may lead to reinforcement learning-type algorithms for approximating lexicographic-optimal policies for (large) possibilistic Markov decision processes. Such algorithms would use samplings of the trajectories instead of full dynamic programming or quantile-based reinforcement learning approaches [START_REF] Gilbert | Quantile reinforcement learning[END_REF].

The work presented in this thesis has answered several questions concerning discriminant policies in sequential decision-making models. It thus opened up many promising research tracks:

• The axiomatization of the lexicographic criteria is possible and it may be envisaged in further research. It would consist in the VNM axioms of rational decision since our work is more close to lotteries framework and that we do not use the reduction of lotteries.

• In [Weng, 2005], Weng has proposed a refinement of binary possibilistic utilities (BPU) and as a particular case, to classical, optimistic and pessimistic, possibilitistic utilities. This refinement allows to improve the discrimination power of BP U . But since in [Weng, 2005] treatment indeed, two similar trajectories of the same strategy are merged, the resulting criterion thus suffers from a drowning effect and does no satisfy strict monotonicity: as such, it cannot be represented by an EU-based criterion which "counts" trajectories (weighted by their probabilities). We actually do refine [Weng, 2005]'s criterion. Incorporating our lexicographic refinements in BP U would lead to a more powerful refinement and suggest a probabilistic interpretation of efficient BP U . It also leads to new algorithms that are more discriminant than their original counterparts.

• Another problem remains open: how to refine the coarse ranking produced by Sugeno integral, especially when we consider sequential decision problems ? [START_REF] Dubois | Lexicographic refinements of sugeno integrals[END_REF] proposes to use a mapping from the qualitative scale (of both utility and uncertainty) to the reals, hence, Sugeno integral may be refined by a Choquet integral. In our opinion, the extension of this work to sequential decision-making is a complicated task: first we have to define what is it a Sugeno of a matrix of trajectories and how we calculate the Sugeno of a compound lottery (or a policy). Then, we have to decide which solving algorithm shall be used (dynamic programming, branch and bound, etc.), it depends on the axioms and properties of the new refined criterion (Choquet integral or another one). Note that [START_REF] Dubois | Lexicographic refinements of sugeno integrals[END_REF]'s refined criterion of Sugeno integral is not yet axiomatized.

• Another line of research is to consider collective decision-making under possibilistic uncertainty [START_REF] Amor | Egalitarian collective decision making under qualitative possibilistic uncertainty: Principles and characterization[END_REF], Ben Amor et al., 2015a]. In fact, since it is based on optimistic and pessimistic possibilistic utilities, it suffers from a lack of decisiveness. So, it is interesting to look for collective lexicographic decision rules as an efficient counterpart of collective qualitative ones, in order to found discriminant decisions, which satisfies the collectivity, in sequential decision-making models such as possibilistic decision trees and possibilistic Markov decision processes.

• Finally, our lexicographic approach is may be useful for optimizing policies in other possibilistic variants of sequential decision models, such as Partially Observable Markov Decision Processes (POMDPs) and Factored Markov Decision Processes (FMDPs). One may also think about adapting the lexicographic criteria to possibilistic planning problems that can be used to search optimal plan or a plan that lead to a goal state [START_REF] Da | Possibilistic planning: Representation and complexity[END_REF]. Note that, the integration of the discriminative lexicographic criteria is interesting but it eventually makes these problems more complex.

  Contents 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Decision-making under probabilistic uncertainty . . . . . . . . . . . 5 1.3 Possibilistic decision theory . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Limitations of possibilistic qualitative utilities . . . . . . . . . . . . . 16 1.5 Refinements of possibilistic qualitative utilities . . . . . . . . . . . . 17 1.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Figure 1

 1 Figure 1.1: A possibilistic compound lottery L (a) and its reduction L (b)

  Contents 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2 Possibilistic decision trees (ΠDT s) . . . . . . . . . . . . . . . . . . . 25 2.3 Possibilistic Markov Decision Processes (ΠMDPs) . . . . . . . . . . 30 2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

  and

Figure 2

 2 Figure 2.1: The ΠDT of Example 2.1

Figure 2

 2 Figure 2.2: The finite-horizon ΠMDP (h = 2) of Example 2.3

  Algorithm 2.3: V I-M DP : Possibilistic (Optimistic) Value iteration Data: A stationary ΠMDP Result: Computes and returns an optimal policy δ 1 begin 2 foreach s ∈ S do 3 u opt (s) ← u(s) a) ← 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 Q converges to Qopt ; 11 // Q is epsilon close to Qopt 12 return δ; 2.3.2.3 Optimization of stationary ΠMDPs: Policy iteration

  Algorithm 2.4: P I-M DP : Possibilistic (Optimistic) Policy iteration Data: A stationary ΠMDP Result: Computes and returns an optimal policy δ * = max s ∈S min{π(s |s, a).u δ opt (s )}; 10 until u δ opt converges; 11 // Improvement of δ; 12 foreach s ∈ S do 13 δ(s) = arg max a∈A max s ∈S min{π(s |s, a).u δ opt (s )}; 14 until δ converges to δ * ; 15 // Stabilization of the optimistic value of δ 16 return δ * ;

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Drowning effect in possibilistic sequential decision-making . . . . . 40 3.3 Lexicographic refinements in sequential decision-making problems 45 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Figure 3

 3 Figure 3.1: The ΠDT of Counter-example 3.1

Figure 3 . 2 :

 32 Figure 3.2: The finite-horizon πMDP of Counter-example 3.3

Figure 3

 3 Figure 3.4: A counter-example showing the non-efficiency of lmax(lmin)

Figure 3

 3 Figure 3.5: The ΠDT of Example 3.1

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2 Optimizing lexicographic criteria in ΠDT s . . . . . . . . . . . . ΠMDPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.4 Experimental study . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

  OPTIMIZING LEXICOGRAPHIC CRITERIA IN ΠDT S AND FINITE-HORIZON ΠMDPS 59

  OPTIMIZING LEXICOGRAPHIC CRITERIA IN ΠDT S AND FINITE-HORIZON ΠMDPS 60

Example 4. 1 .Figure 4

 14 Figure 4.1: The ΠDT of Example 4.1

F

  Algorithm 4.3: LexBI-M DP : Backward-induction-ΠMDP-lmax(lmin) Data: A possibilistic finite horizon MDP Result: Computes and returns δ for MDP 1 uture ← (ρ(s ), s ∈ S t ); 8 t ← t -1; 9 foreach s ∈ S t do 10 ρ(s) ← [0]; 11 foreach a ∈ A s do 12 M ← ConcatAndOrder(π(.|a, s), F uture); 13 if M ≥ lmax(lmin) ρ(s)

CHAPTER 4 .

 4 OPTIMIZING LEXICOGRAPHIC CRITERIA IN ΠDT S AND FINITE-HORIZON ΠMDPS 65 the best action for the states of S t .

Figure 4 . 2 :

 42 Figure 4.2: The finite-horizon πMDP of Example 4.2

CHAPTER 4 .

 4 OPTIMIZING LEXICOGRAPHIC CRITERIA IN ΠDT S AND FINITE-HORIZON ΠMDPS

Figure 4

 4 Figure 4.3: Average CPU time of (a) optimistic case and (b) possimistic case for ΠDT s

Figure 4 . 4 :

 44 Figure 4.4: Success rate for ΠDT s with h=2 to 7

Figure 4

 4 Figure 4.5: Average CU time of (a) optimistic case and (b) possimistic case for finitehorizon ΠMDPs

Figure 5

 5 Figure 5.1: The ΠDT of Example 5.1

Figure 5 . 2 :

 52 Figure 5.2: Transformed probabilistic decision tree of ΠDT of Example 5.1

  j ∈ Succ(N ) do 17 U ← Backward-Induction-DT -EU (C j );

  complexities of this algorithm are nevertheless expensive, since it memorizes all the trajectories. At each step t its size may be about b t • (2 • t + 1), where b is the maximal number of possible successors of an action. The overall complexity of the algorithm isO(|S| • |A| • |h| • b h • log(b h ), since:• The number of iterations is bounded by the size of the set of possible matrices of trajectories i.e. |S| • |A| • |h|,• One iteration of the algorithm requires composition, ordering and comparing operations on b matrices. Since the composition and comparison of matrices are linear operations, the complexity of one iteration in worst case (when considering the bigger matrices) is in O

-Figure 6 . 1 :-→

 61 Figure 6.1: The stationary finite-horizon πMDP of Example 6.1

CHAPTER 6 .→→

 6 OPTIMIZING LEXICOGRAPHIC CRITERIA IN STATIONARY ΠMDPS 93 for a = Sav: Since Q(R&F, Sav) lmax(lmin) [0], so δ 2 (R&F ) = Sav and U 2 (R&F ) = s = P &U for a = Stay: Future = 0.3 0.3 1 , Q(P &U, Stay) = ConcatAndOrder-S( π = (1), u = (0Since Q(P &U, Stay) lmax(lmin) [0], so δ 2 (P &U ) = Stay and U 2 (P &U ) = 0.3 0.3 0.3 1 1 . =⇒ The stationary policy optimal w.r.t. lmax(lmin) is: δ(R&U ) = Adv; δ(R&F ) = Sav; δ(P &U ) = Stay.

CHAPTER 6 .

 6 OPTIMIZING LEXICOGRAPHIC CRITERIA IN STATIONARY ΠMDPS 96

  OPTIMIZING LEXICOGRAPHIC CRITERIA IN STATIONARY ΠMDPS 97 From (6.2), we have, of course,(U ⊗ (N 1 , . . . , N a )) lmaxlmin l,c= U ⊗ ((N 1 ) lmaxlmin , . . . , (N a ) lmaxlmin ) 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.

Figure 6

 6 Figure 6.2: Average CPU-time for optimistic criteria in stationary ΠMDPs

Figure 6 . 3 :

 63 Figure 6.3: Success rate for optimistic criteria in stationary ΠMDPs

F

  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 . Then, obviously,lim t→∞ U t (s) lmaxlmin l,c = U * l,c .Thus, bounded 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 . Considering H, let us calculate [U t+1 (s) lmaxlmin ] l,c : F uture t+1 = (U t (s ), s ∈ succ(s, a)) = F uture t , → Q t+1 (s, a) = [ T U s,a ⊗ F uture t lmaxlmin ] l,c = [ T U s,a ⊗ F uture t-1 lmaxlmin ] l,c = Q t (s, a). OPTIMIZING LEXICOGRAPHIC CRITERIA IN STATIONARY ΠMDPS 102The overall complexity of Bounded lmax(lmin)-Value Iteration algorithm isO(|V | • (l • c) • |S| • |A| • (l • c) • b • log(l • c)) = O(|V | • (l • c) 2 • |S| • |A| • b • log(l • c)).Algorithm 6.4: BLex-IH-V I: Bounded-infinite-horizon-lmax(lmin)-Value Iteration Data: A stationary ΠMDP and an horizon h δ * , the policy built by the algorithm, is a global variable 1 // δ a global variable starts as an empty setResult: Computes and returns δ * for ΠMDP 2 S do U t (s) ← ((u(s)));5 foreach s ∈ S, a ∈ A s do T U s,a ← T s,a ⊗ ((u(s )), s ∈ succ(s, a)) ; uture ← (U t-1 (s ), s ∈ succ(s,a)); // Gather the matrices provided by the successors of s; 12 Q(s, a) ← [(T U s,a ⊗ F uture) lmaxlmin ] l,c ; 13 if Q * ≤ lmaxlmin Q(s, a) s) ← argmax a Q(s, a) 19 return δ * ;

Table 1 .

 1

1: Consequences of acts Insurance and N o insurance

•

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

	CHAPTER 3. EXTENDING LEXICOGRAPHIC REFINEMENTS TO POSSIBILISTIC
	SEQUENTIAL DECISION-MAKING	56

•

  Transitivity. The proof can be deduced from Proof of Proposition 3.2 (second point) by replacing π τ = (π 1 , . . . , π h , u h ) by v τ = (u 0 , π 1 , u 1 , π 2 , . . . , π h-1 , u h ). Since π τ and v τ are obviously two vectors of numbers in [0, 1], then by transitivity of lmax and lmin we can conclude that lmin(lmax) and lmax(lmin) are transitive.• Monotonicity. Using Proof of Proposition 3.2 (third point): when considering intermediate utilities v τ are vectors of numbers that will be ordered just like π τ . So, δ + δ 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.

  Algorithm 4.2: ConcatAndOrder(π, ρ 1 , . . . , ρ k ) Data: k matrices ρ 1 , . . . , ρ k and a distribution π on {1, . . . , k} Result: ρ, the combination of ρ 1 , . . . , ρ k according to π 1 // Notations: 2 // L ρ : number of lines of ρ, 3 // C ρ : number of columns of ρ, 4 // ρ (z) : the line z in ρ, 5 // ρ z,t : the element in line z and column t in ρ ) 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/chance node. If the matrices have different numbers of lines, dummy lines are added at the bottom of the shortest one (filled with 1 for the optimistic case, with 0 for the pessimistic one).

	CHAPTER 4. OPTIMIZING LEXICOGRAPHIC CRITERIA IN ΠDT S AND
	FINITE-HORIZON ΠMDPS	61
	Algorithm 4.1
	6 begin
	7	N bLines ← k m=1 L ρ m ;
	18	// Ordering the elements of each line by increasing
		order
	19	for z = 1, N bLines do
	20	sortIncreasing(ρ (z) , ≥);
	21	// Ordering the lines by decreasing order according
		to lmax
	22	sortDecreasing(ρ, ≥ lmax );
	23	return ρ;
		Because the ρ matrices are ordered, the lexicographic comparison of two decisions (line 15 of

8 max C ← max m=1,k (C ρ m ); 9 Creates a matrix ρ with NbLines lines and max C + 1 collumns 10 // Concatenation 11 z ← 0; 12 for m = 1, k do 13 for z = 1, L ρ m do 14 z ← z + 1;

15 for t = 1, C ρ m do ρ z,t ← ρ m z ,t ; 16 for t = C ρ m + 1, max C do ρ z,t ← 0; 17 ρ z,max C +1 ← π(m);

Table 5 .

 5 1: Average CPU time (in ms) for optimistic criteria in ΠDT s with h=2 to 7

			Number of decision nodes
		5	21	85	341 1365 5461
	lmax(lmin) 2.5 6.3 11.4 62	80	649
	EU opt	0.97 2.7 8.1 28.8	66	423
	u opt	0.5 0.8 2.7 16.9	43	414

Table 5 .

 5 2: Average CPU time (in ms) for pessimistic criteria in ΠDT s with h=2 to 7

			Number of decision nodes
		5	21	85 341 1365 5461
	lmin(lmax) 2.3	6	12.4 64	98	761
	EU pes	1.17 3.7	7.7	46	72	488
	u pes	0.6 0.83 2.4	18	48	481

  A finite set A of actions, A s denotes the set of actions available in state s; -A utility function u s.t. u(s) is the intermediate satisfaction degree obtained in state s ∈ S. -A transition function i.e. a possibility distribution on each action a ∈ A s s.t. π(.|s, a)

  Algorithm 6.1: Lex-V I: lmax(lmin)-Value Iteration Data: A finite-horizon stationary ΠMDP and an horizon h δ * , the policy built by the algorithm, is a global variable 1 // δ a global variable starts as an empty setResult: Computes and returns δ * for ΠMDP S, a ∈ A s do T U s,a ← T s,a ⊗ ((u(s )), s ∈ succ(s, a)) ;

	2 begin
	3	t ← 0;
	4	foreach s ∈ S do U t (s) ← ((u(s)));
	5 foreach s ∈ 6 repeat
	7	t ← t + 1;
	8	foreach s ∈ S do
	9	Q * ← ((0));
	10	foreach a ∈ A do
	11	F uture ← {U t-1 (s ), s ∈ succ(s, a)}; // Gather the
		matrices provided by the successors of s;
	13

12

Q(s, a) ← ConcatAndOrder-S( π, u, F uture);

  Algorithm 6.2: ConcatAndOrder-S( π, u, {ρ 1 , . . . , ρ k })Data: k matrices ρ 1 , . . . , ρ k , a distribution π on {1, . . . , k}, a set of k utilities Result: ρ, the combination of ρ 1 , . . . , ρ k according to π and u 1 // Notations: 2 // L ρ : number of lines of ρ, 3 // C ρ : number of columns of ρ, 4 // ρ (z) : the line z in ρ, 5 // ρ z,t : the element in line z and column t in ρ

	6 begin
	7	N bLines ← k m=1 L ρ m ;
	8	max C ← max m=1,k (C ρ m );
	9	Creates a matrix ρ with NbLines lines and max C + 1 columns
	10	// Concatenation
	11	z ← 0;
	12	for m = 1, k do
	13	for z = 1, L ρ m do
	14	z ← z + 1;
	19	// Ordering the elements of each line by increasing
		order
	20	for z = 1, N bLines do
	21	sortIncreasing(ρ (z) , ≥);
	22	// Ordering the lines by decreasing order according
		to lmax
	23	sortDecreasing(ρ, ≥ lmax );
	24	return ρ;

15 for t = 1, C ρ m do ρ z,t ← ρ m z ,t ; 16 for t = C ρ m + 1, max C do ρ z,t ← 0; 17 ρ z,max C +1 ← π(m); 18 ρ z,max C +2 ← u(m);

  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 counts 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

i,|V | t

As in classical probabilistic decision trees, it is assumed that π(X j = x|past(C j )) only depends on the variables in past(C j ) and often only on the decision made in the preceding node and on the state of the preceding chance node.

If the policies have different numbers of trajectories, neutral trajectories (vectors) are added at the bottom of the shortest list of trajectories.

If a trajectory is shorter than h, neutral elements (1 for the optimistic case and 0 for the pessimistic one) are added at the end. If the policies have different numbers of trajectories, neutral trajectories (vectors) are added to the shortest one.

The details of the calculation are similar to the ones made for ΠDT s.

Remerciements

CHAPTER 3. EXTENDING LEXICOGRAPHIC REFINEMENTS TO POSSIBILISTIC SEQUENTIAL DECISION-MAKING 53 Note that ∀C j ∈ N C , ∀D i ∈ Succ(C j ), δ, δ ∈ ∆ D i , δ ∈ ∆ Succ(C j )\D i . The trajectories of δ +δ are composed of two disjoint sets of trajectories : One for δ and one for δ . The same holds for δ + δ . Then, note that adding or removing identical trajectories to two sets of trajectories does not change the lmax(lmin) or the lmin (lmax) ordering between these two sets.

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.

(ii) Now we prove that lmax(lmin) satisfy The principle of Pareto efficiency. So, suppose that δ lmax(lmin) δ . Two cases arise:

implies that there exist a pair of different

), that determines the best policy. Here we get

and thus δ 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) . (iii) 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:

implies that there exist a pair of different

), determining the best policy. We get

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) .

• For N 2 = D 2 , we have ρ D 2 = Backward-Induction-ΠDT -lmax(lmin)(D 2 ) and Succ(D 2 ) = {C 4 }:

-For C 4 , we have ρ C 4 = ConcatAndOrder(π C 4 , ρ LN 5 , ρ LN 6 ) = ((1, 1), 0.8 , 0.8 )

= ((0.4, 1), 0.9 1 0.1 1 , 0.8 1 0.8 1 ) = ( 0.4 0.9 1 0.4 0.1 1

⇒ The optimal strategy returned is:

Complexity analysis

Even if working with matrices rather than numerical values, Algorithm 4.1 is polynomial w.r.t. the size of the original tree. However, it is computationally more expensive than the algorithm proposed by [START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF] for the optimization of u opt /u pes (Algorithm 2.1), since it requires to memorize the trajectories that follow from the current policy (i.e. the ρ matrices).

Consider the branching factor of the tree b; the size of the tree is thus equal to b 2h . Now, consider the size of a matrix ρ: it is in the order of b h × (h + 1) in the worst case (i.e. at the end of the backward induction) -the same order of magnitude as the one of the size of the tree.

Let us now study the time complexity. The complexity of ConcatAndOrder is based on operations: the concatenation of b matrices which is linear and ordering matrices which depends on the sorting algorithm: for instance, if we use QuickSort on an n × m matrix, then ordering the elements within a line is performed in O(m • log(m)), and the inter-ranking of the lines is done in

At each step t, from t = h-1 to t = 1, there is a chance phase and a decision phase -b decision nodes, each followed by b chance node. The chance phase is more expensive than the decision one -it makes the same number of recursive calls than the decision phase, but the decision phase does CHAPTER 4. OPTIMIZING LEXICOGRAPHIC CRITERIA IN ΠDT S AND FINITE-HORIZON ΠMDPS 63 not increase the size of the matrices it receives while the chance phase builds and orders, for each of its b 2 chance nodes a matrix that is bigger than the one it receives: it receives (for a given chance node, again) b matrices with b h-t-1 lines and h -t -1 columns and concat them in a matrix with b h-t lines and h -t columns (concat). The ordering then costs b

So the worst time complexity at step t is a function

The order of magnitude of worst case complexity of the algorithm is thus:

then we can calculate this upper bound approximation as

since the primitive of the function f = y • log(y) is F = 0.5 × y 2 (log(y) -0.5), we get:

)) -it is polynomial with respect to the horizon and the size of the tree (which, again, is in b 2h ).

Optimizing lexicographic criteria in finite-horizon ΠMDPs

A first way to solve a finite-horizon ΠMDP would be to compute a DT that is equivalent to the finite-horizon MDP (this is always possible, through the duplication of the nodes with several predecessors) and to apply the algorithm presented in the previous Section. However, this approach may lead to algorithms which are exponential in time and space (w.r.t. the finite-horizon MDP description), since the size of the DT s associated to a finite-horizon MDP may be exponential in the size of the MDP. So there can be a combinatorial explosion. In this Section, we propose an algorithm that calculates a lexicographic optimal policy on the finite-horizon ΠMDP itself.

69

The temporal complexity of bounded backward induction is decreased, compared to that of the lexicographic backward induction. Indeed, the number of calls to ConcatAndOrder of the algorithm does not change, however, the ConcatAndOrder algorithm is only called on sets of matrices which have at most l lines, instead of b h . We deduce that the complexity of the algorithm is bounded by

where n is the (maximal) number of states in S t .

Experimental study

In this Section, we evaluate different solving algorithms proposed in this chapter. We have two criteria for each of the pessimistic and optimistic approaches: the basic possibilistic one and the lexicographic refinement. These criteria aim at solving the same decision problems: sequential decision under possibilistic uncertainty, represented by a ΠDT or a finite-horizon ΠMDP.

We compare the algorithms with two measures:

• the CPU time.

• pairwise success rate: Success A B is the percentage of solutions provided by an algorithm optimizing criterion A that are optimal with respect to criterion B; for instance, the less Success u opt lmax (lmin) , the more important the drowning effect.

The algorithms corresponding to these criteria have been implemented in Java. The experiments have been performed on an Intel Core i5 processor computer (1.70 GHz) with 8GB DDR3L of RAM (all experiments in this section are made using the same computer).

Experimental results in ΠDT s

In what follows, we propose to compare the performance of Lexicographic Backward Induction algorithm (Algorithm 4.1), so-called LexBI-DT , to the classical Backward Induction algorithm (Algorithm 2.1), so-called BI-DT .

The tests were performed on randomly generated complete binary decision trees, from h = 2 to h = 7. The first node is a decision node: at each decision level from the root (i = 1) to the last level (i = 7) the tree contains 4 i-1 decision nodes. This means that with h = 2 (resp. 3, 4, 5, 6, 7), the number of decision nodes is equal to 5 (resp. 21, 85, 341, 1365, 5461) The utility values are uniformly randomly drawn in the set V = {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}. Conditional possibilities relative to chance nodes are normalized, one edge having possibility one and the possibility degree of the other being uniformly drawn in L. For each value of h, 100 ΠDT s are generated.

Summary

In this Chapter, we have proposed new planning algorithms (based on Dynamic Programming), for ΠDT s and finite-horizon ΠMDPs. These algorithms allow to overcome the drowning effect by calculating lexicographic optimal policies. The complexity of the backward induction algorithm depends on the number of trajectories in the optimal policy -and is thus exponential in time and space (with respect to the size of the decision model). We show that an approximate policy can be computed in controlled, polynomial time and space using bounded matrices. Moreover, we have performed experiments on ΠDT s and finite-horizon ΠMDPs built randomly in order to show the discrimination power of lexicographic algorithms.

In the next Chapter, we show that, for ΠDT s and finite-horizon ΠMDPs, the lexicographic criteria can be captured by an EU criterion, relying on big stepped probabilities and utilities.

Introduction

As we have detailed in Section 1.5.2, [Fargier and[START_REF] Fargier | [END_REF][START_REF] Fargier | [END_REF] have shown that, when the problem is not sequential, the comparison of possibilistic utility distributions by lmax(lmin) and lmin(lmax) can be captured by an expected utility, relying on infinitesimal probabilities and utilities.

In this Chapter, we show that such a result can be extended to finite-horizon sequential problems. We focus only on ΠDT s, since a finite-horizon ΠMDP can be translated into a set of ΠDT s (one for each state). So, the comparison of the policies of a finite-horizon ΠMDP can be refined using the same method as the one relative to ΠDT s.

The next Section develops our proposition, defining infinitesimal expected utilities, that refine qualitative utilities, in decision trees. Besides, we show that the 'qualitative' lexicographic criteria presented in Chapter 3 can be represented by these expected utilities. Then, in Section 5.3, we DECISION-MAKING 81

which is the lmax relation when considering DT inv . We get δ DT inv lmin(lmax) δ.

If we invert each degree in both trajectories, we get:

We get δ ∼ DT inv lmin(lmax) δ.

Thus, EUpes is equivalent to lmin(lmax) .

Propositions 5.2 and 5.4 show that lexicographic comparisons have a probabilistic interpretation -actually, using infinitesimal probabilities and utilities. This result comforts the idea, first proposed by [START_REF] Benferhat | Possibilistic and standard probabilistic semantics of conditional knowledge bases[END_REF] and then by [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF], of a bridge between qualitative approaches and probabilities, through the notion of big stepped probabilities [START_REF] Benferhat | Possibilistic and standard probabilistic semantics of conditional knowledge bases[END_REF], Snow, 1999]. But here we make a step further, since the proposed transformations support sequential decision-making.

Backward induction algorithm for EU-refinements

Beyond this theoretical argument, this result suggests an alternative algorithm for the optimization of lmax(lmin) (resp. lmin(lmax)). The proposed algorithm, denoted EU -BI (see Algorithm 5.1 for the optimistic version), simply transform the ΠDT into a probabilistic one, transforming u into φ•u and each π i into a probability distribution p i = φ i •π i , and use an adaptation of classical, EU-based backward induction. This algorithm is optimistic (resp. pessimistic) i.e. optimize EU opt (resp. EU pes ) if it uses an optimistic transformation (resp. pessimistic transformation) of the decision tree. Note that the horizon h and the branching factor b are known in advance. In this algorithm, we first transform the possibilistic scale V to a probabilistic one V p = (φ • V ) using the adequate transformation function that we get using only h and b. It is important that we keep the two vectors associated to the two scales, each value in V has its probabilistic counterpart in V p in same position.

The principle of EU-based backward induction is as follows:

• When a leaf node N is reached, its expected utility is u Vp (N ) the probabilistic utility in V p that matches u(N ) the possibilistic utility in leaf N . This Chapter is organized as follows: Section 6.2 presents some definitions needed all along the chapter. Then, Section 6.3 is devoted to adaptations of value iteration algorithm for the lexicographic criteria in fixed horizon stationary ΠMDPs. Section 6.4 presents our experimental study of these algorithms. Finally, Section 6.5 extends the latter algorithm to the infinite-horizon case.

79%

Principle results of this chapter are published in [Ben Amor et al., 2017].