In everyday life, we learn
a lot without getting explicit,
positive, or negative feedback.
Imagine for example, you are riding
a bike and hit a rock that sends you off balance.
Let's say you recover so you don't suffer any injury.
You might learn to avoid rocks in the future and
perhaps react more quickly if you do hit one.
How do we know that hitting a rock is bad
even when nothing bad happened this time?
The answer is that we recognize that the state of losing
our balance is bad even
without falling and hurting ourselves.
Perhaps we had similar experiences in
our past when things didn't work out so nicely.
In reinforce and learning
a similar idea allows us to relate the value of
the current state to the value of future states
without waiting to observe all the future rewards.
We use Bellman equations to formalize
this connection between the value
of a state and its possible successors.
By the end of this video,
you'll be able to derive
the Bellman equation for state value functions,
define the Bellman equation for action value functions,
and understand how Bellman equations
relate current and future values.
First, let's talk about
the Bellman equation for the state value function.
The Bellman equation for
the state value function defines a relationship
between the value of a state and
the value of his possible successor states.
Now, I'll illustrate how to derive this relationship from
the definitions of the state value function and return.
Let's start by recalling that the state value function
is defined as the expected return starting
from the state S. Recall that
the return is defined as
the discounted sum of future rewards.
We saw previously that the return at time t,
can be written recursively as
the immediate reward plus
the discounted return at time t plus 1.
Now, let's expand this expected return.
First, we expand the expected return as
a sum over possible action choices made by the agent.
Second, we expand over possible rewards
and next states condition on state S and action a.
We can break it down in this order because
the action choice depends only on the current state,
while the next state and reward
depend only on the current state and action.
The result is a weighted sum of terms consisting of
immediate reward plus expected future returns
from the next state S prime.
All we have done is explicitly write
the expectation as it's defined,
as a sum of possible outcomes
weighted by the probability that they occur.
Note that capital R_t plus 1 is a random variable,
while the little r represents
each possible reward outcome.
The expected return depends on states and
rewards infinitely far into the future.
We could recursively expand
this equation as many times as we want,
but it would only make the expression more complicated.
Instead, we can notice that this expected return
is also the definition of
the value function for state S prime.
The only difference is that the time index is t
plus 1 instead of t. This
is not an issue because
neither the policy nor p depends on time.
Making this replacement, we get
the Bellman equation for the state value function.
The magic of value functions is that we can use them as a
stand-in for the average of
an infinite number of possible futures.
We can derive a similar equation
for the action value function.
It will be a recursive equation for the value of
a state action pair in terms of
its possible successors state action pairs.
In this case, the equation does not
begin with the policy selecting an action.
This is because the action is already
fixed as part of the state action pair.
Instead, we skip directly to the dynamics function
p to select the immediate reward and next state S prime.
Again, we have a weighted sum over
terms consisting of immediate reward
plus expected future return given
a specific next state little s prime.
However, unlike the Bellman equation
for the state value function,
we can't stop here.
We want to recursive equation for the value of
one state action pair in
terms of the next state action pair.
At the moment, we have
the expected return given only the next state.
To change this, we can express the expected return from
the next state as a sum
of the agents possible action choices.
In particular, we can change
the expectation to be conditioned on
both the next state and
the next action and then sum over all possible actions.
Each term is weighted by the probability under Pi
of selecting A prime in the state S prime.
Now, this expected return is the same as
the definition of the action value function
for S prime and A prime.
Making this replacement, we get
the Bellman equation for the action value function.
So we have now covered how to derive
the Bellman equations for
state and action value functions.
These equations provide relationships
between the values of a state or
state action pair and
the possible next states or next state action pairs.
You might be wondering why we care so much
about these definitions and relationships.
The Bellman equations capture
an important structure of
the reinforcement learning problem.
Next, we will discuss why this relationship is
so fundamental and reinforcement
learning and how we can use
it to design algorithms which
efficiently estimate value functions.
