United Kingdom

This paper presents new algorithms and theoretical results for solutions to Multi-action Multi-armed Restless Bandits, an important but insufficiently studied generalization of traditional Multi-armed Restless Bandits (MARBs). Though MARBs are popular for modeling many problems, they are restricted to binary actions, i.e., &quot;to act or not to act&quot;. This renders them unable to capture critical complexities faced by planners in real domains, such as a system manager balancing maintenance, repair, and job scheduling, or a health worker deciding among treatments for a given patient. Limited previous work on Multi-action MARBs has only been specialized to sub-problems. Here we derive multiple algorithms for use on general Multi-action MARBs using Lagrangian relaxation techniques, leading to the following contributions: (i) We develop BLam, a bound optimization algorithm which leverages problem convexity to quickly and provably converge to the well-performing Lagrange policy; (ii) We develop SampleLam, a fast sampling technique for estimating the Lagrange policy, and derive a concentration bound to investigate its convergence properties; (iii) We derive best and worst case computational complexities for our algorithms as well as our main competitor; (iv) We provide experimental results comparing our algorithms to baselines on simulated distributions, including one motivated by a real-world community health intervention task. Our approach achieves significant, up to ten-fold speedups over more general methods without sacrificing performance and is widely applicable across general Multi-action MARBs. Code is available at https://github.com/killian-34/MAMARB-Lagrange-Policies.

AAMAS 2021

Beyond &quot;To Act or Not to Act&quot;: Fast Lagrangian Approaches to General Multi-Action Restless Bandits

EMNLP 2021 is planned to be a hybrid event in Punta Cana, Dominican Republic, with both on-site and fully virtual participation possible. The experience for on-site participants would closely approximate a normal pre-COVID *ACL conference, with 5-6 thematically organized parallel sessions and live Q/A and interactive discussion immediately after the talks. Presentations by virtual participants will be equitably interleaved with those of on-site participants, projected on the auditorium screens as if on-site, and also followed immediately by live Q/A and interactive discussion at a time during reasonable waking hours for the virtual presenter. For all participants, on-site and virtual, who are unable to attend a session due to either time-zone issues or because they are participating in another session live, talk recordings and slides will be available online at a minimum after the live presentation (and in many cases before as well), and questions may be submitted in advance on session-specific discussion boards and answered live in session with the usual visual aids if desired.

<iframe style="width:700px;height:400px" src="https://online.fliphtml5.com/ebtyf/ceby/"  seamless="seamless" scrolling="no" frameborder="0" allowtransparency="true" allowfullscreen="true" ></iframe>

Please Note: The EMNLP registration system is not currently connected to the underline site as we are still in the process of building out EMNLP 2021. You will receive access instructions from underline the week of November 1st. 

Access is given only to EMNLP upon registration, if you have not registered please do so [here](https://2021.emnlp.org/registration).

Registered attendees will receive access the week of November 1st.

EMNLP 2021

EMNLP 2021 is planned to be a hybrid event in Punta Cana, Dominican Republic, with both on-site and fully virtual participation possible.

This paper presents new algorithms and theoretical results for solutions to Multi-action Multi-armed Restless Bandits, an important but insufficiently studied generalization of traditional Multi-armed Restless Bandits (MARBs). Though MARBs are popular for modeling many problems, they are restricted to binary actions, i.e., "to act or not to act". This renders them unable to capture critical complexities faced by planners in real domains, such as a system manager balancing maintenance, repair, and job scheduling, or a health worker deciding among treatments for a given patient. Limited previous work on Multi-action MARBs has only been specialized to sub-problems. Here we derive multiple algorithms for use on general Multi-action MARBs using Lagrangian relaxation techniques, leading to the following contributions: (i) We develop BLam, a bound optimization algorithm which leverages problem convexity to quickly and provably converge to the well-performing Lagrange policy; (ii) We develop SampleLam, a fast sampling technique for estimating the Lagrange policy, and derive a concentration bound to investigate its convergence properties; (iii) We derive best and worst case computational complexities for our algorithms as well as our main competitor; (iv) We provide experimental results comparing our algorithms to baselines on simulated distributions, including one motivated by a real-world community health intervention task. Our approach achieves significant, up to ten-fold speedups over more general methods without sacrificing performance and is widely applicable across general Multi-action MARBs. Code is available at https://github.com/killian-34/MAMARB-Lagrange-Policies.

Beyond "To Act or Not to Act": Fast Lagrangian Approaches to General Multi-Action Restless Bandits

technical paper

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

Asymmetric distributed constraint optimization problems (ADCOPs) in which agents are partially cooperative, is a model for representing multi-agent optimization problems  in which agents, are willing to cooperate in order to achieve a global goal,  as long as some minimal threshold on their personal utility is satisfied.

Partially Cooperative Multi-Agent Periodic Indivisible Resource Allocation

In this paper, we extend the unavailable candidate model (Tyler Lu and Craig Boutilier, The Unavailable Candidate Model : a Decision-Theoretic View of Social Choice, 2010) and present two new voting rules based on a finer notion of disagreement, called dissatisfaction, which depends on the ranks of the candidates, considered among all the candidates (
 rule) or only among the available candidates (
 rule). We provide algorithmic results for the two rules and show that apparently very different voting rules such as scoring rules or Kemeny rule can be unified under the same aggregation concept: expectation of dissatisfaction under the availability distribution.

Rank Aggregation by Dissatisfaction Minimisation in the Unavailable Candidate Model

A finite-time consensus protocol is developed for a connected network of agents, where communication between agents occurs locally, some of the agents are malicious, and the non-malicious or cooperative agents do not know the identities of the malicious ones. The agents are modeled with first-order dynamics, and the inputs to each agent that enable consensus are designed using the principles of sliding mode control (SMC). The use of the SMC algorithm guarantees finite-time consensus and ensures that in the transient stage, the agents' states are contained within the convex hull formed by their initial conditions (ICs). With this feature and by modeling the network as a connected graph, the protocol guarantees consensus amongst the cooperative agents when the malicious agents transmit values of their states lying outside the convex hull of ICs, and the graph formed by the cooperative agents with the removal of the malicious agents is strongly connected. The protocol does not require a cooperative agent to know the number of malicious or other cooperative agents in the network, and is based only on local communication.

Finite-time Consensus in the Presence of Malicious Agents

We explore the possibility of an alternative cryptocurrency that is egalitarian in control, just in the distribution of its created wealth, and forms and grows in a grassroots way; we analyze it via a mathematical entity called a 
 Our main result states sufficient conditions for the establishment of 1:1 exchange rates and distributive justice in a currency network.

Egalitarian and Just Digital Currency Networks

Crowdfunding has become an effective way of raising capital for
developing and producing new products. In a typical crowdfunding campaign, a fundraiser (a seller) sets a product pre-buy price
and a campaign success threshold. Consumers can indicate their
willingness to pay the pre-buy price now, in exchange of a product
in the future. Only when the number of consumers who commit to
pre-buy exceeds the threshold, the crowdfunding is successful and
the seller gets the corresponding pre-buy payments.
A series of works has modeled crowdfunding as imperfect information games, where each player (potential contributor) has a
private valuation for the product, and has characterized the equilibrium behavior for some specific settings [1–4]. Other works focus
on the effectiveness or the moral hazard of the crowdfunding campaigns by regarding it as an option to raise money for either private
[5, 9, 10] or public projects [6–8].
However, the strategic aspect of crowdfunding from the seller’s
perspective hasn’t attracted its deserved attention. In this paper,
we take a mechanism design perspective and explore how a seller
can design crowdfunding campaigns to maximize his profit. In
addition to choosing the pre-buy price and the campaign success
threshold for a crowdfunding campaign, the seller in our paper can
consider two richer design variants: (1) choose two price-threshold
pairs where a pre-buy price discount is given when the number
of committed buyers exceeds the larger threshold, and (2) offer
two differentiating products (simplified vs. standard) and set two
success thresholds such that the advanced product will be delivered
if the larger threshold is reached. We examine the optimal profit
achieved in each scheme. Somewhat surprisingly, the richer design
variants may not improve the seller’s profit.

Optimal Crowdfunding Design

Individuals in a social network may form their views as a result of the influence exerted by their connections. In elections, for example, while they might initially support one candidate, social influence may lead them to support another. Here, we investigate whether a recently proposed metric, influence gap, designed to measure the effect of social influence in voting on social networks, is able to predict the outcome of a vote on networks exhibiting community structure, i.e., made of highly interconnected components, and therefore more resembling of real-world interaction. To encode communities, we extend the classical model of caveman graphs to a richer graph family that displays levels of homophily, i.e., where connections and opinions are highly intertwined. We show that, across these graphs, there are important cases when the influence gap correlation is a weak predictor due to communities, and a simpler metric, counting the initial partisan majority, provides a more accurate prediction overall. Using regression models, we further demonstrate that the influence gap combined with the more successful metrics does increase their predictive power for some levels of homophily.

Predicting Voting Outcomes in Presence of Communities

In swarm robotics, research mainly follows a theoretical approach that considers robot systems in the abstract, where the complexity and capabilities of the underlying model are often reduced to their minimum. One general and well-investigated model is &#248;blot, where the robots are silent, anonymous, and oblivious. In this work, we introduce MOBLOT, a model that extends &#248;blot to address a larger spectrum of cases. MOBLOT stands for molecular oblivious robots: like atoms combine themselves to form molecules, in MOBLOT simple robots can move to form more complex computational units, having an extent and different capabilities with respect to robots; like molecules combine themselves to form the matter, in MOBLOT the complex structures can exploit their own capabilities to arrange themselves to form any shape defining an acceptable final structure.   In MOBLOT, we formally define the Matter Formation (MF) problem and, as a preliminary general result, we provide a necessary condition for its solvability which relies on symmetricity.  Informally, the symmetricity of a configuration measures the amount of symmetries of the robots' disposal.  We actually show how dealing with molecules can resolve in some cases the symmetry breaking issue where &#248;blot cannot. Finally, we provide a case study for MOBLOT, that is, a representative MF problem along with a resolution distributed algorithm.

MOBLOT: Molecular Oblivious Robots

Multi-agent reinforcement learning (MARL) requires coordination to efficiently solve certain tasks. Fully centralized control is often infeasible in such domains due to the size of joint action spaces. Coordination graph based formalization allows reasoning about the joint action based on the structure of interactions. However,they often require domain expertise in their design. This paper introduces the deep implicit coordination graph (DICG) architecture for such scenarios. DICG consists of a module for inferring the dynamic coordination graph structure which is then used by a graph neural network based module to learn to implicitly reason about the joint actions or values. DICG allows learning the tradeoff between full centralization and decentralization via standard actor-critic methods to significantly improve coordination for domains with large number of agents. We apply DICG to both centralized-training-centralized-execution and centralized-training-decentralized-execution regimes. We demonstrate that DICG solves the relative over generalization pathology in predatory-prey tasks as well as outperforms various MARL baselines on the challenging StarCraft II Multi-agent Challenge (SMAC) and traffic junction environments.

Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning

Partially Observable Monte-Carlo Planning (POMCP) is a powerful online algorithm able to generate approximate policies for large Partially Observable Markov Decision Processes. The online nature of this method supports scalability by avoiding complete policy representation. The lack of an explicit representation however hinders interpretability. In this work, we propose a methodology based on Satisfiability Modulo Theory (SMT) for analyzing POMCP policies by inspecting their traces, namely sequences of belief-action-observation triplets generated by the algorithm. The proposed method explores local properties of policy behavior to identify unexpected decisions. We propose an iterative process of trace analysis consisting of three main steps, i) the definition of a 
 by means of a parametric logical formula describing (probabilistic) relationships between beliefs and actions, ii) the generation of an 
 by computing the parameters of the logical formula that maximize the number of satisfied clauses (solving a MAX-SMT problem), iii) the analysis of the generated logical formula and the related decision boundaries for identifying unexpected decisions made by POMCP with respect to the original question. We evaluate our approach on Tiger, a standard benchmark for POMDPs, and a real-world problem related to mobile robot navigation. Results show that the approach can exploit human knowledge on the domain, outperforming state-of-the-art anomaly detection methods in identifying unexpected decisions. An improvement of the Area Under Curve up to 47% has been achieved in our tests.

Identification of Unexpected Decisions in Partially Observable Monte-Carlo Planning: A Rule-Based Approach

Traffic congestion is a major challenge in modern urban settings. The industry-wide development of autonomous and automated vehicles (AVs) motivates the question of how can AVs contribute to congestion reduction. Past research has shown that in small scale mixed traffic scenarios with both AVs and human-driven vehicles, a small fraction of AVs executing a controlled multiagent driving policy can mitigate congestion. In this paper, we scale up existing approaches and develop new multiagent driving policies for AVs in scenarios with greater complexity. We start by showing that a congestion metric used by past research is manipulable in open road network scenarios where vehicles dynamically join and leave the road. We then propose using a different metric that is robust to manipulation and reflects open network traffic efficiency. Next, we propose a modular transfer learning approach and use it to scale up the multiagent driving policy to a realistic simulated scenario that is an order of magnitude larger than past scenarios (hundreds rather than tens of vehicles). Our experimental study shows that the resulting policy improves traffic efficiency over human-driven traffic in a large open network, where existing approaches fail to do so. Another key advantage of our modular transfer learning approach is that it avoids collecting samples from entire network, which saves up to 80% of training and data collection time in our experiments. Finally, we show for the first time a distributed multiagent policy that improves congestion over human-driven traffic. The distributed approach is more realistic as it does not require adding communication infrastructure, it relies on existing sensing capabilities, and its complexity scales linearly with the number of vehicles.

Beyond "To Act or Not to Act": Fast Lagrangian Approaches to General Multi-Action Restless Bandits

Downloads

Next from AAMAS 2021

Partially Cooperative Multi-Agent Periodic Indivisible Resource Allocation

Similar lecture

Few-Shot Named Entity Recognition: An Empirical Baseline Study

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Beyond "To Act or Not to Act": Fast Lagrangian Approaches to General Multi-Action Restless Bandits

.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 AAMAS 2021

Partially Cooperative Multi-Agent Periodic Indivisible Resource Allocation

Similar lecture

Few-Shot Named Entity Recognition: An Empirical Baseline Study

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads