Talks

Reinforcement learning (RL) has made substantial empirical progress in solving hard AI challenges in the past few years. A large fraction of these progresses—Go, Dota 2, Starcraft 2, economic simulation, social behavior learning, and so on—come from multi-agent RL, that is, sequential decision making involving more than one agent. While the theoretical study of single-agent RL has a long history and a vastly growing recent interest, multi-agent RL theory is arguably a newer and less developed field, with its own unique challenges and opportunities. In this tutorial, we present an overview of recent theoretical developments in multi-agent RL. We will focus on the model of Markov games, and cover basic formulations, objectives, as well as learning algorithms with their theoretical guarantees. We will discuss the inefficiency of classical algorithms---self-play, fictitious play, etc., and then proceed with recent advances in provably efficient learning algorithms under various regimes including two-player zero-sum games, multiplayer general-sum games, exploration, and large state space (function approximation).

Reinforcement learning (RL) has made substantial empirical progress in solving hard AI challenges in the past few years. A large fraction of these progresses—Go, Dota 2, Starcraft 2, economic simulation, social behavior learning, and so on—come from multi-agent RL, that is, sequential decision making involving more than one agent. While the theoretical study of single-agent RL has a long history and a vastly growing recent interest, multi-agent RL theory is arguably a newer and less developed field, with its own unique challenges and opportunities. In this tutorial, we present an overview of recent theoretical developments in multi-agent RL. We will focus on the model of Markov games, and cover basic formulations, objectives, as well as learning algorithms with their theoretical guarantees. We will discuss the inefficiency of classical algorithms---self-play, fictitious play, etc., and then proceed with recent advances in provably efficient learning algorithms under various regimes including two-player zero-sum games, multiplayer general-sum games, exploration, and large state space (function approximation).

This tutorial will give an overview of the theoretical foundations of reinforcement learning, a promising paradigm for developing AI systems capable of making data-driven decisions in unknown environments. The first part of the tutorial will cover introductory concepts such as problem formulations, planning in Markov decision processes (MDPs), exploration, and generalization; no prior background will be assumed. Building on these concepts, the main aim of the tutorial will be to give a bird's-eye view of the statistical landscape of reinforcement learning (e.g., what modeling assumptions lead to sample-efficient algorithms), with a focus on algorithmic principles and fundamental limits. Topics covered will range from basic challenges and solutions (exploration in tabular RL, policy gradient methods, contextual bandits) to the current frontier of understanding. A running theme will be connections and parallels between supervised learning and reinforcement learning. Time permitting, we will touch on additional topics such as reinforcement learning with offline data.

The formalism of quantum theory over discrete systems is extended in two significant ways. First, tensors and traceouts are generalized, so that systems can be partitioned according to almost arbitrary logical predicates. Second, quantum evolutions are generalized to act over network configurations, in such a way that nodes be allowed to merge, split and reconnect coherently in a superposition. The hereby presented mathematical framework is anchored on solid grounds through numerous lemmas. Indeed, one might have feared that the familiar interrelations between the notions of unitarity, complete positivity, trace-preservation, non-signalling causality, locality and localizability that are standard in quantum theory be jeopardized as the partitioning of systems becomes both logical and dynamical. Such interrelations in fact carry through, albeit two new notions become instrumental: consistency and comprehension.

Joint work with Amélia Durbec and Matt Wilson

Reference: https://arxiv.org/abs/2110.10587

Zoom Link: https://pitp.zoom.us/j/97185954578?pwd=OC9mUzl4L3V4WDZzVEZoekpOS24wQT09

This tutorial will give an overview of the theoretical foundations of reinforcement learning, a promising paradigm for developing AI systems capable of making data-driven decisions in unknown environments. The first part of the tutorial will cover introductory concepts such as problem formulations, planning in Markov decision processes (MDPs), exploration, and generalization; no prior background will be assumed. Building on these concepts, the main aim of the tutorial will be to give a bird's-eye view of the statistical landscape of reinforcement learning (e.g., what modeling assumptions lead to sample-efficient algorithms), with a focus on algorithmic principles and fundamental limits. Topics covered will range from basic challenges and solutions (exploration in tabular RL, policy gradient methods, contextual bandits) to the current frontier of understanding. A running theme will be connections and parallels between supervised learning and reinforcement learning. Time permitting, we will touch on additional topics such as reinforcement learning with offline data.

Classically, the outcome of a learning algorithm is considered in isolation from the effects that it may have on the process that generates the data or the party who is interested in learning. In today's world, increasingly more people and organizations interact with learning systems, making it necessary to consider these effects. This tutorial will cover the mathematical foundation for addressing learning and learnability in the presence of economic and social forces. We will cover recent advances in the theory of machine learning and algorithmic economics. In the first half of this tutorial, we will consider strategic and adversarial interactions between learning algorithms and those affected by algorithmic actions. What makes these interactions especially powerful is that they often occur over a long-term basis and can corrupt data patterns that are essential for machine learning. In this part of the talk, we work with online decision processes (such as no-regret learning) and solution concepts (such as stackelberg and minmax equilibria) to discuss statistical and computational aspects of  learning and learnability in the presence of such interactions. In the second half of the tutorial, we will consider collaborative interactions in machine learning. What makes these interactions especially beneficial is their ability to learn across multiple stakeholders' tasks. In this part of the talk, we see how online algorithms act as a medium for effective collaborations. We also discuss challenges involved in designing efficient data sharing mechanisms that fully account for learner's incentives.

Classically, the outcome of a learning algorithm is considered in isolation from the effects that it may have on the process that generates the data or the party who is interested in learning. In today's world, increasingly more people and organizations interact with learning systems, making it necessary to consider these effects. This tutorial will cover the mathematical foundation for addressing learning and learnability in the presence of economic and social forces. We will cover recent advances in the theory of machine learning and algorithmic economics. In the first half of this tutorial, we will consider strategic and adversarial interactions between learning algorithms and those affected by algorithmic actions. What makes these interactions especially powerful is that they often occur over a long-term basis and can corrupt data patterns that are essential for machine learning. In this part of the talk, we work with online decision processes (such as no-regret learning) and solution concepts (such as stackelberg and minmax equilibria) to discuss statistical and computational aspects of  learning and learnability in the presence of such interactions. In the second half of the tutorial, we will consider collaborative interactions in machine learning. What makes these interactions especially beneficial is their ability to learn across multiple stakeholders' tasks. In this part of the talk, we see how online algorithms act as a medium for effective collaborations. We also discuss challenges involved in designing efficient data sharing mechanisms that fully account for learner's incentives.

In this talk, I will revisit the calculation of infinite-dimensional symmetries that emerge in the vicinity of isolated horizons. In particular, I will focus my attention on extremal black holes, for which the isometry algebra that preserves a sensible set of asymptotic boundary conditions at the horizon strictly includes the BMS algebra. The conserved charges that correspond to this BMS sector, however, reduce to those of superrotation, generating only two copies of Witt algebra. For more general horizon isometries, in contrast, the charge algebra does include both Witt and supertranslations, being similar to BMS but s.str. differing from it. I will also show how this is extended to the case of black holes in the Einstein-Yang-Mills case, where a loop algebra associated to the gauge group is found to emerge at the horizon.

 

This short course will review recent advances in econometric theory for datasets that stem from the strategic interaction of participants in a game theoretic scenario. The course will cover basics of identification and estimation strategies for structural parameters of game theoretic models in settings like market entry games, dynamic games and auctions. In the first part, I will review basic econometric theory and in particular large sample asymptotic theory of generalized method of moment estimators and M-estimators, which forms the basis of many estimation and identification strategies proposed for game theoretic settings. I will then give an application of this theory to entry games of incomplete information. I will finish with an overview of how this approach extends to dynamic games of incomplete information. In the second part, I will analyze games of complete information and focus on the problem arising from the multiplicity of equilibria in these games, due to the unobserved heterogeneity of the participants. The latter leads to partial identification of the parameters of interest and set estimation. Finally, I will focus on econometrics of auction games and in particular estimation of the private value distribution in simple single item auctions. I will finish with a brief description of recent progress at the intersection of algorithmic game theory and econometrics.

This short course will review recent advances in econometric theory for datasets that stem from the strategic interaction of participants in a game theoretic scenario. The course will cover basics of identification and estimation strategies for structural parameters of game theoretic models in settings like market entry games, dynamic games and auctions. In the first part, I will review basic econometric theory and in particular large sample asymptotic theory of generalized method of moment estimators and M-estimators, which forms the basis of many estimation and identification strategies proposed for game theoretic settings. I will then give an application of this theory to entry games of incomplete information. I will finish with an overview of how this approach extends to dynamic games of incomplete information. In the second part, I will analyze games of complete information and focus on the problem arising from the multiplicity of equilibria in these games, due to the unobserved heterogeneity of the participants. The latter leads to partial identification of the parameters of interest and set estimation. Finally, I will focus on econometrics of auction games and in particular estimation of the private value distribution in simple single item auctions. I will finish with a brief description of recent progress at the intersection of algorithmic game theory and econometrics.