Title: RL 2 : FAST REINFORCEMENT LEARNING VIA SLOW REINFORCEMENT LEARNING

Abstract: Deep reinforcement learning (deep RL) has been successful in learning sophisticated behaviors automatically; however, the learning process requires a huge number of trials. In contrast, animals can learn new tasks in just a few trials, benefiting from their prior knowledge about the world. This paper seeks to bridge this gap. Rather than designing a "fast" reinforcement learning algorithm, we propose to represent it as a recurrent neural network (RNN) and learn it from data. In our proposed method, RL 2 , the algorithm is encoded in the weights of the RNN, which are learned slowly through a general-purpose ("slow") RL algorithm. The RNN receives all information a typical RL algorithm would receive, including observations, actions, rewards, and termination flags; and it retains its state across episodes in a given Markov Decision Process (MDP). The activations of the RNN store the state of the "fast" RL algorithm on the current (previously unseen) MDP. We evaluate RL 2 experimentally on both small-scale and large-scale problems. On the small-scale side, we train it to solve randomly generated multi-armed bandit problems and finite MDPs. After RL 2 is trained, its performance on new MDPs is close to human-designed algorithms with optimality guarantees. On the largescale side, we test RL 2 on a vision-based navigation task and show that it scales up to high-dimensional problems.

1. INTRODUCTION:

In recent years, deep reinforcement learning has achieved many impressive results, including playing Atari games from raw pixels (Guo et al., 2014; Mnih et al., 2015; Schulman et al., 2015) , and acquiring advanced manipulation and locomotion skills (Levine et al., 2016; Lillicrap et al., 2015; Watter et al., 2015; Heess et al., 2015b; Schulman et al., 2015; 2016) . However, many of the successes come at the expense of high sample complexity. For example, the state-of-the-art Atari results require tens of thousands of episodes of experience (Mnih et al., 2015) per game. To master a game, one would need to spend nearly 40 days playing it with no rest. In contrast, humans and animals are capable of learning a new task in a very small number of trials. Continuing the previous example, the human player in Mnih et al. (2015) only needed 2 hours of experience before mastering a game. We argue that the reason for this sharp contrast is largely due to the lack of a good prior, which results in these deep RL agents needing to rebuild their knowledge about the world from scratch.

Although Bayesian reinforcement learning provides a solid framework for incorporating prior knowledge into the learning process (Strens, 2000; Ghavamzadeh et al., 2015; Kolter & Ng, 2009) , exact computation of the Bayesian update is intractable in all but the simplest cases. Thus, practical reinforcement learning algorithms often incorporate a mixture of Bayesian and domain-specific ideas to bring down sample complexity and computational burden. Notable examples include guided policy search with unknown dynamics (Levine & Abbeel, 2014) and PILCO (Deisenroth & Rasmussen, 2011) . These methods can learn a task using a few minutes to a few hours of real experience, compared to days or even weeks required by previous methods (Schulman et al., 2015; 2016; Lillicrap et al., 2015) . However, these methods tend to make assumptions about the environment (e.g., instrumentation for access to the state at learning time), or become computationally intractable in high-dimensional settings (Wahlström et al., 2015) .

Rather than hand-designing domain-specific reinforcement learning algorithms, we take a different approach in this paper: we view the learning process of the agent itself as an objective, which can be optimized using standard reinforcement learning algorithms. The objective is averaged across all possible MDPs according to a specific distribution, which reflects the prior that we would like to distill into the agent. We structure the agent as a recurrent neural network, which receives past rewards, actions, and termination flags as inputs in addition to the normally received observations. Furthermore, its internal state is preserved across episodes, so that it has the capacity to perform learning in its own hidden activations. The learned agent thus also acts as the learning algorithm, and can adapt to the task at hand when deployed.

We evaluate this approach on two sets of classical problems, multi-armed bandits and tabular MDPs. These problems have been extensively studied, and there exist algorithms that achieve asymptotically optimal performance. We demonstrate that our method, named RL 2 , can achieve performance comparable with these theoretically justified algorithms. Next, we evaluate RL 2 on a vision-based navigation task implemented using the ViZDoom environment (Kempka et al., 2016) , showing that RL 2 can also scale to high-dimensional problems.

2. METHOD:



2.1. PRELIMINARIES:

We define a discrete-time finite-horizon discounted Markov decision process (MDP) by a tuple M = (S, A, P, r, ρ 0 , γ, T ), in which S is a state set, A an action set, P :

S × A × S → R + a transition probability distribution, r : S × A → [-R max , R max ] a bounded reward function, ρ 0 : S → R + an initial state distribution, γ ∈ [0, 1] a discount

factor, and T the horizon. In policy search methods, we typically optimize a stochastic policy π θ : S × A → R + parametrized by θ. The objective is to maximize its expected discounted return, η(π

θ ) = E τ [ T t=0 γ t r(s t , a t )],

where τ = (s 0 , a 0 , . . .) denotes the whole trajectory, s 0 ∼ ρ 0 (s 0 ), a t ∼ π θ (a t |s t ), and s t+1 ∼ P(s t+1 |s t , a t ).

2.2. FORMULATION:

We now describe our formulation, which casts learning an RL algorithm as a reinforcement learning problem, and hence the name RL 2 .

We assume knowledge of a set of MDPs, denoted by M, and a distribution over them: ρ M : M → R + . We only need to sample from this distribution. We use n to denote the total number of episodes allowed to spend with a specific MDP. We define a trial to be such a series of episodes of interaction with a fixed MDP. This process of interaction between an agent and the environment is illustrated in Figure 1 . Here, each trial happens to consist of two episodes, hence n = 2. For each trial, a separate MDP is drawn from ρ M , and for each episode, a fresh s 0 is drawn from the initial state distribution specific to the corresponding MDP. Upon receiving an action a t produced by the agent, the environment computes reward r t , steps forward, and computes the next state s t+1 . If the episode has terminated, it sets termination flag d t to 1, which otherwise defaults to 0. Together, the next state s t+1 , action a t , reward r t , and termination flag d t , are concatenated to form the input to the policy1 , which, conditioned on the hidden state h t+1 , generates the next hidden state h t+2 and action a t+1 . At the end of an episode, the hidden state of the policy is preserved to the next episode, but not preserved between trials.

The objective under this formulation is to maximize the expected total discounted reward accumulated during a single trial rather than a single episode. Maximizing this objective is equivalent to minimizing the cumulative pseudo-regret (Bubeck & Cesa-Bianchi, 2012) . Since the underlying MDP changes across trials, as long as different strategies are required for different MDPs, the agent must act differently according to its belief over which MDP it is currently in. Hence, the agent is forced to integrate all the information it has received, including past actions, rewards, and termination flags, and adapt its strategy continually. Hence, we have set up an end-to-end optimization process, where the agent is encouraged to learn a "fast" reinforcement learning algorithm.

For clarity of exposition, we have defined the "inner" problem (of which the agent sees n each trials) to be an MDP rather than a POMDP. However, the method can also be applied in the partiallyobserved setting without any conceptual changes. In the partially observed setting, the agent is faced with a sequence of POMDPs, and it receives an observation o t instead of state s t at time t.

The visual navigation experiment in Section 3.3, is actually an instance of the this POMDP setting.

2.3. POLICY REPRESENTATION:

We represent the policy as a general recurrent neural network. Each timestep, it receives the tuple (s, a, r, d) as input, which is embedded using a function φ(s, a, r, d) and provided as input to an RNN. To alleviate the difficulty of training RNNs due to vanishing and exploding gradients (Bengio et al., 1994) , we use Gated Recurrent Units (GRUs) (Cho et al., 2014) which have been demonstrated to have good empirical performance (Chung et al., 2014; Józefowicz et al., 2015) . The output of the GRU is fed to a fully connected layer followed by a softmax function, which forms the distribution over actions.

We have also experimented with alternative architectures which explicitly reset part of the hidden state each episode of the sampled MDP, but we did not find any improvement over the simple architecture described above.

2.4. POLICY OPTIMIZATION:

After formulating the task as a reinforcement learning problem, we can readily use standard off-theshelf RL algorithms to optimize the policy. We use a first-order implementation of Trust Region Policy Optimization (TRPO) (Schulman et al., 2015) , because of its excellent empirical performance, and because it does not require excessive hyperparameter tuning. For more details, we refer the reader to the original paper. To reduce variance in the stochastic gradient estimation, we use a baseline which is also represented as an RNN using GRUs as building blocks. We optionally apply Generalized Advantage Estimation (GAE) (Schulman et al., 2016) to further reduce the variance.

3. EVALUATION:

We designed experiments to answer the following questions:

• Can RL 2 learn algorithms that achieve good performance on MDP classes with special structure, relative to existing algorithms tailored to this structure that have been proposed in the literature? • Can RL 2 scale to high-dimensional tasks?

For the first question, we evaluate RL 2 on two sets of tasks, multi-armed bandits (MAB) and tabular MDPs. These problems have been studied extensively in the reinforcement learning literature, and this body of work includes algorithms with guarantees of asymptotic optimality. We demonstrate that our approach achieves comparable performance to these theoretically justified algorithms.

For the second question, we evaluate RL 2 on a vision-based navigation task. Our experiments show that the learned policy makes effective use of the learned visual information and also short-term information acquired from previous episodes.

3.1. MULTI-ARMED BANDITS:

Multi-armed bandit problems are a subset of MDPs where the agent's environment is stateless. Specifically, there are k arms (actions), and at every time step, the agent pulls one of the arms, say i, and receives a reward drawn from an unknown distribution: our experiments take each arm to be a Bernoulli distribution with parameter p i . The goal is to maximize the total reward obtained over a fixed number of time steps. The key challenge is balancing exploration and exploitation-"exploring" each arm enough times to estimate its distribution (p i ), but eventually switching over to "exploitation" of the best arm. Despite the simplicity of multi-arm bandit problems, their study has led to a rich theory and a collection of algorithms with optimality guarantees.

Using RL 2 , we can train an RNN policy to solve bandit problems by training it on a given distribution ρ M . If the learning is successful, the resulting policy should be able to perform competitively with the theoretically optimal algorithms. We randomly generated bandit problems by sampling each parameter p i from the uniform distribution on [0, 1]. After training the RNN policy with RL 2 , we compared it against the following strategies:

• Random: this is a baseline strategy, where the agent pulls a random arm each time.

• Gittins index (Gittins, 1979) : this method gives the Bayes optimal solution in the discounted infinite-horizon case, by computing an index separately for each arm, and taking the arm with the largest index. While this work shows it is sufficient to independently compute an index for each arm (hence avoiding combinatorial explosion with the number of arms), it doesn't show how to tractably compute these individual indices exactly. We follow the practical approximations described in Gittins et al. (2011) , Chakravorty & Mahajan (2013) , and Whittle (1982) , and choose the best-performing approximation for each setup.

• UCB1 (Auer, 2002) : this method estimates an upper-confidence bound, and pulls the arm with the largest value of ucb i (t) = μi (t -1) + c 2 log t Ti(t-1) , where μi (t -1) is the estimated mean parameter for the ith arm, T i (t-1) is the number of times the ith arm has been pulled, and c is a tunable hyperparameter (Audibert & Munos, 2011) . We initialize the statistics with exactly one success and one failure, which corresponds to a Beta(1, 1) prior.

• Thompson sampling (TS) (Thompson, 1933) : this is a simple method which, at each time step, samples a list of arm means from the posterior distribution, and choose the best arm according to this sample. It has been demonstrated to compare favorably to UCB1 empirically (Chapelle & Li, 2011) . We also experiment with an optimistic variant (OTS) (May et al., 2012) , which samples N times from the posterior, and takes the one with the highest probability.

• -Greedy: in this strategy, the agent chooses the arm with the best empirical mean with probability 1 -, and chooses a random arm with probability . We use the same initialization as UCB1.

• Greedy: this is a special case of -Greedy with = 0.

The Bayesian methods, Gittins index and Thompson sampling, take advantage of the distribution ρ M ; and we provide these methods with the true distribution. For each method with hyperparameters, we maximize the score with a separate grid search for each of the experimental settings. The hyperparameters used for TRPO are shown in the appendix.

The results are summarized in Table 1 . Learning curves for various settings are shown in Figure 2 . We observe that our approach achieves performance that is almost as good as the the reference methods, which were (human) designed specifically to perform well on multi-armed bandit problems. It is worth noting that the published algorithms are mostly designed to minimize asymptotic regret (rather than finite horizon regret), hence there tends to be a little bit of room to outperform them in the finite horizon settings.

Table 1 : MAB Results. Each grid cell records the total reward averaged over 1000 different instances of the bandit problem. We consider k ∈ {5, 10, 50} bandits and n ∈ {10, 100, 500} episodes of interaction. We highlight the best-performing algorithms in each setup according to the computed mean, and we also highlight the other algorithms in that row whose performance is not significantly different from the best one (determined by a one-sided t-test with p = 0.05).

Setup:

Random Gittins TS OTS UCB1 -Greedy Greedy RL 2 n = 10, k = 5 5.0 6.6 5.7 6.5 6.7 6.6 6.6 6.7 n = 10, k = 10 5.0 6.6 5.5 6.2 6.7 6.6 6.6 6.7 n = 10, k = 50 5.1 6.5 5.2 5.5 6.6 6.5 6.5 We observe that there is a noticeable gap between Gittins index and RL 2 in the most challenging scenario, with 50 arms and 500 episodes. This raises the question whether better architectures or better (slow) RL algorithms should be explored. To determine the bottleneck, we trained the same policy architecture using supervised learning, using the trajectories generated by the Gittins index approach as training data. We found that the learned policy, when executed in test domains, achieved the same level of performance as the Gittins index approach, suggesting that there is room for improvement by using better RL algorithms.

3.2. TABULAR MDPS:

The bandit problem provides a natural and simple setting to investigate whether the policy learns to trade off between exploration and exploitation. However, the problem itself involves no sequential decision making, and does not fully characterize the challenges in solving MDPs. Hence, we perform further experiments using randomly generated tabular MDPs, where there is a finite number of possible states and actions-small enough that the transition probability distribution can be explicitly given as a table. We compare our approach with the following methods:

• Random: the agent chooses an action uniformly at random for each time step; • PSRL (Strens, 2000; Osband et al., 2013) : this is a direct generalization of Thompson sampling to MDPs, where at the beginning of each episode, we sample an MDP from the posterior distribution, and take actions according to the optimal policy for the entire episode. Similarly, we include an optimistic variant (OPSRL), which has also been explored in Osband & Van Roy (2016). • BEB (Kolter & Ng, 2009) : this is a model-based optimistic algorithm that adds an exploration bonus to (thus far) infrequently visited states and actions.

• UCRL2 (Jaksch et al., 2010) : this algorithm computes, at each iteration, the optimal policy against an optimistic MDP under the current belief, using an extended value iteration procedure.

• -Greedy: this algorithm takes actions optimal against the MAP estimate according to the current posterior, which is updated once per episode.

• Greedy: a special case of -Greedy with = 0. The distribution over MDPs is constructed with |S| = 10, |A| = 5. The rewards follow a Gaussian distribution with unit variance, and the mean parameters are sampled independently from Normal(1, 1). The transitions are sampled from a flat Dirichlet distribution. This construction matches the commonly used prior in Bayesian RL methods. We set the horizon for each episode to be T = 10, and an episode always starts on the first state. The results are summarized in Table 2 , and the learning curves are shown in Figure 3 . We follow the same evaluation procedure as in the bandit case. We experiment with n ∈ {10, 25, 50, 75, 100}. For fewer episodes, our approach surprisingly outperforms existing methods by a large margin. The advantage is reversed as n increases, suggesting that the reinforcement learning problem in the outer loop becomes more challenging to solve. We think that the advantage for small n comes from the need for more aggressive exploitation: since there are 140 degrees of freedom to estimate in order to characterize the MDP, and by the 10th episode, we will not have enough samples to form a good estimate of the entire dynamics. By directly optimizing the RNN in this setting, our approach should be able to cope with this shortage of samples, and decides to exploit sooner compared to the reference algorithms.

3.3. VISUAL NAVIGATION:

The previous two tasks both only involve very low-dimensional state spaces. To evaluate the feasibility of scaling up RL2 , we further experiment with a challenging vision-based task, where the agent is asked to navigate a randomly generated maze to find a randomly placed target 2 . The agent receives a +1 reward when it reaches the target, -0.001 when it hits the wall, and -0.04 per time step to encourage it to reach targets faster. It can interact with the maze for multiple episodes, during which the maze structure and target position are held fixed. The optimal strategy is to explore the maze efficiently during the first episode, and after locating the target, act optimally against the current maze and target based on the collected information. An illustration of the task is given in Figure 4 . 2016) have studied similar vision-based navigation tasks in Minecraft. However, they use higher-level actions for efficient navigation. Similar high-level actions in our task would each require around 5 low-level actions combined in the right way. In contrast, our RL 2 agent needs to learn these higher-level actions from scratch.

We use a simple training setup, where we use small mazes of size 5 × 5, with 2 episodes of interaction, each with horizon up to 250. Here the size of the maze is measured by the number of grid cells along each wall in a discrete representation of the maze. During each trial, we sample 1 out of 1000 randomly generated configurations of map layout and target positions. During testing, we evaluate on 1000 separately generated configurations. In addition, we also study its extrapolation behavior along two axes, by (1) testing on large mazes of size 9 × 9 (see Figure 4c ) and (2) running the agent for up to 5 episodes in both small and large mazes. For the large maze, we also increase the horizon per episode by 4x due to the increased size of the maze.

Table 3 : Results for visual navigation. These metrics are computed using the best run among all runs shown in Figure 5 . In 3c, we measure the proportion of mazes where the trajectory length in the second episode does not exceed the trajectory length in the first episode.

(a) Average length of successful trajectories Episode Small Large 1 52.4 ± 1.3 180.1 ± 6.0 2 39.1 ± 0.9 151.8 ± 5.9 3 42.6 ± 1.0 169.3 ± 6.3 4 43.5 ± 1.1 162.3 ± 6.4 5 43.9 ± 1.1 169.3 ± 6.5 The results are summarized in Table 3 , and the learning curves are shown in Figure 5 . We observe that there is a significant reduction in trajectory lengths between the first two episodes in both the smaller and larger mazes, suggesting that the agent has learned how to use information from past episodes. It also achieves reasonable extrapolation behavior in further episodes by maintaining its performance, although there is a small drop in the rate of success in the larger mazes. We also observe that on larger mazes, the ratio of improved trajectories is lower, likely because the agent has not learned how to act optimally in the larger mazes.

Still, even on the small mazes, the agent does not learn to perfectly reuse prior information. An illustration of the agent's behavior is shown in Figure 6 . The intended behavior, which occurs most frequently, as shown in 6a and 6b, is that the agent should remember the target's location, and utilize it to act optimally in the second episode. However, occasionally the agent forgets about where the target was, and continues to explore in the second episode, as shown in 6c and 6d. We believe that better reinforcement learning techniques used as the outer-loop algorithm will improve these results in the future. 

4. RELATED WORK:

The concept of using prior experience to speed up reinforcement learning algorithms has been explored in the past in various forms. Earlier studies have investigated automatic tuning of hyperparameters, such as learning rate and temperature (Ishii et al., 2002; Schweighofer & Doya, 2003) , as a form of meta-learning. Wilson et al. (2007) use hierarchical Bayesian methods to maintain a posterior over possible models of dynamics, and apply optimistic Thompson sampling according to the posterior. Many works in hierarchical reinforcement learning propose to extract reusable skills from previous tasks to speed up exploration in new tasks (Singh, 1992; Perkins et al., 1999) . We refer the reader to Taylor & Stone (2009) for a more thorough survey on the multi-task and transfer learning aspects.

The formulation of searching for a best-performing algorithm, whose performance is averaged over a given distribution over MDPs, have been investigated in the past in more limited forms (Maes et al., 2011; Castronovo et al., 2012) . There, they propose to learn an algorithm to solve multiarmed bandits using program search, where the search space consists of simple formulas composed from hand-specified primitives, which needs to be tuned for each specific distribution over MDPs. In comparison, our approach allows for entirely end-to-end training without requiring such domain knowledge.

More recently, Fu et al. (2015) propose a model-based approach on top of iLQG with unknown dynamics (Levine & Abbeel, 2014) , which uses samples collected from previous tasks to build a neural network prior for the dynamics, and can perform one-shot learning on new, but related tasks thanks to reduced sample complexity. There has been a growing interest in using deep neural networks for multi-task learning and transfer learning (Parisotto et al., 2015; Rusu et al., 2015; 2016a; Devin et al., 2016; Rusu et al., 2016b) .

In the broader context of machine learning, there has been a lot of interest in one-shot learning for object classification (Vilalta & Drissi, 2002; Fei-Fei et al., 2006; Larochelle et al., 2008; Lake et al., 2011; Koch, 2015) . Our work draws inspiration from a particular line of work (Younger et al., 2001; Santoro et al., 2016; Vinyals et al., 2016) , which formulates meta-learning as an optimization problem, and can thus be optimized end-to-end via gradient descent. While these work applies to the supervised learning setting, our work applies in the more general reinforcement learning setting. Although the reinforcement learning setting is more challenging, the resulting behavior is far richer: our agent must not only learn to exploit existing information, but also learn to explore, a problem that is usually not a factor in supervised learning. Another line of work (Hochreiter et al., 2001; Younger et al., 2001; Andrychowicz et al., 2016; Li & Malik, 2016) studies meta-learning over the optimization process. There, the meta-learner makes explicit updates to a parametrized model. In comparison, we do not use a directly parametrized policy; instead, the recurrent neural network agent acts as the meta-learner and the resulting policy simultaneously.

Our formulation essentially constructs a partially observable MDP (POMDP) which is solved in the outer loop, where the underlying MDP is unobserved by the agent. This reduction of an unknown MDP to a POMDP can be traced back to dual control theory (Feldbaum, 1960) , where "dual" refers to the fact that one is controlling both the state and the state estimate. Feldbaum pointed out that the solution can in principle be computed with dynamic programming, but doing so is usually impractical. POMDPs with such structure have also been studied under the name "mixed observability MDPs" (Ong et al., 2010) . However, the method proposed there suffers from the usual challenges of solving POMDPs in high dimensions.

Apart from the various multiple-episode tasks we investigate in this work, previous literature on training RNN policies have used similar tasks that require memory to test if long-term dependency can be learned. Recent examples include the Labyrinth experiment in the A3C paper (Mnih et al., 2016) , and the water maze experiment in the Recurrent DDPG paper (Heess et al., 2015a) . Although these tasks can be reformulated under the RL 2 framework, the key difference is that they focus on the memory aspect instead of the fast RL aspect.

5. DISCUSSION:

This paper suggests a different approach for designing better reinforcement learning algorithms: instead of acting as the designers ourselves, learn the algorithm end-to-end using standard reinforcement learning techniques. That is, the "fast" RL algorithm is a computation whose state is stored in the RNN activations, and the RNN's weights are learned by a general-purpose "slow" reinforcement learning algorithm. Our method, RL 2 , has demonstrated competence comparable with theoretically optimal algorithms in small-scale settings. We have further shown its potential to scale to high-dimensional tasks.

In the experiments, we have identified opportunities to improve upon RL 2 : the outer-loop reinforcement learning algorithm was shown to be an immediate bottleneck, and we believe that for settings with extremely long horizons, better architecture may also be required for the policy. Although we have used generic methods and architectures for the outer-loop algorithm and the policy, doing this also ignores the underlying episodic structure. We expect algorithms and policy architectures that exploit the problem structure to significantly boost the performance. Note that there are two columns associated with the UCB1 algorithm, where UCB1 (without " * ") is evaluated with c = 0.2, the parameter that gives the best performance as evaluated by the average total reward, and UCB1 * uses c = 1.0. Surprisingly, although using c = 1.0 performs the best in terms of recovering the best arm, its performance is significantly worse than using c = 0.2 when evaluated under the average total reward (369.2 ± 2.2 vs. 405.8 ± 2.2). This also explains that although RL 2 does not perform the best according to this metric (which is totally expected, since it is not optimized under this metric), it achieves comparable average total reward as other bestperforming methods.

:

To make sure that the inputs have a consistent dimension, we use placeholder values for the initial input to the policy.

Videos for the task are available at https://goo.gl/rDDBpb.

Figures and Tables:

Figure 1: Procedure of agent-environment interaction

Figure 2: RL 2 learning curves for multi-armed bandits. Performance is normalized such that Gittins index scores 1, and random policy scores 0.

Figure 3: RL 2 learning curves for tabular MDPs. Performance is normalized such that OPSRL scores 1, and random policy scores 0.

Figure 4: Visual navigation. The target block is shown in red, and occupies an entire grid in the maze layout.

Figure 5: RL 2 learning curves for visual navigation. Each curve shows a different random initialization of the RNN weights (by using a different random seed). Performance varies greatly across different initializations.

Figure 6: Visualization of the agent's behavior. In each scenario, the agent starts at the center of the blue block, and the goal is to reach anywhere in the red block.

Random MDP Results

Table content: <table><tr><td>Setup</td><td colspan="4">Random PSRL OPSRL UCRL2</td><td>BEB</td><td colspan="2">-Greedy Greedy</td><td>RL 2</td></tr><tr><td>n = 10</td><td>100.1</td><td>138.1</td><td>144.1</td><td>146.6</td><td>150.2</td><td>132.8</td><td>134.8</td><td>156.2</td></tr><tr><td>n = 25</td><td>250.2</td><td>408.8</td><td>425.2</td><td>424.1</td><td>427.8</td><td>377.3</td><td>368.8</td><td>445.7</td></tr><tr><td>n = 50</td><td>499.7</td><td>904.4</td><td>930.7</td><td>918.9</td><td>917.8</td><td>823.3</td><td>769.3</td><td>936.1</td></tr><tr><td>n = 75</td><td>749.9</td><td colspan="3">1417.1 1449.2 1427.6</td><td colspan="2">1422.6 1293.9</td><td>1172.9</td><td>1428.8</td></tr><tr><td colspan="2">n = 100 999.4</td><td colspan="3">1939.5 1973.9 1942.1</td><td colspan="2">1935.1 1778.2</td><td>1578.5</td><td>1913.7</td></tr></table>

Percentage of tasks where the best arm is chosen most frequently, with k = 5 arms and n = 500 episodes of interaction.

Table content: <table><tr><td>Setup</td><td colspan="2">Random Gittins</td><td>TS</td><td>OTS</td><td>UCB1</td><td>UCB1  *</td><td colspan="2">-Greedy Greedy</td><td>RL 2</td></tr><tr><td>∈ [0, 0.01]</td><td>21.5%</td><td>51.1%</td><td>53.1%</td><td>52.8%</td><td>50.9%</td><td>56.5%</td><td>37.3%</td><td>38.3%</td><td>46.1%</td></tr><tr><td colspan="2">∈ [0.01, 0.05] 19.3%</td><td>59.5%</td><td>71.2%</td><td>67.4%</td><td>62.5%</td><td>76.3%</td><td>42.3%</td><td>41.3%</td><td>55.1%</td></tr><tr><td>∈ [0.05, 0.1]</td><td>17.7%</td><td>71.2%</td><td>91.5%</td><td>84.0%</td><td>78.9%</td><td>94.6%</td><td>46.1%</td><td>45.7%</td><td>67.4%</td></tr><tr><td>∈ [0.1, 0.3]</td><td>20.1%</td><td>92.7%</td><td>99.2%</td><td>95.3%</td><td>93.5%</td><td>99.9%</td><td>58.1%</td><td>58.4%</td><td>87.1%</td></tr><tr><td>∈ [0.3, 0.5]</td><td>20.4%</td><td>99.6%</td><td colspan="2">100.0% 99.5%</td><td>99.8%</td><td colspan="2">100.0% 85.4%</td><td>84.6%</td><td>99.0%</td></tr><tr><td>∈ [0.5, 1.0]</td><td>19.4%</td><td colspan="6">100.0% 100.0% 100.0% 100.0% 100.0% 98.4%</td><td>99.1%</td><td>100.0%</td></tr></table>

Peer review (iclr2017):
The problem of maximising total discounted reward across multiple trials of an unknown MDP (but sampled from a known distribution, e.g. multi-arm bandit) can be formulated as a POMDP problem. A single episode of the POMDP consists of multiple episodes of interaction with the underlying MDP during which the agent should efficiently explore and integrate information about the MDP to minimize reward across the whole trial. Using this observation (which is not original to this work), the authors compare using an existing RL algorithm (TRPO) to solve POMDPs against classic regret minimization methods on two classic tasks: multi-armed bandits and tabular MDPs. Additionally, they also demonstrate their approach can scale to a visual navigation task. While the comparison with classic regret minimization problems is useful, this paper has several weaknesses. It seems very confusing to introduce a new name (RL^2) for an existing class of algorithms (essentially any RL method for solving POMDPs). This terminology and the paper structure obscures to relationship between this and prior work. The comparison with prior work training RNNs is, while improved from the previous version, still lacking. The distinction the authors make, that prior work “focussed on memory aspect instead of fast RL”, seems somewhat arbitrary. The visual navigation task is conceptually identical to the water maze experiment [Heess et al, 2015] or Labyrinth navigation [Mnih et al, 2016]. These prior tasks require more than just memory, the also requires meta-learning such as exploration and demonstrate “fast RL” with the agent able to improve dramatically after a single episode. The introduction mentions the need for the use of priors on the environment to create agents which learn quickly and suggests that prior work in DeepRL is data inefficient. Yet, the recently prior work (e.g. previous paragraph) focussed on POMDPs demonstrated one-shot learning once trained (in the “fast RL” task to use the author’s terminology). Although the discussion highlights the potential for new algorithms and architectures which are structured to improve performance at these “multi-episode” tasks, no new algorithms or architectures are introduced. Unfortunately, because of the limited contribution, poor comparisons with prior work and confusing terminology this paper is not suitable for ICLR without substantial revision.