Dictionary of Applied Machine Learning: 114 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here

reinforcement learning (RL)

Updated on 2026-10-28

Readiness 100/100

▶ Run the Python demo Open in Colab Typeset PDF LaTeX source Markdown Cite this entry

See also policy reward online learning supervised learning unsupervised learning

Reinforcement learning (RL) is the task of learning to act optimally within some environment. The actions are taken by an agent based on observations about the environment. The standard mathematical model of the interaction between agent and environment is a Markov decision process (MDP). An MDP includes a transition function, the conditional probability distribution of the next state given the current state and action. Another component of an MDP is a reward function that maps each pair of state and action to a reward value, which can be interpreted as a negative loss value. RL differs from supervised learning in the construction of the loss function: at each time step, the reward is observed only for the action taken, and it depends on previous actions, which forces a trade-off between exploring new actions and exploiting the ones found best.

Figure produced by the Python demo of the entry reinforcement learning (RL)
Figure written by the entry's Python demo reinforcementlearning.py, which recomputes what the entry states: the script block by block · open in Colab

Definition

B-gridworldConsider a robot on the $4 \times 4$ gridworld of Fig. 1: a grid of cells, the cell in row $r$ and column $c$ written $\langle r, c \rangle$, with a wall at $\langle 2, 2 \rangle$ and a goal at $\langle 3, 3 \rangle$. At each time step, the robot moves up, down, left or right. A move into the wall or the boundary leaves it in place. Every move yields a reward of $-1$, while the move that enters the goal yields a reward of $+1$ and results in a stand still. RL is the task of learning, from such interaction, to choose actions that eventually reach the goal. The learner is not told which action is correct but must discover the actions that yield the most reward by trying them, and an action affects not only the immediate reward but also the next state and, through it, all later rewards. These two properties, trial-and-error search and delayed reward, distinguish RL from other forms of learning (Sutton and Barto, 2018, Sect. 1.1).

The standard mathematical model of an RL application is a Markov decision process (MDP) (Sutton and Barto, 2018, Sect. 1.1): a state space $\mathcal{S}$, an action space $\mathcal{A}$, the conditional probability distribution of the next state and reward given the current state and action, and a discount factor $\gamma \in [0, 1]$. The conditional probability distribution of the next state alone is the transition function. An agent interacts with its environment in time steps $t = 1, 2, \ldots$: it observes the state $s_{t}$, chooses an action $a_{t}$, and receives the reward $r_{t+1}$ and the next state $s_{t+1}$ (Sutton and Barto, 2018, Sect. 3.1). The actions are chosen by a policy $\pi$, which for a stochastic policy is a conditional probability distribution $\mathbb{P}^{(a \mid s)}$ over the actions given the state. The quantity to be maximized is the return, the discounted sum of the rewards to come, $G_{t} = \sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1}$, where the discount factor $\gamma$ weighs later rewards less (Sutton and Barto, 2018, Sect. 3.3).

The state-value function of a policy, \[ v_{\pi}(s) := \mathbb{E}_{\pi} \big\{ G_{t} \mid s_{t} = s \big\} \text{,} \] is the expected return from a state when the actions are chosen by $\pi$ (Sutton and Barto, 2018, Sect. 3.5). An optimal policy $\pi_{*}$ is one whose state-value function is at least that of every other policy at every state (Sutton and Barto, 2018, Sect. 3.6). In the gridworld with $\gamma = 1$, a shortest route of $d$ moves earns $-1$ for each of its first $d - 1$ moves and $+1$ for the last, so $v_{\pi_{*}}(s) = -(d-1) + 1 = 2 - d$.

Figure 1 of the entry reinforcementlearning
Figure 1: The $4 \times 4$ gridworld of the opening example: a wall at $\gridcell{2}{2}$, the goal at $\gridcell{3}{3}$, reward $-1$ per move and $+1$ for the move that enters the goal. Each cell shows the optimal state-value function $\statevaluefunc{\optpolicy}(\state)$, which equals $2$ minus the number of moves to the goal, and the arrow of the optimal policy $\optpolicy$. Both are learned from the rewards of the moves tried, without being told how a move changes the state. Data generated by pythondemos/reinforcementlearning.py
As a special case of machine learning (ML), RL also trains a model on data: a policy is the hypothesis of RL. The two properties named above set it apart from supervised learning. The first, trial-and-error search, is the construction of the loss function. A supervised learning method holds the label of each data point and can evaluate the loss of every candidate hypothesis and its predictions. An RL method can evaluate the loss, the negative reward, only for the action it took, since the rewards of the actions not taken are not observed. The second, delayed reward, is that the loss at time step $t$ depends on the previous actions. RL is not unsupervised learning either: it maximizes a reward signal instead of finding structure in unlabeled data points (Sutton and Barto, 2018, Sect. 1.1).

B-improveWithin RL itself, methods differ in the amount of information about the environment required upfront, from a known MDP to nothing beyond the observed rewards (Sutton and Barto, 2018, Sect. 1.3). If the MDP is known, methods such as value iteration and policy iteration compute an optimal policy before the agent executes it (Sutton and Barto, 2018, Ch. 4). A policy is greedy with respect to a value function $v$ if it maximizes, at every state $s \in \mathcal{S}$, the expected immediate reward plus the discounted value of the next state. It therefore chooses an action in $\mathop{\mathrm{arg\,max}}_{a \in \mathcal{A}} \mathbb{E} \big\{ r_{t+1} + \gamma v(s_{t+1}) \mid s_{t} = s, a_{t} = a \big\}$ (Sutton and Barto, 2018, Sect. 4.2). Value iteration and policy iteration use two facts. The state-value function of a policy is the fixed point of its Bellman operator, which iterative policy evaluation reaches from any starting value function (Sutton and Barto, 2018, Sect. 4.1). And the policy that is greedy with respect to $v_{\pi}$ is at least as good as $\pi$ (Sutton and Barto, 2018, Sect. 4.2).

When the MDP is not known, an RL method has to learn from the interaction itself, and every reward it observes is that of an action it has taken. This forces a trade-off between exploration, trying actions whose reward is unknown, and exploitation, choosing the actions found best so far (Sutton and Barto, 2018, Sect. 1.1). Q-learning learns the action-value function $q_{\pi_{*}}(s, a)$, the expected return of taking $a$ in $s$ and following $\pi_{*}$ afterwards, from the rewards of the actions it tries, updating after each time step (Sutton and Barto, 2018, Sect. 6.5). Other methods learn the policy directly (Sutton and Barto, 2018, Ch. 13), or estimate a model of the environment and plan with it (Sutton and Barto, 2018, Ch. 8).

Two special cases of the MDP remove the delayed reward and leave only the trade-off between exploration and exploitation (Sutton and Barto, 2018, Sect. 2.1). The first has a single state: the transition function yields that state whatever the action, so the return is a sum of rewards that each depend on the current action alone. This is the multiarmed bandit (MAB) (Sutton and Barto, 2018, Ch. 2). An ad server that shows one of ten banners and observes the clicks of the banner shown, but not of the nine it withheld, faces this case (Bubeck and Cesa-Bianchi, 2012). The upper confidence bound (UCB) method handles it by adding to the sample mean of each action a confidence term that shrinks with the number of times the action was chosen (Auer et al., 2002; Bubeck and Cesa-Bianchi, 2012).

The second case keeps several states but draws $s_{t}$ from a fixed probability distribution that does not depend on the actions taken. The action at time $t$ then changes the reward $r_{t+1}$ and nothing else, and the state is called the context (Sutton and Barto, 2018, Sect. 2.9). This is the contextual bandit. The learning task is to learn a hypothesis that maps a context to an action, which has the form of a supervised learning problem, except that the loss is still observed only for the action taken. News recommendation is an instance: the context is the visitor profile, the action is the article placed on the front page, and the reward is the click (Li et al., 2010).

RL is often a form of online learning: the agent learns while it acts, and the data points it learns from arrive one per time step and depend on its current policy (Sutton and Barto, 2018, Sect. 1.1). Offline RL instead learns a policy from a fixed dataset of recorded interactions, without acting in the environment during training (Levine et al., 2020). The exploration is then fixed by whoever collected the dataset.

See also: Markov decision process, policy, reward, return, value function, state-value function, gridworld, agent, environment, Bellman operator, Q-learning, policy iteration, value iteration, multiarmed bandit, contextual bandit, upper confidence bound, online learning, supervised learning, unsupervised learning.

References

  1. Sutton and Barto (2018). Reinforcement Learning: An Introduction. MIT Press.
  2. Bubeck and Cesa-Bianchi (2012). Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Found. Trends Mach. Learn.. doi.org/10.1561/2200000024
  3. Auer et al. (2002). Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning.
  4. Li et al. (2010). A Contextual-Bandit Approach to Personalized News Article Recommendation. Proc. International World Wide Web Conference.
  5. Levine et al. (2020). Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems. arxiv.org/abs/2005.01643

Cite this entry

@misc{dictml_reinforcementlearning,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {reinforcement learning (RL)},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-03},
  url = {https://dictionaryofml.org/terms/reinforcementlearning.html}
}