welcome back so in this lecture i'm really excited about telling you
uh about how reinforcement learning connects with optimal nonlinear control this is just a splash
screen don't try to read everything i'm going to build this out and go through it carefully
i just wanted to kind of show you this is going to be a really cool one and this fits in again to
this bigger picture of reinforcement learning that we've been talking about specifically down here
in this kind of model based reinforcement learning where instead of a probabilistic process
we're dealing with a nonlinear dynamical system or differential equation x dot equals f of x comma u
and we you know in the control boot camp we talked a lot about how do you do
optimal control for linear systems when these dynamics are given by a matrix a
times x plus b times u and this kind of generalizes it to fully nonlinear dynamics
okay and again this fits into this idea that richard bellman put forward in the 50s
basically you can view this optimal nonlinear control problem as part of a broader class of
optimization where you can use ideas from dynamic programming and this is bellman's
equation that we've seen before in reinforcement learning we're going to see something like that
for these differential equations so optimal nonlinear control the idea is that we're going
to be working with this differential equation so x is the state of my system it's a vector of
information that characterizes the state of my system like a pendulum on a cart for example
the position of the cart and theta and theta dot the angle and angular velocity of the pendulum
and f describes the kind of dynamics the f equals m a dynamics of that system
and the goal is going to be to design some control law u so u is something we have control over we're
going to design a control law u to follow some trajectory x of t that minimizes the cost j
and that cost j is going to be given by this cost function and i'll walk you through this
so this j is a function of the trajectory x which varies in time the control u which varies in time
we say that this has a start time and an end time t 0 and t final and on the right hand
side this cost function is given by some kind of a terminal cost and you we usually include this to
say you know maybe i'm trying to get to some final location and if i don't quite get there there's
some cost associated with that so i want to get to some final location and maybe i also can penalize
how long it takes me maybe i have a term that is you know a cost proportional to the final time tf
something like that and then this term here is the amount that that you increase the cost at
every little time step along the way so you're going from state x at time 0 to exit time tf
and at each step along the way there is some cost associated
uh with typically with being far away from your state so usually my goal minus x at time now
uh and also there is usually a cost associated with using that control input u maybe that
you're actually burning gasoline and it costs money okay and again this could simplify in the
case of linear dynamics and a linear quadratic regulator cost function this might be just uh x
transposed times x so kind of x squared plus u squared we might just measure kind of the uh the
square sum of errors of x minus its goal state and of the control input u in which case this would
reduce to a linear quadratic regulator problem if the dynamics were linear and so what we can do is
essentially introduce this value function just like in reinforcement learning before
this value function is essentially the cost j when we have minimized over the control input u
So basically out of all of the possible control functions u(t) you could pick,
which is an infinite dimensional function space of functions *u*, if we minimized over all of those
controllers then the minimum possible cost, the best possible thing we could do to get
this minimal cost, that would be defined by this value function. And it no longer is a function of *u*
because *u* is specified. It's also not a function of x(t) because that is also specified by *u* and by
the dynamics. It's only a function of my initial condition and my start and end time and this
value function is sometimes called the cost to go. I'll come back to that in a minute.
So what Bellman did, and this is a big deal, so Bellman essentially generalized the Hamilton Jacobi
equation for optimization. If we didn't have u(t) here... if we just had a free system
and we were trying to, for example, find the minimum time solution of a differential equation or
the minimum distance solution, or things like that, then the Hamilton Jacobi equations would be useful.
Those actually generalize some ideas that Bernoulli came up with from the variation
the calculus of variations to solve things like the Brachistochrone problem, the finite
time problem or minimum time problem. And what Bellman did was essentially write down this
partial differential equation that has to be true for these optimal solutions
given by this optimal *u* and we're going to derive this. This is a little bit hairy so if
this doesn't look obvious, it's not. And we call this the Hamilton Jacobi Bellman equation. So the
Hamilton Jacobi equation was around for a couple of hundred years, maybe 150 years earlier
and again generalized Bernoulli's calculus of variations and Bellman came along and basically
extended it to include systems with control inputs u(t). So this is a big deal... this is one of
the biggest most important equations in nonlinear control theory, is this Hamilton Jacobi Bellman equation.
and so just to recap the idea is that this value function is the cost given
that we have optimized to find the best possible control input u of t and the best u of t sometimes
is a function of x you might you know in a linear quadratic regulator it would be a function of x
uh defined that way so we're going to actually derive this and show where this comes from and uh
and also talk about how this partial differential equation is is what you actually need to solve
for for finding that that optimization that that optimal control u because this has to
be true for the optimal uh minimum solution u you can use this to actually solve for you
good and this all relies on on bellman's principle of optimality so this has been something we looked
at before in reinforcement learning and we're going to look at it again for for this problem
so the idea here is that the value function this this cost to go from time 0 to time tf
can be written as the sum of the value function on any two segments that make up that trajectory
so if i pick some intermediate point along this trajectory x of t at any intermediate time t then
i can add up the the value function from t 0 to t and the value function from t to t f and that
sum is given is the value function across this entire trajectory and what that means is that at
any point t along this trajectory the remainder of my trajectory still has to be optimal if i
imagine that my problem just started over with this new initial condition x of t at any point
along this trajectory it still has to be optimal as if i started from that initial condition
every decision i make in the future still has to be optimal and so that's a really important
idea this bellman optimality means that we can break this problem up and essentially solve
uh this optimization using kind of smaller optimization problems exactly like what we did in
dynamic programming for uh reinforcement learning before okay really important so we're going to use
this to derive the hjb equation and again what we're going to do is take this value function
and essentially expand it out we're going to take the total derivative in time and we're
going to expand that out so that's the partial of v with respect to time plus the derivative
of v with respect to the state x times dx dt so this is how you do that kind of total derivative
and we'll notice that uh dx dt is going to be our dynamics x dot equals f of x comma u
okay and so this expression here essentially what we're going to do is
this expression on the left is just d dt of my definition of v
and so this is my definition of v here where what i've done is i've put the d dt inside the
minimization because i'm minimizing over over u of t i can kind of swap those two those two terms and
so if i take ddt of this integral i should just recover uh i should just recover my my integral
whatever is inside the integral because this is a definite integral from 0 to tf this
terminal cost kind of is fixed and so what we're going to get is is minus the argument l
of x t u t okay so that's that's what this is going to equal when we take its derivative and
uh and then we're going to minimize that over uh all u's and so essentially what i can do
is i can take this expression here and this expression here and i can equate the pieces
so i'm going to move things around and get a minus partial v partial t equals um kind of all
of this stuff here that's this minimum uh l plus this partial v partial x transpose times x dot
which is this term here okay and i can you know this term here because x dot equals
f of x comma u i can put that inside of this minimization over u so i have to put this inside
the min of u because now i've replaced my x dot with f of x comma u so that was a little fast you
should really kind of carefully convince yourself that this is true and in fact there's actually
you know a couple of pieces i glossed over a little bit this is not the most
precise way of deriving this possible the best way to do this is using the calculus of variations
this is kind of a sketch of why this works um and you know i think that this step from here to here
you'll really want to convince yourself of why i could drop these bounds of integration and
when i take the derivative with respect to time uh why why this works out the way it does okay
good and so that is kind of how you derive this this hamilton jacobi belmont equation now the idea
is that this is a partial differential equation it's a partial differential equation because v
is a function of t and of x and so you can take its partial derivative so this is a big
partial differential equation and we generally can solve this partial differential equation
for v and then once we have v we can extract u from it okay and uh to some extent the way
we generally do this is using a two point uh this is a two point boundary value problem
because we know uh what our final state is where we wanna be and so we can kind of and we know our
initial condition is and so you can use like shooting methods or other approaches to solve
this two-point boundary value problem good uh okay so that was the continuous time hjb i'll show you
just briefly how to do the discrete time hjb when you have discrete time dynamics and in this case
you can similarly write the cost function as the sum of a bunch of intermediate costs at each step
plus some final cost at the nth or last time step so here we have discrete time steps
and again this cost function is defined starting with an initial condition a control sequence and
however many steps and i'm going to take and so similarly you can define this value function where
it is the best possible cost ji could possibly have if i optimized over that control sequence u
and again the bellman optimality the kind of discrete hjp equation or bellman equation
here states that again the n step value function the value function starting from an initial
condition taking n steps is the same as the sum of the value function for any two segments that
kind of add up to that full trajectory so if i start you know if i go from from time step 0 to
step k that's this term here that if i started from x k it should still be optimal in the future
meaning if i started from x k and i went you know to that final n step it should still be optimal
uh going into the future good and i think here this this probably should be an n minus k
and that can also be useful uh for these equations so then you can actually um solve
for sorry i think that was a statement of bellman optimality um i think this is a typo i think that
i should say that this is a statement of bellman's optimality condition and this is going to be the
the discrete hjb equation right here so again you can kind of represent this as the minimum
over all of the control sequences of those intermediate costs at the current step xk
plus the value function at the next step because of the bellman optimality essentially what i have
to do is i only have to optimize my cost at the current kth time step i only have to optimize
my control right now so that if i step to the next step through these dynamics if i go to xk plus one
you know this v k plus 1 is is also minimized so let me say this again what i'm trying to do
and my my parentheses are completely botched here i apologize
the parentheses should be the minimum of u should be outside of these parentheses
so what i'm doing is i'm picking the best u at the kth time step right now so that the current cost
plus my future value function at the next time step is minimized and again this is a statement
of bellman's optimality that i can break this up into a recursion where the value function at the
step now can be written in terms of the cost now plus the value function at the next time step and
this allows me to do this kind of recursive or iterative optimization to solve for this
and again there's a lot of numerical methods this is a huge field i'm showing you how these
are derived and what they are there's a huge field actually showing how to solve these
and they're they're very expensive i should point out um this is important when i derived
the hjb here for continuous time systems i said that this is a partial differential equation
and what that means if my original dynamics x dot equals f of x comma u if my original
system had three discrete states x1 x2 x3 this is a three-dimensional partial differential equation
that's very expensive to solve if i have a 10 dimensional state i have a 10 dimensional pde
if i have a thousand dimensional state i have a thousand dimensional pde and we're you know it's
pretty expensive to solve a thousand dimensional pde so these are really expensive to solve you
actually can find an optimal nonlinear control solution but it requires solving this kind of
heinous pde in high dimensions and that's really really challenging numerically okay so that's
important similarly you can do this for hjb and this is a better way of writing it recursively
where i actually was correct and pulled the minimization out this is again for discrete hjb
and the idea again is that once you have this expression here this kind of bellman optimality
expression this starts to look a lot like what we had from reinforcement learning so if you
minimize this expression over u you get the um the value function at that point and if you do
the argument if you find the u that minimizes this you have extracted a control policy this would be
the optimal control u equals pi of x okay that was kind of a whirlwind a little bit high level
but what i want to show what i hope to show you is that these ideas from dynamic programming and
reinforcement learning also connect very strongly with optimal non-linear control
which is kind of a generalization of what i've shown you before in the control boot camp
for linear systems like lqr controllers okay good so that's this piece here and i'll probably have
more lectures on kind of non-linear optimal control maybe more from a non-linear control
perspective and less from a reinforcement learning dynamic programming perspective
but i hope that gives you kind of a flavor of how these things fit together all right thank you