Title: POSTERIOR SAMPLING: MAKE REINFORCEMENT LEARNING SAMPLE EFFICIENT AGAIN

Abstract: Machine learning thrives on leveraging structure in data, and many breakthroughs (e.g. convolutional networks) have been made by designing algorithms which exploit the underlying structure of a distribution. Reinforcement Learning agents interact with worlds that are similarly full of structure. For example, no sequence of actions an agent takes will ever cause the laws of physics to change, therefore an agent which learns to generalize such laws through time and space will have an advantage. Sample efficient reinforcement learning can be accomplished when assuming that the world has structure and designing learning algorithms which exploit this assumption without knowing the actual structure beforehand. Posterior Sampling for Reinforcement Learning (PSRL) (Strens, 2000) is such a method which assumes structure in the world and exploits it for learning. A PSLR learning agent first samples models of the environment which conform to both prior assumptions on the world's structure and past observations and then interacts with the true environment using a policy guided by the sampled model of the environment. While PSRL delivers theoretical Bayesian regret bounds, there are many open issues which must be addressed before PSRL can be applied to current benchmark continuous reinforcement reinforcement tasks. In this work, we identify these issues and find practical solutions to them leading to a novel algorithm we call Neural-PSRL 1 . We validate the algorithm's effectiveness by achieving state-of-the-art results in the HalfCheetah-v3 and Hopper-v3 domains.

1. INTRODUCTION:

In Reinforcement Learning (RL) an agent interacts with an environment by taking a sequence of actions, making observations and collecting rewards along the way. The goal in classic Reinforcement Learning is to find an agent that is able to maximize its accumulated rewards over time. This task is challenging since the agent is interacting with an unknown environment, and the agent must balance efficiently exploring the environment while collecting rewards, a trade-off known as the exploration exploitation trade-off.

Strategies for solving this problem fall into two broad classes: model-based RL and model-free RL. In the model-based case, a model of the true environment is learned, and actions are selected based on this model. Some examples of model-based methods include Dyna (Sutton, 1990) , Monte Carlo Tree Search (MCTS) and PILCO (Deisenroth & Rasmussen, 2011 ). In the model-free case, no model of the environment is learned, instead generally a value function or Q-function is learned directly from interactions with the environment. Some examples of model free include Q-Learning (Watkins & Dayan, 1992) , DQN (Mnih et al., 2015) , Actor Critic Methods (Mnih et al., 2016) and Soft Actor Critic (Haarnoja et al., 2018) .

Model-free Reinforcement Learning has delivered impressive results on many tasks, including tasks with high dimensional state spaces. Nevertheless, such algorithms are not sample efficient, requiring millions of observations to achieve human level performance (Hessel et al., 2018; Jin et al., 2018) .

Viewed from a certain light, the millions of observations required shouldn't be a surprise since if the agent interacts with a discrete Markov Decision Process (MDP), the expected regret (i.e. the difference between the reward under an agent learned by a RL algorithm and the reward under an optimal agent) of an arbitrary unknown environment is lower bounded by O( √ SAT ) (Osband & Van Roy, 2016b; Jaksch et al., 2010) , where S is the number of possible states, A is the number of possible actions and T is the number of interactions with the environment. Therefore, as the number of possible states and number of possible actions grow, so does the regret. Transferring this to the continuous state space case would imply an exponential growth in regret as the dimensionality of the state and action spaces increases. Making weak assumptions on the problem's structure could improve this bound vis-à-vis the tabula rasa setting, i.e. settings where only information about the state and action spaces are known. Examples of such weak assumptions include assuming that transition and reward dynamics can be modeled with a parameterizable model (Osband & Van Roy, 2014a) or that the conditional reward and transition probabilities factor (Osband & Van Roy, 2014b) . Since agents generally interact with worlds that have structure (for example, the same physical laws apply everywhere) such structure assumptions are justified.

A framework to integrate such assumptions comes from Osband & Van Roy (2014a) , where they assume the true environment is a sample from a know prior over all possible environments. This prior can then be chosen so that all environments sampled have structure, even if the underlying structure isn't yet known. For example, if we want to sample environments with linear structure, we can assume there is a linear mapping from the previous state-action pair to the next state and sample linear weight matrices. By assuming knowledge of such a prior, one can assume that the true environment is likely to have desirable properties. We note that restricting the possible environments to reduce regret is not a new strategy, for example the Linear Quadratic Regulator Bemporad et al. (2002) is able to find an optimal policy when assuming linear dynamics. Imposing a prior over all possible environments is an extremely general and adaptable extension of this idea.

By assuming that the true environment is a sample from a prior over all environments, we can use posterior sampling for reinforcement learning (PSRL), a variant of Thompson Sampling (Thompson, 1933) for Markov Decision Processes, to find a policy. It's known that the expected regret of the PSRL learning rule (Strens, 2000; Osband et al., 2013) is upper bounded by Õ( & Van Roy, 2014a) . Here d K is the Kolmogorov dimension and d E is the Eluder dimension (Russo & Van Roy, 2013) of the space of possible environments that can be sampled from the prior. In this way, the regret is now bounded by the complexity of the prior we assume the true environment to be sampled from, and not the dimensionality of the state and action spaces. A corollary is then if we know the true environment to be highly structured then the regret can be bounded by choosing a prior which accurately reflects the structure.

√ d K d E T ) (Osband

Equivalent to Thompson Sampling, PSRL happens in three alternating steps. First, an environment is sampled from a posterior constructed from the prior and all previous environment observations. Next, the optimal policy for this sampled environment is found. Since the sampled environment is fully known, this step can be done with computing power alone and does not require environment interactions. Finally, the policy found in the last step interacts with the true environment for an episode, and the resulting observations are saved.

While this method seems very appealing from a theoretical perspective, to the best of our knowledge it hasn't been applied to benchmark continuous reinforcement learning tasks. This could very well be because two of the three PSRL steps are themselves very challenging machine learning problems. In order to sample environments from a posterior, one must come up with a generative model of environments, and generative modeling is very much a very active research area in Machine Learning. Further, finding a policy which is optimal with respect to a sampled MDP is computationally complex (Sidford et al., 2018) , and this computational overhead must also be addressed in order to apply PSRL to challenging reinforcement learning tasks.

In this paper, we address both challenges and propose methods for learning a generative model of MDPs, and for finding an optimal policy for an MDPs sampled from this generative model. We refer to this suite of solutions as Neural-PSRL. Our method is then applied to the benchmark HalfCheetah-v3 and Hopper-v3 MuJoCo continuous control tasks (Todorov et al., 2012) and match the performance of current sample-efficient methods in both domains. Our work demonstrates that PSRL is more than just a theoretically appealing method, but is a framework which can leverage assumptions on a problem's structure to achieve state-of-the-art results.

2. NOTATION, DEFINITIONS AND ASSUMPTIONS:

In the following section, we largely use the notation from Osband et al. (2013) . For simplicity we assume interactions with the environment occur in episodes of fixed length τ ∈ N. Environments where an episode can end early, e.g. Hopper-v3 (Erez et al., 2012) , can easily be adapted to the fixed length setting by adding an absorbing state. Such an environment is formalized by a Markov Decision Processes M = (S, A, R M , P M , τ, ρ) where S and A are vector-valued state and action spaces, R M ( • |s, a) is a reward distribution over the real numbers R, and P M ( • |s, a) is the transition probability over S conditioned on state s and action a. Finally, τ ∈ N is the episode length and ρ is an initial state distribution over S.

A policy µ( • |s, i) is a probability measure over the action space conditioned on a state s ∈ S and the current step in the episode i ∈ {1, . . . , τ }, meaning when the environment is in state s and is about to take the i-th action in this episode, the policy determines with what probability an action a ∈ A is then taken.

Given a policy µ and an MDP M = (S, A, R M , P M , τ, ρ), we can recursively define the value function of policy µ at time i ∈ {1, . . . , τ } starting with V M µ,τ +1 (s) := 0 and working backwards

from i = τ to i = 1 via V M µ,i (s) := E a∼µ( • |s,i) R M (s, a) + E s ∼P M ( • |s,a) [V M µ,i+1 (s )] .

Intuitively, the value function is the expected future reward under policy µ; at the end of an episode no more reward will come, thus V M µ,τ (s) := 0, and for every previous step the expected future value is the reward at the current step plus all future rewards.

A policy µ is said to be the optimal policy for MDP

EQUATION

) for all s ∈ S. Generally the optimal policy need not be unique; for the sake of simplicity we will not consider the whole set of optimal policies but use µ M to denote some arbitrary policy from the set of policies which are optimal for M .

The regret of a policy µ under a MDP M is the difference between the reward that will on average be collected by policy µ vs. the optimal policy µ M . Formally, the regret is defined as

∆ M µ := E s∼ρ [V M µ M ,1 (s) -V M µ,1 (s)].

Lower regret policies are generally desirable, since such policies collect on average more rewards.

Interaction with the MDP M happens in episodes of length τ , and at the beginning of the k-th episode, we wish to use past observations to find a policy µ which will collect both rewards and new knowledge about the environment. A sequence of conditional distributions over policies (π k ) k∈N = π 0 , π 1 , . . . where each π k is conditioned on all past observations from the past k episodes is called a learning rule or learning agent. We denote with H k all observations from the first k episodes. Although other evaluation criteria are possible, We evaluate a learning rule on an MDP M by it's sum of expected regrets

EQUATION

The rest of this paper will be devoted to motivating, developing and evaluating such a learning rule.

3. NEEDLE IN A d-DIMENSIONAL HAYSTACK:

The fundamental problem with reinforcement learning in higher dimensions without any prior assumptions can be illustrated with the following extremely simple example adapted from Russo & Van Roy (2013) for the continuous case. Figure 1 is a visual representation of the example for the d = 2 case. Assume we have a family of deterministic, finite time horizon MDPs

(M ϑ ) ϑ∈[0,1] d = {(S, A, P, R ϑ , τ, ρ) | ϑ ∈ [0, 1] d }

where S = {s 0 }, A = [0, 1] d , ρ({s 0 }) = 1, τ = 1 (so the episode only has length 1). Further assume R ϑ (s, a) = max(1 -L a -ϑ 2 ), 0). In this simple example, an agent takes an action by exploring a point in the d-dimensional hypercube. If the distance between the point explored and ϑ is smaller than 1/L, a strict positive reward is collected. If not, a reward of zero is collected and the agent doesn't learn much useful information about the environment. Even if an agent knows everything about this environment except for ϑ, the agent's best strategy will be some variant of grid search, which will take O(L d ) episodes before a non-zero reward is found. Regret in the sense of Eq. 1 for any agent will therefore grow exponentially with d and polynomially with L, and higher dimensional problems will require billions of episodes for a reasonably good policy to be found.

Thankfully, the world we live in (and consequently most reinforcement learning tasks we wish to solve) has a more generalizable structure than the needle in a haystack. For example, the same laws of physics apply everywhere, independent of time and space. Therefore physical laws learned in one area of the state space can be applied to other parts of the state space.

We can therefore safely make many prior assumptions about our environment (an example for such an assumption is that the world is generalizable) before the agent executes even one interaction. Nearly all successful deeplearning RL algorithms implicitly make such prior assumption by assuming that true transition dynamics (in the model-based case) and Q-and valuefunctions (in the model-free case) can be modeled with a neural network of limited capacity.

3.1. ACCURATE PRIOR ASSUMPTIONS BOUND REGRET:

Now that we have established that no prior assumptions results in (almost) unbounded regret, one asks oneself if the converse is true: can one use prior assumptions to derive regret bounds in the continuous state and action space MDP setting? In Russo & Van Roy (2013) , such bounds can be derived for the infinite-arm bandit setting, and the proof concept is expanded upon in Osband & Van Roy (2014a) to bound the Bayesian regret for finite time horizon continuous Markov Decision Processes.

Theorem 1 (Regret for PSRL in parameterized MDPs, from Osband & Van Roy (2014a)) Fix real state and action spaces S and A and two function families R and P of bounded mappings from S × A → R and S × A → S. Let M * be an MDP with state space S, action space A, reward distribution equal to R * + ε R where R * ∈ R and ε R a sub-Gaussian random variable with variance σ R and similarly for transition probability equal to P * + ε P with P * ∈ P. If φ is the distribution of M * and K * = K M * is a global Lipschitz constant for the future-value function, then

EQUATION

where Õ ignores terms logarithmic in T and d K and d E are the Kolmogorov and Eluder dimensions.

The main takeaway from this theorem is that the expected regret of the PSRL learning rule π PS (defined in subsection 4.1) is bounded by the complexity of the classes of functions from which reward and transition dynamics are drawn. This result shouldn't be a surprise, if we know that the reward and transition distributions are drawn from a simple class of functions (e.g. linear functions) then the problem will be easier than if for example we only know that the environment dynamics are merely Lipschitz continuous. Work on analogous bounds for the infinite-time horizon MDP case is inconclusive, Abbasi-Yadkori & Szepesvári (2015) claims to have found such bounds, but Osband & Van Roy (2016a) points out a fault in their proof.

4. METHOD:

Although the PSRL method is well understood in theory, the method assumes one can sample MDPs from a posterior distribution and find an optimal policy for said sampled MDPs, both non-trivial problems. Our contribution is to demonstrate Neural-PSRL, a suite of methods which address these challenges in the continuous setting, thus opening a novel path to solve continuous reinforcement problems. The effectiveness of this approach is experimentally demonstrated in section 6

4.1. POSTERIOR SAMPLING FOR REINFORCEMENT LEARNING:

The learning rule which achieves the desirable regret bounds in Eq. 2 is the Posterior Sampling for Reinforcement Learning rule π PS , an extension of Thompson Sampling to Markov Decision Processes first proposed by Strens (2000) . The learning rule assumes access to a prior over MDPs φ, and that the true MDP M * is a sample from said prior. It is exactly this prior into which the practitioner can integrate prior knowledge about the environment. For example, by choosing a prior which when sampled returns for a transition dynamics model a neural network of limited capacity, the practitioner assumes the true transition dynamics are simple enough to be modeled by a neural network of limited capacity. Clearly, if the practitioner selects a prior from which the true MDP M * cannot be sampled, the PSRL learning rule π PS is not guaranteed to find a good policy.

Algorithm 1 Posterior Sampling for Reinforcement Learning (PSRL)

INPUT: Prior distribution φ for M * , t = 1, H t = {} for episodes k = 1, 2, . . . do sample M k ∼ φ(• | H t ) compute µ k = µ M k for timestep j = 1, . . . , τ do perform action a t ∼ µ k (s t ) observe r t and s t+1 H t+1 ← H t ∪ {(s t , a t , r t , s t+1 )} t ← t + 1 end for end for

The PSRL algorithm is outlined in Algorithm 1. At its heart, it is analogous to Thompson sampling in that given past observations H t , an environment M k is sampled which fits both the prior assumptions and past observations H t . In the next step a policy µ k which is optimal for M k is found and executed, and the observations are saved to the history. Since the MDP setting is more expressive than the simple bandit setting in which Thompson Sampling was developed, both these steps become more challenging. On the one hand, reward and transition dynamics are more complex than returns from a stateless multi-armed bandit which necessitates a more complex prior φ from which one can sample MDPs conditioned on past observations. This is nothing more than a generative model from which one can sample different transition and reward dynamics. In addition, while the optimal strategy given a known bandit is obvious (simply pull the arm that gives the highest expected return), discovering the optimal policy given a known MDP is often non-trivial (Azar et al., 2013) . In the following two subsections, we will propose solutions to both these problems.

4.2. GENERATIVE MODELING OF POSTERIOR φ(• | H t ):

Constructing models from which complex distributions can be sampled is an active area of research, with many proposed methods including Variational Auto-Encoders (Kingma & Welling, 2014), Restricted Boltzmann Machines (Hinton, 2002) and Generative Adversarial Networks (Goodfellow et al., 2014) . Generative modeling has already found applications in reinforcement learning (Deisenroth & Rasmussen, 2011; Ha & Schmidhuber, 2018; Chua et al., 2018) .

Fortunately, in a meta-study of deep Baysian networks for Thompson sampling (Riquelme et al., 2018) , it was shown that a relatively simple Bayesian linear regression model similar to Snoek et al. (2015) generally performs well on a broad range of reinforcement learning tasks. In that model, a neural network is trained to predict the next state (or reward), and the last layer of the network is then replaced with a Bayesian linear regression model; by sampling a new weight matrix from the Bayesian linear regression model one samples a new transition (or reward) model.

We use this model as a basis for our model, in which the predicted next state ŝt+1 is given by ŝt+1 := Wz (st,at) + s t where z (st,at) is the output of the last hidden layer of a network trained to predict s t+1 -s t given the previous state action pair (s t , a t ) as input. Further, W is a weight matrix sampled via Bayesian linear regression to regress z (st,at) to s t+1 -s t for all state-actionobservation sets in our history. We predict not the next state but the difference to the previous state, as suggested in Deisenroth et al. (2013) . Thus, dynamics models P M k (and by extension whole MDPs M k ) are sampled conditioned on past observations H k by sampling only the last layer of a next-state prediction network. Note that in contrast to Chua et al. (2018) , we sample deterministic next-state predictions, which allows us learn a policy with gradient based methods without the need to sample multiple trajectories (see below).

In a final fine-tuning step, we compose multiple copies of the sampled network from above to predict the n-next states and then backpropagate the errors through the composed-together network. This allows the network to not just predict the next state, but accurately predict the next n-states despite errors in next-state predictions. To both increase the generalization ability of the network, and integrate assumptions about the structure of the true environment, we use weight decay with the AdamW optimization algorithm.

4.3. POLICY FINDING:

Given a known MDP M k , the expected returns of a proposed policy µ can be evaluated via brute force Monte Carlo sampling, so in theory finding a (near) optimal policy is possible via trial and error. Unfortunately, in Azar et al. (2013) it's shown that even in the setting described in Kakade et al. (2003) with an oracle which returns a sample of the next observation conditioned on arbitrary state action pairs, finding an -optimal policy with probability 1 -δ has a complexity of

O |S||A| (1 -γ) 3 2

We are not aware of any analogous bounds for the continuous state-action space setting, but already this result would indicate that finding µ M k entails a high computational complexity. See Sidford et al. (2018) for an analogous bound for the finite-horizon case.

Fortunately, we have access not just to samples from the transition function but also to the gradients thereof, suggesting we should make use of an established policy gradient method (Silver et al., 2014; Sutton & Barto, 2018) , offering a practical method to deal with large continuous actions spaces. One such method that has a proven track record is Soft Actor Critic (Haarnoja et al., 2018) .

Soft Actor Critic learns a stochastic policy µ where actions sampled from the policy achieve a high reward with respect to the value function (here called the critic). Further, the entropy of sampled actions is enforced to match a pre-defined target, thereby ensuring the policy's actions are a bit random and explore nicely. SAC already brings a large bag of tricks to finding an optimal policy. For example the update uses a target value network V θ where θ is the exponential moving average of the value function weights θ (Mnih et al., 2015) . Second, they two value functions to minimize the positive bias that degrades performance of value based methods (Hasselt, 2010; Fujimoto et al., 2018) . These two value functions are neural networks parameterized with parameters θ 1 and θ 2 and trained independently with standard next-step predictions provided by M k (in contrast to Mnih et al. (2015) which uses a replay buffer) and Bellmann updates. To update the policy, the minimum of the two value functions is used.

We modify SAC in a few key points. First, assume that executing n steps of the policy µ starting in state s 0 ∈ S leads to state s 1 , . . . , s n ∈ S. With TD(0) updates (i.e. V µ (s -Medina et al., 2019) . We therefore elect to predict the next T states and update according to

i ) ← (1 -λ)V µ (s i ) + λ(r i + γV µ (s i+1 ))) it will take exponentially long in n for values from V µ (s n ) update V µ (s 0 ) (Arjona

V µ (s i ) ← (1 -λ)V µ (s 0 ) + λ( T -1 t=0 γ t r t + γ T V µ (s i+1 ))

This is a multi player game (the policy, value function and transition + reward dynamics interact together) where the gradients from the value function and environment dynamics are used to update the policy. Such a setting is strongly reminiscent of Generative Adversarial Networks (Goodfellow et al., 2014) . In this context it has been shown that low-variance gradient estimates are conducive for the multiple players to quickly reach a steady equilibrium (Seward et al., 2018) . As networks grow deeper, errors in gradient estimation compound. Therefore, although we use a large rollout to update the value function, we elect to obtain policy gradient with a short, i.e. one-step rollout.

Policy gradient methods for continuous control problems can converge to locally optimal policies (Tessler et al., 2019) . We observed this to be an issue in our experiments, with different runs under the same conditions converging to very different policies with very different average episode returns. This is a well documented issue in reinforcement learning (Henderson et al., 2018) . We found using an ensemble of policies was a helpful heuristic to tackle this issue. There, multiple policies are initialized, and the value function is updated by performing separate rollouts with each policy and as a reward estimate the maximum of the reward estimates from all rollouts.

With this, we were able to reliably and find policies µ M k for sampled MDPs µ k . Our method is summarized in Algorithm 2 in the Appendix.

5. RELATED WORK:

At this point, we'd like to showcase two similar methods which both solve continuous reinforcement learning tasks by learning models of the true environment and interacting with said environment guided by the learned world model. In the first method by Chua et al. (2018) called Probabilistic Ensembles with Trajectory Sampling (PETS) they first train an ensemble of models of the world using all past observations, then alternate between sampling action sequences a t:t+T from a cross-entropy method (Botev et al., 2013) , predicting trajectories given action sequence a t:t+T and updating the CEM distribution from which action sequences are sampled. Once a satisfactory action sequence has been found, the first action in the sequence is performed.

An open question from Chua et al. (2018) is how long trajectories should be. An overly long trajectories will be inaccurate, while an overly short trajectories won't capture long-term consequences of an action. In Janner et al. (2019) this issue is addressed and a method for optimal Trajectory length is developed. Like in (Chua et al., 2018) they learn an ensemble of probabilistic neural networks, and sample trajectories from these probabilistic neural networks. The difference is that the actions for the trajectory samples are from a policy, and the policy is learned with SAC (Haarnoja et al., 2018) applied to the sampled trajectories.

6. EXPERIMENTS:

The goal of our experimental evaluation is to demonstrate the applicability of Neural-PSRL to sample efficient learning in benchmark reinforcement learning tasks. We evaluate Neural-PSRL on the popular and widely studied MuJoCo continuous control tasks (Todorov et al., 2012) of HalfCheetah-v3 and Hopper-v3 (Erez et al., 2012) , comparing our method to Model Based Policy Optimization (MBPO) (Janner et al., 2019) . To the best of our knowledge, MBPO is the current state-of-the-art Wu et al. (2017) , TRPO Schulman et al. (2015) , PPO Schulman et al. (2017) , SAC Haarnoja et al. (2018) , MBPO Janner et al. (2019) on these tasks when the number of environment evaluations allowed is restricted (≤ 500K steps). Since MBPO clearly outperforms by a wide margin other reinforcement learning methods such as PPO (Schulman et al., 2017) and PETS (Chua et al., 2018) , we compare only to the model-based MBPO and the model-free SAC. Like in MBPO, we use the canonical 1000-step horizon with early termination versions of both tasks, and assume knowledge of the termination criteria, and for the sake of simplicity also assume knowledge of the reward distribution instead of learning it.

Since the goal set out Eq. 1 was to minimize the sum of regrets over all episodes, we report a closely related metric: the cumulative reward over episodes since the cumulative reward after n episodes is n times the expected reward of the unknown optimal policy minus the cumulative regret. In contrast to many experimental evaluations, we report the reward with respect to the number of episodes, not the number of environment interactions. When reporting cumulative reward with respect to the number of environment interactions, it is impossible to distinguish between undesirable policies that achieve a high per-interaction reward but often terminate early and more desirable policies which achieve similarly high per-interaction reward and rarely terminate early. We report the reward received during learning, not the reward that would have been received in an offline evaluation of the policy.

Since PSRL can be split into separate tasks (building a model of the world, sampling from the model with an eye to optimal exploration-exploitation trade-off, finding an optimal policy for sampled models) we leave the questions of optimizing the individual tasks to specific domains to future work, and restrict ourselves to demonstrating that Neural-PSRL works.

7. NEXT STEPS:

Neural-PSRL shows that the highly-adaptable PSRL framework is an important tool in the Reinforcement Learner's toolbox, and indeed our experiments confirm that PSRL can match state-of-the art performance with a relatively small number of samples. Still, our experiments are not yet a fair head-to-head comparison with other methods. For example, we employ the the ensemble of policies trick which could also improve other off-policy policy-gradient based methods such as MBPO, SAC, and PPO. In addition, the effect of an expanded Neural-PSRL which also learns the reward dynamics has not yet been explored and is something we would like to investigate.

:

See supplementary material for videos and code which will be published

Figures and Tables:

Figure 1: Reward function R ϑ (s 0 , •). Any agent will struggle to learn the relevant information of this function (the location of the point) Samples from other areas yield little relevant information.

Figure 2: Training curves for Neural-PSRL and both model-free SAC(Haarnoja et al., 2018) and model-based(Janner et al., 2019) baselines on continuous control benchmarks Hopper-v3 and HalfCheetah-v3 Each environments is evaluated with the canonical 1000-step variant of the task. Thin curves indicate individual training curves, thick curves indicate the mean of the training runs and the shaded area is the standard deviation among trials. We see that in such a sample-constrained environment, the model based methods outperform the model-free SAC. Our method matches the performance of the current state-of-the-art model based method.

Figure 3: Cumulative training curves of runs from figure 2. To maximize cumulative reward (or equivalently minimize regret), learning must quickly learn a good policy and constantly improve it.

Mean and 95% confidence bounds of training reward for DDPG Lillicrap et al. (2016), ACKTR

Table content: <table/>

and Neural-PSRL when trained to convergence. Numbers for first four methods are fromHenderson et al. (2018), see Appendix section A.2 for details.

Table content: <table><tr><td/><td>DDPG</td><td>ACKTR</td><td>TRPO</td><td>PPO</td><td>SAC</td><td>MBPO</td><td>Neural-PSRL</td></tr><tr><td>HalfCheetah</td><td>5037</td><td>3888</td><td>1254</td><td>3043</td><td>11820</td><td>12543</td><td>13885</td></tr><tr><td/><td>(3664, 6574)</td><td>(2288, 5131)</td><td>(999, 1464)</td><td>(1920, 4165)</td><td>(2636, 21005)</td><td>(11299, 13787)</td><td>(11171, 16599)</td></tr><tr><td>Hopper</td><td>1632</td><td>2546</td><td>2965</td><td>2715</td><td>3030</td><td>3123</td><td>3347</td></tr><tr><td/><td>(607, 2370)</td><td>(1875, 3217)</td><td>(2854, 3076)</td><td>(2589, 2847)</td><td>(2009, 4050)</td><td>(2301, 3944)</td><td>(2883, 3811)</td></tr></table>

Peer review (iclr2020):
Posterior Sampling: Make Reinforcement Learning Sample Efficient Again =============================================================== This paper proposes an implementation of PSRL via Neural-PSRL: a neural network is trained fit the transition dynamics, with a last-layer linear approximation used to give a posterior distribution. This model can be used in conjunction with a policy gradient algorithm to give an exploratory policy. Evaluated on Mujoco benchmarks this leads to state of the art performance. There are several things to like about this paper: - The problem of extending *efficient exploration* to Deep RL is an important one, and PSRL seems like one of the most suitable general approaches to base an algorithm on. - The proposed algorithm seems reasonable, and seems like it also performs well. - The approach to writing and accessible code release should be praised. However, there are some other places where this paper falls down: - Despite the focus on *incorporating prior knowledge* in the early part of the paper, it seems like the proposed method actually incorporates very little prior knowledge... for example, the *Eluder dimension* of the space represented by these neural networks is presumably huge! This seems like a bit of a bait and switch. - I don*t think the experiments offer a huge amount of *insight* into what is really happening in the algorithm. It would be helpful to show *really good* performance even on a toy domain, so that you can really say that the exploration via PSRL is really working... maybe something like bsuite = https://github.com/deepmind/bsuite and particularly the *deep sea* experiments could help? - It*s a problem that the actual main paper doesn*t give a clear and concise description of the algorithm used. I think this is quite important and it would be much better to put the older results on PSRL to the appendix instead. Minor points: - I*m not sure the title is a great idea... it might put off some people, but also I don*t think it*s really warranted from the results... it seems like Neural-PSRL is a potentially interesting avenue, but hardly making anything great (again?)! - You might want to connect / contrast this work vs the line of research around *Randomized Value Functions* http://jmlr.org/papers/v20/18-339.html... which is another approach that tries to extend something like PSRL to Deep RL. Overall, I do think this is an interesting paper, and a promising avenue for research. However there are probably too many places where the paper could be tightened up: clarity of algorithm description, clarity of support/results, separation of actual claims vs claims of *making great* ;D.