State Values and Policy Evaluation
An Introduction to Reinforcement Learning: Part 1
Getting Started
Once upon a time there was a Baby Robot who got lost in the mall. Using the strategies from Multi-Armed Bandits he was able to recharge, in the shortest time possible, and is now ready to start looking for his mum.
Unfortunately he can’t quite remember his way back to her, so will need our help to guide him. We’ll do this using Reinforcement Learning, to help him find his way and ensure that he gets back safely.
Introduction
In very simple terms, Reinforcement Learning can be thought of as learning from trial and error. An agent, that interacts with its environment, receives rewards that reflect its ability to accomplish some predefined goal. By evaluating how the agent’s actions impact on its performance, and then modifying those actions to improve performance, Reinforcement Learning can progressively move towards an agent that gives the maximum amount of reward and that solves the task at hand.
Reinforcement Learning can therefore be considered to consist of two distinct parts:
- The Prediction Problem, in which the performance of the agent is evaluated.
- The Control Problem, where the policy, used by the agent to select its actions, is modified to improve performance.
In this part we’ll mainly consider the prediction problem. Then, once we are able to measure how actions relate to the amount of reward received, we can turn our attention to improving the policy, to maximise those rewards.
The standard reinforcement learning book or syllabus will begin with a description of the full reinforcement learning system and the derivation of the equations used to describe that system. Only then, once they have all the theory in place, will they show how that theory can be applied to practical applications.
In this article we’ll take the opposite approach. We’ll start with very simple methods of practically solving very simple problems and gradually build on these, adding the bits of theory as required, until we’re able to solve the full reinforcement learning problem.
So we’ll end up in the same place as a traditional course, but by using a top-down approach, rather than the standard bottom-up method. We want to get Baby Robot back to his mum as quickly as possible, so don’t have time to learn all the theory up-front, instead we’ll add it as we go!
Contents
In this post we’ll cover the following Reinforcement Learning topics:
- The terminology of Reinforcement Learning (RL)
- Basic RL mathematics
- Policy Evaluation
- Iterative Policy Evaluation
- Policy Improvement
- Discounted Rewards
A Jupyter Notebook version of this article can be found on github. This contains all of the code used to create the grid levels and RL algorithms described in this article.
The Terminology of Reinforcement Learning (RL)
Consider this level where Baby Robot initially finds himself:
On entering the level he has two possible choices: he can either go North or South. Which of these will get him to the exit the quickest?
Rewards
The fundamental concept in Reinforcement Learning (RL) is the concept of a reward: a single numerical value that is used to measure how well the task at hand has been performed. It is the reward that drives learning, allowing a problem solving strategy to be optimised to give the maximum reward.
In problems such as this one, in which Baby Robot must find his way out of a level, a reward could be given simply for reaching the exit, however that doesn’t fully describe what we want to achieve. We actually want to get to the exit as quickly as possible. Giving a reward just for reaching the exit doesn’t encourage this behaviour. Baby Robot could spend days walking around the level before finding the exit and would receive exactly the same amount of reward as he would for proceeding there directly.
Therefore a better reward system would be one that encourages taking the shortest route and that discourages wandering around aimlessly. Effectively we want to express the reward as a penalty, that increases with the number of steps taken to reach the exit.
However, we also still want to stick with RL’s central idea of maximising rewards and so we introduce the idea of negative rewards. For each step taken we give a reward of -1. In this way, a route that takes a long time to find the exit will accumulate a large negative reward and one that goes there directly will have a small negative reward. In terms of getting the most reward, the direct route will be better since it will be less negative.
States
With our reward system, each time Baby Robot moves from one square to the next he will be given a reward of -1. In RL terminology, each of these squares represents a state, where a state is defined to be a unique, self-contained, stage in the environment that we’re working in.
So, in this case, each state describes a position within the grid that forms the level. In a game, such as chess, the state would describe the current board position. In the case of a self-driving car the state could describe properties such as the position on the road, the direction and speed of the car and details of other traffic. In each case the state defines the current situation.
The state is self-contained in the respect that it is independent of any previous states. For example, in chess, the state given by the current board position is independent of all other moves that have been made up to that point. To choose the next move you don’t need to know which moves were made in the past. Similarly, for Baby Robot to move from one square to the next in the grid, he doesn’t need to know which states he was previously in. When a state is independent of the prior states it is said to satisfy the Markov Property.
Value
Since we know that a penalty (reward) of -1 is incurred each time Baby Robot moves from one state to the next, and we also have the luxury of being able to see the map of the level, we can help Baby Robot to make his choice by calculating the value of each state, where the value defines how good it is to be in a particular state.
Obviously, for this grid level, it’s better to be in a state that’s close to the exit than it is to be in one that’s far away. In RL the value of a state is defined to be the expected reward that can be obtained when starting in that state and then proceeding to choose actions that are defined by a plan, or policy, in all future states.
Let’s add this information to the level. Beginning at the exit (which in RL is referred to as the Terminal State, where the episode ends and which, by definition, is given a reward value of zero), and working our way around the level, incurring a penalty of -1 each time we move to a new square, gives the following values for each state:
There are a few points to note here:
-
The value of any state is equal to the expected amount of reward that can be accumulated when starting in that state. In RL language the expected total amount of reward is referred to as the return. So, given Baby Robot’s starting position, if he is given a reward of -1 each time he moves from one state to the next, he can expect a return of -4 if he follows the shortest path to the exit.
- Additionally, the value of a state is given by the sum of taking an action in that state and the value of the next state. For example, moving South from the initial state gives a reward of -1 for taking the action and the new state has a value of -3, therefore the value of the initial state equals -4.
-
By looking ahead one state we can choose to move in the direction that would take us to a state with a less negative value. So, from the initial position, we’d choose to go South to a state with a value of -3, rather than going North to one with a value of -5. The strategy used to select the next action is known as the policy. In this case if we choose to move in the direction of increasing value we are actually following the best or optimal policy and, as we saw for Multi-Armed Bandits, when we choose to take the action that gives us the highest amount of immediate reward we are said to be choosing greedily. In this case a greedy policy results in an optimal policy.
We can show the policy on our level diagram, where the arrows now point in the direction of the action that should be taken in each state. Note how for this greedy policy the arrows always point in the direction that will give the maximum reward from the current state.
So, from Baby Robot’s starting position, if he follows this optimal policy he will arrive at the exit with an accumulated total reward of -4.
Since we give a fixed reward when moving from one state to the next, under this optimal policy the expected return, and therefore the value of each state, is simply the number of steps to the exit, multiplied by the reward of -1 that is given for each step.
Basic Mathematics
In the description of the initial level, where Baby Robot finds himself, we’ve already covered most of the basic concepts of Reinforcement Learning. We can now add the simple mathematical terms that go with these concepts and then build on these as we go along.
Firstly we’ve said that Baby Robot receives a reward when he takes an action in a state. Unsurprisingly we use the first letter of each of these terms to refer to its corresponding value, with lower-case being used to refer to specific values for each of these quantities, which gives us:
- r = reward
- a = action
- s = state
Additionally, when Baby Robot takes an action he’ll most likely move from his current state to another state. The next or successor state is denoted by s′ (read as "s prime"):
- s′ = next state
The rewards, states and actions are actually random variables: there’s a probability of getting a certain reward, taking a specific action or being in a certain state and these probabilities are referred to using capital letters.
Tying all these terms together gives us the expected reward for a state-action pair:
So, at time ‘t -1‘, starting in a particular state ‘s‘ and taking action ‘a‘, the expected reward that’s received at the next time step is a function of the current state and action. The reason it’s an expected reward is because the amount of reward that’s received, when repeatedly taking a particular action in a particular state, may not always return a constant value and so this effectively defines the mean value that will be obtained.
Using these terms we can create equations for the basic properties we’ve defined:
_Return ‘Gₜ’: the total amount of reward accumulated over an episode, starting at time ‘t’._In our case an episode refers to all the time steps that occur between entering and exiting a level. (Things obviously get a bit more complicated in long-running or continuous tasks, but we’ll come back to that later).
So, starting at time ‘t‘, the return is just the sum of the future rewards.
Value: the value of a state is just a measure of how good it is to be in that state. This can be expressed in terms of the amount of future reward or, in other words, the return that you’re likely to receive if you start in that state. Obviously, no matter which state you start in, the rewards you’ll receive will depend on the actions you choose and these actions are determined by the Policy, which is commonly denoted by the symbol ‘π‘.
So the value for state ‘s‘ under policy π is simply the expected return:
Since, in our simple case, we always get the same reward of -1 for taking an action, the value of a state is simply the immediate reward plus the value of the next state:
For example, the value of the start state of the level is -4. If the optimal policy is followed from this state Baby Robot will have accumulated a total reward of -4 by the time he reaches the exit. Similarly, if he chooses to take a single step South from the initial state, he’ll receive a reward of -1 for taking the action and the value of the next state is -3, so again this gives the value of the initial state as -4.
Note how the calculation of the state value is split into two parts; the immediate reward received for taking the action and the value of the state where that action takes you. This technique, of splitting a problem into sub-problems, is known as Dynamic Programming. Using this, state values that have already been calculated can be reused to calculate the values of other states whose actions lead there.
This greatly simplifies the problem, since you don’t need to work out the reward that will be given at every state when calculating the total return obtained between a starting state and the end of the episode. Instead you only need to look ahead one step.
Policy Evaluation
Baby Robot’s mum told him to never trust strangers, so he’s a bit nervous about following our policy. What happens if we’re lying to him and it’s not the optimal policy?
So, rather than using our policy, he instead decides to toss a coin and use that to decide which way to go. Every time he enters a new state he’ll flip the coin. If it’s heads he’ll go forwards, tails he’ll go backwards. Therefore each of these actions now has a 50% chance of being selected.
What happens to the value of each state under this new policy and how do we go about calculating it?
- Firstly, the value of a state will still be a measure of how good it is to be in that state. However, since Baby Robot is no longer heading straight for the exit, the total reward he’s going to accumulate will decrease. In other words, because he’s likely to be visiting more states, or the same states several times, and the reward given for moving from one state to the next is still -1, the total reward is going to become more negative.
- Additionally, the value of a state still represents the expected return from that state. However, because Baby Robot is now following a random policy (referred to as a Stochastic Policy in RL), based on the toss of a coin, the number of steps from any state to the exit may vary. Therefore the value of a state now represents the average, or expected, reward that can be achieved when starting in that state.
- Since a state’s value is the expected return obtainable from that state, its value may be used to help calculate the value of the previous state. This avoids needing to know all the rewards that will be accumulated during the episode.
- Consequently, the value of any action is simply the reward given for taking this action plus the value of the next state where you end up. The contribution of this action towards the current state’s value is then obtained by multiplying the value of the action by the probability of taking this action.
This can all be summarised by the following equation:
As with equation 4, for a deterministic policy, the value of any action is given by the reward ‘r‘ obtained for taking that action ‘a‘, plus the value of the next state ‘ s′ ‘ where that action leads to. However, since under a stochastic policy there can be more than one action, the action’s reward is multiplied by the probability of taking the action: π(a|s) represents the probability of taking action ‘a’ from state ‘s’ under policy ‘π’.
These values are then summed, over all the actions for the state, which gives the expected reward value for state ‘s‘. Effectively, the combination of the sum and the probability of taking an action gives the average value of the rewards returned from the actions.
Under Baby Robot’s new policy each of the 2 actions (forwards or backwards) are taken with a probability of 0.5 and the reward for taking any action is still -1. Therefore the value of any state will be:
Where sᶠ is the state moved to when choosing the forwards action and sᵇ is the next state when taking the backwards action.
Iterative Policy Evaluation
For this simple level, calculating the optimal policy was easy. We simply started at the exit and worked our way backwards, adding another -1 reward every time we moved to the next state. But how do we go about calculating the state value when the chance of moving to the next state is random? (In the language of RL the chance of moving to the next state is referred to as State Transition Probability).
We can do this by taking a similar approach to the calculation of the optimal policy values, except now, rather than being able to find the value of each state in a single sweep through all of the states, we’ll need to do multiple sweeps. Each of these will give us a slightly better estimate of a state’s true value.
Initially, since we don’t know the value of any of the states, let’s assume that none of them return a reward, so we’ll set all initial values to zero. By definition the reward of the exit, the terminal state, is also zero since this is where the episode ends.
To start the iterative process we can begin in any state but, for simplicity, let’s begin at Baby Robot’s current location, the entrance to the level.
Baby Robot tosses his coin. Heads he goes north, tails he goes south. So the probability of each action is 0.5, the reward for either action is -1 and value of the next state is currently 0 for both actions. Therefore, using equation 6 above, the current value of the current state is:
To keep things simple we’ll take the initial value of each state at the beginning of the sweep, rather than its updated value, to avoid the condition where some states have been updated and some haven’t (although doing this is a perfectly reasonable thing to do and can often lead to a faster convergence of the state values; using the updated values is referred to as ‘in-place‘ updating).
Therefore, keeping the value of each next state at zero for this sweep, we can repeat the above procedure for the remaining states. This results in a value of -1 for all states at the end of the first pass.
At the end of the first pass, the value of each state looks like this:
Once the value of each state has been calculated, the process can be repeated, using the newly calculated state values to calculate the state values of the next iteration. The progress in calculating the state values, over the first 10 iterations, is shown below (ignore the blue arrows for now, we’ll come to those shortly).
If this process is repeated for long enough the state values eventually stop increasing and are said to have reached convergence. In theory convergence is truly only reached "in the limit" or, in other words, when the number of time-steps is equal to infinity. Obviously this is rather impractical and so we instead define convergence to have occurred when the maximum difference between a state value at one iteration and the next is less than some threshold value. In our experiments we use a threshold of 1e-3 (=0.001) and, with this, it takes 206 iterations for the state values to converge for this policy.
Now it can be seen that, under this policy of choosing the next state by tossing a coin, the values of each state are a lot more negative than under the optimal policy of going straight to the exit. The values do however still represent the expected number of steps from any state to the exit, except now Baby Robot is following a random trajectory that will lead to many more states being visited. This is shown below, for one of his shorter trips from the start to the exit of the level:
Iterative Policy Evaluation Code
The code used to evaluate the policy is shown below. This repeatedly calculates the state values for every state until convergence is reached.
(This snippet of code has been taken from the full notebook for this article, which can be found on github)
This code consists of three main parts that implement the Iterative Policy Evaluation routine:
-
Get the value of a single state (the _get_statevalue function) This implements equation 6, and just calculates the value of a state by adding the immediate reward, received for taking an action, to the value of the state where we end up. In equation 6 we averaged over the actions by multiplying the value obtained for each action by 0.5, since for this level we only ever have 2 possible actions. In the code this is made a bit more general, by instead multiplying by one over the number of possible actions.
-
Do a single sweep to calculate the value of all states (the _standardsweep function) This iterates over all states and calculates the value of each.
-
_Perform multiple state sweeps until convergenceI_nitially the value of each state is set to zero. Then, at each iteration, the new value of all states is calculated using the current values. This continues until the maximum change in the state values falls below the predefined threshold.
Policy Improvement
Unsurprisingly, deciding which move to make based on the toss of a coin isn’t a very good strategy. As shown above, under this policy it takes much longer to reach the exit. Additionally, the value of each state is much lower than under the optimal policy. However, although the state values are much worse, in terms of the reward that can be obtained, they do still give one important bit of information: the relative goodness of each state.
Looking back at the final, converged, state values, it can be seen that the expected reward that can be obtained from the starting square is -32. So, on average it will take 32 moves to reach the exit from this point. Similarly, for the square immediately to the North of the start position, the expected reward is -35 and to the South it’s -27. Therefore its easy to see that, to get to the exit in the shortest number of steps, its better to head South from the starting square.
By repeating this one-step look ahead, and acting greedily with respect to the value of the next state, we can modify the stochastic coin toss policy to create a policy that moves in the direction of the greatest reward. In this manner we can improve the policy, to produce one that gives increased rewards.
Indeed, after a single iteration of policy evaluation on this level, acting greedily with respect to the state values gives us the optimal policy. This is shown by the blue arrows, which can be seen to point in the direction of greatest reward and lead directly from the entrance to the exit of the level.
One other interesting observation, when acting greedily with respect to the calculated state values, is that it may not be necessary to wait for the values to converge before the policy can be improved. Look again at the first few iterations for this level (conveniently copied here to avoid you having to scroll!):
Although, during policy evaluation, it takes 206 iterations for the state values to fully converge, it can be seen that by the 5th iteration greedy selection has already found the optimal policy. Indeed, for the start square, which is all we’re really interested in, the optimal policy has been found by the 4th iteration. All future iterations are therefore redundant in terms of improving the policy. We’ll make use of this observation as we look at more efficient ways of finding the best policy.
Discounted Rewards
So far we’ve evaluated the state values for the optimal policy, which we were able to easily determine for this very simple level, and for a stochastic policy, where all actions were selected with a random probability. In both cases a series of actions existed that would ultimately lead from the start of the level to the exit. But what would happen if this wasn’t the case and if none of the policy’s actions ever lead to the terminal state?
For example, consider the deterministic policy shown below:
In this policy an action is defined for every state, to specify the direction that should be moved from that state. The important point to note about this policy is that none of the actions ever lead to the exit and, as a result, the episode will never terminate. Obviously this will cause problems when evaluating the policy.
The state value represents the total reward that can be obtained from a state. As we’ve seen, this is calculated as the sum of all the rewards that will be obtained, starting in the state and then following the policy thereafter. Since our initial policy never reaches the terminal state, at each iteration of policy evaluation, this sum will just continue to grow.
To prevent this from happening we introduce the idea of discounted rewards. Now, rather than the return simply being the sum of all the rewards that are accumulated from a state until the end of an episode, we progressively reduce the contribution of rewards. The further a reward is into the future, the less weight it will be given when calculating the state’s return value.
The formula for calculating the return now becomes:
In this new discounted formula for the return value, ‘γ‘ (gamma) is the discount factor, where 0 ≤ γ ≤ 1. So the reward from each time step is multiplied by an increasing power of ‘γ‘. When the value of the discount factor is less than one, this will act to progressively reduce the value of rewards from future time steps, until eventually their contribution to the overall return is effectively zero.
For example, a value of 0.9 is commonly used as the discount factor. With this we can calculate the return value of the initial state, as follows:
Clearly, applying a discount factor progressively decreases the future return values and it doesn’t take long before they’re down close to zero.
However, as we’ve seen, it would be impractical to calculate a state’s value by considering the reward from all future states. Instead we use Dynamic Programming to simplify the problem into one that just uses the immediate reward and value of the next state. The value of the next state represents the return that will be obtained from the next state and therefore we can just change equation 7 to apply the discount factor to the next state’s value:
In other words: the value of a state, when following policy ‘π’, is equal to the sum, over all actions from that state, of the probability of taking each action, times the immediate reward for that action plus the discounted value of the next state where we end up after taking the action.
Using the discounted state value function, with the discount factor set to 0.9, we can now calculate the value of our deterministic policy:
With discounted rewards, the value of each state, rather than continually decreasing, now converges to our threshold in 67 iterations. In this case, all of the states (other than the exit) has a value of -10. The reason that no state is better than an other is because, under this policy, its never possible to reach the terminal state and therefore all states are equally bad. In a future part we’ll look at how we can use these state values to improve the policy, to give one that does allow Baby Robot to escape from this level.
One important point to note about the new, discounted, state values is the following:
- The state values no longer represent the expected number of steps to the exit. Instead they now show the expected discounted future reward from each state under this policy.
Summary
After all the running through mazes Baby Robot is pretty tired (as I’m sure you are too!), so we’ll take a break here. We’ve managed to successfully get Baby Robot through the very simple initial level. In the process we covered nearly all of the main foundations of Reinforcement Learning:
- Reinforcement Learning uses the concept of rewards to drive learning. For the states that make up the problem environment, a value can be calculated from the rewards to represent how good it is to be in each state. Then, by choosing the actions that maximise the rewards, it’s possible to find the optimal policy that can be applied to solve the problem at hand.
- The value for each state represents the return that can be obtained if you start in that state and then follow the current policy until the end of the episode. Discounted rewards make it possible to focus the state values on rewards that would be obtained in the close future. Additionally they can prevent problems that may otherwise occur if the episode is not guaranteed to terminate.
- The calculation of state values can be greatly simplified by using Dynamic Programming. Rather than having to know all future rewards from a particular state, the problem is split into the immediate reward and the value of the next state.
- Using Dynamic Programming, we were able to perform Policy Evaluation, in which we calculated the value of all states under the current policy.
- Once Policy Evaluation was complete the state values could then be used to improve the policy by selecting greedily with respect to these values.
What’s Next?
Although we’ve covered a lot of ground, we’re still missing a few of the core concepts of Reinforcement Learning. In particular, Markov Decision Processes and Bellman Equations. In simple terms these are, respectively, the mathematical framework used to model Reinforcement Learning problems and the set of equations used to calculate the values of states and actions. As you’ve seen, we’ve already used some equations to calculate the state and action values. These are actually partial forms of the full Bellman Equations. We’ll fully describe both of these topics in the next post.
Additionally, we’ve only really looked at the Prediction Problem, in which we evaluate the value function for a given policy. While we were able to act greedily with respect to these calculated values, and thereby help Baby Robot find his way through the simple grid level, we need to expand on this for more complicated problems. We therefore need to examine the Control Problem, in which we find the optimal policy based on the policy evaluation.
Furthermore, Baby Robot has not yet had to actually explore any of the levels where he’s found himself. All of the information about the level, such as the rewards and state transition probabilities, was already given and this was used to derive the optimal policy for each level. When all the information is given up front it’s known as a model-based system. A more realistic scenario is when these values aren’t available and some exploration is required to solve the problem. Unsurprisingly, problems of this nature are called model-free problems and we’ll take a look into these in future posts.
Footnotes:
Top-Down Learning: This approach to learning is probably most famously used (at least in the machine-learning world) by Jeremy Howard in his excellent Fast.ai courses. In academic studies it’s been shown to help give a better understanding of the overall concepts involved in a subject.
References
For a full theoretical breakdown of everything covered in this article, check out the bible of Reinforcement Learning: "Reinforcement Learning: An Introduction", Sutton & Barto (2018)
For the Baby Robot’s Guide to Multi-Armed Bandits, start here:
Share This Article
Towards Data Science is a community publication. Submit your insights to reach our global audience and earn through the TDS Author Payment Program.
Write for TDS
