<jupyter_start><jupyter_text><NAME>  Reinforcement Learning  OpenAI gym<jupyter_code>'''
The make() function creates an environment, in this case a CartPole environment. This is a 2D simulation in
which a cart can be accelerated left or right in order to balance a pole placed on top of it. After 
the environment is created, we must initialize it using the reset() method. This returns the first observation.
Observations depend on the type of environment. For the CartPole environment, each observation is a 1D NumPy
array containing four floats: these floats represent the cart’s horizontal position (0.0 = center), its 
velocity, the angle of the pole (0.0 = vertical), and its angular velocity. Finally, the render() method 
displays the environment
'''
import gym

env = gym.make("CartPole-v0")
print('The environment: ', env )

obs = env.reset()
print('the first observation: ', obs) 

env.render()
# Ask the environment what actions are possible
print('What actions are possible: ', env.action_space) 

'''
Discrete(2) means that the possible actions are integers 0 and 1, which represent accelerating left (0) or 
right (1). Other environments may have more discrete actions, or other kinds of actions (e.g.,continuous).
Since the pole is leaning toward the right, let’s accelerate the cart toward the right:
'''
action = 1 # accelerate right
obs, reward, done, info = env.step(action)
print('The new observation: ', obs)
print( 'Thereward: ', reward) 
print('This value will be True when the episode is over: ', done) 
print('This dictionary may provide extra debug information in other environments: ', info) 

'''
The step() method executes the given action and returns four values:
- obs: This is the new observation. The cart is now moving toward the right (obs[1]>0). The pole is still
tilted toward the right (obs[2]>0 ), but its angular velocity is now negative (obs[3]<0 ), so it will likely
be tilted toward the left after the next step.
- reward:In this environment, you get a reward of 1.0 at every step, no matter what you do, so the goal is to
keep running as long as possible.
- done: This value will be True when the episode is over. This will happen when the pole tilts too much. After 
that, the environment must be reset before it can be used again.
- info: This dictionary may provide extra debug information in other environments. This data should not be used
for training (it would be cheating).
'''
'''
Let’s hardcode a simple policy that accelerates left when the pole is leaning toward the left and accelerates 
right when the pole is leaning toward the right. We will run this policy to see the average rewards it gets 
over 500 episodes
'''
def basic_policy(obs):
    angle = obs[2]
    return 0 if angle < 0 else 1

totals = []
for episode in range(500):
    episode_rewards = 0
    obs = env.reset()
    for step in range(1000): # 1000 steps max, we don't want to run forever
        action = basic_policy(obs)
        obs, reward, done, info = env.step(action)
        episode_rewards += reward
        if done:
            break
    totals.append(episode_rewards)
    
# Let’s look at the result
import numpy as np

print('The result: ', np.mean(totals), np.std(totals), np.min(totals), np.max(totals)) 

'''
Even with 500 tries, this policy never managed to keep the pole upright for more than 68 consecutive steps.
Not great.
'''<jupyter_output><empty_output><jupyter_text>Neural Network Policies<jupyter_code>'''
Let’s create a neural network policy. Just like the policy we hardcoded earlier, this neural network will
take an observation as input, and it will output the action to be executed. More precisely, it will estimate
a probability for each action, and then we will select an action randomly according to the estimated 
probabilities. In the case of the CartPole environment, there are just two possible actions (left or right),
so we only need one output neuron. It will output the probability p of action 0 (left), and of course the 
probability of action 1 (right) will be 1 – p. For example, if it outputs 0.7, then we will pick action 0 with
70% probability, and action 1 with 30% probability. You may wonder why we are picking a random action based on
the probability given by the neural network, rather than just picking the action with the highest score. This
approach lets the agent find the right balance between exploring new actions and exploiting the actions that
are known to work well. Here’s an analogy: suppose you go to a restaurant for the first time, and all the 
dishes look equally appealing so you randomly pick one. If it turns out to be good, you can increase the 
probability to order it next time, but you shouldn’t increase that probability up to 100%, or else you will 
never try out the other dishes, some of which may be even better than the one you tried. Also note that in this
particular environment, the past actions and observations can safely be ignored, since each observation 
contains the environment’s full state. If there were some hidden state, then you may need to consider past 
actions and observations as well. For example, if the environment only revealed the position of the cart but 
not its velocity, you would have to consider not only the current observation but also the previous observation
in order to estimate the current velocity. Another example is when the observations are noisy; in that case, 
you generally want to use the past few observations to estimate the most likely current state. The CartPole 
problem is thus as simple as can be; the observations are noise-free and they contain the environment’s full
state.
'''
# The code to build this neural network policy using TensorFlow
'''
import tensorflow as tf
from tensorflow.contrib.layers import fully_connected

# 1. Specify the neural network architecture
n_inputs = 4 # == env.observation_space.shape[0]
n_hidden = 4 # it's a simple task, we don't need more hidden neurons
n_outputs = 1 # only outputs the probability of accelerating left
initializer = tf.contrib.layers.variance_scaling_initializer()

# 2. Build the neural network
X = tf.placeholder(tf.float32, shape=[None, n_inputs])
hidden = fully_connected(X, n_hidden, activation_fn=tf.nn.elu,
                    weights_initializer=initializer)
logits = fully_connected(hidden, n_outputs, activation_fn=None,
                    weights_initializer=initializer)
outputs = tf.nn.sigmoid(logits)

# 3. Select a random action based on the estimated probabilities
p_left_and_right = tf.concat(axis=1, values=[outputs, 1 - outputs])
action = tf.multinomial(tf.log(p_left_and_right), num_samples=1)
init = tf.global_variables_initializer()
'''

'''
Let’s go through this code:
1. After the imports, we define the neural network architecture. The number of inputs is the size of the 
observation space (which in the case of the CartPole is four), we just have four hidden units and no need for
more, and we have just one output probability (the probability of going left).
2. Next we build the neural network. In this example, it’s a vanilla Multi-Layer Perceptron, with a single 
output. Note that the output layer uses the logistic (sigmoid) activation function in order to output a 
probability from 0.0 to 1.0. If there were more than two possible actions, there would be one output neuron 
per action, and you would use the softmax activation function instead.
3. Lastly, we call the multinomial() function to pick a random action. This function independentlysamples one
(or more) integers, given the log probability of each integer. For example, if you call it with the array 
[np.log(0.5), np.log(0.2), np.log(0.3)] and with num_samples=5 , then it will output five integers, each of 
which will have a 50% probability of being 0, 20% of being 1, and 30% of being 2. In our case we just need one
integer representing the action to take. Since the outputs tensor only contains the probability of going left,
we must first concatenate 1-outputs to it to have a tensor containing the probability of both left and right
actions. Note that if there were more than two possible actions, the neural network would have to output one
probability per action so you would not need the concatenation step.
'''<jupyter_output><empty_output><jupyter_text>Evaluating Actions: The Credit Assignment Problem<jupyter_code>'''
If we knew what the best action was at each step, we could train the neural network as usual, by minimizing the
cross entropy between the estimated probability and the target probability. It would just be regular supervised
learning. However, in Reinforcement Learning the only guidance the agent gets is through rewards, and rewards
are typically sparse and delayed. For example, if the agent manages to balance the pole for 100 steps, how can
it know which of the 100 actions it took were good, and which of them were bad? All it knows is that the pole
fell after the last action, but surely this last action is not entirely responsible. This is called the credit 
assignment problem: when the agent gets a reward, it is hard for it to know which actions should get credited
(or blamed) for it. Think of a dog that gets rewarded hours after it behaved well; will it understand what it
is rewarded for? To tackle this problem, a common strategy is to evaluate an action based on the sum of all the
rewards that come after it, usually applying a discount rate r at each step. For example, if an agent decides
to go right three times in a row and gets +10 reward after the first step, 0 after the second step, and finally
–50 after the third step, then assuming we use a discount rate r = 0.8, the first action will have a total 
score of 10 + r × 0 + r 2 × (–50) = –22. If the discount rate is close to 0, then future rewards won’t count
for much compared to immediate rewards. Conversely, if the discount rate is close to 1, then rewards far into
the future will count almost as much as immediate rewards. Typical discount rates are 0.95 or 0.99. With a 
discount rate of 0.95, rewards 13 steps into the future count roughly for half as much as immediate rewards 
(since 0.95 13 ≈ 0.5), while with a discount rate of 0.99, rewards 69 steps into the future count for half as
much as immediate rewards. In the CartPole environment, actions have fairly short-term effects, so choosing a 
discount rate of 0.95 seems reasonable. Of course, a good action may be followed by several bad actions that
cause the pole to fall quickly, resulting in the good action getting a low score (similarly, a good actor may
sometimes star in a terrible movie). However, if we play the game enough times, on average good actions will
get a better score than bad ones. So, to get fairly reliable action scores, we must run many episodes and 
normalize all the action scores (by subtracting the mean and dividing by the standard deviation). After that,
we can reasonably assume that actions with a negative score were bad while actions with a positive score were
good.
'''<jupyter_output><empty_output><jupyter_text>Policy Gradients<jupyter_code>'''
PG algorithms optimize the parameters of a policy by following the gradients toward higher rewards. One popular
class of PG algorithms, called REINFORCE algorithms, was introduced back in 1992 by <NAME>. Here is 
one common variant:
1. First, let the neural network policy play the game several times and at each step compute the gradients that
would make the chosen action even more likely, but don’t apply these gradients yet.
2. Once you have run several episodes, compute each action’s score (using the method described in the previous
paragraph).
3. If an action’s score is positive, it means that the action was good and you want to apply the gradients 
computed earlier to make the action even more likely to be chosen in the future. However, if the score is 
negative, it means the action was bad and you want to apply the opposite gradients to make this action slightly
less likely in the future. The solution is simply to multiply each gradient vector by the corresponding
action’s score.
4. Finally, compute the mean of all the resulting gradient vectors, and use it to perform a Gradient Descent
step.

Let’s implement this algorithm using TensorFlow. We will train the neural network policy we built earlier so 
that it learns to balance the pole on the cart. Let’s start by completing the construction phase we coded 
earlier to add the target probability, the cost function, and the training operation. Since we are acting as
though the chosen action is the best possible action, the target probability must be 1.0 if the chosen action
is action 0 (left) and 0.0 if it is action 1 (right)
'''
# y = 1. - tf.to_float(action)

'''
Now that we have a target probability, we can define the cost function (cross	entropy) and compute the
gradients
'''
# learning_rate = 0.01
# cross_entropy = tf.nn.sigmoid_cross_entropy_with_logits(
#                                                labels=y, logits=logits)
# optimizer = tf.train.AdamOptimizer(learning_rate)
# grads_and_vars = optimizer.compute_gradients(cross_entropy)

'''
Note that we are calling the optimizer’s compute_gradients() method instead of the minimize() method. This is
because we want to tweak the gradients before we apply them. The compute_gradients() method returns a list of
gradient vector/variable pairs (one pair per trainable variable). Let’s put all the gradients in a list, to 
make it more convenient to obtain their values
'''
# gradients = [grad for grad, variable in grads_and_vars]

'''
Okay, now comes the tricky part. During the execution phase, the algorithm will run the policy and at each
step it will evaluate these gradient tensors and store their values. After a number of episodes it will tweak
these gradients as explained earlier (i.e., multiply them by the action scores and normalize them) and compute
the mean of the tweaked gradients. Next, it will need to feed the resulting gradients back to the optimizer so
that it can perform an optimization step. This means we need one placeholder per gradient vector. Moreover, we
must create the operation that will apply the updated gradients. For this we will call the optimizer’s 
apply_gradients() function, which takes a list of gradient vector/variable pairs. Instead of giving it the 
original gradient vectors, we will give it a list containing the updated gradients (i.e., the ones fed 
through the gradient placeholders)
'''
# gradient_placeholders = []
# grads_and_vars_feed = []
# for grad, variable in grads_and_vars:
#    gradient_placeholder = tf.placeholder(tf.float32, shape=grad.get_shape())
#    gradient_placeholders.append(gradient_placeholder)
#    grads_and_vars_feed.append((gradient_placeholder, variable))
    
#training_op = optimizer.apply_gradients(grads_and_vars_feed)

# Let’s step back and take a look at the full construction phase
import tensorflow as tf
from tensorflow.contrib.layers import fully_connected

n_inputs = 4
n_hidden = 4
n_outputs = 1
initializer = tf.contrib.layers.variance_scaling_initializer()

learning_rate = 0.01

X = tf.placeholder(tf.float32,	shape=[None, n_inputs])

hidden = fully_connected(X, n_hidden, activation_fn=tf.nn.elu,
                    weights_initializer=initializer)
logits = fully_connected(hidden, n_outputs,	activation_fn=None,
                    weights_initializer=initializer)
outputs = tf.nn.sigmoid(logits)
p_left_and_right = tf.concat(axis=1, values=[outputs, 1 - outputs])
action = tf.multinomial(tf.log(p_left_and_right), num_samples=1)

y = 1. - tf.to_float(action)
cross_entropy = tf.nn.sigmoid_cross_entropy_with_logits(
                                                labels=y,	logits=logits)
optimizer = tf.train.AdamOptimizer(learning_rate)
grads_and_vars = optimizer.compute_gradients(cross_entropy)
gradients = [grad for grad, variable in grads_and_vars]

gradient_placeholders = []
grads_and_vars_feed = []
for grad, variable in grads_and_vars:
    gradient_placeholder = tf.placeholder(tf.float32, shape=grad.get_shape())
    gradient_placeholders.append(gradient_placeholder)
    grads_and_vars_feed.append((gradient_placeholder, variable))
training_op = optimizer.apply_gradients(grads_and_vars_feed)
init = tf.global_variables_initializer()
saver = tf.train.Saver()

'''
On to the execution phase! We will need a couple of functions to compute the total discounted rewards,
given the raw rewards, and to normalize the results across multiple episodes
'''
def discount_rewards(rewards, discount_rate):
    discounted_rewards = np.empty(len(rewards))
    cumulative_rewards = 0
    for step in reversed(range(len(rewards))):
        cumulative_rewards = rewards[step] + cumulative_rewards * discount_rate
        discounted_rewards[step] = cumulative_rewards
    return	discounted_rewards

def discount_and_normalize_rewards(all_rewards, discount_rate):
    all_discounted_rewards = [discount_rewards(rewards, discount_rate) for rewards in all_rewards]
    flat_rewards = np.concatenate(all_discounted_rewards)
    reward_mean = flat_rewards.mean()
    reward_std = flat_rewards.std()
    return [(discounted_rewards - reward_mean)/reward_std for discounted_rewards in all_discounted_rewards]
# Let’s check that this works
print('The discount_rewards: ', discount_rewards([10, 0, -50], discount_rate=0.8)) 
print('The discount_and_normalize_rewards: \n', discount_and_normalize_rewards([[10, 0, -50], [10, 20]], 
                                                                             discount_rate=0.8))

'''
The call to discount_rewards() returns exactly what we expect. You can verify that the function 
discount_and_normalize_rewards() does indeed return the normalized scores for each action in both episodes. 
Notice that the first episode was much worse than the second, so its normalized scores are all negative; all
actions from the first episode would be considered bad, and conversely all actions from the second episode 
would be considered good
'''

# Train the policy
env = gym.make("CartPole-v0")

n_iterations = 250 # number of training iterations
n_max_steps = 1000 # max	steps	per	episode
n_games_per_update = 10 # train the policy every 10 episodes
save_iterations = 10 # save the model every 10 training iterations
discount_rate = 0.95

with tf.Session() as sess:
    init.run()
    for iteration in range(n_iterations):
        print("\rIteration: {}".format(iteration), end="")
        all_rewards = [] # all sequences of raw rewards for each episode
        all_gradients = [] # gradients saved at each step of each episode
        for game in range(n_games_per_update):
            current_rewards = [] # all raw rewards from the current episode
            current_gradients = [] # all gradients from the current episode
            obs = env.reset()
            for step in range(n_max_steps):
                action_val, gradients_val = sess.run(
                                    [action, gradients],
                                    feed_dict={X: obs.reshape(1, n_inputs)}) # one obs
                obs, reward, done, info = env.step(action_val[0][0])
                current_rewards.append(reward)
                current_gradients.append(gradients_val)
                if done:
                    break
            all_rewards.append(current_rewards)
            all_gradients.append(current_gradients)
        # At this point we have run the policy for 10 episodes, and we are
        # ready for a policy update using the algorithm described earlier.
        all_rewards = discount_and_normalize_rewards(all_rewards, discount_rate=discount_rate)
        feed_dict = {}
        for var_index, grad_placeholder in enumerate(gradient_placeholders):
            # multiply the gradients by the action scores, and compute the mean
            mean_gradients = np.mean(
                            [reward * all_gradients[game_index][step][var_index]
                        for game_index, rewards in enumerate(all_rewards)
                     for step, reward in enumerate(rewards)],
                     axis=0)
            feed_dict[grad_placeholder] = mean_gradients
        sess.run(training_op, feed_dict=feed_dict)
        if iteration % save_iterations == 0:
            saver.save(sess, "./my_policy_net_pg.ckpt")

'''
Each training iteration starts by running the policy for 10 episodes (with maximum 1,000 steps per episode, 
to avoid running forever). At each step, we also compute the gradients, pretending that the chosen action was
the best. After these 10 episodes have been run, we compute the action scores using the discount_and_
normalize_rewards() function; we go through each trainable variable, across all episodes and all steps, to 
multiply each gradient vector by its corresponding action score; and we compute the mean of the resulting
gradients. Finally, we run the training operation, feeding it these mean gradients (one per trainable variable).
We also save the model every 10 training operations. And we’re done! This code will train the neural network
policy, and it will successfully learn to balance the pole on the cart. Note that there are actually two ways 
the agent can lose the game: either the pole can tilt too much, or the cart can go completely off the screen.
With 250 training iterations, the policy learns to balance the pole quite well, but it is not yet good enough
at avoiding going off the screen. A few hundred more training iterations will fix that. Despite its relative 
simplicity, this algorithm is quite powerful. You can use it to tackle much harder problems than balancing a
pole on a cart. In fact, AlphaGo was based on a similar PG algorithm
'''<jupyter_output><empty_output><jupyter_text>Learning to Play Ms. Pac-Man Using Deep Q-Learning<jupyter_code># Create a Ms. Pac-Man environment
import gym 

env = gym.make("MsPacman-v0")
obs = env.reset()
print('The observation: ', obs.shape) # [height, width, channels]
print('The environment space: ', env.action_space) 

'''
As you can see, there are nine discrete actions available, which correspond to the nine possible positions
of the joystick (left, right, up, down, center, upper left, and so on), and the observations are simply 
screenshots of the Atari screen, represented as 3D NumPy arrays. These images are a bit large, so we will 
create a small preprocessing function that will crop the image and shrink it down to 88 × 80 pixels, convert
it to grayscale, and improve the contrast of Ms. Pac-Man. This will reduce the amount of computations required
by the DQN, and speed up training
'''
mspacman_color = np.array([210, 164, 74]).mean()
def preprocess_observation(obs):
    img = obs[1:176:2, ::2] # crop and downsize
    img = img.mean(axis=2) # to greyscale
    img[img==mspacman_color] = 0 # improve	contrast
    img = (img - 128) / 128 - 1 # normalize from -1. to 1.
    return img.reshape(88, 80, 1)

'''
Next, let’s create the DQN. It could just take a state-action pair (s,a) as input, and output an estimate of
the corresponding Q-Value Q(s,a), but since the actions are discrete it is more convenient to use a neural
network that takes only a state s as input and outputs one Q-Value estimate per action. The DQN will be
composed of three convolutional layers, followed by two fully connected layers, including the output layer.
As we will see, the training algorithm we will use requires two DQNs with the same architecture (but different
parameters): one will be used to drive Ms. Pac-Man during training (the actor), and the other will watch the
actor and learn from its trials and errors (the critic). At regular intervals we will copy the critic to the 
actor. Since we need two identical DQNs, we will create a q_network() function to build them
'''
from tensorflow.contrib.layers import convolution2d, fully_connected

input_height = 88
input_width = 80
input_channels = 1
conv_n_maps = [32, 64, 64]
conv_kernel_sizes = [(8,8), (4,4), (3,3)]
conv_strides = [4, 2, 1]
conv_paddings = ["SAME"]*3
conv_activation = [tf.nn.relu]*3
n_hidden_in = 64 * 11 * 10 # conv3 has 64 maps of 11x10 each
n_hidden = 512
hidden_activation = tf.nn.relu
n_outputs = env.action_space.n # 9 discrete actions are available
initializer = tf.contrib.layers.variance_scaling_initializer()

def q_network(X_state,	scope):
    prev_layer = X_state
    conv_layers = []
    with tf.variable_scope(scope) as scope:
    for n_maps, kernel_size, stride, padding, activation in zip(
                                        conv_n_maps, conv_kernel_sizes, conv_strides,
                                        conv_paddings,	conv_activation):
        prev_layer = convolution2d(
                        prev_layer, num_outputs=n_maps, kernel_size=kernel_size,
                        stride=stride, padding=padding, activation_fn=activation,
                    weights_initializer=initializer)
        conv_layers.append(prev_layer)
        last_conv_layer_flat = tf.reshape(prev_layer, shape=[-1, n_hidden_in])
        hidden = fully_connected(
                        last_conv_layer_flat, n_hidden, activation_fn=hidden_activation,
                        weights_initializer=initializer)
        outputs = fully_connected(
                            hidden, n_outputs, activation_fn=None,
                            weights_initializer=initializer)
    trainable_vars = tf.get_collection(tf.GraphKeys.TRAINABLE_VARIABLES,
                                    scope=scope.name)
    trainable_vars_by_name = {var.name[len(scope.name):]: var
                                                for var in trainable_vars}
    return outputs, trainable_vars_by_name

'''
The first part of this code defines the hyperparameters of the DQN architecture. Then the q_network() function
creates the DQN, taking the environment’s state X_state as input, and the name of the variable scope. Note that
we will just use one observation to represent the environment’s state since there’s almost no hidden state 
(except for blinking objects and the ghosts’ directions). The trainable_vars_by_name dictionary gathers all the
trainable variables of this DQN. It will be useful in a minute when we create operations to copy the critic DQN
to the actor DQN. The keys of the dictionary are the names of the variables, stripping the part of the prefix
that just corresponds to the scope’s name. It looks like this
'''
print(trainable_vars_by_name)

# Create the input placeholder, the two DQNs, and the operation to copy the critic DQN to the actor DQN
X_state = tf.placeholder(tf.float32, shape=[None, input_height, input_width,
                    input_channels])
actor_q_values, actor_vars = q_network(X_state, scope="q_networks/actor")
critic_q_values, critic_vars = q_network(X_state, scope="q_networks/critic")
copy_ops = [actor_var.assign(critic_vars[var_name])
                for var_name, actor_var in actor_vars.items()]
copy_critic_to_actor = tf.group(*copy_ops)

'''
Let’s step back for a second: we now have two DQNs that are both capable of taking an environment state
(i.e., a preprocessed observation) as input and outputting an estimated Q-Value for each possible action in
that state. Plus we have an operation called copy_critic_to_actor to copy all the trainable variables
of the critic DQN to the actor DQN. We use TensorFlow’s tf.group() function to group all the assignment 
operations into a single convenient operation. The actor DQN can be used to play Ms. Pac-Man (initially 
very badly). As discussed earlier, you want it to explore the game thoroughly enough, so you generally want to 
combine it with an ε-greedy policy or another exploration strategy. But what about the critic DQN? How will it
learn to play the game? The short answer is that it will try to make its Q-Value predictions match the Q-Values
estimated by the actor through its experience of the game. Specifically, we will let the actor play for a 
while, storing all its experiences in a replay memory. Each memory will be a 5-tuple (state, action, next 
state, reward, continue), where the “continue” item will be equal to 0.0 when the game is over, or 1.0 
otherwise. Next, at regular intervals we will sample a batch of memories from the replay memory, and we will
estimate the Q-Values from these memories. Finally, we will train the critic DQN to predict these Q-Values
using regular supervised learning techniques. Once every few training iterations, we will copy the critic
DQN to the actor DQN. 
NOTE: The replay memory is optional, but highly recommended. Without it, you would train the critic DQN using
consecutive experiences that may be very correlated. This would introduce a lot of bias and slow down the 
training algorithm’s convergence. By using a replay memory, we ensure that the memories fed to the training
algorithm can be fairly uncorrelated.
Let’s add the critic DQN’s training operations. First, we need to be able to compute its predicted Q-Values 
for each state-action in the memory batch. Since the DQN outputs one Q-Value for every possible action, we 
need to keep only the Q-Value that corresponds to the action that was actually chosen in this memory. For 
this, we will convert the action to a one-hot vector (recall that this is a vector full of 0s except for a 1 
at the i th index), and multiply it by the Q-Values: this will zero out all Q-Values except for the one 
corresponding to the memorized action. Then just sum over the first axis to obtain only the desired
Q-Value prediction for each memory
'''
X_action = tf.placeholder(tf.int32, shape=[None])
q_value = tf.reduce_sum(critic_q_values * tf.one_hot(X_action, n_outputs),
                            axis=1,	keep_dims=True)

'''
Next let’s add the training operations, assuming the target Q-Values will be fed through a placeholder. We
also create a nontrainable variable called global_step. The optimizer’s minimize() operation will take care
of incrementing it. Plus we create the usual init operation and a Saver.
'''
y = tf.placeholder(tf.float32, shape=[None, 1])
cost = tf.reduce_mean(tf.square(y - q_value))
global_step = tf.Variable(0, trainable=False, name='global_step')
optimizer = tf.train.AdamOptimizer(learning_rate)
training_op = optimizer.minimize(cost, global_step=global_step)

init = tf.global_variables_initializer()
saver = tf.train.Saver()

'''
That’s it for the construction phase. Before we look at the execution phase, we will need a couple of tools.
First, let’s start by implementing the replay memory. We will use a deque list since it is very efficient at 
pushing items to the queue and popping them out from the end of the list when the maximum memory size is 
reached. We will also write a small function to	randomly sample a batch of experiences from the replay memory
'''

from collections import deque

replay_memory_size = 10000
replay_memory = deque([], maxlen=replay_memory_size)
def sample_memories(batch_size):
    indices = rnd.permutation(len(replay_memory))[:batch_size]
    cols = [[], [], [], [], []] # state, action, reward, next_state, continue
    for idx in indices:
        memory = replay_memory[idx]
        for col, value in zip(cols,	memory):
            col.append(value)
    cols = [np.array(col) for col in cols]
    return (cols[0], cols[1], cols[2].reshape(-1, 1), cols[3],
                cols[4].reshape(-1, 1))

'''
Next, we will need the actor to explore the game. We will use the ε-greedy policy, and gradually decrease
ε from 1.0 to 0.05, in 50,000 training steps
'''
eps_min = 0.05
eps_max = 1.0
eps_decay_steps = 50000
def epsilon_greedy(q_values, step):
    epsilon = max(eps_min, eps_max - (eps_max-eps_min) * step/eps_decay_steps)
    if rnd.rand() < epsilon:
        return rnd.randint(n_outputs) # random action
    else:
        return np.argmax(q_values) # optimal action
    
    
'''
That’s it! We have all we need to start training. The execution phase does not contain anything too complex,
but it is a bit long, so take a deep breath. Ready? Let’s go! First, let’s initialize a few variables
'''

n_steps = 100000 # total number of training steps
training_start = 1000 # start training after 1,000 game iterations
training_interval = 3 # run a training step every 3 game iterations
save_steps = 50 # save the model every 50 training steps
copy_steps = 25 # copy the critic to the actor every 25 training steps
discount_rate = 0.95
skip_start = 90 # skip the start of every game (it's just waiting time)
batch_size = 50
iteration = 0 # game iterations
checkpoint_path = "./my_dqn.ckpt"
done = True # env needs to be reset

# Next, let’s open the session and run the main training loop
with tf.Session() as sess:
    if os.path.isfile(checkpoint_path):
        saver.restore(sess, checkpoint_path)
    else:
        init.run()
    while True:
        step = global_step.eval()
        if step >= n_steps:
            break
        iteration += 1
        if done: # game over, start again
            obs = env.reset()
            for skip in range(skip_start): # skip the start of each game
                obs, reward, done, info = env.step(0)
            state = preprocess_observation(obs)
            
        # Actor evaluates what to do
        q_values = actor_q_values.eval(feed_dict={X_state: [state]})
        action = epsilon_greedy(q_values, step)
        
        # Actor plays
        obs, reward, done, info = env.step(action)
        next_state = preprocess_observation(obs)
        
        # Let's memorize what just happened
        replay_memory.append((state, action, reward, next_state, 1.0 - done))
        state = next_state
        
        if iteration < training_start or iteration % training_interval != 0:
            continue
            
        # Critic learns
        X_state_val, X_action_val, rewards, X_next_state_val, continues = (
                                                            sample_memories(batch_size))
        next_q_values = actor_q_values.eval(
                                    feed_dict={X_state: X_next_state_val})
        max_next_q_values = np.max(next_q_values, axis=1, keepdims=True)
        y_val = rewards + continues * discount_rate * max_next_q_values
        training_op.run(feed_dict={X_state: X_state_val,
                            X_action:	X_action_val,	y:	y_val})
        
        # Regularly copy critic to actor
        if step % copy_steps == 0:
            copy_critic_to_actor.run()
        # And save regularly
        if step % save_steps == 0:
            saver.save(sess, checkpoint_path)
            
'''
We start by restoring the models if a checkpoint file exists, or else we just initialize the variables
normally. Then the main loop starts, where iteration counts the total number of game steps we have
gone through since the program started, and step counts the total number of training steps since training
started (if a checkpoint is restored, the global step is restored as well). Then the code resets the game
(and skips the first boring game steps, where nothing happens). Next, the actor evaluates what to do, and
plays the game, and its experience is memorized in replay memory. Then, at regular intervals (after a
warmup period), the critic goes through a training step. It samples a batch of memories and asks the actor
to estimate the Q-Values of all actions for the next state, and it applies Equation 16-7 to compute the target
Q-Value y_val. The only tricky part here is that we must multiply the next state’s Q-Values by the continues
vector to zero out the Q-Values corresponding to memories where the game was over. Next we run a training 
operation to improve the critic’s ability to predict Q-Values. Finally, at regular intervals we copy the
critic to the actor, and we save the model.
TIP: Unfortunately, training is very slow: if you use your laptop for training, it will take days before 
Ms. Pac-Man gets any good, and if you look at the learning curve, measuring the average rewards per episode,
you will notice that it is extremely noisy. At some points there may be no apparent progress for a very long
time until suddenly the agent learns to survive a reasonable amount of time. As mentioned earlier, one 
solution is to inject as much prior knowledge as possible into the model (e.g., through preprocessing, rewards,
and so on), and you can also try to bootstrap the model by first training it to imitate a basic strategy. In
any case, RL still requires quite a lot of patience and tweaking, but the end result is very exciting.
'''<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup