# Can non-Markov environments also be deterministic?

The definition of deterministic environment I am familiar with goes as follows:

The next state of the agent depends only on the current state and the action chosen by the agent.

By exclusion, everything else would be a stochastic environment.

However, what about environments where the next state depends deterministically on the history of previous states and actions chosen? Are such environments also considered deterministic? Are they very uncommon, and hence just ignored, or should I include them into my working definition of deterministic environment?

Markov Environment is not about deterministic or stochastic. "Depends only on the current state and your action" does not mean you know what will happen(deterministic).

We can have Markov + deterministic, Markov + Stochastic, Non-Markov + deterministic, and Non-Markov + stochastic.

The definition you have is not a definition of deterministic. It is a definition of Markov property.

Refer to Wikipedia.

A stochastic process has the Markov property if the conditional probability distribution of future states of the process (conditional on both past and present values) depends only upon the present state; that is, given the present, the future does not depend on the past. A process with this property is said to be Markovian or a Markov process. The most famous Markov process is a Markov chain. Brownian motion is another well-known Markov process.

Markov property is assumed mostly in stochastic problems. Brownian motion is the motion of molecules of ink in the water and used to model the movement of a stock price, which is stochastic.

Deterministic means when you are in the same state and choose the same action your next state will be always the same.

Stochastic means even you are in the same state and choose the same action, you next state can be different than the previous time.

Example) You toss a coin and roll a die. Every time you roll a die you get pennies as many. If the coin gets head, you get a chance to roll a die twice next time. Your state can be (money you collect so far, coin head/tail in the previous time).

In this problem, your next state will not be affected by the past. the only thing you need to know is the current state, the money you got and head or tail. It has a Markov process/environment. However, still, it is stochastic because you don't know what will be the next state.

Depends on the information provided in the state of the system. In theory, the history can be an element of the state, in which case, by the definition you provided:

The next state of the agent depends only on the current state and the action chosen by the agent.

It is a deterministic agent.

On the otherhand assume the state has no information about the history, in which case at every point you only know its current status and nothing about where it was previously. In this case, it is a stochastic environment because you can define a distribution with greater than 0 entropy/uncertainty over possible next states.

• Technically in the last paragraph, what you have constructed may still be deterministic (or not), but the state description will definitely be non-Markov. Jul 16, 2019 at 7:17
• Also, critically this answer misses on the interpretation of "depends on". Often that allows for stochastic dependencies, and that is usually intended in descriptions of MDPs, and "depends on" can also be "correlates with". However, a strict reading in normal English might interpret it as meaning deterministic as you have put. I often add "and a random factor" to the list of things the next state and reward can depend on, as clarification when describing Markov property Jul 16, 2019 at 7:23