United States

Network games provide a natural machinery to compactly represent strategic interactions among agents whose payoffs exhibit sparsity in their dependence on the actions of others. Besides encoding interaction sparsity, however, real networks often exhibit a multi-scale structure, in which agents can be grouped into communities, those communities further grouped, and so on, and where interactions among such groups may also exhibit sparsity. We present a general model of multi-scale network games that encodes such multi-level structure. We then develop several algorithmic approaches that leverage this multi-scale structure, and derive sufficient conditions for convergence of these to a Nash equilibrium. Our numerical experiments demonstrate that the proposed approaches enable orders of magnitude improvements in scalability when computing Nash equilibria in such games. For example, we can solve previously intractable instances involving up to 1 million agents in under 15 minutes.

AAAI 2021

Multi-Scale Games: Representing and Solving Games on Networks with Group Structure

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

technical paper

Collaborative Multi-Agent Planning (MAP) problems with uncertainty and partial observability are often modeled as Dec-POMDPs. Yet, in deterministic domains, Qualitative Dec-POMDPs can scale up to much larger problem sizes. The best current QDec solver (QDec-FP) reduces MAP problems to multiple single-agent problems. In this paper, we describe a planner that uses richer information about agentsâ€™ knowledge to improve upon QDec-FP. With this change, the planner not only scales up to larger problems with more objects, but it can also support signaling, where agents signal information to each other by changing the state of the world.

Improved Knowledge Modeling and Its Use for Signaling in Multi-Agent Planning with Partial Observability

We present *-CFQ ("star-CFQ"): a suite of large-scale datasets of varying scope based on the CFQ semantic parsing benchmark, designed for principled investigation of the scalability of machine learning systems in a realistic compositional task setting. Using this suite, we conduct a series of experiments investigating the ability of Transformers to benefit from increased training data size under conditions of fixed computational cost. We show that compositional generalization remains a challenge at all training sizes, and we show that increasing the scope of natural language leads to consistently higher error rates, which are only partially offset by increased training data. We further show that while additional training data from a related domain improves the accuracy in data-starved situations, this improvement is limited and diminishes as the distance from the related domain to the target domain increases.

*-CFQ: Analyzing the Scalability of Machine Learning on a Compositional Task

We consider the problem of responsibility attribution in the setting of parametric Markov chains. Given a family of Markov chains over a set of parameters, and a property, responsibility attribution asks how the difference in the value of the property should be attributed to the parameters when they change from one point in the parameter space to another. 

We formalize responsibility as path-based attribution schemes studied in cooperative game theory. An attribution scheme in a game determines how a value (a surplus or a cost) is distributed among a set of participants. Path-based attribution schemes include the well-studied Aumann-Shapley and the Shapley-Shubik schemes. In our context, an attribution scheme measures the responsibility of each parameter on the value function of the parametric Markov chain. 

We study the decision problem for path-based attribution schemes. Our main technical result is an algorithm for deciding if a path-based attribution scheme for a rational (ratios of polynomials) cost function is over a rational threshold. In particular, it is decidable if the Aumann-Shapley value for a player is at least a given rational number. As a consequence, we show that responsibility attribution is decidable for parametric Markov chains and for a general class of properties that include expectation and variance of discounted sum and long-run average rewards, as well as specifications in temporal logic.

Responsibility Attribution in Parameterized Markovian Models

We investigate the relational classification of biological cells in 2D microscopy images. Rather than treating each cell image independently, we investigate whether and how the neighborhood information of a cell can be informative for its prediction. 
We propose a Relational Long Short-Term Memory (R-LSTM) algorithm, coupled with auto-encoders and convolutional neural networks, that can learn from both annotated and unlabeled microscopy images and that can utilize both the local and neighborhood information to perform an improved classification of biological cells. Experimental results on both synthetic and real datasets show that R-LSTM performs comparable to or better than six baselines.

Relational Classification of Biological Cells in Microscopy Images

Real-time forwarding prediction for predicting online contents' popularity is beneficial to various social applications for enhancing interactive social behaviors. Cascade graphs, formed by online contents' propagation, play a vital role in real-time forwarding prediction. Existing cascade graph modeling methods are inadequate to embed cascade graphs that have hub structures and deep cascade paths, or they fail to handle the short-term outbreak of forwarding amount. To this end, we propose a novel real-time forwarding prediction method that includes an effective approach for cascade graph embedding and a short-term variation sensitive method for time-series modeling, making the best of cascade graph features. Using two real world datasets, we demonstrate the significant superiority of the proposed method compared with the state-of-the-art. Our experiments also reveal interesting implications hidden in the performance differences between cascade graph embedding and time-series modeling.

Fully Exploiting Cascade Graphs for Real-Time Forwarding Prediction

Using temporal abstraction, various forms of sampled multivariate temporal data can be transformed into a uniform representation of symbolic time intervals, from which Time Intervals Related Patterns (TIRPs) can be then discovered. Hence, mining TIRPs from symbolic time intervals offers a comprehensive framework for heterogeneous multivariate temporal data analysis. While the field of time intervals mining has gained a growing interest in recent decades, frequent closed TIRPs mining was not investigated in its full complexity. Mining frequent closed TIRPs is highly effective due to the discovery of a compact set of frequent TIRPs, which contains the complete information of all the frequent TIRPs. However, as we demonstrate in this paper, the recent advancements made in closed TIRPs discovery are incomplete, due to the discovery of only the first instances of the TIRPs within each STIs series in the database. In this paper we introduce the TIRPClo algorithm â€“ for complete and efficient mining of frequent closed TIRPs. The algorithm utilizes a memory-efficient index and a novel method for data projection, due to which it is the first algorithm to guarantee a complete discovery of frequent closed TIRPs. In addition, a rigorous runtime comparison of TIRPClo to state-of-the-art methods is performed, demonstrating a significant speed-up on various real-world datasets.

Complete Closed Time Intervals-Related Patterns Mining

This work proposes an approach for latent-dynamics learning that exactly enforces physical conservation laws. The method comprises two steps. First, the method computes a low-dimensional embedding of the high-dimensional dynamical-system state using deep convolutional autoencoders. This defines a low-dimensional nonlinear manifold on which the state is subsequently enforced to evolve. Second, the method defines a latent-dynamics model that associates with the solution to a constrained optimization problem. Here, the objective function is defined as the sum of squares of conservation-law violations over control volumes within a finite-volume discretization of the problem; nonlinear equality constraints explicitly enforce conservation over prescribed subdomains of the problem. Under modest conditions, the resulting dynamics model guarantees that the time-evolution of the latent state exactly satisfies conservation laws over the prescribed subdomains.

Deep Conservation: A Latent-Dynamics Model for Exact Satisfaction of Physical Conservation Laws

Recently, deep reinforcement learning (RL) has achieved remarkable empirical success by integrating deep neural networks into RL frameworks. However, these algorithms often require a large number of training samples and admit little theoretical understanding. To mitigate these issues, we propose a theoretically principled nearest neighbor (NN) function approximator that can replace the value networks in deep RL methods. Inspired by human similarity judgments, the NN approximator estimates the action values using rollouts on past observations and can provably obtain a small regret bound that depends only on the intrinsic complexity of the environment. We present (1) Nearest Neighbor Actor-Critic (NNAC), an online policy gradient algorithm that demonstrates the practicality of combining function approximation with deep RL, and (2) a plug-and-play NN update module that aids the training of existing deep RL methods. Experiments on classical control and MuJoCo locomotion tasks show that the NN-accelerated agents achieve higher sample efficiency and stability than the baseline agents. Based on its theoretical benefits, we believe that the NN approximator can be further applied to other complex domains to speed-up learning.

Theoretically Principled Deep Rl Acceleration via Nearest Neighbor Function Approximation

Consider a set of voters V, represented by a multiset in a metric space (X,d). The voters have to reach a decision - a point in X. A choice pâˆˆ X is called a Î²-plurality point for V, if for any other choice qâˆˆ X it holds that |{vâˆˆ V âˆ£Â  Î²â‹… d(p,v)â‰¤ d(q,v)}|Â â‰¥|V|/2 . In other words, at least half of the voters ``prefer'' over q, when an extra factor of Î² is taken in favor of p.

For Î²=1, this is equivalent to Condorcet winner, which rarely exists. The concept of Î²-plurality was suggested by Aronov, de Berg, Gudmundsson, and Horton [SoCG 2020] as a relaxation of the Condorcet criterion. 

Denote by Î²*(X,d) the value sup{ Î² âˆ£Â  every finite multiset V in X admits a Î²-plurality point}}.
The parameter Î²* determines the amount of relaxation required in order to reach a stable decision.
Aronov et al. showed that for the Euclidean plane Î²*(â„2,\|â‹…\|2)=âˆš3/2 , and more generally, for d-dimensional Euclidean space, 1/âˆšd â‰¤ Î²*(â„d,\|â‹…\|2)â‰¤âˆš3/2 .

In this paper, we show that 0.557â‰¤ Î²*(â„d,\|â‹…\|2) for any dimension d (notice that 1/âˆšd <0.557 for any dâ‰¥ 4). In addition, we prove that for every metric space (X,d) it holds that âˆš2-1â‰¤Î²*(X,d), and show that there exists a metric space for which Î²*(X,d)â‰¤ 1/2 .

Condorcet Relaxation in Spatial Voting

We study an important and challenging task of attacking natural language processing models in a hard label black box setting. We propose a decision-based attack strategy that crafts high quality adversarial examples on text classification and entailment tasks. Our proposed attack strategy leverages population-based optimization algorithm to craft plausible and semantically similar adversarial examples by observing only the top label predicted by the target model. At each iteration, the optimization procedure allow word replacements that maximizes the overall semantic similarity between the original and the adversarial text. Further, our approach does not rely on using substitute models or any kind of training data. We demonstrate the efficacy of our proposed approach through extensive experimentation and ablation studies on five state-of-the-art target models across seven benchmark datasets. In comparison to attacks proposed in prior literature, we are able to achieve a higher success rate with lower word perturbation percentage that too in a highly restricted setting.

Downloads

Next from AAAI 2021

Improved Knowledge Modeling and Its Use for Signaling in Multi-Agent Planning with Partial Observability

Similar lecture

Double Oracle Algorithm for Computing Equilibria in Continuous Games

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAAI 2021

Improved Knowledge Modeling and Its Use for Signaling in Multi-Agent Planning with Partial Observability

Similar lecture

Double Oracle Algorithm for Computing Equilibria in Continuous Games

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads