Policies for partially observable Markov decision processes are rich objects, prescribing actions to take depending on the whole history of observations and actions. Typical representations of such policies are by hyperplanes in the space of belief states, or by finite-state controllers, which are arguably not easy to interpret. We propose to redescribe policies into mappings defined on features of the current belief state, built in a systematic manner from state features. Such a mapping can in turn be represented by an intelligible object, like a decision tree, thereby providing an interpretable representation of the policy as a whole. We moreover show how our approach allows to explain the decision taken by an agent at each step of an interaction with the environment. This provides an end-to-end process, starting from a policy computed by any solver, and ending with an explanation of each decision made at execution time. We formally define our approach, investigate related computational problems, and report on experiments on several families of problems.

Extensive-form games model strategic interaction between players, with an emphasis on the sequential aspect of decision-making: players take turns to move until an ending is reached, and receive a reward according to which ending is reached. We study the complexity of computing the pure maxmin value for such games, i.e. the maximum reward that a player can guarantee by playing a pure strategy, whatever their opponents play. We focus on two-player and two-team games and perform a systematic study depending on the degree of imperfect information of each player or team: perfect information, perfect recall, or perfect recall for each agent in a team (which we call multi-agent perfect recall). For each combination, we settle the complexity of deciding whether the maxmin value is at least as high as a given threshold. We give a complete complexity picture for three orthogonal settings: games represented explicitly by their game tree; games represented compactly by game rules, for which we propose two new formalisms; games in which the set of strategies of the opponents is restricted to a known set of opponent models.

Games with incomplete information are games that model situations where players do not have common knowledge about the game they play, e.g. card games such as poker or bridge. Opponent models can be of crucial importance for decision-making in such games. We propose algorithms for computing optimal and/or robust strategies in games with incomplete information, given various types of knowledge about opponent models. As an application, we describe a framework for reasoning about an opponent's reasoning in such games, where opponent models arise naturally.

We define a new setting related to the evaluation of AND-OR directed acyclic graphs with partially ordered values. Such graphs arise naturally when solving games with incomplete information (e.g. most card games such as Bridge) or games with multiple criteria. In particular, this setting generalises standard AND-OR graph evaluation and computation of optimal strategies in games with complete information. Under this setting, we propose a new algorithm which uses both alpha-beta pruning and cached values. In this paper, we present our algorithm, prove its correctness, and give experimental results on a card game with incomplete information.

We consider sequential decision making problems under uncertainty, in which a user has a general idea of the task to achieve, and gives advice to an agent in charge of computing an optimal policy. Many different notions of advice have been proposed in somewhat different settings, especially in the field of inverse reinforcement learning and for resolution of Markov Decision Problems with Imprecise Rewards. Two key questions are whether the advice required by a specific method is natural for the user to give, and how much advice is needed for the agent to compute a good policy, as evaluated by the user. We give a unified view of a number of proposals made in the literature, and propose a new notion of advice, which corresponds to a user telling why she would take a given action in a given state. For all these notions, we discuss their naturalness for a user and the integration of advice. We then report on an experimental study of the amount of advice needed for the agent to compute a good policy. Our study shows in particular that continual interaction between the user and the agent is worthwhile, and sheds light on the pros and cons of each type of advice.

Qualitative Decentralized Partially Observable Markov Decision Problems (QDec-POMDPs) constitute a very general class of decision problems. They involve multiple agents, decentralized execution, sequential decision, partial observability, and uncertainty. Typically, joint policies, which prescribe to each agent an action to take depending on its full history of (local) actions and observations, are huge, which makes it difficult to store them onboard, at execution time, and also hampers the computation of joint plans. We propose and investigate a new representation for joint policies in QDec-POMDPs, which we call Multi-Agent Knowledge-Based Programs (MAKBPs), and which uses epistemic logic for compactly representing conditions on histories. Contrary to standard representations, executing an MAKBP requires reasoning at execution time, but we show that MAKBPs can be exponentially more succinct than any reactive representation.

We deal with online learning of acyclic Conditional Preference networks (CP-nets) from data streams, possibly corrupted with noise. We introduce a new, efficient algorithm relying on (i) information-theoretic measures defined over the induced preference rules, which allow us to deal with corrupted data in a principled way, and on (ii) the Hoeffding bound to define an asymptotically optimal decision criterion for selecting the best conditioned variable to update the learned network. This is the first algorithm dealing with online learning of CP-nets in the presence of noise. We provide a thorough theoretical analysis of the algorithm, and demonstrate its effectiveness through an empirical evaluation on synthetic and on real datasets.

We model a document treatment chain as a Markov Decision Process, and use reinforcement learning to allow the agent to learn to construct and continuously improve custom-made chains "on the fly". We build a platform which enables us to measure the impact on the learning of various models, web services, algorithms, parameters, etc. We apply this in an industrial setting, specifically to an open source document treatment chain which extracts events from massive volumes of web pages and other open-source documents. Our emphasis is on minimising the burden of the human analysts, from whom the agent learns to improve guided by their feedback on the events extracted. For this, we investigate different types of feedback, from numerical feedback, which requires a lot of tuning, to partially and even fully qualitative feedback, which is much more intuitive, and demands little to no user calibration. We carry out experiments, first with numerical feedback, then demonstrate that intuitive feedback still allows the agent to learn effectively.

The construction of exact exponential-time algorithms for NP-complete problems has for some time been a very active research area. Unfortunately, there is a lack of general methods for studying and comparing the time complexity of algorithms for such problems. We propose such a method based on clone theory and demonstrate it on the SAT problem. Schaefer has completely classified the complexity of SAT with respect to the set of allowed relations and proved that this parameterized problem exhibits a dichotomy: it is either in P or is NP-complete. We show that there is a certain partial order on the NP-complete SAT problems with a close connection to their worst-case time complexities; if a problem SAT(S) is below a problem SAT(S′) in this partial order, then SAT(S′) cannot be solved strictly faster than SAT(S). By using this order, we identify a relation R such that SAT({R}) is the computationally easiest NP-complete SAT(S) problem. This result may be interesting when investigating the borderline between P and NP since one appealing way of studying this borderline is to identify problems that, in some sense, are situated close to it (such as a ‘very hard’ problem in P or a ‘very easy’ NP-complete problem). We strengthen the result by showing that SAT({R})-2 (i.e. SAT({R}) restricted to instances where no variable appears more than twice) is NP-complete, too. This is in contrast to, for example, l-in-3-SAT (or even CNF-SAT), which is in P under the same restriction. We then relate SAT({R})-2 to the exponential-time hypothesis (ETH) and show that ETH holds if and only if SAT({R})-2 is not sub-exponential. This constitutes a strong connection between ETH and the SAT problem under both severe relational and severe structural restrictions, and it may thus serve as a tool for studying the borderline between sub-exponential and exponential problems. In the process, we also prove a stronger version of Impagliazzo et al.'s sparsification lemma for k-SAT; namely that all finite Boolean constraint languages S and S′ such that SAT(·) is NP-complete can be sparsified into each other. This should be compared with Santhanam and Srinivasan's recent negative result which states that the same does not hold for all infinite Boolean constraint languages.

Given a finite set of vectors over a finite totally ordered domain, we study the problem of computing a constraint in conjunctive normal form such that the set of solutions for the produced constraint is identical to the original set. We develop an efficient polynomial-time algorithm for the general case, followed by specific polynomial-time algorithms producing Horn, dual Horn, and bijunctive formulas for sets of vectors closed under the operations of conjunction, disjunction, and median, respectively. Our results generalize the work of Dechter and Pearl on relational data, as well as the papers by Hébrard and Zanuttini. They complement the results of Hähnle et al. on multivalued logics and Jeavons et al. on the algebraic approach to constraints.

Abduction is the process of explaining a given query with respect to some background knowledge. For instance, p is an explanation for the query q given the knowledge $p\rightarrow q$. This problem is well known to have many applications, particularly in artificial intelligence (AI), and has been widely studied from both an AI and a complexity-theoretic point of view. In this paper we completely classify the complexity of propositional abduction in Schaefer's famous framework. We consider the case where knowledge bases are taken from a class of formulas in generalized conjunctive normal form. This means that the propositional formulas considered are conjunctions of constraints taken from a fixed finite language. We show that according to the properties of this language, deciding whether at least one explanation exists is either polynomial, NP-complete, or $\Sigma_2 {\mathrm{P}}$-complete. Our results are stated for a query consisting of a single, positive literal and for assumption-based solutions, i.e., the solutions must be formed upon a distinguished subset of the variables that is part of the input. We show, however, that our results can be interpreted "dually" for negative queries, and thus also for unrestricted (positive or negative) queries.

We address the problem of propositional logic-based abduction, i.e., the problem of searching for a best explanation for a given propositional observation according to a given propositional knowledge base. We give a general algorithm, based on the notion of projection; then we study restrictions over the representations of the knowledge base and of the query, and find new polynomial classes of abduction problems.