Markov Decision Process - Reinforcement Learning

reinforcement-learning

cover: https://img1.wsimg.com/isteam/ip/7ecb9a34-1c63-4a1f-89db-2f3124edebd3/f4272377-c479-4863-a068-dd6bb6559be0.png

categories: []

---

A MDP is a discrete time-state transition system. MDP is actually a reinforcement learning task and it satisfies all the requirements of a Markov property. Furthermore finite MDPs having the finite actions and state fulfill the requirement of a Markov property. Finite MDPs are mainly important in reinforcement learning.

An MDP can be described formally with four components:

• A set of possible world states: S
• A set of possible actions: A(s) or A
• Model: T(s, a, s') ~ Probability(s'| s, a)
• A real-valued reward function: R(s) ~ R(s, a) ~ R(s, a, s')

A reinforcement learning task that satisfies the Markov property is called MDP. If the state and action spaces are finite, then it is called a finite MDP. Finite MDPs are particularly important to the theory of reinforcement learning.

To understand this framework, I will use the Grid World example as depicted in the following figure:

Figure 1: Grid World

State

MDP has a set of states; it represents all the states that one can be in. In the GridWorld example, it has 12 states and we can represent them in X and Y coordinates; say, the start state is (1,1) or the goal state is (4,4). Actually it doesn't matter whether we call these as 1, 2, 3 ...... 12 or A,B,C ... L. The point is that there are states that represent something and we should know which state we happen to be in. We can represent state as s.

Action

Next are actions--things that you can do in a particular state. Actions are the things I am allowed to execute when I am in a given state. What will be the actions in the GridWorld? In the GridWorld, we can take four types of actions: UP, DOWN, LEFT, and RIGHT. The point is that your action set will represent all the things that the agent, robot, or person we are trying to model is allowed to do. Now, in its generalized form, you can think of the set of actions one can take as the function state A(s). However, most of the time, people just treat it as set of actions or actions that are allowed on the particular state and represent it as a.

Model

The third part of our framework is the model, sometime called transition model. It describes the rules of the games that apply, or is rather the physics of the world. It's basically a function of three variables: state, action, and another state. It produces the probability that you end up transitioning s' given that you were in state s and you took action a. Here, s' is the state where you end up and s and a are the given state and action, respectively. In our GridWorld example, we are at the start state. The probability of going up is 0.8, the probability of going right is 0.1, and the probability that we end up where we started is 0.1. If we sum up all the probabilities, it becomes 1, and that's the way it works. The model is really an important thing and the reason for its importance is that it describes the rules of the game. It tells us what will happen if we do something in a particular place. It captures everything we can know about the transition:

T(s, a, s') ~ Probability(s'| s, a)

These processes are called Markov, because they have what is known as the Markov property. That is, given the current state and action, the next state is independent of all the previous states and actions. The current state captures all that is relevant about the world in order to predict what the next state will be.

The effects of an action taken in a state depend only on that state and not on the prior history.

Reward

Next is the reward. It is a scalar value that you get from being in a state. There are three different definitions of rewards (R); sometimes it will be very useful to think about them in different ways.

R(s) means we get a reward when entering into the state. R(s, a) means we get a reward when being in a state and taking an action. R(s, a, s')means we get a reward when being in a state, taking an action, and ending up in a new state. These are all mathematically equivalent but it is easier to think about one form or another:

R(s) ~ R(s, a) ~ R(s, a, s')

The preceding four components define a problem; now, we'll look into the solution. The solution to the MDP is called policy.

Policy

A plan or a result of classical planning can be either an ordered list of actions or a partially ordered set of actions meant to be executed without reference to the state of the environment. When we looked at conditional planning, we considered building plans with branches in them that observed something about the state of the world and acted differently depending on the observation. In an MDP, we can assume that it takes only one step to go from any one state to another. Hence, in order to be prepared, it is typical to compute a whole policy rather than a simple plan.

A policy is a mapping from states to actions. It says, no matter what state you happen to find yourself in, here is the action that it’s best to take now. Because of the Markov property, we’ll find that the choice of action only needs to depend on the current state (and possibly the current time), but not on any of the previous states.

A policy is a function that takes state and returns an action. In other words, for any given state you are in, it tells you the action you should take:

π(s) -> a

MDP - more about rewards

Generally, in a reinforcement learning problem, the actions of the agent will give not only the immediate rewards but also the next state of the environment. The agent actually gets the immediate reward and the next state, and then agent needs to decide on further actions. Furthermore, the agent normally determines how it should take the future value into account; it's called model of long-run optimality.

The agent also has to learn from the delayed rewards; it sometimes takes a long sequence of actions to retrieve an irrelevant reward and, after some time, it reaches a state with a high reward. The agent should also learn which of its actions give it a high reward based on the past history. This will help decide future actions.

Let's take an example of a chess game. I played a long game of chess and it took 100 moves and at the end I lost the game. However, I actually lost the game on the 8th move; I made a mistake and reversed two moves because it was a new opening that I was just learning. From that point on, I played a beautiful game, but the truth is that the other player had an advantage that I never overcame. I lost the game, not because I played poorly but because I made one bad move and that move happened very early. This is the notion of a late reward. I played this long game of chess and maybe I played well and screwed up in the end.

Or maybe I played a mediocre game but I had a couple of brilliant moves and that's why I won. Or maybe I played very well in the beginning and poorly at the end. Or the other way round! The truth is that you don't really know; all you know is that you take a bunch of actions and you get the reward signal back from the environment such as I won the game or I lost the game. Then we have a problem: of all the actions I took, what was the action that led me to ultimately win or lose or get whatever reward I got?

In this particular case, we are in some state, take some action, and get some reward for the action we took. We get a sequence of state and action tuples and ultimately we have to figure out what action we took for the given state we were in. It helps to determine the ultimate sequence of rewards that we saw. This problem is called temporal credit assignment.

Now, we will look into the Grid World example, Reinforcement Learning. Think about how we learn to get from the start state to the goal (+1) or failure (-1) depending on the kind of reward we see.

In the Grid World example, the only change is in the rewards we receive for all states other then the goal (green) and failure (red) state. Let's say we give the reward for all the states as +2, and goal and failure have rewards of +1 and -1. Just to remind you of the rule, the game continues until we reach the goal or failure state:

R(s) = +2

As the reward is +2, which is very high, and the target is to get the maximum rewards, in this case we will never get to the goal or failure state because the game ends as soon as it has reached to these states and that's the end of our treasure gathering!

Figure 2: Grid World R(s)=+2

Refer to Figure 2; it displays what action the agent will choose when the reward is +2. Let's start with state (3,3); what action should we take here? We should never go right because it's ends the game and we want to continue getting rewards. We should take left (←) to that state. So, we never reach the goal state. Now, consider we are in the state (3,2). What action should be take here? We don't want to go to failure state because it ends the game and we don't want to go up because it has a chances that we take right from there. Instead we, should take left (←); in this case, we will be in the same state because we cannot go into the block state. In state (4,1), we should not go up because it will end up the game. We would prefer to go down (↓) and, as this is the boundary state, it means we would be in the same state as we were. All other states with + don't matter because there is no chance to end the game and we continue getting the rewards.

As seen in the previous example, because the reward is positive and we just accumulate the rewards, we always avoid the goal and failure states. It doesn't matter that they have a +1 or -1 reward.

Now take another example as shown in Figure 3, where we the reward is -2 for all the states except goal and failure where reward is +1 and -1:

R(s) = -2

Figure 3: Grid World R(s)=-2

Refer to Figure 3; it displays all the actions the agent can choose when the reward is -2. Now, our target should be to exit the game as early as possible, because traversing each state will give us a -2 reward. Let's start with state (3,3); we would definitely go to the right (→) to get +1and end the game. Now, let's think about (4,1). What action should we take? Should we go around and jump into the +1? That will take three steps of -2 reward each. It will become -6 and at the end we will get +1 reward, which makes it -5. The best we can do is go up (↑) and end the game. Now, consider the state (3,2); we will go right (→) to end the game. For state (3,1), we have both options to go right or to go up and end the game.

Here the reward is so strongly negative that we just need to end the game quickly. We try to take the shortest path to end the game no matter whether we finish at the goal or failure state.

Now, take one more example, where the reward is -0.04:

R(s) = -0.04

What will having this small negative reward encourage you to do? It's making us think about each step taken and a little bit of punishment. The best way to finish is to get to the goal state and get a +1 reward after the penalty of -0.04 for each step. That means a small negative reward everywhere encourages you to end the game.

Figure 4: Grid World R(s)=-0.04

From the start state, it actually goes towards goal state and it's the same policy we saw before. Here, the interesting state is (3,1) where we can go straight up to the goal instead of going the long way round. But by taking the long way, we are picking up little bit of negative rewards for a while (-0.24) though we avoid going to the state that gives -1.

After looking into different reward values R(s) = +2, R(s) = -2 and R(s) = -0.04, it seems that minor changes in the reward matter. When the reward function's value differs, we see that some of the decisions are actually different.

Another way to think about a reward that it has main knowledge as it keeps the history of good and bad moves, our agent will only act and take a decision based on the history of rewards. If we want to design the MDP to capture some world, then we have to think carefully about how we set the rewards in order to get the behavior that we wish. No matter what you do, you have to inject the domain knowledge somehow; otherwise, there is no learning to do and, in this case, the reward is basically telling you how important it is to get to the end.

Optimal policy

What is our criterion for finding a good policy? In the simplest case, we'll try to find the policy that maximizes, for each state, the expected reward for executing that policy in the state. This is a particularly easy problem because it completely decomposes into a set of decision problems--for each state, find the single action that maximizes the expected reward:

E [rt | π, st]

We've been assuming infinite horizons. When we think about the last Grid World as per Figure 4, the game doesn't end until we reach an observing state. We have two observing states: goal and failure. This implies that the we live forever and we have an infinite time horizon to work with. If we don't have an infinite horizon to work with, we might end up with something different. In the Grid World example where we have a reward of -0.04 and we find the optimal policy, imagine we were at (3,1) state. Rather than going up, it makes sense to go the long way round because we get some negative reward, but it's a small negative reward compared to the positive reward where we end up. This only makes sense if we will live long enough and we can afford to take the long route. What would happen if we have only three time steps left and then game would end no matter where we end up? Then it's clearly better to go ahead and quickly get to the +1, even though there is some chance to falling into -1, as opposed to trying to loiter on the long route where it's guaranteed that we will never reach +1.

Whether to take a risk or not depends on the reward and on whether we have infinite time to get to the observing state or not. If you don't have an infinite horizon but a finite horizon, then two things happen. One is that the policy might change because the GridWorld might have reached to an end because we are in a finite horizon.

Secondly and more importantly, the policy will change even though we were in the same state. Let say we are in the (3,1) state and we don't have infinite amount of time but we still have 100 million time steps. Then it still makes sense to take the longer route. But if I change this 100million to two, three or four, then the policy will change even though we are in the same state.

We discussed the notion of policy that maps states to actions. In terms of Markov properties, it doesn't matter where we were; it only matters where we are now and always takes the same action. However, this is only true in an infinite horizon case:

π(s) -> a

If we are in the finite horizon case and it's counting down every time we take a step, suddenly, depending upon the time stamps left, we might take a different action:

π(s, t) -> a

It is important to understand that without the infinite horizon assumption, we lose the notion of stationary in our policy.

We have implicitly discussed not only the reward we get in the single state but also the rewards we get through sequences of states that we take.

Let say we have two sequences of states and we put them in the utility functions U(S0 S1 S2 S3 .....) and U(S0 S'1 S'2 S'3 .....):

If U(S0 S1 S2 S3 .....) > U(S0 S'1 S'2 S'3 .....)

Since S0 is common in both the series, it also turns out as follows:

then U(S1 S2 S3 .....) > U(S'1 S'2 S'3 .....)

These are two different sequences and, in the beginning we were comparing them with S0 in front of both the sequences. It means that S0following by all the S and S0 following by all S primes, then we have the same preference when S0 is missing and it is called stationary of preferences. Another way to look at it is as follows: if we prefer one sequence of states today over another sequence of states, then we will prefer that sequence of states over the same sequence tomorrow.

If we believe that the utility of one sequence of states is greater than the utility of another sequence of states, both today and tomorrow, then it actually forces us to do some variation such as adding sequence of states or adding rewards of the sequence of states.

The utility that we receive by visiting the sequence of states is simply a sum of rewards that we receive for visiting those states:

U(S0 S1 S2 S3 .....) = ∑∞t=0 R(st)

Now, the previous equation has a problem that it goes to infinity, like in our earlier example when reward was +2 the game never end.

Now, consider the following two sequences of states and the reward we receive; in the first one, we receive a reward of +10, and in the second one, some instances of reward are +10 and some are +20. This goes on forever:

Figure 5: Sequence of states

Which is better? The answer is neither. Some people say that the bottom one is better because in the bottom we are getting +20 rewards in some occasions. What is the utility of the top one? 10+10+10+10+10+10 ........ = ∞. And what is the utility of the bottom one? 10+10+20+10+20+20 ........ = ∞.

The utility of both of them is ∞. Is one of them is bigger than the other? Neither is bigger then other, because both of them are equal to ∞. The reason they are equal to ∞ is that all we do is accumulate rewards and we are always getting positive rewards no matter what we do. This is the existential dilemma of immortality. If we live forever and we can always get to a better place, then it really doesn't matter what we do.

If we look at the bottom sequence of states, because we are getting more rewards occasionally, it seems like the right intuition to have. But it's just not built into this particular scheme. It turns out that there is very easy way we can build this into utility scheme by making one tiny change.

All I have done is replaced the equation on top with an alternate version of the equation. I multiply γ with the rewards of states; here γ is between 0 and 1. So, it's exponentially implodes:

U(S0 S1 S2 S3 .....) = ∑∞t=0 γt R(st)   0 < γ < 1  //Case 1

We will rewrite the previous equation and bound it with the largest reward we will ever see, in the following way:

U(S0 S1 S2 S3 .....) = ∑∞t=0 γt RMAX    0 < γ < 1   //Case 2

What does it look like? This is a geometric series and is exactly equal to:

Rmax / (1-γ)

In the previous equation, when γ is close to 1, we divide by something very tiny, which is like multiplying it by something really big. So, it's magnifying the reward, but it's not infinity until γ gets all the way up to 1, and that's the same case we were in before. That's the reason we wrote that γ is between 0 and 1, 0 inclusive but strictly less then 1. If we include 1 also then it is exactly like the first case because 1 to a power is always 1. So, this is actually a generalization of the sort of infinite sum of rewards. This is called discounted rewards, discounted series, or discounted sum, and it allows us to go to infinite distances in finite times. The difference between case 1 and case 2 is that, by doing the discount, we get to add the infinite sequence and still get something finite. The intuition here is that since γ is less then 1, eventually as we raise it to a power, it becomes 0. This is like having a finite horizon but that horizon is always the same finite distance away no matter where you are in time, which means its effectively infinite.

The discount factor gamma is a number between 0 and 1, which has to be strictly less than 1. Usually it’s some where near 0.9 or 0.99 .

This model has a very convenient property that the optimal policy is stationary. It's independent of how long the agent has run or will run in the future (since nobody knows that exactly). Once you’ve survived to live another day, in this model, the expected length of your life is the same as it was on the previous step, and so your behavior is the same as well.

More about Policy

After going through the utilities and discounted reward, we can now write down what the optimal policy is. The optimal policy is simply π*, the one that maximizes our long-term expected reward. We have an expected value of the sum of the discounted rewards at time t, given π:

π* = argmaxπ E [∑∞t=0 γt R(St) | π ]

These are the sequences of states we are going to see in a world where we follow π. And it's an expectation because things are non-deterministic. The policy that maximizes the value of that expression gives the highest expected reward.

We know what the optimal policy is, except that it's not very clear what to do with it. All we have really done is written down what we knew it was we were trying to solve. However, it turns out that we have defined the utility in such a way that it's going to help us to solve it. The utility of the particular state depends on the policy I am following and that's simply going to be the expected set of states that I am going to see from that point on given I am following the policy:

Uπ(s) = E [∑∞t=0 γt R(St) | π, s0=s ]

The difference in this equation compared with the previous one is that the utility of the policy out of state is what will happen if we start running from that state and we follow that policy. How good is it to be in some state? Well, it's exactly as good to be in that state as what we expect to see from that point on, given that we are following a specific policy where we started in that state.

Another important point is that the reward for entering a state is not the same thing as the utility for that state. Reward gives us immediate feedback, but utility gives us long-term feedback. The reward for a state is the actual value that we get for being in that state. Utility is both the reward we get for that state and all the rewards that we are going to get from that point on. Let's say I want to go to a college for a master's degree but it costs me $10,000. If I spend $10,000, at the end I get a degree. The point is that there is an immediate negative reward of $10,000. But at the end of the day, I get something positive out of it. It not just prevents you from taking short-term positive things if that is going to lead to long-term negative things, it also allows you to take short-term negative if it will lead to long-term positives. Utility is really about accounting for all delayed rewards. Given the following mathematical expression of delayed rewards, we will be able to start dealing with the credit assignment problem:

R(s) ≠ Uπ(s) = E [∑∞t=0 γt R(St) | π, s0=s ]

Summary

In this article, we learned the basics of the Markov Decision Process, states, actions, transitions, and rewards.