nils-herrmann/clean_scirepeval huggingface dataset:
11 Hierarchical Approaches to Concurrency , Multiagency , and Partial Observability

ion level: traversal abstraction level: primitiveion level: primitive Fig. 11.13 A hierarchical suffix memory state estimator for a robot navigation task. At the abstract (navigation) level, observations and decisions occur at intersections. At the lower (corridor-traversal) level, observations and decisions occur within the corridor. At each level, each agent constructs states out of its past experience with similar history (shown with shadows). Partially observable MDPs are theoretically more powerful than finite memory models, but past work on POMDPs has mostly studied “flat” models for which learning and planning algorithms scale poorly with model size. We have developed a newhierarchical POMDPframework termed H-POMDPs  , by extending the hierarchical hidden Markov model (HHMM)  to include rewards, multiple entry/exit points into abstract states and (temporally extended) actions. H-POMDPs can also be represented as Dynamic Bayesian networks [43], in a similar way that HHMMs can be represented as DBNs [23]. Figure 11.15 shows a Dynamic Bayesian net representation of H-POMDPs. This model differs from the CONCURRENCY, MULTIAGENCY, AND PARTIAL OBSERVABILITY 303 Fig. 11.14 State transition diagram of a hierarchical POMDP used to model corridor environments. Large ovals represent abstract states; the small solid circles within them represent entry states, and the small hollow circles represent exit states. The small circles with arrows represent production states. Arcs represent non-zero transition probabilities as follows: Dotted arrows from concrete states represent concrete horizontal transitions, dashed arrows from exit states represent abstract horizontal transitions, and solid arrows from entry states represent vertical transitions. model described in  in two basic ways: the presence of action nodes A, and the fact that exit nodesX are no longer binary.
Extraction of Key Words from News Stories

In this work, we consider the task of extracting key-words such as key-players, key-locations, key-nouns and key-verbs from news stories. We cast this problem as a classification problem wherein we assign appropriate labels to each word in a news story. We considered statistical models such as naive Bayes model, hidden Markov model and maximum entropy model in our work. We have also experimented with various features. Our results indicate that a maximum entropy model that ignores contextual features and considers only word-based features combined with stopping and stemming yields the best performance. We found that extraction of keyverbs and key-nouns is a much harder problem than extracting keyplayers and key-locations.
Learning hierarchical models of activity

This paper investigates learning hierarchical statistical activity models in indoor environments. The abstract hidden Markov model (AHMM) is used to represent behaviors in stochastic environments. We train the model using both labeled and unlabeled data and estimate the parameters using expectation maximization (EM). Results are shown on three datasets: data collected in lab, entryway, and home environments. The results show that hierarchical models outperform flat models.
Average reward reinforcement learning: Foundations, algorithms, and empirical results

This paper presents a detailed study of average reward reinforcement learning, an undiscounted optimality framework that is more appropriate for cyclical tasks than the much better studied discounted framework. A wide spectrum of average reward algorithms are described, ranging from synchronous dynamic programming methods to several (provably convergent) asynchronous algorithms from optimal control and learning automata. A general sensitive discount optimality metric calledn-discount-optimality is introduced, and used to compare the various algorithms. The overview identifies a key similarity across several asynchronous algorithms that is crucial to their convergence, namely independent estimation of the average reward and the relative values. The overview also uncovers a surprising limitation shared by the different algorithms while several algorithms can provably generategain-optimal policies that maximize average reward, none of them can reliably filter these to producebias-optimal (orT-optimal) policies that also maximize the finite reward to absorbing goal states. This paper also presents a detailed empirical study of R-learning, an average reward reinforcement learning method, using two empirical testbeds: a stochastic grid world domain and a simulated robot environment. A detailed sensitivity analysis of R-learning is carried out to test its dependence on learning rates and exploration levels. The results suggest that R-learning is quite sensitive to exploration strategies and can fall into sub-optimal limit cycles. The performance of R-learning is also compared with that of Q-learning, the best studied discounted RL method. Here, the results suggest that R-learning can be fine-tuned to give better performance than Q-learning in both domains.
Learning to Communicate and Act in Cooperative Multiagent Systems using Hierarchical Reinforcement Learning

In this paper, we address the issue of rational communication behavior among autonomous agents. We extend our previously reported cooperative hierarchical reinforcement learning (HRL) algorithm to include communication decision and propose a new multiagent HRL algorithm, called COM-Cooperative HRL. In this algorithm, at specific levels of the hierarchy, called cooperation levels, a group of subtasks, in which coordination among agents has significant effect on the performance of the overall task, are defined as cooperative subtasks. Coordination skills among agents are learned faster by sharing information at cooperation levels, rather than the level of primitive actions. We add a communication level to the hierarchical decomposition of the problem, below each cooperation level. A communication action has a certain cost and is used by each agent to obtain the actions selected by the cooperative subtasks of the other agents. Before making a decision at a cooperative subtask, agents decide if it is worthwhile to perform a communication action in order to acquire the actions chosen by the cooperative subtasks of the other agents. Using this algorithm, agents learn a policy to balance the amount of communication needed for proper coordination, and communication cost. We demonstrate the efficacy of the COM-Cooperative HRL algorithm as well as the relation between communication cost and the learned communication policy, using a multiagent taxi
Coarticulation in Markov Decision Processes

We investigate an approach for simultaneously committing to multiple activities, each modeled as a temporally extended action in a semi-Markov decision process (SMDP). For each activity we define a set of admissible solutions consisting of the redundant set of optimal policies, and those policies that ascend the optimal state-value function associated with them. A plan is then generated by merging them in such a way that the solutions to the subordinate activities are realized in the set of admissible solutions satisfying the superior activities. We present our theoretical results and empirically evaluate our approach in a simulated domain.
Learning to communicate and act using hierarchical reinforcement learning

In this paper, we address the issue of rational communication behavior among autonomous agents. The goal is for agents to learn a policy to optimize the communication needed for proper coordination, given the communication cost. We extend our previously reported cooperative hierarchical reinforcement learning (HRL) algorithm to include communication decisions and propose a new multiagent HRL algorithm, called COM-Cooperative HRL. In this algorithm, we define cooperative subtasks to be those subtasks in which coordination among agents significantly improves the performance of the overall task. Those levels of the hierarchy which include cooperative subtasks are called cooperation levels. Coordination skills among agents are learned faster by sharing information at the cooperation levels, rather than the level of primitive actions. We add a communication level to the hierarchical decomposition of the problem below each cooperation level. Before making a decision at a cooperative subtask, agents decide if it is worthwhile to perform a communication action. A communication action has a certain cost and provides each agent at a certain cooperation level with the actions selected by the other agents at the same level. We demonstrate the efficacy of the COM-Cooperative HRL algorithm as well as the relation between the communication cost and the learned communication policy using a multiagent taxi domain.
Hierarchical Policy Gradient Algorithms

Hierarchical reinforcement learning is a general framework which attempts to accelerate policy learning in large domains. On the other hand, policy gradient reinforcement learning (PGRL) methods have received recent attention as a means to solve problems with continuous state spaces. However, they suffer from slow convergence. In this paper, we combine these two approaches and propose a family of hierarchical policy gradient algorithms for problems with continuous state and/or action spaces. We also introduce a class of hierarchical hybrid algorithms, in which a group of subtasks, usually at the higher-levels of the hierarchy, are formulated as value function-based RL (VFRL) problems and the others as PGRL problems. We demonstrate the performance of our proposed algorithms using a simple taxi-fuel problem and a complex continuous state and action ship steering domain.
Extending Hierarchical Reinforcement Learning to Continuous-Time, Average-Reward, and Multi-Agent Models

Hierarchical reinforcement learning (HRL) is a general framework that studies how to exploit the structure of actions and tasks to accelerate policy learning in large domains. Prior work on HRL has been limited to the discrete-time discounted reward semi-Markov decision process (SMDP) model. In this paper we generalize the setting of HRL to average-reward, continuous-time and multi-agent SMDP models. We also describe experimental results from a large-scale real-world domain, attesting to the bene ts of HRL generally, and to our extensions more speci cally. Although in principle any HRL framework could su ce, we focus in this paper on the MAXQ framework. We describe three new hierarchical reinforcement learning algorithms: continuous-time discounted reward MAXQ, discrete-time average reward MAXQ, and continuous-time average reward MAXQ. We also investigate the use of hierarchical reinforcement learning to speed up the acquisition of cooperative multiagent tasks. We extend the MAXQ framework to the multiagent case which we term cooperative MAXQ, where each agent uses the same task hierarchy. 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. We use two experimental testbeds to study the empirical performance of our proposed extensions. One domain is a simulated robot trash collection task. The other domain is a much larger real-world multi-agent autonomous guided vehicle (MAGV) problem. We compare the performance of our proposed algorithms with each other, as well as with the original MAXQ method and to standard Q-learning. In the MAGV domain, we show that our proposed extensions outperform widely used industrial heuristics, such as first come first serve", "highest queue first" and "nearest station first".
Hierarchically Optimal Average Reward Reinforcement Learning

Two notions of optimality have been explored in previous work on hierarchical reinforcement learning (HRL): hierarchical optimality, or the optimal policy in the space defined by a task hierarchy, and a weaker local model called recursive optimality. In this paper, we introduce two new average-reward HRL algorithms for finding hierarchically optimal policies. We compare them to our previously reported algorithms for computing recursively optimal policies, using a grid-world taxi problem and a more real-world AGV scheduling problem. The new algorithms are based on a three-part value function decomposition proposed recently by Andre and Russell, which generalizes Dietterich’s MAXQ value function decomposition. A key difference between the algorithms proposed in this paper and our previous work is that there is only a single global gain (average reward), instead of a gain for each subtask. Our results show the new average-reward algorithms have better performance than both the previous recursively optimal counterparts, as well as the corresponding discounted hierarchical optimal algorithms.
Machine Learning for Robots A Comparison of Di erent Paradigms

For robots to be truly exible they need to be able to learn to adapt to partially known or dynamic environments to teach themselves new tasks and to compensate for sensor and e ector defects The problem of robot learning has been an intensively stud ied research topic over the last decade In this paper we critically examine four major formulations of the robot learning problem inductive concept learning explanation based learning reinforcement learning and evolutionary learning We describe some well known examples of systems that t under each formulation and discuss their strengths and limitations
A multiagent reinforcement learning algorithm by dynamically merging markov decision processes

One general strategy for accelerating the learning of cooperative multiagent problems is to reuse good or optimal solutions to the task when each agent is acting alone. In this paper, we formalize this approach as dynamically merging solutions to multiple Markov decision processes (MDPs), each representing an individual agent's solution when acting alone, to obtain solutions to the overall multiagent MDP when all the agents act together. We present a new learning algorithm called MAPLE (MultiAgent Policy LEarning) that uses Q-learning and dynamic merging to efficiently construct global solutions to the overall multiagent problem from solutions to the individual MDPs. We illustrate the efficiency of MAPLE by comparing its performance with standard Q-learning applied to the overall multiagent MDP.
STUDENT PAPER : A Multiagent Reinforcement Learning Algorithm by Dynamically Merging Markov Decision Processes

One general strategy for a elerating the learning of ooperative multiagent tasks is to reuse (good or optimal) solutions to the task when ea h agent is a ting alone. In this paper, we formalize this approa h as dynami ally merging solutions to multiple Markov de ision pro esses (MDPs), ea h representing an individual agent's solution when a ting alone, to obtain (good or optimal) solutions to the overall multiagent MDP when all the agents a t together. We present a new temporal-di eren e learning algorithm alled MAPLE (MultiAgent Poli y LEarning) that uses Q-learning and dynami merging to e iently onstru t global solutions to the overall multiagent problem from solutions to the individual MDPs. We illustrate the e ien y of MAPLE by omparing its performan e with standard Q-learning applied to the overall multiagent MDP. We also des ribe a orresponding planning algorithm that, given omplete knowledge of the underlying single agent MDPs, uses dynami merging to efiently solve the multiagent MDP. We also illustrate how the dynami merging framework an be extended to the ase when agents use temporally extended a tions, by using semiMarkov de ision pro esses (SMDPs) to represent variablelength de ision epo hs.
Spatiotemporal Abstraction of Stochastic Sequential Processes

Probabilistic finite state machines have become a popular modelingto ol for representing sequential processes, ranging from images and speech signals to text documents and spatial and genomic maps. In this paper, I describe two hierarchical abstraction mechanisms for simplifyingthe (estimation) learningand (control) optimization of complex Markov processes: spatial decomposition and temporal aggregation. I present several approaches to combiningspatial and temporal abstraction, drawingup on recent work of my group as well as that of others. I show how spatiotemporal abstraction enables improved solutions to three difficult sequential estimation and decision problems: hidden state modelingand control, learningparallel plans, and coordinatingwith multiple agents.
Learning the hierarchical structure of spatial environments using multiresolution statistical models

We explore the use of hierarchical Partially Observable Markov Decision Process (HPOMDP) models to represent and learn a multiresolution spatial structure representation of indoor office environments. The hierarchical POMDP model is based on the hierarchical Hidden Markov Model (HHMM). HPOMDPs can be learned from sequences of observations using an extension of the hierarchical Baum-Welch estimation algorithm for HHMMs. We apply the HPOMDP model to indoor robot navigation and show how this framework can be used to represent multiresolution spatial maps. In the HPOMDP framework the environment is modeled at different levels of resolutions where abstract states represent both spatial and temporal abstraction. We test our hierarchical POMDP approach using a large simulated (modeled after a real environment) navigation environment. The results show that the hierarchical POMDP model is more capable in inferring the spatial structure than a uniform resolution "flat" POMDP.
Hierarchical learning and planning in partially observable markov decision processes

Sequential decision making under uncertainty is a fundamental problem in artificial intelligence. This problem is faced by autonomous agents embedded in complex environments (e.g., physical systems, including robots, softbots, and automated manufacturing systems) that need to choose actions to achieve long-term goals efficiently. Incomplete knowledge about the state of the environment, termed as hidden state, and the uncertain effects of their actions, makes sequential decision making difficult. 
Partially Observable Markov Decision Processes (POMDPs) are a general framework for sequential decision making in environments where states are hidden and actions are stochastic. A POMDP model represents the dynamics of the environment, such as the probabilistic outcomes of the actions, and the probabilistic relationships between the agents observations and the hidden states. Unfortunately, “learning” the dynamics of the environment, and planning, scales poorly as the application domains get larger. 
In this dissertation, we propose and investigate a Hierarchical POMDP (HPOMDP) model to scale learning and planning to large scale partially observable environments. In scaling planning, the key ideas are spatial and temporal abstraction. In spatial abstraction, grouping of lower level states into abstract higher level states reduces uncertainty of the agent. In temporal abstraction, the agent uses longer-duration actions instead of just primitive one-step actions. Macro-actions are crucial, in that they produce long traces of experience, which help the agent to disambiguate perceptually aliased situations. In scaling learning, the main advantage of hierarchy is that a multi-resolution problem representation has advantages in ease of maintenance, interpretability, and reusability. We investigate the new HPOMDP framework within the context of indoor robot navigation. 
This dissertation makes the following principal contributions. We formally introduce and describe the HPOMDP model. We derive a hierarchical EM algorithm for learning the parameters of a given HPOMDP, and show empirical convergence. We introduce two approximate training methods, “reuse-training”, and “selective-training”, which result in fast training and better learned models. We also derive two planning algorithms for approximating the optimal policy for a given HPOMDP. We conduct a detailed experimental study of the learning algorithms for indoor robot navigation, and show how the robot localization improves with our learning methods. We also apply the planning algorithms to indoor robot navigation, both in simulation and in the real world. The results show that the planning algorithms are very successful in taking the robot to any environment state starting from no positional knowledge, and use significantly less number of steps than flat approaches.
Approximate planning with hierarchical partially observable Markov decision process models for robot navigation

We propose and investigate a planning framework based on the hierarchical partially observable Markov decision process model (HPOMDP), and apply it to robot navigation. We show how this framework can be used to produce more robust plans as compared to flat models such as partially observable Markov decision processes (POMDPs). In our approach the environment is modeled at different levels of resolution, where abstract states represent both spatial and temporal abstraction. We test our hierarchical POMDP approach using a large simulated and real navigation environment. The results show that the robot is more successful in navigating to goals starting with no positional knowledge (uniform initial belief state distribution) using the hierarchical POMDP framework as compared to the flat POMDP approach.
Decision-Theoretic Planning with Concurrent Temporally Extended Actions

We investigate a model for planning under uncertainty with temporally extended actions, where multiple actions can be taken concurrently at each decision epoch. Our model is based on the options framework, and combines it with factored state space models, where the set of options can be partitioned into classes that affect disjoint state variables. We show that the set of decision epochs for concurrent options defines a semi-Markov decision process, if the underlying temporally extended actions being parallelized are restricted to Markov options. This property allows us to use SMDP algorithms for computing the value function over concurrent options. The concurrent options model allows overlapping execution of options in order to achieve higher performance or in order to perform a complex task. We describe a simple experiment using a navigation task which illustrates how concurrent options results in a more optimal plan when compared to the case when only one option is taken at a time.
A reinforcement learning model of selective visual attention

This paper proposes a model of selective attention for visual search tasks, based on a framework for sequential decision-making. The model is implemented using a fixed pan-tilt-zoom camera in a visually cluttered lab environment, which samples the environment at discrete time steps. The agent has to decide where to fixate next based purely on visual information, in order to reach the region where a target object is most likely to be found. The model consists of two interacting modules. A reinforcement learning module learns a policy on a set of regions in the room for reaching the target object, using as objective function the expected value of the sum of discounted rewards. By selecting an appropriate gaze direction at each step, this module provides top-down control in the selection of the next fixation point. The second module performs “within fixation” processing, based exclusively on visual information. Its purpose is twofold: to provide the agent with a set of locations of interest in the current image, and to perform the detection and identification of the target object. Detailed experimental results show that the number of saccades to a target object significantly decreases with the number of training epochs. The results also show the learned policy to find the target object is invariant to small physical displacements as well as object inversion.