A system for training a deep neural network used to control an agent that interacts with an environment by performing actions selected from a predetermined set of actions, wherein the environment is a real-world environment and the agent is a mechanical agent interacting with the real-world environment, the deep neural network comprising a policy neural network having a plurality of policy parameters and a baseline neural network having a plurality of baseline parameters, wherein the baseline neural network is a neural network that is configured to receive an input observation and to generate a baseline score that represents an estimated long-term reward received by the agent starting from the state characterized by the input observation, the system comprising one or more computers configured to implement a plurality of workers, wherein each worker is configured to operate independently of each other worker, wherein each worker is associated with a respective actor that interacts with a respective replica of the environment during the training of the deep neural network, and wherein each worker is further configured to repeatedly perform operations comprising: determining current values of the parameters of the deep neural network, comprising: receiving, from a shared memory accessible by all of the workers, current values of the baseline parameters of the baseline neural network; and receiving, from the shared memory, current values of the policy parameters of the policy neural network; until the environment replica interacted with by the actor associated with the worker transitions into a state that satisfies particular criteria, wherein the particular criteria comprise one of: receiving a predetermined number of observations and reaching a predetermined terminal state: receiving observations characterizing states of the environment replica and, in response to each observation, selecting an action to be performed by the actor associated with the worker in response to the observation in accordance with a respective action selection policy for the worker, wherein the selecting comprises, for each observation: processing the observation using the policy neural network and in accordance with the current values of the parameters of the policy neural network to generate a respective score for each action in the predetermined set of actions in accordance with the current values of the policy parameters of the policy neural network, and selecting the action to be performed by the actor in response to the observation using the respective scores; for each observation received before the particular criteria are satisfied: generating, based on the current values of the parameters of the baseline network, a baseline score representing an estimated reward received by the agent starting from a state characterized by the observation; identifying an actual reward resulting from the actor performing the selected action in response to the observation; determining an actual long-term reward from at least the actual reward and a baseline score for the observation characterizing the terminal state that satisfies the particular criteria; and performing an iteration of a reinforcement learning technique to determine a respective current gradient using gradients for the baseline and policy networks based on the baseline score and the actual long-term reward; updating respective accumulated gradients for the baseline and policy networks based on respective current gradient updates to determine respective updated accumulated gradients; determining whether criteria for updating the current values of the parameters of the deep neural network have been satisfied; and when the criteria for updating the current values of the parameters of the deep neural network have been satisfied: updating the parameters of the deep neural network, wherein the updating comprises: determining updated values of the parameters using the updated accumulated gradients, and storing the updated values in the shared memory accessible to all of the plurality of workers. processing the observation using the policy neural network and in accordance with the current values of the parameters of the policy neural network to generate a respective score for each action in the predetermined set of actions in accordance with the current values of the policy parameters of the policy neural network, and selecting the action to be performed by the actor in response to the observation using the respective scores; generating, based on the current values of the parameters of the baseline network, a baseline score representing an estimated reward received by the agent starting from a state characterized by the observation; identifying an actual reward resulting from the actor performing the selected action in response to the observation; determining an actual long-term reward from at least the actual reward and a baseline score for the observation characterizing the terminal state that satisfies the particular criteria; and performing an iteration of a reinforcement learning technique to determine a respective current gradient using gradients for the baseline and policy networks based on the baseline score and the actual long-term reward; determining updated values of the parameters using the updated accumulated gradients, and storing the updated values in the shared memory accessible to all of the plurality of workers.