Reinforcement learning (RL) is a subfield of machine learning and artificial intelligence in which an agent learns to make sequences of decisions by interacting with an environment. The agent receives rewards or penalties for its actions and aims to maximize cumulative reward over time. Unlike supervised learning, RL does not rely on labeled input-output pairs; instead, it explores its environment, discovers which actions yield the most reward, and refines its policy through trial and error. RL has been successfully applied to domains such as game playing, robotics, autonomous navigation, and recommendation systems.
1 Core concepts
1.1 Agent and environment
In reinforcement learning, the agent is the learner or decision-maker that interacts with the environment, which comprises everything outside the agent. The agent observes the environment's state, chooses actions, and the environment responds with a new state and a reward signal.
1.2 State and action
A state is a representation of the environment at a given time step. An action is a move or decision that the agent can take. The set of all possible states is the state space, and the set of all possible actions is the action space. States may be fully or partially observable.
1.3 Reward and return
A reward is a scalar feedback signal received after each action, indicating the immediate benefit or cost of that action. The return is the cumulative discounted sum of rewards over time, typically defined as \(G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}\), where \(\gamma\) (0 ≤ γ ≤ 1) is the discount factor that balances immediate versus future rewards.
1.4 Policy
A policy (\(\pi\)) is a strategy that the agent uses to decide which action to take in a given state. It can be deterministic (\(\pi(s) = a\)) or stochastic (\(\pi(a|s)\) = probability of taking action \(a\) in state \(s\)). The goal of RL is to find an optimal policy that maximizes expected return.
1.5 Value function
A value function estimates the expected return from a given state or state–action pair.
1.5.1 State-value function
The state-value function \(V(s)\) represents the expected return starting from state \(s\) and following a given policy \(\pi\): \(V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]\).
1.5.2 Action-value function (Q-function)
The action-value function \(Q(s, a)\) denotes the expected return after taking action \(a\) in state \(s\) and thereafter following policy \(\pi\): \(Q^\pi(s, a) = \mathbb{E}_\pi[G_t | S_t = s, A_t = a]\).
1.6 Model of the environment
A model of the environment describes the transition probabilities between states and the reward function. Models can be known explicitly (e.g., in a game) or learned from experience. RL methods that use a model are called model-based; those that do not are model-free.
2 Learning paradigms
2.1 Model-based reinforcement learning
In model-based RL, the agent learns or is given a model of the environment and uses it for planning (e.g., dynamic programming, tree search). The agent can simulate future trajectories to select actions, often improving sample efficiency but requiring accurate model learning.
2.2 Model-free reinforcement learning
Model-free RL learns directly from interaction without building an explicit environment model. It encompasses value-based, policy-based, and actor-critic methods.
2.2.1 Value-based methods
Value-based methods learn a value function (typically the Q-function) and derive a policy implicitly (e.g., greedy action selection with respect to the Q-function).
2.2.1.1 Q-learning
Q-learning is a model-free, off-policy algorithm that updates the Q-function using the Bellman equation: \(Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma \max_{a'} Q(s', a') - Q(s, a)]\). It learns the optimal action-value function directly.
2.2.1.2 Deep Q-networks (DQN)
DQN combines Q-learning with deep neural networks as function approximators for the Q-function. It introduces experience replay and a target network to stabilize training, achieving human-level performance on many Atari 2600 games.
2.2.2 Policy-based methods
Policy-based methods directly parameterize the policy (e.g., with a neural network) and optimize it via gradient ascent on expected return.
2.2.2.1 REINFORCE algorithm
REINFORCE is a Monte Carlo policy gradient method that updates the policy parameters in the direction that increases the probability of actions that yielded higher returns: \(\nabla J(\theta) \approx \sum_t \nabla_\theta \log \pi_\theta(a_t|s_t) G_t\).
2.2.2.2 Policy gradient theorem
The policy gradient theorem provides a theoretical foundation for policy gradient methods: \(\nabla J(\theta) = \mathbb{E}_\pi [ \nabla_\theta \log \pi_\theta(a|s) Q^\pi(s,a) ]\). It shows that the gradient of the expected return can be expressed as an expectation over the score function times the Q-value.
2.2.3 Actor-critic methods
Actor-critic methods maintain two components: an actor (policy) that selects actions and a critic (value function) that evaluates them. The critic reduces variance in the policy gradient update.
2.2.3.1 Advantage actor-critic (A2C)
A2C uses the advantage function \(A(s,a) = Q(s,a) - V(s)\) instead of the raw Q-value to reduce variance. The critic estimates the value function, and the actor is updated using the advantage.
2.2.3.2 Asynchronous advantage actor-critic (A3C)
A3C extends A2C by running multiple parallel agents in separate environment instances, each with its own copy of the network. Asynchronous updates break sample correlation and stabilize training without experience replay.
3 Exploration vs. exploitation
The exploration–exploitation dilemma is the trade-off between trying new actions to discover their effects (exploration) and repeating known high-reward actions (exploitation). Effective RL requires balancing both.
3.1 Epsilon-greedy strategy
Epsilon-greedy selects the greedy action with probability \(1-\epsilon\) and a random action with probability \(\epsilon\). The value of \(\epsilon\) can be decayed over time to shift from exploration to exploitation.
3.2 Upper confidence bound (UCB)
UCB selects actions based on an optimistic estimate: \(a_t = \arg\max_a \left( Q(a) + c \sqrt{\frac{\ln t}{N(a)}} \right)\), where \(N(a)\) counts how many times action \(a\) has been chosen. This encourages exploration of actions with high uncertainty.
3.3 Thompson sampling
Thompson sampling maintains a Bayesian posterior distribution over the Q-values. At each step, it samples from the posterior and selects the action that maximizes the sampled value. It balances exploration and exploitation probabilistically.
4 Algorithms and techniques
4.1 Temporal difference learning
Temporal difference (TD) learning combines Monte Carlo ideas with dynamic programming by updating estimates based on other estimates (bootstrapping) without waiting for the final outcome.
4.1.1 SARSA
SARSA is an on-policy TD control algorithm. It updates the Q-function using the actual next action taken: \(Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma Q(s', a') - Q(s,a)]\). The name comes from the tuple (state, action, reward, next state, next action).
4.1.2 Q-learning (further detail)
As described in 2.2.1.1, Q-learning is off-policy: it updates toward the maximum Q-value of the next state, regardless of the next action actually taken. This enables it to learn the optimal policy while following a different exploration policy.
4.2 Monte Carlo methods
Monte Carlo methods learn from complete episodes of experience. They update value estimates using the actual return obtained, averaging over many episodes. Unlike TD methods, they do not bootstrap and have higher variance but no bias.
4.3 Deep reinforcement learning
Deep RL uses deep neural networks as function approximators for policies, value functions, or both. It enables RL to scale to high-dimensional state spaces like images.
4.3.1 Experience replay
Experience replay stores past transitions \((s, a, r, s')\) in a buffer and samples mini-batches randomly during training. This breaks temporal correlations and improves data efficiency.
4.3.2 Target networks
Target networks are separate copies of the Q-network whose parameters are updated slowly (e.g., every C steps or via Polyak averaging). They provide stable targets in TD updates, mitigating divergence.
4.3.3 Double DQN
Double DQN addresses the overestimation bias of DQN by using the online network to select actions and the target network to evaluate them: \(y = r + \gamma Q_{\text{target}}(s', \arg\max_{a'} Q_{\text{online}}(s', a'))\).
4.3.4 Dueling DQN
Dueling DQN separates the Q-function into a state-value stream and an advantage stream: \(Q(s,a) = V(s) + A(s,a) - \frac{1}{|A|}\sum_{a'} A(s,a')\). This allows the network to learn which states are valuable without needing to know the effect of each action.
4.4 Policy optimization algorithms
4.4.1 Trust region policy optimization (TRPO)
TRPO restricts policy updates to a trust region to avoid large, destabilizing changes. It uses a constraint on the KL divergence between old and new policy and solves a surrogate optimization problem.
4.4.2 Proximal policy optimization (PPO)
PPO simplifies TRPO by clipping the probability ratio in the surrogate objective: \(L^{\text{CLIP}}(\theta) = \mathbb{E}[\min(r_t(\theta) \hat{A}_t, \text{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon) \hat{A}_t)]\). It is easier to implement and widely used.
4.4.3 Soft actor-critic (SAC)
SAC is an off-policy actor-critic method that maximizes a trade-off between expected return and entropy (randomness) of the policy. The entropy term encourages exploration and leads to more robust policies.
5 Applications
5.1 Game playing
RL has achieved superhuman performance in many games.
5.1.1 Atari games
DQN (2013) learned to play 49 Atari 2600 games directly from pixel input, outperforming previous methods and matching human-level performance on many titles.
5.1.2 Go (AlphaGo)
AlphaGo (2016) combined deep neural networks with Monte Carlo tree search and defeated world champion Lee Sedol. It used supervised learning from human games and RL self-play.
5.1.3 Chess and shogi (AlphaZero)
AlphaZero (2017) learned chess, shogi, and Go entirely through self-play RL, without human data or domain-specific knowledge, achieving superhuman performance within hours.
5.2 Robotics
RL enables robots to learn complex motor skills through trial and error.
5.2.1 Motion control
RL has been used for locomotion (walking, running) in legged robots, learning stable gaits in simulation and transferring to real hardware.
5.2.2 Manipulation tasks
Robotic arms learn tasks such as grasping, stacking, and assembly via RL, often using deep RL with visual input.
5.3 Autonomous driving
RL is applied to train driving policies for lane keeping, overtaking, and intersection navigation in simulated and real environments, often combined with imitation learning.
5.4 Recommendation systems
RL-based recommenders treat user interactions as sequential decisions, optimizing for long-term engagement (e.g., click-through rate, dwell time) rather than immediate reward.
5.5 Natural language processing (dialogue systems)
Dialogue agents use RL to learn conversational strategies, reward responses based on user satisfaction or task completion, and improve through interaction.
6 Challenges and open problems
6.1 Sample efficiency
Deep RL often requires millions of interactions to learn effective policies, limiting real-world deployment. Improving sample efficiency remains an active research area.
6.2 Reward design (reward hacking)
Poorly designed reward functions can lead agents to exploit loopholes (e.g., killing itself to avoid negative rewards). Shaping rewards that align with true objectives is difficult.
6.3 Safety and alignment
RL agents may learn unsafe behaviors (e.g., speeding in autonomous driving) or pursue reward in ways that conflict with human values. Ensuring safe exploration and value alignment is critical.
6.4 Generalization across tasks
RL agents typically struggle to transfer knowledge to new environments or tasks. Developing algorithms that generalize robustly without retraining is an open challenge.
7 Related fields
7.1 Control theory
Control theory studies dynamical systems and optimal feedback control. RL shares concepts such as state, action, and optimal cost/reward, but RL emphasizes learning from data rather than analytical solutions.
7.2 Operations research (dynamic programming)
Dynamic programming (DP) provides exact solutions for Markov decision processes when the model is known. RL can be seen as a data-driven extension of DP, handling unknown models via sampling.
7.3 Psychology (operant conditioning)
Operant conditioning in psychology describes how organisms learn through rewards and punishments. RL formalizes this idea mathematically, with the agent as the “learner” and the environment providing reinforcement.