United States

Multi-Agent Reinforcement Learning (MARL) has been increasingly used in safety-critical applications but has no safety guarantees, especially during training. In this paper, we propose dynamic shielding, a novel decentralized MARL framework to ensure safety in both the training and deployment phases. Our framework leverages Shield, a reactive system running in parallel with the reinforcement learning algorithm, to monitor and correct agents’ behavior. In our algorithm, shields dynamically split and merge according to the environment state in order to maintain decentralization and avoid conservative behaviors while enjoying formal safety guarantees. We demonstrate the effectiveness of MARL with dynamic shielding in the mobile navigation scenario.

AAAI 2023

Tackling Safe and Efficient Multi-Agent Reinforcement Learning via Dynamic Shielding (Student Abstract)

robustness & trustworthiness mas: multiagent learning

ml: reinforcement learning algorithms peai: safety

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-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/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.

lightning talk

Applications such as employees sharing office spaces over
a workweek can be modeled as problems where agents are
matched to resources over multiple rounds. Agents’ require-
ments limit the set of compatible resources and the rounds in
which they want to be matched. Viewing such an application
as a multi-round matching problem on a bipartite compati-
bility graph between agents and resources, we show that a
solution can be found efficiently if one exists. To cope with
situations where a solution does not exist, we consider two
extensions. In the first extension, a benefit function is defined
for each agent and the objective is to find a solution to maxi-
mize the total benefit. For a general class of benefit functions
satisfying certain properties (including diminishing returns),
we show that this multi-round matching problem is efficiently
solvable. This class includes utilitarian and Rawlsian wel-
fare functions. For another benefit function, we show that the
maximization problem is NP-hard. In the second extension,
the objective is to generate advice to each agent (i.e., a subset
of requirements to be relaxed) subject to a budget constraint
so that the agent can be matched. We show that this budget-
constrained advice generation problem is NP-hard. For this
problem, we develop an integer linear programming formu-
lation as well as a heuristic based on local search. We exper-
imentally evaluate our algorithms on synthetic networks and
apply them to two real-world situations: shared office spaces
and matching courses to classrooms.

Resource Sharing Through Multi-Round Matchings

Although weakly-supervised techniques can reduce the labeling effort, it is unclear whether a saliency model trained with weakly-supervised data (e.g., point annotation) can achieve the equivalent performance of its fully-supervised version. This paper attempts to answer this unexplored question by proving a hypothesis: there is a point-labeled dataset where saliency models trained on it can achieve equivalent performance when trained on the densely annotated dataset. To prove this conjecture, we proposed a novel yet effective adversarial trajectory-ensemble active learning (ATAL). Our contributions are three-fold:  1) Our proposed adversarial attack triggering uncertainty can conquer the overconfidence of existing active learning methods and accurately locate these uncertain pixels. {2)} Our proposed trajectory-ensemble uncertainty estimation method maintains the advantages of the ensemble networks while significantly reducing the computational cost. {3)} Our proposed relationship-aware diversity sampling algorithm can conquer oversampling while boosting performance.
Experimental results show that our ATAL can find such a point-labeled dataset, where a saliency model trained on it obtained $97\%$ -- $99\%$ performance of its fully-supervised version with only ten annotated points per image.

Pixel is All You Need: Adversarial Trajectory-Ensemble Active Learning for Salient Object Detection

Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. In such games, agents maximize their utility by choosing strategies (i.e., actions) that differ from their neighbors’ strategies. Two important problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time of the dynamics. In this work, we study these two problems for anti-coordination games under sequential and synchronous dynamics. For each type of dynamics, we examine two decision-making modes based on whether an agent considers its own previous action (self essential mode) or not (self non-essential mode) in choosing its next action. Using a relationship between anti-coordination games and discrete graphical dynamical systems, we show that for both forms of dynamics, finding an NE can be done efficiently for the self non-essential mode but is computationally intractable under the self essential mode. To cope with this hardness, we identify some special cases for which an NE can be found efficiently, and present the corresponding algorithms. With respect to convergence time, we show that the dynamics converges in a polynomial number of steps in the synchronous case for both modes; for the sequential case, the convergence time is polynomial only for the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.

Networked Anti-Coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence

The facility location game is an extensively studied problem in mechanism design. In the classical model, the cost of each agent is her distance to the nearest facility. In this paper, we consider a novel model where each facility charges an entrance fee, which is a function of the facility's location. Thus, in our model, the cost of each agent is the sum of the distance to the facility and the entrance fee of the facility. The generalized model captures more real-life scenarios. In our model, the entrance fee function can be an arbitrary function, and the corresponding preferences of agents may not be single-peaked anymore: this makes the problem complex and requires new techniques in the analysis. We systematically study the model and design strategyproof mechanisms with nice approximation ratios and also complement these with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms, with respect to the utilitarian and egalitarian objectives. Most of our bounds are tight, and these bounds are independent of the entrance fee functions. Our results also match the results of the classical model.

Facility Location Games with Entrance Fees

Epistemic logics typically talk about knowledge of individual agents or groups of explicitly listed agents. Often, however, one wishes to express knowledge of groups of agents specified by a given property, as in ‘it is common knowledge among economists’. We introduce such a logic of common knowledge, which we term abstract-group epistemic logic (AGEL). That is, AGEL features a common knowledge operator for groups of agents given by concepts in a separate agent logic that we keep generic, with one possible agent logic being ALC. We show that AGEL is EXPTIME-complete, with the lower bound established by reduction from standard group epistemic logic, and the upper bound by a satisfiability-preserving embedding into the full µ-calculus. Further main results include a finite model property (not enjoyed by the full µ-calculus) and a complete axiomatization.

Common Knowledge of Abstract Groups

Graph Neural Networks (GNNs) are powerful tools for graph representation learning. Despite their rapid development, GNNs also face some challenges, such as over-fitting, over-smoothing, and non-robustness. Previous works indicate that these problems can be alleviated by random dropping methods, which integrate augmented data into models by randomly masking parts of the input. However, some open problems of random dropping on GNNs remain to be solved. First, it is challenging to find a universal method that are suitable for all cases considering the divergence of different datasets and models. Second, augmented data introduced to GNNs causes the incomplete coverage of parameters and unstable training process. Third, there is no theoretical analysis on the effectiveness of random dropping methods on GNNs. In this paper, we propose a novel random dropping method called DropMessage, which performs dropping operations directly on the propagated messages during the message-passing process. More importantly, we find that DropMessage provides a unified framework for most existing random dropping methods, based on which we give theoretical analysis of their effectiveness. Furthermore, we elaborate the superiority of DropMessage: it stabilizes the training process by reducing sample variance; it keeps information diversity from the perspective of information theory, enabling it become a theoretical upper bound of other methods. To evaluate our proposed method, we conduct experiments that aims for multiple tasks on five public datasets and two industrial datasets with various backbone models. The experimental results show that DropMessage has the advantages of both effectiveness and generalization, and can significantly alleviate the problems mentioned above. A detailed version with full appendix can be found on arXiv: https://arxiv.org/abs/2204.10037.

DropMessage: Unifying Random Dropping for Graph Neural Networks

Previous research on the comprehensive negotiation strategy using deep reinforcement learning (RL) has scalability issues of not performing effectively in the large-sized domains.
We improve negotiation strategy via deep RL by considering an issue-based represented deep policy network to deal with multi-issue negotiation.
The architecture of the proposed learning agent considers the characteristics of multi-issue negotiation domains and policy-based learning.
We demonstrate that proposed method achieve equivalent or higher utility than existing negotiation agents in the large-sized domains.

Scalable Negotiating Agent Strategy via Multi-Issue Policy Network (Student Abstract)

Modern social networks are dynamic in their nature; new connections are appearing, and old connections are disappearing all the time. However, in our algorithmic and complexity studies, we usually model social networks as static graphs.

In this paper, we propose a new paradigm for the study of the well-known Target Set Selection problem, which is a fundamental problem in viral marketing and the spread of opinion through social networks. In particular, we use temporal graphs to capture the dynamic nature of social networks.

We show that the temporal interpretation is, unsurprisingly, NP-complete in general. Then, we study the computational complexity of this problem for multiple restrictions of both the threshold function and the underlying graph structure and provide multiple hardness lower bounds.

Maximizing Influence Spread through a Dynamic Social Network

Conversational Systems (CSys) represent practical and tangible outcomes of advances in NLP and AI. CSys see continuous improvements through unsupervised training of large language models (LLMs) on a humongous amount of generic training data. However, when these CSys are suggested for use in domains like Mental Health, they fail to match the acceptable standards of clinical care, such as the clinical process in Patient Health Questionnaire (PHQ-9). The talk will present, Knowledge-infused Learning (KiL), a paradigm within NeuroSymbolic AI that focuses on making machine/deep learning models (i) learn over knowledge-enriched data, (ii) learn to follow guidelines in process-oriented tasks for safe and reasonable genera-
tion, and (iii) learn to leverage multiple contexts and stratified knowledge to yield user-level explanations. KiL established Knowledge-Intensive Language Understanding, a set of tasks for assessing safety, explainability, and conceptual flow in CSys.

Targeted Knowledge Infusion To Make Conversational AI Explainable and Safe

A hallmark of human intelligence is that we continue to learn new information and then extrapolate the learned information onto new tasks and domains (Thrun and Pratt (1998)). While this is a fairly intuitive observation, formulating such ideas has proved to be a challenging research problem and continues to inspire new studies. Recently, there has been increasing interest in AI/ML about building models that generalize across tasks, even when they have some form of distribution shifts. How can we ground this research in a solid framework to develop principled methods for better practice? This talk will present my recent works addressing this research question, including understanding information transfer in multitask learning, identifying negative transfers in multitask learning using surrogate models, and positive and negative generalizations in data augmentation.

Premium content

Tackling Safe and Efficient Multi-Agent Reinforcement Learning via Dynamic Shielding (Student Abstract)

Downloads

Next from AAAI 2023

Resource Sharing Through Multi-Round Matchings

Similar lecture

An Action Language for Multi-Agent Domains