Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning

1 Introduction

• Greedy policy optimization can fail when action penalties make the expected reward of a swing-up maneuver too low, leaving the pendulum at a local minimum.The paper identifies a lack of efficient, principled ways to incorporate optimism in deep MBRL.Source: §1 · pp. 1–2
• H-UCRL reparameterizes plausible models and augments control with hallucinated inputs that directly control epistemic uncertainty, reducing optimistic exploration to greedy exploitation.The paper reports that this approach can be applied with state-of-the-art RL algorithms and calls it the first successful implementation of optimistic exploration with deep MBRL.Source: §1 · p. 2
• Greedy exploitation is common in model-based RL, but the paper notes it is provably optimal only in limited cases such as linear quadratic regulators.The authors contrast this with optimism-based approaches for continuous state and action spaces, which they describe as less explored.Source: §1 · p. 2
• Existing continuous-domain optimistic approaches include methods that are intractable to implement, while Thompson sampling requires tractable posterior sampling and may be limited by approximate inference.The paper notes that GP-UCRL is intractable in practice and that posterior sampling is intractable for GP models with continuous domains.Source: §1 · pp. 2–3

2.1 Model-based Reinforcement Learning

• The setting uses episodic control with unknown dynamics, a known reward function, and one real-system rollout per iteration to collect transition data.The model estimates plausible dynamics from collected data and is required to satisfy a calibration condition.Source: §2.1 · pp. 3–4
• Calibration requires the true dynamics to lie within a confidence interval around the model mean, with width determined by predictive uncertainty and a sequence β_t.The stated condition holds jointly over iterations, states, and actions with probability at least 1 − δ.Source: §2.1 · p. 4

2.2 Exploration Strategies

• Greedy exploitation optimizes expected performance under the current model, while Thompson sampling optimizes against one posterior-sampled model per episode.The paper notes that greedy exploration is inefficient in general, though it can work without regret for some structures such as linear-quadratic control; posterior sampling can be intractable.Source: §2.2 · pp. 4–5
• UCRL jointly optimizes policies and plausible models, but this optimization is generally intractable and standard greedy planners do not solve its objective.Plausible models are those inside confidence intervals around the estimated dynamics.Source: §2.2 · p. 5

3 Hallucinated Upper Confidence Reinforcement Learning (H-UCRL)

• H-UCRL represents each plausible model as the mean dynamics plus predictive uncertainty scaled by a bounded function η, then optimizes over η instead of the model directly.The policy selects the next-state distribution, while η selects an optimistic outcome within the one-step confidence interval.Source: §3 · p. 5

3.1 Solving the Optimization Problem

• Treating η as a hallucinated control input converts the optimistic objective to greedy exploitation on an augmented action space of dimension q + p.The method requires calibration for one-step predictions and recursively plans an optimistic trajectory using pointwise uncertainty estimates.Source: §3 · p. 5, §3.1 · p. 6
• The proposed solver combines offline policy search and online planning: learned policies warm-start planning, while a learned critic bootstraps the planning horizon.Planning reduces model bias relative to pure policy search; policy search shortens the planning horizon and accelerates planning.Source: §3.1 · p. 6

3.2 Theoretical Analysis

• Under Assumptions 1–3, the regret bound depends on model complexity I_T(S, A); sublinear growth of this quantity yields policies approaching optimal performance.The analysis also depends on the horizon and relevant Lipschitz constants.Source: §3.2 · p. 7
• For Gaussian Process models, I_T is bounded by worst-case mutual information, yielding a sublinear regret bound for commonly used kernels including the squared exponential kernel.The stated bound depends on the functional complexity B_f and model and state-action dimensions.Source: §3.2 · p. 7
• On Reacher and Pusher, exploration strategies perform equally, whereas H-UCRL outperforms alternatives on Sparse-Reacher and Half-Cheetah.The figure reports mean final episodic returns averaged over five random seeds.Source: Figure 3 · p. 8

Sparse Inverted Pendulum

• For ρ = 0.2, only H-UCRL successfully swings up the sparse-reward inverted pendulum.Without action penalties, all methods perform equally well; at ρ = 0.1, greedy sometimes finds the swing-up sequence.Source: §4 · p. 8

Half-Cheetah

• H-UCRL learns faster than greedy exploitation and Thompson sampling across all action penalties in Half-Cheetah.At larger penalties, greedy and Thompson sampling can get stuck in local optima with poor performance.Source: Figure 4 · p. 9, §4 · p. 9

7-DOF PR2 Robot

• All strategies achieve state-of-the-art performance on quadratic-reward Reacher and Pusher tasks, where greedy exploitation appears sufficient.The authors suggest over-actuated dynamics and reward structure may explain this pattern.Source: §4 · p. 9
• On sparse-reward Reacher, H-UCRL outperforms alternatives, particularly at larger action penalties.The sparse reward signals favor being near the goal and using actions close to zero.Source: §4 · p. 9

H-UCRL vs. Thompson Sampling

• The authors suggest Thompson sampling’s weaker performance reflects a need for posterior models calibrated across full trajectories, rather than calibrated one-step confidence intervals.H-UCRL uses ensemble members to form one-step confidence intervals, whereas Thompson sampling samples one model for the full horizon.Source: §4 · p. 9

• H-UCRL reduces optimistic exploration to greedy exploitation in an augmented policy space, and the analysis shows sublinear regret for some models.Experiments report performance as good as or better than other exploration algorithms, with state-of-the-art results on evaluated tasks.Source: §5 · p. 9

Broader Impact

• Improving sample efficiency could reduce the cost of optimizing RL policies for applications such as robotics, renewable energy, and medical decision-making.The paper notes that potential misuse of the overall RL framework cannot be ruled out.Source: Broader Impact · p. 10

Appendix

• The appendix section provides an overview of its contents.Source: Appendix · p. 16

A Expected Performance for Exploration in the Bandit Setting

• The bandit example reduces control to maximizing an unknown function of policy parameters θ at a fixed context, using a one-step, one-dimensional system with linear reward.Source: A Expected Performance for Exploration… · p. 17
• Expected-performance optimization maximizes the posterior mean, equivalent to GP-UCB with βt = 0, and is known to get stuck in local optima.In the illustrated comparison, β = 2 evaluates parameters with close-to-optimal performance after few evaluations, unlike β = 0.Source: A Expected Performance for Exploration… · pp. 17–18, Figure 5 · p. 18

B.1 Experimental Setup

• The experiments use probabilistic ensembles and Gaussian-process models, with predictive means and variances supplying the model estimates.Ensemble training assigns transitions to members using Poisson(1) sampling; GP hyperparameters are not optimized because this can get stuck in local minima.Source: §B.1 · p. 18
• Policy search uses a modification of MPO with hallucinated data augmentation and value expansion, while planning uses Dyna-MPC and cross-entropy sampling.For greedy exploitation, the PE-DS trajectory-sampling algorithm is used because it has the same predictive uncertainty as H-UCRL.Source: §B.1 · pp. 18–19

B.2.1 Swing-Up Inverted Pendulum

• H-UCRL finds a swing-up maneuver quickly in the inverted pendulum, even with high action penalties.The learning curves cover five random seeds.Source: §B.2.1 · p. 19, Figure 6 · p. 19

B.2.2 Mujoco Cart Pole

• For Cart-Pole, action penalty 0.2, H-UCRL finds a swing-up maneuver by episode five, while Thompson sampling does so in one run after episode 35.At action penalty 0.05, H-UCRL outperforms the other algorithms.Source: §B.2.2 · p. 19, Figure 7 · p. 20

B.2.3 Reacher

• In Reacher, greedy, Thompson sampling, and H-UCRL perform equally well across action penalties.Source: §B.2.3 · p. 20, Figure 8 · p. 20

B.2.4 Pusher

• In Pusher, greedy, Thompson sampling, and H-UCRL perform equally well across action penalties.Source: §B.2.4 · p. 21, Figure 9 · p. 21

B.2.5 Sparse Reacher

• In sparse Reacher, H-UCRL performs better than greedy and Thompson sampling, particularly with larger action penalties.Source: §B.2.5 · p. 21, Figure 10 · p. 22

B.2.6 Half-Cheetah

• With action penalty 1, H-UCRL finds quicker Half-Cheetah policies with higher returns and considerably outperforms greedy and Thompson sampling.The Half-Cheetah episode lasts 1000 time steps.Source: §B.2.6 · p. 22

B.3.1 H-UCRL Trajectories

• In the inverted pendulum, H-UCRL finds an optimistic trajectory to the goal in the first episode; with more episodes, simulated and real trajectories match.As the action penalty rises, action magnitude decreases and finding a swing-up trajectory takes longer.Source: §B.3.1 · p. 23, Figure 12 · p. 23, Figure 13 · p. 23

B.4.1 Can the sampled models solve the task?

• Thompson sampling's simulated returns are also low, indicating no model bias; the algorithm cannot solve the task with its sampled model.The comparison uses the last simulated trajectory from each episode's bottom position.Source: §B.4.1 · p. 24, Figure 15 · p. 24

B.4.2 Is it variance starvation?

• Thompson sampling's predictive variance does not shrink, so the experiments find no variance starvation in one-step-ahead predictions.The plotted uncertainty summarizes ensemble predictive variance using the trace of a covariance-matrix Cholesky factorization.Source: §B.4.2 · p. 25, Figure 16 · p. 25

B.4.3 Is the number of ensemble members enough?

• With action penalty 0.1, ensembles of 20, 50, and 100 find swing-up in only one of five runs; with penalty 0.2, none do.Larger ensembles may help, but this is not convincing, and training complexity grows linearly with ensemble size.Source: §B.4.3 · p. 25, Figure 17 · p. 25

B.4.4 Is it the bootstrapping procedure during Training?

• Without bootstrapping, learning curves closely follow those with bootstrapping, so the authors conclude bootstrapping is likely not the cause of Thompson sampling’s failure.Without bootstrapping, model discrepancies come from initialization; the models learn from consistent trajectories.Source: §B.4.4 · p. 26, Figure 18 · p. 26

B.4.5 Are probabilistic ensembles not a good approximation to the posterior in Thompson sampling?

• With action penalties above zero, neither RFF nor QFF Thompson sampling finds a swing-up maneuver, whereas optimistic exploration with both feature models does.At zero penalty, optimistic exploration with RFF underperforms greedy exploitation and Thompson sampling, which the authors suggest might reflect RFF variance starvation.Source: §B.4.5 · p. 26, Figure 19 · p. 27

B.4.6 Is it the optimization procedure?

• With five ensemble heads, optimistic exploration finds a swing-up trajectory after the first episode, while the best head returns zero; at penalty 0.2 it never finds one within ten episodes.At penalty 0.1, the best head finds a swing-up trajectory after ten episodes, indicating that optimization can find such a policy for a single model even when Thompson-sampling data collection does not.Source: §B.4.6 · p. 27, Figure 20 · p. 27

B.4.7 Conclusions

• The authors suspect one-step uncertainty does not capture the diversity of plausible multi-step trajectories needed for Thompson sampling; an ensemble with B members may require BN members for N-step predictions.They identify tractable approximate posteriors with sufficient multi-step variance as an open challenge.Source: §B.4.7 · pp. 27–28
• H-UCRL and UCRL implement optimism deterministically and recursively, requiring only one-step calibrated predictive uncertainties rather than sampled multi-step models.The authors suggest this may make optimism better suited than approximate Thompson sampling in model-based reinforcement learning.Source: §B.4.7 · p. 28

C Solving the Augmented Greedy Exploitation Program

• The augmented greedy-exploitation problem is a stochastic optimal-control problem for the hallucinated model, solvable by offline policy search, online planning, or their combination.The appendix describes these solver families in separate subsections.Source: C Solving the Augmented Greedy… · p. 29

C.1 Offline Policy Search

• Offline search can optimize hallucinated control through data augmentation, back-propagation through time, or value expansion, with different exposure to model bias and gradient variance.HDA generates optimistic data for a model-free learner and can suffer compounding model bias; HBPTT differentiates through sampled trajectories and can have high variance, which KL regularization helps control; HVE uses optimistic trajectories for Bellman targets and suffers less model bias but is usually less data efficient than BPTT or IDA.Source: §C.1 · pp. 29–30

C.2 Online Planning

• Online planning jointly optimizes true and hallucinated inputs; H-MPC adapts MPC solvers, while MPC reduces model bias but has high online computational costs.Differential dynamic programming and sampling or linearization methods are among the described planning approaches; MPC methods are limited by planning horizon unless a learned terminal reward approximates reward-to-go.Source: §C.2 · pp. 30–31, §C.3 · p. 31

C.3 Combining Offline Policy Search with Online Planning

• Dyna-MPC learns parametric true and hallucinated policies, then uses them to warm-start the planning algorithm’s sampling distributions.This combines policy search with sampling-based planning; the section distinguishes Dyna-MPC from POPLIN by its policy-search optimization rather than cross-entropy optimization.Source: §C.3 · p. 32

D Proofs for Exploration Regret Bound

• The appendix introduces the proof of the main exploration regret theorem and defines notation for states under the true and optimistic dynamics.The optimistic dynamics are written as the model mean plus predictive uncertainty scaled by a hallucinated input.Source: D Proofs for Exploration Regret Bound · p. 33, §D.1 · p. 33

D.1 Notation

• Under the stated Lipschitz assumptions on the open-loop dynamics and policy, the closed-loop system is also Lipschitz continuous.The section also fixes the two-norm convention when no norm is specified.Source: §D.1 · p. 33

D.2 Bounding the Regret

• The analysis bounds instantaneous regret by comparing the optimistic value estimate with the true value under the same policy.The proof uses the fact that the true dynamics are feasible in the optimistic model set, followed by bounds on value and trajectory deviations.Source: §D.2 · p. 34
• Trajectory deviations are bounded using predictive uncertainty along the true trajectory, with Lipschitz continuity controlling deviations between true and optimistic states.The illustrated confidence intervals contain the true state after one step, but not necessarily beyond one step because optimistic dynamics are iteratively evaluated at optimistic states.Source: §D.2 · p. 34, Figure 21 · p. 34
• The resulting instance-dependent regret bound depends on predictive uncertainty at states visited under the true dynamics.The analysis then replaces this data-dependent uncertainty with a worst-case bound.Source: §D.2 · pp. 35–36
• Theorems 1 and 2 bound H-UCRL regret in (7) for all T ≥ 1 under Assumptions 1–3, with probability at least 1 − δ.Theorem 1 assumes sₙ,ₜ ∈ S and aₙ,ₜ ∈ A; Theorem 2 assumes sₙ,ₜ ∈ Sₜ, Sₜ₋₁ ⊆ Sₜ, and aₙ,ₜ ∈ A.Source: §D.2 · p. 37

E Properties of the Functions η(·)

• Optimizing over Lipschitz-continuous η functions generally preserves the optimistic regret bounds, but their complexity can increase as predictive variance decreases.At zero variance, η may need to be discontinuous; meanwhile, its effect on the dynamics decreases with σ.Source: E Properties of the Functions η(·) · p. 38

F Background on Gaussian Processes

• A Gaussian process specifies a distribution over functions through a prior mean and covariance kernel, with posterior mean and uncertainty obtained from noisy observations.The work assumes a zero prior mean without loss of generality.Source: F Background on Gaussian Processes · p. 38

F.1 Information Capacity

• The information capacity γ_t measures function-class complexity and grows sublinearly in t for many commonly used kernels, including the Gaussian kernel.For Gaussian processes, mutual information depends on the sampled inputs rather than the observed measurement values.Source: §F.1 · p. 39

F.2 Functions in a Reproducing Kernel Hilbert Space

• An RKHS represents functions as kernel expansions, and its norm measures their complexity relative to the chosen kernel.Functions in the RKHS are Lipschitz continuous with respect to the kernel metric, with smoothness controlled by the norm.Source: §F.2 · pp. 39–40

F.2.1 Confidence Intervals

• For bounded-RKHS-norm functions with sub-Gaussian observation noise, Gaussian-process posterior intervals can provide high-probability confidence bounds across the domain.These bounds do not require a probabilistic assumption on the underlying function, which may be fixed adversarially.Source: §F.2.1 · p. 40

F.3 Extension to multiple dimensions

• The confidence-bound construction extends to vector-valued outputs by adding an input index for the output dimension.The resulting guarantee holds jointly over parameters, output indices, and iterations.Source: §F.3 · p. 40

G Lipschitz Continuity of Gaussian Process Predictions

• Gaussian-process posterior standard deviation is Lipschitz in the kernel metric, supporting regularity bounds for GP predictions.Existing bounds that scale with the number of data points would make the paper’s regret bound superlinear, motivating a data-independent regularity bound.Source: G Lipschitz Continuity of Gaussian… · p. 41

H.1 Assumptions about the model

• A Lipschitz kernel and kernel metric, together with a bounded RKHS norm, support Lipschitz dynamics and calibrated Gaussian-process confidence bounds.The assumptions permit confidence intervals for model error and a bound on the vector-output error.Source: §H.1 · p. 42

H.2 Bounding IT for the GP model

• For independent-output Gaussian processes with a squared exponential kernel, the information-capacity bound makes the overall regret bound sublinear.For the Matérn kernel, the stated best-known capacity bound does not yield sublinear regret for long trajectories, though the authors expect the bound to be loose.Source: §H.2 · p. 44

H.3 Comparison to Chowdhury and Gopalan (2019)

• The comparison with Chowdhury and Gopalan (2019) notes that their value-function smoothness assumption avoids explicit reasoning about full trajectory deviations.Their dynamics-Lipschitz restriction also avoids β_N dependence but relies on system properties that can be difficult to estimate.Source: §H.3 · p. 45

H.3.1 Our bound under the assumptions of (Chowdhury and Gopalan, 2019)

• Under the comparison’s Lipschitz-dynamics assumption, the paper obtains regret bounds matching Chowdhury and Gopalan (2019) up to constant factors.This optimization is not tractable in the noisy case; the paper identifies β_N as the cost of not optimizing over such dynamics.Source: §H.3.1 · pp. 45–46

I Extension to Unbounded Domains

• The extension handles potentially unbounded noise by bounding the state domain with high probability, avoiding a compact-domain assumption for the dynamics analysis.The section notes that compactness conflicts with noise distributions of unbounded support and that bounded dynamics cannot generally be assumed even for linear systems.Source: I Extension to Unbounded Domains · p. 46

I.1 Bound on Aleatoric Uncertainty (Noise Bound)

• For i.i.d. sub-Gaussian noise, the analysis bounds noise over all time steps with high probability, at the cost of an O(·) increase in confidence intervals.The supplied passage leaves the order expression incomplete, so no specific rate is stated.Source: §I.1 · p. 48

I.2 Bounding the Domain Under Aleatoric Uncertainty

• With probability at least 1 − δ, states across iterations lie in a norm-ball centered at s₀ with radius b_t.The domain bound follows from Lipschitz dynamics and a high-probability bound on the transition noise.Source: §I.2 · pp. 48–49

I.3 Regret bounds over Unbounded Domains

• The unbounded-domain regret result combines the model-calibration and domain bounds, holding jointly with probability at least 1 − 2δ.The theorem assumes sub-Gaussian noise, compact actions, and bounded initial-step dynamics.Source: §I.3 · p. 50

I.4 Bounding the Maximum Information Capacity for Gaussian Processes

• Because the domain radius grows at a logarithmic rate, the information-capacity increase adds only a logarithmic factor to regret relative to a fixed domain.The passage states this conclusion for the Gaussian-process information-capacity analysis.Source: §I.4 · p. 51