Approximate reinforcement learning: An overview <s> II. PRELIMINARIES. CLASSICAL DP AND RL <s> This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning. <s> BIB001 </s> Approximate reinforcement learning: An overview <s> II. PRELIMINARIES. CLASSICAL DP AND RL <s> \cal Q-learning (Watkins, 1989) is a simple way for agents to learn how to act optimally in controlled Markovian domains. It amounts to an incremental method for dynamic programming which imposes limited computational demands. It works by successively improving its evaluations of the quality of particular actions at particular states. ::: ::: This paper presents and proves in detail a convergence theorem for \cal Q-learning based on that outlined in Watkins (1989). We show that \cal Q-learning converges to the optimum action-values with probability 1 so long as all actions are repeatedly sampled in all states and the action-values are represented discretely. We also sketch extensions to the cases of non-discounted, but absorbing, Markov environments, and where many \cal Q values can be changed each iteration, rather than just one. <s> BIB002 </s> Approximate reinforcement learning: An overview <s> II. PRELIMINARIES. CLASSICAL DP AND RL <s> Reinforcement learning, one of the most active research areas in artificial intelligence, is a computational approach to learning whereby an agent tries to maximize the total amount of reward it receives when interacting with a complex, uncertain environment. In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning. Their discussion ranges from the history of the field's intellectual foundations to the most recent developments and applications. The only necessary mathematical background is familiarity with elementary concepts of probability. The book is divided into three parts. Part I defines the reinforcement learning problem in terms of Markov decision processes. Part II provides basic solution methods: dynamic programming, Monte Carlo methods, and temporal-difference learning. Part III presents a unified view of the solution methods and incorporates artificial neural networks, eligibility traces, and planning; the two final chapters present case studies and consider the future of reinforcement learning. <s> BIB003 </s> Approximate reinforcement learning: An overview <s> II. PRELIMINARIES. CLASSICAL DP AND RL <s> This research monograph is the authoritative and comprehensive treatment of the mathematical foundations of stochastic optimal control of discrete-time systems, including the treatment of the intricate measure-theoretic issues. <s> BIB004 </s> Approximate reinforcement learning: An overview <s> II. PRELIMINARIES. CLASSICAL DP AND RL <s> Reinforcement learning is a learning paradigm concerned with learning to control a system so as to maximize a numerical performance measure that expresses a long-term objective.What distinguishes reinforcement learning from supervised learning is that only partial feedback is given to the learner about the learner's predictions. Further, the predictions may have long term effects through influencing the future state of the controlled system. Thus, time plays a special role. The goal in reinforcement learning is to develop efficient learning algorithms, as well as to understand the algorithms' merits and limitations. Reinforcement learning is of great interest because of the large number of practical applications that it can be used to address, ranging from problems in artificial intelligence to operations research or control engineering. In this book, we focus on those algorithms of reinforcement learning that build on the powerful theory of dynamic programming.We give a fairly comprehensive catalog of learning problems, describe the core ideas, note a large number of state of the art algorithms, followed by the discussion of their theoretical properties and limitations. <s> BIB005
This section briefly introduces the RL problem, together with classical algorithms to solve it, in the framework of Markov decision processes. Consider a Markov decision process with state space X and action space U . For now, X and U are assumed countable, but under appropriate technical conditions, the formalism can be extended to uncountable sets BIB004 . The probability that the next state x k+1 is reached after action u k is taken in state x k is f (x k , u k , x k+1 ), where f : X×U ×X → [0, 1] is the transition probability function. After the transition to x k+1 , a reward r k+1 = ρ(x k , u k , x k+1 ) is received, where ρ : X × U × X → R is the reward function. The symbol k denotes the discrete time index. BIB005 The expected infinite-horizon discounted return of initial state x 0 under a policy h : X → U is: where is the discount factor, and the notation The goal is to find an optimal policy h * that maximizes the return (1) from every x 0 ∈ X. Other types of return can also be used, such as finite-horizon or averaged over time BIB001 ,  . Many algorithms employ value functions to find h * . The Q-function (state-action value function) of a policy h is the expected return when starting in a given state, applying a given action, and following h thereafter: The optimal Q-function is the best that can be obtained by any policy: . Any policy h * that selects at each state an action with the largest optimal Q-value, i.e., that satisfies: is optimal (it maximizes the return). In general, a policy that chooses actions by maximizing a certain Q-function is called greedy in this Q-function. Policy Q-functions and, respectively, the optimal Q-function satisfy the Bellman equations: State value functions can be used as an alternative to Q-functions. In particular, the V-function of policy h is , and the optimal V-function is V * (x) = max u Q * (x, u). Henceforth, we will prefer using Q-functions, because they make greedy policies easier to find -see (2) -than when V-functions are employed. Modulo this difficulty, many of the algorithms easily extend to the V-function case. 1 shows the algorithms taxonomy that we will employ. DP algorithms are model-based: they find h * using knowledge of the model (the functions f and ρ). 3 RL algorithms are model-free: they find h * from transition and reward data, without using f and ρ. Moreover, online RL algorithms collect their own data, by interacting with the system while they learn. Some RL algorithms are model-learning (not shown in Fig. 1 ): they estimate f and ρ, and apply DP techniques to these estimates. Looking at the path they take to find an optimal policy, the algorithms can be classified along a second, orthogonal axis into three classes: value iteration, policy iteration, and policy search. We next introduce these classes, together with several central algorithms useful later in this survey. Value iteration algorithms directly search for an optimal value function, which they use to compute an optimal policy. An important DP algorithm from this class is Q-iteration 4 , which starts from some initial Q 0 and updates it at each iteration by turning the Bellman equation (4) into an assignment: In the countable state-action spaces assumed, the expectation can be written as a sum. Q-iteration asymptotically converges to Q * , which can then be used to obtain h * with (2). The most widely used RL algorithm from the value iteration class is Q-learning BIB002 , which updates the Q-function online, using observed state transitions and rewards, i.e., data tuples of the form (x k , u k , x k+1 , r k+1 ): where α k ∈ (0, 1] is the learning rate. Q-learning can be seen as a sample-based, stochastic approximation of Q-iteration. At each step, the estimate for the optimal Q-value of (x k , u k ) is corrected by the 'temporal difference' between the update target r k+1 + γ max u Q k (x k+1 , u ) -given by the Q-iteration update (5) or the Bellman equation (4) -and the current estimate Q k (x k , u k ). To converge to Q * , Q-learning crucially requires exploration: the probability of attempting new, non-greedy actions must always be non-zero, to avoid becoming stuck in a local optimum. The tradeoff between exploration and greedy action choices ('exploitation') is essential for the performance of any online RL algorithm. A classical way to achieve this tradeoff is the ε-greedy policy, [1, Sec. 2.2]: where ε k ∈ (0, 1) is the exploration probability at step k. Policy iteration algorithms evaluate policies by constructing their value functions (policy evaluation step), and use these value functions to find greedy, improved policies (policy improvement step). For instance, a DP algorithm for policy iteration starts with some initial policy h 0 , and at every iteration ≥ 0, finds Q h by iteratively applying the Bellman equation (3), in a similar way to Q-iteration. Then, an improved policy is determined: and the algorithm continues with this policy at the next iteration. This algorithm is guaranteed to converge to h * , see BIB003 Sec. 4.3] . A well-known algorithm from the online RL, policy iteration class is SARSA  . SARSA employs tuples of the form (x k , u k , r k+1 , x k+1 , u k+1 ) to update the Q-function: and applies an exploration-exploitation policy such as ε-greedy (7). In contrast to Q-learning, the update target is r k+1 + γQ k (x k+1 , u k+1 ). Since u k+1 = h k+1 (x k+1 ), this target is derived from the Bellman equation (3), and under a fixed policy, SARSA would perform online policy evaluation. However, since the exploitative part of the policy is always greedy in Q k , SARSA implicitly performs policy improvements, and is therefore a type of online policy iteration. Policy search algorithms aim to find an optimal policy directly. To this end, they solve an optimization problem: , where s(h) is a score value representative for the returns obtained by h. We will delve into details about policy search in Sec. VI, in the approximate setting. Relation to other taxonomies: Policy search is sometimes called 'approximation in policy space', and by contrast value and policy iteration are grouped together into 'approximation in value function space'  . Also, it may seem striking that we classify Q-learning as online value iteration and SARSA as online policy iteration, since traditionally value and policy iteration are offline, while Q-learning and SARSA are respectively 'off-policy' and 'on-policy' (on-policy means here that the Q-value Q(x k+1 , u k+1 ) of the actually chosen next action u k+1 is used in the updates, while off-policy methods may use another action). However, as seen above, Q-learning is an online, incremental way of performing Q-iteration, and SARSA is an incremental policy iteration where policy improvements are 'hidden' in the greedy action selections. We find this deeper relationship more interesting; e.g., some policy iteration methods can use data collected off-policy! Finally, we wish to emphasize the distinction between model-based and model-learning methods. While the latter are (somewhat confusingly) called 'model-based' in the AI literature, we reserve the name 'model-based' for methods that truly require an a priori model of the problem.