Reinforcement Learning Fundamentals

Reinforcement Learning is one of the three paradigms of machine learning — alongside supervised and unsupervised learning — and arguably the one most closely resembling how humans and animals actually learn. Rather than being told what the correct answer is, an RL agent discovers which actions yield the greatest reward by exploring its environment and learning from the consequences of its actions .

At its core, RL formalizes a simple idea: rewarding desired behaviors and punishing undesired ones causes an agent to shift its behavior toward the rewarded actions over time. This feedback loop between an agent and its environment creates a powerful learning framework that has produced breakthrough results in game playing (AlphaGo), robotics, autonomous vehicles, and resource management .

The fundamental challenge in RL is the exploration-exploitation tradeoff: the agent must exploit what it already knows to obtain reward, but it must also explore unknown actions to discover potentially better strategies in the future .

The diagram above illustrates the core RL loop: at each timestep, the agent observes a state, selects an action, and receives a reward and a new state from the environment.

Footnotes

1. Reinforcement Learning Basics - SmythOS - Core RL concepts including agent-environment interaction and algorithm categories. ↩

2. An Introduction to Reinforcement Learning: Fundamental Concepts and Practical Applications - arXiv - Comprehensive survey of RL fundamentals, MDPs, policy iteration, and value iteration. ↩

3. On-Policy vs Off-Policy Reinforcement Learning - CORE Robotics Lab, Georgia Tech - Detailed comparison of on-policy and off-policy methods with SARSA vs Q-learning analysis. ↩

The Agent–Environment Interface

The RL framework is built on the interaction between two entities:

• Agent: The learner or decision-maker. It observes the environment's state and selects actions according to a Policy.
• Environment: Everything external to the agent. It receives actions, transitions to new states, and emits reward signals .

This interface is modeled as a finite Markov Decision Process, which provides the formal foundation for nearly all RL problems.

Key Components of an MDP

An MDP is defined by the tuple $\langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle$:

The Markov Property is the critical assumption: the future is independent of the past given the present. Formally:

$P(S_{t+1} \mid S_t, A_t) = P(S_{t+1} \mid S_0, A_0, \ldots, S_t, A_t)$

This "memorylessness" is what makes RL problems tractable — the agent need not remember the entire history of interactions .

Footnotes

1. Reinforcement Learning Basics - SmythOS - Core RL concepts including agent-environment interaction and algorithm categories. ↩

2. Part 1: Key Concepts in RL - OpenAI Spinning Up - OpenAI's authoritative introduction to RL terminology, notation, and core mathematical framework. ↩

Rewards, Returns, and Value Functions

The Reward Signal defines the goal of the RL problem. However, the agent's true objective is not to maximize immediate reward, but to maximize the expected cumulative return over time.

The return $G_t$ is defined as the discounted sum of future rewards:

$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 Discount Factor $\gamma$ controls the agent's horizon: values near 0 make the agent myopic (short-sighted), while values near 1 make the agent far-sighted.

Two types of Value Function are central to RL:

• State-value function $V_\pi(s)$: Expected return starting from state $s$ and following policy $\pi$:

$V_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$

• Action-value function $Q_\pi(s, a)$: Expected return starting from state $s$, taking action $a$, and then following policy $\pi$:

$Q_\pi(s, a) = \mathbb{E}_\pi[G_t \mid S_t = s, A_t = a]$

The relationship between them is:

$V_\pi(s) = \sum_{a} \pi(a \mid s) \, Q_\pi(s, a)$

The Bellman Equations

The Bellman Equation is arguably the most fundamental equation in RL. It decomposes the value function into two parts: the immediate reward and the discounted value of the successor state 2.

Bellman Expectation Equation (for $V_\pi$):

$V_\pi(s) = \sum_{a} \pi(a \mid s) \sum_{s'} P(s' \mid s, a) \left[ R(s, a, s') + \gamma V_\pi(s') \right]$

Bellman Expectation Equation (for $Q_\pi$):

$Q_\pi(s, a) = \sum_{s'} P(s' \mid s, a) \left[ R(s, a, s') + \gamma \sum_{a'} \pi(a' \mid s') Q_\pi(s', a') \right]$

The Bellman Optimality Equations express the value under the optimal policy $\pi^*$:

$V_*(s) = \max_{a} \sum_{s'} P(s' \mid s, a) \left[ R(s, a, s') + \gamma V_*(s') \right]$

$Q_*(s, a) = \sum_{s'} P(s' \mid s, a) \left[ R(s, a, s') + \gamma \max_{a'} Q_*(s', a') \right]$

The key insight: under the optimal policy, the value of a state equals the expected return from taking the best action — no averaging over a policy is needed .

This backup diagram represents the Bellman equation: the value at state $s$ is computed by looking ahead to all possible next states, weighted by their transition probabilities.

Footnotes

1. Part 1: Key Concepts in RL - OpenAI Spinning Up - OpenAI's authoritative introduction to RL terminology, notation, and core mathematical framework. ↩

2. Markov Decision Processes and Bellman Equations - Towards Data Science - Thorough derivation and explanation of the Bellman equations from first principles. ↩ ↩²

Temporal Difference Learning

Temporal Difference Learning is the central idea behind the most widely used RL algorithms. TD learning combines the sampling of Monte Carlo methods with the bootstrapping of dynamic programming — it updates estimates using other learned estimates without waiting for the final outcome .

The simplest TD update rule (TD(0)) for state values is:

$V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$

The quantity $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ is called the TD Error, and it drives all TD-based learning.

Footnotes

1. Part 1: Key Concepts in RL - OpenAI Spinning Up - OpenAI's authoritative introduction to RL terminology, notation, and core mathematical framework. ↩

Policy Gradient Methods

While value-based methods like Q-learning learn an action-value function and derive a policy from it, Policy Gradient methods directly parameterize and optimize the policy $\pi_\theta(a \mid s)$ .

The objective is to maximize the expected cumulative reward:

$J(\theta) = \mathbb{E}_{\pi_\theta} \left[ \sum_{t=0}^{T} \gamma^t R_{t+1} \right]$

Using the Policy Gradient Theorem (Sutton et al., 1999), the gradient can be expressed as:

$\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta} \left[ \nabla_\theta \log \pi_\theta(a \mid s) \, Q^{\pi_\theta}(s, a) \right]$

This means we can update the policy parameters by increasing the probability of actions that led to high returns:

$\theta_{t+1} = \theta_t + \alpha \, \nabla_\theta \log \pi_\theta(a_t \mid s_t) \, G_t$

The REINFORCE algorithm (Williams, 1992) is the simplest policy gradient method — it uses Monte Carlo returns $G_t$ after each complete episode . While conceptually elegant, it suffers from high variance. Actor-Critic methods address this by using a learned value function (the critic) to reduce variance in the gradient estimate .

Footnotes

1. Policy Gradient Algorithms - Lil'Log (Lilian Weng) - Extensive catalog of policy gradient methods including REINFORCE, Actor-Critic, DDPG, PPO, and SAC. ↩ ↩²

2. What is Deep Reinforcement Learning? - IBM - Overview of deep RL algorithms, actor-critic architecture, and the exploration-exploitation balance. ↩

Deep Reinforcement Learning

Deep Reinforcement Learning emerged when researchers realized that tabular methods cannot scale to problems with large or continuous state spaces (e.g., raw pixel inputs, robotics) .

The Deep Q-Network (DQN) introduced several key innovations to stabilize training:

1. Experience Replay: Store transitions in a replay buffer and sample random mini-batches to break temporal correlations
2. Target Network: Use a separate, slowly-updated network for computing target Q-values to reduce moving-target instability
3. Gradient Clipping: Clip the TD error to prevent gradient explosion

The DQN update becomes:

$\mathcal{L}(\theta) = \mathbb{E}_{(s,a,r,s') \sim \mathcal{D}} \left[ \left( r + \gamma \max_{a'} Q_{\theta^-}(s', a') - Q_\theta(s, a) \right)^2 \right]$

where $\theta^-$ are the frozen target network parameters and $\mathcal{D}$ is the replay buffer.

Footnotes

1. Sutton & Barto Summary: Finite MDPs - Summary of Chapter 3 from the definitive RL textbook covering policies, value functions, and the Bellman equations. ↩