Bayesian Optimistic Optimization: Optimistic Exploration for Model-based Reinforcement Learning
Authors: Chenyang Wu
Tianci Li
Zongzhang Zhang
Yang Yu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Model-based Reinforcement Learning
Exploration and Exploitation
Optimism in the Face of Uncertainty

Abstract: Reinforcement learning (RL) is a general framework for modeling sequential decision making problems, at the core of which lies the dilemma of exploitation and exploration. An agent failing to explore systematically will inevitably fail to learn efficiently. Optimism in the face of uncertainty (OFU) is a conventionally successful strategy for efficient exploration. An agent following the OFU principle explores actively and efficiently. However, when applied to model-based RL, it involves specifying a confidence set of the underlying model and solving a series of nonlinear constrained optimization, which can be computationally intractable. This paper proposes an algorithm, Bayesian optimistic optimization (BOO), which adopts a dynamic weighting technique for enforcing the constraint rather than explicitly solving a constrained optimization problem. BOO is a general algorithm proved to be sample-efficient for models in a finite-dimensional reproducing kernel Hilbert space. We also develop techniques for effective optimization and show through some simulation experiments that BOO is competitive with the existing algorithms.

Bayesian Optimistic Optimization: Optimistic Exploration for Model-based Reinforcement Learning
Chenyang Wu', Tianci Li', Zongzhang Zhang'; Yang Yu!.2
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China Pazzoou Lab, Guangzhou, China
{wucy, litc) www.aannn.ee..e............ nju.edu. edu. cn, {zzzhang, yuy) edu.. cn
Abstract
Reinforcement learning (RL) is general framework for modeling sequential decision making problems, at the core of which lies the dilemma of exploitation and exploration. An agent failing explore systematically will inevitably fail to learn efficiently. Optimism in the face of uncertainty (OFU) is a conventionally successful strategy for efficient exploration. An agent following the OFU principle explores actively and efficiently. However, when applied to model-based RI,, it involves specifying confidence set of the underlying model and solving series of nonlinear constrained optimization, which can be computationally intractable. This paper proposes algorithm, Bayesian optimistic optimization (BOO), which adopts a dynamic weighting technique for enforcing the constraint rather than explicitly solving constrained optimization problem. BOO is a general algorithm proved to be sample-efficient for models in finite-diment miite-dimensional reproducing kernel Hilbert space. We also develop techniques for effective optimization and show through some simulation experiments that BOO is competitive with the existing algorithms.
Introduction
Reinforcement learning (RL) is a sequential decision- mmaking problem in which an agent acts in an unknown environment while maximizing the cumulative rewards it receives [1, 2]. In this paper, we consider the RL in Markov decision processes (MDPs), where the agent observes the state of the environment at each timestep and makes decisions accordingly. Since the environment is unknown, maximizing the cumulative rewards naturally involves a trade-off between exploration and exploitation. Exploitation is to make the best-rewarding decision based on the agent's 's information, and exploration means actively gathering information about the environment so that the agent understands better about the environment and thus makes better decisions in the future. An algorithm cannot be sample-efficient without balancing them properly.
Theoretically, the exploration and exploitation dilemma admits Bayesian optimal solution [3]. That is consider the RL problem a so-called layes-Adaptie MDP (BAMDP), special case of partially observable Markov decision processes (POMDPs), where the parameter of the dynamics unobservable. Although this formulation provides useful insights, the POMDP formulation computationally intractable [4-6]. Therefore, all practical algorithms [7-10] resolve this dilemma by achieving delicate balance between seeking rewards and gathering information. Optimism in the face of uncertainty (OFU) is one of the conventionally successful approaches for this balance and is established as an efficient learning principle in various cases [11-13].
"Corresponding Author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The OFU principle makes the agent an optimist who is always optimistic about the uncertainty of the environment. If it ever stands chance that a policy is highly profitable, the agent will try out. By executing an optimistic policy, the agent either receives high rewards or gains information after observing unexpected outcomes. OFU involves constructing a confidence set of possible MDPs and solving for the most optimistic one within the confidence set. Unfortunately, this is typically constrained nonlinear non-concave optimization and is impractical to solve [14, 15J. Therefore, a model-based OFU algorithm is previously deemed an inferior choice [15].
In this paper, we propose model-based OFU algorithm, Bayesian optimistic optimization (BOO), which enforces the constraint via a dynamic weighting technique and therefore makes the optimization more practical. We show that BOO seneral-purposs model- based OFU RL algorithm that is both provably sample-efiie cumple-effiieett and comparatively computationally tractable. Our contribution is three-fold:
We extend the OFU algorithms to the Bayesian setting by requiring the model to reside in a Bayesian credible region. BOO is then proposed as the Lagrangian relaxation of this constrained optimization.
We prove that BOO is efficient in terms of the frequentist regret for a finiteddimensional reproducing kernel Hilbert space (RKHS).
We derive optimization methods for BOO and demonstrate empirical evidence that BOO is competitive with UCRL2 [16] and PSRL [17].
2
Preliminaries
This section introduces the preliminaries, including RL in MDPs and the principle of optimism the face of uncertainty.
2.1 Reinforcement Learning in Markov Decision Processes
We consider the problem where a seward-seeking agent repeatedly interacts with a finite-horizon MDPs M (S, A. P. R, H, s1), where S and A are the state and action spaces, respectively. The algorithm adopted by the agent is denoted as 21. At each episode, the agent is spawned at the initial state $1 S. It takes an action aj AA at each period h within episode and receives Then, the environmental state transitions to the next state,
a random reward, Fh ~ R(sh, Sh+1 P(sn, ag)) This process repeats until the episode ends the H-th period, and another episode begins. Note that the fixed initial state is not a stringent condition since starting from an initial distribution po is equivalent starting from special state 8 such that P(s(s), a) ps(s) holds for any state s and action a. A finite MDP is an MDP with finite state and action spaces.
A policy æ is function mapping state and a period the MDP M, policy म, and period h is defined recursively as
action distribution. The value function for
T. (sn) = Eas ((s.h(s).h)) @ ( (sh, an)] Vh E [H],
(I)
M an) = RM (sh, an) + E PM
[ (sh+1)] vh E [H - -],
M (SH, ax) RM (sH, where RM (s,a) = En.n" and Q
We use X4. to represent the variable X at the h-th period of the k-th episode. For notational convenience, X1. is sometimes abbreviated as XRu. The history prior to k-th episode is defined as H4: = ($1,1, 01,1, .1,2...., Sk-1. 0g-1, 0H-1,,,F--1.H11 The agent is assumed to be capable of memorizing the entire history. In this paper, we consider model- based RL algorithms which produce model Mj per episode in light of the history Hr and derive its corresponding optimal policy TH arg max, V.T.Me (s1) for execution. We use the terms model and MDP interchangeably. For any history H, ((HH) defines distribution over models and policies. Within the k-th episode, the agent samples an action from T (swn, h) at each period h.
In the frequentist viewpoint, there exists an unknown true MDP M We abbreviate V VT", "M" as VAA where n7 is an optimal policy of the true MDP M The frequentist performance metric, regret, is

---

defined in terms of the true MDP:
K
Regret (T, 2, M*) = B
A
(2)
where As is defined as Bry~)((H)) (i((s)) - Vi (81) K is the total number of episodes,
T KH is the number of the total time steps, and HK+1 21, MM* means that the history is sampled by the interaction of the algorithm 21 and the real MDP M In the Bayesian viewpoint, the unknown MDP M is treated as a random variable and assigned prior Pv- All MDPs in the support of pM differ only in the transition function P and the reward function R. The Bayesian objective the agent to minimize the Bayesian regret up to time T, BayesRegret 2, pM) = Ext [Tegrel[T 21 ].
2.2 Optimism in the Face of Uncertainty
Optimism in the face uncertainty is strategy for information gathering. When the optimal action is not clear given the current information, it is preferable to hazard an optimistic guess. If we make an atrocious guess, we effectively rule that out and pick another next time. Otherwise, we end up finding competitive solution that incurs little regrets. This idea is mathematically realized as constrained optimistic optimization, maX Mr (s1) s.t. Mg E Ma. where Ma a confidence set constructed using empirical data Hr such that M E Ma with high probability. The pseudocode of the OFU algorithm shown Algorithm 1.
Algorithm 1 OFU RL
1: for episode k 1, 1,2....du do
2: Construct a confidence set Mr with He
3: Compute Ty E arg max. maxas, VaTMe (s1) s.t. M& E Ms
4:
Execute TT for an episode
3 Related Work
One line of research resolves the exploration and exploitation dilemma by formalizing the RL problem as a planning problem in Bayes-Adaptive MDPs (BAMDPs) [3], which treats the unknown MDP parameter as an additional hidden variable and maintains a belief distribution of the parameter. This line of work shares the scalability problem, which is caused by the exponential increase of possible histories w.r.t. the planning horizon. That is, the planning in BAMDPs is PSPACE-complete [4] and requires exponential time to solve. Intuitively, this is because methods based on BAMDPs deal with the belief distributions of MDPs (or histories) rather than single MDP. Efficient planning algorithms in BAMDPs do exist. Exploiting the root sampling technique, we can implement an algorithm that gets rid of the posterior distribution and only requires posterior sampling [18]. Nonetheless, the underlying scalability issue remains prominent.
Methods following the OFU principle construct an optimistic estimate of the unknown MDP and execute its optimal policy. Since these methods plan on single MDP estimate, they are computa- tionally preferable compared to methods based on BAMDPs. The UCRL2 [16] is one such method. However, unlike tabular and linear MDPs for which constructing an optimistic estimate is analytically tractable [11, 13], constructing an optimistic estimate for general MDPs involves constrained joint optimization of model and policy and is computationally prohibitive. Hence, previous model-based OFU algorithms [19, 20] for general model classes cannot be implemented and rely on posterior sampling for exploration.
The posterior sampling for reinforcement learning (PSRL) works by selecting a random MDP from the posterior distribution and executing its optimal policy [21]. This strategy ensures that a policy is selected according to the probability that it is the optimal policy of the real model. It is shown that PSRL is at least as good as any frequentist OFU algorithm terms of Bayesian regret [22, 15). PSRL is argued to be better than optimism since it is more computationally tractable [15]. Nevertheless, as opposed to OFU algorithms, incremental implementation of PSRL. is challenging because requires replanning after each sampling. Practical implementation instead tries to directly sample from the
3

---

posterior distribution of the optimal value function [23-25]. However, the theoretical guarantee for these methods only established for tabular MDPs [25].
H-UCRL was devoted to resolving the intractability of model-hased optimistic exploration for general models [26]. It proposes to convert the joint optimization of model and policy into hallucinated control problem. This approach ignores the correlation between state-action pairs and treats them separately, causing inefficiency as reflected by the extra dependency on the cumulative posterior variance in their regret bound. Our method, BOO, also tries to attack the intractabilitty of optimism, which builds an optimistic model by optimizing both the value and the pog-portrrio density. avoids the defect of H-UCRL since maximizing the log posspottrroor density naturally enforces the correlation between state-action pairs.
We note that, when the prior is uniform, this idea is equivalent to balance value versus log-likelihood, which is first explored in [27] and is named eeward-biased maximum likelihood estimation (RBMLE). They have applied this approach to multi-armed bandits [28], contextual bandits [29], and RL where the model belongs to a known finite set [27, 30J. A constrained version RBMLE is also successfully applied to RL of linear quadratic control systems [31]. Our algorithm can be considered generalizing RBMLE Bayesian perspective and finite dimensional RKHS. In this regard, BOO could also be referred to as reward-biased maximum posteriori.
Concerning the regret analysis, previous regret analysis for general model-based RL [19, 20] relies on the fact that the constructed model is the most optimistic one in the confidence set. The regret analysis of BOO differs with them significantly since the model constructed by BOO may not belong to a confidence set or a credible region. This difference entails a distinet analysis, where we show that neither the large deviation from the real model nor the possibly pessimistic estimation of the model causes a large regret.
4 Bayesian Optimistic Optimization
In this section, we derive the learning objective of Bayesian optimistic optimization (BOO) as a Lagrangian relaxation of a constrained optimization problem and give intuitive interpretation of the resulting objective. Assuming the model class resides in finite-dimensional RKHS, we show that BOO enjoys Ó( Ō(VK) regret.
4.1 Constrained BOO
The conventional OFU algorithm, as demonstrated in Algorithm contains a constrained optimistic optimization, where we look for an optimistic MDP Mj, E Mr and its corresponding optimal policy such that the value is maximized. The constrained BOO is almost the same (see Algorithm 2), except the frequentist confidence set is now replaced with the Bayesian credible region. A credible region with 1 ag level of confidence set Mr such that PM (H+)) 2 agk where Pr(-174+) is the posterior distribution given history Hs. and Pr(M& (74) = MMEMM Pr(M)/H4s dMM.
By the construction of the credible region, we have M E ME holds with probability 1 - as given any history Ha- Therefore, the per-episode Bayesian regret is bounded with probability Ok
E < E (si) Vi((s) M E Mi] + [v((s))
ViTA (s (st) E Ma s Agnne
Appt
Agone
(3)
where V -1,, M2x and the optimism term Àgue less than or equal to 0 by construction. We
define a distance metric d( M1, M2) max V (s1) Ma (81)). It is preferable to have a credible region M such that the set width max d(M1, M2) is minimized since the set width certifies an upper bound on Åpone, However, designing value concentration credible region could be intractable for generic model classes. As a reasonable alternative, we propose the highest density region (HDR) [32] or, in the Bayesian context, the highest posterior density (HPD) region [33], i.e.,
MA [M&l (r (7x) 2 ). where é is the largest constant such that Pr(Ms (H4x) 2 1 Og- This kind of region features a desirable property that occupies the smallest volume the sample
space among all credible regions of the same confidence level and has a potentially small set width.

---

There are two problems preventing the constrained BOO from being a practical algorithm. The first that the E; the definition of the HPD region is unknown. Although we may approximate it with the Monte Carlo approximation [34], an estimator of high/low quantiles has high variance rendering the approximation difficult. The other difficulty that the constrained joint optimization of model and policy is an NP-hard problem even in bandits with linear reward and quadratic constraints [14].
Algorithm 2 Constrained BOO
1: for episode = 1, 2....... do
2:
Construct credible region Mr with He
3: Compute Ty arg max- maxae V. (s1) s.t. M& E Ma
4: Execute тy for an episode
4.2 BOO as Lagrangian Relaxation of Constrained BOO
By introducing a Lagrange multiplier λE. we transform the constrained BOO with HPD regions into an unconstrained optimization problem, max,.M (VTT.M + (log Pr(M (Hx) log ex)
where Pr(M))H) Pr(H, IM) Pr(M)) Once the Lagrange multiplier is determined, the constant Pr(Hx)
log and the marginal likelihood log Pr(H+) are irrelevant, and the optimization equivalent to max M (VTT.Ad( (s1) + Aæ(log Pr(HulM) + log Pr(M))) This gives rise to the BOO algorithm as shown in Algorithm 3.
Algorithm 3 BOO
1:
for episode 1, 2, do
2: Compute тy arg max, max (ViT. Aoo Pr(HslAM) log Pr(M)))
3: Execute for an episode
However, the problem is how determine the value of λς. We note that the following argument by posterior sampling provides an inexact yet insightful viewpoint. A strict discussion is presented in Appendix B. The maximization of the BOO objective can be considered the problem of selecting the best one among multiple posterior samples (see Algorithm 4). When only one sample is taken, Algorithm 4 reduces to the well-known PSRL [21]. As the number of samples goes infinity, maximizing among all posterior samples gives approximately the solution of the above optimization.
Algorithm 4 BOO via Posterior Sampling for episode 1,2,... ........ do
2: Sample M1 ......, M Pr(-1HH)
3: Compute Ty E arg max, max;eb] Mz + Aa + log Pr(Mi))
4: Execute Tgg for episode
Notice that we can regard Algorithm as maximizing over several identically distributed random Mi
variables, A log Pr(M H4) Mi (s1). The magnitude of their mean does not matter since subtracting a constant will not change the optimum. The thing that matters is their variation. We need
to make sure that the variation not dominated by either V (si) or 2 log Pr(Mi value dominates the variation, the algorithm will select unreliable model, which causes inefficiency, the variation is dominated by the probability, it shows a strong preference for high-probability models and hesitates explore.
the
Theorem 4.1 shows that the standard deviation of log probability is at least a constant (proof in Appendix A),
Theorem 4.1 (Variation the log-posterior density). Suppose X (X1, X Xn) are obser- vations from stochastic process whose distribution Py depends 0 θ, open subset of Rm Assume that the posterior is asymptotic normal, and the log-posterior density is continuous. The variance of the pos-posterror density satisfies lim inf Varę [log Pr( 2 m/2.
5

---

The process where an algorithm 21 interacts with a random MDP parameterized by 0 is a stochastic process where the observation X, is the State-action pair (,), and the observation distribution Pr(X" (0 2) is distribution depending on O. Thus, by Theorem 4.1, we know that if the posterior distribution asymptotic normal, then, for a random sample from the posterior distribution, the variance of the random variable log Pr(0) x*)
) is at least m/2 when n is large enough.
Theorem 4, I relies on the asymptotic normality of the posterior distribution, which is satisfied under some regularity conditions specified in [35]. The theorem only certifies lower bound on the variance rather than establishing its convergence. Arguably, this is mostly a technical issue arising from the unboundedness of the log posttrrio density. It is possible to strengthen this result and derive the convergence of the variance. Indeed, it is empirically observed that this quantity converges rapidly to a constant.
For a proper RL algorithm, it is clear that the standard deviation of V V. w.r.t. k. Otherwise, the algorithm fails to find out the optimal value and policy. Suppose that the standard deviation of V is O(k-1/a), where Ô is variant of the big O notation that ignores logarithmic factors. We need to set the scaling parameter 2 proportionally such that the variation of the log-posterior density term log Pr (H&,) matches that of the value term VsL.M, Given specific model class and noise type, it is possible to derive a worst-case rate for the shrinkage of the value uncertainty and thus determine the proper value of λς. Nonetheless, the rate of information revealing could appear in an instance-dependent manner. That is to say, the optimal policy of some MDPs could be inherently easier to determine than the others. Even in a fixed MDP, the rate of uncertainty shrinkage could also change abruptly. For example, consider a ReLU bandit problem, where B {a E R ||||||| $ 1}. and the agent at each episode selects an action B and receives Gaussian reward of mean max(0"
(s1) should shrink
0). If it happens that the agent selects an action a in the inactive region / = {a E BI0Ta a < 0}, the resulting observation reveals little information about the optimal action. Suppose the parameter 0 is selected such that the positive region B\ is of maximum width > 0. Then, in the worst case, the agent needs to explore Q(1/c==1) actions in order to find the positive region, but the uncertainty starts diminishing rapidly whenever the positive region is identified.
The view of matching the log probability variation with the value uncertainty provides rationales for the dynamic adjustment of λg. Meanwhile, it points out the potential limitation of decaying Å with fixed rate. In this paper, we focus on methods that scale A with a fixed rate, but as mentioned above, it would be fascinating to adjust it in an instance-dependent manner.
4.3 BOO Regret
In this section, we introduce the regret BOO. The regret of BOO relies on both the decay rate of the scaling parameter and the complexity of model class. We assume that the model class resides in a d-dimensional RKHS, which roughly means any function in the model class can be represented as a linear function of a potentially unknown finie-ddmensional feature map. This assumption is not very restrictive because it places no restriction on the choice of feature map except for the finitude of the dimension.
In Appendix B, we derive the asymptotic regret of the BOO algorithm in Theorem B.I. As suggested
by Theorem 1. the optimal asymptotic regret of BOO is O VK log K) i..., Ô (VK) achieved
by setting > c/ Tr where >j is the optimal scaling parameter and e a constant associated with the model class. More detailed derivations and conclusions can be found in Appendix B.
We can further interpret \ = v/Vk as M = <X / where EM stands for the variation of the log- bog-posterior density for the model Mg. and <X represents the value uncertainty. In contrast to the discussion in Section 4, where we consider samples from the posterior distribution and the variation of log-posterior density remains constant, the width of the HPD region measured by the variation of log-posterior density is, in fact, growing at
depending the log covering number. Accroding
to Lemma D.7 in Appendix D.1, &% :M = O (log k). Therefore, we have E/ =x = O log
VR
Section 5 will highlight the need of manipulating with E/ and &M in optimization.

---

Optimization
In this section, we introduce optimization methods for BOO based on posterior sampling and gradient descent, respectively, and discuss in detail the problems of gradient-based optimization and our proposed solutions.
5.1 Optimization via Posterior Sampling
Algorithm 4 provides a method of optimizing the BOO objective via posterior sampling. As discussed previously. the optimal scaling parameter 2 for this algorithm is proportional to the value uncertainty, ic., A = - = A e.M The potential advantage of Algorithm 4 over PSRL is that, unlike PSRL, does not require posterior samples be independent. Even the requirement that samples are from the posterior can be relaxed. These features are essential either when the posterior distribution is approximated when the posterior samples are produced by Markov chain Monte Carlo methods and are correlated.
5.2 Optimization via Gradient-Basel Methods
We can also perform the optimization via gradient-based methods. The objective function of BOO consists of two parts, V. (s1) and (log Pr(H{)|M)) + log Pr ))) The gradients of the log- likelihood and the log-prior are easily obtained. For the value part, we provide value model gradient that admits a similar form as the well-known policy gradient [36, 37] (proof in Appendix E. The value model gradient is amenable Monte Carlo approximation and can be computed exactly for finite MDPs.
Theorem 5.1 (Value model gradient). Suppose that the transition function PMs and reward function Mo of model Mg. the gradient of the value V Ma ($1) w.rl. the model is
H Σ
VoVi Me (s1) (31)
-E Mo
VeR
(sh, an)
Σ
Vi+1 Vi (s log Mo (sh+1
p an)
an)
where t (81, ........,....... aH) is a trajectory, T ~ n, Mg means that the trajectory is formed by the interaction of the policy πI and the model Ma. and PMa (s1+1l8h, an) is the probability of sh+1 under distribution palo (5h, an).
Nevertheless, the value model gradient suffers the same inefficiency just as the policy gradient [38] since the model gradient for a particular state-action pair whenever is not visited under the current model and policy.
We propose some techniques to improve the optimization efficiency of BOO, and conduct ablation experiments to verify the effectiveness of our proposed methods in Section G. Two of the most effective techniques are described below, and the of the techniques detailed in Appendix F.
5.2.1 Mean Reward Bonus
In the gradient-based optimization, the model becomes optimistic on state-action pairs it visits frequently, which in turn makes these state-action pairs more appealing. This mutual strengthening phenomenon makes optimization easily stuck at local optima. One way to solve this problem is to increase the rewards of all state-action pairs, which raises the attractiveness of less visited state-action pairs. This can be achieved by adding bonus term CX HE(ss)) [R(s, a)] to the BOO objective. Here, Usx is the uniform distribution over the state-action space. The coefficient EX ensures that the bonus decays with the value uncertainty. The unvisited state-action pairs will eventually be visited by the policy because they have sufficiently high rewards. Our experiments will show that, in tabular setting, this method is very effective. However, a concern that it might fail to scale to high dimensional sate-actionn space.
5.2.2 Entropy Regularization
Another intricacy of the optimization that the optimal solution of the BOO objective could change dramatically across the parameter space from episode to episode, which renders the optimization
7

---

extremely hard. A revealing fact is that small change in the model could change the optimal policy dramatically, making the loss landscape unsmooth. Hence, we introduce an untropy-regularii optimization procedure, which starts with a high initial entropy regularization and gradually annealing. The entropy plays role in smoothing the policy's 's loss landscape such that the optimal policy will not change drastically when the model changes. The smoothing effect of entropy regularization is also discussed previously in [39].
The entropy-regulariiee learning objective mimics the maximum entropy RL [40]:
Ju V.T.M(si) + log Pr(M[HH) Ex (
KL(T(sn, ()]l+(s,
(5)
-V (s1) + X log Pr(M)))))
where (T(pl)g) stands for the relative entropy, म is prior policy ensuring is absolutely continuous w.r.t n, the hyperparameter Ç controls the amount of entropy, and V is the entropy-regularize value.
The entropy term is downscaled in proportion to the value uncertainty such that the influence of regularization diminishes with time. We denote by Ma the set of models parameterized by
0. Let b, be the smallest number ensuring that, for any Ma E .Ma there exists Te E II
{ (L((T(s, (s), h)) < be, Vs S, h E [H] such that sup,- V. ".",,,, (s1) Vi S C.
Then, the value of the maximum entropy policy #* arg max Via.M (s1) satisfies that
H
V .M (81)
V .M (81)
C CT.
KT, (sh, h)] (
VTt (s1) -E% - CTE MM
KL(
(sh. (s ()]la(s,,
(6)
sup V ,M (M1s) - - Cbe
-
If e is sufficiently small, then the sub-optimality gap caused by entropy regularization will decrease the same rate the decay of value uncertainty, which ensures that the resulting policy covers multiple uncertain actions without detriment to the performance.
The antropy-regularin value is equivalently defined by the following Bellman backup,
V T. (sx) = (sn, .M (sh, a,)] - <% (TL((((S,))) ha]lss (s) h)), wh E [H],
2 (sh, an) Me (sn, an)) + BERTiNPM (es.oa)
h+1 (sn+1)] wh. [H 1].
where QT (SH, aH) (sH, aH). The optimization of the policy can be carried out by, for example, the maximum entropy actor-critic algorithm [40] or the soft actor-critic algorithm [41]. In finite MDPs, the optimal value is given by soft value iteration.
O @ an)
a M (Sn) <X log E
az a(an |sh, h) exp
(8)
where т (an 8h, h) is the probability of an under the distribution T8h,, h). The maximum entropy policy #* is then derived from the optimal value
(2 @x%-M (sh, an)
Vit M.'",M(L .M(s))
(a sh, h) (ax 1hh h) exp
The gradient of the entropy-regularize value w.r.. the model is similar to that specified in Theo- rem 5.1, with the value replaced by the engroiy-regularized value.
Experiments
This section compares the performance BOO with PSRL and UCRL2 in RiverSwim, Chain, and Random MDPs. WiverSwim and Chain are hard-exploration MDPs requiring the agent to explore

---

efficiently, while Random MDPs test the average performance. Two implementations of BOO are presented, namely, FiniteBOO and BPS. FiniteBOO is the BOO with entropy regularization and mean reward bonus mentioned in Section 5.2, which is empirically found to be the best variant in tabular setting according to the ablation study. BPS an implementation of Algorithm 4 (BOO via posterior sampling).
0.4
0.6
0.6
0.6
0.35
0.35
0.35
0.35
1,r 0.005
S1
0.05
S2
0.05
S3
0.05
S4
0.4
Sg
0.6,
1
1
1
1
(a) RiverSwim
1
1
1,r~N(0,1)
S1
2z
1
1 i
St
1 1. r~N(111)
1
1
1
1
Chain
Figure I: Illustrative diagrams for RiverSwim and Chain. Solid and dotted arrows represent actions, "left" and "right", respectively, with the transition probability tagged. The action left never fails, but the action right often fails. Except for the rewards shown in the figure, the rewards of other state-action pairs are all zero.
6.1 RiverSwim
The RiverSwim is an MDP where states are organized in chains, and the agent can move left or right, as shown in Figure 1(a), Although the rightmost state has huge reward, the action of moving right fails with a high probability. Only a policy moves right at each time period has a small chance of success.
We start with the experiment on the RiverSwim demonstrate the performance of our algorithm in the face of high transition uncertainty. We perform experiments for ten seeds on RiverSwim with SS H 5, |A| and record the cumulative regret over 100,000 time steps. shown in Figure 2(a), our algorithm is competitive to PSRL and outperforms UCRL22 significantly.
6.2
Chain
The chain MDP is variant of the RiverSwim, which has Gaussian rewards and relatively deterministic transitions, as shown Figure 1(b). Although transitions are relatively certain, the stochastic rewards make the problem difficult to explore. The horizon H and the number of states |S] are equal to the length of the chain.
We evaluate our algorithms in Chain of a length L E {10, 40) for 100, 000 episodes and ten random trials. Figure 2(d~ff illustrates that our algorithm compares favorably with PSRL and UCRL2, which certifies the effectiveness of BOO in problems requiring long-term planning.
6.3 Random MDPs
Random MDPs are tabular MDP models randomly generated from a prior distribution and used to test the general performance of the algorithm.
We randomly generate 100 stochastie MDPs with |S| = |A| = 5 and |S| = H 20, |A| from the prior and measure the performance of algorithms over 10, 000 timesteps. As shown in

---

BPS
FinileBOO
PSRL
UCRL2
600
400
350
Cumulative regret
300
400
250
1500
1000
200
100
500
0
20000
40000
60000
100000
4000
8000
10000
2000
500n
10000
Episodes
Episodes
Episodes
(a) RiverSwim
(b) Random MDPs with size
(c) Random MDPs with size 20
1200
8000
250
Cumulative regret
1000
800
150
600
4000
400
2000
50
0
20000
40000 60000
80000
L00000
20000
40000 60000 Episodes
50000 100000
20000
50000 50000 100000 Episodes Chain with length
40000
Episodes
(d) Chain with length
Chain with length
Figure 2: (a~f) show the cumulative regrets of different algorithms on RiverSwim ([S) = H
|A| = 2), Random MDPs ([S) H |A| 5), Random MDPs ([S) H 20, |A| 5), and the chains of different lengths, respectively.
Figure 2(b), the performance of BOO and BPS is close to PSRL, and both algorithms outperform UCRI.2 significantly. However, the performance gap between FiniteBOO and PSRL in Figure 2(c) indicates that there remains a challenge in the optimization of large-scale MDPs.
Conclusion
This paper proposes BOO generic model-based RL algorithm. is provably sample-efficient and enjoys Ö(VK) regret for models in minee-dimensional RKHS, where K is the number of episodes. To optimize the BOO objective, we propose the value model gradient and optimization techniques, such entropy regularization, to improve its efficiency. Through have shown that BOO is competitive with PSRL and outperforms UCRL2 greatly. However, to apply BOO in real-world RL problems, there remains lots of work be done. Importantly, to develop methods that further facilitate the gradient-based optimization of BOO in large-scale problems. is also an appealing direction for future work adapt the scaling parameter of BOO on an instance-dependent basis.
experiments,
need
Acknowledgements
This work supported by National Key Research and Development Program of China (2020AAA 0107200), the National Science Foundation of China (61921006, 618761 19, 62276126), the Natural Science Foundation of Jiangsu (BK20221442), and the Fundamental Research Funds for the Central Universities (0221 14380010))
References
[1] R. Sutton and G. Barto, Reinforcement Learning: An Introduction (Second Edition). MIT Press, 2018.
10

---

[2] Q. Liu, J. Zhai, Z. Zhang, S. Zhong, Q. Zhou, P. Zhang, and J. Xu, "A survey on deep reinforcement learning," Chinese Journal of Computers. vol. 41, no. I. pp. 1-27, 2018.
[3] M. Ghavamzadeh, S. Mannor, Pineau, and A. Tamar, "Bayesian reinforeement learning: survey," Foundations and Trends in Machine Learning, vol. 8, no. 5-6, pp. 359-483, 2015.
[4] C. H. Papadimitriou and J. N. Tsitsiklis, "The complexity of Markov decision processes," Mathematics of Operations Research, vol. 12, no. 3, pp. 441-450, 1987.
[5] O. Madani, S. Hanks, and A. Condon, "On the undecidability of probabilisticc planning and related stochastic optimization problems." Artificial Intelligence, vol. 147, no. I, pp. 5-34, 2003,
[6] Z. Zhang, M. L. Littman, and X. Chen, "Covering number complexity measure for POMDP planning and learning." " in AAAI Conference on Artificial Intelligence, pp. 1859, 2012.
[7] Z. Zhang, D. Hsu, and W. S. Lee, "Covering number for efficient heuristic-based POMDP planning." in International Conference Machine Learning, pp. 28 36, 2014.
[8] 7. Zhang, D. Hsu, W. S. Lee, Z. W. Lim, and A. Bai, "PLEASE: Palm leaf search for POMDPs with large observation spaces," in International Conference on Automated Planning and Schedul- ing, pp. 247-257, 2015.
[9] C. Wu, R. Kong, G. Yang, X. Kong, Z. Zhang, Y. Yu, D. Li, and W. Liu, "LB-DESPOT: Efficient online POMDP planning considering lower bound in action selection (student abstract)," in AAAI Conference on Artificial Intelligence, pp. 15927-15928, 2021.
[10] C. Wu, G. Yang, Z. Zhang, Y. Yu, D. Li, W. Liu, and J. Hao. "Adaptive online packing-guided guided search for POMDPs," in Advances in Neural Information Processing Systems, pp. 28419-28444 2021.
[11] M. G. Azar, Osband, and Munos, "Minimax regret bounds for reinforcement learning." in International Conference on Machine Learning, pp. 263 272, 2017.
[12] S. R. Sinclair, S. Banerjee, and C. L. Yu, "Adaptive discretization for episodic reinforcement learning in metric spaces," in ACM on Measurement and Analysis of Computing Systems, pp. 1-44, 2019.
[13] C. Jin, Z. Yang. Z. Wang. and M. I. Jordan, "Provably efficient reinforcement learning with linear function approximation," " in Conference on Learning Theory, pp. 2137-2143, 2020.
[14] V. Dani, T. Hayes, and S. Kakade, "Stochastic linear optimization under bandit feedback," in Conference Learning Theory, pp. 355-366, 2008
[15] I. Osband and B. V. Roy, "Why is posterior sampling better than optimism for reinforcement learning?," International Conference on Machine Learning, pp. 2701-2710, 2017.
[16] T. Jaksch, R. Ortner, and P. Auer, "Near-optimal regret bounds for reinforcement learning." " Journal of Machine Learning Research, vol. 11, no. 51, pp. 1563-1600, 2010.
[17] I. Osband, D. Russo, and B. Van Roy, "(More) efficient reinforcement learning via posterior sampling," in Advances in Neural Information Processing Systems, pp. 3003-3011, 2013.
[18] A. Guez, N. Heess, D. Silver, and P. Dayan, "Bayes-adaptive simulation-based search with value function approximation." Advances in Neural Information Processing Systems, pp. 451-459, 2014.
[19] S. R. Chowdhury and A. Gopalan, "Online learning in kernelized markov decision processes," in International Conference on Artificial Intelligence and Statistics, pp. 3197-3205, 2019.
[20] S. Kakade, Krishnamurthy, K. Lowrey, M. Ohnishi, and W. Sun, "Information theoretic regret bounds for online nonlinear control," in Advances in Neural Information Processing Systems, pp. 15312-15325, 2020.
[21] M. A. Strens, "A Bayesian framework for reinforcement learning," " in International Conference on Machine Learning, pp. 943-950, 2000.

---

[22] D. Russo and B. Van Roy, "Learning to optimize via posterior sampling," Mathematics of Operations Research, vol. 39, no. 4, pp. 1221-1243, 2014.
[23] I. Osband, C. Blundell, A. Pritzel, and B. Van Roy, "Deep Exploration via Bootstrapped DQN," in Advances in Neural Information Processing Systems, vol. 29, pp. 4026-4034, 2016.
[24] Ian Osband, Benjamin Van Roy, and Zheng Wen, "Generalization and Exploration via Ran- domized Value Functions," " in Proceedings of The 33rd International Conference on Machine Learning (Maria Florina Balcan and Kilian Q. Weinberger, eds.), vol. 48, pp. 2377-2386, PMLR, June 2016.
[25] I. Osband, B. V. Roy, D. J. Russo, and Z. Wen, "Deep Exploration via Randomized Value Functions," Journal of Machine Learning Research, vol. 20, no. 124, pp. 1-62, 2019.
[26] S. Curi, F. Berkenkamp, and A. Krause, "Efficient model-based reinforcement learning through optimistic policy search and planning," in Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, eds.). pp. 14156-14170, 2020.
[27] P. Kumar and A. Becker, "A new family of optimal adaptive controllers for Markov chains," IEEE Transactions on Automatic Control, vol. 27, no. pp. 137-146, 1982.
[28] X. Liu, P.-C. Hsieh, Y. H. Hung, A. Bhattacharya, and P. Kumar, "Exploration through reward biasing: Reward-biased maximum likelihood estimation for stochastic multi-armed bandits," in International Conference Machine Learning, pp. 6248-6258, 2020.
[29] Y.-H. Hung, P.-.. Hsieh, X. Liu, and P. R. Kumar, "Reward-biased maximum likelihood estimation for linear stochastic bandits," in AAAI Conference on Artificial Intelligence, pp. 7874- 7882, 2021.
[30] A. Mete, R. Singh, X. Liu, and P. R. Kumar, "Reward biased maximum likelihood estimation for reinforcement learning," " in Annual Learning for Dynamics and Control, pp. 115-827, 2021.
[31] A. Mete, R. Singh, and P. R. Kumar, "Augmented RBMLE-UCB approach for adaptive control of linear quadratic systems," arXiv preprint arXiv:2201. 10542, 2022.
[32] R. J. Hyndman, "Computing and graphing highest density regions," The American Statistician, vol. 50, no. 2, pp. 120-126, 1996.
[33] A. Gelman, J. B. Carlin, H. S. Stern, D. B. Dunson, A. Vehtari, and B. Rubin, Bayesian Data Analysis. Chapman and Hall/CRC, 2013.
[34] R. J. Hyndman and Fan, "Sample quantiles statistical packages," " The American Statistician, vol. 50, no. 4, pp. 361-365, 1996.
[35] O. A. Adekola, Asymptomatic posterior normality for stochastic processes. PhD thesis, Univer- sity of Surrey, Guildford, 1987.
[36] J. J. Williams, "Simple statistical gradient-following algorithms for connectionist reinforcement learning," Machine Learning, vol. 8. no. 3, pp. 229-256. 1992.
[37] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour, "Policy gradient methods for reinforce- ment learning with function approximation." in Advances in Neural Information Processing Systems, pp. 1057-1063, 2000.
[38] S. Kakade and J. Langford, "Approximately optimal approximate reinforcement learning." in International Conference on Machine Learning, pp. 267-274, 2002.
[39] Z. Ahmed, N. L.. Roux, M. Norouzi, and D. Schuurmans, "Understanding the impact of entropy on policy optimization," in International Conference on Machine Learning, pp. 151-160, 2019.
[40] S. Levine, "Reinforcement learning and control as probabilistic inference: Tutorial and review." arXiv preprint 1805vv1005.000 2018
12

---

[41] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine, "Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor," in International Conference on Machine Learning, pp. 1861-1870, 2018. 2018.
[42] M. Brookes, "The matrix reference manual," 2020. [online] staff/ ///d///aaattiiitttt.// html.
[43] A. Klenke, Probability Theory: A Comprehensive Course. Springer Science & Business Media, 2013.
[44] C. A. Micchelli and M. Pontil, "On learning vector-valued functions," Neural Computation. vol. 17, pp. 177-204, Jan. 2005.
[45] D. Russo and B. Van Roy, "Eluder dimension and the sample complexity of optimistic explo- ration," " in Advances Neural Information Processing Systems, pp. 2256-2264, 2013.
[46] C. Jin, Q. Liu, and S. Miryoosefi, "Bellman eluder dimension: New rich classes RL problems, and sample-efficient algorithms," in Advances in Neural Information Processing Systems, pp. 13406-13418 13418, 2021.
[47] I. Osband and B. Van Roy, "Model-based reinforcement learning and the eluder dimension," in Advances in Neural Information Processing Systems, pp. 1466-1474, 2014.
[48] A. Maurer, "A bound on the deviation probability for sums of non-negative random variables," Journal of Inequalities in Pure and Applied Mathematics, vol. 4, no. 1, 2003.
[49] S. M. Kakade, "A natural policy gradient," in Advances in Neural Information Processing Systems, pp. 1531-1538, 2002.
[50] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan, "Optimality and approximation with policy gradient methods in Markov decision processes," in Conference on Learning Theory, pp. 64-66, 2020.
[51] N. N. Schraudolph, "Fast curvature matrix-vector products for second-order gradient descent," Neural Computation, vol. 14, no. 7, pp. 1723-1738, 2002.
[52] Martens, "New insights and perspectives on the natural gradient method," Journal of Machine Learning Research, vol. 21, no. 146, pp. 1-76, 2020.
[53] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski. Peterson, W. Weckesser, J. Bright, S. van der Walt, M. Brett, J. Wilson, K. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, I. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro. F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors, "SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python," Nature Methods, vol. 17, pp. 261-272, 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]
(c) Did you discuss any potential negative societal impacts of your work? [No] No relevant
potential negative impacts is identified.
(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]
(b) Did you include complete proofs of all theoretical results? [Yes]
13

---

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 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 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, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, 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": "osliAmjtlbd", "reviewer": "Reviewer_pz9j", "summary": "The paper considers the exploration-exploitation tradeoff in reinforcement learning and develops a new algorithm rooted in the \"optimisim in the face of uncertainty\" principle. The paper starts from a Bayesian perspective where the policy is selected optimistically w.r.t. a credible, high-probability region of the model posterior. It then develops a lagrangian relaxation (BOO) and provides a regret bound that is sublinear depending on a schedule for the Lagrange multiplier and novel upper-bounds for the distributional eluder dimension. The paper also shows that BOO can be approximated by optimizing over samples from the posterior and, based on that, developes a practical algorithm for parametric models based on the reinforce trick applied to the model's stochasticity. It also extends this methods with the natural policy gradient. The main paper does not provide any experimental evaluation, though a small-scale study is included in the appendix.", "questions": "Could you summarize what you view as the main technical novelties in the derivations of the regret bound?\n\nIt seems to me that the policy gradient in (8) would, like standard reinforce, yield high-variance results for close-to-detministic models as the gradient of the log-probability becomes very steep. Usually that is \"resolved\" by adding an entropy bonus for the policy, but this seems unreasonable for the model. How do you deal with this in practice? \n\nThe Related work section is currently a bit sparse and should be expanded. Below are some recent papers on OFU that come to mind, it would probably be good to discuss them in relation to the current paper.\n- Chowdhury et. al, \"Online Learning in Kernelized Markov Decision Processes\", AISTATS, 2019\n- Kakade et. al, \"Information theoretic regret bounds for online nonlinear control\", NeurIPS 2020\n- Curi et. al., Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning, NeurIPS 2020", "limitations": "For the theoretical part are discussed throughout the paper, but not for Sec. 6", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper investigates the relevant topic of efficient exploration in reinforcement learning. It provides novel regret bounds. As far as I can tell the theoretical analysis is rigorous and presents an interesting perspective on how to side-step defining explicit confidence regions for the model. The main limitation, which is also discussed in the paper, is that this comes at the cost of having to manually specify a Lagrange multiplier to trade-off model-likelihood v.s. gained value. While the paper provides regret bounds for fixed schedules that depend on the model-class, without an adaptive selection this severely limits the usefullness of the approach.\n\nThe paper tries to cover both the theoretical contribution and the practical question of how to optimize it. While this is commendable in general, in this case experiments are banished to the appendix. In it's current form, imho anything beyond Theorem 6.1 does not add significant value, since empirical concerns like entropy-regularization would also require empirical evaluation. The current experiments in the appendix lack significant details, but are limited to toy systems and do not seem to cover any results from Sec. 6.", "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": "iyJojYahUAs", "reviewer": "Reviewer_hRsL", "summary": "This paper proposes a new model-based RL that exploits the principle of optimism in the face of uncertainty (OFU). The proposed algorithm, Bayesian optimistic optimization (BOO) is shown to be sample-efficient and less computationally expensive than previous Bayes-adaptive MDP methods. The paper also provide theoretical analysis to show that the algorithm has a sublinear regret for many model classes. ", "questions": "See below", "limitations": "\nThe paper proposes an interesting idea to combine OFU into MBRL. Constructing an uncertainty constraint is not new in MBRL. The step-by-step derivation from start to the final algorithm CBOO is very clear and easy to follow. The use of Lagrangian Relaxation of CBOO is sensible to exploit uncertainty in making decisions. I was wondering how this is different from adding UCB, ie. probably the closest work is [1]. Does it lead to a totally different behavior for optimization/online planning? Can the authors also comment or discuss about your approach in comparisons to previous work that already introduced uncertainty bonus to Bayes-Adaptive MDP?\n\nThe theoretical result reported in Theorem 4.1 is interesting. Can the authors provide a bit of insights about it, i.e. on why the variance is at least m/2 is good thing for RL?\n\nIt is also very interesting to see the authors provided practical optimization aspects for the proposed algorithm. It would be very interesting if this can be realized with empirical results.\n\n[1] Arthur Guez, Nicolas Heess, David Silver, Peter Dayan:\nBayes-Adaptive Simulation-based Search with Value Function Approximation. NIPS 2014: 451-459\n\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- Principled method to integrate OFU into MBRL. \n- Theoretical analysis showing a sublinear regret\n- An optimization based on the natural gradient and entropy\nregularization\n\nWeakness:\n- No empirical results\n- Lacking discussions on related work of OFU on Batesian BMRL.", "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": "_57Aagb8O9p", "reviewer": "Reviewer_EVFD", "summary": "This paper presents a model-based reinforcement learning algorithms based on the optimism in the face of uncertainty. First of all, the algorithm CBOO is constructed based on Bayesian credible region. However, CBOO is difficult to use in practice and therefore, the authors apply Lagrangian relaxation and posterior sampling to construct practical algorithm. Then, the authors provide regret analysis and conditions for various model setting. Finally, the authors discuss the optimization of the BOO.", "questions": "1. This paper seems to deal with frequentist RL problem. But the authors introduce the definition of Bayesian regret in preliminaries. This confuses me if I'm understanding correctly. Would you clarify this part?\n\n2. Many previous frequentist model-based RL algorithms also uses similar concept with Bayesian credible region. For example, in [1], UCRL2 also introduces ‘plausible MDPs’ $\\mathcal{M}_k$, where true MDP $M$ is in $\\mathcal{M}_k$ with high probability $1-\\delta$. Then, UCRL2 choose optimistic MDP $\\tilde{M}_k$ among these plausible MDPs. I would like to know the main difference between BOO and previous model-based RL algorithms in finite MDP setting. It will be very helpful for understanding this paper.\n\n3. How can we construct Algorithm 4 in practice? In my opinion, Algorithm 2 is nothing new and already well-known part. However, as the authors mentioned in Section 4.1, obtaining optimistic MDP (from credible region), is not trivial. Previous model-based RL algorithms have focused on how to make it possible in practice. Then, how can we construct a practical OFU algorithm based on Algorithm 4?\n\n4. In conclusion section, the authors claimed BOO enjoys sublinear regret. Where can we know that the regret is sublinear? In Theorem 5.1, (7) is the regret bound for the best $v$. But, the order of $K$ is $1+\\text{(some positive)}\\ge 1$: as the number of episode increases, the regret bounds exponentially increases. It looks too weird to me. Would you please correct my misunderstanding?\n\n[1] Auer, Peter, Thomas Jaksch, and Ronald Ortner. \"Near-optimal regret bounds for reinforcement learning.\" NIPS 2008.\n", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\nThe proposed algorithm is a general algorithm for various model classes. In addition, the authors provide regret analysis to support the proposed algorithm.\n\n**Weakness**:\n\n1. Related work.\n\nThere are many model-based RL algorithms in finite MDPs. However, this paper presents only a very brief introduction to the related work. Because BOO can be reduced to finite MDPs, comparisons with previous works would be very helpful for understanding (e.g. connections between Theorem 5.1 in this paper and regret analysis in previous work)\n\n2. Clarity\n\nIn this paper, notations are very confused. For example, $M$ is used to express MDP and to define covering number. Also, there is no definition of $\\mathcal{X}$ in the paper. Finally, what is the definition of model – only transition, or only policy, or both? It is very confusing because there are no connection between $\\mathcal{X}$, $\\mathcal{F}$ and notations in MDP.\n\n3. Implementation\n\nIt is not clear how to implement practical algorithm. It would be good if the authors could suggest at least the algorithms for models in Table 1. (how to compute & update posterior, how to sample MDPs from posterior, how to compute $\\arg\\max_\\pi$, etc.)\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": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept