Charles University, Faculty of Mathematicsand Physics
Prague, Czech Republic
16-19 July 2007


Ricardo Shirota Filho, Fabio Cozman, Felipe Trevizan, Cassio Campos, Leliane Barros

Multilinear and Integer Programming for Markov Decision Processes with Imprecise Probabilities


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 Gamma-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.

Keywords. Markov Decision Processes with Imprecise Probabilities, maximin criterion, multilinear and integer programming.

Paper Download

The paper is availabe in the following formats:

Authors addresses:

Ricardo Shirota Filho
Laboratório de Tomada de Decisão
A/C Prof. Dr. Fabio G. Cozman
Escola Politécnica da USP
Av. Prof. Mello Moraes, 2231
CEP: 05356-000
São Paulo, SP, BRAZIL

Fabio Cozman
Av. Prof. Mello Moraes, 2231
Cidade Univesitaria, CEP 05508-900
Sao Paulo, SP - BRAZIL

Felipe Trevizan
Despatx 398
Departamento de Tecnologia - UPF
Paseo de Circunvalacion, 8
08003 Barcelona, Spain

Cassio Campos
University of Sao Paulo
Sao Paulo, SP, Brazil

Leliane Barros
Departamento de Computacao
Instituto de Matematica e Estatistica
Cidade Universitaria, CEP 05508900
Sao Paulo, SP

E-mail addresses:

Ricardo Shirota Filho
Fabio Cozman
Felipe Trevizan
Cassio Campos
Leliane Barros

[ back to the Proceedings of ISIPTA'07 home page 
Send any remarks to the following address: