okay thanks Wenger for the introduction uh my name is viendo I'm a research scientist in meta AI fair today I'm going to talk about some Basics about
reinforcement learning and application to computer systems because this tutorial this talk has only 30 minutes so I basically like try to compress
everything into maybe like 60 slides to make sure that people have a like a rough idea about what
reinforcement is about and some of the like a pretty famous applications that you can leverage for something to uh to solve these problems so first of
all I want to cover Like a Warrior reinforcement and what it matters and the second and third we're going to talk a little bit about the two different
branches of reinforcement learning that's equal to value-based approaches this include the key
learning Alpha zero with a case study of Arc tensor and finally we're going to talk about the policy based approach this include the policy gradient
like the critic PPO and also an application that try to leverage acid critic to network planning problems which is a system problem so uh let's start
with these slides this is a kind of like a good slice that show uh reinforcement is useful for many
kind of situations especially in games right so we have seen like a successful uh stories in different kind of games like gold chess showing and on
maybe dollar Starcraft so there's a big success there uh and recently there's a resurgent of reinforcement being used in uh the charity Beauty and
gpd4 um this chatbot right so what they do is that the first Trend and supervise the agent uh with a lot
of data using language models and then you can basically train a reward model on this comparison data and finally you can basically tune the language
model with reinforcement learning right so uh this basically like shows as reinforcement will play a rule in building the state of art chat about
instead about like uh this kind of QA systems so today I'm going to talk I'm not going to cover this
part because it's kind of Beyond on the computer architecture and computer system domain we're going to talk a little bit about like a mono system
side how we can system people uh want to use it reinforcement and why system people want to care about that right so here's like two motivating
examples so people may uh already see this Alpha tensor also after that from the mind what they do is like
they are trying to leverage reinforcement to find uh what is the most efficient matrix multiplication uh given like two Matrix of side n by m and also
recently there's Alpha Dev as I try to find what is the shortest assembly code so that you can sort like two three numbers or to five numbers Etc
right so they are both using the same kind of technique called Alpha zero and we're going to introduce
later so uh in the higher level uh why system people care about IO this is because in the system side people usually think about like a multiple
access to be optimized right so people talk about like a memory usage uh latency and efficiency Etc there's a lot of like access they want to optimize
and if you want to think about optimization problem is high dimensional space usually what people will
do is that we start with some kind of initial solution and then you find try to find a way to improve that in a in a sequential manner as long as the
problem is modeled as a security system making process then you can use a little reinforcement link to actually improve our existing Solutions and to
find a better solution that's how reinforcement is being used for system for system side so uh in
this tutorial we're going to cover a bunch of possible optimization problems right so this includes like computer optimization this includes the
network planning problem I'm going to cover uh in a very a short amount of time and also we also want to cover like compiler optimization uh by Chris
right so on the other hand we can also use reinforcement to model multiplication so uh and uh in this
part when the Mulan will cover um how can we leverage IR uh to find the best attacker and also defenders in the cache timing attack form which is also
how reinforcement I have like system problems uh in uh in computer system architecture domain okay so now let's like really come to this page that
what is reinforcement we'll talk about reinforcement for five minutes now and uh people have no idea
what is your height right so for reinforcement uh I think it is like one figure let's try to show what it is right so uh we have an agent okay some
agent here and an agent will actually perceive the word uh and that the word perception is compressed into a state s right and then agent will see the
state as and it will take an action the action will change the environment as well as change the
agent's Behavior Uh income of the state and then at the same time the agent will get a reward right so you basically do this return in a iterative
manner okay so here's one example so suppose you have a maze here and you have a red dots which is basically the occasional agent and the state here
is the basically where is this agent and action is that the agent is going to be moving uh left right or
top of the bottom and next state will be like where will be the agent after that move so in terms of mathematical language if we put like a
coordinates X and Y into this two-dimensional maze then we can basically use two numbers to represent the state of the agent and also the action will
become like a subtraction addition of one of the numbers uh by one right so that's very clear oh okay cool
thanks so if we do this intuitively then what happens that you're going to have a trailer trade right the territory starts from S1 and you take an
action a it will give you uh state two and taking action two if you can use stage three and at the same time you also get rewards okay so what is the
reward is basically to say like if you choose action a uh what will be um uh the return um from this
action right so for example in this kind of physical scenario suppose there's a goal State and the goal say is basically at the exit of the Maze and I
go away of this agent is try to find a path all the way to the Ghostly and then we can exit there right so uh then like the if you are closer to the
go State then you will get a higher reward and this will basically uh trigger the agent to move
towards the destination right so the goal of reinforcement overall is to maximize the long-term reward uh by uh maximizing this like a capital R
functions and that random reward usually is a linear combination of all the short-term reward a one-step reward and here the gamma is a discount
Factor basically means that you want to favor short-term reward but you also want to consider long-term rule
as well but the long-term reward will be discounted uh using the discount Factor gamma that's uh that's how uh that's basically goal of reinforcement
you basically want to find like what is the best strategy uh to move around in this in this world so that the London world is maximized okay so
there's a few key quantities there are a few key quantities in reinforcement and so for example uh here
you have uh three of them right so um first of all you have this policy which is basically the probability of taking action a given State s you can
also have a Q function and a v function that is basically like the reward starting from the state as and the basically an expected reward out of it
and the difference between q and V is that in Q function you try to find what is expected reward if you
start from s and taking action a and but for V basically that's the rewards you can get if you start from the state s but there's no like action
Conditioning there so for all these three properties as long as you get one of them it's sufficient to find Optimal strategy right so for example if
you manage to get like a pi which is a policy then just follow the policy you just say okay in the current
state okay I will check the policy book but let's see Playbook say okay you take the action a okay just take action a it will give you the optimal
strategy right similarly if you already have the Q function then what happens is that given the kernel State you go through all the A's and then you
basically get a like a vector of the Q values and pick the best one uh then you basically also get the
best policies Etc so then like given these two then you actually have two different pattern methods right so if you optimize the policy it will give
you a policy based approach if you optimize the Q function it will give you a value-based approach that's basically the second part right so I'm
called I'm going to cover a little bit about the value basic approach first and then I will cover uh the
policy based approach so first let's cover the database approach uh so for variables of course you want optimize Q so how we're going to optimize Q is
actually pretty simple right so consider that Q is actually table which has uh has like a lot of slots so if you have a number at the neural States
it's like s and no action is a then the Q table will become s times a so this kind of a few tables
and your goal is trying to just fill in these tables until your table is optimal then you just follow option policy right so what you do basically
very simple right so you get like few territories and for each other tree you update these Q functions using this formula right so if you update that
for sufficient time then the Q function will be proved to be converting to the optimum queue then you
add them however the world is not as nice as that because in practice Q function may have exponential number of entries right because the state can be
exponential and a Also may be a continuous value so in that case like people come with this lead Q learning ID in which like we can replace the Q
function as a table by a parametric function which is represented by a neural network so you have a
neural network then you also will directly give you Q function given S and A or the nearest will give you uh the list of a given Q Prime so these are
all basically different approaches you can parameterize Q functions so once you have the parametric function then what you do is that you can just
secure this Q function every time and this Q function is going to be generalizable to basically like a
new state that you have never seen before and this is going to the benefit of using the Deep models so but if you directly optimize that function it
will lead to instability because you see like on the both side they're going to have a Q and this Q are parameterized by Theta it's going to be
unstable if you train models so uh people basically think about like different hacks in order to make
things work well how it would be like you basically wanted to fix uh the queue function that is on the right and then the Q functions parameter is
also fixed use the um the old fixed parameters and then you use that to update the queue function on the left hand side right so uh that's actually
like the way you update that but there are still issues the issue is that you mean after this update it
may change the QC that function substantially this will also lead to instability so then what we do here is that we can actually make the target even
smoother which means that we don't need to I want to update the Q function in one shot but we want to up the Q function you know kind of gradually
manner so you still have the Q function in the right hand side but now you have a kind of like a some
kind of Correction term that correction term is called the temporal difference error so TD error so the correction term is basically difference
between the current Q function and the future the Q function that according to the Future rewards right so you basically do that and update and then
all you will give like more smoother updates and the algorithm can converge so this is called the dqn
algorithm that's basically published uh in nature uh in 2015. so here's like a one uh simple like video showing like how people see this function
functioning and this is algorithm function you start from like a very simple games and that game is basically like uh when people play with this game
called breakout right so you basically move the pedal around and pick the ball and so the ball bounces
around to kick out all the bricks on the top at the beginning the agent is like doing like a very bad thing so you mix level all the time but over
time when you keep training the Q functions then um it will become like a much better right so it will basically like try to basically pick all the
balls that is bouncing around and finally can clear up all the other all the uh all the bricks on the top
right so that's how the thing works okay so uh there are like a multiple uh different like extensions that you can leverage uh for solving the Q
learning problems the first uh basically the first approach that people were thinking about and it's very effective is called multi-step programming
so instead of like a going one step further and retrieve the future queue and use that future queue to
update your current uh clear functions uh you can basically go uh forward multiple steps that's called and step layouts usually this will basically
give you like more accurate estimation of the future values right so and this basically is like one of the standard approach people will use right and
another like a thing that people will think about is called replay buffer so uh the Traditions here
are basically all generated by the previous policies right so usually the previous policies um you learn them and then you collect the directories
into a replay buffer and then you get the data from the paper for Android basically like execute your or learning algorithms right so that's basically
the idea of the play buffer and the folder buffer is actually you can see this as like a dynamic data
sets right the dataset has a lot of expert experience and you take the data sets inside and you're updating it at the same time you train these models
right but if you think this uh concept of paper for a little bit more then you actually think you actually realize that this is actually very
different from simplified learning right so this actually uh give you this difference between the two
concepts uh in the reinforcement one is called arm policy and the other is called all policy approaches so for all policy it's very simple it's kind
of like super learning you have a fixed data set and you train your reinforcement agent on the fixed data set right so difficult data set can be
collected by expert behaviors or can be like a uh coming from some like historical data but on the
reinforcement side there's another kind of uh kind of like rental algorithms are called on policy either on policy usually the data sets are sampled
by the current models and the data will actually be updated again with the model get update as well so in reinforcement a key difference here is that
agent not only learned from data but also choose which data to learn this is actually very
interesting so this is kind of one example right so you start from like going State and then you first collect a few data on like one branch of the
space and then you start to explore another branch of the space and collect more data more data model and then the data becomes larger and larger and
cover larger space and your policy become more stable all right so but that's also a way with the
trade-off because the space is exponential you cannot explore every possible state so there needs to be a trade-off so one way to hand this trade-off
is what is called medical research so in much research what happens is that you try to update your QQ values on the Fly uh depending on your
exploration and once you have new Explorations and that exploration will basically leads you to update your
queue functions and then you explore the space larger and at the same time your queue function becomes more accurate and the medical Tracer in some
sense is optimal in terms that I mean in the long run if you run like a sufficient number of Trials it will eventually cover the entire search space
and give you Optimum policies so along that line you actually see like a lot of applications this
include this deepminds Alpha 0 series and they are basically using the the this kind of loop in order to uh optimize and to find like what is option
policies right so this Loop is actually quite simple it's exactly like what I just said you start from this medical research and then you collect lots
of data and then once you have lots of data you update your current models uh using reverse memory
uh and then you use this updated model to generate more data right so let me do this kind of intuitive approach until you actually gets good Solutions
so that's uh and this work it used to leads you to like a superhuman performance right so we also follow the same kind of paradings this is one of our
work in the 20 uh 2019 that we're actually able to create a very strong robot that can be
professional players in a single GPU this professional player I'll go coming from like Korean gold associations and basically no one can able to beat
it um in the finite amount of time so a recently Divine also comes with this Alpha tensor approach uh basically this one is also a kind of application
of the alpha zero kind of method right so the question of alpha tensor is how to multiply two
matrices of PSI n by n but with a small number of multiplications right so it's we all know like a stress is a matrix multiplication you can multiply
two by two matrices with only seven multiplications but what happened with larger and larger and larger matrices so in that case like we actually can
write down the alpha tensor write down the mission replication formulation as this follow objective
basically mathematically you can show that you want to this equivalent to minimizing the rank of the third order tensor and this third of the tensor
is written as the following kind of formula right and this TN is a predefined tensor of size N squared by N squared by n square that represents this
multiplication structure of these two n by instances and you want to find what is the best
decomposition of this TN so that the composition will have the fewest terms this term is called the rank here right if you have fewer terms this
represents that you have fewer uh number of multiplications in the final algorithms right so the goal is to search this UV and W so that this
constraint satisfied and the I is minimized so what they do is very simple right so you basically treat this as
reinforcement carbon right you start from the original state in which s0 equals to this TN this kind of tensors and then every time you try to find an
action this action is consists of a U V and W and then you basically subtract this term from this tensor and you get S1 this is New State and then you
do this iteratively until hopefully at some point your St becomes zero which means that you
actually arrive at the decomposition uh that has all this rankling terms and your goal is to find like this St goes to zero as soon as possible right
so that's basically like the correspond to the lower rank Solutions uh they basically like use this Alpha after their kind of approach in order to
solve these problems and there they actually find a new matrix multiplication uh schemes so that the
number of medications is smaller then the best known rank right so that's actually pretty impressive you know it'll be this kind of a computer
optimization problem character will be solved in this manner okay so yeah the dimension of s here is a so this is equal to dimension of TN right and T
as the third order tensor so uh okay if you come back here so if you have n Square by N squared M squared
right so if n is equal to 2 then becomes four times four times four this is 64 dimensional sorry [Music] yes but I may have lots of I mean there's a
commentatorial structures there right so it's basically explanation okay so I will quickly also cover the second part uh sorry I need to uh because
this tutorial so I don't want to cover like too deep too deep but we want to cover like many uh
different uh directions and so that people have over a picture about the word reinforcement is doing so we also can do policy based approaches right
as I just said uh as long as you optimize you get like a one uh one key quantity solved then the problem is solved right so the post-based approach is
basically trying to focus on policies you want to basically learn a policy directly in order to
maximize your overall rewards if you write down the object function JC dot here the obvious function jcdot actually consists of these policy functions
directly right so you basically get territories from the price functions and then you can basically like find Community rewards along the territory
and you want to maximize that objectives so after some mathematical manipulation you actually can
come up with this gradient of uh of this updated functions and the gradient here is in terms of student expectation but uh it's kind of like a
summation of this scoring function and the reward right so and the good thing about writing this as expectation is that you can instead compute using
tight exploitation you can basically do and set a sampling approach right sample or any kind of territories
with these policies and then you basically like approximate the gradient with respect to the trajectories right so then you have an approximate
gradient and you can use the Xbox equator to update your cdas Etc and here the reward here can be taken can take in different forms it can be uh just
like as simple as just the reward by definition so that's basic definition that's the reward function you
can get but it can also be uh basically like a combination of the n-step rewards and the final V functions uh that is being estimated future rewards
and put them together it can also be maybe like just a q function uh that is being estimated at some point right it can take different forms but the
issue with consequent is that if data on policy that is learned quite fast but if data is not on
policy then there's a there's some issues right so you really need to have data to trans actually drive these entire algorithms right so if there's
but that this basically means that if you if every data point has been used in the data points once have been used to update the update function it
has you have you have this through this away right so because the data is no longer on policy and the
policy has been updated so you cannot uh just use that onpause data to update your iPhone again that's actually bad right so this is actually a lot of
waste in terms of the computational time so then people come with this kind of policy Corrections so how we do this objective Corrections is that we
actually add a term in the uh in the gradient right so in the prosequent approach we have this clean
forms but when the data comes actually not from the policy itself but come from some Behavior policies beta which is not necessarily the same as the
current policy you actually add the additional term roof T that so that the final like estimation of the gradient is student biased right so here this
root is important an important sampling factor that is the ratio between the policy that's being
currently used and the uh to the behavior policies so basically the ratio of the two right so obviously if by if pi equals to Beta then this rule T
will be one and it will come back to the original policy green updates but then there's a problem the problem is that the routine can go to Infinity
right so if you actually hit a action they have never experienced uh in your behavior policy right but
you actually experience like we're not one in a lifetime then this routine will go to uh go to basic Google app so in practice what people do is that
there will be a cap for the Roti so that the problem uh the estimation is not unbiased it's not unbounded right so and then the equivalent can be
pretty stable so uh based on the policy update policy gradient update so we can also uh improve on top
of that so that's basically the algorithm usually people call this actor critic so what they do here is that instead of using the Q function as the
reward in the actor in the project gradient we can use Advantage function the value function is trying to basically find the relative advantage of an
action relative to other actions right so here is a very simple illustration you start from State s
you can roll out like multiple different trailer trees and some of them will basically give you for example a higher than average return some of them
give you lower than average return right so at Advantage will be like basically the advantage of a one action compared to other actions right so
that's basically the definition of identity functions you use that and once the user identity functions
and also you use the motion to compute Advantage functions then in your algorithm you have to estimate both policies which is pi and the value
functions which is q or V right so uh then this algorithm actually become called actor and critic in which like you are optimizing both the actor and
also the critic at the same time uh maybe with different parameters that's the definition of the critic
algorithms and one of the famous actor critic algorithm is called a policy of proximal points optimization abbreviated as a PPO so these algorithms
what you do is actually exactly the same as such as I just said so you have uh the advantage functions and you also want to clip uh this rule which is
the importance Factor so that the rule is not going to be too far uh from one right so and that
algorithm is called PPO is actually being widely used in many different scenarios and including the open AI 5.2 there's a box that can beat like
professional data players and we also see people being used in like IHF uh in many different scenarios so uh so this is actually one of the uh very
widely been used algorithms in practice in reinforcement in literature okay finally uh we have like me a
few minutes left I'm going to talk a little bit about uh the application of using reinforcement uh for Network planning problems so this is a paper
that uh we have published uh in uh AAS ccom 2021 so in that problem we are dealing with a very concrete like a system problems is that you have like a
Network that has n different nodes and these networks will have connect interconnect capabilities
right so for node a node B there's a connection and the connection can be a fiber it can be a cable okay whatever and you basically want to borrow
these different capacities to map to basically meet the needs of the network like data flows but at the same time you don't want to use too much money
right so there's a minimum minimization of the cost so the entire optimization problem can be written
down as the Interlinear programming right so in that case like there will be an operator function and you want to minimize some cost uh overall cost
for basically like borrowing different fibers at different sites but there is a constraint right so the network flow and then you'll be conserved and
there's a link capacity and there's a lot of other capacities constraints and also you don't want to
like change your current topology for too much right so basically there's a lot of constraints but if you want to solve this problem from scratch
there's a lot of stories like iot service but they are very it's very tricky to use it because the problem itself can be huge right so it may take
days or weeks in order to solve this problem uh but from scratch so in order to do that usually people will
Design their own heuristics to trade optimality for attractability right so you want to find oh let's maybe you can solve a small problem first and
then combine all the solutions together right that's one possibility then this will be one Solutions but we want to find like make better Solutions
right so then the key problem here is it's hard to find feedable solutions for this IRP problems right
so uh how to do that we basically train a reinforcement agent uh to actually like solve these problems so we start from this problem description which
is a network and also all the capacities different edges you basically train an I reverse an agent to propose any initial solution and then we
basically feed this in this solution into the IRP solver and then episode will give you the final solution
much faster and also at the same time with high quality that's basically how it works so uh basically is a two-state approach right for stage one what
do we do is that we start from the topology the topology is being given as basically the problem specification at the beginning there's no uh capacity
at every edges of the topology and every time the reinforcement agent will find a way to add some
capacity at some edges right and then it will keep adding the capacity and two at one point problem uh the solution becomes feasible right so that's
basically the entire trajectories right so uh and the reason why we think this is more reasonable than like the solves the entire problem in one
sketch is that it's much easier to check the feasibility of problems than to find the optimal solution of
the problem in one shot because the visibility check it can be done and it can be accelerate in like a lot of with the different aspects right so for
example uh what you can do is that you can basically shrink the graph by a source aggregation basically different nodes inside which hacker if the if
the aggregated the problem is not visible then okay the original problem cannot be feasible can get
rid of that right so there's a lot of shortcuts you can use to do visibility check so you basically leverage like a reinforcement to learn what is the
best policy to add different uh capacity at different edges so that the problem become feasible as soon as possible right so once it's done then we
can actually go to the next territories and keep coming running so and the reinforcement architecture
yeah sorry
[Music]
no I think for IOP because it's a very general solver right so it may not leverage the problem-specific structures right so for this one because you
already know the topology right so and the reinforcement trying to leverage the structure of the problem to find the best policies
what are the keys operators [Music] I think the uh okay I'm not sure if I understand the question so here we are basically find the optimal policy so
that you can I mean intuitively increase the capacity at every edges and the capacity being added may have maybe a function of the actual Network
structures right so humans may have their own perception before say okay here's the Boston act yeah then
it seems like there's a person and then we add more capacity in this position like to solve the problem okay so okay so for this one um it's uh it's
it's actually as easy as like you just like a fine like what is the solutions there right so you basically find like what's the it's basically this
one right so you physically check like whether this topology is feasible if it's feasible then uh then
like uh yes and you basically performance solve and you usually go to the second stage if it's not feasible then you go through the reforms agent you
pick like the the the capacity there yeah that makes sense okay so uh in terms of the reinforcement architectures it's very simple you basically like
put all the features and topologies into uh into a graph in your network and then you learn a
graphic embedding and that embedding will be used to predict the actions as well as the rewards as well as the critic so that's the actor and critic
Network and the actor Will basically pick which I which like a address to add capacity and the critique will tell you uh whether it's promising uh to
going through that line right so you basically learn activity uh agent uh to find the the find the
way to add your capacity over time so and stage two is very simple right so once you have reinforcement and solutions what you do is like you can
basically add a solution back to the IRP uh solver and then you only allow IP server to search in the local Varsity of the reinforcement Solutions and
this will actually make things much easier because you already have a feedable solution as a
reinforcement solution and IOP will be able to leverage that in order to find better Solutions because this reinforcement solution give you a lower
balance about how things can be so it's much easier for IP server to solve a problem and the finally we actually we have to find that our approach are
able to give you a solution that is better than the heuristics and in terms of like a lower cost at
the same time can deal with like a larger non-network topology right so here A B C D E are five different topologies and E is the largest and you will
see that if you just saw IOP solutions from scratch and uh for this last three is basically like a for the last four it basically gives you like a
e-feelable Solutions uh yeah given like a short amount of time but ours we are able to find a good
Solutions at the same time and it's quite fast for larger Networks in the code is only online and people are interested you can take a look okay so
this conclude my tutorials and so let me know if there's any more questions