FrozenLake Learning Agents

The problem

Project 2 of 3 for the Artificial Intelligence course at the Universitat de les Illes Balears — the one on reinforcement learning.

FrozenLake is a 4×4 grid with holes: you start at one corner, the goal is the opposite one, and falling in ends the episode. With is_slippery=True the ice does the interesting part — the action you choose is only the intended direction, and the environment may push you sideways instead.

The reward is 1 for reaching the goal and 0 everywhere else, so there is no gradient to follow. The agent gets one bit of feedback at the very end of an episode and has to work out which of the moves that led there deserved the credit. On a board where most early episodes end in a hole, most of them teach nothing at all.

That is the whole difficulty, and it is why four methods that look unrelated all apply to it.

How it works

Three of the four estimate an action-value function Q(s, a) and differ in when and from what they update it. The fourth never estimates a value at all.

• Monte Carlo — plays whole episodes, then walks each one backwards accumulating the return and stores Q(s, a) as the mean of every return ever seen for that pair. Without bootstrapping, the reward only travels through complete returns, so it needs far more successful episodes than the others to settle.
• Q-learning — off-policy temporal difference, updating on every step towards r + γ·max Q(s',·). It learns about the greedy policy while behaving ε-greedily, with ε decaying by 0.9995 per episode down to a floor of 0.01.
• SARSA — the on-policy counterpart, identical but for the target: it uses the value of the action it actually took next rather than the best available one, so the policy it converges on accounts for its own exploration. On slippery ice that is the difference between an optimistic route and a cautious one.
• Genetic algorithm — no value estimation. An individual is one action per state, that is, a whole deterministic policy. It keeps a population of 100, scores each by playing it, breeds the top 20% with a single-point crossover, mutates zero to two genes, rejects duplicates and stops when the best clears a fitness of 0.9. The winner is written back into a Q-table as a one-hot row per state, so it answers the same actua() call as the other three.
• One interface, one comparator — all four extend the course’s agent base class, which is what lets the comparator train them, evaluate each over 1000 greedy episodes and put their cumulative success rates on a single chart.

Because the ice is stochastic, no policy reaches 100%. The best one can only maximise the probability of arriving, never remove the risk.

Running it

Requires Python 3.10 or newer, gymnasium, matplotlib, seaborn and the course’s iaLib, all pinned in the repository’s requirements.txt. Both entry points run from the repository root:

pip install -r requirements.txt
python -m P2                      # train one agent, plot it, then watch it play
python -m P2.comparador_agentes   # train all four and chart them against each other

The first draws a heatmap of the learned Q* with an arrow per state, and the distribution of the states and actions visited during training, before opening the environment and playing an episode under the learned policy.