Adaptive Learning for Interactive Agents and Systems – ALIAS

A critical challenge in the current digital era is the need for real-time decision-making in complex systems, often based on data that arrive at very high volumes: traffic routing in packet-switched networks, online matching markets (taxi-hailing apps, micro-labor markets, etc.), generative adversarial networks in machine learning, and malware/fraud detection systems are just some of the hallmark examples where real-time decision-making plays a major role.
Techniques based on adaptive learning have met with prolific success in addressing these challenges by exploiting a simple feedback loop: first, the agent interfaces with their environment (a computer network, other agents, etc.) by selecting an action (e.g. a synaptic weight configuration in a neural network or a client/provider matching in an online assignment market); subsequently, the agent receives some feedback based on the quality of the action and the state of the environment, and the process repeats. While this simple online process has had big successes in many applications, several fundamental challenges remain:
A. Does adaptive learning lead to stable outcomes in multi-agent systems?
B. What types of behavior can be expected otherwise, and how far are they from optimality?
We intend to approach these questions with a blend of techniques from game theory, machine learning, online optimization and dynamical systems, our ultimate aim being to circumvent – or, at worst, predict – the failures and successes of online learning in multi-agent systems.
In more detail, we intend to structure our work along two synergistic theory thrusts that target a distinction which is commonly neglected in the literature:
1. Prescriptive multi-agent learning: Here the features of the underlying game are known in advance and the aim is to calculate an optimal action profile. The computation process does not need to be rationally justifiable or otherwise provide good interim payoffs – the only desideratum is to return an optimum (or near-optimum) con?guration. Accordingly, the main goal is the design of convergent learning algorithms for complex multi-agent interactions.
2. Predictive multi-agent learning: at the other end of the spectrum, if the game is not known in advance (or it evolves over time), the agents' most sensible choice is to implement a simple online algorithm with reasonable worst-case guarantees – such as the minimization of the agents' regret. In this case, the overriding goal is to predict the outcome of an adaptive multi-agent learning process and to contrast it to the solution of the underlying game.
These overarching goals dovetail to provide a uni?ed answer to the question of stability in multi-agent systems: for systems that can be controlled (such as programmable machine learning models), prescriptive learning algorithms can steer the system towards an optimum con?guration; for systems that cannot (e.g., online assignment markets), a predictive learning analysis can determine whether stability can arise in the long run. Elevating these observations, the objectives of ALIAS are to:
I. Identify the fundamental limits of learning in multi-agent systems: in particular, to determine which classes of games are "learnable" and which aren't.
II. Design novel, robust algorithms that achieve convergence in cases where conventional online learning methods fail.
III. Implement our theoretical advances in real-world problems, ranging from generative adversarial networks to online assignment markets.
Tackling these ambitious objectives requires interdisciplinary expertise from game theory, machine learning, online optimization, information theory, and statistics. This amalgam of skills and expertise is the defining characteristic of the Franco-Singaporean team, which is thus in a unique position to successfully address the challenges identi?ed above - and, in so doing, to provide a significant boost to the design and operation of a wide array of multi-agent digital systems.