Algorithmic Cooperation, Competition, and Collusion
Abstract
agent learning in information-limited autonomous systems. As autonomation is introduced in practical settings, increasingly algorithmstypically designed for stationary stochastic or adversarial, worst-case settingsare interacting with one anotherthereby violating the assumptions under which the algorithms were designed or certified. Systems with multiple autonomous agents learning as they explore the environment and seek best strategiesare inherently non-stationary due the presence of multiple decision makers, and uncertainties abound. Techniques to understand how diverse learning algorithms interact with one another, characterize the emergent strategic behaviors such as cooperation versus competition, and optimize theperformance of such algorithms are crucial for the operationalization and deployment of autonomy.Research Plan: The core innovations of this project will be a suite of analysis and synthesis tools that draw on the aforementioned domains in order to provide assurances for learning in cooperative and competitive settings. The proposed research will consist of three thrusts which align with threegaps in the current state of the art: (T1) analysis and synthesis of heterogeneous learning algorithms, (T2) effects of information availability on performance, and (T3) characterization and classification of emergent strategic behaviors including collusion, coercion, and deception.Technical Approach: The research focuses on the extension and development of novel analysis and synthesis tools for autonomous systems, which build on the PIs prior work, to guarantee the performance of heterogeneous learning algorithms. The research agenda will consider heterogeneity inboth the learning algorithm structure and the information available to agents (e.g., full, partial, asynchronous or lossy) and the effects of heterogeneity on strategic behavior. The theoretical results will be assessed on benchmark problems including both simultaneous and hierarchical decision problemsspanning classes of continuous and finite action space games, multi-agent reinforcement learning, and adversarial learning. The proposed research will advance the science of autonomy by drawing connections between and extending tools from areas core to autonomy: dynamical systems theory will provide a unified framework in which to analyze the coupled learning algorithmsfrom different classes, game theory and economic analysis will be used to assess and characterize strategic behaviors, and machine learning and optimization will be used to analyze and synthesize implementable algorithms with finite-time performance guarantees in uncertain environments.Expected Outcome: The expected outcome is a suite of tools for analysis and synthesis of heterogeneous learning algorithms in information-limited settings and the identification and design of emergent strategic behaviors. It is also expected that several benchmark problems will be arise through the research, helping to standardize the processes of certifying learning algorithms in cooperative and non-cooperative multi-agent settings.Impact on DoD Capabilities: This project will deliver a coherent and transformative body of theoretical and algorithmic tools for studying heterogeneous learning in information-limited multiagent settings that exhibit complex dynamics, and uncertainties. If successful, this research effortwill provide significanure performance guarantees on the collective behavior, identify strategic behaviors consequent of algorithmic interaction, and avoid unintended consequences which could be catastrophi operationalizing autonomous systems in military applications.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jun 17, 2020
- Source ID
- N000142012571
Entities
People
- Lillian J. Ratliff
Organizations
- Office of Naval Research
- United States Navy
- University of Washington