# Markov Decision process

## Introduction

Markov Decision process(MDP) is a framework used to help to make decisions on a stochastic environment. Our goal is to find a policy, which is a map that gives us all optimal actions on each state on our environment.

MDP is somehow more powerful than simple planning, because your policy will allow you to do optimal actions even if something went wrong along the way. Simple planning just follow the plan after you find the best strategy.

![](/files/-LvMRrVbvw9eHZ1pfPCK)

### What is a State

Consider state as a summary (then called state-space) of all information needed to determine what happens next. There are 2 types of state space:

* World-State: Normally huge, and not available to the agent.
* Agent-State: Smaller, have all variables needed to make a decision related to the agent expected utility.

### Markovian Property

Basically you don't need past states to do a optimal decision, all you need is the current state $$s$$. This is because you could encode on your current state everything you need from the past to do a good decision. Still history matters...

### Environment

To simplify our universe imagine the grid world, here your agent objective is to arrive on the green block, and avoid the red block. Your available actions are: $$\uparrow,\downarrow,\leftarrow,\rightarrow$$

![](/files/-LvMRrVdOMycPnw1-jQG)

The problem is that we don't live on a perfect deterministic world, so our actions could have have different outcomes:

![](/files/-LvMRrVfvHSMxbvYlzpn)

For instance when we choose the up action we have 80% probability of actually going up, and 10% of going left or right. Also if you choose to go left or right you have 80% chance of going left and 10% going up or down.

Here are the most important parts:

* States: A set of possible states $$S$$
* Model: $$T(s,a,s') \therefore P(s'|s,a)$$ Probability to go to state $$s'$$ when you do the action $$a$$ while you were on state $$s$$, is also called transition model.
* Action: $$A(s)$$, things that you can do on a particular state $$s$$
* Reward: $$R(s)$$, scalar value that you get for been on a state.
* Policy: $$\Pi(s)\rightarrow a$$, our goal, is a map that tells the optimal action for every state
* Optimal policy: $$\Pi^\*(s)\rightarrow a$$, is a policy that maximize your expected reward $$R(s)$$

In reinforcement learning we're going to learn a optimal policy by trial and error.

### Solving MDPs with Dynamic Programming

As stated earlier MDPs are the tools for modelling decision problems, but how we solve them? In order to solve MDPs we need Dynamic Programming, more specifically the Bellman equation.

But first what is dynamic programming? Basically it's a method that divides a problem into simpler sub-problems easier to solve, it's just really a divide and conquer strategy.

Dynamic programming is both a mathematical optimization method and a computer programming method, but both of them follow this divide and conquer mechanism. But on mathematics it's often used as an optimization tool. On programming is often implemented with recursion and is used on problems like find the shortest path on a graph and generation sequences.

Also you may find a term called memoization which is something that computer people use to improve the performance of those divide-and-conquer algorithms by memorizing sub problems that were already calculated.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leonardoaraujosantos.gitbook.io/artificial-inteligence/artificial_intelligence/markov_decision_process.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.