Distributed optimization, control and learning in multiagent networks

Se ha estimado que en el mundo habrá decenas de miles de millones de dispositivos interconectados en las próximas décadas, cada uno obteniendo datos del entorno, procesándolos y transmitiéndolos en tiempo real. Para manejar esta ingente cantidad de datos, las arquitecturas tradicionales, en las que existe un centro de fusión recopilando las muestras de todos los dispositivos, podría no satisfacer requisitos de rendimiento y coste de operación de estas redes (por ejemplo, privacidad de los datos, robustez frente a fallos o el coste de transmitir los datos desde cada dispositivo). La computación distribuida es una alternativa interesante que consiste en no utilizar un nodo central de fusión de datos y en que la computación la hagan exclusivamente los nodos de la red. Esta tesis propone y evalúa algoritmos para dos escenarios multiagente complementarios. Primero, consideramos algoritmos distribuidos cooperativos, en los que los agentes interaccionan para solucionar un problema común. Incluso si cada agente tiene acceso a un pequeño conjunto de datos, al cooperar con sus vecinos puede obtener rendimiento similar al que tendría una arquitectura centralizada. En este contexto, proponemos métodos de análisis de componentes distribuidos—incluyendo “principal component analysis”, “factor analysis” y “linear discriminant analysis”—basados en un esquema del tipo “consensus-averaging”. También proponemos y analizamos un algoritmo de “off-policy reinforcement learning”, que permite que los agentes exploren el espacio de estados de forma independiente y compartan sus estimadores intermedios (nunca las muestras obtenidas durante la exploración) con sus vecinos para evaluar una política objetivo común. Finalmente, introducimos un algoritmo distribuido tipo “cross-entropy” para optimización global (no convexa) de funciones objetivo desconocidas (“black-box”). El segundo escenario consiste en juegos potenciales dinámicos. Se trata de una clase de juegos en los que el estado del entorno varía con el tiempo, en función de las acciones de los agentes, y en los que los agentes compiten por un recurso común. Este tipo de juegos puede formalizarse como problemas de control óptimo multiobjetivo, los cuáles son difíciles de abordar. Nuestro análisis generaliza resultados anteriores, garantizando la existencia de un punto de equilibrio del sistema, bajo condiciones muy generales, y proporcionando un método para encontrarlo—o incluso aprenderlo mediante técnicas de “reinforcement learning”. También estudiamos la aplicación de este tipo de juegos con varios ejemplos de ingeniería de comunicaciones. ABSTRACT It is estimated that, in the next decade, there will be tens of billions of interconnected devices in the world, each one sensing, streaming and processing data. In order to manage such huge amount of data, traditional architectures—where a fusion center gather all the data—may not satisfy performance specifications or cost constraints (e.g., data privacy, resilience, scalability or communication cost). Distributed computing is an interesting alternative that consists in moving the data processing to the devices— which become intelligent agents—so that the fusion-center is completely avoided. This thesis proposes and evaluates algorithms for two complementary multiagent scenarios. First, we consider cooperative distributed algorithms, where the nodes interact with each other to solve a social problem. Even if each agent has only access to very few data, it can approximate the performance of a centralized architecture through cooperation. In this context, we propose distributed component analysis methods— including principal component analysis, factor analysis and linear discriminant analysis— based on the consensus-averaging scheme. We also propose and analyze an off-policy reinforcement learning algorithm, where the agents explore the state-set independently and share some intermediate results (not the samples) with their neighbors in order to evaluate a common target policy. Finally, we introduce a distributed implementation of the cross-entropy method for black-box global (nonconvex) optimization, where the objective is unknown to the agents. The second scenario consists in dynamic potential games. This is a class of statebased time-varying games, where the agents influence each other and compete for a shared resource, so that they have to find an equilibrium. These kind of games can be formalized as multiobjective optimal control problems, which are generally difficult to solve. We extend previous analysis for these kind of games and guarantee existence of equilibrium under mild conditions. In addition, we propose a framework for finding—or even learning with reinforcement learning methods—an equilibrium strategy. We also study the applicability of this kind of games with a number of examples