Citation: This work considers how the structure of an explicitly-described reward function can be exploited to support efficient learning. This important setting has so far been under-explored; reward functions are typically expert-designed and therefore contain structure that most existing work ignores. The article proposes representing such a structure using a reward machine, a richly expressive type of finite-state machine; it also describes several powerful and effective methodologies to exploit the resulting structure. This article is the culmination of an influential line of research that bridges and enriches three different communities: AI planning, reinforcement learning, and formal methods.

 

Citation: This paper presents the state-of-the-art results in online POMDP planning. It offers both theoretical proofs and empirical evaluations to justify the claims presented by the authors. Online POMDP solving is one of the more popular problems recently, and DESPOT is considered as one of the top choices in this direction. Since its publication, the paper has been employed for solving problems in applications including human-robot collaboration tasks and autonomous driving, as well as in fundamental research in hybrid POMDPs.

 

Citation: This paper makes an important contribution to AI, namely one of the first end-to-end differentiable approaches to inductive logic programming (ILP). The approach taken is elegant and extends ILP beautifully to the differentiable domain, paving the way to bridging both logical and deep (neural) learning. Since its publications, the work has inspired a lot of follow ups, and the idea described therein, namely differentiable deduction through forward chaining on definite clauses has been demonstrated to have profound impact on making symbolic systems more robust and neural systems more understandable. In addition, the paper gives new emphasis and impulse to neuro-symbolic AI and, in turn, to the System 1 and System 2 debate in psychology, cognitive science, and AI.

 

Citation: This paper elegantly shows how to automatically construct abstract representations suitable for evaluating plans composed of sequences of high-level actions in a continuous, low-level environment. This follows a long tradition in AI of structuring agent control architectures around procedural abstraction, i.e., grounded abstract symbolic representation, establishing a principled link between high-level actions and abstract representations along with a theoretical foundation for constructing abstract representations with provable properties and a practical mechanism for autonomously learning abstract high-level representations.

 

Citation: This paper introduces a novel learning paradigm that lies between traditional online learning, where the utilities of each action are visible to the algorithm, and bandit settings, where the utilities of only the optimal action are observed. It presents very solid theoretical results, showing upper bounds on expected regret, as well as an extensive experimental evaluation of a number of algorithms implementing the approach on real-world scenarios.

 

Citation: This paper describes fundamental and practical results on a range of clause elimination procedures as preprocessing and simplification techniques for SAT and QBF solvers. Since its publication, the techniques described therein have been demonstrated to have profound impact on the efficiency of state-of-the-art SAT and QBF solvers. The work is elegant and extends beautifully some well-established theoretical concepts. In addition, the paper gives new emphasis and impulse to pre- and in-processing techniques - an emphasis that resonates beyond the two key problems, SAT and QBF, covered by the authors.

 

Citation: This article deals with the problem of associating images with natural language sentences that describe what is depicted in them. It specifically considers the task of associating images with sentences drawn from a large, predefined pool of image descriptions, and introduces a benchmark collection for sentence-based image description and search that has since become widely used within the community. The authors describe and thoroughly evaluate several image description algorithms and demonstrate that image features capturing only low-level perceptual properties can work surprisingly well in cases where no in-domain detectors are available. In their empirical evaluation, they consider different metrics for the quality of single image-caption pairs. Automatically computed scores are also compared with detailed human judgments.

 

The work is recognised for its thorough empirical treatment of an interesting problem at the intersection of computer vision and natural language processing, and for its lasting impact on the literature in this area. It clearly demonstrates the value of carefully designed benchmark sets and computational experiments. Overall, this article serves as an excellent example for high-quality and impactful empirical work in AI.

Citation: This paper describes a procedure for constructing word representations using text- and image-based distributional information. This has been a fundamental and innovative contribution in the area of natural language and vision. Another key contribution is the data set, which has since been used extensively. This work is recognised for its impact within multiple areas in AI, including NLP, Vision, and Machine Learning, and for its seminal role in the introduction of a multimodal perspective in distributional semantics models for computational representations of word meaning.

Citation: This paper combines classical planning over a domain model with reasoning over continuous change - a challenging topic of high relevance within the AI community as well as for real-world applications, including energy management, chemical engineering and robotics. It introduces a concrete instantiation of what has since become the dominant approach for temporal hybrid planning, by effectively combining heuristic search with an external numeric reasoner such as a linear program solver. This work is recognised for its impact within AI planning and beyond, and for its seminal role in the development of hybrid discrete-continuous planning techniques.

Citation: This article presents a core AI result in computational social choice using automatic theorem proving techniques, by studying axioms that relate preferences over individual objects with preferences over sets of objects. These axioms are represented as formulae in a many-sorted first-order-logic that are then mapped into propositional logic formulae amenable and tackled using a SAT solver. A key contribution of the paper is a result showing that inconsistencies found for a fixed domain size can be extended to larger domains, leading to an impossibility theorem. Using this approach, the authors verify a number of known theorems and discover several new ones. Overall, the contributions made in this work are of considerable importance for computational social choice and for AI in general; they include: (i) a practical automatic method for theorem search, (ii) the verification of a number of well-known theorems, and (iii) the automatic discovery of several new and non-trivial impossibility theorems in social choice.

Citation: This paper gives a comprehensive description and analysis of the award winning LAMA planner. LAMA's use of landmarks in combination with cost-sensitive heuristics is presented, and the performance of the planner in different configurations is evaluated and analyzed in a detailed and insightful experimental study. This excellently written paper has been very influential and has helped to establish the use of landmarks as a key technique in classical planning.

Citation: This paper demonstrates how contextual word meaning can be represented in a high-dimensional space of concepts derived from encyclopedic knowledge bases such as Wikipedia. A key insight is that the set of target documents provided for a semantic analysis task is normally insufficient; knowledge from publicly available resources, such as Wikipedia, allow much finer-grained representations of contextual word meaning to be recovered, which can significantly improve the quality of text categorization and assessments of semantic relatedness. This work represents one of the earliest and most influential investigations of using large-scale encyclopedic resources for extracting meaning representations---an idea that now lies at the heart of much work in natural language processing and information retrieval.

Citation: This paper investigates the possibility of designing reinforcement learning agents based on a direct approximation of AIXI, a Bayesian notion of optimality in uncertain sequential decision making environments. Although it had been unclear whether AIXI could provide a practical foundation for designing learning agents, this paper demonstrates the first plausible realization of an AIXI agent by exploiting Monte Carlo tree search and context tree weighting algorithms. The paper presents a bold and original perspective on the difficult problem of partially observable reinforcement learning, while demonstrating impressive results on a range of applications.