The Reinforcement Learning Framework: Agents, Environments, and the Sequential Decision Problem

The Reinforcement Learning Framework: Agents, Environments, and the Sequential Decision Problem

1.1 Introduction: The Challenge of Learning from Interaction

Consider how a child learns to ride a bicycle. The child does not receive a detailed manual explaining the physics of balance, the mechanics of steering, or the optimal muscle activations for different inclines. Instead, the child interacts with the environment—attempting to balance, observing the consequences of leaning too far left or right, receiving feedback in the form of wobbles or tumbles, and gradually refining their behavior until they can ride smoothly. This process of learning through interaction, feedback, and iterative improvement lies at the heart of reinforcement learning (RL).

Reinforcement learning represents one of the three fundamental paradigms of machine learning, alongside supervised learning and unsupervised learning. Unlike supervised learning, where an agent learns from explicit examples of correct behavior labeled by an external supervisor, RL agents must discover which actions yield the highest cumulative reward through direct interaction with their environment. Unlike unsupervised learning, which focuses on uncovering hidden structures in data, RL is fundamentally concerned with learning to make decisions that maximize a scalar reward signal over time.

The defining characteristic of reinforcement learning is its treatment of sequential decision-making under uncertainty. When an RL agent takes an action, the consequences may not be immediate—the agent may need to take dozens or even thousands of steps before discovering whether a particular decision was wise or foolish. This temporal structure distinguishes RL from simpler prediction problems and introduces fundamental challenges in credit assignment: how does an agent determine which of its past actions were responsible for its current success or failure?

The origins of reinforcement learning can be traced to multiple intellectual traditions. In engineering, the field emerged from optimal control theory, particularly the work of Richard Bellman on dynamic programming in the 1950s. In psychology, RL draws heavily from theories of animal learning, most notably B.F. Skinner's operant conditioning and the concept of reinforcement as a mechanism for behavioral modification. This dual heritage is reflected in the terminology of the field, which borrows concepts from both engineering (state, policy, value function) and psychology (reward, punishment, exploration).

1.2 The Agent-Environment Paradigm

1.2.1 Conceptual Foundations

At its core, reinforcement learning formalizes the problem of an agent interacting with an environment over discrete time steps. This interaction follows a structured pattern that forms the backbone of all RL algorithms:

```mermaid graph LR A[Environment<br/>State $s_t$] -->|Observation $o_t$| B[Agent] B -->|Action $a_t$| A A -->|Reward $r_{t+1}$| B ```

At each time step $t$, the agent receives information about the current state of the environment, denoted $s_t \in \mathcal{S}$, where $\mathcal{S}$ is the set of all possible states. Based on this state and its learned knowledge, the agent selects an action $a_t \in \mathcal{A}(s_t)$, where $\mathcal{A}(s_t)$ represents the set of actions available in state $s_t$. After executing this action, the environment transitions to a new state $s_{t+1}$ and emits a reward signal $r_{t+1} \in \mathcal{R} \subset \mathbb{R}$. This cycle continues until the agent reaches a terminal state or the interaction proceeds indefinitely.

The environment's dynamics are captured by the state transition function, which in the general case can be expressed as a conditional probability distribution:

$$P(s_{t+1} = s' | s_t = s, a_t = a) : \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1]$$

This function, often called the model of the environment, specifies the probability of transitioning to each possible next state given the current state and action. If this transition function is deterministic, we can write $s_{t+1} = f(s_t, a_t)$.

Similarly, the reward function defines the immediate feedback the agent receives:

$$r_t = R(s_t, a_t, s_{t+1}) : \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$$

In some formulations, the reward depends only on the current state: $r_t = R(s_t)$. The reward signal is the primary source of information that guides the agent's learning, as it provides scalar feedback about the quality of the agent's decisions.

1.2.2 The Markov Property and State Representations

A crucial assumption underlying most RL formulations is the Markov property, named after the mathematician Andrey Markov. A state is said to satisfy the Markov property if it captures all relevant information about the past in such a way that the future depends only on the current state, not on the complete history of interactions. Formally:

$$P(s_{t+1} | s_t, a_t) = P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, \ldots, s_0, a_0)$$

If this property holds, the state is said to be Markov, or to have the Markov property. In a Markov state, knowledge of the current state is sufficient to determine the future without requiring explicit memory of the past.

The Markov property has profound implications for learning and decision-making. If the environment is truly Markov, an optimal policy—one that maximizes expected cumulative reward—need only consider the current state, not the entire history. This dramatically simplifies the problem and enables the application of dynamic programming techniques.

In practice, whether a state representation is Markov depends on the level of abstraction. Consider a game of chess: the positions of all pieces on the board constitute a Markov state because the rules of chess specify exactly how the game will proceed from any legal position. However, if we only knew the position of the white king, this would not be a sufficient state representation—the game would not be Markov with respect to that partial information.

Many real-world problems are not perfectly Markov, but we can often construct state representations that approximate the Markov property. For instance, in partially observable environments, where the agent cannot directly observe the true state of the environment, we might construct a state representation that includes relevant history or uses learned representations that capture temporal dependencies. Techniques such as recurrent neural networks, memoryaugmented architectures, and belief states provide ways of handling non-Markovian environments.

1.2.3 Episodes and Continuing Tasks

RL problems are often categorized by their temporal structure. In episodic tasks, the interaction between agent and environment naturally divides into episodes, each beginning in an initial state and ending in a terminal state. Many game-playing scenarios fall into this category: a single game of chess, a round of Atari, or a traversal of a maze all represent distinct episodes.

When an episode terminates, the agent's state resets to some initial configuration (possibly with variation across episodes), and the learning process continues with a new episode. The set of terminal states is denoted $\mathcal{S}^+ = \mathcal{S} \cup \{terminal\}$.

In continuing tasks, the interaction does not naturally terminate. A robotic control task that runs indefinitely, a stock trading algorithm that operates continuously, or an autonomous vehicle navigating traffic all represent continuing tasks. These require slightly different mathematical treatment, as there is no natural notion of episode boundaries.

1.3 Rewards, Returns, and the Objective of RL

1.3.1 The Reward Hypothesis

The reward hypothesis is a foundational assumption of reinforcement learning: that all goals can be described by the maximization of expected cumulative reward. This hypothesis does not claim that the reward signal must