[MENGDI WANG] --and to games at Facebook. So let's have Yuandou. Welcome.
Yuandong, you're muted.
[YUANDONG TIAN] Try that. Hey, hello everyone. Can you hear me now?
Can you hear me now? Hello? [MENGDI WANG] Yes I can hear you. [YUANDONG TIAN] Okay. Nice, nice. Sorry about that. Let me try again.
Okay, I think now it should work. Can you see this? Wait. Can you see the screen? Yes, we can see it. Okay, cool. Nice. So my name is Yuandong Tian.
So I'm a research scientist, also manager in Facebook AI Research. Today I'm going to talk about our recent several works on learning multi-agent
collaborations with decomposition. So first, I want to introduce a little bit of myself. So I'm going
to-- I'm heading, like, two different directions. One is reinforcement learning, and the other is theoretical understanding of deep models. Uh, in
this case, so in this pa-- in this talk, I'm going to talk a little bit on reinforcement learning side, because it's a reinforcement seminar. And on
the theoretical understanding of deep learning paper we also actually do some understanding of student
teacher models, and also recently, we actually apply our approach to self-supervised learning, and understand why it works in breaking the black box.
But this time I'm going to omit that, and focus on the first part. So I'm going to talk about three different papers in this 30 minutes talk, which is
an ambitious goal. Uh, so I'm going to be a little bit faster in term of, like, the pace, and also
leave a lot of details in the paper, and also in the detailed slides. So the first paper I'm gonna talk about is the Multiagent Ad Hoc Team Play with
through Reward Attribution Q-functions. So this paper has already been open-sourced, and all the code is online, and people can play with that. Uh,
this is a joint collaboration with UC Berkeley and also UCSD and also Tsinghua University. So
multi-agent reinforcement has been, making a strong, a very great progress in recent years. I mean, we have seen a lots of results from OpenAI and
DeepMind. They actually solve these problems with very heavy computational resources by computing by basically training multiple agent at the same
time, and ask this agent to compete with against each other so that the performance become better and
better. And from a theoretical point of view, for multiagent collaboration, we want to talk about there are two different things we want to think
about. One is how to efficiently train collaborative agents at the same time. Right? So the second question is I mean, we don't want this
collaborative agent to be very dedicated and also very overfitted to the same this task, right? We want them to be
adapt to a new team configurations in test time without fine tuning. So in order to do, to achieve these two goals, we propose this collaborative
Q-learning. So, this is basically like based on the first principle, and we want to basically find the, using the first principle to understand how a
agent can collaborate, and what kind of collaboration, and also what kind of computation model we can
derive from the first principle. Right? So, and so we started with thinking about the value function decoupling in collaborative setting. So if you
think about the joint value function V joint from S1 all the way to SK, where this S is basically the state of all this agent I. So if you want to
just directly formulate this joint value function, you have these three different negative points, so
that things are very hard to deal with. First of all, there's exponential consumer complexity to estimate this function. You need exponential samples
to fill in this table, which is not possible. The second one is that there's no decentralized execution, which is something we really want. What do we
mean by decentralized execution is that each agent should be able to execute by its own, from its
own local observations. Right? So but since this V joints is a function of all the agent states, it's hard to deal with. And the third one is it's not
able to generalize with new agent and teammates. So what can we do for that? Right? So in this paper, we basically talk a little bit about seeing,
like, how can we model agent collaborations using reward attribution? So we think about what is the
motivation for the agent to collaborate. Right? So we basically try to decompose this motivation into the term called assigned rewards. So we think
about each agent has a decentralized value function, VI, and that VI is actually conditioned on assigned rewards, I. And this assigned rewards is
given by some centralized mechanism. And once assigned rewards is there, and each agent is only acting
based on the its own state, as well as the assigned rewards. And given that assigned rewards, each agent is decoupled from each other. So that's
actually the idea and the motivation of this work. So, and then people might think, "Okay, since this is true, but how can we do this assigned
rewards?" Right? So this assigned rewards is actually can be computed from this following optimization
functions. So considering that we are actually maximizing uh, some kind of function that is the joint reward, and the-- the joint reward is basically
like the-- the-- The summation of all this uh, local V-functions, and you take the maximum of all these assigned rewards, so that you probably assign
all these rewards so that the-- the-- The value functions is maximized. Okay. So we obviously need
an objective, need a constraint so that this assigned rewards won't exceed the external rewards you can get, right? Which is the condition that I put
in the second part of this equation. Obviously this is still a hard problem because uh, first of all, you need to solve this problem at every
timestamp in the joint execution, which is a very hard problem. And second, it's still not decentralized
because when you are solving the problem, you need all the state putting together so that the problem can be solved. But interestingly we actually
find there's a theorem that you can show in certain conditions, you actually can find a reward assignment. And this reward assignment called the R hat
I for each of this agent, so that it's identified two properties. The first property is it only
depends on the local observation of the agent I. So basically, the local, for a given agent I's point of view, it can see like a bunch of other agent
state, and we denote that as SI local, and we can show that there exists a local assignment, a real assignment, that it only depend on this local
joint state, but not the entire state. And third-- and second, that reward assignment is actually, if
you put all them together, it's actually a reasonable good solution. The solution that you put 'em together which is the R hat, is actually has a
lower bound in term of its performance compared to optimal assignment. So based on that, so what we can think about is instead of like solving this
problem solving this like formulation in one shot, and that requires all the state of all the agents, what
we can do is we can actually ask each agent to take a look at its local state and then its own state and also its state around it, and then you put
all them together and try to learn a function directly from this local state combinations all the way to its local to this reward assignment. And that
reward assignment will be used to guide agents agent's moves. Right. So once we have that, then we
can actually think about, okay, so because this reward has this kind of structure, maybe you can do a tail expansion for these Q functions, right? So
because the Q function is also a function of this local reward assignment, so it can actually be, using this compositional rule of tail expansion, we
actually can decompose this Q function into two different terms. The first term is called a Q-alone,
which basically only model the Q function component that is only dependent on the local state of that particulars of particulars uh, agent I. So you
only need to input that particulars agent I state there without knowing all the rest of the state, including the state that is around you. And the
second term is also the, actually called the co-collaboration. And that collaboration term, and it's
actually only depends on the local observation of the agent state. So by local observation, what I mean is it's not only including the local state of
the agents I, but also include its surrounding state of the other agents that the agent I can actually perceive, right? So you can just put 'em
together. And also from this tail expansion, you can naturally see that the second term need to be zero if
yeah, if the agent I is in a long state in which like the agent I does not really see other people's state. So then it actually becomes a kind of
regularization. And this actually give you like a natural algorithm, right? The natural algorithm basically say that we can just decompose the Q
function into these two components and that we actually put the regularization in the second components and
so that you can train these two things in the same time. So that's actually a very simple approach you can get from the zero derivation. So we
actually apply that idea and try this to StarCraft II multi-agent challenge, which is a empirical benchmark that in which our reinforcement agent need
to control a multiple agent, multiple small units in this game. So they have to compete against the other
group of agents that is controlled by the computer by him the human design rules. And we actually find that our approach called CollabQ and also
CollabQ But with attention actually does much better in term of performance, the level of win rates given the number of same amount of environment
steps used to train a model. So basically of all these figures, we basically show that our project is shown
by purple and also brown. I mean, they are actually doing a very good job in all these different environments. And all these tasks are actually pretty
hard tasks, and these tasks are actually regarded as a very hard task, and if you try simple approaches, this won't work that well. And no matter for
that, and we actually see that the CollabQ actually perform very well in different uh, in ad hoc
team play. So if we actually add or swap or remove units in a test time, and we actually just use this trend model on this test time environment, we
actually see our approach is actually doing a reasonably good job compared to other approaches. So that's actually why very interesting as well,
because of this decomposition, it somehow learns the structure decomposition and actually can be adapt to
other situations quite well. And finally, we also tried basically using checking like a different component of this CollabQ and see whether all these
components are necessary, right? So we basically say, okay, how about we get rid of this loss function in which this Q decomposition this Q collab is
not necessary to be zero when the agent is alone. So if we could get rid of that, we actually see
that the curve is actually doing much worse. So it's actually become comparable with existing approaches. But with this loss function, our approach is
doing much better, showing that this decomposition makes sense and regularisation is also doing a very good job. So This is the first paper, and
forgive me for this fast pace, but we have several papers to cover. And let me know if you have more
questions and more comments after this series of talks. The second paper that I'm going to mention is uh, another paper. They are trying to improve
the collaboration of multi-agents, using a joint policy search. So this is basically like a focus more on these game settings imperfect information
games, in which each of these players, they don't need to-- they don't necessarily like learn or see
each other's like states. So here's like one illustrative example. So suppose we have two players, one is Alice and the other is Bob. And Alice has
two private cards, either or has one private card, and, but that private card can be either spade A or heart A. Right? So then Alice can send a
private, public signal to Bob, so that Bob can guess what the, the card is. So because the private signal
has three different choices, so we actually see six symmetry solutions. Right? So here's like a table that lists like just one possible solutions, but
there could be lots of other solutions. In that particular solution, what you see is that Alice action number two, is actually not used because
there's two card with three signals. Right? So but if we change the game rule by a little bit, saying how
about if you send signal two, the second, we actually get an additional small reward, right? So in addition to whether Bob has guessed correctly from
Alice's hint. So if the game rule has changed a little bit, then what happens is that if you start with the existing solution, it's going to be super
hard for you to change the policy from Alice point of view or from Bob point of view. Because uh,
from Bo-- from either person's point of view, it's actually very risky to change their own policy, right? So this change their own policy
unilaterally, if that ch-- they change their own policy unilaterally, then it really risk that the communication is not working at all and you won't
get any reward. So this actually bring about this problem, right? So for pure multi-agent collaborative games, a
unilateral optimization of policy doesn't really improve overall values. So and if you check back like a lots of like empirical results, that
empirical algorithms that people have tried, and usually what people do is we fix, we basically treat the environment as a constant and try to
optimize the policy from one agent point of view. And this actually will get into trouble in this kind of settings.
Right? So another example is like that. So this is like a more example more example from the real world, is that if you have two players who are both
can speak English and one speak French, but they may get trapped into local minima by just talking about French, about, none of them want to switch to
another eng-- language. So this actually corresponds to this game tree in this incomplete
information game set imperfect information game setting. So in this game settings, each of these player state basically don't know each other's hidden
state. They and they basically want to figure out one joint policy so that this joint policy is not local minima. But unfortunately, we're going to
see a local minima here first. So for example here, if you just both of them choose French-French,
then the-- there's a local Nash equilibrium, which is 0.1.5 because one of the player does not really speak French well. But on the other side,
there's actually another global optimal solutions, which is English-English. Right? So in that case, how can we deal with that? So one natural idea to
deal with that is, can we actually change the policy of two agents at the same time? Right? So that's how
we'll be like one solution for that. For example, if you can change these two policies of this two players at the same time, then they can actually
get to the same solution, that optimal solution, obviously. But in order to do that you want to basically like write down the formulation about the
policy changes. Right? So what do you want to do is if you change the policy of these two information
set at the same time, what do we do value changes? So but this actually is a hard problem, especially for incomplete imperfect information game. This
is because imperfect information game the game tree is not a tree anymore. It actually can be a digraph. So that's the reason of that is because I
mean, the information that you see from one player may not be available for the other player's point of
view. Because of that, you're going to see this game trees basically span here and then go back to the other states. So this actually makes things
very complicated. So but fortunately, we actually discover there's actually some properties in this formulation, and we actually find interesting
density which is called the policy change density. This is a quantity which has two properties. The first
property is that if you sum all this policy change density together, you actually will get the overall value changes. Right? So here, like a sigma is
the current policy and sigma prime is the new policy, and V sigma bar is basically the value of this current policy, and V sigma bar prime is the
value of the improved policy. So if you compute the difference between the two, this is something that
you want. You want to find the sigma bar so that this V sigma bar this V sigma prime is better than V sigma. Right? So you have two probabilities.
First is if you sum of them together, you get this difference in term of the values, and the second is if you sum this if you check this rule in a
region where the policy didn't change, then this rule is actually automatically become zero. No matter
whether or not it's upstream or downstream states has been, has a changed policy or not. Right? So this is actually quite interesting. Because of
these two properties, we actually can arrive at this main theorem. The main theorem basically tell you the overall value changes due to policy changes
can be decomposed into some of this policy change rules. So and you only need to add all the rules in
this active information set in which the policy will change. And this inactive information set actually doesn't matter. So this actually create a much
interesting and also more effective way of computing this overall value changes. So based on that we actually can develop our own approach called the
joint policy search. So the policy search is actually very simple. You start from a starting policy
which is starting from information set I1, and then you change the-- It's on, it's o-- it's policy. And then once you change the policy, you dig down
into the consequence of its changed policy, so by doing a depth-first search. So when the depth-first search has reached a given depths, you use the
previous theorems to compute the policy changes, because the policy changes can be computed
efficiently whose complexity is proportional to the number of active information sets in which the policy has changed, and regardless of how many
policies, how many other information sets that has somehow been changed, and I mean, this search can be done in a very efficient manner. So, once you
have done that, then you actually can apply this to any existing policy improvements approaches, and
compare that with other existing approaches. And we see that in multiple small games that is defined in the paper in definition one, two and three in
for the, uh-- We actually see, like, our approach is doing much better in term of the joint rewards. Right? So we actually see that this approach can
actually improve the existing process by jumping out of the local minima that is trapped by running
these approaches. And we actually see-- And we also apply this to bridge which is, like, a very old game of 100 years, and it's an imperfect
information with four players, and each players, the two of these players are forming a team, the other two are forming another team. They're
competing with each other. So there's both a collaborative and a competitive component on that. And our goal is
trying to improve the collaborative component between you and a teammate, right? It has a very large state space, so that you cannot name all the
possible states. So if you run, like, a H2C self-play on top of that, this bridge bidding, you actually see, like, things actually converge to local
minima quite easily, and after that it hard to get trend better. But if we try our approach we actually
see that our approach achieve a much better performance, and you can actually evaluate this resulting model against WR5, which is a champion of
computer bridged tournament in multiple years. And we see that without training with WR5, with just train by ourself and also without using any human
knowledge we actually is able to beat WR5's bidding phrase in a double dummy evaluation by a large amount.
Okay? So that's the second paper. And finally, I'm going to talk a little bit about a-- another paper that is actually nothing to do with multi-agent,
but it's actually a very cool paper, and I'm going to spend some time on discussing that in this seminar basically, because it's actually ex-- uh,
touch and a very important problem in reinforcement exploration. So the basically the idea here is
kind of very simple. It has very simple idea, but the performance is super good, so we're going to see why-- We're having to figure out why that's the
case, but we want to first introduce the paper, and hopefully we can trigger more kind of thoughts about interesting theoretical explanation of it. So
here we switch gear a little bit and talk about environment exploration, but with sparse reward,
right? So here's, like, one very simple environment, and when we have an agent which has partial observability, and the agent's goal is to reach to
the goal that is shown in this purple circles, right? So the agent, in order to achieve the goal, the agent first need to explore the space, and needs
to pick the key in the corner, and then use that key to open this locked door, and enter then into
this door to reach the goal. Right? But the problem with that is that the agent does not really see the goal, and also the agent does not really get
the reward at any intermediate step, right? So there's no reward if you went around, there's no reward in pick key, there's no reward when you open a
door, there's only reward when you reach the goal. So this actually makes things super complicated
and very hard. So in order to achieve some kind of exploration properties, one thing people usually do is to basically add an intrinsic reward in
addition to the external reward for the agent, right? So the agent will be tempted to visit states that has a very infrequent visitation counts,
right? So that's something that people usually do. But then, like, people might ask, "Okay, how about in a
state, in a situation that we don't really have a temporary representation?" In some situations that you have exponential number of state to explore,
what should we do, right? So one thing that we could do is we basically can use what we just called it RND, which is called the random network
distillation, in which we actually train two networks. So one is the random fixed teacher network that you
don't touch, you don't train, but there's another network, which is called student network, that can be learned from a teacher. So the first time you
visit, like, one state, and you basically train your student network so that student network actually learn to achieve a lower prediction error. So
with a lower and lower prediction error, this basically means that the state has a higher visitation
counts. So we can approximate this N this way. There's issues in this INDS, right? So the IND actually has issues. If you actually run this following
a maze, then what happens is we'll first explore a few interesting regions, but after a while you actually move back and forth into two already
explored regions, because the policy is already being trained to only go to these two paths heavily.
Right? So here's like one interesting theoretical very simple experiments, right, running this multi-corridor problems. So you have a state, S0, and
then you start from this state, and there's four different corridors you can go, right? Each corridor have different lengths. And what do you actually
see if you run like an IND or counter-based kind of exploration, is that they will get stuck into
one of two corridors, and they'll never visit the other corridors because of this kind of problems. And you actually compute entropy of visiting
different corridors, and you see like these, both of these entropies are quite low compared to our approach, which is the B-BOLT approach that we will
be represent we will going to talk about in next slides. So in the next slides we're going to have, this
is basically the idea of B-BOLT, very simple. So we actually have intrinsic rewards, but we instead of using this inverse of visitation counts as this
intrinsic rewards, we actually use the difference of the visitation counts along the trajectory. So we also do a regularization by cutting off the
negative intrinsic rewards along the way by using a ReLU functions. It will also multiply all these
things by an episodic visitation counts, which is computed in, as a hash function in each of this environment. This is basically used to prevent an
agent to visit like a state multiple times to get like multiple intrinsic rewards. So we basically, the idea here is actually the source is the sum,
Yeah, the intuition is actually here, right? So you start from a small room, and if once you do the
exploration, you actually will find there will be some of the bottleneck whose visitation count is super, super low. But once you put high rewards of
these bottlenecks, so what happens is the visitation counts of all these bottlenecks will become higher, and this actually will reduce the intrinsic
rewards and enable the agent to go beyond that bottleneck and move to the next uh, move to the next
room. That's the idea. But there's no theory on top of that, and we are still exploring why that's the case why this can actually give good
performance. So here, I'm I'm talking a little bit on this performance here. So we actually evaluate this approach in, very similar approach in like a
MiniGrid environment, which is a procedure generated environment that is used to evaluate exploration in for
different algorithms. So we see that our approach actually solve like 12 most challenging tasks in this environments, while the prior arts has been
trying and hard and only solve half of them. And also, if you check this curves in term of the visitation count with, in term of this environmental
steps versus the average return, and we see that in the hard tasks, our approach, which is shown in the
purple, in the light purple, actually has a much better performance compared to the other approaches. We don't really see promising results on the
other approaches, but our approach were able to address these hard problems. And we check this pure exploration results, and we see that people
actually did much better in term of the environmental steps and in, in comparison, IND only basically do, get
stuck into the fifth room after double number of environment steps. And we also try this same idea in the NetHack, which is a new environment where
one of our colleagues have proposed. This is a very famous game in 1980s, and people have tried their best to play this game. And we actually did a
very good job in six tasks in NetHack. So future work based in this approach is first this is a very
simple approach and see performance, so people in that question will ask, it's like, "What is a little understanding of it? Why this very simple
approaches actually achieve good performance?" Right? So this actually after some kind of thinking one idea that we are thinking about is maybe it is
related to exploration in Factor MDP, right? So because the environment in a real world is kind of
factored, there's a lot of components there. So in that case, like what will be the key assumption we need to make in the Factor MDP so that this kind
of exploration would work, but this is still ongoing work. And this is basically the presentation, and thanks for your attention, and I welcome any
questions.
[MENGDI WANG] Okay. Thank you, Yuandong. So that's a very impressive set of results. So there are many questions for Yuandong and for Shai. And again,
so we're going to defer them after the last talk. All right, so please stay until end of the break. [YUANDONG TIAN] Okay. Thanks. [MENGDI WANG] Okay.
Thank you. Okay. So--