{'fraction_non_alphanumeric': 0.038967711338576454, 'fraction_numerical': 0.013279057819230921, 'mean_word_length': 4.493703864524533, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deep Model-Based Reinforcement Learning via Estimated Uncertainty and Conservative Policy Optimization

Model-based reinforcement learning algorithms tend to achieve higher sample efficiency than model-free methods. However, due to the inevitable errors of learned models, model-based methods struggle to achieve the same asymptotic performance as model-free methods. In this paper, We propose a Policy Optimization method with Model-Based Uncertainty (POMBU)---a novel model-based approach---that can effectively improve the asymptotic performance using the uncertainty in Q-values. We derive an upper bound of the uncertainty, based on which we can approximate the uncertainty accurately and efficiently for model-based methods. We further propose an uncertainty-aware policy optimization algorithm that optimizes the policy conservatively to encourage performance improvement with high probability. This can significantly alleviate the overfitting of policy to inaccurate models. Experiments show POMBU can outperform existing state-of-the-art policy optimization algorithms in terms of sample efficiency and asymptotic performance. Moreover, the experiments demonstrate the excellent robustness of POMBU compared to previous model-based approaches.


Introduction
Model-free reinforcement learning has achieved remarkable success in sequential decision tasks, such as playing Atari games (Mnih et al. 2015;Hessel et al. 2018) and controlling robots in simulation environments (Lillicrap et al. 2016;Haarnoja et al. 2018). However, model-free approaches require large amounts of samples, especially when using powerful function approximators, like neural networks. Therefore, the high sample complexity hinders the application of model-free methods in real-world tasks, not to mention data gathering is often costly. In contrast, modelbased reinforcement learning is more sample efficient, as it can learn from the interactions with models and then find a near-optimal policy via models (Kocijan et al. ;Deisenroth and Rasmussen 2011;Levine and Abbeel 2014;Nagabandi et al. 2018). However, these methods suffer from errors of learned models, which hurt the asymptotic performance (Schneider 1997;Abbeel, Quigley, and Ng 2006).
Thus, compared to model-free methods, model-based algorithms can learn more quickly but tend to learn suboptimal policies after plenty of trials.
Early model-based methods achieve impressing results using simple models, like linear models (Bagnell and Schneider 2001;Levine et al. 2016) and Gaussian processes (Kuss and Rasmussen 2004;Deisenroth and Rasmussen 2011). However, these methods have difficulties in highdimensional and non-linear environments due to the limited expressiveness of models. Recent methods use neural network models for better performance, especially for complicate tasks (Punjani and Abbeel 2015;Nagabandi et al. 2018). Some methods further characterize the uncertainty in models via neural network ensembles (Rajeswaran et al. 2017;Kurutach et al. 2018), or Bayesian neural networks (Depeweg et al. 2017). Although the uncertainty in models improves the performance of model-based methods, recent research shows that these methods still struggle to achieve the comparable asymptotic performance to state-of-the-art model-free methods robustly (Wang et al. 2019).
Inspired by previous work that improves model-free algorithms via uncertainty-aware exploration (O'Donoghue et al. 2018), we propose a theoretically-motivated algorithm to estimate the uncertainty in Q-values and apply it to the exploration of model-based reinforcement learning. Moreover, we propose to optimize the policy conservatively by encouraging a large probability of performance improvement, which is also informed by the estimated uncertainty. Thus, we use the uncertainty in Q-values to enhance both exploration and policy optimization in our model-based algorithm.
Our contributions consist of three parts. First, we derive an upper bound of the uncertainty in Qvalues and present an algorithm to estimate it. Our bound is tighter than previous work (O'Donoghue et al. 2018), and our algorithm is feasible for deep model-based reinforcement learning, while many previous methods only focus on model-free cases (Osband et al. 2016;, or assume simple models (Dearden, Friedman, and Andre 1999).
Second, we propose to optimize the policy conservatively based on an estimated probability of performance improvement, which is estimated via the uncertainty in Q-values and is useful to prevent the overfitting to the biased models.
Third, we propose a Policy Optimization method with Model-Based Uncertainty (POMBU), which combines our uncertainty estimation algorithm with the conservative policy optimization algorithm. Experiments show that POMBU achieves excellent robustness and can outperform state-ofthe-art policy optimization algorithms.

Background
A finite-horizon Markov decision process (MDP) M is defined by the tuple (S, A, P, R, ρ, H). Here, S is a finite set of states, A is a finite set of actions, P is a third-order tensor that denotes the transition probabilities, R is a matrix that denotes the rewards, ρ denotes the distribution of initial states and H is the horizon length. More specifically, at the state s and selecting the action a, P sas ∈ [0, 1] is the probability of transitioning to the state s , and R sa ∈ [−R max , R max ] is the obtained reward. We represent a posterior of MDPs as (Ω, F, P r), where Ω is the sample space containing all possible MDPs, F is a σ-field consisting of subsets of Ω, and P r : F → [0, 1] measures the posterior probability of MDPs. We assume that each MDP in Ω is different from others only in terms of P and R. In this case, P is a random tensor and R is a random matrix. For any random variable, matrix or tensor X, E M [X] and D M [X] denotes its expectation and variance respectively. When without ambiguity, we write E M [X] asX for short, e.g.,P denotes Let π denotes a policy. π sa denotes the probability of taking the action a at the state s. Considering the posterior of MDPs, the expected return J π is a random variable, which is defined by Here τ = (s 1 , a 1 , . . . , s H , a H ) is a trajectory. τ ∼ (M, π) means that the trajectory is sampled from the MDP M under policy π. That is, s 1 is sampled from the initial state distribution ρ of M, a h is sampled with the probability π s h a h and s h+1 is sampled with the probability P s h a h s h+1 in M. Our goal is to find a policy maximizing J π in real environment.
Given an MDP M, we define the corresponding stateaction value function Q, the state value function V and the advantage function A as follow: When the policy π is fixed, we write V h π (s), Q h π (s, a) and A h π (s, a) as V h s , Q h sa and A h sa respectively for short. In this case, for any time-step h, V h s , Q h sa and A h sa are random variables mapping Ω to R. Hence, V h is a random vector. Q h and A h are random matrices.

Uncertainty Estimation
In this section, we consider a fixed policy π. Similarly to the uncertainty Bellman equation (UBE) (O'Donoghue et al. 2018), we regard the standard deviations of Q-values as the uncertainty. In this section, we derive an upper bound of D M Q h sa for each s, a, h, and prove that our upper bound is tighter than that of UBE. Moreover, we propose an uncertainty estimation algorithm for deep model-based reinforcement learning and discuss its advantages. We provide related proofs in Appendix A.1-A.4.

Upper Bound of Uncertainty in Q-values
To analyze the uncertainty, we first make two assumptions.

Assumption 1 Each MDP in Ω is a directed acyclic graph.
This assumption is common O'Donoghue et al. 2018). It means that the agent cannot visit a state more than twice within the same episode. This assumption is weak because each finite horizon MDP violating the assumption can be converted into a similar MDP that satisfying the assumption (O'Donoghue et al. 2018).
Assumption 2 The random vector R s1 and the random matrix P s1 are independent on R s2 and P s2 if s 1 = s 2 .
This assumption is used in the derivation of UBE (O'Donoghue et al. 2018). It is consistent with the trajectory sampling strategies used in recent model-based algorithms (Chua et al. 2018;Kurutach et al. 2018), which sample a model from the ensemble of models independently per time step to predict the next state and reward.
First, we derive an inequation from these assumptions.
Lemma 1 Under Assumption 1 and 2, for any s ∈ S and a ∈ A, we have We consider u h sa as a local uncertainty, because we can compute it locally withV .
Then, we can derive our main theorem from this lemma.
Theorem 1 Under Assumption 1 and 2, for any policy π, there exists a unique solution U satisfying the following equation: for any (s, a) and h = 1, 2, . . . , H, where U H+1 = 0, and Theorem 1 means that we can compute an upper bound of D M Q h sa by solving the Bellman-style equation (1). Moreover, we provide the following theorem to show the convergence when computing U iteratively.
for any (s, a), h = 1, 2, . . . , H and i ≥ 1, where U H+1 i = 0 and (u) i converges to u pointwise, we have (U ) i converges to U pointwise. Theorem 2 shows that we can solve the equation (1) iteratively if the estimated local uncertainty is not accurate per update but converges to the correct value, whis is significant when we use an estimatedV to compute the uncertainty.
As U h sa is an upper bound of D M Q h sa , U h sa is an upper bound of the uncertainty in Q h sa . We use the upper bound to approximate the uncertainty in our algorithm similarly to UBE. We need to analyze the accuracy of our estimates.
Here, we compare our upper bound U with that of UBE under the same assumptions, and hence we need to make an extra assumption used in UBE. Assumption 3 R s is independent on P s for any s ∈ S. This assumption is not used to derive our upper bound of the uncertainty but is used in UBE. Under the assumption 2 and 3, we have R is independent on P .
The upper bound B derived in UBE satisfies Here, Q max is an upper bound of all |Q h sa | for any s, a, h and MDP. For example, we can regard HR max as Q max .
Theorem 3 Under the assumption 1, 2 and 3, U h sa is a tighter upper bound of D M Q h sa than B h sa . This theorem means that approximating the uncertainty using our upper bound U is more accurate than using the upper bound B derived in UBE.

Uncertainty Estimation Algorithm
First, we characterizes the posterior of MDPs approximatively using a deterministic model ensemble (please refer to the Section 5 for the details of training models). A deterministic ensemble is denoted by (f w1 , f w2 , . . . , f w K ). Here, for any i = 1, 2, . . . , K, f wi : S × A → S × R is a single model that predicts the next state and reward given a state and an action, and w i is its parameters. We define the posterior probability of MDPs by where equal is defined by Then, we can construct an MDPM defined according to the posterior of MDPs, such that its transition tensorP is equal toP and its reward matrixR is equal toR. Hence, the state value matrixV of the MDPM is equal toV . Moreover, we use a neural networkṼ φ : S → R to predict V h s for any state s and time step h, which is equivalent to predictingV . We trainṼ φ by minimizing 2 loss function (2) Finally, given an imagined trajectory τ sampled fromM under π, we can estimate the uncertainty in Q-values via the algorithm 1. Note that for long-horizon tasks, we can introduce a discount factor γ similarly to previous work (O'Donoghue et al. 2018). The modified uncertainty estimation method can be found in Appendix B.

Discussion
In this part, we discuss some advantages of our algorithm to estimate the uncertainty in Q-values.
Accuracy Based on the Theorem 3, our upper bound of the uncertainty is tighter than UBE, which means a more accurate estimation. Intuitively, our local uncertainty depends onV h while that of UBE depends on Q max . Therefore, our local uncertainty has a weaker dependence on H and can provide a relatively accurate estimation for long-horizon tasks (see an example in Appendix C). Moreover, considering an infinite set of states, our method ensures the boundedness of the local uncertainty becauseV h and R are bounded. Therefore, our method has the potential to apply to tasks with continuous action spaces.
Applicability for Model-Based Methods Our method to estimate the uncertainty in Q-values is effective for modelbased reinforcement learning. In model-based cases, estimated Q-values are highly dependent on the models. Our method considers the model when computing the local uncertainty, while most of the existing methods estimate the uncertainty directly via the real-world samples regardless of the models. Ignoring models may lead to bad estimates of uncertainty in model-based cases. For example, the uncertainty estimated by a count-based method (Bellemare et al. 2016;Ostrovski et al. 2017) tends to decrease with the increase of the number of samples, while the true uncertainty keeps high even with a large amount of samples when modeling a complicate MDP using a simple model.

Computational Cost
Our method is much more computationally cheap compared with estimating the uncertainty via the empirical standard deviation of Q h sa . Estimating Q h sa given an MDP requires plenty of virtual samples, let alone estimating its empirical standard deviation. Previous work reduces the computational cost by learning an ensemble of Q functions (Buckman et al. 2018). However, training an ensemble of Q functions requires higher computational overhead than training a single neural networkṼ φ in our method.
Compatibility with Neural Networks Previous methods that estimate uncertainty for model-based methods always assume simple models, like Gaussian processes (Deisenroth and Rasmussen 2011;Dearden, Friedman, and Andre 1999). Estimating uncertainty using Theorem 1 only requires that the models can represent a posterior. This makes our method compatible with neural network ensembles and Bayesian neural networks. For instance, we propose Algorithm 1 with an ensemble of neural networks.
Propagation of Uncertainty As discussed in previous work (Osband, Aslanides, and Cassirer 2018), Bellman equation implies the high dependency between Q-values. Ignoring this dependence will limit the accuracy of the estimates of uncertainty. Our method considers the dependency and propagates the uncertainty via a Bellman-style equation.

Conservative Policy Optimization
In this section, we first introduce surrogate objective and then modify it via uncertainty. The modified objective leads to conservative policy optimization because it penalizes the update in the high-uncertainty regions. Let π θ : S × A → [0, 1] denotes a parameterized policy, and θ is its parameters. π θ (a|s) denotes the probability of taking action a at state s.

Surrogate Objective
Recent reinforcement learning algorithms, like Trust Region Policy Optimization (TRPO) (Schulman et al. 2015), Proximal Policy Optimization (PPO) (Schulman et al. 2017), optimize the policy based on surrogate objective. We rewrite the surrogate objective in TRPO and PPO as follow: where θ old are the old policy parameters before the update, A old is the advantage function of π θold and r θ (s, a) = π θ (a|s) π θold (a|s) .
Previous work has proven the surrogate objective is the first order approximation to J(π θ ) − J(π θold ) when θ is around θ old (Schulman et al. 2015;Kakade and Langford 2002). That is, for any θ old , we have the following theorem: (see proof in Appendix A.5). Therefore, maximizing L sr (θ) can maximize J(π θ ) approximately when θ is around θ old .

Uncertainty-Aware Surrogate Objective
To prevent the overfitting of the policy to inaccurate models, we introduce the estimated uncertainty in Q-values into the surrogate objective. First, we need to estimate P r{J(π θ ) > J(π θold )}, which means the probability that the new policy outperforms the old one. Because of Theorem 4, P r{L sr (θ) > 0} can approximate P r{J(π θ ) > J(π θold )}. Then, we assume that a Gaussian can approximate the distribution of L sr (θ) > 0.
is approximately equal to P r{L sr (θ) > 0}, where F is the probability distribution function of standard normal distribution.
Then, we need to construct an objective function for optimization. Here, we aims to find a new θ with a large . Therefore, we can maximize where α ≥ 0 is a hyperparameter. Moreover, we need to estimate the expectation and the variance of the surrogate objective. Because L sr (θ) is equal to we can approximate E M [L sr (θ)] and D M [L sr (θ)] as L exp (θ) and L std (θ) respectively, where HereM is defined in Section 3 using a learned ensemble, A h old (s h , a h ) can be approximated by H l=hRs l a l −Ṽ φ (s h ), and D h is computed by Algorithm 1.
However, policy optimization without trust region may lead to unacceptable bad performance (Schulman et al. Sample virtual trajectories fromM using π θ ; 10 TrainṼ φ by minimizeing L v (φ);
Note that, the main difference of our objective from PPO is the uncertainty penalty L std (θ). This penalty limits the ratio changes |r θ (s h , a h ) − 1| in high-uncertainty regions. Therefore, this objective is uncertainty-aware and leads to a conservative update.

Algorithm
In this section, we propose a Policy Optimization method with Model-Based Uncertainty (POMBU) in Algorithm 2. We details each stage of our algorithm as following.
Exploration Policy We train a set of exploration policies by maximizing the L clip (θ). Different policies are trained with different virtual trajectories. To explore the unknown, we replaceĀ h old (s h , a h ) withĀ h old (s h , a h ) + β √ D h in the equation (6). Here, β ≥ 0 controlling the exploration to high-uncertainty regions.

Model Ensemble
To predict the next state, a single neural network in the ensemble outputs the change in state and then adds the change to the current state (Kurutach et al. 2018;Nagabandi et al. 2018). To predict the reward, we assume the reward in real environment is computed by a function μ such that R s h a h = μ(s h , a h , s h+1 ), which is commonly true in many simulation control tasks. Then, we can predict the reward via the predicted next state. We train the model by minimizing 2 loss similarly to previous work (Kurutach et al. 2018;Nagabandi et al. 2018) and optimize the parameter using Adam (Kingma and Ba 2014). Different models are trained with different train-validation split.
Policy Optimization We use a Gaussian policy whose mean is computed by a forward neural network and standard deviation is represented by a vector of parameters. We optimizing all parameters by maximizing L π (θ) via Adam.

Experiments
In this section, we fist evaluate our uncertainty estimation method. Second, we compare POMBU to state-of-the-arts. Then, we show how does the estimated uncertainty work by ablation study. Finally, we analyze the robustness of our method empirically. In the following experiments, we report the performance averaged over at least three random seeds. Please refer to Appendix D for the details of experiments. The source code and appendix of this work is available at https://github.com/MIRALab-USTC/RL-POMBU.

Effectiveness of Uncertainty Estimation
We evaluate the effectiveness of our uncertainty estimation method in two simple environments: 2D-point and 3D-point. These environments have continuous state spaces and continuous action spaces. First, we train an ensemble model of the environment and sample state-action pairs from the model using a deterministic policy. Then, we estimate the Q-values of these pairs via the means of virtual returns (computed using the models), and estimate the uncertainty using the algorithm 1. Finally, we compute the real Q-values using the return in real world, compute the ratios of errors to the estimated uncertainties, and count the frequencies of these ratios to draw Figure 1. This figure shows the distribution of ratios is similar to a standard normal distribution after sufficient training ofṼ φ , which demonstrates the accuracy of the estimated uncertainty.

Comparison to State-of-the-Arts
We compare POMBU with state-of-the-art policy optimization algorithms on four continuous control tasks in Mujoco (Todorov, Erez, and Tassa 2012): Swimmer, HalfCheetah, Ant, and Walker2d. Our method and our baselines optimize a stochastic policy to complete the tasks. Our baselines include: soft actor critic (SAC) (Haarnoja et al. 2018); proximal policy optimization (PPO); stochastic lower bounds optimization (SLBO) (Luo et al. 2018); model-ensemble trust region policy optimization (METRPO) (Kurutach et al. 2018). To show the benefits of using uncertainty in modelbased reinforcement learning, we also compare POMBU to model-ensemble proximal policy optimization (MEPPO), which is equivalent to POMBU when α = 0 and β = 0. We evaluate POMBU with α = 0.5 and β = 10 for all tasks.
The result is shown in Figure 2. The solid curves correspond to the mean and the shaded region corresponds to the empirical standard deviation. It shows that POMBU achieves higher sample efficiency and better final performance than baselines, which highlights the great benefits of using uncertainty. Moreover, POMBU achieves comparable asymptotic performances with PPO and SAC in all tasks.
We also provide Table 1 that summarizes the performance, estimated wall-clock time and the number of used imagined samples and real-world samples in the HalfCheetah task (H=200). Compared to MEPPO, the extra time used in POMBU is small (time: 10.17 → 12.05), while the improvement is significant (mean: 449 → 852; standard deviation: 226 → 21). Compared to SAC, POMBU achieve higher performance with about 5 times less real-world samples. Moreover, in our experiments, the total time to compute the uncertainty (not include the time to trainṼ φ ) is about 1.4 minutes, which is ignorable compared with the overall time.
We further compare POMBU with state-of-the-art modelbased algorithms in long-horizon tasks. The compared algorithms include model-based meta policy optimization (MBMPO) , probabilistic ensemble with trajectory sampling (PETS) (Chua et al. 2018) and stochastic ensemble value expansion (STEVE) (Buckman et al. 2018) in addition. We directly use some of the results given by Wang et al. (2019), and summarize all results in Table 2. The table shows that POMBU achieves comparable performance with STEVE and PETS, and outperforms other model-based algorithms. It demonstrates that POMBU is also effective in long-horizon tasks. We train the policy via PPO and SAC with at least 1 million samples and report the best averaged performance as "max".

Ablation Study
We provide an ablation study to show how the uncertainty benefits the performance. In our algorithm, we employ the uncertainty in policy optimization (controlled by α) and exploration (controlled by β). Therefore, we compare the performance with different α and β.
The results are shown in Figure 3 and 4. Setting α as 0.5 or 0.75 achieves the best final performance and the best robustness with 200K samples. Note that a large α may re-   sult in poorer performance in the early stage, because the uncertainty is high in the early stage and a large α tends to choose a small step size when uncertainty is high. Using β = 10 can improve the performance (larger mean and smaller standard deviation), which demonstrate the effectiveness of uncertainty-aware exploration.

Robustness Analyses
We demonstrate the excellent robustness of POMBU in two ways. First, we evaluate algorithms in noisy environments. In these environments, we add Gaussian noise to the observation with the standard deviation σ. This noise will affect the accuracy of the learned models. Second, we evaluate algorithms in long-horizon tasks. In these tasks, models need to generate long trajectories, and the error is further exacerbated due to the difficulty of longterm predictions. We report the results in Figure 5. Experiments show that our algorithm achieves similar performance with different random seeds, while the performance of METRPO varies greatly with the random seeds. Moreover, in Figure 5, the worst performance of POMBU beats the best of METRPO.  This implies that our method has promising robustness, even in noisy environments and long-horizon environments.

Conclusion
In this work, we propose a Policy Optimization method with Model-Based Uncertainty (POMBU), which is a novel uncertainty-aware model-based algorithm. This method estimates uncertainty using a model ensemble and then optimizes policy Conservatively considering the uncertainty. Experiments demonstrate that POMBU can achieve comparable asymptotic performance with SAC and PPO while using much fewer samples. Compared with other modelbased methods, POMBU is robust and can achieve better performance. We believe that our approach will bring new insights into model-based reinforcement learning. An enticing direction for further work is the combination of our uncertainty estimation method with other kinds of models like Bayesian neural networks. Another exciting direction is to modify other advanced model-based algorithms like STEVE and PETS using our uncertainty estimation method.