Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration $\&$ Planning
Authors: Reda Ouhamma
Debabrota Basu
Odalric-Ambrym Maillard
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Reinforcement learning
bilinear MDP
frequentist regret
tractable optimism

Abstract: We study the problem of episodic reinforcement learning in continuous state-action spaces with unknown rewards and transitions. Specifically, we consider the setting where the rewards and transitions are modeled using parametric bilinear exponential families. We propose an algorithm, $\texttt{BEF-RLSVI}$, that a) uses penalized maximum likelihood estimators to learn the unknown parameters, b) injects a calibrated Gaussian noise in the parameter of rewards to ensure exploration, and c) leverages linearity of the exponential family with respect to an underlying RKHS to perform tractable planning. We further provide a frequentist regret analysis of $\texttt{BEF-RLSVI}$ that yields an upper bound of $\tilde{\mathcal{O}}(\sqrt{d^3H^3K})$, where $d$ is the dimension of the parameters, $H$ is the episode length, and $K$ is the number of episodes. Our analysis improves the existing bounds for the bilinear exponential family of MDPs by $\sqrt{H}$ and removes the handcrafted clipping deployed in existing $\texttt{RLSVI}$-type algorithms. Our regret bound is order-optimal with respect to $H$ and $K$.

Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration & Planning
Anonymous Author(s)
Affiliation
Address
email
Abstract
We study the problem of episodic reinforcement learning in continuous state- action spaces with unknown rewards and transitions. Specifically, we consider the setting where the rewards and transitions are modeled using parametric bilinear exponential families, We propose an algorithm, BEF-RLSVI, that a) uses penalized maximum likelihood estimators to learn the unknown parameters, b) injects a calibrated Gaussian noise in the parameter of rewards to ensure exploration, and c) leverages linearity of the exponential family with respect an underlying RKHS to perform tractable planning. We further provide a frequentist regret analysis of BES-RLSVI that yields an upper bound of OOVd@HHH H)), where d is the dimension of the parameters, is the episode length, and K is the number of episodes. Our analysis improves the existing bounds for the bilinear exponential family of MDPs by VH and removes the handcrafted clipping deployed in existing RLSVI-type algorithms. Our regret bound order-optimal with respect to H and K.
2
10
11
13
Introduction
15 Reinforcement Learning (RL) is a well-studied and popular framework for sequential decision making, where agent aims compute a policy that allows her to maximize the accumulated reward horizon by interacting with an unknown environment (SB18).
17
Episodic RL. In this paper, we consider the episodic finite-horizon MDP formulation of RL, in short 19 Episodic RL [ORVR[3] DLBIZ). Episodic RL is a tuple M = (S, A, I., r, K, H), where the state (resp. action) space S (resp. A) might be continuous. In episodic RL, the agent interacts 21 with the environment in episodes consisting of steps. Episode starts by observing state s Then,
22 for = 1,... H, the agent draws action af from a (possibly time-dependent) policy Te (s())), observes
23 the reward rsst at) E [0, 1], and transits to a state s P(. af)) according to the transition
24 function IP. The performance of a policy π is measured by the total expected reward 1/T starting from
25 a state s E S. the value function and the itate-action value functions at step h E [H] are defined
H
H
E
Σ
r(st, az) sh
and ()
Σ
ssh =3, s, r(st,
Here, computing the policy leading to maximization of cumulative reward requires the agent to strategically control the actions in order to learn the transition functions and reward functions as precisely as required. This tension between learning the unknown environment and reward maximization is quantified as regret: the typical performance measure of an episodic RI algorithm. Regret defined as the difference between the expected cumulative reward or value collected by the optimal agent that knows the environment and the expected cumulative reward or value obtained by
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

an agent that has to learn about the unknown environment. Formally, the regret over K episodes is
K VT (st) - (o4)).
R(K)- A
Key Challenges. The first key challenge in episodic RL is to tackle the apploratioo-eeploiaattie trade- 27 off. This is traditionally addressed with the optimism principle that either carefully crafts optimistic maintains a posterior 28 upper bounds the value (or state-action value) functions [AOMI7],
29 on the parameters to perform posterior sampling [ORVRI3) or perturbs the value (or state-action value) function estimates with calibrated noise [OVRW16]. Though the first two approaches induce theoretically optimal exploration, they might not yield tractable algorithms for large/continuous state-action spaces as they either involve optimization in the optimistic set or maintaining high- dimensional posterior. Thus, we focus on extending the third approach of Randomized Least-Square Value Iteration (RLSVI) framework, and inject noise only in rewards to perform tractable exploration.
30
31
32
33
34
35
The second challenge, which emerges for continuous state-action spaces, is to learn a parametric functional approximation of either the value function or the rewards and transitions in order to perform planning and exploration. Different functional representations (or models), such as linear (JW220), bilinear 21L and bilinear exponential families [CGM21] optimal algorithms for episodic RL with continuous state-action spaces. Since the linear assumption is restrictive in real-life -where non-linear structures are abundant-, generalized representations have obtained more attention recently [CGM21 LLS DKL FKQR2I). The bilinear exponential family model is of special interest as it is expressive enough represent tabular MDPs (discrete state-action), factored MDPs [K99), linear MDPs [YW120) linearly controlled dynamical systems (such as Linear Quadratic Regulators (AYSTI) as special cases [CGM2T] Thus, in this paper, we study the bilinear exponential family of MDPs, i.e. the episodic RL setting where the rewards and transition functions can be modelled with bilinear exponential families.
37
38
studied in literature to develop
39
40
41
42
43
44
45
46
47
The third challenge is to perform tractable planning given the perturbation for exploration and the model class. Existing work [OVR14 [CGM21 assumes oracle to perform planning and yield policies that aren't explicit. The main difficulty in such planning approaches is that dynamic programming requires calculating f P(ss' | V. for all (s, a) pairs. This is not trivial unless the transition is assumed to be linear and decouples s' from (s, a), which is not known to hold except for tabular MDPs. Much ink has been spilled about this challenge recently, e.g. (DKWY19) asks when misspecified linear representations are enough for polynomial sample complexity in several settings.
49
50
51
52
53
54
SS20 LSW20 VRD19 provide positive answers for specific linear settings. In this paper, we aim to address this issue by designing a tractable planner for the bilinear exponential family representation.
55
56
In this paper, we aim address the following question that encompasses the three challenges:
Can design an algorithm that performs tractable exploration and planning for bilinear exponential family of MDPs yielding a near-optimal frequentist regret bound?
58
59
Our Contributions. Our contributions to this question are three-fold.
80 1. Formalism: We assume that neither rewards nor transitions are known, whereas existing efforts on the bilinear exponential family of MDPs assume knowledge of rewards. This makes the addressed problem harder, practical, and more general. We also observe that though the transition model can represent non-linear dynamics, it implies linear behavior (see Section 2 in a Reproducible Kernel Hilbert Space (RKHS). This observation contributes to the tractability of planning.
61
62
63
64
85
2. Algorithm: We propose an algorithm BEF-RLSVI that extends the RLSVI framework to bilinear exponential families (see Section Bp. BEF-RLSVI a) injects calibrated Gaussian noise in the rewards
66
87 to perform exploration, b) leverages the linearity of the transition model with respect to an underlying
88 RKHS to perform tractable planning and c) uses penalized maximum likelihood estimators to
89 learn the parameters corresponding to rewards and transitions (see Section 4). To the best of our
70
knowledge, BEF- REF-RLSVITE is the first algorithm for the bilinear exponential family of MDPs with tractable exploration and planning under unknown rewards and transitions.
71
By tractable planning. we mean having a planner with (pseudo-)polyy Jpolyoomal complexity in the problem parameters, ie. dimension of parameters, dimension of features, horizon, and number of episodes.

---

Table 1: A comparison of RL Algorithms for continuous state-actions with functional representations.
Algo
Regret
Tractable exploration
Tractable planning
Free of clipping
Model, assumptions
Thompson sampling
V (Bayesian)
X
N.A
Gaussian P Known rewards
RZSD21
LSVI-PER
V
Generalized approx Tabular, anti-concentration
2I
(Freq.)
OPT-RLSVI [ZBB+20
V (Freq.)
X
Linear V
EXP-UCRL [CGM21]
x
X
N.A
Bilinear Exp family known rewards
(Freq.)
BEF-RLSVI
V
Bilinear Exp family
This work
(Freq.)
72 3. Analysis: We carefully develop an analysis of BEF-RLSVI that yields Ö H3K) regret which improves the existing regret bound for bilinear exponential family of MDPs with known reward by
73
74 a factor of /H (Section 3.2). Our analysis (Section 5) builds on existing analyses of RLSVI-type algorithms [OVRW16], but contrary to them,
75
remove the need handcraft a clipping of the value functions (ZBB 20). We also do not need to assume anti motteioncentttioon bounds as we can explicitly control by the injected noise. This was not done previously except for the linear MDPs.
76
77
78 We illustrate this comparison in Table We highlight three technical tools that we used to improve
79 the previous analyses: 1) Using transportation inequalities instead of the simulation lemma reduces
80 H factor compared to [RZSD21] 2) Leveraging the observation that true value functions are
81 bounded enables using an improved elliptical lemma (compared to (CGM21)) and 3) Noticing that
82 the norm features can only be large for a finite amount time allows us to forgo clipping and
83 reduce vd factor from the regret compared to [ZBB+20
84 2 Bilinear exponential family of MDPs
85 In this section, we introduce the bilinear exponential family model coined in [CGM21 and extend parametric rewards. Then, state novel observation about linearity of this representation.
86
87 Bilinear exponential family model. We consider both transition and reward kernels to be unknown 88 and modeled with bilinear exponential families. Specifically,
P (3 a) exp (v²3) Merp(s, a) ZT, (oP)
(1)
(r s, a) exp (r BT Marip(s,) - (0))
(2)
89 where & E (SA and & (RL)) are known feature functions, and B E Rd is a known scaling
90 factor. The unknown reward and transition parameters are . E Rd.. Mg. def E U,A,, where
91 A; is known p x q matrix for each i. Finally, Z denotes the log partition function:
(0P) def log ! /eepp (3)) T Mgx (ss a)) dē,
92 Zr is defined similarly. We denote V "or.or.n- respectively Q o h the value, respectively state-action
93 value function for policy in the MDP parameterized by (0P, OF) at time h. A policy x² is optimal if
max V (s). A learning algorithm minimizes the (pseudo-)regret defined 94 for all s E S, V xell
95 as:
K
R(K)& A Σ Voii -vi))
96 Linearity of transitions. Now, we state an observation about the bilinear exponential family and discuss how it helps with the challenge of planning in episodic RL. Specifically, the popular 38 assumption of linearity of the transition kernel is a direct consequence of our model. Indeed,
246 (5') as a) - -I(()(s') M Il + 12) + ||Me a)ll².
3

---

99
Notice that the quadratic term resembles the Radial Basis Function (RBF) kernel. More precisely, for an RBF kernel with covariance Σ= Ip and k( y) def
exp (-1 - /2), we find
100
PP (s' 8, a) = (0) a), (c (+:
(4)
n/2 & (1)(s').. exp (Ilu (s') IP2/2). where 7/ is the RKHS associated with the kernel, (s') (2m)-~/2
101
and o² (s, a) k (M (oss, a)..) exp (olMorp(ss a) 22 (..a((P)) Equation 4 shows that s' is decoupled from as,a), we see hereafter why this is crucial to reducing the complexity of planning. Remark. Up to our knowledge, ARZSD2IJ is the only work providing an example of linear transition kernel for RL with continuous state- acte-action spaces. They consider Gaussian transitions with an unknown mean (f" (s, a)) and known variance (a²). Actually, linear f is special case the bilinear exponential family model, where (b(s) (1=1()) and Mas((,, a) (fo(s, a)/o² -1/o²))
104
105
106
Importance of linearity. To understand the planning challenge in RL., recall the Bellman equation:
(s, r(s.a) + [ P(s' s.
We must approximate the integral at the R.H.S.for (s, E x A. For tabular MDP with |S| states 110 and |A| actions, we need to evaluate (QW)am i.. to approximate |S] x |A| x H integrals per episode, which can be very expensive. However, if the transition model is linear (Equation 4h) then
(s. r(s + ((00)++(Ppss0000 a), / 1P( (3)d3
When MP IR, obtain Qa & h by computing integrals per timestep, reducing the 113 state-action space complexity to r only. For our model, although &P and μP are infinite dimensional, show in Section|4 planning) that the planning complexity is still significantly reduced.
3 -EF-ILSVI: algorithm design and frequentist regret bound
116 In this section, we formally introduce the Bilinear Exponential Family Randomized easttSquares Value Iteration (EEF-LLVVI) algorithm along with a high probability upper-hound on its regret.
117
118
3.1
BEF-R:SVI: algorithm design
BEF-RIE RLSVI is based on RLSVI [OVRW16) framework with the distinction that only perturb the reward parameters and not all the parameters of the value function. RLSVI algorithms are reminiscent of Thompson Sampling, yet tractable with better control over the probability be optimistic.
120
Algorithm BEF-RLSVI
1: Input: failure rate 5, constants aP, and (IK)KE(K) E
2: for episode h = 1, ......dd do
3: Observe initial state sf
4: Sample noise &L N (0, TR GP) -1) such that
GP OF A k- E T AT Asp(s), a au)44
5: Perturb reward parameter: 0' (k) &
6: Compute (Q) @r. heEE via Bellman-backtrackingg
Algorithm
7:
for h = I....,,H H. do
(sf,.a a) 8: Pull action a arg max, Qb n. (sh
9: Observe reward rss at))) and state shi-1-
10: end for
11: Update the penalized MI. estimators OP (k)), 80 (k)), see Equation (6) and Equation
12:
end for
We can see that Algorithm performs exploration by Gaussian perturbation of the reward parameter
123 (Line 4.. Contrary optimistic approaches, this method is explicit and also more efficient since does not involve high-dimensional optimization.

---

Algorithm 2 Bellman Backtracking
1: Input Parameters (P, (=.. initialize 0 (Ø=, (e) and Vs, Vn++1 (8) = 0
2: for steps h = - H. 2, do
3: Calculate Q8 = E [ + ( a), V0,+1 (sP(s)
4: end for
125 We can approximate Line of Algorithm 2 with O(pH / K log(HK)) complexity and without
128 harming the learning process (cf. planning, Section 4 Therefore, here, planning is tractable.
127
3.2
BEF-RLSVI: regret upper-bound
We state the standard smoothness assumptions the model [CGM21 JBNWI7 LMT21).
129
Assumption There exist constants a², a²,a" o", "", > O, such that the representation model satisfies:
((s,a) E S x x a s C2 S B"
V(s ES X,
a Var (r() x B B 3
where Co [&b (s') A E Eg-ralaa
vs (s') B.sBols s,a 1 BarnBolsso (s') and
130
131
Var ( (r) A (Eg,a [r-]] Eº [r]²
is the variance of the reward under 0.
132
A closer look at the derivatives of the model (see Appendix D.3) tells us that previous inequalities directly imply a control over the eigenvalues of the Hessian matrices of the nog-normalizers.
133
134
We now state our main result, the regret upper-bound of BEF -RLSI..
Theorem 2 (Regret bound). Let & & (tr(A;A)) (tr(A,A)))ssE(( and G. - (p(s, T AT Azp(s, a))
135
Under Assumption [ and further considering that
138
|, [|a] S BR, | S Ba, and Eerlr(s, [0, for all (8, a).
137
noise & (0, (G)) satisfies xx 2 [HV] (P v (BTg((K(6) min(1, g
2.
x dHH
139
then for all E (0, 1). with probability at least 76,
288 Br OP(K 8K, + V log(1 (1)2)
(m,,0)7
R(K)= S VKH
2H
V az
+ Br
20"
Reward concentration d
concentration
+ cgr Vo log(dK/8) 3 VV dx log( log(e/02)
/og(d/8))
(--1)
Noise concentration da/2
PrCo (V8TKR: 20" okd
H
Estimation error for no clipping Re dH
3rd gdd/ (1+ (log(o/))) Ca (1+ ar aT
+ (-1)
Learning ervor for no clipping na (d1f)38/2
8' "n B.,.KK.. Also, where for i E [p, r), (8((K()) 5) B 7/ + log(1/8), and 7/k dlog(1 +
140
a "1'|A B3 P3
141
C4
3d [2]
log
+
(2))
+ is the Gaussian CDF, and e is universal constant.
Theorem entails a regret R(K)= = O(VPH3K) for BEF-RLSVI, where d is the number of parameters of the bilinear exponential family model, K the number of episodes, and H is the horizon of an episode. We now clarify how this contrasts with related literature.
143
5

---

145
Comparison with Other Bounds. The closest work to ours is [CGM21 as it considers the same model for transitions but with known rewards. They propose a UCRL-type and PSRL-type algorithm. which achieve a regret of order O(Vd(H+K) There are two notable algorithmic differences with work. First, they do exploration using intractable-optimiste upper bounds high- lishdiimensional posteriors, while we do it with explicit perturbation. The second difference is in planning. While planning oracle, do it explicitly with pseudo-poly polynomial complexity
148
147
149
they assume access (Section 4p. Moreover, we improve the regret bound by v H factor thanks to improved analysis, (cf. Lemma 18 But similar to all RLSVI-type algorithms, we pick up extra vd (cf. (AL17).
BBB 20] proposes a variant of RLSVI for continuous state-action spaces, where there are low-rank 153
models of transitions and rewards. They show a regret bound R(K) = ((Vd'((K)) which is larger than that of BEF-RLSVI by O(v In algorithm design, we improve on their work by removing the need to carefully clip the value function. Analytically, our model allows us use transportation 13) instead of the simulation lemma, which saves us v H factor.
154
155
156
157
inequalities (cf. Lemma
158
considers Gaussian transitions, i.e. s' = f", a) + c such that c ~ N o0, This is a particular case of our model. They propose to use Thompson Sampling. and have the merit of being the first to have observed linearity of the value function from this transition structure. But they do not connect it to the finite dimensional approximation of [RR07 unlike (Section 4 Finally, they show
RZSD21
160
161
Bayesian regret bound of D( This notion of regret weaker than frequentist regret,
162
183
hence this result is not directly comparable with Theorem 2
Tightness of Regret Bound. A lower bound for episodic RL with continuous state-action spaces is still missing. However, for tabular RL, (DKV211) proves lower bound of order S2 ((VH35AA)) If we represent a tabular MDP in our model, we would need d = 52 x A parameters (Section 4.3, (GM21)). In this case, our bound becomes R(K) O / (S A H)²H which is clearly not tight S and A. This is understandable due to the relative generality of our setting. We however positively surprised that our bound is tight in terms of its dependence on H and K.
165
186
187
188
189
170
4
Algorithm design: building blocks of BEF-RLSV
171
We present necessary details about BEF-RO -RF-RLSVI and discuss the key algorithm design techniques.
172
Estimation of parameters. We estimate transitions and rewards from observations similar to EXP-UCRL (CGM21), iee. by using penalized maximum likelihood estimator
H
0P (k) E arg min
log Po (sh+1 I sh of. + pen()))
BERd
174 Here, pon(O) is a trace-norm penalty: pen(O) 1 and A (tr(A:A,))s By properties of the exponential family, the penalized maximum likelihood estimator verifies, for all i S d:
175
H
4/ (sh+1)
-E F. ( (()))
App (sh. a%) = v, pen 0P
(6)
h=1
176
can be solved in closed form for simple distributions, like Gaussian, but it can involve integral approximations for other distribution. We estimate the parameter for reward, i.e. 0,, similarly
Equation 6
177
H
Or (k) E arg min
log Po (ra sh, af)) + 1) pen(O),
BERd
Famm
Pr
E. a (rl)
B Anp (sh, af) = v,, pen 0h
Vi [d].
(8)
178 Exploration. A significant challenge in RL is handling exploration in continuous spaces. The majority
179 of the literature split between intractable, upper confidence bound-style optimism or Thompson sampling algorithms with high-dimensional posterior and guarantees only in terms of Bayesian regret. BEF -LSVI, we adopt the approach of reward perturbation motivated by the RLSVI- We show that perturbing the reward estimation can guarantee
181
framework [ZBB+] 22
OVRW16).

---

optimism with constant probability, ie. there exists v E (0, 1] such that for all &t E [K] and sf E S,
183
(vi (5
2
184
ZBB (BB=20 proves that this suffices to bound the learning error. However, their method clashes with clipping the value function, as it modifies the probability of optimism. Thus, (ZBB+20) proposes an involved clipping procedure to handle the issue of unstable values. Instead, by careful geometric analysis (cf. Lemma (9). we bound the occurrences of the unstable values, and in turn, upper bound the regret without clipping. Note that unlike [IC BEF-RLSVI does not guarantee that the estimated value function is optimistic but still is able control the learning error (cf. Section 5
186
187
188
189
190
Planning. Recall that with our model assumptions, we can write the state-action value function
linearly (Equation (5)). Using BESVI, have at step h:
2e fr (s, = E.g [r(s,a)] + (DP(s.0), [ (F) or h+1 (5)ds)
(
Then, select the best action greedily using dynamic programming to compute Qn (s, a). Although our model yields infinite dimensional ΦP and v/P, approximating them (cf. next paragraph) with linear features of dimension Opp ()) is possible without increasing the regret. Thus, the planning is done in O(pH K log H)), which is
199
195
in p. H and K, i.e. tractable.
For details about the fiite-dimensional approximation of our transition kernel, refer to Appendix D.5 Now, we highlight the schematic of finite-dimensional approximation of &P and v.P. We proceed three steps. 1) We have with high probability S(V d=, S dH3/2 (Section 5) 2) If we have
197
198
uniform e-approximation of Pær, we show that using it incurs at most an extra (ed K) regret. 3) Finally, following [R07], we approximate uniformly the shift invariant kernels, here the RBF in Equation 4 within eиror and with features of dimensions O(pe log / ). where is dimension of
200
v/. Associating these three elements and choosing & = /////(2K) we establish our claim.
202
Theoretical analysis: proof outline
203
To convey the novelties in our analysis, provide proof sketch for Theorem decomposing the regret into an estimation loss and a learning error, as given below
We start by
205
K
R(K)
Σ (V
V (816)
Σ
Vo 0
V 0r.0=
V 0,,0111
V (81k).
(9)
learning
Estimation
For the estimation error, we use smoothness arguments with concentrations of parameters up to some novelties. Regarding the learning error, we show that the injected noise ensures a constant probability of anti-concentration. Applying Assumption and Lemma 18 leads to the upper-bound.
207
209
5.1
Bounding the estimation error
210
We further decompose the estimation error into the errors in estimating transitions and rewards.
V de ($1x) - V (S1x) V (51k) T or (51k) + V Vr. (51k) - V fr (51x)
(10)
transition estimation
reward estimation
211
Transition estimation Since the reward parameter exact, the value function's 's span S H. Then,
using the transportation of Lemma 13 we obtain the bound H D / 22KLeaa.aa (fr, 6r). We notice
212
that since the reward parameter is exact, the bound is actually И min ΣN / 2KKL (0p, (r)}. we win a / factor compared to the analysis of CG19)
213
214
Using Lemma 18 under Assumption !
Reward estimation Previous work uses clipping to help control this error, but in this case it can hinder the optimism probability by biasing the noise. (ZBB+20) proposes an involved clipping depending on the norms [[Ayp(s)) a (a))eealll 1, which is somewhat delicate analyze and
216
7

---

218
deploy. We remedy the situation acting solely in the proof. First let's define what we call the set of "bad rounds": {N E 3h [|Appp(s (e)))t 2 1 }. these rounds are why clipping necessary. Thanks to Lemma [9] we know that the number of such rounds is most O(d). Surprisingly, it depends neither on H nor on K. We show that the "bad rounds" incur at most O (d H22 regret, independent of K. Therefore, our algorithm can forgo clipping for free.
219
220
222
223
Remark. if wasn't for the episodic nature of our setting, we could have used the forward algorithm to eliminate the span control issue. We refer to [VovOT] AWOT] for description of this algorithm, 10MP21 for a stochastic analysis, and Section therein for an application to linear bandits.
225
226
5.2
Bounding the learning error
227
To upper-bound this term of the regret, we first show that the estimated value function is optimistic with constant probability. Then, we show that this is enough to control the learning error.
228
229
Stochastic optimism. The perturbation ensures a constant probability of optimism. Specifically,
(Vov,0r.1 Vo d0,00,10 00,00.111. (s1) 2 (0
xT)(),,)((s))
Vir or (51) 6f (81) V Vo (81) (81)
V (81)
V 00,0r (81)
V or (81)
second
third
The first and second terms are perturbation free, we handle them similarly to the estimation error, i.e. using concentration arguments for (i and (F For the third term, use transportation of rewards (Lemma] 17) and anti-concentration of &x (Lemma) 12}. We find that with probability at least 28
232
5 (r) (Acg( x- (5)))se
(Vorbr.1 Voo,o 10,,0,1)666 (511) 25h E
(5))e
B
2
H
- -He(n, d)
E hee [[Aup(Sh, (B Σ
(G))
where c(n, 6) (0,
(r (i, oat ((ar))
Since &a- NO x (CF)
233
234
and ny 2 H²((n, we get P VT 60
60 (51) Vin (s1) 2 0) o(-1), where & is the normal
235
CDF. This is ensured by the anti-concentration property of Gaussian random variables, see Lemma 12
Existing algorithms require the value function to be optimistic (i.e. negative learning error) with large probability. Contrary to them, BEF-RLSVI only requires the estimated value be optimistic with constant probability. When it is, the learning happens. Otherwise, the policy is still close to good one thanks to the decreasing estimation error, and the learning still happens. This part of the proof is similar in spirit to that of (ZBB+20)
From stochastic optimism to error control:
237
238
239
240
241
Upper bound on Vi+: Draw (Ee)) i.id copies of (E*)кE[K] and define the event where optimism holds O₂ (V o5 (sf)-Vi+ (xf) 2 0). This implies that (++(s) < 10 (V V 6 (+t))-
242
Lower bound on V g- Consider V (sf) to be a solution of the optimization problem
min Vir fr +Ea. (st) subject to: llEalla, S /zndlog(d/5),
Ek
244 As the injected noise concentrates, we obtain V, (st) S Voe.gr($)).
Combination: Using these upper and lower bounds, show that with probability at least - 8,
Vit (s+)) Váo (e.. ( (s+) S Be, (Vo (Ve. (E.
(,()
S [Rg, VV 6:.. (0)) V, (81)) RE,00 (V. 0r.. - /P((O),
The last step follows from the tower rule. Note that the term inside the expectations is positive 247 with high probability but not necessarily in expectation. We follow the lines of the estimation error analysis to complete the proof of Theorem 2
We refer to Appendix B.2 for the detailed proof.
8

---

249
6
Related works: functional representations with regret and tractability
250
Our work extends the endeavor of using functional representations to perform optimal regret mini- mization in continuous state-action MDPs. We now provide a few complementary details.
251
252
General functional representation. (DSL+18) provides the first convergence guarantee for general nonlinear function representations in the Maximum Entropy RL setting, where entropy of a policy is used regularizer induce exploration. Thus, the analysis cannot address episodic RL, where we have to explicitly ensure exploration with optimism. [WSY20] proposes a framework that leverages the optimism with confidence bound approach for general functional representations with bounded
253
254
255
256
257
Eluder dimensions, which is complexity measure in RL. However, knowing the Eluder dimension crucial for the optimistic confidence bound in their algorithm. Eluder dimension is not known for MDPs except linear and tabular MDPs. To concretize our design, we focus on the general but explicit bilinear exponential family of MDPs than any abstract representation.
258
259
260
261
Bilinear exponential famill family of MDPs. Exponential families are studied widely in RL theory, from expressive parametric family to design model-based algorithms. [CGM21] first studies episodic RL with Bilinear Exponential Family (BEF) of transitions, which is linear in both state-action pairs and the next- state. It proposes a regularized log-likelihood method to estimate the model parameters, and two optimistic algorithms with upper confidence bounds and posterior sampling. Due to its generality
262
bandits to MDPs [LMT21 [KMI3 FCGSTO KH06),
263
paaretticallygrounndee
264
265
266
to unifiedly model tabular MDPs, factored MDPs, linear MDPs, and linearly controlled dynamical systems, the BEF-family of MDPs has received increasing attention [LL [LLS+21] estimates the model parameters based on score matching that enables them to replace regularity assumption on the log- per-pattition function with inforaiinformation and assumption on the parameters. Both CGM21 LLS+21 achieve a worst-case regret of order Ō (²) for known reward. On a different note, DDKL 21 FKQR2T] also introduces a new structural framework for generalization in RL, called bilinear classes as it requires the Bellman error to be upper bounded by a bilinear form. Instead of using bilinear forms to capture non-linear structures, this class is not identical to BEF class of MDPs, and studying the connection is out of the scope of this paper. Specifically, we address the shortcomings of the existing works on BEF-fam BEF-family of MDPs that assume known rewards, absence of RLSeI-rype algorithmss, and access to oracle planners.
257
268
269
270
271
272
273
275
276
277
278
Tractable planning and linearity. Planning is major byproduct of the chosen functional represen- tation. In general, planning can incur high computational complexity if done naïvely. Specially, DKWY19 shows that for some settings, even with a linear e-approximation of the Q-function, planning procedure able to produce an 6-optimal policy has complexity at least 2 Thus, different works (S220 LSW20 VRD19] propose to leverage different low-dimensional representations of
279
281
283
value functions or transitions to perform efficient planning. Here, we take note from [RZSD21] that Gaussian transitions induce explicit linear value function in an RKHS. And generalize this observation with the bilinear exponential. Moreover, using uniformly good features [RR07] to approximate transition dynamics from model enables to design tractable planner. We provide a detailed discussion of this approximation in Section 4 More practically, [RZSD21] [NY21] use representations given by random Fourier features [RR07 to approximate the transition dynamics and provide experiments validating the benefits of this approach for high-dimensional Atari-games.
285
207
289
290
7
Conclusion and future work
291
We propose the -RSVI algorithm for the bilinear exponential family of MDPs in the setting of RL, BEF-RLSVI explores using a Gaussian perturbation of rewards, and plans tractably (complexity of O(pH K log(H K))) thanks to properties of the RBF kernel. Our proof shows that clipping can be forwent for similar RLSVI-type algorithms. Moreover, we prove a H frequentist regret bound, which improves over existing work, accommodates unknown rewards, and matches the lower bound in terms of H and K. Regarding future work, we believe that our proof approach can be extended to rewards with bounded variance. We also believe that the extra v'd in our bound is an artefact of the proof, and specifically, the anti-concentration. We will investigate it further. Finally, we plan to study the practical efficiency of BEF-RLSVI through experiments on tasks with continuous sate-action spaces in an extended version of this work.
292
293
294
296
297
299
300

---

References
301
302
[AL17] Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-184. PMLR, 2017. (Cited 6 21
303
27 28
304
[AOM17] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272 PMLR, 2017. (Cited on (2)
305
306
307
[AWOI] Katy S Azoury and Manfred K Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine Learning, 43(3):211- 246, 2001. (Cited on 8)
308
309
[AYSI]] Yasin Abbasi- Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pages 1-26. JMLR Workshop and Conference Proceedings, 2011. (Cited on
311
313
[BLM13] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, Concentration inequalities: nonasymptotic theory of independence. Oxford university press, 2013. (Cited on 29
314
[CG19] Sayak Ray Chowdhury and Aditya Gopalan. Online learning in kernelized markov decision processes. In The 22nd International Conference on Artificial Intelligence and
316
Statistics, pages 3197-3205. PMLR, 2019. (Cited on 7 23
318
[CGM21] Sayak Ray Chowdhury, Aditya Gopalan, and Odalric- Ambrym Maillard. Reinforcement learning in parametric mdps with exponential families. In International Conference on Artificial Intelligence and Statistics, pages 1855-1863. PMLR, 2021. (Cited on 2 5
320
6 23
322
22]
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826-28266 2836. PMLR, 2021. (Cited on 9
323
324
325
[DKWY19] Simon S Du. Sham M Kakade, Ruosong Wang, and Lin F Yang, Is a good representation sufficient for sample efficient reinforcement learning? arXiv preprint arX0v:1910.03016. 2019. (Cited on 2
327
329
[DLB17] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017. (Cited on T
331
332
[DMKV21] Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021. (Cited on (
333
334
[88
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approxi- mation. In International Conference on Machine Learning, pages 1 1125-1134. PMLR. 2018. (Cited on 9
336
338
339
[FCGS10] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems, 23, 2010. (Cited on
340
[FKQR21] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021.
343
344
(Cited on 2
345
[ICN+21] Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin F Yang. Randomized exploration for reinforcement learning with general value function approximation. arXiv preprint arXiv:2106.0784] 2021. (Cited on 3
347
10

---

349
[JBNW17]
Kwang- Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scal- able generalized linear bandits: Online computation and hashing, arXiv preprint arXiv: /00::/706000..0000 13, 2017. (Cited 5
350
[JYWJ20] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020. (Cited o
353
355
[KH06] Branislav Kveton and Milos Hauskrecht. Solving factored mdps with exponential-family transition models. In ICAPS, pages 114-120, 2006. (Cited on 2
356
357
[KK99]
Michael Kearns and Daphne Koller. Efficient reinforcement learning in factored mdps. In IJCAI, volume 16, pages 740-747, 1999. (Cited on )
358
359
[KKM13] Nathaniel Korda, Emilie Kaufmann, and Remi Munos. Thompson sampling for dimensional exponential family bandits. Advances in neural information processing systems, 26, 2013. (Cited on
361
382
[L] Gene Li. Junbo Li, Nathan Srebro, Zhaoran Wang, and Zhuoran Yang. Exponen- tial family model-based reinforcement learning via score matching. arXiv preprint arXiv:21 14195, 2021. (Cited on 2
363
364
385
[LMT21] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Low-rank generalized linear bandit problems. In International Conference on Artificial Intelligence and Statistics, pages 460-468. PMLR, 2021. (Cited on 5 9
386
387
[LS20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020. (Cited on 33
369
370
[LSW20] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with generative model. In International Conference on Machine Learning, pages 5662-5670. PMLR, 2020. (Cited on 2
372
373
[NY21] Ofir Nachum and Mengjiao Yang. Provable representation learning for imitation with contrastive fourier features. Advances in Neural Information Processing Systems, 34, 2021. (Cited on D
374
375
376
[OMP21] Reda Ouhamma, Odalric-Ambrys Maillard, and Vianney Perchet. Stochastic online lin- ear regression: the forward algorithm to replace ridge. Advances Neural Information Processing Systems, 34:24430-24441 2021. (Cited on
377
[ORVR13] Ian Osband, Daniel Russo, and Benjamin Van Roy, (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013. (Cited on 2
380
382
[OVR14] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014. (Cited on 2
383
384
[OVRW16] Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pages 2377-2386. PMLR, 2016. (Cited on
385
[RR07] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007. (Cited on
388
389
[RZSD21] Tongzheng Ren, Tianjun Zhang, Csaba Szepesvári, and Bo Dai. A free lunch from the noise: Provable and practical exploration for representation learning. arXiv preprint
381
arXiv:2111.11488 2021. (Cited on
16)
382
[SB18] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. (Cited on [
393
394
[SS20] Roshan Shariff and Csaba Szepesvári. Efficient planning in large mdps with weak linear function approximation. arXiv preprint arXiv:2007.06184, 2020. (Cited on 9

---

396
[Vov01] Volodya Vovk. Competitive on-line statistics. 69(2):2132448, 2001. (Cited on [
International Statistical Review,
397
396
[VRD19] Benjamin Van Roy and Shi Dong. Comments on the du--aakadewaang-yang lower bounds. arXiv preprint arXiv:1911.07910 2019. (Cited on 9
[WSY20] Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. arXiv preprint 2rXi::2005.10804 2020. (Cited on 9
401
402
403
[ZBB +0]
20] Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessan- dro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964. PMLR, 2020. (Cited on
404
405
406
6
S
Checklist
407
1. For all authors...
409
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
410
411
(b) Did you describe the limitations of your work? [Yes]
412
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is a purely theoretical contribution
413
414
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
415
416
2. If you are including theoretical results...
417
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
418
(b) Did you include complete proofs of all theoretical results? [Yes] See the appendices
419
3. If you ran experiments..
420
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
421
422
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
423
424
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
425
426
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
427
428
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
429
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite creator of the bilinear exponential family model.
431
(b) Did you mention the license of the assets? [N/A]
432
(c) Did you include any new assets either in the supplemental material or as URL? [No]
435
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
438
437
5. If you used crowdsourcing or conducted research with human subjects...
438
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
439
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
441
442
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
443
12


Reviews:
[{"review_id": "TTUxCLQMBjD", "reviewer": "Reviewer_jyJc", "summary": "This paper studies model-based reinforcement learning for episodic Markov decision processes whose rewards and transitions are parametrized by bilinear exponential families with features of state and action. To balance the exploration-exploitation trade-off, the author suggested a randomized algorithm that injects a calibrated Gaussian noise in the parameter of rewards. The proposed algorithm achieves $\\tilde{\\mathcal{O}}(\\sqrt{d^3 H^3 K})$ regret bound with high probability. \n", "questions": "I would appreciate it if the author could tell me their opinion on the aformentioned 'Weakness' part.\n\nSome more questions are as follows:\n\nLine 93: I think $\\theta$ denotes $(\\theta^p, \\theta^r)$. It would be better to mention that before referring to the optimal policy for clarity.\n\nLine 191: For the $Q$ function that the agent calculates using the estimated parameter, if $Q^{\\pi}_{\\hat{\\theta}^p, \\tilde{\\theta}^r, h}$ in line 191 is the same $Q\\_{\\tilde{\\theta}, h}$ as the calculated in Algorithm 2, shouldn't it be correct that there should be no $\\pi$ symbol in $Q$? Also, I think it should be fixed in the regret decomposition (eq. 10).\n\nLine 230 (Stochastic optimism): I am a little confused because of the $\\pi$ notation in the value function calculated with the estimated parameter (e.g., $V^{\\pi}\\_{\\hat{\\theta}^p, \\tilde{\\theta}^r, 1})$, but I am curious how the $Q^*_{\\hat{\\theta}^p, \\tilde{\\theta}^r, 1}$ appears in the first inequality. Also, I am not sure how the second inequality decomposes? \n\nMost of explanations were clear and well written, but with appearance of a lot of notations, it would be very helpful to understand this paper if the author mentions why the inequality holds in the appendix. ", "limitations": "I think there are no issues related to social impact. However, although this paper is highly related to theoretical part, considering that many recently published theoretical papers about model-based RL also present numerical experiments, I think it would be better if there was an experimental result in this paper.  ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "<Strengths>\n\n1. In this paper, the author not only presented a provable algorithm for a model-based algorithm whose transitions and rewards are parametrized by a bilinear exponential family that extends the linear transition assumption but also improved the regret by $\\sqrt{H}$ compared to the upper-confidence based algorithm in a similar setting. \n\n2. Unlike the other model-based algorithms that assume the reward information is known, this paper solves the problem under the assumption that neither transition model nor reward information is known. In addition, it is interesting that the analysis is carried out by dividing the “Good rounds” and “Bad rounds” according to the weighted norm of the state-action feature without using the handcrafted clipping value function.\n\n3. Based on the concentration results of the upper-confidence based algorithm in a similar problem setting, the author presented a randomized algorithm which is known to be practical but difficult to analyze with a frequentist regret bound guarantee for the first time. \n\n<Weakness>\n\n1.  Although the author dealt with the setting where the model is parametrized by the bilinear exponential family, but it seems to solve the problem by using linearity in RKHS. This seems to rely on the information on the RKHS (e.g., RBF kernel $k(x,y)$) corresponding to the transition probability that the agent estimates. If not, what is the difference between the problem in this paper and the linear MDP method in ([JYWJ20], [ZBB+20], Yang & Wang;2020)  ?\n    \nc.f) Yang & Wang, 2020: Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound\n\n2. As the author said, the most existing works on model-based RL usually assume that information about reward is given. The reason is that it is more difficult to estimate the transition model than the reward, and in the end, the part for reward estimation in regret is not the leading term. This can be seen in the main theorem presented in the paper. Therefore, it is questionable whether learning without information on reward can be said to be a special contribution.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8ZqaaRfW-ny", "reviewer": "Reviewer_rPG8", "summary": "This paper studies episodic reinforcement learning where the reward and transition probability functions belong to parametric bilinear exponential families. A randomized least square value iteration algorithm is proposed to perform tractable exploration and planning for bilinear exponential family of MDPs. Novel analysis techniques are introduced to show that the regret of the proposed algorithm is bounded by $\\widetilde{\\mathcal{O}}(\\sqrt{d^3H^3K})$.", "questions": "Some comments and questions are as follows:\n\n1. The notation for matrix $\\mathbb{A}$ in Algorithm 1 is used before its definition. It's better to move earlier the definition of $\\mathbb{A}$.\n2. Compared with the original definition of the bilinear exponential family model in [CGM21], the factor $h(s',s,a)$ is omitted. Is this critical for the observation of linearity of transitions in Eq.(4)?\n3. It is said in line 41-43 that linear MDP is a special case of the bilinear exponential family model. Could the authors elaborate on this?\n4. In line 11 of Algorithm 1, solving $\\hat\\theta^p(k)$ and $\\hat\\theta^r(k)$ involves integral approximations as remarked in line 176-177. Can this be implemented efficiently? More details on this should be provided.\n5. The $({\\hat\\theta}^p, \\tilde\\theta^r)$ in line 6 of Algorithm 1 should be indexed with $k$? Similarly, in the regret decomposition in Eq.(9) and the corresponding analysis in Section 5 and Appendix B, what is $\\hat \\theta^p$? Is it an arbitrary estimator or some estimate constructed during running Algorithm 1?\n6. Following the previous question, it is not clear why $\\zeta_{hk}$ in line 508 in the appendix is a martingale sequence. Does $V_{\\hat\\theta^p,\\theta^r,h+1}$ depend on previous data? Details about this $\\hat\\theta^p$ need to be specified.\n\n---\nMinor issues:\n\n1. In line 22, '$t = 1, \\ldots, H$', missing a comma.\n2. It seems that the definition of $\\mathbb{E}_{s,a}^{\\tilde\\theta^r}[r]$ is missing in the main context.\n3. In line 40, a few extra '-'.\n4. The inner product in Eq.(5) and the equation under line 191 should be $\\langle\\cdot, \\cdot \\rangle_{\\mathcal{H}}$?\n5. In line 140, '$[p, r]$' should be {$p, r$}?", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well-written and easy to follow. The authors have clearly summarized their contributions and discussed the improvement in their method over existing works. The theoretical analysis seems to be novel and non-trivial. However, the bilinear exponential family model defined in this paper seems to be more restrictive than the original definition in [CGM21]. Also, some notations are confusing. See more details below.", "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": "4TNrI0w4eoM", "reviewer": "Reviewer_gSYF", "summary": "The work consider RLSVI-type algorithms on a bilinear exponential family MDP.\nThey make several contribution, including achieving tractable exploration.\n\nI believe this work represents a significant improvement over existing art, both in terms of result as well as techniques involved. The work is well explained and it flows easily.", "questions": "See above in details", "limitations": "In the specific linear setting considered by the authors, only a restricted linear MDP model seems to be covered", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I appreciate the work: I think it is well explained, there is a solid contribution to a well defined problem.\nI therefore recommend acceptance. \n\nHowever, I have one major complaint / observation.\nThis work is model based, but the authors claim that it applies to the linear MDP model. Specifically, there is a choice that results in linear MDP. However, as I understand, not all linear MDP as defined in (Jin et al, 20’) can be solved with this algorithm. This is because fixing \\phi on a linear MDP still yields many choice for \\mu (proportional to the state space). In this case, one would need order S (the state space) parameters to fully describe the transition kernel of the linear MDP. Jin et al, 20’ bypasses this problem as it only needs to compute inner products, but the submission here puts a specific model on P; I would expect this model to be of order S in terms of dimensionality. Rather, the model assumed here seems to be that of Yang et al, “Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound” which is far more restrictive. If that’s the case, the comparison / improvement with Zanette et al “Frequentist Regret Bounds for Randomized Least-Squares Value Iteration” is also not as clear, as the two operates in quite different models. More precisely, this work seems to be model based (as explained above); as such, it requires estimating different quantities that the work by Zanette et al. It follows that the improvement that removes the artificial clipping of the value function (and improves the bound) used in Zanette et al. may be enabled by the setting where the current algorithm operates. I think this aspect should be clarified, both in the rebuttal as well as in the paper (apologies if I missed something).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject