Reinforcement Learning: Value Iteration and Q-Learning

Reinforcement learning (RL) is the branch of machine learning that studies how an agent should act in an environment in order to maximize a cumulative reward signal. Unlike supervised learning, there is no labeled dataset saying “here is the right action for this input”. Instead the agent must discover, through trial and error, which sequences of actions eventually pay off. This framing captures an enormous range of practical problems: robots learning to walk, programs learning to play board games, recommender systems learning what content to surface, and adaptive controllers for chemical plants, elevators, and datacenter cooling systems.

In this chapter we implement two classical RL algorithms in Gerbil Scheme, both from scratch and with no external dependencies. The first, Value Iteration, solves a fully known Markov Decision Process by directly computing the optimal value of every state. The second, Q-Learning, drops the assumption that the transition model is known and learns action values by simply interacting with an environment. Value Iteration and Q-Learning are the two canonical algorithms in the field, and they illustrate the two very different worlds RL practitioners work in: model-based planning versus model-free learning.

A Markov Decision Process (MDP) is the standard mathematical framework for RL. An MDP consists of:

• A finite set of states .
• A finite set of actions .
• A transition function giving the probability of ending in state after taking action in state .
• A reward function giving the expected immediate reward for taking action in state .
• A discount factor that weighs immediate rewards more heavily than distant ones.

The Markov property is that the next state depends only on the current state and action, not on the history that led to the current state. This assumption is what makes the problem tractable, and it is a surprisingly good approximation in many domains.

A policy is a rule that tells the agent which action to take in each state. The value of following policy starting in state is the expected discounted return:

The goal of RL is to find the optimal policy that maximizes this expected return from every state.

The optimal value function satisfies the recursive Bellman optimality equation:

This equation says: the value of the best action from state equals the immediate reward plus the discounted expected value of where you end up. Once we know , the optimal policy is trivially derived by acting greedily with respect to it:

Value Iteration solves the Bellman equation by turning it into an update rule. Starting from everywhere, we repeatedly apply:

This contraction converges to for any . In practice we stop when the maximum change across all states over one sweep drops below a small threshold.

Value Iteration requires the full transition and reward model of the environment. When we have that model, it is elegant and exact.

In many real problems we do not know and . The agent has to learn purely from experience. This is what Q-Learning does. Instead of storing a value per state, we store a Q-value for every state-action pair. Given a transition observed during play, we update:

The bracketed quantity is called the temporal-difference (TD) error. It is the discrepancy between our current estimate of and the newly observed one-step lookahead. The learning rate controls how aggressively we pull our estimate toward the new evidence.

If the agent always picks the action it currently thinks is best, it will never discover superior alternatives. To break out of this trap, Q-Learning uses an \epsilon$-greedy strategy: with probability take a random action (exploration), otherwise take the current best action (exploitation). Over the course of training we anneal from a large value (say 1.0) down to a small floor (say 0.01), so the agent explores aggressively early and exploits its learned knowledge later.

The project directory source_code/reinforcement-learning contains:

Each Scheme file is self-contained: no shared modules, no external data files, and no dependencies beyond Gerbil’s standard library.

The first example plants an agent in a grid with a rewarding goal cell and a punishing trap. The environment is deterministic: attempting to move up in cell 4 always lands in cell 1. Attempting to walk into a wall keeps the agent in place.

We number the cells row-major from to :

The rewards are attached to actions taken from these cells (rather than to arriving there), so any action from cell 8 pays out +10 and any action from cell 5 pays out -5.

The file begins with imports and two small helpers for pretty-printing floating-point numbers. Gerbil’s default float printing produces long decimal expansions (like 65.6100000000...), which is inconvenient for reporting value functions:

The transition model is naturally represented as a 3-dimensional array indexed by action, source state, and next state. Gerbil vectors are one-dimensional, so we build a 3D vector by nesting:

Reading a single probability out of then requires three vector-ref calls: (vector-ref (vector-ref (vector-ref P a) s) sp).

The core algorithm is a direct translation of the Bellman update. We sweep over every state, compute the value of each action as the immediate reward plus the discounted expected value of successor states, keep the best action, and remember both the new value and the greedy policy:

The termination criterion max-delta < threshold is the numerical realization of “the values have stopped changing”.

The main function wires up the grid dynamics. The four actions are UP, RIGHT, DOWN, and LEFT, encoded as , , , . Given a state we compute its row and column, apply the direction, clip to the grid boundary (bounce), and set the transition probability to 1.0:

The reward matrix is initialized to zero everywhere and then patched: any action from the goal cell 8 gives +10, and any action from the trap cell 5 gives -5:

Run either make run-mdp or invoke the interpreter directly:

• Optimal policy arrows show the greedy action from every cell. From the top-left corner (cell 0) the best action is RIGHT, which begins the path 0 -> 1 -> 2 -> 5 -> 8. Even though cell 5 is a trap, the policy is willing to accept the -5 penalty once because reaching the goal is worth so much more.
• Value function: cell 8 has value 100.0, which is the goal reward of 10 amplified through the loop where every action from cell 8 collects another +10 discounted by . The infinite geometric series sums to exactly .
• Value monotonicity: values decrease with distance from the goal, from 100.0 at cell 8 down to 65.61 at cell 0. Each step away from the goal multiplies the payoff by .
• Cell 5 = 85.0: even though cell 5 is a trap, its value is still positive and high, because from cell 5 you can immediately move DOWN into the goal at cell 8. The trap penalty is paid once, but the goal payoff dominates.
• 154 iterations: the algorithm converged in 154 sweeps to a maximum change of less than . The convergence rate is governed by : a larger means longer-horizon planning and therefore more iterations before things settle.

The second example is much more interesting because the agent no longer knows the environment ahead of time and the environment itself is stochastic. FrozenLake is a grid modelled after a slippery frozen pond:

• S is the start (cell 0).
• G is the goal (cell 15). Stepping onto G yields a reward of +1 and ends the episode.
• H cells are holes. Stepping into H ends the episode with reward 0.
• F are frozen cells that are safe to walk on.

The twist is that the ice is slippery. With probability the agent slips and moves in one of the two orthogonal directions instead of the one it chose. This means the agent cannot deterministically follow any path; it has to learn a policy that is robust to slipping.

The environment holds its state in a Gerbil hash table:

frozen-lake-step! implements the slippery dynamics. If slippery is true, it flips a coin: with probability the requested action is replaced by or (a -degree slip). Otherwise the action goes through as intended:

The step function returns an association list with three keys: the new state, the reward received, and a boolean indicating whether the episode is over.

The Q-table is a vector of vectors: 16 states, each with a 4-element vector of Q-values (one per action). Two small helpers, argmax and vector-max, extract the greedy action and best Q-value for a state:

To measure progress during training we need a way to run the greedy policy that Q currently implies, without any exploration noise, and count how often it reaches the goal. evaluate runs a fixed number of episodes (default 100) using pure argmax action selection and returns the fraction of episodes that ended in success:

Note the 100-step cap. Without it, a very bad or oscillating policy could loop forever on the ice without ever hitting a hole or the goal.

Here is the heart of the algorithm. For each of 10,000 episodes we reset the environment and take actions until we finish. Each action is chosen either randomly (with probability ) or greedily. After each step we update the Q-value for the chosen state-action pair using the temporal-difference rule:

Every 1000 episodes we run the evaluator so the reader can watch the policy improve. After each episode is multiplied by , so after 10,000 episodes it has decayed from toward the floor of .

main wires everything together, prints the environment summary, trains the Q-table, then displays the learned greedy policy and a final held-out evaluation over 1000 episodes:

Because Q-learning involves random exploration and a stochastic environment, the exact numbers change on every run. A representative session looks like this:

The most immediately surprising thing about the learned policy is that it does not look at all like “walk toward the goal”. Many cells appear to point away from the goal. This is the fingerprint of a policy that has learned to exploit the slipperiness of the ice.

Consider cell 0 (top-left), where the policy says LEFT. The agent obviously cannot walk further left than the wall. What actually happens is that pressing LEFT with slip probability yields:

• chance to actually go LEFT (stay in cell 0).
• chance to slip UP (also stay in cell 0).
• chance to slip DOWN (move to cell 4, a safe frozen cell).

The nominal “LEFT” action is really “make progress downward without ever risking a slip into the deadly hole at cell 5”. The agent has learned to use the wall to filter out dangerous slips. This is a classic and beautiful phenomenon in stochastic RL: the optimal action often has to be chosen for its distribution of outcomes rather than its intended direction.

Other observations:

• Success rates oscillate during training. Because is still positive, exploration occasionally overwrites good Q-values with noisy ones. This is unavoidable in tabular Q-learning without more advanced tricks like target networks or Double Q-learning.
• Final success rate around 0.75–0.80 is typical for this environment and this algorithm. The theoretical maximum success rate on slippery FrozenLake with a Q-learning agent is a bit above 0.80. Getting significantly higher requires either less slipperiness or more sophisticated algorithms.
• The learned policy is not unique. Repeated runs produce different arrangements of arrows, all of which are approximately optimal. Any two policies that agree on the “moves that trigger the right slip distribution” have roughly equal expected return.

Value Iteration and Q-Learning are the two founding algorithms of reinforcement learning, and both fit comfortably into a few hundred lines of readable Gerbil Scheme. The exercise reveals several ideas that generalize far beyond these toy examples:

• Bellman equations turn planning into a fixed-point computation. Whenever you can write a recursive characterization of the value function, you can build a solver by iterating it.
• Model-free learning is simply model-based planning with a moving estimate. The Q-learning update rule is the Bellman update rule with the transition and reward model replaced by one sample of experience.
• Exploration is not a nuisance to be minimized, it is a first-class part of the algorithm. -greedy decay is a specific choice; entire subfields of RL exist to design better exploration strategies.
• Stochastic dynamics reward counterintuitive policies. Learning “walk away from the goal” is often correct on FrozenLake, because it neutralizes the slipperiness.

Gerbil Scheme’s combination of vectors, hash tables, and named let loops makes it a natural language for these numerical experiments. The imperative flavor of the code, with set! and vector-set!, may feel unusual to Schemers coming from a purely functional background, but it maps directly onto how these algorithms are described in textbooks and helps keep the code close to the theory.

1. Deterministic FrozenLake: Call (make-frozen-lake #f) instead of (make-frozen-lake #t) and rerun q-learning. Report the final success rate and describe how the learned policy differs from the slippery case. Explain why the arrows now point unambiguously toward the goal.

2. Sweep the Discount Factor: In mdp_demo.ss, run value-iteration with gamma set to 0.5, 0.7, 0.9, and 0.99. Report the number of iterations to convergence and the value at cell 0 for each . Explain the relationship between and convergence rate.

3. Slower Epsilon Decay: Change the decay argument in q-learning from 0.999 to 0.9995 and rerun. Does the final success rate improve? Does the training take noticeably longer to reach a stable policy? Explain how the exploration schedule affects sample efficiency.

4. Add a Reward Shaper: Modify frozen-lake-step! so that stepping onto a hole yields reward -1.0 instead of 0.0. Re-train and report how the learned policy changes. Discuss the tradeoffs of reward shaping versus letting the agent learn purely from the terminal +1 signal.

5. Larger Grid World: Generalize mdp_demo.ss from to . Place a goal at the bottom-right corner, a trap somewhere in the interior, and run value iteration. Print the value function as a heat map (using formatted numbers in a grid layout) and the policy arrows side by side.

6. Q-Learning on the 3×3 Grid: Port the deterministic 3×3 grid world from mdp_demo.ss into a Q-learning environment analogous to FrozenLake and train a Q-table on it. Compare the learned policy and value estimates against the exact solution from Value Iteration. This exercise directly demonstrates the connection between model-free learning and model-based planning.

7. Double Q-Learning: Q-learning is known to suffer from maximization bias: the term systematically overestimates true action values. Implement Double Q-Learning, which maintains two independent Q-tables and and uses one to select the greedy action and the other to evaluate it. Compare final success rates against vanilla Q-learning across ten training runs.

8. SARSA: Implement SARSA, the on-policy sibling of Q-learning. Instead of updating toward , SARSA updates toward where is the action actually taken by the current -greedy policy. Compare SARSA’s learned policy with Q-learning’s on slippery FrozenLake and explain any qualitative differences (SARSA is typically more conservative near cliffs and holes).