By: Themis Haris
Date: June 2026
Reinforcement Learning (RL) is about developing algorithms to make decisions based on a reward landscape. These algorithms yield so called policies, which are ways to navigate complex state-space systems. The machine making decisions on behalf of a policy is called an agent.
For example, consider the problem of teaching a machine to play tetris. At each point in time, the machine is faced with a state — what blocks have been layed out and what block is on the way. It is also able to make a decision: where and how to place the incoming block. Based on its decisions the state gets updated and the game continues.
Reinforcement learning is about teaching the agent how to play via a training cycle of interactions with their environment.
This tutorial is a walkthrough over the fundamental algorithms and ideas that one needs to know in order to get a solid foundation of RL. We will cover algorithms that show up specifically in the context of deep learning, where we use neural networks to represent and learn courses of action in complex systems.
Beyond the theoretical foundations, we will also look at implementation and see these methods in practice. We will be using the Gymnasium library from OpenAI to train an RL agent to do all sorts of cool things.
We will work in the following idealized setting. We consider a state space $\mathcal{S}$, observation space $\mathcal{O}$ and action space $\mathcal{A}$. These are sets that can be continuous (e.g. the position of a robot) or discrete (e.g. a chess board). The observation space represents the fact that we might not always be able to fully know the state we are in; instead we are only equipped with the observations we make about the world.
Once inside these spaces, we imagine a time variable $t$ indexing the timestep we are in. At time $t$, we are at state $s_t$ witnessing observation $o_t$. If we choose to take an action $a_t \in \mathcal{A}$, then that action lands us in state $s_{t+1} \in \mathcal{S}$. This gives a trajectory $\tau = (s_1,a_1,s_2,a_2,…,s_T)$ over a time-horizon with $T$ timesteps.
Once at state $s_t$, taking action $a_t$ doesn’t deterministically take us to state $s_{t+1}$. Instead we imagine that the next state is a random variable. The probability of seeing state $s_{t+1}$ given we take action $a_t$ at state $s_t$ is denoted by $p(s_{t+1} \mid s_t,a_t)$. These are called transition probabilities.
Notice the enormous assumption we making here: the next state depends only on the previous state and the action we take! This is often called the Markovian property. Indeed, we assume that the systems we are navigating are so called Markov Decisions Processes (MDPs).
This is a huge assumption and is often not true in the real world. MDPs are memoryless, since they forget about the past transcript and only care about the most recent state and action. Our decisions in the real world very often carry memory. The only way to incorporate memory in an MDP is by increasing the state space to include it, which often makes the problem intractable.
Nevertheless, MDPs are a fundamental abstraction and we use them because of their mathematical elegance. Many of the RL algorithms we will develop work well even if the Markovian property does not hold.
Once the agent takes an action, it interacts with its environment and gets back a reward $r(s_t,a_t)$. The goal of the agent is to learn a policy $\pi(\alpha_t \mid s_t)$ ****that will tell it which action to take at each state. $\pi$ could be a probability distribution over actions and it could also depend on a past window of observations: $\pi(a_t \mid o_{t-m:t})$.
Our goal will be to learn a policy that yields maximum reward over a trajectory with horizon $T$.
Note that the overall reward is what matters, not maximizing the reward over a handful of actions. A central theme throughout will be the tradeoff between exploration and exploitation: how do we prioritize learning about the state space before making drastic decisions that will “lock-in” our trajectory?