1
$\begingroup$

I'm trying to model a MDP to traverse a complete weighted graph (i.e. all vertex are connected). The states, and also the actions (i.e. S=A), are the vertex of the weighted graph. The transition function is 1 for given state s if next state s'=a. The reward is the weight of the edges, which is 1 for a given set, and 0 for the rest. The state and action space is huge, and the representation is continuous.

This is the MDP so far, but I have the constraint that each vertex can be visited just once per episode; then I added a condition that if the vertex had been visited, it is ignored and not traversed (instead, the closest non-visited vertex, its action, is selected). I noticed that this was wrong, since I'm breaking the markov property. Then I though about changing the reward from 1 to 0 once the vertex is visited, but again, if I'm not wrong, this breaks the markov property. On the other hand, if I do not use this constraint of ignoring already visited vertex, I can get stuck in infinite loops, which is even worse. How can I properly design the described problem in order to be sure that vertex will be visited at most once? If I can't, at least it's possible to avoid infinite loops?

I want to avoid breaking the markov property in order to properly model the MDP. Anyway, this is WIP for a paper, and I wonder how common is to break the markov property in the literature. I've tried to look for examples, but I have not been able to find clear examples where the authors clearly stay this fact. I'd appreciate some comments on this.

Thank you.

$\endgroup$

1 Answer 1

1
$\begingroup$

Many environments are non-Markovian. Sometimes based on the perception of the agent a Markovian environment becomes non-Markovian (woods101 with perception aliasing).

If the model assumes a Markovian environment and it is non-Markovian the non-Markovianness gets misinterpreted as randomness and depending on the dynamics of the non-Markovianness this may cause the model to perform poorly.

BUT, there is a Markovian representation of your environment. Think of all possible moves in the graph represented as a tree. The agent can never come back to a state it once visited. Instead when it sees that vertex again, edges which have already been visited are replaced by equal weighted transitions to unvisited vertex. This explodes the number of states but it is Markovian.

If one represented the graph in the simpler form (one state per vertex) as a Q-table and allowed it to explore this much larger Markovian Tree representation, it would appear a bit random to the table. Just as if it were exploring a non-Markovian environment.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .