Cette thèse développe des méthodes pour l'optimisation d’un processus de décision markovien (MDP) à temps discret, caractérisé par $k geq 2$ fonctions objectif. Au début de chaque période, le MDP se trouve dans un état où plusieurs actions alternatives sont disponibles. Le choix d’une action génère une récompense de taille $k$ et détermine la distribution de probabilité de l’état suivant. Une politique spécifie l'action à entreprendre dans chaque état. Une politique est dite efficiente si elle réalise un vecteur de récompense total espéré Pareto efficient sur l’horizon du processus. Une politique uniformément efficiente est une politique qui est efficiente quel que soit l'état initial. Cette étude se limite au cas d’un horizon temporel fini. Elle est divisée en trois chapitres.
Dans le premier chapitre, nous réfutons le théorème standard portant sur l’extension vectorielle des équations d’optimalité d’un MDP mono-objectif à horizon fini. Au moyen d’un contre-exemple, nous montrons que la solution des équations étendues ne fournit pas toujours les ensembles de valeurs efficientes stipulés par le théorème. L’analyse du contre-exemple nous conduit à une condition suffisante pour que le théorème soit valable dans sa forme originelle. Cette condition est démontrée vraie lorsqu’il ne reste qu’une ou deux périodes, ainsi que lorsque la dynamique du modèle est déterministe. Plus généralement, nous démontrons que les vraies solutions des équations correspondent aux ensembles des valeurs efficientes atteintes dans une classe plus large de politiques que celle autorisée par le théorème. Cette classe inclut des politiques markoviennes et non markoviennes. Nous décrivons un algorithme de programmation dynamique permettant de construire des politiques uniformément efficientes par rapport au nouvel espace de politiques.
Le deuxième chapitre s’attache à caractériser et à calculer les politiques uniformément efficientes lorsqu’on ne considère que les politiques markoviennes déterministes. À cette fin, le concept de politique F-efficiente est introduit. Nous montrons que la F-efficience est une condition nécessaire à l’efficience uniforme, et qu’elle peut être caractérisée à l’aide d’équations d’optimalité. Ces équations donnent lieu à un algorithme de programmation dynamique qui identifie toutes les politiques F-efficientes. À partir d’une certaine représentation de l’ensemble des politiques uniformément efficientes au sein de l’ensemble F-efficient, nous déduisons une procédure permettant d’énumérer les politiques uniformément efficientes. Des expériences numériques menées avec cette procédure suggèrent des avantages computationnels par rapport à une recherche exhaustive.
Le troisième chapitre propose une formulation en programmation linéaire multi-objectif d’un cas de figure dans lequel les récompenses et les probabilités de transition peuvent varier dans le temps. Nous établissons une bijection entre les solutions efficientes du programme linéaire et les politiques efficientes. Grâce à cette équivalence, nous sommes en mesure de caractériser et de démontrer l'existence de politiques déterministes efficientes. Cette caractérisation est ensuite utilisée dans le développement d’un algorithme de type simplexe permettant de détecter toutes les politiques déterministes efficientes en un nombre fini d’itérations. À notre connaissance, il s’agit du seul algorithme dans la littérature qui est conçu spécialement pour cet objectif. Nous présentons les résultats de son application dans un problème d’ingénierie bicritère.
Les méthodes présentées dans cette thèse facilitent et éclairent la résolution de problèmes de prise de décision pouvant être modélisés comme des MDP à horizon fini mais ne pouvant être représentés de manière réaliste par une unique fonction objectif. |
This dissertation develops methods for the optimization of a discrete-time Markov decision process (MDP) characterized by $k geq 2$ objective functions. At the beginning of each time period, the MDP occupies a state in which a number of alternative actions are available. The choice of an action generates a $k$-dimensional reward and determines the probability distribution of the next state. A policy specifies the action to be taken in each state as a function of the period. A policy that achieves a Pareto efficient expected total reward vector over the process's lifetime is termed efficient. A uniformly efficient policy is a policy efficient for all initial states. This study deals strictly with the case of a finite time horizon. It is divided into three main chapters.
In the first chapter, we disprove the standard theorem on the vector extension of the optimality equations of a finite-horizon single-objective MDP. By dint of a counterexample, we show that solution of the extended equations does not always yield the efficient value sets stipulated by the theorem. Analysis of the counterexample leads us to a condition sufficient for the theorem to hold in its original form. The condition is shown to hold when one or two time periods are left, as well as when the dynamics of the model are deterministic. More generally, we demonstrate that the actual solutions to the equations are the sets of all efficient values achieved in a larger policy class than that allowed by the theorem. This class includes Markov and non-Markov policies. We describe a dynamic programming algorithm for constructing uniformly efficient Markov policies with respect to the new policy space.
The second chapter focuses on how to characterize and compute uniformly efficient policies when we only allow consideration of Markov deterministic policies. To this end, the concept of an F-efficient policy is introduced. We show F-efficiency to be a necessary condition for uniform efficiency that can be characterized using functional equations. The equations yield a dynamic programming algorithm that finds all F-efficient policies. From an alternate representation of the uniformly efficient policy set within the F-efficient policy set, we deduce a procedure for enumerating the former set. Numerical experiments with this procedure suggest definite computational advantages over full search-based policy optimization.
The third chapter proposes a multi-objective linear programming formulation of a model instance in which rewards and transition probabilities can vary with time. We allow consideration of all Markov randomized policies, but in order to exclude policies of a certain anomalous type, we introduce the concept of a regular policy. We establish a one-to-one correspondence between the efficient solutions of the multi-objective linear program and the efficient regular policies. Thanks to this equivalence, we are able to characterize, and demonstrate the existence of, efficient deterministic policies. The characterization is then employed in the development of a simplex method-like algorithm that detects all efficient deterministic policies after a finite number of iterations. To our knowledge, this is the only algorithm in print designed for accomplishing this end. We report the results of testing the algorithm in a bi-objective engineering application.
The methods presented in this study enable and inform the resolution of decision-making problems that can be treated as finite-horizon MDPs but cannot realistically be represented by a single objective function. |