quarta-feira, 6 de maio de 2009

Value Iteration to solve Factored MDP-IPs

------------------------------------------------------------------------------------------
 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: Value Iteration to solve Factored MDP-IPs
Palestrante:  Leliane Nunes Barros

Data:   07/05/2009, 14h00
Local:  Sala 241A, 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.

Todos são benvindos



Nenhum comentário: