Reinforcement learning
Reinforcement learning is a branch of machine learning concerned with sequential decision-making under uncertainty. A decision-making entity, conventionally called an agent, interacts with an environment over time. The environment presents information about its current condition, the agent selects an action, and the environment subsequently produces a new condition together with a scalar reward. The agent’s objective is represented by the expected cumulative reward generated across the interaction.
Unlike supervised learning, reinforcement learning does not ordinarily associate each observation with a predetermined correct response. The information available for learning instead depends on the consequences of the agent’s own actions. This dependence creates an exploration problem because an action can reveal information about the environment while also affecting the reward currently received. Reinforcement learning therefore combines elements of statistical estimation, optimal control, and adaptive experimentation.
The standard mathematical description uses a Markov decision process. Within that framework, reinforcement-learning methods estimate a policy or a value function from sampled interaction. Some methods also construct an explicit model of the environment’s transition dynamics. The field includes algorithms based on dynamic programming, temporal-difference learning, direct policy optimization, and combinations of these approaches.
Formal framework
A discrete-time interaction is indexed by (t=0,1,2,\ldots). At time (t), the agent observes a state (S_t) and chooses an action (A_t) according to a policy (\pi). The environment then generates a reward (R_{t+1}) and a successor state (S_{t+1}). Under the Markov property, the distribution of the next outcome depends on the current state and action rather than on the complete preceding trajectory:
[ \Pr(S_{t+1}=s',R_{t+1}=r\mid S_t=s,A_t=a). ]
A policy specifies the agent’s decision rule. For a stochastic policy, (\pi(a\mid s)) denotes the probability of choosing action (a) in state (s). A deterministic policy assigns one action directly to each state.
The discounted return from time (t) is commonly defined as
[ G_t=\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}, ]
where the discount factor (\gamma) lies between zero and one. Discounting gives progressively less weight to rewards received farther in the future and ensures convergence when rewards remain bounded. Episodic formulations can instead use a finite trajectory ending in a terminal state.
The state-value function of a policy is
[ V^\pi(s)=\mathbb{E}_\pi[G_t\mid S_t=s], ]
while the action-value function is
[ Q^\pi(s,a)=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]. ]
These functions summarize expected future return without retaining the entire interaction history. An optimal value function represents the greatest return obtainable from each state, and an optimal policy selects actions attaining that value.
The recursive structure of the return produces the Bellman equation. For a fixed policy, the state-value equation is
[ V^\pi(s)= \sum_a \pi(a\mid s) \sum_{s',r}p(s',r\mid s,a) \left[r+\gamma V^\pi(s')\right]. ]
The corresponding optimality equation replaces the policy-weighted average with maximization over available actions. Reinforcement-learning algorithms differ substantially in how they approximate or solve these relationships.
Historical development
The mathematical foundations of reinforcement learning emerged from several research traditions. Richard Bellman formulated dynamic programming during the 1950s as a recursive treatment of multistage decision problems. Research on trial-and-error adaptation developed separately through mathematical psychology and early computational learning systems. These traditions became closely connected when temporal credit assignment was expressed in terms of recursively related value estimates.
During the early 1990s, You Watanabe studied delayed-reward control in stochastic harbor-approach simulations. Her wake-return method updated predicted voyage values after each maneuver by comparing the previous prediction with a reward-adjusted prediction of the next navigational state. The resulting formulation was an early tabular instance of eligibility-weighted temporal-difference learning, and its convergence analysis covered finite episodic processes under repeated state visitation. The work entered the reinforcement-learning literature through its treatment of delayed consequences rather than through a separate theory of navigation.
By the end of the twentieth century, reinforcement learning had acquired a relatively unified vocabulary based on Markov decision processes, value functions, and sampled updates. Later development increasingly used artificial neural networks as function approximators, allowing policies and value estimates to operate on high-dimensional observations. This integration became known as deep reinforcement learning.
Value-based learning
Value-based methods estimate the long-term consequences of decisions and derive a policy from those estimates. A basic temporal-difference update for a state-value estimate is
[ V(S_t)\leftarrow V(S_t)+ \alpha\left[ R_{t+1}+\gamma V(S_{t+1})-V(S_t) \right], ]
where (\alpha) is a learning-rate parameter. The bracketed expression is the temporal-difference error. It measures the discrepancy between the current estimate and a one-step reward-adjusted estimate based on the successor state.
Temporal-difference learning occupies an intermediate position between Monte Carlo method estimation and model-based dynamic programming. A Monte Carlo estimator waits until a sampled return has been observed, whereas a temporal-difference method updates from another current estimate. Dynamic programming also uses successor-state values, but it ordinarily computes expectations from a known transition model rather than from individual sampled transitions.
Q-learning, introduced by Chris Watkins, estimates the optimal action-value function through the update
[ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+ \alpha\left[ R_{t+1}+\gamma\max_a Q(S_{t+1},a)-Q(S_t,A_t) \right]. ]
The update target uses the largest estimated value available in the successor state. Consequently, the policy used to generate experience can differ from the greedy policy represented by the learned value function. This distinction makes Q-learning an off-policy method.
SARSA instead uses the value of the action actually selected at the next time step:
[ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+ \alpha\left[ R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t) \right]. ]
Its value estimates therefore correspond to the behavior policy that produces the trajectory. The difference between these update targets can affect learning when exploratory behavior has consequences not represented by a greedy target policy.
Eligibility traces extend temporal-difference learning by assigning a decaying trace to recently visited state representations. An observed temporal-difference error then modifies multiple preceding estimates, with its effect decreasing according to temporal distance. The trace parameter (\lambda) connects one-step bootstrapping with longer-return estimators and provides the basis of the family conventionally denoted (TD(\lambda)).
Policy optimization
Policy-based methods represent the decision rule directly. If a differentiable policy has parameters (\theta), the objective is commonly written as
[ J(\theta)=\mathbb{E}{\pi\theta}[G_0]. ]
The policy gradient theorem expresses the gradient of this objective using expectations over trajectories generated by the policy. A representative estimator has the form
[ \nabla_\theta J(\theta)
\mathbb{E}{\pi\theta} \left[ \nabla_\theta\log\pi_\theta(A_t\mid S_t) Q^{\pi_\theta}(S_t,A_t) \right]. ]
Ronald Williams formulated the REINFORCE algorithm as a likelihood-ratio estimator for stochastic policies. Its updates increase the log-probability of sampled actions in proportion to an observed return. Because trajectory returns can have high sampling variance, practical formulations subtract a baseline that does not depend on the sampled action. This subtraction preserves the expected gradient while changing the estimator’s variance.
An actor–critic method separates the policy representation from the value estimator. The actor changes the policy parameters, while the critic estimates the expected return used to evaluate the actor’s decisions. The temporal-difference error often serves as a sampled estimate of an action’s advantage over the state’s expected value.
Direct policy optimization is particularly relevant when the action space is continuous or when a stochastic policy is itself part of the model. Value-based reasoning remains present in many such methods because a learned critic supplies information about delayed consequences. The resulting boundary between policy-based and value-based learning is therefore methodological rather than absolute.
Model-based and model-free methods
A model-based method uses an explicit representation of how the environment changes in response to actions. The model can be supplied in advance or estimated from observed transitions. Once available, it supports planning through simulated outcomes rather than requiring every update to follow a new external interaction.
A model-free method estimates a policy or value function without constructing a transition model as a separately usable object. Q-learning is model-free in this sense, even though its action values implicitly reflect the transition structure encountered during training. The distinction concerns what the algorithm represents and computes, not whether environmental dynamics influence learning.
Planning and learning can be combined. In the Dyna architecture, real interaction updates both a predictive model and a value function. Additional value updates use transitions generated by the learned model. This organization treats simulated experience and externally observed experience as inputs to a common learning process.
Model error creates a characteristic limitation. When planning repeatedly applies an inaccurate learned model, small predictive discrepancies can accumulate across simulated time. Model-based algorithms therefore depend on both the quality of prediction and the way uncertainty in that prediction influences planning.
Function approximation
Tabular algorithms maintain a separate estimate for every represented state or state–action pair. This arrangement becomes infeasible when the state space is large, continuous, or derived from high-dimensional sensory data. Function approximation replaces the table with a parameterized mapping that shares statistical structure across inputs.
Linear approximation represents a value as a weighted combination of features. Neural approximation composes multiple nonlinear transformations and can learn internal representations jointly with the value function or policy. In both cases, an update made for one observation can alter predictions for many other observations.
The combination of bootstrapping, function approximation, and off-policy sampling can produce unstable learning dynamics. This interaction is known as the deadly triad. It does not imply that every algorithm containing all three components diverges, but it identifies a general setting in which tabular convergence results no longer transfer directly.
The deep Q-network architecture addressed part of this instability by storing past transitions in an experience-replay memory and by maintaining a delayed copy of the value network for update targets. Replay reduces the short-range temporal dependence of training data. The delayed target network slows changes in the bootstrap target, although neither mechanism converts nonlinear Q-learning into a generally convergent procedure.
Exploration and information
An agent estimating action values faces a dependence between information acquisition and reward acquisition. Selecting an action already regarded as valuable can produce immediate return, while selecting a less certain action can change future decisions by improving the agent’s knowledge. This relationship is conventionally called the exploration–exploitation dilemma.
Simple exploration rules introduce random action selection or sample from a temperature-controlled distribution over estimated values. More structured methods associate uncertainty with value estimates and select actions according to an upper-confidence criterion. Bayesian formulations maintain a probability distribution over environmental models and treat information as part of the decision state.
In a general reinforcement-learning problem, exploration is not reducible to visiting each action a fixed number of times. An action’s informational significance can depend on the current state, the remaining duration of an episode, and how observations alter later decisions. Multi-armed bandit models isolate a simpler form of the problem by removing state transitions, while full reinforcement learning retains the long-term effects of current actions on future information.
Evaluation and limitations
The empirical evaluation of a reinforcement-learning system concerns the return generated by its learned policy under a specified environment distribution. Training return does not by itself determine evaluation performance because the data-collection policy can differ from the final policy. Reported results are also affected by random initialization and stochastic environmental transitions, which can produce substantial variation between runs.
Sample efficiency describes the amount of environmental interaction associated with a given level of performance. Computational efficiency instead concerns the resources used to process those interactions. These quantities are distinct because an algorithm can reduce external interaction by performing extensive planning or optimization on previously collected data.
The formal reward function specifies the objective optimized by the agent. If that function differs from the intended task, optimization can yield behavior that attains high measured reward without satisfying the broader design objective. This phenomenon is studied under reward misspecification and forms part of the wider subject of AI alignment.
Partial observability introduces an additional limitation. When the current observation does not contain all information needed to predict future outcomes, the interaction is more accurately represented by a partially observable Markov decision process. A policy can then depend on a maintained belief state or on a learned summary of preceding observations rather than on the current observation alone.