Previously we learned about terminology the various words we use to describe reinforcement learning
problems which allow us to solve reinforcement learning problems.
Now that you understand concepts such as agents environments policies states actions and rewards we
can build on this.
The goal is to have a framework which we can then use to find solutions.
So at this stage we are still working to more accurately and more narrowly define a problem.
Once we have an accurately defined problem we can work within this framework and whatever assumptions
it involves to derive solutions.
The main assumption we make in the reinforcement learning is the mark of assumption.
This is something we often discuss in terms of mark of models and sequence modelling.
But let's review it here anyway.
The Markov assumption goes like this.
Suppose we want to predict whether tomorrow will be rainy sunny or cloudy.
Perhaps your idea may be to base this on whether it was raining sunny or cloudy in the past seven days.
Well the Markov assumption is that tomorrow's weather it doesn't depend on all of the past seven days.
Only the immediate previous day
here's another example of the Markov assumption.
Suppose I want to predict the next word of a sentence.
I tell you that the previous word in the sentence is lazy.
The mark of assumption is that the next word only depends on the previous word.
Therefore if the Markov assumption is true then you should be able to predict the next word in my sentence.
Of course things are not so easy you might think because you are taking a course by the lazy programmer
that the next word in the sentence is programmer but in fact that's not what I had in mind.
Now let's suppose I tell you the full sentence so far is the quick brown fox jumps over the lazy.
Of course we know that since we've seen this example many times that the next word is dog so you might
think this mark of assumption thing doesn't really seem to be a great idea.
In fact there has been some work in reinforcement learning where they do not make use of the mark of
assumption although that is outside the scope of this course.
The mark of assumption has actually been quite successful so far.
In general the Markov assumption states that the probability of the state at time t depends only on
the state at time T minus one and not on any state that came before that now by itself.
The mark of assumption is weak but as you recall I said earlier that we can make the state whatever
we want.
So if we want to make the state three or four words long that's fine too.
The words are merely observations but the state is made up of a sequence of observations.
In this way the Markov assumption is not as bad as you might initially think.
So why do we need to know about the mark of assumption.
This is because reinforcement learning problems are commonly described as a Markov decision process
or MVP.
Previously we discussed the Markov assumption in terms of a state only but as you know reinforcement
learning problems involve other objects as well namely actions and rewards.
So the way we describe an MVP is to use the state transition probability it's the probability of arriving
in the state at time T plus 1 and getting the reward at times plus one given the state at time t and
taking the action at time t another simpler way of writing this without time indices is just to write
P of s prime and are given as in a note that because the reward R has no prime symbol the prime symbol
does not indicate time T plus 1 you get the reward at time T plus 1 for arriving in state as prime.
But we do not put a prime symbol on r
so I just showed you the most general way of writing down the state transition probability but often
we can make it less general.
For example if we are solving a maze then most likely we are going to make the reward deterministic.
In other words there's no need to represent it as a probability distribution.
In this case we can use the notation P of s prime given SSA and the reward it can be a symbol all by
itself usually denoted as r of essay as prime.
This encodes the idea that we were in status.
We performed action a and we arrived in the next state as prime we can even just say r of S or R of
as prime.
In the case where the reward depends only on the state where you arrive at which is actually quite common
an important point to consider is what is the usefulness of the state transition probability.
You can imagine that if we are playing some game like breakout on a tree it is very unlikely we will
ever be able to calculate these probabilities given that the state space would be in a feasible to enumerate
and in fact for Q learning the main algorithm we're going to discuss in the section this probability
is not used at all.
I want you to think of the MVP and the state transition probability as stepping stones.
They are simply conceptual tools which we will use to further advance our knowledge and take us to a
point where we can actually come up with a practical algorithm for reinforcement learning in other words
while we're not going to be using state transition probabilities directly in Q learning.
They do help us build on what we've done so far so that we can actually arrive at Q learning in a logical
manner.
Why else is the state transition probability useful Imagine a game like tic tac toe.
You might think there is nothing probabilistic about this game.
When I write down an extra I know that's where the X or the O goes.
Why is there a possibility associated with that.
Why is my action not deterministic.
And in fact it is entirely possible for your action to deterministic Lee bring you to the next day imagine
for example a classic test known as the inverted pendulum.
And this reinforcement learning task your job is to control an upside down pendulum so that it does
not fall down by moving the cart left or right as necessary.
Now you might think to yourself how do we describe such a system.
Well we use the laws of physics and now think to yourself are the laws of physics not deterministic.
For example when we learn Newton's three laws of motion to those laws of motion involve probability
the answer is no.
So then what in the world do we need.
Probability for
the answer is that your state may not completely capture all the possible information about the environment.
Consider tic tac toe again in tic tac toe.
There is another player that players moves cannot be predicted by a tic tac toe Asian.
Therefore there are multiple possible moves that could occur between the agents previous move and the
agent's next move.
If we're talking about physical systems we also have to take into account chaos theory that is even
if you know the exact laws of motion.
This does not mean you can accurately predict the future.
In fact the further into the future you try to predict the more unreliable your predictions become.
Sometimes we refer to the transition probability as the environment dynamics which makes sense when
you think about it in the context of physical systems.
A system like an inverted pendulum is in fact a dynamical system.
The last thing I want to mentioned in this lecture is to bring us back to this picture which you've
probably seen several times at this point.
An MVP or a reinforcement learning problem consists of these two objects the agent and the environment
going back and forth.
The agent reads the state from the environment and decides what action to take.
It takes that action in the environment and the environment is updated based on that action and brings
the agent to the next state while also returning an associated reward.
The agent can then read this next day take the next action and so forth.
So they just go back and forth in the circular pattern.
What we've done so far is to represent both of these objects with probabilities the environment as represented
by the state transition probability P of s prime and are given us and a.
The agent is represented by the probability Pi of a given s this is more helpful than you probably realize
at this point by representing both the agent and the environment as probabilities it allows us to describe
reinforcement learning problems mathematically in particular.
Once we have an equation we can solve that equation without an equation.
There isn't really anything to solve.
That's a pretty deep inside.
In order to come up with a solution we have to have a well-defined problem using mathematics specifically
probability allows us to create this well-defined problem.
And that's the first step towards finding a solution.