<jupyter_start><jupyter_text>DQN - Replay BufferAnother potential problem with the use of function approximators for Q-learning is the correlations between consecutive transitions. Typically, an agent will spend many consecutive frames repeating the same action with very little changes to the state and reward. Such transitions can negatively affect learning. It is for similar reasons that we randomize batches in supervised learning to avoid similar updates to the network. A replay buffer is simply a store for transitions can be implemented using a variety of data structures with fixed capacity. After each step, we store the tuple (s, a, r, s') of the current state, action taken, reward received and next state into the buffer (old transitions are eventually evicted). Finally, rather than train with a single target as before, we uniformly sample a random minibatch from the buffer and train using this minibatch. Another advantage of using a replay buffer is that we can now learn from the same transition multiple times which could be helpful.<jupyter_code>import math
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import gym
import cntk
from cntk import *
from cntk.layers import *<jupyter_output><empty_output><jupyter_text>Replay buffer ImplementationHere I've used a numpy ndarray to represent a fixed capacity circular buffer if we go off one end, we wrap around and resume at the other). To sample, we randomly pick n transitions from the buffer making sure that n is less than or equal to the number of items in the buffer.<jupyter_code>class ReplayBuffer: 
    """
    Fixed capacity buffer implemented as circular queue
    Transitions are stored as (s, a, r, s', done) tuples
    """
    def __init__(self, capacity):
        self.samples = np.ndarray(capacity, dtype=object)
        self.capacity = capacity
        self.counter = 0
        self.flag = False
        
    def size(self):
        if self.flag:
            return self.capacity
        else:
            return self.counter
        
    def add(self, sample):
        self.samples[self.counter] = sample
        
        self.counter += 1
        if self.counter >= self.capacity:
            self.counter = 0
            self.flag = True
            
    def sample(self, n):
        n = min(n, self.size())
        
        size = self.size()
        if size < self.capacity:
            return np.random.choice(self.samples[:size], n, replace=False)
        else:
            return np.random.choice(self.samples, n, replace=False)<jupyter_output><empty_output><jupyter_text>The agent class is exactly the same as in the original Q-learning implementation. CNTK is able to evaluate and train a model when given a single input as well as when given multiple.<jupyter_code>class Agent:
    def __init__(self, state_dim, action_dim, learning_rate):
        self.state_dim = state_dim
        self.action_dim = action_dim
        self.learning_rate = learning_rate
        self.epsilon = 1.0
        
        # Create the neural network
        self.state_var = input(state_dim, np.float32)
        self.action_var = input(action_dim, np.float32)
        
        self.model = Sequential([
            Dense(64, activation=relu),
            Dense(action_dim)
        ])(self.state_var)
        
        loss = reduce_mean(square(self.model - self.action_var), axis=0)
        lr_schedule = learning_rate_schedule(self.learning_rate, UnitType.sample)
        learner = sgd(self.model.parameters, lr_schedule)
        self.trainer = Trainer(self.model, loss, learner)
    
    def predict(self, state):
        """
        Feeds a state through our model to obtain the values of each action
        """
        return self.model.eval(state)
    
    def act(self, state):
        """
        Selects an action using the epoch-greedy approach
        """
        prob = np.random.randn(1)
        if prob > self.epsilon:
            # exploit (greedy)
            return np.argmax(self.predict(state))
        else:
            # explore (random action)
            return np.random.randint(0, self.action_dim)
        
    def update_epsilon(self, episode):
        """
        Updates epsilon using exponential decay with the decay rate chosen such
        that epsilon is 0.05 by episode 8000
        """
        self.epsilon = max(math.exp(-3.74e-4 * episode), 0.05)
        
    def train(self, x, y):
        """
        Performs a single gradient descent step using the provided state and target
        """
        self.trainer.train_minibatch({self.state_var: x, self.action_var: y})
        
    def evaluate(self, env, n):
        """
        Computes the average performance of the trained model over n episodes
        """
        episode = 0
        rewards = 0
        while episode < n:
            s = env.reset()
            done = False
            while not done:
                a = np.argmax(self.predict(s.astype(np.float32)))
                s, r, done, info = env.step(a)
                rewards += r
            episode += 1
            
        return rewards / float(n)<jupyter_output><empty_output><jupyter_text>Before we start training, we initialize the buffer using randomly generated transitions as shown here:<jupyter_code>def initialize_buffer(env, buffer):
    """
    Initializes the replay buffer using experiences generated by taking random actions
    """
    actions = env.action_space.n
    s = env.reset()
    
    while buffer.size() < buffer.capacity:
        a = env.action_space.sample()
        s_, r, done, info = env.step(a)
        
        buffer.add((s, a, r, s_, done))
        
        if done:
            s = env.reset()
        else:
            s = s_<jupyter_output><empty_output><jupyter_text>Train has been updated since we now calculate the targets for a batch of transitions than for a single transition.<jupyter_code>def train(env, agent, buffer, episodes, gamma, minibatch_size):
    """
    param env: The gym environment to train with
    param agent: The agent to train
    param buffer: The replay buffer to sample experiences from
    param episodes: The number of episodes to train for
    param gamma: The discount factor
    param minibatch_size: The number of transitions to sample for training
    """
    episode = 0
    rewards = 0
    log_freq = 200
    episode_rewards = []
    s = env.reset().astype(np.float32)
    
    while episode < episodes:
        # Select an action using policy derived from Q (e-greedy)
        a = agent.act(s)
        
        # Take action and observe the next state and reward
        s_, r, done, info = env.step(a)
        s_ = s_.astype(np.float32)
        
        # Store transition in replay buffer
        buffer.add((s, a, r, s_, done))
        
        s = s_
        rewards += r
        
        # Sample random transitions from replay buffer
        batch = buffer.sample(minibatch_size)
        
        # Compute targets, y_i
        states = np.array([obs[0] for obs in batch], dtype=np.float32)
        states_ = np.array([obs[3] for obs in batch], dtype=np.float32)
        
        y = agent.predict(states)
        q_next = agent.predict(states_)
        
        for i in range(minibatch_size):
            p, a, r, p_, d = batch[i]
            if d:
                y[i, a] = r
            else:
                y[i, a] = r + gamma * np.amax(q_next[i])
        
        # Train using state and computed target
        agent.train(states, y)
        
        if done:
            # Episode over, reset environment
            episode_rewards.append(rewards)
            rewards = 0
            
            episode += 1
            agent.update_epsilon(episode)
            s = env.reset().astype(np.float32)
            
            if episode % log_freq == 0:
                ave = sum(episode_rewards[(episode - log_freq):]) / float(log_freq)
                print('Episode = {}, Average rewards = {}'.format(episode, ave))
                
    return episode_rewards
gamma = 0.60
learning_rate = 0.00025
episodes = 10000
buffer_capacity = 32
minibatch_size = 8
env = gym.make('CartPole-v0')
state_dim = env.observation_space.shape
action_dim = env.action_space.n 
buffer = ReplayBuffer(buffer_capacity)
agent = Agent(state_dim, action_dim, learning_rate)
initialize_buffer(env, buffer)
rewards = train(env, agent, buffer, episodes, gamma, minibatch_size)
buffer2 = ReplayBuffer(1)
agent2 = Agent(state_dim, action_dim, learning_rate)<jupyter_output><empty_output><jupyter_text>To simulate the orignal Q-learning, we simply use a replay buffer of size 1 and a minibatch of size 1.<jupyter_code>rewards2 = train(env, agent2, buffer, episodes, gamma, 1)
pd.Series(rewards).rolling(window=100).mean().plot(label='with experience replay')
pd.Series(rewards2).rolling(window=100).mean().plot(label='without experience replay')
plt.legend()
plt.show()
eval_episodes = 100
ave_er = agent.evaluate(env, eval_episodes)
ave_no_er = agent2.evaluate(env, eval_episodes)
print('Average reward (without experience replay) = {}'.format(ave_no_er))
print('Average reward (with experience replay) = {}'.format(ave_er))<jupyter_output>Average reward (without experience replay) = 134.37
Average reward (with experience replay) = 177.94<jupyter_text>As shown, learning is faster when experience replay is used. We also achieve a better final performance on the evaluation.<jupyter_code>s = env.reset()
done = False
while not done:
    env.render()
    a = np.argmax(agent2.predict(s.astype(np.float32)))
    s, r, done, info = env.step(a)
env.close()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08590170762182424, 'fraction_numerical': 0.010724698042482298, 'mean_word_length': 2.54036122373756, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '633337', 'license': 'MIT', 'n_tokens_mistral': 2804, 'n_tokens_neox': 2686, 'n_words': 923, 'path': 'cartpole/experience_replay.ipynb', 'repo_name': 'frankibem/reinforcement-learning', 'size': '9604'}