Decision Making under Uncertainty: A Quasimetric Approach

N’Guyen, Steve and Moulin-Frier, Clément and Droulez, Jacques

Link to the article


We propose a new approach for solving a class of discrete decision making problems under uncertainty with positive cost. This issue concerns multiple and diverse fields such as engineering, economics, artificial intelligence, cognitive science and many others. Basically, an agent has to choose a single or series of actions from a set of options, without knowing for sure their consequences. Schematically, two main approaches have been followed: either the agent learns which option is the correct one to choose in a given situation by trial and error, or the agent already has some knowledge on the possible consequences of his decisions; this knowledge being generally expressed as a conditional probability distribution. In the latter case, several optimal or suboptimal methods have been proposed to exploit this uncertain knowledge in various contexts. In this work, we propose following a different approach, based on the geometric intuition of distance. More precisely, we define a goal independent quasimetric structure on the state space, taking into account both cost function and transition probability. We then compare precision and computation time with classical approaches.


  title = {{Decision Making under Uncertainty: A Quasimetric Approach}},
  author = {N'Guyen, Steve and Moulin-Frier, Cl{\'e}ment and Droulez, Jacques},
  journal = {PLoS ONE},
  year = {2013},
  month = dec,
  number = {12 },
  pages = {e83411},
  volume = {8},
  affiliation = {Institut des Syst{\`e}mes Intelligents et Robotique - ISIR , Laboratoire de Physiologie de la Perception et de l'Action - LPPA , FLOWERS - INRIA Bordeaux - Sud-Ouest , Grenoble Images Parole Signal Automatique - GIPSA-lab},
  doi = {10.1371/journal.pone.0083411 },
  keywords = {optimal control; markov decision process; control under uncertainty},
  url = {},
  hal_id = {hal-00922767}