reinforcement learning for reinforcement learning in psychology see reinforcement and operant conditioning machine learning anddata mining problems classification clustering regression anomaly detection automl association rules reinforcement learning structured prediction feature engineering feature learning online learning semisupervised learning unsupervised learning learning to rank grammar induction supervised learning classification regression decision trees ensembles bagging boosting random forest knn linear regression naive bayes artificial neural networks logistic regression perceptron relevance vector machine rvm support vector machine svm clustering birch cure hierarchical kmeans expectationmaximization em dbscan optics meanshift dimensionality reduction factor analysis cca ica lda nmf pca tsne structured prediction graphical models bayes net conditional random field hidden markov anomaly detection knn local outlier factor artificial neural networks autoencoder deep learning multilayer perceptron rnn lstm gru restricted boltzmann machine som convolutional neural network unet reinforcement learning qlearning sarsa temporal difference td theory biasvariance dilemma computational learning theory empirical risk minimization occam learning pac learning statistical learning vc theory machinelearning venues nips icml ml jmlr arxivcslg glossary of artificial intelligence glossary of artificial intelligence related articles list of datasets for machinelearning research outline of machine learning machine learning portalvte reinforcement learning rl is an area of machine learning concerned with how software agents ought to take actions in an environment so as to maximize some notion of cumulative reward the problem due to its generality is studied in many other disciplines such as game theory control theory operations research information theory simulationbased optimization multiagent systems swarm intelligence statistics and genetic algorithms in the operations research and control literature reinforcement learning is called approximate dynamic programming or neurodynamic 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 in machine learning the environment is typically formulated as a markov decision process mdp as many reinforcement learning algorithms for this context utilize dynamic programming techniques reinforcement learning differs from standard supervised learning in that correct inputoutput pairs 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 basic reinforcement is modeled as a markov decision process a set of environment and agent states s a set of actions a of the agent p a s s p r s t 1 s s t s a t a displaystyle passprst1sstsata is the probability of transition from state s displaystyle s to state s displaystyle s under action a displaystyle a r a s s displaystyle rass is the immediate reward after transition from s displaystyle s to s displaystyle s with action a displaystyle a rules that describe what the agent observes rules are often stochastic the observation typically involves the scalar immediate reward associated with the last transition in many works the agent is assumed to observe the current environmental state full observability if not the agent has partial observability sometimes the set of actions available to the agent is restricted a zero balance cannot be reduced a reinforcement learning agent interacts with its environment in discrete time steps at each time t the agent receives an observation o t displaystyle ot which typically includes the reward r t displaystyle rt it then chooses an action a t displaystyle at from the set of available actions which is subsequently sent to the environment the environment moves to a new state s t 1 displaystyle st1 and the reward r t 1 displaystyle rt1 associated with the transition s t a t s t 1 displaystyle statst1 is determined the goal of a reinforcement learning agent is to collect as much reward as possible the agent can possibly randomly choose any action as a function of the history when the agents 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 ie maximize future income although the immediate reward associated with this might be negative thus reinforcement learning is particularly wellsuited to problems that include a longterm versus shortterm reward tradeoff 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 simulationbased 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 reinforcement learning requires clever exploration mechanisms randomly selecting actions without reference to an estimated probability distribution shows poor performance the case of small finite markov decision processes is relatively well understood however due to the lack of algorithms that provably 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 displaystyle epsilon greedy when the agent chooses the action that it believes has the best longterm effect with probability 1 displaystyle 1epsilon if no action which satisfies this condition is found the agent chooses an action uniformly at random here 0 1 displaystyle 0epsilon 1 is a tuning parameter which is sometimes changed either according to a fixed 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 are good criterion of optimality policy the agents action selection is modeled as a map called policy s a 0 1 displaystyle pi stimes arightarrow a s p a t a s t s displaystyle pi aspatasts the policy map gives the probability of taking action a displaystyle a when in state s displaystyle s 61 there are also nonprobabilistic policies statevalue function value function v s displaystyle vpi s is defined as the expected return starting with state s displaystyle s ie s 0 s displaystyle s0s and successively following policy displaystyle pi hence roughly speaking the value function estimates how good it is to be in a given state60 v s e r e t 0 t r t s 0 s displaystyle vpi se where the random variable r displaystyle r denotes the return and is defined as the sum of future discounted rewards r t 0 t r t textstyle rsum t0infty gamma trt where r t displaystyle rt is the reward at step t displaystyle t 0 1 displaystyle gamma in is the discountrate 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 socalled stationary policies a policy is stationary if the actiondistribution returned by it depends only on the last state visited from the observation agents 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 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 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 ie 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 v s e r s displaystyle vpi se where r displaystyle r stands for the return associated with following displaystyle pi from the initial state s displaystyle s defining v s displaystyle vs as the maximum possible value of v s displaystyle vpi s where displaystyle pi is allowed to change v s max v s displaystyle vsmax limits pi vpi 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 e v s displaystyle rho pi e where s displaystyle s is a state randomly sampled from the distribution displaystyle mu although statevalues suffice to define optimality it is useful to define actionvalues given a state s displaystyle s an action a displaystyle a and a policy displaystyle pi the actionvalue of the pair s a displaystyle sa under displaystyle pi is defined by q s a e r s a displaystyle qpi sae where r displaystyle r now stands for the random return associated with first taking action a displaystyle a in state s 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 q s displaystyle qpi scdot with the highest value at each state s displaystyle s the actionvalue function of such an optimal policy q displaystyle qpi is called the optimal actionvalue function and is commonly denoted by q displaystyle q in summary the knowledge of the optimal actionvalue function alone suffices to know how to act optimally assuming full knowledge of the mdp the two basic approaches to compute the optimal actionvalue function are value iteration and policy iteration both algorithms compute a sequence of functions q k displaystyle qk k 0 1 2 displaystyle k012ldots that converge to q displaystyle q computing these functions involves computing expectations over the whole statespace 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 stateaction 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 displaystyle pi the goal is to compute the function values q s a displaystyle qpi sa or a good approximation to them for all stateaction pairs s a displaystyle sa assuming for simplicity that the mdp is finite that sufficient memory is available to accommodate the actionvalues 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 stateaction pair s a displaystyle sa can be computed by averaging the sampled returns that originated from s a displaystyle sa over time given sufficient time this procedure can thus construct a precise estimate q displaystyle q of the actionvalue function q displaystyle qpi 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 q displaystyle q given a state s displaystyle s this new policy returns an action that maximizes q s displaystyle qscdot 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 stateaction 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 temporal difference methods temporal difference learning 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 stateaction pair in them this may also help to some extent with the third problem although a better solution when returns have high variance is suttons 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 finitedimensional vector to each stateaction pair then the action values of a stateaction pair s a displaystyle sa are obtained by linearly combining the components of s a displaystyle phi sa with some weights displaystyle theta q s a i 1 d i i s a displaystyle qsasum limits i1dtheta iphi isa the algorithms then adjust the weights instead of adjusting the values associated with the individual stateaction 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 qlearning algorithm and its many variants the problem with using actionvalues 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 socalled 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 socalled displaystyle lambda parameter 0 1 displaystyle 0leq 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 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 gradientbased and gradientfree methods gradientbased methods policy gradient methods start with a mapping from a finitedimensional 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 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 informationthese include simulated annealing crossentropy search or methods of evolutionary computation many gradientfree 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 valuefunction based methods that rely on temporal differences might help in this case in recent years actorcritic methods have been proposed and performed well on various problems theory both the asymptotic and finitesample behavior of most algorithms is well understood algorithms with provably good online performance addressing the exploration issue are known efficient exploration of large mdps is largely unexplored except for the case of bandit problems although finitetime performance bounds appeared for many algorithms 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 temporaldifferencebased 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 condition addressing the exploration problem in large mdps largescale empirical evaluations learning and acting under partial information eg using predictive state representation modular and hierarchical reinforcement learning improving existing valuefunction and policy search methods algorithms that work well with large or continuous action spaces transfer learning lifelong learning efficient samplebased planning eg based on monte carlo tree search multiagent or distributed reinforcement learning is a topic of interest applications are expanding actorcritic reinforcement learning reinforcement learning algorithms such as td learning are under investigation as a model for dopaminebased 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 19951996 comparison of reinforcement learning algorithms algorithm description model policy action space state space operator monte carlo every visit to monte carlo modelfree offpolicy discrete discrete samplemeans qlearning stateactionrewardstate modelfree offpolicy discrete discrete qvalue sarsa stateactionrewardstateaction modelfree onpolicy discrete discrete qvalue qlearning lambda stateactionrewardstate with eligibility traces modelfree offpolicy discrete discrete qvalue sarsa lambda stateactionrewardstateaction with eligibility traces modelfree onpolicy discrete discrete qvalue dqn deep q network modelfree offpolicy discrete continuous qvalue ddpg deep deterministic policy gradient modelfree offpolicy continuous continuous qvalue a3c asynchronous actorcritic algorithm modelfree offpolicy continuous continuous qvalue naf qlearning with normalized advantage functions modelfree offpolicy continuous continuous advantage trpo trust region policy optimization modelfree onpolicy continuous continuous advantage ppo proximal policy optimization modelfree onpolicy continuous continuous advantage endtoend deep reinforcement learning the work on learning atari tv games by google deepmind increased attention to endtoend reinforcement learning or deep reinforcement learning this approach extends reinforcement learning to the entire process from observation to action sensors to motors or end to end by forming it using a deep network and without explicitly designing state space or action space 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 apprenticeship learning in apprenticeship learning an expert demonstrates the target behavior the system tries to recover the policy via observation temporal difference learning qlearning stateactionrewardstateaction sarsa fictitious play learning classifier system optimal control dynamic treatment regimes errordriven learning multiagent system distributed artificial intelligence footnotes auer peter jaksch thomas ortner ronald 2010 nearoptimal regret bounds for reinforcement learning journal of machine learning research 11 15631600 bertsekas dimitri p tsitsiklis john 1996 neurodynamic programming nashua nh athena scientific isbn1886529108 bertsekas dimitri p 2012 dynamic programming and optimal control approximate dynamic programming volii nashua nh athena scientific isbn9781886529441 busoniu lucian babuska robert de schutter bart ernst damien 2010 reinforcement learning and dynamic programming using function approximators taylor francis crc press isbn9781439821084 deisenroth marc peter neumann gerhard peters jan 2013 a survey on policy search for robotics foundations and trends in robotics 2 now publishers pp1142bradtke steven j barto andrew g 1996 learning to predict by the method of temporal differences machine learning springer 22 3357 doi101023a1018056104778 gosavi abhijit 2003 simulationbased optimization parametric optimization techniques and reinforcement springer isbn1402074549 peters jan vijayakumar sethu schaal stefan 2003 reinforcement learning for humanoid robotics pdf ieeeras international conference on humanoid robots powell warren 2007 approximate dynamic programming solving the curses of dimensionality wileyinterscience isbn0470171553 sutton richard s barto andrew g 1998 reinforcement learning an introduction mit press isbn0262193981 sutton richard s 1988 learning to predict by the method of temporal differences machine learning springer 3 944 doi101007bf00115009 sutton richard s 1984 temporal credit assignment in reinforcement learning phd thesis university of massachusetts amherst ma szita istvan szepesvari csaba 2010 modelbased reinforcement learning with nearly tight exploration complexity bounds pdf icml 2010 omnipress pp10311038 archived from the original pdf on 20100714 williams ronald j 1987 a class of gradientestimating algorithms for reinforcement learning in neural networks proceedings of the ieee first international conference on neural networks watkins christopher jch 1989 learning from delayed rewards pdf phd thesis kings college cambridge uk literature conferences journals most reinforcement learning papers are published at the major machine learning and ai conferences icml nips aaai ijcai uai ai and statistics and journals jair jmlr machine learning journal ieee tciaig some theory papers are published at colt and alt however many papers appear in robotics conferences iros icra and the agent conference aamas operations researchers publish their papers at the informs conference and for example in the operation research and the mathematics of operations research journals control researchers publish their papers at the cdc and acc conferences or eg in the journals ieee transactions on automatic control or automatica although applied works tend to be published in more specialized journals the winter simulation conference also publishes many relevant papers other than this papers also published in the major conferences of the neural networks fuzzy and evolutionary computation communities the annual ieee symposium titled approximate dynamic programming and reinforcement learning adprl and the biannual european workshop on reinforcement learning ewrl are two regularly held meetings where rl researchers meet website for reinforcement learning an introduction 1998 by rich sutton and andrew barto mit press including a link to an html version of the book reinforcement learning repository reinforcement learning and artificial intelligence rlai rich suttons lab at the university of alberta a beginners guide to deep reinforcement learning autonomous learning laboratory all andrew bartos lab at the university of massachusetts amherst hybrid reinforcement learning realworld reinforcement learning experiments at delft university of technology stanford university andrew ng lecture on reinforcement learning dissecting reinforcement learning series of blog post on rl with python code vtemajor fields of computer sciencenote this template roughly follows the 2012 acm computing classification systemhardware printed circuit board peripheral integrated circuit very large scale integration systems on chip socs energy consumption green computing electronic design automation hardware acceleration computer systemsorganization computer architecture embedded system realtime computing dependability networks network architecture network protocol network components network scheduler network performance evaluation network service software organization interpreter middleware virtual machine operating system software quality software notationsand tools programming paradigm programming language compiler domainspecific language modeling language software framework integrated development environment software configuration management software library software repository software development software development process requirements analysis software design software construction software deployment software maintenance programming team opensource model theory of computation model of computation formal language automata theory computational complexity theory logic semantics algorithms algorithm design analysis of algorithms algorithmic efficiency randomized algorithm computational geometry mathematicsof computing discrete mathematics probability statistics mathematical software information theory mathematical analysis numerical analysis informationsystems database management system information storage systems enterprise information system social information systems geographic information system decision support system process control system multimedia information system data mining digital library computing platform digital marketing world wide web information retrieval security cryptography formal methods security services intrusion detection system hardware security network security information security application security humancomputerinteraction interaction design social computing ubiquitous computing visualization accessibility concurrency concurrent computing parallel computing distributed computing multithreading multiprocessing artificialintelligence natural language processing knowledge representation and reasoning computer vision automated planning and scheduling search methodology control method philosophy of artificial intelligence distributed artificial intelligence machine learning supervised learning unsupervised learning reinforcement learning multitask learning crossvalidation graphics animation rendering image manipulation graphics processing unit mixed reality virtual reality image compression solid modeling appliedcomputing ecommerce enterprise software computational mathematics computational physics computational chemistry computational biology computational social science computational engineering computational healthcare digital art electronic publishing cyberwarfare electronic voting video games word processing operations research educational technology document management book category portal wikiproject commons 