Off-Policy Reinforcement Learning via Importance Sampling

On-policy learning: an overly cautious policy

In my previous article, I showed how an agent can learn to play Tic Tac Toe using On-Policy Monte Carlo methods. In order to guarantee an exploration of the state-action pairs, the agent could either explore different starting pairs (which is an unrealistic assumption most of the time) or it could use an ε-greedy policy.

One important issue with the second approach is that the policy used to explore the environment is the same policy being optimized through Policy Improvement. Thus, the action-values learned are affected by the exploration component. As a consequence, we can only guarantee that the agent will learn the best policy among all ε-soft policies possible, and not among all policies.

In the Tic Tac Toe case, this fact didn’t impact much the final policy learned by the agent, but depending on the environment, the agent may learn a policy that is very different from the optimal. This case is well illustrated with the Mini-grid environment from the Farama Foundation, as shown below:

Customized Mini-grid environment

In this environment, the agent starts in the bottom of the grid and has to reach the goal (green cell) as quickly as possible without falling into the lava cells (in orange). The maximum number of moves is 100, after which the episode truncates. The available actions are to go UP, DOWN, LEFT or RIGHT. If the agent reaches the goal, it gets a reward of +100 and the episode terminates. If it falls into the lava, it gets a reward of -500 and the episode terminates. Any other state transition gets a reward of -1. Finally, if the agent tries to move past the wall, it will stay in the same cell.

It is easy to conclude that the optimal policy is to go UP all the way to the goal in 9 moves, in which case the agent gets -8 of reward from going up 8 cells and +100 from reaching the goal in the last move, totaling +92.

Let’s now see how an agent performs using On-Policy Monte Carlo with an ε-greedy policy, where ε = 0.3 and the number of episodes trained is 10,000 for this experiment.

The chart above shows the return of the agent if it uses a greedy policy with respect to the current action-values being learned. We can see that, at the beginning, the agent gets a return of less than -500, meaning that it falls into the lava. After a few episodes, it learns to avoid the lava cells, but it still gets a return of -100, meaning that it is walking aimlessly around the grid, reaching the maximum number of moves allowed. Finally, after around 3,000 episodes trained, the agent reaches a positive return of +78, meaning that it is taking 23 moves to reach the goal.

The chart above corroborates what we observed in the previous one. The agent starts by taking less than 10 moves and falling into the lava. After learning to avoid it, it uses the maximum number of 100 moves. Finally, it learns how to reach the goal in 23 moves.

After 10,000 episodes, the agent was able to update 78% of the state-action pairs available. Below we can see the path taken by the agent by following a greedy policy with respect to the final action values learned:

Greedy policy wrt. the final action values learned on-policy

Interestingly, the agent is very cautious and avoids the lava cells by going all the way to the right. That’s because, when the agent was close to the lava cells during training, there was a 30% probability that it would explore and eventually fall into the lava, which is reflected in the action values of those states. Therefore, this policy is the best policy among all the soft policies for ε=0.3, but it is clearly not the optimal policy.

But how can we learn the optimal policy instead of the optimal soft policy ?

In this article, I’ll talk about 2 approaches:

1. Keep using On-Policy Monte Carlo, but reducing the exploration factor ε over time.
2. Use Off-Policy Monte Carlo methods.

Decaying ε: from soft to greedy

An alternative to avoid the exploration factor being reflected into the action values is to reduce the value of ε over time.

The largest the exploration factor ε, the higher the chance that the agent will fall into the lava cells when it is close to it during training. As a consequence, the more cautious is the agent. Hence, the idea is to reduce the exploration factor so that the action values are adjusted over time to be less cautious.

After training an agent for 10,000 episodes and decaying ε linearly from 0.5 to 0, we get the following results:

We can see that the final result was the same as before, with the agent getting a return of +78 in 23 moves. The only difference was that it reached this final result in less episodes, probably because it had a higher exploration factor at the beginning. However, the agent visited 79% of state-action pairs instead of 78%, representing just a minor increase.

The results above illustrate how hard it is to use ε-decaying techniques to reach an optimal policy. This is because it is very hard to find the right balance for the speed of decay of ε. If we reduce it too quickly, the agent will not explore enough of the environment to be able to adjust the action values to the new ε. If we reduce it too slowly, we may need a lot of training episodes to reach the optimal solution, making this technique inefficient.

In order to overcome that problem, we can learn the optimal policy by using a new technique: Off-Policy Learning.

Off-policy learning: decoupling behavior and target

At the beginning of this article, we illustrated one of the main dilemmas of Reinforcement Learning: learning action values for the optimal policy assumes subsequent optimal behavior from the agent, but in order to find the optimal actions, the agent needs to behave sub-optimally by exploring.

One solution to this dilemma is to have 2 policies instead of 1. The first one, called the behavior policy b, can be used to generate behavior and explore the environment and the second one, called target policy π, is the one being learned. Thus, on-policy methods are simply a special case of off-policy methods when the behavior and target policies are the same.

This decoupling of policies have another immediate powerful advantage: we can learn the action values of a policy by using only observed data from other agents with other policies. This is very useful when we are not in control of the agent, but still have access to the data about its interaction with the environment.

As seen in my previous article, the main idea of Monte Carlo methods is to sample multiple trajectory returns from the agent in order to compute an estimate of the action-values, which are the expected value of the distribution of returns by following some policy. Since this sample of returns was obtained by following a behavior policy, the sample distribution reflects the return probabilities under the behavior policy. The idea here is then to convert the distribution with respect to the behavior policy to the distribution with respect to the target policy - which is now different from the behavior policy - by adjusting the return probabilities. This approach is called Importance Sampling.

The probability of a trajectory starting at time t under a policy π is given by:

where S is the state, A is the action, T is the terminal step and p is the transition probability from a state to the next given an action.

Then, all we have to do is multiply the return obtained in a trajectory by the ratio of the probability of that trajectory under the target policy π to the probability of that trajectory under the behavior policy b. This ratio is called the importance-sampling ratio.

This distribution adjustment comes with a condition: every action taken under π must, at least occasionally, also be taken under b. Mathematically speaking, this means that π(a|s) > 0 implies b(a|s) > 0 (otherwise, we would have a division by zero in the ratio). This is known as the assumption of coverage.

By using the behavior policy to generate exploratory trajectories and then adjusting the trajectory probabilities to the target policy, we can use the same Monte Carlo techniques to compute an estimate of the action values using the adjusted distribution of returns. The estimate of the action values then becomes:

where G is the return and Γ(s) represents the set of all time steps where state s is visited.

This calculation is called Ordinary Importance Sampling. The complete Off-Policy Monte Carlo algorithm is shown below:

Are we now able to learn the optimal policy using Monte Carlo with Ordinary Importance Sampling ?

After training an agent for the same 10,000 episodes, we get the following returns:

Surprisingly, the agent was not even able to match the policy obtained by the previous agents. We can notice below that, after 10,000 episodes, the agent learns that it needs to go UP, but it still behaves randomly and it turns right when it is almost reaching the goal.

Greedy policy wrt. the final action values learned off-policy with Ordinary Importance Sampling

We can see that the learning is very irregular, with a lot of spikes. This behavior can be explained by the way the algorithm works. If we go back to it, we can notice that, after updating the action values and the target policy, the algorithm checks if the greedy action under the updated policy is still the same as before. If it is not, the algorithm stops and generates a new episode. This happens because, if the greedy action changes, the probability of the current trajectory under the new target policy becomes zero.

This is a well known issue with Monte Carlo Importance Sampling methods. In order for the coverage assumption to hold, the agent is only able to learn from the tail of the episodes when the policy is changing a lot, especially at the beginning of training.

We can see above that, for almost all of the 10,000 training episodes, the agent only learned from the last state-action pair of the episode. Also, the agent only updated around 65% of the state-action pairs, compared to almost 80% before. This makes this method extremely slow and inefficient, and explains why we got poor results.

You may be asking if there is any value in using off-policy learning, since it is probably as inefficient as decaying the ε. Fortunately, it turns out there are some ways of correcting this undesired behavior.

Discount-Aware Importance Sampling: learning from entire episode

One way of enforcing that the agent learn from the entire episode and not only from the tail is by using a variant of importance sampling called Discount-Aware Importance Sampling. In this method, we take into account the return’s internal structures as sums of discounted rewards.

Let’s first consider the extreme case where the discount factor is γ = 0. This means that we only care about the immediate reward of the agent. If we use the traditional importance sampling, we will adjust the return by the probability of the entire trajectory, when clearly all that matters is the first transition.

Extending this idea to the general case of any discounting factor, we can think of discounting as determining the probability of termination. We can then think of the return Gt as the sum of flat partial returns Gt:h weighted by their probabilities of termination as a function of γ. The flat partial return is given by:

The return can be written as follows:

The probability of termination after 1 step would then be (1-γ), (1-γ)*γ after 2 steps, and so on, until the probability of terminating in the last step, which would be γ to the power of T-t-1.

With that in mind, we can now adjust the trajectory probabilities of each individual flat partial return separately. This approach has 2 benefits:

1. It allows the agent to learn from transitions far from the tail of the episode, even if the target policy changes for the tail of the episode.
2. It reduces the variance of the estimate, since we have now a weighted sum of trajectory probabilities of different lengths, with smaller trajectories having smaller variance than bigger ones.

Let’s now check the performance of the agent. The discount factor used here was γ = 0.99 and ε = 0.3.

As expected, the agent performed way more updates per episode than before, due to the fact that it is now learning from transitions far from the tail. It also covered way more state-action pairs. 90% of them were updated, instead of less than 80% for the previous agents. Notice that the number of updates per episode is bounded by the number of steps the agent needed to complete the episode.

Below we can see the performance of the agent in term of returns and episode length:

We can see now less spikes in the curve, but still a couple of them. The agent was able to learn better action values that obtained +86 of return with the greedy policy, but at the end of training the performance reduced a little bit and matched the on-policy return of +78.

If we observe the trajectory of the agent using the final action values, we can notice that it is not avoiding the lava anymore. Nevertheless, it takes a right turn in the middle of the lava zone, for no apparent reason.

Greedy policy wrt. the final action values learned off-policy with Discount-Aware OIS

This can be explained by the high variance of the updates. For the on-policy case, we can notice that, once the agent learned to reach the goal in 23 steps, this performance remained constant and the action values didn’t change that much. Here, on the other hand, the agent learned to reach the goal in 15 steps, but there were some large spikes that reduced the performance temporarily to 100 steps and 23 steps.

This high variance is due to the vanishing effect of multiplying transition probabilities for longer trajectories, making the probability of the trajectory very small. Since this probability is in the denominator of the importance sampling ratio, sometimes we may have very large updates of action values that can disturb learning. In the traditional importance sampling we didn’t have this problem because only the last transition of the episode was being considered in the updates.

Below we can see how the value of the pair given by the starting cell and the action UP varied along the first 2,500 training episodes:

After 300 episodes, we observe a large spike in the value, which is then corrected down in later episodes. This large update, as explained before, is probably due to a very small trajectory probability in the denominator of the importance sampling ratio.

In the next section, we will see one way to reduce this variance.

Weighted Importance Sampling: reducing the variance

In the previous section, we’ve seen how the importance sampling ratio can affect the amplitude of the value updates due to the vanishing effect of multiplying probabilities. For example, in the first update of a state-action pair initialized with 0, if a trajectory is 10 times more likely to happen for the target policy, the first value will be 10 times the obtained return of the trajectory. In expectation, those updates are not biased, but they have a high variance.

In order to correct that, we can change the importance sampling estimate from ordinary average to weighted average, that is, instead of dividing the adjusted returns by the number of updates done so far, we can divide it by the sum of all the importance sampling ratios so far. This approach is called Weighted Importance Sampling and the mathematical formulation is defined below:

Going back to our previous example of doing the first update of a state-action pair initialized with zero, in this case the first value would be the same as the first return obtained, because the ratio in the numerator would cancel out with the ratio in the denominator. This estimate is now biased, because the probability ratios got cancelled out, but the variance is now lower. In fact, with Weighted Importance Sampling, the action values are bounded by the lowest and highest return obtained, which reduces the variance significantly.

As usual, let’s check the performance of the agent with this approach.

As expected, we can see that the action value of the initial state-action pair is now well-behaved, without the large spike seen with Ordinary Importance Sampling.

The returns and episode lengths are given below:

The agent learned a target policy that obtained +88 of return after only 600 episodes and the performance didn’t have spikes as before. After around 1,600 episodes, the agent learned an even better policy, obtaining +92 of return, which turns out to be the optimal return with 9 steps.

Indeed, we can observe the agent’s trajectory using this final policy below:

Greedy policy wrt. the final action values learned off-policy with Discount-Aware WIS

By moving from on-policy to off-policy learning, then considering the discount-aware estimate and finally reducing the variance with weighted importance sampling, the agent was able to learn the optimal policy!

There is only one last detail, however: if γ = 1, this technique is reduced to the traditional inefficient importance sampling.

What if we don’t want to use a discount factor ?

Per-Decision Importance Sampling: in the absence of discounting

We’ve seen in the previous sections how to break down the return Gt into a sum of partial flat returns weighted by the “termination probabilities”. Similarly, we can break down the return Gt in another way if we notice that it is simply the sum of individual discounted rewards:

When we apply the importance sampling ratio to the return, we are actually applying it to each individual reward obtained in the trajectory.

The catch here is to notice that the expected value of each adjusted reward doesn’t depend on the whole trajectory, but only in the transitions until the one responsible for that reward:

With that, we can define a new adjusted return:

The action value estimator is now modified to be:

This estimator uses ordinary importance sampling and, so far, there is no per-decision weighted importance sampling estimator that is able to converge.

We can notice now that, even if γ = 1, we can still learn from the entire episode, which makes this method more general than the previous one.

If we train an agent with this method, we get the following results:

The first thing we notice is that the spikes in the learning are back. This is because we are back to ordinary importance sampling, which increases the variance of the updates. This increase, in turn, is probably affecting the final performance of the agent, which is now +88 return and 13 steps.

The agent is very close to the optimal performance. It doesn’t deviate from the lava zone all the way to the right wall, but it still makes a suboptimal right turn inside the lava zone, as seen below:

Greedy policy wrt. the final action values learned off-policy with Per-Decision OIS

Very likely, if we trained the agent for a few more episodes, this behavior would be corrected.

If we observe the value of the initial state-action pair, we can see that the spikes are back, as expected. This time, the spike was after 2,000 episodes, and not as high as before.

Finally, as expected, we also have a lot of updates per episode, since the agent is able to learn from the entire trajectory:

In my last article and in this one, I showed how an agent is able to learn the optimal policy by using Monte Carlo techniques, both on-policy and off-policy. For simple environments such as the Tic Tac Toe and the Mini-grid ones, the agent was able to achieve the optimal performance without too much work. However, in order to start updating the action values, the agent has to wait until the entire episode is done.

Moreover, as we’ve seen in the article about Dynamic Programming, the action values for an MDP follow a recursive structure that is explored in the Policy Iteration and Value Iteration algorithms with bootstrapping. In the case of Monte Carlo, even if we know that the value of a state depends on the value of the states that are reachable in one time step, this fact is not taken into account in the updates and each Monte Carlo update is independent of each other. If we choose more complex environments, this approach starts to be very inefficient and learning becomes too slow.

In my next article, I show how to introduce the bootstrapping concepts from Dynamic Programming algorithms together with the learning from experience concept from Monte Carlo.

Github: https://github.com/ffcmarcellino/applied-reinforcement-learning

Linkedin: https://www.linkedin.com/in/fellipemarcellino/