Reinforcement Learning from First Principles

Small, explicit implementations of reinforcement-learning algorithms and experiments, based primarily on Sutton & Barto's Reinforcement Learning: An Introduction.

This repository is for understanding algorithms rather than providing a general-purpose RL library. The emphasis is on readable implementations, controlled experiments, and reproducing the qualitative behavior described in the literature.

Scope

The repository follows the classical reinforcement-learning path from bandits to direct policy optimization:

• multi-armed bandits and nonstationarity
• finite Markov decision processes and dynamic programming
• Monte Carlo prediction, control, and off-policy importance sampling
• TD(0), SARSA, and Q-learning
• n-step TD and n-step SARSA
• TD(lambda) and SARSA(lambda) with eligibility traces
• Dyna-Q and Dyna-Q+ model-based planning
• linear state aggregation and semi-gradient TD
• tile-coded semi-gradient SARSA on Mountain Car
• REINFORCE with and without a learned state-value baseline

The implementations deliberately expose the update equations and data flow rather than hiding them behind a general RL framework.

Setup

uv sync --dev

Run the tests:

uv run pytest

Experiments

Bandits:

uv run python experiments/bandits/compare_methods.py --runs 500 --steps 1000 --seed 0

Dynamic programming:

uv run python experiments/gridworld/compare_planning.py --output figures/value-iteration.png

Monte Carlo prediction and control:

uv run python experiments/monte_carlo/predict_gridworld.py --output figures/mc-prediction.png
uv run python experiments/monte_carlo/control_gridworld.py --episodes 30000 --epsilon 0.1
uv run python experiments/monte_carlo/compare_importance_sampling.py --episodes 20000

Temporal-difference learning:

uv run python experiments/temporal_difference/predict_random_walk.py --episodes 100 --alpha 0.1
uv run python experiments/temporal_difference/compare_control.py --runs 10 --episodes 500
uv run python experiments/temporal_difference/compare_n_step_prediction.py --runs 100 --episodes 10
uv run python experiments/temporal_difference/compare_n_step_control.py --runs 20 --episodes 500
uv run python experiments/temporal_difference/compare_lambda_prediction.py --runs 100 --episodes 20
uv run python experiments/temporal_difference/compare_lambda_control.py --runs 20 --episodes 500

Model-based planning:

uv run python experiments/planning/compare_dyna_q.py --runs 20 --episodes 50
uv run python experiments/planning/compare_dyna_plus.py --runs 20 --steps 6000

Function approximation:

uv run python experiments/approximation/compare_state_aggregation.py --states 19 --episodes 2000 --alpha 0.03
uv run python experiments/approximation/learn_mountain_car.py --episodes 200 --alpha 0.3

Policy gradients:

uv run python experiments/policy_gradient/compare_reinforce.py --runs 20 --episodes 1500

Structure

rl-foundations/
├── src/rl_foundations/
│   ├── bandits/
│   ├── mdp/
│   ├── monte_carlo/
│   ├── temporal_difference/
│   ├── planning/
│   ├── approximation/
│   └── policy_gradient/
├── experiments/
│   ├── bandits/
│   ├── gridworld/
│   ├── monte_carlo/
│   ├── temporal_difference/
│   ├── planning/
│   ├── approximation/
│   └── policy_gradient/
├── tests/
│   ├── mdp/
│   ├── monte_carlo/
│   ├── temporal_difference/
│   ├── planning/
│   ├── approximation/
│   └── policy_gradient/
└── notes/
    ├── 02-bandits.md
    ├── 03-mdps.md
    ├── 04-dynamic-programming.md
    ├── 05-monte-carlo.md
    ├── 06-temporal-difference.md
    ├── 07-n-step.md
    ├── 08-eligibility-traces.md
    ├── 09-planning.md
    ├── 10-function-approximation.md
    └── 11-policy-gradient.md

Roadmap

• Multi-armed bandits
• Finite Markov decision processes
• Dynamic programming
• Monte Carlo prediction and on-policy control
• Off-policy Monte Carlo methods
• Temporal-difference learning: TD(0), SARSA, and Q-learning
• n-step TD and SARSA
• Eligibility traces: TD(lambda) and SARSA(lambda)
• Planning and Dyna
• Linear function approximation
• Policy-gradient methods

References

• Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction, 2nd edition, Chapters 2-13.
• University of Alberta Reinforcement Learning specialization.