5
$\begingroup$

From what I understand, a $MDP=(G, A, P, R)$ (markov decision process) is represented as:

  • A complete directed graph $G=(V, E)$
  • A set of actions $A_u$ for each vertex $u \in V$
  • A reward function $R$ that maps any vertex to some reward, i.e., $R \colon V \mapsto \mathbb{R}$.
  • A probability function $P$ that gives the probability $P_a(u, v)\in [0, 1]$ of taking edge $(u, v)$ after performing action $a \in A_u$ at node $u$

The behavior of any MDP is talked about in terms of some policy $F$, where $F_0$ is the initial state that the policy starts in, and $F(u)\in A_u$ is the action $F$ takes when at node $u$, which is defined for all $u \in V$.

We then say that the MDP starts in $u=F_0$, performs some action $a=F(u)$, then moves to some other vertex $v \in V$ with probability $P_a(u, v)$. It repeats this process, where on turn $t$ it performs an action $b=F(w)$ some node $w \in V$, then moves to some other node $z\in V$ according to probability $P_b(w, z)$.

Now, a POMDP (partially observable markov decision process) is defined in a similar manner, except at each state $u \in V$ instead of knowing it's current state, $F$ is given some observation data $O(u) \in S$, where $S$ is any set. $F$ then constructs a "belief state" $b \in [0, 1]^{\vert V \vert }$ based on that information, which is a set of probabilities associated with each node of how much it "believes" it is in that node.

Now we define $F$ in terms of what action it performs in a given belief state, where the belief state can change with time.

This all makes sense, my question it just that since there are a different set of actions for each node, how does $F$ know what actions $A_u$ it has available without knowing what node $u\in V$ it is in?

$\endgroup$
2
$\begingroup$

The availability of action $ a $ can be understood as $P_a(u, v) > 0$ for some $ v $

If an action $ a $ is not available in $ u $ then it will have not effect, this means that $P_a(u, v) = 0 $ for every possible $v$

$\endgroup$
  • $\begingroup$ Ah! That makes sense! So essentially, every action is available for every state, and some just do nothing and stay in the current state? $\endgroup$ – Phylliida Feb 25 '16 at 16:18
  • 1
    $\begingroup$ No, in that case Pa(S1,S1)=1. What I am proposing is that it is zero for all cases, even Pa(S1,S1). It would be the same as saying that it is not defined. Remember that if you loop into the same node, you will get the reward again... and you don't want that. $\endgroup$ – Juan Leni Feb 25 '16 at 16:21
  • $\begingroup$ Sorry if misunderstood your comment. You will stay in the same state. But what I wanted to emphasise is that you don't want to loop into the same state (read previous comment). $\endgroup$ – Juan Leni Feb 25 '16 at 16:54

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.