The task of computing approximate Nash equilibria in large zero-sum extensive-form games has received a tremendous amount of attention due mainly to the Annual Computer Poker Competition. Immediately after its inception, two competing and seemingly different approaches emerged---one an application of no-regret online learning, the other a sophisticated gradient method applied to a convex-concave saddle-point formulation. Since then, both approaches have grown in relative isolation with advancements on one side not effecting the other. In this paper, we rectify this by dissecting and, in a sense, unify the two views.

Although techniques for finding Nash equilibria in extensive form games have become more powerful in recent years, many games that model real world interactions remain too large to be solved directly. The current approach is to create a smaller abstracted game, allowing the computation of an optimal solution. The strategy can then be used in the original game. Considering public information to create the abstraction can be strategically important, yet very few of the previous abstraction algorithms specifically consider public information or use an expert approach. In this paper, we show that the public information can be crucial, and we present a new, automatic technique for abstracting the public state space. We also present an experimental evaluation in the domain of Texas Hold’em poker and show that it outperforms state-of-the-art abstraction algorithms.

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.

A unique behavior of humans is modifying one’s unobservable behavior based on the reaction of others for cooperation. We used a card game called Hanabi as an evaluation task of imitating human reflective intelligence with artificial intelligence. Hanabi is a cooperative card game with incomplete information. A player cooperates with an opponent in building several card sets constructed with the same color and ordered numbers. However, like a blind man's bluff, each player sees the cards of all other players except his/her own. Also, communication between players is restricted to information about the same numbers and colors, and the player is required to read his/his opponent's intention with the opponent's hand, estimate his/her cards with incomplete information, and play one of them for building a set. We compared human play with several simulated strategies. The results indicate that the strategy with feedbacks from simulated opponent's viewpoints achieves more score than other strategies.

Clustering agents by their behaviour can be crucial for building effective agent models. Traditional clustering typically aims to group entities together based on a distance metric, where a desirable clustering is one where the entities in a cluster are spatially close together. Instead, one may desire to cluster based on actionability, or the capacity for the clusters to suggest how an agent should respond to maximize their utility with respect to the entities. Segmentation problems examine this decision-theoretic clustering task. Although finding optimal solutions to these problems is computationally hard, greedy-based approximation algorithms exist. However, in settings where the agent has a combinatorially large number of candidate responses whose utilities must be considered, these algorithms are often intractable. In this work, we show that in many cases the utility function can be factored to allow for an efficient greedy algorithm even when there are exponentially large response spaces. We evaluate our technique theoretically, proving approximation bounds, and empirically using extensive-form games by clustering opponent strategies in toy poker games. Our results demonstrate that these techniques yield dramatically improved clusterings compared to a traditional distance-based clustering approach in terms of both subjective quality and utility obtained by responding to the clusters.

Generalized Additive Models (GAM) are a widely popular class of regression models to forecast electricity demand, due to their high accuracy, flexibility and interpretability. However, the residuals of the fitted GAM are typically heteroscedastic and leptokurtic caused by the nature of energy data. In this paper we propose a novel approach to estimate the time-varying conditional variance of the GAM residuals, which we call the GAM2 algorithm. It allows utility companies and network operators to assess the uncertainty of future electricity demand and incorporate it into their planning processes. The basic idea of our algorithm is to apply another GAM to the squared residuals to explain the dependence of uncertainty on exogenous variables. Empirical evidence shows that the residuals rescaled by the estimated conditional variance are approximately normal. We combine our modeling approach with online learning algorithms that adjust for dynamic changes in the distributions of demand. We illustrate our method by a case study on data from RTE, the operator of the French transmission grid.

Bike sharing systems consist of a fleet of bikes placed in a network of docking stations. These bikes can then be rented and returned to any of the docking stations after usage. Predicting unrealized bike demand at locations currently without bike stations is important for effectively designing and expanding bike sharing systems. We predict pairwise bike demand for New York City’s Citi Bike system. Since the system is driven by daily commuters we focus only on the morning rush hours between 7:00 AM to 11:00 AM during weekdays. We use taxi usage, weather and spatial variables as covariates to predict bike demand, and further analyze the influence of precipitation and day of week. We show that aggregating stations in neighborhoods can substantially improve predictions. The presented model can assist planners by predicting bike demand at a macroscopic level, between pairs of neighborhoods.

The problem with this type of method is that it does not really take advantage of Land use and land cover classification (LUCC) maps from high resolution images. We believe that pixel based spectral remote sensor data are of great interest since they allow to information is not enough to characterize land use and track issues like deforestation/reforestation, water sources land cover classes. For this reason, our goal is to design a reduction, urban growth, or to calculate indicators like a methodology that models classes as areas of correlated pixels.

While human behavior models based on repeated Stackelberg games have been proposed for domains such as "wildlife crime" where there is repeated interaction between the defender and the adversary, there has been no empirical study with human subjects to show the effectiveness of such models. This paper presents an initial study based on extensive human subject experiments with participants on Amazon Mechanical Turk (AMT). Our findings include: (i) attackers may view the defender’s coverage probability in a non-linear fashion; specifically it follows an S-shaped curve, and (ii) there are significant losses in defender utility when strategies generated by existing models are deployed in repeated Stackelberg game settings against human subjects.

While great strides have been made in collecting presence data and developing accurate species distribution models, much less is known about the migratory process that guides the spatio-temporal changes in distributions for migrating species, especially birds. In this work, we address a challenging inference task, where given only aggregate and noisy data of the volume of birds for each spatial pixel and time window, we predict the likely transition links with their associated probabilities. We propose a framework to build such migration networks for different bird species and present a real world example of constructing a network using our approach.