3.2 Reinforcement Learning

3.2 Foundation of Reinforcement Learning (RL)

3.2.1 Problem, Process, and Uniqueness

The Problem Addressed by Reinforcement Learning

The Reinforcement Learning Process

1. Observation: Observe the current state of the environment.

2. Decide and act: The agent selects an action based on its current policy or strategy and then acts.

3. Receive feedback: After the action, the environment provides a reward signal and transitions to a new state.

1. In each iteration, the agent observes the current state of the environment and computes an action.

2. The action is applied to the environment, which then generates an immediate reward signal and transitions to a new state.

3. The agent perceives the new state in the next iteration, repeating the process until a terminal state is reached.

The Uniqueness of Reinforcement Learning

• Both supervised and reinforcement learning optimize the expectation of some score (loss or reward) over a distribution of data.

• In supervised learning, we fix the data distribution and optimize the model’s parameters.

• In reinforcement learning, the data distribution is adjusted by optimizing the policy (which could be parameterized by a model as well) because a new policy changes what data (state-action pairs) will be encountered.

3.2.2 Markov Process

Markov Process

1. Stochastic Processes: A stochastic process studies how random phenomena evolve over time. Let denote the state of a system at time . The probability of transitioning to the next state given the entire history can be written as:

2. Markov Property: A random process has the Markov property if the next state depends only on the current state. Formally:
In other words, knowing the current state is sufficient to predict the next state

3. Markov Process (Markov Chain): A Markov process is a stochastic process that satisfies the Markov property. It is often defined as a tuple , where:
1. is a finite set of possible states.
2. is the state transition matrix:
where the entry represents the probability of moving from state to state :
Each row of sums to 1 because, from any given state, the probabilities of moving to all possible next states must add up to 1.



Sampling from a Markov chain means starting from some initial state and using the transition probabilities to generate a sequence (episode) of states over time, such as .

Markov Reward Process

1. Markov Reward Process: A Markov Reward Process is a Markov process augmented with a reward function and a discount factor . Formally, it is defined by the tuple , where:
1. is a finite set of states.
2. is the state-transition matrix, with .
3. gives the expected reward for transitioning into state .
4. (ranging from 0 to 1) is the discount factor, reflecting the idea that future rewards may be uncertain or less valuable than immediate ones.

2. Return: When starting from a specific state at time , the return is the sum of all (discounted) rewards until reaching a terminal state:
Here, is the reward received upon transitioning into the state at time , is the discount factor, and the series continues until the process terminates (or indefinitely if it never does).

3. Value Function: The value of a state , denoted , is the expected return when starting in that state:
Because we are in a Markov Reward Process, this expectation can be broken down using the Bellman equation:
where is the immediate reward for entering , and is the probability of moving from to .
For a finite state space , we can write (the values of all states) as a column vector, as another column vector of immediate rewards, and as the transition matrix. Then in matrix form, the Bellman equation becomes:
This closed-form solution has computational complexity for states, so it is feasible only for small-scale problems. For larger MRPs, methods like dynamic programming, Monte Carlo, and temporal-difference learning are used to estimate . These techniques will be introduced in later sections.

Markov Decision Process

1. Markov Decision Process (MDP): Markov Decision Process extends a Markov Reward Process by including an action chosen by an agent. Formally, an MDP is described by the tuple , where:
1. is the set of states.
2. is the set of possible actions.
3. is the state-transition function, which gives the probability of transitioning to state after taking action at state .
4. is the reward function, giving the expected reward when action is taken at state . If depends only on , it reduces to the MRP case.
5. is the discount factor ().
Unlike the spontaneous transitions in a Markov Reward Process, an MDP features agent actions that influence how the state evolves. The following figure illustrates how the agent observes the current state , chooses an action , and then the environment transitions to a new state while providing a reward .

2. Policy: A policy determines how the agent chooses actions. Formally, is the probability of selecting action in state . A policy can be:
1. Deterministic: always choose a specific action in each state.
2. Stochastic: provide a probability distribution over actions for each state.
Because of the Markov property, depends only on the current state, not on prior history.

3. State-Value Function: In an MDP, the value of a state under a policy , denoted , is the expected return (sum of discounted future rewards) when starting from and following . Formally:
Here, is the total discounted reward from time onward.

4. Action-Value Function: Because actions explicitly influence transitions in an MDP, we also define the action-value function . It is the expected return when the agent starts from state , takes action , and then continues following policy :
The relationship between and is:
And:
These equations show how a policy affects the expected return and reward in an MDP.

3.2.3 Bellman Expectation Equations

Bellman Expectation Equations

1. State-Value Function

2. Action-Value Function

• The Bellman Expectation Equations let you evaluate any policy in an MDP by relating current value estimates to expected future returns.

• For large state-action spaces, exact matrix-based solutions become impractical, so algorithms such as dynamic programming, Monte Carlo methods, or temporal-difference learning approximate and .

• Even so, the underlying idea always stems from these Bellman equations—understanding them is fundamental in reinforcement learning.

Converting an MDP + Policy into an MRP

• The reward for being in state under policy becomes

• The transition probability from to under is

Optimal Policies

1. Defining an Optimal Policy
1. We say a policy is better than or equal to another policy (denoted ) if its expected return is at least as high for every state :
2. In a finite MDP (with limited states and actions), there is at least one policy that is not worse than any other policy. Such a is called an optimal policy. There may be multiple optimal policies; we denote them all just as .

2. Optimal Value Functions
All optimal policies share the same optimal state-value function, denoted:
They also share the optimal action-value function:

3. Relationship Between and :
The relationship between the optimal state-value function and optimal action-value function is the same as we saw for general (non-optimal) policies.
We consider the best possible actions at each step, which yield the highest state value:

Bellman Optimality Equation

3.2.4 Monte Carlo Methods

Estimating the Area of a Circle

Estimating a Policy’s State-Value Function

• First-visit MC only updates the state value for the first time each state is encountered in an episode.

• Every-visit MC updates the value estimate for every occurrence of a state in an episode.

Monte Carlo Value Estimation

1. Sampling Trajectories: Use policy to sample multiple trajectories. Each trajectory has the form:

2. Trajectory Processing and State Information Update: For each state at time step in every trajectory:
1. Update the state’s counter:
2. Update the state’s total return:

3. State Value Estimation:
1. The value of each state is estimated as the average return:
2. By the Law of Large Numbers, as ,

4. Incremental Update (Optional): Use this to substitute step 3 if you want to save some memory. For each state and its corresponding return :
1. Update the counter:
2. Update the value incrementally:

• episodes: A list of sampled trajectories (each a list of tuples).

• V: A dictionary (or array) for the estimated value of each state.

• N: A dictionary (or array) counting how many times each state has appeared.

• gamma: The discount factor.

3.2.5 Dynamic Programming

Policy Iteration

1. Policy Evaluation
Given a policy , we compute its state-value function with the Bellman expectation equation:
In practice, we can generalize the Bellman expectation equation as below, where we compute the next iteration's state value function based on the current iteration's state values. Pick an initial guess , then iteratively update:
We stop when changes between successive updates fall below a small threshold .

2. Policy Improvement
Once we have , we can derive a better policy by choosing, at each state , the action that maximizes the action-value (Q-value):
Hence, the improved policy is given by:
If this new policy is identical to , the algorithm has converged; otherwise, replace with and repeat.

• Overall workflow:

• Policy Iteration Code: here, we adopt the Cliff Walking environment for demonstration
• Cliff Walking is a classic reinforcement learning environment where an agent must start from the bottom-left of a 4×12 grid and reach the bottom-right goal while avoiding a cliff.
• The agent can move up, down, left, or right. Hitting a wall keeps the agent in place; otherwise, it moves to the next state. Falling into the cliff or reaching the goal ends the episode and resets the agent to the start.
• Each step gives a reward of -1, while falling into the cliff gives -100.

Value Iteration

• Overall Workflow:

3.2.6 Temporal-Difference Methods

• MC-style sampling: They learn from actual sampled returns, without needing the environment’s transition probabilities.

• Dynamic Programming: They use estimates of future returns (via the Bellman equation concept) to update the current value.

On-Policy vs. Off-Policy Learning

• On-policy: The agent updates its estimates using the same policy it uses to generate data (e.g., SARSA).
• The data efficiency is low, and the old data cannot be used after the policy is updated. New data is acquired through interaction with the environment using the updated policy.

• Off-policy: The agent can learn an optimal policy while following a different behavior policy for exploration (e.g., Q-learning).
• It can reuse data generated by the behavior policy, and is efficient.

SARSA (On-Policy TD)

• With probability , the agent chooses the best action — the one that maximizes the estimated action-value .

• With probability , the agent chooses a random action from the action space , including the best action, encouraging exploration.

• SARSA Code

Multi-Step TD (e.g., n-Step SARSA)

Q-Learning (Off-Policy TD)

• Q-Learning Code

3.2.7 Types of Reinforcement Learning

• Based on Data Source:
• Online: The agent interacts with the environment while collecting trajectory samples and learns the policy simultaneously.
• Offline: The trajectory samples used for learning are collected beforehand and provided to the agent as an offline dataset. The learning process does not involve interaction with the environment.

• Based on Behavior Policy and Target Policy
• On-Policy: The behavior policy (used to collect samples) and the target policy (used to update) are the same policy. For example, in SARSA, the update uses five-tuple data sampled using : ; so the behavior and target policies are both
• Off-Policy: The behavior policy (used to collect samples) and the target policy (used to update) are not the same. For example, in Q-learning, the update uses four-tuples data , and is obtained via , rather than sampled from the behavior policy. So here, the behavior policy is and the target policy is purely greedy.

• Based on if we have access to the Environment Model
• Model-based: The dynamics of the environment are known or learned in the form of a transition model and reward function. Using planning (e.g., dynamic programming or tree search), an optimal policy can be computed without real interaction with the environment.
• Model-free: The environment dynamics are unknown. The agent learns the policy through direct interaction with the environment and does not require learning a transition model.

• Based on How the Policy is Learned
• Value-based: The agent first learns a value function, then derives a policy from it. There is no explicit policy during learning.
• Policy-based: The agent explicitly learns a target policy directly.

3.2.8 Deep Q-Network

Deep Q-Network (DQN)

1. Replay Buffer: In standard supervised learning, each training sample is used multiple times. However, in vanilla Q-learning, each sample updates the Q-value only once. DQN introduces a Replay Buffer (typically a fixed-size FIFO buffer with sampling strategies like random or prioritized sampling) to store transition samples. During training, batches are sampled from this buffer (like the offline method). The advantage include:
1. Independence Assumption: Sequential MDP samples are correlated, violating the i.i.d. assumption critical for neural network training. The Replay Buffer breaks temporal correlations.
2. Improved Sample Efficiency: Each sample can be reused multiple times, suitable for gradient-based learning in deep networks.

2. Target Network: The TD target depends on the same Q-network , leading to instability as the target shifts during training (a "chasing moving target" problem). To mitigate this, DQN employs a separate Target Network , initialized identically to the main Q-network. The target network’s parameters are periodically synchronized with (e.g., every fixed number of steps), stabilizing training. The loss function is formulated as:

• DQN Code
• You may have to downgrade the numpy lib if you run this code on the Colab: pip install numpy==1.26.4

Double DQN

• Action selection: uses the current network for action selection.

• Value calculation: uses the target network .

• Formula

• Double DQN Code: Just replace the DQN class to the new one

• Results

Click here to see more code and results of Double DQN on Pendulum-v1.

Dueling DQN

• A state value function .

• An advantage function , capturing how much better or worse an action is compared to the average at that state. In the same state, the sum of the advantage values of all actions is 0

• Advantages of Dueling DQN
• By explicitly modeling , the network more rapidly learns which states are good or bad overall—without waiting to see how each action plays out.
• This can be helpful when there are many actions or when most actions have similar outcomes in certain states.
Since Dueling DQN is an improvement only for the action-value estimation network, it does not conflict with Double DQN. In fact, it is common and effective to combine Dueling DQN with Double DQN.

• Dueling DQN Code: just replace the DQN class with below code and set lr = 2e-2

• Visualization

Click here to see more code and results of Dueling DQN on Pendulum-v1.

3.2.9 Policy Gradient Algorithm

REINFORCE algorithm

• REINFORCE Code

• Results

3.2.10 Actor-Critic Algorithm

• Motivation
• Value-based methods: Value-based methods, like DQN (or its variants), learn only a value function (like a critic), which estimates the action-value function . Actions are selected using an policy derived from the function.
• Policy-based methods: Policy-based methods, like REINFORCE, learn only a policy function (like an actor), which directly parameterizes the policy . These methods use Monte Carlo (MC) to estimate returns for updating the policy.
• A natural question: Can we learn both at once? The answer is Actor‑Critic, which combines a parameterized policy model (actor) with a learned value function model (critic). The critic provides bootstrapped estimates (i.e., using Temporal Difference learning) to reduce the variance of the policy gradient estimates. Although the critic is learned, these algorithms are still fundamentally policy-based, because the primary objective is to optimize the policy through gradient ascent.

Note that the bootstrapping used in the Temporal-Difference learning is not like the one in machine learning, below is a comparison table to clarify this concept.

Aspect	Bootstrapping in Reinforcement Learning	Bootstrapping in Statistics / Traditional ML
What	Using the model’s own estimates to update targets without sampling a complete episode (e.g., TD learning)	Resampling from data to create multiple sub-datasets for estimation and combine their predictions to enhance performance
Why	Accelerate learning, reduce variance	Estimate generalization error, stabilize learning, quantify uncertainty
Uses multiple data subsets?	No	Yes
Combines multiple models?	No	Yes
Used in Actor-Critic?	Yes (the Critic uses TD bootstrapping)	No (unrelated to Actor-Critic)

• The Basic Idea
Recall the policy gradient formula:
• In a pure policy-based method like REINFORCE, we estimate via Monte Carlo, which can suffer from high variance.
• Actor‑Critic replaces this Monte Carlo estimate with a learned value function (critic). The actor (the policy network) interacts with the environment, while the critic (the value network) evaluates how good the actor’s chosen actions are.

• Generalized Policy Gradient
You can express the policy gradient more generally as:
where could be:
1. Total return of the trajectory: . This uses the total discounted return of the entire trajectory to update the policy at each time step . The drawback is that it assigns the same return value to every state-action pair in the trajectory. Additionally, it requires the full episode to be completed before updates can be made.
2. Returns after action : . This is the Monte Carlo estimate used in the REINFORCE method. While unbiased, MC methods suffer from high variance due to the accumulated uncertainty of state transitions and rewards.
3. Baseline-adjusted variant: . Introducing a baseline reduces variance. A common choice is the value function .



💡
Why does subtracting a baseline reduce variance?
• With the baseline, the policy gradient becomes:
• However, the baseline function is only a function of the state and is independent of the action, so subtracting it doesn’t affect the expected value of the policy gradient. That is, the expected policy gradient remains unchanged:
Now we prove that the second term equals 0:
• Without changing the expected policy gradient, the role of the baseline is to serve as a reference value, used to reduce the background "noise" in the reward that does not depend on the current action selection. By subtracting an appropriate baseline, the scores for different actions become more focused and stable, which reduces variance.
• Intuitively: If no baseline is subtracted, the reward received after taking an action may vary significantly due to the randomness of the environment. Subtracting a suitable baseline makes the relative quality of different actions clearer, reducing randomness and lowering the variance of the policy gradient.
4. Action-value function: . In the general form, Actor-Critic uses the action-value function to estimate . However, in practical implementations, we rarely estimate full Q-function directly due to its high variance or instability.
5. Advantage function: . The advantage function subtracts the state-value function from the action-value function , measuring how much better the current action is compared to the average
Similar to baseline-adjusted method, the advantage function reduces the variance, which makes the training more stable.
6. Temporal difference (TD) residual: . Using the advantage function requires learning both and networks, doubling estimation error. In practice, TD-based approximations of the advantage function are used.
💡
Why Can We Use the Temporal Difference of the Value Function to Approximate the Advantage Function?
Let’s revisit the Markov Decision Process (MDP) we discussed earlier. We know that the action-value function and the state-value function are directly related through the following equation:
The action-value of taking action in state equals the immediate reward plus the discounted expected value of the next state, averaged over all possible transitions. However, in many cases, the state transition is deterministic — that is, the next state after taking action in state is fixed. So we can write:
When the state transition is deterministic, the formula above is an unbiased estimation. Even if transitions are stochastic or uncertain, which leads the formula to biased estimation, this expression still serves as a reasonable approximation of the true Q-value. Therefore, using the expression , we can define an advantage function based on the temporal difference of :

• Loss Function
After obtaining the policy gradient for Actor-Critic, we can update the Actor based on the policy gradient, and update the Critic using the TD-error update method as previously discussed. The MSE loss for the critic is as follows:
So we have , here we consider the as a constant so we don't calculate gradients for it. This is the idea of the semi-gradient method.

• Actor-Critic Code

• Results

3.2.11 PPO Algorithm

TRPO Algorithm

PPO Algorithm

• If the advantage function value is positive, it indicates the action is better than average in that state, so maximizing the equation increases the probability of selecting that action.

• If the advantage function is negative, it means the action is worse than average, so maximizing the equation will decrease the probability of selecting that action.

• Importance Sampling: From the simplified formula above, we can see that PPO is an on-policy algorithm, meaning the policy used for sampling and the policy being updated are the same (both come from ). However, a problem with this is low sample efficiency, so PPO uses importance sampling techniques, which allow it to reuse data generated from the previous policy .
📌
Importance Sampling
1. To estimate the expectation of a function under the target distribution :
2. Suppose there is a proposal distribution , and , as long as , the expectation can be rewritten as:

• Policy Clipping: PPO is essentially an improvement based on the TRPO algorithm. TRPO introduces a KL divergence constraint between the current policy and the previous policy to ensure that the updated policy doesn't deviate too much from the previous one. In other words, the step size of the policy update is adjusted based on the KL divergence. However, TRPO uses complex mathematical methods to estimate the KL divergence.
In contrast, PPO simplifies this by using a fixed policy clipping operation — the "clip" — which restricts the update ratio of the policy within a range of . PPO-Clip essentially sets a “safe range” to ensure that the policy update doesn't deviate too much. Each time the policy is updated, PPO calculates the difference between the new and old policy. If the difference is too large, PPO will “clip” it back into a reasonable range.

• GAE Estimation: PPO uses Generalized Advantage Estimation (GAE). Traditional advantage function estimation is usually based on either the one-step/multi-step TD error (Temporal Difference Error), or Monte Carlo methods for computing returns. GAE is designed to reduce the variance in policy gradient methods while maintaining low bias, thereby improving sample efficiency and convergence speed of the algorithm.
Based on the idea of multi-step temporal difference, we have:
The first step is the advantage estimation used in Actor-Critic, but it only uses one-step estimation. Although it has low variance, its estimation accuracy is not as good as multi-step temporal difference estimation. GAE (Generalized Advantage Estimation) performs an exponentially weighted average over these multi-step advantage estimates:
The parameter is a hyperparameter introduced in GAE (Generalized Advantage Estimation). When , GAE degrades back to one-step TD errors :
When , it becomes the infinite-step TD (Monte Carlo-style advantage):

• Advantages of PPO: Stable, easy to implement, suitable for high-dimensional problems, balances exploration and exploitation, no need for complex constraints or second-order optimization, etc.