Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs

Kim Bauters, Weiru Liu, Lluis Godo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)
127 Downloads (Pure)

Abstract

The ability of an agent to make quick, rational decisions in an uncertain environment is paramount for its applicability in realistic settings. Markov Decision Processes (MDP) provide such a framework, but can only model uncertainty that can be expressed as probabilities. Possibilistic counterparts of MDPs allow to model imprecise beliefs, yet they cannot accurately represent probabilistic sources of uncertainty and they lack the efficient online solvers found in the probabilistic MDP community. In this paper we advance the state of the art in three important ways. Firstly, we propose the first online planner for possibilistic MDP by adapting the Monte-Carlo Tree Search (MCTS) algorithm. A key component is the development of efficient search structures to sample possibility distributions based on the DPY transformation as introduced by Dubois, Prade, and Yager. Secondly, we introduce a hybrid MDP model that allows us to express both possibilistic and probabilistic uncertainty, where the hybrid model is a proper extension of both probabilistic and possibilistic MDPs. Thirdly, we demonstrate that MCTS algorithms can readily be applied to solve such hybrid models.
Original languageEnglish
Title of host publicationFoundations of Information and Knowledge Systems: 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings
PublisherSpringer-Verlag
Pages24-41
ISBN (Electronic)978-3-319-30024-5
ISBN (Print)978-3-319-30023-8
DOIs
Publication statusPublished - 04 Mar 2016
Event9th International Symposium on Foundations of Information and Knowledge Systems (FoIKS'16) - Linz, Austria
Duration: 07 Mar 201611 Mar 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9616
ISSN (Electronic)0302-9743

Conference

Conference9th International Symposium on Foundations of Information and Knowledge Systems (FoIKS'16)
CountryAustria
CityLinz
Period07/03/201611/03/2016

Fingerprint

Uncertainty

Cite this

Bauters, K., Liu, W., & Godo, L. (2016). Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs. In Foundations of Information and Knowledge Systems: 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings (pp. 24-41). (Lecture Notes in Computer Science; Vol. 9616). Springer-Verlag. https://doi.org/10.1007/978-3-319-30024-5_2
Bauters, Kim ; Liu, Weiru ; Godo, Lluis. / Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs. Foundations of Information and Knowledge Systems: 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings. Springer-Verlag, 2016. pp. 24-41 (Lecture Notes in Computer Science).
@inproceedings{a12f8995879847bab732fce15328892e,
title = "Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs",
abstract = "The ability of an agent to make quick, rational decisions in an uncertain environment is paramount for its applicability in realistic settings. Markov Decision Processes (MDP) provide such a framework, but can only model uncertainty that can be expressed as probabilities. Possibilistic counterparts of MDPs allow to model imprecise beliefs, yet they cannot accurately represent probabilistic sources of uncertainty and they lack the efficient online solvers found in the probabilistic MDP community. In this paper we advance the state of the art in three important ways. Firstly, we propose the first online planner for possibilistic MDP by adapting the Monte-Carlo Tree Search (MCTS) algorithm. A key component is the development of efficient search structures to sample possibility distributions based on the DPY transformation as introduced by Dubois, Prade, and Yager. Secondly, we introduce a hybrid MDP model that allows us to express both possibilistic and probabilistic uncertainty, where the hybrid model is a proper extension of both probabilistic and possibilistic MDPs. Thirdly, we demonstrate that MCTS algorithms can readily be applied to solve such hybrid models.",
author = "Kim Bauters and Weiru Liu and Lluis Godo",
year = "2016",
month = "3",
day = "4",
doi = "10.1007/978-3-319-30024-5_2",
language = "English",
isbn = "978-3-319-30023-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag",
pages = "24--41",
booktitle = "Foundations of Information and Knowledge Systems: 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings",

}

Bauters, K, Liu, W & Godo, L 2016, Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs. in Foundations of Information and Knowledge Systems: 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings. Lecture Notes in Computer Science, vol. 9616, Springer-Verlag, pp. 24-41, 9th International Symposium on Foundations of Information and Knowledge Systems (FoIKS'16), Linz, Austria, 07/03/2016. https://doi.org/10.1007/978-3-319-30024-5_2

Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs. / Bauters, Kim; Liu, Weiru; Godo, Lluis.

Foundations of Information and Knowledge Systems: 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings. Springer-Verlag, 2016. p. 24-41 (Lecture Notes in Computer Science; Vol. 9616).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs

AU - Bauters, Kim

AU - Liu, Weiru

AU - Godo, Lluis

PY - 2016/3/4

Y1 - 2016/3/4

N2 - The ability of an agent to make quick, rational decisions in an uncertain environment is paramount for its applicability in realistic settings. Markov Decision Processes (MDP) provide such a framework, but can only model uncertainty that can be expressed as probabilities. Possibilistic counterparts of MDPs allow to model imprecise beliefs, yet they cannot accurately represent probabilistic sources of uncertainty and they lack the efficient online solvers found in the probabilistic MDP community. In this paper we advance the state of the art in three important ways. Firstly, we propose the first online planner for possibilistic MDP by adapting the Monte-Carlo Tree Search (MCTS) algorithm. A key component is the development of efficient search structures to sample possibility distributions based on the DPY transformation as introduced by Dubois, Prade, and Yager. Secondly, we introduce a hybrid MDP model that allows us to express both possibilistic and probabilistic uncertainty, where the hybrid model is a proper extension of both probabilistic and possibilistic MDPs. Thirdly, we demonstrate that MCTS algorithms can readily be applied to solve such hybrid models.

AB - The ability of an agent to make quick, rational decisions in an uncertain environment is paramount for its applicability in realistic settings. Markov Decision Processes (MDP) provide such a framework, but can only model uncertainty that can be expressed as probabilities. Possibilistic counterparts of MDPs allow to model imprecise beliefs, yet they cannot accurately represent probabilistic sources of uncertainty and they lack the efficient online solvers found in the probabilistic MDP community. In this paper we advance the state of the art in three important ways. Firstly, we propose the first online planner for possibilistic MDP by adapting the Monte-Carlo Tree Search (MCTS) algorithm. A key component is the development of efficient search structures to sample possibility distributions based on the DPY transformation as introduced by Dubois, Prade, and Yager. Secondly, we introduce a hybrid MDP model that allows us to express both possibilistic and probabilistic uncertainty, where the hybrid model is a proper extension of both probabilistic and possibilistic MDPs. Thirdly, we demonstrate that MCTS algorithms can readily be applied to solve such hybrid models.

UR - http://cdcc.faw.jku.at/FoIKS2016/

U2 - 10.1007/978-3-319-30024-5_2

DO - 10.1007/978-3-319-30024-5_2

M3 - Conference contribution

SN - 978-3-319-30023-8

T3 - Lecture Notes in Computer Science

SP - 24

EP - 41

BT - Foundations of Information and Knowledge Systems: 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings

PB - Springer-Verlag

ER -

Bauters K, Liu W, Godo L. Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs. In Foundations of Information and Knowledge Systems: 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings. Springer-Verlag. 2016. p. 24-41. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-30024-5_2