nils-herrmann/clean_scirepeval huggingface dataset:
Hierarchical multi-agent reinforcement learning

In this paper we investigate the use of hierarchical reinforcement learning to speed up the acquisition of cooperative multi-agent tasks. We extend the MAXQ framework to the multi-agent case. Each agent uses the same MAXQ hierarchy to decompose a task into sub-tasks. Learning is decentralized, with each agent learning three interrelated skills: how to perform subtasks, which order to do them in, and how to coordinate with other agents. Coordination skills among agents are learned by using joint actions at the highest level(s) of the hierarchy. The Q nodes at the highest level(s) of the hierarchy are configured to represent the joint task-action space among multiple agents. In this approach, each agent only knows what other agents are doing at the level of sub-tasks, and is unaware of lower level (primitive) actions. This hierarchical approach allows agents to learn coordination faster by sharing information at the level of sub-tasks, rather than attempting to learn coordination taking into account primitive joint state-action values. We apply this hierarchical multi-agent reinforcement learning algorithm to a complex AGV scheduling task and compare its performance and speed with other learning approaches, including flat multi-agent, single agent using MAXQ, selfish multiple agents using MAXQ (where each agent acts independently without communicating with the other agents), as well as several well-known AGV heuristics like "first come first serve", "highest queue first" and "nearest station first". We also compare the tradeoffs in learning speed vs. performance of modeling joint action values at multiple levels in the MAXQ hierarchy.
Continuous-Time Hierarchical Reinforcement Learning

Hierarchical reinforcement learning (RL) is a general framework which studies how to exploit the structure of actions and tasks to accelerate policy learning in large domains. Prior work in hierarchical RL, such as the MAXQ method, has been limited to the discrete-time discounted reward semiMarkov decision process (SMDP) model. This paper generalizes the MAXQ method to continuous-time discounted and average reward SMDP models. We describe two hierarchical reinforcement learning algorithms: continuous-time discounted reward MAXQ and continuous-time average reward MAXQ. We apply these algorithms to a complex multiagent AGV scheduling problem, and compare their performance and speed with each other, as well as several well-known AGV scheduling heuristics.
Learning hierarchical observable Markov decision process models for robot navigation

We propose and investigate a general framework for hierarchical modeling of partially observable environments, such as office buildings, using hierarchical hidden Markov models (HHMMs). Our main goal is to explore hierarchical modeling as a basis for designing more efficient methods for model construction and usage. As a case study we focus on indoor robot navigation and show how this framework can be used to learn a hierarchy of models of the environment at different levels of spatial abstraction. We introduce the idea of model reuse that can be used to combine already learned models into a larger model. We describe an extension of the HHMM model to includes actions, which we call hierarchical POMDPs, and describe a modified hierarchical Baum-Welch algorithm to learn these models. We train different families of hierarchical models for a simulated and a real world corridor environment and compare them with the standard "flat" representation of the same environment. We show that the hierarchical POMDP approach, combined with model reuse, allows learning hierarchical models that fit the data better and train faster than flat models.
Hierarchical Map Learning For Robot Navigation

In this paper we investigate learning a hierarchy of maps at di erent spatial scales using the framework of hierarchical hidden Markov models (HHMM). This framework provides a formal mechanism to explicitly model stochastic processes at varying temporal abstraction, and hence gives a rigorous framework for constructing hierarchical models for applications such as autonomous oÆce navigation. Our research is also motivated by both cognitive science and engineering considerations. Animal and human navigation studies suggest they represent the external world at di erent spatial scales and use hierarchical planning strategies for navigation. However, existing robot navigation systems primarily learn at uniform resolution models, which are unlikely to scale to large environments. Our long-term goal is to use hierarchical maps as a basis for more eÆcient learning and planning algorithms that reuse already learned maps (and policies) in larger maps. Di erent families of HHMMs are trained on a sample navigation problem using a real robot testbed. We provide a detailed set of experiments comparing hierarchical models, hierarchical models with reuse, and at models. The models are compared in terms of their ability to localize the robot (state estimation), goodness of t to the data, speed of learning, quality of the learned map, and ability to use previously learned submodels and also infer the abstract structure of the environment. Overall, the results show hierarchical HMM models provide a robust framework for learning multiscale spatial models of real environments.
Hierarchical Memory-Based Reinforcement Learning

A key challenge for reinforcement learning is scaling up to large partially observable domains. In this paper, we show how a hierarchy of behaviors can be used to create and select among variable length short-term memories appropriate for a task. At higher levels in the hierarchy, the agent abstracts over lower-level details and looks back over a variable number of high-level decisions in time. We formalize this idea in a framework called Hierarchical Suffix Memory (HSM). HSM uses a memory-based SMDP learning method to rapidly propagate delayed reward across long decision sequences. We describe a detailed experimental study comparing memory vs. hierarchy using the HSM framework on a realistic corridor navigation task.
Face Recognition Using Foveal Vision

Data from human subjects recorded by an eyetracker while they are learning new faces shows a high degree of similarity in saccadic eye movements over a face. Such experiments suggest face recognition can be modeled as a sequential process, with each fixation providing observations using both foveal and parafoveal information. We describe a sequential model of face recognition that is incremental and scalable to large face images. Two approaches to implementing an artificial fovea are described, which transform a constant resolution image into a variable resolution image with acute resolution in the fovea, and an exponential decrease in resolution towards the periphery. For each individual in a database of faces, a hidden-Markov model (HMM) classifier is learned, where the observation sequences necessary to learn the HMMs are generated by fixating on different regions of a face. Detailed experimental results are provided which show the two foveal HMM classifiers outperform a more traditional HMM classifier built by moving a horizontal window from top to bottom on a highly subsampled face image.
Solving Semi-Markov Decision Problems Using Average Reward Reinforcement Learning

A large class of problems of sequential decision making under uncertainty, of which the underlying probability structure is a Markov process, can be modeled as stochastic dynamic programs (referred to, in general, as Markov decision problems or MDPs). However, the computational complexity of the classical MDP algorithms, such as value iteration and policy iteration, is prohibitive and can grow intractably with the size of the problem and its related data. Furthermore, these techniques require for each action the one step transition probability and reward matrices, and obtaining these is often unrealistic for large and complex systems. Recently, there has been much interest in a simulation-based stochastic approximation framework called reinforcement learning (RL), for computing near optimal policies for MDPs. RL has been successfully applied to very large problems, such as elevator scheduling, and dynamic channel allocation of cellular telephone systems. In this paper, we extend RL to a more general class of decision tasks that are referred to as semi-Markov decision problems (SMDPs). In particular, we focus on SMDPs under the average-reward criterion. We present a new model-free RL algorithm called SMART (Semi-Markov Average Reward Technique). We present a detailed study of this algorithm on a combinatorially large problem of determining the optimal preventive maintenance schedule of a production inventory system. Numerical results from both the theoretical model and the RL algorithm are presented and compared.
N Average- Ent Learning Algorit Mot Ivat Ion

Average-reward reinforcement learning (ARL) is an undiscounted optimality framework that is generally applicable to a broad range of control tasks. ARL computes gain-optimal control policies that maximize the expected payoff per step. However, gainoptimality has some intrinsic limitations as an optimality criterion, since for example, it cannot distinguish between different policies that all reach an absorbing goal state, but incur varying costs. A more selective criterion is bias optima&y, which can filter gain-optimal policies to select those that reach absorbing goals with the minimum cost. While several ARL algorithms for computing gain-optimal policies have been proposed, none of these algorithms can guarantee bias optimality, since this requires solving at least two nested optimality equations. In this paper, we describe a novel model-based ARL algorithm for computing bias-optimal policies. We test the proposed algorithm using an admission control queuing system, and show that it is able to utilize the queue much more efficiently than a gain-optimal method by learning bias-optimal policies.
Robust Mobile Robot Navigation using Partially-Observable Semi-Markov Decision Processes

Mobile robots operating in dynamic ooce environments need robust navigation algorithms capable of dealing with uncertainties arising from sensor and actuator errors. Such algorithms also need to be able to synthesize plans that take into account temporal aspects of their environment, such as crowded corridors, and busy intersections. This paper describes a novel mobile robot navigation architecture based on Partially-Observable Semi-Markov Decision Processes (POSMDP). This model extends previous work on POMDP-based navigation architectures, which assumed a discrete-time temporal model of actions. We show that the POSMDP model allows the robot to explicitly model the transition time of diierent actions in various locations in the environment (e.g. passing through intersections takes more time than going through corridors). The paper describes experimental results of using the POSMDP architecture on a real mobile robot called PAVLOV. The results show that the robot is able to traverse paths of several hundred meters and also plan to avoid crowded corridors.
A Study of Reinforcement Learning in the Continuous Case by the Means of Viscosity Solutions

This paper proposes a study of Reinforcement Learning (RL) for continuous state-space and time control problems, based on the theoretical framework of viscosity solutions (VSs). We use the method of dynamic programming (DP) which introduces the value function (VF), expectationof the best future cumulativereinforcement. In the continuous case, the value function satisses a non-linear rst (or second) order (depending on the deterministic or stochastic aspect of the process) diierential equation called the Hamilton-Jacobi-Bellman (HJB) equation. It is well known that there exists an innnity of generalized solutions (diierentiable almost everywhere) to this equation, other than the VF. We show that gradient-descent methods may converge to one of these generalized solutions, thus failing to nd the optimal control. In order to solve the HJB equation, we use the powerful framework of viscosity solutions and state that there exists a unique viscosity solution to the HJB equation, which is the value function. Then, we use another main result of VSs (their stability when passing to the limit) to prove the convergence of numerical approximations schemes based on nite diierence (FD) and nite element (FE) methods. These methods discretize, at some resolution, the HJB equation into a DP equation of a Markov Decision Process (MDP), which can be solved by DP methods (thanks to a \strong" contraction property) if all the initial data (the state dynamics and the reinforcement function) were perfectly known. However, in the RL approach, as we consider a system in interaction with some a priori (at least partially) unknown environment, which learns \from experience", the initial data are not perfectly known but have to be approximated during learning. The main contribution of this work is to derive a general convergence theorem for RL algorithms when one uses only \approximations" (in a sense of satisfying some \weak" contraction property) of the initial data. This result can be used for model-based or model-free RL algorithms, with oo-line or on-line updating methods, for deterministic or stochastic state dynamics (though this latter case is not described here), and based on FE or FD discretization methods. It is illustrated with several RL algorithms and one numerical simulation for the \Car on the Hill" problem.
Hierarchical Optimization of Policy-Coupled Semi-Markov Decision Processes

One general strategy for approximately solving large Markov decision processes is \divide-and-conquer": the original problem is decomposed into sub-problems which interact with each other, but yet can be solved independently by taking into account the nature of the interaction. In this paper we focus on a class of \policy-coupled" semi-Markov decision processes (SMDPs), which arise in many nonstationary real-world multi-agent tasks, such as manufacturing and robotics. The nature of the interaction among sub-problems (agents) is more subtle than that studied previously: the components of a sub-SMDP, namely the available states and actions, transition probabilities and rewards, depend on the policies used in solving the \neighboring" sub-SMDPs. This \strongly-coupled" interaction among sub-problems causes the approach of solving each sub-SMDP in parallel to fail. We present a novel approach whereby many variants of each sub-SMDP are solved, explicitly taking into account the diierent modes of interaction , and a dynamic merging algorithm is used to combine the base level policies. We present detailed experimental results for a 12-machine transfer line, a large real-world manufacturing task. We show that the hierarchical approach is not only much faster than a ""at" algorithm, but also outperforms two well-known heuristics for running transfer lines used in many factories.
Rapid Concept Learning for Mobile Robots

Concept learning in robotics is an extremely challenging problem: sensory data is often high dimensional, and noisy due to specularities and other irregularities. In this paper, we investigate two general strategies to speed up learning, based on spatial decomposition of the sensory representation, and simultaneous learning of multiple classes using a shared structure. We study two concept learning scenarios: a hallway navigation problem, where the robot has to induce features such as “opening” or “wall”. The second task is recycling, where the robot has to learn to recognize objects, such as a “trash can”. We use a common underlying function approximator in both studies in the form of a feedforward neural network, with several hundred input units and multiple output units. Despite the high degree of freedom afforded by such an approximator, we show the two strategies provide sufficient bias to achieve rapid learning. We provide detailed experimental studies on an actual mobile robot called PAVLOV to illustrate the effectiveness of this approach.
Optimizing Production Manufacturing Using Reinforcement Learning

Many industrial processes involve making parts with an assembly of machines, where each machine carries out an operation on a part, and the finished product requires a whole series of operations. A well-studied example of such a factory structure is the transfer line, which involves a sequence of machines. Optimizing transfer lines has been a subject of much study in the industrial engineering and operations research fields. A desirable goal of a lean manufacturing system is to maximize demand, while keeping inventory levels of unfinished product as low as possible. This problem is intractable since the number of states is usually very large, and the underlying models are stochastic. In this paper we present an artificial intelligence approach to optimization based on a simulation-based dynamic programming method called reinforcement learning. We describe a reinforcement learning algorithm called SMART, and compare its performance on optimizing manufacturing systems with that of standard heuristics used in industry.
A Greedy Divide-and-Conquer Approach to Optimizing Large Manufacturing Systems using Reinforcement Learning

Manufacturing is a challenging real-world domain for studying hierarchical MDP-based optimization algorithms. We have recently obtained very promising results using a hierarchical reinforcement learning based optimization algorithm for a 12-machine transfer line. Transfer lines model factory processes in automobile and many other product assembly plants. Unlike domains such as elevator scheduling, where the individual elevator \agents" are eeectively independent , individual machines in a transfer line are directly aaected by each others behavior. This interaction creates a highly non-stationary environment that defeats ""at" learning algorithms that train each machine while they are part of the line. Our hierarchical optimization algorithm comprises of an average-reward Q-learning algorithm for semi-Markov decision processes called SMART for learning low-cost policies for operating each individual machine, and a greedy algorithm for combining the base level policies to obtain an overall policy for running the transfer line. Unlike other approaches to hierarchical optimization, in our system policies at the lowest level are modeled using semi-Markov decision processes (SMDPs). In our results to date, we can show that the hierarchical approach is not only much faster than the ""at" algorithm, but also appears to outperform well-known heuristics for running transfer lines used in many factories today.
The NSF Workshop on Reinforcement Learning: Summary and Observations

Reinforcement learning (RL) has become one of the most actively studied learning frameworks in the area of intelligent autonomous agents. This article describes the results of a three-day meeting of leading researchers in this area, sponsored by the National Science Foundation (NSF). As RL is an interdisciplinary topic, the workshop brought together researchers from a variety of elds, including machine learning, neu-ral networks, artiicial intelligence, robotics, and operations research. Thirty leading researchers from the U.S., Canada, Europe, and Japan participated in the workshop, from many diierent universities, government and industrial research laboratories. The goals of the meeting were to (1) understand limitations of current RL systems and deene promising directions for further research, (2) clarify the relationships between RL and existing work in engineering elds, such as operations research, and (3) identify potential industrial applications of RL.
n Average- ent Learning Algorit

Average-reward reinforcement learning (ARL) is an undiscounted optimality framework that is generally applicable to a broad range of control tasks. ARL computes gain-optimal control policies that maximize the expected payoff per step. However, gainoptimality has some intrinsic limitations as an optimality criterion, since for example, it cannot distinguish between different policies that all reach an absorbing goal state, but incur varying costs. A more selective criterion is bias optima&y, which can filter gain-optimal policies to select those that reach absorbing goals with the minimum cost. While several ARL algorithms for computing gain-optimal policies have been proposed, none of these algorithms can guarantee bias optimality, since this requires solving at least two nested optimality equations. In this paper, we describe a novel model-based ARL algorithm for computing bias-optimal policies. We test the proposed algorithm using an admission control queuing system, and show that it is able to utilize the queue much more efficiently than a gain-optimal method by learning bias-optimal policies.
An Average-Reward Reinforcement Learning Algorithm for Computing Bias-Optimal Policies

Average-reward reinforcement learning (ARL) is an undiscounted optimality framework that is generally applicable to a broad range of control tasks. ARL computes gain-optimal control policies that maximize the expected payoff per step. However, gainoptimality has some intrinsic limitations as an optimality criterion, since for example, it cannot distinguish between different policies that all reach an absorbing goal state, but incur varying costs. A more selective criterion is bias optimality, which can filter gain-optimal policies to select those that reach absorbing goals with the minimum cost. While several ARL algorithms for computing gain-optimal policies have been proposed, none of these algorithms can guarantee bias optimality, since this requires solving at least two nested optimality equations. In this paper, we describe a novel model-based ARL algorithm for computing bias-optimal policies. We test the proposed algorithm using an admission control queuing system, and show that it is able to utilize the queue much more efficiently than a gain-optimal method by learning bias-optimal policies.
The National Science Foundation Workshop on Reinforcement Learning

Reinforcement learning has become one of the most actively studied learning frameworks in the area of intelligent autonomous agents. This article describes the results of a three-day meeting of leading researchers in this area that was sponsored by the National Science Foundation. Because reinforcement learning is an interdisciplinary topic, the workshop brought together researchers from a variety of fields, including machine learning, neural networks, AI, robotics, and operations research. Thirty leading researchers from the United States, Canada, Europe, and Japan, representing from many different universities, government, and industrial research laboratories participated in the workshop. The goals of the meeting were to (1) understand limitations of current reinforcement-learning systems and define promising directions for further research; (2) clarify the relationships between reinforcement learning and existing work in engineering fields, such as operations research; and (3) identify potential industrial applications of reinforcement learning.