From Wikipedia, the free encyclopedia
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.
Reinforcement learning is one of three basic machine learning
paradigms, alongside supervised learning and unsupervised learning.
Reinforcement learning differs from supervised learning in not
needing labelled input/output pairs be presented, and in not needing
sub-optimal actions to be explicitly corrected. Instead the focus is on
finding a balance between exploration (of uncharted territory) and
exploitation (of current knowledge). Partially supervised RL algorithms can combine the advantages of supervised and RL algorithms.
The environment is typically stated in the form of a Markov decision process (MDP), because many reinforcement learning algorithms for this context use dynamic programming techniques.
The main difference between the classical dynamic programming methods
and reinforcement learning algorithms is that the latter do not assume
knowledge of an exact mathematical model of the MDP and they target
large MDPs where exact methods become infeasible.
Introduction
The
typical framing of a Reinforcement Learning (RL) scenario: an agent
takes actions in an environment, which is interpreted into a reward and a
representation of the state, which are fed back into the agent.
Due to its generality, reinforcement learning is studied in many disciplines, such as game theory, control theory, operations research, information theory, simulation-based optimization, multi-agent systems, swarm intelligence, and statistics. In the operations research and control literature, reinforcement learning is called approximate dynamic programming, or neuro-dynamic programming. The problems of interest in reinforcement learning have also been studied in the theory of optimal control,
which is concerned mostly with the existence and characterization of
optimal solutions, and algorithms for their exact computation, and less
with learning or approximation, particularly in the absence of a
mathematical model of the environment. In economics and game theory, reinforcement learning may be used to explain how equilibrium may arise under bounded rationality.
Basic reinforcement learning is modeled as a Markov decision process (MDP):
- a set of environment and agent states, S;
- a set of actions, A, of the agent;
is the probability of transition (at time 
) from state 
to state 
under action 
.
is the immediate reward after transition from to with action .
The purpose of reinforcement learning is for the agent to learn an
optimal, or nearly-optimal, policy that maximizes the "reward function"
or other user-provided reinforcement signal that accumulates from the
immediate rewards. This is similar to processes that appear to occur in
animal psychology. For example, biological brains are hardwired to
interpret signals such as pain and hunger as negative reinforcements,
and interpret pleasure and food intake as positive reinforcements. In
some circumstances, animals can learn to engage in behaviors that
optimize these rewards. This suggests that animals are capable of
reinforcement learning.
A basic reinforcement learning agent AI interacts with its environment in discrete time steps. At each time t, the agent receives the current state 
and reward 
. It then chooses an action 
from the set of available actions, which is subsequently sent to the environment. The environment moves to a new state 
and the reward 
associated with the transition 
is determined. The goal of a reinforcement learning agent is to learn a policy: ![{\displaystyle \pi :A\times S\rightarrow [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53cdefaaea162af26e217b740b90f8f8c692a641)
, 
which maximizes the expected cumulative reward.
Formulating the problem as an MDP assumes the agent directly
observes the current environmental state; in this case the problem is
said to have full observability. If the agent only has access to a
subset of states, or if the observed states are corrupted by noise, the
agent is said to have partial observability, and formally the problem must be formulated as a Partially observable Markov decision process.
In both cases, the set of actions available to the agent can be
restricted. For example, the state of an account balance could be
restricted to be positive; if the current value of the state is 3 and
the state transition attempts to reduce the value by 4, the transition
will not be allowed.
When the agent's performance is compared to that of an agent that
acts optimally, the difference in performance gives rise to the notion
of regret.
In order to act near optimally, the agent must reason about the
long-term consequences of its actions (i.e., maximize future income),
although the immediate reward associated with this might be negative.
Thus, reinforcement learning is particularly well-suited to
problems that include a long-term versus short-term reward trade-off. It
has been applied successfully to various problems, including robot control, elevator scheduling, telecommunications, backgammon, checkers and Go (AlphaGo).
Two elements make reinforcement learning powerful: the use of
samples to optimize performance and the use of function approximation to
deal with large environments. Thanks to these two key components,
reinforcement learning can be used in large environments in the
following situations:
- A model of the environment is known, but an analytic solution is not available;
- Only a simulation model of the environment is given (the subject of simulation-based optimization);
- The only way to collect information about the environment is to interact with it.
The first two of these problems could be considered planning problems
(since some form of model is available), while the last one could be
considered to be a genuine learning problem. However, reinforcement
learning converts both planning problems to machine learning problems.
Exploration
The exploration vs. exploitation trade-off has been most thoroughly studied through the multi-armed bandit problem and for finite state space MDPs in Burnetas and Katehakis (1997).
Reinforcement learning requires clever exploration mechanisms;
randomly selecting actions, without reference to an estimated
probability distribution, shows poor performance. The case of (small)
finite MDPs is relatively well understood. However, due to the lack of
algorithms that scale well with the number of states (or scale to
problems with infinite state spaces), simple exploration methods are the
most practical.
One such method is 
-greedy, where 
is a parameter controlling the amount of exploration vs. exploitation. With probability 
,
exploitation is chosen, and the agent chooses the action that it
believes has the best long-term effect (ties between actions are broken
uniformly at random). Alternatively, with probability , exploration is chosen, and the action is chosen uniformly at random.
is usually a fixed parameter but can be adjusted either according to a
schedule (making the agent explore progressively less), or adaptively
based on heuristics.
Algorithms for control learning
Even
if the issue of exploration is disregarded and even if the state was
observable (assumed hereafter), the problem remains to use past
experience to find out which actions lead to higher cumulative rewards.
Criterion of optimality
Policy
The agent's action selection is modeled as a map called policy:
The policy map gives the probability of taking action when in state . There are also deterministic policies.
State-value function
The value function 
is defined as the expected return starting with state , i.e. 
, and successively following policy 
. Hence, roughly speaking, the value function estimates "how good" it is to be in a given state.
![{\displaystyle V_{\pi }(s)=\operatorname {E} [R\mid s_{0}=s]=\operatorname {E} \left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\mid s_{0}=s\right],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42cacec1da9e5861cc7538e33cd239dc76136dbf)
where the random variable 
denotes the return, and is defined as the sum of future discounted rewards:
where is the reward at step , 
is the discount-rate. Gamma is less than 1, so events in the distant future are weighted less than events in the immediate future.
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.
Brute force
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 the 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
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 Markov decision processes,
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 by
![{\displaystyle V^{\pi }(s)=E[R\mid s,\pi ],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8ff1cf02d3c0c16f1d0da9a204cf9e4d955c48c)
where stands for the return associated with following from the initial state . Defining 
as the maximum possible value of 
, where is allowed to change,
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 
, since ![\rho ^{\pi }=E[V^{\pi }(S)]](https://wikimedia.org/api/rest_v1/media/math/render/svg/607d2a3c3a3f369d464fb3fd4beb5c7a108ad690)
, where 
is a state randomly sampled from the distribution 
of initial states (so 
).
Although state-values suffice to define optimality, it is useful to define action-values. Given a state , an action and a policy , the action-value of the pair 
under is defined by
![{\displaystyle Q^{\pi }(s,a)=\operatorname {E} [R\mid s,a,\pi ],\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/589b970c42fc5cd7b8a1c4859046d18e97046090)
where now stands for the random return associated with first taking action in state and following , thereafter.
The theory of MDPs states that if 
is an optimal policy, we act optimally (take the optimal action) by choosing the action from 
with the highest value at each state, . The action-value function of such an optimal policy (
) is called the optimal action-value function and is commonly denoted by 
. 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 
(
) that converge to .
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
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 , the goal is to compute the function values 
(or a good approximation to them) for all state-action pairs .
Assume (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 can be computed by averaging the sampled returns that originated from over time. Given sufficient time, this procedure can thus construct a precise estimate 
of the action-value function 
. 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 : Given a state , this new policy returns an action that maximizes 
. In practice lazy evaluation can defer the computation of the maximizing actions to when they are needed.
Problems with this procedure include:
1. The procedure may spend too much time evaluating a suboptimal policy.
2. It uses samples inefficiently in that a long trajectory improves the estimate only of the single state-action pair that started the trajectory.
3. When the returns along the trajectories have high variance, convergence is slow.
4. It works in episodic problems only.
5. It works in small, finite MDPs only.
Temporal difference methods
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.
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,
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.
Another problem specific to TD comes from their reliance on the recursive Bellman equation. Most TD methods have a so-called 
parameter 
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.
Function approximation methods
In order to address the fifth issue, function approximation methods are used. Linear function approximation starts with a mapping 
that assigns a finite-dimensional vector to each state-action pair. Then, the action values of a state-action pair are obtained by linearly combining the components of 
with some weights 
:
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.
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.
Direct policy search
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 , let 
denote the policy associated to . Defining the performance function by
under mild conditions this function will be differentiable as a function of the parameter vector . If the gradient of 
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 (which is known as the likelihood ratio method in the simulation-based optimization literature). Policy search methods have been used in the robotics context. 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.
Model-based algorithms
Finally, all of the above methods can be combined with algorithms that first learn a model. For instance, the Dyna algorithm
learns a model from experience, and uses that to provide more modelled
transitions for a value function, in addition to the real transitions.
Such methods can sometimes be extended to use of non-parametric models,
such as when the transitions are simply stored and 'replayed' to the learning algorithm.
There are other ways to use models than to update a value function. For instance, in model predictive control the model is used to update the behavior directly.
Theory
Both the
asymptotic and finite-sample behaviors of most algorithms are well
understood. Algorithms with provably good online performance (addressing
the exploration issue) are known.
Efficient exploration of MDPs is given in Burnetas and Katehakis (1997).
Finite-time performance bounds have also appeared for many algorithms,
but these bounds are expected to be rather loose and thus more work is
needed to better understand the relative advantages and limitations.
For incremental algorithms, asymptotic convergence issues have been settled.
Temporal-difference-based algorithms converge under a wider set of
conditions than was previously possible (for example, when used with
arbitrary, smooth function approximation).
Research
Research topics include
- adaptive methods that work with fewer (or no) parameters under a large number of conditions
- addressing the exploration problem in large MDPs
- combinations with logic-based frameworks
- large-scale empirical evaluations
- learning and acting under partial information (e.g., using predictive state representation)
- modular and hierarchical reinforcement learning
- improving existing value-function and policy search methods
- algorithms that work well with large (or continuous) action spaces
- transfer learning
- lifelong learning
- efficient sample-based planning (e.g., based on Monte Carlo tree search).
- bug detection in software projects
- Intrinsic motivation
which differentiates information-seeking, curiosity-type behaviours
from task-dependent goal-directed behaviours (typically) by introducing a
reward function based on maximising novel information
- Multiagent or distributed reinforcement learning is a topic of interest. Applications are expanding.
- Actor-critic reinforcement learning
- Reinforcement learning algorithms such as TD learning are under investigation as a model for dopamine-based learning in the brain. In this model, the dopaminergic projections from the substantia nigra to the basal ganglia function as the prediction error.
- Reinforcement learning has been used as a part of the model for
human skill learning, especially in relation to the interaction between
implicit and explicit learning in skill acquisition (the first
publication on this application was in 1995–1996).
- Occupant-centric control
- Algorithmic trading and optimal execution
- Optimization of computing resources
Comparison of reinforcement learning algorithms
| Monte Carlo |
Every visit to Monte Carlo |
Either |
Discrete |
Discrete |
Sample-means
|
| Q-learning |
State–action–reward–state |
Off-policy |
Discrete |
Discrete |
Q-value
|
| SARSA |
State–action–reward–state–action |
On-policy |
Discrete |
Discrete |
Q-value
|
| Q-learning - Lambda |
State–action–reward–state with eligibility traces |
Off-policy |
Discrete |
Discrete |
Q-value
|
| SARSA - Lambda |
State–action–reward–state–action with eligibility traces |
On-policy |
Discrete |
Discrete |
Q-value
|
| DQN |
Deep Q Network |
Off-policy |
Discrete |
Continuous |
Q-value
|
| DDPG |
Deep Deterministic Policy Gradient |
Off-policy |
Continuous |
Continuous |
Q-value
|
| A3C |
Asynchronous Advantage Actor-Critic Algorithm |
On-policy |
Continuous |
Continuous |
Advantage
|
| NAF |
Q-Learning with Normalized Advantage Functions |
Off-policy |
Continuous |
Continuous |
Advantage
|
| TRPO |
Trust Region Policy Optimization |
On-policy |
Continuous |
Continuous |
Advantage
|
| PPO |
Proximal Policy Optimization |
On-policy |
Continuous |
Continuous |
Advantage
|
| TD3
|
Twin Delayed Deep Deterministic Policy Gradient
|
Off-policy
|
Continuous
|
Continuous
|
Q-value
|
| SAC
|
Soft Actor-Critic
|
Off-policy
|
Continuous
|
Continuous
|
Advantage
|
Associative reinforcement learning
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.
Deep reinforcement learning
This approach extends reinforcement learning by using a deep neural network and without explicitly designing the state space. The work on learning ATARI games by Google DeepMind increased attention to deep reinforcement learning or end-to-end reinforcement learning.
Adversarial deep reinforcement learning
Adversarial
deep reinforcement learning is an active area of research in
reinforcement learning focusing on vulnerabilities of learned policies.
In this research area some studies initially showed that reinforcement
learning policies are susceptible to imperceptible adversarial
manipulations. While some methods have been proposed to overcome these
susceptibilities, in the most recent studies it has been shown that
these proposed solutions are far from providing an accurate
representation of current vulnerabilities of deep reinforcement learning
policies.
Fuzzy reinforcement learning
By introducing fuzzy inference in RL, approximating the state-action value function with fuzzy rules
in continuous space becomes possible. The IF - THEN form of fuzzy rules
make this approach suitable for expressing the results in a form close
to natural language. Extending FRL with Fuzzy Rule Interpolation allows the use of reduced size sparse fuzzy rule-bases to emphasize cardinal rules (most important state-action values).
Inverse reinforcement learning
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.
Safe reinforcement learning
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.
Partially supervised reinforcement learning (PSRL)
In
PSRL algorithms the advantages of supervised and RL based approaches
are synergistically combined. For example the control policy learnt by
an inverse ANN based approach to control a nonlinear system can be
refined using RL thereby avoiding the computational cost incurred by
starting from a random policy in traditional RL. Partially supervised
approaches can alleviate the need for extensive training data in
supervised learning while reducing the need for costly exhaustive random
exploration in pure RL.
