Reda Ouhamma
email: reda.ouhamma@gmail.com

Debabrota Basu
email: debabrota.basu@inria.fr

Odalric-Ambrym Maillard
email: odalric.maillard@inria.fr

Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration & Planning

Keywords:

We study the problem of episodic reinforcement learning in continuous stateaction 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 to an underlying RKHS to perform tractable planning. We further provide a frequentist regret analysis of BEF-RLSVI that yields an upper bound of Õ(

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

√

H and removes the handcrafted clipping deployed in existing RLSVI-type algorithms. Our regret bound is order-optimal with respect to H and K. * https://redaouhamma.github.io/

Introduction

Reinforcement Learning (RL) is a well-studied and popular framework for sequential decision making, where an agent aims to compute a policy that allows her to maximize the accumulated reward over a horizon by interacting with an unknown environment [START_REF] Richard | Reinforcement learning: An introduction[END_REF].

Episodic RL. In this paper, we consider the episodic finite-horizon MDP formulation of RL, in short Episodic RL [ORVR13, AOM17, DLB17]. Episodic RL is a tuple M = ⟨S, A, P, r, K, H⟩, where the state (resp. action) space S (resp. A) might be continuous. In episodic RL, the agent interacts with the environment in episodes consisting of H steps. Episode k starts by observing state s k 1 . Then, for t = 1, . . . H, the agent draws action a k t from a (possibly time-dependent) policy π t (s k t ), observes the reward r(s k t , a k t ) ∈ [0, 1], and transits to a state s k t+1 ∼ P(. | s k t , a k t ) according to the transition function P. The performance of a policy π is measured by the total expected reward V π 1 starting from a state s ∈ S, the value function and the state-action value functions at step h ∈ [H] are defined as

V π h (s) def = E H t=h r(s t , a t ) | s h = s , and Q π h (s, a) def = E H t=h r(s t , a t ) | s h = s, a h = a .
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 RL algorithm.

Regret is 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 an agent that has to learn about the unknown environment. Formally, the regret over K episodes is

R(K) ≜ K k=1 V π ⋆ 1 (s k 1 ) -V πt 1 (s k 1 ) .
Key Challenges. The first key challenge in episodic RL is to tackle the exploration-exploitation tradeoff. This is traditionally addressed with the optimism principle that either carefully crafts optimistic upper bounds on the value (or state-action value) functions [START_REF] Gheshlaghi Azar | Minimax regret bounds for reinforcement learning[END_REF], or maintains a posterior on the parameters to perform posterior sampling [START_REF] Osband | more) efficient reinforcement learning via posterior sampling[END_REF], or perturbs the value (or state-action value) function estimates with calibrated noise [START_REF] Osband | Generalization and exploration via randomized value functions[END_REF]. 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 a highdimensional 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.

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 [START_REF] Jin | Provably efficient reinforcement learning with linear function approximation[END_REF], bilinear [DKL + 21], and bilinear exponential families [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF], are studied in literature to develop 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 + 21, DKL + 21, FKQR21]. The bilinear exponential family model is of special interest as it is expressive enough to represent tabular MDPs (discrete state-action), factored MDPs [START_REF] Kearns | Efficient reinforcement learning in factored mdps[END_REF] and linearly controlled dynamical systems (such as Linear Quadratic Regulators [START_REF] Abbasi | Regret bounds for the adaptive control of linear quadratic systems[END_REF]) as special cases [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF]. 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.

The third challenge is to perform tractable planning2 given the perturbation for exploration and the model class. Existing work [START_REF] Osband | Model-based reinforcement learning and the eluder dimension[END_REF][START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF] assumes an oracle to perform planning and yield policies that aren't explicit. The main difficulty in such planning approaches is that dynamic programming requires calculating P(s ′ | s, a)V h (s) 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. [START_REF] Simon S Du | Is a good representation sufficient for sample efficient reinforcement learning?[END_REF] asks when misspecified linear representations are enough for a polynomial sample complexity in several settings. [SS20, LSW20, VRD19] provide positive answers for specific linear settings. In this paper, we aim to design a tractable planner for the bilinear exponential family representation.

In this paper, we aim to address the following question that encompasses the three challenges:

Can we design an algorithm that performs tractable exploration and planning for bilinear exponential family of MDPs yielding a near-optimal frequentist regret bound?

Our Contributions. Our contributions to this question are three-fold.

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 a linear behavior (see Section 2) in a Reproducible Kernel Hilbert Space (RKHS). This observation contributes to the tractability of planning.

Algorithm:

We propose an algorithm BEF-RLSVI that extends the RLSVI framework to bilinear exponential families (see Section 3). BEF-RLSVI a) injects calibrated Gaussian noise in the rewards to perform exploration, b) leverages the linearity of the transition model with respect to an underlying RKHS to perform tractable planning and c) uses penalized maximum likelihood estimators to learn the parameters corresponding to rewards and transitions (see Section 4). To the best of our knowledge, BEF-RLSVI is the first algorithm for the bilinear exponential family of MDPs with tractable exploration and planning under unknown rewards and transitions.

✓ ✓ ✓ Bilinear Exp Family 3. Analysis: We carefully develop an analysis of BEF-RLSVI that yields Õ( √ d 3 H 3 K) regret which improves the existing regret bound for bilinear exponential family of MDPs with known reward by a factor of √ H (Section 3.2). Our analysis (Section 5) builds on existing analyses of RLSVI-type algorithms [START_REF] Osband | Generalization and exploration via randomized value functions[END_REF], but contrary to them, we remove the need to handcraft a clipping of the value functions [ZBB + 20]. We also do not need to assume anti-concentration bounds as we can explicitly control it by the injected noise. This was not done previously except for the linear MDPs. We illustrate this comparison in Table 1. We highlight three technical tools that we used to improve the previous analyses: 1) Using transportation inequalities instead of the simulation lemma reduces a

√

H factor compared to [START_REF] Ren | A free lunch from the noise: Provable and practical exploration for representation learning[END_REF], 2) Leveraging the observation that true value functions are bounded enables using an improved elliptical lemma (compared to [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF]), and 3) Noticing that the norm of features can only be large for a finite amount of time allows us to forgo clipping and reduce a

√

d factor from the regret compared to [ZBB + 20].

Bilinear exponential family of MDPs

In this section, we introduce the bilinear exponential family (BEF) model coined in [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF], extend it to parametric rewards, and we state a novel observation about linearity of this representation.

Bilinear exponential family. We consider transitions and rewards from the BEF. Specifically,

P (s | s, a) = exp ψ(s) ⊤ M θ p φ(s, a) -Z p s,a (θ p ) , (1)
P (r | s, a) = exp r B ⊤ M θ r φ(s, a) -Z r s,a (θ r ) , (2)
where φ ∈ (R q + ) S×A and ψ ∈ (R p + ) S are known feature mappings, and B ∈ R p is a known matrix. The reward and transition parameters are

θ p , θ r ∈ R d . M θ • def = d i=1 θ • i A i , where (A i ) 1≤i≤d are known matrices. The log partition function: Z p s,a (θ p ) def = log S exp ψ(s) ⊤ M θ p φ(s, a
) ds, and Z r is defined similarly. Finally, we emphasize a minor difference with the original BEF model: like [LLS + 21], we omit a base measure of the form h(s, s, a) from the model, note that all the examples provided in [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF] still hold with this slight restriction.

We denote V π θ p ,θ r ,h , respectively Q π θ p ,θ r ,h , the value, respectively state-action value function for policy π in the MDP parameterized by (θ p , θ r ) at time h. A policy π ⋆ is optimal if for all s ∈ S,

V π ⋆ θ,h (s) = max π∈Π V π θ,h (
s). A learning algorithm minimizes the (pseudo-)regret defined as:

R(K) ≜ K k=1 V π ⋆ θ,1 (s k 1 ) -V π t θ,1 (s k 1 ) . (3)
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 assumption of linearity of the transition kernel is a direct consequence of our model. Indeed,

2ψ (s ′ ) ⊤ M θ p φ(s, a) = -∥(ψ(s ′ ) -M θ p φ(s, a)∥ 2 + ∥ψ(s ′ )∥ 2 + ∥M θ p φ(s, a)∥ 2 .
Notice that the quadratic term resembles the Radial Basis Function (RBF) kernel. More precisely, for an RBF kernel with covariance Σ = I p and k(x, y) def = exp -∥x -y∥ 2 /2 , we find

P (s ′ | s, a) = ⟨ϕ p (s, a), µ p (s ′ )⟩ H , (4)
where H is the RKHS associated with the kernel, µ p (s ′ ) = (2π) -p/2 k (ψ(s ′ ), .) exp ∥ψ (s ′ ) ∥ 2 /2 , and ϕ p (s, a) = k M ⊤ θ p φ(s, a), . exp ∥M θ p φ(s, a)∥ 2 /2 -Z s,a (θ p ) . Equation (4) shows that s ′ is decoupled from (s, a), we see hereafter why this is crucial to reducing the complexity of planning. Remark 1. Up to our knowledge, [START_REF] Ren | A free lunch from the noise: Provable and practical exploration for representation learning[END_REF] is the only work providing an example of linear transition kernel for RL with continuous state-action spaces. They consider Gaussian transitions with an unknown mean (f ⋆ (s, a)) and known variance (σ 2 ). Actually, linear f ⋆ is a special case of the bilinear exponential family model, where

ψ(s ′ ) = (s ′ , ∥s ′ ∥ 2 ) and M θ φ(s, a) = (f θ (s, a)/σ 2 , -1/σ 2 ).
Importance of linearity. To understand the planning challenge in RL, recall the Bellman equation: 4), although ϕ p and µ p are infinite dimensional, we show in Section 4 ( § planning) that the planning complexity becomes polynomial in the problem parameters.

Q π h (s, a) = r(s, a) + s∈S P (s ′ | s, a)V π h+1 (s)

BEF-RLSVI: algorithm design and frequentist regret bound

In this section, we formally introduce the Bilinear Exponential Family Randomized Least-Squares Value Iteration (BEF-RLSVI) algorithm along with a high probability upper-bound on its regret.

BEF-RLSVI: algorithm design

BEF-RLSVI is based on RLSVI [START_REF] Osband | Generalization and exploration via randomized value functions[END_REF] framework with the distinction that we only perturb the reward parameters and not all the parameters of the value function. RLSVI algorithms are reminiscent of Thompson Sampling, yet more tractable with better control over the probability to be optimistic.

Algorithm 1 BEF-RLSVI

1: Input: failure rate δ, constants α p , η and

(x k ) k∈[K] ∈ R + 2: for episode k = 1, 2, . . . do 3: Observe initial state s k 1 4: Sample noise ξ k ∼ N 0, x k ( Ḡp k ) -1 such that Ḡp k = η α p A + k-1 τ =1 H h=1 (φ(s τ h , a τ h ) ⊤ A ⊤ i A j φ(s τ h , a τ h )) i,j∈[d]
5:

Perturb reward parameter: Update the penalized ML estimators θp (k), θr (k), see Equation (5) and Equation (7) 12: end for We can see that Algorithm 1 performs exploration by a Gaussian perturbation of the reward parameter (Line 4). Contrary to optimistic approaches, this method is explicit and also more efficient since it does not a involve high-dimensional optimization.

θr (k) = θr (k) + ξ k 6: Compute (Q k θp , θr ,h ) h∈[H]
Algorithm 2 Bellman Backtracking 1: Input Parameters θp , θr , initialize θ = ( θr , θp ) and ∀s, V H+1 (s) = 0

2: for steps h = H -1, H -2, • • • , 0 do 3: Calculate Q θ,h (s, a) = E θr s,a [r] + ⟨ϕ p (s, a), V θ,h+1 (s ′ )µ p (s ′ )ds ′ ⟩ H . 4: end for
We can approximate Line 3 of Algorithm 2 with O(pH 3 K log(HK)) complexity and without harming the learning process (cf. § planning, Section 4). Therefore, here, planning is tractable.

BEF-RLSVI: regret upper-bound

We state the standard smoothness assumptions on the model [CGM21, JBNW17, LMT21]. Assumption 1. There exist constants α p , α r , β p , β r > 0, such that the representation model satisfies:

∀(s, a) ∈ S × A, ∀θ, x ∈ R d α p ≤ x ⊤ C θ s,a [ψ]x ≤ β p ∀(s, a) ∈ S × A, ∀θ, x ∈ R d α r ≤ Var θ s,a (r) x ⊤ B ⊤ Bx ≤ β r where C θ s,a [ψ (s ′ )] ≜ E s ′ ∼P θ |s,a ψ (s ′ ) ψ (s ′ ) ⊤ -E s ′ ∼P θ |s,a [ψ (s ′ )] E s ′ ∼P θ |s,a ψ (s ′ ) ⊤ and Var θ s,a (r) ≜ E θ s,a r 2 -E θ s,a [r]
2 is the variance of the reward under θ.

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 log-normalizers.

We now state our main result, the regret upper-bound of BEF-RLSVI.

Theorem 2 (Regret bound). Let A ≜ (tr

(A i A ⊤ j )) i,j∈[d] and G s,a ≜ (φ(s, a) ⊤ A ⊤ i A j φ(s, a)) i,j∈[d] .
Under Assumption 1 and further considering that

1. max{∥θ r ∥ A , ∥θ p ∥ A } ≤ B A , ∥A -1 G s,a ∥ ≤ B φ,A and E θ r [r(s, a)] ∈ [0, 1] for all (s, a). 2. noise ξ k ∼ N (0, x k ( Ḡp k ) -1 ) satisfies x k ≥ H β p β p (K,δ) α p α r + √ β r β r (K,δ) min{1, α p α r } 2α r 2 ∝ dH 2 ,
then for all δ ∈ (0, 1], with probability at least 1 -7δ,

R(K) ≤ √ KH 2H 2β p α p β p (K, δ)γ p K +(1+ γ r K ) log(1/δ 2 ) Transition concentration ≈ dH + β r β r (n, δ)γ r K 2α r Reward concentration ≈ d + cβ r x K dγ r K log(dK/δ) + β r x K dγ r K log(e/δ 2 ) Φ(-1) (1+ log(d/δ)) Noise concentration ≈ d 3/2 H + Hγ r K β r C d β r (K, δ) 2α r + c x K d log(dK/δ)
Estimation error for no clipping ≈ dH

+ β r d √ x K Φ(-1) (1+ log(d/δ)) C d 1+ α r B φ,A H η Learning error for no clipping ≈ (dH) 3/2
, where for i ∈ [p, r],

β i (K, δ) ≜ η 2 B 2 A + γ i K + log(1/δ), and γ i K ≜ d log(1 + β i η B φ,A HK). Also, C d ≜ 3d log(2) log 1 + α r ∥A∥ 2 2 B 2 φ,A η log(2)
, Φ is the Gaussian CDF, and c is a universal constant.

Theorem 2 entails a regret R(K) = O( √ d 3 H 3 K) for BEF-RLSVI, where d is the number of parameters of the bilinear exponential family model, K is the number of episodes, and H is the horizon of an episode. We now clarify how this contrasts with related literature.

Comparison with other bounds. The closest work to ours is [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF] 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(

√ d 2 H 4 K).
There are two notable algorithmic differences with our work. First, they do exploration using intractable-optimistic upper bounds or high-dimensional posteriors, while we do it with explicit perturbation. The second difference is in planning. While they assume access to a planning oracle, we do it explicitly with pseudo-polynomial complexity (Section 4). Moreover, we improve the regret bound by a

√

H factor thanks to an improved analysis, (cf. Lemma 18). But similar to all RLSVI-type algorithms, we pick up an extra √ d (cf. [START_REF] Abeille | Linear thompson sampling revisited[END_REF]).

[ZBB + 20] proposes a variant of RLSVI for continuous state-action spaces, where there are low-rank models of transitions and rewards. They show a regret bound R(K) = O( ). In this case, our bound becomes R(K) = O( (S 2 A) 3 H 3 K), which is clearly not tight is S and A. This is understandable due to the relative generality of our setting. We are however positively surprised that our bound is tight in terms of its dependence on H and K.

√ d 4 H 5 K),

Algorithm design: building blocks of BEF-RLSVI

We present necessary details about BEF-RLSVI and discuss the key algorithm design techniques.

Estimation of parameters. We estimate transitions and rewards from observations similar to EXP-UCRL [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF], i.e. by using a penalized maximum likelihood estimator θp (k) ∈ arg min

θ∈R d k t=1 H h=1 -log P θ s t h+1 | s t h , a t h + η pen(θ).
Here, pen(θ) is a trace-norm penalty: pen(θ) = 1 2 ∥θ∥ A and A = (tr(A i A ⊤ j )) i,j . By properties of the exponential family, the penalized maximum likelihood estimator verifies, for all i ≤ d:

k t=1 H h=1 ψ s t h+1 -E θp k s t h ,a t h [ψ (s ′ )] ⊤ A i φ s t h , a t h = η∇ i pen θp k . (5)
Equation ( 5) can be solved in closed form for simple distributions, like Gaussian, but it can involve integral approximations for other distribution (cf. Appendix F). We estimate the parameter for reward, i.e. θ r , similarly θr (k) ∈ arg min

θ∈R d k t=1 H h=1 -log P θ r t | s t h , a t h + η pen(θ), (6)
=⇒ k t=1 H h=1 r t -E θr k s t h ,a t h [r] B ⊤ A i φ s t h , a t h = η∇ i pen θr k ∀i ∈ [d]. (7)
Exploration. A significant challenge in RL is handling exploration in continuous spaces. The majority of the literature is split between intractable, upper confidence bound-style optimism or Thompson sampling algorithms with high-dimensional posterior and guarantees only in terms of Bayesian regret. In BEF-RLSVI, we adopt the approach of reward perturbation motivated by the RLSVIframework [ZBB + 20, OVRW16]. We show that perturbing the reward estimation can guarantee optimism with a constant probability, i.e. there exists ν ∈ (0, 1] such that for all k ∈ [K] and s k 1 ∈ S,

P Ṽ1 (s k 1 ) -V ⋆ 1 (s k 1 ) ≥ 0 ≥ ν.
[ZBB + 20] proves that this suffices to bound the learning error. However, their method clashes with not 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 19), we bound the occurrences of the unstable values, and in turn, upper bound the regret without clipping. Note that unlike [ICN + 21], BEF-RLSVI does not guarantee that the estimated value function is optimistic but still is able to control the learning error (cf. Section 5).

Planning. Recall that with our model assumptions, we can write the state-action value function linearly. Using BEF-RLSVI, we have at step h:

Q π θp , θr ,h (s, a) = E θr [r(s, a)] + ϕ p (s, a), S µ p (s)V π θp , θr ,h+1 (s)ds . (8)
Then, we select the best action greedily using dynamic programming to compute Q h (s, a). Although our model yields infinite dimensional ϕ p and ψ p , approximating them (cf. next paragraph) with linear features of dimension O(pH 2 K log(HK)) is possible without increasing the regret. Thus, the planning is done in O(pH 3 K log(HK)), which is pseudo-polynomial in p, H and K, i.e. tractable.

For details about the finite-dimensional approximation of our transition kernel, refer to Appendix E. Now, we highlight the schematic of a finite-dimensional approximation of ϕ p and ψ p . We proceed in three steps. 1) We have with high probability S(V θp , θr ,h ) ≤ dH 3/2 (Section 5). 2) If we have a uniform ϵ-approximation of P θ p , we show that using it incurs at most an extra O(ϵdH 5/2 K) regret.

3) Finally, following [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF], we approximate uniformly the shift invariant kernels, here the RBF in Equation ( 4), within ϵ error and with features of dimensions O(pϵ -2 log 1 ϵ 2 ), where p is dimension of ψ. Associating these three elements and choosing ϵ = 1/ (H 2 K), we establish our claim.

Remark 2. The observation of linearity (cf. Equation. (8) and Line 3) does not reduce BEF MDPs to linear MDPs because the former holds in an RKHS. Also, linearity is not in the representation parameter. Therefore, linear RL algorithms do not readily solve the BEF MDPs.

Theoretical analysis: proof outline

To convey the novelties in our analysis, we provide a proof sketch for Theorem 2. We start by decomposing the regret into an estimation loss and a learning error, as given below

R(K) = K k=1 (V ⋆ θ p ,θ r ,1 -V π k θ p ,θ r ,1 )(s 1k ) = K k=1 (V ⋆ θ p ,θ r ,1 -V π k θp , θr ,1 learning + V π k θp , θr ,1 -V π k θ p ,θ r ,1 Estimation )(s 1k ). (9)
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 1 and Lemma 18 leads to the upper-bound.

Bounding the estimation error

We further decompose the estimation error into the errors in estimating transitions and rewards.

V π θp , θr (s 1k ) -V π θ p ,θ r (s 1k ) = V π θp ,θ r (s 1k ) -V π θ p ,θ r (s 1k ) transition estimation + V π θp , θr (s 1k ) -V π θp ,θ r (s 1k ) reward estimation (10)
Transition estimation Since the reward parameter is exact, the value function's span is ≤ H. Then, using the transportation of Lemma 13 we obtain the bound H H h=1 2 KLs hk ,a hk (θ p , θp ). We notice that since the reward parameter is exact, the bound is actually H min{1, H h=1 2 KLs hk ,a hk (θ p , θp )}.

Using Lemma 18 under Assumption 1, we win a √ H factor compared to the analysis of [START_REF] Ray | Online learning in kernelized markov decision processes[END_REF].

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

∥(A i φ(s k h , a k h )) i∈[d] ∥ ( Ḡp k ) -1
, which is somewhat delicate to analyze and deploy. We remedy the situation acting solely in the proof. First let's define what we call the set of "bad rounds":

k ∈ [K], ∃h : ∥(A i φ(s k h , a k h )) i∈[d] ∥ ( Ḡp k ) -1
≥ 1 , these rounds are why clipping is necessary. Thanks to Lemma 19, we know that the number of such rounds is at most O(d). Surprisingly, it depends neither on H nor on K. We show that the "bad rounds" incur at most O(d 3/2 H 2 ) regret, independent of K. Therefore, our algorithm can forgo clipping for free.

Remark 3. If it 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 [START_REF] Vovk | Competitive on-line statistics[END_REF][START_REF] Katy | Relative loss bounds for on-line density estimation with the exponential family of distributions[END_REF] for a description of this algorithm, [START_REF] Ouhamma | Stochastic online linear regression: the forward algorithm to replace ridge[END_REF] for a stochastic analysis, and Section 4 therein for an application to linear bandits.

Bounding the learning error

To upper-bound this term of the regret, we first show that the estimated value function is optimistic with a constant probability. Then, we show that this is enough to control the learning error.

Stochastic optimism. The perturbation ensures a constant probability of optimism. Specifically,

(V θp , θr ,1 -V ⋆ θ p ,θ r ,1 )(s 1 ) ≥ (Q ⋆ θp , θr ,1 -Q ⋆ 1 )(s 1 , π ⋆ (s 1 )) ≥ V π ⋆ θp ,θ r (s 1 ) -V π ⋆ θ p ,θ r (s 1 ) first term + V π ⋆ θp , θr (s 1 ) -V π ⋆ θp ,θ r (s 1 ) second term + V π ⋆ θp , θr (s 1 ) -V π ⋆ θp , θr (s 1 ) third term
The first and second terms are perturbation free, we handle them similarly to the estimation error, i.e. using concentration arguments for θp and θr . For the third term, we use transportation of rewards (Lemma 17) and anti-concentration of ξ k (Lemma 12). We find that with probability at least 1 -2δ

(V θp , θr ,1 -V ⋆ θ p ,θ r ,1 )(s 1 ) ≥ξ ⊤ k E (st) t∈[H] ∼ θp |s k 1 H t=1 Var θ r j (r) 2 (A i φ(s t , π ⋆ (s t ))) i∈[d] B -Hc(n, δ) H h=1 E (st) t∈[H] ∼ θp |s k 1 (A i φ(s h , π ⋆ (s h ))) i∈[d] ( Ḡp k ) -1
,

where c(n, δ) = β p β p (n, δ)/α p + β r β r (n, δ) min{1, α p /α r }/(2α r ) . Since ξ k ∼ N (0, x k ( Ḡp k ) -1 ) and x k ≥ H 2 c(n, δ) 2 , we get P V π θp , θr ,1 (s 1 ) -V ⋆ θ p ,θ r ,1 (s 1 ) ≥ 0 ≥ Φ(-1)
, where Φ is the normal CDF. This is ensured by the anti-concentration property of Gaussian random variables, see Lemma 12.

From stochastic optimism to error control: 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 to be optimistic with a constant probability. When it is, the learning happens. Otherwise, the policy is still close to a 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].

Upper bound on

V ⋆ 1 : Draw ( ξk ) k∈[K] i.i.d copies of (ξ k ) k∈[K]
and define the event where optimism holds as

Ōk ≜ {V θp , θr k ,1 (s k 1 )-V ⋆ 1 (s k 1 ) ≥ 0}. This implies that V ⋆ 1 (s k 1 ) ≤ Eξ k | Ōk [V θp , θr + ξk ,1 (s k 1 )].
Lower bound on V θp , θr : Consider V 1 (s k 1 ) to be a solution of the optimization problem

min ξ k V θp , θr +ξ k ,1 (s k 1 ) subject to: ∥ξ k ∥ Ḡk ≤ x k d log(d/δ),
As the injected noise concentrates, we obtain V 1 (s k 1 ) ≤ V θp , θr (s k 1 ).

Combination: Using these upper and lower bounds, we show that with probability at least 1 -δ,

V ⋆ 1 (s k 1 )-V θp , θr + ξk ,1 (s k 1 ) ≤ Eξ k | Ōk [V θp , θr + ξk ,1 (s k 1 ) -V 1 (s k 1 )] ≤ Eξ k [V θp , θr + ξk ,1 (s k 1 ) -V 1 (s k 1 )] -Eξ k | Ōc k [V θp , θr + ξk ,1 (s k 1 ) -V 1 (s k 1 )]P( Ōc k ) /P( Ōk ),
The last step follows from the tower rule. Note that the term inside the expectations is positive 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.

6 Related work: functional representation in RL with regret and tractability

√ d 3 H 4 K)
for linear MDPs. However, the latter assumes an oracle perturbing the estimation to achieve anti-concentration while maintaining a bounded covering number, which is a counter-intuitive mix of boundedness and anticoncentration. Indeed, [ZBB + 20] studied the linear MDP case, and while it managed to design an ingenious clipping verifying previous assumptions, the method is extremely intricate and the proof is involved and unlikely to extend for general value function spaces. To concertize our design, we focus on the general but explicit BEF of MDPs than any abstract representation. We also remove the requirement to clip with a novel analysis.

Bilinear exponential family of MDPs. Exponential families are studied widely in RL theory, from bandits to MDPs [LMT21, KKM13, FCGS10, KH06], as an expressive parametric family to design theoretically-grounded model-based algorithms. [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF] 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 to unifiedly model tabular MDPs, factored MDPs, and linearly controlled dynamical systems, the BEF-family of MDPs has received increasing attention [LLS + 21]. [LLS + 21] estimates the model parameters based on score matching that enables them to replace regularity assumption on the log-partition function with Fisher-information and assumption on the parameters. Both [CGM21, LLS + 21] achieve a worstcase regret of order Õ( √ d 2 H 4 K) for known reward. On a different note, [DKL + 21, FKQR21] 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-family of MDPs that assume known rewards, absence of RLSVI-type algorithms, and access to oracle planners.

Tractable planning and linearity. Planning is a major byproduct of the chosen functional representation. In general, planning can incur high computational complexity if done naïvely. Specially, [START_REF] Simon S Du | Is a good representation sufficient for sample efficient reinforcement learning?[END_REF] shows that for some settings, even with a linear ϵ-approximation of the Q-function, a planning procedure able to produce an ϵ-optimal policy has a complexity at least 2 H . Thus, different works [SS20, [START_REF] Lattimore | Learning with good feature representations in bandits and in rl with a generative model[END_REF][START_REF] Van | Comments on the du-kakade-wang-yang lower bounds[END_REF] propose to leverage different low-dimensional representations of value functions or transitions to perform efficient planning. Here, we take note from [START_REF] Ren | A free lunch from the noise: Provable and practical exploration for representation learning[END_REF] that Gaussian transitions induce an explicit linear value function in an RKHS. And generalize this observation with the bilinear exponential. Moreover, using uniformly good features [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF] to approximate transition dynamics from our model enables us to design a tractable planner. We provide a detailed discussion of this approximation in Section 4. More practically, [RZSD21, NY21] use representations given by random Fourier features [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF] to approximate the transition dynamics and provide experiments validating the benefits of this approach for high-dimensional Atari-games. Thus, we propose the first algorithm with tractable planning for BEF-family.

Conclusion and future work

We propose the BEF-RLSVI algorithm for the bilinear exponential family of MDPs in the setting of episodic-RL. BEF-RLSVI explores using a Gaussian perturbation of rewards, and plans tractably (complexity of O(pH 3 K log(HK))) thanks to properties of the RBF kernel. Our proof shows that clipping can be forwent for similar RLSVI-type algorithms. Moreover, we prove a √ d 3 H 3 K 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 √ 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 state-action spaces in an extended version of this work.

Appendix

A Notations

We dedicate this section to index all the notations used in this paper. Note that every notation is defined when it is introduced as well.

(R + ) S×A×H G s,a def = φ(s, a) ⊤ A ⊤ i A j φ(s, a) i,j∈[d] Ḡr k def = Ḡr (k-1)h = η α r A + k-1 τ =1 H h=1 G s τ h ,a τ h Ḡp k def = Ḡp (k-1)h = η α p A + k-1 τ =1 H h=1 G s τ h ,a τ h C θ s,a [ψ (s ′ )] def = E θ s,a ψ (s ′ ) ψ (s ′ ) ⊤ -E θ s,a [ψ (s ′ )] E θ s,a ψ (s ′ ) ⊤ β p def = sup θ,s,a λ max C θ s,a [ψ (s ′ )] linked to the maximum eigenvalue of ∇ 2 Z p α p def = inf θ,s,a λ max C θ s,a [ψ (s ′ )] linked to the minimum eigenvalue of ∇ 2 Z p β r def = λ max BB ⊤ sup θ,s,a Var θ s,a (r), linked to the maximum eigenvalue of ∇ 2 Z r α r def = λ min BB ⊤ inf θ,s,a Var θ s,a (r), linked to the minimum eigenvalue of ∇ 2 Z r

B Regret analysis

We provide a high probability analysis of the regret of BEF-RLSVI under standard regularity assumptions of the representation. First we recall the regret definition then we separate the perturbation error from the statistical estimation:

R(K) = K k=1 (V ⋆ θ p ,θ r ,1 -V π k θ p ,θ r ,1 )(s k 1 ) = K k=1 V ⋆ θ p ,θ r ,1 -V π k θp , θr ,1 learning + V π k θp , θr ,1 -V π k θ p ,θ r ,1 Estimation (s k 1 )

B.1 Estimation error

To show that the estimation error

K k=1 V θp , θr ,1 -V π k θ p ,θ r ,1
can be controlled, we decompose it to an error that comes from the estimation of the transition parameter and one that comes from the estimation of the reward parameter:

V π θp , θr (s k 1 ) -V π θ p ,θ r (s k 1 ) = V π θp ,θ r (s k 1 ) -V π θ p ,θ r (s k 1 ) transition estimation + V π θp , θr (s k 1 ) -V π θp ,θ r (s k 1 )
reward estimation , we control each term separately in Section B.1.1 and Section B.1.2. Therefore, we obtain the following lemma controlling the estimation error. Lemma 3. The estimation error satisfies, with probability at least 1 -5δ

K k=1 V θp , θr ,1 (s k 1 ) -V π θ p ,θ r ,1 (s k 1 ) ≤ 2H 2β p α p β p (N, δ)N γ p K + 2H 2N log(1/δ) + KHd log (1 + α r η -1 B φ,A n) + C d Hd log(1 + αη -1 B φ,A H) × β r (n, δ) 2α r +c (max k x k )d log(dK/δ) β r + 2KHd log (1 + α r η -1 B φ,A n) log(1/δ)
where for i ∈ [p, r],

β i (K, δ) ≜ η 2 B 2 A + γ i K + log(1/δ), and
γ i K ≜ d log(1 + β i η B φ,A HK). Also, C d ≜ 3d log(2) log 1 + α r ∥A∥ 2 2 B 2 φ,A η log(2)
, and c is a universal constant.

Proof. It follows directly by combining Lemma 4 and Lemma 5 using a union bound.

B.1.1 Transition estimation

The goal of this section is to prove the following lemma which bounds the regret due to transition estimation.

Lemma 4. We have, with probability at least 1 -2δ

K k=1 V θp ,θ r (s k 1 ) -V π θ p ,θ r (s k 1 ) ≤ 2H 2β p α p β p (N, δ)N γ p K + 2H 2N log(1/δ)
where γ p K := d log 1 + β p η -1 B φ,A HK , and

β p (K, δ) ≜ η 2 B 2 A + γ p K + log(1/δ).
Proof. The proof proceeds in two parts. First, we will reveal a bound in terms of the induced local geometry, i.e. a bound in terms of KL-divergence. Second, we explicit the bound by transferring the induced local geometry to the euclidean one.

1) Bound in terms of local geometry. We provide a bound on the estimation error of the transition in terms of KL divergences, for that end we show that the estimation error can be decomposed and well controlled. We start by writing the one-step decomposition:

V π θp ,θ r ,1 (s k 1 )-V π θ p ,θ r ,1 (s k 1 ) = E θp s k 1 ,a k 1 V π θp ,θ r ,2 -E θ p s k 1 ,a k 1 V π θp ,θ r ,2 + E θ p s k 1 ,a k 1 [V π θp ,θ r ,2 -V π θ p ,θ r ,2 ] = E θp s k 1 ,a k 1 V π θp ,θ r ,2 -E θ p s k 1 ,a k 1 V π θp ,θ r ,2 + V π θp ,θ r ,2 (s 2k ) -V π θ p ,θ r ,2 (s 2k ) + ζ k 1 = H h=1 E θp s hk ,a hk V π θp ,θ r ,h+1 -E θ p s hk ,a hk V π θp ,θ r ,h+1 + ζ hk where ζ hk = E θ p s hk ,a hk [V π θp ,θ r ,h+1 -V π θ p ,θ r ,h+1 ] -V π θp ,θ r ,h+1 (s h+1k ) -V π θ p ,θ r ,h+1 (s h+1k
) is a martingale sequence, and the last equality comes by induction. Here we consider the true reward parameter which verifies |E θ r [r(s, a)]| ≤ 1 by assumption, therefore |ζ hk | ≤ 2H. Using the Azuma-Hoeffding inequality [START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF], with probability at least 1 -δ

K k=1 H h=1 ζ hk ≤ 2H 2KH log(1/δ)
We finish bounding the first term using Lemma 13, indeed

E θp s hk ,a hk V π θp ,θ r ,h+1 -E θ p s hk ,a hk V π θp ,θ r ,h+1 ≤ H 2 KL s hk ,a hk (θ p , θp ) ≤ H min 1, 2 KL s hk ,a hk (θ p , θp ) ,
the last inequality follows because ∀h, S(V θp ,θ r ,h+1 ) ≤ H.

Remark 4. Traditionally, the expected value difference bound follows from the simulation lemma [START_REF] Ren | A free lunch from the noise: Provable and practical exploration for representation learning[END_REF]. The simulation lemma incurs an extra √ H factor compared to our bound.

We deduce that with probability at least 1 -δ:

K k=1 V θp ,θ r (s k 1 ) -V π θ p ,θ r (s k 1 ) ≤ H K k=1 min 1, H h=1 2 KL s hk ,a hk (θ p , θp ) + 2H 2KH log(1/δ) (11)
2) Bounding the sum of KL divergences. we explicit the bound of inequality (11) using Assumption 1 along with properties of the exponential family (cf. Section D.3). We have for all (s, a),

∀θ p , θ p′ , α p 2 ∥θ p′ -θ p ∥ 2 Gs,a ≤ KL s,a (θ p , θ p′ ) ≤ β p 2 ∥θ p′ -θ p ∥ 2 Gs,a . (12)
This implies that

KL s,a θp (k), θ p ≤ β p 2 θ p -θp (k) 2 Gs,a ≤ β p ( Ḡp k ) -1/2 G s,a ( Ḡp k ) -1/2 1 2 θ p -θp (k) 2 Ḡp k , where Ḡp k ≡ Ḡp (k-1)H := G k + (α p ) -1 ηA and G k ≡ k-1 τ =1 H h=1 G s τ s ,a τ
h . From Corollary 8, with probability at least 1 -δ and for all k ∈ N

θ p -θp (k) 2 Ḡp k ≤ 2β p (k, δ)/α p .
Also, using Lemma 18, we have

T t=1 H h=1 min 1, ( Ḡp k ) -1/2 G s,a ( Ḡp k ) -1/2 ≤ 2d log 1 + α p η -1 B φ,A HK .
Combining these two results we obtain, with probability at least 1 -δ:

T t=1 H h=1 min 1, KL s t h ,a t h θp (k), θ p ≤ 2β p α p β p (K, δ)γ p K . (13)
Remark 5. Notice that the minimum with 1 is crucial, indeed, without it the bound deteriorates by a factor H as was the case in [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF].

3) Combining the bounds. By applying Cauchy-Schwarz in inequality (11), we obtain, with probability at least 1 -δ, and for all

K ∈ N K k=1 V θp ,θ r (s k 1 ) -V π θ p ,θ r (s k 1 ) ≤ H 2 K k=1 H h=1 KL s hk ,a hk (θ p , θp ) + 2H 2KH log(1/δ).
Injecting inequality (13) proves the desired result with probability at least 1 -2δ.

B.1.2 Reward estimation

Now, we provide the bound over the regret due to estimating the reward parameter. Lemma 5. With probability at least 1 -3δ, the following result holds true.

K k=1 V π θp , θr ,1 (s k 1 )-V π θp ,θ r ,1 (s k 1 ) ≤ β r (K, δ) 2α r + c (max k≤K x k )d log(dK/δ) β r × C d 1 + α r B φ,A H η + K log(e/δ 2 ) Hd log (1 + α r η -1 B φ,A HK),
where

β p (K, δ) ≜ η 2 B 2 A + γ p K + log(1/δ), and γ p K ≜ d log(1 + β p η B φ,A HK). Also, C d ≜ 3d log(2) log 1 + α r ∥A∥ 2 2 B 2 φ,A η log(2)
, and c is a universal constant.

Proof. The reward estimation error in Equation (10) can be written explicitly. Indeed, using Lemma 17

V π θp , θr ,1 (s k 1 ) -V π θp ,θ r ,1 (s k 1 ) = E (s h ) 1≤h≤H ∼π| θp ,s k 1 H h=1 Var sh ,π(s h ) (r) 2 B ⊤ M θr -θ r φ(s h , π(s h )) ≤E H h=1 Var sh ,π(s h ) (r) 2 ∥ θr -θ r ∥ Ḡr k ∥(B ⊤ A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k ) -1 ≤∥ θr -θ r ∥ Ḡr k E H h=1 Var sh ,π(s h ) (r) 2 ∥(B ⊤ A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k ) -1 ≤∥ θr -θ r ∥ Ḡr k β r 2 E H h=1 ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k ) -1 def = traj k , where traj k def = H h=1 ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ (G r k ) -1 . Bad rounds.
We separate the analysis of this estimation error into bad and good rounds. Here we analyze the bad rounds, which are define by the following set:

T = {k ∈ N * , ∃h ∈ [H], ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k ) -1 ≥ 1} 1) We know that ∥(A i φ(s h , π(s h ))) 1≤i≤d (A i φ(s h , π(s h ))) ⊤ 1≤i≤d ∥ 2 2 ≤ ∥A∥ 2 2 B 2 φ,A . Consequently, according to Lemma 19 |T | ≤ 3d log(2) log 1 + α∥A∥ 2 2 B 2 φ,A η log(2) .
2) Since G k is positive semi-definite, we have Ḡr k ⪰ (α r ) -1 ηA, and in turn, for all state-action couples (s, a), ( Ḡr

k ) -1 G s,a ≤ α r η A -1 G s,a ≤ α r B φ,A η
. This further yields

I + ( Ḡr k ) -1 H h=1 G s t h ,a t h ≤ 1 + H h=1 ( Ḡr k ) -1 G s t h ,a t h ≤ 1 + α r B φ,A H η .

Let us define Ḡr

k+H := Ḡr k + H h=1 G s k h ,a k h . Then, Ḡ-1 k+H G s,a = I + ( Ḡr k ) -1 H h=1 G s t h ,a t h -1 ( Ḡr k ) -1 G s,a .
Therefore, for all pairs (s, a),

∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k ) -1 = tr((A i φ(s h , π(s h ))) ⊤ 1≤i≤d ( Ḡr k ) -1 (A i φ(s h , π(s h ))) 1≤i≤d ) = tr( 1 + α r B φ,A H η ( Ḡr k+H ) -1 G s,a ) ≤ 1 + α r B φ,A H η ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k+H ) -1 Since ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k+H ) -1 ≤ 1, we have ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k+H ) -1 ≤ min 1, ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k ) -1 . Consequently H h=1 ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k+H ) -1 ≤ Hd log(1 + α r η -1 B φ,A H).
3) From 1) and 2), we deduce that the total regret induced by rounds from T is bounded.

k∈T h∈[H] V π θp , θr ,1 (s k 1 ) -V π θp ,θ r ,1 (s k 1 ) ≤ ∥ θr -θ r ∥ Ḡr k β r 2 3d log(2) log 1 + α r ∥A∥ 2 2 B 2 φ,A η log(2) 1 + α r B φ,A H η Hd log(1 + α r η -1 B φ,A H) (14)
Remark 6. The bad rounds analysis is one of our most important contributions as it enables us to forgo clipping without consequences. Consequently, this is a novel method to control the reward estimation error that improves on existing work for whom clipping was essential.

Good rounds. Going forward we consider rounds from T . Let us define

ζ ′ k def = traj k -E (s h ) 1≤h≤H ∼π| θp ,s k 1 traj k .
where traj k is the same quantity as traj but with a random realization of state transitions. Since all feature norms are smaller than one, (ζ ′ k ) k is a martingale sequence with |ζ ′ k | ≤ Hd log (1 + α r η -1 B φ,A HK). We deduce that with probability at least 1 -δ:

K k=1 ζ ′ k ≤ 2KHd log (1 + α r η -1 B φ,A HK) log(1/δ)
Therefore, we have with probability at least 1 -3δ:

k∈T c V π θp , θr ,1 (s k 1 ) -V π θp ,θ r ,1 (s k 1 ) ≤ β r (K, δ) 2α r + c (max k x k )d log(dK/δ) × β r KHd log (1 + α r η -1 B φ,A KH) log(e/δ 2 ).
The last inequality follows from controlling the concentration of the reward parameter. First we observe that (Corollary 10) with probability at least 1 -δ, uniformly over k ∈ N, θ rθr (k)

2 Ḡr k ≤ 2 α r β r (k, δ).
Second, we also have that for all k ≥ 1, with probability at least 1 -δ, ∥ξ k ∥ G r k ≤ c x k d log(d/δ), we then use a union bound. Combining with Equation ( 14) we find

K k=1 V π θp , θr ,1 (s k 1 ) -V π θp ,θ r ,1 (s k 1 ) ≤ β r (K, δ) 2α r + c (max k x k )d log(dK/δ) × β r KHd log (1 + α r η -1 B φ,A HK) log(e/δ 2 ).
This concludes the proof.

Remark 7. If we use Lemma 17 without the martingale difference sequence, it will lead to a linear regret. Indeed, the span of the sum of norms over an episode is of order √ H. Using the martingale technique instead allows us to retrieve a telescopic sum controlled using the elliptical lemma, this is essential to obtaining a sub-linear regret bound.

B.2 Learning error

We now start the control of an important regret term, due to the distance between the estimated value function and the optimal value function. Lemma 6. If the variance parameter of the injected noise (ξ k ) k satisfies

x k ≥   H β p β p (k, δ) α p α r + β r β r (k, δ) min{1, α p α r } 2α r   ,
then the learning error is controlled with probability at least 1 -2δ as

K k=1 V ⋆ 1 (s k 1 ) -V π θp , θr + ξk ,1 (s k 1 ) ≤ dβ r √ x k 1 + log(d/δ) Φ(-1) H log (1 + α r η -1 B φ,A HK) × C d 1 + α r B φ,A H η + K log(e/δ 2 ) ,
where for i ∈ [p, r],

β i (K, δ) ≜ η 2 B 2 A + γ i K + log(1/δ), and
γ i K ≜ d log(1 + β i η B φ,A HK). Also C d def = 3d log(2) log 1 + α r ∥A∥ 2 2 B 2 φ,A η log(2)
, and Φ is the normal CDF.

This result basically means that we are no longer obliged to follow optimistic value functions, the perturbed estimation is enough to have a tight bound on the learning error.

B.2.1 Stochastic optimism

The goal here is to show that by injecting our carefully designed noise in the rewards we can ensure optimism with a constant probability. Consider the optimal policy π ⋆ , we have:

(V θp , θr ,1 -V ⋆ θ p ,θ r ,1 )(s 1 ) ≥ (Q ⋆ θp , θr ,1 -Q ⋆ 1 )(s 1 , π ⋆ (s 1 )) ≥ V π ⋆ θp ,θ r (s 1 ) -V π ⋆ θ p ,θ r (s 1 ) first term + V π ⋆ θp , θr (s 1 ) -V π ⋆ θp ,θ r (s 1 ) second term + V π ⋆ θp , θr (s 1 ) -V π ⋆ θp , θr (s 1 ) third term
First term. By assumption, the expected reward under the true parameter satisfies

E θ r [r(s, a)] ∈ [0, 1], then S H t=1 E θ r [r(s t , π(s t ))] ≤ H.
Consequently, the first term can be controlled using Lemma 13

V π ⋆ θ p ,θ r (s 1 ) -V π ⋆ θp ,θ r (s 1 ) ≤ H KL(P θp (s 2 , . . . , s H ), P θ p (s 2 , . . . , s H )) ≤ H E (st) t∈[H] ∼ θp |s k 1 H t=1 ψ(s t+1 ) ⊤ M θp -θ p φ(s t , π ⋆ (s t )) + Z p θ p (s t , π ⋆ (s t )) -Z p θp (s t , π ⋆ (s t ))
Using Taylor's expansion, for all h ∈ [H], ∃θ h ∈ [θ p , θp ] such that:

E (st) t∈[H] ∼ θp |s k 1 ψ(s t+1 ) ⊤ M θp -θ p φ(s t , π ⋆ (s t )) + Z p θ p (s t , π ⋆ (s t )) -Z p θp (s t , π ⋆ (s t )) = 1 2 ( θp -θ p ) ⊤ E (st) t∈[H] ∼ θp |s k 1 ∇ 2 s h ,π ⋆ (s h ) Z p (θ h ) ( θp -θ p ) ≤ β p 2 E (st) t∈[H] ∼ θp |s k 1 ∥ θp -θ p ∥ 2 G sh ,π ⋆ (s h ) . Define u k def = H h=1 E (st) t∈[H] ∼ θp |s k 1 (A i φ(s h , π ⋆ (s h ))) i∈[d] , then V π ⋆ θ p ,θ r (s 1 ) -V π ⋆ θp ,θ r (s 1 ) ≤ H β p 2 H h=1 E (st) t∈[H] ∼ θp |s k 1 ∥ θp -θ p ∥ 2 G sh ,π ⋆ (s h ) ≤ H β p 2 θp -θ p H h=1 E (s t ) t∈[H] ∼ θp |s k 1 [Gs h ,π ⋆ (s h )] ≤ H β p 2 θp -θ p u k u ⊤ k ≤ H β p 2 ( Ḡp k ) -1/2 u k u ⊤ k ( Ḡp k ) -1/2 ∥ θp -θ p ∥ Ḡp k ≤ H β p 2 ∥u k ∥ ( Ḡp k ) -1 ∥ θp -θ p ∥ Ḡp k
The third line follows because ∀x ∈ R d , ∥x∥ i=1 aia ⊤ i ≤ ∥x∥ ( i=1 ai)( i=1 ai) ⊤ , and the last one follows because tr(AB) ≤ tr(A) tr(B) for any two real positive semi-definite matrices A and B. We deduce, with probability at least 1 -δ:

V π ⋆ θ p ,θ r (s 1 ) -V π ⋆ θp ,θ r (s 1 ) ≤ H β p β p (k, δ) α p H h=1 E (st) t∈[H] ∼ θp |s k 1 (A i φ(s h , π ⋆ (s h ))) i∈[d] ( Ḡp k ) -1
Second term. We have

V π ⋆ θp , θr (s 1 ) -V π ⋆ θp ,θ r (s 1 ) = E (st) t∈[H] ∼ θp |s k 1 H t=1 Var θ r t (r) 2 B ⊤ M θr -θ r φ(s t , π ⋆ (s t )) = ( θr -θ r ) ⊤ E (st) t∈[H] ∼ θp |s k 1 H t=1 Var θ r t (r) 2 (A i φ(s t , π ⋆ (s t ))) i∈[d] B ≤ √ β r 2 ∥ θr -θ r ∥ Ḡr k E (st) t∈[H] ∼ θp |s k 1 H t=1 (A i φ(s t , π ⋆ (s t ))) i∈[d] ( Ḡr k ) -1
The last inequality comes from Cauchy-Schwarz. Applying that the norm (sum) makes appear only symmetric matrices times the variances so that we can bound the latter by β r . We conclude that with probability at least 1 -δ,

V π ⋆ θp , θr (s 1 ) -V π ⋆ θp , θr (s 1 ) ≤ β r β r (k, δ) √ 2α r E (st) t∈[H] ∼ θp |s k 1 H t=1 (A i φ(s t , π ⋆ (s t ))) i∈[d] ( Ḡr k ) -1 V π θp , θr ,1 (s k 1 )-V π θp , θr +ξ k ,1 (s k 1 ) = E (s h ) 1≤h≤H ∼π| θp ,s k 1 H h=1 Var sh ,π(s h ) (r) 2 B ⊤ M θr -θr -ξ k φ(s h , π(s h )) ≤ E H h=1 Var sh ,π(s h ) (r) 2 ∥ θr -θr -ξ k ∥ Ḡp k ∥(B ⊤ A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡp k ) -1 ≤ ∥ θr -θr -ξ k ∥ Ḡp k E H h=1 Var sh ,π(s h ) (r) 2 ∥(B ⊤ A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡp k ) -1 ≤ ∥ ξk -ξ k ∥ Ḡp k β r 2 E H h=1 ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡp k ) -1
Then,

E ξk V π θp , θr ,1 (s k 1 )-V π θp , θr +ξ k ,1 (s k 1 ) ≤ β r 2 E ξk [∥ ξk -ξ k ∥ Ḡp k ]E (s h )∼π| θp H h=1 ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡp k ) -1 .
Also,

E ξ k | Ōc k [V θp , θr +ξ k ,1 (s k 1 )-V 1 (s k 1 )] ≤ β r 2 E ξk | Ōc k [∥ ξk -ξ k ∥ Ḡp k ]E (s h )∼π| θp H h=1 ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡp k ) -1 ≤ β r 2 E ξk [∥ ξk -ξ k ∥ Ḡp k ]E (s h )∼π| θp H h=1 ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡp k ) -1 .
We have a bound on the expected value of the sum of feature norms in the proof of Lemma 5. Also,

E ξk [∥ ξk -ξ k ∥ Ḡp k ] ≤ E ξk [∥ ξk ∥ Ḡp k ] + E ξk [∥ξ k ∥ Ḡp k ] ≤ E ξk [∥ ξk ∥ 2 Ḡp k ] + x k d log(d/δ) ≤ x k d + x k d log(d/δ)
The second line follows from Cauchy-Schwarz and by definition of ξ k . The last line is due to the fact that

x k ( Ḡp k ) -1 ∼ N (0, x k I d ), which implies ∥ ξk ∥ 2 Ḡp k ∼ N (0, dx k ).
We conclude the proof by taking the sum of feature norms from the proof of Lemma 5.

We conclude that with probability at least 1 -2δ:

K k=1 V ⋆ 1 (s k 1 ) -V θp , θr + ξk ,1 (s k 1 ) ≤ β r Φ(-1) ( x k d + x k d log(d/δ)) 3d log(2) log 1 + α r ∥A∥ 2 2 B 2 φ,A η log(2) 1 + α r B φ,A H η Hd log(1 + α r η -1 B φ,A H) + KHd log (1 + α r η -1 B φ,A HK) log(e/δ 2 ) C Concentrations C.

Concentration of the transition parameter

We recall the important concentration of the maximum likelihood estimator for general bilinear exponential families (cf. Theorem 1 of [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF]).

Theorem 7. Suppose {F t } ∞ t=0 is a filtration such that for each t, (i) s t+1 is F t -measurable, (ii) (s t , a t ) is F t-1 measurable, and (iii) given (s t , a t ) , s t+1 ∼ P p θ p (• | s t , a t ) according to the exponential family defined by Equation (1). Let θp (k) be the penalized MLE defined by Equation (5), and let Z p s,a (θ) be strictly convex in θ for all (s, a). Then, for any δ ∈ (0, 1], with probability at least 1 -δ, the following holds uniformly over all n ∈ N :

k t=1 KL st,at θp (k), θ p + η 2 θ p -θp (k) 2 A - η 2 ∥θ p ∥ 2 A ≤ log C p A,k δ , where C p A,k = R d exp -η 2 ∥θ ′ ∥ 2 A dθ ′ / R d exp - k t=1 KL st,at (θ k , θ ′ )-η 2 ∥θ ′ -θ k ∥ 2 A dθ ′ . Define G s,a def = φ(s, a) ⊤ A ⊤ i A j φ(s, a) i,j∈[d] ,
we have

C p A,k ≤ det I + β p η -1 A -1 k t=1 G st,at ,
where

β p = sup θ,s,a λ max C θ s,a [ψ (s ′ )] .
A proof of this result can be found in the work [START_REF] Sayak | Reinforcement learning in parametric mdps with exponential families[END_REF]. We provide an almost similar proof for the concentration of rewards in the next section.

Corollary 8. The previous theorem implies a simple euclidean confidence region. Indeed, with probability at least 1 -δ, for all k ∈ N

θ p -θp (k) 2 Ḡp n ≤ 2 α p β p (k, δ),
where

β p (k, δ) def = β p (k-1)H (δ) = 2 2 B 2 A + log 2C p A,k /δ .
Proof. The result follows from the following simple calculations:

1 2 θ p -θp (k) 2 Ḡk = (α p ) -1 η 2 θ p -θp (k) 2 A + k-1 τ =1 H h=1 1 2 θ p -θp (k) 2 G s τ h ,a τ h ≤ (α p ) -1 η 2 θ p -θp (k) 2 A + k-1 τ =1 H h=1 KL s τ h ,a τ h (θ k , θ) .

C.2 Concentration of the reward parameter (contribution)

Theorem 9. Suppose {F t } ∞ t=0 is a filtration such that for each t, (i) r(s t , a t ) is F t -measurable, (ii) (s t , a t ) is F t-1 measurable, and (iii) given (s t , a t ) , r(s t , a t ) ∼ P r θ r (• | s t , a t ) according to the exponential family defined by (2). Let θr (k) be the penalized MLE defined by Equation (7), and let Z r s,a (θ) be strictly convex in θ for all (s, a). Then, for any δ ∈ (0, 1], with probability at least 1 -δ, the following holds uniformly over all k ∈ N :

k t=1 KL st,at θr (k), θ r + η 2 θ r -θr (k) 2 A - η 2 ∥θ r ∥ 2 A ≤ log C r A,k δ , where C r A,k = R d exp -η 2 ∥θ ′ ∥ 2 A dθ ′ / R d exp - k t=1 KL st,at (θ k , θ ′ )-η 2 ∥θ ′ -θ k ∥ 2 A dθ ′ . Define G s,a def = φ(s, a) ⊤ A ⊤ i A j φ(s, a) i,j∈[d] , we have C A,k ≤ det I + β r η -1 A -1 k t=1 G st,at ,
where β r := ∥B∥ 2 2 sup θ,s,a Var θ s,a (r).

Proof. We proceed similar to the proof of Theorem 1 in [START_REF] Ray | Online learning in kernelized markov decision processes[END_REF].

Step 1: Martingale construction. First, observe that by assuming strict convexity, the log-partition function Z r s,a becomes a Legendre function. Now for the conditional exponential family model, the KL divergence between P r θ r (• | s, a) and P r θ ′r (• | s, a) can be expressed as a Bregman divergence associated to Z r s,a with the parameters reversed, i.e.

M λ n = exp λ ⊤ S n - n t=1 B Zn t ,a t ,θ r (λ)
where ∀i ≤ d, we denote

(S n ) i = n t=1 r (s t , a t ) -E θ r st,at [r] B ⊤ A i φ (s t , a t )
. Note that M λ n > 0 and it is F n -measurable. Furthermore, we have for all (s, a),

E θ r s,a exp d i=1 λ i r (s t , a t ) -E θ r st,at [r] B ⊤ A i φ (s t , a t ) = exp -λ ⊤ ∇Z r s,a (θ r ) S exp d i=1 (θ r i + λ i ) B ⊤ A i φ(s, a) -Z r s,a (θ r ) dr = exp Z r s,a (θ r + λ) -Z r s,a (θ r ) -λ ⊤ ∇Z r s,a (θ r ) = exp B Z r s,a (θ r ) This implies E exp λ ⊤ S n | F n-1 = exp λ ⊤ S n-1 + B Z nn ,an ,θ r (λ) thus E M λ n | F n-1 = M λ n-1 . Therefore M λ n ∞
n=0 is a non-negative martingale adapted to the filtration {F n } ∞ n=0 and actually satisfies E M λ n = 1. For any prior density q(θ) for θ, we now define a mixture of martingales

M n = R d M λ n q (θ r + λ) dλ (19) Then {M n } ∞ n=0 is also a non-negative martingale adapted to {F n } ∞ n=0 and in fact, E [M n ] = 1.
Step 2: Method of mixtures. Considering the prior density N (0, (ηA) -1 ), we obtain from ( 19) that

M n = c 0 R d exp λ ⊤ S n - n t=1 B Z r x t ,a t ,θ r (λ) - η 2 ∥θ r + λ∥ 2 A dλ, (20)
where

c 0 = 1 R d exp(-η 2 ∥θ ′ ∥ 2 Λ )dθ ′ . We now introduce the function Z r n (θ) = n t=1 Z r st,at (θ). Note that Z r
n is a also Legendre function and its associated Bregman divergence satisfies

B Z r n (θ ′ , θ) = n t=1 Z r st,at (θ ′ ) -Z r st,at (θ) -(θ ′ -θ) ⊤ ∇Z r St,at (θ) = n t=1 B Z r s t ,α t (θ ′ , θ)
Furthermore, we have

n t=1 B Z r s t ,α t ,θ r (λ) = B Z r n ,θ r (λ).
From the penalized likelihood formula (7), recall that

∀i ≤ d, n t=1 ∇ i Z r st,at θr (k) + η 2 ∇ i ∥ θr (k)∥ 2 A = k t=1 r t B ⊤ A i φ (s t , a t ) .
This yields

S k = k t=1 ∇Z r st,at θr (k) -∇Z r st,at (θ r ) + ηA θr (k) = ∇Z r k θr (k) -∇Z r k (θ r ) + ηA θr (k) (21)
We now obtain from (20) and ( 21) that

M k = c 0 • exp - η 2 ∥θ r ∥ 2 A R d exp λ ⊤ x k -B Z k ,θ * (λ) + g k (λ) dλ, (22)
where we introduced

g k (λ) = η 2 2λ ⊤ A θr (k) + ∥θ r ∥ 2 A -∥θ r + λ∥ 2 A and x k = ∇Z r k θr (k) - ∇Z r k (θ r ). Now, note that sup λ∈R d g k (λ) = η 2 θ r -θr (k) 2 A
, where the supremum is attained at λ ⋆ = θr (k)θ r . We then have

g k (λ) = g n (λ) + sup λ∈R ⋆ g k (λ) -g k (λ ⋆ ) = η 2 θr (k) -θ r 2 A + η (λ -λ ⋆ ) ⊤ A (θ r + λ ⋆ ) + η 2 ∥θ r + λ ⋆ ∥ 2 A - η 2 ∥θ r + λ∥ 2 A = B Z r 0 θ r , θr (k) + (λ -λ ⋆ ) ⊤ ∇Z r 0 (θ r + λ ⋆ ) + Z r 0 (θ r + λ ⋆ ) -Z r 0 (θ r + λ) (23)
where we have introduced the Legendre function Z r 0 (θ) = η 2 ∥θ∥ 2 A . We now have from (27) that sup

λ∈R d λ ⊤ x n -B Z r n ,θ r (λ) = B ⋆ Z r n ,θ r (x n ) = B ⋆ Z r n ,θ r ∇Z r n θr (n) -∇Z r n (θ r ) = B Z r n θ r , θr (n) .
Further, any optimal λ must satisfy

∇Z r n (θ r + λ) -∇Z r n (θ r ) = x n =⇒ ∇Z r n (θ r + λ) = ∇Z r n θr (n) .
One possible solution is λ = λ ⋆ . Now, since Z r n is strictly convex, the supremum is indeed attained at λ = λ ⋆ . We then have

λ ⊤ x n -B Z r n ,θ r (λ) = λ ⊤ x n -B Z r n ,θ r (λ) + B Z r n θ r , θr (n) -λ ⋆ x n -B Z r n ,θ r (λ ⋆ ) = B Z r n θ r , θr (n) + (λ -λ ⋆ ) ⊤ ∇Z r n (θ r + λ ⋆ ) + B Z r n ,θ * (λ ⋆ ) -B Z r n ,θ * (λ) -(λ -λ ⋆ ) ⊤ ∇Z r n (θ r ) = B Z r n θ r , θr (n) + (λ -λ ⋆ ) ⊤ ∇Z r n (θ r + λ ⋆ ) + Z r n (θ r + λ ⋆ ) -Z r n (θ r + λ) (24)
Plugging Equation (23) and Equation (24) in Equation ( 22), we obtain

M n = c 0 • exp   j∈{0,n} B Z r j (θ r , θ j ) - η 2 ∥θ r ∥ 2 A   × R d exp   j∈{0,n} (λ -λ ⋆ ) ⊤ ∇Z r j (θ r + λ ⋆ ) + Z r j (θ r + λ ⋆ ) -Z r j (θ r + λ)   dλ = c 0 • exp   j∈{0,n} B Z r j θ r , θr (n) - η 2 ∥θ r ∥ 2   × exp   - j∈{0,n} (θ r + λ ⋆ ) ⊤ ∇Z r j (θ r + λ ⋆ ) -Z r j (θ r + λ ⋆ )   × R d exp   j∈{0,n} (θ r + λ) ⊤ ∇Z r j (θ r + λ ⋆ ) -Z r j (θ r + λ)   dλ = c 0 c n exp   j∈{0,n} B Z r j θ r , θr (n) - η 2 ∥θ r ∥ 2 A   × R d exp j∈{0,n} (θ r + λ) ⊤ ∇Z r j (θ r + λ ⋆ ) -Z r j (θ r + λ) dλ R d exp j∈{0,n} (θ ′ ) ⊤ ∇Z r j (θ r + λ ⋆ ) -Z r j (θ ′ ) dθ ′ = c 0 c n • exp B Zn θ r , θr (n) + B Z0 θ r , θr (n) - η 2 ∥θ r ∥ 2 A ,
where we introduced c n = exp( j∈{0,n} ((θ r +λ * ) ⊤ ∇Z r j (θ r +λ * )-Z r j (θ r +λ * )))

R d exp( j∈{0,n} ((θ ′ ) ⊤ ∇Z r j (θ r +λ * )-Z r j (θ ′ )))dθ ′ . Since λ ⋆ = θr (n) -θ r , we have

c n = 1 R d exp -j∈{0,n} B Z r j (θ ′ , θ r + λ ⋆ ) dθ ′ = 1 R d exp - n t=1 B Zs t ,a t θ ′ , θr (n) -η 2 θ ′ -θr (n) 2 A ′ dθ ′
Therefore, we have from (5) that

C A,n := c n c 0 = R d exp -η 2 ∥θ ′ ∥ 2 A dθ ′ R d exp - n t=1 KL st,at θr (n), θ ′ -η 2 θ ′ -θr (n) 2 A dθ ′
An application of Markov's inequality now yields

P n t=1 KL st,at θr (n), θ r + η 2 θ r -θr (n) 2 A - η 2 ∥θ r ∥ 2 A ≥ log C A,n δ = P M n ≥ 1 δ ≤ δE [M n ] = δ
Step 3: A stopped martingale and its control. Let N be a stopping time with respect to the filtration {F n } ∞ n=0 . Now, by the martingale convergence theorem, M ∞ = lim n→∞ M n is almost surely well-defined, and thus M N is well-defined as well irrespective of whether N < ∞ or not. Let Q n = M min{N,n} be a stopped version of {M n } n . Then an application of Fatou's lemma yields

E [M N ] = E lim inf n→∞ Q n ≤ lim inf n→∞ E [Q n ] = lim inf n→∞ E M min{N,n} ≤ 1,
since the stopped martingale M min{N,n} n≥1 is also a martingale. Therefore, by the properties of M n , (12) also holds for any random stopping time N < ∞. To complete the proof, we now employ a random stopping time construction as in [START_REF] Abbasi | Regret bounds for the adaptive control of linear quadratic systems[END_REF] We define a random stopping time N by

N = min n ≥ 1 : n t=1 KL st,at θr (n), θ r + η 2 θ r -θr (n) 2 A - η 2 ∥θ r ∥ 2 A ≥ log C A , n δ
with min{∅} := ∞ by convention. We then have

P ∃n ≥ 1, n t=1 KL st,at θr (n), θ r + η 2 θ r -θr (n) 2 A - η 2 ∥θ r ∥ 2 A ≥ log C A,n δ = P[N < ∞] ≤ δ,
which concludes the proof of the first part.

Proof of second part: upper bound on C A,n . First, we have for some

θ ∈ θr (n), θ ′ ∞ that KL s,a θr (n), θ ′ = 1 2 d i,j=1 θ ′ -θr (n) i Var θ s,a (r)×φ(s, a) ⊤ A ⊤ i BB ⊤ A j φ(s, a) θ ′ -θr (n) j (25) Now (25) implies that n t=1 KL st,at θr (n), θ ′ ≤ β 2 n t=1 d i,j=1 θ ′ -θr (n) i φ (s t , a t ) ⊤ A ⊤ i A j φ (s t , a t ) θ ′ -θr (n) j = β r 2 θ ′ -θr (n) 2 n t=1
G st,at , where β r := λ max BB ⊤ × sup θ,s,a Var θ s,a (r) and ∀i, j ≤ d, (G s,a ) i,j := φ(s, a) ⊤ A ⊤ i A j φ(s, a). Therefore, we obtain

C A,n ≤ R d exp -η 2 ∥θ ′ ∥ 2 A dθ ′ R d exp -1 2 θ ′ -θr (n) 2 (β r n t=1 Gs t ,a t +ηA) dθ ′ = (2π) d/2 det(ηA) 1/2 × det (β r n t=1 G st,at + ηA) 1/2 (2π) d/2 = det I + β r η -1 A -1 n t=1
G st,at , which completes the proof of the second part.

Corollary 10. Here also, the theorem implies a euclidean control. With probability at least 1 -δ uniformly over k ∈ N θ rθr (k) Thanks to lower bounds on the error function, we have the following bound on the probability of anti-concentration Φ(-1) ≥ 1/(4 √ eπ).

2 Ḡr k ≤ 2 α r β r (k, δ), where β r (k, δ) def = β r (k-1)H (δ) = 2 2 B 2 A + log 2C r A,k /δ .

D Technical results

D.1 A transportation lemma

For any function f : X → R, we define its span as S(f ) := max x∈X f (x) -min x∈X f (x).

For a probability distribution P supported on the set X , let

E P [f ] := E P [f (X)] and V P [f ] := V P [f (X)] = E P f (X) 2 -E P [f (X)
] 2 denote the mean and variance of the random variable f (X), respectively. We now state the following transportation inequalities, which can be adapted from [START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF] (Lemma 4.18). Lemma 13. (Transportation inequalities) Assume f is such that S(f ) and V P [f ] are finite. Then it holds

∀Q ≪ P, E Q [f ] -E P [f ] ≤ 2V P [f ]KL(Q, P ) + 2S(f ) 3 KL(Q, P ) ∀Q ≪ P, E P [f ] -E Q [f ] ≤ 2V P [f ]KL(Q, P ) D.2 Bregman divergence
For a Legendre function F : R d → R, the Bregman divergence between θ ′ , θ ∈ R d associated with F is defined as

B F (θ ′ , θ) := F (θ ′ ) -F (θ) -(θ ′ -θ) ⊤ ∇F (θ)
. Now, for any fixed θ ∈ R d , we introduce the function

B F,θ (λ) := B F (θ + λ, λ) = F (θ + λ) -F (θ) -λ ⊤ ∇F (θ).
It then follows that B F,θ is a convex function, and we define its dual as

B ⋆ F,θ (x) = sup λ∈R d λ ⊤ x -B F,θ (λ)
We have for any θ, θ ′ ∈ R d :

B F (θ ′ , θ) = B ⋆ F,θ ′ (∇F (θ) -∇F (θ ′ )) (27)
To see this, we observe that

B ⋆ F,θ ′ (∇F (θ) -∇F (θ ′ )) = sup λ∈R d λ ⊤ (∇F (θ) -∇F (θ ′ )) -F (θ ′ + λ) -F (θ ′ ) -λ ⊤ ∇F (θ ′ ) = sup λ∈R d λ ⊤ ∇F (θ) -F (θ ′ + λ) + F (θ ′ ) .
Now an optimal λ must satisfy ∇F (θ) = ∇F (θ ′ + λ). One possible choice is λ = θ -θ ′ . Since, by definition, F is strictly convex, the supremum will indeed be attained at λ = θ -θ ′ . Plugin-in this value, we obtain

B ⋆ F,θ ′ (∇F (θ) -∇F (θ ′ )) = (θ -θ ′ ) ⊤ ∇F (θ) -F (θ) + F (θ ′ ) = B F (θ ′ , θ) .
Note that (27) holds for any convex function F . Only difference is that, in this case, B F (•, •) will not correspond to the Bregman divergence.

D.3 Properties of the bilinear exponential family

In this section, we detail some useful results related to exponential families in our model.

D.3.1 Derivatives

Lemma 14. (Gradients) We provide the derivatives of the log-partitions in closed form. As usual with exponential families, these are intimately linked to moments of the random variable. We have:

∇ i Z p s,a (θ) = E θ s,a [ψ (s ′ )] ⊤ A i φ(s, a).
And

∇ i Z r s,a (θ) = E θ s,a [r] B ⊤ A i φ(s, a).
Proof. We prove the lemma as follows

∇ i Z p s,a (θ) = S ψ (s ′ ) ⊤ A i φ(s, a) exp d i=1 θ i ψ (s ′ ) ⊤ A i φ(s, a) S exp d i=1 θ t ψ (s ′ ) ⊤ A i φ(s, a) ds ′ ds ′ = E θ s,a [ψ (s ′ )] ⊤ A i φ(s, a) ∇ i Z r s,a (θ) = S rB ⊤ A i φ(s, a) exp r d i=1 θ i B ⊤ A i φ(s, a) S exp r d i=1 θ i B ⊤ A i φ(s, a) dr dr = E θ s,a [r] B ⊤ A i φ(s, a)
Lemma 15. (Hessians) The entries of the Hessians of the log partition functions are given by

∇ 2 i,j Z p s,a (θ) = φ(s, a) ⊤ A ⊤ i C θ s,a [ψ (s ′ )] A j φ(s, a)
,

where C θ s,a [ψ (s ′ )] def = E θ s,a ψ (s ′ ) ψ (s ′ ) ⊤ -E θ s,a [ψ (s ′ )] E θ s,a ψ (s ′ ) ⊤ .
Similarly,

∇ 2 i,j Z r s,a (θ) = Var θ s,a (r) × φ(s, a) ⊤ A ⊤ i BB ⊤ A j φ(s, a),
where Var θ s,a (r)

def = E θ s,a r 2 -E θ s,a [r]
2 is the variance of the reward under θ.

Proof. We prove these formulas by differentiating under the integral sign.

∇ 2 i,j Z p s,a (θ) = S ψ (s ′ ) ⊤ A i φ(s, a)ψ (s ′ ) ⊤ A j φ(s, a) exp d i=1 θ i ψ (s ′ ) ⊤ A i φ(s, a) S exp d i=1 θ i ψ (s ′ ) ⊤ A i φ(s, a) ds ′ ds ′ - S ψ (s ′ ) ⊤ A i φ(s, a) exp d i=1 θ i ψ (s ′ ) ⊤ A i φ(s, a) S exp d i=1 θ i ψ (s ′ ) ⊤ A i φ(s, a) ds ′ ds ′ (∇ j Z s,a ) (θ) = E θ s,a ψ (s ′ ) ⊤ A i φ(s, a)ψ (s ′ ) ⊤ A j φ(s, a) -E θ s,a ψ (s ′ ) ⊤ A i φ(s, a) E θ s,a ψ (s ′ ) ⊤ A j φ(s, a) =φ(s, a) ⊤ A ⊤ i E θ s,a ψ (s ′ ) ψ (s ′ ) ⊤ -E θ s,a [ψ (s ′ )] E θ s,a ψ (s ′ ) ⊤ A j φ(s, a) =φ(s, a) ⊤ A ⊤ i C θ s,a [ψ (s ′ )] A j φ(s, a),
where we introduce in the last line the p × p covariance matrix given by

C θ s,a [ψ (s ′ )] = E θ s,a ψ (s ′ ) ψ (s ′ ) ⊤ -E θ s,a [ψ (s ′ )] E θ s,a ψ (s ′ ) ⊤
The proof of the form of the Hessian for the reward partition function follows the same steps as above.

Lemma 16. (KL Divergences) For any two θ, θ ′ and for some pair (s, a),

∃ θ ∈ [θ, θ ′ ] ∞ , KL (P p θ (• | s, a), P p θ ′ (• | s, a)) = 1 2 (θ -θ ′ ) ⊤ ∇ 2 Z p s,a ( θ) (θ -θ ′ ) , where [θ, θ ′ ] ∞ denotes the d-dimensional hypercube joining θ to θ ′ . Similarly ∃ θ ∈ [θ, θ ′ ] ∞ , KL (P r θ (• | s, a), P r θ ′ (• | s, a)) = 1 2 (θ -θ ′ ) ⊤ ∇ 2 Z r s,a ( θ) (θ -θ ′ ) .
Proof. We start by writing:

log P p θ (s ′ | s, a) P p θ ′ (s ′ | s, a) = d i=1 (θ i -θ ′ i ) ψ (s ′ ) ⊤ A i φ(s, a) -Z p s,a (θ) + Z p s,a (θ ′ ) , then KL (P p θ (• | s, a), P p θ ′ (• | s, a)) = d i=1 (θ i -θ ′ i ) E θ s,a [ψ (s ′ )] ⊤ A i φ(s, a) -Z p s,a (θ) + Z p s,a (θ ′ ) = 1 2 (θ -θ ′ ) ⊤ ∇ 2 Z p s,a ( θ) (θ -θ ′ )
, where in the last line, we used, by a Taylor expansion, that Z s,a (θ

′ ) = Z s,a (θ) + (∇Z s,a (θ)) ⊤ (θ ′ -θ) + 1 2 (θ-θ ′ ) ⊤ ∇ 2 Z s,a ( θ) (θ -θ ′ ) for some θ ∈ [θ, θ ′ ] ∞ .
The proof of the form of the KL divergence for the reward follows the same steps as above.

D.3.2 A transportation lemma for rewards

Lemma 17. We provide a closed-form formula for the difference of expected rewards under two distinct parameters:

∃θ 3 ∈ [θ 1 , θ 2 ], E θ1 s,a [r] = E θ2 s,a [r] + Var θ3 s,a (r) 2 B ⊤ M θ1-θ2 φ(s, a)
Proof. Let's recall the gradient of the reward log partition function:

∇ i Z r s,a (θ r ) = E θ r s,a [r] B ⊤ A i φ(s, a
) then for all θ r′ we have:

E θ r s,a [r] = 1 B ⊤ M θ r′ φ(s, a) ∇ i Z r s,a (θ r ) ⊤ θ r′
Let θ 1 , θ 2 ∈ R d , using Taylor-Cauchy's formula there exists θ 3 ∈ [θ 1 , θ 2 ] such that:

E θ1 s,a [r] = E θ2 s,a [r] + 1 2B ⊤ M θ r′ φ(s, a) (θ 1 -θ 2 ) ⊤ ∇ 2 Z r s,a (θ 3 ) ⊤ θ r′
We know that ∇ 2 i,j Z r s,a (θ) = Var θ s,a (r) × φ(s, a) ⊤ A ⊤ i BB ⊤ A j φ(s, a), choosing θ r′ = θ 1 -θ 2 we find:

E θ1 s,a [r] = E θ2 s,a [r] + Var θ3 s,a (r) 2 B ⊤ M θ1-θ2 φ(s, a).

D.4 Elliptical potentials and elliptical lemma D.4.1 Elliptical lemma

Here we show a lemma that is popular for regret control in linear MDPs and linear Bandits.

First, consider the notations: G s,a := (φ(s, a)

⊤ A ⊤ i A j φ(s, a)) 1≤i,j≤d , Ḡe n ≡ Ḡe (k-1)H := G n + (α e ) -1 ηA , and G n ≡ G (k-1)H := k-1 τ =1 H h=1 G s τ s ,a τ h .
Where e represents either r or p, we omit the superscript e w.l.o.g in the rest of this section. Lemma 18. (Elliptical lemma and variant for bounded potentials) Let c ∈ R + , we can bound the sum of feature norms as follows

T t=1 min{c, H h=1 Ḡ-1/2 n G s,a Ḡ-1/2 n } ≤ c log(1 + c) d log 1 + αη -1 B φ,A n .
where B φ,A := sup s,a A -1 G s,a .

Further, we have

T t=1 H h=1 Ḡ-1/2 n G s,a Ḡ-1/2 n ≤ 2d log 1 + αη -1 B φ,A n + 3dH log(2) log 1 + α∥A∥ 2 2 B 2 φ,A η log(2) Proof. First we have ∥ Ḡ-1/2 n G s,a Ḡ-1/2 n ∥ = tr( Ḡ-1/2 n G s,a Ḡ-1/2 n Ḡ-1/2 n G s,a Ḡ-1/2 n ) ≤ tr( Ḡ-1/2 n G s,a Ḡ-1/2 n ) = tr( Ḡ-1 n G s,a ) = tr(a ⊤ h Ḡ-1 n a h ) the last line is because G s,a = a h a ⊤ h , where a h = (A i φ(s h , a h )) i∈[d] . First result. Consider h ∈ [H], denote (λ h,i )i ∈ [d] the eigenvalues of a ⊤ h Ḡ-1 n a h . Ḡn is positive definite hence λ h,i > 0, ∀h, i, then min{c, H h=1 tr(a ⊤ h Ḡ-1 n a h )} = min{c, H h=1 d i=1 λ h,i } ≤ c log(1 + c) H h=1 d i=1 log(1 + λ h,i ) (log is concave) ≤ c log(1 + c) H h=1 log( d i=1 1 + λ h,i ) = c log(1 + c) H h=1 log det(I + a ⊤ h Ḡ-1 n a h ) ≤ c log(1 + c) log det( Ḡn + H h=1 G s h ,a h ) det( Ḡn )
where the last line follows from the matrix determinant lemma:

det Ḡn + a h a ⊤ h = det(I + a ⊤ h Ḡ-1 n a h ) det( Ḡn ) Therefore: T t=1 min{c, H h=1 Ḡ-1 n G s t h ,a t h } ≤ c log(1 + c)
det Ḡ0 = log det ḠN det ((α p ) -1 ηA) = log det I + αη -1 A -1 G N ≤ d log 1 + α p η -1 d tr A -1 G n (Trace-determinant (or AM-GM) inequality) ≤ d log 1 + α p η -1 B φ,A n
This concludes the proof of the first result.

Second result. First, we have sup s,a ∥G s,a ∥ 2 ≤ ∥A∥ 2 B φ,A .

Fix an episode k ∈ [K], n = (k -1)H, using Lemma 19, we know that the number of times

h ∈ [h] such that Ḡ-1 n G s h ,a h ≥ 1 is smaller than 3d log(2) log 1 + α(∥A∥2B φ,A ) 2 η log(2)
. Let us call

T k := {h ∈ [H] Ḡ-1 (k-1)h G s h ,a h ≤ 1}, then T t=1 H h=1 Ḡ-1 n G s t h ,a t h ≤ 3d log(2) log 1 + α∥A∥ 2 2 B 2 φ,A η log(2) + h∈T k min{1, Ḡ-1 n G s t h ,a t h }
the sum of the right hand side is similar to the first result. Although the sum is not contiguous, the previous bound holds since if h 1 < h 2 , det( Ḡn+h1 ) ≤ det( Ḡn+h2 ), this concludes the proof.

Remark 8. We can also write from the lemma in terms of ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k ) -1 by skipping the norm upper bound at the beginning of the proof: Proof. Let T be the set of rounds t when ∥a t ∥ V -1 t-1 ≥ 1 and G t = V 0 + t s=1 I T (s)a s a ⊤ s . Then

T t=1 min{c, H h=1 ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k ) -1 } ≤ c log(1 + c) d log 1 + αη -1 B φ,A n . and T t=1 H h=1 ∥(A i φ(s h , π(s h ))) 1≤i≤d ∥ ( Ḡr k ) -1 ≤2d log 1 + αη -1 B φ,A n + 3dH log(2) log 1 + α∥A∥ 2 2 B 2 φ,A η
dλ + |T |L 2 d d ≥ trace (G n ) d d ≥ det (G n ) (Trace-determinant inequality) = det (V 0 ) t∈T 1 + ∥a t ∥ 2 G -1 t-1 ≥ det (V 0 ) t∈T 1 + ∥a t ∥ 2 V -1 t-1 ≥ λ d 2 |T |
where the third line follows from the matrix determinant lemma:

det Ḡn + a h a ⊤ h = det(I + a ⊤ Notice that this provides an alternative approach to decompose the transition kernel and obtain linearity of the value function. Moreover, since ∀x, w ∈ R d , b ∈ R, |f (x, w, b)| ≤ √ 2, we can use Hoeffding's inequality to prove that a Monte-Carlo approximation of P(s ′ | s, a, θ) using N sample pairs of (w, b) guarantees an error smaller than ϵ with probability at least 1 -2 exp(-N ϵ 2 /4).

[RR07] proves a stronger result: it provides an algorithm approximating the Gaussian kernel for which the following uniform convergence bound holds. Lemma 20. Let M be a compact subset of R p with diameter diam(M). Then, using the explicit mapping z defined in Algorithm 1 in [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF] with N samples, we have Pr sup Application to planning in BEF-RLSVI. Since our regret analysis is done under the high probability event of bounded estimation parameters, we know that the spaces of ψ(s ′ ) and M θ φ(s, a) are bounded and the diameter depends on the dimensions. We abstain from explicating the exact diameter as it only influences the number of samples logarithmically. Using N ≈ p/ϵ 2 samples, we can construct a uniform ϵ-approximation of P(s ′ | s, a, θ).

Let's call Vh the estimated value function using Algorithm 3 with the above approximation of transition. Here, we elucidate the span of this estimation of value function. First we have:

V π H -V π H = s ′ ( P -P )(s ′ | s, a)r(s ′ , π(s ′ )) ds ′ ≤ ϵdH 3/2
Here, we use the facts that S V θ, θx ,h ≤ dH 3/2 (cf. Section B.2) and the error in approximating P is bounded by ϵ, i.e. sup s ′ ,s,a |( P -P )(s ′ |s, a)| ≤ ϵ.

Assume that at step h + 1, we have V π h+1 -V π h+1 ≤ h+1 j=1 ϵ j α h+1,j . Then, we obtain ϵ j (α h+1,j-1 + α h+1,j ) + ϵ h+2 α h+1,h+1

V π h -V π h ≤
Using the fact that α 1,1 = dH 3/2 and with a proper induction, we find that:

V π 1 -V π 1 ≤ ϵdH 5/2 1 -ϵ H-h 1 -ϵ ≤ H→∞ ϵdH 5/2
This concludes the proof of the arguments provided in § Planning of Section 4. This means that the extra regret due to planning with the approximation by RFT features is of order O(ϵdH 5/2 K).

By choosing an ϵ of order 1/(H √ K), we deduce that approximating the probability kernel with O(pH 2 K) samples induces a tractable planning procedure without harming the regret. Remark 9. The reader might be tempted to combine the finite approximation using RFT with algorithms from the linear reinforcement learning literature [START_REF] Jin | Provably efficient reinforcement learning with linear function approximation[END_REF]. However, note that the dimensionality of the linear space induced by RFT is polynomial in H and K. Consequently, applying algorithms designed with the assumption of linear value function incurs a linear regret.

F Tractable Maximum Likelihood estimation

The maximum likelihood estimation is explicit for simple distributions like the Gaussian [START_REF] Gerald | Explicit maximum likelihood estimators for certain patterned covariance matrices[END_REF] and for Linearly controlled dynamical systems. But it requires integral approximations for generic transitions. However, we believe that this estimation problem is far simpler than the planning problem since the latter traditionally involves approximating an integral for all state-action pairs. Different approximation techniques have been used in literature to handle the penalized ML estimation. For instance, Integral Approximation techniques are well studied for this problem. Indeed, [START_REF] Radford | Annealed importance sampling[END_REF] proposes to handle the ML estimation using simulated annealing, a method that starts from a tractable distribution and updates it to resemble the distribution at hand. [START_REF] Vembu | Probabilistic structured predictors[END_REF] proposes MCMC techniques for approximating the partition function. [START_REF] Miguel A Carreira-Perpinan | On contrastive divergence learning[END_REF] shows that optimizing a different objective, called the contrastive divergence leads to a good approximation of the ML. Another line of work is related to Score matching, a technique that avoids approximating the partition function and is well studied in literature, see [START_REF] Jørgensen | Maximum likelihood estimation and large-sample inference for generalized linear and nonlinear regression models[END_REF]. More recently, [LLS + 21] proposed an adaptation of this technique to the exact setting we consider. The latter shows that under certain conditions, that we are unable to verify, the estimation can be solved in O(d 3 ) time. Furthermore, in the case of Bounded distribution support and natural parameter, [START_REF] Shah | A computationally efficient method for learning exponential family distributions[END_REF] shows that for a minimally represented k-parameter Exponential family, an α-approximation of the ML can be derived in O(poly(k/α)) time. The latter assumes a specific definition of compactness of the representation as well as knowledge of the support and shows how to re-parameterize the density to a specific class of exponential families that are easier to study. Finally, [DDG + 19] studies exponential families such that the natural parameter belongs to an RKHS, it proposes a method that improves over score matching in time and in memory complexity.

  C Concentrations C.1 Concentration of the transition parameter . . . . . . . . . . . . . . . . . . . . . C.2 Concentration of the reward parameter (contribution) . . . . . . . . . . . . . . . Step 1: Martingale construction. . . . . . . . . . . . . . . . . . . . . . Step 2: Method of mixtures. . . . . . . . . . . . . . . . . . . . . . . . . Step 3: A stopped martingale and its control. . . . . . . . . . . . . . . . C.3 Gaussian concentration and anti-concentration . . . . . . . . . . . . . . . . . . D Technical results D.1 A transportation lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Bregman divergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.3 Properties of the bilinear exponential family . . . . . . . . . . . . . . . . . . . D.3.1 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.3.2 A transportation lemma for rewards . . . . . . . . . . . . . . . . . . . . D.4 Elliptical potentials and elliptical lemma . . . . . . . . . . . . . . . . . . . . . D.4.1 Elliptical lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.4.2 Elliptical potentials: finite number of large feature norms (contribution) . E Tractable planning with random Fourier transform F Tractable Maximum Likelihood estimation

==

  state at time h of episode k, denoted s h when k is clear from context a k h def = action at time h of episode k, denoted a h when k is clear from context r(s, a) def = realization of the reward in state s under action a θ p def = parameter of the transition distribution, ∈ R d θ r def = parameter of the reward distribution, ∈ R d θ def = ∈ R d denotes either θ r or θ p , unless stated otherwise θ def = θ estimator with Maximum Likelihood unless stated otherwise θ def = θ + ξ where ξ is a chosen noise. Perturbed estimation of θ. [θ 1 , θ 2 ] def = the d-dimensional ℓ ∞ hypercube joining θ 1 and θ 2 P θ p def = transition under the exponential family model with parameter θ p ψ def = feature function, ∈ (R p + ) S φ def = feature function, ∈ (R q + ) S×A B def = p-dimensional vector M θ def = d i=1 θ i A i , where A i are p × q matrices. Z r def = the rewards' log partition function Z p def = the transitions' log partition function H def Hilbert space where we decompose transitions µ p def = feature function after decomposition, ∈ (R + ) S×H ϕ p def = feature function after decomposition, ∈

  KL s,a (θ r , θ r′ ) := KL (P θ r (• | s, a), P θ r′ (• | s, a)) = B Zs,a (θ r′ , θ r ) . Now, for any λ ∈ R d , we introduce the function B Zn,α,θ r (λ) = B Zn,α (θ r + λ, λ) and define

C. 3

 3 Gaussian concentration and anti-concentrationLemma 11 (Gaussian concentration, ref. Appendix A in [AL17]). Let ξ tk ∼ N (0, Hν k (δ)Σ -1 tk ). For any δ > 0, with probability 1 -δ ∥ξ tk ∥ Σ tk ≤ c Hdν k (δ) log(d/δ)(26) for some absolute constant c. Lemma 12 (Gaussian anti-concentration, ref. Appendix A in[START_REF] Abeille | Linear thompson sampling revisited[END_REF]). Let ξ ∼ N (0, I d ), for any u ∈ R d with ∥u∥ = 1, we have: P(u ⊤ ξ ≥ 1) ≥ Φ(-1), where Φ is the normal CDF.

E

  Abbreviate x = d/ log(2) and y = L 2 /dλ, which are both positive. Thenx log(1 + y(3x log(1 + xy))) ≤ x log 1 + 3x 2 y 2 ≤ x log(1 + xy) 3 = 3x log(1 + xy). Since z -x log(1 + yz) is decreasing for z ≥ 3x log(1 + xy) it follows that |T | ≤ 3x log(1 + xy) = 3d log(2) log 1 + L 2 λ log(2).

  x,y∈M|z(x) ′ z(y) -k(y, x)| ≥ ϵ ≤ 2 8 σ p diam(M) ϵ 2 exp -N ϵ 2 4(p + 2) where σ 2 p ≡ E p [ω ′ ω]is the second moment of the Fourier transform of k.Further, it implies that if N = Ω p ϵ 2 log σp diam(M) ϵ, then sup x,y∈M |z(x) ′ z(y) -k(y, x)| ≤ ϵ with constant probability.

  P )(s ′ | s, a) V π h+1 (s ′ ) ds ′ + s ′ P (s ′ | s, a)( V π h+1 -V π h+1 )(s ′ ) ds ′ = s ′ ( P -P )(s ′ | s, a)(V π h+1 + V π h+1 -V π h+1 ) ds ′ + s ′ P (s ′ | s, a)( V π h+1 -V π h+1 )(s ′ ) ds ′ ≤ ϵ(dH 3/2 + h+1 j=1 ϵ j α h+1,j ) + h+1 j=1 ϵ j α h+1,j ≤ ϵ(dH 3/2 + α h+1,1 ) + h+1 j=2

  Our work extends the endeavor of using functional representations for regret minimization in continuous state-action MDPs. Now, we posit our contributions in existing literature.Kernel value function representation. [AJS + 20] studies MDPs with a linear mixtures model then extends to an RKHS setting, this generalizes our work and that of[START_REF] Yang | Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound[END_REF]. However, the paper proposes an Eluder-dimension analysis, for RKHS settings this leads to the result of[START_REF] Yang | Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound[END_REF], i.e.

a regret H log(T ) d higher than for BEF-RLSVI.Recently,

[START_REF] Huang | A short note on the relationship of information gain and eluder dimension[END_REF]

shows that for RKHS, Eluder dimension and the information gain are strictly equivalent, which brings in the extra factor.

General functional representation. The Eluder dimension is a complexity measure often used to analyze RL with general function space,

[START_REF] Huang | A short note on the relationship of information gain and eluder dimension[END_REF]

asserts that "common examples of where it is known to be small are function spaces (vector spaces)". [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 as a regularizer to induce exploration. Thus, the analysis cannot address episodic RL, where we have to explicitly ensure exploration with optimism. In the episodic setting,

[START_REF] Wang | Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension[END_REF]

leverage the UCB approach for tabular MDPs and function spaces with bounded Eluder dimension, this strategy achieves a and achieve a Õ √ d 4 H 2 T regret for linear MDPs. [ICN + 21] considers the same setting, proposes an RLSVI based algorithm, and achieves a Õ(

  Estimation error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1.1 Transition estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1.2 Reward estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Learning error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2.1 Stochastic optimism . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2.2 Controlling the learning error . . . . . . . . . . . . . . . . . . . . . . . Upper bound on V ⋆ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lower bound on V θp , θr . . . . . . . . . . . . . . . . . . . . . . . . . . . Combining the error bounds. . . . . . . . . . . . . . . . . . . . . . . .

	Table of Contents
	A Notations
	B Regret analysis
	B.1

Table 2 :

 2 Notations

  We can now control the R.H.S. of the above equation, as

									T t=1	log	det Ḡn+H det Ḡn	,
	T t=1	log	det Ḡn+H det Ḡn	=	T t=1	log	det ḠtH det Ḡ(t-1)H	= log	det ḠT H

  = λI and a 1 , . . . , a n ∈ R d×p be a sequence of matrices with∥a t ∥ 2 ≤ L for all t ∈ [n]. Let V t = V 0 + t s=1 a s a ⊤ s , then {t ∈ N * , ∥a t ∥ V -1

					log(2)
	D.4.2 Elliptical potentials: finite number of large feature norms (contribution)
	Lemma 19. (Worst case elliptical potentials, adaptation of Exercise 19.3 [LS20] for matrices) Let
	V 0 t-1	≥ 1} ≤	3d log(2)	log 1 +	L 2 λ log(2)

By tractable planning, we mean having a planner with (pseudo-)polynomial complexity in the problem parameters, i.e. dimension of parameters, dimension of features, horizon, and number of episodes.

Acknowledgments and Disclosure of Funding

The authors acknowledge the funding of the French National Research Agency, the French Ministry of Higher Education and Research, Inria, the MEL and the I-Site ULNE regarding project R-PILOTE-19-004-APPRENF. R. Ouhamma also acknowledges support from Ecole polytechnique.

We want to write all the norms in the same matrix. Therefore, with probability at least 1 -δ, V π ⋆ θp , θr (s 1 ) -V π ⋆ θp , θr (s 1 ) ≤

Third term. We have

Given the normal CDF Φ, we obtain that with probability at least Φ(-1)

and using Lemma 12, we find that the perturbed value function is optimistic with probability at least Φ(-1).

B.2.2 Controlling the learning error

In this section we see the core difference with optimistic algorithms. On the one hand, optimistic approaches require the value function generating the agent's policy to be larger than the optimal one with large probability, and can therefore ensure that the learning error is negative. On the other hand, BEF-RLSVI only ensures that the value function is optimistic with a constant probability: intuitively when this event holds the learning happens, and if it does not then the policy is still close to a good one thanks to the decreasing estimation error.

. Define the optimism event at episode k:

we know that P( Ōk ) ≥ Φ(-1). This event provides the upper bound:

Lower bound on V θp , θr . We define this bound with an optimization problem under concentration of the noise. Consider V 1 (s k 1 ) is the solution of min

Combining the error bounds. Combining the upper bound of Equation ( 16) with the lower bound of Equation ( 18), we get, with probability at least 1 -δ:

Also, using the tower rule,

)]P( Ōc k ) /P( Ōk ).

The last line follows since ξ k and ξk are i.i.d.

The rest of the analysis proceeds similarly to the proof of the reward estimation.

Let us call the argument of the minimum in Equation ( 17) as ξ k . Using Lemma 17, we find