3
$\begingroup$

To give some perspective, first consider the following diagram comparing Markov Chains, HMMs, MDPs, and POMDPs (I'm not sure who to credit for it).


                    Fully observable          Partially observable
                _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
               |                         |                           |
    no actions |      Markov chain       |           HMM             |
               |_ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _|
               |                         |                           |
    actions    |          MDP            |          POMDP            |
               |_ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _|

Recall that an HMM allows us to model probability distributions over a sequence of observations. Bayesian networks (not pictured) are a generalization of HMMs which model conditional distributions over sets of random variables (see here for a description). When modeling a problem over time, one appends a time index to the model resulting in a dynamic Bayesian network.

A tool known as a dynamic influence diagram extends dynamic Bayesian networks to decision-making problems through the inclusion of actions that can effect the evolution of the problem.

My question is: how do dynamic influence diagrams and POMDPs compare? On the surface they seem like they are modeling the same problem type. What sort of problems are amenable to each tool?

$\endgroup$
1
$\begingroup$

I'll quote from the paper "Interactive Dynamic influence diagrams" (DIDs) by Polich and Gmytrasiewicz (AAMAS 2007):

A dynamic influence diagram is a computational representation of a POMDP.

They continue soon afterward:

DIDs perform planning using a forward exploration technique known as reachability analysis. This technique explores the possible states of belief an agent may be in in the future, the likelihood of reaching each state of belief, and the expected utility of each belief state. The agent then adopts the plan which maximizes the expected utility. DIDs provide exact solutions for finite horizon POMDP problems, and finite look-ahead approximations for POMDPs of infinite horizon.

To me this suggests that DIDs are, as the authors state, one possible representation of a POMDP, to which a specific look-ahead type solution method is related to. As look-ahead is limited to approximate solutions for infinite horizon POMDPs, this also suggests that DIDs can not represent every POMDP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.