United States

We study the exploration-exploitation trade-off for large multiplayer coordination games where players strategise via Q-Learning, a common learning framework in multi-agent reinforcement learning. Q-learning is known to have two shortcomings, namely  non-convergence and potential equilibrium selection problems, when there are multiple fixed points, called Quantal Response Equilibria (QRE). Furthermore, whilst QRE have full support for finite games, it is not clear how Q-learning behaves as the game becomes large. 

In this paper, we characterise the critical exploration rate that guarantees convergence to a unique fixed point, addressing the two shortcomings above. Using a generating-functional method, we show that this rate increases with the number of players and the alignment of their payoffs. For many-player coordination games with perfectly aligned payoffs, this exploration rate is roughly twice that of $p$-player zero-sum games. As for large games, we provide a structural result for QRE, which suggests that as the game size increases, Q-Learning converges to a QRE near the boundary of the simplex of the action space, a phenomenon we term asymptotic extinction, where a constant fraction of the actions are played with zero probability at a rate $o(1/N)$ for an $N$-action game.

AAAI 2025

Asymptotic Extinction in Large Coordination Games

gtep

coordination and collaboration

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. 

AAAI 2021

technical paper

We are pleased to announce the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), which will be held in Philadelphia, Pennsylvania at the Pennsylvania Convention Center from February 25 to March 4, 2025.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

### [Invited Speakers](https://aaai.org/conference/aaai/aaai-25/aaai-25-invited-speakers/)

Register [here](https://aaai.org/conference/aaai/aaai-25/registration/)

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.



Given an edge-colored graph, the goal of the Proportionally Fair Matching problem is to find a *maximum weight matching* while ensuring proportional representation of each color. The colors may correspond to demographic groups or other protected traits where we seek to ensure roughly equal representation from each group. It is known that, assuming ETH, it is impossible to approximate the problem with $\ell$ colors in time $2^{o(\ell)} n^{\mathcal{O}(1)}$ (i.e., subexponential in $\ell$). Further, even determining the existence of a non-empty matching satisfying proportionality is NP-Hard.
  
To overcome this hardness, we relax the stringent proportional fairness constraints to a probabilistic notion. We introduce a notion we call $\eta$-ProbablyApproximatelyFair, where we ensure proportionality to within a constant factor violation with high probability. We propose and analyze simple, fast algorithms with constant-factor approximation guarantees that satisfy $\eta$-ProbablyApproximateFairness for the Proportionally Fair Matching problem.

Proportionally Fair Matching via Randomized Rounding

Natural language is the most intuitive means for humans to interact with robots, making task planning based on natural language commands a longstanding area of research. Large language models (LLMs) have significantly improved task planning by enhancing understanding of language and common sense. However, current methods still face several challenges: they lack a deep understanding of physical environments, their performance relies heavily on prompt examples, LLMs are oversized and not customized for specific tasks, and the planning costs remain high. 
To overcome these issues, we introduce the GNN-Transformer Task Planner (GTTP), designed to predict task-level actions by leveraging the semantic environment and incorporating historical state data. The GTTP architecture is scalable through the use of GNN layers, while transformer layers facilitate understanding task progression. In addition, our model uses a text encoder to embed environments, allowing it to be trained on simulated datasets and applied directly in real-world scenarios. We also propose an automated data generation method that includes semantic augmentation, planning verification, and instruction generation via LLM. This method enables the collection of 14$k$ instruction-annotated tasks in the VirtualHome environment with minimal human effort. The model has been validated across diverse scenes containing up to 715 objects, achieving significantly higher success rates compared to baseline models. It has also been successfully deployed on a physical mobile manipulator, demonstrating its practical applicability and effectiveness. Our datasets and code will be made publicly available.

GNN-Transformer Task Planning Enhanced with Semantic-Driven Data Augmentation

In this paper, we focus on estimating the causal effect of an intervention over time on a dynamical system. 
To that end, we formally define causal interventions and their effects over time on discrete-time stochastic processes (DSPs). 
Then, we show under which conditions the equilibrium states of a DSP, both before and after a causal intervention, can be captured by a structural causal model (SCM). 
With such an equivalence at hand, we provide an explicit mapping from vector autoregressive models (VARs), broadly applied in econometrics, to linear, but potentially cyclic and/or affected by unmeasured confounders, SCMs. The resulting \emph{causal VAR framework} allows us to perform \emph{causal inference over time} from observational time series data.  
Our experiments on synthetic and real-world datasets show that the proposed framework achieves strong performance in terms of observational forecasting while enabling accurate estimation of the causal effect of interventions on dynamical systems. 
We demonstrate, through a case study, the potential practical questions that can be addressed using the proposed causal VAR framework.

A Practical Approach to Causal Inference over Time

Emotion Recognition in Conversations (ERC) refers to the task of automatically identifying the emotion of each utterance in conversations. Unfortunately, because the emotion of an utterance is influenced by the contextual information of the conversation, to label each utterance in ERC, the annotators are required to repeatedly read the whole conversation, making the fine-grained labeling process very costly. In this work, we suggest an efficient coarse-grained labeling pattern for ERC, where it asks annotators to assign a set of emotions for each conversation. The empirical results of our preliminary evaluations indicate the accuracy and efficiency of this conversation-level labeling pattern. Accordingly, we suggest that inducing ERC predictors with conversation-level emotion sets in a weakly-supervised learning manner can be a potential candidate for ERC, and we formally refer to this new weakly-supervised learning task as Dataless ERC (DERC). To validate its potential, we propose a simple-yet-flexible DERC framework, namely DERC with Progressive Learning (DERC-PL). We jointly update pseudo-utterance-level emotions and the ERC predictor in a self-training manner, and in particular, progressively update the ERC predictor from training subsets with lower noise densities to the ones with higher noise densities. We specify several versions of DERC-PL by applying various off-the-shelf ERC methods. Empirical results indicate that DERC-PL can be on par with existing weakly-supervised learning baselines and supervised learning ERC methods.

Utterance-level Emotion Recognition in Conversation with Conversation-level Supervision

In causal inference, a randomized experiment is a de facto method to overcome various theoretical issues in observational study.
However, the experimental design requires expensive costs, so an efficient experimental design is necessary.
We propose ABC3, a Bayesian active learning policy for causal inference.
We show a policy minimizing an estimation error on conditional average treatment effect is equivalent to minimizing an integrated posterior variance, similar to Cohn criteria.
We theoretically prove ABC3 also minimizes an imbalance between the treatment and control groups and the type 1 error probability.
Imbalance-minimizing characteristic is especially notable as several works have emphasized the importance of achieving balance.
Through extensive experiments on real-world data sets, ABC3 achieves the highest efficiency, while empirically showing the theoretical results hold.

ABC3: Active Bayesian Causal Inference with Cohn Criteria in Randomized Experiments

Emotion recognition in conversation (ERC) has been promoted with diverse approaches in the recent years. However, many studies have pointed out that emotion shift and confusing labels make it difficult for models to distinguish between different emotions. Existing ERC models suffer from these problems when the emotions are forced to be mapped into single label. In this paper, we propose a multi-label classification framework for emotion recognition in conversation (ML-ERC).
Specifically, we introduce weighted supervised contrastive learning tailored for multi-label, which can also extend previous ERC models. 
Experimental results on three benchmark datasets show that the proposed approach effectively handles multiple emotions. Our model achieves improved results for identifying emotions in the most challenging settings in emotion shift and confusing labels.

Beyond Single Emotion: Multi-label Approach to Conversational Emotion Recognition

Graph Neural Networks (GNNs) have demonstrated remarkable ability in semi-supervised node classification. However, most existing GNNs rely heavily on a large amount of labeled data for training, which is labor-intensive and requires extensive domain knowledge. In this paper, we first analyze the restrictions of GNNs generalization from the perspective of supervision signals in the context of few-shot semi-supervised node classification. To address these challenges, we propose a novel algorithm named NormProp, which utilizes the homophily assumption of unlabeled nodes to generate additional supervision signals, thereby enhancing the generalization against label scarcity. The key idea is to efficiently capture both the class information and the consistency of aggregation during message passing, via decoupling the direction and Euclidean norm of node representations. Moreover, we conduct a theoretical analysis to determine the upper bound of Euclidean norm, and then propose homophilous regularization to constraint the consistency of unlabeled nodes. Extensive experiments demonstrate that NormProp achieve state-of-the-art performance under low-label rate scenarios with low computational complexity. The code of NormProp is available at supplementary material.

Normalize Then Propagate: Efficient Homophilous Regularization for Few-Shot Semi-Supervised Node Classification

Unauthorised face recognition (FR) systems have posed significant threats to digital identity and privacy protection. To alleviate the risk of compromised identities, recent makeup transfer-based attack methods embed adversarial signals in order to confuse unauthorised FR systems. However, their major weakness is that they set up a fixed image unrelated to both the protected and the makeup reference images as the confusion identity, which in turn has a negative impact on both attack success rate and visual quality of transferred photos. In addition, the generated images cannot be recognised by authorised FR systems once attacks are triggered. To address these challenges, in this paper, we propose a Recoverable Makeup Transferred Generative Adversarial Network (RMT-GAN) which has the distinctive feature of improving its image-transfer quality by selecting a suitable transfer reference photo as the target identity. Moreover, our method offers a solution to recover the protected photos to their original counterparts that can be recognised by authorised systems. Experimental results demonstrate that our method provides significantly improved attack success rates while maintaining higher visual quality compared to state-of-the-art makeup transfer-based adversarial attack methods.

Recoverable Facial Identity Protection via Adaptive Makeup Transfer Adversarial Attacks

The great challenge of handwritten mathematical expression recognition (HMER) is the complex structures of the expressions, which are directly related to the symbol spatial positions. Existing HMER methods typically employ attention mechanisms in the decoder of their models to implicitly perceive the symbol positions, or employ symbol counting and tree-based strategies to model the symbol spatial relation. However, these methods still cannot effectively capture the structural information of formulas, thus negatively impacting the symbol decoding in HMER. To deal with this problem and enhance the HMER performance, this paper proposes a novel auxiliary task, namely predicting the symbol spatial distribution map of handwritten expression images. On such basis, this paper designs a symbol spatial-aware network (SSAN) for this task, which is jointly optimized with the HMER model. Specifically, considering the similarity of the symbol spatial positions between the handwritten mathematical expression images and their corresponding printed templates, we obtain the symbol spatial distribution map by first generating printed templates from LaTeX ground-truth for handwritten formula images and then replacing the connected components of printed templates with 2D Gaussian distribution maps of the same size. Meanwhile, due to the loose alignment of the symbol spatial positions between handwritten and printed formula images, and misclassification of similar symbols, we further propose a coarse-to-fine alignment strategy and an attention-guided symbol masking strategy in SSAN to tackle these issues. Extensive experiments demonstrate that SSAN significantly improves the recognition performance of the HMER models, and the proposed auxiliary tasks are more effective in enhancing HEMR performance than existing auxiliary tasks. Code is available at https://anonymous.4open.science/r/SSAN-5223.

SSAN: A Symbol Spatial-Aware Network for Handwritten Mathematical Expression Recognition

Information Retrieval (IR) systems used in search and recommendation platforms frequently employ Learning-to-Rank (LTR) models to rank items in response to user queries. These models heavily rely on features derived from user interactions, such as clicks and engagement data. This dependence introduces cold start issues for items lacking user engagement and poses challenges in adapting to non-stationary shifts in user behavior over time. We address both challenges holistically as an online learning problem and propose BayesCNS, a Bayesian approach designed to handle cold start and non-stationary distribution shifts in search systems at scale. BayesCNS achieves this by estimating prior distributions for user-item interactions, which are continuously updated with new user interactions gathered online. This online learning procedure is guided by a ranker model, enabling efficient exploration of relevant items using contextual information provided by the ranker. We successfully deployed BayesCNS in a large-scale search system and demonstrated its efficacy through comprehensive offline and online experiments. Notably, an online A/B experiment showed a 10.60\% increase in new item interactions and a 1.05\% improvement in overall success metrics over the existing production baseline.

Downloads

Next from AAAI 2025

Proportionally Fair Matching via Randomized Rounding

Similar lecture

Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theory

.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 2025

Proportionally Fair Matching via Randomized Rounding

Similar lecture

Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theory

Downloads