Answers.Body: <p>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.</p>
  <p>&quot;b-)&quot; 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.</p>
  <p><a href="https://i.sstatic.net/bZBEHOzU.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/bZBEHOzU.png" alt="enter image description here" /></a></p>
  <p>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).</p>
  <p>&quot;a-)&quot; 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.</p>
  <p><a href="https://i.sstatic.net/8MXKDRwT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8MXKDRwT.png" alt="enter image description here" /></a></p>
  <p>(x,y) here marks the probability of transition on the first pass (x) vs second pass (y).</p>
  <p>Extra:<br />
  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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-18T15:35:57.313Z
Answers.Text: Could you re-express the last paragraph because it was not clear to me?
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-18T16:28:40.780Z
Answers.Text: I gave it a shot and added some diagrams.
Answers.UserDisplayName: foreverska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-18T17:04:26.527Z
Answers.Text: Really, very hard to understand your explanations and diagrams.
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-20T22:00:13.760Z
Answers.Text: I've tried to be more exact in my wording once more and removed the errant A in the graph.
Answers.UserDisplayName: foreverska
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-18T13:46:06.407Z
Answers.LastActivityDate: 2024-05-20T21:59:01.177Z
Answers.LastEditDate: 2024-05-20T21:59:01.177Z
Answers.UserDisplayName: foreverska
Body: <p>Consider the following cases:</p>
  <p>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.</p>
  <p>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.</p>
  <p>Which case(s) violates Markov property and why?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-18T13:43:29.080Z
Comments.Text: Where did you take this exercise from? Please, edit your post to provide it and if this a homework, tag it with [tag:homework]
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><markov-decision-process><dynamic-programming>
Title: Violation of Markov property
UserDisplayName: DSPinfinity
ThreadText: # Violation of Markov property
  
  (Asked by: username_0 on 2024-05-17)
  
  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?
  
  **Tags:** reinforcement-learning, markov-decision-process, dynamic-programming
  > **Comments:**
  > **username_1**: Where did you take this exercise from? Please, edit your post to provide it and if this a homework, tag it with [tag:homework]  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-05-18. Score: 0
  
  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](https://i.sstatic.net/bZBEHOzU.png)](https://i.sstatic.net/bZBEHOzU.png)
  
  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](https://i.sstatic.net/8MXKDRwT.png)](https://i.sstatic.net/8MXKDRwT.png)
  
  (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.
  
  > **Comments:**
  > **username_0**: Could you re-express the last paragraph because it was not clear to me?  
  > **username_2**: I gave it a shot and added some diagrams.  
  > **username_0**: Really, very hard to understand your explanations and diagrams.  
  > **username_2**: I've tried to be more exact in my wording once more and removed the errant A in the graph.  
  
  ---
  
  