[This manuscript was  completed in September 2021 while both authors worked at Baidu Cognitive Computing Lab.   ]Model-based Reinforcement Learning (MBRL) has been widely adapted due to its sample efficiency. However, existing worst-case regret analysis typically requires optimistic planning, which is not realistic in general. In contrast, motivated by the theory, empirical study utilizes ensemble of models, which achieve state-of-the-art performance on various testing environments. Such deviation between theory and empirical study leads us to question whether randomized model ensemble guarantee optimism, and hence the optimal worst-case regret? This paper partially answers such question from the perspective of reward randomization, a scarcely explored direction of exploration with MBRL. We show that under the kernelized linear regulator (KNR) model, reward randomization guarantees a partial optimism, which further yields a  near-optimal worst-case regret in terms of the number of interactions. We further extend our theory to generalized function approximation and identified conditions for reward randomization to attain provably efficient exploration. Correspondingly, we propose concrete examples of efficient reward randomization. To the best of our knowledge, our analysis establishes the first worst-case regret analysis on randomized MBRL with function approximation.

§ INTRODUCTION

Reinforcement learning (RL) [Sutton and Barto, 2018] aims to learn the optimal policy by iteratively interacting with the environment. Model-based reinforcement learning (MBRL) [Osband and Roy, 2014, Luo et al., 2019, Ha and Schmidhuber, 2018, Luo et al., 2019, Sun et al., 2019, Kaiser et al., 2020, Ayoub et al., 2020, Kakade et al., 2020] achieves such a goal by fitting the environment from the observation and obtaining the policy from the fitted environment. Incorporated with deep learning, MBRL has achieved tremendous success in real-world tasks, including video games [Ha and Schmidhuber, 2018, Kaiser et al., 2020] and control tasks [Watter et al., 2015, Williams et al., 2015, Chua et al., 2018, Hafner et al., 2019, Song and Sun, 2021].

A key factor to the success of MBRL is sample efficiency. In terms of the theoretical analysis, such sample efficiency is characterized by the regret analysis of MBRL. Previous analysis suggests that when incorporated with exploration strategies, MBRL enjoys a near-optimal $\tilde\cO(\sqrt{T})$ regret [Jaksch et al., 2010, Ayoub et al., 2020, Kakade et al., 2020], where $T$ is the total number of interactions with the environment. However, previous provably efficient exploration typically utilizes optimistic planning [Jaksch et al., 2010, Luo et al., 2019, Ayoub et al., 2020, Kakade et al., 2020]. Such exploration strategy requires (i) identifying a confidence set of models $\cD$, which captures the uncertainty in model estimation, and then (ii) conducting optimistic planning by searching for the maximal policy among all possible models within $\cD$. The key to the success of optimistic planning is optimism under the face of the uncertainty principle [Jaksch et al., 2010]. Intuitively, optimistic planning encourages the agent to explore less visited areas, hence enhancing the sample complexity of the corresponding RL algorithm. While step (i) is realizable with ensemble techniques, step (ii) is in general impossible to implement, as it requires solving an optimization problem over a possibly continuous space of models $\cD$. As an alternative, previous empirical study [Chua et al., 2018, Pathak et al., 2017, Pathak et al., 2019] typically borrows the idea from optimistic planning and the study of Thompson sampling (TS) based algorithm [Osband and Roy, 2014]. A common empirical approach is to utilize model ensembles to capture the uncertainty of model estimations. Such ensembles are further utilized in planning through TS [Chua et al., 2018] or bonus construction [Pathak et al., 2017, Pathak et al., 2019]. Unlike optimistic planning, such approaches typically do not have a worst-case regret guarantee. Nevertheless, they attain state-of-the-art performance in various testing environments. Such deviation from theory and practice motivates us to propose this question:

Does randomized model ensemble guarantees optimism, and hence the optimal worst-case regret?

In this paper, we provide a partial solution to the above question from reward randomization, a relatively less studied method for exploration in MBRL. We initiate our analysis under the kernelized linear regulator (KNR) transition model [Mania et al., 2022, Kakade et al., 2020, Song and Sun, 2021] and known reward functions. We propose , which conducts exploration by iteratively planning with the fitted transition model and a randomized reward function. We further show that attains the near-optimal $\tilde\cO(\sqrt{T})$ regret. A key observation of reward randomization is a notion of partial optimism [Russo, 2019, Zanette et al., 2020], which ensures that a sufficient amount of interactions are devoted to exploration under the optimism principle. Motivated by the analysis under the KNR transition model, we extend to general function approximation with calibrated model [Curi et al., 2020, Kidambi et al., 2021] and propose a generic design principle of reward randomization. We further propose concrete examples of valid reward randomization and demonstrate the effectiveness of reward randomization  theoretically. We highlight that the proposed reward randomization method can be easily implemented based on the model ensembles. In addition, the reward randomization is highly modular and can be incorporated with various SOTA baselines.

Contribution. Our work provides a partial solution to the question we raised. Specifically, we investigate reward randomization and propose . Our contributions are as follows.

* We propose , a novel exploration algorithm for MBPO with worst-case regret guarantee that is realizable with general function parameterizations.

* We show that  has near-optimal worst-case regret under the KNR dynamics.

To the best of our knowledge, our analysis establishes the first worst-case regret analysis on randomized MBRL with function approximation.

Related Work.
Our work is closely related to the regret analysis of MBRL and online control problem [Osband and Roy, 2014, Luo et al., 2019, Sun et al., 2019, Lu and Roy, 2019, Ayoub et al., 2020, Kakade et al., 2020, Curi et al., 2020, Agarwal et al., 2020, Song and Sun, 2021]. [Ayoub et al., 2020] propose the value-target regression (VTR) algorithm, which focuses on the aspects of the transition model that are relevant to RL. [Agarwal et al., 2020] propose FLAMBE, a provably efficient MBRL algorithm under the linear MDP setting [Jin et al., 2020, Yang and Wang, 2019]. [Kakade et al., 2020] propose LC3, an online control algorithm under the KNR dynamics [Mania et al., 2022] that attains the optimal worst-case regret. Both [Ayoub et al., 2020] and [Kakade et al., 2020] utilizes optimistic planning for exploration, which is in general intractable. In contrast, we utilize reward randomization for exploration, which also attains the optimal worst-case regret and is highly tractable. To attain tractable optimistic planning, [Curi et al., 2020] design HUCRL, which introduces an extra state deviation variable in the optimization for planning. In contrast, planning with randomized reward does not introduce extra variable in optimization. [Luo et al., 2019] optimizes a lower bound of value functions, which avoids explicit uncertain quantification. Recent works also utilizes reward bonus to attain optimistic planning [Kidambi et al., 2021, Song and Sun, 2021]. [Song and Sun, 2021] propose PC-MLP, which constructs bonus by estimating the policy cover [Agarwal et al., 2020] and is computationally tractable. As a comparison, PC-MLP requires extra sampling to estimate the covariate matrix of policy cover. As a consequence, PC-MLP does not attain the optimal $\tilde\cO(\sqrt{T})$-regret. In contrast, does not require extra sampling to construct the bonus and can achieve the $\tilde\cO(\sqrt{T})$-regret. In addition, to attain tractable realization, PC-MLP utilizes different feature in model fitting and bonus construction, which is inconsistent with the theoretical analysis. In contrast, the implementation of is consistent with the theoretical analysis under the calibrated model assumption. Previous work also study efficient model-free RL exploration algorithms with function approximation. See, e.g., [Jiang et al., 2017, Jin et al., 2020, Du et al., 2020, Wang et al., 2020, Cai et al., 2020, Agarwal et al., 2020, Modi et al., 2021] and references therein for this line of research.

Our analysis is inspired by the recent progress in worst-case regret analysis of randomized RL algorithms [Russo, 2019, Pacchiano et al., 2020, Zanette et al., 2020, Ishfaq et al., 2021]. Our optimism analysis is inspired by [Russo, 2019] and [Zanette et al., 2020]. [Russo, 2019] propose the first worst-case regret analysis to the randomized least-squares value iteration (RLSVI) algorithm under the tabular setting. [Zanette et al., 2020] extend the analysis of RLSVI to truncated linear function approximations under the general state space. [Ishfaq et al., 2021] analyze the randomized Q-learning with both linear function approximation and general function approximation. In contrast, we focus on the randomized MBRL algorithm. [Pacchiano et al., 2020] analyze the worst-case regret of MBRL with both reward and transition randomization. We remark that both [Pacchiano et al., 2020] and [Ishfaq et al., 2021] require drawing multiple samples for each state-action pair in planning and further maximizing over all randomized reward functions in planning. In contrast, we only require one sample at each time step, and do not need further maximization. In addition, [Pacchiano et al., 2020] focus on the tabular setting with finite state and action spaces, whereas we consider the generic setting with function approximation.

§ BACKGROUND

§.§ Reinforcement Learning

In this paper, we model the environment by an episodic MDP $(\cS, \cA, H, \{r_h\}_{h\in[H]}, \PP)$. Here $\cS$ and $\cA$ are the state spaces, $H$ is the length of episodes, $r_h: \cS\times\cA\mapsto [0, 1]$ is the bounded reward function for $h\in[H]$, and $\PP$ is the transition kernel, which defines the transition probability $s_{h+1}\sim\PP(\cdot\given s_h, a_h)$ for all $h\in[H]$ and $(s_h, a_h)\in\cS\times\cA$.

Interaction Procedure. An agent with a set of policies $\{\pi_h\}_{h\in[H]}$ interacts with such environment as follows. The agent starts from a fixed initial state $s_1\in\cS$. Iteratively, upon reaching the state $s_h\in\cS$, the agent takes the action $a_h = \pi_h(s_h)$. The agent then receives the reward $r_h(s_h, a_h)$. The environment transits into the next state $s_{h+1}$ according to the probability $\PP(\cdot\given s_h, a_h)$. The process ends when the agent reaches the state $s_{H+1}$.

To describe the expected cumulative reward, for each policy $\pi = \{\pi_h\}_{h\in[H]}$, we introduce the action-value functions $\{Q^\pi_h\}_{h\in[H]}$ defined as follows,
Q^π_h(s_h, a_h; {r_h}_h∈[H], ) = ∑^H_τ= h[ r_τ(s_τ, a_τ) s_h, a_h, π],  ∀h∈[H],  (s_h, a_h)∈×,
where $a_\tau = \pi_\tau(s_\tau)$ and $s_{\tau+1}\sim \PP(\cdot \given s_\tau, a_\tau)$ for all $\tau = h, \ldots, H$. Similarly, we define the value functions $\{V^\pi_h\}_{h\in[H]}$ as follows,
V^π_h(s_h; {r_h}_h∈[H], ) = ∑^H_τ= h[ r_τ(s_τ, a_τ) s_h,  π],  ∀h∈[H],  (s_h, a_h)∈×.
We define optimal policy $\pi^* = \{\pi^*_h\}_{h\in[H]}$ as the maximizer of the following optimization problem,
π^* = _π V^π_1(s_1; {r_h}_h∈[H], ).
Correspondingly, we define $V^*$ and $Q^*$ the value and action-value functions corresponding to the optimal policy $\pi^*$.

The goal of reinforcement learning (RL) is to sequentially select the policy $\pi^k = \{\pi^k_h\}_{h\in[H]}$ based on the previous experiences, aiming to maximize the expected cumulative reward collected by the agent in the interaction process. Equivalently, the goal is to minimize the following regret,
R(K) = ∑^K_k = 1 V^*(s_1) - V^π^k(s_1),
where $K$ is the total number of interactions and $s_1$ is the fixed initial state. Intuitively, the regret $R(K)$ describes the deviation between the policies executed in the interaction process and the optimal policy.

§.§ The Online Nonlinear Control Problem

We consider the online nonlinear control problem with the following transition dynamics,
s_h+1 = f(s_h, a_h) + ϵ,   where ϵ∼N(0, σ^2·I),  ∀h∈[H],  (s_h, a_h)∈×.
Here the function $f: \cS\times\cA\mapsto \cS$ belongs to a Reproducing Kernel Hilbert Space (RKHS) with known kernel and the noise $\epsilon$ is independent across transitions. Such transition is also known as the Kernelized Nonlinear Regulator (KNR) in previous study [Kakade et al., 2020, Song and Sun, 2021]. In this work, we follow [Mania et al., 2022, Kakade et al., 2020, Song and Sun, 2021] and consider a primal version of such transition dynamics as the underlying transition dynamics for the RL problem, which is defined as follows,
s_h+1 = f(s_h, a_h;W^*) + ϵ,   where ϵ∼N(0, σ^2·I),

f(s_h, a_h; W^*) = W^* ϕ(s_h, a_h),   ∀h∈[H],  (s_h, a_h)∈×.
Here $\phi: \cS\times\cA \mapsto \RR^{d_\phi}$ is a known feature embedding. Meanwhile, the state space $\cS\subseteq \RR^{d_\cS}$ is a subset of the Euclidean space with dimension $d_\cS$ and $W^* \in\RR^{d_{\cS}\times d_{\phi}}$ is the unknown true parameter of the KNR transition dynamics.

Correspondingly, in the sequel, we denote by $Q^\pi(\cdot, \cdot; \{r_h\}_{h\in[H]}, W)$ and $V^\pi(\cdot; \{r_{h}\}_{h\in[H]}, W)$ the value functions of the policy $\pi$ under the reward functions $\{r_h\}_{h\in[H]}$ and the transition dynamics defined by the matrix $W\in\RR^{d_{\cS}\times d_\phi}$. For the simplicity of our analysis, we fix the following scaling of features and parameters.
[Normalized Model]

We assume that $\|\phi(s, a)\|_2 \leq 1/\sqrt{H}$ for all $(s, a)\in\cS\times\cA$. correspondingly, we assume that $\|W^*\|_2 =\cO( \sqrt{H})$, where $W^*$ is the true parameter of the KNR transition dynamics defined in (<ref>).

Similar normalization assumptions also arises in [Mania et al., 2022]. We remark that the scaling assumptions in Assumption <ref> only affect the rate of $H$ in regret, and is imposed for the simplicity of our analysis.

§.§ Model-based RL for Unknown Transition Dynamics

In model-based RL, the agent optimizes the policy by iteratively fitting the transition dynamics based on the data collected, and conducting optimal planning on the fitted transition dynamics. For each iteration $k$, the model-based RL consists of the following steps.

* (i) Model Fitting. In this step, the agent updates the parameter $W_k$ of transition dynamics based on the replay buffer $\cD_k$.

* (ii) Planning. In this step, the agent conducts optimal planning based on the fitted parameter $W_k$ of transition dynamics. By planning with the fitted models, the agent updates the policy $\pi^k$.

* (iii) Interaction. In this step, the agent interacts with the environment with the policy $\pi^k$ and collects a trajectory $\iota_k = (s^k_1, a^k_1, \ldots, s^k_H, a^k_H, s^k_{H+1})$. The agent then updates the replay buffer by $\cD_{k+1} = \cD_k \cup \iota_k$.

In the sequel, we raise the following assumption, which assume that we have access to a planning oracle to handle the planning in step (ii).
[Planning Oracle]

We assume that we have access to the oracle $\text{Plan}(\cdot, \cdot, \cdot)$, which returns the optimal policy $\pi = \text{Plan}(s_1, \{r_h\}_{h\in[H]}, W)$ for any input reward functions $\{r_h\}_{h\in[H]}$ and the parameter $W$ of the transition dynamics.

In practice, the planning on fitted environment is typically handled by deep RL algorithms [Pathak et al., 2017, Luo et al., 2019, Pathak et al., 2019, Song and Sun, 2021] or model predictive control [Williams et al., 2015, Chua et al., 2018, Kakade et al., 2020]. We remark that since such planning is conducted on the fitted environment, solving such planning problem does not raise concerns in the sample complexity of solvers. In contrast, such sample complexity concern is raised when interacting with the real environment in step (iii). We remark that the goal of exploration is to obtain a near-optimal policy with as few round of interactions $K$ as possible. When measured with the regret $R(K)$ defined in (<ref>), the goal of exploration is to design algorithms to attain an regret $R(K)$ that grows as slow as possible in terms of $K$.

§ EXPLORATION WITH RANDOMIZED REWARD

In this section, we propose , an provably efficient and realizable algorithm for the RL problem with KNR dynamics. In the sequel, we describe the procedure of each step in the $k$-th iteration of .

(i) Model Fitting. Given the dataset $\cD_k = \{(s^\tau_h, a^\tau_h, s^\tau_{h+1})_{(h, \tau)\in[H]\times[k-1]}\}$, we fit the transition parameter $W^k$ by minimizing the prediction error of $s_{h+1}$ given $(s_h, a_h)$. Specifically, we minimize the following least-squares loss,
W^k ←_W ∈^d_×d_ϕ∑^H_h = 1∑^k-1_τ= 1s^τ_h+1 - W ϕ(s^τ_h, a^τ_h)^2_2 + λ·W^2_F,
where we denote by $\|\cdot\|_{F}$ the matrix Frobenius norm. The optimization in (<ref>) has the following explicit form solution,
W^k ←(∑^H_h = 1∑^k-1_τ= 1s^τ_h+1 ϕ(s^τ_h, a^τ_h)^⊤)Λ^-1_k,   Λ_k = ∑^H_h = 1∑^k-1_τ= 1ϕ(s^τ_h, a^τ_h)ϕ(s^τ_h, a^τ_h)^⊤+ λI.

(ii) Planning. In the planning stage, we aim to derive a policy $\pi^k$ that interact with the environment. There are two objectives that we aim to achieve in deriving the policy $\pi^k$. (a) Firstly, the policy $\pi^k$ should properly exploit our knowledge about the environment to optimize the cumulative reward. (b) Secondly, the policy $\pi^k$ should also incorporate our uncertainty to the environment and conduct exploration to unexplored critical events. To properly balance between (a) and (b), we need to quantify our uncertainty to the environment. Such uncertainty quantification can be done by the matrix $\Lambda_k$ defined in (<ref>). Specifically, it is known <cit.> that the matrix $\Lambda_k$ defines the following confidence region
_k = {W∈^d_×d_ϕ: (W - W^k)Λ^1/2_k^2_2 ≤β_k }.
For properly set $\beta_k$, it is known that $W^* \in \cG_k$ with high probability. Under such observation, previous attempts [Jaksch et al., 2010, Kakade et al., 2020] attain the balance between exploitation and exploration by finding the maximizer $\pi$ of $V^\pi(s_1; \{r_h\}_{h\in[H]}, W)$ for $W \in\cG_k$, which, however, is computationally intractable. To propose a computationally tractable alternative, previous empirical approaches utilizes ensemble models to estimate the epistemic uncertainty in fitting the model with finite observations.

In this work, we investigate the approach of directly incorporating uncertainty into the reward functions. To this end, we introduce the following perturbed reward function,
r^k_h, ξ(s_h, a_h) = {r_h(s_h, a_h) + ϕ(s_h, a_h)^⊤ξ^k_h}^+,   ∀h∈[H], (s_h, a_h)∈×,
where the noise $\{\xi^k_h\}_{h \in[H]}$ are sampled independently from the Gaussian distribution $\xi^k_h\sim N(0, \sigma^2_{k}\cdot \Lambda^{-1}_k)$. Intuitively, such noise has larger variance in regions that are less explored by the agent, and smaller variance in regions that are well-explored. In addition, we clip the reward to ensure that the reward is positive.

Upon perturbing the reward, we update the policy by planning based on the estimated transition and perturbed reward as follows,
π^k = {π^k_h}_h∈[H] = Plan(s_1, {r^k_h, ξ }_h∈[H], W^k).
We remark that the reward perturbation in (<ref>) is conducted before planning. The perturbed reward defined in (<ref>) is fixed throughout the planning stage. We summarize in Algorithm <ref>.

Planning with Randomized Reward

[1]
Dataset $\cD$, rewards $\{r_h\}_{h\in[H]}$.
Initialization: Set $\Lambda_1 = \lambda\cdot I$.
$ k = 1, 2, \ldots, K $
Generate a set of independent noise $\xi^k_h \sim N(0, \sigma^2_{k}\cdot \Lambda^{-1}_k)$ for all $h\in[H]$.
Obtain the perturbed rewards
r^k_h, ξ(s_h, a_h) = {r_h(s_h, a_h) + ϕ(s_h, a_h)^⊤ξ^k_h}^+,   ∀(s_h, a_h)∈×,  h∈[H].
Obtain the policy $\pi^k$ by calling the planning oracle,
π^k = Plan(s_1, {r^k_h, ξ }_h∈[H], W^k).
Execute $\pi^k$ to sample a trajectory $\tau^k = \{s^k_1, a^k_1, s^k_2, ..., s^k_{H}, a^k_{H}, s^k_{H+1}\}$.
Update the dataset $\cD_k \leftarrow \cD_{k-1} \cup \tau^k$.
Update the model and covariate matrix
W^k+1    ←_W∈×d ∑^H_h=1∑^k_τ= 0 s^τ_h+1 - W ϕ(s^τ_h, a^τ_h)^2_2 + λ·W^2_2,

Λ_k+1    ←Λ_k + ∑^H_h=1ϕ(s^k_h, a^k_h)ϕ(s^k_h, a^k_h)^⊤.

§ THEORETICAL ANALYSIS

In this section, we analyze in Algorithm <ref>. Our key observations are,

* the reward perturbation in leads to optimistic planning for at least a constant proportion of the interactions, and

* such partial optimism guaranteed by is sufficient for exploration.

§.§ Partial Optimism

In the sequel, we show that enjoys a partial optimism. Specifically, the following lemma holds.

Under the good event $W^* \in \cG_k = \{W\in\RR^{d_\cS\times d_\phi}: \|(W - W^k)\Lambda^{1/2}_k\|^2_2 \leq \beta_k\}$, for properly selected $\sigma_k$, it holds with probability at least $\Phi(-1)$ that
V^*_1(s_1; {r_h}_h∈[H], W^*)  - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)  ≤0,
where $\Phi(\cdot)$ is the cumulative distribution function of the standard Gaussian distribution.

See <ref> for a detailed proof.

Lemma <ref> ensures that at least $\Phi(-1)$ of the value function estimation in overestimates the optimal value function $V^*_1(\cdot;\{r_h\}_{h\in[H]}, W^*)$ that we wish to obtain. As a consequence, the randomized reward in guarantees that at least $\Phi(-1)$ of the trajectories contributes to exploration under the optimism principle. Intuitively, such optimism holds since, (i) on the one hand, the randomized Gaussian perturbation ensures that the perturbed reward has a sufficiently large probability to be larger than the true reward, and (ii) on the other hand, the good event $\cG_{k}$ ensures that the value functions estimated under the true model $(\{r_h\}_{h\in[H]}, W^*)$ does not deviate too much from the value function estimated under the current model $(\{r_h\}_{h\in[H]}, W^k)$ without perturbation.

§.§ Regret Analysis

We highlight that the optimism guarantee in Lemma <ref> alone does not guarantee optimal regret. To conduct reasonable exploration, in addition to optimism, we need to ensure that the overestimation induced by perturbed reward does not deviated too far away from the value functions under the true reward. In our work, we ensure such deviation guarantee by properly incorporating the uncertainty into the transition dynamics. More specifically, recall that we define the reward perturbation as follows
r^k_h, ξ(s_h, a_h) = {r_h(s_h, a_h) + ϕ(s_h, a_h)^⊤ξ^k_h}^+,   ∀h∈[H], (s_h, a_h)∈×,
where the noise $\{\xi^k_h\}_{h \in[H]}$ are sampled independently from the Gaussian distribution $\xi^k_h\sim N(0, \sigma^2_{k}\cdot \Lambda^{-1}_k)$. Such perturbation introduces the noise $\xi^k_h$, whose variance scales with the model uncertainty $\Lambda_k$. Such reward perturbation ensures that, with a high probability, the bias in value estimation under the perturbed reward scales with the error in transition model estimation in (<ref>). Thus, as long as we have reasonable model estimation, such as minimizing least-squares error in (<ref>), the overestimation induced by perturbed reward is small. Specifically, the following Theorem guarantees that has an optimal regret in $K$.

Let $\lambda = 1$ and $\sigma_k^2 = H^3\cdot \beta_k/\sigma^2$ with $\beta_k$ specified in Appendix <ref>. Under Assumptions <ref> and <ref>, it holds for $K > 1/\Phi(-1)$ that
[R(K)] =( (d_+ d_ϕ)^3/2·H^7/2·log^2(K)·√(K)),
where the expectation is taken with respect to the randomized reward perturbation and trajectory sampling in .

See <ref> for a detailed proof.

We remark that the rate in Theorem <ref> is information-theoretically optimal in the number of interactions $K$ with the environment [Jiang et al., 2017]. We remark that comparing with the optimal planning approach such as LC3 [Kakade et al., 2020], suffers from extra dependencies in $H$, $d_\phi$ and $d_\cS$, which arises due to the random perturbation of rewards. In addition, we highlight that, comparing with PC-MLP [Song and Sun, 2021], our algorithm attains the optimal $\cO(\sqrt{K})$ dependency with respect to $K$. Such stronger sample efficiency arises as does not require extra sampling to compute policy cover matrix, which is required by PC-MLP.

Exploration with Model Uncertainty.
We remark that the high probability optimism based on Thompson sampling typically arises in the analysis of randomized value iterations for RL [Russo, 2019, Zanette et al., 2020]. In contrast, our work utilizes such idea for model-based exploration. To understand such counterpart in model-based exploration, we highlight that for both model-based and model-free exploration, designing provable exploration hinges on incorporating the model uncertainty into the value functions and its corresponding policy. In value-based approaches such as LSVI-UCB [Jin et al., 2020], such model uncertainty is estimated via regression of target value functions on $s_{h+1}$ with respect to $(s_h, a_h)$, and is incorporated into value functions as the bonus. In model-based approaches such as UCRL and its variants [Jaksch et al., 2010, Kakade et al., 2020], such model uncertainty is characterized by a confidence region of transition dynamics, and is incorporated into value functions via optimistic planning. In addition, for algorithms that utilizes policy cover [Song and Sun, 2021, Agarwal et al., 2020], such model uncertainty is obtained by aggregating the visitation trajectories of current policies. Our work instantiates such idea by directly perturbing the reward functions based on model uncertainty, which serves as a primitive view of all the exploration algorithms.

§ A GENERALIZATION WITH GENERAL FUNCTION APPROXIMATION

A key observation from the design of is that sufficient exploration is guaranteed as long as at least a fixed proportion of iterations are dedicated to exploration with optimism. To further validate such observation, we generalize by general function approximation in the sequel. We summarize the algorithm in Algorithm <ref>. To conduct our analysis, we assume that the estimation of transition dynamics is sufficiently accurate and satisfies the following calibrated model assumption.

Planning with Randomized Reward

[1]
Rewards $\{r_h\}_{h\in[H]}$.
Initialization: Initialize buffer $\cD_0$ as an empty set. Initialize the transition dynamics $\PP^1$.
$ k = 1, 2, \ldots, K $
Generate the randomized reward $\{r^k_{h, \xi}\}_{h\in[H]}$.
Obtain the policy $\pi^k$ by calling the planning oracle, $\pi^k = \textrm{Plan}(s_1, \{r^k_{h, \xi} \}_{h\in[H]}, \PP^k)$.
Execute $\pi^k$ to sample a trajectory $\tau^k = \{s^k_1, a^k_1, s^k_2, ..., s^k_{H}, a^k_{H}, s^k_{H+1}\}$.
Update the dataset $\cD_k \leftarrow \cD_{k-1} \cup \tau^k$.
Update the transition dynamics $\PP^{k+1}$ based on the dataset $\cD_k$.

[Calibrated model]

Let $\PP^k$ be the transition dynamics estimated in the $k$-th iteration. For all $\delta>0$ and $k\in[K]$, it holds with probability at least $1 - \delta$ that
(·s_h, a_h) -  ^k(·s_h, a_h)_1 ≤β(δ) ·ι_k(s_h, a_h),   ∀k∈[K],  (s_h, a_h)∈×.
Meanwhile, it holds that $\iota_k \leq 1$ for all $k\in[K]$.

Here the parameter $\beta(\delta)$ characterizes the variance in concentration, which typically scales with $\log(1/\delta)$. Similar assumption also arises in the analysis under general function approximation [Curi et al., 2020, Kidambi et al., 2021]. In addition, we remark that such assumption generalizes various commonly adopted parametric models, including the linear MDP model [Jin et al., 2020] and the KNR model [Kakade et al., 2020] we adopted in previous sections. Correspondingly, we propose the following complexity metric for the RL problems,
I_K = max_{_k}_k∈[K] ∑^K_k = 1∑^H_h = 1 ι^2_k(s^k_h, a^k_h).
Here the maximization is taken over all possible dataset $\{\cD_k\}_{k\in[K]}$ collected by an online learning algorithm with $|\cD_k| = H$ for all $k\in[K]$. We remark that similar complexity metric also arises in the analysis of model-based RL with general function approximations [Curi et al., 2020, Kakade et al., 2020, Kidambi et al., 2021].

We cast the following conditions on the reward randomization that ensures sufficient exploration.

It holds for the randomized reward function $\{r^k_{h, \xi}\}_{h\in[H]}$ that
∑^H_h = 1r^k_h, ξ(s_h, a_h) - r_h(s_h, a_h) ≥H·β(δ)·∑^H_h = 1ι_k(s_h, a_h),
which holds uniformly for all trajectories $\{(s_h, a_h)\}_{h\in[H]}$ with probability at least $p_0$.

[(Concentration of Rewards)]

It holds for all $\delta' > 0$ that $|r^k_{h, \xi} - r_h| \leq C_r(\delta')\cdot \iota_k$ with probability at least $1 - \delta'$ for all $(k,h)\in[K]\times[H]$, where $\iota_k$ is defined in Assumption <ref>.

Intuition Behind Reward Randomization Conditions. We remark that Conditions <ref> and <ref> are the key factors for the success of the randomized reward in . On the one hand, Condition <ref> ensures that a constant $p_0$ proportion of the evaluations results in optimistic value functions. Such optimistic value estimation further allows for exploration under the optimism principle. On the other hand, the concentration condition in Condition <ref> ensures that with high probability, the value function estimated under the randomized reward does not deviate too much from that evaluated under the true reward.

The following Theorem upper bounds the regret of Algorithm <ref> under Assumption <ref>.

Under Assumption <ref>, for the randomized reward that satisfies Conditions <ref> and <ref>, the regret of Algorithm <ref> is bounded as follows,
[R(K)] = (Poly(C_r(1/K), β(1/K), H)·I_K ·√(K)).

See <ref> for the detailed proof.

We remark that for commonly used model parameterization such as linear MDP and KNR, the parameter $\beta(1/K)$ typically scales with $\log(K)$. Meanwhile, for properly designed reward randomization scheme, the term $C_r(1/K)$ also scales with $\log(K)$. Thus, Theorem <ref> shows that Algorithm <ref> has a regret bound that scales with $\tilde\cO( I_K\cdot\sqrt{K})$, which matches the previous regret bound of exploration under model-based RL <cit.>.

§.§ Design of Randomized Reward

We remark that in practice, the model uncertainty $\{\iota_k\}_{k\in[K]}$ defined in Assumption <ref> can be estimated based on disagreement of ensemble models. Thus, to instantiate Algorithm <ref>, it remains to design proper reward randomization scheme that satisfies Conditions <ref> and <ref>. In what follows, we present examples of such randomized rewards.

[Gaussian Perturbation]

Let $r^k_{h, \xi}(s^k_h, a^k_h) = r(s^k_h, a^k_h) + \xi^k_h$, where $\{\xi^k_h\}_{(k, h)\in[K]\times[H]}$ are sampled independently from the Gaussian distribution $N(0, \sigma_k\cdot \iota^2_k(s^k_h, a^k_h))$. Under regulation conditions specified in <ref>, the randomized reward $\{r^k_{h, \xi}\}_{(k, h)\in[K]\times[H]}$ satisfies Conditions <ref> and <ref>.

[Bernoulli Perturbation]

Let $r^k_{h, \xi}(s^k_h, a^k_h) = r(s^k_h, a^k_h) + \xi^k_h\cdot \sigma'_{k}\iota_k(s^k_h, a^k_h)$, where $\xi^k_h = 1$ with probability $1/2$ and $\xi^k_h=-1$ with probability $1/2$. For the parameters $\{\sigma'_{k}\}_{(k)\in[K]}$ specified in <ref>, the randomized reward $\{r^k_{h, \xi}\}_{(k, h)\in[K]\times[H]}$ satisfies Conditions <ref> and <ref>.

A Comparison with Bonus-based Approaches.
We remark that our proposed randomized reward is closely related to the reward bonus for model-based RL, which arises in the recent progress of exploration under model-based RL [Kidambi et al., 2021, Song and Sun, 2021]. Such bonus-based approaches typically estimate the model uncertainty $\{\iota_k\}_{k\in[K]}$ and then design reward bonus that incorporates such uncertainty estimation. Indeed, one may view the randomized rewards in Examples <ref> and <ref> as a randomized generalization of such reward bonus.
Specifically, both the randomized reward and the reward bonus accomplishes exploration with optimism principle. For randomized reward, such exploration is guaranteed by the partial optimism that we investigated in <ref>. In contrast, for reward bonus, such exploration is guaranteed by directly enforcing optimism with bonus.

Given the connections between the reward bonus and randomized reward, one may be prompt to ask why using randomized reward? We highlight that adding bonus is, in fact, a pessimistic approach in order to reduce the worst-case regret. Such approach enforces a bonus that deviates from the true reward, aiming to introduce a bias in value estimations to achieve minimal worst-case regret. In comparison, randomized reward allows the perturbation to be centered around the true reward, and yields a milder deviation from the true reward. In addition, as shown in our work, such perturbation also has a worst-case regret guarantee at $\tilde\cO(\sqrt{K})$ order.

[Abbasi-Yadkori et al., 2011]
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.
Improved algorithms for linear stochastic bandits.
In Advances in Neural Information Processing Systems (NIPS),
pages 2312–2320, Granada, Spain, 2011.

[Agarwal et al., 2020]
Alekh Agarwal, Mikael Henaff, Sham M. Kakade, and Wen Sun.
PC-PG: policy cover directed exploration for provable policy
gradient learning.
In Advances in Neural Information Processing Systems
(NeurIPS), virtual, 2020a.

[Agarwal et al., 2020]
Alekh Agarwal, Sham M. Kakade, Akshay Krishnamurthy, and Wen Sun.
FLAMBE: structural complexity and representation learning of low
rank MDPs.
In Advances in Neural Information Processing Systems
(NeurIPS), virtual, 2020b.

[Ayoub et al., 2020]
Alex Ayoub, Zeyu Jia, Csaba Szepesvári, Mengdi Wang, and Lin Yang.
Model-based reinforcement learning with value-targeted regression.
In Proceedings of the 37th International Conference on Machine
Learning (ICML), pages 463–474, Virtual Event, 2020.

[Cai et al., 2020]
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang.
Provably efficient exploration in policy optimization.
In Proceedings of the 37th International Conference on Machine
Learning (ICML), pages 1283–1294, Virtual Event, 2020.

[Chua et al., 2018]
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine.
Deep reinforcement learning in a handful of trials using
probabilistic dynamics models.
In Advances in Neural Information Processing Systems
(NeurIPS), pages 4759–4770, Montréal, Canada, 2018.

[Curi et al., 2020]
Sebastian Curi, Felix Berkenkamp, and Andreas Krause.
Efficient model-based reinforcement learning through optimistic
policy search and planning.
In Advances in Neural Information Processing Systems
(NeurIPS), virtual, 2020.

[Du et al., 2020]
Simon S. Du, Sham M. Kakade, Ruosong Wang, and Lin F. Yang.
Is a good representation sufficient for sample efficient
reinforcement learning?
In Proceedings of the 8th International Conference on Learning
Representations (ICLR), Addis Ababa, Ethiopia, 2020.

[Ha and Schmidhuber, 2018]
David Ha and Jürgen Schmidhuber.
World models.
arXiv preprint arXiv:1803.10122, 2018.

[Hafner et al., 2019]
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi.
Dream to control: Learning behaviors by latent imagination.
arXiv preprint arXiv:1912.01603, 2019.

[Ishfaq et al., 2021]
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang,
Doina Precup, and Lin Yang.
Randomized exploration in reinforcement learning with general value
function approximation.
In Proceedings of the 38th International Conference on Machine
Learning (ICML), pages 4607–4616, Virtual Event, 2021.

[Jaksch et al., 2010]
Thomas Jaksch, Ronald Ortner, and Peter Auer.
Near-optimal regret bounds for reinforcement learning.
J. Mach. Learn. Res., 11:0 1563–1600, 2010.

[Jiang et al., 2017]
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E.
Contextual decision processes with low Bellman rank are
In Proceedings of the 34th International Conference on Machine
Learning (ICML), pages 1704–1713, Sydney, Australia, 2017.

[Jin et al., 2020]
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan.
Provably efficient reinforcement learning with linear function
In Proceedings of the Conference on Learning Theory (COLT),
pages 2137–2143, Virtual Event [Graz, Austria], 2020.

[Kaiser et al., 2020]
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H.
Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski,
Sergey Levine, Afroz Mohiuddin, Ryan Sepassi, George Tucker, and Henryk
Model based reinforcement learning for atari.
In Proceedings of the 8th International Conference on Learning
Representations (ICLR), Addis Ababa, Ethiopia, 2020.

[Kakade et al., 2020]
Sham M. Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen
Information theoretic regret bounds for online nonlinear control.
In Advances in Neural Information Processing Systems
(NeurIPS), virtual, 2020.

[Kidambi et al., 2021]
Rahul Kidambi, Jonathan Chang, and Wen Sun.
MobILE: Model-based imitation learning from observation alone.
In Advances in Neural Information Processing Systems
(NeurIPS), pages 28598–28611, virtual, 2021.

[Lu and Roy, 2019]
Xiuyuan Lu and Benjamin Van Roy.
Information-theoretic confidence bounds for reinforcement learning.
In Advances in Neural Information Processing Systems
(NeurIPS), pages 2458–2466, Vancouver, Canada, 2019.

[Luo et al., 2019]
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu
Algorithmic framework for model-based deep reinforcement learning
with theoretical guarantees.
In Proceedings of the 7th International Conference on Learning
Representations (ICLR), New Orleans, LA, 2019.

[Mania et al., 2022]
Horia Mania, Michael I. Jordan, and Benjamin Recht.
Active learning for nonlinear system identification with guarantees.
J. Mach. Learn. Res., 23:0 32:1–32:30, 2022.

[Modi et al., 2021]
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal.
Model-free representation learning and exploration in low-rank
arXiv preprint arXiv:2102.07035, 2021.

[Osband and Roy, 2014]
Ian Osband and Benjamin Van Roy.
Model-based reinforcement learning and the eluder dimension.
In Advances in Neural Information Processing Systems (NIPS),
pages 1466–1474, Montreal, Canada, 2014.

[Pacchiano et al., 2020]
Aldo Pacchiano, Philip Ball, Jack Parker-Holder, Krzysztof Choromanski, and
Stephen Roberts.
On optimism in model-based reinforcement learning.
arXiv preprint arXiv:2006.11911, 2020.

[Pathak et al., 2017]
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell.
Curiosity-driven exploration by self-supervised prediction.
In Proceedings of the 34th International Conference on Machine
Learning (ICML), pages 2778–2787, Sydney, Australia, 6-11 August 2017,

[Pathak et al., 2019]
Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta.
Self-supervised exploration via disagreement.
In Proceedings of the 36th International Conference on Machine
Learning (ICML), pages 5062–5071, Long Beach, CA, 2019.

[Russo, 2019]
Daniel Russo.
Worst-case regret bounds for exploration via randomized value
In Advances in Neural Information Processing Systems
(NeurIPS), pages 14410–14420, Vancouver, Canada, 2019.

[Song and Sun, 2021]
Yuda Song and Wen Sun.
PC-MLP: model-based reinforcement learning with policy cover guided
In Proceedings of the 38th International Conference on Machine
Learning (ICML), pages 9801–9811, Virtual Event, 2021.

[Sun et al., 2019]
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford.
Model-based RL in contextual decision processes: PAC bounds and
exponential improvements over model-free approaches.
In Proceedings of the Conference on Learning Theory (COLT),
pages 2898–2933, Phoenix, AZ, 2019.

[Sutton and Barto, 2018]
Richard S Sutton and Andrew G Barto.
Reinforcement Learning: An Introduction.
MIT press, 2018.

[Veraar, 2010]
Mark Veraar.
On khintchine inequalities with a weight.
Proceedings of the American Mathematical Society, pages
4119–4121, 2010.

[Wang et al., 2020]
Ruosong Wang, Simon S. Du, Lin F. Yang, and Ruslan Salakhutdinov.
On reward-free reinforcement learning with linear function
In Advances in Neural Information Processing Systems
(NeurIPS), virtual, 2020.

[Watter et al., 2015]
Manuel Watter, Jost Tobias Springenberg, Joschka Boedecker, and Martin A.
Embed to control: A locally linear latent dynamics model for
control from raw images.
In Advances in Neural Information Processing Systems (NIPS),
pages 2746–2754, Montreal, Canada, 2015.

[Williams et al., 2015]
Grady Williams, Andrew Aldrich, and Evangelos Theodorou.
Model predictive path integral control using covariance variable
importance sampling.
arXiv preprint arXiv:1509.01149, 2015.

[Yang and Wang, 2019]
Lin Yang and Mengdi Wang.
Sample-optimal parametric q-learning using linearly additive
In Proceedings of the 36th International Conference on Machine
Learning (ICML), pages 6995–7004, Long Beach, CA, 2019.

[Zanette et al., 2020]
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and
Alessandro Lazaric.
Frequentist regret bounds for randomized least-squares value
In Proceedings of the 23rd International Conference on
Artificial Intelligence and Statistics (AISTATS), pages 1954–1964, Online
[Palermo, Sicily, Italy], 2020.

§ PROBLEM SETUP

We consider the following transition,
s_h+1 = W^* ϕ(s_h, a_h) + ,   h∈[H],
where $\epsilon \sim N(0, \sigma^2 I)$. We assume that the reward functions $r_h: \cS\times\cA \mapsto [0, 1]$ is known for all $h\in[H]$. We assume further that the feature embedding $\phi: \cS\times\cA \mapsto \RR^d$ is known and $\|\phi(s_h, a_h)\|_2 \leq 1/\sqrt{H}$ for all $(s_h, a_h)\in\cS\times\cA$. Let $\|W^*\|_2 = \cO(\sqrt{H})$ correspondingly.  The objective is to minimize the following regret in the online learning process,
R = ∑^K_k = 1 V^*(s_1; r, W^*) - V^π^k(s_1; r, W^*).

§ ALGORITHM

Planning with Randomized Model

[1]
Dataset $\cD$, rewards $\{r_h\}_{h\in[H]}$.
Initialization: Set $\Lambda_1 = \lambda\cdot I$.
$ k = 1, 2, \ldots, K $
Generate a set of independent noise $\xi^k_h \sim N(0, \sigma^2_{k}\cdot \Lambda^{-1}_k)$ for all $h\in[H]$.
Obtain the perturbed rewards
r^k_h, ξ(s_h, a_h) = {r_h(s_h, a_h) + ϕ(s_h, a_h)^⊤ξ^k_h}^+,   ∀(s_h, a_h)∈×,  h∈[H].
Obtain the policy $\pi^k$ by calling the planning oracle,
π^k = Plan(s_1, {r^k_h, ξ }_h∈[H], W^k).
Execute $\pi^k$ to sample a trajectory $\tau^k = \{s^k_1, a^k_1, s^k_2, ..., s^k_{H}, a^k_{H}, s^k_{H+1}\}$.
Update the dataset $\cD_k \leftarrow \cD_{k-1} \cup \tau^k$.
Update the model and covariate matrix
W^k+1    ←_W∈×d ∑^H_h=1∑^k_τ= 0 s^τ_h+1 - W ϕ(s^τ_h, a^τ_h)^2_2 + λ·W^2_2,

Λ_k+1    ←Λ_k + ∑^H_h=1ϕ(s^k_h, a^k_h)ϕ(s^k_h, a^k_h)^⊤.

§ PROOF OF MAIN RESULT

In this section, we present the proofs of main results in <ref>.

§.§ Good Events and Parameters

In what follows, we define the following good events for the analysis.

We define the following good events,
_W^k, good    = { W^* - W^k^2_Λ_k ≤β_k},  _ξ^k, good = { ξ^k_h^2_Λ^k≤β_k, ξ,   ∀h ∈[H]},

_ξ^k, opt    = { V^*_1(s_1; {r_h}_h∈[H], W^*)  - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k) ≤0}.
Correspondingly, we further define
_W, good = ⋂_k∈[K]_W^k, good,     _ξ, good = ⋂_k∈[K]_ξ^k, good.

In the sequel, we follow Lemma <ref> and set $\beta_k$ as follows
β_k = 2λ·W^*^2_2 + 8σ^2(d_·log(5) + 2log(k) + log(4) + log((Λ_k)/(Λ_0))),
where $\sigma$ is the noise variance that defines the transition dynamics in (<ref>). Correspondingly, we set the parameter $\sigma_k$ in as follows,
σ^2_k =  H^3·β_k/σ^2,
Meanwhile, we set the parameter $\beta_{k, \xi} = 2\sigma^2_k\cdot\log(KH/\delta)$ in Definition <ref>. It thus holds that $\PP(\cG_{\xi, \textrm{good}}) \geq 1 - \delta$.

§.§ Optimality

In the sequel, we present the optimality analysis of , which is inspired by [Russo, 2019] and [Zanette et al., 2020].

Under the good event $\cG_{W^k, \textrm{good}}$, it holds with probability at least $\Phi(-1)$ that
V^*_1(s_1; {r_h}_h∈[H], W^*)  - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)  ≤0.
In other words, it holds that $\PP(\cG_{\xi^k, \textrm{opt}} \given \cG_{W^k, \textrm{good}}) \geq \Phi(-1)$.

Note that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k) - V^*_1(s_1; {r_h}_h∈[H], W^*)

≥V^π^*_1(s_1; {r^k_h, ξ}_h∈[H], W^k)- V^*_1(s_1; {r_h}_h∈[H], W^*),

≥ϕ(s_1, a_1)^⊤ξ^k_1 - [V^*_2(s_2; {r_h}_h∈[H], W^*)   |  s_1, a_1, W^* ]

+ [V^π^*_2(s_2; {r^k_h, ξ}_h∈[H], W^k)   |  s_1, a_1, W^k ],
where the second inequality holds since $\{r_1 + \phi^\top \xi^k_1\}^{+}  - r_1 = \max\{\phi^\top \xi^k_1, -r_1\}\geq \phi^\top \xi^k_1$. Here we denote by $\pi^*$ the optimal policy under the model $(\{r_h\}_{h\in[H]}, W^*)$ and $a_1$ the optimal action $a_1 = \pi^*(s_1)$. It further holds that,
[V^π^*_2(s_2; {r^k_h, ξ}_h∈[H], W^k)   |  s_1, a_1, W^k ] - [V^*_2(s_2; {r_h}_h∈[H], W^*)   |  s_1, a_1, W^* ]

=  [V^*_2(s_2; {r_h}_h∈[H], W^*)   |  s_1, a_1, W^k ] -[V^*_2(s_2; {r_h}_h∈[H], W^*)   |  s_1, a_1, W^* ]_(i)

+  [V^π^*_2(s_2; {r^k_h, ξ}_h∈[H], W^k) - V^*_2(s_2; {r_h}_h∈[H], W^*)    |  s_1, a_1, W^k ]_(ii).
By Lemma <ref> and the fact that $V^*_h\leq H$ for all $h\in[H]$, we upper bound the absolute value of term (i) as follows,
|(i)| ≤H·(W^k- W^*)ϕ(s_1, a_1)_2/σ≤H ·W^k- W^*_Λ_l·ϕ(s_1, a_1)_Λ^-1_k.
Thus, under the event $\cG_{W^k, \textrm{good}})$, it further holds that
|(i)| ≤√(β_kH^2)/σ·ϕ(s_1, a_1)_Λ^-1_k.
By plugging (<ref>) into (<ref>) and further unrolling term (ii) based on similar computation in (<ref>) and (<ref>), we conclude that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k) - V^*_1(s_1; {r_h}_h∈[H], W^*)

≥∑^H_h = 1[ ϕ(s_h, a_h)^⊤ξ^k_h -  √(β_kH^2)/σ·ϕ(s_h, a_h)_Λ^-1_k s_1, π^*, W^k].
Note that for any given trajectory $\{(s_h, a_h)\}_{h\in[H]}$, it holds that
∑^H_h=1 ϕ(s_h, a_h)^⊤ξ^k_h ∼N(0, σ^2_k, H),   σ^2_k, H = σ^2_k·∑^H_h = 1ϕ(s_h, a_h)_Λ^-1_k^2.
It then holds from the setup $\sigma^2_{k} =  H^3\cdot \beta_k/\sigma^2$ and Cauchy-Schwartz inequality that
σ_k, H = √(H^3·β_k/σ^2·∑^H_h = 1ϕ(s_h, a_h)_Λ^-1_k^2) ≥√(β_k H^2)/σ·∑^H_h = 1ϕ(s_h, a_h)_Λ^-1_k.
Thus, for any given trajectory $\{(s_h, a_h)\}_{h\in[H]}$, it holds with probability at least $\Phi(-1)$ that
∑^H_h=1 ϕ(s_h, a_h)^⊤ξ^k_h ≥σ_k, H ≥√(β_kH^2)/σ·ϕ(s_h, a_h)_Λ^-1_k.
Hence, upon taking integration with respect to the trajectory under $s_1$, $\pi^*$, $W^k$, and the good event $\cG_{W^k, \textrm{good}}$, it holds with probability at least $\Phi(-1)$ that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k) - V^*_1(s_1; {r_h}_h∈[H], W^*)

≥∑^H_h = 1[ ϕ(s_h, a_h)^⊤ξ^k_h -  √(β_kH^2)/σ^2 ·ϕ(s_h, a_h)_Λ^-1_k s_1, π^*, W^k] ≥0.
Thus, we complete the proof of Lemma <ref>.

It holds for $K > 1/\Phi(-1)$ that
[∑^K_k = 1 V^*_1(s_1; {r_h}_h∈[H], W^*) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)   |  _W, good, _ξ, good ]= (√(K)).

In the sequel, we set $\delta = 1/K$ in the good events defined in Definition <ref>. We fix an arbitrary $k\in[K]$ and upper bound the following difference,
Δ_k = V^*_1(s_1; {r_h}_h∈[H], W^*) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k).
We construct a noise set $\{\tilde \xi^k_h\}_{h\in[H]}$, which is an identical and independent copy of the noise set $\{\xi^k_h\}_{h\in[H]}$. Correspondingly, we define the good events $\cG_{\tilde \xi, \textrm{good}}$ and $\cG_{\tilde \xi, \textrm{opt}}$ in Definition <ref>. We further define the optimal value function $V^{\tilde\pi^k}_1\bigl(s_1; \{r^k_{h, \tilde \xi}\}_{h\in[H]}, W^k)$ under the perturbed reward set $\{r_h + \phi^\top\tilde \xi^k_h\}_{h\in[H]}$ and the transition $W^k$. It thus follows from Lemma <ref> that
Δ_k    = V^*_1(s_1; {r_h}_h∈[H], W^*) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)

≤[ V^π̃^k_1(s_1; {r^k_h, ξ̃}_h∈[H], W^k)  |  _ξ̃, good, _ξ̃, opt] - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k).

We further define the value function corresponding to the minimal perturbation under the good event $\cG_{\xi, \textrm{good}}$ as follows,
{ξ^k_h}_h∈[H] = _ξ^k_h^2_Λ_k ≤β_k, ξ max_π V^π_1(s_1; {r_h + ϕ^⊤ξ^k_h}^+_h∈[H], W^k).
We define $r^k_{h, \underline \xi} =\{r_h + \phi^\top\underline\xi^k_h\}^{+}$ the corresponding perturbed reward. We further define $\underline \pi^k$ the corresponding optimal policy of the model $(\{r^k_{h, \underline \xi}\}_{h\in[H]}, W^k)$. Thus, under the good event $\cG_{\xi, \textrm{good}}$, we have
Δ_k ≤[ V^π̃^k_1(s_1; {r^k_h, ξ̃}_h∈[H], W^k) - V^π^k_1(s_1;{r^k_h, ξ}_h∈[H], W^k) |  _ξ̃, good, _ξ̃, opt].
Meanwhile, note that under the good event $\cG_{\tilde\xi^k, \textrm{good}}$, we have
V^π̃^k_1(s_1; {r^k_h, ξ̃}_h∈[H], W^k) ≥V^π^k_1(s_1;{r^k_h, ξ}_h∈[H], W^k).
In what follows, we write $V^{\tilde\pi^k}_1 = V^{\tilde\pi^k}_1(s_1; \{r^k_{h, \tilde \xi}\}_{h\in[H]}, W^k)$ and $V^{\underline\pi^k}_1 = V^{\underline\pi^k}_1(s_1;\{r^k_{h, \underline \xi}\}_{h\in[H]}, W^k)$ for notational simplicity. It holds that
_ξ̃[ V^π̃^k_1 - V^π^k_1 |  _ξ̃, good]    = _ξ̃[ V^π̃^k_1- V^π^k_1 |  _ξ̃^k, good, _ξ̃^k, opt] ·(_ξ̃^k, opt_ξ̃^k, good)

+ _ξ̃[ V^π̃^k_1- V^π^k_1 |  _ξ̃^k, good, ^c_ξ̃^k, opt] ·(^c_ξ̃^k, opt_ξ̃^k, good)

≥_ξ̃[ V^π̃^k_1 - V^π^k_1 |  _ξ̃^k, good, _ξ̃^k, opt] ·(_ξ̃^k, opt_ξ̃^k, good).
Meanwhile, it follows from Lemma <ref> that, under $\cG_{W, \textrm{good}}$,
(_ξ̃^k, opt_ξ̃^k, good) ≥(_ξ̃^k, opt∩_ξ̃^k, good) ≥1 - (^c_ξ̃^k, opt) - ( ^c_ξ̃^k, good) ≥Φ(-1) - δ.
By further plugging (<ref>) and (<ref>) into (<ref>), we obtain that
Δ_k    ≤(Φ(-1) - δ)^-1·_ξ̃[ V^π̃^k_1- V^π^k_1 |  _ξ̃^k, good]

= (Φ(-1) - δ)^-1·_ ξ[ V^π^k_1- V^π^k_1 |  _ξ^k, good],
where we use the fact that the noise set $\{\tilde \xi^k_h\}_{h\in[H]}$ is an identical and independent copy of the noise set $\{\xi^k_h\}_{h\in[H]}$.

It now remains to upper bound the difference $V^{\pi^k}_1- V^{\underline\pi^k}_1$ under the good events $\cG_{\xi, \good}$ and $\cG_{W, \good}$. Note that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)- V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)

≤V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)- V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k),
which holds since $\underline\pi^k$ is optimal for the model $( \{r^k_{h, \underline\xi}\}_{h\in[H]}, W^k)$. Meanwhile, by adding and subtracting the value function $V^{\pi^k}_1(s_1; \{r_{h}\}_{h\in[H]}, W^*)$ of $\pi^k$ under the true model $(\{r_{h}\}_{h\in[H]}, W^*)$ in (<ref>), we obtain that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)- V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)

≤V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)- V^π^k_1(s_1; {r_h}_h∈[H], W^*)_(iii)

+V^π^k_1(s_1; {r_h}_h∈[H], W^*) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)_(iv).#
In the sequel, we upper bound terms (iii) and (iv) in (<ref>) under the good events $\cG_{\xi, \good}$ and $\cG_{W, \good}$, respectively.

Upper bound of term (iii). The upper bound is similar to that in the proof of Lemma <ref>. Note that
(iii)    = V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)- V^π^k_1(s_1; {r_h}_h∈[H], W^*)

=max{ϕ(s_1, a_1)^⊤ξ^k_1, -r_1(s_1, a_1)} + ϕ(s_1, a_1)^⊤ξ^k_h + [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^k]

- [V^π^k_2(s_2; {r_h}_h∈[H], W^*)  |  s_1, π^k, W^*]

≤ϕ(s_1, a_1)_Λ^-1_k ·ξ^k_1_Λ_k + Δ^k_ξ, 1

+ [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k) - V^π^k_2(s_2; {r_h}_h∈[H], W^*)  |  s_1, π^k, W^*],
where the inequality follows from Cauchy-Schwartz inequality and the fact that $r_1 \geq 0$. Here we define $a_1 = \pi^k(s_1)$ and
Δ^k_ξ, 1 = [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^k] - [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^*].
Note that under the good event $\cG_{\xi, \good}$, it holds for all $(s_h, a_h)\in\cS\times\cA$ and $h\in[H]$ that
r^k_h, ξ(s_h, a_h)    ≤r(s_h, a_h) + |ϕ(s_h, a_h)^⊤ξ^k_h| ≤1 + ϕ(s_h, a_h)_Λ^-1_k·ξ^k_h_Λ_k

≤1 + √(β_k, ξ/(λ^2 H)).
Thus, it holds under the good event $\cG_{\xi, \good}$ that
0 ≤V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k) ≤H·(1 + √(β_k, ξ/(λ^2 H))) = H + √(β_k, ξ H)/λ.
By Lemma <ref>, it further holds under good events $\cG_{\xi, \good}$ and $\cG_{W, \good}$ that
Δ^k_ξ, 1    = [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^k] - [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^*].

≤(H + √(β_k, ξ H)/λ)·σ^-1·(W^k - W^*)ϕ(s_1, a_1)_2

≤(H + √(β_k, ξ H)/λ)·σ^-1·W^k - W^*_Λ_k·ϕ(s_1, a_1)_Λ^-1_k

≤(H + √(β_k, ξ H)/λ)·σ^-1·√(β_k) ·ϕ(s_1, a_1)_Λ^-1_k.
Here the first inequality follows from Lemma <ref> and the bounds in (<ref>), the second inequality follows from Cauchy-Schwartz inequality, and the third inequality follows from the definition of the good event $\cG_{W, \good}$ in Definition <ref>. Plugging (<ref>) and the definition of the good event $\cG_{\xi, \good}$ into (<ref>), we obtain that
(iii)     ≤C_k·ϕ(s_1, a_1)_Λ^-1_k

+ [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k) - V^π^k_2(s_2; {r_h}_h∈[H], W^*)  |  s_1, π^k, W^*],#
where we define
C_k =  (H + √(β_k, ξ H)/λ)·σ^-1·√(β_k) + √(β_k, ξ).
By further unrolling (<ref>), we conclude that, under the good events $\cG_{\xi, \good}$ and $\cG_{W, \good}$, we have
(iii) ≤[ ∑^H_h = 1C_k ·ϕ(s_h, a_h)_Λ^-1_k | s_1, π^k, W^*, _ξ^k, , _W^k, ].

Upper bound of term (iv). The upper bound of term (iv) is similar that of term (iii). Note that
(iv)    = V^π^k_1(s_1; {r_h}_h∈[H], W^*) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)

= min{-ϕ(s_1, a_1)^⊤ξ^k_h, r_1(s_1, a_1)} + [V^π^k_2(s_2; {r_h}_h∈[H], W^*)  |  s_1, π^k, W^*]

- [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^k]

≤-ϕ(s_1, a_1)^⊤ξ^k_h + Δ^k_ξ, 1

+ [V^π^k_2(s_2; {r_h}_h∈[H], W^*) - V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^*],
where we define
Δ^k_ξ, 1 = [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^*)  |  s_1, π^k, W^k] - [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^k].
By the definition of the minimal perturbation in (<ref>), it holds that $\|\underline \xi^k_h\|_{\Lambda_k} \leq \beta_{\xi}$ for all $(h, k)\in[H]\times[K]$. Thus, we have
-ϕ(s_1, a_1)^⊤ξ^k_h ≤β_k, ξ·ϕ(s_1, a_1)_Λ^-1_k.
The rest of the computation is almost identical to that in (iii). We omit the computation for simplicity and conclude that, under good events $\cG_{\xi, \good}$ and $\cG_{W, \good}$, we have
(iv) ≤[ ∑^H_h = 1C_k ·ϕ(s_h, a_h)_Λ^-1_k | s_1, π^k, W^*, _ξ^k, , _W^k, ],
where we define
C_k = (H + √(β_k, ξ H)/λ)·σ^-1·√(β_k) + √(β_k, ξ).

Thus, by plugging (<ref>) and (<ref>) into (<ref>), we conclude that
[Δ_k _W, good, _ξ, good]    ≤(Φ(-1) - δ)^-1·_ ξ[ V^π^k_1- V^π^k_1 |   _W^k, good, _ξ^k, good]

≤(Φ(-1) - δ)^-1 ·C_max·[ ∑^H_h = 1ϕ(s^k_h, a^k_h)_Λ^-1_k | _W^k, good, _ξ^k, good],
where we define
C_max = C_K = (H + √(β_K, ξ H)/λ)·σ^-1·√(β_K) + √(β_K, ξ) ≥C_k,   ∀k ∈[K],
and the expectation is taken with respect to the trajectories of $\pi^k$ under the transition defined by $W^*$. Recall that we set $\lambda = 1$, $\delta = 1/K$, and $\sigma_k = H^3\cdot \beta_k/\sigma^2$. Thus, under Assumption <ref>, we obtain that
β_K    = (H + d_+log(K) + d_ϕ·log(K)),

β_K, ξ    = 2σ^2_K·log(K/δ) = (H^4·log(KH) + (d_+ d_ϕ)·H^3·log^2(KH)).
Thus, upon computation, we have
C_max = ((d_+ d_ϕ)·H^3·log^3/2(KH)).

Finally, it holds that
[∑^K_k = 1 V^*_1(s_1; {r_h}_h∈[H], W^*) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)   |  _W, good, _ξ, good ]

≤(Φ(-1) - 1/K)^-1 ·C_max·[ ∑^K_k = 1∑^H_h = 1ϕ(s^k_h, a^k_h)_Λ^-1_k | _W, good, _ξ, good]

≤(Φ(-1) - 1/K)^-1 ·C_max·[( HK·∑^K_k = 1∑^H_h = 1ϕ(s^k_h, a^k_h)^2_Λ^-1_k )^1/2 | _W, good, _ξ, good]

= ( (d_+ d_ϕ)^3/2·H^7/2·log^2(KH)·√(K)),
where the expectation is taken with respect to the trajectories of $\{\pi^k\}_{k\in[K]}$ under the true transition defined by $W^*$, and the last inequality follows from Lemma <ref> and the fact that $\log\det(\Lambda_{K+1})\leq d_\phi\cdot\log K$. Thus, we complete the proof of Lemma <ref>.

§.§ Estimation Error

It holds for $K > 1/\Phi(-1)$ that
[∑^K_k = 1 V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k) - V^π^k_1(s_1; {r_h}_h∈[H], W^*)   |  _W, good, _ξ, good ]= (√(K)).

Note that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)- V^π^k_1(s_1; {r_h}_h∈[H], W^*)

=max{ϕ(s_1, a_1)^⊤ξ^k_1, -r_1(s_1, a_1)} + ϕ(s_1, a_1)^⊤ξ^k_h + [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^k]

- [V^π^k_2(s_2; {r_h}_h∈[H], W^*)  |  s_1, π^k, W^*]

≤ϕ(s_1, a_1)_Λ^-1_k ·ξ^k_1_Λ_k + Δ^k_ξ, 1

+ [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k) - V^π^k_2(s_2; {r_h}_h∈[H], W^*)  |  s_1, π^k, W^*],
where the inequality follows from Cauchy-Schwartz inequality and the fact that $r_1 \geq 0$. Here we define $a_1 = \pi^k(s_1)$ and
Δ^k_ξ, 1 = [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^k] - [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^*].
Note that under the good event $\cG_{\xi, \good}$, it holds for all $(s_h, a_h)\in\cS\times\cA$ and $h\in[H]$ that
r^k_h, ξ(s_h, a_h)    ≤r(s_h, a_h) + |ϕ(s_h, a_h)^⊤ξ^k_h| ≤1 + ϕ(s_h, a_h)_Λ^-1_k·ξ^k_h_Λ_k

≤1 + β_ξ/λ.
Thus, it holds under the good event $\cG_{\xi, \good}$ that
0 ≤V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k) ≤H·(1 + β_ξ/λ).
By Lemma <ref>, it further holds under good events $\cG_{\xi, \good}$ and $\cG_{W, \good}$ that
Δ^k_ξ, 1    = [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^k] - [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k)  |  s_1, π^k, W^*].

≤H·(1 + β_ξ/λ)/σ·(W^k - W^*)ϕ(s_1, a_1)_2

≤H·(1 + β_ξ/λ)/σ·W^k - W^*_Λ_k·ϕ(s_1, a_1)_Λ^-1_k

≤H·(1 + β_ξ/λ)/σ·β_k ·ϕ(s_1, a_1)_Λ^-1_k.
Here the first inequality follows from Lemma <ref> and the bounds in (<ref>), the second inequality follows from Cauchy-Schwartz inequality, and the third inequality follows from the definition of the good event $\cG_{W, \good}$ in Definition <ref>. Plugging (<ref>) and the definition of the good event $\cG_{\xi, \good}$ into (<ref>), we obtain that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)- V^π^k_1(s_1; {r_h}_h∈[H], W^*) ≤C_k·ϕ(s_1, a_1)_Λ^-1_k

+ [V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], W^k) - V^π^k_2(s_2; {r_h}_h∈[H], W^*)  |  s_1, π^k, W^*],$
where $C_k$ is defined in (<ref>). By further unrolling (<ref>) and summing over $k\in[K]$, we conclude that
∑^K_k = 1V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)- V^π^k_1(s_1; {r_h}_h∈[H], W^*)

≤[∑^K_k = 1 ∑^H_h = 1C_k ·ϕ(s^k_h, a^k_h)_Λ^-1_k |  _W^k, good, _ξ^k, good ],
where the expectation is taken with respect to the trajectories of $\{\pi^k\}_{k\in[K]}$ under the true transition defined by $W^*$. The rest of the computation is identical to that of Lemma <ref>. We omit the computation and conclude that
[∑^K_k = 1 V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k) - V^π^k_1(s_1; {r_h}_h∈[H], W^*)   |  _W, good, _ξ, good ]= (√(K)).

§.§ Regret Analysis

We set $\lambda = 1$ and $\sigma_k$ as in <ref>. It holds for $K > 1/\Phi(-1)$ that
[R(K)] =( (d_+ d_ϕ)^3/2·H^7/2·log^2(KH)·√(K)).

It holds that
[R(K)]  = [∑^K_k = 1    V^*_1(s_1; {r_h}_h∈[H], W^*) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)

+ V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k) - V^π^k_1(s_1; {r_h}_h∈[H], W^*) ].
Thus, we have
[R(K)]  ≤Opt + Est + V_max·∑^K_k = 1 ((^c_W^k, )) + V_max·K·(^c_ξ, ),
where we define
Opt    = [∑^K_k = 1 V^*_1(s_1; {r_h}_h∈[H], W^*) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k)   |  _W, good, _ξ, good ],

Est    = [∑^K_k = 1 V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], W^k) - V^π^k_1(s_1; {r_h}_h∈[H], W^*)   |  _W, good, _ξ, good ].
Plugging the bounds of $\text{Opt}$ and $\text{Est}$ in Lemmas <ref> and <ref>, respectively, the fact that $V_{\max} = H$, and $\delta = 1/T$ into (<ref>), we conclude that
[R(K)] =( (d_+ d_ϕ)^3/2·H^7/2·log^2(KH)·√(K)).
Thus, we completes the proof of Theorem <ref>.

§ PROOF OF RESULT IN <REF>

In this section, we present the proofs of results in <ref>.

§.§ Regret Analysis

Similar to the proofs in <ref>, we define the good event $\cG_{\textrm{good}}$ as follows,
_good= {   |r_h - r^k_h, ξ| ≤C_r(δ')·ι_k,   (·s, a) - ^k(·s, a)_1 ≤β_k(δ)·ι_k(s, a),

∀(k, h)∈[K]×[H],  (s, a)∈×}.
Under Assumption <ref>, it holds for the randomized reward satisfying Condition <ref> that $\PP(\cG_{\textrm{good}}) \geq 1 - \delta' - \delta$.

Under Assumptions <ref> and the good event $\cG_{\textrm{good}}$, it holds for the randomized reward satisfying Condition <ref> that
V^*_1(s_1; {r_h}_h∈[H], ) ≤V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) ≥1/2
with probability at least $p_0$.

The proof is similar to that for Lemma <ref>. Note that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^*_1(s_1; {r_h}_h∈[H], )

≥V^π^*_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^*(s_1; {r_h}_h∈[H], )

= r^k_h, ξ(s_1, π^*(s_1)) - r_h(s_1, π^*(s_1)) +[V^π^*_2(s_2; {r^k_h, ξ}_h∈[H], ^k) |  s_1, π^*, ^k  ]

- [V^*_2(s_2; {r_h}_h∈[H], ) |  s_1, π^*, ],
where we denote by $\pi^*$ the optimal policy under the environment defined by $(\{r_h\}_{h\in[H]}, \PP)$, and the first inequality follows from the optimality of $\pi^k$ under the environment defined by $(\{r^k_{h, \xi}\}_{h\in[H]}, \PP^k)$. Meanwhile, it holds that
[V^π^*_2(s_2; {r^k_h, ξ}_h∈[H], ^k) |  s_1, π^*, ^k  ] - [V^*_2(s_2; {r_h}_h∈[H], ) |  s_1, π^*, ]

= [V^*_2(s_2; {r_h}_h∈[H], ) |  s_1, π^*, ^k  ] - [V^*_2(s_2; {r_h}_h∈[H], ) |  s_1, π^*, ]_(i)

+ [V^π^*_2(s_2; {r^k_h, ξ}_h∈[H], ^k) - V^*_2(s_2; {r_h}_h∈[H], ) |  s_1, π^*, ^k  ]_(ii).
By Assumption <ref>, Hölder's inequality, and the fact that $V^*_1\leq H$, it holds under the good event $\cG_{\textrm{good}}$ that
|(i)| ≤[ H·(- ^k)(·s_1, a_1)_1 s_1, π^*] ≤[ H·β(δ)·ι_k(s_1, a_1) s_1, π^*].
By further unrolling term (ii) in (<ref>), we conclude from (<ref>) that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^*_1(s_1; {r_h}_h∈[H], )

≥[∑^H_h = 1 r^k_h, ξ(s_1, a_1) - r_h(s_1, a_1) - H·β_k∑^H_h = 1ι_k(s_h, a_h) |  s_1, π^*, ^k ].
Thus, under the optimism condition in Condition <ref>, it holds that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^*_1(s_1; {r_h}_h∈[H], ) ≥0
with probability at least $p_0 - \delta$.

For $\delta' \leq p_0$, it holds with probability at least $1 - \delta - \delta'$ that
[∑^K_k = 1V^*_1(s_1; {r_h}_h∈[H], ) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k)  |  _good] =(C(δ, δ')·I_K·√(K) ),
where we define $C(\delta, \delta')= C_r(\delta') + H\cdot(1 + C_r(\delta'))\cdot\beta(\delta)$.

The proof is similar to that of Lemma <ref> in <ref>.

We define the following minimal perturbed value function,
V^π^k_1 = _r̃ ∈_good _π V^π_1(s_1; {r̃_h}_h∈[H], ^k).
Following the same computation as in the proof of Lemma <ref>, we obtain that
[∑^K_k = 1V^*_1(s_1; {r_h}_h∈[H], ) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k)  |  _good]

≤(p_0 - δ)^-1·[∑^K_k = 1V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^π^k_1(s_1; {r̃_h}_h∈[H], ^k)  |  _good]_Δ_k.
By further adding and subtracting $V^{\pi^k}(s_1; \{r_h\}, \PP)$, we obtain that
Δ_k    = [∑^K_k = 1V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^π^k(s_1; {r_h}, )  |  _good]_(iii)

+ [∑^K_k = 1 V^π^k(s_1; {r_h}, ) - V^π^k_1(s_1; {r̃_h}_h∈[H], ^k)  |  _good]_(iv).
Thus, upon a similar computation to that in <ref>, under the good event $\cG_{\textrm{good}}$, it further holds that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^π^k(s_1; {r_h}, ) ≤[C(δ, δ')∑^H_h = 1ι_k(s_h, a_h)  |  s_1, π^k, ],
where we define
C(δ, δ')= C_r(δ') + H·(1 + C_r(δ'))·β(δ).
Here we use the fact that $\|V^{\pi^k}_h\bigl(\cdot; \{r^k_{h, \xi}\}_{h\in[H]}, \PP^k)\|_{\infty}\leq H\cdot(1 + C_r(\delta'))$ under the good event $\cG_{\textrm{good}}$. The same bound holds for term (iv) in (<ref>) following the fact that $\tilde r \in \cG_{\textrm{good}}$. Thus, by plugging (<ref>) into (<ref>), we conclude that
[∑^K_k = 1V^*_1(s_1; {r_h}_h∈[H], ) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k)  |  _good]

≤C(δ, δ')·(p_0 - δ)^-1·[∑^K_k = 1∑^H_h = 1C_k·σ_k(s_h, a_h)  |  _good ]

≤C(δ, δ')·(p_0 - δ)^-1·√(HK)·[(∑^H_h = 1ι^2_k(s_h, a_h) )^1/2 |  _good ],
By further plugging into the definition of $I_K$ in (<ref>), we obtain that
[∑^K_k = 1V^*_1(s_1; {r_h}_h∈[H], ) - V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k)  |  _good] =(C(δ, δ')·I_K·√(K) ),
which concludes the proof of Lemma <ref>.

It holds that
[∑^K_k = 1 V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^π^k_1(s_1; {r_h}_h∈[H], ) |  _good]= (C(δ, δ')·I_K·√(K) ).

Under the good event $\cG_{\textrm{good}}$, it holds that
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^π^k_1(s_1; {r_h}_h∈[H], )

≤C_r·σ^k(s_1, a_1) +  [   V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], ^k)  |  s_1, π^k, ^k]

- [V^π^k_2(s_2; {r_h}_h∈[H], ) s_1, π^k, ]

≤C_r·σ^k(s_1, a_1) + Δ^k_ξ, 1

+ [  V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], ^k) - V^π^k_2(s_2; {r_h}_h∈[H], ) s_1, π^k, ],
where we define $a_1 = \pi^k_1(s_1)$ and
Δ^k_ξ, 1 = [   V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], ^k)  |  s_1, π^k, ^k] - [   V^π^k_2(s_2; {r^k_h, ξ}_h∈[H], ^k)  |  s_1, π^k, ].
Under the good event $\cG_{\textrm{good}}$, it holds from Hölder's inequality that
Δ^k_ξ, 1 ≤H·(1 + C_r(δ'))·β_k·ι_k(s_1, a_1).
By plugging (<ref>) into (<ref>) and further unrolling (<ref>), we obtain that, under the good event $\cG_{\textrm{good}}$,
V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^π^k_1(s_1; {r_h}_h∈[H], )

≤C(δ, δ')·[  ∑^H_h = 1ι_k(s_h, a_h) s_1, π^k, ],
where we define $
C(\delta, \delta')= C_r(\delta') + H\cdot(1 + C_r(\delta'))\cdot\beta(\delta)
$. Thus, by summing (<ref>) over $k\in[K]$, we obtain that
[∑^K_k = 1 V^π^k_1(s_1; {r^k_h, ξ}_h∈[H], ^k) - V^π^k_1(s_1; {r_h}_h∈[H], ) |  _good]

≤C(δ, δ') ·[∑^K_k = 1 ∑^H_h = 1 σ_k(s^k_h, a^k_h) |  _good] ≤C(δ, δ')·√(HK)·I_K,
where $I_K$ is defined in (<ref>). Thus, we complete the proof of Lemma <ref>.

Let $\delta = \delta' = 1/K$. Under Assumption <ref>, for the randomized reward that satisfies Conditions <ref> and <ref>, we have
[R(K)] = ((C_r(1/K) + H·(1 + C_r(1/K))·β(1/K))·√(H^2K)·I_K).

Combining Lemmas <ref> and <ref>, it holds that
[∑^K_k = 1V^*_1(s_1; {r_h}_h∈[H], ) - V^π^k_1(s_1; {r_h}_h∈[H], ^k)  |  _good] =(C(δ, δ')·I_K·√(K) ).
Meanwhile, under Assumption <ref>, it holds for rewards that satisfies <ref> that $\PP(\cG_{\textrm{good}}) 1 - \delta - \delta'$. Thus, for $\delta = \delta' = 1/K$, we have
[∑^K_k = 1V^*_1(s_1; {r_h}_h∈[H], ) - V^π^k_1(s_1; {r_h}_h∈[H], ^k)  |  ^c_good] ≤2K·(δ+ δ') = 4.
Combining (<ref>) and (<ref>), it holds that
[R(K)]    = (C(1/K, 1/K)·√(H^2K)·I_K)

= ((C_r(1/K) + H·(1 + C_r(1/K))·β(1/K))·√(H^2K)·I_K),
which concludes the proof of Theorem <ref>.

§.§ Verification of Example

In the sequel, we verify that Examples <ref> and <ref> satisfies Conditions <ref> and <ref>.

[Gaussian Reward]
r^k_h, ξ(s_h, a_h) ∼N(r_h(s_h, a_h), H·β(δ)·σ^2_k(s_h, a_h)),
which are sampled independently over $(s_h, a_h)\in\cS\times\cA$. It holds that the probability of
∑^H_h = 1r^k_h, ξ(s_h, a_h) - r_h(s_h, a_h) ≥H·β(δ) ∑^H_h = 1σ_k(s_h, a_h)
is greater than the following event,
N(0, H·∑^H_h = 1σ^2_k(s_h, a_h)) ≥√(H·β(δ) ∑^H_h = 1σ^2_k(s_h, a_h)),
which holds with probability at least $\Phi(-1)$. In addition, if $r/\sigma_k$ are lipschitz functions of $(s, a)\in\cS\times\cA$ and $\cS\times\cA$ has a covering number $\cC_{\cS\times\cA}$ under the same metric, it further holds that $|r^k_{h, \xi} - r_h| \leq \sqrt{H\cdot\beta(\delta)\cdot\log(\cC_{\cS\times\cA}\cdot HK/\delta')}\cdot\sigma_k$ with probability at least $1 - \delta'$. Thus, Conditions <ref> and <ref> are satisfied.

[Bernoulli Reward]
r^k_h, (s_h, a_h) ∼r(s_h, a_h) + 2√(H)·β(δ)·σ_k(s_h, a_h)·ϵ_h,
where $\epsilon_h = 1$  with probability $1/2$ and $\epsilon_h = -1$ with probability $1/2$. For any trajectory $\tau$, it holds from the Khintchine's inequality [Veraar, 2010] that
∑^H_h = 1√(H)·β(δ)·σ_k(s_h, a_h)·ϵ_h /S(τ) ≥1/2
with probability at least $p_0 = 3/16$, where we define
S(τ) = H ∑^H_h = 1β^2(δ)·σ^2_k(s_h, a_h).
Thus, it holds that
∑^H_h = 1r^k_h, (s_h, a_h) - r(s_h, a_h)    ≥2∑^H_h = 1√(H)·β(δ)·σ_k(s_h, a_h)·ϵ_h

≥S(τ) ≥∑^H_h = 1β(δ)·σ_k(s_h, a_h)
with probability at least $p_0 = 3/16$. In addition, it holds that $|r^k_{h, \eps}(s_h, a_h) - r(s_h, a_h)| \leq 2\sqrt{H}\cdot \beta(\delta)\cdot\sigma_k(s_h, a_h)$. Thus, Conditions <ref> and <ref> are satisfied.

§ AUXILIARY LEMMA

It holds for
β_k = 2λ·W^*^2_2 + 8σ^2(d_·log(5) + 2log(k) + log(4) + log((Λ_k)/(Λ_0)))
∑^∞_k = 0 (^c_W^k, ) = ∑^∞_k = 0 (W^k - W^*^2_Λ_k≥β_k) ≤1/2.

See [Kakade et al., 2020] for a detailed proof.

Let $z_1 \sim N(\mu_1, \sigma^2)$ and $z_2 \sim N(\mu_2, \sigma^2)$ be two Gaussian random variables. Let $g$ be a positive measurable function. It holds that
_z_1∼N(μ_1, σ^2) [g(z_1)] - _z_2∼N(μ_1, σ^2) [g(z_2)] ≤min{μ_1 - μ_2_2/σ, 1}·√(_z_1∼N(μ_1, σ^2) [g^2(z_1)]).

See [Kakade et al., 2020] for a detailed proof.

Let $\|\phi^k_h\|_2 \leq 1/\sqrt{H}$ for all $(k, h)\in[K]\times[H]$. Let $\Lambda_1  = I$ and $\Lambda_{k+1} = \Lambda_k + \sum^H_{h = 1}\phi^k_h (\phi^k_h)^\top$. It holds that
∑^K_k = 1∑^H_h = 1 ϕ^k_h^2_Λ^-1_k ≤2log((Λ_K+1)·(Λ_0)^-1).

Note that we have $\Lambda_k \succ \Lambda_1 = I$. It thus holds that
0 ≤∑^H_h = 1(ϕ^k_h)^⊤Λ^-1_k ϕ^k_h ≤∑^H_h = 1ϕ^k_h^2_2 ≤1,   ∀k∈[K].
Meanwhile, since $x\leq 2\log(1+x)$ for $x \in [0, 1]$, we have
2log(1 + ∑^H_h=1(ϕ^k_h)^⊤Λ^-1_k ϕ^k_h) ≥∑^H_h = 1(ϕ^k_h)^⊤Λ^-1_k ϕ^k_h.
On the other hand, it follows from matrix determinant lemma that
log(Λ_k+1) - log(Λ_k) = log(I + Λ^-1/2_k ∑^H_h = 1(ϕ^k_h)(ϕ^k_h)^⊤Λ^-1/2_k_Ξ_k).
Let $\{\sigma_i\}_{i\in[d]}$ be the eigenvalues of the matrix $\Xi_k$. It holds that $\sigma_i > 0$ for all $i\in[d]$ and
log(I + Ξ_k) = logΠ_i∈[d] (1+σ_i) ≥log(1 + ∑_i∈[d]σ_i) = log(1 + (Ξ_k)).
Thus, we have
log(Λ_k+1) - log(Λ_k)    = log(I + Ξ_k) ≥log(1 + (Ξ_k))

=log(1 + ∑^H_h = 1(Λ^-1/2_k(ϕ^k_h)(ϕ^k_h)^⊤Λ^-1/2_k))

= log(1 + ∑^H_h=1(ϕ^k_h)^⊤Λ^-1_k ϕ^k_h).
Combining (<ref>) and (<ref>), we conclude that
∑^K_k = 1∑^H_h = 1 ϕ^k_h^2_Λ^-1_k ≤∑^K_k = 1 log(Λ_k+1) - log(Λ_k) =  2log((Λ_K+1)·(Λ_0)^-1),
which concludes the proof of Lemma <ref>.