Deep Reinforcement Learning in Large Discrete Action Spaces

Deep Reinforcement Learning in Large Discrete Action Spaces

Gabriel Dulac-Arnold*, Richard Evans*, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap, Jonathan Hunt,

Timothy Mann, Theophane Weber, Thomas Degris, Ben Coppin DULACARNOLD@GOOGLE.COM

Google DeepMind

Abstract

Being able to reason in an environment with a

large number of discrete actions is essential to

bringing reinforcement learning to a larger class

of problems. Recommender systems, industrial

size of the set are both necessary to handle such

tasks. Current approaches are not able to provide

both of these, which motivates the work in this

paper. Our proposed approach leverages prior

information about the actions to embed them in

a continuous space upon which it can general-

ize. Additionally, approximate nearest-neighbor

methods allow for logarithmic-time lookup com-

plexity relative to the number of actions, which is

necessary for time-wise tractable training. This

1. Introduction

Advanced AI systems will likely need to reason with a large

number of possible actions at every step. Recommender

systems used in large systems such as YouTube and Ama-

zon must reason about hundreds of millions of items every

second, and control systems for large industrial processes

may have millions of possible actions that can be applied

at every time step. All of these systems are fundamentally

*Equal contribution.

reinforcement learning (Sutton & Barto, 1998) problems,

but current algorithms are difficult or impossible to apply.

our action set. Our policy produces a continuous action

within this space, and then uses an approximate nearest-

neighbor search to find the set of closest discrete actions

in logarithmic time. We can either apply the closest ac-

tion in this set directly to the environment, or fine-tune this

selection by selecting the highest valued action in this set

relative to a cost function. This approach allows for gen-

eralization over the action set in logarithmic time, which is

necessary for making both learning and acting tractable in

time.

2. Definitions

We consider a Markov Decision Process (MDP) where A is

the set of discrete actions, S is the set of discrete states, P :

S ×A×S → R is the transition probability distribution,

R : S ×A → R is the reward function, and γ ∈ [0, 1] is

a discount factor for future rewards. Each action a ∈ A

corresponds to an n-dimensional vector, such that a ∈ R

n

.

This vector provides information related to the action. In

the same manner, each state s ∈ S is a vector s ∈ R

.

policy π : S → A which maximizes the expected return

over all episodes, E[R

]. The state-action value function

Q

(s, a) = E[R

π

X

In this paper, both Q and π are approximated by

parametrized functions.

3. Problem Description

There are two primary families of policies often used in RL

systems: value-based, and actor-based policies.

For value-based policies, the policy’s decisions are directly

In the common case that the value function is a parame-

terized function which takes both state and action as input,

|A| evaluations are necessary to choose an action. This

quickly becomes intractable, especially if the parameter-

ized function is costly to evaluate, as is the case with deep

neural networks. This approach does, however, have the

desirable property of being capable of generalizing over

actions when using a smooth function approximator. If a

i

and a

are similar, learning about a

will also inform us

ders this approach intractable when the number of actions

grows significantly.

In a standard actor-critic approach, the policy is explicitly

defined by a parameterized actor function: π

In practice π

tor, which scale linearly in relation to the number of ac-

tions. However, actor-based architectures avoid the com-

putational cost of evaluating a likely costly Q-function on

handle the tasks we interest ourselves with. Current ap-

proaches are not able to provide both of these, which moti-

vates the approach described in this paper.

Our architecture reasons over actions within a continuous

space R

these cases, simply selecting the closest element to

ˆ

a from

the set of actions generated previously is not ideal.

To avoid picking these outlier actions, and to generally im-

prove the finally emitted action, the second phase of the

algorithm, which is described by the top part of Figure 1,

refines the choice of action by selecting the highest-scoring

action according to Q

θ

:

This equation is described more explicitly in Algorithm 1.

It introduces π

parameter θ represents both the parameters of the action

generation element in θ

π

and of the critic in θ

ing our system learn in certain domains. The size of the

θ

sider the training of a simpler policy, one defined only as

˜π

θ

θ

. In this initial case we can consider that the

policy is f

and that the effects of g are a deterministic

aspect of the environment. This allows us to maintain a

(2) can be seen as introducing a non-stationary aspect to the

environmental dynamics.

4.4. Wolpertinger Training

The training algorithm’s goal is to find a parameterized

policy π

episode’s length. To do this, we find a parametrization θ

of our policy which maximizes its expected return over an

both f

inducing aspects of Deep Q-Networks (Mnih et al., 2015)

to extend Deterministic Policy Gradient (Silver et al., 2014)

to neural network function approximators by introducing a

replay buffer (Lin, 1992) and target networks. DPG is sim-

ilar to work introduced by NFQCA (Hafner & Riedmiller,

The critic is trained from samples stored in a replay buffer

(Mnih et al., 2015). Actions stored in the replay buffer are

generated by π

taken at

(s). This allows the learning algorithm to

action in the Q-update is generated by the full policy π

and not simply f

A detailed description of the algorithm is available in the