View on GitHub

relearn

A Reinforcement Learning Library for C++11/14

Roadmap

relearn now has most of the tabular methods of Sutton and Barto’s book [1]: from bandits and dynamic programming, through Monte Carlo, TD, n-step methods, planning and eligibility traces, to policy gradients, R-Learning and Monte Carlo Tree Search. Each one is tested against hand-worked steps and against the book’s own figures. A few are still to come (truncated TD(λ), off-policy traces, real-time dynamic programming, and a few more), and they are the first part of this plan.

This page is where it goes next. It is a plan, not a promise: there are no dates, the order may change, and each step is only done once it has been implemented, tested, documented and reviewed, like everything before it.

flowchart LR
    classic["1. finish the classics<br/>the tabular methods still to come,<br/>then function approximation"]
    games["2. the games<br/>verified, a watch mode,<br/>and new ones"]
    deep["3. DQN and its variants<br/>then deep policy gradients"]
    python["4. Python bindings"]
    sims["5. simulators and<br/>game engines"]
    llm["6. RL for language models<br/>(exploratory)"]
    classic --> games --> deep
    deep --> python
    deep --> sims
    deep --> llm

What stays the same

Whatever gets added, a few things don’t change:

1. Finishing the classics

The tabular methods still to come

The book has a few more tabular methods that relearn doesn’t have yet (the whole n-step family of Chapter 7 is now in, have a look at n_step.md, and so are true online TD(λ) and Sarsa(λ), in eligibility_traces.md, and Actor-Critic with eligibility traces, episodic and for tasks that never end, in policy_gradient.md, and off-policy Monte Carlo prediction with every importance sampling of Chapter 5, in monte_carlo.md). What is left are the smaller or rarer ones:

Function approximation

Chapters 9 and 10. Instead of one value per state and action, the values come from a function q̂(s, a, w) whose weights w are learnt, so that what is learnt about one state carries over to the states near it. This is what makes continuous and very large state spaces possible:

Do bear in mind that a table is simply linear function approximation with one feature per state and action, all of them 0 but one. So relearn’s true online TD(λ) and Sarsa(λ) are the table’s case of the book’s linear ones, and once function approximation is in, they will work with features too.

note: function approximation, bootstrapping and off-policy learning together can make the weights diverge (the book calls it the deadly triad, Section 11.3), so the control examples will use Sarsa, as the book does, and the docs will explain why.

2. The games

New games, to show each algorithm at its best

Every algorithm already has a game, but some of them deserve one that shows what they are really good at. These would all be written from scratch in C++, header-only, in examples/games/, like the current ones (the ones that come from Gymnasium included, as FrozenLake was), and drawable in the watch mode. In the order of the roadmap:

Game What it shows Learnt with Source
Drifting bandit arms whose values drift over time: a constant step size against sample averages ε-Greedy, UCB, gradient bandit Exercise 2.5 [1]
Jack’s car rental dynamic programming on a model with thousands of transitions (Figure 4.2) policy iteration, value iteration Example 4.2 [1]
Racetrack learning to drive round a bend from another policy’s play, then planning it in real time off-policy Monte Carlo, real-time DP Exercise 5.12, Example 8.6 [1]
Taxi a pick-up and a drop-off, with wrong moves punished: a small test bench for the whole n-step family Q-Learning, Sarsa, tree backup, Q(σ) [14]
Superoptimiser writing the shortest program, below, step by step MCTS, Q-Learning, linear function approximation [12], [13]
Connect Four a game too big for a table, played by planning alone MCTS  
Mountain Car, the book’s way tile coding, and traces that make a slow task fast (Figures 10.1 and 12.10) semi-gradient Sarsa, Sarsa(λ), true online Sarsa(λ) Example 10.1 [1]
Acrobot a harder swing-up, with four continuous variables semi-gradient Sarsa, then DQN Gymnasium
Pac-Man, small a few hand-made features (the nearest ghost, the nearest pellet) instead of a table linear function approximation  
Snake learning from the whole grid, in retro pixels DQN and its variants  
Lunar Lander landing softly, with discrete then continuous thrust DQN, then SAC Gymnasium
Pendulum a continuous action: how hard to push Gaussian policies, DDPG, TD3, SAC Gymnasium
Drone, in 2D hovering and landing in random wind, so that the policy copes with a world it hasn’t seen PPO, SAC, domain randomisation  
Boat, in 2D docking in a current, with noisy sensors PPO, SAC  
Arithmetic a tiny language model learning to add, rewarded only when it is right GRPO, RL with verifiable rewards [10]

The superoptimiser game

A game where the agent writes a program, one instruction at a time, and is rewarded for getting the answer right with as few instructions as possible: an idea from superoptimisation, which AlphaDev [12] took to real sorting routines with RL, and STOKE [13] with a random search.

Basically it is a puzzle with a tiny model of the world (the processor), so MCTS can solve it by planning, Q-Learning by trial and error on short programs, and linear function approximation once the programs get longer. Do bear in mind that the features matter more than anything here: “instruction X at position i” can’t tell that a register written at one step is read at another, whereas features from the program’s data flow (which registers are written, read, still needed) can. Showing that difference is half the point of the game.

3. DQN and its variants

Deep Q-Networks [2] replace the table with a neural network, and add the two things that make that stable: a replay buffer, which learns from random mini-batches of past steps, and a target network, a copy of the network that is updated only every so often. Then the variants, each of which fixes one weakness:

Variant What it adds
Double DQN [3] picks the next action with one network and values it with the other, as Double Q-Learning does
Dueling DQN splits the network into the value of the state and the advantage of each action
Prioritised replay replays more often the steps whose error is largest
n-step returns learns from the next n rewards, as in Chapter 7
Noisy Nets explores by learning noise in the weights, instead of ε-Greedy
Distributional (C51, QR-DQN) learns the whole distribution of the return, not just its mean
Rainbow [4] Double DQN, Dueling, prioritised replay, n-step returns, Noisy Nets and C51, together

The plan is for relearn to own the algorithm (the replay buffer, the targets, the target network, the schedules), and to leave the network itself to a backend behind a small interface, which works on batches:

After DQN, the deep policy gradient methods follow the same pattern: A2C, PPO [5], DDPG, TD3 and SAC [6].

4. Python bindings

Most people train in Python, so relearn should be easy to reach from it, in both directions:

Basically, you should be able to train in Python as you do today, and run the very same environment and policy in C++.

5. Simulators and game engines

Every simulator goes through the same environment interface the games already use (reset, step and actions), so no algorithm ever depends on a particular simulator. Each one would be its own optional sub-project:

Game engines

A game engine’s world can be the environment: the engine steps the physics, and relearn chooses the actions. Each engine would get a thin adapter, run headless and faster than real time for training, and with graphics to watch the agent play. In order:

Engine Why How relearn would plug in
Godot open source (MIT), small, and extended in C++ a GDExtension: relearn compiled straight into the game
Unreal Engine C++ throughout, and the engine behind CARLA a plugin module, next to its own Learning Agents plugin
Unity the most used, and home of ML-Agents a native plugin (relearn behind a small C interface, called from C#)
O3DE open source (Apache 2.0), C++, with ROS 2 support for robots a Gem (O3DE’s name for a module)

The raylib window of the watch mode is not an engine, just a library for drawing, which is why it is enough for relearn’s own games.

6. RL for language models (exploratory)

Reinforcement learning is now part of how language models are trained, and the ideas behind it are the policy gradients of Chapter 13 [1], applied to a policy that writes one token at a time:

This one is exploratory. The aim would be to implement these algorithms clearly, test them, and run them on small models through the same backends as DQN, so that they can be studied and understood; not to train large models.

References

  1. Sutton, R.S. and Barto, A.G., 2018. Reinforcement Learning: An Introduction, 2nd edition. Cambridge, MA: MIT Press.
  2. Mnih, V. et al., 2015. Human-level control through deep reinforcement learning. Nature, 518, pp. 529 to 533.
  3. van Hasselt, H., Guez, A. and Silver, D., 2016. Deep reinforcement learning with double Q-learning. AAAI.
  4. Hessel, M. et al., 2018. Rainbow: combining improvements in deep reinforcement learning. AAAI.
  5. Schulman, J. et al., 2017. Proximal policy optimization algorithms. arXiv:1707.06347.
  6. Haarnoja, T. et al., 2018. Soft actor-critic: off-policy maximum entropy deep reinforcement learning with a stochastic actor. ICML.
  7. Ernst, D., Geurts, P. and Wehenkel, L., 2005. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, pp. 503 to 556.
  8. Bellemare, M.G. et al., 2013. The Arcade Learning Environment: an evaluation platform for general agents. Journal of Artificial Intelligence Research, 47, pp. 253 to 279.
  9. Ouyang, L. et al., 2022. Training language models to follow instructions with human feedback. NeurIPS.
  10. Shao, Z. et al., 2024. DeepSeekMath: pushing the limits of mathematical reasoning in open language models. arXiv:2402.03300.
  11. Rafailov, R. et al., 2023. Direct preference optimization: your language model is secretly a reward model. NeurIPS.
  12. Mankowitz, D.J. et al., 2023. Faster sorting algorithms discovered using deep reinforcement learning. Nature, 618, pp. 257 to 263.
  13. Schkufza, E., Sharma, R. and Aiken, A., 2013. Stochastic superoptimization. ASPLOS.
  14. Dietterich, T.G., 2000. Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research, 13, pp. 227 to 303.