Plan monitoring in a collaborative multi-agent system requires an agent to not only monitor the execution of its own plan, but also to detect possible deviations or failures in the plan execution of its teammates. In domains featuring partial observability and uncertainty in the agents’ sensing and actuation, especially where communication among agents is sparse (as a part of a cost-minimized plan), plan monitoring can be a significant challenge. We design an Expectation Maximization (EM) based algorithm for detection of plan deviation of teammates in such a multi-agent system. However, a direct implementation of this algorithm is intractable, so we also design an alternative approach grounded on the agents’ plans, for tractability. We establish its equivalence to the intractable version, and evaluate these techniques in some challenging tasks.

Reinforcement learning (RL) is designed to learn optimal control policies from unsupervised interactions with the environment. Many successful RL algorithms have been developed, however, none of them can efficiently tackle problems with high-dimensional state spaces due to the "curse of dimensionality," and so their applicability to real-world scenarios is limited. Here we propose a Sample Aware Feature Selection algorithm embedded in NEAT, or SAFS-NEAT, to help address this challenge. This algorithm builds upon the powerful evolutionary policy search algorithm NEAT, by exploiting data samples collected during the learning process. This data permits feature selection techniques from the supervised learning domain to be used to help RL scale to problems with high-dimensional state spaces. We show that by exploiting previously observed samples, on-line feature selection can enable NEAT to learn near optimal policies for such problems, and also outperform an existing feature selection algorithm which does not explicitly make use of this available data.

Autonomous agents are emerging in diverse areas and many rely on reinforcement learning (RL) to learn optimal control policies by acting in the environment. This form of learning generates large amounts of transition dynamics data, which can be mined to improve the agent's understanding of the environment. There could be many uses for this data, here we focus on mining it to identify a relevant feature subspace. This is vital since RL performs poorly in high-dimensional spaces, such as those that autonomous agents would commonly face in real-world problems. This paper demonstrates the necessity and feasibility of integrating data mining into the learning process while an agent is learning, enabling it to learn to act by both acting and understanding. Doing so requires overcoming challenges regarding data quantity and quality, and difficulty measuring feature relevance with respect to the control policy. We propose the progressive mining framework to address these challenges by relying on cyclic interaction between data mining and RL. We show that a feature selection algorithm developed under this framework, PROFESS, can improve RL scalability better than a competing approach.

Stability is an important yet under-addressed issue in feature selection from high-dimensional and small sample data. In this paper, we show that stability of feature selection has a strong dependency on sample size. We propose a novel framework for stable feature selection which first identifies consensus feature groups from subsampling of training samples, and then performs feature selection by treating each consensus feature group as a single entity. Experiments on both synthetic and real-world data sets show that an algorithm developed under this framework is effective at alleviating the problem of small sample size and leads to more stable feature selection results and comparable or better generalization performance than state-of-the-art feature selection algorithms. Synthetic data sets and algorithm source code are available at http://www.cs.binghamton.edu/~lyu/KDD09/.

Many feature selection algorithms have been proposed in the past focusing on improving classification accuracy. In this work, we point out the importance of stable feature selection for knowledge discovery from high-dimensional data, and identify two causes of instability of feature selection algorithms: selection of a minimum subset without redundant features and small sample size. We propose a general framework for stable feature selection which emphasizes both good generalization and stability of feature selection results. The framework identifies dense feature groups based on kernel density estimation and treats features in each dense group as a coherent entity for feature selection. An efficient algorithm DRAGS (Dense Relevant Attribute Group Selector) is developed under this framework. We also introduce a general measure for assessing the stability of feature selection algorithms. Our empirical study based on microarray data verifies that dense feature groups remain stable under random sample hold out, and the DRAGS algorithm is effective in identifying a set of feature groups which exhibit both high classification accuracy and stability.