Reinforcement learning

Template:Infobox algorithm

Reinforcement learning (RL) is an area of machine learning concerned with how intelligent agents ought to take actions in an environment in order to maximize the notion of cumulative reward.^[1] Reinforcement learning is one of three basic machine learning paradigms, alongside supervised learning and unsupervised learning.^[2]

Unlike supervised learning which requires labeled input/output pairs, and unlike unsupervised learning which focuses on finding hidden structure in unlabeled data, reinforcement learning focuses on finding a balance between exploration (of uncharted territory) and exploitation (of current knowledge) through trial-and-error interaction with an environment.^[3] The environment is typically formulated as a Markov decision process (MDP), as many reinforcement learning algorithms utilize dynamic programming techniques.^[4]

Overview

Reinforcement learning achieved widespread recognition through several landmark achievements. In 2016, DeepMind's AlphaGo defeated world champion Lee Sedol in the complex game of Go^[5], a feat previously thought to be decades away. In 2019, OpenAI Five defeated the reigning world champion team in Dota 2^[6], demonstrating RL's ability to handle complex team-based strategy games.

The field emerged from the convergence of multiple intellectual traditions. The psychology of animal learning, beginning with Edward Thorndike's Law of Effect in 1911, established that behaviors followed by satisfying consequences tend to be repeated. The mathematical framework came from optimal control theory and Richard Bellman's development of dynamic programming in the 1950s. These threads were unified in the modern field through the work of Richard Sutton and Andrew Barto, who received the 2024 Turing Award for their foundational contributions.^[7]

Core Concepts

Agent-Environment Interaction

Reinforcement learning problems involve an agent interacting with an environment through a cycle of observation, action, and reward.^[3] At each discrete time step t:

1. The agent observes the current state s_t of the environment
2. Based on its policy π, the agent selects an action a_t
3. The environment transitions to a new state s_t+1 according to transition probabilities P(s'|s,a)
4. The agent receives a scalar reward r_t+1 indicating the immediate benefit of that action

The agent's objective is to learn a policy that maximizes the expected return (cumulative reward), typically discounted by factor γ (gamma) where 0 ≤ γ ≤ 1:^[1]

G_t = R_t+1 + γR_t+2 + γ²R_t+3 + ... = Σ_k=0^∞ γ^kR_t+k+1

Key Components

Core Components of Reinforcement Learning Systems

Component	Description	Example
Agent	The learner and decision-maker	Robot, game-playing AI, trading algorithm
Environment	External world the agent interacts with	Maze, chess board, stock market
State (s)	Complete description of environment configuration	Board position in chess
Action (a)	Choice available to the agent	Move piece, buy/sell stock
Reward (r)	Immediate feedback signal	Points scored, profit/loss
Policy (π)	Agent's strategy mapping states to actions	"If in state X, take action Y"
Value Function	Expected long-term reward from a state	Position evaluation in chess
Model	Agent's representation of environment dynamics	Predicted next state and reward

Value Functions

Value functions are central to reinforcement learning, estimating the expected return from states or state-action pairs:^[1]

• State-value function V^π(s): Expected return starting from state s and following policy π
• Action-value function Q^π(s,a): Expected return from taking action a in state s, then following policy π

The optimal value functions satisfy the Bellman optimality equations:^[4]

• V*(s) = max_a Σ_s' P(s'|s,a)[R(s,a,s') + γV*(s')]
• Q*(s,a) = Σ_s' P(s'|s,a)[R(s,a,s') + γ max_a' Q*(s',a')]

Exploration vs. Exploitation

One fundamental challenge in reinforcement learning is the exploration-exploitation tradeoff.^[2] The agent must balance:

• Exploration: Trying new actions to discover potentially better strategies
• Exploitation: Using current knowledge to maximize immediate rewards

Common strategies include ε-greedy (acting randomly with probability ε), upper confidence bound (UCB), and Thompson sampling.

Mathematical Foundations

Markov Decision Processes

Reinforcement learning problems are formally modeled as Markov Decision Processes (MDPs), defined by the tuple (S, A, P, R, γ):^[8]

• S: Finite set of states (state space)
• A: Finite set of actions (action space)
• P(s'|s,a): State transition probability function
• R(s,a,s'): Reward function
• γ: Discount factor (0 ≤ γ < 1)

The Markov property states that the future depends only on the current state, not on the sequence of events that preceded it: P(s_t+1|s_t,a_t,s_t-1,...,s₀) = P(s_t+1|s_t,a_t)

Algorithm Taxonomy

Taxonomy of Reinforcement Learning Algorithms

Category	Description	Examples
Model-Based vs. Model-Free	Whether agent learns environment dynamics	Model-Based: Dyna-Q, AlphaZero Model-Free: Q-Learning, PPO
Value-Based vs. Policy-Based	What the agent learns	Value-Based: Q-Learning, DQN Policy-Based: REINFORCE, PPO
On-Policy vs. Off-Policy	Source of learning data	On-Policy: SARSA, A2C Off-Policy: Q-Learning, DQN
Tabular vs. Function Approximation	State representation method	Tabular: Classic Q-Learning Function Approx: Deep RL

Key Algorithms

Q-Learning

Q-learning is a model-free, off-policy algorithm that learns the optimal action-value function.^[9] The update rule is:

Q(s,a) ← Q(s,a) + α[r + γ max_a' Q(s',a') - Q(s,a)]

where α is the learning rate. Q-learning converges to the optimal Q-function with probability 1 under certain conditions.

Deep Q-Networks (DQN)

Deep Q-Networks revolutionized RL by using deep neural networks to approximate Q-values for high-dimensional state spaces.^[10] Key innovations include:

• Experience replay: Stores transitions in buffer and samples randomly for training
• Target network: Separate network for computing target values, updated periodically

DQN achieved human-level performance on 29 of 49 Atari games using only raw pixel inputs.

Policy Gradient Methods

Policy gradient methods directly optimize parameterized policies by gradient ascent on expected return.^[11] The REINFORCE algorithm updates policy parameters θ using:

∇_θJ(θ) ≈ Σ_t G_t ∇_θ log π_θ(a_t|s_t)

Proximal Policy Optimization (PPO)

Proximal Policy Optimization constrains policy updates to prevent catastrophic performance drops.^[12] PPO optimizes a clipped surrogate objective:

L^CLIP(θ) = E[min(r_t(θ)Â_t, clip(r_t(θ), 1-ε, 1+ε)Â_t)]

where r_t(θ) = π_θ(a_t|s_t)/π_θold(a_t|s_t) and ε is typically 0.2.

Actor-Critic Methods

Actor-critic algorithms combine value-based and policy-based approaches:^[13]

• Actor: Policy network that selects actions
• Critic: Value network that evaluates actions

Examples include A2C, A3C, SAC, and DDPG.

Algorithm Comparison

Comparison of Major RL Algorithms

Algorithm	Type	Year	Key Innovation	Best For	Sample Efficiency
Q-Learning	Value, Off-policy	1989	Model-free optimal control	Tabular tasks	Low
SARSA	Value, On-policy	1994	On-policy TD control	Safe learning	Low
DQN	Value, Off-policy	2013	Deep RL with replay buffer	Discrete actions, visual input	Medium
DDPG	Actor-Critic, Off-policy	2015	Continuous action DQN	Continuous control	Medium
TRPO	Policy, On-policy	2015	Trust region constraints	Stable learning	Low
PPO	Policy, On-policy	2017	Clipped surrogate objective	General purpose	Low
A3C	Actor-Critic, On-policy	2016	Asynchronous parallel training	CPU-based training	Low
SAC	Actor-Critic, Off-policy	2018	Maximum entropy RL	Continuous control	High
TD3	Actor-Critic, Off-policy	2018	Twin critics, delayed updates	Continuous control	High
AlphaZero	Model-based	2017	Self-play with MCTS	Perfect info games	Very High
MuZero	Model-based	2020	Learned latent dynamics	Games without rules	Very High

Historical Milestones

Key Milestones in Reinforcement Learning History

Year	Milestone	Key Contributor(s)	Significance
1911	Law of Effect	Edward Thorndike	Established principle that rewarded actions are reinforced
1950s	Dynamic Programming & Bellman Equation	Richard Bellman	Mathematical framework for sequential decision-making
1959	Checkers Program	Arthur Samuel	First self-learning game program, coined "machine learning"
1963	MENACE	Donald Michie	Matchbox machine that learned tic-tac-toe
1988	Temporal Difference Learning	Richard Sutton	Unified Monte Carlo and dynamic programming methods
1989	Q-Learning	Christopher Watkins	Model-free off-policy control algorithm
1992	TD-Gammon	Gerald Tesauro	Achieved world-class backgammon performance
1992	REINFORCE Algorithm	Ronald Williams	Fundamental policy gradient algorithm
1998	"Reinforcement Learning: An Introduction"	Richard Sutton, Andrew Barto	Seminal textbook defining the field
2013-2015	Deep Q-Networks	DeepMind	Deep RL breakthrough on Atari games
2016	AlphaGo defeats Lee Sedol	DeepMind	First AI to defeat world champion at Go
2017	AlphaGo Zero	DeepMind	Learned Go from scratch through self-play
2018	AlphaZero	DeepMind	Mastered chess, shogi, and Go in 24 hours
2019	OpenAI Five	OpenAI	Defeated Dota 2 world champions
2019	AlphaStar	DeepMind	Achieved Grandmaster in StarCraft II
2024	Turing Award	Richard Sutton, Andrew Barto	Recognition for RL foundations

Applications

Game Playing

Reinforcement learning has achieved superhuman performance in numerous games:

• Board Games: AlphaGo, AlphaZero, and MuZero revolutionized game AI^[14]
• Video Games: DQN mastered 49 Atari games; OpenAI Five conquered Dota 2; AlphaStar reached Grandmaster in StarCraft II^[15]
• Poker: Pluribus defeated professional players in 6-player no-limit Texas Hold'em

Robotics

RL enables robots to learn complex motor skills through trial and error:

• Locomotion: Boston Dynamics robots use RL for walking and navigation^[16]
• Manipulation: Robotic hands solving Rubik's Cube, grasping diverse objects
• Assembly: Industrial robots learning assembly sequences
• Sim-to-Real Transfer: Training in simulation before real-world deployment

Autonomous Vehicles

Self-driving cars employ RL for:

• Path planning and trajectory optimization
• Lane changing and merging decisions
• Adaptive cruise control
• Traffic light negotiation
• Waymo reports over 20 million autonomous miles driven^[17]

Healthcare

RL applications in medicine include:

• Treatment Optimization: Dynamic treatment regimes for chronic diseases^[18]
• Drug Discovery: Molecular design and optimization
• Personalized Medicine: Adaptive clinical trials
• Resource Allocation: ICU bed management, staff scheduling

Finance and Trading

Financial applications include:

• Algorithmic Trading: Automated trading strategies^[19]
• Portfolio Management: Dynamic asset allocation
• Risk Management: Credit scoring, fraud detection
• Market Making: Liquidity provision strategies

Energy and Sustainability

• Data Center Cooling: Google achieved 40% energy reduction using RL^[20]
• Smart Grids: Load balancing and demand response
• Wind Farms: Turbine control optimization
• Building Management: HVAC system optimization

Natural Language Processing

• Reinforcement Learning from Human Feedback (RLHF): Training ChatGPT, Claude, GPT-4^[21]
• Dialogue Systems: Conversational AI optimization
• Machine Translation: Improving translation quality
• Text Summarization: Generating concise summaries

Development Tools and Frameworks

Popular RL Development Frameworks

Framework	Language	GitHub Stars	Backend	Best For
OpenAI Gym/Gymnasium	Python	35,000+	Agnostic	Environment standard
Ray RLlib	Python	33,000+	Multiple	Production, distributed training
Stable-Baselines3	Python	9,000+	PyTorch	Reliable implementations
Unity ML-Agents	C#/Python	17,000+	PyTorch	3D/VR/AR simulation
TorchRL	Python	2,300+	PyTorch	Research flexibility
TF-Agents	Python	2,800+	TensorFlow	TF ecosystem
Tianshou	Python	7,800+	PyTorch	Modular design
ACME	Python	3,400+	JAX/TF	DeepMind research

Simulation Environments

• Physics Simulators: MuJoCo, PyBullet, Isaac Gym
• Game Environments: ALE (Atari), MineRL (Minecraft)
• Multi-Agent: PettingZoo, SMAC
• Autonomous Driving: CARLA, SUMO
• Robotics: RoboSuite, Meta-World

Challenges and Limitations

Sample Inefficiency

RL algorithms often require millions of interactions to learn:^[22]

• DQN: 200 million frames for Atari (equivalent to 924 hours of human play)
• OpenAI Five: 45,000 years of Dota 2 gameplay
• AlphaGo Zero: 4.9 million self-play games

Solutions include model-based RL, transfer learning, and curriculum learning.

Exploration Challenges

Effective exploration remains difficult in:

• Sparse Reward Environments: Where rewards are rare
• Large State Spaces: Exponential growth of possibilities
• Safety-Critical Domains: Where exploration risks catastrophic failure

Approaches include curiosity-driven learning, intrinsic motivation, and safe exploration.

Reward Specification

Designing appropriate reward functions is challenging:^[23]

• Reward Hacking: Agents exploit unintended loopholes
• Reward Shaping: Manual engineering is difficult and error-prone
• Multi-Objective Optimization: Balancing competing goals

Solutions include inverse reinforcement learning, preference learning, and reward modeling.

Generalization and Transfer

RL agents often fail to generalize:

• Domain Shift: Performance degrades in new environments
• Sim-to-Real Gap: Policies trained in simulation fail in reality
• Catastrophic Forgetting: Learning new tasks overwrites old knowledge

Research areas include meta-learning, domain randomization, and continual learning.

Interpretability and Safety

• Black Box Policies: Neural networks lack interpretability
• Verification Challenges: Difficult to prove safety guarantees
• Adversarial Vulnerabilities: Susceptible to adversarial attacks
• Alignment Problem: Ensuring AI goals align with human values

Current Research Directions

Offline Reinforcement Learning

Offline RL learns from fixed datasets without environment interaction:^[24]

• Conservative Q-Learning (CQL)
• Implicit Q-Learning (IQL)
• Decision Transformers
• Applications in healthcare and robotics where exploration is expensive

Multi-Agent Reinforcement Learning

Multi-agent RL addresses scenarios with multiple learning agents:^[25]

• Cooperative: Team coordination and communication
• Competitive: Game theory and Nash equilibria
• Mixed: Social dilemmas and negotiation
• Applications in autonomous driving, robotics swarms

Hierarchical Reinforcement Learning

Hierarchical RL decomposes complex tasks into subtasks:

• Options framework for temporal abstraction
• Goal-conditioned policies
• Feudal networks
• Applications in long-horizon planning

Model-Based Reinforcement Learning

Leveraging learned environment models for planning:^[26]

• World models and imagination
• MuZero: Planning without knowing rules
• Dreamer: Visual model-based RL
• Differentiable physics simulators

Reinforcement Learning from Human Feedback (RLHF)

Aligning AI systems with human preferences:^[27]

• Preference modeling from comparisons
• Constitutional AI for value alignment
• AI feedback (RLAIF) for scalability
• Applications in large language models

Foundation Models and Transformers

Integration with large-scale pre-trained models:

• Decision Transformers: RL as sequence modeling
• Gato: Generalist agent for multiple domains
• RT-1/RT-2: Vision-language-action models for robotics
• Pre-trained world models from internet-scale data

See Also

Template:Columns-list

References

1. Sutton, R. S., & Barto, A. G. (2018). *Reinforcement Learning: An Introduction* (2nd ed.). MIT Press.
2. Kaelbling, L. P., Littman, M. L., & Moore, A. W. (1996). "Reinforcement learning: A survey." *Journal of Artificial Intelligence Research*, 4, 237-285.
3. Sutton, R. S., & Barto, A. G. (1998). *Reinforcement Learning: An Introduction* (1st ed.). MIT Press.
4. Bellman, R. (1957). *Dynamic Programming*. Princeton University Press.
5. Silver, D., et al. (2016). "Mastering the game of Go with deep neural networks and tree search." *Nature*, 529(7587), 484-489.
6. OpenAI. (2019). "OpenAI Five defeats Dota 2 world champions." OpenAI Blog.
7. ACM. (2024). "ACM A.M. Turing Award recognizes pioneers of reinforcement learning."
8. Pavlov, I. P. (1927). *Conditioned Reflexes: An Investigation of the Physiological Activity of the Cerebral Cortex*. Oxford University Press.
9. Thorndike, E. L. (1911). *Animal Intelligence: Experimental Studies*. Macmillan.
10. Bellman, R. (1957). "A Markovian decision process." *Journal of Mathematics and Mechanics*, 6(5), 679-684.
11. Sutton, R. S. (1988). "Learning to predict by the methods of temporal differences." *Machine Learning*, 3(1), 9-44.
12. Sutton, R. S., & Barto, A. G. (1998). *Reinforcement Learning: An Introduction*. MIT Press.
13. Puterman, M. L. (1994). *Markov Decision Processes: Discrete Stochastic Dynamic Programming*. Wiley.
14. Sutton, R. S. (1990). "Integrated architectures for learning, planning, and reacting based on approximating dynamic programming." *Proceedings of the 7th International Conference on Machine Learning*.
15. Hafner, D., et al. (2023). "Mastering diverse domains through world models." *arXiv:2301.04104*.
16. Watkins, C. J. C. H., & Dayan, P. (1992). "Q-learning." *Machine Learning*, 8(3), 279-292.
17. Rummery, G. A., & Niranjan, M. (1994). "On-line Q-learning using connectionist systems." *Technical Report CUED/F-INFENG/TR 166*, Cambridge University.
18. Mnih, V., et al. (2015). "Human-level control through deep reinforcement learning." *Nature*, 518(7540), 529-533.
19. Williams, R. J. (1992). "Simple statistical gradient-following algorithms for connectionist reinforcement learning." *Machine Learning*, 8(3), 229-256.
20. Konda, V. R., & Tsitsiklis, J. N. (2000). "Actor-critic algorithms." *Advances in Neural Information Processing Systems*, 12.
21. Mnih, V., et al. (2016). "Asynchronous methods for deep reinforcement learning." *Proceedings of the 33rd International Conference on Machine Learning*.
22. Lillicrap, T. P., et al. (2015). "Continuous control with deep reinforcement learning." *arXiv:1509.02971*.
23. Fujimoto, S., Hoof, H., & Meger, D. (2018). "Addressing function approximation error in actor-critic methods." *Proceedings of the 35th International Conference on Machine Learning*.
24. Schulman, J., et al. (2017). "Proximal policy optimization algorithms." *arXiv:1707.06347*.
25. Haarnoja, T., et al. (2018). "Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor." *Proceedings of the 35th International Conference on Machine Learning*.
26. Tesauro, G. (1995). "Temporal difference learning and TD-Gammon." *Communications of the ACM*, 38(3), 58-68.
27. Silver, D., et al. (2017). "Mastering the game of Go without human knowledge." *Nature*, 550(7676), 354-359.
28. Silver, D., et al. (2018). "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play." *Science*, 362(6419), 1140-1144.
29. Vinyals, O., et al. (2019). "Grandmaster level in StarCraft II using multi-agent reinforcement learning." *Nature*, 575(7782), 350-354.
30. Christiano, P. F., et al. (2017). "Deep reinforcement learning from human preferences." *Advances in Neural Information Processing Systems*, 30.
31. Ouyang, L., et al. (2022). "Training language models to follow instructions with human feedback." *Advances in Neural Information Processing Systems*, 35.
32. Bai, Y., et al. (2022). "Constitutional AI: Harmlessness from AI feedback." *arXiv:2212.08073*.
33. DeepSeek-AI. (2025). "DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning." *arXiv:2501.12948*.
34. Brown, N., & Sandholm, T. (2019). "Superhuman AI for multiplayer poker." *Science*, 365(6456), 885-890.
35. FAIR et al. (2022). "Human-level play in the game of Diplomacy by combining language models with strategic reasoning." *Science*, 378(6624), 1067-1074.
36. OpenAI et al. (2019). "Solving Rubik's Cube with a robot hand." *arXiv:1910.07113*.
37. Komorowski, M., et al. (2018). "The Artificial Intelligence Clinician learns optimal treatment strategies for sepsis in intensive care." *Nature Medicine*, 24(11), 1716-1720.
38. Evans, R., & Gao, J. (2016). "DeepMind AI reduces Google data centre cooling bill by 40%." DeepMind Blog.
39. Busoniu, L., Babuska, R., & De Schutter, B. (2008). "A comprehensive survey of multiagent reinforcement learning." *IEEE Transactions on Systems, Man, and Cybernetics*, 38(2), 156-172.
40. Albrecht, S. V., Christianos, F., & Schafer, L. (2024). *Multi-Agent Reinforcement Learning: Foundations and Modern Approaches*. MIT Press.
41. Dulac-Arnold, G., et al. (2019). "Challenges of real-world reinforcement learning." *arXiv:1904.12901*.
42. Amodei, D., et al. (2016). "Concrete problems in AI safety." *arXiv:1606.06565*.
43. Zhao, W., et al. (2020). "Sim-to-real transfer in deep reinforcement learning for robotics: A survey." *arXiv:2009.13303*.
44. Levine, S., et al. (2020). "Offline reinforcement learning: Tutorial, review, and perspectives on open problems." *arXiv:2005.01643*.
45. Reed, S., et al. (2022). "A generalist agent." *arXiv:2205.06175*.

External Links

• Reinforcement Learning: An Introduction - Sutton and Barto's textbook
• OpenAI Spinning Up - Educational resource for deep RL
• Gymnasium - Standard RL environment library
• Stable-Baselines3 Documentation
• Ray RLlib Documentation
• DeepMind Research

Template:Machine learning

Template:Navbox Template:Game artificial intelligence