Conservative Dual Policy Optimization for Efficient Model-Based Reinforcement Learning
Authors: Shenao Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
Model-Based Reinforcement Learning

Abstract: Provably efficient Model-Based Reinforcement Learning (MBRL) based on optimism or posterior sampling (PSRL) is ensured to attain the global optimality asymptotically by introducing the complexity measure of the model. However, the complexity might grow exponentially for the simplest nonlinear models, where global convergence is impossible within finite iterations. When the model suffers a large generalization error, which is quantitatively measured by the model complexity, the uncertainty can be large. The sampled model that current policy is greedily optimized upon will thus be unsettled, resulting in aggressive policy updates and over-exploration. In this work, we propose Conservative Dual Policy Optimization (CDPO) that involves a Referential Update and a Conservative Update. The policy is first optimized under a reference model, which imitates the mechanism of PSRL while offering more stability. A conservative range of randomness is guaranteed by maximizing the expectation of model value. Without harmful sampling procedures, CDPO can still achieve the same regret as PSRL. More importantly, CDPO enjoys monotonic policy improvement and global optimality simultaneously. Empirical results also validate the exploration efficiency of CDPO.

Conservative Dual Policy Optimization for Efficient Model-Based Reinforcement Learning
Shenao Zhang Georgia Institute of Technology Atlanta, GA 30332 shenao@gatech. edu
Abstract
Provably efficient Model-Based Reinforcement Learning (MBRL) based on op- timism posterior sampling (PSRL) is ensured attain the global optimality asymptotically by introducing the complexity measure of the model. However, the complexity might grow exponentially for the simplest nonlinear models, where global convergence is impossible within finite iterations. When the model suffers a large generalization error, which is quantitatively measured by the model complex- ity, the uncertainty can be large. The sampled model that current policy is greedily optimized upon will thus be unsettled, resulting in aggressive policy updates and werrexploratioo. In this work, we propose Conservative Dual Policy Optimization (CDPO) that involves a Referential Update and Conservative Update. The policy is first optimized under a reference model, which imitates the mechanism of PSRL while offering more stability. conservative range of randomness is guaranteed by maximizing the expectation of model value. Without harmful sampling procedures, CDPO can still achieve the same regret as PSRL. More importantly, CDPO enjoys monotonic policy improvement and global optimality simultancously. Empirical results also validate the exploration efficiency of CDPO.
Introduction
Model-Basse Reinforcement Learning (MBRL) involves acquiring model by interacting with the enviromment and learning to make the optimal decision using the model [55, 32). MBRL is appealing due to its significantly reduced sample complexity compared to its model-free counterparts. However, greedy model exploitation that assumes the model is sufficiently accurate lacks guarantees for global optimality. The policies can be suboptimal and get stuck at local maxima even in simple tasks [10].
As such, several provably-effiiieet MBRL algorithms have been proposed. Based on the principle of optimism in the face of uncertainty (OFU) [56, 49, 10], -FU-RL achieves the global optimality by ensuring that the optimistically biased value is close to the real value in the long run. Based on Thompson Sampling [62], Posterior Sampling RL (PSRL) [57, 42, 43] explores by greedily optimizing the policy in an MDP which is sampled from the posterior distribution over MDPs. Beyond finite MDPs, to obtain general bound that permits sample efficiency in various cases,
need introduce additional complexity measure, For example, [49, 43] provide an Ö(vdgT) regret for both OFU and PSRL with eluder dimension dg capturing how effectively the model generalizes. However, it is recently shown [13, 33] that the eluder dimension for even the simplest nonlinear models cannot be polynomially bounded. The effectiveness of the algorithms will thus be crippled.
The underlying reasons for such ineffectiveness exploration issue. Specifically, when a nonlinear model is used to fit complex transition functions, its generalizability will be poor compared simple linear problems. If random model is selected from the large hypothesis, e.g., optimistically chosen or sampled from the posterior, it is "unsettled".
the aggressive policy updates and the over-
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In other words, the selected model can change dramatically between successive iterations. Policy updates under this model will also be aggressive and thus cause value degradation. What's worse, large epistemic uncertainty results in an unrealistic model, which drives agents for uninformative exploration. An exploration step can only eliminate an exponentially small portion of the hypothesis.
In this work, we present Conservative Dual Policy Optimization (CDPO), simple yet provable MBRL algorithm. As the sampling process in PSRL harms policy updates due to the unsettled model during training, we propose the Referential Update that greedily optimizes an intermediate policy under reference model. It mimics the sampling- carpllnngtten-opeee -petimiiiiiitionn procedure in PSRL but offers more stability since we are free to set steady reference model. We show that even without a sampling procedure, CDPO can match the expected regret of PSRL up to constant factors for any proper reference model, e.g., the least squares estimate where the confidence set is centered at. The Conservative Update step then follows to encourage exploration within a reasonable range. Specifically, the objective of a reactive policy is to maximize the expectation of model value, instead of a single model's value. These two steps are performed in an iterative manner CDPO.
Theoretically, we show the statistical equivalence between CDPO and PSRL with the same order of expected regret. Additionally, we give the iterative policy improvement bound of CDPO, which guarantees monotonic improvement under mild conditions. We also establish the sublinear regret of CDPO, which permits its global optimality equipped with any model function class that has a bounded complexity measure. To our knowledge, the proposed framework is the first that simultanoousy enjoys global optimality and iterative policy improvement. Experimental results verify the existence of the over-exploration issue and demonstrate the practical benefit of CDPO.
2 Background
2.1 Model-Based Reinforcement Learning
We consider the problem of learning to optimize an infinite-horizon 7-discounted Markov Decision Process (MDP) over repeated episodes of interaction. Denote the state space and action space as S and A. respectively. When taking action a E A at state E S, the agent receives reward r(s, a) and the environment transits into measure for deterministic dynamics and is probability distribution for probabilistic dynamics.
state according to probability s' ~ f (-Iss a). Here, f is dirac
In model-based RL,, the true dynamical model f is unknown and needs to be learned using the collected data through episodic (or iterative) interaction. The history data up to iteration then forms
H4 = ssss On.i: 1.. ) ---11-1 where H is the actual timesteps agents run in an episode. The posterior distribution of the dynamics model is estimated as (f-(HH)). Alternatively, the frequentist model of the mean and uncertainty can also be estimated. Specifically, consider the model function class F = (ʃ S A + S) with size [F], which contains the real model f" E F. The confidence set (or model hypothesis set) F, C F is introduced to represent the range of dynamics that is statistically plausible [49, 43, 10]. To ensure that f F, with high probability, one way is to construct the confidence set as F, := ( E FIll - 17.., S vBr). Here, 3, is an appropriately chosen confidence parameter (via concentration inequality), the cumulative empirical 2-norm is defined by ||911, F, := - 1-1 [1: The least squares estimate is
h= J==1-
fLS. argmin Σ a) s'1
(2.1)
JEF
(s,a,"")EH,
Denote the state and state-action value function associated with æ on model f by V22 S - IR and Qf : S x A + R, respectively, which are defined as
Vi((s E Σ rrs,,, an) so = s, s] (f(ssa)= = E
Σ
yh Mrss az) so = s,
=, ag = a, ,,
-h=0
The objective of RL is learn a policy .- argmax, (IT) that maximizes the expected return (Tr). Denote the initial state distribution as Ç. Under policy r, the state visitation measure 1x (s)
over S and the state-action visitation measure Pa (s, a) over S x A in the true MDP are defined as
(s) = (1 7)-
nh P(sn = =), ()) = (1 - 7)
A F(sh = s, an = =a), (2.2)
h
h=0
2

---

where ~ ~w, an ~ (-(sk) and 8h+1 (+(-(s,, an). The objective J(T) is then
J(T) Beg~< VV (5o)] = ((s.))rp
(2.3)
2.2 Cumulative Regret and Asymptotic Optimality
common criterion to evaluate RI algorithms is the cumulative regret, defined as the cumulative performance discrepancy between policy at each iteration and the optimal policy π over the run of the algorithm. The (cumulative) regret up to iteration T is defined as:
/
Regret fT,
Σ
(()) (s) V.. [=1
(2.4)
In the Bayesian view, the model f*, the learning policy and the regret are random variables that must be learned from the gathered data. The Bayesian expected regret is defined as:
BayesRegret ग, Φ) == E [Regret 5" f Φ)
(2.5)
One way to prove the asymptotic optimality is to show that the (expected) regret is sublinear in T, so that my converges to within sufficient iterations. To obtain the regret bound, the width of confidence ser we (s, a) is introduced to represent the maximum deviation between any two members in Fr:
wr a) sup [f(s,a) - f(s,a)lla
(2.6)
1JA
3 Provable Model-Based Reinforcement Learning
In this section, we analyze the central ideas and limitations of greedy algorithms as well as two popular theoretically justified frameworks: optimistic algorithms and posterior sampling algorithms.
Greedy Model Exploitation. Before introducing provable algorithms, we first analyze greedy model- based algorithms. In this framework. the agent takes actions assuming that the fitted model sufficiently accurately resembles the real MDP. Algorithms that lie this category can be roughly divided into two groups: model-based planning and model-augmented policy optimization. For instance, Dyna agents [61, 20, 17] optimize policies using model-free learners with model-generated data. The model also be exploited in first-order gradient estimators [18, 12, 9] or value expansion [15, 6]. On the other hand, model-based planning, or model-predicie control (MPC) [40, 41], directly generates optimal action sequences under the model receding horizon fashion.
However, greedily exploiting the model without deep exploration [45] will lead to suboptimal per- formance. The resulting policy can suffer from premature convergence, leaving the potentially high-reward region unexplored. Since the transition data is generated by the agent taking actions in the real MDP, the dual effect [4, 27] that current action influences both the next state and the model uncertainty is not considered by greedy model-base algorithms.
Optimism in the Face of Uncertainty. A common provable exploration mechanism is adopt the principle of optimism in the face of uncertainty (OFU) [56, 49, 10]. With OFU, the agent assigns to its policy an optimistically biased estimate of virtual value by jointly optimizing over the policies and models inside the confidence set F,, At iteration ł, the OFU-RL policy is defined as:
T = argmax max V!A. F.F.
(3.1)
Most asymptotic analyses of optimistic RL. algorithms can be abstracted as showing two properties: the virtual value / is sufficiently high, and it is close to the real value V/" in the long run. However, in complex environments where the generalizability of nonlinear models is limited, large epistemic uncertainty will result in an unrealisticalyy large optimistic return that drives agents for uninformative exploration. What's worse, such suboptimal exploration steps eliminate only small portion of the model hypothesis [13], leading to slow converging process and suboptimal practical performance.
Posterior Sampling Reinforcement Learning. alternative exploration mechanism is based on Thompson Sampling (TS) [62, 52], which involves selecting the maximizing action from statistically
3

---

plausibly set of action values. These values can be associated with the MDP sampled from its posterior distribution, thus giving its name posterior sampling for reinforcement learning (PSRL) [57. 42, 43]. The algorithm begins with prior distribution of f" At each iteration I, a model ft. is sampled from the posterior (f-(H)), and nt updated be optimal under fe:
St ~ 1 (1HHH)), मe = argmax V
(3.2)
The insight is to keep away from actions that are unlikely to be optimal in the real MDP. Exploration is guaranteed by the randomness in the sampling procedure. Unfortunately, executing actions that are optimally associated with single sampled model can cause similar over-exploration issues [52, 51J. Specifically, an imperfect model sampled from the large hypothesis can cause aggressive policy updates and value degradation between successive iterations. The suboptimality degree of the resulting policies depends on the epistemic model uncertainty. Besides, executing H, is not intended to offer performance improvement for follow-up policy learning, but only to narrow down the model uncertainty. However, this elimination procedure will be slow when the model suffers a large generalization error, which is quantitatively formulated in the model complexity measure below.
Complexity Measure and Generalization Bounds. In RI,, we seek to have the sample complexity for finding a near-optimal policy or estimating accurate value function. When given access to generative model (i.e., an abstract sampling model) in finite MDPs, it is known that the (minimax) number of transitions the agent needs observe can be sublinear in the model size, i.c. smaller than ((S))AA)). Beyond finite MDPs where the number of states is large (or countably or uncountably infinite), we are interested in the learnability or generalization of RL. Unfortunately, it is impossible for agnostic reinforcement learning that finds the best hypothesis in some given policy, value, or model hypothesis class: the number of needed samples depends exponentially on the problem horizon [24]. Despite of the structural assumptions, e.g. linear MDPs [66, 22, 65] or low-rank MDPs [21, 38), we focus on the generalization bounds that can cover various cases. This can be done with additional complexity measure, e.g. eluder dimension [49], witness rank [60], or bilinear rank [14].
By introducing the eluder dimension dg [49], previous work [43, 44] established regret Ö T for both OFU-RL and PSRL. Intuitively, the eluder dimension captures how effectively the model learned from observed data can extrapolate to future data, and permits sample efficiency in various (linear) cases. Nevertheless, it shown in [13, 33] that even the simplest nonlinear models do not have a saynommalll-boondde eluder dimension. The following result is from Thm. 5.2 in Dong et al. [13] and similar results are also established in [33].
Theorem 3.1 (Eluder Dimension of Nonlinear Models [13)). The eluder dimension dim (F, E) (c.f. Definition 5.6) of one-layer ReLU neural networks is at least ((==(d-1)), where d is the state-action dimension, i.e. (s,a) a) Rdd With more layers, the requirement of ReLU activation can be relaxed.
As result, additional complexity is hidden in the eluder dimension, e.g. when we choose e = T regret ((VdgT) contains dg = (((T-1)) and is no longer sublinear in T. In this case, previous provable exploration mechanisms will lose the desired property of global optimality and sample efficiency, which is the underlying reason for the over-exploration issue.
4 Conservative Dual Policy Optimization
When using nonlinear models, e.g. neural networks. the over-exploration issue causes unfavorable performance in practice, in terms of slow convergence and suboptimal asymptotic values. To tackle this challenge, the key is to abandon the sampling process and have guarantees during training.
In this regard, we propose Conservative Dual Policy Optimization (CDPO) that is simple yet provably efficient. By optimizing the policy following two successive update procedures iteratively, CDPO simultaneously enjoys monotonic policy value improvement and global optimality properties.
4.1 CDPO Framework
To begin with, consider the problem of maximizing the expected value, ,, = argmax, B[V!") HH)), where E [H.] denotes the expected values over the posterior. Obviously, we have the expected value improvement guarantee [[VV [H,] E[V H.). We can also perform expected value

---

maximization in a trust-region to guarantee iterative improvement under any f". However, such updates will lose the desired global convergence guarantee and may get stuck at local maxima even with linear models. For this reason, we propose a dual procedure of policy optimization.
Referential Update. The first update step returns an intermediate policy, denoted as qc- This step a greedy one in the sense that q is optimal with respect to the value of a single model fts which we call a reference model. Selecting a reference model and optimizing a policy w.r.t. imitates the sampling-optimizaton procedure of PSRL. We will show in Section 5.1 that if we pose the constraint ft E Ft, then CDPO achieves the same expected regret PSRI., which implies global optimality.
More importantly, policy optimization under fe is more stable and can avoid the over-exploration issue in PSRL since we are free to set it as a steady reference between successive iterations. For example, we fix the reference model ft as the least squares estimate FIJS defined in (2.1), instead of a random model sampled from the large hypothesis that causes aggressive policy update. This gives us:
Referential Update (with LS Reference):
qt = argmax Vi
(4.1)
Constrained Conservative Update. The conservative update then follows as the second stage of CDPO, which takes input qt and returns the reactive policy TT
Conservative Update: n, = argmax B[VA/ [H,], s.t. Rowvn (T)( S 5n, (4.2)
where -rv(:-) stands for the total variation distance and 17 is the hyperparameter that characterizes the trust-region constraint and controls the degree of exploration.
Compared with OFU-RL. and PSRL., the above exploration and policy updates are conservative since the policy maximizes the expectation of the model value, instead of single model's value (i.e. the optimistic model in OFU-RL and the sampled model PSRL). The conservative update (4.2) avoids the pitfalls when the optimistic model or the posterior sampled model suffers large bias, which leads to aggressive policy updates and over-exploration during training. Notably, the term conservative in our work differs from previous use, e.g. Conservative Policy Iteration [23, 53). While the latter refers to policy updates with constraints, ours is to emphasize the conservative range of randomness and the reduction of unnecessary over-exploration by shelving the sampling process.
In our analysis, we follow previous work [43, 59, 10, 35] and assume access to a policy optimization oracle. In practice, the problem of finding optimal policy under a given model can be approximately solved by model-based solvers listed below. More fine-grainer analysis can be obtained by applying off-the-shelf results established for policy gradient MPC for specific policy or model function classes. This, however, is beyond the scope of this paper.
4.2 Practical Algorithm
The pseudocode of CDPO in Alg. The model-based solver MBPO f. outputs the policy (9: or Re) that optimizes the objec- tive I with access to model f. Several dif- ferent types of solvers can be leveraged, e.g., model-augmented model-free policy optimiza- tion such as Dyna [61], model-based reparame-
Algorithm Practical CDPO Algorithm
Input: Prior Φ, model-based policy optimization solver MBPD J)..
for iteration = 1, ..., T do ge +- MBPO FL.. (4.1))
3: Sample N models [ J==l
terization gradient [18, 9]. or model-predictive control [63]. Details different optimization choices can be found in Appendix E. In exper- iments, we use Dyna and MPC solvers.
4:
ne < MBPO Qt, {ftm 1N 1. (4.2))
Execute π. in the real MDP
6: Update H4+1 = M4 U {SN., an 1,h
7: Update ÍL.S and Φ
8: end for return policy nт
With Pinsker's ss inequality, the total variation
constraint in (4.2) is replaced by the KL di- vergence [53, 2] in experiments. We follow previous work [34] to use neural network ensembles [10, 25] for model estimation and use calibra- tions [29, 10] for accurate uncertainty measure.
5

---

5
Analysis
In this section, we first show the statistical equivalence between CDPO and PSRL in terms of the same BayesRegret bound. Then we give the iterative policy value bound with monotonic improvement. Finally, we prove the global convergence of CDPO. The missing proofs can be found in the Appendix.
5.1 Statistical Equivalence between CDPO and PSRL
We begin our analysis by highlighting the connection between CDPO and PSRL with the following theorem, from which we also show the role of the dual update procedure and the reference model. Theorem 5.1 (CDPO Matches PSRL in BayesRegret). Let n PSRLL be the policy of any posterior sampling algorithm for reinforcement learning optimized by (3.2). If the BayesRegret bound of π PSRL satisfies that for any T > O, BayesRegret n PSRL Φ) < D, then for all T > O, we have for the CDPO policy n CDPP that BayesRegret π CDPO, 6) S 3D.
Sketch proof. We first sketch the general strategy in the PSRI. analysis. Recall the definition of the Bayesian expected regret (ayesRegret((; ; () == E R.), where Ri Vz- VVL" PSRL breaks down R, by adding and subtracting Vi, the value of the imagined optimal policy xy under sampled model fa, i.e. ff argmax, V
PSRL: Ri V
V.." de
-f -
V..
VL + Ki 4/ 'A
VJ.
VV-
(5.1)
where the second equality follows from the definition of the PSRL policy. Following the law of total expectation and the Posterior Sampling Lemma (e.g. Lemma in [42]). we have B V by noting that f* and St are identically distributed conditioned upon H4. Then we obtain
T
BayesRegret PSRL 6)
E
Vi T.
S
7
E E [[]]f((sh,a)) an) - ( an [12]
4/
L
T
S 48
Σ
K[we] + 4y8T SDD D,
(5.2)
where the first inequality follows from the simulation lemma under the L-Lipschitz value assumption [43]. The second inequality follows from the definition of wi in (2.6) and the construction of con- fidence set such that P(f NFF)= 2 1 28 and P(f E FiF. f E (F)= > 1 - 46 via union bound. As more data is collected, the model uncertainty is reduced and the sum of confidence set width Wt will be sublinear in 7 (c.f. Lemma B.5 and B.6), indicating sublinear regret.
When it comes to CDPO, we decompose the regret as
CDPO:
H4 = vf. V vaf"
v Ts.
Vh. %i.
Vf Vff V
(5.3)
where the CDPO policy n, is defined in (4.2). Since B|v="
V O, we have
T
BayesRegret (T, x CDPO
x)
EIV!
vhl m + vh - V
1=1
T
T
BVV - v 4/. + + - vil +
v
3E|wy + 8,8T S 3D, (5.4) 1 48
[=1
where the first inequality follows from the greediness of de and m. in the dual update steps, i.e., Vh. < <V.. for any Ty as well as B[V[ 2 E[V The 8&T term is introduced since fo E Fi and g.
P(f E F.. FFF 28.
Theorem 5.1 indicates that although CDPO performs conservative updates and abandons the sampling process, it matches the statistical efficiency of PSRL up to constant factors.
The importance of the reference model and the dual procedure is also reflected in the proof. The referential update builds the bridge between Vi and ViJ. Policy optimization under the reference model mimics the the reference is steady, e.g., the least squares estimate we use. We formalize this idea below.
procedure of PSRL while offering more stability when

---

5.2 CDPO Policy Iterative Improvement
One motivation for the conservative update is that maximizes (thus improves) the expected value over the posterior. In this section, we are interested in the policy value improvement under any unknown fr. Namely, we seek have the iterative improvement bound ( J (T),)) where the true objective J is defined in (2.3).
We impose the following regularity conditions the underlying MDP transition and the state-action visitation.
Assumption 5.2 (Regularity Condition on MDP Transition). Assume that the MDP transition function f" : x A + S is with additive e-sub-Gaussiin noise and bounded norm, i.e., ||s||2 S C. Assumption 5.3 (Regularity Condition on State-Action Visitation), We assume that there exists such that for any policy n,, t E [1,
( (dpn (s, a)
}}}
21
1/2
S.
(5.5)
where / is the Radon- Nikoo-- derivative of Pac-1 with respect to Px.
Theorem 5.4 (Policy Iterative Improvement). Suppose have IIf((:))] C C f F where the model class JF finite. Define := max3,a |AA" (s, a)), where A is the advantage function defined as AL (s, a) == Of (s, a) - VL" (s). With probability at least 1 the policy improvement between successive iterations is bounded by
J(m,) - J(TT+1) 1) 2 A (D) - (1+K) 22yC² In
2Tp
(5.6)
7
1 1-7¹
where A(t) = E (s)
J. Qe- (8) 2 due to the greediness of qt-
The above theorem provides the iterative improvement bound following the CDPO algorithm. When I is large enough, the policy value improvement is at least A(t) by choosing properly small r7.
In particular, the first term Att) characterizes the policy improvement brought by the greedy exploita- tion in (4.1), and (t) 2 0 since qe is optimal under the reference model ft. The second term in (5.6) accounts for the generalization error least square methods. Specifically, model f. = fT.S E Fr trained fit the history samples. However, we seek to have the model error bound action visitation measure, which requires the deviation from the empirical mean to its expectation using Bernstein's 's inequality and union bound. Finally, the trust-region constraint in (4.2) brings the 4nja (1 - 7) term, which reduces to zero if is small. This makes intuitive sense as controls the degree of conservative exploration.
the state-
5.3 Global Optimality of CDPO
We now analyze the global optimality of CDPO by studying its expected regret. As discussed in Section 3, agnostic reinforcement learning is impossible. Without structural assumptions, additional complexity measure is required for generalization bound beyond finite settings. For this reason, we adopt the notation of eluder dimension [49, 43], defined follows:
Definition 5.5 ((F,e)- De-eeeenddn.c) we say (s, a) E ix (F, dependent on {(s), a;) H S A, then
VI, Elln(( - f2(s), 5² = [|)((,,)) -2,,, se.
Conversely, (s, a) E S x is (F, inddeeenndn of a1)) and only if it does not satisfy the definition for dependence.
Definition 5.6 (Eluder Dimension). The eluder dimension dim 8) is the length of the longest
possible sequence of elements in S Sx. A such that for some e' E, everr element is (Fdeee)niddeeende of its predecessors.
We make the following assumption on the Lipschitz continuity of the value function.
7

---

Assumption 5.7 (Lipschitz Continuous Value). At iteration t, assume the value function V for any policy π is Lipschitz continuous in the sense that (s)) V (82) S L, [81 - 82112-
Notably, Assumption 5.7 holds under certain regularity conditions of the MDP, e.g. when the transition and rewards are Lipschitz continuous [5, 47]. Under this assumption, many RL settings can be satisfied [13]. e.g., nonlinear models with stochastic Lipschitz policies and Lipschitz reward models, and is thus adopted by various model- based RL work [35, 7. 13].
We now study the global optimality of CDPO by the following expected regret theorem, which can be seen as a direct consequence of Theorem 5.1 that states the statistical equivalence between CDPO and PSRL.
Theorem 5.8 (Expected Regret of CDPO), Let NJF, a, I1-112) be the a-covering number of F. Denote dg := dimg(F, for the eluder dimension of F precision 1/T.. Under Assumption 5.2 and 5.7, the cumulative expected regret of CDPO in T iterations is bounded by
/T - 5)L (T- 2)
(1+
BeyesRegrel <
Cdz + TVTdBB + +44C, 1-7
(5.7)
where 3 = = log 2N (FF.11(T9)),HH + 2(8C + /80 (og(7))(()))) /T and L:= B[L]].
Here, the covering number is introduced since we are considering F that may contain infinitely many functions, for which we cannot simply apply union bound. Besides, is the confidence parameter that contains f with high probability (via concentration inequality).
To clarify the asymptotics of the expected regret bound, we introduce another measure of dimension- ality that captures the sensitivity of F to statistical overfitting.
Corollary 5.9 (Asymptotic Bound). Define the Kolmogorov dimension w.r.t. function class F
(og(N( a, 1+112)
dx dimx(F) lim sup
log(1/a)
aio
Under the assumptions of Theorem 5.8 and by omitting terms logarithmic in T, the regret of CDPO is
BayesRegret x, o) = Ö(Lo d
(5.8)
The sublinear regret result permits the global optimality and sample efficiency for any model class with reasonable complexity measure. Meanwhile, the iterative improvement theorem guarantees efficient exploration and good performance even when the model class is highly nonlinear.
Empirical Evaluation
6.1 Understanding Different Exploration Mechanisms
We first provide insights and evidence of why CDPO exploration can be more efficient in the tabular N-Chain MDPs, which have optimal right actions and suboptimal left actions at each of the N states. Settings and full results are provided in Appendix F.2. In Figure we compare the posterior of CDPO and PSRL at the state that is the furthest away from the initial state, i.c. the state that is the hardest for the agents reach and explore.
15-Ohain
100
3000
X0a
180K
1300
1809
Figure 1: CDPO and PSRL posterior on an 8-Chain MDP Figure 2: Regret curve of CDPO and and a 15-Chain MDP, where the right actions are optimal. PSRL when N 8 and N 15.
When training starts, both algorithms have a large variance value estimation. However, as training progresses, CDPO gives more accurate and certain estimates, but only for the optimal right actions not

---

for the suboptimal left actions, while PSRL agents explore both directions. This verifies the potential over-exploration issue in PSRL: as long as the uncertainty contains unrealistically large values. PSRL agents can perform uninformative exploration by acting suboptimally according sampled model. contrast, CDPO replaces the sampled model with a stable mean estimate and cares about the expected value, thus avoiding such pitfalls. We see in Figure 2 that although CDPO has much larger uncertainty for the suboptimal left actions, its regret is lower.
inaccurate
6.2 Exploration Efficiency with Nonlinear Model Class
In finite MDPs, PSRL-style agents can specify and try every possible action to finally obtain an accurate high-confidence prediction. However, our discussion Section 3 indicates that similar over-exploration issue in more complex environments can lead to less informative exploration steps, which only eliminate an exponentially small portion of the uncertainty.
To see its impact on the training performance, we report the results of provable algorithms with nonlinear models several MuJoCo tasks in Figure 3. For OFU-RL, mainly evaluate HUCRL [10], a deep algorithm proposed to deal with the intractability of the joint optimization. We observe that all algorithms achieve asymptotic optimality the inverted pendulum. Since the dimension of the pendulum task is low, learning an accurate (and thus generalizable) model poses no actual challenge. However, in higher dimensional tasks such half-cheetah, CDPO achieves higher asymptotic value with faster convergence. Implementation details and hyperparameters are provided in Appendix F.I.
200
-30
2500
CDPO
-350
3300
PSRL
timesteps (1e4)
timesteps (1e4)
timestaps (1e5)
(a) Inverted Pendulum.
(b) 7-DOF Pusher.
(c) Half-Cheetah.
Figure 3: Performance CDPO, PSRL, and HUCRL equipped with nonlinear models in several MuloCo tasks: inverted pendulum swing-up, pusher goal-reaching, and half-cheetah locomotion.
6.3 Comparison with Prior RL Algorithms
We also examine a broader range MBRL algorithms, including MBPO [20], SLBO [35], and ME-TRPO [30]. The model-free baselines include SAC [16], PPO [54], and MPO [2]. The results are shown in Figure 4. We observe that CDPO achieves competitive higher asymptotic performance while requiring fewer samples compared to both the model-based and the model- ffeee baselines.
200
-150
6230
3000
2300
timestops (104)
timestops (164)
timestaps (1e5)
(a) Inverted Pendulum.
(b) 7-DOF Pusher.
(c) Half-Cheetall
CDPO МВРО
PSRL MPO
HUCRL
SLBO
ME-TRPO
SAC
PPO
Convergence
Figure 4: Comparison between CDPO and model-free, model-based RL bascline algorithms.

---

6.4 Ablation Study
We conduct ablation studies to provide better understanding of the components in CDPO. One can observe from Figure 5 that the policies updated with only Referential Update or Conservative Update lag behind the dual framework. We also test the necessity and sensitivity of the constraint hyperparameter v). We see that a constant 1/ and time-decayed achieve similar asymptotic values with similar convergence rate, showing the robustness of CDPO, However, removing the constraint will lose the policy improvement guarantee, thus causing degradation. Ablation on different choices of MBPD solver (Dyna and POPLIN-P [63]) shows the generalizability of CDPO.
1990
190
3000
5304
return
2000
200
1230
Thme Deceyady
300
CDPO
Wiboe Compran
CDPO PORUN
60
63
24
1100
trmesteps (1c5)
timesteps (leb)
(a) Inverted Pendulum.
(b)
(c) Half-Chectall
Figure 5: Ablation studies on the effect of the dual update steps and the trust-region constraint. The robustness and generalizability of the CDPO framework are demonstrated by the results of different choices of the constraint threshold and different solvers.
7 Conclusions & Future Work
In this work, we present Conservative Dual Policy Optimization (CDPO), simple yet provable model- based algorithm. By iterative execution of the Referential Update and Conservative Update, CDPO explores within a reasonable range while avoiding aggressive policy update. Moreover, CDPO gets rid of the harmful sampling procedure in previous provable approaches. Instead, intermediate policy is optimized under a stable reference model, and the agent conservatively explore the environment by maximizing the expected policy value. With the same order of regret PSRL., the proposed algorithm can achieve global optimality while monotonically improving the policy. Considering our naive choice of the reference model, other more sophisticated designs should be fruitful future direction. It will also be interesting to explore different choices of the MBPO solvers, which we would like leave as future work.
References
[1] Yasin Abbasi-Yadkori Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pages 1-26. JMLR Workshop and Conference Proceedings, 2011.
[2] Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum a posteriori policy optimisation. arXiv preprint w7Xiv:1806.06920, 2018.
[3] Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept.. UW Seatlle, Seattle, WA, USA, Tech. Rep, 2019.
[4] Yaakov Bar-Shalom and Edison Tse. Dual effect, certainty equivalence, and separation in stochastic control. IEEE Transactions on Automatic Control, 1955)494-500, 1974.
[5] Osbert Bastani.
Sample complexity of estimating the policy gradient for nearly deterministic dynamical systems. In International Conference on Artificial Intelligence and Statistics, pages PMLR, 2020.
[6] Jacob Buckman, Danijar Hafner, George Tucker, Eugene Brevdo, and Honglak Lee. Sample- efficient reinforcement learning with stochastic ensemble value expansion. arXiv preprint arXiv:1807.01677 2018.
10

---

[7] Sayak Ray Chowdhury and Aditya Gopalan. Online learning in kernelized markov decision processes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3197-3205. PMLR, 2019.
[8] Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforce- ment learning in a handful of trials using probabilistic dynamics models. arXiv preprini arXiv:1805. 121144 2018.
[9] Ignasi Clavera, Violet Fu, and Pieter Abbeel. Model- oodel-augmented actor-critic: Backpropagating through paths. arXiv preprint arXhv:2005,0800 2020.
[10] Sebastian Curi, Felix Berkenkamp, and Andreas Krause. Efficient model-based reinforcement learning through optimistic policy search and planning. arXiv preprint arXiv:2006. 08684, 2020.
[11] Richard Dearden, Nir Friedman, and Stuart Russell. Bayesian q-learning. In Aaaifiaai, pages 761-768, 1998.
[12] Marc Deisenroth and Carl E Rasmussen. Pilco: A model-based and data-efficient approach to policy search. In Proceedings of the 28th International Conference on machine learning (ICML-11), pages 465-472. Citeseer, 2011.
[13] Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforce- ment learning: Shelve optimism, embrace virtual curvature. arXiv preprint 2rXiv:2102 04168, 2021.
[14] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: structural framework for provable generalization in rl. In International Conference Machine Learning, pages 2826-2836. PMLR. 2021.
[15] Vladimir Feinberg, Alvin Wan, Ion Stoica, Michael I Jordan, Joseph E Gonzalez, and Sergey Levine. Model-based value estimation for efficient model-free reinforcement learning. arXiv preprint arXiv: arXiv:8833.00100 0000000000,110000000000000010110 2018
[16] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning, pages 1861-1870. PMLR, 2018.
[17] Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. arXiv preprint
2019.
[18] Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learning continuous control policies by stochastic value gradients. Advances in neural informa- tion processing systems, 28, 2015.
[19] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1 11(4). 2010.
[20] Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. arXiv preprint arXiv:1906.08253. 2019.
[21] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are lac-leaee. International Conference on Machine Learning, pages 1704-1713. PMLR, 2017.
[22] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[23] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning.
In In Proc. 19th International Conference Machine Learning. Citeseer, 2002.
[24] Michael Kearns, Yishay Mansour, and Andrew Ng. Approximate planning large pomdps via reusable trajectories. Advances in Neural Information Processing Systems, 12, 1999.
11

---

[25] Rahul Kidambi, Jonathan Chang, and Wen Sun. Optimism is all you need: Model-base imitation learning from observation alone. arXiv preprint arXiv:2102.10769, 2021.
[26] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
[27] Edgar D Klenske and Philipp Hennig. Dual control for approximate bayesian reinforcement learning. The Journal of Machine Learning Research, (711):434443883 2016.
[28] Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pages 1008-1014, Citeseer, 2000.
[29] Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate uncertainties for deep learning using calibrated regression. In International Conference on Machine Learning, pages 2796-2804. PMLR, 2018
[30] Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model-ensemble trust-region policy optimization. arXiv preprint arXiv: 10592, 2018.
[31] Sergey Levine and Pieter Abbeel. Learning neural network policies with guided policy search under unknown dynamics. In NIPS, volume 27, pages 1071-1079. Citeseer, 2014.
[32] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334-1373, 2016.
[33] Gene Li, Pritish Kamath, Dylan J Foster, and Nathan Srebro. Eluder dimension and generalized rank. arXiv preprint arXiv:2104.06970 2021.
[34] Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. Advances in neural information processing systems, 30, 2017.
[35] Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorith- mie framework for model-based deep reinforcement learning with theoretical guarantees. arXiv preprint arXiv:/807.038. 2018.
[36] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. arXiv preprint arXiv: vrXiv:/902.000 9902.0782, 2019.
[37] Efstratios Markou and Carl E. Rasmussen. Bayesian methods for efficient reinforcement learning in tabular problems, 2019.
[38] Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07035, 2021.
[39] William Montgomery and Sergey Levine. Guided policy search approximate mirror descent. 2016.
arXiv preprint
[40] Manfred Morari and Jay H Lee. Model predictive control: past, present and future. Computers Chemical Engineering, 23(4-5):667-681 1999.
[41] Anusha Nagabandi, Gregory Kahn, Ronald S Fearing, and Sergey Levine. Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 7559-7566. IEEE, 2018.
[42] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. arXiv preprint 1306. 2013.
[43] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. arXiv preprint arXiv: /406. 1853, 2014.
[44] Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning, pages 2701-2710. PMLR, 2017.
12

---

[45] Ian Osband, Benjamin Van Roy. Daniel J Russo, Zheng Wen, et al. Deep exploration via randomized value functions. J. Mach. Learn. Res., 20(124):1-62, 2019.
[46] Brendan O'Donoghue, lan Osband, Remi Munos, and Volodymyr Mnih. The uncertainty bellman equation and exploration. In International Conference on Machine Learning, pages 3836-3845, 2018.
[47] Matteo Pirotta, Marcello Restelli, and Luca Bascetta. Policy gradient in lipschitz markov decision processes. Machine Learning, 100(2)2555-28 283, 2015.
[48] Stephane Ross and J Andrew Bagnell. Agnostic system identification for model-based rein- forcement learning. arXiv preprint arXiv:/203. 1007, 2012.
[49] Daniel Russo and Benjamin Van Roy. Fluder dimension and the sample complexity of optimistic exploration. In NIPS, pages 2256-2264. Citeseer, 2013.
[50] Daniel Russo and Benjamin Van Roy, Learning to optimize via posterior sampling. Mathematics of Operations Research, :9(4):122111)) 2014.
[51] Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. arXiv preprint arXiv: arXiv: 0001. 2018.
[52] Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial 2017.
on thompson sampling. arXiv preprint
[53] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
[54] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal 2017.
policy optimization algorithms. arXiv preprint
[55] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. nature, 550(76766:354-35,, 2017.
[56] Alexander L Strehl and Michael L Littman. theoretical analysis of model-based interval estimation. In Proceedings of the 22nd international conference on Machine learning, pages 856 863, 2005.
[57] Malcolm Strens. A bayesian framework for reinforcement learning. In ICML, volume 2000, pages 943-950, 2000.
[58] HJ Suh, Max Simchowitz, Kaiqing Zhang, and Russ Tedrake. Do differentiable simulators give better policy gradients? arXiv preprint arXiv:2202.00817, 2022.
[59] Wen Sun, Geoffrey J Gordon, Byron Boots, and J Andrew Bagnell. Dual policy iteration. arXiv preprint 1805 10755, 2018
[60] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference Learning Theory, pages 1898-2933. PMLR, 2019.
[61] Richard S Sutton.
Integrated architectures for learning, planning, and reacting based on ap- proximating dynamic programming. In Machine learning proceedings 1990, pages 216-224. Elsevier, 1990.
[62] William Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-29) 1933.
[63] Tingwu Wang and Jimmy Ba. Exploring model-based planning with policy networks. arXiv preprint arXiv: 1906. 08649, 2019.
13

---

[64] Jie Xu, Viktor Makoviychuk, Yashraj Narang, Fabio Ramos, Wojciech Matusik, Animesh Garg. and Miles Macklin. Accelerated policy learning with parallel differentiable simulation, arXiv preprint arXiv:2204.07137, 2022.
[65] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning. pages 6995-7004. PMLR, 2019.
[66] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference Machine Learning, pages 10746-10756. PMLR, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Some components in our algo- rithm are naively designed.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix H.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assumption 5.2 and 5.7.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
Our code can be found in the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "ynv4qISpq1t", "reviewer": "Reviewer_2poR", "summary": "This work addresses the problem of model-based planning in RL, focused on nonlinear models and high-dimensional environments. As the model in these cases tends to be erroneous, planning greedily or optimistically wrt the model can lead to poor performance. The authors propose a conservative update algorithm that relies on greedy updates of a reference policy wrt the least-squares estimate of the model, and another update of the behaviour policy that is constrained to remain close to the reference policy but also to optimize the expected performance wrt. the posterior over models. Theoretically, they show that greedy optimization wrt the least-squares model mimics the behaviour of PSRL in terms of Expected Regret. They also bound the policy improvement at each iteration, and provide global convergence results for classes of models with finite complexity measures. Empirical evaluations show that their proposed algorithm (CDPO) has improved performance over some common baselines on a few continuous control domains.\n", "questions": "- Each optimization in (4.1) and (4.2) needs to be done to completion. In the deep learning regime, these optimizations may never converge to the optimum point or even good local optima. How does this impact the results? Has this been an issue in the experiments and how was it addressed?\n\nSection 6.1:\n- L309-310: “incompatibility brought by the model”: Does this refer to the model class not being sufficient to learn a good model of the environment? If so, how do we know this network is not able to learn a good model of the environment for HalfCheetah? It would help to see the model prediction loss for example. Otherwise, I don’t think we can necessarily make this conclusion. It could be that the policy is harder to learn in HalfCheetah. \n- Related to the above point — L310-311 : “This phenomenon is most obvious in the half-cheetah task, where learning a globally accurate model is hard.” and L312-313: “When the model uncertainty is large, the aggressive policy updates and uninformative exploration lead to slow convergence and lower asymptotic value within finite iterations.” This is more of a hypothesis that’s not really being shown in the results. I don’t think it can be concluded from the present results that this is why the performance is lower.\n- How do we know these results are due to better exploration and not, for example, better optimization? \n- Potentially a better argument for better exploration may be better shown in a finite domain where the exploration of the algorithms (i.e. what states are visited) can be visualized.\n", "limitations": "I did not find that the authors sufficiently discussed the limitations of their work. See Questions.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is very well-written and easy to follow. The authors do a good job of placing it within the context of existing literature. \n\nStrengths:\n- I think the idea behind CDPO is a good one, and addresses an important problem. I also feel that overall the paper does a good job of analyzing this algorithm from different perspectives (including the results in the appendix) \n\nWeaknesses:\n- Experimental results are good but could include more domains. \n- Results depend on convergence of (4.1) and (4.2) (see Questions)\n- I think more in-depth description and implications of the result in (5.6) would have been helpful\n\nRegarding writing:\n- L217 should be argmax\n- L218-219: instead of “PSRL proceeds by …” I would suggest writing out the reasoning and the lemma that is used to obtain this result (e.g. Lemma 1 of [1]). \n- L299-300: I would say “discussed” rather than “analyzed”\n\n[1] Osband, Ian, Daniel Russo, and Benjamin Van Roy. \"(More) efficient reinforcement learning via posterior sampling.\" Advances in Neural Information Processing Systems 26 (2013).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QGnhSdbwqBb", "reviewer": "Reviewer_M8qo", "summary": "This paper proposes a novel algorithm: Conservative Dual Policy Optimization (CDPO). CDPO involves a referential update optimized optimized for a reference model, which is similar to PSRL. It also involves a conservative update, which provides a conservative range of randomness by maximizing the expectation of model value. CDPO provides same regret bound as of PSRL and can simultaneously offer monotonic policy improvement and global optimality. The paper presents this CDPO framework along with theoretical and empirical analysis.", "questions": "The paper is well written and well organized, answering most of the questions up front. Thanks to the authors.\n\nSection 2 of the paper builds up the technical ground for model based RL and presents the basic for regret analysis. Section 3 explains OFU and PSRL framework along with general complexity and performance bound analysis for them.\n\nThe algorithm presented in section 4 is concise and clear. Theoretical analysis presented in section 5 is solid. \n\nEmpirical evaluation is performed on multiple domains and compared against different SOTA models. The CDPO algorithm shows clear evidence of performing better, specially for domain with higher dimensional state space involving more uncertainties.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents a novel algorithm that can better handle exploration and learning in the face of uncertainty. The contribution is solid given the simplicity, theoretical soundness and empirical superiority of the proposed method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "GhU9QdSj3Yh", "reviewer": "Reviewer_q3JM", "summary": "The paper proposes Conservative Dual Policy Optimization (CDPO) that involves a Referential Update and a Conservative Update. It is proven that CDPO achieves the same regret as PSRL and ensures the monotone improvement of the policy. Experimental results validates its effectiveness.\n\n", "questions": "See the weakness.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.The proposed method is simple and effective. Theoretical results are sufficient.\n2. The literature review is sufficient.\n\nWeakness:\n1. The motivation of the proposed method is not clear and the paper is not easy to follow.\n2. The paper only test their algorithm on 3 environments of MuJoCo. I am curious about the performance on larger env such as Ant and Humanoid.\n3. I am also interested at the improvement ratio of sample efficiency over baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "G4muzAuWmFD", "reviewer": "Reviewer_NcmH", "summary": "This paper aims to solve the over-exploration issue of posterior sampling (PSRL) in model-based reinforcement learning. They propose Conservative Dual Policy Optimization (CDPO) which involves a Referential Update and a Conservative Update. They also proves CDPO can achieves the same regret as PSRL, and experimental results show CDPO can achieve better performance than PSRL.", "questions": "See  Weaknesses above.", "limitations": "Lack of motivation, limited evaluation", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-written and easy to follow.\n2. They provide a detailed theoretical analysis for CDPO.\n3. CDPO outperforms PSRL on three MuJoCo environments.\n\nWeaknesses:\n1. In line 7 the paper claims that ``The sampled model that current policy is greedily optimized upon will thus be unsettled, resulting in aggressive policy updates and over-exploration”. However, in the main sections, the paper doesn’t provide any theoretical analysis or empirical evidence to support this claim. They only cite two papers in line 31. This leads to the lack of reasonable motivation for the proposed method. I hope the authors can provide more detailed analysis for the over-exploration issue.\n2. In Eq.4.2, CDPO uses KL divergence $\\mu$ to trade off exploitation and exploration, so this is a very important hyperparameter. In section 6.3, the results show that a time-decay $\\mu$ performs worse than a fixed $\\mu$. This is quite strange because intuitively, as the environment is gradually explored, we should make the current policy closer to the exploitation policy. I think the ablation study for $\\mu$ should be more complete and have a more specific explanation. For example, how should the time decay $\\mu$ be designed, and how much does $\\mu$ affect the performance of the policy.\n3. Since CDPO solves two model-based solvers (line 2 and line 4 in Algorithm1), the time complexity of the algorithm should be twice that of PSRL. Many MBRL algorithms take a very long time to run to convergence (for example, one of the state-of-the-art methods MBPO [1] needs almost 48 hours on HalfCheetah-v2).  If combined with CDPO, the running time of the MBRL algorithm is likely to be twice as long. Is it reasonable to take such a long time to obtain an insignificant performance improvement?\n4. The benchmark environment for experiments is too simple. Only HalfCheetah is a slightly more complex environment. The authors did not conduct experiments on the complex environments commonly used in MuJoCo such as Ant, Walker2d and Humanoid.\n5. The baseline model-based methods (DPI, SLBO) that the author chose to compare in section 6.2 are too old, and these methods are not the current SOTA algorithms. My suggestion is to compare with MBPO [1] and VaGraM [2].\n\n[1] Janner, Michael, et al. \"When to trust your model: Model-based policy optimization.\" Advances in Neural Information Processing Systems 32 (2019).\n[2] Voelcker, Claas A., et al. \"Value Gradient weighted Model-Based Reinforcement Learning.\" International Conference on Learning Representations. 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept