Coordination in generative modeling, automatic differentiation and multi-agent learning

Abstract

Cette thèse présente quatre articles dans trois domaines différents : la modélisation générative de la musique, l’attribution de crédits pour les réseaux de neurones récurrents (RNN) et l’apprentissage par renforcement multi-agents (MARL) dans des dilemmes sociaux. Un thème commun est la coordination, c’est-à-dire la prise en compte des dépendances entre des éléments modélisés comme indépendants.

Le premier article concerne la coordination des états informationnels. Nous développons une approche de raffinement itératif de la composition musicale. Notre modèle produit des prédictions conditionnellement indépendantes pour les variables dépendantes, qui sont réconciliées par un processus de raffinement itératif. Notre processus est plus proche de celui des compositeurs humains que des approches existantes qui produisent de la musique du début à la fin, et plus résistant aux entrées corrompues.

Dans le deuxième article, nous considérons la coordination des communications entre des nœuds des graphes. L’algorithme d’entraînement UORO pour les réseaux neuronaux récurrents en mode direct simplifie le graphe de calcul des dérivées en introduisant des fausses connexions, ce qui transforme les communications ciblées en simples diffusions. Les véritables connexions sont rétablies en espérance, grâce à l’utilisation de secrets partagés sous forme de bruit corrélé. Nous étudions la variance de cette approximation. Sur la base de nos connaissances, nous introduisons une variation pratique qui réduit considérablement la variance au prix d’une augmentation des ressources de calcul. Nous établissons également un lien théorique entre REINFORCE et UORO, avec égalité jusqu’à un terme dont l’espérance est zéro mais qui contribue à une variance arbitraire.

Dans les troisième et quatrième articles, nous coordonnons des processus. D’abord, nous proposons un algorithme pour trouver des politiques fortes dans des dilemmes sociaux en supposant un adversaire rationnel. Notre agent vise à trouver des politiques pour lesquelles la meilleure réponse est favorable, coordonnant ainsi de manière unilatérale les deux agents. Cette méthode est plus évolutive que les travaux antérieurs basés sur la même idée, et elle est performante sur un benchmark exigeant impliquant des politiques de réseaux neuronaux.

Ensuite, nous proposons de traiter l’apprentissage multi-agents comme un jeu et d’y appliquer value learning. Il en résulte une fonction de méta-valeur ; un jeu modifié dans lequel l’apprentissage naïf est coordonné. Nous démontrons une manière efficace d’apprendre la méta-valeur en Q-learn, sans représenter explicitement l’espace d’actions continues et sans utiliser d’estimateurs REINFORCE. La méthode trouve des politiques fortes dans des dilemmes sociaux et se compare favorablement à une méthode similaire basée sur une méthode policy-gradient dans la littérature.

This dissertation presents four articles in three different domains: generative modeling of music, credit assignment for recurrent neural networks (RNNs), and multi-agent reinforcement learning (MARL) on social dilemmas. A common theme is coordination, by which we mean accounting for dependencies between things that were modeled as independent.

The first article concerns coordination of information states of disjoint variables. We develop a model that produces conditionally independent predictions for dependent variables, which are reconciled through an iterative refinement process. Our process is closer to that of human composers than existing approaches which produce music from beginning to end, and more robust to corrupted inputs.

In the second article, we consider coordination of communications between graph nodes. The forward-mode RNN training algorithm UORO simplifies the derivative computation graph by introducing spurious connections, turning targeted communications into simple broadcasts. The true connections are restored in expectation through the use of shared secrets in the form of correlated noise. We study the variance of this approximation. Based on our insights we introduce a practical variation that drastically reduces variance at increased computational expense. We also establish a theoretical connection between REINFORCE and UORO, with equality up to a term that is zero in expectation but contributes arbitrary variance.

In the third and fourth articles, we coordinate processes. First, we propose an algorithm for finding strong policies in social dilemmas by assuming a rational opponent. Our agent aims to find policies for which the best response is favorable, thus unilaterally coordinating both agents. This method scales better than prior work based on the same idea, and is competitive on a tough benchmark involving neural network policies.

We then proceed to treat multi-agent learning as a game and apply value learning to it. This results in a meta-value function that measures how the return improves as learning progresses, which can be seen as a modified game in which naive learning is coordinated. We demonstrate an efficient way to Q-learn the meta-value, without explicitly representing the continuous action space of policy updates, and without the use of REINFORCE estimators. The method finds strong policies in social dilemmas and compares favorably to a related policy gradient-based method from the literature.