Reinforcement learning in robotics: A survey <s> Goals of reinforcement learning <s> Recent developments in the area of reinforcement learning have yielded a number of new algorithms for the prediction and control of Markovian environments. These algorithms, including the TD(λ) algorithm of Sutton (1988) and the Q-learning algorithm of Watkins (1989), can be motivated heuristically as approximations to dynamic programming (DP). In this paper we provide a rigorous proof of convergence of these DP-based learning algorithms by relating them to the powerful techniques of stochastic approximation theory via a new convergence theorem. The theorem establishes a general class of convergent algorithms to which both TD(λ) and Q-learning belong. <s> BIB001 </s> Reinforcement learning in robotics: A survey <s> Goals of reinforcement learning <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> BIB002 </s> Reinforcement learning in robotics: A survey <s> Goals of reinforcement learning <s> This paper introduces random versions of successive approximations and multigrid algorithms for computing approximate solutions to a class of finite and infinite horizon Markovian decision problems (MDPs). We prove that these algorithms succeed in breaking the curse of dimensionality for a subclass of MDPs known as discrete decision processes (DDPs). <s> BIB003 </s> Reinforcement learning in robotics: A survey <s> Goals of reinforcement learning <s> Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically intractable. In this paper we explore an alternative approach in which the policy is explicitly represented by its own function approximator, independent of the value function, and is updated according to the gradient of expected reward with respect to the policy parameters. Williams's REINFORCE method and actor-critic methods are examples of this approach. Our main new result is to show that the gradient can be written in a form suitable for estimation from experience aided by an approximate action-value or advantage function. Using this result, we prove for the first time that a version of policy iteration with arbitrary differentiable function approximation is convergent to a locally optimal policy. <s> BIB004 </s> Reinforcement learning in robotics: A survey <s> Goals of reinforcement learning <s> We present new algorithms for reinforcement learning and prove that they have polynomial bounds on the resources required to achieve near-optimal return in general Markov decision processes. After observing that the number of actions required to approach the optimal return is lower bounded by the mixing time T of the optimal policy (in the undiscounted case) or by the horizon time T (in the discounted case), we then give algorithms requiring a number of actions and total computation time that are only polynomial in T and the number of states and actions, for both the undiscounted and discounted cases. An interesting aspect of our algorithms is their explicit handling of the Exploration-Exploitation trade-off. <s> BIB005 </s> Reinforcement learning in robotics: A survey <s> Goals of reinforcement learning <s> Stochastic optimization arises in a wide range of problems, and as a result the ideas have been developed in different communities, creating fragmented styles in terms of notation, modeling and algorithms. Some of these variations can be explained by differences in application, as well as differences in research styles. We attempt to bridge these communities by describing how to translate notational systems, while contrasting modeling and algorithmic strategies. We also touch on differences in research styles which reflect expectations for a publishable contribution as well as the style of publication outlets used by different communities. This version of the paper has been written largely without references (more references may be added later). At this point, I think it is fair to say that all of the concepts contained in this paper have been expressed somewhere in the literature, or are at least known among groups of researchers. This article synthesizes these ideas in a coherent way, and while multiple notational systems are reviewed, there is also an attempt to develop some common notational principles that will help to foster communication across communities. This article is intended as a discussion piece and is not intended for journal publication. The goal is to help foster communication between the different communities. Constructive thoughts and comments are warmly appreciated. Since this document will evolve over time, please email your comments to powell@princeton.edu. You may put notes directly on the pdf (this is best), but if you put them in email, please include the date on the front page so I know which version you are using. <s> BIB006
The goal of reinforcement learning is to discover an optimal policy π * that maps states (or observations) to actions so as to maximize the expected return J , which corresponds to the cumulative expected reward. There are different models of optimal behavior BIB002 This setting can also be applied to model problems where it is known how many steps are remaining. Alternatively, future rewards can be discounted by a discount factor γ (with 0 ≤ γ < 1) This is the setting most frequently discussed in classical reinforcement learning texts. The parameter γ affects how much the future is taken into account and needs to be tuned manually. As illustrated by BIB002 , this parameter often qualitatively changes the form of the optimal solution. Policies designed by optimizing with small γ are myopic and greedy, and may lead to poor performance if we actually care about longer-term rewards. It is straightforward to show that the optimal control law can be unstable if the discount factor is too low (e.g. it is not difficult to show this destabilization even for discounted linear quadratic regulation problems). Hence, discounted formulations are frequently inadmissible in robot control. In the limit when γ approaches 1, the metric approaches what is known as the average-reward criterion  , This setting has the problem that it cannot distinguish between policies that initially gain a transient of large rewards and those that do not. This transient phase, also called prefix, is dominated by the rewards obtained in the long run. If a policy accomplishes both an optimal prefix as well as an optimal long-term behavior, it is called bias optimal  ). An example in robotics would be the transient phase during the start of a rhythmic movement, where many policies will accomplish the same long-term reward but differ substantially in the transient (e.g. there are many ways of starting the same gait in dynamic legged locomotion) allowing for room for improvement in practical application. In real-world domains, the shortcomings of the discounted formulation are often more critical than those of the average reward setting as stable behavior is often more important than a good transient  . We also often encounter an episodic control task, where the task runs only for H time steps and then reset (potentially by human intervention) and started over. This horizon, H, may be arbitrarily large, as long as the expected reward over the episode can be guaranteed to converge. As such episodic tasks are probably the most frequent ones, finite-horizon models are often the most relevant. Two natural goals arise for the learner. In the first, we attempt to find an optimal strategy at the end of a phase of training or interaction. In the second, the goal is to maximize the reward over the whole time the robot is interacting with the world. In contrast to supervised learning, the learner must first discover its environment and is not told the optimal action it needs to take. To gain information about the rewards and the behavior of the system, the agent needs to explore by considering previously unused actions or actions it is uncertain about. It needs to decide whether to play it safe and stick to well-known actions with (moderately) high rewards or to dare trying new things in order to discover new strategies with an even higher reward. This problem is commonly known as the exploration-exploitation trade-off. In principle, reinforcement learning algorithms for MDPs with performance guarantees are known  BIB005  with polynomial scaling in the size of the state and action spaces, an additive error term, as well as in the horizon length (or a suitable substitute including the discount factor or "mixing time" BIB005 ). However, state-spaces in robotics problems are often tremendously large as they scale exponentially in the number of state variables and often are continuous. This challenge of exponential growth is often referred to as the curse of dimensionality  (also discussed in Section 3.1). Off-policy methods learn independent of the employed policy, i.e. an explorative strategy that is different from the desired final policy can be employed during the learning process. On-policy methods collect sample information about the environment using the current policy. As a result, exploration must be built into the policy and determines the speed of the policy improvements. Such exploration and the performance of the policy can result in an exploration-exploitation trade-off between long-and shortterm improvement of the policy. Modeling exploration models with probability distributions has surprising implications, e.g. stochastic policies have been shown to be the optimal stationary policies for selected problems BIB001 BIB004 and can even break the curse of dimensionality BIB003 . Furthermore, stochastic policies often allow the derivation of new policy update steps with surprising ease. The agent needs to determine a correlation between actions and reward signals. An action taken does not have to have an immediate effect on the reward but can also influence a reward in the distant future. The difficulty in assigning credit for rewards is directly related to the horizon or mixing time of the problem. It also increases with the dimensionality of the actions as not all parts of the action may contribute equally. The classical reinforcement learning setup is a MDP where additionally to the states S, actions A, and rewards R we also have transition probabilities T( s , a, s). Here, the reward is modeled as a reward function R (s, a). If both the transition probabilities and reward function are known, this can be seen as an optimal control problem BIB006 .