Exponential Family Model-Based Reinforcement Learning via Score Matching
Authors: Gene Li
Junbo Li
Anmol Kabra
Nathan Srebro
Zhaoran Wang
Zhuoran Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: online reinforcement learning
exponential family
model-based RL

Abstract: We propose an optimistic model-based algorithm, dubbed SMRL, for finite-horizon episodic reinforcement learning (RL) when the transition model is specified by exponential family distributions with $d$ parameters and the reward is bounded and known. SMRL uses score matching, an unnormalized density estimation technique that enables efficient estimation of the model parameter by ridge regression. Under standard regularity assumptions, SMRL achieves $\tilde O(d\sqrt{H^3T})$ online regret, where $H$ is the length of each episode and $T$ is the total number of interactions (ignoring polynomial dependence on structural scale parameters). 

Exponential Family Model-Based Reinforcement Learning via Score Matching
Gene Li Toyota Technological Institute at Chicago gene@ttic. edu
Junbo Li UC Santa Cruz j117530ucsc.edi edu
Anmol Kabra Toyota Technological Institute at Chicago anmo Betttttiiii... edu
Nathan Srebro
Toyota Technological Institute Chicago nati@tticn edu
Zhaoran Wang Northwestern University zhaoranwang@gmail com
Zhuoran Yang
Yale University
zhuoran, yaw.gyale.ggdlyllllll
Abstract
We propose an optimistic model-based algorithm, dubbed SMRL, for finite-horizon episodic reinforcement learning (RI.) when the transition model is specified by exponential family distributions with d parameters and the reward is bounded and known. SMRL uses score matching, an unnormalized density estimation technique that enables efficient estimation of the model parameter by ridge regression. Under standard regularity assumptions, SMRL achieves Ö(dv H3T) online regret, where is the length each episode and T is the total number of interactions (ignoring polynomial dependence structural scale parameters).
Introduction
This paper studies the regret minimization problem for finite horizon, episodic reinforcement learning (RL) with infinitely large state and action spaces. Empirically, RI has achieved success, in diverse domains, even when the problem size (measured in the number of states and actions) explodes The key to developing sample-efficient algorithms is to leverage function approximation, enabling us to generalize across different state-action pairs. Much thcoretical progress has been made towards understanding function approximation in RL. Existing theory typically requires strong linearity assumptions on transition dynamics [e.g.. [T] 26 S. 36 or action-value functions [e.g., 30 12 of the Markov Decision Process (MDP). However, most real world problems nonlinear. Our theoretical understanding of these settings remains limited. Thus, we ask the question:
35 41 28).
Can we design provably efficient RL algorithms nonlinear environments?
Recently, Chowdhury et al. [I]] introduced nonlinear setting where the state-transition measures are finitely parameterized exponential family models, and they proposed to estimate model parameters maximum likelihood estimation (MLE). The exponential family is a well-studied and powerful statistical framework, so it is natural model class to consider beyond linear models. Chowdhury ctt al. study exponential family transitions of the form:
Pw, (s'1s, a) q(s') exp ((b(5'), Wod(s, a)) (Wo))
where s Rd and I&ds are known feature mappings, q known base measure, Wo the unknown parameter to be learned, and Zea is the log partition function that ensures the density integrates to This transition model covers both linear dynamical systems well the nonlinear dynamical system (nonLDS). introduced by Mania et al. 33). Linear dynamical systems with quadratic rewards, i.e., the linear quadratic regulator (LQR), have received much attention recently as
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

an important testbench for RL in unknown, complex environments [19 42 271. Thus, the work of Chowdhury al. is a crucial step in bridging the gap between RL and continuous control.
However, MLE has several shortcomings. In order to estimate the parameter Wo in (T. MLE requires estimating the log partition function Zaa which is computationally intensive. Practical implementations for MLE which estimate the log partition function via Markov Chain Monte Carlo (MCMC) methods can be slow and induce approximation errors [10]. These approximation errors can propagate in undesirable ways the algorithm's 's planning procedure. Since the MLE W cannot be computed in closed form. Chowdbury et al. leave their estimator implicitly defined as solutions of the likelihood equations. As is typical for upper confidence RL (UCRL) algorithms, one constructs high probability confidence sets around the estimator. Due to the challenging modeling assumption, Chowdhury al. employ confidence sets which are sums of KI. divergences taken over the dataset.
In this work, we bypass these difficulties by instead proposing to learn the model parameters with score matching, an unnormalized density estimation technique introduced by Hyvärinen [22]. Score matching provides an explicit, easily computable closed form estimator for the model parameters by solving certain ridge regression problem (Theorem DD. Moreover, we can employ high probability confidence sets which are ellipsoids centered at the estimator, a standard component in prior theoretical
work on linear bandits and linear MDPs [e.g.. 2 26).
Our main results are as follows:
We extend prior work on the score matching estimator in the i.i.d. setting by proving nonasymptotic concentration guarantees for non-i.i.d. data (Theorem 2)
We consider regret minimization for the setting of exponential family transitions and bounded and known rewards. We design a model-based algorithm, dubbed SMRL, which achieves regret of Odd'''dvv H with polynomial dependence on structural scale parameters (Theorem 3). Here, d= d de dæ is the total number of parameters of Wo. H is the episode length, and T is the total number of interactions. In each episode, SMRL uses score matching as computationally efficient subroutine to estimate W/ from data, then it constructs elliptic confidence regions around the estimator which contain Wo w.h.p. and chooses policies optimistically based on such confidence regions. (This work assumes computational oracle access to an optimistic planner.)
Our regret guarantee matches that of Exp-UCRL, the model-based algorithm proposed by Chowdhury et al. When specialized to the nonL.DS with bounded costs and features, score matching and MI.E are equivalent estimators (Proposition TOp. Here, the work of Kakade et al. (27 gives a tighter
guarantee of Ö( /do + dg. + H) HT)); however we stress that our analysis applies a broader class of models. Broadly speaking, we view score matching and MLE as complementary estimation techniques; while MLE relies on less assumptions, score matching enjoys computational efficiency and allows us to simplify both the algorithm and proofs. A detailed comparison is deferred to Section 5 In this work, we mainly compare against the papers related work can be found in Appendix A
but a broader summary of
Notation. For vector I IRd, we let || := ||=|| denote the lg norm. For matrix M Rxd we denote vec (M) Innd be the vectorized version of M. For matrix M, also denote ||M ll to be the operator norm and || to be the Frobenius norm, i.e., [| == ||vec (M)I)- We also let e, E Rd and Egg E gaxd denote the canonical basis vectors and matrices respec- tively. For positive semidefinite matrices A, B, we let A = B to be B A z 0. For posi- tive semidefinite matrix and vector x we define || = Vx Ax. For any n E N, we let [n] := (1.2.....77) n]. For twice differentiable function f ET + R" and any [m]. we let 0² azf(x) = a fz), ds; fn(z) E R and f())())==))))))))(())))))) = du? fi()) du? fn dz
E IR...
We the word "algorithm" liberally, since methods discussed in this paper as well other papers require solving optimization procedures which can be computationally intractable.
2 Problem statement
We consider the setting of an episodic Markov Decision Process, denoted by MDP(S, A, H. r). where S is the state space, A is the action space, H E N is the horizon length of each episode, is state transition probability measure, and S x A + IR is the reward function.

---

The agent interacts with the episodic MDP as follows. At the beginning of each episode, state $1 chosen by an adversary and revealed the agent. The agent picks a policy function, which is collection of (possibly random) functions = T S + A (AA) he[H] that determines the agent's strategy for interacting with the world. For each step / E [ the agent observes the state sn and plays action d4 (s,). Afterwards, they observe reward rh (5), 04), and the MDP evolves to new state 8/+1 ~ P S/s, ah). The episode terminates at state H after which the world resets.
The goal of the agent is maximize their cumulative rewards through interactions with the MDP. Concretely, in our model-based setting the agent knows the reward function r and that the transition model IP lies in some model class P, and they want to pick policies every episode minimize regret, which we formally define later on.
Now define the value function and action- value function. For every policy can define value function V + R. which is the expected value the cumulative future rewards when the agent plays policy и starting from state in step h, and the world transitions according to P. this paper, we include IP in the subscript since we will analyze value functions for different models; if clear from context, we will drop the subscript IP. Specifically, we have:
H
P (8) = Ep
Σ
TM (Sw,, axc) 8h = 8, ~ π
ASE USES,hE [H]
Similarly, we define the action-value functions ( a) S x A R to be the expected value of cumulative rewards starting from a state-action pair in step h, following ग afterwards:
H
(s, = = Ep
Σ h
(she, )w) $1. =, s, = a, 44+1-
V(s,a) (XA
An optimal policy オt is defined to be the policy such that the corresponding value function V (s) is maximized at every state s E S and step h E [H]. Without loss of generality, it suffices to consider deterministic policies [48). Given knowledge of the MDP (S,A, H, IP, r), the optimal value function and action-value function can be computed via dynamic programming [47]; then the optimal policy can be computed the policy that acts greedily with respect to the optional action-value function, i.e. (s) = arg max.5A Q7 (s,
In the online setting, we will measure the performance of an agent interacting with the MDP over K episodes via the notion of regret. In every episode l E [K], an adversary presents the agent with a state st; and the agent then chooses a policy x² The regret over K episodes is the expected suboptimality of the agent's choice of policy n= compared to the optimal policy n=:
K
R(K)= = Σ
VT (5/)
VI (sf)
Implicit in the notation R(K) are the adversary's choice of initial states; our results for regret will hold for any sequence of adversarially chosen {sf ]eeeк]. We will also denote T == K H as the total number of interactions the agent makes with the world.
2.1 Exponential family transitions
We consider the setting when the transition model class P is given by exponential family transitions and the the reward function S x A + R is bounded a.s. in [0, 1] and known the learner
Definition 1 (Exponential family transitions, c.f., (II). Suppose C Rdd and A is any arbitrary action set. Fix feature mappings vi : + Rd and Φ
::SSx S A + Rdd as well as base measure
q R. R. For any matrix W xd let:
Pw(s'|s, q(8') exp (Wb('), W Wo(s, a)) Zsa (W)),
Our results extend to settings where rewards are not known but instead in some class R. C (S x A R) by including an additional reward estimation procedure in our algorithm; the regret would additionally depend on the complexity of R.
3

---

where (.) is the log partition function, which is completely determined once s, Ø. 9. and W are specified. Then we define the exponential family transitions model class P(1. @, q) as:
{{{ IPw exx))xxxxll exp((v())) W Wo(ss, a))) ds <0, V(s, V(s.a) ES
P(u, 0. :=
Since tb ó, q are taken be fixed and known to the learner, we will write the model class as P.
Along with this assumption, we introduce a notational convention. Given some real or vector- measurable function f(s'). we will write E fs') to denote the expected value of f when s' is drawn from the conditional distribution (-1s, a), i.e. I := Is f(
Chowdhury et state their results for setting where the unknown matrix Wo Σ 0,4, where the A, R7 are known matrices and I is unknown. This setting can be viewed nonlinear analog of the linear mixture model considered in 36 5. Definition
D is a special case with d = de dg and Ay := Eaj. Our results can be extended to their general setting with minor modification. Quantitatively, we would replace factors of d, x de with d in both the concentration and regret guarantees, and similar to Chowdhury et al. we would introduce constants which depend on A. For simplicity of presentation, study the fully unknown matrix setting.
2.2 Relationship to (non)linear dynamical systems
We now describe how Definition |
generalizes the previously studied model class of (non)linear dynamical systems which have been explored in reinforcement learning and control theory literature.
First, take step back and describe linear dynamical systems (LDS), which govern the transition dynamics of the LQR problem An LDS defined by the following transition dynamics:
As Ba + E, where E ~ (00 E).
where 8, E Rd, a E Rd,, A, B are appropriately sized parameter matrices, and E E RR x is a known covariance matrix. The problem of estimating (A, B), known system identification, has long history (see Appendix A for more details).
Recently, system identification and regret minimization have been studied for nonlinear generaliza- tions of LDS no for short)
33 27 In this paper, we refer to this setting as the nonlinear dynamical system (or The nonI.DS is described by the state transition model:
= Woo(s, a) + where NO, E).
By setting ((s a) [s T and Wo = [A B]. we recover the classical linear dynamical system. The nonLDS (and by extension the L.SS) are special cases of Definition out the pdf of the multivariate Gaussian distribution to get:
This can be seen by writing
(0s'== = --'ss Z.o [[Wo
q(s') (2x))d// exp
Lastly, note that Definition] I is more general than that of the nonLDS, whose base measure g(-) and feature mapping (-) must take a specific form given by the multivariate Gaussian. Definition I gives extra flexibility in the functions q, v. and ø, which can be regarded as design choices for the practitioner. For example, one can pick the mapping & the output of a neural network which captures the relevant features for the transition to 8'; this is not permitted under the nonLDS setting.
3 Model estimation via score matching
In this section, we present the score matching method, the subroutine in our RL algorithm that estimates model parameters. We also introduce structural assumptions that enable us to derive nonasymptotic concentration guarantee for the score matching estimator.
"Strictly spcaking, our results do not handle unbounded costs, so they do not apply to the LQR problem.
3 Kakade et al. [27] study kernelized version of this model, which they call the kernelized nonlinear regulator.

---

3.1 Background on score matching
Suppose we want estimate the conditional density P(s'|s, a) of the form 2 given dataset D= {[st, at, St41) MLE is the natural candidate for this estimation procedure, but it suffers from pitfalls. Solving for the MLE requires computing the log-partition function (:) If the log-partition function not known in closed form, it can be estimated using Markov Chain Monte Carlo methods 10 14]: however, this procedure may be computationally expensive. For some settings such as kernelized exponential families, MLE fails due ill-posedness
21
Hyvärinen 22 23 proposed score matching as an alternative to minimizing the log likelihood. Score matching minimizes the Fischer divergence, which is the expected squared distance between the score functions v. NoglPw(C (s'|sss,, a). Specifically, we define the divergence between Pw, and Pw for fixed (s, a) as:
Fwg (.a)) ? Pw s.a)
J(Pwo (1ss,, := Pw. (s'1s, V log
ds'.
(3)
Before proceeding with the exposition of the score matching estimator, we list standard regularity conditions that required for the analysis of score matching [ef., 44
Assumption (Regularity conditions).
(A) S is a non-empty open subset IR with piecewise smooth boundary as == 3 S, where
S is the closure of S.
(B) (Differentiabilityy): <b()) is twice continuously differentiable on S with respect to each coordinate i E [dz], and 0 (bs) is continuously extensible to 5 for all j E {1,2), & [da].
(C) (Boundary Condition): For all (s, a) E S x A and i E [da]. as s' + as, we have:
|0.v0(s'|| Puo (8|ss,a)
o[[ls']] )
(D) (Integrabilitt): For all i E [4.), (s, a) E S x A, let Psa = Fwa (-18, Then:
|,,,(s')|| E LS P..), vs (s')) E L' [0,0((')) 0 log q(s') E L' P.n).
The key insight of |Hyvärinenja that via an integration by parts trick, the divergence can rewritten in more amenable form. Essentially, these regularity conditions allow us to rewrite the conditional score function (WW = JPWw, (-18, a) a) (-(s,a)) as:
1 2 / Pw. (s'ls,
de Σ [1a, log Pw (s' a))s + 20 log Fw (s'1s, ds' +C, (4) 1=1
J(W)
where C' does not depend on the parameter W. In Appendix B.I
we provide a more formal derivation
of 4 for exponential family densities well as further discussion on Assumption
Crucially, can be estimated with samples without requiring computation of the partition function, since the partition function vanishes when taking partial derivatives with respect to s'. This gives rise to the following formulation of the empirical score matching loss for dataset D [(s a,, 8 be(m):
J.(W): 1=1=1
(10, log Pw (5/1s,, a,)) + 206 log Pw
(SM-L)
Furthermore, for any regularizer X > O, we can define the empirical score matching estimator:
Wn.* mig (W) + ||
(SM-E)
w
The following theorem gives a closed form expression for the empirical score matching estimator, when specialized to densities given by Definition] [
5

---

Theorem 1. For dataset D = {(st, at, s() hejm) (M-L) can be written as:
Jn(W) 1 (vec (W), V2 vec (W)) + (vec (W),6,) + C,
where:
Vn =
vec (Os)))))(())))))))) vec (0 E Redododaayy
1=1 1=1
de
ΣΣ
(a, log ((s)) + (s)() o(s),a)7 E Ruuds
I=1 iml
and C does not depend on W. addition, (M-E) can be computed as:
(Wn..) (Vn + A
vec
(5)
Theorem iis typical result in score matching literature, and can be derived as corollary of Arbel and Gretton Thm. 3]. For completeness, we give proof in Appendix B.2
For the rest of the paper, it is useful derive matrix expressions for V, and 8n We define the following functions:
((8 a) = [Eni((s, a), (i20(s, a), Eijo(s, a), E.. o(s, Rdodexd, d,
C(s) = Σ (.0())); E eddoxd, {(8) = Σ 0, (())()))))))))))) + of i=1
Rdv. addition, we use the subscript / denote the value the above expressions on sample (st, aes 8)).
We succintly represent Vn = Em= D and b, = - +.C..
We make few remarks the computation of the score matching 1 see that computing Wn, does not require estimation of the log- partition function Zun- The objective a quadratic function in W, which we can solve for via Equation ( However, Equation (5) requires to invert dædæ dody matrix, which takes time d and memory ddd) This can be disappointing from a practical perspective, where the dimensionality of é and & can be large. Several additional considerations may remedy this. First, using the representer theorem, it is possible to show that W is the solution of linear system of n ds variables, thus taking time ((n)dg)) and space (n ( d 4 Thm. I]. One can further reduce the dependence using Nyström approximations [4)] Second, if are in the structured setting
Computational efficiency.
estimator. From Theorem
d where W Σ Ei= O, where 0 Red is unknown but the matrices A, Re xd. are known. Theorem can be adapted to this setting, and solving for 6,, will take time (dd) and space O(d²).
3.2 Concentration guarantee
We provide concentration guarantees for score matching under some structural assumptions: Assumption (Structural scaling).
(A) For any (s, a) E S x A and s' ~ Pw, (-1,, a): we have {(s') is B -ussuuaaussiinn
(B) For any (s,a) E S x A and s' ~ Pw. (-1s, a): we have W(s)) a) is B--subgaussinn.
(C) For any s' E an C(s') 2 azl, where a2 2 01 0.
(D) For any (s,a) E x A: E. ( (8'))('')) - ( (ss)EE (T) S kl.
with suitable The conditions in Assumption 2 are mostly adapted from prior work 44
modifications to accomodate our non-i.i.d setting. Notably, Assumption holds for nonLDS (when Σ o² I) with Bg 6 B, 0, 02 - and x -2 Due space considerations,
defer further discussion on Assumption
2 to Appendix B.3
We prove the following concentration guarantee.

---

Theorem 2. Suppose Assumptions 1 and hold. Let (Fe) be filtration such that (st. 01) is Fi measurable, 5y Fet1 measurable, and s Pwo (-|s;, For any 8 E (0, and À > 0, leu:
BR 2(B++ of
log det(A "V, +1) V W
With probability at least 1 - 8, the score matching estimators of SM-E satisfy:
vec (Wm.)) vec (Wo) V. S Bo, for all n E N.
Theorem is self-normalized concentration guarantee, since the parameter error is rescaled by data-dependert term Vn + AI. The proof is provided in Appendix B.4 The proof relies on the method of mixtures argument developed the linear bandit literature [see, e.g.. .. 29
Algorithm and main result
In this section, present our main results, which introduce the Score Matching for RL (SMRL) algorithm (Algorithm ! and provide regret guarantees.
4.1 Algorithm specification
. K, we compute elliptic confidence set Wi centered at our score matching estimator. In particular, we consider the n n: (k - 1) state transitions D {st, dee 1 the agent has observed up until the beginning of episode k and run the score matching estimator to get the prediction Wr == arg minw J(W)+ [[]] via (Equation 5).
Our algorithm works as follows. In each episode A: = 1.......
In discussing our RL algorithm and its regret guarantees, we choose to index W and V by k rather than emphasize that these quantities are computed once per episode. We also drop the subscript because it is fixed across the run of the algorithm.
Let B, is some known upper bound on ||Wll We define the confidence set
W Rdd |ecc (w:.) vec (W) +N
Wh
S Be
where
2(B B.) af
log 2det(A Adet(A--VizHe (1+t1) + VAB
Bk =
Once the agent computes the confidence set Wk. they observe a new state sf and compute an optimistic policy Th (line 5-6), which is the optimal policy with respect to the "best model" in Wi- As long as Wo E Wr, the optimistic planning procedure gives an overestimate of the true value function Vē, (sf), ensuring sufficient exploration of the MDP. Lastly, the agent runs policy x² on the MDP collect new trajectory of data, which added the dataset D.
4.2 Computational complexity
Algorithm I has two main components: model estimation (line 9) via score matching and optimistic planning (line 6). We have already discussed in Section 3 that the model estimation can be computed efficiently. Planning is different story. Even planning with a known model, i.e., solving the problem x arg max, V (s*), is already challenging without imposing further structure. However, it can be approximated with model predictive control [34, 49). Furthermore, even with access to planning oracle, optimistic planning known to NP-hard the worst case [5] In this work, we assume computational oracle access to the optimistic planner that solves (line 6) and leave developing efficient approximation algorithms to future work. One alternative to optimistic planning is to employ posterior sampling methods in conjunction with (approximate) planning oracles; the Bayesian regret can be theoretically analyzed using well-established techniques [e.g.. [I]
7

---

Algorithm Score Matching for RL (SMRL)
1: Input: Regularizer and constants B Bry Bu, Ri On
2: Initialize: starting confidence set W1 = Rd Xdo, confidence widths {84 dataset D =
3: for episode k 3, K do
4: Planning:
5: Observe initial state sf
6:
Choose the optimistic policy: x² arg max, maxwew, V (
7: Execution:
8:
Execute to get a trajectory {sh, of r/. s 1htmh and add it to D.
9: Solve for score matching estimator We arg minw J(W) + a/ | via 5
10:
Update confidence set Wx+1 via (6)
4.3
Regret guarantee
We now provide our main result, which is a rreget guarantee on the performance of SMRL.
Theorem (SMRL Regret Guarantee). Suppose Assumptions and hold. Set == L/ and fix ō E (0, 1). Then with probability at least 1 5:
R(K)= S CVTK+1 B.) ag
(7K+1 + log 1/6) 0o
+11 V2TT.
where C' > is an absolute constant and YK-1 == log det det (8, a), then R(K) S Ö(dads v VH3T), where the Ô hides log factors and poly (K. By, Be, ).
+ If a)ll S for all
The proof is presented in Appendix C few remarks are in order. Our regret guarantee depends on the number of model parameters dæ de and not the state and action space sizes, thus making algorithm sample-efficient in large-scale environments where S and |A| are infinite. Additionally, is easy redo the analysis when the parameter matrix is structured, i.e., Wo = Dí 0,A,, to see that the regret guarantee depends on d instead dæ x dø. Thus, we can recover the same regret guarantee of (dv (T) that Chowddury et al. provide.
On the more technical side, in Theorem dynamical systems do not satisfy in general (recall & = [s, a] and s, a can have unbounded norm). We need this to provide a bound on certain "information gain" quantity
require ø to be bounded feature mapping, which linear
log det(A-1 1/2 + I) [cf., 43 [27;: however, the bounded assumption can be substantially weakened because our proof only requires Σ || 2 to bounded every episode with high probability. In particular, one restricts to controllable policies which do not blow up norm of the state [e.g.. [3], then the information gain term can be bounded.
Score matching vs maximum likelihood estimation
In this section, provide detailed comparison of score matching with maximum likelihood approaches. First we compare for exponential family transitions of Definition 1 then we specialize comparison for the nonLDS setting. Lastly, provide numerical evidence to demonstrate setting where (a variant of) SMRL is superior.
5.1 General comparison for exponential family transitions
Score matching and MLE can be viewed as complementary techniques for density estimation; highlight the relative pros and cons of SMRL vs EXp-UCRL.
In general, Exp-UCRI. can be applied to more settings than score matching, due to the fact that score matching requires regularity conditions (Assumption) TT that are needed for the derivation of (4). In particular, we require S to be Euclidean space and the feature vector x) S - IR to be a twice-differentiable mapping. this sense, the scope of SMRL is more limited than that of EXp-UCRL. For example, while tabular and factored MDPs can be modeled as exponential family

---

transitions via the softmax parameterization we cannot prove regret guarantees for SMRL due to the differentiability requirement. Since the MLE estimator of of et al. can be computed in poly(S, A) time, in the tabular and factored MDP settings we would prefer to run Exp-UCRI..
Among models given by Definition] I where both score matching and MLE can be applied, score matching is preferred because the estimator can be computed in closed form as the solution to ridge regression problem, and elliptic confidence sets can be constructed around it using Theorem 2 For the MLE, this is not possible in general. Chowdhury et al. implicitly define the estimator as the solution to the likelihood equations, and their confidence set is constructed in a complicated fashion, in terms of sums of KL divergences taken over the dataset. Thus, while we are unable to claim overall computational tractability of Algorithm due the computational difficulty of optimistic planning, score matching enables us to estimate model parameters efficiently, an improvement from Exp-UCRI..
We now compare the regret guarantee of Theorem 3 with previous results; the detailed calculations are deferred to Appendix D.I] We achieve the same order-wise guarantee as Chowdhury et Thm. 2) of Ö(dady H)). In terms of problem constants, both bounds depend on vr, but we (1) require the constants By and Be, (2) replace dependence on strict convexity of the log partition function with the parameter 01.
5.2 Comparison with prior work for nonLDS
Now we compare our results for SMRL with the results for Exp-UCRL Chowdhhuy et al.) and LC (Kakade et al.) for the nonLDS problem with bounded and known rewards. For simplicity we will take the transition noise to be (0, (2,)), We will also assume that |[ S B. and that the feature vectors are bounded as [|o(s, a)ll S Bg for all (s, a) E S x A. All three similar UCRL-style algorithms, and we compare the parameter estimation, confidence sets, and regret guarantee.
Estimation and confidence set construction. For nonLDS, score matching and MLE are equivalent estimators (see Proposition 10 for a formal statement). Thus, in all three algorithms, the parameter estimation procedure is identical, up rescaling of regularization parameter X. To further facilitate comparison, we will hereafter fix the À of each algorithm such that the parameter estimation is the same as LC (for any fixed dataset). Our choices are detailed in Appendix D.2
Once we have fixed the parameter À for each algorithm, the main distinction lies in the confidence set construction. While all three algorithms essentially utilize the same optimistic planning procedure, optimistic planning depends on the confidence sets constructed in each episode. The chosen policies and the resulting trajectories will be different in all three algorithms. The confidence sets constructed for each paper are essentially the tightest self-normalizer bound one can prove, so it is hard to directly compare the confidence sets from paper to paper due to the difference in analyses. Generally speaking, SMRL uses Frobenius norm bounds (Theorem 2}.
uses a mixture of both Frobenius and spectral [1 Sec. 3.1], and LC3 uses only spectral norm bounds (2 Eq. 3.2].
Regret guarantee. In terms of the regret guarantee, Theorem 3 gives us a regret guarantee of can be derived for EXp-UCRL. Note that the latter bound depends polynomially the scale of Wo and 6. Kakade et al. (Remark 3.5) give bound for LCC of Ö(vdg + de + H)H²T), without polynomial dependence on o² and the scale of Wo and Φ. We conjecture that the o" dependence is an artifact our analysis, but is less clear whether the dependence on dø, dae can be improved.
((Vdade (oAdady + H)H)). while bound of Ö(y Li (1
5.3 Experiments on synthetic MDP
We demonstrate end-to-end benefits of using score matching in a (highly stylized) synthetic MDP; see Figure [ In our constructed MDP, the transition function multimodal; the action choice affects the location of the modes of the next state density. The reward is constructed so that = +1 leads -1 at most states. To enable fair comparison, we fix a simple random sampling shooting planner (39] and evaluate three model estimation procedures: score matching with
to higher reward than
'There is mild technical issue, since Definition] cannot capture transitions with probability 0, so we must assume that the support of the transitions is known in advance. See the paper [I] for more details.

---

LDS
0.8
200
Geound sruh
98 with given
9.0
130
Cumulatiin
6.0
Reward lunction
100
6.5
0.2
50-
3.0
3.0 -1.5
3.0
20
50
10
Episode
(a) MDP transition and reward
(b) Cumulative rewards
(c) Planner action choices
Figure 1: Comparing SM vs fitting an LDS for a synthetic MDP. with S R. A= [+1.-1]. H 10. (xxp(-s"'7//0 /1.7) exp((in(4ss))) (s + a)), and r(s, exp(-10(s x/ = + exp( (00(= + / (a) plots for a single starting state s 0.5 for a = ++1 and a = 11; the reward r superimposed. Taking a = +1 is more likely to transition to states with high reward. (b) plots cumulative reward for fixed planner with varying model estimation: SM with the given P. fitting an LDS, and a bascline with the ground truth model. (c) plots the number of steps in every episode where +1 picked by the planner. In and (c), shaded areas correspond 95% confidence intervals.
initial state distribution Unif[[-1, + P(s. P(s'(s s, a)
the given class P. fitting an LDS via MLE, and a baseline where planner supplied the ground truth F. (For this simple one-dimensional RL task, one can also numerically compute the MLE with the given P. However, this approach does not scale to RL tasks with high-dimensional states.) Fitting an LDS does poorly because the LDS density is not expressive enough to differentiate between and a -1, while score matching estimates the density well, so the planner quickly learns to pick = +1. Our experiments suggest that modeling the transition I' via the richer Definition I can yield end-to-end benefits for RL tasks. Further experimental details can be found Appendix F
+1
6 Conclusion
In this paper, we show -rerggret guarantees for a reinforcement learning setting when the state transition model is an exponential family model, challenging nonlinear setting. Under this modeling assumption, the commonly employed MIEE may be intractable; we bypass such issues by proposing learn the model via the score matching method.
We conclude with a few possible directions for future work.
Model Misspecifcaation: Proving guarantees for SMRL when the underlying transition P do not lie in the model class P but instead is well-approximated by P e: P is an interesting direction.
Arbitrary State Spaces: A key limitation of the score matching estimator is that requires that the state space S must be subset of the Fuclidean space Rd, and the feature mapping v to be twice differentiable; therefore it cannot handle arbitrary state spaces. One important direction is extending the score matching algorithm to discrete state spaces such as tabular/factored MDPs through suitable modification of the estimation procedure [c.g.. 23]
Kernelization: We would like to extend our guarantees to the kernel conditional exponential family (KCEF) setting of Arbel and Gretton 4. i.e., when the conditional model is y [s, 3...) q(8"). exp ((f, I k.sk(sss -)) - (f), where ff lies in some vector valued Reproducing Kernel Hilbert Space (RKHS) H. k(s'.-) lies in an RKHS Hss and I'.o H.s + H. is operator that depends on (s, a). This generalizes our finite dimensional setting and a special case of the conditional family where the inner product is df, a, s')). studied by Canu and Smola (. In the KCEF setting. MLE becomes computationally intractable; yet score matching can be kernelized and efficiently computed, and fast approximation methods exist [46]. Our theory does not hold for the KCEF because the parameter a1 0. Instead, one might be able to adapt the range-space assumption from the paper 4 to the non-i.i.d. setting.
Acknowledgments and Disclosure of Funding
This work is supported by funding from the Institute for Data, Econometrics, Algorithms, and Learning (IDEAL). We thank Pritish Kamath, Danica J. Sutherland, Akshay Krishnamurthy, and Wen Sun for helpful discussions. Part of this work was done while GI., 7W, and ZY were participating in the Simons Program on the Theoretical Foundations of Reinforcement Learning in Fall 2020.
10

---

References
[1] 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.
[2] Yasin Jabasi-Yadkorf Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. NIPS, volume 11, pages 2312-2320, 2011.
[3] Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst- case regret bounds. In Advances in Neural Information Processing Systems, pages 1184-1194, 2017.
[4] Michael Arbel and Arthur Gretton. Kernel conditional exponential family. In International Conference Artificial Intelligence and Statislicx, pages 1337-1346, 2018.
[5] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with talue-targeted regression. In Proceedings of the 37th International Conference Machine Learning, pages
PMLR, 2020.
[6] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[7] Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of markov chain monte carlo. CRC press, 2011.
[8] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
[9] Stéphane Canu and Alex Smola. Kernel methods and the exponential family. Neurocomputing, 69(7-9):714-720, 2006.
[10] Miguel A PerreiraPerrpina and Geoffrey Hinton. On contrastive divergence learning. In International workshop on artificial intelligence and statistics, pages 33 40. PMLR, 2005.
[11] Sayak Ray Chowdhury, Aditya Gopalan, and Odalric-Ambrym Maillard. Reinforcement learning in parametric mdps with exponential families. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pages 1855-1863, 2021.
[12] Adam D Cobb, Atilım Güneş Baydin, Andrew Markham, and Stephen Roberts. Introducing an explicit symplectic integration scheme for riemannian manifold hamiltonian monte carlo. arXiv preprint 1XX000900000243 2019.
[13] Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only sqrtt regret. International Conference on Machine Learning, pages 1300-1309. PMLR, 2019.
[14] Bo Dai, Zhen Liu, Hanjun Dai, Niao He, Arthur Gretton, Le Song. and Dale Schuurmans. Expo- nential family estimation via adversarial dynamics embedding. arXiv preprint arXiv: 12083, 2019.
[15] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback.
[16] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pages 5713-5723, 2017.
[17] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. In Advances in Neural Information Processing Systems, 2018

---

[18] Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou. Root-n-regret for learning in markov decision processes with function upproximation and low bellman rank. In Conference on Learning Theory, pages 1554-1557. PMLR, 2020.
[19] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning, pages 1467-1476. PMLR. 2018.
[20] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint 1xXxv:2112.134883 2021.
[21] Kenji Fukumizu. Exponential manifold by reproducing kernel hilbert spaces. Algebraic and Geometric mothods in statistics, pages 291-306, 2009.
[22] Aapo Hyvärinen. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(Apr):695-709) 2005.
[23] Aapo Hyvärinen. Some extensions of score matching. Computational statistics & data analysis, 51(5):2499-2513 2007.
[24] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(,), 2010.
[25] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire. Contextual decision processes with low bellman rank are pac-lcarnable. In International Conference on Machine Learning, pages 1713- PMLR, 2017.
[26] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143, 2020.
[27] Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Infor- mation theoretic regret bounds for online nonlinear control. In Advances in Neural Information Processing Systems, pages 15312-15325, 2020.
[28] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11): 2013.
[29] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[30] Tor Lattimore, Csaba Szepesvari, and Gellent Weisz. Learning with good feature representations in bandits and in rl with a generative model. In International Conference on Machine Learning, pages 5662-5670. PMLR, 2020.
[31] Siwei Lyu. Interpretation and generalization of score matching. In Proceedings of the Twenty- Fifth Conference on Uncertainty in Artificial Intelligence, pages 359-366, 2009.
[32] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. In Advances in Newral Information Processing Systems, 2019.
[33] Horia Mania, Michael Jordan, and Benjamin Recht. Active learning for nonlinear system identification with guarantees. arXiv preprint arXiv:2006.1022 10277, 2020.
[34] David Q Mayne. Model predictive control: Recent developments and future promise. Automat- ica, 50(12):2967-2986, 2014.
[35] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1321v:1312.5602, 2013.
[36] Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of rein- forcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
12

---

[37] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems, pages 1466-1474, 2014.
[38] Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pages 2377-2386, 2016.
[39] Anil V Rao. A survey of numerical methods for optimal control. Advances in the Astronautical Sciences, 135(1):497-528, 2009.
[40] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In NIPS, pages 2256-2264, 2013.
[41] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-335 2017.
[42] Max Simchowitz and Dylan Foster. Naive exploration optimal for online lqr. International Conference Machine Learning, pages 1937-8948. PMLR, 2020.
[43] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian pro- cess optimization in the bandit setting: No regret and experimental design. arXiv preprins arXiv:0912.3995, 2009.
[44] Bharath Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Aapo Hyvärinen, and Revant Kumar. Density estimation in infinite dimensional exponential families. The Journal of Machine Learning Research, 18(1):1830-1888 2017.
[45] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pages 2898-2933. PMLR, 2019.
[46] Danica J. Sutherland, Heiko Strathmann, Michael Arbel, and Arthur Gretton. Efficient and prin- cipled score estimation with nyström kernel exponential families. In International Conference on Artificial Intelliencce and Statisties, pages 652-660. PMLR, 2018
[47] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[48] Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis lectures on artificial intelligence and machine learning, 4(1):1-103, 2010.
[49] Nolan Wagener, Ching-An Cheng, Jacob Sacks, and Byron Boots. An online learning approach to model predictive control. arXiv preprint arXiv: 08967, 2019.
[50] Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6135, 2020.
[51] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix handit, kernels, and regret bound. arXiv preprint
2019.
[52] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work
mostly theoretical, and does have any immediate negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A] Experiments
laptop.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're '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]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "bH5hau_iiPs", "reviewer": "Reviewer_rkgm", "summary": "This paper presents a new model-based algorithm, called SMRL, for finite horizon episodic MDPs where the transition model is specified by exponential family distribution. Essentially, the work builds on Exp-UCRL [1] and proposes to use score matching instead of MLE to estimate the parameters of the transition model, which helps it run efficiently by eliminating the need to estimate the computationally expensive log partition function required in MLE. The proposed algorithm matches the regret bound offered by Exp-UCRL while being computationally efficient. The paper also presents theoretical proof for their efficient algorithm.", "questions": "Q1: How can we handle the problems for which the transition model does not belong to the exponential family distribution? \nQ2: Can we approximate such transition models which do not belong to exponential family?", "limitations": "The main limitations is that the algorithm works on specific problems which satisfies the assumptions on transition and reward models, which limits the application of the algorithm.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Strong theoretical justification.\n- The language of the paper is fine apart from some typos and uncommon abbreviations.\n\nWeaknesses:\n- The assumption that transition model belongs to exponential family may be limiting for many real-world problems.\n- Although it is a theory paper, I would have liked to see how does the algorithm performs empirically vs Exp-UCRL.\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": "HI7NAiRyDLT", "reviewer": "Reviewer_LwWm", "summary": "This paper studies model-based reinforcement learning for episodic MDP whose transition model is parametrized by exponential families with features of state and action. \nTo estimate the model parameter, the author uses the score matching technique to minimize the expected squared distance between the score functions. \nTo promote exploration, the author utilizes the optimistic planning.\nThe author states that under some regularity assumptions, the suggested algorithm achieves $\\tilde{\\mathcal{O}}(d \\sqrt{H^3 T})$. ", "questions": "(1) Before introducing Assumption 2, $\\Phi(s,a), C(s'), \\xi(s')$ are defined on line 184. If the author could explain these functions in more detail, it would be helpful to understand the Assumption 2.\n\n(2) The current model parameter $\\hat{W}_k$ is updated after the episode is over. However, since the current problem is a model-based setting, I think it is possible to update the model parameter on every horizon because the agent receives transition feedback on every horizon. If the agent can construct a confidence set for the true model parameter every horizon without considering the computation issue for planning, I think the regret bound might be tighter. I wonder what the author thinks about this.\n\nminor typos\n1. Line 566: I think it would be better to unify the numbering of Assumption 2 and the numbering in the appendix.\n2. Line 579: $\\hat{V}_n + \\lambda I \\succeq \\lambda I$\n3. Line 615: I think \"Under Definition 1 and 2\" should be fixed to \"Under Definition 1 and Assumption 2\"", "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 is an experimental result in this paper.  ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think their research is relevant to RL community since they focus on how to design a provably and efficient algorithm for the nonlinear environment.\nBeyond the existing work based on the linearity assumption for transition models or MDPs, as an extension of Exp-UCRL [10], which dealt with the problem when the transition models are parametrized by exponential families, the author proposes a more efficient method for estimating model parameters. \nBased on the score matching technique, it can be more efficient than the previous method because it does not need to estimate the log-partition $Z_{sa}$.\nAlso, I think the analysis of the proposed algorithm is sound and the writing is clear.\n\nHowever, in my opinion, the most important part of score matching relies on how to formulate the Fisher divergence (eq 3) into an empirical score matching loss (eq SM-L). \nThis result is presented in Theorem 1 and since this result is from [4], I carefully consider whether the result of this paper has significant novelty\n\nAlso, in Theorem 2, it presents the result of a self-normalized concentration guarantee when the parameter to be estimated $\\hat{W}$ is vectorized.\nI think this kind of result can be obtained if the problem setting $\\exp(\\langle \\psi, W \\phi \\rangle)$ is replaced with $\\exp(\\langle vec(W), vec(\\psi \\phi^\\top) \\rangle)$.\nIf so, I think the bilinear structure disappears. Is there a way to express this concentration result without vectorization?\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": "AX_qmGtfhhl", "reviewer": "Reviewer_QcxS", "summary": "The paper proposes a novel method for estimating the transition model of an MDP parametrized by exponential functions, in the episodic finite-horizon model-based RL setting with bounded and known rewards. The method uses score matching that reduces to ridge regression of the known parameters of the exponential parametrization, thus eliminating the difficulties associated with estimating the partition function in MLE-based methods. An estimate of the online regret for the new algorithm is derived, too. ", "questions": "What are the actually achievable advantages of the proposed method in comparison with a reasonable baseline, for example MLE? Section 5 provides a comparison in general terms, but there is no empirical verification. Maybe such a verification on prototypical test MDPs would be useful in illustrating the analysis?", "limitations": "The authors have addressed limitations adequately, for example they have conscientiously pointed out that their analysis does not cover LQR problems, due to their unbounded costs. I do not see any potential negative societal impacts of this work.\n\nMinor typos:\nP.4 L.136,138: \"gaussian\" -> \"Gaussian\"", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main contribution of the paper is probably the idea to apply score matching to the exponential parametrization proposed earlier, resulting in a more efficient estimation algorithm. This is a very non-obvious and original advance, and given that the investigated parametrization subsumes a very large class of systems encountered in practice, the practical significance of this advance is likely to be high. However, the paper is entirely theoretical, and it is difficult to understand the computational advantages of the proposed method without at least some kind of empirical evaluation. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept