Multilinear and Integer Programming for Markov Decision Processes with Imprecise Probabilities

Ricardo Shirota Filho; Fabio Gagliardi Cozman; Felipe Werndl Trevizan; Cassio Polpo de Campos; Leliane Nunes de Barros

Multilinear and Integer Programming for Markov Decision Processes with Imprecise Probabilities

Ricardo Shirota Filho, Fabio Gagliardi Cozman, Felipe Werndl Trevizan, Cassio Polpo de Campos, Leliane Nunes de Barros

School of Electronics, Electrical Engineering and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

12 Citations (Scopus)

190 Downloads (Pure)

Abstract

Markov Decision Processes (MDPs) are extensively used to encode sequences of decisions with probabilistic effects. Markov Decision Processes with Imprecise Probabilities (MDPIPs) encode sequences of decisions whose effects are modeled using sets of probability distributions. In this paper we examine the computation of Γ-maximin policies for MDPIPs using multilinear and integer programming. We discuss the application of our algorithms to “factored” models and to a recent proposal, Markov Decision Processes with Set-valued Transitions (MDPSTs), that unifies the fields of probabilistic and “nondeterministic” planning in artificial intelligence research.

Original language	English
Title of host publication	Proceedings of the 5th International Symposium on Imprecise Probability: Theories and Applications
Pages	395-404
Number of pages	10
Publication status	Published - 2007
Event	The 5th International Symposium on Imprecise Probability: Theories and Applications - Prague, Czech Republic Duration: 16 Jul 2007 → 19 Jul 2007

Conference

Conference	The 5th International Symposium on Imprecise Probability: Theories and Applications
Country/Territory	Czech Republic
City	Prague
Period	16/07/2007 → 19/07/2007

Access to Document

Multilinear and Integer Programming for Markov Decision Processes with Imprecise Probabilities
Copyright the author 2007
Accepted author manuscript, 178 KB

http://www.sipta.org/isipta07/proceedings/062.html

Cite this

@inproceedings{adba0bf3e76e4c1592f7cc002f9375a7,

title = "Multilinear and Integer Programming for Markov Decision Processes with Imprecise Probabilities",

abstract = "Markov Decision Processes (MDPs) are extensively used to encode sequences of decisions with probabilistic effects. Markov Decision Processes with Imprecise Probabilities (MDPIPs) encode sequences of decisions whose effects are modeled using sets of probability distributions. In this paper we examine the computation of Γ-maximin policies for MDPIPs using multilinear and integer programming. We discuss the application of our algorithms to “factored” models and to a recent proposal, Markov Decision Processes with Set-valued Transitions (MDPSTs), that unifies the fields of probabilistic and “nondeterministic” planning in artificial intelligence research. ",

author = "{Shirota Filho}, Ricardo and Cozman, {Fabio Gagliardi} and Trevizan, {Felipe Werndl} and {de Campos}, {Cassio Polpo} and {de Barros}, {Leliane Nunes}",

year = "2007",

language = "English",

pages = "395--404",

booktitle = "Proceedings of the 5th International Symposium on Imprecise Probability: Theories and Applications",

note = "The 5th International Symposium on Imprecise Probability: Theories and Applications ; Conference date: 16-07-2007 Through 19-07-2007",

}

Shirota Filho, R, Cozman, FG, Trevizan, FW, de Campos, CP & de Barros, LN 2007, Multilinear and Integer Programming for Markov Decision Processes with Imprecise Probabilities. in Proceedings of the 5th International Symposium on Imprecise Probability: Theories and Applications. pp. 395-404, The 5th International Symposium on Imprecise Probability: Theories and Applications, Prague, Czech Republic, 16/07/2007. <http://www.sipta.org/isipta07/proceedings/062.html>

Multilinear and Integer Programming for Markov Decision Processes with Imprecise Probabilities. / Shirota Filho, Ricardo; Cozman, Fabio Gagliardi; Trevizan, Felipe Werndl et al.
Proceedings of the 5th International Symposium on Imprecise Probability: Theories and Applications. 2007. p. 395-404.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Multilinear and Integer Programming for Markov Decision Processes with Imprecise Probabilities

AU - Shirota Filho, Ricardo

AU - Cozman, Fabio Gagliardi

AU - Trevizan, Felipe Werndl

AU - de Campos, Cassio Polpo

AU - de Barros, Leliane Nunes

PY - 2007

Y1 - 2007

N2 - Markov Decision Processes (MDPs) are extensively used to encode sequences of decisions with probabilistic effects. Markov Decision Processes with Imprecise Probabilities (MDPIPs) encode sequences of decisions whose effects are modeled using sets of probability distributions. In this paper we examine the computation of Γ-maximin policies for MDPIPs using multilinear and integer programming. We discuss the application of our algorithms to “factored” models and to a recent proposal, Markov Decision Processes with Set-valued Transitions (MDPSTs), that unifies the fields of probabilistic and “nondeterministic” planning in artificial intelligence research.

AB - Markov Decision Processes (MDPs) are extensively used to encode sequences of decisions with probabilistic effects. Markov Decision Processes with Imprecise Probabilities (MDPIPs) encode sequences of decisions whose effects are modeled using sets of probability distributions. In this paper we examine the computation of Γ-maximin policies for MDPIPs using multilinear and integer programming. We discuss the application of our algorithms to “factored” models and to a recent proposal, Markov Decision Processes with Set-valued Transitions (MDPSTs), that unifies the fields of probabilistic and “nondeterministic” planning in artificial intelligence research.

M3 - Conference contribution

SP - 395

EP - 404

BT - Proceedings of the 5th International Symposium on Imprecise Probability: Theories and Applications

T2 - The 5th International Symposium on Imprecise Probability: Theories and Applications

Y2 - 16 July 2007 through 19 July 2007

ER -

Multilinear and Integer Programming for Markov Decision Processes with Imprecise Probabilities

Abstract

Conference

Access to Document

Fingerprint

Cite this