Markov Decision Processes and Value Iteration

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.

# 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.

Quick check: What does value iteration need that Q-learning does not?

• A known model of transitions and rewards
• A reward signal
• States
• Actions