Catch is a straightforward arcade game that you might have played as a child. Fruits fall from the top of the screen, and the player has to catch them with a basket. For every fruit caught, the player scores a point. For every fruit lost, the player loses a point.

The goal here is to let the computer play Catch by itself. We will be using a simplified version in this example in order to make the task easier:

The "Catch" game that we will be creating

While playing Catch, the player decides between three possible actions. They can move the basket to the left, to the right, or make it stay put.

The basis for this decision is the current state of the game; in other words, the positions of the falling fruit and of the basket. Our goal is to create a model that, given the content of the game screen, chooses the action that leads to the highest score possible. This task can be seen as a simple classification problem. We could ask expert human players to play the game multiple times and record their actions. Then, we could train a model to choose the "correct" action that mirrors the expert players.

This is not how humans learn, however. Humans can learn a game such as Catch by themselves, without guidance. This is very useful, because imagine if you had to hire a bunch of experts to perform a task thousands of times every time you wanted to learn something as simple as Catch: it would be expensive and slow.

In reinforcement learning, the model trains from experience, rather than labeled data. Instead of providing the model with the correct actions, we provide it with rewards and punishments. The model receives information about the current state of the environment, for example, the computer game screen. It then outputs an action, such as a joystick movement. The environment reacts to this action and provides the next state, along with any rewards:

RL scheme

The model then learns to find actions that lead to maximum rewards. There are many ways this can work in practice. Right now, we are going to look at Q-learning. Q-learning made a splash when it was used to train a computer to play Atari video games. Today, it is still a relevant concept. Most modern RL algorithms are based on some adaptation of Q-learning.

An excellent way to understand Q-learning is to compare playing Catch with playing chess. In both games, you are given a state, s. With chess, this is the position of the figures on the board. In Catch, this is the location of the fruit and the basket. The player then has to take an action, a. In chess, this is moving a figure. In Catch, this is moving the basket left or right or remaining in the current position.

As a result, there will be some reward, r, and a new state, . The problem with both Catch and chess is that the rewards do not appear immediately after the action.

In Catch, you only earn rewards when the fruits hit the basket or fall on the floor, and in chess, you only earn a reward when you win or lose the game. This means that rewards are sparsely distributed. Most of the time, r will be zero. When there is a reward, it is not always a result of the action taken immediately before. Some action taken long before might have caused the victory. Figuring out which action is responsible for the reward is often referred to as the credit assignment problem. Because rewards are delayed, good chess players do not choose their plays only by the immediate reward. Instead, they choose the expected future reward.

For example, they do not only think about whether they can eliminate an opponent's figure in the next move, they also consider how taking a specific action now will help them in the long run. In Q-learning, we choose our action based on the highest expected future reward. We use a Q-function to calculate this. This is a mathematical function that takes two arguments: the current state of the game, and a given action. We can write this as Q(state, action).

While in state s, we estimate the future reward for each possible action, a. We assume that after we have taken action a and moved to the next state, , everything works out perfectly. The expected future reward, q(s,a), for a given state and action is calculated as the immediate reward, plus the expected future reward thereafter, . We assume the next action, , is optimal. Because there is uncertainty about the future, we discount by the factor gamma, . We, therefore, arrive at an expected reward of this:

Good chess players are very good at estimating future rewards in their head. In other words, their Q-function, Q(s,a), is very precise.

Most chess practice revolves around developing a better Q-function. Players peruse many old games to learn how specific moves played out in the past, and how likely a given action is to lead to victory. However, this raises the question, how can a machine estimate a good Q-function? This is where neural networks come into play.

class ExperienceReplay(object):                                   #1
    def __init__(self, max_memory=100, discount=.9):
        self.max_memory = max_memory                              #2
        self.memory = []
        self.discount = discount

    def remember(self, states, game_over):                        #3
        self.memory.append([states, game_over])
        if len(self.memory) > self.max_memory:
            del self.memory[0]                                    #4

    def get_batch(self, model, batch_size=10):                    #5
        len_memory = len(self.memory)                             #6
        num_actions = model.output_shape[-1]
        env_dim = self.memory[0][0][0].shape[1]
        
        inputs = np.zeros((min(len_memory, batch_size), env_dim)) #7
        targets = np.zeros((inputs.shape[0], num_actions))
        
        for i, idx in enumerate(np.random.randint(0, len_memory, size=inputs.shape[0])):           #8
            state_t, action_t, reward_t, state_tp1 = self.memory[idx][0]                               #9
            game_over = self.memory[idx][1]

            inputs[i:i+1] = state_t                               #10
            
            targets[i] = model.predict(state_t)[0]                #11
            
            Q_sa = np.max(model.predict(state_tp1)[0])            #12
            
            if game_over:                                         #13
                targets[i, action_t] = reward_t
            else:
                targets[i, action_t] = reward_t + self.discount * Q_sa
        return inputs, targets

num_actions = 3
grid_size = 10

model = Sequential()
model.add(Dense(100, input_shape=(grid_size**2,), activation='relu'))
model.add(Dense(100, activation='relu'))
model.add(Dense(num_actions))
model.compile(optimizer='sgd', loss='mse')

Training to play Catch

The final ingredient to Q-learning is exploration. Everyday life shows that sometimes you have to do something weird and/or random to find out whether there is something better than your daily trot.

The same goes for Q-learning. By always choosing the best option, you might miss out on some unexplored paths. To avoid this, the learner will sometimes choose a random option, and not necessarily the best one.

Now we can define the training method:

def train(model,epochs):
    win_cnt = 0                                                 #1

    win_hist = []

    for e in range(epochs):                                     #2
        loss = 0.
        env.reset()
        game_over = False
        input_t = env.observe()
        
        while not game_over:                                    #3
            input_tm1 = input_t                                 #4
            
            if np.random.rand() <= epsilon:                     #5
                action = np.random.randint(0, num_actions, size=1)
            else:
                q = model.predict(input_tm1)                    #6
                action = np.argmax(q[0])

            input_t, reward, game_over = env.act(action)        #7
            if reward == 1:
                win_cnt += 1

            exp_replay.remember([input_tm1, action, reward, input_t],game_over)            #8

            inputs, targets = exp_replay.get_batch(model, batch_size=batch_size)          #9

            batch_loss = model.train_on_batch(inputs, targets)

            loss += batch_loss
            
        win_hist.append(win_cnt)
    return win_hist

Before we go further, again let's break down the code so we can see what we're doing:

1. We want to keep track of the progress of our Q-learner, so we count the wins of the model over time.
2. We now play for a number of games, specified by the epoch argument. At the beginning of a game, we first reset the game, set the game_over indicator to False, and observe the initial state of the game.
3. We will then be playing frame by frame until the game is over.
4. At the start of a frame cycle, we save the previously observed input as input_tm1, the input at time t minus one.
5. Now comes the exploration part. We draw a random number between zero and one. If the number is smaller than epsilon, we pick a random action. This technique is also called "epsilon greedy," as we pick a random action with a probability of epsilon and greedily choose the action promising the highest rewards otherwise.
6. If we choose a non-random action, we let the neural network predict the expected rewards for all actions. We then pick the action with the highest expected reward.
7. We now act with our chosen or random action and observe a new state, a reward, and information about whether the game is over. The game gives a reward of one if we win, so we eventually have to increase our win counter.
8. We store the new experience in our experience replay buffer.
9. We then sample a new training batch from the experience replay and train on that batch.

The following graph shows the rolling mean of successful games. After about 2,000 epochs of training, the neural network should be quite good at playing Catch:

The progress of a Q-learning neural network playing Catch

Looking at the preceding graph, it's safe to say that you have now successfully created your first reinforcement learning system, as after 5000 epochs the average of victories per games is between 90% and 100%. In the next section, we will explore the theoretical foundations of reinforcement learning and discover how the same system that learns to play catch can learn to route orders in the futures market.