Deep reinforcement learning algorithms that estimate state and state-action value functions have been shown to be effective in a variety of challenging domains, including learning control strategies from raw image pixels. However, algorithms that estimate state and state-action value functions typically assume a fully observed state and must compensate for partial or non-Markovian observations by using finite-length frame-history observations or recurrent networks. In this work, we propose a new deep reinforcement learning algorithm based on counterfactual regret minimization that iteratively updates an approximation to a cumulative clipped advantage function and is robust to partially observed state. We demonstrate that on several partially observed reinforcement learning tasks, this new class of algorithms can substantially outperform strong baseline methods: on Pong with single-frame observations, and on the challenging Doom (ViZDoom) and Minecraft (Malmö) first-person navigation benchmarks. Many reinforcement learning problems of practical interest have the property of partial observability, where observations of state are generally non-Markovian. Despite the importance of partial observation in the real world, value function-based methods such as Q-learning (Mnih et al., 2013; BID6 generally assume a Markovian observation space. On the other hand, Monte Carlo policy gradient methods do not assume Markovian observations, but many practical policy gradient methods such as A3C (Mnih et al., 2016) introduce the Markov assumption when using a critic or state-dependent baseline in order to improve sample efficiency.Consider deep reinforcement learning methods that learn a state or state-action value function. One common workaround for the problem of partial observation is to learn value functions on the space of finite-length frame-history observations, under the assumption that frame-histories of sufficient length will give the environment the approximate appearance of full observability. When learning to play Atari 2600 games from images, deep Q-learning algorithms (Mnih et al., 2013; BID6 concatenate the last 4 observed frames of the video screen buffer as input to a state-action value convolutional network. Not all non-Markovian tasks are amenable to finite-length frame-histories; recurrent value functions can incorporate longer and potentially infinite histories BID12 BID8 , but at the cost of solving a harder optimization problem. Can we develop methods that learn a variant of the value function that is more robust to partial observability?Our contribution is a new model-free deep reinforcement learning algorithm based on the principle of regret minimization which does not require access to a Markovian state. Our method learns a policy by estimating a cumulative clipped advantage function, which is an approximation to a type of regret that is central to two partial information game-solving algorithms from which we draw our primary inspiration: counterfactual regret minimization (CFR) BID35 and CFR+ BID28 . Hence we call our algorithm "advantage-based regret minimization" (ARM).We evaluate our approach on three visual reinforcement learning domains: Pong with varying framehistory lengths BID2 , and the first-person games Doom BID16 and Minecraft BID15 . Doom and Minecraft exhibit a first-person viewpoint in a 3-dimensional environment and should appear non-Markovian even with frame-history observations. We find that our method offers substantial improvement over prior methods in these partially observ-able environments: on both Doom and Minecraft, our method can learn well-performing policies within about 1 million simulator steps using only visual input frame-history observations. In this paper, we presented a novel deep reinforcement learning algorithm based on counterfactual regret minimization (CFR). We call our method advantage-based regret minimization (ARM). Similarly to prior methods that learn state or state-action value functions, our method learns a cumulative clipped advantage function of observation and action. However, in contrast to these prior methods, ARM is well suited to partially observed or non-Markovian environments, making it an appealing choice in a number of difficult domains. When compared to baseline methods, including deep Q-learning and TRPO, on non-Markovian tasks such as the challenging ViZDoom and Malmö firstperson navigation benchmarks, ARM achieves substantially better results. This illustrates the value of ARM for partially observable problems. In future work, we plan to further explore applications of ARM to more complex tasks, including continuous action spaces.6 APPENDIX 6.1 EXPERIMENTAL DETAILS 6.1.1 PONG (ARCADE LEARNING ENVIRONMENT)We use the preprocessing and convolutional network model of (Mnih et al., 2013) . Specifically, we view every 4th emulator frame, convert the raw frames to grayscale, and perform downsampling to generate a single observed frame. The input observation of the convnet is a concatenation of the most recent frames (either 4 frames or 1 frame). The convnet consists of an 8 × 8 convolution with stride 4 and 16 filters followed by ReLU, a 4 × 4 convolution with stride 2 and 32 filters followed by ReLU, a linear map with 256 filters followed by ReLU, and a linear map with |A| filters where |A| is the action space cardinality (|A| = 6 for Pong).We used Adam with a constant learning rate of α = 10 −4 , a minibatch size of 32, and the moment decay rates set to their defaults β 1 = 0.9 and β 2 = 0.999. Our results on each method are averaged across 3 random seeds.We ran ARM with the hyperparameters: sampling batch size of 12500, 4000/3000 minibatches of Adam for the first/subsequent sampling iterations respectively, and target update step size τ = 0.01. Double DQN uses the tuned hyperparameters . Note that our choice of ARM hyperparameters yields an equivalent number of minibatch gradient updates per sample as used by DQN and double DQN, i.e. 1 minibatch gradient update per 4 simulator steps.
Advantage-based regret minimization is a new deep reinforcement learning algorithm that is particularly effective on partially observable tasks, such as 1st person navigation in Doom and Minecraft. This paper introduces the concepts of counterfactual regret minimization in the field of Deep RL and an algorithm called ARM which can deal with partial observability better. The paper provides a game-theoretic inspired variant of policy-gradient algorithm based on the idea of counter-factual regret minimization and claims that the approach can deal with the partial observable domain better than standard methods.