Publications de Gildas Jeantet [C.V]

Sequential Decision Making with Rank Dependent Utility: a Minimax Regret Approach
2012 - AAAI conference on Artificial Intelligence (AAAI 2012)
Gildas Jeantet - Patrice Perny - Olivier Spanjaard

This paper is devoted to sequential decision making with Rank Dependent expected Utility (RDU). This decision criterion generalizes Expected Utility and enables to model a wider range of observed (rational) behaviors. In such a sequential decision setting, two conflicting objectives can be identified in the assessment of a strategy: maximizing the performance viewed from the initial state (optimality), and minimizing the incentive to deviate during implementation (deviation-proofness). In this paper, we propose a minimax regret approach taking these two aspects into account, and we provide a search procedure to determine an optimal strategy for this model. Numerical results are presented to show the interest of the proposed approach in terms of optimality, deviation-proofness and computability.

Voir la publication
Resolute Choice in Sequential Decision Problems with Multiple Priors
2011 - International Joint Conference on Artificial Intelligence (IJCAI 2011)
Hélène Fargier - Gildas Jeantet - Olivier Spanjaard

This paper is devoted to sequential decision making under uncertainty, in the multi-prior framework of Gilboa and Schmeidler. In this setting, a set of probability measures (priors) is defined instead of a single one, and the decision maker selects a stratégy that maximizes the minimum possible value of expected utility over this set of priors. We are interested here in the resolute choice approach, where one initially commits to a complete strategy and never deviates from it later. Given a decision tree representation with multiple priors, we study the problem of determining an optimal strategy from the root according to min expected utility. We prove the intractability of evaluating a strategy in the general case. We then identify different properties of a decision tree that enable to design dedicated resolution procedures. Finally, experimental results are presented that evaluate these procedures.

Voir la publication
Computing Rank Dependent Utility in Graphical Models
2011 - Artificial Intelligence Journal (AIJ 2011)
Gildas Jeantet - Olivier Spanjaard

This paper is devoted to automated sequential decision in AI. More precisely, we focus here on the Rank Dependent Utility (RDU) model. This model is able to encompass rational decision behaviors that the Expected Utility model cannot accomodate. However, the non-linearity of RDU makes it difficult to compute an RDU-optimal strategy in sequential decision problems. This has considerably slowed the use of RDU in operational contexts. In this paper, we are interested in providing new algorithmic solutions to compute an RDU-optimal strategy in graphical models. Specifically, we present algorithms for solving decision tree models and influence diagram models of sequential decision problems. For decision tree models, we propose a mixed integer programming formulation that is valid for a subclass of RDU models (corresponding to risk seeking behaviors). This formulation reduces to a linear program when mixed strategies are considered. In the general case (i.e., when there is no particular assumption on the parameters of RDU), we propose a branch and bound procedure to compute an RDU-optimal strategy among the pure ones. After highlighting the difficulties induced by the use of RDU in influence diagram models, we show how this latter procedure can be extended to optimize RDU in an influence diagram. Finally, we provide empirical evaluations of all the presented algorithms.

Voir la publication
Une approche de choix résolu au sens de Jaffray dans les arbres de décision munis de probabilités imprécises
2010 - Société française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2010)
Gildas Jeantet - Olivier Spanjaard

Dans cet article, nous nous intéressons à l'optimisation du critère de Hurwicz dans un arbre de décision muni de probabilités imprécises. Nous proposons une procédure de choix résolu au sens de Jaffray afin de déterminer une stratégie dont toutes les sous-stratégies sont à la fois proches de l'optimum (au sens de Hurwicz) et E-admissible (c'est-à-dire qu'il existe un jeu de probabilités sur le sous-arbre tel que la sous-stratégie maximise l'espérance d'utilité). Cette procédure fait appel à la résolution de programmes linéaires pour évaluer les sous-stratégies selon le critère de Hurwicz, et pour tester leur E-admissibilité. Des résultats numériques sont fournis qui illustrent le caractère opérationnel de l'approche proposée.

Voir la publication
Optimisation du critère d'Hurwicz pour les arbres de décision hasard en situation d'incertain total
2009 - Manifestation de JEunes Chercheurs STIC (MajecSTIC 2009)
Gildas Jeantet

Cet article est consacré aux problèmes de décision séquentielle dans l'incertain lorsque le décideur a une ignorance complète sur les probabilités des événements. Nous étudions ici le problème de la détermination d'une stratégie optimale au sens de Hurwicz dans les arbres de décision hasard. Après avoir montré que l'approche par programmation dynamique classique est inopérante pour optimiser le critère de Hurwicz dans un arbre de décision hasard, nous proposons un algorithme polynomial pour résoudre ce problème. Enfin nous fournissons des tests numériques effectués sur des instances générées aléatoirement pour illustrer les performances de notre algorithme.

Voir la publication
Optimizing the Hurwicz Criterion in decision trees with imprecise probabilities
2009 - International Conference on Algorithmic Decision Theory (ADT 2009)
Gildas Jeantet - Olivier Spanjaard

This paper is devoted to sequential decision problems with imprecise probabilities. We study the problem of determining an optimal strategy according to the Hurwicz criterion in decision trees. More precisely, we investigate this problem from the computational viewpoint. When the decision tree is separable (to be defined in the paper), we provide an operational approach to compute an optimal strategy, based on a bicriteria dynamic programming procedure. The results of numerical tests are presented. When the decision tree is non-separable, we prove the NP-hardness of the problem.

Voir la publication
Choix résolu et utilité espérée dépendant du rang dans les diagrammes d'influences
2009 - Journées Francophones Modèles Formels de l'Interaction (MFI 2009)
Gildas Jeantet - Olivier Spanjaard

Nous nous intéressons ici à l'optimisation de l'utilité espérée dépendant du rang (RDU) dans un diagramme d'influence. Les stratégies potentielles considérées habituellement dans un diagramme d'influence forment un sous-ensemble X de l'ensemble Y des stratégies potentielles considérées dans l'arbre de décision-hasard obtenu en développant le diagramme. A la différence du modèle EU, il n'existe pas nécessairement une stratégie optimale selon RDU dans X (autrement dit, l'ensemble des stratégies optimales selon RDU peut être inclus dans Y). Dans cet article, nous proposons d'une part une méthode en deux phases pour déterminer la stratégie optimale dansY (développement du diagramme d'influence en arbre décision hasard, puis détermination de la stratégie optimale selon RDU dans cet arbre), et nous montrons d'autre part comment enrichir l'espace X des stratégies lorsque l'on souhaite opérer directement sur le diagramme d'influence. Nous présentons en particulier un algorithme d'énumération implicite afin de déterminer une stratégie optimale dans cet espace. Les expérimentations numériques menées s'avèrent encourageantes.

Voir la publication
Rank Dependent Probability Weighting in Sequential Decision Problems under Uncertainty
2008 - International Conference on Automated Planning and Scheduling (ICAPS 2008)
Gildas Jeantet - Olivier Spanjaard

This paper is devoted to the computation of optimal strategies in automated sequential decision problems. We consider here problems where one seeks a strategy which is optimal for rank dependent utility (RDU). RDU generalizes von Neumann and Morgenstern's expected utility (by probability weighting) to encompass rational decision behaviors that EU cannot accomodate. The induced algorithmic problem is however more difficult to solve since the optimality principle does not hold anymore. More crucially, we prove here that the search for an optimal strategy (w.r.t. RDU) in a decision tree is an NP-hard problem. We propose an implicit enumeration algorithm to compute optimal rank dependent utility in decision trees. The performances of our algorithm on randomly generated instances and real-world instances of different sizes are presented and discussed.

Voir la publication
Approche algorithmique de la recherche d'une stratégie RDU-optimale dans un arbre de décision
2008 - Société française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2008) Best paper
Gildas Jeantet - Olivier Spanjaard

Le problème de la recherche d'une stratégie EU-optimale (i.e., optimale au sens de l'utilité espérée) dans un arbre décision hasard se résout en temps linéaire en fonction du nombre d'arcs par programmation dynamique. Nous nous intéressons ici à une variante plus difficile de ce problème, où l'on recherche une stratégie RDU-optimale (i.e., optimale au sens de l'utilité dépendant du rang). L'utilité dépendant du rang présente une plus grande richesse descriptive que l'utilité espérée car elle permet un traitement non linéaire des probabilités. Le problème algorithmique qui s'ensuit dans les arbres décision hasard est cependant plus difficile car la programmation dynamique ne s'applique plus. Nous établissons ici que le problème est NP-difficile. Nous proposons un algorithme de séparation et évaluation pour le résoudre, et présentons des résultats numériques montrant l'efficacité de notre approche.

Voir la publication