Implementing and evaluating a random search policy

After some practice with PyTorch programming, starting from this recipe, we will be working on more sophisticated policies to solve the CartPole problem than purely random actions. We start with the random search policy in this recipe.

A simple, yet effective, approach is to map an observation to a vector of two numbers representing two actions. The action with the higher value will be picked. The linear mapping is depicted by a weight matrix whose size is 4 x 2 since the observations are 4-dimensional in this case. In each episode, the weight is randomly generated and is used to compute the action for every step in this episode. The total reward is then calculated. This process repeats for many episodes and, in the end, the weight that enables the highest total reward will become the learned policy. This approach is called random search because the weight is randomly picked in each trial with the hope that the best weight will be found with a large number of trials.

How to do it...

Let's go ahead and implement a random search algorithm with PyTorch:

1. Import the Gym and PyTorch packages and create an environment instance:

>>> import gym
>>> import torch
>>> env = gym.make('CartPole-v0')

2. Obtain the dimensions of the observation and action space:

>>> n_state = env.observation_space.shape[0]
>>> n_state
 4
>>> n_action = env.action_space.n
>>> n_action
 2

These will be used when we define the tensor for the weight matrix, which is size 4 x 2 in size.

3. Define a function that simulates an episode given the input weight and returns the total reward:

 >>> def run_episode(env, weight):
 ...     state = env.reset()
 ...     total_reward = 0
 ...     is_done = False
 ...     while not is_done:
 ...         state = torch.from_numpy(state).float()
 ...         action = torch.argmax(torch.matmul(state, weight))
 ...         state, reward, is_done, _ = env.step(action.item())
 ...         total_reward += reward
 ...     return total_reward

Here, we convert the state array to a tensor of the float type because we need to compute the multiplication of the state and weight tensor, torch.matmul(state, weight), for linear mapping. The action with the higher value is selected using the torch.argmax() operation. And don't forget to take the value of the resulting action tensor using .item() because it is a one-element tensor.

4. Specify the number of episodes:

>>> n_episode = 1000

5. We need to keep track of the best total reward on the fly, as well as the corresponding weight. So, we specify their starting values:

>>> best_total_reward = 0
>>> best_weight = None

We will also record the total reward for every episode:

>>> total_rewards = []

6. Now, we can run n_episode. For each episode, we do the following:

• Randomly pick the weight
• Let the agent take actions according to the linear mapping
• An episode terminates and returns the total reward
• Update the best total reward and the best weight if necessary
• Also, keep a record of the total reward

Put this into code as follows:

 >>> for episode in range(n_episode):
 ...     weight = torch.rand(n_state, n_action)
 ...     total_reward = run_episode(env, weight)
 ...     print('Episode {}: {}'.format(episode+1, total_reward))
 ...     if total_reward > best_total_reward:
 ...         best_weight = weight
 ...         best_total_reward =  total_reward
 ...     total_rewards.append(total_reward)
 ...
 Episode 1: 10.0
 Episode 2: 73.0
 Episode 3: 86.0
 Episode 4: 10.0
 Episode 5: 11.0
 ……
 ……
 Episode 996: 200.0
 Episode 997: 11.0
 Episode 998: 200.0
 Episode 999: 200.0
 Episode 1000: 9.0

We have obtained the best policy through 1,000 random searches. The best policy is parameterized by best_weight.

7. Before we test out the best policy in the testing episodes, we can calculate the average total reward achieved by random linear mapping:

 >>> print('Average total reward over {} episode: {}'.format(
           n_episode, sum(total_rewards) / n_episode))
 Average total reward over 1000 episode: 47.197

This is more than twice what we got from the random action policy (22.25).

8. Now, let's see how the learned policy performs on 100 new episodes:

 >>> n_episode_eval = 100
 >>> total_rewards_eval = []
 >>> for episode in range(n_episode_eval):
 ...     total_reward = run_episode(env, best_weight)
 ...     print('Episode {}: {}'.format(episode+1, total_reward))
 ...     total_rewards_eval.append(total_reward)
 ...
 Episode 1: 200.0
 Episode 2: 200.0
 Episode 3: 200.0
 Episode 4: 200.0
 Episode 5: 200.0
 ……
 ……
 Episode 96: 200.0
 Episode 97: 188.0
 Episode 98: 200.0
 Episode 99: 200.0
 Episode 100: 200.0
 >>> print('Average total reward over {} episode: {}'.format(
           n_episode, sum(total_rewards_eval) / n_episode_eval))
 Average total reward over 1000 episode: 196.72

Surprisingly, the average reward for the testing episodes is close to the maximum of 200 steps with the learned policy. Be aware that this value may vary a lot. It could be anywhere from 160 to 200.

How it works...

The random search algorithm works so well mainly because of the simplicity of our CartPole environment. Its observation state is composed of only four variables. You will recall that the observation in the Atari Space Invaders game is more than 100,000 (which is 210 * 160 * 3) . The number of dimensions of the action state in CartPole is a third of that in Space Invaders. In general, simple algorithms work well for simple problems. In our case, we simply search for the best linear mapping from the observation to the action from a random pool.

Another interesting thing we've noticed is that before we select and deploy the best policy (the best linear mapping), random search also outperforms random action. This is because random linear mapping does take the observations into consideration. With more information from the environment, the decisions made in the random search policy are more intelligent than completely random ones.

There's more...

We can also plot the total reward for every episode in the training phase:

>>> import matplotlib.pyplot as plt
>>> plt.plot(total_rewards)
>>> plt.xlabel('Episode')
>>> plt.ylabel('Reward')
>>> plt.show()

This will generate the following plot:

If you have not installed matplotlib, you can do so via the following command:

conda install matplotlib

We can see that the reward for each episode is pretty random, and that there is no trend of improvement as we go through the episodes. This is basically what we expected.

In the plot of reward versus episodes, we can see that there are some episodes in which the reward reaches 200. We can end the training phase whenever this occurs since there is no room to improve. Incorporating this change, we now have the following for the training phase:

 >>> n_episode = 1000
 >>> best_total_reward = 0
 >>> best_weight = None
 >>> total_rewards = []
 >>> for episode in range(n_episode):
 ...     weight = torch.rand(n_state, n_action)
 ...     total_reward = run_episode(env, weight)
 ...     print('Episode {}: {}'.format(episode+1, total_reward))
 ...     if total_reward > best_total_reward:
 ...         best_weight = weight
 ...         best_total_reward = total_reward
 ...     total_rewards.append(total_reward)
 ...     if best_total_reward == 200:
 ...         break
 Episode 1: 9.0
 Episode 2: 8.0
 Episode 3: 10.0
 Episode 4: 10.0
 Episode 5: 10.0
 Episode 6: 9.0
 Episode 7: 17.0
 Episode 8: 10.0
 Episode 9: 43.0
 Episode 10: 10.0
 Episode 11: 10.0
 Episode 12: 106.0
 Episode 13: 8.0
 Episode 14: 32.0
 Episode 15: 98.0
 Episode 16: 10.0
 Episode 17: 200.0

The policy achieving the maximal reward is found in episode 17. Again, this may vary a lot because the weights are generated randomly for each episode. To compute the expectation of training episodes needed, we can repeat the preceding training process 1,000 times and take the average of the training episodes:

 >>> n_training = 1000
 >>> n_episode_training = []
 >>> for _ in range(n_training):
 ...     for episode in range(n_episode):
 ...         weight = torch.rand(n_state, n_action)
 ...         total_reward = run_episode(env, weight)
 ...         if total_reward == 200:
 ...             n_episode_training.append(episode+1)
 ...             break
 >>> print('Expectation of training episodes needed: ',
            sum(n_episode_training) / n_training)
 Expectation of training episodes needed:  13.442

On average, we expect that it takes around 13 episodes to find the best policy.