Tabular reinforcement learning on grid worlds
Post 34 gave us the vocabulary of reinforcement learning: agents, states, actions, rewards, and the idea that an agent improves by interacting with an environment. What it did not give us was a way to actually compute a good policy (a rule that chooses an action in each state). That is the job of this post. We will solve two grid worlds exactly with dynamic programming (exact value computation from a known model), then throw away the model and learn the same policies from raw experience. The payoff is concrete: on the Taxi environment, Q-learning reaches a mean reward of -168.24 after 500 episodes, while a random policy flounders around -345. The through-line we will follow is a single question that every method in this post answers differently: how much credit does a state deserve for a reward that arrives later? Dynamic programming answers it with a model, Monte Carlo answers it by waiting until the episode ends, and temporal-difference methods answer it one step at a time.
We build everything on two environments from Gymnasium, a standard reinforcement-learning environment library (its toy-text collection). FrozenLake is a 4x4 grid of ice with a goal and holes, 16 states and 4 actions, and slippery transitions that make the agent skid. Taxi is a 500-state, 6-action puzzle where a cab picks up and drops off passengers across four locations. Both are small enough that a table can hold every value, which is exactly what makes them the right place to see the algorithms clearly before we scale up.
The lay of the land
Before training anything, we look at what a random policy does. On FrozenLake, a random episode wanders through states like [0, 1, 0, 0, 0, 0, 4, 5] and ends with reward 0, because the agent fell in a hole or ran out of steps. Over 100 random episodes the mean reward is 0.02, and the mean episode length is 7.9 steps with a maximum of 31. The goal is rarely reached.
Taxi tells a different story. A random episode starts at state 386 and drifts through 286, 186, 86, and 98, collecting a reward of -345 because every step costs -1 and the cab never completes a delivery. Over 100 random episodes the mean reward is about -345. The two environments are a deliberate contrast: FrozenLake is stochastic with sparse rewards, Taxi is deterministic with a large state space and dense negative rewards. The poor random baseline is the number every method below has to beat.
Solving with a model
To beat that random baseline with a known model, we first package the environment as a Markov Decision Process, which packages states, actions, transition probabilities, rewards, and a discount factor into one object. If we know the transition model, we can compute the optimal value function directly. The Bellman equations express the value of a state in terms of the values of its successors, and that recursion is what makes exact solution possible. Value iteration applies the Bellman optimality equation repeatedly until the values stop moving. Policy iteration alternates between evaluating a fixed policy and improving it greedily.
The env.unwrapped.P table is the model: for each state and action it lists the possible next states, their probabilities, and the reward. Using that model, the core of value iteration is a single sweep over states, taking the best action at each one:
for s in range(nS):
max_q = -np.inf
for a in range(nA):
q = 0
for prob, next_s, reward, done in env.unwrapped.P[s][a]:
q += prob * (reward + gamma * V[next_s] * (not done)) # Bellman backup
max_q = max(max_q, q)
V[s] = max_q
On FrozenLake, value iteration converges in 228 sweeps and lands on a start-state value of 0.5420. Policy iteration reaches the same value but spends 809 evaluation sweeps getting there, because each outer improvement step runs a full policy evaluation to convergence. The two policies match exactly.