-1
$\begingroup$

Consider the following cases:

a-) In solving an episodic problem we observe that all trajectories from the start state to the goal state pass through a particular state exactly twice.

b-) In solving an episodic problem we observe that some trajectories from the start state to the goal state pass through a particular state exactly twice.

Which case(s) violates Markov property and why?

$\endgroup$
1
  • $\begingroup$ Where did you take this exercise from? Please, edit your post to provide it and if this a homework, tag it with homework $\endgroup$
    – nbro
    Commented May 18 at 13:43

1 Answer 1

0
$\begingroup$

Markovian environments contain everything the agent needs to make an optimal decision in the present state. There cannot be a state where an agent passes through it once and the optimal action is one action and when it passes through it again, the optimal action is a different one.

"b-)" is likely Markovian. The simplest example is a triangle of points. To one of the points of the triangle let us make a path from the starting state. From another point let’s make a path to the terminal state with some fixed probability.

enter image description here

Trajectories through this arrangement pass through any given point not only twice but sometimes none (A, B, end) or many times (A, B, C, A, B, C, A, B, end).

"a-)" on the other hand is non-Markovian because the trajectory passes through a point twice and at some other point exits deterministically. If exiting was always optimal we’d see some paths with one or zero traversals of a given state. So the optimal policy must be determined based on something not in the state, violating the markov property.

enter image description here

(x,y) here marks the probability of transition on the first pass (x) vs second pass (y).

Extra:
To be exact, there is a markovian representation of this graph but states where we pass through twice are two distinct states which doesn't fit the wording of the question.

$\endgroup$
4
  • $\begingroup$ Could you re-express the last paragraph because it was not clear to me? $\endgroup$ Commented May 18 at 15:35
  • 1
    $\begingroup$ I gave it a shot and added some diagrams. $\endgroup$
    – foreverska
    Commented May 18 at 16:28
  • $\begingroup$ Really, very hard to understand your explanations and diagrams. $\endgroup$ Commented May 18 at 17:04
  • 1
    $\begingroup$ I've tried to be more exact in my wording once more and removed the errant A in the graph. $\endgroup$
    – foreverska
    Commented May 20 at 22:00

You must log in to answer this question.

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