United States

This paper introduces state abstraction for two-player zero-sum Markov games (TZMGs) where the payoffs for the two players are determined by the state representing the environment and their respective actions, with state transitions following a Markov decision processes (MDPs). For example, in games like soccer, the value of actions changes according to the state of play, we should describe them as Markov games. In TZMGs, the more the number of states becomes, the more difficult computing the equilibrium becomes. Therefore, we abstract the states of TZMGs and examine the performance. State abstraction reduces the number of states by treating multiple different states as a single state, and there is a substantial body of research on finding optimal policies for Markov decision processes using state abstraction. This study extends the state abstraction for MDPs to Markov games. In this case, the game with state abstraction may yield different equilibrium solutions from those of the ground game. To evaluate the equilibrium solutions of the game with state abstraction, we derived bounds on duality gap, which represents the distance from the equilibrium solutions of the ground game. Finally, we demonstrate our state abstraction with Markov Soccer, compute equilibrium policies, and examine the results.

AAAI 2025

Approximate State Abstraction for Markov Games

multiagent learning

## Welcome to EMNLP 2022!
I am delighted to welcome you to EMNLP 2022! I believe this conference has been complicated beyond any precedent. Over the past year, it’s been thrilling to see the organization team approach each new puzzle with creativity and enthusiasm. We hope that those participating in Abu Dhabi as well as those joining remotely will leave the conference feeling newly inspired by the program and newly connected to our ever-growing community. Following EMNLP 2021 and major NLP conferences since, EMNLP 2022 is “hybrid,” serving both virtual and in-person participants.

Our key innovations for EMNLP 2022 include:

* EMNLP 2022 is “hybrid” in a second sense, as well: we allowed both direct and rolling review paper submissions, building on the pilot experiment of EMNLP 2021, which considered a small number of ARR submissions. 
* Familiar from NAACL but new to EMNLP, we’ve added an industry track.
* During the conference, “portals” will link virtual poster sessions to in-person conference participants during poster sessions each day.
* The first ACL-family conference in the United Arab Emirates.

 *Message from Noah A. Smith, University of Washington and Allen Institute for AI, Seattle, Washington, USA* 
***EMNLP 2022 General Chair***
 
[![](https://assets.underline.io/uploads/markdown_image/1/image/9eec7d4a287ee18c278b08229290aa83.png)](https://drive.google.com/file/d/1OlPv6QBeo62VVTughj2jkiLeyHd1WnUt/view)
 
[![](https://assets.underline.io/uploads/markdown_image/1/image/a3db7a768409f05192210d98601edb25.png)](https://emnlp2022.rocket.chat/)

To access this site you need to register. Please register [here](https://2022.emnlp.org/registration/).

Register here

EMNLP 2022

Welcome!
EMNLP 2022 will take place in Abu Dhabi from December 7th to December 11th, 2022. And it will be held in hybrid mode, both online and offline.

poster

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.



Black box optimization (BBO) focuses on optimizing unknown functions in high-dimensional spaces. In many applications, sampling the unknown function is expensive, imposing a tight sample budget.Ongoing work is making progress on reducing the sample budget by learning the shape/structure of the function, known as kernel learning.
We propose a new method to learn the kernel of a Gaussian Process. Our idea is to create a continuous kernel space in the latent space of a variational autoencoder, and run an auxiliary optimization to identify the best kernel. Results show that the proposed method, {\em Kernel Optimized Blackbox Optimization} (KOBO), outperforms state of the art by estimating the optimal at considerably lower sample budgets.
Results hold not only across synthetic benchmark functions but also in real applications. We show that a hearing aid may be personalized with fewer audio queries to the user, or a generative model could converge to desirable images from limited user ratings.

Kernel Learning for Sample Constrained Black-Box Optimization

Video inpainting is a crucial task with diverse applications, including fine-grained video editing, video recovery, and video dewatermarking. However, most existing video inpainting methods primarily focus on visual content completion while neglecting text information. There are only a limited number of text-guided video inpainting techniques, and these techniques struggle with maintaining visual quality and exhibit poor semantic representation capabilities. In this paper, we introduce CoCoCo, a text-guided video inpainting diffusion framework. To address the aforementioned challenges, we enhance both the training data and model structure. Specifically, we devise an instance-aware region selection strategy for masked area sampling and develop a novel motion block that incorporates efficient 3D full attention and textual cross attention. Additionally, our CoCoCo framework can be seamlessly integrated with various personalized text-to-image diffusion models through a delicate training-free transfer mechanism. Comprehensive experiments demonstrate that CoCoCo can create high-quality visual content with enhanced temporal consistency, improved text controllability, and better compatibility with personalized image models.

CoCoCo: Improving Text-Guided Video Inpainting for Better Consistency, Controllability and Compatibility

Instruction tuning has emerged as an effective approach that notably improves large language models (LLMs) performance, showing particular promise in natural language generation tasks by producing more diverse, coherent, and task-relevant outputs. However, extending instruction tuning to natural language understanding (NLU) tasks presents significant challenges, primarily due to the difficulty in achieving high-precision responses and the scarcity of large-scale, high-quality instruction data necessary for effective tuning. In this work, we introduce **Adversarial Noisy Instruction Tuning** (ANIT) to improve NLU performance on LLMs. First, we leverage low-resource techniques to construct noisy instruction datasets. Second, we employ semantic distortion-aware techniques to quantify the intensity of noise within these instructions. Last, we devise an adversarial training method that incorporates noise response strategy to achieve noisy instruction tuning. ANIT enhances LLMs capacity to detect and accommodate semantic distortions in noisy instructions, thereby augmenting their comprehension of task objectives and ability to generate more accurate responses. We evaluate our approach across the diverse spectrum of noisy instructions and semantic distortion quantification methods on multiple NLU tasks. Comprehensive empirical results demonstrate that our method consistently outperforms existing approaches across various experimental settings.

Enhancing NLU in Large Language Models Using Adversarial Noisy Instruction Tuning

Micro-video popularity prediction (MVPP) plays a crucial role in various real-world applications, including product marketing and recommendation systems. Recently, multimodal fusion methods that integrate multiple modalities to assess the popularity have exhibited impressive performance. However, these methods face several unresolved issues: (1) limited contextual information and (2) incomplete modal semantics. Incorporating relevant videos and performing full fine-tuning on pre-trained models typically achieves powerful capabilities in addressing these issues. However, this paradigm is not optimal due to its weak transferability and scarce downstream data. Inspired by prompt learning in the language domain, we propose ICPF, a novel In-Context Prompt-augmented Framework to enhance popularity prediction. ICPF maintains a model-agnostic design, facilitating seamless integration with various multimodal fusion models. Specifically, the multi-branch retriever first retrieves similar modal content through within-modality similarities. Next, in-context prompt generator extracts semantic prior features of retrieved videos, producing in-context prompts that enhance pre-trained models with rich contextual knowledge. Finally, knowledge-augmented predictor captures complementary features including modal semantics and popularity information. Extensive experiments conducted on three datasets demonstrate the superiority of ICPF compared to 14 competitive baselines, while training only 4\% of model parameters.

In-context Prompt-augmented Micro-video Popularity Prediction

In this paper, we consider the k-center problem with outliers (the (k,z)-center problem) in the context of Massively Parallel Computation (MPC). Existing MPC algorithms for the (k,z)-center problem typically require 𝜴(k) local space per machine. While this may be feasible when k is small, these algorithms become impractical for large k, where each machine may lack sufficient space for computation. This motivates the study of fully-scalable algorithms with sublinear local space.  We propose the first fully-scalable MPC algorithm for the (k,z)-center problem. The main challenge is to design an MPC algorithm that operates with sublinear local space for finding the inliers close to the optimal clustering centers, and ensuring the approximation loss remains bounded. To address this issue, we propose an iterative sampling-based algorithms with sublinear local space in the data size. A key component of our approach is an outliers-removal algorithm that adjusts the sample size in each iteration to select inliers as clustering centers. However, the number of discarded outliers increases with the iteration of the outliers-removal algorithm, making it difficult to bound.  To address this, we propose a self-adaptive method that can automatically adjust sample size to account for different outliers distributions on each machine, ensuring a lower bound on the sampling success probability. With these two techniques, we present an O(log*n)-approximation MPC algorithm for the (k,z)-center problem in constant-dimensional Euclidean space. The algorithm opens k(1+o(1)) centers and discards at most (1+ε)z outliers, completing in O(loglog n) computation rounds while using O(n^𝛿) local space per machine.

Fully-Scalable Massively Parallel Algorithm for k-center with Outliers

Document summarization has greatly benefited from advances in large language models (LLMs). In real-world situations, summaries often need to be generated from multiple documents with diverse sources and authors, lacking a clear information flow. Naively concatenating these documents and generating a summary can lead to poorly structured narratives and redundancy. Additionally, attributing each part of the generated summary to a specific source is crucial for reliability. In this study, we address multi-document summarization with attribution using our proposed solution ***MiDAS-PRo***, consisting of three stages: (i) Planning the hierarchical organization of source documents, (ii) Reasoning by generating relevant entities/topics, and (iii) Summary Generation. We treat the first two sub-problems as a code completion task for LLMs. By incorporating well-selected in-context learning examples through a graph attention network, LLMs effectively generate plans and reason topics for a document collection. Experiments on summarizing scientific articles from public datasets show that our approach outperforms state-of-the-art baselines in both automated and human evaluations.

Language Models of Code Are Few-Shot Planners and Reasoners for Multi-Document Summarization with Attribution

Measuring the similarity of the internal representations of deep neural networks is an important and challenging problem.
Model stitching has been proposed as a possible approach, where two half-networks are connected by mapping the output of the first half-network to the input of the second one. The representations are considered functionally similar if the resulting stitched network achieves good task-specific performance. The mapping is normally created by training an affine stitching layer on the task at hand while freezing the two half-networks, a method called task loss matching. Here, we argue that task loss matching may be very misleading as a similarity measure. For example, it can indicate very high similarity between very distant layers, whose representations are known to have different functional properties. Moreover, it can indicate very distant layers to be more similar than architecturally corresponding layers. Even more surprisingly, when comparing layers within the same network, task loss matching often indicates that some layers are more similar to a layer than itself. We argue that the main reason behind these problems is that task loss matching tends to create out-of-distribution representations to improve task-specific performance. We demonstrate that direct matching (when the mapping minimizes the distance between the stitched representations) does not suffer from these problems. We compare task loss matching, direct matching, and well-known similarity metrics such as CCA and CKA. We conclude that direct matching strikes a good balance between the structural and functional requirements for a good similarity measure.

How Not to Stitch Representations to Measure Similarity: Task Loss Matching Versus Direct Matching

Code benchmarks such as HumanEval are widely adopted to evaluate the capabilities of Large Language Models (LLMs), providing insights into their strengths and weaknesses. However, current benchmarks primarily exercise LLMs' capability on common coding tasks (e.g., bubble sort, greatest common divisor), leaving **domain-specific coding tasks** (e.g., computation, system, cryptography)unexplored. To fill this gap, we propose a multi-domain code benchmark, DOMAINEVAL, designed to evaluate LLMs' coding capabilities thoroughly. Our pipeline works in a fully automated manner, enabling a push-bottom construction from code repositories into formatted subjects under study. Interesting findings are observed by evaluating 12 representative LLMs against DOMAINEVAL. We notice that LLMs are generally good at **computation** tasks while falling short on **cryptography and system** coding tasks. The performance gap can be as much as 68.94% (80.94% - 12.0%) in some LLMs. We also observe that generating more samples can increase the overall performance of LLMs, while the domain bias may even increase. The contributions of this study include a code generation benchmark dataset DOMAINEVAL, encompassing six popular domains, a fully automated pipeline for constructing code benchmarks, and an identification of the limitations of LLMs in code generation tasks based on their performance on DOMAINEVAL, providing directions for future research improvements.

DOMAINEVAL: An Auto-Constructed Benchmark for Multi-Domain Code Generation

Information retrieval methods often rely on a single embedding model trained on large, general-domain datasets like MSMARCO. While this approach can yield a retriever with reasonable overall performance, training a model on domain-specific data can yield better results within that domain. While prior work in information retrieval has tackled this problem via multi-task training or providing domain knowledge to an instruction-following retriever, the topic of combining different expert domain-specific retrievers has remained unexplored, despite its popularity in language model generation settings. In this work, we introduce RouterRetriever, a retrieval model that leverages multiple domain-specific experts and a routing mechanism to select the most appropriate expert for each query. It is lightweight and allows easy addition or removal of gates without additional training. Evaluation on the BEIR benchmark demonstrates that RouterRetriever outperforms both MSMARCO-trained (+2.1 absolute nDCG@10) and multi-task trained (+3.2) models. To achieve this, we developed a routing mechanism that shows higher performance over other routing techniques (+1.8 on average) that have been successfully employed in language modeling settings. Moreover, the benefit generalizes to other datasets even when there are no experts for that dataset. RouterRetriever is the first work to demonstrate the benefits of using multiple domain-specific expert embedding models with effective routing techniques compared to relying on a single embedding model for all domains in retrieval tasks.

RouterRetriever: Routing over a Mixture of Expert Embedding Models

In recent years, as data and problem sizes have increased, distributed learning has become an essential tool for training high-performance models. However, the communication bottleneck, especially for high-dimensional data, is a challenge. Several techniques have been developed to overcome this problem. These include communication compression and the implementation of local steps, which work particularly well when there is similarity of local data samples. In this paper, we study the synergy of these two approaches for efficient distributed optimization. Using variance reduction and error feedback frameworks, we present the first theoretically grounded accelerated algorithms with unbiased and biased compression for distributed problems under similarity. In terms of communicated time our theory gives $\tilde{\mathcal{O}} \left(  1+\left[ M^{-\frac{1}{4}} + \omega^{-\frac{1}{2}} \right]\sqrt{\frac{\delta}{\mu}}  \right)$ complexity for unbiased compressors and $\tilde{\mathcal{O}}\left(1+\beta^{\frac{1}{4}}\sqrt{\frac{\delta}{\mu}}\right)$ for biased ones, where $M$ is the number of computational nodes, $\beta$ is the compression power, $\delta$ is the similarity measure and $\mu$ is the parameter of strong convexity of objective. Our theoretical results are of record and confirmed by experiments on different average losses and datasets.

Downloads

Next from AAAI 2025

Kernel Learning for Sample Constrained Black-Box Optimization

Similar lecture

Draw Me a Flower: Processing and Grounding Abstraction in Natural Language

.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

Kernel Learning for Sample Constrained Black-Box Optimization

Similar lecture

Draw Me a Flower: Processing and Grounding Abstraction in Natural Language

Downloads