Evolution of RL Algorithms from Value Iteration to PPO

In Reinforcement Learning, the goal is for an agent to learn how to make decisions in each state so that it can maximize long-term reward.

In MDP, we have a full model of the environment, meaning we know the complete rules of the game and everything is deterministic in terms of structure. The only task is to compute the best decision, which is essentially planning.

MDP consists of:

• state
• action
• reward
• transition

If we know what happens after each action and what reward we get, we can find the optimal policy.

However, in RL we don’t have the model. We don’t know exactly what will happen after taking an action or what the reward will be.

So we have two main approaches in RL:

1. Model-based: First learn a model of the environment, then solve it like an MDP.
2. Model-free: Do not learn the model; instead directly learn which actions are good or bad from experience.

Model-Based Methods:

Value Iteration

Value Iteration: This algorithm says we first guess the value of each state and then repeatedly update these estimates. (What happens if I do this? How good will it be? Continue until it converges.)

If we know the environment, meaning we know what each action leads to and what reward we get, we can determine the best behavior. In other words, we decide which action to take in each state to maximize long-term reward.

First, we learn how good each state is, and then we choose the best action. Initially, we assign a guessed action for each state, and during decision making we evaluate each state by asking what happens if we try each action. This update process is repeated continuously.

Policy Iteration

Policy Iteration: In this method, instead of directly updating value estimates, we start with an initial policy and then improve it step by step.

The overall process is:

• First, we start with a random or initial policy
• Then we compute the value of that policy (Policy Evaluation)
• Next, we check whether a better action exists in each state (Policy Improvement)
• If a better action exists, we update the policy
• This cycle continues until the policy converges to the optimal one

In other words, instead of focusing directly on value, we focus on improving the policy itself.

Model-Free Reinforcement Learning Methods:

Q-Learning:

This method doesn't use a model. It learns purely from experience:

it takes actions, observes rewards, and updates Q-values. In general, the agent takes an action in the current state, receives a reward, moves to the next state, and then updates its previous Q-values based on the best future estimate.

Instead of separating action and value, we compute how good each action is in a given state. So we evaluate all actions within a state using Q-values and then choose the best action.

The difference between Q-Learning and Value Iteration is:

Value Iteration: It knows the full model and computes where an action will lead probabilistically.

**Q-Learning: **It does not use the model; it learns from experience by interacting with the environment and updating Q-values.

Policy Gradient:

In RL, agents used to learn a value for each state-action pair and then choose the action with the highest value (value function approaches).

The problem with this method is that it always selects a single best action, while in real-world settings, the best behavior is often stochastic.

So instead of learning values and deriving a policy from them, we directly learn the policy itself. This is called policy gradient (learning the probability of each action).

In policy-based methods, we don’t use a table like Q-learning; instead, we use a neural network.

The parameters of the policy are represented by a model (usually a neural network), where the network weights define the policy. We then adjust these weights to maximize reward.

REINFORCE (Basic Policy Gradient):

The first major policy gradient algorithm is REINFORCE:

A state is passed into the neural network, the network outputs action probabilities, and the agent samples an action. This continues until the episode ends.

At the end, we compute the total reward and update the policy.

The issue is that learning happens only at the end of the episode. This means we don’t know which specific action was responsible for success.

Actor-Critic:

Actor-Critic is a method in Reinforcement Learning that tries to combine the advantages of value-based and policy-based approaches to achieve more stable learning.

In this method, we have two main components:

Critic

The Critic estimates how good a state or an action is.

• Its job is to evaluate how good each state is
• In other words, it learns the value function
• It helps the agent understand how valuable the current situation is

Actor

The Actor is the decision-making part.

• It learns the policy
• It selects actions based on the feedback from the Critic
• In other words, it decides which action to take in each state

Main Idea of Actor-Critic

In earlier methods like REINFORCE, there was a key problem:

We only get feedback at the end of an episode

So we do not know exactly which action was good or bad

Actor-Critic solves this problem by:

Providing step-by-step feedback through the Critic

Telling the Actor whether an action was better or worse than expected

Learning Process

At each step:

• A state is passed into the NN
• The Actor selects an action
• The environment returns a reward and the next state
• The Critic evaluates whether the action was better or worse than expected
• If it was better, the Actor increases the probability of that action
• If it was worse, the Actor decreases the probability of that action

A3C (Parallel Actor-Critic)

A state is passed into the NN, and it computes action probabilities. The agent samples an action and interacts with the environment, receiving reward and next state.

The critic evaluates whether the action was better or worse than expected.

If the action is better than expected, the actor increases its probability.

Multiple agents run in parallel, collecting diverse experiences and sending them to the main network, which improves stability and speed.

However, the problem is that when the critic updates the policy, the policy might change too much at once, which can destabilize learning or collapse exploration.

TRPO (Trust Region Policy Optimization)

TRPO is a policy optimization method designed to make policy updates stable and prevent sudden large changes in the policy, which can easily destabilize learning in Reinforcement Learning.

Main Idea of TRPO:

In previous algorithms, sudden changes in the agent caused unstable learning and the loss of exploration, and this algorithm was designed to solve this problem.

How TRPO Works?

Before updating the policy, TRPO checks how different the new policy is from the old policy.

• If the difference is small then update is allowed
• If the difference is too large then update is restricted

Instead of allowing full updates, TRPO forces the new policy to stay inside a safe region, called the Trust Region.

Learning Behavior

At each update step:

• The agent collects experience from the environment
• The critic estimates whether actions were better or worse than expected
• The policy is updated
• But before applying the update, TRPO checks the distance between old and new policy
• If the change is too large, it prevents a full update and restricts it

PPO (Proximal Policy Optimization):

PPO is one of the most important and widely used reinforcement learning algorithms. It is essentially a simpler and more practical version of TRPO. The main goal of PPO is to improve the policy without causing large and unstable updates.

Main Idea of PPO

In policy gradient methods, if updates are too large:

• the policy changes suddenly
• the agent’s behavior becomes unpredictable
• learning becomes unstable

TRPO solves this problem by restricting policy updates, but it is complex. PPO keeps the same goal but uses a simpler and more practical approach.

PPO Workflow

In PPO:

• A state is passed into the neural network
• The Actor computes the probability of each action
• The agent samples one action
• The environment returns a reward and the next state

At the same time:

• The Critic estimates V(s)
• Meaning it predicts how much future reward we can expect from this state

Role of Advantage

Instead of using raw reward, PPO uses Advantage.

whether an action is better or worse than expected

If:

• (Advantage > 0) then the action is better than expected (increase its probability)
• (Advantage < 0) then the action is worse than expected (decrease its probability)

Main Problem in PPO:

If the policy is updated too freely:

• a single large update can completely change the policy
• and learning becomes unstable

PPO Solution

To solve this issue, PPO uses a simple idea:

Instead of directly applying large gradients, it uses the probability ratio between the new policy and the old policy.

Then this ratio is clipped.

This means:

• if the new policy deviates too much from the old policy
• its effect on the update is limited
• and overly large gradient updates are prevented

Result

With this approach:

• the policy changes gradually
• learning remains stable
• and performance still improves

Conclusion

If we look at the path from Value Iteration to PPO, we can clearly see a progression: from fully known and analytically solvable models to methods that learn purely from experience and handle the uncertainty of the real world. In Value Iteration, we know everything about the environment, and we only need to compute the optimal decision. However, in real-world problems, such complete knowledge is usually not available, and the agent must learn through interaction with the environment. This is where Q-Learning and other Model-Free methods begin; where learning happens purely from experience and received rewards. As problems become more complex, learning only a value function is no longer sufficient. This led to the introduction of Policy Gradient methods, where instead of directly estimating values, the policy itself is learned. However, early methods like REINFORCE showed that learning based only on final outcomes is highly noisy and unstable. After that, the Actor-Critic idea was introduced to stabilize learning, where one component makes decisions and the other evaluates them. Later, algorithms like A3C attempted to make learning parallel and more diverse, but the main problem still remained: sudden changes in the policy.

TRPO and later PPO were introduced exactly to solve this issue: ensuring that learning remains gradual, controlled, and stable. PPO, in particular, is a more practical version of this idea, which made reinforcement learning usable in large-scale real-world applications.

In the end, if we take a broader view, the evolution of reinforcement learning is less about changing algorithms and more about finding a balance: between learning and exploiting experience, between fast and stable updates, and between simplicity and expressive power.

Refrences:

https://arxiv.org/pdf/2401.13662

https://arxiv.org/abs/cs/9605103

pictures created by AI.