# Real-life examples of Markov Decision Processes

I've been watching a lot of tutorial videos and they are look the same. This one for example: https://www.youtube.com/watch?v=ip4iSMRW5X4

They explain states, actions and probabilities which are fine. The person explains it ok but I just can't seem to get a grip on what it would be used for in real-life. I haven't come across any lists as of yet. The most common one I see is chess.

Can it be used to predict things? If so what types of things? Can it find patterns amoung infinite amounts of data? What can this algorithm do for me.

Bonus: It also feels like MDP's is all about getting from one state to another, is this true?

A Markovian Decision Process indeed has to do with going from one state to another and is mainly used for planning and decision making.

## The theory

Just repeating the theory quickly, an MDP is:

$$\text{MDP} = \langle S,A,T,R,\gamma \rangle$$

where $$S$$ are the states, $$A$$ the actions, $$T$$ the transition probabilities (i.e. the probabilities $$Pr(s'|s, a)$$ to go from one state to another given an action), $$R$$ the rewards (given a certain state, and possibly action), and $$\gamma$$ is a discount factor that is used to reduce the importance of the of future rewards.

So in order to use it, you need to have predefined:

1. States: these can refer to for example grid maps in robotics, or for example door open and door closed.
2. Actions: a fixed set of actions, such as for example going north, south, east, etc for a robot, or opening and closing a door.
3. Transition probabilities: the probability of going from one state to another given an action. For example, what is the probability of an open door if the action is open. In a perfect world the later could be 1.0, but if it is a robot, it could have failed in handling the doorknob correctly. Another example in the case of a moving robot would be the action north, which in most cases would bring it in the grid cell north of it, but in some cases could have moved too much and reached the next cell for example.
4. Rewards: these are used to guide the planning. In the case of the grid example, we might want to go to a certain cell, and the reward will be higher if we get closer. In the case of the door example, an open door might give a high reward.

Once the MDP is defined, a policy can be learned by doing Value Iteration or Policy Iteration which calculates the expected reward for each of the states. The policy then gives per state the best (given the MDP model) action to do.

In summary, an MDP is useful when you want to plan an efficient sequence of actions in which your actions can be not always 100% effective.

Can it be used to predict things?

I would call it planning, not predicting like regression for example.

If so what types of things?

See examples.

Can it find patterns among infinite amounts of data?

MDPs are used to do Reinforcement Learning, to find patterns you need Unsupervised Learning. And no, you cannot handle an infinite amount of data. Actually, the complexity of finding a policy grows exponentially with the number of states $$|S|$$.

What can this algorithm do for me.

See examples.

## Examples of Applications of MDPs

• White, D.J. (1993) mentions a large list of applications:
• Harvesting: how much members of a population have to be left for breeding.
• Agriculture: how much to plant based on weather and soil state.
• Water resources: keep the correct water level at reservoirs.
• Inspection, maintenance and repair: when to replace/inspect based on age, condition, etc.
• Purchase and production: how much to produce based on demand.
• Queues: reduce waiting time.
• ...
• Finance: deciding how much to invest in stock.
• Robotics:

And there are quite some more models. An even more interesting model is the Partially Observable Markovian Decision Process in which states are not completely visible, and instead, observations are used to get an idea of the current state, but this is out of the scope of this question.

A stochastic process is Markovian (or has the Markov property) if the conditional probability distribution of future states only depend on the current state, and not on previous ones (i.e. not on a list of previous states).

• This is probably the clearest answer I have ever seen on Cross Validated. Oct 23, 2015 at 19:55
• Any chance you can fix the links? Some of them appear broken or outdated. Jun 28, 2016 at 19:40
• So any process that has the states, actions, transition probabilities and rewards defined would be termed as Markovian? Nov 22, 2018 at 11:54

Bonus: It also feels like MDP's is all about getting from one state to another, is this true?

• Since, MDP is about making future decisions by taking action at present, yes! it's about going from the present state to a more returning(that yields more reward) future state.

To answer the comment by @Suhail Gupta:

So any process that has the states, actions, transition probabilities and rewards defined would be termed as Markovian?

• The process to be called Markovian should also follow the Markov property along with what you have mentioned; the property says, "the future state depends upon the action taken in the present state and is not affected by the past states."
New contributor
ashokchhetri is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.