0.0.1 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 [1].

Episodic RL. In this paper, we consider the episodic finite-horizon MDP formulation of RL, in short Episodic RL [2]–[4]. Episodic RL is a tuple \(\mathcal{M}= \langle \mathcal{S}, \mathcal{A}, \mathbb{P}, r, K, H \rangle\), where the state (resp. action) space \(\mathcal{S}\) (resp. \(\mathcal{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_1^k\). Then, for \(t=1,\ldots H\), the agent draws action \(a_t^k\) from a (possibly time-dependent) policy \(\pi_t(s_t^k)\), observes the reward \(r(s_t^k,a_t^k) \in [0,1]\), and transits to a state \(s_{t+1}^k \sim \mathbb{P}(.\mid s_t^k,a_t^k)\) according to the transition function \(\mathbb{P}\). The performance of a policy \(\pi\) is measured by the total expected reward \(V_{1}^\pi\) starting from a state \(s\in \mathcal{S}\), the value function and the state-action value functions at step \(h\in [H]\) are defined as \[V_h^\pi (s) \stackrel{\rm def}{=}\mathbb{E}\left[\sum_{t=h}^H r(s_t,a_t) \mid s_h =s \right], \quad\text{and}\quad Q_h^\pi (s,a) \stackrel{\rm def}{=}\mathbb{E}\left[\sum_{t=h}^H r(s_t,a_t) \mid s_h =s, a_h=a \right].\] 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 \[\mathcal{R}(K) \triangleq \sum_{k=1}^K \left(V_{1}^{\pi^\star}(s_1^k)-V_{1}^{\pi_t}(s_1^k) \right).\]

Key Challenges. The first key challenge in episodic RL is to tackle the exploration–exploitation trade-off. This is traditionally addressed with the optimism principle that either carefully crafts optimistic upper bounds on the value (or state-action value) functions [3], or maintains a posterior on the parameters to perform posterior sampling [2], or perturbs the value (or state-action value) function estimates with calibrated noise [5]. 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 high-dimensional posterior. Thus, we focus on extending the third approach of Randomized Least-Square Value Iteration (RLSVI)* framework, and inject noise only in rewards to perform tractable exploration.*

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 [6], bilinear [7], and bilinear exponential families [8], 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 [7]–[10]. The bilinear exponential family model is of special interest as it is expressive enough to represent tabular MDPs (discrete state-action), factored MDPs [11] and linearly controlled dynamical systems (such as Linear Quadratic Regulators [12]) as special cases [8]. 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 planning² given the perturbation for exploration and the model class. Existing work [8], [13] 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 \(\int \mathbb{P}(s'\mid 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. [14] asks when misspecified linear representations are enough for a polynomial sample complexity in several settings. [15]–[17] 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:

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

2. Algorithm: We propose an algorithm BEF-RLSVI that extends the RLSVI framework to bilinear exponential families (see Section 0.0.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 0.0.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.

3. Analysis: We carefully develop an analysis of BEF-RLSVI that yields \(\tilde{ \text{\usefont{OMS}{cmsy}{m}{n}O}}(\sqrt{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 \(\sqrt{H}\) (Section 0.0.3.2). Our analysis (Section 0.0.5) builds on existing analyses of RLSVI-type algorithms [5], but contrary to them, we remove the need to handcraft a clipping of the value functions [18]. 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 \(\sqrt{H}\) factor compared to [19], 2) Leveraging the observation that true value functions are bounded enables using an improved elliptical lemma (compared to [8]), 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 \(\sqrt{d}\) factor from the regret compared to [18].

0.0.2 Bilinear exponential family of MDPs↩︎

In this section, we introduce the bilinear exponential family (BEF) model coined in [8], 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, \[\begin{align} \tag{1} \mathbb{P}\left(\tilde{s} \mid s,a\right) &= \exp\left(\psi (\tilde{s})^\top M_{\theta^{\texttt{p}}}\varphi(s,a) - Z_{s,a}^\texttt{p}(\theta^{\texttt{p}})\right),\\ \mathbb{P}\left(r \mid s,a\right) &= \exp\left(r\: B^\top M_{\theta^{\texttt{r}}}\varphi(s,a) - Z_{s,a}^\texttt{r}(\theta^{\texttt{r}})\right), \tag{2} \end{align}\] where \(\varphi \in (\mathbb{R}_{+}^{q})^{\mathcal{S}\times \mathcal{A}}\) and \(\psi \in (\mathbb{R}_{+}^{p})^{\mathcal{S}}\) are known feature mappings, and \(B \in \mathbb{R}^p\) is a known matrix. The reward and transition parameters are \(\theta^{\texttt{p}}, \theta^{\texttt{r}}\in \mathbb{R}^d\). \(M_{\theta^{\cdot}} \stackrel{\rm def}{=}\sum_{i=1}^d \theta_i^{\cdot} A_i\), where \((A_i)_{1\le i\le d}\) are known matrices. The log partition function: \(\quad Z^{\texttt{p}}_{s,a}(\theta^{\texttt{p}}) \stackrel{\rm def}{=}\log \int_{\mathcal{S}} \exp\left(\psi(\tilde{s})^\top M_{\theta^{\texttt{p}}} \varphi(s,a)\right)d\tilde{s}, \quad\) and \(Z^{\texttt{r}}\) is defined similarly. Finally, we emphasize a minor difference with the original BEF model: like [9], we omit a base measure of the form \(h(s,\tilde{s},a)\) from the model, note that all the examples provided in [8] still hold with this slight restriction.

We denote \(V_{\theta^{\texttt{p}},\theta^{\texttt{r}},h}^\pi\), respectively \(Q_{\theta^{\texttt{p}},\theta^{\texttt{r}},h}^\pi\), the value, respectively state-action value function for policy \(\pi\) in the MDP parameterized by \((\theta^{\texttt{p}},\theta^{\texttt{r}})\) at time \(h\). A policy \(\pi^\star\) is optimal if for all \(s\in \mathcal{S},\: V_{\theta,h}^{\pi^\star}(s) = \max\limits_{\pi \in \Pi} V_{\theta,h}^{\pi}(s)\). A learning algorithm minimizes the (pseudo-)regret defined as: \[\label{def:regret} \mathcal{R}(K) \triangleq \sum_{k=1}^K \left(V_{\theta,1}^{\pi^\star}(s_1^k)-V_{\theta,1}^{\pi^t}(s_1^k) \right).\tag{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 \psi\left(s^{\prime}\right)^{\top} M_{\theta^{\texttt{p}}} \varphi(s, a) = -\|(\psi(s^{\prime}) - M_{\theta^{\texttt{p}}}\varphi(s, a)\|^2 + \|\psi(s')\|^2+\|M_{\theta^{\texttt{p}}}\varphi(s,a)\|^2.\] Notice that the quadratic term resembles the Radial Basis Function (RBF) kernel. More precisely, for an RBF kernel with covariance \(\Sigma \!=\! I_p\) and \(k(x,y) \!\stackrel{\rm def}{=}\! \exp\left(-\|x-y\|^2 /2\right)\), we find

\[\label{eq:linear95transition} \mathbb{P}\left(s^{\prime} \mid s, a\right) = \langle \phi^{\texttt{p}}(s,a), \mu^{\texttt{p}}(s') \rangle_{\mathcal{H}},\tag{4}\]

where \(\mathcal{H}\) is the RKHS associated with the kernel, \(\mu^{\texttt{p}}(s') = (2\pi)^{-p/2} \: k\left(\psi(s'),.\right) \: \exp\left(\|\psi\left(s^{\prime}\right)\|^2 /2\right)\), and \(\phi^{\texttt{p}}(s,a) = k\left(M_{\theta^{\texttt{p}}}^\top \varphi(s,a),.\right) \: \exp\left(\|M_{\theta^{\texttt{p}}} \varphi(s, a) \|^2 /2 -Z_{s,a}(\theta^{\texttt{p}}) \right)\). Equation 4 shows that \(s'\) is decoupled from \((s,a)\), we see hereafter why this is crucial to reducing the complexity of planning.

Importance of linearity. To understand the planning challenge in RL, recall the Bellman equation: \[Q_h^\pi(s,a) = r(s,a) + \int_{\tilde{s}\in \mathcal{S}} P(s'\mid s,a) V_{h+1}^\pi(\tilde{s}) d \tilde{s},\] We must approximate the integral at the R.H.S.for \((s,a) \in \mathcal{S}\times \mathcal{A}\). For a tabular MDP with \(|S|\) states and \(|A|\) actions, we need to evaluate \((Q_h^\pi)_{h\in [H]}\), i.e. to approximate \(|S| \times |A| \times H\) integrals per episode, which can be very expensive. However, with the linear transition model of Equation 4 , although \(\phi^{\texttt{p}}\) and \(\mu^{\texttt{p}}\) are infinite dimensional, we show in Section 0.0.4 (§ planning) that the planning complexity becomes polynomial in the problem parameters.

0.0.3 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.

0.0.3.1 BEF-RLSVI: algorithm design

BEF-RLSVI is based on RLSVI [5] 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.

We can see that Algorithm 1 performs exploration by a Gaussian perturbation of the reward parameter (Line [alg951:line954]). Contrary to optimistic approaches, this method is explicit and also more efficient since it does not a involve high-dimensional optimization.

We can approximate Line [alg952:planning] of Algorithm 2 with \(\text{\usefont{OMS}{cmsy}{m}{n}O}(p H^3 K\log(H K))\) complexity and without harming the learning process (cf. § planning, Section 0.0.4). Therefore, here, planning is tractable.

0.0.3.2 BEF-RLSVI: regret upper-bound

We state the standard smoothness assumptions on the model [8], [23], [24].

A closer look at the derivatives of the model (see Appendix 1.0.4.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 1 entails a regret \(\mathcal{R}(K) = \text{\usefont{OMS}{cmsy}{m}{n}O}(\sqrt{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 [8] 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 \(\widetilde{O}(\sqrt{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 [sec:planning]). Moreover, we improve the regret bound by a \(\sqrt{H}\) factor thanks to an improved analysis, (cf. Lemma 12). But similar to all RLSVI-type algorithms, we pick up an extra \(\sqrt{d}\) (cf.  [25]).

[18] 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) = \widetilde{O}(\sqrt{d^4 H^5 K})\), which is larger than that of BEF-RLSVI by \(O(\sqrt{d H^2})\). In algorithm design, we improve on their work by removing the need to carefully clip the value function. Analytically, our model allows us to use transportation inequalities (cf. Lemma 7) instead of the simulation lemma, which saves us a \(\sqrt{H}\) factor.

[19] considers Gaussian transitions, i.e. \(s^{\prime}=f^{*}(s, a)+\epsilon\) such that \(\epsilon \sim \mathcal{N}\left(0, \sigma^{2}\right)\). This is a particular case of our model. They propose to use Thompson Sampling, and have the merit of being the first to have observed linearity of the value function from this transition structure. But they do not connect it to the finite dimensional approximation of [26] unlike us (Section 0.0.4). Finally, they show a Bayesian regret bound of \(O(\sqrt{d^2 H^3 K})\). This notion of regret is weaker than frequentist regret, hence this result is not directly comparable with Theorem 1.

Tightness of regret bound. A lower bound for episodic RL with continuous state-action spaces is still missing. However, for tabular RL, [27] proves a lower bound of order \(\Omega(\sqrt{H^3 S A K})\). If we represent a tabular MDP in our model, we would need \(d = S^2 \times A\) parameters (Section 4.3, [8]). In this case, our bound becomes \(R(K) = O(\sqrt{(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\).

0.0.4 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 [8], i.e. by using a penalized maximum likelihood estimator \[\hat{\theta}^{\texttt{p}}(k) \in \mathop{\mathrm{arg\,min}}_{\theta \in \mathbb{R}^{d}} \sum_{t=1}^{k} \sum_{h=1}^H -\log \mathbb{P}_{\theta}\left(s_{h+1}^t \mid s_{h}^t, a_{h}^t\right)+\eta \operatorname{pen} (\theta).\] Here, pen\((\theta)\) is a trace-norm penalty: \(\operatorname{pen}(\theta) = \frac{1}{2}\|\theta\|_{\mathbb{A}}\) and \(\mathbb{A}=(\operatorname{tr}(A_i A_j^\top))_{i,j}\). By properties of the exponential family, the penalized maximum likelihood estimator verifies, for all \(i\le d\): \[\label{eq:ML95transition} \sum_{t=1}^{k}\sum_{h=1}^H \left(\psi\left(s_{h+1}^{t}\right)-\mathbb{E}_{s_{h}^t, a_{h}^t}^{\hat{\theta}^{\texttt{p}}_{k}}\left[\psi\left(s^{\prime}\right)\right]\right)^{\top} A_{i} \varphi\left(s_{h}^t, a_{h}^t\right)=\eta \nabla_{i} \operatorname{pen}\left(\hat{\theta}^{\texttt{p}}_{k}\right).\tag{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 1.0.6). We estimate the parameter for reward, i.e. \(\theta_r\), similarly \[\begin{align} \hat{\theta}^{\texttt{r}}(k) \in \mathop{\mathrm{arg\,min}}_{\theta \in \mathbb{R}^{d}} \sum_{t=1}^{k}\sum_{h=1}^H -\log \mathbb{P}_{\theta}\left(r_{t} \mid s_{h}^t, a_{h}^t\right) &+\eta \operatorname{pen}(\theta),\\ \implies \qquad \sum_{t=1}^{k}\sum_{h=1}^H \left(r_t -\mathbb{E}_{s_{h}^t, a_{h}^t}^{\hat{\theta}^{\texttt{r}}_{k}}\left[r\right]\right)\: B^{\top} A_{i} \varphi\left(s_{h}^t, a_{h}^t\right) =\eta &\nabla_{i} \operatorname{pen}\left(\hat{\theta}^{\texttt{r}}_{k}\right)\quad \forall i \in [d].\label{eq:ML95reward} \end{align}\tag{6}\] 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 RLSVI-framework [5], [18]. We show that perturbing the reward estimation can guarantee optimism with a constant probability, i.e. there exists \(\nu \in (0,1]\) such that for all \(k\in [K]\) and \(s_1^k \in \mathcal{S}\), \[\mathbb{P}\left(\tilde{V}_1(s_1^k) - V_1^\star(s_1^k)\ge 0\right)\ge \nu.\] [18] 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, [18] proposes an involved clipping procedure to handle the issue of unstable values. Instead, by careful geometric analysis (cf. Lemma 13), we bound the occurrences of the unstable values, and in turn, upper bound the regret without clipping. Note that unlike [21], BEF-RLSVI does not guarantee that the estimated value function is optimistic but still is able to control the learning error (cf. Section 0.0.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\):

\[\label{eq:linear95value95function} Q_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},h}^\pi (s, a) = \mathbb{E}_{\tilde{\theta}^{\texttt{r}}}[r(s,a)] + \bigg\langle \phi^{\texttt{p}}(s,a), \int_{\mathcal{S}} \mu^{\texttt{p}}(\tilde{s}) V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},h+1}^\pi (\tilde{s}) d\tilde{s} \bigg\rangle.\tag{7}\]

Then, we select the best action greedily using dynamic programming to compute \(Q_h(s,a)\). Although our model yields infinite dimensional \(\phi^{\texttt{p}}\) and \(\psi^{\texttt{p}}\), approximating them (cf. next paragraph) with linear features of dimension \(\text{\usefont{OMS}{cmsy}{m}{n}O}(p H^2 K\log(H K))\) is possible without increasing the regret. Thus, the planning is done in \(\text{\usefont{OMS}{cmsy}{m}{n}O}(p H^3 K\log(H K))\), 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 1.0.5. Now, we highlight the schematic of a finite-dimensional approximation of \(\phi^{\texttt{p}}\) and \(\psi^{\texttt{p}}\). We proceed in three steps. 1) We have with high probability \(\mathbb{S}(V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},h})\le d H^{3/2}\) (Section 0.0.5). 2) If we have a uniform \(\epsilon\)-approximation of \(\mathbb{P}_{\theta^{\texttt{p}}}\), we show that using it incurs at most an extra \(\text{\usefont{OMS}{cmsy}{m}{n}O}(\epsilon d H^{5/2} K)\) regret. 3) Finally, following [26], we approximate uniformly the shift invariant kernels, here the RBF in Equation 4 , within \(\epsilon\) error and with features of dimensions \(\text{\usefont{OMS}{cmsy}{m}{n}O}(p \epsilon^{-2}\log\frac{1}{\epsilon^2})\), where \(p\) is dimension of \(\psi\). Associating these three elements and choosing \(\epsilon = 1/\sqrt{(H^2 K)}\), we establish our claim.

0.0.5 Theoretical analysis: proof outline↩︎

To convey the novelties in our analysis, we provide a proof sketch for Theorem 1. We start by decomposing the regret into an estimation loss and a learning error, as given below \[\label{eq:regret95decomposition95estim95learn} R(K) = \sum_{k=1}^K (V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^\star - V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^{\pi_k})(s_{1 k}) = \sum_{k=1}^K (\underbrace{V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^\star - V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}^{\pi_k}}_{learning} + \underbrace{V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}^{\pi_k} - V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^{\pi_k}}_{Estimation})(s_{1 k}).\tag{8}\] 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 12 leads to the upper-bound.

0.0.5.1 Bounding the estimation error

We further decompose the estimation error into the errors in estimating transitions and rewards. \[\label{eq:estimation95error95decomposition} V_{\hat{\theta}^{\texttt{p}}, \tilde{\theta}^{\texttt{r}}}^\pi(s_{1 k}) -V_{\theta^{\texttt{p}}, \theta^{\texttt{r}}}^\pi(s_{1 k}) = \underbrace{V_{\hat{\theta}^{\texttt{p}}, \theta^{\texttt{r}}}^\pi(s_{1 k}) -V_{\theta^{\texttt{p}}, \theta^{\texttt{r}}}^\pi(s_{1 k})}_{\text{transition estimation}} + \underbrace{V_{\hat{\theta}^{\texttt{p}}, \tilde{\theta}^{\texttt{r}}}^\pi(s_{1 k}) - V_{\hat{\theta}^{\texttt{p}}, \theta^{\texttt{r}}}^\pi(s_{1 k})}_{\text{reward estimation}}\tag{9}\]

Transition estimation Since the reward parameter is exact, the value function’s span is \(\le H\). Then, using the transportation of Lemma 7 we obtain the bound \(H \sum_{h=1}^H \sqrt{2\operatorname{KL}_{s_{h k}, a_{h k}}(\theta^{\texttt{p}}, \hat{\theta}^{\texttt{p}})}\). We notice that since the reward parameter is exact, the bound is actually \(H \min\{1,\sum_{h=1}^H \sqrt{2\operatorname{KL}_{s_{h k}, a_{h k}}(\theta^{\texttt{p}}, \hat{\theta}^{\texttt{p}})}\}\). Using Lemma 12 under Assumption 1, we win a \(\sqrt{H}\) factor compared to the analysis of [28].

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. [18] proposes an involved clipping depending on the norms \(\|(A_i \varphi(s_h^k,a_h^k))_{i\in[d]}\|_{(\bar{G}_{k}^\texttt{p})^{-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”: \(\left\{k \in [K], \exists h:\: \|(A_i \varphi(s_h^k,a_h^k))_{i\in[d]}\|_{(\bar{G}_{k}^\texttt{p})^{-1}}\ge 1\right\}\), these rounds are why clipping is necessary. Thanks to Lemma 13, we know that the number of such rounds is at most \(\text{\usefont{OMS}{cmsy}{m}{n}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.

0.0.5.2 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, \[\begin{align} (V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}-&V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^\star)(s_1) \ge (Q_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}^\star-Q_{1}^\star)(s_1,\pi^\star (s_1))\\ &\ge \underbrace{V_{\hat{\theta}^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\theta^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1)}_{\text{first term}} + \underbrace{V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1)}_{\text{second term}} + \underbrace{V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}}^{\pi^\star} (s_1)}_{\text{third term}} \end{align}\] The first and second terms are perturbation free, we handle them similarly to the estimation error, i.e. using concentration arguments for \(\hat{\theta}^{\texttt{p}}\) and \(\hat{\theta}^{\texttt{r}}\). For the third term, we use transportation of rewards (Lemma 11) and anti-concentration of \(\xi_k\) (Lemma 6). We find that with probability at least \(1-2 \delta\) \[\begin{align} (V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}-V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^\star)(s_1) \ge& \xi_k ^\top \: \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}\left[\sum_{t=1}^H \frac{\mathbb{V}\mathrm{ar}^{\theta^{\texttt{r}}_j} (r)}{2} (A_i \varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t)))_{i\in[d]}\right] B\\ &{\displaystyle - H c(n,\delta) \left\|\sum_{h=1}^H \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k} \left[ (A_i \varphi(\tilde{s}_h, \pi^\star (\tilde{s}_h)))_{i\in [d]}\right] \right\|_{(\bar{G}_{k}^\texttt{p})^{-1}}}, \end{align}\] where \(c(n,\delta)\!= \!\left(\!\sqrt{\!\beta^{\texttt{p}}\beta^{\texttt{p}}(n,\delta)/\alpha^{\texttt{p}}}\! +\! \sqrt{\!\beta^{\texttt{r}}\beta^{\texttt{r}}(n,\delta) \min\{1,\alpha^{\texttt{p}}/\alpha^{\texttt{r}}\}/(2 \alpha^{\texttt{r}})\!} \!\right)\). Since \(\xi_k \!\sim\! \mathcal{N}(0,x_k (\bar{G}_{k}^\texttt{p})^{-1}\!)\) and \(x_k \!\ge\! H^2 c(n,\delta)^2\), we get \(\mathbb{P}\left(V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}^\pi(s_1)-V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^\star(s_1) \ge 0\right)\ge \Phi(-1)\), where \(\Phi\) is the normal CDF. This is ensured by the anti-concentration property of Gaussian random variables, see Lemma 6.

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 [18].

Upper bound on \(V_1^\star\): Draw \((\bar{\xi}_{k})_{k\in [K]}\) i.i.d copies of \((\xi_{k})_{k\in [K]}\) and define the event where optimism holds as \(\bar{O}_k \triangleq \{V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}}_k,1}(s_1^k) - V_1^\star (s_1^k) \ge 0\}\). This implies that \(\quad V_1^\star (s_1^k) \le \mathbb{E}_{\bar{\xi}_k \mid \bar{O}_k }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)].\)

Lower bound on \(V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}}}\:\): Consider \(\underbar{V}_{1}(s_1^k)\) to be a solution of the optimization problem \[\min _{\xi_{ k}} V_{\hat{\theta}^{\texttt{p}}, \hat{\theta}^{\texttt{r}}+\xi_k,1}(s_{1}^k) \quad \text{ subject to: } \: \|\xi_k\|_{\bar{G}_k} \le \sqrt{x_k d\log(d/\delta)},\] As the injected noise concentrates, we obtain \(\underbar{V}_{1}(s_1^k) \le V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}}}(s_1^k)\).

Combination: Using these upper and lower bounds, we show that with probability at least \(1-\delta\), \[\begin{align} V_1^\star (s_1^k) -& V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k) \le \mathbb{E}_{\bar{\xi}_k \mid \bar{O}_k }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)-\underbar{V}_{1}(s_1^k)]\\ &\le \left(\mathbb{E}_{\bar{\xi}_k }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)-\underbar{V}_{1}(s_1^k)] - \mathbb{E}_{\bar{\xi}_k \mid \bar{O}_k^\texttt{c} }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)-\underbar{V}_{1}(s_1^k)]\mathbb{P}(\bar{O}_k^\texttt{c})\right)/ \mathbb{P}(\bar{O}_k), \end{align}\] 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 1. We refer to Appendix 1.0.2.2 for the detailed proof.

0.0.6 Related work: functional representation in RL with regret and tractability↩︎

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. [20] studies MDPs with a linear mixtures model then extends to an RKHS setting, this generalizes our work and that of [22]. However, the paper proposes an Eluder-dimension analysis, for RKHS settings this leads to the result of [22], i.e. a regret \(H\log(T)^d\) higher than for BEF-RLSVI.Recently, [32] 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, [32] asserts that "common examples of where it is known to be small are function spaces (vector spaces)". [33] 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, [34] leverage the UCB approach for tabular MDPs and function spaces with bounded Eluder dimension, this strategy achieves a and achieve a \(\tilde{O}\left(\sqrt{d^4 H^2 T}\right)\) regret for linear MDPs. [21] considers the same setting, proposes an RLSVI based algorithm, and achieves a \(\tilde{O}(\sqrt{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 anti-concentration. Indeed, [18] 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 [24], [35]–[37], as an expressive parametric family to design theoretically-grounded model-based algorithms. [8] 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 [9]. [9] 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 [8], [9] achieve a worst-case regret of order \(\tilde{O}(\sqrt{d^2 H^4 K})\) for known reward. On a different note, [7], [10] 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, [14] shows that for some settings, even with a linear \(\epsilon\)-approximation of the \(Q\)-function, a planning procedure able to produce an \(\epsilon\)-optimal policy has a complexity at least \(2^H\). Thus, different works [15]–[17] propose to leverage different low-dimensional representations of value functions or transitions to perform efficient planning. Here, we take note from [19] 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 [26] to approximate transition dynamics from our model enables us to design a tractable planner. We provide a detailed discussion of this approximation in Section 0.0.4. More practically, [19], [38] use representations given by random Fourier features [26] 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.

0.0.7 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 \(\text{\usefont{OMS}{cmsy}{m}{n}O}(p H^3 K\log(H K))\)) thanks to properties of the RBF kernel. Our proof shows that clipping can be forwent for similar RLSVI-type algorithms. Moreover, we prove a \(\sqrt{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 \(\sqrt{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.

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.

1 Appendix↩︎

1.0.1 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.

1.0.2 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: \[\begin{align} \mathcal{R}(K) = \sum_{k=1}^K (V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^\star - V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^{\pi_k})(s_{1}^k) = \sum_{k=1}^K \Big(\underbrace{V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^\star - V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}^{\pi_k}}_{learning} + \underbrace{V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}^{\pi_k} - V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^{\pi_k}}_{Estimation}\Big)(s_{1}^k) \end{align}\]

1.0.2.1 Estimation error

To show that the estimation error \(\big(\sum_{k=1}^K V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1} - V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^{\pi_k}\big)\) 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_{\hat{\theta}^{\texttt{p}}, \tilde{\theta}^{\texttt{r}}}^\pi( s_{1}^k) -V_{\theta^{\texttt{p}}, \theta^{\texttt{r}}}^\pi(s_{1}^k) = \underbrace{V_{\hat{\theta}^{\texttt{p}}, \theta^{\texttt{r}}}^\pi(s_{1}^k) -V_{\theta^{\texttt{p}}, \theta^{\texttt{r}}}^\pi(s_{1}^k)}_{\text{transition estimation}} + \underbrace{V_{\hat{\theta}^{\texttt{p}}, \tilde{\theta}^{\texttt{r}}}^\pi(s_{1}^k) - V_{\hat{\theta}^{\texttt{p}}, \theta^{\texttt{r}}}^\pi( s_{1}^k)}_{\text{reward estimation}},\] we control each term separately in Section 1.0.2.1.1 and Section 1.0.2.1.2. Therefore, we obtain the following lemma controlling the estimation error.

1.0.2.1.1 Transition estimation

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

1.0.2.1.2 Reward estimation

Now, we provide the bound over the regret due to estimating the reward parameter.

1.0.2.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.

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.

1.0.2.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 \(\pi^\star\), we have: \[\begin{align} (V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}-V_{\theta^{\texttt{p}},\theta^{\texttt{r}},1}^\star &)(s_1) \ge (Q_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}^\star-Q_{1}^\star)(s_1,\pi^\star (s_1))\\ &\ge \underbrace{V_{\hat{\theta}^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\theta^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1)}_{\text{first term}} + \underbrace{V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1)}_{\text{second term}} + \underbrace{V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}}^{\pi^\star} (s_1)}_{\text{third term}} \end{align}\]

First term. By assumption, the expected reward under the true parameter satisfies \(\mathbb{E}_{\theta^{\texttt{r}}}[r(s,a)] \in [0,1]\), then \(\mathbb{S}\left(\sum_{t=1}^H \mathbb{E}_{\theta^{\texttt{r}}}[r(s_t,\pi(s_t))]\right)\le H\). Consequently, the first term can be controlled using Lemma 7 \[\begin{align} &V_{\theta^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1) \le H \sqrt{\mathrm{KL}(P_{\hat{\theta}^{\texttt{p}}}(s_2,\ldots, s_H),P_{\theta^{\texttt{p}}}(s_2,\ldots, s_H)) }\\ &\le H \sqrt{\mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}\left[\sum_{t=1}^H \psi(\tilde{s}_{t+1})^\top M_{\hat{\theta}^{\texttt{p}}-\theta^{\texttt{p}}} \varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t)) + Z^{\texttt{p}}_{\theta^{\texttt{p}}}(\tilde{s}_t, \pi^\star (\tilde{s}_t)) - Z^{\texttt{p}}_{\hat{\theta}^{\texttt{p}}}(\tilde{s}_t, \pi^\star (\tilde{s}_t)) \right]} \end{align}\]

Using Taylor’s expansion, for all \(h\in [H], \exists \theta_h \in [\theta^{\texttt{p}},\hat{\theta}^{\texttt{p}}]\) such that: \[\begin{align} \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}&\left[ \psi(\tilde{s}_{t+1})^\top M_{\hat{\theta}^{\texttt{p}}-\theta^{\texttt{p}}} \varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t)) + Z^{\texttt{p}}_{\theta^{\texttt{p}}}(\tilde{s}_t, \pi^\star (\tilde{s}_t)) - Z^{\texttt{p}}_{\hat{\theta}^{\texttt{p}}}(\tilde{s}_t, \pi^\star (\tilde{s}_t)) \right]\\ &= \frac{1}{2} (\hat{\theta}^{\texttt{p}}-\theta^{\texttt{p}})^\top \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}\left[\nabla_{s_h,\pi^\star(s_h)}^2 Z^{\texttt{p}}(\theta_h)\right] (\hat{\theta}^{\texttt{p}}-\theta^{\texttt{p}})\\ &\le \frac{\beta^{\texttt{p}}}{2} \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}\left[\|\hat{\theta}^{\texttt{p}}-\theta^{\texttt{p}}\|_{G_{\tilde{s}_h, \pi^\star (\tilde{s}_h)}}^2\right]. \end{align}\] Define \(u_k \stackrel{\rm def}{=}\sum_{h=1}^H \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k} \left[ (A_i \varphi(\tilde{s}_h, \pi^\star (\tilde{s}_h)))_{i\in [d]}\right]\), then \[\begin{align} V_{\theta^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1) - V_{ \hat{\theta}^{\texttt{p}}, \theta^{\texttt{r}}}^{\pi^\star} (s_1) &\le H \sqrt{ \frac{\beta^{\texttt{p}}}{2} \sum_{h=1}^H \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}\left[\|\hat{\theta}^{\texttt{p}}-\theta^{\texttt{p}}\|_{G_{\tilde{s}_h, \pi^\star (\tilde{s}_h)}}^2\right]}\\ &\le H \sqrt{\frac{\beta^{\texttt{p}}}{2}} \left\|\hat{\theta}^{\texttt{p}}-\theta^{\texttt{p}}\right\|_{\sum_{h=1}^H \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k} \left[ G_{\tilde{s}_h, \pi^\star (\tilde{s}_h)}\right]} \\ &\le H \sqrt{\frac{\beta^{\texttt{p}}}{2}} \left\|\hat{\theta}^{\texttt{p}}-\theta^{\texttt{p}}\right\|_{u_k u_k^\top} \\ &\le H \sqrt{\frac{\beta^{\texttt{p}}}{2} \left\|(\bar{G}_{k}^\texttt{p})^{-1/2} u_k u_k^\top (\bar{G}_{k}^\texttt{p})^{-1/2}\right\|} \|\hat{\theta}^{\texttt{p}}-\theta^{\texttt{p}}\|_{\bar{G}_{k}^\texttt{p}}\\ &\le H \sqrt{\frac{\beta^{\texttt{p}}}{2}} \| u_k \|_{ (\bar{G}_{k}^\texttt{p})^{-1}} \|\hat{\theta}^{\texttt{p}}-\theta^{\texttt{p}}\|_{\bar{G}_{k}^\texttt{p}} \end{align}\] The third line follows because \(\forall x\in \mathbb{R}^d,\quad \|x\|_{\sum_{i=1}a_i a_i^\top} \le \|x\|_{(\sum_{i=1}a_i)(\sum_{i=1}a_i)^\top}\), and the last one follows because \(\operatorname{tr}(AB)\le \operatorname{tr}(A)\operatorname{tr}(B)\) for any two real positive semi-definite matrices \(A\) and \(B\).
We deduce, with probability at least \(1-\delta\): \[V_{\theta^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1) \le H \sqrt{\frac{\beta^{\texttt{p}}\beta^{\texttt{p}}(k,\delta)}{\alpha^{\texttt{p}}}} \left\|\sum_{h=1}^H \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k} \left[ (A_i \varphi(\tilde{s}_h, \pi^\star (\tilde{s}_h)))_{i\in [d]}\right] \right\|_{(\bar{G}_{k}^\texttt{p})^{-1}}\]

Second term. We have \[\begin{align} V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\theta^{\texttt{r}}}^{\pi^\star} (s_1) &= \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}\left[\sum_{t=1}^H \frac{\mathbb{V}\mathrm{ar}^{\theta^{\texttt{r}}_t} (r)}{2} B^\top M_{\hat{\theta}^{\texttt{r}}- \theta^{\texttt{r}}}\varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t))\right]\\ &= (\hat{\theta}^{\texttt{r}}- \theta^{\texttt{r}})^\top \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}\left[\sum_{t=1}^H \frac{\mathbb{V}\mathrm{ar}^{\theta^{\texttt{r}}_t} (r)}{2} (A_i\varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t)))_{i\in [d]}\right] B\\ &\le \frac{\sqrt{\beta^{\texttt{r}}}}{2} \|\hat{\theta}^{\texttt{r}}- \theta^{\texttt{r}}\|_{\bar{G}_{k}^\texttt{r}} \left\| \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}\left[\sum_{t=1}^H (A_i\varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t)))_{i\in [d]}\right] \right\|_{(\bar{G}_{k}^\texttt{r})^{-1}} \end{align}\] 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 \(\beta^{\texttt{r}}\).
We conclude that with probability at least \(1-\delta\), \[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) \le \frac{\beta^{\texttt{r}}\sqrt{\beta^{\texttt{r}}(k,\delta)}}{\sqrt{2 \alpha^{\texttt{r}}}} \left\| \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}\left[\sum_{t=1}^H (A_i\varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t)))_{i\in [d]}\right] \right\|_{(\bar{G}_{k}^\texttt{r})^{-1}}\] We want to write all the norms in the same matrix. Therefore, with probability at least \(1-\delta\), \[\begin{align} V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) \le& \sqrt{\frac{\beta^{\texttt{r}}\beta^{\texttt{r}}(k,\delta) \min\{1,\frac{\alpha^{\texttt{p}}}{\alpha^{\texttt{r}}}\}}{2 \alpha^{\texttt{r}}}}\\ & \times \left\| \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k}\left[\sum_{t=1}^H (A_i\varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t)))_{i\in [d]}\right] \right\|_{(\bar{G}_{k}^\texttt{p})^{-1}} \end{align}\]

Third term. We have \[\begin{align} V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}},1}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}^{\pi^\star} (s_1) &= \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k} \left[\sum_{t=1}^H \frac{\mathbb{V}\mathrm{ar}^{\theta^{\texttt{r}}_j} (r)}{2} B^\top M_{\hat{\theta}^{\texttt{r}}- \tilde{\theta}^{\texttt{r}}}\varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t))\right]\\ &= \xi_k ^\top \: \mathbb{E}_{(\tilde{s}_t)_{t \in [H]}\sim \hat{\theta}^{\texttt{p}}\mid s_1^k} \left[\sum_{t=1}^H \frac{\mathbb{V}\mathrm{ar}^{\theta^{\texttt{r}}_j} (r)}{2} (A_i \varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t)))_{i\in[d]}\right] B \end{align}\]

Given the normal CDF \(\Phi\), we obtain that with probability at least \(\Phi(-1)\) \[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) - V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}}}^{\pi^\star} (s_1) \ge \sqrt{x_k \alpha^{\texttt{r}}} \left\|\left[\sum_{t=1}^H \frac{\mathbb{V}\mathrm{ar}^{\theta^{\texttt{r}}_j} (r)}{2} (A_i \varphi(\tilde{s}_t,\pi^\star (\tilde{s}_t)))_{i\in[d]}\right]\right\|_{(\bar{G}_{k}^\texttt{p})^{-1}}\]

Choosing \(x_k \ge \left(H\sqrt{\frac{\beta^{\texttt{p}}\beta^{\texttt{p}}(k,\delta)}{\alpha^{\texttt{p}}\alpha^{\texttt{r}}}}+\frac{\sqrt{\beta^{\texttt{r}}\beta^{\texttt{r}}(k,\delta)\min\{1,\frac{\alpha^{\texttt{p}}}{\alpha^{\texttt{r}}}\}}}{2 \alpha^{\texttt{r}}}\right)\) and using Lemma 6, we find that the perturbed value function is optimistic with probability at least \(\Phi(-1)\).

1.0.2.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.

1.0.2.2.2.1 Upper bound on \(V_1^\star\).

Let us draw \((\bar{\xi}_{k})_{k\in [K]}\) i.i.d copies of \((\xi_{k})_{k\in [K]}\). Define the optimism event at episode \(k\): \[\label{def:optimism95k} \bar{O}_k = \{V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k) - V_1^\star (s_1^k) \ge 0\}\tag{14}\] we know that \(\mathbb{P}(\bar{O}_k)\ge \Phi(-1)\). This event provides the upper bound: \[\label{eq:value95upper95bound} V_1^\star (s_1^k) \le \mathbb{E}_{\bar{\xi}_k \mid \bar{O}_k }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)]\tag{15}\]

1.0.2.2.2.2 Lower bound on \(V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}}}\).

We define this bound with an optimization problem under concentration of the noise. Consider \(\underbar{V}_{1}(s_1^k)\) is the solution of \[\begin{align} &\min _{\xi_{ k}} V_{\hat{\theta}^{\texttt{p}}, \hat{\theta}^{\texttt{r}}+\xi_k,1}(s_{1^k}) \label{eq:value95lower95bound95opt}\\ &\|\xi_k\|_{\bar{G}_{k}^\texttt{p}} \le \sqrt{x_k d\log(d/\delta)}, \quad \forall t \in[H] \nonumber \end{align}\tag{16}\] Under the concentration of our injected noise, we obtain \[\label{eq:value95lower95bound} \underbar{V}_{1}(s_1^k) \le V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}}}(s_1^k)\tag{17}\]

1.0.2.2.2.3 Combining the error bounds.

Combining the upper bound of Equation 15 with the lower bound of Equation 17 , we get, with probability at least \(1-\delta\): \[V_1^\star (s_1^k) - V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k) \le \mathbb{E}_{\bar{\xi}_k \mid \bar{O}_k }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)-\underbar{V}_{1}(s_1^k)]\] Also, using the tower rule, \[\begin{align} \mathbb{E}_{\bar{\xi}_k }[&V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)-\underbar{V}_{1}(s_1^k)]\\ &= \mathbb{E}_{\bar{\xi}_k \mid \bar{O}_k }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)-\underbar{V}_{1}(s_1^k)]\mathbb{P}(\bar{O}_k) + \mathbb{E}_{\bar{\xi}_k \mid \bar{O}_k^\texttt{c} }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)-\underbar{V}_{1}(s_1^k)]\mathbb{P}(\bar{O}_k^\texttt{c}) \end{align}\] Therefore, \[\begin{align} V_1^\star (s_1^k) - &V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)\\ &\le \left(\mathbb{E}_{\bar{\xi}_k }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)-\underbar{V}_{1}(s_1^k)] - \mathbb{E}_{\bar{\xi}_k \mid \bar{O}_k^\texttt{c} }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)-\underbar{V}_{1}(s_1^k)]\mathbb{P}(\bar{O}_k^\texttt{c})\right)/ \mathbb{P}(\bar{O}_k)\\ &=\left(\mathbb{E}_{\xi_k }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+{\xi}_k,1}^\pi (s_1^k)-\underbar{V}_{1}^\pi (s_1^k)] - \mathbb{E}_{\xi_k \mid \bar{O}_k^\texttt{c} }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\xi_k,1}(s_1^k)-\underbar{V}_{1}(s_1^k)]\mathbb{P}(\bar{O}_k^\texttt{c})\right)/ \mathbb{P}(\bar{O}_k). \end{align}\] The last line follows since \(\xi_k\) and \(\bar{\xi}_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 16 as \(\underline{\xi}_k\). Using Lemma 11, we find \[\begin{align} V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}^\pi(s_{1}^{k}) - &V_{\hat{\theta}^{\texttt{p}}, \hat{\theta}^{\texttt{r}}+\underline{\xi}_k,1}^\pi(s_{1}^{k})\\ &= \mathbb{E}_{(\tilde{s}_h)_{1\le h\le H}\sim \pi \mid \hat{\theta}^{\texttt{p}}, s_{1}^{k}}\left[\sum_{h=1}^H \frac{\mathbb{V}\mathrm{ar}_{\tilde{s}_h,\pi(\tilde{s}_h)}(r)}{2} B^\top M_{\tilde{\theta}^{\texttt{r}}-\hat{\theta}^{\texttt{r}}-\underline{\xi}_k}\varphi(\tilde{s}_h,\pi(\tilde{s}_h))\right] \\ &\le \mathbb{E}\left[\sum_{h=1}^H \frac{\mathbb{V}\mathrm{ar}_{\tilde{s}_h,\pi(\tilde{s}_h)}(r)}{2} \|\tilde{\theta}^{\texttt{r}}-\hat{\theta}^{\texttt{r}}-\underline{\xi}_k\|_{\bar{G}_{k}^\texttt{p}} \|(B^\top A_i\varphi(\tilde{s}_h,\pi(\tilde{s}_h)))_{1\le i\le d}\|_{(\bar{G}_{k}^\texttt{p})^{-1}}\right]\\ &\le \|\tilde{\theta}^{\texttt{r}}-\hat{\theta}^{\texttt{r}}-\underline{\xi}_k\|_{\bar{G}_{k}^\texttt{p}} \mathbb{E}\left[\sum_{h=1}^H \frac{\mathbb{V}\mathrm{ar}_{\tilde{s}_h,\pi(\tilde{s}_h)}(r)}{2} \|(B^\top A_i\varphi(\tilde{s}_h,\pi(\tilde{s}_h)))_{1\le i\le d}\|_{(\bar{G}_{k}^\texttt{p})^{-1}}\right]\\ &\le \|\tilde{\xi}_k-\underline{\xi}_k\|_{\bar{G}_{k}^\texttt{p}} \frac{\beta^{\texttt{r}}}{2} \mathbb{E}\Bigg[ \sum_{h=1}^H \|(A_i\varphi(\tilde{s}_h,\pi(\tilde{s}_h)))_{1\le i\le d}\|_{(\bar{G}_{k}^\texttt{p})^{-1}} \Bigg] \end{align}\] Then, \[\begin{align} \mathbb{E}_{\tilde{\xi}_k} \Big[V_{\hat{\theta}^{\texttt{p}},\tilde{\theta}^{\texttt{r}},1}^\pi(s_{1}^{k}) - &V_{\hat{\theta}^{\texttt{p}}, \hat{\theta}^{\texttt{r}}+\underline{\xi}_k,1}^\pi (s_{1}^{k}) \Big]\\ &\le \frac{\beta^{\texttt{r}}}{2} \mathbb{E}_{\tilde{\xi}_k}[\|\tilde{\xi}_k-\underline{\xi}_k\|_{\bar{G}_{k}^\texttt{p}}] \mathbb{E}_{(\tilde{s}_h) \sim \pi \mid \hat{\theta}^{\texttt{p}}}\left[\sum_{h=1}^H \|(A_i\varphi(\tilde{s}_h,\pi(\tilde{s}_h)))_{1\le i\le d}\|_{(\bar{G}_{k}^\texttt{p})^{-1}}\right]. \end{align}\] Also, \[\begin{align} \Big|\mathbb{E}_{\xi_k \mid \bar{O}_k^\texttt{c} }[V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\xi_k,1}(s_1^k)-&\underline{V}_{1}(s_1^k)]\Big|\\ \le \frac{\beta^{\texttt{r}}}{2}& \mathbb{E}_{\tilde{\xi}_k \mid \bar{O}_k^\texttt{c}}[\|\tilde{\xi}_k-\underline{\xi}_k\|_{\bar{G}_{k}^\texttt{p}}] \mathbb{E}_{(\tilde{s}_h) \sim \pi \mid \hat{\theta}^{\texttt{p}}}\left[\sum_{h=1}^H \|(A_i\varphi(\tilde{s}_h,\pi(\tilde{s}_h)))_{1\le i\le d}\|_{(\bar{G}_{k}^\texttt{p})^{-1}}\right]\\ \le \frac{\beta^{\texttt{r}}}{2}& \mathbb{E}_{\tilde{\xi}_k}[\|\tilde{\xi}_k-\underline{\xi}_k\|_{\bar{G}_{k}^\texttt{p}}] \mathbb{E}_{(\tilde{s}_h) \sim \pi \mid \hat{\theta}^{\texttt{p}}}\left[\sum_{h=1}^H \|(A_i\varphi(\tilde{s}_h,\pi(\tilde{s}_h)))_{1\le i\le d}\|_{(\bar{G}_{k}^\texttt{p})^{-1}}\right]. \end{align}\] We have a bound on the expected value of the sum of feature norms in the proof of Lemma 3. Also, \[\begin{align} \mathbb{E}_{\tilde{\xi}_k}[\|\tilde{\xi}_k-\underline{\xi}_k\|_{\bar{G}_{k}^\texttt{p}}] &\le \mathbb{E}_{\tilde{\xi}_k}[\|\tilde{\xi}_k\|_{\bar{G}_{k}^\texttt{p}}] + \mathbb{E}_{\tilde{\xi}_k}[\|\underline{\xi}_k\|_{\bar{G}_{k}^\texttt{p}}]\\ &\le \sqrt{\mathbb{E}_{\tilde{\xi}_k}[\|\tilde{\xi}_k\|_{\bar{G}_{k}^\texttt{p}}^2]} + \sqrt{x_k d \log(d/\delta)}\\ &\le \sqrt{x_k d}+\sqrt{x_k d \log(d/\delta)} \end{align}\] The second line follows from Cauchy-Schwarz and by definition of \(\underline{\xi}_k\). The last line is due to the fact that \(x_k(\bar{G}_{k}^\texttt{p})^{-1} \sim \mathcal{N}(0,x_k I_d)\), which implies \(\|\tilde{\xi}_k\|_{\bar{G}_{k}^\texttt{p}}^2 \sim \mathcal{N}(0, d x_k)\). We conclude the proof by taking the sum of feature norms from the proof of Lemma 3.

We conclude that with probability at least \(1-2\delta\): \[\begin{align} \sum_{k=1}^K V_1^\star &(s_1^k) - V_{\hat{\theta}^{\texttt{p}},\hat{\theta}^{\texttt{r}}+\bar{\xi}_k,1}(s_1^k)\le \frac{\beta^{\texttt{r}}}{\Phi(-1)}(\sqrt{x_k d}+\sqrt{x_k d \log(d/\delta)})\\ &\Bigg[ \sqrt{\frac{3d}{\log(2)}\log\left(1+ \frac{\alpha^{\texttt{r}}\|\mathbb{A}\|_2^2 B_{\varphi,\mathbb{A}}^2}{\eta \log(2)}\right) \left(1+\frac{\alpha^{\texttt{r}}B_{\varphi, A} H}{\eta}\right) H d\log(1+\alpha^{\texttt{r}}\eta^{-1} B_{\varphi, \mathbb{A}}H)} \\ &+ \sqrt{K H d \log \left(1+\alpha^{\texttt{r}}\eta^{-1} B_{\varphi, \mathbb{A}} H K\right)\log(e/\delta^2)} \Bigg] \end{align}\]

1.0.3 Concentrations↩︎

1.0.3.1 Concentration of the transition parameter

We recall the important concentration of the maximum likelihood estimator for general bilinear exponential families (cf. Theorem 1 of [8]).

A proof of this result can be found in the work [8]. We provide an almost similar proof for the concentration of rewards in the next section.

1.0.3.2 Concentration of the reward parameter (contribution)

1.0.3.3 Gaussian concentration and anti-concentration

Thanks to lower bounds on the error function, we have the following bound on the probability of anti-concentration \(\Phi(-1) \ge 1/(4 \sqrt{e \pi})\).

1.0.4 Technical results↩︎

1.0.4.1 A transportation lemma

For any function \(f: \mathcal{X} \rightarrow \mathbb{R}\), we define its span as \(\mathbb{S}(f):=\max _{x \in \mathcal{X}} f(x)-\min _{x \in \mathcal{X}} f(x) .\) For a probability distribution \(P\) supported on the set \(\mathcal{X}\), let \(\mathbb{E}_{P}[f]:=\mathbb{E}_{P}[f(X)]\) and \(\mathbb{V}_{P}[f]:=\mathbb{V}_{P}[f(X)]=\mathbb{E}_{P}\left[f(X)^{2}\right]-\) \(\mathbb{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 [39] (Lemma 4.18).

1.0.4.2 Bregman divergence

For a Legendre function \(F: \mathbb{R}^{d} \rightarrow \mathbb{R}\), the Bregman divergence between \(\theta^{\prime}, \theta \in \mathbb{R}^{d}\) associated with \(F\) is defined as \(B_{F}\left(\theta^{\prime}, \theta\right):=F\left(\theta^{\prime}\right)-F(\theta)-\left(\theta^{\prime}-\theta\right)^{\top} \nabla F(\theta) .\) Now, for any fixed \(\theta \in \mathbb{R}^{d}\), we introduce the function \[B_{F, \theta}(\lambda):=B_{F}(\theta+\lambda, \lambda)=F(\theta+\lambda)-F(\theta)-\lambda^{\top} \nabla F(\theta) .\] It then follows that \(B_{F, \theta}\) is a convex function, and we define its dual as \[B_{F, \theta}^{\star}(x)=\sup _{\lambda \in \mathbb{R}^{d}}\left(\lambda^{\top} x-B_{F, \theta}(\lambda)\right)\] We have for any \(\theta, \theta^{\prime} \in \mathbb{R}^{d}\): \[\label{eq:Bregman95duality} B_{F}\left(\theta^{\prime}, \theta\right)=B_{F, \theta^{\prime}}^{\star}\left(\nabla F(\theta)-\nabla F\left(\theta^{\prime}\right)\right)\tag{25}\] To see this, we observe that \[\begin{align} B_{F, \theta^{\prime}}^{\star}&\left(\nabla F(\theta)-\nabla F\left(\theta^{\prime}\right)\right) \\ &= \sup _{\lambda \in \mathbb{R}^{d}} \lambda^{\top}\left(\nabla F(\theta)-\nabla F\left(\theta^{\prime}\right)\right)-\left[F\left(\theta^{\prime}+\lambda\right)-F\left(\theta^{\prime}\right)-\lambda^{\top} \nabla F\left(\theta^{\prime}\right)\right] \\ &= \sup _{\lambda \in \mathbb{R}^{d}} \lambda^{\top} \nabla F(\theta)-F\left(\theta^{\prime}+\lambda\right)+F\left(\theta^{\prime}\right) . \end{align}\]

Now an optimal \(\lambda\) must satisfy \(\nabla F(\theta)=\nabla F\left(\theta^{\prime}+\lambda\right)\). One possible choice is \(\lambda=\theta-\theta^{\prime}\). Since, by definition, \(F\) is strictly convex, the supremum will indeed be attained at \(\lambda=\theta-\theta^{\prime}.\) Plugin-in this value, we obtain \[B_{F, \theta^{\prime}}^{\star}\left(\nabla F(\theta)-\nabla F\left(\theta^{\prime}\right)\right)=\left(\theta-\theta^{\prime}\right)^{\top} \nabla F(\theta)-F(\theta)+F\left(\theta^{\prime}\right)=B_{F}\left(\theta^{\prime}, \theta\right) .\] Note that 25 holds for any convex function \(F\). Only difference is that, in this case, \(B_{F}(\cdot, \cdot)\) will not correspond to the Bregman divergence.

1.0.4.3 Properties of the bilinear exponential family

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

1.0.4.3.1 Derivatives

1.0.4.3.2 A transportation lemma for rewards

1.0.4.4 Elliptical potentials and elliptical lemma

1.0.4.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} :=(\varphi(s, a)^{\top} A_{i}^{\top} A_{j} \varphi(s, a))_{1\le i,j \le d} \:\), \(\quad \bar{G}_{n}^\texttt{e} \equiv \bar{G}_{(k-1) H}^\texttt{e}:=G_{n}+(\alpha^\texttt{e})^{-1} \eta A \:\), and \(G_{n} \equiv G_{(k-1) H}:=\sum_{\tau=1}^{k-1} \sum_{h=1}^{H} G_{s_{s}^{\tau}, a_{h}^{\tau}}\). Where \(\texttt{e}\) represents either \(\texttt{r}\) or \(\texttt{p}\), we omit the superscript \(\texttt{e}\) w.l.o.g in the rest of this section.

1.0.4.4.2 Elliptical potentials: finite number of large feature norms (contribution)

1.0.5 Tractable planning with random Fourier transform↩︎

A Primer on random Fourier transforms. We start by defining the Random Fourier Transform and its most relevant property. Let us consider the transition model of Equation 1 , we have \[\begin{align} \mathbb{P}(s' \mid s,a, \theta) = \exp\left(\psi(s') M_\theta \varphi(s,a) - Z_{\theta}(s,a)\right) = \mathbb{E}_{p(w,b)}\left[f\left(\psi(s'),w,b\right) f\left(M_\theta \varphi(s,a),w,b\right)\right], \end{align}\] where \(f\left(x,w,b\right) = \sqrt{2}\cos(w^\top x +b)\) are the random Fourier bases. \(p(w,b) = \mathcal{N}(0,\sigma^{-2} I) \times \mathcal{U}([0,2\pi])\), such that \(\mathcal{N}\) is the Gaussian distribution, \(\mathcal{U}\) is the Uniform distribution, and \(p(w,b)\) is a coupling among them.

Notice that this provides an alternative approach to decompose the transition kernel and obtain linearity of the value function. Moreover, since \(\forall x,w \in \mathbb{R}^d , b \in \mathbb{R}, |f(x,w,b)| \le \sqrt{2}\), we can use Hoeffding’s inequality to prove that a Monte-Carlo approximation of \(\mathbb{P}(s' \mid s,a, \theta)\) using \(N\) sample pairs of \((w,b)\) guarantees an error smaller than \(\epsilon\) with probability at least \(1-2\exp(-N\epsilon^2 /4)\). [26] proves a stronger result: it provides an algorithm approximating the Gaussian kernel for which the following uniform convergence bound holds.

Further, it implies that if \(N=\Omega\left(\frac{p}{\epsilon^{2}} \log \frac{\sigma_{p} \operatorname{diam}(\mathcal{M})}{\epsilon}\right)\), then \(\sup _{x, y \in \mathcal{M}}\left|\mathbf{z}(\mathbf{x})^{\prime} \mathbf{z}(\mathbf{y})-k(\mathbf{y}, \mathbf{x})\right| \leq \epsilon\) with constant probability.

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 \(\psi(s')\) and \(M_\theta \varphi(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 \approx p/\epsilon^{2}\) samples, we can construct a uniform \(\epsilon\)-approximation of \(\mathbb{P}(s' \mid s,a, \theta)\).

Let’s call \(\hat{V}_h\) the estimated value function using Algorithm [alg952:planning] with the above approximation of transition. Here, we elucidate the span of this estimation of value function. First we have: \[\hat{V}_H^\pi - V_H^\pi = \int_{s'} (\hat{P}-P)(s'\mid s,a) r(s',\pi(s')) \,\mathrm{d}s' \le \epsilon d H^{3/2}\] Here, we use the facts that \(\mathbb{S}\left(V_{\hat{\theta}, \tilde{\theta}^{\mathrm{x}}, h}\right) \leq d H^{3 / 2}\) (cf. Section 1.0.2.2) and the error in approximating \(P\) is bounded by \(\epsilon\), i.e. \(\sup_{s',s,a} |(\hat{P}-P)(s'|s,a)| \leq \epsilon\).

Assume that at step \(h+1\), we have \(\hat{V}_{h+1}^\pi - V_{h+1}^\pi \le \sum_{j=1}^{h+1} \epsilon^j \alpha_{h+1,j}\). Then, we obtain \[\begin{align} \hat{V}_{h}^\pi - V_{h}^\pi &\le \int_{s'} (\hat{P}-P)(s'\mid s,a) \hat{V}_{h+1}^\pi(s') \,\mathrm{d}s' + \int_{s'} P(s'\mid s,a)(\hat{V}_{h+1}^\pi - V_{h+1}^\pi)(s') \,\mathrm{d}s' \\ &= \int_{s'} (\hat{P}-P)(s'\mid s,a) (V_{h+1}^\pi + \hat{V}_{h+1}^\pi - V_{h+1}^\pi) \,\mathrm{d}s' + \int_{s'} P(s'\mid s,a)(\hat{V}_{h+1}^\pi - V_{h+1}^\pi)(s') \,\mathrm{d}s'\\ &\le \epsilon(d H^{3/2} + \sum_{j=1}^{h+1} \epsilon^j \alpha_{h+1,j}) + \sum_{j=1}^{h+1} \epsilon^j \alpha_{h+1,j}\\ &\le \epsilon (d H^{3/2} + \alpha_{h+1,1}) + \sum_{j=2}^{h+1} \epsilon^j (\alpha_{h+1,j-1} + \alpha_{h+1,j}) + \epsilon^{h+2} \alpha_{h+1,h+1} \end{align}\] Using the fact that \(\alpha_{1,1}=d H^{3/2}\) and with a proper induction, we find that: \[\hat{V}_{1}^\pi - V_{1}^\pi \le \epsilon d H^{5/2} \frac{1-\epsilon^{H-h}}{1-\epsilon} \underset{H \rightarrow \infty}{\leq} \epsilon d H^{5/2}\]

This concludes the proof of the arguments provided in § Planning of Section [sec:planning]. This means that the extra regret due to planning with the approximation by RFT features is of order \(\text{\usefont{OMS}{cmsy}{m}{n}O}(\epsilon d H^{5/2} K)\). By choosing an \(\epsilon\) of order \(1/(H \sqrt{K})\), we deduce that approximating the probability kernel with \(\text{\usefont{OMS}{cmsy}{m}{n}O}(p H^2 K)\) samples induces a tractable planning procedure without harming the regret.

1.0.6 Tractable Maximum Likelihood estimation↩︎

The maximum likelihood estimation is explicit for simple distributions like the Gaussian [41] 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, [42] 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. [43] proposes MCMC techniques for approximating the partition function. [44] 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 [45]. More recently, [9] 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 \(\mathcal{O}(d^3)\) time. Furthermore, in the case of Bounded distribution support and natural parameter, [46] shows that for a minimally represented \(k\)-parameter Exponential family, an \(\alpha\)-approximation of the ML can be derived in \(\mathcal{O}(\operatorname{poly}(k/\alpha))\) 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, [47] 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.

References↩︎