Elements of Reinforcement Learning

Introduction

Welcome to a new module in our journey. Having just concluded our deep dive into generative AI with diffusion models, we now pivot to an entirely different and foundational paradigm of machine learning: Reinforcement Learning (RL). While supervised learning learns from labeled data and unsupervised learning finds patterns in unlabeled data, reinforcement learning is about learning to achieve goals through interaction with an environment. It is the theoretical framework behind an agent that learns optimal behavior through trial and error.

This lesson establishes the fundamental vocabulary and conceptual structure of RL. We will define the five core components that form the basis of every reinforcement learning problem: the agent, the environment, the state, the action, and the reward. By the end of this lesson, you will be able to describe this interactive framework and formalize it mathematically as a Markov Decision Process, setting the stage for all subsequent RL concepts.

The Reinforcement Learning Paradigm

At its heart, RL is a framework for sequential decision-making. It stands apart from the supervised and unsupervised paradigms you've seen so far. The legendary RL researcher David Silver provides an excellent overview of these distinctions. His lecture will help you build a strong intuition for what makes RL a unique and powerful tool.

These characteristics—particularly the departure from IID data and the agent's active role in data collection—present unique theoretical challenges that we will unpack throughout this module.

The Agent-Environment Interaction Loop

The entire RL framework can be understood through the interaction between two primary entities: the agent and the environment.

• The Agent is the learner and decision-maker. It is the algorithm we are trying to design.
• The Environment is everything outside the agent. It is the world the agent interacts with, and it encompasses the problem or task the agent is meant to solve.

This interaction happens over a sequence of discrete time steps. At each step $t$, the agent receives information about the environment, selects an action, and the environment responds. This creates a continuous feedback loop.

The communication between the agent and the environment is mediated by three key components:

1. State ($s_t$): A representation of the environment at time $t$.
2. Action ($a_t$): A choice made by the agent at time $t$.
3. Reward ($r_{t+1}$): A scalar feedback signal received by the agent after taking action $a_t$ in state $s_t$.

Let's examine each of these components in more detail.

State and Observation

The state is a complete description of the world. An observation is a partial description. This distinction is critical.

For instance, in a game of chess, the state is the position of all pieces on the board. The environment is fully observed. In a game of poker, your observation consists of your own cards and the public cards, but the true state includes your opponents' cards, which are hidden. This is a partially observed environment.

Given your background, you'll appreciate the deeper theoretical distinctions here. The "state" can be decomposed further. David Silver's lecture provides a lucid breakdown.

The concept of the Markov state is the theoretical bedrock upon which most of RL is built. It allows us to make decisions based on the current state alone, without needing the entire history of interactions.

Action

The action is how the agent influences the environment. The set of all possible actions is called the action space.

The nature of the action space—whether it is discrete (a finite set of actions, like "up," "down," "left," "right") or continuous (actions are real-valued vectors, like the amount of torque to apply to a robot's joints)—has significant implications for the types of algorithms that can be used.

Reward and the Goal

The reward is a scalar signal, $r_t$, that indicates how well the agent is doing at a given time step. The agent's goal is to maximize not the immediate reward, but the cumulative reward over time. This concept is captured by the Reward Hypothesis.

This simple but powerful hypothesis allows us to frame complex goals in a mathematically tractable way. Designing a reward function that correctly specifies the desired behavior without leading to unintended "hacks" (like a robot sweeping dishes onto the floor to "clean" the counter) is a central challenge in applied RL known as reward engineering.

The sequence of states, actions, and rewards generated by the interaction loop is called a trajectory or an episode: $s_0,a_0,r_1,s_1,a_1,r_2,\dots$. The agent's ultimate objective is to learn a strategy for choosing actions that maximizes the total expected reward over such trajectories.

Formalizing the Framework: The Markov Decision Process (MDP)

When the environment is fully observable (i.e., the agent's observation is the true environment state) and possesses the Markov property, we can formalize the entire RL problem as a Markov Decision Process (MDP). The MDP is the canonical mathematical framework for RL.

An MDP is defined as a tuple $⟨S,A,P,R,{\rho }_0⟩$, where:

• $S$ is the set of all possible states (the state space).
• $A$ is the set of all possible actions (the action space).
• $P$ is the transition dynamics function, $P(s^{\prime }|s,a)=\mathrm{Pr}(s_{t+1}=s^{\prime }|s_t=s,a_t=a)$. It defines the probability of transitioning to state $s^{\prime }$ after taking action $a$ in state $s$.
• $R$ is the reward function. A common definition is $R(s,a,s^{\prime })$, the reward received after transitioning from $s$ to $s^{\prime }$ via action $a$.
• ${\rho }_0$ is the distribution of the initial state, $s_0$.

The following resources provide excellent formal definitions.

A Concrete Example: Grid World

Let's ground these abstract concepts in a simple example from the "Introduction to Deep Reinforcement Learning" paper.

This is a simple grid world environment. The agent (robot) starts at a designated position and must navigate to the trophy cell.

Let's define the MDP for this task:

• States ($S$): The set of 11 grid cells where the agent can be. $S=\{s_0,s_1,...,s_{10}\}$.
• Actions ($A$): The set of four cardinal movements: $\text{up},\text{down},\text{left},\text{right}$.
• Transition Function ($P$):
  • In a deterministic world, if the agent is in cell $s_0$ and takes the action 'right', the next state is $s_1$ with probability 1. $P(s_1|s_0,\text{’right’})=1$.
  • In a stochastic world, the action might fail. For example, trying to move 'right' might succeed with probability 0.9, but with probability 0.1, the agent stays in place. $P(s_1|s_0,\text{’right’})=0.9$ and $P(s_0|s_0,\text{’right’})=0.1$.
• Reward Function ($R$): As shown in the image, the reward is +1 for entering the trophy cell, and -0.01 for entering any other cell. The small negative reward encourages the agent to find the goal as quickly as possible.

This simple example encapsulates all the core components and their formal relationships within an MDP.

Conclusion

In this lesson, we have laid the theoretical groundwork for our study of Reinforcement Learning. We've moved from the high-level paradigm of learning through interaction to a precise, mathematical formulation.

Here are the key takeaways:

• The RL Framework: Consists of an agent learning to make decisions by interacting with an environment.
• Core Components: The interaction is defined by a loop of state representations, agent actions, and resulting rewards.
• Agent's Goal: To maximize the cumulative reward (the return) over a trajectory.
• The Reward Hypothesis: All goals can be represented as the maximization of expected cumulative reward.
• The MDP Formalism: In fully observable settings, the RL problem is formally modeled as a Markov Decision Process (MDP), defined by a tuple $⟨S,A,P,R,{\rho }_0⟩$. The Markov Property is the key assumption that makes this framework tractable.

We have defined the problem, but not yet the solution. The agent's "brain," or its strategy for choosing actions, is called a policy. How does an agent learn a good policy? How does it estimate the long-term value of being in a particular state?

In our next lesson, we will answer these questions by deriving the Bellman equation, a fundamental identity that relates the value of a state to the value of its successor states. This equation is the cornerstone of nearly all RL algorithms.