New Zealand

Pablo M. Olmos, Juan Jose Murillo-Fuentes and Fernando Perez-Cruz (February 1st 2010). Gaussian Processes and its Application to the design of Digital Communication Receivers, Application of Machine Learning, Yagang Zhang, IntechOpen, DOI: 10.5772/8617.

We tackle the problem of learning equilibria in simulation-based games. In such games, the players&#39; utility functions cannot be described analytically, as they are given through a black-box simulator that can be queried to obtain noisy estimates of the utilities. This is the case in many real-world games in which a complete description of the elements involved is not available upfront, such as complex military settings and online auctions. In these situations, one usually needs to run costly simulation processes to get an accurate estimate of the game outcome. As a result, solving these games begets the challenge of designing learning algorithms that can find (approximate) equilibria with high confidence, using as few simulator queries as possible. Moreover, since running the simulator during the game is unfeasible, the algorithms must first perform a pure exploration learning phase and, then, use the (approximate) equilibrium learned this way to play the game. In this work, we focus on two-player zero-sum games with infinite strategy spaces. Drawing from the best arm identification literature, we design two algorithms with theoretical guarantees to learn maximin strategies in these games. The first one works in the fixed-confidence setting, guaranteeing the desired confidence level while minimizing the number of queries. Instead, the second algorithm fits the fixed-budget setting, maximizing the confidence without exceeding the given maximum number of queries. First, we formally prove delta-PAC theoretical guarantees for our algorithms under some regularity assumptions, which are encoded by letting the utility functions be drawn from a Gaussian process. Then, we experimentally evaluate our techniques on a testbed made of randomly generated games and instances representing simple real-world security settings.

AAMAS 2020

Learning Probably Approximately Correct Maximin Strategies in Simulation-Based Games with Infinite Strategy Spaces

simulation-based games; gaussian process; pac learning

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

We tackle the problem of learning equilibria in simulation-based games. In such games, the players' utility functions cannot be described analytically, as they are given through a black-box simulator that can be queried to obtain noisy estimates of the utilities. This is the case in many real-world games in which a complete description of the elements involved is not available upfront, such as complex military settings and online auctions. In these situations, one usually needs to run costly simulation processes to get an accurate estimate of the game outcome. As a result, solving these games begets the challenge of designing learning algorithms that can find (approximate) equilibria with high confidence, using as few simulator queries as possible. Moreover, since running the simulator during the game is unfeasible, the algorithms must first perform a pure exploration learning phase and, then, use the (approximate) equilibrium learned this way to play the game. In this work, we focus on two-player zero-sum games with infinite strategy spaces. Drawing from the best arm identification literature, we design two algorithms with theoretical guarantees to learn maximin strategies in these games. The first one works in the fixed-confidence setting, guaranteeing the desired confidence level while minimizing the number of queries. Instead, the second algorithm fits the fixed-budget setting, maximizing the confidence without exceeding the given maximum number of queries. First, we formally prove delta-PAC theoretical guarantees for our algorithms under some regularity assumptions, which are encoded by letting the utility functions be drawn from a Gaussian process. Then, we experimentally evaluate our techniques on a testbed made of randomly generated games and instances representing simple real-world security settings.

technical paper

We build on an emerging line of work which studies strategic manipulations in training data provided to machine learning algorithms.Specifically, we focus on the ubiquitous task of linear regression.Prior work focused on the design of strategyproof algorithms, which aim to prevent such manipulations altogether by aligning the incentives of data sources. However, algorithms used in practice are often not strategyproof, which induces a strategic game among the agents. We focus on a broad class of non-strategyproof algorithms for linear regression, namely ℓpnorm minimization (p>1)with convex regularization. We show that when manipulations are bounded, every algorithm in this class admits a unique pure Nash equilibrium outcome. We also shed light on the structure of this equilibrium by uncovering a surprising connection between strategyproof algorithms and pure Nash equilibria of non-strategyproof algorithms in a broader setting, which may be of independent interest. Finally, we analyze the quality of equilibria under these algorithms in terms of the price of anarchy.

The Effect of Strategic Noise in Linear Regression

In strategic candidacy games, both voters and candidates have pref- erences over the set of possible election outcomes, and candidates may strategically withdraw from the election in order to manipu- late the result in their favor. In this work, we extend the candidacy game model to the setting of multiwinner elections, where the goal is to select a fixed-size subset of candidates (a committee), rather than a single winner. We examine the existence and properties of Nash equilibria in the resulting class of games, under various voting rules and voter preference structures.

Multiwinner Candidacy Games

Several recent works have found the emergence of grounded compositional language in the communication protocols developed by mostly cooperative multi-agent systems when learned end-to-end to maximize performance on a downstream task. However, human populations learn to solve complex tasks involving communicative behaviors not only in fully cooperative settings but also in scenarios where competition acts as an additional external pressure for improvement. In this work, we investigate whether competition for performance from an external, similar agent team could act as a social influence that encourages multi-agent populations to develop better communication protocols for improved performance, compositionality, and convergence speed. We start from Task & Talk, a previously proposed referential game between two cooperative agents as our testbed and extend it into Task, Talk & Compete, a game involving two competitive teams each consisting of two aforementioned cooperative agents. Using this new setting, we provide an empirical study demonstrating the impact of competitive influence on multi-agent teams. Our results show that an external competitive influence leads to improved accuracy and generalization, as well as faster emergence of communicative languages that are more informative and compositional.

On Emergent Communication in Competitive Multi-Agent Teams

"In multi-capacity ridesharing, multiple requests (e.g., customers, food items, parcels) with different origin and destination pairs travel in one resource. In recent years, online multi-capacity ridesharing services (i.e., where assignments are made online) like Uber-pool, foodpanda, and on-demand shuttles have become hugely popular in transportation, food delivery, logistics and other domains. This is because multi-capacity ridesharing services benefit all parties involved – the customers (due to lower costs), the drivers (due to higher revenues) and the matching platforms (due to higher revenues per vehicle/resource). Most importantly these services
can also help reduce carbon emissions (due to fewer vehicles on roads).
Online multi-capacity ridesharing is extremely challenging as the underlying matching graph is no longer bipartite (as in the unit-capacity case) but a tripartite graph with resources (e.g., taxis,
cars), requests and request groups (combinations of requests that can travel together). The desired matching between resources and request groups is constrained by the edges between requests and request groups in this tripartite graph (i.e., a request can be part of at most one request group in the final assignment). While there have been myopic heuristic approaches employed for solving the online multi-capacity ridesharing problem, they do not provide any
guarantees on the solution quality. To that end, this paper presents the first approach with bounds on the competitive ratio for online multi-capacity ridesharing (when resources rejoin the system at their initial location/depot after serving a group of requests)."

Competitive Ratios for Online Multi-capacity Ridesharing

How about Explainability in Human-Agent Systems

Incentivised decision markets are mechanisms that allow selecting one action among a set of actions based on properly incentivised forecasts about the actions' consequences. Existing research on decision markets is based on scoring rules. Because scoring rules based decision markets involve two-side liabilities that can be difficult to track, we here study more convenient securities based decision markets. We present a decision market setting that prices securities using a cost function derived from a scoring rule. In such a decision market setting, traders will have the same expected utility as forecasters measured by the corresponding scoring rule. Moreover, we identify differences between scoring rules based decision markets and securities based decision markets in terms of actual payoffs. Lastly, we describe an insurance mechanism that can shift risk from the market creator to a risk-neutral third party.

Decision Markets Implementation

Moving target defense has emerged as a critical paradigm of protecting a vulnerable system against persistent and stealthy attacks. To protect a system, a defender proactively changes the system configurations to limit the exposure of security vulnerabilities to potential attackers. In doing so, the defender creates asymmetric uncertainty and complexity for the attackers, making it much harder for them to compromise the system. In practice, the defender incurs a switching cost for each migration of the system configurations. The switching cost usually depends on both the current configuration and the following configuration. Besides, different system configurations typically require a different amount of time for an attacker to exploit and attack. Therefore, a defender must simultaneously decide both the optimal sequences of system configurations and the optimal timing for switching. In this paper, we propose a Markov Stackelberg Game framework to precisely characterize the defender's spatial and temporal decision-making in the face of advanced attackers. We introduce a relative value iteration algorithm that computes the defender's optimal moving target defense strategies. Empirical evaluation on real-world problems demonstrates the advantages of the Markov Stackelberg game model for spatial-temporal moving target defense.

Spatial-Temporal Moving Target Defense: A Markov Stackelberg Game Model

Introducing DCRAC, a deep reinforcement learning framework for solving multi-objective partially-observable problems. DCRAC follows a conditioned actor-critic approach in
learning the optimal policy.

DCRAC: Deep Conditioned Recurrent Actor-Critic for Multi-Objective Partially Observable Environments

This tutorial will survey results on fairness in resource allocation. Starting from the classical setting of cake-cutting, the tutorial will explore the allocation of divisible and indivisible goods, public decision-making, and online resource allocation. The tutorial will include various formal definitions of fairness, relations among these definitions, and algorithms for (and complexity of) satisfying such definitions.

Recent Advances in Fair Resource Allocation Tutorial Part 1

A quadcopter can capture photos from vantage points unattainable for a human photographer, but teloperating it to a good viewpoint is a non-trivial task. Since humans are good at composing photos, the aim of our research is to leverage deep learning to create a customizable flight controller that can capture photos under the guidance of a human photographer. Our system, the Selfie Drone Stick, allows the user to assign a vantage point to the quadcopter based on the phone's sensors. The user takes a selfie with the phone once, and the quadcopter autonomously flies to the target viewpoint. The proliferation of open source deep learning models provided us with a large variety of options for the computer vision and flight control systems. This article describes three key innovations required to deploy the models on a real robot: 1) a new architecture for rapid object detection, DUNet; 2) an abstract state representation for transferring learning from simulation to the hardware platform; 3) reward shaping and staging paradigms for training a deep reinforcement learning controller. Without these improvements, we were unable to learn a flight controller that adequately supported the intuitive user interface.

Downloads

Next from AAMAS 2020

The Effect of Strategic Noise in Linear Regression

Similar lecture

Improved Algorithms for Learning Equilibria in Simulation-Based Games

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

The Effect of Strategic Noise in Linear Regression

Similar lecture

Improved Algorithms for Learning Equilibria in Simulation-Based Games

Downloads