We consider a strategic variant of the facility location problem. We would like to locate a facility on a closed interval. There are n agents located on that interval, divided into two types: type 1 agents, who wish for the facility to be as far from them as possible, and type 2 agents, who wish for the facility to be as close to them as possible. Our goal is to maximize a form of aggregated social benefit: maxisum– the sum of the agents’ utilities, or the egalitarian objective– the minimal agent utility. The strategic aspect of the problem is that the agents’ locations are not known to us, but rather reported to us by the agents– an agent might misreport his location in an attempt to move the facility away from or towards to his true location. We therefore require the facility-locating mechanism to be strategyproof, namely that reporting truthfully is a dominant strategy for each agent. As simply maximizing the social benefit is generally not strategyproof, our goal is to design strategyproof mechanisms with good approximation ratios. In this paper, we provide a best-possible 3approximate deterministic strategyproof mechanism, as well as a 23/13 approximate randomized strategyproof mechanism, both for the maxisum objective. We provide lower bounds of 3 and 3/2 on the approximation ratio attainable for maxisum, in the deterministic and randomized settings, respectively. For the egalitarian objective, we show that no bounded approximation ratio is attainable in the deterministic setting, and provide a lower bound of 3/2 for the randomized setting. To obtain our deterministic lower bounds, we characterize all deterministic strategyproof mechanisms when all agents are of type 1. Finally, while still restricting ourselves to agents of type 1 only, we consider a generalized model that allows an agent to control more than one location. In this generalized model, we provide best-possible 3and 3 approximate strategyproof 2 mechanisms for the maxisum objective in the deterministic and randomized settings, respectively.

Answering point-to-point distance queries is important inmany applications, including games, robotics and vehiclerouting in operations research. Searching in a graph to answer distance queries on demandcan often be too slow.An alternative strategy, taken in methods such asTransit and Hub Labels, is to pre-compute information that can help computedistances much faster.To be practical, such methods need to generate muchless preprocessed data than a naive all-pairs distance table. We present Heuristic-Aid Compressed Distance Databases (HCDs),pre-computed data structures based on the observation thatheuristic distance estimations can sometimes coincide with true distances.Compared to a naive all-pairs distance table,we report compression factors of two to three orders of magnitude in a wide range ofmaps, reducing the memory usage to a reasonable size. Comparedto compressed path databases, our approachgenerally generates smaller databases, and answers query distances faster.

This article discusses the notion of context transfer in reinforcement learning tasks. Context transfer, as defined in this article, implies knowledge transfer between tasks that share the same environment's dynamics and reward function, but have different state and action spaces. For example, we have a working mobile robot in an environment. At some point, we decide to upgrade its sensors and/or actuators. Any change in these modules will result in a different description of the agent-environment model, and the trained knowledge is no longer applicable. We consider the tasks of the old and new robots, as the source and target tasks, respectively. The Markov decision process (MDP) of these tasks, under certain conditions, are called Q-transferable tasks, and the problem of knowledge transfer between them is called context transfer. We investigate the relation of the MDPs of these tasks.

Solving games of imperfect information with linear programming took a significant leap forward when Koller, Megiddo, and Stengel (KMS) proposed an exponentially more compact way to represent two-player games of imperfect information as linear programs. Despite this substantial advancement many recent works on solving these games rely on Counter Factual Regret Minimization (CFR) as opposed to linear programming. One reason CFR became a standard approach is that CFR is easily parallelizable whereas the linear program defined by KMS's technique is difficult to solve in parallel. Convenient parallelism made CFR more amenable to multi-core computing environments and large games. This paper presents a method to parallelize the linear programing techniques of KMS. The proposed iterative method divides a potentially intractable linear program representing a large game of imperfect information into many smaller linear programs. Each of the smaller LPs can be processed independently and in parallel. It is shown that the solutions to the smaller LPs interact together over multiple iterations of this algorithm to produce a strategy pair that converges to the Nash Equilibrium solution to the original undivided problem. This is the first work to propose a Dantzig-Wolfe style decomposition for solving two-player games of imperfect information.

Skills are generally designed by a domain expert, but designing a `good' set of skills can be challenging in high-dimensional, complex domains. In some cases, the skills may contain useful prior knowledge but cannot solve the task, resulting in a sub-optimal solution or no solution at all. Given a `poor' set of skills, we would like to dynamically improve them. The main contribution of this paper is showing that Interrupting Options (IO) can improve the initial skill set in a high-dimensional, complex domain by learning when to switch between skills. Furthermore, we discuss some of the pitfalls we ran into while trying to get IO to work.

The paper explores the potential of weighted best-first search schemes as anytime optimization algorithms for solving graphical models tasks such as MPE (Most Probable Explanation) or MAP (Maximum a Posteriori) and WCSP (Weighted Constraint Satisfaction Problem). While such schemes were widely investigated for path-finding tasks, their application for graphical models was largely ignored, possibly due to their memory requirements. Compared to the depth-first branch and bound, which has long been the algorithm of choice for optimization in graphical models, a valuable virtue of weighted best-first search is that they are w-optimal, i.e. when terminated, they return a solution cost C and a weight w, such that C < = wC*, where C* is the optimal cost. We report on a significant empirical evaluation, demonstrating the usefulness of weighted best-first search as approximation anytime schemes (that have suboptimality bounds) and compare against one of the best depth-first branch and bound solver to date. We also investigate the impact of different heuristic functions on the behaviour of the algorithms.

We carry out an empirical study of classification-based policy iteration (CBPI) in a simplified Markovian Decision Process (MDP). In this simple MDP, we expose some pathological cases where variance in state-action value estimates can degrade the performance of CBPI to the point of complete ineffectiveness. In particular, it is shown that with enough variance in the returns, e.g., if we estimate state-action values with a single rollout, CBPI drifts away from the/an optimal policy over iterations, even when the optimal policy is its initial policy to iterate over. From our investigation we also arrived at a natural cost-sensitive classification problem where the costs are noisy, a problem which to the best of our knowledge has not been studied in the classification literature.

Contract bridge is an example of an incomplete information game for which computers typically do not perform better than expert human bridge players. In particular, the typical bidding decisions of human bridge players are difficult to mimic with a computer program, and thus automatic bridge bidding remains to be a challenging research problem. Currently, the possibility of automatic bidding without mimicking human players has not been fully studied. In this work, we take an initiative to study such a possibility for the specific problem of bidding without competition. We propose a novel learning framework to let a computer program learn its own bidding decisions. The framework transforms the bidding problem into a learning problem, and then solves the problem with a carefully designed model that consists of cost-sensitive classifiers and upper-confidence-bound algorithms. We validate the proposed model and find that it performs competitively to the champion computer bridge program that mimics human bidding decisions.

This paper outlines a new approach to creating value from the Smart Grid by incorporating individual households into the response system that must be deployed to accommodate increasingly large sources of intermittent renewable power. We propose a framework that couples agent-based AI techniques with envelope methods. Envelope methods provide a unified mathematical framework to model intermittent renewable resources, conventional dispatchable resources, demand side response, and storage. The overall goal of our system is to develop a distributed autonomous agent architecture that is able to facilitate market transactions among load serving entities, residential consumers, conventional merchant power producers, and intermittent power producers.

We show that setting a reasonable frame skip can be critical to the performance of agents learning to play Atari 2600 games. In all of the six games in our experiments, frame skip is a strong determinant of success. For two of these games, setting a large frame skip leads to state-of-the-art performance.