A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization in Reinforcement Learning <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> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization in Reinforcement Learning <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> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization in Reinforcement Learning <s> We adapt the ideas underlying the success of Deep Q-Learning to the continuous action domain. We present an actor-critic, model-free algorithm based on the deterministic policy gradient that can operate over continuous action spaces. Using the same learning algorithm, network architecture and hyper-parameters, our algorithm robustly solves more than 20 simulated physics tasks, including classic problems such as cartpole swing-up, dexterous manipulation, legged locomotion and car driving. Our algorithm is able to find policies whose performance is competitive with those found by a planning algorithm with full access to the dynamics of the domain and its derivatives. We further demonstrate that for many of the tasks the algorithm can learn policies end-to-end: directly from raw pixel inputs. <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization in Reinforcement Learning <s> We propose a conceptually simple and lightweight framework for deep reinforcement learning that uses asynchronous gradient descent for optimization of deep neural network controllers. We present asynchronous variants of four standard reinforcement learning algorithms and show that parallel actor-learners have a stabilizing effect on training allowing all four methods to successfully train neural network controllers. The best performing method, an asynchronous variant of actor-critic, surpasses the current state-of-the-art on the Atari domain while training for half the time on a single multi-core CPU instead of a GPU. Furthermore, we show that asynchronous actor-critic succeeds on a wide variety of continuous motor control problems as well as on a new task of navigating random 3D mazes using a visual input. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization in Reinforcement Learning <s> The game of Go has long been viewed as the most challenging of classic games for artificial intelligence owing to its enormous search space and the difficulty of evaluating board positions and moves. Here we introduce a new approach to computer Go that uses ‘value networks’ to evaluate board positions and ‘policy networks’ to select moves. These deep neural networks are trained by a novel combination of supervised learning from human expert games, and reinforcement learning from games of self-play. Without any lookahead search, the neural networks play Go at the level of stateof-the-art Monte Carlo tree search programs that simulate thousands of random games of self-play. We also introduce a new search algorithm that combines Monte Carlo simulation with value and policy networks. Using this search algorithm, our program AlphaGo achieved a 99.8% winning rate against other Go programs, and defeated the human European Go champion by 5 games to 0. This is the first time that a computer program has defeated a human professional player in the full-sized game of Go, a feat previously thought to be at least a decade away. <s> BIB005 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization in Reinforcement Learning <s> We give an overview of recent exciting achievements of deep reinforcement learning (RL). We discuss six core elements, six important mechanisms, and twelve applications. We start with background of machine learning, deep learning and reinforcement learning. Next we discuss core RL elements, including value function, in particular, Deep Q-Network (DQN), policy, reward, model, planning, and exploration. After that, we discuss important mechanisms for RL, including attention and memory, unsupervised learning, transfer learning, multi-agent RL, hierarchical RL, and learning to learn. Then we discuss various applications of RL, including games, in particular, AlphaGo, robotics, natural language processing, including dialogue systems, machine translation, and text generation, computer vision, neural architecture design, business management, finance, healthcare, Industry 4.0, smart grid, intelligent transportation systems, and computer systems. We mention topics not reviewed yet, and list a collection of RL resources. After presenting a brief summary, we close with discussions. ::: Please see Deep Reinforcement Learning, arXiv:1810.06339, for a significant update. <s> BIB006 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. Optimization in Reinforcement Learning <s> In this work, we propose to apply trust region optimization to deep reinforcement learning using a recently proposed Kronecker-factored approximation to the curvature. We extend the framework of natural policy gradient and propose to optimize both the actor and the critic using Kronecker-factored approximate curvature (K-FAC) with trust region; hence we call our method Actor Critic using Kronecker-Factored Trust Region (ACKTR). To the best of our knowledge, this is the first scalable trust region natural gradient method for actor-critic methods. It is also a method that learns non-trivial tasks in continuous control as well as discrete control policies directly from raw pixel inputs. We tested our approach across discrete domains in Atari games as well as continuous domains in the MuJoCo environment. With the proposed methods, we are able to achieve higher rewards and a 2- to 3-fold improvement in sample efficiency on average, compared to previous state-of-the-art on-policy actor-critic methods. Code is available at this https URL <s> BIB007
Reinforcement learning (RL) is an important research field of machine learning and is also one of the most popular topics. Agents using deep reinforcement learning have achieved great success in learning complex behavior skills and solving challenging control tasks in high-dimensional primitive perceptual state space BIB003 , BIB004 , BIB005 . It interacts with the environment through the trial-and-error mechanism and learns optimal strategies by maximizing cumulative rewards BIB002 . We describe several concepts of reinforcement learning as follows: 1) Agent: making different actions according to the state of the external environment, and adjusting the strategy according to the reward of the external environment. 2) Environment: all things outside the agent that will be affected by the action of the agent. It can change the state and provide the reward to the agent. 3) State s: a description of the environment. 4) Action a: a description of the behavior of the agent. 5) Reward r t (s t−1 , a t−1 , s t ): the timely return value at time t. 6) Policy π(a|s): a function that the agent decides the action a according to the current state s. 7) State transition probability p(s ′ |s, a): the probability distribution that the environment will transfer to state s ′ at the next moment, after the agent selecting an action a based on the current state s. 8) p(s ′ , r|s, a): the probability that the agent transforms to state s ′ and obtains the reward r, where the agent is in state s and selecting the action a. Many reinforcement learning problems can be described by Markov decision process (MDP) < S, A, P, γ, r > BIB002 , in which S is state space, A is action space, P is state transition probability function, r is reward function and γ is the discount factor 0 < γ < 1. At each time, the agent accepts a state and selects the action from an action set according to the policy. The agent receives feedback from the environment and then moves to the next state. The goal of reinforcement learning is to find a strategy that allows us to get the maximum γ discounted cumulative reward. The discounted return is constructed as People do not necessarily know the MDP behind the problem. From this point, reinforcement learning is divided into two categories. One is model-based reinforcement learning which knows the MDP of the whole model (including the transition probability P and reward function r), and the other is the model-free method in which the MDP is unknown. Systematic exploration is required in the latter methods. The most commonly used value function is the state value function, which is the expected return of executing policy π from state s. The state-action value function is also essential which is the expected return for selecting action a under state s and policy π, The value function of the current state s can be calculated by the value function of the next state s ′ . The Bellman equations of V π (s) and Q π (s, a) describe the relation by There are many reinforcement learning methods based on value function. They are called value-based methods, which play a significant role in RL. For example, Q-learning BIB001 and SARSA  are two popular methods which use temporal difference algorithms. The policy-based approach is to optimize the policy π θ (a|s) directly and update the parameters θ by gradient descent BIB006 . The actor-critic algorithm is a reinforcement learning method combining policy gradient and temporal differential learning, which learns both a policy and a state value function. It estimates the parameters of two structures simultaneously. 1) The actor is a policy function, which is to learn a policy π θ (a|s) to obtain the highest possible return. 2) The critic refers to the learned value function V φ (s), which estimates the value function of the current policy. That is to evaluate the quality of the actor. In the actor-critic method, the critic solves a problem of prediction, while the actor pays attention to the control  . There is more information of actor-critic method in BIB002 ,  The summary of the value-based method, the policybased method and the actor-critic method are as follows: 1) The value-based method: It needs to calculate value function, and usually get a definite policy. 2) The policy-based method: It optimizes the policy π without selecting an action according to value function. 3) The actor-critic method: It combines the above two methods, and learns both the policy π and the state value function. Deep reinforcement learning (DRL) combines reinforcement learning and deep learning, which defines problems and optimizes goals in the framework of RL, and solves problems such as state representation and strategy representation using deep learning techniques. DRL has achieved great success in many challenging control tasks and uses deep neural networks to represent control policy. For neural network training, a simple stochastic gradient algorithm or other first-order algorithms are usually chosen, but these algorithms are not efficient in exploring the weight space, which makes DRL methods often take several days to train BIB007 . So, a distributed method was proposed to solve this problem, in which parallel actor-learners have a stabilizing effect during training BIB004 . It executes multiple agents to interact with the environment simultaneously, which reduces the training time. But this method ignores the sampling efficiency. A scalable and sample-efficient natural gradient algorithm was proposed, which uses a Kroneckerfactored approximation method to compute the natural policy gradient update, and employ the update to the actor and the critic (ACKTR) BIB007 .