MDPs, Policies and Value

The ingredients

A Markov decision process has a set of states $S$, actions $A$, transition probabilities $P(s' \mid s, a)$, a reward for each transition, and a discount $\gamma$. Markov means the current state contains everything relevant: where you go next depends on where you are and what you do, not on how you got here. In the gridworld lab the state is the square, the actions are four moves, the transitions are deterministic, and rewards arrive only at the coin, the goal and the pit.

A policy $\pi(a \mid s)$ is the agent's behaviour: a probability for each action in each state (or a single fixed choice). Value functions score policies:

• $V^\pi(s)$: the expected return starting in $s$ and following $\pi$.
• $Q^\pi(s,a)$: the expected return after taking action $a$ in $s$, then following $\pi$.

The Bellman equation

Values are recursive: what a state is worth equals what you get now plus what the next state is worth, discounted. For the best possible behaviour:

$$Q^*(s,a) \;=\; \mathbb{E}\big[\, r + \gamma \max_{a'} Q^*(s', a') \,\big]$$

Tiny numeric example (gridworld, γ = 0.9): a square next to the +10 goal is worth 10, because you can step in now. One square further back is worth 0 + 0.9 × 10 = 9, the next 8.1, and so on back to the start, five moves away: $10 \times 0.9^4 \approx 6.56$. Heading for the coin instead, three moves away, is worth only $0.9^2 \times 1 = 0.81$ from the start, so the optimal policy walks to the goal.