# Markov Decision Processes and Value Iteration — Artificial Intelligence

Source: https://www.skillbyai.com/en/artificial-intelligence/l-mdp

> Planning when actions have uncertain results.

## States, actions, rewards, discount

A **Markov decision process (MDP)** describes sequential decisions under uncertainty: states, actions, **transition probabilities**, **rewards**, and a **discount factor** that values sooner rewards more. The goal is a **policy** (what to do in each state) that maximises expected total reward. When the model is known, **value iteration** repeatedly updates each state's value from the best action's expected reward plus discounted next-state value until values converge; the best action in each state forms the optimal policy.

## Value iteration in a slippery corridor, run

I ran this with plain Python 3 (standard library only), with fixed random seeds where randomness is used. In a five-cell corridor with +10 at the right end, -10 at the left, -1 per move and moves that succeed only 80% of the time, value iteration gives values rising from 0.08 to 6.92 towards the goal and a policy of always moving right.

```python
# 1x5 corridor: reward +10 at the right end, -10 at the left end, -1 per move; moves succeed 80%
states = range(5); terminal = {0: -10, 4: 10}; gamma = 0.9
V = [0.0] * 5
def q(s, a):
    intended = s + (1 if a == "right" else -1); other = s - (1 if a == "right" else -1)
    val = 0
    for nxt, p in [(intended, 0.8), (other, 0.2)]:
        nxt = min(4, max(0, nxt))
        val += p * (-1 + gamma * (terminal.get(nxt, 0) if nxt in terminal else V[nxt]))
    return val
for it in range(50):
    V = [terminal[s] if s in terminal else max(q(s, "left"), q(s, "right")) for s in states]
policy = ["exit" if s in terminal else max(["left", "right"], key=lambda a: q(s, a)) for s in states]
print("values :", [round(v, 2) for v in V])
print("policy :", policy)
```

Output:

```
values : [-10, 0.08, 4.0, 6.92, 10]
policy : ['exit', 'right', 'right', 'right', 'exit']
```

## Choose the discount deliberately

A low discount makes agents short-sighted; a discount near 1 values long-term reward but converges more slowly.

**Quiz:** What does value iteration need that Q-learning does not?

- [x] A known model of transitions and rewards
- [ ] A reward signal
- [ ] States
- [ ] Actions

*Answer:* A known model of transitions and rewards. Value iteration plans with a model; Q-learning learns from experience.