Reinforcement Learning

Reinforcement learning (RL) is the branch of artificial intelligence concerned with agents that learn what to do by acting in an environment and observing the consequences.

13 frameworks, from 1952 to today · Artificial Intelligence · Computer Science

still a working view ended · each leads to its entry below

Overview

Reinforcement learning (RL) is the branch of artificial intelligence concerned with agents that learn what to do by acting in an environment and observing the consequences1. Unlike supervised learning, which needs a teacher to label each example with the right answer, RL assumes only a reward signal: a number the environment returns after each action, saying how good that step was1. The agent's problem is to choose actions that maximize reward over the long run, which usually means sacrificing immediate reward for future gain and discovering which actions matter by trial and error1. What is at stake is learning from consequences rather than instruction — the form of learning that animals and humans use most of the time, and the one that lets a machine master games, robot control, and resource management without anyone telling it the right move.

The optimal-control root: dynamic programming

The mathematical foundation was laid in the 1950s by Richard Bellman, working on multistage decision problems for the RAND Corporation. Bellman formalized the Markov decision process (MDP): a setting with a set of states, a set of actions, transition probabilities saying where each action leads, and rewards. His key insight, the principle of optimality, is that an optimal policy has the property that whatever the first decision is, the remaining decisions must be optimal from the state that results2. This yields the Bellman equation, which relates the value of a state to the values of its successors, and the value function — the expected total discounted reward from a state under a given policy12. Discounting, the factor that shrinks rewards far in the future, was Bellman's device for keeping infinite-horizon sums finite.

Bellman's dynamic programming solved such problems exactly by iterating the Bellman equation over all states1. The catch, obvious from the start, was the "curse of dimensionality": the method needs a table over every state, and real problems have astronomically many2. For decades dynamic programming was a tool for small, fully known models. Its vocabulary — states, values, policies, discounting — became the language every later RL method speaks.

Learning without a model: Monte Carlo and temporal differences

The shift from solving known models to learning from experience came from two directions. Samuel's checkers program (1959) improved its play by playing against itself and adjusting weights on board features, an early demonstration that a program could get better without a human supplying correct moves. In the 1980s, Chris Watkins formalized Q-learning (his 1989 thesis), which learns the value of taking each action in each state directly from experience, without any model of the environment's transitions, and converges to the optimal action-values under mild conditions. Around the same time, Sutton's temporal difference (TD) learning (1988) offered a middle path between Monte Carlo methods, which wait until an episode ends to compute the actual return, and dynamic programming, which needs a model. TD learning updates a state's estimated value toward a bootstrapped target — the reward just received plus the estimated value of the next state — so learning proceeds step by step, online, before the outcome is known3. Sutton's TD-Gammon, built with Gerry Tesauro and reported in 1992, learned backgammon by self-play to a level competitive with strong human players, a landmark showing that TD learning with a learned value function could work at scale.

The 1980s also brought the formal bridge between RL and optimal control: Sutton's 1988 paper explicitly connected TD methods to Bellman's equations, and the textbook Reinforcement Learning: An Introduction by Sutton and Barto (first edition 1998) consolidated the field's vocabulary and became its standard teaching text.

The exploration problem

Any agent learning by trial and error faces the exploration–exploitation dilemma: should it exploit the action it currently believes is best, or explore alternatives that might turn out better14? The multi-armed bandit problem, studied statistically since the 1950s (Herbert Robbins' 1952 work on sequential design), became RL's canonical model of this trade-off. Simple strategies such as ε-greedy (occasionally act randomly) and softmax action selection were standard by the 1990s; optimism in the face of uncertainty — initializing values high so every action gets tried — was another. The deeper point, made repeatedly, is that exploration is not a nuisance but a source of the information the agent needs; a policy that never explores can lock in a mediocre choice forever.

Value functions, policy gradients, and actor–critic

Two families of methods grew up alongside value-based learning. Policy-gradient methods, developed in the late 1980s and 1990s (notably by Ronald Williams, whose 1992 REINFORCE paper gave the likelihood-ratio estimator still used today), parameterize the policy directly and adjust its parameters in the direction that increases expected reward. They handle continuous action spaces and stochastic policies naturally, where tabular value methods struggle. Actor–critic methods combine the two: an actor (the policy) chooses actions, and a critic (a learned value function) evaluates them, supplying a lower-variance signal than raw returns. Barto, Sutton, and Anderson's 1983 neuron-like adaptive element is an early instance; later work made the critic a TD learner.

A parallel line of theory asked when these methods converge. Watkins and Dayan proved Q-learning's convergence in 1992; Jaakkola, Jordan, and Singh analyzed TD(λ) in 1994; and the policy-gradient theorem (Sutton, McAllester, Singh, and Mansour, 2000) gave the exact gradient of expected return with respect to policy parameters, grounding policy methods in calculus rather than heuristics.

Scaling up: function approximation and the deep turn

Tabular methods die when states are continuous or numerous, so the field turned to function approximation: representing values or policies with parameterized functions — linear models, then neural networks — and learning the parameters. This introduced instability, since the guarantees of tabular RL do not carry over. The breakthrough came when deep learning matured5. In 2013 and 2015, DeepMind's DQN (Mnih and colleagues) combined Q-learning with a convolutional neural network to play Atari games from raw pixels, using experience replay (storing past transitions and sampling them) and a target network to stabilize training. It learned dozens of games from the same architecture and signal5. In 2016 AlphaGo defeated Lee Sedol at Go, a game long thought beyond machines, using a policy network, a value network, and Monte Carlo tree search; AlphaGo Zero (2017) learned from self-play alone, without human games. These results made deep RL (deep reinforcement learning) the field's dominant practical paradigm and pushed it into robotics, chip design, and language-model fine-tuning.

Model-based methods and hierarchy

Not everyone abandoned models. Model-based RL learns or is given a model of the environment's transitions and rewards, then plans with it — the direct descendant of Bellman's dynamic programming. Dyna (Sutton, 1990) interleaved real experience with simulated experience from a learned model; later work (PILCO, 2011; MuZero, 2019) showed that learned models could support strong planning. Model-based methods are sample-efficient, learning from less real interaction, at the cost of model error.

Hierarchical RL attacks long-horizon problems by decomposing them into sub-tasks. The options framework (Sutton, Precup, and Singh, 1999) formalized temporally extended actions — "options" — that a higher level can invoke, letting an agent plan over skills rather than primitive steps. Feudal RL (Dayan and Hinton, 1993) and later hierarchical architectures pursued the same idea: build reusable sub-policies and compose them.

Many agents at once

Multi-agent RL studies several learners sharing an environment, where each agent's reward depends on others' actions. This breaks the single-agent assumption that the environment is stationary. Early work in the 1990s applied RL to games and coordination; the field matured with the study of equilibrium concepts, opponent modeling, and self-play, and with landmark results in competitive games (AlphaStar for StarCraft II, 2019) and cooperative benchmarks. Central questions — non-stationarity, credit assignment among agents, and convergence to equilibria — remain active.

Where the field stands

Today RL is split among value-based methods (DQN and its descendants), policy-gradient and actor–critic methods (PPO, SAC, and their relatives), model-based planning, and hierarchical and multi-agent extensions, with deep networks as the default function approximator. The field's open problems are the ones its history kept exposing: sample efficiency (agents still need far more experience than animals), exploration in sparse-reward settings, stability of function approximation, and safe deployment where a bad exploratory action has real costs. The vocabulary Bellman built — states, values, policies, discounting — still organizes everything practitioners do.

References

  1. Reinforcement learning (introduction, Principles, State-value function, Value function), Wikipedia
  2. Bellman equation, Wikipedia
  3. Temporal difference learning, Wikipedia
  4. Exploration–exploitation dilemma, Wikipedia
  5. Deep reinforcement learning (History), Wikipedia

The frameworks of Reinforcement Learning

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1952-Present
  2. 1957-Present

    Dynamic Programming

    How can a multistage decision be solved exactly?

    Fly to its tower in Nousfarer

  3. 1980-Present

    Monte Carlo Methods

    How can outcomes be estimated from sampled experience?

    Fly to its tower in Nousfarer

  4. 1983-Present

    Actor-critic algorithm

    How can a policy and a value estimate improve each other?

    Fly to its tower in Nousfarer

  5. 1988-Present

    Temporal-Difference Learning

    How can values be learned step by step before outcomes are known?

    Fly to its tower in Nousfarer

  6. 1989-Present

    Q-learning

    How can action values be learned without a model?

    Fly to its tower in Nousfarer

  7. 1989-Present

    Value-Function Methods

    How can the value of states or actions be estimated?

    Fly to its tower in Nousfarer

  8. 1990-Present

    Model-Based Reinforcement Learning

    How can a learned model be used to plan?

    About Model-Based Reinforcement Learning
    How can an agent learn to make good decisions when the environment is unknown, and do so with far fewer interactions than trial-and-error methods require? Model-Based Reinforcement Learning (MBRL) answers this by having the agent first learn an explicit model of the environment's dynamics—how actions change states and produce rewards—and then use that model to simulate, plan, and improve its policy. Unlike model-free approaches that directly learn value functions or policies through extensive interaction, MBRL decouples learning the world from acting in it, enabling faster learning and safer planning. This framework addresses the credit assignment problem by allowing the agent to "imagine" the consequences of actions, attributing reward to hypothetical sequences before ever executing them.
    Core curriculum clusters:
    1. Model Learning & Representations: The agent learns a transition and reward function from experience. This can be implicit (stored in a neural network's weights) or explicit (stored as a table or parametric model). Models can be local (approximating dynamics only near visited states) or global (approximating the entire state space). Key approaches include System Identification from control theory and modern deep learning methods.
    1. Integrating Learning and Planning: The Dyna Architecture (Sutton, 1991) provides a canonical framework: interleave real experience (used to update the model) with simulated experience (generated by the model for planning). The agent performs simulated rollouts: running the model forward from a state to evaluate candidate actions. This hybrid approach combines the sample efficiency of model-based methods with the asymptotic convergence of model-free learning.
    1. Planning as Optimization: Given a learned model, the agent can plan by solving a shorter-horizon optimization problem. Trajectory Optimization finds a sequence of actions that maximizes cumulative reward over a planning horizon. Model Predictive Control (MPC) executes only the first action of the optimized plan, then re-plans at each step—a robust strategy that compensates for model inaccuracies.
    1. Handling Model Imperfection: A learned model is never perfect. Certainty Equivalence assumes the model is accurate and plans accordingly, which can fail under misspecification. Bayesian Model-Based RL maintains a distribution over plausible models and plans by averaging over them. Probabilistic Ensembles (e.g., ensembles of neural networks) capture aleatoric and epistemic uncertainty, enabling the agent to allocate exploration where the model is uncertain. Model Uncertainty explicitly quantifies how confident the agent is in its predictions, guiding both planning and exploration.
    1. Sample Efficiency & Exploration: Because planning with a model generates synthetic experience, MBRL often requires far fewer real-world interactions than model-free methods—this is Sample Efficiency. The agent can also engage in Reward-Free Exploration: building a model of the environment without any reward information, then later using that model to solve any reward function specified. This decoupling of exploration from task specification is a distinctive advantage of the model-based paradigm.
    Intellectual history: The roots of MBRL lie in Dynamic Programming (Bellman, 1957), which assumed a perfect model and suffered the curse of dimensionality. In the 1980s, Temporal-Difference Learning (Sutton, 1988) and Q-Learning (Watkins, 1989) introduced model-free value estimation, achieving learning without a model—but at the cost of sample inefficiency. The first explicit MBRL framework emerged in 1991 when Richard Sutton proposed the Dyna architecture, which combined learning a world model with planning via simulated rollouts. Dyna showed that even a simple table-based model could dramatically accelerate learning. Concurrently, Andrew Moore developed Prioritized Sweeping (1993), focusing computational resources on states with large model prediction errors. The field then bifurcated: some researchers (e.g., Atkeson, 1994) pursued local trajectory optimization using differential dynamic programming (DDP), while others explored probabilistic models such as Gaussian processes (Deisenroth & Rasmussen, 2011—a later codification). In the 2010s, deep neural networks enabled high-capacity models for high-dimensional state spaces, leading to the PETS algorithm (Chua et al., 2018) and MBPO (Janner et al., 2019), which revived the Dyna idea with neural network ensembles. These later works are revivals and extensions within the ongoing local dominance window (1991–2026). The framework has coexisted with successor approaches like Policy Gradient Methods, which directly optimize policies but often use MBRL as a source of simulation data. Today, MBRL remains a vibrant research area, prized for its sample efficiency and flexibility.
    The 13 concepts its tower teaches
    • Bayesian Model-Based RL
    • Certainty Equivalence
    • Dyna Architecture
    • Implicit vs Explicit Models
    • Local vs Global Models
    • Model Learning
    • Model Predictive Control
    • Model Uncertainty
    • Planning with Learned Models
    • Probabilistic Ensembles
    • Sample Efficiency
    • Simulated Rollouts
    • Trajectory Optimization

    Fly to its tower in Nousfarer

  9. 1992-Present

    Policy gradient method

    How can a policy be improved directly from reward?

    Fly to its tower in Nousfarer

  10. 1993-Present

    Hierarchical Reinforcement Learning

    How can long-horizon tasks be broken into subtasks?

    Fly to its tower in Nousfarer

  11. 1994-Present

    Multi-Agent Reinforcement Learning

    How do multiple learners behave when sharing an environment?

    Fly to its tower in Nousfarer

  12. 2013-Present

    Deep Reinforcement Learning

    How can neural networks learn control from raw input?

    About Deep Reinforcement Learning
    Deep reinforcement learning (deep RL) addresses a fundamental limitation of classical reinforcement learning: the need for hand-crafted state representations. By combining the trial-and-error logic of RL with deep neural networks as function approximators, deep RL enables agents to learn directly from raw sensory inputs—pixels, audio, or sensor readings—without explicit feature engineering. This breakthrough, beginning around 2013, transformed RL from a small-scale theoretical discipline into a driver of high-impact applications, from game playing to robotics.
    A first course in deep RL builds on classical RL concepts—the Bellman equation, temporal-difference learning, Q-learning, and policy gradients—and then introduces the deep learning machinery that makes them practical. The curriculum progresses through a sequence of algorithmic innovations, each addressing a specific challenge that arises when neural networks serve as function approximators.
    1. Deep Q-Network (DQN) – The foundational algorithm that replaced the Q-table with a deep convolutional neural network, enabling an agent to play Atari games from pixel inputs. DQN introduced two stabilizing mechanisms: experience replay and a target network.
    1. Experience Replay and Target Network – Experience replay stores past transitions in a buffer and samples uniformly, breaking temporal correlations. A separate target network, updated periodically, provides stable targets for the Bellman update, preventing harmful feedback loops.
    1. Double DQN and Dueling DQN – Double DQN reduces overestimation bias by decoupling action selection from evaluation. Dueling DQN splits the Q-value into state-value and advantage streams, allowing the network to learn which states are valuable independently of actions.
    1. Prioritized Experience Replay – A refinement that samples transitions with probability proportional to their temporal-difference error, focusing learning on surprising or informative experiences.
    1. Deep Deterministic Policy Gradient (DDPG) – An actor-critic algorithm for continuous action spaces, using a deterministic policy and a Q-function, both represented by deep networks, with experience replay and target networks for stability.
    1. Trust Region Policy Optimization (TRPO) and Proximal Policy Optimization (PPO) – Policy gradient methods that constrain updates to prevent large, destabilizing changes. TRPO uses a trust region constraint; PPO simplifies this with a clipping mechanism, becoming a default choice for many applications.
    1. Asynchronous Advantage Actor-Critic (A3C) – A framework that runs multiple agents in parallel, each accumulating gradients asynchronously to a shared model, breaking data correlation without a replay buffer.
    1. Soft Actor-Critic (SAC) – An off-policy actor-critic that maximizes a trade-off between expected return and policy entropy, achieving state-of-the-art sample efficiency and stability in continuous control.
    1. Rainbow DQN – An integration of six DQN extensions (including Double, Dueling, Prioritized, and others) into a single agent, demonstrating their complementarity.
    The intellectual history of deep RL traces a convergence of two traditions. Classical RL had matured through temporal-difference learning (Sutton, 1988), Q-learning (Watkins, 1989), and the policy gradient theorem (Sutton et al., 1999). Separately, deep learning underwent a revolution around 2012, when deep convolutional networks achieved dramatic improvements in image classification (Krizhevsky, Sutskever, and Hinton, 2012). The key insight was that these same networks could serve as powerful function approximators for RL. The modern era began in 2013, when Volodymyr Mnih and colleagues at DeepMind published "Playing Atari with Deep Reinforcement Learning," introducing DQN and showing that a single architecture could learn to play seven Atari games at superhuman levels from raw pixels. A 2015 Nature paper extended this to 49 games, cementing deep RL as a major research direction. Subsequent years saw rapid progress: Hado van Hasselt and colleagues introduced Double DQN (2016); Ziyu Wang and colleagues proposed Dueling DQN (2016); Tom Schaul and colleagues developed Prioritized Experience Replay (2016); Timothy Lillicrap and colleagues created DDPG (2016); John Schulman and colleagues introduced TRPO (2015) and PPO (2017); Volodymyr Mnih and colleagues developed A3C (2016); Tuomas Haarnoja and colleagues proposed SAC (2018); and Matteo Hessel and colleagues integrated advances into Rainbow (2018). Deep RL did not replace earlier frameworks but absorbed and extended them. It built on value-based methods (DQN is deep Q-learning), policy gradient methods (PPO is a deep policy gradient), and actor-critic methods (A3C, SAC, DDPG). It has coexisted with model-based and hierarchical RL, often incorporating their ideas. Deep RL transformed RL from a primarily theoretical field into an applied driver of breakthroughs in games (AlphaGo, OpenAI Five), robotics, and scientific discovery.
    The 12 concepts its tower teaches
    • Asynchronous Advantage Actor-Critic (A3C)
    • Deep Deterministic Policy Gradient (DDPG)
    • Deep Q-Network (DQN)
    • Double DQN
    • Dueling DQN
    • Experience Replay
    • Prioritized Experience Replay
    • Proximal Policy Optimization (PPO)
    • Rainbow DQN
    • Soft Actor-Critic (SAC)
    • Target Network
    • Trust Region Policy Optimization (TRPO)

    Fly to its tower in Nousfarer

  13. 2013-Present

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Exploration–Exploitation and Bandit T…Dynamic ProgrammingMonte Carlo MethodsActor-critic algorithmTemporal-Difference LearningQ-learningValue-Function MethodsModel-Based Reinforcement LearningPolicy gradient methodHierarchical Reinforcement LearningMulti-Agent Reinforcement LearningDeep Reinforcement LearningFunction Approximation and Deep Reinf…

Beyond the field

Where Reinforcement Learning's ideas came from in other fields, and what they led to there: the strongest 12 of 44 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Reinforcement Learning is a planet in Nousfarer

Its city has a tower for each of these 13 frameworks. Land, walk in, and climb one concept at a time.

Land on Reinforcement Learning

Related fields

Fields its ideas are linked to

More in Artificial Intelligence

See where Reinforcement Learning sits on the Map of Human Knowledge