Achieving the highest levels of automated driving will require effective solutions to the key challenging maneuver of highway on-ramp merging. This paper extends our previous work on a multi-agent reinforcement-learning (MARL) approach to study the problem of highway on-ramp merging, with particular emphasis on the study of the behavior of the vehicle that is on the on-ramp with approaching traffic. Our previous model was based on a discretized space of states and actions. Here, we present results on a more sophisticated model based on a continuous space of states and actions. We exploit recent advances on deep reinforcement learning (deep RL) to train controllers for this task in an idealized environment using an implementation of our MARL approach. We specifically employ artificial neural network architectures for policy and function approximation within our multiagent Q-learning approach. We show the effectiveness of our trained controllers by demonstrating their collision-avoidance performance on interaction scenarios with different in-traffic behavior. We compare their performance to those obtained using a similar deep RL single-agent approach. We argue why the resulting MARL-based controllers are essentially optimal within the context, conditions, and parameters of the evaluation environment that we employ and our previously established fundamental performance limitations governing the highway on-ramp merging maneuver.

Graphical games are one of the earliest examples of the impact that the general field of graphical models have had in other areas, and in this particular case, in classical mathematical models in game theory. Graphical multi-hypermatrix games, a concept formally introduced in this research note, generalize graphical games while allowing the possibility of further space savings in model representation to that of standard graphical games. The main focus of this research note is discretization schemes for computing approximate Nash equilibria, with emphasis on graphical games, but also briefly touching on normal-form and polymatrix games. The main technical contribution is a theorem that establishes sufficient conditions for a discretization of the players’ space of mixed strategies to contain an approximate Nash equilibrium. The result is actually stronger because every exact Nash equilibrium has a nearby approximate Nash equilibrium on the grid induced by the discretization. The sufficient conditions are weaker than those of previous results. In particular, a uniform discretization of size linear in the inverse of the approximation error and in the natural game-representation parameters suffices. The theorem holds for a generalization of graphical games, introduced here. The result has already been useful in the design and analysis of tractable algorithms for graphical games with parametric payoff functions and certain game-graph structures. For standard graphical games, under natural conditions, the discretization is logarithmic in the game-representation size, a substantial improvement over the linear dependency previously required. Combining the improved discretization result with old results on constraint networks in AI simplifies the derivation and analysis of algorithms for computing approximate Nash equilibria in graphical games.

We provide the first fully polynomial time approximation scheme (FPTAS) for computing an approximate mixed-strategy Nash equilibrium in graphical multi-hypermatrix games (GMhGs), which are generalizations of normal-form games, graphical games, graphical polymatrix games, and hypergraphical games. Computing an exact mixed-strategy Nash equilibria in graphical polymatrix games is PPAD complete and thus generally believed to be intractable. In contrast, to the best of our knowledge, we are the first to establish an FPTAS for tree polymatrix games as well as tree graphical games when the number of actions is bounded by a constant. As a corollary, we give a quasi-polynomial time approximation scheme (quasi-PTAS) when the number of actions is bounded by a logarithm of the number of players.

Roughly speaking, Interdependent Defense (IDD) games, previously proposed, model the situation where an attacker wants to cause as much damage as possible to a network by attacking one of the sites in the network. Each site must make an investment decision regarding security to protect itself against a direct or indirect attack, the latter due to potential transfer-risk from an unprotected neighboring site. The work introducing IDD games discusses potential applications to model the essence of real-world scenarios such as the 2006 transatlantic aircraft plot. In this paper, our focus is the study of the problem of computing a Nash Equilibrium (NE) in IDD games. We show that an efficient algorithm to determine whether some attacker’s strategy can be a part of a NE in an instance of IDD games is unlikely to exist. Yet, we provide a dynamic programming algorithm to compute an approximate NE when the graph/network structure of the game is a directed tree with a single source, and show that it is an FPTAS. We also introduce an improved heuristic to compute an approximate NE on arbitrary graph structures. Our experiments show that our heuristic is more efficient, and provides better approximations, than best-response-gradient dynamics for the case of Internet games, a class of games introduced and studied in the original work on IDD games.

We address the problem of network-side localization where cellular operators are interested in localizing cellular devices by means of signal strength measurements alone. While fingerprinting-based approaches have been used recently to address this problem, they require significant amount of geo-tagged (`labeled') measurement data that is expensive for the operator to collect. Our goal is to use semi-supervised and unsupervised machine learning techniques to reduce or eliminate this effort without compromising the accuracy of localization. Our experimental results in a university campus (6 sq. km) demonstrate that sub-100m median localization accuracy is achievable with very little or no labeled data so long as enough training is possible with `unlabeled' measurements. This provides an opportunity for the operator to improve the model with time. We present extensive analysis of the error characteristics to gain insight and improve performance, including understanding spatial properties and developing confidence measures.

Clothing recognition is a societally and commercially important yet extremely challenging problem due to large variations in clothing appearance, layering, style, and body shape and pose. In this paper, we tackle the clothing parsing problem using a retrieval-based approach. For a query image, we find similar styles from a large database of tagged fashion images and use these examples to recognize clothing items in the query. Our approach combines parsing from: pre-trained global clothing models, local clothing models learned on the fly from retrieved examples, and transferred parse-masks (Paper Doll item transfer) from retrieved examples. We evaluate our approach extensively and show significant improvements over previous state-of-the-art for both localization (clothing parsing given weak supervision in the form of tags) and detection (general clothing parsing). Our experimental results also indicate that the general pose estimation problem can benefit from clothing parsing.

From Flickr to Facebook to Pinterest, pictures are increasingly becoming a core content type in social networks. But, how important is this visual content and how does it influence behavior in the network? In this paper we study the effects of visual, textual, and social factors on popularity in a large real-world network focused on fashion. We make use of state of the art computer vision techniques for clothing representation, as well as network and text information to predict post popularity in both in-network and out-of-network scenarios. Our experiments find significant statistical evidence that social factors dominate the in-network scenario, but that combinations of content and social factors can be helpful for predicting popularity outside of the network. This in depth study of image popularity in social networks suggests that social factors should be carefully considered for research involving social network photos.

In this paper we demonstrate an effective method for parsing clothing in fashion photographs, an extremely challenging problem due to the large number of possible garment items, variations in configuration, garment appearance, layering, and occlusion. In addition, we provide a large novel dataset and tools for labeling garment items, to enable future research on clothing estimation. Finally, we present intriguing initial results on using clothing estimates to improve pose identification, and demonstrate a prototype application for pose-independent visual garment retrieval.

We propose influence games, a new class of graphical games, as a model of the behavior of large but finite networked populations. Grounded in non-cooperative game theory, we introduce a new approach to the study of influence in networks that captures the strategic aspects of complex interactions in the network. We study computational problems on influence games, including the identification of the most influential nodes. We characterize the computational complexity of various problems in influence games, propose several heuristics for the hard cases, and design approximation algorithms, with provable guarantees, for the most influential nodes problem.

We consider the problem of localizing a wireless client in an indoor environment based on the signal strength of its transmitted packets as received on stationary sniffers or access points. Several state-of-the-art indoor localization techniques have the drawback that they rely extensively on a labor-intensive 'training' phase that does not scale well. Use of unmodeled hardware with heterogeneous power levels further reduces the accuracy of these techniques.

We propose an agent-based behavioral model of pedestrians to improve tracking performance in realistic scenarios. In this model, we view pedestrians as decision-making agents who consider a plethora of personal, social, and environmental factors to decide where to go next. We formulate prediction of pedestrian behavior as an energy minimization on this model. Two of our main contributions are simple, yet effective estimates of pedestrian destination and social relationships (groups). Our final contribution is to incorporate these hidden properties into an energy formulation that results in accurate behavioral prediction. We evaluate both our estimates of destination and grouping, as well as our accuracy at prediction and tracking against state of the art behavioral model and show improvements, especially in the challenging observational situation of infrequent appearance observations-something that might occur in thousands of webcams available on the Internet.

Locality information is crucial in datasets where each variable corresponds to a measurement in a manifold (silhouettes, motion trajectories, 2D and 3D images). Although these datasets are typically under-sampled and high-dimensional, they often need to be represented with low-complexity statistical models, which are comprised of only the important probabilistic dependencies in the datasets. Most methods attempt to reduce model complexity by enforcing structure sparseness. However, sparseness cannot describe inherent regularities in the structure. Hence, in this paper we first propose a new class of Gaussian graphical models which, together with sparseness, imposes local constancy through ${\ell}_1$-norm penalization. Second, we propose an efficient algorithm which decomposes the strictly convex maximum likelihood estimation into a sequence of problems with closed form solutions. Through synthetic experiments, we evaluate the closeness of the recovered models to the ground truth. We also test the generalization performance of our method in a wide range of complex real-world datasets and demonstrate that it can capture useful structures such as the rotation and shrinking of a beating heart, motion correlations between body parts during walking and functional interactions of brain regions. Our method outperforms the state-of-the-art structure learning techniques for Gaussian graphical models both for small and large datasets.

This paper proposes constraint propagation relaxation (CPR), a probabilistic approach to classical constraint propagation that provides another view on the whole parametric family of survey propagation algorithms SP(ρ), ranging from belief propagation (ρ = 0) to (pure) survey propagation(ρ = 1). More importantly, the approach elucidates the implicit, but fundamental assumptions underlying SP(ρ), thus shedding some light on its effectiveness and leading to applications beyond k-SAT.

We develop and analyze game-theoretic algorithms for predicting coordinate binding of multiple DNA binding regulators. The allocation of proteins to local neighborhoods and to sites is carried out with resource constraints while explicating competing and coordinate binding relations among proteins with affinity to the site or region. The focus of this paper is on mathematical foundations of the approach. We also briefly demonstrate the approach in the context of the -phage switch.

We examine the marriage of recent probabilistic generative models for social networks with classical frameworks from mathematical eco- nomics. We are particularly interested in how the statistical structure of such networks influences global economic quantities such as price vari- ation. Our findings are a mixture of formal analysis, simulation, and experiments on an international trade data set from the United Nations.

We introduce new online models for two important aspectsof modern financial markets: Volume Weighted Average Pricetrading and limit order books. We provide an extensivestudy of competitive algorithms in these models and relatethem to earlier online algorithms for stock trading.

nspired by events ranging from 9/11 to the collapse of the accounting firm Arthur Ander- sen, economists Kunreuther and Heal [5] recently introduced an interesting game-theoretic model for problems of interdependent security (IDS), in which a large number of players must make individual investment decisions related to security — whether physical, finan- cial, medical, or some other type — but in which the ultimate safety of each participant may depend in a complex way on the actions of the entire population. A simple example is the choice of whether to install a fire sprinkler system in an individual condominium in a large building. While such a system might greatly reduce the chances of the owner’s prop- erty being destroyed by a fire originating within their own unit, it might do little or nothing to reduce the chances of damage caused by fires originating in other units (since sprinklers can usually only douse small fires early). If “enough” other unit owners have not made the investment in sprinklers, it may be not cost-effective for any individual to do so.

We examine correlated equilibria in the recently introduced formalism of graphical games, a succinct representation for multiplayer games. We establish a natural and powerful relationship between the graphical structure of a multiplayer game and a certain Markov network representing distributions over joint actions. Our first main result establishes that this Markov network succinctly represents all correlated equilibria of the graphical game up to expected payoff equivalence. Our second main result provides a general algorithm for computing correlated equilibria in a graphical game based on its associated Markov network. For a special class of graphical games that includes trees, this algorithm runs in time polynomial in the graphical game representation (which is polynomial in the number of players and exponential in the graph degree).

This paper gives distribution-free concentration inequalities for the miss- ing mass and the error rate of histogram rules. Negative association meth- ods can be used to reduce these concentration problems to concentration questions about independent sums. Although the sums are independent, they are highly heterogeneous. Such highly heterogeneous independent sums cannot be analyzed using standard concentration inequalities such as Hoeffding’s inequality, the Angluin-Valiant bound, Bernstein’s in- equality, Bennett’s inequality, or McDiarmid’s theorem.

We introduce NashProp, an iterative and local message-passing algo- rithm for computing Nash equilibria in multi-player games represented by arbitrary undirected graphs. We provide a formal analysis and exper- imental evidence demonstrating that NashProp performs well on large graphical games with many loops, often converging in just a dozen itera- tions on graphs with hundreds of nodes. NashProp generalizes the tree algorithm of (Kearns et al. 2001), and can be viewed as similar in spirit to belief propagation in probabilis- tic inference, and thus complements the recent work of (Vickrey and Koller 2002), who explored a junction tree approach. Thus, as for prob- abilistic inference, we have at least two promising general-purpose ap- proaches to equilibria computation in graphs.