New Zealand


Recent success in reinforcement learning (RL) has brought renewed attention to the design of reward functions by which agent behavior is reinforced or deterred. Manually designing reward functions is tedious and error-prone. An alternative approach is to specify a formal, unambiguous logic requirement, which is automatically translated into a reward function to be learned from. Omega-regular languages, of which Linear Temporal Logic (LTL) is a subset, are a natural choice for specifying such requirements due to their use in verification and synthesis. However, current techniques based on omega-regular languages learn in an episodic manner whereby the environment is periodically reset to an initial state during learning. In some settings, this assumption is challenging or impossible to satisfy. Instead, in the continuing setting the agent explores the environment without resets over a single lifetime. This is a more natural setting for reasoning about omega-regular specifications defined over infinite traces of agent behavior. Optimizing the average reward instead of the usual discounted reward is more natural in this case due to the infinite-horizon objective that poses challenges to the convergence of discounted RL solutions. 

We restrict our attention to the omega-regular languages which correspond to \emph{absolute liveness} specifications. These specifications cannot be invalidated by any finite prefix of agent behavior, in accordance with the spirit of a continuing problem. We propose a translation from absolute liveness omega-regular languages to an average reward objective for RL. Our reduction can be done on-the-fly, without full knowledge of the environment, thereby enabling the use of model-free RL algorithms. Additionally, we propose a reward structure that enables RL without episodic resetting in communicating MDPs, unlike previous approaches. We demonstrate empirically with various benchmarks that our proposed method of using average reward RL for continuing tasks defined by omega-regular specifications is more effective than competing approaches that leverage discounted RL.

AAMAS 2022

Translating Omega-Regular Specifications to Average Objectives for Model-Free Reinforcement Learning

automata probabilistic logic uncertainty computational modeling learning (artificial intelligence) average reward reinforcement learning markov processes control system synthesis decision theory temporal logic limit deterministic büchi automaton rl algorithm ldba good for mdp automaton gfm reward machine ltl specification fully unknown mdp agent actions linear temporal logic formulas high-level control objectives control policies model-free reinforcement learning algorithm satisfaction guarantees temporal logic control synthesis satisfaction probability absolute liveness communicating mdp

The AGI conference series is the only major conference series devoted wholly and specifically to the creation of AI systems possessing general intelligence at the human level and ultimately beyond. By gathering together active researchers in the field, for presentation of results and discussion of ideas, we accelerate our progress toward our common goal.

Underline hosted the two main days of AGI 2020 on Wednesday June 24th and Thursday June 25th. Both days were **live-streamed** and you can read the full program bellow. All presentations are available for a **asynchronous viewing**. All presenters are grouped into panels. You can also hear guest talks by **Ben Goertzel** (SingularityNET), **Valery Tarasov** (Semenov Institute of Chemical Physics), **Tatiana Shavrina** (Sberbank) and **Joscha Bach** (MIT Media Lab). 

AGI-20

The AGI conference series is the only major conference series devoted wholly and specifically to the creation of AI systems possessing general intelligence at the human level and ultimately beyond. By gathering together active researchers in the field, for presentation of results and discussion of ideas, we accelerate our progress toward our common goal.

technical paper

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

The AAMAS conference series was initiated in 2002 in Bologna, Italy as a joint event comprising the 6th International Conference on Autonomous Agents (AA), the 5th International Conference on Multiagent Systems (ICMAS), and the 9th International Workshop on Agent Theories, Architectures, and Languages (ATAL).

Subsequent AAMAS conferences have been held in Melbourne, Australia (July 2003), New York City, NY, USA (July 2004), Utrecht, The Netherlands (July 2005), Hakodate, Japan (May 2006), Honolulu, Hawaii, USA (May 2007), Estoril, Portugal (May 2008), Budapest, Hungary (May 2009), Toronto, Canada (May 2010), Taipei, Taiwan (May 2011), Valencia, Spain (June 2012), Minnesota, USA (May 2013), Paris, France (May 2014), Istanbul, Turkey (May 2015), Singapore (May 2016), São Paulo (2017) and Stockholm, Sweden (2018), Montreal (May 2019), Auckland (May 2020, Virtual), London (May 2021, Virtual).
<br>
<br>



A ticket is required to attend this event, please register using the link below:

https://aamas2022-conference.auckland.ac.nz/attending/registration/

Registration Is Required

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).


In partially observable reinforcement learning, offline training gives access to latent information which is not available during online training and/or execution, such as the system state. Asymmetric actor-critic methods exploit such information by training a history-based policy via a state-based critic. However, many asymmetric methods lack theoretical foundation, and are only evaluated on limited domains. We examine the theory of asymmetric actor-critic methods which use state-based critics, and expose fundamental issues which undermine the validity of a common variant, and limit its ability to address partial observability. We propose an unbiased asymmetric actor-critic variant which is able to exploit state information while remaining theoretically sound, maintaining the validity of the policy gradient theorem, and introducing no bias and relatively low variance into the training process. An empirical evaluation performed on domains which exhibit significant partial observability confirms our analysis, demonstrating that unbiased asymmetric actor-critic converges to better policies and/or faster than symmetric and biased asymmetric baselines.

Unbiased Asymmetric Reinforcement Learning under Partial Observability


Recent Multi-Agent Reinforcement Learning (MARL) literature has been largely focused on Centralized Training with Decentralized Execution (CTDE) paradigm. CTDE has been a dominant approach for both cooperative and mixed environments due to its capability to efficiently train decentralized policies. While in mixed environments full autonomy of the agents can be a desirable outcome, cooperative environments allow agents to share information to facilitate coordination. Approaches that leverage this technique are usually referred as communication methods, as full autonomy of agents is compromised for better performance. Although communication approaches have shown impressive results, they do not fully leverage this additional information during training phase. In this paper, we propose a new communication method called MAMBA which utilizes on Model-Based Reinforcement Learning (MBRL) to further leverage centralized training in multi-agent environments. We show that communication between agents can be used to sustain a world model for each agent during execution phase while imaginary rollouts can be used for training, removing the necessity to interact with the environment. These properties yield sample efficient algorithm that can scale gracefully with the number of agents. We empirically confirm that MAMBA achieves good performance while reducing the number of interactions with the environment up to the orders of magnitude compared to Model-Free state-of-the-art approaches in challenging domains of SMAC and Flatland.

Scalable Multi-Agent Model-Based Reinforcement Learning


Multi-agent pathfinding is the problem of finding collision-free paths for a set of agents. Solving this problem optimally is computationally hard, therefore many techniques based on reductions to other formalisms were developed. In comparison to search-based techniques, the reduction-based techniques fall behind on large maps even for a small number of agents. To combat this phenomenon, we propose several strategies for pruning vertices off large instances that will most likely not be used by agents. First, we introduce these strategies conceptually and prove which of them maintain completeness and optimality. Eventually, we conduct an exhaustive evaluation and show that graph pruning strategies make reduction-based solvers comparable to search-based techniques on large maps while maintaining their advantage on small dense maps.

Reduction-based Solving of Multi-agent Pathfinding on Large Maps Using Graph Pruning


Multi-Agent Path Finding (MAPF) is a well studied problem with many existing optimal algorithms capable of solving a wide variety of instances, each with its own strengths and weaknesses. 
While for some instances the fastest algorithm can be easily determined, not enough is known about their performance to predict the fastest algorithm for every MAPF instance, or what makes some instances more difficult than others. There is no clear answer for which features dominate the hardness of MAPF instances. 
In this work, we study how betweenness centrality affects the empirical difficulty of MAPF instances. To that end, we benchmark the largest and most complete optimal MAPF algorithm portfolio to date. We analyze the algorithms' performance independently and as part of the portfolio, and discuss how betweenness centrality can be used to improve estimations of algorithm performance on a given instance of MAPF.

Betweenness Centrality in Multi-Agent Path Finding


Multi-agent path planning (MAPP) in continuous spaces is a challenging problem with significant practical importance. One promising approach could first construct graphs approximating the spaces called roadmaps, then apply multi-agent pathfinding (MAPF) algorithms on those roadmaps to derive a set of conflict-free trajectories. While conventional studies have just utilized roadmap construction methods developed for single-agent planning, it remains largely unexplored what can serve as effective roadmaps for multiple agents and how we can construct them. To this end, we propose a novel concept of graph representations of the space named cooperative timed roadmaps (CTRMs). CTRMs enable each agent to focus on their important locations around potential solution paths, in a way to consider the behavior of other agents to avoid inter-agent collisions (i.e., "cooperative"), while being augmented in time direction to make it easy to derive a "timed" solution path. To construct CTRMs, we develop a machine learning approach that learns a generative model from a collection of relevant problem instances and plausible solutions and uses the learned model to sample the vertices of CTRMs for new, previously-unseen problem instances. Our empirical evaluation revealed that the use of CTRMs significantly reduced the planning effort with acceptable overheads while maintaining its success rate and solution quality comparable to conventional roadmap construction approaches.

CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces


Planning for multi-robot coordination during long-horizon missions in complex environments requires considering robot resources, temporal constraints, and probabilistic uncertainty. This could be computationally expensive and impractical for online planning and execution. We propose a decoupled framework for temporal and probabilistic planning. At the high-level, we plan for multi-robot missions that require coordination amongst robots considering temporal and numeric constraints. The temporal plan is decomposed into low-level plans for individual robots. At the low-level, we perform online learning and adaptation due to unexpected probabilistic outcomes to achieve mission goals. Our framework learns over time from goal execution failures to improve the performance by (1) updating the learned domain model to reduce model prediction errors and (2) constraining the robot's capabilities which in turn improves goal allocation. The approach provides a solution to planning problems by pondering mission execution quality over implementation time. We demonstrate our approach to experiments involving a fleet of heterogeneous robots.

Planning, Execution, and Adaptation for Multi-Robot Systems using Probabilistic and Temporal Planning


A new mobile attention economy has emerged with the explosive growth of short-video apps such as TikTok. In this internet market, a short-video platform encourages its influencers to attract users by creating various short-form videos, and allows advertisers to display their short-video ads. There are two options for the advertisers: one is to bid for platform advert slots in a similar way to search engine auctions; the other is to pay an influencer to make engaging short videos and promote them through the influencer's channel. The second option will generate a higher conversion ratio if advertisers choose the right influencers whose followers match their target market. Although displaying influencer ads will generate less revenue, it is more engaging than platform ads, which is better for maintaining user traffic. Therefore, it is crucial for a platform to balance these factors by establishing a sustainable business agreement with its influencers and advertisers.
In this paper, we develop a two-stage solution for a platform to maximize short-term revenue and long-term user traffic maintenance. In the first stage, we estimate the impact of user traffic generated by displaying influencer ads and characterize the user traffic the platform should allocate to influencers for overall revenue maximization. We deploy an optimal $(1-1/e)$-competitive algorithm for ad slot allocation in the second stage. To complement this analysis, we examine the ratio of the revenue generated by our online algorithm to the optimal offline revenue. Our simulation results show that this ratio is 0.94 on average, which is much higher than $(1-1/e)$ and outperforms four baseline algorithms.

Revenue and User Traffic Maximization in Mobile Short-Video Advertising


Motivated by a broad class of mobile intervention problems, we propose and study restless multi-armed bandits (RMAB) with network effects. In our model, arms are partially recharging and connected through a graph, so that pulling one arm also improves the state of neighboring arms, significantly extending the previously studied setting of fully recharging bandits with no network effects. Our model is motivated by mobile intervention applications, where mobile services visit different locations to provide interventions, relevant in a variety of domains including mobile health interventions and food security, in which network effects arise due to regular population movements (such as commuting between home and work). We show that network effects in RMABs induce strong reward coupling that is not accounted for by existing solution methods. We propose a new solution approach for networked RMAB that exploits concavity structure that arises under natural assumptions on the structure of intervention effects. We show that our proposed algorithm is optimal for a large class of networked RMAB settings, and empirically demonstrate that it consistently outperforms state-of-the-art baselines.

Networked Restless Multi-Armed Bandits for Mobile Interventions


Peer incentivation (PI) is a recent approach, where all agents learn to reward or to penalize each other which often leads to emergent cooperation. Current PI mechanisms implicitly assume a flawless communication channel in order to exchange rewards. These rewards are directly integrated into the learning process without any chance to respond with feedback. Furthermore, most PI approaches rely on global information which limits scalability and applicability to real-world scenarios, where only local information is accessible. In this paper, we propose Mutual Acknowledgment Token Exchange (MATE), a PI approach defined by a two-phase communication protocol to mutually exchange acknowledgment tokens to shape individual rewards. Each agent evaluates the monotonic improvement of its individual situation in order to accept or reject acknowledgment requests from other agents. MATE is a completely decentralized approach which only requires local communication and information. We evaluate MATE in three social dilemma domains. Our results show that MATE is able to achieve and maintain significantly higher levels of cooperation than previous PI approaches. In addition, we evaluate the robustness of MATE in more realistic scenarios, where agents can defect from the protocol and where communication failures can occur.

Emergent Cooperation from Mutual Acknowledgment Exchange


We propose Streaming Bandits, a Restless Multi-Armed Bandit(RMAB) framework in which heterogeneous arms may arrive and leave the system after staying on for a finite lifetime. Streaming Bandits naturally capture the health-intervention planning problem, where health workers must manage the health outcomes of a patient cohort while new patients join and existing patients leave the cohort each day. Our contributions are as follows: (1) We de-rive conditions under which our problem satisfies indexability, a pre-condition that guarantees the existence and asymptotic optimality of the Whittle Index solution for RMABs. We establish the conditions using a polytime reduction of the Streaming Banditsetup to regular RMABs. (2) We further prove a phenomenon that we call index decay — whereby the Whittle index values decrease for short residual lifetimes — driving the intuition underpinning our algorithm. (3) We propose a novel and efficient algorithm to compute the index-based solution for Streaming Bandits. Unlike previous methods, our algorithm does not rely on solving the costly finite horizon problem on each arm of the RMAB, thereby lowering the computational complexity compared to existing methods. (4) Finally, we evaluate our approach via simulations run on real-world data sets from a tuberculosis patient monitoring task and an intervention planning task for improving maternal healthcare, in addition to other synthetic domains. Across the board, our algorithm achieves a 2-orders-of-magnitude speed-up over existing methods while maintaining the same solution quality

Translating Omega-Regular Specifications to Average Objectives for Model-Free Reinforcement Learning

Downloads

Next from AAMAS 2022

Unbiased Asymmetric Reinforcement Learning under Partial Observability

Similar lecture

The Dynamics of Growing Symbols: A Ludics Approach to Language Design by Autonomous Agents

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Translating Omega-Regular Specifications to Average Objectives for Model-Free Reinforcement Learning

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

Unbiased Asymmetric Reinforcement Learning under Partial Observability

Similar lecture

The Dynamics of Growing Symbols: A Ludics Approach to Language Design by Autonomous Agents

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads