Reinforcement Learning

What is Reinforcement Learning?

Reinforcement learning is a category of machine learning algorithms that solve very specific and complex problems by learning from the environment through trial and error, receiving feedback in the form of rewards or penalties. The goal is to learn a policy that maximizes the cumulative reward over time.

For example, how can you work with a dynamic system, such as a robot navigating a maze, or a self-driving car learning to drive in different traffic conditions? In these cases, you don’t have a label, neither a discrete or continuous output, the only thing you have is a feedback signal that tells you how well the algorithm interacts with the environment.

This is the essence of reinforcement learning, and what makes it a fundamentally different paradigm compared to other kinds of machine learning that rely on labeled or input-output data.

At its core, it is an optimization problem: it tries to find the best action for a given state.

Applications

Some application examples of reinforcement learning include:

• Robotics: train robots to perform complex tasks, such as grasping objects, walking, or flying.
• Self-driving cars: train self-driving cars to navigate complex traffic scenarios, such as merging onto highways or avoiding obstacles.
• High-frequency trading: develop trading strategies that adapt to changing market conditions based on real-time feedback from the market.
• Recommendation systems: despite being more commonly associated with supervised learning, reinforcement learning can also be used to optimize recommendation systems by learning from user feedback and adapting recommendations accordingly.

How it works

Reinforcement learning is based on the concept of an agent that interacts with an environment, and learns from the feedback it receives. So, the properties involved in a reinforcement learning problem are:

• Agent: The entity that takes actions in the environment to achieve a goal.
• Environment: The external system that the agent interacts with, which provides feedback in the form of rewards or penalties.
• State: The current situation or configuration of the environment, which the agent observes and uses to make decisions.
• Action: The choices or moves that the agent can make in response to the current state of the environment.
• Reward: The feedback signal that the agent receives from the environment after taking an action, which indicates how well it is performing in achieving its goal.
• Policy: The strategy or mapping that the agent uses to determine which action to take in a given state, based on its past experiences and the feedback it has received.

The combination of state, action, reward, and next state is called a Markov Decision Process (MDP), and it is what gives us a framework that allows us to model a dynamic environment.

graph LR
    S["State (Sₜ)"] -- "agent's policy" --> A["Action (Aₜ)"]
    A --> Env{{Environment}}
    Env --> R["Reward (Rₜ₊₁)"]
    Env --> S2["Next state (Sₜ₊₁)"]
    S2 -. "next step" .-> S

Genetic Algorithms

Genetic algorithms (GA) are a type of optimization algorithm that is inspired by the principles of natural selection and evolution. They are used to solve complex problems by iteratively improving a population of candidate solutions through selection, crossover, and mutation.

Vastly used in optimization problems, genetic algorithms can be applied to reinforcement learning to evolve policies that maximize the cumulative reward over time. By simulating the process of natural selection, genetic algorithms can explore a wide range of possible solutions and converge towards optimal or near-optimal policies for complex reinforcement learning tasks.

NEAT Architecture

NEAT (NeuroEvolution of Augmenting Topologies) is a specific type of genetic algorithm that evolves neural networks to solve reinforcement learning problems. It combines the principles of genetic algorithms with neural network architectures, allowing for the evolution of both the weights and the structure of the neural networks.

It has been used successfully in tasks such as game playing, where the model learns how to play a game by evolving its neural network architecture and weights over time.

EXAMPLE

This video is a cool example of how NEAT works in practice.

In this example, you will notice that:

1. The agent starts on state zero (S0)
2. Based on S0 the agent takes an action (A0)
3. Agent moves to the right, and environment changes to S1
4. S1 rewards the agent with a positive feedback (R1), so the agent learns that moving to the right is a good action

State observations

In reinforcement learning, the agent’s understanding of the environment is based on the current state or observations. The state can be represented in various ways, depending on the complexity of the environment and the problem being solved.

NOTE

A state is the complete description of the environment, while an observation is what the agent actually gets to see, which may not fully represent the environment, but only a fraction of it.

In a chess game, for example, the agent has full observability of the environment, meaning it can see the entire board and all the pieces. In contrast, in a 2D platform game, the agent may only have partial observability, meaning it can only see a limited portion of the environment at any given time. This can make the problem more challenging, as the agent must learn to make decisions based on incomplete information.

Depending on the limitations of the state observations, there will be a class of algorithms that are better suited for the problem.

A state is nothing but a representation of the current situation, derived from the way the environment can be configured. This means that highly complex environments can have a very large observability space: the number of possible states.

Action space

Which actions can the agent take in the environment? It can be a discrete set of actions — moving left, right, up or down in a grid world, or the legal moves available to a player in a game of chess — or a continuous set of actions, such as adjusting the speed and direction of a self-driving car.

The action space is defined by the environment and the specific problem we are trying to solve, so it is dictated by the rules of the environment and varies with the complexity of the task.

NOTE

Both the environment and the agent are coded by us, so we are the ones responsible for defining the “rules of the game”: what the states are, what the actions are, and how the rewards are assigned.

Reward function

The goal of every reinforcement learning algorithm is to maximize the cumulative reward over time. The reward function defines how the agent receives feedback from the environment based on its actions. It can be a simple binary signal (e.g., +1 for success, -1 for failure) or a more complex function that takes into account multiple factors, such as distance traveled, time taken, or resources used.

This is how you measure the performance of the agent, since you can’t use traditional metrics like accuracy or precision, the reward function is the only way to evaluate how well the agent is performing in achieving its goal.

At each step, the reward is just the feedback for the action you took in a given state:

$$r_t=R(s_t,a_t)$$

But the agent doesn’t care about a single step, it cares about the cumulative reward over time. That total, discounted into the future, is called the return:

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$

The $\gamma$ (gamma) is the discount factor, a number between 0 and 1 that decides how much future rewards count. Close to 0 the agent is myopic and only chases the next reward; close to 1 it plays the long game, weighing rewards far in the future almost as much as immediate ones.

NOTE

The discount is also what keeps the sum finite when a task never ends. Without it, an infinite stream of rewards would just add up to infinity and every policy would look equally good.

WARNING

It’s crucial to design a reward function that aligns with the desired behavior of the agent. A poorly designed reward function can lead to unintended consequences, such as the agent learning to exploit loopholes in the environment rather than achieving the intended goal.

Policy

The process of decision making in reinforcement learning is called policy, which is a mapping from states to actions: for a given state or environment observation, a given (or many) action(s) need to be performed by the agent.

A policy is essentially the agent’s strategy, and the brain behind its actions. In practical terms it can be represented as a neural network, where the input is the state (or observation) and the output is the action (or the action probabilities).

Exploration and exploitation

• Exploration: the agent behaves in a more “curious” way to discover new states and actions, helping it to learn more about the environment and gather more information for better decision-making.
• Exploitation: the agent uses its current knowledge to maximize rewards based on what it has learned so far.

Exploration is more used in the early stages of learning, while exploitation is more used in the later stages.

TIP

It’s crucial to find the right balance between both in order to achieve optimal learning and performance. An optimal agent should have explored enough of the environment to have figured out its “gotchas”, while also being able to take advantage of what it learned and exploit it.

A personal example of how this imbalance can be frustrating is YouTube recommendations these days. The algorithm feels too focused on exploitation: I keep seeing the same kind of content over and over, when it should also be exploring new things I might like.

Model-based and model-free methods

In reinforcement learning, you have model-based and model-free methods.

Model-based methods are more complex, with highly sophisticated algorithms that try to learn the environment’s dynamics.

Within model-free methods, you have value-based and policy-based methods, in order to learn the best policy for a given environment. Some can also be hybrid methods that combine both approaches.

Policy-based methods

• Directly learn the policy function that maps states to actions
• We estimate what’s the best action to be performed within the environment based on the given state
• There is no value function involved, the output of the policy is the action to be performed

Value-based methods

• Don’t train the policy, learn a value function that estimates the expected return (reward) for each state or state-action pair
• We give a value to each state or state-action pair, and the agent selects the one which will maximize the expected return
• This value is called the Q-value, which represents the expected cumulative reward (quality) for taking a specific action in a specific state
• The policy in this case is derived from the value function, which in practice is a function (like a neural network) that takes the state as input and outputs the Q-values for each possible action

In both cases, the policy itself is nothing but a function that maps states to actions, but the way it is learned differs between the two approaches.

Q-Learning

Q-learning is an example of value-based reinforcement learning. The function that estimates the Q-values is called the Q-function, and in its simplest form it is backed by a Q-table: a lookup table that maps all the possible state-action pairs to their corresponding Q-values. The Q stands for “quality”, the quality of a particular action taken in a specific state.

When a Q-table is initialized, all Q-values are typically set to zero or to a small random value. As the agent interacts with the environment and receives rewards, it updates them based on the observed outcomes. Over time the Q-values converge to represent the optimal action-value function, allowing the agent to make informed decisions and maximize its cumulative reward.

Training

The training of a Q-learning agent involves iteratively updating the Q-values based on the agent’s experiences in the environment, and it is done in episodes:

1. The number of episodes is a hyperparameter, and can therefore be tuned.
2. On each episode, the environment is reset: the agent is placed in a starting state.
3. The duration of each episode is also a hyperparameter, defining the maximum number of steps the agent can take before the episode ends — or until the agent reaches a terminal state, which in a game could be winning or losing it.
4. On each step, the agent selects an action based on its current state and the Q-values in the Q-table. The action selection can be done using an exploration-exploitation strategy, such as epsilon-greedy, where the agent sometimes explores random actions and sometimes exploits the best-known one, in a balanced manner as an attempt to reach the optimal policy.
5. After the action is taken, we observe the new state and the reward received from the environment. The agent then updates the Q-value for the chosen state-action pair using the Bellman equation, which allows it to calibrate its Q-values based on the observed outcomes and the expected future rewards.
6. The process continues until the episode ends, either by reaching a terminal state or by exceeding the maximum number of steps. The agent then starts a new episode, and the training repeats until the specified number of episodes is completed.
7. When an episode ends, the Q-table is not reset, so the agent retains the Q-values learned in previous episodes, allowing it to build upon its knowledge and improve its decision-making over time.

NOTE

SARSA (State-Action-Reward-State-Action) is a kind of Q-learning algorithm.

The Bellman equation

The Bellman equation is the value equation. It is how we calculate the Q-value for a state-action pair, based on the observed reward and the expected future rewards:

$$Q(s,a)\leftarrow Q(s,a)+\alpha \left[r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })-Q(s,a)\right]$$

Where:

• $Q(s,a)$ is the current Q-value for the state-action pair $(s,a)$
• $\alpha$ is the learning rate
• $r$ is the reward received after taking action $a$ in state $s$
• $\gamma$ is the discount factor
• ${\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$ is the maximum Q-value for the next state $s^{\prime }$ across all possible actions $a^{\prime }$. In other words, the maximum expected future reward that can be obtained by taking the best action in the next state, based on previous experiences — the Q-values currently sitting in the Q-table.

This is what allows the agent to update its Q-values based on the observed outcomes and the expected future rewards, so it learns an optimal policy over time.

Hyperparameters

Beyond the number of episodes and their duration, these are the knobs you tune:

• Epsilon (ε): controls the exploration-exploitation trade-off, by setting the probability of choosing a random action (exploration) instead of the best-known action (exploitation). A common strategy is to start with a high epsilon and gradually decrease it over time, letting the agent explore more in the early stages of training and exploit what it learned later on. This is known as epsilon decay, or epsilon-greedy decay.
• Learning rate (α): how much of a new experience gets written into the Q-value. A high learning rate means the agent trusts the latest experience more, so it learns faster but keeps overreacting to single lucky or unlucky steps instead of settling; a low one learns slower, in smaller and more stable steps.
• Discount factor (γ): how much future rewards count compared to immediate ones, as described in the reward function above.

Deep Q-Networks (DQN)

For environments with a large observability space, it is often impractical to use a Q-table to store all the possible state-action pairs. In such cases, function approximation methods — such as deep Q-networks (DQN) — can estimate the Q-values instead of relying on a tabular representation.

The main difference is that, instead of a Q-table, we have a neural network that takes the current state as input and outputs the Q-values for all the possible actions in that state. Nothing has to be mapped in a table beforehand. The network is trained with a variant of the Q-learning algorithm, where the loss function is defined by the difference between the predicted Q-values and the target Q-values derived from the Bellman equation.

The training process is similar to the one of a Q-learning agent, but instead of updating a Q-table we update the weights of the neural network based on the observed experiences, through backpropagation and gradient descent.

What's the difference between backpropagation and gradient descent?

Backprop measures how much each weight contributed to the loss, and gradient descent is what then nudges the weights in that direction. Two stages of the same loop.

NOTE

The Q-values of a DQN are really bad at the beginning of the training process, but they improve over time as the agent explores the environment and learns from it.

Deep reinforcement learning

Convolutional neural networks (CNNs) — which were initially designed for classification tasks — can be used to process visual input from the environment, such as images or video frames, and extract the relevant features for decision-making.

Combining these deep learning techniques with reinforcement learning is what gives us deep reinforcement learning (DRL), which can handle complex environments and learn from high-dimensional sensory input. This is how we reach a high level of generalization and adaptability, enabling agents to learn effective policies in environments with large state spaces and complex dynamics.

Pre-processing visual input

Pre-processing is very important on this kind of visual input task, both to compress the data and to remove the noise that could hinder the learning process. Common techniques include resizing the images, converting them to grayscale, or even removing the parts of the frame that don’t contribute to the decision-making — the background or the UI elements, for example.

This helps the agent focus on the most relevant information, for the same reason feature scaling matters on tabular data: the model learns better and converges faster when the input isn’t working against it.

Running experiments with Gymnasium

Gymnasium is a library that provides a wide range of ready-made environments for reinforcement learning.

To reproduce the same results across different runs of the training process, you can set a random seed for the environment, which keeps the random number generation consistent.

References

• Géron, A. Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems, 3rd ed. Sebastopol: O’Reilly Media, 2022.