---------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página:
http://www.ime.usp.br/~liamf/seminarios/index.html -----------------------------------------------------------------------------
Título: Efficient Solutions to Factored MDPs with Imprecise Transition
Probabilities
Palestrante: Karina Valdivia
Data: 1/10/2009, 14h00
Local: Sala 243A, IME-USP
Resumo:
When modeling real-world decision-theoretic planning problems in the
Markov decision process (MDP) framework, it is often impossible to
obtain a completely accurate estimate of transition probabilities.
For example, natural uncertainty arises in the transition
specification due to elicitation of MDP transition models from an
expert or data, or non-stationary transition distributions arising
from
insufficient state knowledge. In the interest of obtaining the most
robust policy under transition uncertainty, the Markov Decision
Process with Imprecise Transition Probabilities (MDP-IPs) has been
introduced to model such scenarios. Unfortunately, while solutions to
the MDP-IP are well-known, they require nonlinear optimization and are
extremely time-consuming in practice. To address this deficiency, we
propose efficient dynamic programming methods to exploit the structure
of factored MDP-IPs. Noting that the key computational bottleneck in
the solution of MDP-IPs is the need to repeatedly solve nonlinear
constrained optimization problems, we show how to target approximation
techniques to drastically reduce the computational overhead of the
nonlinear solver while producing bounded, approximately optimal
solutions. Our results show up to two orders of magnitude speedup in
comparison to traditional ``flat'' dynamic programming approaches and
up to an order of magnitude speedup over the extension of
factored MDP approximate value iteration techniques to MDP-IPs.
(paper presented in the International Conference of Automatic Planning
and Scheduling - ICAPS 2009)
--------------
Todos são bem-vindos
