Deep Learning and Reinforcement Learning

Module 5
Deep Reinforcement Learning

Prepared By:
Dr. Rajesh Nayak
Associate Professor
Dept. of Artificial Intelligence and Data Science
 Contents
9. Deep Reinforcement Learning
– 9.1 Introduction
– 9.2 Stateless Algorithms: Multi-Armed Bandits
• 9.2.1 Naïve Algorithm
• 9.2.2 ϵ-Greedy Algorithm
• 9.2.3 Upper Bounding Methods
– 9.3 The Basic Framework of Reinforcement Learning
• 9.3.1 Challenges of Reinforcement Learning
• 9.3.2 Simple Reinforcement Learning for Tic-Tac-Toe
• 9.3.3 Role of Deep Learning and a Straw-Man Algorithm
– 9.7 Case Studies
• 9.7.1 AlphaGo: Championship Level Play at Go
• 9.7.2 Self-Learning Robots
• 9.7.3 Building Conversational Systems: Deep Learning for Chatbots
• 9.7.4 Self-Driving Cars
• 9.7.5 Inferring Neural Architectures with Reinforcement Learning 2
9. Deep Reinforcement Learning
• 9.1 Introduction
• Human beings do not learn from a concrete notion of training data.
Learning in humans is a continuous experience-driven process in which
decisions are made, and the reward/punishment received from the
environment are used to guide the learning process for future decisions.
• In other words, learning in intelligent beings is by reward-guided trial and
error.
• Furthermore, much of human intelligence and instinct is encoded in
genetics, which has evolved over millions of years with another
environment-driven process, referred to as evolution. Therefore, almost all
of biological intelligence, as we know it, originates in one form or other
through an interactive process of trial and error with the environment.
• Human beings are considered simple because they are one-dimensional,
selfish, and reward-driven entities (when viewed as a whole), and all of
biological intelligence is therefore attributable to this simple fact.

3
9.1 Introduction
• Since the goal of artificial intelligence is to simulate biological intelligence,
it is therefore natural to draw inspirations from the successes of biological
greed in simplifying the design of highly complex learning algorithms.
• A reward-driven trial-and-error process, in which a system learns to
interact with a complex environment to achieve rewarding outcomes, is
referred to in machine learning parlance as reinforcement learning.
• In reinforcement learning, the process of trial and error is driven by the
need to maximize the expected rewards over time.
• Reinforcement learning can be a gateway to the quest for creating truly
intelligent agents such as game-playing algorithms, self-driving cars, and
even intelligent robots that interact with the environment.

4
9.1 Introduction
1. Deep learners have been trained to play video games by using only the
raw pixels of the video console as feedback. A classical example of this
setting is the Atari 2600 console, which is a platform supporting multiple
games. The input to the deep learner from the Atari platform is the
display of pixels from the current state of the game. The reinforcement
learning algorithm predicts the actions based on the display and inputs
them into the Atari console. Initially, the computer algorithm makes many
mistakes, which are reflected in the virtual rewards given by the console.
As the learner gains experience from its mistakes, it makes better
decisions. This is exactly how humans learn to play video games.
2. DeepMind has trained a deep learning algorithm AlphaGo to play the
game of Go by using the reward-outcomes in the moves of games drawn
from both human and computer self-play. Go is a complex game that
requires significant human intuition, and the large tree of possibilities
(compared to other games like chess) makes it an incredibly difficult
candidate for building a game-playing algorithm. AlphaGo has not only
convincingly defeated all top-ranked Go players it has played against, but
has contributed to innovations in the style of human play by using
unconventional strategies in defeating these players. 5
9.1 Introduction
3. In recent years, deep reinforcement learning has been harnessed in
self-driving cars by using the feedback from various sensors around the
car to make decisions. Although it is more common to use supervised
learning (or imitation learning) in self-driving cars, the option of using
reinforcement learning has always been recognized as a viable possibility.
During the course of driving, these cars now consistently make fewer
errors than do human beings.
4. The quest for creating self-learning robots is a task in reinforcement
learning. For example, robot locomotion turns out to be surprisingly
difficult in nimble configurations. Teaching a robot to walk can be
couched as a reinforcement learning task, if we do not show a robot what
walking looks like. In the reinforcement learning paradigm, we only
incentivize the robot to get from point A to point B as efficiently as
possible using its available limbs and motors. Through reward-guided trial
and error, robots learn to roll, crawl, and eventually walk.

6
9.1 Introduction
• Reinforcement learning is appropriate for tasks that are simple to evaluate
but hard to specify. For example, it is easy to evaluate a player’s
performance at the end of a complex game like chess, but it is hard to
specify the precise action in every situation.
• As in biological organisms, reinforcement learning provides a path to the
simplification of learning complex behaviors by only defining the reward
and letting the algorithm learn reward-maximizing behaviors. The
complexity of these behaviors is automatically inherited from that of the
environment.
• The simplest example of a reinforcement learning setting is the
multi-armed bandit problem, which addresses the problem of a gambler
choosing one of many slot machines in order to maximize his payoff. The
gambler suspects that the (expected) rewards from the various slot
machines are not the same, and therefore it makes sense to play the
machine with the largest expected reward. Since the expected payoffs of
the slot machines are not known in advance, the gambler has to explore
different slot machines by playing them and also exploit the learned
knowledge to maximize the reward. 7
9.2 Stateless Algorithms: Multi-Armed Bandits
• The simplest example of a reinforcement learning setting is the
multi-armed bandit problem, which addresses the problem of a gambler
choosing one of many slot machines in order to maximize his payoff.
• The gambler suspects that the (expected) rewards from the various slot
machines are not the same, and therefore it makes sense to play the
machine with the largest expected reward.
• Since the expected payoffs of the slot machines are not known in advance,
the gambler has to explore different slot machines by playing them and
also exploit the learned knowledge to maximize the reward.
• Although exploration of a particular slot machine might gain some
additional knowledge about its payoff, it incurs the risk of the (potentially
fruitless) cost of playing it.
• Multi-armed bandit algorithms provide carefully crafted strategies to
optimize the trade-off between exploration and exploitation.
• However, in this simplified setting, each decision of choosing a slot
machine is identical to the previous one.

8
9.2 Stateless Algorithms: Multi-Armed Bandits

9
9.2 Stateless Algorithms: Multi-Armed Bandits
• We revisit the problem of a gambler who repeatedly plays slot machines
based on previous experience.
• The gambler suspects that one of the slot machines has a better expected
reward than others and attempts to both explore and exploit his
experience with the slot machines. Trying the slot machines randomly is
wasteful but helps in gaining experience.
• Trying the slot machines for a very small number of times and then always
picking the best machine might lead to solutions that are poor in the
long-term.
• How should one navigate this trade-off between exploration and
exploitation? Note that every trial provides the same probabilistically
distributed reward as previous trials for a given action, and therefore there
is no notion of state in such a system.
• This is a simplified case of traditional reinforcement learning in which the
notion of state is important. In a computer video game, moving the cursor
in a particular direction has a reward that heavily depends on the state of
the video game.
10
9.2 Stateless Algorithms: Multi-Armed Bandits
• There are a number of strategies that the gambler can use to regulate the
trade-off between exploration and exploitation of the search space.
• In the following, we will briefly describe some of the common strategies
used in multi-armed bandit systems. All these methods are instructive
because they provide the basic ideas and framework, which are used in
generalized settings of reinforcement learning.
• In fact, some of these stateless algorithms are also used as subroutines in
general forms of reinforcement learning. Therefore, it is important to
explore this simplified setting.

11
9.2 Stateless Algorithms: Multi-Armed Bandits
• 9.2.1 Naïve Algorithm
• In this approach, the gambler plays each machine for a fixed number of
trials in the exploration phase. Subsequently, the machine with the highest
payoff is used forever in the exploitation phase.
• Although this approach might seem reasonable at first sight, it has a
number of drawbacks. The first problem is that it is hard to determine the
number of trials at which one can confidently predict whether a particular
slot machine is better than another machine.
• The process of estimation of payoffs might take a long time, especially in
cases where the payoff events are rare compared to non-payoff events.
Using many exploratory trials will waste a significant amount of effort on
suboptimal strategies.
• Furthermore, if the wrong strategy is selected in the end, the gambler will
use the wrong slot machine forever. Therefore, the approach of fixing a
particular strategy forever is unrealistic in real-world problems.

12
9.2 Stateless Algorithms: Multi-Armed Bandits
• 9.2.2 ϵ-Greedy Algorithm
• The ϵ-greedy algorithm is designed to use the best strategy as soon as
possible, without wasting a significant number of trials. The basic idea is to
choose a random slot machine for a fraction ϵ of the trials.
• These exploratory trials are also chosen at random (with probability ϵ)
from all trials, and are therefore fully interleaved with the exploitation
trials. In the remaining (1− ϵ) fraction of the trials, the slot machine with the
best average payoff so far is used.
• An important advantage of this approach is that one is guaranteed to not
be trapped in the wrong strategy forever. Furthermore, since the
exploitation stage starts early, one is often likely to use the best strategy a
large fraction of the time.
• The value of ϵ is an algorithm parameter. For example, in practical settings,
one might set ϵ = 0.1, although the best choice of ϵ will vary with the
application at hand.
• It is often difficult to know the best value of ϵ to use in a particular setting.
13
9.2 Stateless Algorithms: Multi-Armed Bandits
• 9.2.2 ϵ-Greedy Algorithm
• Nevertheless, the value of ϵ needs to be reasonably small in order to gain
significant advantages from the exploitation portion of the approach.
However, at small values of ϵ it might take a long time to identify the
correct slot machine. A common approach is to use annealing, in which
large values of ϵ are initially used, with the values declining with time.
• 9.2.3 Upper Bounding Methods
• Even though ϵ-Greedy strategy is better than the naïve strategy in dynamic
settings, it is still quite inefficient at learning the payoffs of new slot
machines.
• In upper bounding strategies, the gambler does not use the mean payoff
of a slot machine. Rather, the gambler takes a more optimistic view of slot
machines that have not been tried sufficiently, and therefore uses a slot
machine with the best statistical upper bound on the payoff.
• Therefore one can consider the upper bound Ui of testing a slot machine i
as the sum of expected reward Qi and one-sided confidence interval length
C i: Ui = Q i + C i
14
• 9.2.3 Upper Bounding Methods
• The value of Ci is like a bonus for increased uncertainty about that slot
machine in the mind of the gambler. The value Ci is proportional to the
standard deviation of the mean reward of the tries so far.
• According to the central limit theorem, this standard deviation is inversely
proportional to the square-root of the number of times the slot machine i
is tried. One can estimate the mean μi and standard deviation σi of the ith
slot machine and then set Ci to be K · σi/√ni, where ni is the number of
times the ith slot machine has been tried. Here, K decides the level of
confidence interval.
• Therefore, rarely tested slot machines will tend to have larger upper
bounds (because of larger confidence intervals Ci) and will therefore be
tried more frequently.
• Unlike ϵ-Greedy, the trials are no longer divided into two categories of
exploration and exploitation; the process of selecting the slot machine with
the largest upper bound has the dual effect of encoding both the
exploration and exploitation aspects within each trial. One can regulate the
trade-off between exploration and exploitation by using a specific level of
statistical confidence. The choice of K = 3 leads to a 99.99% confidence
interval for the upper bound under the Gaussian assumption. 15
9.3 The Basic Framework of Reinforcement Learning
• The bandit algorithms of the previous section are stateless. In other words,
the decision made at each time stamp has an identical environment, and
the actions in the past only affect the knowledge of the agent (not the
environment itself). This is not the case in generic reinforcement learning
settings like video games or self-driving cars, which have a notion of state.
• In generic reinforcement learning settings, each action is associated with a
reward in isolation. While playing a video game, you do not get a reward
only because you made a particular move. The reward of a move depends
on all the other moves you made in the past, which are incorporated in the
state of the environment.
• In a video game or self-driving car, we would need a different way of
performing the credit assignment in a particular system state. For
example, in a self-driving car, the reward for violently swerving a car in a
normal state would be different from that of performing the same action in
a state that indicates the danger of a collision. In other words, we need a
way to quantify the reward of each action in a way that is specific to a
particular system state.
16
9.3 The Basic Framework of Reinforcement Learning
• In reinforcement learning, we have an agent that interacts with the
environment with the use of actions. For example, the player is the agent
in a video game, and moving the joystick in a certain direction in a video
game is an action. The environment is the entire set up of the video game
itself. These actions change the environment and lead to a new state.
• In a video game, the state represents all the variables describing the
current position of the player at a particular point. The environment gives
the agent rewards, depending on how well the goals of the learning
application are being met.
• For example, scoring points in a video game is a reward. Note that the
rewards may sometimes not be directly associated with a particular action,
but with a combination of actions taken some time back. For example, the
player might have cleverly positioned a cursor at a particularly convenient
point a few movies back, and actions since then might have had no bearing
on the reward.
• One of the primary goals of reinforcement learning is to identify the inherent
values of actions in different states, irrespective of the timing and stochasticity
of the reward. 17
9.3 The Basic Framework of Reinforcement Learning

18
9.3 The Basic Framework of Reinforcement Learning
• The learning process helps the agent choose actions based on the inherent
values of the actions in different states. This general principle applies to all
forms of reinforcement learning in biological organisms, such as a mouse
learning a path through a maze to earn a reward.
• The rewards earned by the mouse depend on an entire sequence of
actions, rather than on only the latest action. When a reward is earned, the
synaptic weights in the mouse’s brain adjust to reflect how sensory inputs
should be used to decide future actions in the maze.
• This is exactly the approach used in deep reinforcement learning, where a
neural network is used to predict actions from sensory inputs (e.g., pixels
of video game). This relationship between the agent and the environment
is shown in Figure 9.1.
• The entire set of states and actions and rules for transitioning from one
state to another is referred to as a Markov decision process. The main
property of a Markov decision process is that the state at any particular
time stamp encodes all the information needed by the environment to
make state transitions and assign rewards based on agent actions.
19
9.3 The Basic Framework of Reinforcement Learning
• Finite Markov decision processes (e.g., tic-tac-toe) terminate in a finite
number of steps, which is referred to as an episode.
• A particular episode of this process is a finite sequence of actions, states,
and rewards. An example of length (n + 1) is the following:
s0a0r0s1a1r1 . . . statrt . . . Snanrn

• Note that st is the state before performing action at, and performing the
action at causes a reward of rt and transition to state st+1.
• Infinite Markov decision processes (e.g., continuously working robots) do
not have finite length episodes and are referred to as non-episodic.

20
9.3 The Basic Framework of Reinforcement Learning

21
9.3.1 Challenges of Reinforcement Learning

22
9.3.2 Simple Reinforcement Learning for Tic-Tac-Toe
• Reinforcement learning can be applied to the game of Tic-Tac-Toe by
extending the ε-greedy algorithm. In this setup, each board position
represents a state, and an action means placing an ‘X’ or an ‘O’ in any valid
position.
• Since every cell on the 3×3 board can have three possibilities (‘X’, ‘O’, or
blank), the total number of valid states is bounded by 3⁹ = 19,683.
• Instead of estimating the value of a single action as in multi-armed bandits,
here the algorithm learns the value of each state–action pair (s, a).
• This value depends on how successful an action is in a given board state.
The learning process prefers shorter wins, which is controlled using a
discount factor γ < 1. If a win occurs after r moves, the value of that action
increases by γr-1, while for a loss it decreases by –γr-1.
• Draws are given a value of zero. The discount factor ensures that earlier
actions have a stronger effect than later ones.

23
9.3.2 Simple Reinforcement Learning for Tic-Tac-Toe
• The values are stored in a table, which is updated after each game ends. To
get the normalized value, the total accumulated value of each state–action
pair is divided by the number of times it has been visited.
• The table starts with small random values. During play, the ε-greedy
strategy is used — with probability (1 – ε), the action with the highest
normalized value is chosen, and with probability ε, a random valid move is
selected.
• As more games are played, the algorithm gradually learns the best moves
by updating the state–action values based on the outcomes.
• The approach can also use self-play, where the agent plays against itself
instead of a fixed opponent. In self-play, values are updated as γ r, 0, or –γr
for win, draw, and loss respectively.
• During actual gameplay, the move with the highest normalized value is
chosen, leading the agent to learn optimal strategies over time.

24
9.3.3 Role of Deep Learning and Straw-Man Algorithm
• The tic-tac-toe learning algorithm used earlier was based on tabulating
state–action values without using neural networks. However, in many
real-world reinforcement learning problems, the number of possible states
is extremely large, making it impossible to explicitly store all state–action
pairs in a table.
• The main goal of reinforcement learning is to discover the long-term value
of actions in different states. In games like tic-tac-toe, some moves may not
give an immediate reward but may create a trap that ensures victory later.
Such strategically valuable moves are credited with higher values in the
state–action table after repeated trial-and-error play.
• This table-based approach works for simple games but becomes infeasible
in complex environments like chess, where the total number of valid board
positions is extremely high. In such cases, reinforcement learning must
generalize knowledge from known experiences to new, unseen states.
• Deep learning provides this generalization ability. Instead of maintaining a
large table of all possible moves, a neural network is trained to
approximate the value of an action based on the input state.
25
9.3.3 Role of Deep Learning and Straw-Man Algorithm
• The network learns from the outcomes of previous games and adjusts its
parameters through backpropagation.
• A simple or “straw-man” algorithm for chess can use the same ε-greedy
reinforcement learning logic as in tic-tac-toe but replaces the table with a
convolutional neural network (CNN). The board position is fed as input,
and the output gives the estimated value of the move. Depending on
whether the move leads to a win, draw, or loss, the network parameters
are updated accordingly.
• Although this basic neural network–based approach is naive, more
advanced systems like AlphaZero combine reinforcement learning with
Monte Carlo Tree Search (MCTS) to achieve world-class performance in
chess and Go.
• AlphaZero learns strategic depth, even sacrificing short-term material for
long-term positional advantages—something traditional rule-based
programs could not do.
• In real-world tasks such as robotics or self-driving cars, the system’s state
often comes from sensory inputs like images or signals.
26
9.3.3 Role of Deep Learning and Straw-Man Algorithm
• Deep neural networks can extract meaningful features from these raw
inputs to evaluate actions effectively, much like how humans use visual
and sensory cues to make decisions.
• Thus, deep learning transforms the reinforcement learning process from a
memory-based lookup table to a parameterized model that maps states
and actions to their long-term values. This makes reinforcement learning
scalable and applicable to complex, real-world environments.

27
9.7 Case Studies
9.7.1 AlphaGo: Championship Level Play at Go
• Go is a two-person board game like chess. The complexity of a two-person
board game largely depends on the size of the board and the number of
valid moves at each position.
• The simplest example of a board game is tic-tac-toe with a 3 × 3 board, and
most humans can solve it optimally without the need for a computer.
• Chess is a significantly more complex game with an 8 × 8 board, although
clever variations of the brute-force approach of selectively exploring the
minimax tree of moves up to a certain depth can perform significantly
better than the best human today.
• Go occurs at the extreme end of complexity because of its 19 × 19 board.
• Players play with white or black stones, which are kept in bowls next to the
Go board. An example of a Go board is shown in Figure 9.7.
• The game starts with an empty board, and it fills up as players put stones
on the board. Black makes the first move and starts with 181 stones in her
bowl, whereas white starts with 180 stones.

28
9.7.1 AlphaGo: Championship Level Play at Go
• The total number of junctions is equal to the total number of stones in the
bowls of the two players. A player places a stone of her color in each move
at a particular position (from the bowl), and does not move it once it is
placed.
• A stone of the opponent can be captured by encircling it. The objective of
the game is for the player to control a larger part of the board than her
opponent by encircling it with her stones.

29
9.7.1 AlphaGo: Championship Level Play at Go

• Whereas one can make about 35 possible moves (i.e., tree branch factor) in
a particular position in chess, the average number of possible moves at a
particular position in Go is 250, which is almost an order of magnitude
larger.
• Furthermore, the average number of sequential moves (i.e., tree depth) of
a game of Go is about 150, which is around twice as large as chess. All
these aspects make Go a much harder candidate from the perspective of
automated game-playing.
• The typical strategy of chess-playing software is to construct a minimax
tree with all combinations of moves the players can make up to a certain
depth, and then evaluate the final board positions with chess-specific
heuristics (such as the amount of remaining material and the safety of
various pieces).
• Suboptimal parts of the tree are pruned in a heuristic manner. This
approach is simply a improved version of a brute-force strategy in which all
possible positions are explored up to a given depth.

30
9.7.1 AlphaGo: Championship Level Play at Go
• The number of nodes in the minimax tree of Go is larger than the number
of atoms in the observable universe, even at modest depths of analysis (20
moves for each player).
• As a result of the importance of spatial intuition in these settings, humans
always perform better than brute force strategies at Go.
• The use of reinforcement learning in Go is much closer to what humans
attempt to do.
• We rarely try to explore all possible combinations of moves; rather, we
visually learn patterns on the board that are predictive of advantageous
positions, and try to make moves in directions that are expected to
improve our advantage.
• The automated learning of spatial patterns that are predictive of good
performance is achieved with a convolutional neural network. The state of
the system is encoded in the board position at a particular point, although
the board representation in AlphaGo includes some additional features
about the status of junctions or the number of moves since a stone was
played.
31
9.7.1 AlphaGo: Championship Level Play at Go
• Multiple such spatial maps are required in order to provide full knowledge
of the state.
• For example, one feature map would represent the status of each
intersection, another would encode the number of turns since a stone was
played, and so on. Integer feature maps were encoded into multiple
one-hot planes. Altogether, the game board could be represented using 48
binary planes of 19 × 19 pixels.
• AlphaGo uses its win-loss experience with repeated game playing (both
using the moves of expert players and with games played against itself) to
learn good policies for moves in various positions with a policy network.
• Furthermore, the evaluation of each position on the Go board is achieved
with a value network. Subsequently, Monte Carlo tree search is used for
final inference.
• AlphaGo is a multi-stage model, whose components are: Policy Networks,
Value Networks, and Monte Carlo Tree Search.

32
9.7.1 AlphaGo: Championship Level Play at Go
• Policy Networks:
• The policy network takes as its input the aforementioned visual
representation of the board, and outputs the probability of action a in
state s.
• This output probability is denoted by p(s, a). Note that the actions in the
game of Go correspond to the probability of placing a stone at each legal
position on the board.
• Therefore, the output layer uses the softmax activation. Two separate
policy networks are trained using different approaches. The two networks
were identical in structure, containing convolutional layers with ReLU
nonlinearities.
• Each network contained 13 layers. Most of the convolutional layers
convolve with 3 × 3 filters, except for the first and final convolutions. The
first and final filters convolve with 5 × 5 and 1 × 1 filters, respectively.
• The convolutional layers were zero padded to maintain their size, and 192
filters were used. The ReLU nonlinearity was used, and no maxpooling was
used in order to maintain the spatial footprint.
33
9.7.1 AlphaGo: Championship Level Play at Go
• Policy Networks:
• The networks were trained in the following two ways:
– Supervised learning: Randomly chosen samples from expert players were used as
training data. The input was the state of the network, while the output was the action
performed by the expert player. The score (advantage) of such a move was always +1,
because the goal was to train the network to imitate expert moves, which is also referred
to as imitation learning. Therefore, the neural network was backpropagated with the
log-likelihood of the probability of the chosen move as its gain. This network is referred
to as the SL-policy network. It is noteworthy that these supervised forms of imitation
learning are often quite common in reinforcement learning for avoiding cold-start
problems.
– Reinforcement learning: In this case, reinforcement learning was used to train the
network. One issue is that Go needs two opponents, and therefore the network was
played against itself in order to generate the moves. The current network was always
played against a randomly chosen network from a few iterations back, so that the
reinforcement learning could have a pool of randomized opponents. The game was
played until the very end, and then an advantage of +1 or −1 was associated with each
move depending on win or loss. This data was then used to train the policy network. This
network was referred to as the RL-policy network.

34
9.7.1 AlphaGo: Championship Level Play at Go
• Value Networks:
• This network was also a convolutional neural network, which uses the state
of the network as the input and the predicted score in [−1, +1] as output,
where +1 indicates a perfect probability of 1.
• The output is the predicted score of the next player, whether it is white or
black, and therefore the input also encodes the “color” of the pieces in
terms of “player” or “opponent” rather than white or black.
• The architecture of the value network was very similar to the policy
network, except that there were some differences in terms of the input
and output.
• The input contained an additional feature corresponding to whether the
next player to play was white or black. The score was computed using a
single tanh unit at the end, and therefore the value lies in the range [−1,
+1].
• The early convolutional layers of the value network are the same as those
in the policy network, although an additional convolutional layer is added
in layer 12. A fully connected layer with 256 units and ReLU activation
follows the final convolutional layer. In order to train the network, one
possibility is to use positions from a data set of Go games. 35
9.7.1 AlphaGo: Championship Level Play at Go
• Value Networks:
• However, the preferred choice was to generate the data set using self-play
with the SL-policy and RL-policy networks all the way to the end, so that the
final outcomes were generated.
• The state-outcome pairs were used to train the convolutional neural
network. Since the positions in a single game are correlated, using them
sequentially in training causes overfitting.
• It was important to sample positions from different games in order to
prevent overfitting caused by closely related training examples. Therefore,
each training example was obtained from a distinct game of self-play.
• Monte Carlo Tree Search:
• In the case of AlphaGo, two approaches are combined. First, fast Monte
Carlo rollouts were used from the leaf node to create evaluation e1.
• While it is possible to use the policy network for rollout, AlphaGo trained a
simplified softmax classifier with a database of human games and some
hand-crafted features for faster speed of rollouts.

36
9.7.1 AlphaGo: Championship Level Play at Go
• Monte Carlo Tree Search:
• Second, the value network created a separate evaluation e2 of the leaf
nodes. The final evaluation e is a convex combination of the two
evaluations as e = βe1 +(1−β)e2. The value of β = 0.5 provided the best
performance, although using only the value network also provided closely
matching performance (and a viable alternative).
• The most visited branch in Monte Carlo tree search was reported as the
predicted move.

37