Reinforcement learning

Uses your system voice; voice and rate in settings.

Snapshot

≈ 12 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In machine learning and optimal control, reinforcement learning (RL) (also known as approximate dynamic programming) is concerned with how an intelligent agent should take actions in a dynamic environment in order to maximize a reward signal. Reinforcement learning is one of the three basic machine learning paradigms, alongside supervised learning and unsupervised learning. While supervised learning and unsupervised learning algorithms respectively attempt to discover patterns in labeled and unlabeled data, reinforcement learning involves training an agent through interactions with its environment. To learn to maximize rewards from these interactions, the agent makes decisions between trying new actions to learn more about the environment (exploration), or using current knowledge of the environment to take the best action (exploitation). The search for the optimal balance between these two strategies is known as the exploration–exploitation dilemma. The environment is typically stated in the form of a Markov decision process, as many reinforcement learning algorithms use dynamic programming techniques.…

In machine learning and optimal control, reinforcement learning (RL) (also known as approximate dynamic programming) is concerned with how an intelligent agent should take actions in a dynamic environment in order to maximize a reward signal. Reinforcement learning is one of the three basic machine learning paradigms, alongside supervised learning and unsupervised learning. While supervised learning and unsupervised learning algorithms respectively attempt to discover patterns in labeled and unlabeled data, reinforcement learning involves training an agent through interactions with its environment. To learn to maximize rewards from these interactions, the agent makes decisions between trying new actions to learn more about the environment (exploration), or using current knowledge of the environment to take the best action (exploitation). The search for the optimal balance between these two strategies is known as the exploration–exploitation dilemma. The environment is typically stated in the form of a Markov decision process, as many reinforcement learning algorithms use dynamic programming techniques. The main difference between classical dynamic programming methods and reinforcement learning algorithms is that the latter do not assume knowledge of an exact mathematical model of the Markov decision process, and they target large Markov decision processes where exact methods become infeasible. P_a(s,s') = \Pr(S_{t+1}{=}s' \mid S_t{=}s, A_t{=}a) , the transition probability (at time t ) from state s to state s' under action a . R_a(s,s') , the immediate reward after transitioning from s to s' under action a . The purpose of reinforcement learning is for the agent to learn an optimal (or near-optimal) policy that maximizes the reward function or other user-provided reinforcement signal that accumulates from 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 learn to adopt behaviors that optimize these rewards. This suggests that animals are capable of reinforcement learning. A basic reinforcement learning agent interacts with its environment in discrete time steps. At each time step , the agent receives the current state S_t and reward R_t . It then chooses an action A_t from the set of available actions, which is subsequently sent to the environment. The environment moves to a new state S_{t+1} and the reward R_{t+1} associated with the transition (S_t,A_t,S_{t+1}) is determined. The goal of a reinforcement learning agent is to learn a policy: \begin{align} &\pi: \mathcal{S} \times \mathcal{A} \to [0,1] \\ &\pi(s,a) = \Pr(A_t{=}a \mid S_t{=}s) \end{align} that maximizes the expected cumulative reward. Formulating the problem as a Markov decision process 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 yields the notion of regret. In order to act near optimally, the agent must reason about long-term consequences of its actions (i.e., maximize future rewards), 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 energy storage, robot control, photovoltaic generators, backgammon, checkers, Go (AlphaGo), and autonomous driving systems. 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, RL 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. \begin{align} &\pi: \mathcal{A} \times \mathcal{S} \to [0,1] \\ &\pi(a,s) = \Pr(A_t{=}a \mid S_t{=}s) \end{align} The policy map gives the probability of taking action a when in state s . There are also deterministic policies \pi for which \pi(s) denotes the action that should be played at state s . The state-value function V_\pi(s) is defined as, expected discounted return starting with state s , i.e. S_0 = s , and successively following policy \pi . Hence, roughly speaking, the value function estimates "how good" it is to be in a given state. V_\pi(s) = \operatorname \mathbb{E}[G\mid S_0{=}s] = \operatorname \mathbb{E}\left[\sum_{t=0}^\infty \gamma^t R_{t+1} \mid S_0{=}s\right], where the random variable G denotes the discounted return, and is defined as the sum of future discounted rewards: G = \sum_{t=0}^\infty \gamma^t R_{t+1}=R_1 + \gamma R_2 + \gamma^2 R_3 + \cdots, where R_{t+1} is the reward for transitioning from state S_t to 0 \le \gamma is the discount rate. \gamma is less than 1, so rewards in the distant future are weighted less than rewards in the immediate future. The goal is to find a policy that maximizes the expected discounted return. From the theory of Markov decision processes 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. V^{\pi} (s) = \operatorname \mathbb{E}[G\mid s,\pi], where G stands for the discounted return associated with following \pi from the initial state s . Defining V^*(s) as the maximum possible state-value of V^\pi(s) , where \pi is allowed to change, V^*(s) = \max_\pi V^\pi(s). A policy that achieves these optimal state-values in each state is called optimal. Clearly, a policy that is optimal in this sense is also optimal in the sense that it maximizes the expected discounted return, since V^*(s) = \max_\pi \mathbb{E}[G\mid s,\pi] , where s is a state randomly sampled from the distribution \mu of initial states (so Although state-values suffice to define optimality, it is useful to define action-values. Given a state s , an action a and a policy \pi , the action-value of the pair (s,a) under \pi is defined by Q^\pi(s,a) = \operatorname \mathbb{E}[G\mid s,a,\pi], where G now stands for the random discounted return associated with first taking action a in state s and following \pi , thereafter. The theory of Markov decision processes states that if \pi^* is an optimal policy, we act optimally (take the optimal action) by choosing the action from Q^{\pi^*}(s,\cdot) with the highest action-value at each state, s . The action-value function of such an optimal policy ( Q^{\pi^*} ) is called the optimal action-value function and is commonly denoted by Q^* . In summary, the knowledge of the optimal action-value function alone suffices to know how to act optimally. Assuming full knowledge of the Markov decision process, the two basic approaches to compute the optimal action-value function are value iteration and policy iteration. Both algorithms compute a sequence of functions Q_k ( k=0,1,2,\ldots ) that converge to Q^* . Computing these functions involves computing expectations over the whole state-space, which is impractical for all but the smallest (finite) Markov decision processes. 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. 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. Including Deep Q-learning methods when a neural network is used to represent Q, with various applications in stochastic search problems. 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. 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 \theta , let \pi_\theta denote the policy associated to \theta . Defining the performance function by \rho(\theta) = \rho^{\pi_\theta} under mild conditions this function will be differentiable as a function of the parameter vector \theta . If the gradient of \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's REINFORCE method (which is known as the likelihood ratio method in the simulation-based optimization literature). 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. 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). The self-reinforcement algorithm updates a memory matrix W = \|w(a,s)\| such that in each iteration executes the following machine learning routine: In situation s perform action a . Receive a consequence situation s' . Compute state evaluation v(s') of how good it is to be in the consequence situation s' . Update crossbar memory w'(a,s) = w(a,s) + v(s') . Initial conditions of the memory are received as input from the genetic environment. It is a system with only one input (situation), and only one output (action, or behavior). Self-reinforcement (self-learning) was introduced in 1982 along with a neural network capable of self-reinforcement learning, named Crossbar Adaptive Array (CAA). The CAA computes, in a crossbar fashion, both decisions about actions and emotions (feelings) about consequence states. The system is driven by the interaction between cognition and emotion.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373420975 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

36 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.