Reinforcement Learning

In this and previous chapters, we have encountered and briefly discussed several key elements of a reinforcement learning system: a policy, an environment, a reward signal, a value function, and, optionally, a model of the environment. In this section, we provide a more formal definition of these elements and discuss how they interact in the context of the reinforcement learning problem.

Let us briefly revisit the MDP framework, which provides a standard mathematical formalization of the reinforcement learning problem. Formally, an MDP is defined as a tuple:

where $𝒳$ denotes the state space, which is the set of all possible environment states $𝒙\in 𝒳$ and can be either discrete or continuous, $𝒰$ denotes the action space, which is the set of admissible actions $𝒖\in 𝒰$ and can also be discrete or continuous, $p$ characterizes the system dynamics through the transition probability distribution $p({𝒙}_{t+1}\mid {𝒙}_t,{𝒖}_t)$, $R:𝒳\times 𝒰\to ℝ$ specifies the reward function, and $\gamma \in (0,1]$ is a discount factor that determines the relative importance of future rewards. From a reinforcement learning perspective, the goal is to learn a policy defined as a probability distribution over actions given states, $\pi (𝒖\mid 𝒙)$. We will use the term trajectory to refer to a sequence of states and actions of length $T$, given by:

where $T$ may be infinite. Given a policy $\pi$, the induced trajectory distribution $p_{\pi }$ is:

where $p_0$ is the initial-state distribution. The reinforcement learning objective is to maximize the expected discounted cumulative reward under this trajectory distribution, namely:

An additional concept required to fully characterize $V_T^{\pi }$ is that of discounting. In particular, the discount factor $\gamma$ is a scalar value in the range $[0,1]$ that determines the relative importance of future rewards, whereby a smaller $\gamma$ will make the agent focus more on immediate rewards, while a larger $\gamma$ will make the agent give more importance to future rewards. For example, in the limit case with $\gamma =0$, the agent will only consider immediate rewards, while in the case with $\gamma =1$, the agent will consider all future rewards equally. Mathematically, discounting is also crucial in ensuring that the sum of rewards in $V^{\pi }$ is finite even in the infinite horizon case with $T=\mathrm{\infty }$, such that if and the rewards $r_t$ are bounded, the sum of the rewards will be finite. In practice, the choice of $\gamma$ is often problem-dependent, and it is common to use a value close to $1$ to ensure that the agent considers future rewards.

Almost all reinforcement learning algorithms involve estimating value functions. At its core, a value function is a function of state or state-action pairs that defines how good^††margin: As defined in the previous section, value functions quantify quality in terms of expected cumulative future rewards. it is for the agent to be in a given state or to take a given action in a given state. Since the reward an agent expects to receive in the future depends on the actions it will take, the value function is inherently defined with respect to a particular policy $\pi$.

We define the state-value function, $V^{\pi }(𝒙)$, as the expected sum of future rewards when starting in state $𝒙$ and following policy $\pi$ thereafter^††margin: Throughout this chapter, we primarily consider the infinite-horizon case when referring to $V^{\pi }$, although the same concepts extend to the finite-horizon case. :

Similarly, the action-value function, $Q^{\pi }(𝒙,𝒖)$, is the expected return when starting in state $𝒙$, taking action $𝒖$, and then following policy $\pi$ thereafter:

A key property of value functions used in the context of reinforcement learning and dynamic programming is that they satisfy the Bellman equations. The Bellman equations describe a recursive relationship that decomposes the value of a state or state-action pair into the immediate reward and the value of the next state or state-action pair. Formally, for any policy $\pi$ and any state $𝒙$, the Bellman equation defines the following self-consistency condition:

where, to simplify notation, we have omitted the time index $t$ and used ${𝒙}^{\prime }$ to denote the next state.

Similarly, the Bellman equation for the action-value function is:

Crucially, the value functions $V^{\pi }$ and $Q^{\pi }$ are unique solutions to the Bellman equations.

In the remainder of this chapter, we show how we can use the Bellman equations to derive algorithms for estimating and approximating value functions, and how we can use these value functions to derive optimal policies.

Central to the solution of reinforcement learning problems are the notions of optimal policies and optimal value functions. The term optimal derives from the fact that value functions induce a partial ordering over policies, where a policy $\pi$ is said to be better than or equal to another policy ${\pi }^{\prime }$ if its value is no worse in every state. Formally, we write $\pi \ge {\pi }^{\prime }$ if and only if:

An optimal policy ${\pi }^{\ast }$ is a policy that is better than or equal to all other policies, such that ${\pi }^{\ast }\ge \pi$ for all policies $\pi$. While the optimal policy does not need to be unique, all optimal policies share the same optimal value function $V^{\ast }$, defined as:

Similarly, optimal policies also share the same optimal action-value function $Q^{\ast }(𝒙,𝒖)$, defined as:

As discussed above, $V^{\ast }$ and $Q^{\ast }$ are value functions for the optimal policy, thus, they must satisfy the Bellman equations with respect to the optimal policy. However, because $V^{\ast }$ and $Q^{\ast }$ are the optimal value functions, the Bellman equations can be written in a policy-independent form. This is achieved by exploiting the fact that, under an optimal policy, the value of a state is equal to the expected return obtained by selecting the best available action in that state.

Formally, the Bellman equations for the optimal state-value function and action-value function—referred to as the Bellman optimality equations—can be derived by substituting the expectation over the policy from Equation 18.5 and Equation 18.6 with a maximization over actions, and are given by:

Why are $V^{\ast }$ and $Q^{\ast }$ so central to reinforcement learning? The key reason is that, once either of these functions is known, deriving an optimal policy is substantially simpler. In particular, an optimal policy can be derived by acting greedily with respect to the optimal value functions. For example, given the optimal state-value function $V^{\ast }$, the optimal policy can be computed as:

That is, once $V^{\ast }$ is known, determining the optimal policy reduces to a one-step lookahead where, at each state, the agent selects the action that leads to successor states with the highest expected value.

Access to the optimal action-value function, $Q^{\ast }$, simplifies the process even further. For any state $𝒙$, we can obtain the optimal policy by selecting the action that maximizes $Q^{\ast }$:

Thus, by representing a function over states (or state-action pairs), the optimal value functions allow for the direct computation of the optimal policy.

We first consider the prediction problem of estimating the value function, $V^{\pi }$, under a given policy $\pi$. According to the Bellman equation in Equation 18.5, the value of a state $𝒙$ under policy $\pi$ is defined as an expectation with respect to the policy and state transition model. For simplicity, we assume that the state transition model and policy describe probability distributions over discrete states and actions, respectively, which allows us to express the expectations in the Bellman equation as sums rather than integrals^††margin: The extension to continuous states and actions is fundamentally equivalent and requires the replacement of summations with integrals. :

Policy evaluation is an iterative algorithm to solve the prediction problem. Consider a sequence of approximations to the value function, denoted as $V_0,V_1,V_2,\mathrm{\dots },V^{\pi }$, where $V_0$ is an arbitrarily chosen initial guess^††margin: Under the condition that any terminal state, occurring when $t=T$ in the finite-horizon setting or when the episode terminates in the infinite-horizon setting, must be assigned a value of zero. . Policy evaluation uses the Bellman equation in Equation 18.11 as an update rule, such that at iteration $k$, the value function for all states $x\in 𝒳$ is updated according to:

It is important to note that $V_k=V^{\pi }$ is a fixed point of the update rule in Equation 18.12 since the Bellman equation for $V^{\pi }$ ensures equality in this case. Moreover, under mild regularity conditions, it can be shown that the sequence of value functions $\{V_k\}$ converges to $V^{\pi }$ as $k\to \mathrm{\infty }$. As we will see in the remainder of this chapter, the ideas described above are at the core of many reinforcement learning algorithms, including both model-based and model-free methods.

Having introduced an approach for solving the prediction problem, namely, estimating the value function under a fixed policy, we now turn to the problem of control, where the objective is to compute an optimal policy. To address the control problem, we rely on the policy improvement theorem, which provides a principled mechanism for transforming a given policy into a new policy that is guaranteed to be better than or equal to the original.

Consider two policies, $\pi$ and ${\pi }^{\prime }$, such that for all states $x\in 𝒳$:

Then, the policy ${\pi }^{\prime }$ is guaranteed to be better than or equal to $\pi$, such that:

Intuitively, if ${\pi }^{\prime }$ chooses actions that are at least as good—according to the action-value function of $\pi$ in Equation 18.13—as those prescribed by $\pi$ in every state (i.e., $V^{\pi }(𝒙)$), then following ${\pi }^{\prime }$ cannot result in worse long-term performance than continuing to follow $\pi$.

Consider the greedy policy ${\pi }^{\prime }$, which selects, in each state, the action that maximizes the action-value function $Q^{\pi }$ associated with policy $\pi$^††margin: In other words, the greedy policy performs a one-step lookahead using the current state-value function $V^{\pi }$. :

By construction, this greedy policy satisfies the condition of the policy improvement theorem in Equation 18.13 and is therefore guaranteed to be better than or equal to the original policy. We refer to the process of constructing a new policy by greedily selecting actions with respect to the current value function as policy improvement.

Suppose now that the greedy policy ${\pi }^{\prime }$ is as good as the original policy $\pi$, such that $V^{{\pi }^{\prime }}=V^{\pi }$. From the definition of the greedy policy in Equation 18.14, we have:

Since $V^{{\pi }^{\prime }}=V^{\pi }$, this expression is equivalent to the Bellman optimality equation in Equation 18.7. Therefore, the value function $V^{\pi }$ must equal the optimal value function, and the policy ${\pi }^{\prime }$ is therefore optimal.

In other words, policy improvement provides a systematic procedure for iteratively improving a policy using its value function, and it converges once the optimal policy is reached.

The policy improvement theorem provides a concrete strategy to improve a policy by greedily selecting actions with respect to the current value function. In this section, we discuss how we use this strategy, in tandem with policy evaluation, to construct an algorithm for finding the optimal policy. We refer to this algorithm for finding the optimal policy as policy iteration. At a high level, the key idea of policy iteration is as follows: starting from a given policy $\pi$, we first evaluate it to obtain its value function $V^{\pi }$ and then improve the policy using this value function to produce a new policy ${\pi }^{\prime }$. The improved policy ${\pi }^{\prime }$ is subsequently evaluated to compute $V^{{\pi }^{\prime }}$, which is in turn used to derive an improved policy ${\pi }^{\prime \prime }$. This alternating process of policy evaluation and policy improvement is repeated until the policy converges to the optimal policy.

More formally, policy iteration defines a sequence of monotonically improving policies by alternating between policy evaluation and policy improvement:

where PE denotes policy evaluation and PI denotes policy improvement. We outline the policy iteration algorithm in Algorithm 1.

Policy iteration is guaranteed to converge to the optimal policy and value function, given enough iterations. In practice, since the policy evaluation step is an iterative algorithm, we typically initialize the value function to the value function from the previous step of policy iteration. This can increase the speed of convergence since the value function does not typically change substantially between iterations.

One drawback of policy iteration is that it requires a full policy evaluation step at each iteration. As a result, the algorithm can be computationally expensive, since it must wait for the value function to converge before performing a policy improvement step, which only happens in the limit^††margin: Several variants of policy iteration mitigate this cost by using truncated or approximate policy evaluation steps. . To address this limitation, value iteration provides an alternative approach that combines policy evaluation and policy improvement into a single step. Value iteration defines the following update rule:

Starting from an arbitrary initial value function $V_0$, the sequence of value functions $\{V_k\}$ generated by value iteration is guaranteed to converge to the optimal value function $V^{\ast }$.

Value iteration can be interpreted through the lens of the Bellman optimality equation, where the update in Equation 18.15 corresponds to applying the Bellman optimality operator from Equation 18.7 to the current value function $V_k$. In contrast to policy iteration, which alternates between iteratively solving the Bellman equation for a fixed policy and performing a separate policy improvement step, value iteration directly applies the Bellman optimality equation at every iteration. We outline the complete value iteration algorithm in Algorithm 2.

Policy iteration and value iteration are two of the most foundational algorithms in reinforcement learning and are the basis for many modern reinforcement learning algorithms.

Dynamic programming methods, including policy iteration and value iteration, are powerful tools for solving MDPs. However, these methods also inherit the limitations of dynamic programming as they require a complete model of the environment, $p({𝒙}^{\prime }\mid 𝒙,𝒖)$, to compute the expectations in the Bellman equations, and are computationally expensive for large state and action spaces. In the next sections, we discuss two key approaches to address these limitations. We first introduce sampling methods, which relax the requirement of having a complete model of the environment, and then we introduce the concept of function approximation, which helps address the computational complexity of dynamic programming methods.

The term Monte Carlo broadly refers to a class of algorithms that rely on random sampling to estimate quantities of interest. In the context of reinforcement learning, Monte Carlo methods represent a class of approaches for solving the reinforcement learning problem based on averaging observed cumulative rewards from experience^††margin: We often use the terms samples or experience to refer to sequences of states, actions, and rewards collected by interacting with the environment. . We assume that the agent interacts with the environment for a fixed number of time steps $T$, referred to as an episode, during which it collects a trajectory consisting of states, actions, and rewards. Episodic MDPs naturally describe tasks with well-defined beginnings and endings, such as navigating a maze, playing a game, or completing a robotic assembly. At the end of each episode, the agent uses these observed trajectories to estimate quantities of interest, such as value functions or policy updates.

Monte Carlo methods for solving the prediction problem aim to learn the value function $V^{\pi }$ (or equivalently, $Q^{\pi }$) given a policy $\pi$. In this section, we first address the problem of using Monte Carlo methods for learning the state-value function $V^{\pi }$, and then extend the discussion to learning the action-value function $Q^{\pi }$. Since the value of a state is defined as the expected cumulative reward obtained when starting from that state, it can be estimated by averaging the cumulative rewards observed across episodes that visit the state. As the agent visits a state more frequently, the estimate of its value becomes increasingly accurate.

Formally, suppose we wish to learn the value $V^{\pi }(𝒙)$ of the state $𝒙$ under the policy $\pi$, using a set of $N$ episodes $\{{\tau }_1,{\tau }_2,\mathrm{\dots },{\tau }_N\}$ passing through $𝒙$. The state-value function can be estimated using the Monte Carlo prediction procedure outlined in Algorithm 3.

In particular, Monte Carlo prediction updates the value estimate $V(x_t)$ using the incremental update rule:

which moves the current estimate toward the observed return $G_t$, where $N(x_t)$ denotes the number of times state $x_t$ has been visited. This incremental form provides an efficient way to compute sample averages and is equivalent to the empirical mean:

where $G_t^i$ is the cumulative future reward observed in the $i$-th visit to state ${𝒙}_t$.

We can also use Monte Carlo methods for learning action values^††margin: Learning action values $Q^{\pi }$ is useful in practice because we can use them to directly derive an optimal policy using Equation 18.10. . At a high level, Monte Carlo methods for estimating action value functions $Q^{\pi }(𝒙,𝒖)$ are essentially equivalent to the method presented above for estimating state values, with the only difference being that we now consider visits to state-action pairs instead of states. We consider a state-action pair to have been visited in an episode if the agent is in state $𝒙$ and takes action $𝒖$ at some point during the episode. As with state-value estimation, Monte Carlo methods estimate the action-value function $Q^{\pi }(x,u)$ by averaging the cumulative rewards observed from visits to the state–action pair $(x,u)$. However, estimating action values introduces an additional challenge.

Suppose that experience is generated using a deterministic policy $\pi$. Under such a policy, the agent selects the same action whenever it encounters a given state and therefore observes rewards for only one action per state. As a result, the agent receives no information about the values of alternative actions in that state, making it impossible to compare actions and improve the policy. This challenge is known as the problem of maintaining exploration and is central to reinforcement learning. As we will see throughout the remainder of this chapter, a common strategy for addressing this issue is to employ policies that ensure every state–action pair is visited with nonzero probability. One way to achieve this is by using stochastic policies that assign positive probability to all actions in each state, thereby guaranteeing sufficient exploration of the environment.

Temporal-difference (TD) learning is widely considered one of the most influential concepts in reinforcement learning. At a high level, temporal-difference learning combines elements of both Monte Carlo methods and dynamic programming. Like dynamic programming methods, temporal-difference learning updates value estimates using other learned estimates rather than waiting for complete returns. This mechanism is known as bootstrapping and allows learning from incomplete sequences of experience^††margin: In other words, without waiting for the end of an episode. At the same time, like Monte Carlo methods, temporal-difference learning learns directly from sampled experience and does not require an explicit model of the environment: a property referred to as sampling. By combining bootstrapping with sampling, temporal-difference learning effectively bridges the gap between Monte Carlo and dynamic programming methods, inheriting many of the advantages of both approaches.

Similar to Monte Carlo methods, temporal-difference methods address the prediction problem by collecting samples from the environment and using them to update value estimates. Recall that in Monte Carlo methods, we must wait until the end of the episode to compute the cumulative reward following time $t$, which we denote as $G_t$, and then use $G_t$ to define the target for the value function update:

where $\leftarrow$ denotes the assignment operator and $\alpha$ is an externally-specified step-size parameter^††margin: In Algorithm 3, we used $\alpha =1/N({𝒙}_t)$ . In contrast, temporal-difference methods update the value function estimate at each time step $t$ based on the observed reward $r_t$ and the estimate of the value function at the next state $V({𝒙}_{t+1})$ by the update:

This update rule is known as the TD($0$) update, where the subscript $0$ indicates that the update relies on a single step of experience^††margin: TD($0$) is a special case of the more general TD($\lambda$) family of methods. . By comparing the Monte Carlo and temporal-difference update rules, we observe that computing the Monte Carlo target $G_t$ requires access to an entire episode, whereas the temporal-difference target $r_t+\gamma V({𝒙}_{t+1})$ can be computed immediately at each time step $t$. We provide a complete algorithm for TD($0$) in Algorithm 4.

It is worth noting that the quantity $r_t+\gamma V({𝒙}_{t+1})-V({𝒙}_t)$ can be interpreted as an error that measures the discrepancy between the current estimate of the value function, $V({𝒙}_t)$, and an improved target estimate, $r_t+\gamma V({𝒙}_{t+1})$^††margin: This target is more informative because it incorporates the realized reward $r_t$ from the transition ${𝒙}_t\to {𝒙}_{t+1}$, together with the current estimate of the value of the successor state. . This quantity, known as the TD error, plays a crucial role in the development of many reinforcement learning algorithms.

We have already discussed how we can use the Monte Carlo and temporal-difference learning paradigms to address the problem of learning without a model of the environment. However, we solely discussed these methods in the context of the prediction problem, where we are trying to estimate the value function of a given policy. In this section, we introduce our first complete example of a reinforcement learning algorithm for learning optimal policies through Monte Carlo methods. Later in this chapter, we introduce various reinforcement learning algorithms that, in one way or another, build upon the principles of model-free control that we discuss here.

The central idea behind using Monte Carlo methods for control mirrors the principles underlying policy iteration, as introduced in Section 18.2. We use the term Generalized Policy Iteration (GPI) to refer to the broad framework encompassing all methods that alternate between policy evaluation and policy improvement. To illustrate this idea, consider a straightforward Monte Carlo extension of the classical policy iteration algorithm. Starting from an arbitrary initial policy ${\pi }_0$, the algorithm alternates between two phases: policy evaluation, in which the value function of the current policy is estimated from sampled experience, and policy improvement, in which the policy is updated based on these value estimates. This process is repeated until convergence.

As discussed in Section 18.3.1, learning action-value functions is often more convenient than learning state-value functions, since action values can be used directly to derive policies. Accordingly, in this example we focus on learning the action-value function. At a high level, the algorithm proceeds by repeatedly alternating between the following steps:

where $\stackrel{\text{E}}{\to }$ denotes policy evaluation, and $\stackrel{\text{I}}{\to }$ denotes policy improvement. In contrast to the Policy Iteration algorithm, we use the Monte Carlo prediction approach from Section 18.3.1 in the policy evaluation step rather than using the exact Bellman equation to update the value function, which would require a model of the environment. The policy improvement step remains the same, where we define the new policy by acting greedily with respect to the current action-value function by choosing ${\pi }_{i+1}(𝒙)={\arg \max }_{𝒖}{Q}^{{\pi }_i}(𝒙,𝒖)$.

While this algorithm captures several core principles underlying many reinforcement learning algorithms, it remains relatively simplistic. As discussed in earlier sections, learning accurate action-value estimates from experience requires the agent to maintain sufficient exploration. More formally, the behavior policy must ensure that every state–action pair is visited with nonzero probability. In the formulation presented above, however, no explicit exploration mechanism is incorporated to guarantee this condition. As a result, the algorithm is only valid under the exploring starts assumption, which posits that each episode begins in every possible state–action pair with nonzero probability. Although useful for theoretical analysis, this assumption is generally unrealistic in practical applications. To obtain a practical and broadly applicable algorithm, this assumption must be relaxed. In the following sections, we introduce several strategies for ensuring adequate exploration, enabling effective learning from experience in realistic settings.

Monte Carlo, temporal-difference, and dynamic programming methods are often presented as distinct approaches to reinforcement learning. However, it is worth noting that these methods are extremes of a spectrum. To appreciate this, we can consider the advantages, disadvantages, and commonalities of each of these paradigms.

Monte Carlo and temporal-difference methods have an advantage over dynamic programming methods in that they do not require an explicit model of the environment and can learn directly from interaction with it—that is, they rely on sampling. This property greatly extends the applicability of these methods to real-world problems, where the environment could be unknown or too complex to model.

Temporal-difference and dynamic programming methods, in turn, offer a key advantage over Monte Carlo methods in that they update value estimates without waiting for an episode to terminate and can therefore learn from incomplete sequences of experience through bootstrapping. This capability is particularly important in practice, as many real-world tasks involve very long or even non-terminating episodes.

On the other hand, Monte Carlo methods also possess an advantage over temporal-difference methods in that they provide unbiased estimates of the true value function. This is because Monte Carlo updates rely on the actual return $G_t$, whereas temporal-difference methods update toward an estimated target, $R({𝒙}_t,{𝒖}_t)+\gamma V({𝒙}_{t+1})$. By doing so, temporal-difference methods deliberately trade some bias—arising from bootstrapped targets—for a reduction in variance, since these targets depend on fewer sources of stochasticity.

These relationships are summarized in Figure 18.2, which organizes reinforcement learning methods along two dimensions: the use of samples and the degree of bootstrapping. At the top right lies exhaustive search, where quantities of interest—such as value functions—are computed exactly through model-based simulation of all possible system evolutions. At the bottom right are dynamic programming methods, which leverage the principle of optimality and a known model to perform one-step lookahead updates via bootstrapping. Moving leftward relaxes the requirement of a model or exhaustive computation, replacing it with learning from sampled experience. At the top left are Monte Carlo methods, which avoid exhaustive search by learning from complete episodes. Finally, at the bottom left are temporal-difference methods, which combine the sampling of Monte Carlo methods with the bootstrapping of dynamic programming, enabling efficient learning from incomplete sequences of experience.

Another crucial distinction among reinforcement learning algorithms is between on-policy and off-policy learning. On-policy methods aim to evaluate or improve the policy that is used to interact with the environment. Off-policy methods, on the other hand, evaluate or improve a policy that is different from the one used to interact with the environment. For example, the Monte Carlo control algorithm we presented in Section 18.3.3 is an on-policy method, as it attempts to improve the same policy used to make decisions in the environment. Off-policy methods define two distinct policies: one that must be updated and ideally becomes the optimal policy and one used to interact with the environment. We refer to the policy being learned as the target policy, while we refer to the policy used to generate samples from the environment as the behavior policy.

In general, on-policy methods are simpler to implement and tend to be more reliable than off-policy methods. Off-policy approaches, on the other hand, are typically more complex and require additional algorithmic considerations, which can make the learning phase less stable and lead to slower convergence in practice. Off-policy learning enables agents to learn from data generated by arbitrary behavior policies, including data collected by human demonstrators or by conventional, non-learning-based controllers. Moreover, off-policy methods make it possible to learn about multiple policies simultaneously, or to learn an optimal policy while continuing to explore the environment.

Throughout the next sections, we introduce various on-policy and off-policy methods for learning and discuss the advantages and disadvantages of each approach.

We begin our discussion on model-free reinforcement learning with value-based methods, which, similarly to the Monte Carlo control algorithm presented in Section 18.3.3, estimate the value function of a policy and use this estimate to derive the optimal policy.

We now continue our discussion of model-free reinforcement learning by turning to policy optimization (PO) methods. In contrast to value-based approaches, policy optimization methods adopt a fundamentally different strategy for solving the reinforcement learning problem by directly optimizing the policy itself. To better motivate policy optimization, let us recall the reinforcement learning objective from Section 18.1:

Rather than learning a value function and deriving a policy from it, as in value-based methods, policy optimization methods define a parametric policy, ${\pi }_{𝜽}$, and directly optimize the parameters $𝜽$ to maximize the reinforcement learning objective $V^{\pi }$. Formally, the goal of policy optimization is to find the optimal policy parameters:

where, for simplicity, we use $V(𝜽)$ to refer to the reinforcement learning objective, $V^{{\pi }_{𝜽}}$, under policy ${\pi }_{𝜽}$ with parameters $𝜽$.

Policy optimization methods typically address this problem in two stages. First, they estimate the gradient of the objective with respect to the policy parameters, ${\nabla }_{𝜽}V(𝜽)$. Then, they update the parameters by performing (approximate) gradient ascent:

where $\alpha$ is a user-defined learning rate.

The first challenge that all policy optimization methods face is estimating the gradient of the reinforcement learning objective. To simplify the notation, we define the cumulative reward as $R(\tau )={\sum }_{t=0}^{T-1}{\gamma }^t{r}_t$ and assume $\gamma =1$^††margin: The extension to the discounted case is equivalent and relatively straightforward. . By definition of expectation, we have:

where $p_{𝜽}(\tau )$ denotes the trajectory distribution induced by the policy ${\pi }_{𝜽}$. Equation 18.26 allows us to write the gradient of the reinforcement learning objective as:

However, we cannot compute this gradient directly because it depends on unknown dynamics through the trajectory distribution, $p_{𝜽}(\tau )$^††margin: Recall that we do not assume access to the system dynamics and thus cannot compute $p_{𝜽}(\tau )$ explicitly. .

To address this issue, we resort to the following useful identity:

and use it to rewrite the gradient of the reinforcement learning objective in Equation 18.27 as:

We can then approximate the expectation using Monte Carlo methods by sampling from the trajectory distribution, $p_{𝜽}(\tau )$, through interaction with the environment. However, the gradient of the log-probability, ${\nabla }_{𝜽}\log p_{𝜽}(\tau )$, remains intractable to compute directly. To address this, let us recall the definition of the trajectory distribution, $p_{𝜽}(\tau )$:

where taking the logarithm yields:

By substituting Equation 18.30 into the gradient of the reinforcement learning objective, we obtain:

Notably, the terms $\log p({𝒙}_0)$ and $\log p({𝒙}_{t+1}\mid {𝒙}_t,{𝒖}_t)$ do not depend on $𝜽$, and thus can be ignored when computing the gradient of the reinforcement learning objective. Moreover, evaluating the gradient of the log-probability of the action, $\log {\pi }_{𝜽}({𝒖}_t\mid {𝒙}_t)$, is tractable and we can easily compute it, for example by using automatic differentiation tools.

This leads to the following expression for the gradient of the reinforcement learning objective:

which is tractable to compute and which we can estimate using samples from the environment. For example, given $N$ episodes of interaction with the environment, we can estimate the gradient of the reinforcement learning objective as:

This is a crucial result and lays the foundations for almost all policy optimization algorithms in reinforcement learning.

Despite their successes, model-free reinforcement learning methods face several important challenges. A primary limitation is sample efficiency. Model-free algorithms often require a large number of interactions with the environment to learn an effective policy, which can be prohibitively expensive or impractical in many real-world settings, particularly in robotics. A second limitation is that, in their standard formulation, model-free methods are inherently single-task learners. Given a fixed reward function defining a specific task, these methods learn a policy optimized exclusively for that task, making it difficult to reuse knowledge or transfer learned behaviors across tasks. Finally, many real-world applications provide reward signals that are sparse, delayed, or noisy. Such reward structures significantly represent a challenge to the learning process, as useful feedback may be infrequent or difficult to attribute to specific actions. As a result, model-free methods can struggle to discover effective policies in these environments.

If we had access to a model of the dynamics, $p({𝒙}_{t+1}\mid {𝒙}_t,{𝒖}_t)$, we could directly leverage tools from model-based optimal control to compute an optimal action sequence or policy. Motivated by this observation, the central idea behind model-based planning methods is to learn an approximate model of the environment dynamics from data, and then use this learned model to plan.

A generic model-based planning procedure can be summarized as follows:

1. 1.

   Run a base policy, ${\pi }_0$, in the environment and collect a dataset of transitions, $𝒟=\{({𝒙}_t,{𝒖}_t,r_t,{𝒙}_{t+1})\}$.

2. 2.

   Fit a dynamics model, $p_{𝜽}({𝒙}_t,{𝒖}_t)$, to the observed data to minimize the prediction error, for example by minimizing the mean squared error between the predicted and true next state:

   $$\underset{[}{\text{minimize}}𝜽]\sum {}_{({𝒙}_t,{𝒖}_t,r_t,{𝒙}_{t+1})\in 𝒟}\parallel p{}_{𝜽}({𝒙}_t,{𝒖}_t)-𝒙{}_{t+1}\parallel {}^2.$$

3. 3.

   Use the learned dynamics model to plan a sequence of actions for the agent to execute.

Despite its simplicity, this scheme works for relatively well-behaved systems, where the dataset $𝒟$ guarantees sufficient coverage of the state-action space, and where the learned model $p_{𝜽}$ is accurate enough to enable effective planning^††margin: This scheme is essentially equivalent to a task known as system identification. . However, in practice, learning an accurate model of the dynamics is often challenging, especially when dealing with high-dimensional, non-linear, and stochastic systems. Most importantly, inaccuracies in the learned model are particularly problematic when used within an optimization process. Optimization algorithms will naturally exploit inaccuracies in the model that have high predicted performance, but may not correspond to high realized performance.

A popular approach to address this issue is to consider a measure of uncertainty in the model’s predictions, and to use this uncertainty to inform the planning process. While there are many ways to quantify uncertainty, we consider methods that aim to learn a posterior distribution over the model parameters. In these methods, rather than learning a single estimate of the model parameters $𝜽$ through standard maximum likelihood estimation: