Near-optimal Policy Identification in Active Reinforcement Learning
Authors: Xiang Li
Viraj Mehta
Johannes Kirschner
Ian Char
Willie Neiswanger
Jeff Schneider
Andreas Krause
Ilija Bogunovic
Venue: ICLR 2023 notable top 5% (2023)
Keywords: reinforcement learning
contextual bayesian optimization
kernelized least-squares value iteration

Abstract: Many real-world reinforcement learning tasks require control of complex dynamical systems that involve both costly data acquisition processes and large state spaces. In cases where the expensive transition dynamics can be readily evaluated at specified states (e.g., via a simulator), agents can operate in what is often referred to as planning with a \emph{generative model}. We propose the AE-LSVI algorithm for best policy identification, a novel variant of the kernelized least-squares value iteration (LSVI) algorithm that combines optimism with pessimism for active exploration (AE). AE-LSVI provably identifies a near-optimal policy \emph{uniformly} over an entire state space and achieves polynomial sample complexity guarantees that are independent of the number of states. When specialized to the recently introduced offline contextual Bayesian optimization setting, our algorithm achieves improved sample complexity bounds. Experimentally, we demonstrate that AE-LSVI outperforms other RL algorithms in a variety of environments when robustness to the initial state is required. 

Published as a conference paper at ICLR 2023
NEAR-OPTIMAL POLICY IDENTIFICATION IN ACTIVE REINFORCEMENT LEARNING
Xiang Li Viraj Mehta Johanness Kirschner Ian Char?, Willie Neiswanger', Jeff Schneider", Andreas Krause', .ljja Bogunovic
ETH Zurich, "Carnegie Mellon Uni, Uni. of Alberta, "Stanford Uni., Uni. College London
xi .aiangg..@outee ww@outttttttto look. (virajm, ichar, schneide) cnu.edu,
jki rrachh@usabeeraa ca, neiswangerecs. st.anfrrd.c..mm.. edu, krausea@ethz. ch, i. Abogunovic@ucll.cc.u
ABSTRACT
Many real-world reinforcement learning tasks require control of complex dynam- ical systems that involve both costly data acquisition processes and large state spaces. In cases where the transition dynamics can be readily evaluated at speci- fied states (e.g., via simulator), agents can operate in what is often referred to as planning with generative model. We propose the AE-LSVI algorithm for best- policy identification, a novel variant of the kernelized least-squares value iteration (LSVI) algorithm that combines optimism with pessimism for active exploration (AE). AE-LSVI provably identifies near-optimal policy uniformly over tire state space and achieves polynomial sample complexity guarantees that are independent of the number of states. When specialized to the recently introduced offline contextual Bayesian optimization setting, our algorithm achieves improved sample complexity bounds. Experimentally, we demonstrate that AE-LSVI out- performs other RL algorithms in a variety of environments when robustness to the initial state is required.
INTRODUCTION
Reinforcement learning (RL) algorithms are increasingly applied to complex domains such as robotics (Kober et al. 2013), magnetic tokamaks (Seo et al. [202]] Degrave et al. 20222,, and molec- ular search (Simm et al. 2020a b). A central challenge in such environments that data acquisition is often time-consuming and expensive process, or may be infeasible due to safety considerations. common approach is therefore to train policies offline by interacting with simulator.
However, even when a simulator is available, such applications require algorithms that are capable of learning and planning in large state spuces. Many existing approaches require large amount of training data to obtain good policies, and efficient active exploration in large state spaces is still an open problem. Moreover, when deploying policies trained on simulators in real-world applications, crucial requirement is that the policy performs well in any state that it might encounter. In par- ticular, at training time, the learning approach has to sufficiently explore the state space. This is of particular importance when at test time, the system's 's state is partly out of the control of the learning algorithm-e.g. for a self-driving car or robot, which may be influenced by human actions.
In this work, we formally study the setting of reinforcement learning with generative model. Our objective is to learn a near-optimal policy by actively querying the simulator with a state-action pair chosen by the learning algorithm. The simulator then returns a new state that is sampled from the transition model of the (simulated) environment. Inspired by previous works, we make structural assumption in the kernel setting, which states that the Bellman operator maps any bounded value function to one with bounded reproducing kernel Hilbert space (RKHS) norm. In particular, this assumption implies that the reward and the optimal Q-function can be represented by an RKHS function. We propose novel approach based on least-squares value iteration (LSVI). The algorithm designed to actively explore uncertain states based on the uncertainty the Q-estimates, and makes use of optimism for action selection and pessimism for estimating near-optimal policy.
"The first three authors contributed equally to this work.

---

Published as a conference paper at ICLR 2023
Contributions We propose novel kernelized algorithm for best policy identification in reinforce- ment learning with a generative model. Our sampling strategy actively explores (i) states for which the best action is the most uncertain and (ii) the corresponding "optimistic" actions. We prove sam- ple complexity guarantees for finding an 6-optimal policy uniformly over any given initial state. Our bounds scale with the maximum information gain of the corresponding reproducing kernel Hilbert space but do not explicitly scale with the number of states or actions. When specialized to the offline contextual Bayesian optimization (BO) setting (Char et al. 2019), we improve upon sample complexity guarantees from prior work. Finally, we include experimental evaluations on several RL and BO benchmark tasks. The former of these includes one of the first empirical evaluations of the model-free optimistic value iteration algorithms with function approximation (ang et al.) 2020).
2 PROBLEM STATEMENT
We consider an episodic MDP (S, (Pa)netu) (ra)neta)) with state space S. action space A. horizon H E N, Markov transition kernel (PP))ee and deterministic reward functions (Th : S x A + [0. 1))eEm)- In particular, for each h E [H]. we let (x,(-s,,)) a) denote the probability transition kernel when action a is taken at state s E S in step h E [H]. A policy consists of H functions π (TT))eew) where for all h E [H] n (-Is) a probability distribution over the action set A. In particular, nA (als) the probability that the agent takes action a in state at step h.
We assume the generative (or random) access model, in which the agent interacts with the environ- ment in the following way: Let I denote the number of episodes and // the horizon, i.e., the number of steps in each episode. Then for each E [T], h E [H) the agent chooses s E S, aj, E A, obtains the reward r% (s). af) and observes the new state s/2, P af))
To measure the performance of an agent, we use the value function. For a policy n, h E [H] 8 E S, and a E A, the value function Vi, SS + R and the Q-function 0% : S A - [0, H] are given by:
H
(s) E Σ The (sw, an)
= s), (T))) EE,
Σ h==h
rhe (Tw,saan)) aw)) =, on a)
(1)
where Fr denotes the expectation with respect to the randomness of the trajectory {(h, as } that is obtained by following the policy æ. We use n' to denote the optimal policy, and we abbreviate ViT", QTT as VY,, Qi respectively. We also have Vi[(s) (s) = sup, (T((s) for all s E S and h [H].
The goal is to find an e-optimal policy while minimizing the number of necessary episodes T. More precisely, for a fixed precision > 0 and horizon H E N, the goal of the learner is to output a policy f after a suitable number of episodes T > such that [VV - , *
le (())
(S) S E.
Finally, we also recall the Bellman equation that is associated to some policy
V#+1 = O, (7(s, a) = rn(s, a) + Ee PV (s'),, VT = Eana (at=) (07
and the Bellman optimality equation:
V = O, ()(s, = Tn. (n, a) E (s']],
(i((s) max (7, aeA
(3)
It follows that the optimal policy nr is the greedy policy with respect to (Q7 he( property that is going to be useful later on when defining our active exploration strategy. We use the reproducing kerne Hilbert space (RKHS) function class to represent functions such the reward functions (ra (T))n(HH)) and the optimal Q-functions [Qi (Qe]he(()) (see the formal statement in Assumption 1 In particular, we consider space of well-behaved functions defined on X' = x A, where 76 denotes an RKHS defined on X' induced by some continuous, positive definite kernel function k : X' x X + R. We also assume that (i) X C Rd is a compact set, (ii) the kernel function is bounded k(r, x') for all x E X, and (iii) every f E H. has a bounded RKHS norm, i.c., I| I Bq H for some fixed positive constant BQ > O.
3 AE-LSVI ALGORITHM
Our algorithm runs in episodes t E [T] of horizon H. As in the kernel least-squares value iteration Yang et al. 2020), at the beginning of every episode 1, it solves sequence of kernel ridge
2

---

Published as a conference paper at ICLR 2023
regression problems based the data obtained in the previous t 1 episodes obtain value function estimates (Q
2 E arg min JEN
(ra(s), aA) + (5 - f(sh/ oh))) + Allf
(4)
where À is the regularization parameter. Recalling that x E A = in Eq. 4 can be written in closed form follows:
Sx xxAA A, the solution of the problem
= (x (KY + 'y,
(5)
where (x) E R the kernel matrix K3 I (=(--))((--) and observations Y E R--1 given as follows:
(x) = [k(2), r)................. kaala' ,x),. K3 = |k(2), 2% ) [M = (s
Next, we can also compute the uncertainty function of (:, :) in the closed form:
(s, a) / (k(2, (x) (K) + AT) A (x))
(6)
We recall that each reward function is bounded in [0, 1]. We use [-10 to denote the truncation to the interval [0, Hl + 1] and we define the optimistic Q% and pessimistic Qh value estimates (i.e., upper and lower confidence bound of Q7: see Lemma 4.1 and Lemma A.I)
ea(,-)= = ((6.))=(((()))))) ( $1
A+1
V²O max (,(),), aEA (i (sh a V 1+1
21(())= = k))) + A1) 'V
(8)
Similarly, we have
Qh(-)) =
- - H-4+1 V4() max Q (1,a), aEA (1(-)) = (. (K) AZ) Yy I at)) V V (5h.))
(9)
(10)
Our proposed algorithm AE-LSVI is presented in Algorithm] 1 At each h. the algorithm uses opti- mistic and pessimistic value estimates from Eqs. 7 and 9 (computed based on the data collected in previous episodes), and selects 8 and of as:
max Qx max Q ((,ss((a))) (s. EEA
$ E arg max
(11)
aad
a arg max Qh(s)aa)) aEA
(12)
The main intuition behind proposed sampling rules as follows. Since the optimal policy "' is the greedy policy with respect to (Qi, [e]H). we do not need to learn (QA ]e] everywhere on x A. Hence, it is sufficient exploration strategy is explicitly designed to focus (i) states for which the best action is the most uncertain (Eq.
focus on discovering the best actions for each state. Our active
TT)) and (ii) corresponding best "optimistic" actions (Eq, [22
We use ीा to denote the final reported policy returned by AE-LSVI (see Algorithm D There are various reasonable greedy- based choices for îĄ.. The simplest one is to return TTy(()) =
arg max,eA QT ())a), but in our theory and experiments, we focus equating का with the pol- icy with the highest lower confidence estimate Q (s, a). Our sampling strategy combined with the proposed policy reporting rule allows for discovering an e-optimal policy uniformly over any given initial state we formally show in the next section.
THEORETICAL RESULTS
We use the structural assumption for the kernel setting from Yang et al. (2020) which states that the Bellman operator maps any bounded value function to function with bounded RKHS norm.
3

---

Published as a conference paper at ICLR 2023
Algorithm 1 AE-LSVI (Active Exploration with Least-Squares Value Iteration)
Require: kernel function exploration parameter B > 0, regularizer À 2 1
1: for = do
2: for (1..... } do
Set Q H+41 QH-11 the zero functions 4: for H H,..., do
3:
5:
Obtain Qn and Qi from Eq. 7 and Eq. (9) end for
6:
7: Choose s% E arg max, max On (s, maX 0%
8: Choose af, E arg max.cA (sh.
9: Observe the reward rn (8), of) and the next state 5/n ~ Ps( 10.(-19h.00
end for
11: end for
Output the policy estimate कं such that (., = arg max max(e(T] (8,00
Assumption 1.
Let BQ > 0 be fixed positive constant. Let k (S x A)2 - R be continuous
kernel function on compact set S x A C Ra such that su k(z, x') S 1. We assume that [TT, Ql S. BoHl for all functions Q : S x A + [0, H) and all h E [H]. where T denotes the Bellman optimality operator, ie.,
= o)
+ EssFaalas max Q(s Q(s',aa) L'EA
(13)
Assumption D implies that for every h [H], both (n())) and (: are elements of the set
{.f E H T S. BoH Conversely, a sufficient condition for Assumption to be satisfied with BQ 2 that Pr et al. 2020). Moreover, only assuming Q7 E H. 1Q S BQ for all h E H is not enough i
S {f
|| < 1} for all E [ and s' E (Yang
order to obtain sample size guarantees which are polynomial in H and d (Du et al. 2020).
The main quantity that characterizes the complexity of the RKHS function class in the kernelized setting is the maximum information gain (Srinivas et al.) 2010)
sup (T( DIST
1 In - x K
(14)
where KD,D denotes the Gram matrix. |- denotes the determinant, À regularization
parameter, and the index l indicates the kernel. This quantity is known to be sublinear in T for most of the popularly used kernels (Srinivas et al., 2010).
Further, we define the set of possible optimistic and pessimistic value functions
@(T,h,b) {0(.)) [Q(:-) Bap( H-h-1
Q E H. 11 S 2H /T A), 3 DCS
(15)
where b and (.). is of the form Eq. 6 computed with data set D C SCSx A, and denote its (29 e*o-coerrngg number as No. T, h b). I Our sample complexity bounds depend on by > defined as the smallest number that satisfies the following inequality:
ST (T, I + 8 log No (H/T, h, bT) + 16 log(21 H) + 22 -2B3 (I+)) S (bT/H)² (16)
For many kernel functions, by has a sublincar dependence on T. For instance, by = Ol / (og((TH)) for bounded and continuously differentiable kernels with 7-finite spectrum for bounded and continuously differentiable kemnels with 7
and by = O(H exponential decay. See (Yang al. 2020 Corollary 4.4) for more details.
'The results on by hold despite Yang al. 2020 Lemma D.1) being stated only in the case of the smaller class obtained from only adding +Bap the definition of Q(:--) in Q(T, h, b) in Eq. (15
4

---

Published as a conference paper at ICLR 2023
We recall that the Bellman equation implies that 2h+1 (-), Qi( are upper and lower confidence
bounds for 02 for all h E [H], respectively (see Lemma A.1p.
while the target functions of ker- nel ridge regressions are T (++()) and T (.) As a technical tool, we use the following concentration result that follows from (Yang al. 2020 Lemma 5.2).
Lemma 4.1. Consider the setup of Assumption
and (++1(.), 2,(+) (f)() from Eqs. 6
and (9) computed with À = 1 + 1/T and B by from Eg. (16). Then with probability at least 1
2 the following holds for all t E [T] h E [H] and all (s,a) ES x A:
0 (7) 5 (s,o,,
(17)
0 5 (1 (h 280
(18)
With the previous confidence lemma in place, we state our main theorem that characterizes the sample complexity of AE-LSVI. The proof is given in Appendix A.2
Theorem 4.2. Consider the setting of Lemma 4.1 and let H E N4 be a fixed horizon. When running
Algorithm foo T episodes, then with probability at least 1 (2T ) )1, the best-policy estimate
ør (Algorithm) 7 Line 12) satisfies:
IV - -- S 22333H + V) (T(T.A) T
(19)
In other words, for a given fixed precision e 0, after T = 0
8 (
episodes (or of ( (TA)) samples) VIV - V1** I e holds with probability at least 1 - (2T2
2
The obtained result is general since it holds for any kernel function that satisfies Assumption [ To obtain concrete kemnel-dependent regret bounds it remains to specify the kernel and the bounds for the corresponding maximum information gain in Eq. (6). These are summarized Yang et al. (0200 for the most widely used kernels (see Assumption 4.3 and its discussion).
In the special case of linear kernels with the feature dimension d, our sample complexity guarantee reduces to Ō dd"#"" Better bounds (in terms of d) for this special case are known Ö df ), see, e.g., |Agarwal et al. (2019 Theorem 3.3). These bounds are obtained by the LSVI algorfthm with D-optimal design. Unlike this algorithm, AE-LSVI uses optimism for active exploration and such performance gap is present even in the simpler linear bandit setting where optimistic algorithms are known to attain worse sample complexity guarantees (Lattimore & Szepesvári, 2020, Chapter 22). The special case also includes the linear MDP setting, which assumes linear reward functions and linear transition kernels. For linear MDPs it is possible to find policy π satisfying Vi
(si(s) < using Ô /=²) samples (Hu et al. policy π can be found using O (H x)/=") samples (Yang et al. 2020). Both results hold with at least constant probability. However, they require that the initial state 81 is fixed for all episodes. In contrast, the result of Theorem holds uniformly over the entire state space.
2022); in our setting of Assumption [ such
5 APPLICATION TO OFFLINE CONTEXTUAL BAYESIAN OPTIMIZATION
In this section, we specialize Algorithm I to the offline contextual Bayesian optimization setting (Char al. 2019). We show that in this setting the proposed active exploration scheme leads to new sample complexity bounds that hold uniformly over the context space.
The offline contextual Bayesian optimization setting is similar the one considered in Section when H = 1. In particular, instead of having H different functions to learn, we have single un- known objective Q* S - IR that we learn about (from noisy point evaluations). Here, we refer to S as the context space, and assume that both S and AA are compact sets. As before, we use short- hand notation X = S A. each round L E [T). the learner chooses a context-action pair (s", a²) E S x A and observes y Q" (s', + n. (with independent sub- Gaussian noise). To choose (s" a²) at each round t, we make use of the same active exploration strategy from Eqs. (11) and 12 Our complete algorithm for the offline BO setting can be found in Appendix A.3 (see Algorithm
We define Q' S x A R (and 0² S x A R) similarly as Q) (resp. of) from Eq. 5 (resp.
Eq. (6) but with the modification of ignoring the index h and defining Y, (1:) R We
5

---

Published as a conference paper at ICLR 2023
further define the upper and lower confidence bounds for Q" as:
- Q
2((-))= 3:o (;
(20)
When Q" E H and 11Q S B correspond to some known kernel (such that k(x, x²) < 1 for all n, x' E X), then ( is a non-decreasing sequence of parameters that can be chosen ac- cording to Abbasi- Yadkori 20022 Theorem 3.11) to yield valid confidence bounds. Similarly, in case of Q" ~ (P,(0,k) k) (Bayesian setting), we can utilize Gaussian Process confidence bounds Sriiivas et al. 2010) and use the corresponding (Be ((e)) sequence. In what follows, we assume that (ee()) non-decreasing sequence such that with probability at least 1 -6 6,
('(s. S (8, S 5Q (s,aa
(21)
holds for all E [2] and (s, a) E A. Corollary 5.1. Assume (EE()) is set to satisfy Eq. (1.) Fix E (0,1) and run Algorithm
2 for
T2 (T,A)
(22)
rounds. Then, for every E S, the reported policy (t(() computed as in Line (Algorithm 2 satisfies (* (s)) 2 maxacA (s, 6 with probability at least - 5.
We briefly compare the result obtained in Corollary 5.1 with related results from the literature. In the Bayesian setting. CCar et al.] (2019 Theorem 1) obtain a sample complexity that scales as E[T] = ( & (T*))/²*) in expectation for given context distribution. In comparison, our result obtained in Eq. (22) holds in 8oe -nrm over the context space (i.e., implies bounds for any context distribution). When specialized the finite set X' = x A and when ʃ ~~ GPx(O, k), the (Srinivas et al. 2010). which then results in result of Corollary 5.1 holld with 37 = O(log([X
= ( logg" (IX)T")T.(T.A) leading to a significant improvement for large discrete context spaces. In the setting of distributionally robust Bayesian optimization (DRBO), Kirschner et al. (2020) obtain a result with the same dependency as ours. However, their bound holds only for a fixed contextual distribution and degenerates function of the distance between the training and test distributions.
RELATED WORK
Reinforcement learning with function approximation dates back to at least (Bellman et al. 1963;
Daniel, 1976; Schweitzer & Seidmann 1985). majority of work is in the online setting where the learning agent interacts with the environment while (typically) minimizing regret. Upper confi-
dence bound algorithms, originally developed in the bandit setting (Lattimore & Szepesvári 2020)
(also, frequently used in the related setting of best-arm identification, e.g.. (Gabillon et al. 2011 Kalyanakrishnan et al. 2012; Soare et al. (0144) have been successfully applied to tabular Markov decision processes (MDPs) (Auer & Ortner 2006; [Aur et al.) 2008), and extended to RL with function approximation. Jin et al. (2020) propose the LSVI-UCB algorithm in the linear MDP set- ting that achieves near-optimal regret bound. Yang et al. 2020 Domingues al. (2021) extend this work to the non-linear function approximation setting. These works are closely related to ours in that we make use of LSVI and confidence bounds for the Q-funccion in the kernelized setting. Unlike previous works, we consider the generative model setting and derive bounds on the sample complexity that hold uniformly over the initial state. There are many more alternative parametric
models that admit sample efficient algorithms (e.g.. Ayoub et al. 2020 Zhou et al. 2021 Du et al.,
2021 Zanette et al. 2020 Liu
2022).
In the generative model setting, the learner has access to a simulator that for any given state-action pair returns a next-state sample from the transition kernel. This provides additional flexibility to obtain data from states that are otherwise hard to reach in the environment. For the tabular case, matching upper and lower bounds are shown by Azar et al. (2012); Gheshlaghi Azar et al. (0013). In the generative model setting with function approximation, Lattimore al. (2020) show that policy iteration can be used to compute a optrmal policy given features such that the Q-fucciion of any policy can be approximated by linear function. Their algorithm uses D-experimental design to roll out policies from a sufficiently diverse set of states. The POLITEX algorithm (Abbasi- Yadkori et al. 2019 Szepesvári 2022) can be used in lieu of policy iteration and leads to tighter bounds on

---

Published as a conference paper at ICLR 2023
the approximation error. A similar approach based on LSVI is analyzed by Agarwal et al. (2019 Chapter 3).
In practical applications of RL, simpler approaches exploration are often used or exploration tech- niques inspired by upper-confidence bound algorithms or Thompson sampling are combined with deep learning function approximation. To list few, the c-greedy approach (Mnih et al. 2013), up- per confidence bounds (UCB) (Chen et al. (017): Thompson sampling (TS) (Osband et al. al, added Ornstein- Sereenn-Uheebeck action noise (Lillicrap al. (2015), and entropy bonuses (Haarnoja al.) 2018) are all widely applied. More sophisticated methods actively plan to encounter novel states (Shyam al., 2019 Ecoffet et al., 2021). Though these methods serve as reasonable heuristics and are usually computationally efficient, they either lack theoretical guarantees or lead to methods that require large numbers of samples. One recent practical work (Mehta et al. 2022b) gives an acquisi- tion function for the generative model setting based on methods from Bayesian experimental design (Neiswanger et al. 202T], and achieves good policies with small numbers of samples; however, this model-based method assumes access to the MDP reward function and is computationally expensive.
An important special case of the MDP setting is the contextual bandit setting. When combined with linear function approximation, this recovers the contextual linear bandit setting (Abbasi- Yadkori ct al., 201T), and contextual Bayesian optimization when using kernel features (Srinivas et al. 2010 Krause & Ong 2011). Various works consider the case where the learner has control over the choice of context during training time. Chaar et al. (2019) propose a variant based on Thompson sampling. Pearce & Branke (2018): |Paaree et al. (2020) also propose variants that leverage ideas from the knowledge gradient (Frazier et al. 2009). The latter works lack theoretical guarantees, while our result (from Section (5) improves upon the sample complexity guarantee of Char al. (2019), The approach by Kirschner et al. (2020) for the distributionally robust setting can be specialized to our setting, in which case they recover similar bounds but only for a fixed context distribution.
7 EXPERIMENTS
7.1 REINFORCEMENT LEARNING EXPERIMENTS
In the previous sections we presented the AE-LSVI algorithm, which provably identifies a near- optimal policy in polynomial time given access a generative model of the MDP dynamics. Here, we test the AE-LSVI algorithm empirically, and additionally provide one of the first empirical evaluation of the LSVI-UCB method from Yang et al. (2020) on standard benchmarks. We evaluate AE-LSVI and LSVI-UCB on four MDPs from the literature as well as four synthetic contextual BO problems from Char et al. (2019). We discuss details of our implementation in Appendix [B.T]
Each environment has a discrete action space. For continuous environments, we discretize the action space into 10 bins per dimension but model the value function in the original continuous state and action space. All methods besides DDQN are initialized by executing random policy for two episodes. In between exploration episodes, the pessimistic policy रy is evaluated by executing it for 10 episodes in the environment.
Initial State Distribution To evaluate the policies found by each method, we must initialize the policy initial states drawn from some distribution po at test time. As AE-LSVI does not explicitly consider the initial state distribution, for each environment we choose both standard po from the lit- erature as well as an alternate distribution pó that is translated in the state space, i.e., ps()) = Po A.) for some A,, The alternate distribution allows us evaluate the best policy estimate in an area of state space that not explicitly given to agents. We evaluate each policy using initial states sampled from P6 as a proxy for understanding how well the optimal policy has been identified in regions of the state space beyond where was initialized. We give a complete description of the various pó for each environment in Appendix B.2 In Table we present results for each method and environment when initialized on Po. which is the typical setup for training and evaluating RL algorithms in the literature. In Table 2 we present results for each method evaluated for the initial state distribution p6-
Comparison Methods Besides AE-LSVI and LSVI-UCB we compare against several abla- tions and methods taken from the literature. As naive baseline for performance in active ex- ploration, we randomly sample state sate-action pairs from the MDP, evaluate the next states and re- wards, and fit Qufuctionss to that data as in the other methods, executing the policy given by the Q Q-function mean (Random). We also perform uncertainty sampling (US) on the Q Q-function, choos- ing state-action pairs at each step that maximize of (:))) as in Eq. (6). Additionally, compare
7

---

Published as a conference paper at ICLR 2023
Environment
AE-LSVI
Random
US
LSVI-UCB
DDQN
BDQN
Greedy
Cartpole
15.2 0.5
13.6 + 0.5
13.6 = 0.6
17.1 0.7
19.3 + 0.7
19.0 0.8
17.2 0.4
Navigation
6.0 1.7
1.4
8.9
12.9 0.2
7.3 1.5
0.9
10.9 + 1.5
3 Tracking
12.7
1..6
11.
131
13.4
0.1
12.9
0.3
3 + Rotation
15.2 0.6
15.1 0.6
0.4
17.
15.1
14.2
17.9
17.9+00 0.1
Table 1: Average Return + standard error of executing the identified best policy on the MDP starting
from Po over 5 seeds after collecting 1000 timesteps of data through the use of generative model (left of line) or episodes starting from Po (right of line).
Environment
AE-LSVI
Random
US
LSVI-UCB
DDQN
BDQN
Greedy
12.9 + 0.3
15.3 + 0.6
16.1 + 0.5
13.3 + 0.5
Cartpole
16.8 + 0.4
12.9
14.5 +.3
(14.2 1 0.6)
(13.71133)
(13.0
(16.7 1 0.2)
Navigation
22.3 + 0.4
15.3 + 0.8
17.5 + 1.3
13.6 1.6
17.1124
21.
15.2 166
(20.6 1.1)
(18.1
(14.0 (1814
13.3
13.810.1
14.0.10.1
12.5 0.4
Tracking
14.0 0.4
9.2 0.9
12.5 0.1
(13.7 1: 0.2)
(13.7:02)
(13.8 (13.7+0..)
10.1 10.1
12.9111
1..7
1.7
6+ Rotation
14.3 +: 0.2
12.8 1.4
13.3 + 0.5
(12.7 1. 0.3)
(13.4.033)
(12.7
(7.5 1..2)
Table 2: Average Return + standard error of executing the identified best policy on the MDP starting from Pó over 5 seeds after collecting 1000 timesteps of data through the use of generative model (left) and online RL methods (right). For online methods, numbers without parentheses refer to training from episodes starting from po, whereas numbers parentheses use the uniform distribution on the state space as initial states during training.
against three online RL baselines: the Double DQN algorithm (Van Hasselt et al. 2016) where an epsilon-greedy approach is used for exploration (DDQN), the bootstrapped DQN (Osband et al.) 2016b) which keeps an ensemble of Q-functions and does exploration acting according to a sam- pled Seed---ffuceioo ffnncttntinn each exploratory rollout (BDQN), and greedy exploration algorithm (Greedy) that chooses arg max, Q% (s, a) at every step h for given state but uses the same value iteration pro- cedure used in the main methods. The experiments are conducted with a default exploration bonus 0.5, however, we also empirically analyze the performance for other 3-values in Appendix [B.3
Environments
We evaluate all methods on four environmente a Cartpole swing-up problem with dense rewards, a nonlinear Navigation problem, and two problems (3 Tracking and / B+ Rotation) in plasma control from Mehta et al. (2022a). in which plasma is driven to desired target state. We give further information on the environments used in Appendix B.2 [.22
Results As our bound on the value function error uses the e (S)mnorm, our method provably finds an approximately optimal policy regardless of the initial distribution. The LSVI-UCB method is able to quickly learn policy for the initial state distribution po given at training time, as it is designed to minimize regret on the episodic MDP initialized at Po- This can be seen clearly in Table D which shows that after 1000 samples, LSVI-UCB performs the best on nearly every environment. In the online setting when the start state distribution is known, greedy and e-greedy methods like DDQN also perform relatively well. We also see in Table I that AE-LSVI does not perform particularly well compared to the online methods given the 1,000-sample budget. This is to be expected, as the online methods naturally collect data that is reachable from po and in particular L. L.VV-UCB is designed to minimize regret on episodes beginning from Po. However, this focus on performing well when starting from po comes the expense of active exploration and identifying the best policy uniformly across the state space.
As shown in Table 2 AB-LSVI outperforms the baselines when evaluated on different initial state distribution pg. even when the online algorithms are initialized from a uniform initial state distri- bution po during training. This is unsurprising, as AE-LSVI is precisely built for this setting and identifies the best action uniformly across the state space, unlike LSVI-UCB which aims to mini- mize regret starting from an initial state distribution. We see that uncertainty sampling outperforms a random data selection strategy and is comparable to the online methods. However, as we discuss above (in Section 3. in general it is the uncertainty in the value of the best action at state and not the uncertainty in the value of a state-action pair that needs to be reduced in order to more efficiently find the best policy. We see that, in general, the online methods perform better on pá when they train on episodes uniformly initialized on the state space. This suggests that in these cases, it is helpful to make sure that the evaluation distribution pó is supported by the training distribution Pn- We also note that (as describe in Appendix B.2 the maximum possible score on Navigation starting from
8

---

Published as a conference paper at ICLR 2023
Branin 1-1
Hartmann 2-2
Hartmann 3-1
Hartmann 4-2
10"
Max Simple Regret
10
10f
10
104
25
100
100
50
400
AE-LSVI
MTS
MEI
TS
RAND
REVI
Figure 1: The maximum simple regret seen in any given context for the offline contextual Bayesian optimization experiments. The shaded regions show the standard error over 10 different seeds.
Po is higher than that from po due to a starting distribution closer to the goal. We believe that these results give empirical support the theoretical claims of Section 4
7.2 OFFLINE CONTEXTUAL BAYESTAN OPTIMIZATION EXPERIMENTS
We test the performance of AE-LSVI (Algorithm 2 in Appendix A.3) in the offline contextual Bayesian optimization setting. In particular, test the algorithm the optimization problems presented in Section 3 of Char et al.] (2019), each having discrete context space but continuous action space. In all experiments, we average over 10 seeds. At the beginning of each experiment, the values corresponding to five actions, chosen uniformly at random, are observed for each context. Every time new data observed, the hyperparameters of the GP are tuned according the marginal likelihood. We leverage the Dragonfly library for these experiments (Kandasamy et al. 2020).
Comparison Methods For baselines, we compare against the Multi-task Thompson Sampling (MTS) method presented by CCaar et al. (2019), which picks context and action based on the largest improvement over what has been seen according to samples from the posterior. addition, we compare to the strategy of picking the context with the greatest expected improvement. This method was presented by Swersky et al. (2013), and we refer to as Multi-task Expected Improvement (MEI,, following Char al. (2019). We also compare against the REVI algorithm (Pearce & Branke 2018), which picks contexts and actions that will increase the posterior mean the most across all contexts. Additionally, we show the performance of naive Thompson sampling (TS) and expected improvement (EI), where contexts are picked a round robin fashion. Lastly, we show the performance of randomly selecting contexts and actions at each time step (RAND).
Experiment Tasks To evaluate the method in the case where the objective function correlated in context space, take higher dimensional function and assign some dimensions to context space and the rest to action space. A single GP with a squared exponential kernel is then used to model the objective function. In particular, the Branin-Hoo (Branin 1972). Hartmann 4, and Hartmann (Picheny et al. 2013) functions are used to create Branin 1-,, Hartmann 2-2, Hartmann 3-1, and Hartmann 4-2, where the first number corresponds the context dimension and the second to the action dimension. These functions have 10, 9, 8, and 16 equispaced contexts, respectively.
Results Figure shows the maximum simple regret seen any given context as a function of t values observed. As seen from these plots, AE-LSVI often is one of the best performing methods. The only task that AE-LSVI struggles on is Hartmann 4-2. We believe that estimating the amount of improvement to be gained at each context is difficult for this benchmark task. This is supported by the fact none of the more sophisticated methods outperforms the baseline that applies El a round-robin fashion. It is likely that improved modeling hyperparameter selection is needed in order for these methods to achieve the highest performance on this task.
CONCLUSION
We provided a new kernelized least-squares value iteration algorithm for RL in the generative model setting, which aims to leam near-optimal policy for all initial states by actively exploring states for which the best action the most uncertain. Our algorithm identifies a near-optimal policy uniformly over the entire state space and attains polynomial sample complexity. Experimentally, we demonstrate that it outperforms other RL algorithms in a variety of environments when robustness to the initial state is required. Perhaps the most immediate direction for future work is to extend the algorithm to the local access model (Yin et al.] (022) in which the simulator can queried only for states that have been encountered in previous simulation steps.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
Johannes Kirschner gratefully acknowledges funding from the SNSF Early Postdoc.Mobility fel- lowship P2E7P2_199781.
Ian Char is supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE1745016 and DGE2140739. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Viraj Mehta was supported in part by US Department of Energy grants under contract numbers DE-SC0021414 and DE-ACO2-09CH1144
Willie Neiswanger was supported in part by NSF (#1651565), AFOSR (FA95501910024), ARO (W911NF-21-100125), CZ. Biohub, and Sloan Fellowship.
In addition, this project has received support from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme grant No. 815943.
REPRODUCIBILITY STATEMENT
The proof of Theorem is provided Appendix A.2 and the proof of Corollary 5.1 is given in Appendix A.3 The supplementary material includes the source code for the experiments. It also includes a requirements file and README with full instructions on how to run the RL and BO experiments. Although we are not allowed to provide the data used for running the 3 Tracking and Rotation experiments this time, all other experiments can be run using the provided code. Lastly, experimental details about the implementation and the environments used can be found in Appendix B.I and Appendix B.2 respectively.
REFERENCES
Yasin Yadkori. Online learning for linearly parametrized control problems. 2012.
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Yasin Abbasi- Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pp. 3602-3702. PMLR, 2019.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. 2019.
Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. Advances in neural information processing systems, 19, 2006.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances neural information processing systems, 21, 2008
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp- 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Rémi Munos, and Bert Kappen. On the sample complexity of rein- forcement learning with generative model. arXiv preprint arXiv:/206.6600 2012.
Richard Bellman, Robert Kalaba, and Bella Kotkin. Polynomial approximation-a new computa- tional technique in dynamic programming: Allocation processes. Mathematics of Computation, 17582),55-161, 1963.
Ilija Bogunovic and Andreas Krause. Misspecified gaussian process bandit optimization. Advances in Neural Information Processing Systems, 34:3004-3015, 2021.
10

---

Published as a conference paper at ICLR 2023
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milmn and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//github. com/ /
Franklin H Branin. Widely convergent method for finding multiple solutions of simultaneous non- linear equations. IBM Journal of Research and Development, 16(5):504-52,, 1972.
Ian Char, Youngseog Chung, Willie Neiswanger, Kirthevasan Kandasamy, Andrew O Nelson, Mark Boyer, Egemen Kolemen, and Jeff Schneider. Offline contextual bayesian optimization. Advances in Neural Information Processing Systems, 32, 2019.
lan Char, Joseph Abbate, Laszo Bardoczi, Mark D. Boyer, Youngseog Chung, Rory Conlin, Keith Erickson, Viraj Mehta, Nathan Richner, Egemen Kolemen, and Jeff Schneider. Offlin model- based reinforcement learning for tokamak control. arXiv preprint, 2022.
Richard Y. Chen, Szymon Sidor, Pieter Abbeel, and John Schulman. UCB and infogain exploration via g-ensembles. CoRR, abs/1706.01502, 2017. URL http://arxxv..ozz//bb////
01502
James Danicl. Splines and efficiency in dynamic programming.. Journal of Maaahheatiicalnnaaaaa and Applications, 54(2):402-405 1976.
Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, et al. Mag- netic control of tokamak plasmas through deep reinforcement learning. Nature, 602(7897):414- 419, 2022.
Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. Kemel-based reinforcement learning: A finite-time analysis. In International Conference on Machine Learning. pp. 2783-2799 PMLR, 2021.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in In International Conference on Machine Learning, pp. 2826-2836. PMLR, 2021.
Simon Shaolei Du, Sham M. Kakade, Ruosong Wang, and Lin F. Yang. Is a good representation sufficient for sample efficient reinforcement learning? International Conference on Learning Representations, 2020.
Adrien Ecoffet, Joost Huizinga. Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 5907744750007 2021.
Dan Foreman-Mackey. Tinygp. 2021. URL htt.lhttps://t hett:s/://iingg..rrahhhccosss
readt io
Peter Frazier, Warren Powell, and Savas Dayanik. The nhowledge-gradient policy for correlated normal beliefs. INFORMS journal on Computing, 21(4):599-613, 2009. 2009..
Victor Gabillon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Sébastien Bubeck. Multi- bandit best arm identification. In J. Shawe-Taylor. R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 24. Curran As- sociates, Inc., 2011. URL htt
nwuz cc//paper/211//11ee
pdf
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91()): 325-349, 2013.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learning, pp. 1861-1870. PMLR, 2018.
Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In ICMI., 2022.
11

---

Published as a conference paper at ICLR 2023
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143 PMLR. 2020.
Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. In Proceedings of the 29th International Coference on Inter- national Conference on Machine Learning, ICML' pp. 227-234, Madison, WI, USA, 2012.
Omnipress. ISBN 9781450312851.
Kirthevasan Kandasamy, Karun Raju Vysyaraju. Willie Neiswanger, Biswajit Paria, Christopher R Collins, Jeff Schneider, Barnabas Poczos, and Eric P Xing. Tuning hyperparameters without grad students: Scalable and robust bayesian optimisation with dragonfly. J. Mach. Learn. Res., 21(81): 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Johannes Kirschner, Ilja Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally ro- bust bayesian optimization. In Silvia Chiappa and Roberto Calandra (eds.). Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 2174-2184. PMLR, 26-28 Aug 2020. URL https::/pprceecinng.. wttp://eessingg.....ee...... wtw.s v 108/ wwtpkkiisscheeeraaaa html.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research,
2013.
Andreas Krause and Cheng Ong. Contextual gaussian process bandit optimization. Advances in neural information processing systems, 24, 2011.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in with generative model. In International Conference Machine Learning, pp- 5662-5670. PMLR, 2020.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint wrXXvv1509.029/99 2015.
Shuang Liu and Hao Su. Provably efficient kernelized q-leanning. arXiv preprint 2022.
Viraj Mehta, Ian Char, Joseph Abbate, Rory Conlin, Mark D Boyer, Stefan Ermon, Jeff Schneider, and Willie Neiswanger. Exploration via planning for information about the optimal trajectory. In Advances in Neural Information Processing Systems, volume 35, 2022a.
Viraj Mehta, Biswajit Paria, Jeff Schneider, Stefano Ermon, and Willie Neiswanger. An experimen- tal design perspective on model-based reinforcement learning. In International Conference on Learning Representations, 2022b.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 112.5:131..5602, 2013.
Willie Neiswanger, Ke Alexander Wang, and Stefano Ermon. Bayesian algorithm execution: Esti- mating computable properties of black-box functions using mutual information. In International Conference on Machine Learning, pp. 8005-8015. PMLR, 2021.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Asso- ciates, Inc., 2016a. URL https: httpttt/ppocceeiiiieee 1 8d881 8c8e1 40 iew.eeeeedddnn...ee............. cencips.ccc/pppp////////111
pdf
12

---

Published as a conference paper at ICLR 2023
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29, 2016b.
Michael Pearce and Juergen Branke. Continuous multi-task bayesian optimisation with correlation. European Journal of Operational Research, 270(3):074--085, 2018.
Michael Pearce, Janis Klaise, and Matthew Groves. Practical bayesian optimization of objectives with conditioning variables. arXiv preprint arXiv:2002.09990 29992090..09 2020.
Victor Picheny, Tobias Wagner, and David Ginsbourger. A benchmark of kriging- kriging-based infill criteria for noisy optimization. Structural and multdisccplinaryy optimization, 48(3):607-626, 2013.
Paul Schweitzer and Abraham Seidmann. Generalized polynomial approximations markovian decision processes. Journal of mathematical analysis and applications, 110(2):568-882 1985.
Jaemin Seo, Y-S Na, B Kim, CY Lee, MS Park, Park, and YH Lee. Feedforward beta control in
the kstar tokamak by deep reinforcement learning. Nuclear Fusion, 61(10):106010, 2021.
Pranav Shyam, Wojciech Jaškowski, and Faustino Gomez. Model-based active exploration. In International conference machine learning, pp. 5788. PMLR, 2019.
Gregor Simm, Robert Pinsler, and José Miguel Hernández-Lobate Reinforcement learning for molecular design guided by quantum mechanics. In International Conference Machine Learn- ing. pp. 8959-8969, PMLR, 2020a.
Gregor NC Simm, Robert Pinsler, Gábor Csányi, and José Miguel Hemúndezz-oobtto. Symmetry- aware actor-critic for 3d molecular design. In International Conference on Learning Representa- tions, 2020b.
Marta Soare, Alessandro Lazaric, and Remi Munos. Best-arm identification in linear ban- dits. 7. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Asso- ciates, Inc., 2014. URL 33572288552cc2233551ccccaaaaaa22
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. International Conference on Machine Learning, 2010.
Kevin Swersky, Jasper Snoek, and Ryan Adams. Multi-task bayesian optimization. Advances in neural information processing systems, 26, 2013.
Csaba Szepesvári. Lecture notes in reinforcement learning theory. Aug 2022. URL https:// catheory.githubee http::/...ttbbb.b../eeeeeeeeeee
m
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the AAAI conference artificial intelligence, volume 30, 2016.
Tingwu Wang, Xuchan Bao, Ignasi Clavera, Jerrick Hoang, Yeming Wen, Eric Langlois, Shunshi Zhang, Guodong Zhang, Pieter Abbeel, and Jimmy Ba. Benchmarking model-based reinforce- 2019.
ment learning. arXiv preprint
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan. On function approx- imation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.04622. 2020.
Dong Yin, Botao Hao. Yasin Abbasi- Yadkori, Nevena Lazić, and Csaba Szepesvári. Efficient local planning with linear function approximation. In International Conference on Algorithmic Learn- ing Theory, pp. 1165-1192. PMLR, 2022.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference Machine Learning, pp. 10978-10989, PMLR, 2020.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532- 4576. PMLR, 2021.
13

---

Published as a conference paper at ICLR 2023
A APPENDIX
A.1 AUXILIARY RESULTS
Lemma A.I. Ler E [T]. Then, for every (s, a) ESxA
1. I (s.a) a) 2 T2 T, a) holds for all E [H]. then (s, 2 (, a) is true for all h E [
2. If I (s,a) a) < T a) holds for all E [H]. then (7 2 (i(8,a) is true for all h E [M].
(8, for all E [H] and / E [T]. We prove vh E [H], (8, 2 (8, by induction on H, H I,... For the initial case h H, we have
Proof. In order to prove part 1., let E S and E A and assume (x,,))) 2 TT
(n)(s,a)
assumption
z
T:
(23)
Det of
(H(8, (x
max Q QH+Ils',a)) La'AA
(24)
= (s)
(25)
(s)
(26)
For the inductive step, we assume that (h+1 S ( a). Then,
= a))
(27)
Def. of (8 a) + Ee
max Qi+ (6', L'Ed 1 (s', a²)
(28)
inductive hypothesis
Th Th(s,a) + (xrwFa(aaa)
max 1
(29)
La'EA
TF Th
(30)
assumption
(s)
(31)
This shows (s, a) 2 (7(s,)) a) for all h E [M] and thus concludes the proof of the first claim. The second part can be shown analogously.
The following a standard result that can be found in multiple works.
Lemma A.2. Consider kernel k X X IR such that k(xxxx) for every X. Then for all E [H] and X 2 we have
Σ ( ah) S / (T.T.
(32)
Proof. We can for example invoke the result of Lemma 3 in Bogunovic & Krause (202)) that in notation reads as:
T
Σ
(sh a &
(33)
for À > Setting 1, we obtain
Σ (hhs (TT.
(34)
14

---

Published as a conference paper at ICLR 2023
A.2 PROOF OF THEOREM 4.2
Let ät be the best-policy estimate returned by the algorithm. Recall the definition of
Trr, for h' = 1,..., for h' . H
T
+2
(35)
The
the policy that equals best-policy estimate ft until step h and then equals the optimal policy n².
We start the proof with the following useful lemma.
Lemma A.3. Let it be best-policy estimute, let E S be an initial state, and let h E [f]. Using
the notation from Eq. (35), we obtain
1
Egg Eoi..... Jollowing
Q7 (hss Q% (sh. (5))())))s=
and V 22++
Proof. To formally prove the lemma, we first explicitly express V," arbitrary initial state 8 E S as
(8) for an
(8)
(36)
E 4y Following my 2 ==
Σ W=1
Tw (skr, an)
(37)
-E following Rt
Eas en en following x lon
The (Sw an)
(38)
H1
E on following fr/s1ms
The (su and + Eag following at 1sn
Σ
The (sh ard
W=1
M=b+1
(39)
and
2h41
(81)
(40)
H Th (sw aw)
E
(41)
o Vollowing ny
=81=8
E Bog... following By =1=0
Bastess following dr drlss
E Bar following x (8h+1
rw rw (swe,, (nss,,an)]] [m]]]
The (sw, (wr) +
E
(42)
M=1
W =1+11
h Th (sn ax²)
E En.... following fry 1i mas
Eas, #1 following frrss.
E Ean. following xe' 18h
Σ
Th an
(43)
W=h+1
Eqs.
37 and
41
use the definition of V/T. Eqs. (38 and (42) the definition of मम and ny
+2
*2h+1
from Eq. 35 and Eqs.
(39 and (43) use the property that integration is a linear operator.
Lemma A.3
then follows from Eqs. 39 and as well as the definition of Oú:
h
(81) - V
(81) = E o following x 181m8
Σ
THe (SN, ax) - Σ Tw (Sw,aw)
15

---

Published as a conference paper at ICLR 2023
H
E E 0o.. ey following xt' 18k
Σ ==++1
Th (w(ssaax)
H
Ennn following len
Bant 1umn following *on+t
The (sw, ax)
(44)
W=++1
= Eag on Sa following Rr|s1=a
2% (5hs (x(3))) - 2% (sh: #II((o))
(45)
We proceed with the proof by using the notation from Eq. 335 We can decompose the instanta- neous regret for an arbitrary initial state 8 E S as follows:
((((2) - V (8) VITH
Vi
(46)
V
(47)
H
Lemme A
E.g a following कo. 1% (sh, (x())) (sh, (r)) 81 = (48)
h=1
The intuition behind Lemma A.3 used in Eq. (48) is as follows. Both Vi (8) and V," 21+1
(s)
refer to the same random trajectory segment (s1, (1......h)) until step h (i.e., the same ini- tial state and policy are used), which is captured as Ee,,es....en following Ro [.]. For the remaining steps h...., H. the policies only differ step h, a property which is captured in the difference Q% ((n) 0% (sh, (rr,
Conditioning on the event in Lemma holding true and by invoking Lemma A.I have that:
Q (s. a) S (7, - (s.aa),
(49)
holds for every h E [H]. t [T]. and (s, a) S x A. Next, we proceed bound Qi (+))))))
(, from Eq. (48) uniformly on S. We have:
Bq. (8) max Li (8. (+))
(1)) (s (x))
(50)
EE(T]
Def. of RT.
(7,s,(7(8)) (s))
max max Q (8, a)
(51)
a tE(T]
-min *E(T]
(07(s,T1))) - max aEA
2 (8, a)
(52)
Def. of mh
min TE
max Q7 max Q (s) aEA
(53)
aEA
Eq
min 1E(T]
max a
O (s, aEA
max
2 a)
(54)
Eq.
min
max a'd
0 (sh a) - max Ω (h(s a))
(55)
LE(T)
aEd
Eq.
min LE|2
(hhh, af)) - 2i of))
(56)
(sh aft) (hish, di)).
(57)
16

---

Published as a conference paper at ICLR 2023
Next, for convenience introduce the notation df := (1h (sh, df.) 17 dh)) + - oh)).
(58)
and obtain the following upper bound on (h a/) - Qh(s% ag)) (from Eq. (57) for every h [H].E [T]:
(81 (/)) -2h al))
Eq. 58
dr.
T
-
(59)
Det. TR
dr + Barona(tssaa
max aEd
2h+ (6',
max
Qh+1
(8'
aEA
(60)
S df + max ''ES
max
1n++1s',aa
-max Qi (s'
(61)
BEA
BEA
di + max Q (sh+41, TEA
max 2i++ (8h+11.))
(62)
2E.A
dx +
(Qh4i dh+1)
(63)
Using the definition of Qi+1 and TH41 as the zero functions, can unroll the recursive inequality
from Eq. (63) and upper bound Q%,(s, (5h o/) - 2i (0/2 ai) for every h E [H], E [7'] as follows:
(hh at) - (h ah) S
Σ
dz..
(64)
k/=h
(sh, ah)) - (sh,
(65)
H1
The (m + (hess (hh) (s/w
h'=h
(66)
Lemma
(she df.).
(67)
h'=h
By substituting the bound from Eq. 667 in Eq. 57 and then in Eq.
48
we arrive at:
ViT(6) - (5) 48
Σ
oh ( al)) < 22333( 1) (a(TA
(68)
-=1W=h
where the last inequality follows from Lemma A.2 our main result:
Since Eq. 668 holds for any S, arrive
VVV - V2fT [ee-()) S 2V38H(H 1) (T.))
(69)
A.3 OFFLINE CONTEXTUAL BAYESIAN OPTIMIZATION
Algorithm 2 AE-LSVI for offline contextual Bayesian optimization
Require: kernel function k(-,-), exploration parameter 3 > 0, regularization parameter X,
1: for t = =,...,, do
2: Obtain Q' and Q¹ from Equation (0
3: Choose s aarg max,es
max Q (s, max (s)
4: Choose a' E arg max Q'(s' (st,
5: Observe the reward 1/: = Q''s", at) + 7t
6: end for
7: Output the policy estimate #ं such that (.(+)) = arg max, EA maX (s(s.
17

---

Published as a conference paper at ICLR 2023
Our algorithm for the offline contextual Bayesian optimization is presented in Algorithm 2 As a side observation, we note that similarly to Char et al. (2019), we can also simply incorporate context weights (i.c., given (s)s that represents some weighting of context that may depend on the probability of seeing at evaluation time or the importance of s), in case they are available, into the proposed acquisition function, i.e.,
8² E arg max #ES
max (s,a) - max Q'(ss ()sss)))o(s)) aEA
(70)
AEA
A.3.1 PROOF OF COROLLARY 5.1
Proof. In this proof, we condition on the event in Eq. 21 holding true. Similar arguments to the ones Eq. (59 Eq. (63 lead to the following for every 8 E S:
max (8) - Q' (s))) aEA
max
Q''QQ''"(''''' (8(8))
max (T(s))
(71)
1E[T]
&
max (s
max max (()s
(72)
aEA
aEA 1E[T)
min [E
max (s) max (ss.
(73)
aEA
acA
Eq
min (E(T)
max Q (s, aEA
max aEA
Q((s
(74)
Def. of
S
min
max Q' (5),a)= - max
('(s'
(75)
AE[T]
a
aed
Def. af
S
min
(s's"'a ('())aa²)
(76)
TE
Q (s',aaa)) (s(s",aa))
(77)
Bq. 20
23300 23,00 (st
(78)
2,T T <
o² "'s (ss,aa))
(79)
T
Lemma
28r
(T.))
(80)
28T V (T,A) VT
Finally, by setting
and expressing it in terms of T, we arrive at the main result.
B ADDITIONAL EXPERIMENTAL DETAILS
B.1 IMPLEMENTATION
We use an exact Gaussian Process with a squared exponential kernel with learned scale parameters in each dimension for the value function regression in Eq. ( We fit the kernel hyperparameters at each iteration using 1000 iterations of Adam (Kingma & Ba 2014), maximizing the marginal log likelihood of the training data. We used the TinyGP package (Foreman-Mackey) (021 built on top of JAX (Bradbury et al. 2018) in order to take advantage of JIT compilation. All experiments conducted with fixed bonus Appendix|B.3 We uniformly sample 1,000 points from the state space and evaluate them to find an approximate maximizer to the objective in Eq. 11
0.5. We have empirically evaluated various settings of B in
18

---

Published as a conference paper at ICLR 2023
DDQN and BDQN. For both of these methods 256 units. For the bootstrapped DQN, we use a network with 10 different heads, each representing a different function. For each step collected during exploration, corresponding mask is generated and added to the replay buffer that signifies which heads will train on this sample. Fach Q function has probability of 0.5 of being trained on each transition.
networks with two hidden layers, each with
B.2 ENVIRONMENTS
Each environment is defined with a native reward function taken from the literature. We established upper and lower bounds the reward function value and used them to scale the reward function values to [0, 1] so that our environments would match the theoretical results in this paper.
Cartpole We use a modified version of the cartpole environment from Mehta et al. (2022a) that has dense rewards as implemented in Wang et al. (2019). The state space is 4/ and consists of the horizontal position and velocity of the cart as well as the angular position and velocity of the pole. Po in this environment is a normal distribution centered with the cart below the goal horizontally with the pole hanging down with very small variance. Pb is the same distribution displaced 5 meters to the right.
Navigation
This is a 2D navigation problem with dynamics of the form s + B(s))a
sin (22 /1) + 4
0
where Btt)= =
co5 (10) -2 The goal is fixed at We define po to
0
be the uniform distribution over the axis-aligned rectangle given by corners
and
We
define pó to be the uniform distribution over the axis-aligned rectangle given by corners
and
The reward function at every timestep is simply the negative Eddisttncce between the agent and the goal.
Tracking and + Rotation Our two simulated plasma control problems are taken from Mehta let al. (2022a), which gives thorough description of their relevance to the problem of nuclear fusion. At a high level, By is a normalized plasma pressure ratio that correlated with the economic output of fusion reactor. Our 3 Tracking environment aims to adjust the injected power in the reactions in order to achieve a target value of AN = 2%. The initial state distribution Pu is taken from a set of real datapoints from shots the DIII-D tokamak in San Diego. Our alternate initial state distribution 16 consists of simply adding 0.4 to each component of a vector sampled from Po- The reward function is the negative -ddistancce between the By value and 2%. The dynamies given by a learned model of the plasma state as introduced in Char et al. (2022).
The B Rotation environment is more complex plasma control problem, introducing an additional actuator (injected torque) and an additional control objective (controlling plasma rotation). Control of plasma rotation is key to plasma stability and this is a reduced version of the realistic problem. This environment also uses a model from Char et al. (2022) for the dynamics, real plasma states for the initial state distribution po, and a fixed translation for the alternate initial state distribution ph- We also include randomly drawn target for 3& and rotation in the state space for every episode.
B.3 EXPLORING 3 VALUES
In the main paper, we report experiments with the exploration parameter 3 = 0.5 for all In this work, we do not explore principled methods of choosing 3 and welcome future work in the area. In lieu of this, we provide an empirical analysis of the sensitivity of AE-LSVI to varying settings of B. We ran the AE-LSVI method in Table 2 where we allowed each method to collect 1,000 timesteps of data and evaluated the identified policies on the environments starting from evaluation initial distribution Pó distinct from the initial distribution Po- In Table we observe that lower values of 3 perform better because the confidence bounds seem too wide at higher settings, where the performance becomes similar that
evaluation environments as in the experiments
19

---

Published as a conference paper at ICLR 2023
Environment
8= 0.25
3
8=1
3=
Cartpole
17.2
16.8 0.4
16.3 0.5
15.1 0.4
Navigation
22.3 0.5
22.3
1 0.4
22.2 1.4
20.6
Tracking
13.9+000
14.0 0.4
13.2
1.74
3 + Rotation
1.3
0.2
1.9
1.9
Table 3: Average Return + standard error of executing the identified best policy on the MDP starting from pá over 5 seeds after collecting 1000 timesteps of data using the AE-LSVI method with varying values of the exploration parameter 3.
of uncertainty sampling. Therefore, we recommend initially trying 3-values around 0.2 - 0.5 when applying AE-LSVI.
20


Reviews:
[{"review_id": "xfqhxHY01Wg", "reviewer": "Reviewer_v5Ka", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper presents a novel algorithm, based on LSVI to perform best-policy identification uniformly across the state space. The method is based on a RHKS assumption on the reward and value functions and performs targeted 'exploration' based on the performance gaps defined as the difference between upper and lower bounds of the action value function. The authors study theoretically the performance of the algorithm in function of $\\Gamma_k$, a property of the specific kernels used and give specific bounds for some families of frequently used kernels. Moreover, the authors perform an empirical evaluation on several domains, comparing AE-LSVI with algorithms from SOTA, explicitly showing the conditions under which this method outperforms the baselines.", "summary_of_the_review": "Overall I am positive about the paper. The issues I describe all all fairly minor and solvable. I would increase my score if my concerns are adequately addressed. (See previous sections for details)", "strength_and_weaknesses": "Strengths:\n - The authors study the interesting problem of best policy identification in episodic reinforcement learning\n - The authors propose a fairly simple algorithm, easy to implement and with performance guarantees\n - The sample complexity bound does not scale with the state and action space sizes\n - The authors perform a thorough empirical evaluation explicitly identifying the limitations of the algorithms and the settings in which it performs better than the baselines\n\nWeaknesses:\n- The central point of the algorithm is choosing states to sample from he generative model based on the perfomance gap, i.e. the difference between the upper and lower bounds on the V-function of the state. The authors should  cite other works that performs selection on similar metrics based on this uncertainty. For example, there is a large body of work in the best-arm identification literature that uses the difference between upper and lower bounds to select which arm to choose, [1], [2] etc.\n- The paper does use a fairly common assumption from the literature, but nonetheless it should be more self contained. I would have expected to see a discussion on how restrictive is the RHKS assumption as well as a comparison of the guarantees provided non only with methods taking the same assumption but also with other method that make less or more limiting assumptions. For example, a comparison with methods that assume linearity of the reward and value functions would improve the clarity of the paper. \n- A bit more discussion on why the bound presented loses the dependency on the state and action space sizes might also improve the paper.  Especially when comparing with the algorithm presented in Cher et. al. 2019 at the end of Section 4 which also makes the RHKS assumption, has a dependency on $\\Gamma_k$ but also on the state and action spaces.\n- The algorithms adds an additional parameter $\\beta_t$, fairly important since it is used to define the upper and lower bound on Q-values, central for the \"exploration\" method used in AE-LSVI. Unfortunately, no discussion on the selection of this hyperparameter is provided. The authors present all the results with the value 0.5 (why 0.5). Instead, an empirical evaluation of the effect off the value of $\\beta_t$ is warranted.\n- While I am mostly positive on the experimental section, I am surprised with the choice of DDQN as a baseline. DDQN was chosen as a SOTA method for online RL, but there are more advanced methods right now for online RL, especially it would have been beneficial to see other online RL methods that use uncertainty estimates just like AE-LSVI like [3] [4] or [5]. Any of them would make a better baseline then DDQN but especially [3] since it makes decisions also based on upper and lower bounds on Q.\n\n[1] Victor Gabillon, Mohammad Ghavamzadeh, Alessandro Lazaric, Sébastien Bubeck, Multi-Bandit Best Arm Identification, NeurIPS 2022\n\n[2] Marta Soare, Alessandro Lazaric, Rémi Munos, Best-Arm Identification in Linear Bandits, NeurIPS 2014\n\n[3] Ted Moskovitz, Jack Parker-Holder, Aldo Pacchiano, Michael Arbel, Michael I. Jordan, Tactical Optimism and Pessimism for Deep Reinforcement Learning\n\n[4] Ian Osband, Charles Blundell, Alexander Pritzel, Benjamin Van Roy, Deep Exploration via Bootstrapped DQN\n\n[5] Alberto Maria Metelli, Amarildo Likmeta, Marcello Restelli, Propagating Uncertainty in Reinforcement Learning via Wasserstein Barycenters\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "j_NFWKxf5b", "reviewer": "Reviewer_Zsrd", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is concerned with near-optimal policy identification in the generative model setting. The contributions of this paper includes:\n\n(1) The development of the AE-LSVI algorithm for $\\epsilon$-optimal identification;\n(2) A concrete proposal of the algorithm based on the RKHS model;\n(3) Establishment of the theoretical findings to justify the proposed algorithm;\n(4) Empirical verification of the proposed algorithm. ", "summary_of_the_review": "The paper is well-written and studies an interesting research question. The proposed algorithm and the theoretical analysis are novel. I have some comments regarding the practical usage of the proposed method and the model setup. I hope the author(s) can address my concerns. ", "strength_and_weaknesses": "The contributions and strengths of paper are listed above. Below, I list some points to discuss: \n\n1. Page 3. It was mentioned that the goal in this setting is to identify an $\\epsilon$-optimal policy while minimizing the number of necessary episodes $T$. This differs from the standard setting on cumulative regret minimization. The paper would benefit from adding more motivations to justify such an objective. Is this objective commonly used in the generative model setting?\n\n2. Under the generative model setting, the agent has access to a simulator that can be used for adaptive data generation. The optimal policy that maximizes the cumulative reward in simulators is not necessarily maximizing that in real applications, due to potential difference from simulator and real-world environments. Would it be better to consider the more realistic setting with sim-to-real gap?\n\n3. Instead of obtaining $s_h^t$ according to Equation (12), we can alternatively define some uncertainty measure for the value and directly selects $s_h^t$ that minimizes the uncertainty. Would this procedure work?\n\n4. While kernel methods enjoy nice theoretical properties, their empirical implementation requires tuning of the kernel bandwidth. What kernel functions did you choose in the numerical experiments? Are the results sensitive to the choice of the bandwidth? How would you suggest practioners to select this hyper-parameter? \n\n5. In continuous action setting, the author(s) proposed to first discretize the action space and then apply the proposed method. Can your methodology be extended to the continuous action setting? Alternatively, can we adaptively discretize the action space to improve the performance (see e.g., http://proceedings.mlr.press/v80/lee18b/lee18b.pdf; https://arxiv.org/pdf/2007.00717.pdf; https://openreview.net/pdf?id=rvKD3iqtBdk)? \n\n6. The current methodology and theory are developed under the episodic MDP setting with time-varying dynamics. Can these results be extended to time-homogeneous MDP models?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Dbxtl5Pc_g", "reviewer": "Reviewer_maWK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper introduces a policy search algorithm that combines kernelized LSTD with the \"optimism in the face of uncertainty\" approach, which is a well-known method in bandit algorithms. The paper analyzes the theoretical properties of the resulting algorithm and reports results on a number of simulated control environments.", "summary_of_the_review": "Overall very solid work, which neatly combines the theory and practice of online policy search.", "strength_and_weaknesses": "Strengths:\n   - Despite being a combination of multi-decade-old ideas, the eventual algorithm is simple, solid, and novel.\n   - The theoretical results are thorough and sufficiently informative, while being a corollary of existing work.\n   - The experiments are comprehensive enough and the reported results support the central claim of the paper.\n\nWeaknesses:\n   - The baselines chosen for comparison are rather arbitrary and not state-of-the-art.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%