Bounding the partition function is a key inference task in many graphical models. In this paper, we develop an anytime anyspace search algorithm taking advantage of AND/OR tree structure and optimized variational heuristics to tighten deterministic bounds on the partition function. We study how our priority-driven best-first search scheme can improve on state-of-the-art variational bounds in an anytime way within limited memory resources, as well as the effect of the AND/OR framework to exploit conditional independence structure within the search process within the context of summation. We compare our resulting bounds to a number of existing methods, and show that our approach offers a number of advantages on real-world problem instances taken from recent UAI competitions.

We show that the HyperPlay technique, which maintains a bag of updatable models for sampling an imperfect-information game, is more efficient than taking random samples of play sequences. Also, we demonstrate that random sampling may become impossible under the practical constraints of a game. We show the HyperPlay sample can become biased and not uniformly distributed across an information set and present a remedy for this bias, showing the impact on game results for biased and unbiased samples. We extrapolate the use of the technique beyond General Game Playing and in particular for enhanced security games with in-game percepts to facilitate a flexible defense response.

Kidney exchanges are organized markets where patients swap willing but incompatible donors. In the last decade, kidney exchanges grew from small and regional to large and national---and soon, international.  This growth results in more lives saved, but exacerbates the empirical hardness of the NP-complete problem of optimally matching patients to donors.  State-of-the-art matching engines use integer programming techniques to clear fielded kidney exchanges, but these methods must be tailored to specific models and objective functions, and may fail to scale to larger exchanges. In this paper, we observe that if the kidney exchange compatibility graph can be encoded by a constant number of patient and donor attributes, the clearing problem is solvable in polynomial time. We give necessary and sufficient conditions for losslessly shrinking the representation of an arbitrary compatibility graph. Then, using real compatibility graphs from the UNOS US-wide kidney exchange, we show how many attributes are needed to encode real graphs. The experiments show that, indeed, small numbers of attributes suffice.

The problem of ordering documents in a large collection into a sequence that is efficient for learning (both human and machine) is of high practical significance, but has not yet been well-formulated. We formulate this problem as mining a maximally informative simple sequence of documents. The mined sequence should be maximally informative in the sense that the reader learns quickly by reading only a few documents, and it should be simple so that the reader is not overwhelmed while trying to learn the content. The task can be posed as: Given that a reader wishes to read (at most) k documents, which documents should be selected from the repository and in what order, so as to provide maximum information. We present the WikiSeq algorithm for this purpose. We also design a metric based on information-gain to help objectively evaluate WikiSeq, and conduct experiments to compare with indicative baselines. Finally, we provide case-studies to subjectively illustrate WikiSeq’s merits.

We present the Utility Maximizing Design (UMD) model for optimally redesigning stochastic environments to achieve maximized performance. This model suits well contemporary applications that involve the design of environments where robots and humans co-exist an co-operate, e.g., vacuum cleaning robot. We discuss two special cases of the UMD model. The first is the equi-reward UMD (ER-UMD) in which the agents and the system share a utility function, such as for the vacuum cleaning robot. The second is the goal recognition design (GRD) setting, discussed in the literature, in which system and agent utilities are independent. To find the set of optimal modifications to apply to a UMD model, we present a generic method, based on heuristic search. After specifying the conditions for optimality in the general case, we present an admissible heuristic for the ER-UMD case. We also present a novel compilation that embeds the redesign process into a planning problem, allowing use of any off-the-shelf solver to find the best way to modify an environment when a design budget is specified. Our evaluation shows the feasibility of the approach using standard benchmarks from the probabilistic planning competition.

This paper deals with the constrained DAG shortest path problem (CDSP), which finds the shortest path on a given directed acyclic graph (DAG) under any logical constraints posed on taken edges. There exists a previous work that uses binary decision diagrams (BDDs) to represent the logical constraints, and traverses the input DAG and the BDD simultaneously. The time complexity of this BDD-based method is derived from BDD size, and tends to be fast only when BDDs are small. However, since it does not prioritize the search order, there is considerable room for improvement, particularly for large BDDs. We combine the well-known A* search with the BDD-based method synergistically, and implement several novel heuristic functions. The key insight here is that the ‘shortest path’ in the BDD is a solution of a relaxed problem, just as the shortest path in the DAG is. Experiments, particularly practical machine learning applications, show that the proposed method deceases search time by up to 2 orders of magnitude, with the specific result that it is 2,000 times faster than a commercial solver.

Stochastic search algorithms are black-box optimizer of an objective function. They have recently gained a lot of attention in operations research, machine learning and policy search of robot motor skills due to their ease of use and their generality. However, when the task or objective function slightly changes, many stochastic search algorithms require complete re-learning in order to adapt thesolution to the new objective function or the new context. As such, we consider the contextual stochastic search paradigm. Here, we want to find good parameter vectors for multiple related tasks, where each task is described by a continuous context vector. Hence, the objective function might change slightly for each parameter vector evaluation. In this paper, we investigate a contextual stochastic search algorithm known as Contextual Relative Entropy Policy Search (CREPS), an information-theoretic algorithm that can learn from multiple tasks simultaneously. We show the application of CREPS for simulated robotic tasks.

Symmetry-breaking is a technique for efficiently solving SAT instances that contain high degrees of symmetry among the variables of the instance. When satisfiability problems are represented as a relational schema, symmetries between objects in the domain can be detected directly from evidence, that is, variables known to have a particular setting prior to solving. These symmetries between domain objects are called term symmetries. In this work, we present two novel extensions to the technique of term equivalent symmetry breaking which allow the detection and exploitation of conditional or hidden symmetries, those relationships between domain objects that are obscured until the instance is partially solved. We give promising preliminary experimental results for this technique, and discuss how the techniques could be extended for use in probabilistic domains.

Learning approximate payoff functions is important to understand the dynamics in multi-player interactions. In general repeat games, each player's payoff can be represented as a combination of all other players' action choices using normal forms, which grow exponentially as the number of action choices increases. Graphical games, however, provide a compact representation to specify the inter-relations where one player's action choice is influenced by its neighbourhood. In this paper, we present how to learn players' approximate payoff functions from normal-form representations, yet also learn a compact graphical game representation of the inter-relations among the players. In this normal form representation, we explore the structural connections of mutual influence between players' action choices in game playing. We formally describe the problem of learning a player influence network and give a novel reward structure-learning algorithm for multiagent graphical games, called the Multi-Descendent Regression Learning Structure Algorithm (MDRLSA). We evaluate MDRLSA on random graphical games generated in GAMUT. Experiments show that MDRLSA can efficiently identify the independence among players and extract the influence graph accurately. The running time of MDRLSA increases linearly with the number of strategy profiles of a game. Compared with state-of-the-art graphical game model learning methods, MDRLSA shows efficiency in terms of time and accuracy.

Extensive-form games with imperfect recall are an important model of dynamic games where the players forget previously known information. Often, imperfect recall games are the result of an abstraction algorithm that simplifies a large game with perfect recall. Unfortunately, solving an imperfect recall game has fundamental problems since a Nash equilibrium does not have to exist. Alternatively, we can seek maxmin strategies that guarantee an expected outcome. The only existing algorithm computing maxmin strategies in imperfect recall games, however, requires approximating a bilinear program that is proportional to the size of the game and thus has a limited scalability. We propose a novel algorithm for computing maxmin strategies that combines this approximate algorithm with an incremental strategy-generation technique designed previously for extensive-form games with perfect recall. Experimental evaluation shows that the novel algorithm builds only a fraction of the game tree and improves the scalability by several orders of magnitude. Finally, we demonstrate that our algorithm can solve an abstracted variant of a large game faster compared to the algorithms operating on the unabstracted perfect-recall variant.