What Is Reinforcement Learning
Reinforcement Learning or RL is a paradigm where an agent learns to make sequential decisions by interacting with an environment. It receives rewards as feedback and optimizes its policy to maximize the total cumulative reward over time. Unlike supervised learning which requires labeled input-output pairs, RL discovers optimal behavior through trial and error. The agent tries things, sees what happens, and learns from the outcomes without being told the correct answer for each situation.
The Markov Decision Process
The Markov Decision Process or MDP is the mathematical framework that formalizes the RL problem. It is defined as a five-tuple consisting of the state space which includes all possible configurations of the environment, the action space which includes all actions available to the agent, the transition function which gives the probability of reaching a new state from the current state after taking a particular action, the reward function which gives immediate scalar feedback for a transition, and the discount factor which determines how much future rewards are valued relative to immediate ones. The Markov property states that the future depends only on the current state and not on the history of how the agent got there. This makes the problem tractable because the agent does not need to remember everything that happened before.
The Agent-Environment Interaction Loop
At each time step, the agent observes the current state of the environment, selects an action according to its policy, the environment transitions to a new state based on the transition function, and the agent receives a reward. This cycle repeats until the agent reaches a terminal state or a predefined horizon is reached.
Core Concepts and Definitions
The policy is a mapping from states to action probabilities. A deterministic policy always picks the same action for a given state while a stochastic policy samples actions according to a probability distribution. The return is the total cumulative discounted reward from a given time step onward. The value function gives the expected return from a particular state under a given policy. It tells the agent how good it is to be in a certain state. The action-value function gives the expected return from a state after taking a specific action and then following the policy. It tells the agent how good it is to take a certain action in a certain state. The advantage function measures how much better a particular action is compared to the average action in that state. The Bellman equations express the value of a state in terms of the value of successor states, creating a recursive relationship that is fundamental to many RL algorithms. The optimal policy is the one that achieves the highest possible value in every state, and the Bellman optimality equations describe the conditions this optimal policy must satisfy.
Taxonomy of RL Methods
Reinforcement learning algorithms can be classified along several axes. The model-free versus model-based distinction separates algorithms that learn directly from experience without knowing the environment dynamics from those that learn or use a model of how the environment works. Model-free methods are most practical for LLMs because language dynamics are intractable to model. The value-based versus policy-based distinction separates algorithms that learn a value function and derive the policy from it from those that directly parameterize and optimize the policy. Value-based methods work well for small discrete action spaces but struggle with large continuous ones, while policy-based methods are natural for high-dimensional action spaces like the vocabulary of an LLM which contains tens of thousands of tokens. Actor-critic methods combine both approaches where the actor proposes actions and the critic evaluates them. The on-policy versus off-policy distinction separates algorithms that learn only from data generated by the current policy from those that can learn from data generated by any policy including old versions of itself or other agents. On-policy methods are more stable but less sample-efficient while off-policy methods are more sample-efficient but harder to stabilize.
Temporal Difference Learning
Temporal Difference or TD learning is a core idea in RL where the agent updates its value estimates using other value estimates without waiting for the full episode to end. This is called bootstrapping. The TD error measures the discrepancy between what the agent thought would happen and what actually happened plus what it expects next. It represents the agent’s surprise. A helpful intuition is the driving analogy where you expect a drive to take thirty minutes, but after ten minutes you hit unexpected construction and your GPS updates to say you now have thirty-five minutes left. The total expected time becomes forty-five minutes and the difference between the new estimate and the old estimate is a positive fifteen minute TD error. You use this surprise to change your route next time. A positive TD error means the outcome was better than expected so you boost this state’s value. A negative TD error means it was worse than expected so you lower this state’s value.
The TD error formula uses the immediate reward plus the discounted estimated value of the next state minus the old estimate of the current state. This combined term is called the TD target. The agent adjusts its value function to drive the TD error toward zero using a learning rate. When the TD error is positive the agent increases the state’s value, when it is negative the agent decreases it, and when it is zero no update is needed and convergence is achieved. TD learning differs from Monte Carlo methods which wait until the episode ends and use the actual return. Monte Carlo is unbiased but has high variance while TD is biased but has much lower variance. TD lambda interpolates between pure TD and pure Monte Carlo where lambda equals zero gives pure TD and lambda equals one gives pure Monte Carlo. This is exactly what GAE does for PPO with lambda typically set to 0.95.
Q-Learning
Q-Learning is the foundational off-policy value-based algorithm. It learns the optimal action-value function directly regardless of the policy being followed. The update rule takes the current Q-value and moves it toward the immediate reward plus the discounted maximum Q-value of the next state. Q-Learning is off-policy because the update uses the maximum Q-value for the next state which is the value of the best action regardless of which action the agent actually took. This means the target is always computed under the optimal policy even if the behavior policy explores randomly. This is why Q-Learning can learn from replay buffers, demonstrations, or any source of experience. The on-policy alternative is SARSA which uses the action actually taken instead of the maximum.
Deep Q-Networks or DQN replace the tabular Q-function with a neural network. The key innovations are the experience replay buffer which enables off-policy data reuse, the target network which provides stability, and epsilon-greedy exploration. The DQN loss function minimizes the mean squared TD error over mini-batches sampled from the replay buffer. The target network is a frozen copy of the Q-network that is updated only periodically to prevent the moving target problem where both the prediction and the target shift simultaneously causing divergence.
Replay buffers store past experiences as tuples of state, action, reward, next state, and a done flag. They are essential because they break data correlation since consecutive steps are highly correlated and neural networks generalize poorly on sequential data. They prevent catastrophic forgetting because without a buffer an agent that passes a difficult level might forget how to clear it while spending many steps failing on a later level. They improve sample efficiency because running environments can be slow and a replay buffer allows multiple weight updates from the same transition extracting more value from every step. Prioritized experience replay scales sampling probability by TD error magnitude so that transitions that caused massive surprise are sampled more frequently. This accelerates learning significantly.
Q-Learning fails for LLMs because the action space in language generation is the full vocabulary which contains tens of thousands of tokens, and the state space is all possible token sequences which is effectively infinite. Computing the maximum Q-value over all actions at every token position is intractable. This is why LLM RL uses policy-based methods like PPO and GRPO instead.
Policy Gradient Methods and REINFORCE
Instead of learning a value function and deriving a policy, policy gradient methods directly optimize the policy parameters to maximize expected return. The policy gradient theorem provides the foundation showing that the gradient of the expected return with respect to the policy parameters can be expressed as an expectation over trajectories of the gradient of the log probability of each action multiplied by the total return. The beauty of this theorem is that the gradient does not require differentiating through the environment dynamics. The log-derivative trick converts it into an expectation that can be estimated by simply running the policy and observing rewards.
REINFORCE is the basic policy gradient algorithm. It samples a complete trajectory, computes the return for each time step, and updates the policy parameters in the direction that increases the probability of actions that led to high returns. The intuition is that it is like reward-weighted maximum likelihood where high-reward trajectories increase the probability of all actions taken while low-reward trajectories decrease their probability. It is supervised learning where the labels are the actions you took weighted by how good they turned out to be.
The variance of REINFORCE can be reduced by subtracting a baseline from the return that does not depend on the action. The best choice for this baseline is the value function which makes the update depend on the advantage rather than the raw return. REINFORCE has several limitations including high variance because each gradient uses only one trajectory, no bootstrapping because it must wait for a full episode, poor sample efficiency because data is used once then discarded, and no step-size control which can lead to catastrophically large policy updates. These limitations motivate the progression from REINFORCE to Actor-Critic to TRPO to PPO.
Actor-Critic Methods
Actor-critic methods combine policy gradient with a learned value function to reduce variance while maintaining the flexibility of policy optimization. The actor is the policy that proposes actions. The critic is the value function that evaluates how good a state or action is and provides a low-variance baseline. The actor update uses the advantage estimate from the critic while the critic update minimizes the TD error. The evolution to PPO for LLMs goes from REINFORCE with high variance and no bootstrapping to A2C and A3C which use TD-based advantage and have lower variance but unbounded step sizes, to TRPO which constrains the KL divergence between policy updates and is stable but expensive, to PPO which clips the policy ratio to achieve similar stability with first-order optimization only, and finally to GRPO which removes the critic entirely and uses group statistics as a baseline.
Generalized Advantage Estimation
Generalized Advantage Estimation or GAE provides a good estimate of the advantage which measures how much better a particular action was than average. There is a fundamental tension between one-step TD advantage which has low variance but high bias and Monte Carlo advantage which has zero bias but high variance. GAE provides a smooth interpolation between these extremes via a single parameter lambda that controls the trade-off. It computes the one-step TD error at each timestep and blends them with exponentially decaying weights. Recent TD errors get full weight while distant ones are down-weighted.
When lambda is zero the advantage estimate completely trusts the value function which gives low variance but high bias if the value function is inaccurate. When lambda is one full Monte Carlo return minus baseline is used which is unbiased but has very high variance. The standard value of 0.95 is the sweet spot that mostly trusts the value function but corrects with actual returns for distant effects. For LLMs specifically the discount factor gamma is set to 1.0 because all tokens matter equally in a single turn while lambda is 0.95. In supervised learning bias and variance stem from model assumptions. In RL via GAE they stem from how much you trust a flawed value model versus how much you trust a chaotic environment. Bias arises when the estimator relies on imperfect predictions of the value network while variance arises when the estimator relies on long environmental trajectories where stochastic transitions and noise accumulate. The hyperparameter lambda serves as a slide-rule between these two fundamental estimation paradigms.
On-Policy versus Off-Policy Detailed Comparison
On-policy methods use data only from the current policy and after each update the old data becomes invalid so new data must be regenerated. This makes them sample inefficient but more stable because the distribution stays consistent. Off-policy methods can use data from any policy stored in a replay buffer and old data remains usable after updates. This makes them sample efficient but they can diverge due to distribution mismatch. For RLHF methods, PPO and GRPO are on-policy so they generate responses with the current policy, compute advantages, update, discard the data, and generate again. This is why generation accounts for about sixty percent of the compute because you regenerate every step. DPO is off-policy and trains on a fixed preference dataset with no generation during training, making it much cheaper but it suffers from distribution shift as the data becomes stale when the policy changes. Online DPO is a hybrid that generates fresh data while using DPO’s supervised loss. PPO uses the clip ratio to squeeze multiple gradient steps from one batch of on-policy data, making it slightly off-policy in a controlled way.
Model-Based versus Model-Free
Model-free methods learn the policy or value function directly from experience without knowing the environment dynamics. They do no planning and make reactive decisions. They have low sample efficiency because they must experience everything, but they have no model bias. They are best for complex or unknown dynamics. Model-based methods learn or use a model of environment transitions and can plan ahead by simulating future trajectories. They have high sample efficiency but any model errors compound during planning. They are best for simple dynamics where efficiency is needed. Language generation dynamics are trivial because they simply append a token to a sequence with deterministic transitions. The hard part is the reward, specifically predicting what humans will prefer. This makes model-based methods unnecessary for LLM RL. The reward model in RLHF predicts human preference but it is used as a reward signal rather than for planning or simulation. LLM RL is fundamentally model-free policy optimization.
Reward Shaping
Reward shaping is a technique where the developer modifies or supplements the original reward function. Its primary objective is to transform a sparse reward scenario where the agent receives feedback only upon final task completion into a dense reward scenario with intermediate feedback signals to accelerate convergence. The reshaped reward adds an auxiliary shaping function to the original reward. However there is a risk of reward hacking where if the shaping function is arbitrarily designed the agent will find structural loopholes to maximize the auxiliary signals while ignoring the global objective. For example a navigation agent rewarded for reaching intermediate landmarks might learn to loop indefinitely around a single checkpoint to accumulate infinite rewards without ever reaching the destination. For LLMs a model rewarded for sounding confident might learn to always start with absolutely regardless of accuracy.
To mathematically guarantee that reshaping does not alter the optimal policy, potential-based reward shaping or PBRS is used. The shaping function is constrained to be the difference in a scalar potential function across states. The complete PBRS reward is the original reward plus the discounted potential of the next state minus the potential of the current state. The policy invariance theorem guarantees that the optimal policy under the reshaped reward is identical to the optimal policy under the original reward. Loop immunity means any cyclic trajectory starting and ending at the same state results in a net potential change of exactly zero so the agent cannot exploit loops to hack the reward. While the optimal policy is unchanged, the shaped reward provides denser gradient signals enabling the agent to converge significantly faster in sparse reward environments.