Reinforcement learning

The agent's action selection is modeled as a map called policy:

${\displaystyle \pi :A\times S\rightarrow [0,1]}$

${\displaystyle \pi (a,s)=\Pr(a_{t}=a\mid s_{t}=s)}$

The policy map gives the probability of taking action ${\displaystyle a}$ when in state ${\displaystyle s}$.[8]^:61 There are also non-probabilistic policies.

Value function ${\displaystyle V_{\pi }(s)}$ is defined as the expected return starting with state ${\displaystyle s}$, i.e. ${\displaystyle s_{0}=s}$, and successively following policy ${\displaystyle \pi }$. Hence, roughly speaking, the value function estimates "how good" it is to be in a given state.[8]^:60

${\displaystyle V_{\pi }(s)=\operatorname {E} [R]=\operatorname {E} \left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\mid s_{0}=s\right],}$

where the random variable ${\displaystyle R}$ denotes the return, and is defined as the sum of future discounted rewards (gamma is less than 1, as a particular state becomes older, its effect on the later states becomes less and less. Thus, we discount its effect).

${\displaystyle R=\sum _{t=0}^{\infty }\gamma ^{t}r_{t},}$

where ${\displaystyle r_{t}}$ is the reward at step ${\displaystyle t}$, ${\displaystyle \gamma \in [0,1)}$ is the discount-rate.

The algorithm must find a policy with maximum expected return. From the theory of MDPs it is known that, without loss of generality, the search can be restricted to the set of so-called stationary policies. A policy is stationary if the action-distribution returned by it depends only on the last state visited (from the observation agent's history). The search can be further restricted to deterministic stationary policies. A deterministic stationary policy deterministically selects actions based on the current state. Since any such policy can be identified with a mapping from the set of states to the set of actions, these policies can be identified with such mappings with no loss of generality.

The brute force approach entails two steps:

• For each possible policy, sample returns while following it
• Choose the policy with the largest expected return

One problem with this is that the number of policies can be large, or even infinite. Another is that variance of the returns may be large, which requires many samples to accurately estimate the return of each policy.

These problems can be ameliorated if we assume some structure and allow samples generated from one policy to influence the estimates made for others. The two main approaches for achieving this are value function estimation and direct policy search.

Value function approaches attempt to find a policy that maximizes the return by maintaining a set of estimates of expected returns for some policy (usually either the "current" [on-policy] or the optimal [off-policy] one).

These methods rely on the theory of MDPs, where optimality is defined in a sense that is stronger than the above one: A policy is called optimal if it achieves the best expected return from any initial state (i.e., initial distributions play no role in this definition). Again, an optimal policy can always be found amongst stationary policies.

To define optimality in a formal manner, define the value of a policy ${\displaystyle \pi }$ by

${\displaystyle V^{\pi }(s)=E[R\mid s,\pi ],}$

where ${\displaystyle R}$ stands for the return associated with following ${\displaystyle \pi }$ from the initial state ${\displaystyle s}$. Defining ${\displaystyle V^{*}(s)}$ as the maximum possible value of ${\displaystyle V^{\pi }(s)}$, where ${\displaystyle \pi }$ is allowed to change,

${\displaystyle V^{*}(s)=\max _{\pi }V^{\pi }(s).}$

A policy that achieves these optimal values in each state is called optimal. Clearly, a policy that is optimal in this strong sense is also optimal in the sense that it maximizes the expected return ${\displaystyle \rho ^{\pi }}$, since ${\displaystyle \rho ^{\pi }=E[V^{\pi }(S)]}$, where ${\displaystyle S}$ is a state randomly sampled from the distribution ${\displaystyle \mu }$.

Although state-values suffice to define optimality, it is useful to define action-values. Given a state ${\displaystyle s}$, an action ${\displaystyle a}$ and a policy ${\displaystyle \pi }$, the action-value of the pair ${\displaystyle (s,a)}$ under ${\displaystyle \pi }$ is defined by

${\displaystyle Q^{\pi }(s,a)=\operatorname {E} [R\mid s,a,\pi ],\,}$

where ${\displaystyle R}$ now stands for the random return associated with first taking action ${\displaystyle a}$ in state ${\displaystyle s}$ and following ${\displaystyle \pi }$, thereafter.

The theory of MDPs states that if ${\displaystyle \pi ^{*}}$ is an optimal policy, we act optimally (take the optimal action) by choosing the action from ${\displaystyle Q^{\pi ^{*}}(s,\cdot )}$ with the highest value at each state, ${\displaystyle s}$. The action-value function of such an optimal policy (${\displaystyle Q^{\pi ^{*}}}$) is called the optimal action-value function and is commonly denoted by ${\displaystyle Q^{*}}$. In summary, the knowledge of the optimal action-value function alone suffices to know how to act optimally.

Assuming full knowledge of the MDP, the two basic approaches to compute the optimal action-value function are value iteration and policy iteration. Both algorithms compute a sequence of functions ${\displaystyle Q_{k}}$ (${\displaystyle k=0,1,2,\ldots }$) that converge to ${\displaystyle Q^{*}}$. Computing these functions involves computing expectations over the whole state-space, which is impractical for all but the smallest (finite) MDPs. In reinforcement learning methods, expectations are approximated by averaging over samples and using function approximation techniques to cope with the need to represent value functions over large state-action spaces.

Monte Carlo methods can be used in an algorithm that mimics policy iteration. Policy iteration consists of two steps: policy evaluation and policy improvement.

Monte Carlo is used in the policy evaluation step. In this step, given a stationary, deterministic policy ${\displaystyle \pi }$, the goal is to compute the function values ${\displaystyle Q^{\pi }(s,a)}$ (or a good approximation to them) for all state-action pairs ${\displaystyle (s,a)}$. Assuming (for simplicity) that the MDP is finite, that sufficient memory is available to accommodate the action-values and that the problem is episodic and after each episode a new one starts from some random initial state. Then, the estimate of the value of a given state-action pair ${\displaystyle (s,a)}$ can be computed by averaging the sampled returns that originated from ${\displaystyle (s,a)}$ over time. Given sufficient time, this procedure can thus construct a precise estimate ${\displaystyle Q}$ of the action-value function ${\displaystyle Q^{\pi }}$. This finishes the description of the policy evaluation step.

In the policy improvement step, the next policy is obtained by computing a greedy policy with respect to ${\displaystyle Q}$: Given a state ${\displaystyle s}$, this new policy returns an action that maximizes ${\displaystyle Q(s,\cdot )}$. In practice lazy evaluation can defer the computation of the maximizing actions to when they are needed.

Problems with this procedure include:

• The procedure may spend too much time evaluating a suboptimal policy.
• It uses samples inefficiently in that a long trajectory improves the estimate only of the single state-action pair that started the trajectory.
• When the returns along the trajectories have high variance, convergence is slow.
• It works in episodic problems only;
• It works in small, finite MDPs only.

The first problem is corrected by allowing the procedure to change the policy (at some or all states) before the values settle. This too may be problematic as it might prevent convergence. Most current algorithms do this, giving rise to the class of generalized policy iteration algorithms. Many actor critic methods belong to this category.

The second issue can be corrected by allowing trajectories to contribute to any state-action pair in them. This may also help to some extent with the third problem, although a better solution when returns have high variance is Sutton's temporal difference (TD) methods that are based on the recursive Bellman equation.[9][10] The computation in TD methods can be incremental (when after each transition the memory is changed and the transition is thrown away), or batch (when the transitions are batched and the estimates are computed once based on the batch). Batch methods, such as the least-squares temporal difference method,[11] may use the information in the samples better, while incremental methods are the only choice when batch methods are infeasible due to their high computational or memory complexity. Some methods try to combine the two approaches. Methods based on temporal differences also overcome the fourth issue.

In order to address the fifth issue, function approximation methods are used. Linear function approximation starts with a mapping ${\displaystyle \phi }$ that assigns a finite-dimensional vector to each state-action pair. Then, the action values of a state-action pair ${\displaystyle (s,a)}$ are obtained by linearly combining the components of ${\displaystyle \phi (s,a)}$ with some weights ${\displaystyle \theta }$:

${\displaystyle Q(s,a)=\sum _{i=1}^{d}\theta _{i}\phi _{i}(s,a).}$

The algorithms then adjust the weights, instead of adjusting the values associated with the individual state-action pairs. Methods based on ideas from nonparametric statistics (which can be seen to construct their own features) have been explored.

Value iteration can also be used as a starting point, giving rise to the Q-learning algorithm and its many variants.[12]

The problem with using action-values is that they may need highly precise estimates of the competing action values that can be hard to obtain when the returns are noisy, though this problem is mitigated to some extent by temporal difference methods. Using the so-called compatible function approximation method compromises generality and efficiency. Another problem specific to TD comes from their reliance on the recursive Bellman equation. Most TD methods have a so-called ${\displaystyle \lambda }$ parameter ${\displaystyle (0\leq \lambda \leq 1)}$ that can continuously interpolate between Monte Carlo methods that do not rely on the Bellman equations and the basic TD methods that rely entirely on the Bellman equations. This can be effective in palliating this issue.

An alternative method is to search directly in (some subset of) the policy space, in which case the problem becomes a case of stochastic optimization. The two approaches available are gradient-based and gradient-free methods.

Gradient-based methods (policy gradient methods) start with a mapping from a finite-dimensional (parameter) space to the space of policies: given the parameter vector ${\displaystyle \theta }$, let ${\displaystyle \pi _{\theta }}$ denote the policy associated to ${\displaystyle \theta }$. Defining the performance function by

${\displaystyle \rho (\theta )=\rho ^{\pi _{\theta }},}$

under mild conditions this function will be differentiable as a function of the parameter vector ${\displaystyle \theta }$. If the gradient of ${\displaystyle \rho }$ was known, one could use gradient ascent. Since an analytic expression for the gradient is not available, only a noisy estimate is available. Such an estimate can be constructed in many ways, giving rise to algorithms such as Williams' REINFORCE method[13] (which is known as the likelihood ratio method in the simulation-based optimization literature).[14] Policy search methods have been used in the robotics context.[15] Many policy search methods may get stuck in local optima (as they are based on local search).

A large class of methods avoids relying on gradient information. These include simulated annealing, cross-entropy search or methods of evolutionary computation. Many gradient-free methods can achieve (in theory and in the limit) a global optimum.

Policy search methods may converge slowly given noisy data. For example, this happens in episodic problems when the trajectories are long and the variance of the returns is large. Value-function based methods that rely on temporal differences might help in this case. In recent years, actor–critic methods have been proposed and performed well on various problems.[16]

Associative reinforcement learning tasks combine facets of stochastic learning automata tasks and supervised learning pattern classification tasks. In associative reinforcement learning tasks, the learning system interacts in a closed loop with its environment.[28]

This approach extends reinforcement learning by using a deep neural network and without explicitly designing the state space.[29] The work on learning ATARI games by Google DeepMind increased attention to deep reinforcement learning or end-to-end reinforcement learning.[30]

In inverse reinforcement learning (IRL), no reward function is given. Instead, the reward function is inferred given an observed behavior from an expert. The idea is to mimic observed behavior, which is often optimal or close to optimal.[31]

Safe Reinforcement Learning (SRL) can be defined as the process of learning policies that maximize the expectation of the return in problems in which it is important to ensure reasonable system performance and/or respect safety constraints during the learning and/or deployment processes.[32]