Chapter 9. Deep Reinforcement Learning

Reinforcement Learning (RL) is a framework that is used by an agent for decision-making. The agent is not necessarily a software entity such as in video games. Instead, it could be embodied in hardware such as a robot or an autonomous car. An embodied agent is probably the best way to fully appreciate and utilize reinforcement learning since a physical entity interacts with the real-world and receives responses.

The agent is situated within an environment. The environment has a state that can be partially or fully observable. The agent has a set of actions that it can use to interact with its environment. The result of an action transitions the environment to a new state. A corresponding scalar reward is received after executing an action. The goal of the agent is to maximize the accumulated future reward by learning a policy that will decide which action to take given a state.

Reinforcement learning has a strong similarity to human...

Principles of reinforcement learning (RL)

Figure 9.1.1 shows the perception-action-learning loop that is used to describe RL. The environment is a soda can sitting on the floor. The agent is a mobile robot whose goal is to pick up the soda can. It observes the environment around it and tracks the location of the soda can through an onboard camera. The observation is summarized in a form of state which the robot will use to decide which action to take. The actions it takes may pertain to low-level control such as the rotation angle/speed of each wheel, rotation angle/speed of each joint of the arm, and whether the gripper is open or close.

Alternatively, the actions may be high-level control moves such as moving the robot forward/backward, steering with a certain angle, and grab/release. Any action that moves the gripper away from the soda receives a negative reward. Any action that closes the gap between the gripper location and the soda receives a positive reward. When the robot...

The Q value

An important question is that if the RL problem is to find , how does the agent learn by interacting with the environment? Equation 9.1.3 does not explicitly indicate the action to try and the succeeding state to compute the return. In RL, we find that it's easier to learn by using the Q value:

(Equation 9.2.1)

Where:

(Equation 9.2.2)

In other words, instead of finding the policy that maximizes the value for all states, Equation 9.2.1 looks for the action that maximizes the quality (Q) value for all states. After finding the Q value function, V* and hence are determined by Equation 9.2.2 and 9.1.3 respectively.

If for every action, the reward and the next state can be observed, we can formulate the following iterative or trial and error algorithm to learn the Q value:

(Equation 9.2.3)

For notational simplicity, both s ' and a ' are the next state and action respectively. Equation 9.2.3 is known as the Bellman Equation which is the core...

Q-Learning example

To illustrate the Q-Learning algorithm, we need to consider a simple deterministic environment, as shown in the following figure. The environment has six states. The rewards for allowed transitions are shown. The reward is non-zero in two cases. Transition to the Goal (G) state has +100 reward while moving into Hole (H) state has -100 reward. These two states are terminal states and constitute the end of one episode from the Start state:

Figure 9.3.1: Rewards in a simple deterministic world

To formalize the identity of each state, we need to use a (row, column) identifier as shown in the following figure. Since the agent has not learned anything yet about its environment, the Q-Table also shown in the following figure has zero initial values. In this example, the discount factor, . Recall that in the estimate of current Q value, the discount factor determines the weight of future Q values as a function of the number of steps, . In Equation 9.2.3, we only consider the...

Q-Learning in Python

The environment and the Q-Learning discussed in the previous section can be implemented in Python. Since the policy is just a simple table, there is, at this point in time no need for Keras. Listing 9.3.1 shows q-learning-9.3.1.py, the implementation of the simple deterministic world (environment, agent, action, and Q-Table algorithms) using the QWorld class. For conciseness, the functions dealing with the user interface are not shown.

In this example, the environment dynamics is represented by self.transition_table. At every action, self.transition_table determines the next state. The reward for executing an action is stored in self.reward_table. The two tables are consulted every time an action is executed by the step() function. The Q-Learning algorithm is implemented by update_q_table() function. Every time the agent needs to decide which action to take, it calls the act() function. The action may be randomly drawn or decided by the policy using the Q-Table...

Nondeterministic environment

In the event that the environment is nondeterministic, both the reward and action are probabilistic. The new system is a stochastic MDP. To reflect the nondeterministic reward the new value function is:

(Equation 9.4.1)

The Bellman equation is modified as:

(Equation 9.4.2)

Temporal-difference learning

Q-Learning is a special case of a more generalized Temporal-Difference Learning or TD-Learning . More specifically, it's a special case of one-step TD-Learning TD(0):

(Equation 9.5.1)

In the equation is the learning rate. We should note that when , Equation 9.5.1 is similar to the Bellman equation. For simplicity, we'll refer to Equation 9.5.1 as Q-Learning or generalized Q-Learning.

Previously, we referred to Q-Learning as an off-policy RL algorithm since it learns the Q value function without directly using the policy that it is trying to optimize. An example of an on-policy one-step TD-learning algorithm is SARSA which similar to Equation 9.5.1:

(Equation 9.5.2)

The main difference is the use of the policy that is being optimized to determine a'. The terms s, a, r, s' and a' (thus the name SARSA) must be known to update the Q value function at every iteration. Both Q-Learning and SARSA use existing estimates...

Q-Learning on OpenAI gym

Before presenting another example, there appears to be a need for a suitable RL simulation environment. Otherwise, we can only run RL simulations on very simple problems like in the previous example. Fortunately, OpenAI created Gym, https://gym.openai.com.

The gym is a toolkit for developing and comparing RL algorithms. It works with most deep learning libraries, including Keras. The gym can be installed by running the following command:

$ sudo pip3 install gym

The gym has several environments where an RL algorithm can be tested against such as toy text, classic control, algorithmic, Atari, and 2D/3D robots. For example, FrozenLake-v0 (Figure 9.5.1) is a toy text environment similar to the simple deterministic world used in the Q-Learning in Python example. FrozenLake-v0 has 12 states. The state marked S is the starting state, F is the frozen part of the lake which is safe, H is the Hole state that should be avoided, and G is the Goal state where the frisbee...

Deep Q-Network (DQN)

Using the Q-Table to implement Q-Learning is fine in small discrete environments. However, when the environment has numerous states or continuous as in most cases, a Q-Table is not feasible or practical. For example, if we are observing a state made of four continuous variables, the size of the table is infinite. Even if we attempt to discretize the four variables into 1000 values each, the total number of rows in the table is a staggering 1000⁴ = 1e¹². Even after training, the table is sparse - most of the cells in this table are zero.

A solution to this problem is called DQN [2] which uses a deep neural network to approximate the Q-Table. As shown in Figure 9.6.1. There are two approaches to build the Q-network:

1. The input is the state-action pair, and the prediction is the Q value
2. The input is the state, and the prediction is the Q value for each action

The first option is not optimal since the network will be called a number of times equal to the number of...

DQN on Keras

To illustrate DQN, the CartPole-v0 environment of the OpenAI Gym is used. CartPole-v0 is a pole balancing problem. The goal is to keep the pole from falling over. The environment is 2D. The action space is made of two discrete actions (left and right movements). However, the state space is continuous and is made of four variables:

1. Linear position
2. Linear velocity
3. Angle of rotation
4. Angular velocity

The CartPole-v0 is shown in Figure 9.6.1.

Initially, the pole is upright. A reward of +1 is provided for every timestep that the pole remains upright. The episode ends when the pole exceeds 15 degrees from the vertical or 2.4 units from the center. The CartPole-v0 problem is considered solved if the average reward is 195.0 in 100 consecutive trials:

Figure 9.6.1: The CartPole-v0 environment

Listing 9.6.1 shows us the DQN implementation for CartPole-v0. The DQNAgent class represents the agent using DQN. Two Q-Networks are created:

1. Q-Network or Q in Algorithm 9.6.1
2. Target Q-Network or Q_target...

Double Q-Learning (DDQN)

In DQN, the target Q-Network selects and evaluates every action resulting in an overestimation of Q value. To resolve this issue, DDQN [3] proposes to use the Q-Network to choose the action and use the target Q-Network to evaluate the action.

In DQN as summarized by Algorithm 9.6.1, the estimate of the Q value in line 10 is:

Q_target chooses and evaluates the action a _j+1.

DDQN proposes to change line 10 to:

The term lets Q to choose the action. Then this action is evaluated by Q_target.

In Listing 9.6.1, both DQN and DDQN are implemented. Specifically, for DDQN, the modification on the Q value computation performed by get_target_q_value() function is highlighted:

# compute Q_max
# use of target Q Network solves the non-stationarity problem
def get_target_q_value(self, next_state):
    # max Q value among next state's actions
    if self.ddqn:
        # DDQN
        # current Q Network selects the action
        # a'_max = argmax_a' Q(s', a&apos...

Conclusion

In this chapter, we've been introduced to DRL. A powerful technique believed by many researchers as the most promising lead towards artificial intelligence. Together, we've gone over the principles of RL. RL is able to solve many toy problems, but the Q-Table is unable to scale to more complex real-world problems. The solution is to learn the Q-Table using a deep neural network. However, training deep neural networks on RL is highly unstable due to sample correlation and non-stationarity of the target Q-Network.

DQN proposed a solution to these problems using experience replay and separating the target network from the Q-Network under training. DDQN suggested further improvement of the algorithm by separating the action selection from action evaluation to minimize the overestimation of Q value. There are other improvements proposed for the DQN. Prioritized experience replay [6] argues that that experience buffer should not be sampled uniformly. Instead, experiences that...

References

1. Sutton and Barto. Reinforcement Learning: An Introduction, 2017 (http://incompleteideas.net/book/bookdraft2017nov5.pdf).
2. Volodymyr Mnih and others, Human-level control through deep reinforcement learning. Nature 518.7540, 2015: 529 (http://www.davidqiu.com:8888/research/nature14236.pdf)
3. Hado Van Hasselt, Arthur Guez, and David Silver Deep Reinforcement Learning with Double Q-Learning. AAAI. Vol. 16, 2016 (http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/download/12389/11847).
4. Kai Arulkumaran and others A Brief Survey of Deep Reinforcement Learning. arXiv preprint arXiv:1708.05866, 2017 (https://arxiv.org/pdf/1708.05866.pdf).
5. David Silver Lecture Notes on Reinforcement Learning, (http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html).
6. Tom Schaul and others. Prioritized experience replay. arXiv preprint arXiv:1511.05952, 2015 (https://arxiv.org/pdf/1511.05952.pdf).
7. Ziyu Wang and others. Dueling Network Architectures for Deep Reinforcement Learning. arXiv preprint arXiv:1511...