Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds

## Abstract

Abstract Learning a transition model via Maximum Likelihood Estimation (MLE) followed by planning inside the learned model is perhaps the most standard and simplest Model-based Reinforcement Learning (RL) framework. In this work, we show that such a simple Model-based RL scheme, when equipped with optimistic and pessimistic planning procedures, achieves strong regret and sample complexity bounds in online and offline RL settings. Particularly, we demonstrate that under the conditions where the trajectory-wise reward is normalized between zero and one and the transition is time-homogenous, it achieves nearly horizon-free and second-order bounds. Nearly horizon-free means that our bounds have no polynomial dependence on the horizon of the Markov Decision Process. A second-order bound is a type of instance-dependent bound that scales with respect to the variances of the returns of the policies which can be small when the system is nearly deterministic and (or) the optimal policy has small values. We highlight that our algorithms are simple, fairly standard, and indeed have been extensively studied in the RL literature: they learn a model via MLE, build a version space around the MLE solution, and perform optimistic or pessimistic planning depending on whether operating in the online or offline mode. These algorithms do not rely on additional specialized algorithmic designs such as learning variances and performing variance-weighted learning and thus can easily leverage non-linear function approximations. The simplicity of the algorithms also implies that our horizon-free and second-order regret analysis is actually standard and mainly follows the general framework of optimism/pessimism in the face of uncertainty.

## 1 Introduction

The framework of model-based Reinforcement Learning (RL) often consists of two steps: fitting a transition model using data and then performing planning inside the learned model. Such a simple framework turns out to be powerful and has been used extensively in practice on applications such as robotics and control (e.g., (Aboaf et al., ; Deisenroth et al., ; Venkatraman et al., ; Williams et al., ; Chua et al., ; Kaiser et al., ; Yang et al., )).

The simplicity of model-based RL also attracts researchers to analyze its performance in settings such as online RL (Sun et al., ) and offline RL (Uehara and Sun, ). Mania et al. () showed that this simple scheme — fitting model via data followed by optimal planning inside the model, has a strong performance guarantee under the classic linear quadratic regulator (LQR) control problems. Liu et al. () showed that this simple MBRL framework when equipped with optimism in the face of the uncertainty principle, can achieve strong sample complexity bounds for a wide range of online RL problems with rich function approximation for the models. For offline settings where the model can only be learned from a static offline dataset, Uehara and Sun () showed that MBRL equipped with the pessimism principle can again achieve robust performance guarantees for a large family of MDPs. Ross and Bagnell () showed that in the hybrid RL setting where one has access to both online and offline data, this simple MBRL framework again achieves favorable performance guarantees without any optimism/pessimism algorithm design.

In this work, we do not create new MBRL algorithms, instead, we show that the extremely simple and standard MBRL algorithm – fitting models using Maximum Likelihood Estimation (MLE), followed by optimistic/pessimistic planning (depending on whether operating in online RL or offline RL mode), can already achieve surprising theoretical guarantees. Particularly, we show that under the conditions that trajectory-wise reward is normalized between zero and one, and the transition is time-homogenous, they can achieve nearly horizon-free and instance-dependent regret and sample complexity bounds, in both online and offline RL with non-linear function approximation. Nearly horizon-free bounds mean that the regret or sample complexity bounds have no explicit polynomial dependence on the horizon $H$. The motivation for studying horizon-free RL is to see if RL problems are harder than bandits due to the longer horizon planning in RL. *Our result here indicates that, even under non-linear function approximation, long-horizon planning is not the bottleneck of achieving statistical efficiency in RL.*
For instance-dependent bounds, we focus on second-order bounds. A second-order regret bound scales with respect to the variances of the returns of policies and also directly implies a first-order regret bound which scales with the expected reward of the optimal policy. Thus our instance-dependent bounds can be small under situations such as nearly-deterministic systems or the optimal policy having a small value.
When specializing to the case of deterministic ground truth transitions (but the algorithm does not need to know this a priori), we show that these simple MBRL algorithms demonstrate a faster convergence rate than the worst-case rates.
The key message of our work is

*Simple and standard MLE-based MBRL algorithms are sufficient for achieving nearly horizon-free and second-order bounds in online and offline RL with function approximation. *

We provide a fairly standard analysis to support the above claim. Our analysis follows the standard frameworks of optimism/pessimism in the face of uncertainty.
For online RL. we use $\ell_{1}$ Eluder dimension (Liu et al., ; Wang et al., ), a condition that uses both the MDP structure and the function class, to capture the structural complexity of exploration. For offline RL, we use the similar concentrability coefficient in Ye et al. () to capture the coverage condition of the offline data. The key technique we leverage is the *triangular discrimination* – a divergence that is equivalent to the squared Hellinger distance up to some universal constants. Triangular discrimination was used in contextual bandit and model-free RL for achieving first-order and second-order instance-dependent bounds (Foster and Krishnamurthy, ; Wang et al., , ). Here we show that it also plays an important role in achieving horizon-free bounds. Our contributions can be summarized as follows.

- 1.
Our results extend the scope of the prior work on horizon-free RL which only applies to tabular MDPs or MDPs with linear functions. Given a finite model class $\mathcal{P}$ (which could be exponentially large), we show that in online RL, the agent achieves an $O\left(\sqrt{(\sum_{k}\mathrm{VaR}_{\pi^{k}})\cdot d_{\text{RL}}\log(KH|
\mathcal{P}|/\delta)}+d_{\text{RL}}\log(KH|\mathcal{P}|/\delta)\right)$ regret, where $K$ is the number of episodes, $d_{\text{RL}}$ is the $\ell_{1}$ Eluder dimension, $\mathrm{VaR}_{\pi^{k}}$ is the variance of the total reward of policy $\pi^{k}$ learned in episode $k$ and $\delta\in(0,1)$ denotes the failure probability. Similarly, for offline RL, the agent achieves an $O\left(\sqrt{{C^{\pi^{*}}\mathrm{VaR}_{\pi^{*}}\log(|\mathcal{P}|/\delta)}/{K}
}+{C^{\pi^{*}}\log(|\mathcal{P}|/\delta)}/{K}\right)$ performance gap in finding a comparator policy $\pi^{*}$, where $C^{\pi^{*}}$ is the single policy concentrability coefficient over $\pi^{*}$, $K$ denotes the number of offline trajectories, $\mathrm{VaR}_{\pi^{*}}$ is the variance of the total reward of $\pi^{*}$. For offline RL with finite $\mathcal{P}$, our result is *completely horizon-free*, not even with $\log H$ dependence.
- 2.
When specializing to MDPs with deterministic ground truth transition (but rewards, and models in the model class could still be stochastic), we show that the same simple MBRL algorithms can adapt to the deterministic environment and achieve a better statistical complexity. For online RL, the regret becomes $O(d_{\text{RL}}\log(KH|\mathcal{P}|/\delta))$, which only depends on the number of episodes $K$ poly-logarithmically. For offline RL, the performance gap to a comparator policy $\pi^{*}$ becomes $O\left({C^{\pi^{*}}\log(|\mathcal{P}|/\delta)}/{K}\right)$, which is tighter than the worst-case $O(1/\sqrt{K})$ rate. All our results can be extended to continuous model class $\mathcal{P}$ using bracket number as the complexity measure.

Overall, our work identifies the *minimalist* algorithms and analysis for nearly horizon-free and instance-dependent (first & second-order) online & offline RL.

## 2 Related Work

#### Model-based RL.

Learning transition models with function approximation and planning with the learned model is a standard approach in RL and control. In the control literature, certainty-equivalence control learns a model from some data and plans using the learned model, which is simple but effective for controlling systems such as Linear Quadratic Regulators (LQRs) (Mania et al., ). In RL, such a simple model-based framework has been widely used in theory with rich function approximation, for online RL (Sun et al., ; Foster et al., ; Song and Sun, ; Zhan et al., ; Liu et al., , ; Zhong et al., ), offline RL (Uehara and Sun, ), RL with representation learning (Agarwal et al., ; Uehara et al., ), and hybrid RL using both online and offline data for model fitting (Ross and Bagnell, ). Our work builds on the maximum-likelihood estimation (MLE) approach, a standard method for estimating transition models in model-based RL.

#### Horizon-free and Instance-dependent bounds.

Most existing works on horizon-free RL typically focus on tabular settings or linear settings. For instance, Wang et al. () firstly studied horizon-free RL for tabular MDPs and proposed an algorithm that depends on horizon logarithmically. Several follow-up work studied horizon-free RL for tabular MDP with better sample complexity (Zhang et al., ), offline RL (Ren et al., ), stochastic shortest path (Tarbouriech et al., ) and RL with linear function approximation (Kim et al., ; Zhang et al., ; Zhou and Gu, ; Di et al., ; Zhang et al., , ; Zhao et al., ). Note that all these works have logarithmic dependence on the horizon $H$. For the tabular setting, recent work further improved the regret or sample complexity to be completely independent of the horizon (i.e., removing the logarithmic dependence on the horizon) (Li et al., ; Zhang et al., ) with a worse dependence on the cardinality of state and action spaces $|\mathcal{S}|$ and $|\mathcal{A}|$. To compare with this, we show that simple MBRL algorithms are already enough to achieve completely horizon-free (i.e., no log dependence) sample complexity for offline RL when the transition model class is finite, and we provide a simpler approach to achieve the nearly horizon-free results for tabular MDPs, compared with Zhang et al. (). A recent work (Huang et al., ) also studied the horizon-free and instance-dependent online RL in the function approximation setting with small Eluder dimensions. They estimated the variances to conduct variance-weighted regression. To compare, in our online RL part, we use the simple and standard MLE-based MBRL approach and analysis to get similar guarantees. A more recent work also studied horizon-free behavior cloning Foster et al. (), which is different from our settings.

Besides horizon-free RL, another line of work aimed to provide algorithms with instance-dependent sample complexity/regret bounds, which often enjoy tighter statistical complexity compared with previous work. To mention a few, Zanette and Brunskill () proposed an EULER algorithm with an instance-dependent regret which depends on the maximum variance of the policy return over all policies. Later, Wagenmaker et al. (); Wang et al. () proposed algorithms with first-order regret bounds. A more refined second-order regret bound has been studied. The second-order regret bound is a well-studied instance-dependent bound in the online learning and bandit literature (Cesa-Bianchi et al., ; Ito et al., ; Olkhovskaya et al., ), and compared to the bounds that depend on the maximum variance over all policies, it can be much smaller and it also implies a first-order regret bound. Zhang et al. (); Zhou et al. () proposed algorithms for tabular MDP with second-order regret bounds. Zhao et al. () studied the RL with linear function approximation and proposed algorithms with both horizon-free and variance-dependent regret bounds. The closest work to us is Wang et al. (, ), which used model-free distributional RL methods to achieve first-order and second-order regret bounds in RL. Their approach relies on distributional RL, a somewhat non-conventional approach for RL. Their regret bounds have explicit polynomial dependence on the horizon. Our work focuses on the more conventional model-based RL algorithms and demonstrates that they are indeed sufficient to achieve horizon-free and second-order regret bounds.

## 3 Preliminaries

#### Markov Decision Processes.

We consider finite horizon time-homogenous MDP $\mathcal{M}=\{{\mathcal{S}},\mathcal{A},H,P^{\star},r,s_{0}\}$ where ${\mathcal{S}},\mathcal{A}$ are the state and action space (could be large or even continuous), $H\in\mathbb{N}^{+}$ is the horizon, $P^{\star}:{\mathcal{S}}\times\mathcal{A}\mapsto\Delta({\mathcal{S}})$ is the ground truth transition, $r:{\mathcal{S}}\times\mathcal{A}\mapsto\mathbb{R}$ is the reward signal which we assume is known to the learner, and $s_{0}$ is the fixed initial state.(^1^11For simplicity, we assume initial state $s_{0}$ is fixed and known. Our analysis can be easily extended to a setting where the initial state is sampled from an unknown fixed distribution.) Note that the transition $P^{\star}$ here is time-homogenous. For notational easiness, we denote $[K-1]=\{0,1,\ldots,K-1\}$.

We denote $\pi$ as a deterministic non-stationary policy $\pi=\{\pi_{0},\dots,\pi_{H-1}\}$ where $\pi_{h}:{\mathcal{S}}\mapsto\mathcal{A}$ maps from a state to an action. Let $\Pi$ denote the set of all such policies. $V^{\pi}_{h}(s)$ represents the expected total reward of policy $\pi$ starting at $s_{h}=s$, and $Q^{\pi}_{h}(s,a)$ is the expected total reward of the process of executing $a$ at $s$ at time step $h$ followed by executing $\pi$ to the end. The optimal policy $\pi^{\star}$ is defined as $\pi^{\star}=\mathop{\mathrm{argmax}}_{\pi}V^{\pi}_{0}(s_{0})$. For notation simplicity, we denote $V^{\pi}:=V^{\pi}_{0}(s_{0})$. We will denote $d_{h}^{\pi}(s,a)$ as the state-action distribution induced by policy $\pi$ at time step $h$. We sometimes will overload notation and denote $d^{\pi}_{h}(s)$ as the corresponding state distribution at $h$. Sampling $s\sim d^{\pi}_{h}$ means executing $\pi$ starting from $s_{0}$ to $h$ and returning the state at time step $h$.

Since we use the model-based approach for learning, we define a general model class $\mathcal{P}\subset{\mathcal{S}}\times\mathcal{A}\mapsto\Delta({\mathcal{S}})$.
Given a transition $P$, we denote $V_{h;P}^{\pi}$ and $Q_{h;P}^{\pi}$ as the value and Q functions of policy $\pi$ under the model $P$. Given a function $f:{\mathcal{S}}\times\mathcal{A}\mapsto\mathbb{R}$, we denote the $(Pf)(s,a):=\mathbb{E}_{s^{\prime}\sim P(s,a)}f(s^{\prime})$. We then denote the *variance induced by one-step transition $P$ and function $f$* as $(\mathbb{V}_{P}f)(s,a):=\left(Pf^{2}\right)(s,a)-\left(Pf(s,a)\right)^{2}$ which is equal to $\mathbb{E}_{s^{\prime}\sim P(s,a)}f^{2}(s^{\prime})-\left(\mathbb{E}_{s^{
\prime}\sim P(s,a)}f(s^{\prime})\right)^{2}$.

#### Assumptions.

We make the realizability assumption that $P^{\star}\in\mathcal{P}$. We assume that the rewards are normalized such that $r(\tau)\in[0,1]$ for any trajectory $\tau:=\{s_{0},a_{0},\dots,s_{H-1},a_{H-1}\}$ where $r(\tau)$ is short for $\sum_{h=0}^{H-1}r(s_{h},a_{h})$. Note that this setting is more general than assuming each one-step reward is bounded, i.e., $r(s_{h},a_{h})\in[0,1/H]$, and allows to represent the sparse reward setting. Without loss of generalizability, we assume $V^{\pi}_{h;P}(s)\in[0,1]$, for all $\pi\in\Pi,h\in[0,H],P\in\mathcal{P},s\in{\mathcal{S}}$(^2^22$r(\tau)\in[0,1]$ implies $V^{\pi}_{h;P^{\star}}(s)\in[0,1]$. If we do not assume $V^{\pi}_{h;P}(s)\in[0,1]$ for all $P\in\mathcal{P}$, we can simply add a filtering step in the algorithm to only choose $\pi$,$P$ with $V^{\pi}_{h;P}(s_{0})\in[0,1]$ to get the same guarantees.).

#### Online RL.

For the online RL setting, we focus on the episodic setting where the learner can interact with the environment for $K$ episodes. At episode $k$, the learner proposes a policy $\pi^{k}$ (based on the past interaction history), executes $\pi^{k}$ starting from $s_{0}$ to time step $H-1$. We measure the performance of the online learning via *regret*: $\sum_{k=0}^{K-1}\left(V^{\pi^{\star}}-V^{\pi^{k}}\right)$. To achieve meaningful regret bounds, we often need additional structural assumptions on the MDP and the model class $\mathcal{P}$. We use a $\ell_{1}$ Eluder dimension (Liu et al., ) as the structural condition due to its ability to capture non-linear function approximators (formal definition will be given in Section 4).

#### Offline RL.

For the offline RL setting, we assume that we have a pre-collected offline dataset $\mathcal{D}=\{\tau^{i}\}_{i=1}^{K}$ which contains $K$ trajectories. For each trajectory, we allow it to potentially be generated by an adversary, i.e., at step $h$ in trajectory $k$, (i.e., $s_{h}^{k}$), the adversary can select $a^{k}_{h}$ based on all history (the past $k-1$ trajectories and the steps before $h$ within trajectory $k$) with a fixed strategy, with the only condition that the state transitions follow the underlying transition dynamics, i.e., $s^{i}_{h+1}\sim P^{\star}(s_{h}^{i},a_{h}^{i})$. We emphasize that $\mathcal{D}$ is not necessarily generated by some offline trajectory distribution. Given $\mathcal{D}$, we can split the data into $HK$ many state-action-next state $(s,a,s^{\prime})$ tuples which we can use to learn the transition. To succeed in offline learning, we typically require the offline dataset to have good coverage over some high-quality comparator policy $\pi^{*}$ (formal definition of coverage will be given in Section 5). Our goal here is to learn a policy $\widehat{\pi}$ that is as good as $\pi^{*}$, and we are interested in the *performance gap* between $\hat{\pi}$ and $\pi^{*}$, i.e., $V^{\pi^{*}}-V^{\hat{\pi}}$.

#### Horizon-free and Second-order Bounds.

Our goal is to achieve regret bounds (online RL) or performance gaps (offline RL) that are (nearly) horizon-free, i.e., logarithmical dependence on $H$. In addition to the horizon-free guarantee, we also want our bounds to scale with respect to the variance of the policies. Denote $\mathrm{VaR}_{\pi}$ as the variance of trajectory reward, i.e., $\mathrm{VaR}_{\pi}:=\mathbb{E}_{\tau\sim\pi}(r(\tau)-\mathbb{E}_{\tau\sim\pi}r
(\tau))^{2}$. Second-order bounds in offline RL scales with $\mathrm{VaR}_{\pi^{*}}$ – the variance of the comparator policy. Second-order regret bound in online setting scales with respect to $\sqrt{\sum_{k}\mathrm{VaR}_{\pi^{k}}}$ instead of $\sqrt{K}$.
Note that in the worst case, $\sqrt{\sum_{k}\mathrm{VaR}_{\pi^{k}}}$ scales in the order of $\sqrt{K}$, but can be much smaller in benign cases such as nearly deterministic MDPs. We also note that second-order regret bound immediately implies first-order regret bound in the reward maximization setting, which scales in the order $\sqrt{KV^{\pi^{\star}}}$ instead of just $\sqrt{K}$. The first order regret bound $\sqrt{KV^{\pi^{\star}}}$ is never worse than $\sqrt{K}$ since $V^{\pi^{\star}}\leq 1$. Thus, by achieving a second-order regret bound, our algorithm immediately achieves a first-order regret bound.

#### Additional notations.

Given two distributions $p\in\Delta(\mathcal{X})$ and $q\in\Delta(\mathcal{X})$, we denote the triangle discrimination $D_{\triangle}(p\mathrel{\|}q)=\sum_{x\in\mathcal{X}}\frac{(p(x)-q(x))^{2}}{p(x
)+q(x)}$, and squared Hellinger distance $\mathbb{H}^{2}(p\mathrel{\|}q)=\frac{1}{2}\sum_{x\in\mathcal{X}}\left(\sqrt{q(
x)}-\sqrt{p(x)}\right)^{2}$ (we replace sum via integral when $\mathcal{X}$ is continuous and $p$ and $q$ are pdfs). Note that $D_{\triangle}$ and $\mathbb{H}^{2}$ are equivalent up to universal constants. We will frequently use the following key lemma in (Wang et al., ) to control the difference between means of two distributions.

###### Lemma 1 (Lemma 4.3 in Wang et al. ( 2024 ) ) .

For two distributions $f\in\Delta([0,1])$ and $g\in\Delta([0,1])$:

$$ $\lvert\mathbb{E}_{x\sim f}[x]-\mathbb{E}_{x\sim g}[x]\rvert\leq 4\sqrt{\mathrm {VaR}_{f}\cdot D_{\triangle}(f\mathrel{\|}g)}+5D_{\triangle}(f\mathrel{\|}g).$ (1) $$

where $\mathrm{VaR}_{f}:=\mathbb{E}_{x\sim f}(x-\mathbb{E}_{x\sim f}[x])^{2}$ denotes the variance of the distribution $f$.

The lemma plays a key role in achieving second-order bounds (Wang et al., ). The intuition is the means of the two distributions can be closer if one of the distributions has a small variance. A more naive way of bounding the difference in means is $|\mathbb{E}_{x\sim f}[x]-\mathbb{E}_{x\sim g}[x]|\leq(\max_{x\in\mathcal{X}}|x
|)\|f-g\|_{1}\lesssim(\max_{x\in\mathcal{X}}|x|)\mathbb{H}(f\mathrel{\|}g)
\lesssim(\max_{x\in\mathcal{X}}|x|)\sqrt{D_{\triangle}(f\mathrel{\|}g)}$. Such an approach would have to pay the maximum range $\max_{x\in\mathcal{X}}|x|$ and thus can not leverage the variance $\mathrm{VaR}_{f}$. In the next sections, we show this lemma plays an important role in achieving horizon-free and second-order bounds.

###### Lemma 1 (Lemma 4.3 in Wang et al. ( 2024 ) ) .

## 4 Online Setting

Figure: Algorithm 1 Optimistic Model-based RL (O-MBRL)

In this section, we study the online setting. We present the optimistic model-based RL algorithm (O-MBRL) in Algorithm 1. The algorithm starts from scratch, and iteratively maintains a version space $\widehat{\mathcal{P}}^{k}$ of the model class using the historical data collected so far. Again the version space is designed such that for all $k\in[0,K-1]$, we have $P^{\star}\in\widehat{\mathcal{P}}_{k}$ with high probability. The policy $\pi^{k}$ in this case is computed via the optimism principle, i.e., it selects $\pi^{k}$ and $\widehat{P}^{k}$ such that $V^{\pi^{k}}_{\widehat{P}^{k}}\geq V^{\pi^{\star}}$.

Note that the algorithm design in Algorithm 1 is not new and in fact is quite standard in the model-based RL literature. For instance, Sun et al. () presented a similar style of algorithm except that they use a min-max GAN style objective for learning models. Zhan et al. () used MLE oracle with optimism planning for Partially observable systems such as Predictive State Representations (PSRs), and Liu et al. () used them for both partially and fully observable systems. However, their analyses do not give horizon-free and instance-dependent bounds. We show that under the structural condition that captures nonlinear function class with small eluder dimensions, Algorithm 1 achieves horizon-free and second-order bounds. Besides, since second-order regret bound implies first-order bound (Wang et al., ), our result immediately implies a first-order bound as well.

We first introduce the $\ell_{p}$ Eluder dimension as follows.

###### Definition 1 ( $\ell_{p}$ Eluder Dimension) .

$DE_{p}(\Psi,\mathcal{X},\epsilon)$ is the eluder dimension for $\mathcal{X}$ with function class $\Psi$, when the longest $\epsilon$-independent sequence $x^{1},\dots,x^{L}\subseteq\mathcal{X}$ enjoys the length less than $DE_{p}(\Psi,\mathcal{X},\epsilon)$, i.e., there exists $g\in\Psi$ such that for all $t\in[L]$, $\sum_{l=1}^{t-1}|g(x^{l})|^{p}\leq\epsilon^{p}$ and $|g(x^{t})|>\epsilon$.

We work with the $\ell_{1}$ Eluder dimension $DE_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},\epsilon)$ with the function class $\Psi$ specified as:

$$ $\displaystyle\Psi=\{(s,a)\mapsto\mathbb{H}^{2}(P^{\star}(s,a)\mathrel{\|}P(s,a )):P\in\mathcal{P}\}\,.$ $$

###### Remark 1 .

The $\ell_{1}$ Eluder dimension has been used in previous works such as Liu et al. (). We have the following corollary to demonstrate that the $\ell_{1}$ dimension generalizes the original $\ell_{2}$ dimension of Russo and Van Roy (), it can capture tabular, linear, and generalized linear models.

###### Lemma 2 (Proposition 19 in (Liu et al., 2022 ) ) .

For any $\Psi,\mathcal{X}$, $\epsilon>0$, $\operatorname{DE}_{1}(\Psi,\mathcal{X},\epsilon)\leq\operatorname{DE}_{2}(\Psi
,\mathcal{X},\epsilon)$.

We are ready to present our main theorem for the online RL setting.

###### Theorem 1 (Main theorem for online setting) .

For any $\delta\in(0,1)$, let $\beta=4\log\left(\frac{K\left|\mathcal{P}\right|}{\delta}\right)$, with probability at least $1-\delta$, Algorithm 1 achieves the following regret bound:

$$ $\displaystyle\sum_{k=0}^{K-1}(V^{\pi^{\star}}-V^{\pi^{k}})$ $\displaystyle\leq O\Big{(}\sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}\cdot \text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)\cdot\log(KH\left| \mathcal{P}\right|/\delta)\log(KH)}$ $\displaystyle\quad+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH) \cdot\log(KH\left|\mathcal{P}\right|/\delta)\log(KH)\Big{)}\,.$ (2) $$

The above theorem indicates the standard and simple O-MBRL algorithm is already enough to achieve horizon-free and second-order regret bounds: our bound does not have explicit polynomial dependences on horizon $H$, the leading term scales with $\sqrt{\sum_{k}\mathrm{VaR}_{\pi^{k}}}$ instead of the typical $\sqrt{K}$.

We have the following result about the first-order regret bound.

###### Corollary 1 (Horizon-free and First-order regret bound) .

Let $\beta=4\log\left(\frac{K\left|\mathcal{P}\right|}{\delta}\right)$, with probability at least $1-\delta$, Algorithm 1 achieves the following regret bound:

$$ $\displaystyle\sum_{k=0}^{K-1}V^{\pi^{\star}}-V^{\pi^{k}}$ $\displaystyle\leq O\Big{(}\sqrt{KV^{\pi^{\star}}\cdot\text{DE}_{1}(\Psi,{ \mathcal{S}}\times\mathcal{A},1/KH)\cdot\log(KH\left|\mathcal{P}\right|/\delta )\log(KH)}$ $\displaystyle\quad+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH) \cdot\log(KH\left|\mathcal{P}\right|/\delta)\log(KH)\Big{)}\,.$ $$

###### Proof.

Note that $\mathrm{VaR}_{\pi}\leq V^{\pi}\leq V^{\pi^{\star}}$ where the first inequality is because the trajectory-wise reward is bounded in $[0,1]$. Therefore, combining with Theorem 1, we directly obtain the first-order result.
∎

Note that the above bound scales with respect to $\sqrt{KV^{\pi^{\star}}}$ instead of just $\sqrt{K}$. Since $V^{\pi^{\star}}\leq 1$, this bound improves the worst-case regret bound when the optimal policy has total reward less than one.(^3^33Typically a first-order regret bound makes more sense in the cost minimization setting instead of reward maximization setting. We believe that our results are transferable to the cost-minimization setting.)

###### Definition 1 ( ℓ p subscript ℓ 𝑝 \ell_{p} roman_ℓ start_POSTSUBSCRIPT italic_p end_POSTSUBSCRIPT Eluder Dimension) .

###### Remark 1 .

###### Lemma 2 (Proposition 19 in (Liu et al., 2022 ) ) .

###### Theorem 1 (Main theorem for online setting) .

###### Corollary 1 (Horizon-free and First-order regret bound) .

###### Proof.

#### Faster rates for deterministic transitions.

When the underlying MDP has deterministic transitions, we can achieve a smaller regret bound that only depends on the number of episodes logarithmically.

###### Corollary 2 ( $\log K$ regret bound with deterministic transitions) .

When the transition dynamics of the MDP are deterministic, setting $\beta=4\log\left(\frac{K\left|\mathcal{P}\right|}{\delta}\right)$, w.p. at least $1-\delta$, Algorithm 1 achieves:

$$ $\displaystyle\sum_{k=0}^{K-1}V^{\pi^{\star}}-V^{\pi^{k}}\leq O\left(\text{DE}_ {1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)\cdot\log(KH\left|\mathcal{P} \right|/\delta)\log(KH)\right).$ $$

###### Corollary 2 ( log ⁡ K 𝐾 \log K roman_log italic_K regret bound with deterministic transitions) .

#### Extension to infinite class 𝒫 𝒫 \mathcal{P} caligraphic_P .

For infinite model class $\mathcal{P}$, we have a similar result. First, we define the bracketing number of an infinite model class as follows.

###### Definition 2 (Bracketing Number (Geer, 2000 ) ) .

Let $\mathcal{G}$ be a set of functions mapping $\mathcal{X}\to\mathbb{R}$.
Given two functions $l,u$ such that $l(x)\leq u(x)$ for all $x\in\mathcal{X}$, the bracket $[l,u]$ is the set of functions $g\in\mathcal{G}$ such that $l(x)\leq g(x)\leq u(x)$ for all $x\in\mathcal{X}$.
We call $[l,u]$ an $\epsilon$-bracket if $||u-l||\leq\epsilon$.
Then, the $\epsilon$-bracketing number of $\mathcal{G}$ with respect to $||\cdot||$, denoted by $\mathcal{N}_{[]}(\epsilon,\mathcal{G},||\cdot||)$ is the minimum number of $\epsilon$-brackets needed to cover $\mathcal{G}$.

We use the bracketing number of $\mathcal{P}$ to denote the complexity of the model class, similar to $|\mathcal{P}|$ in the finite class case. Next, we propose a corollary to characterize the regret with an infinite model class.

###### Corollary 3 (Regret bound for Algorithm 1 with infinite model class $\mathcal{P}$ ) .

When the model class $\mathcal{P}$ is infinite, let $\beta=7\log(K\mathcal{N}_{[]}((KH|{\mathcal{S}}|)^{-1},\mathcal{P},\|\cdot\|_{
\infty})/\delta)$, with probability at least $1-\delta$, Algorithm 1 achieves the following regret bound:

$$ $\displaystyle\sum_{k=0}^{K-1}V^{\pi^{\star}}-V^{\pi^{k}}\leq O\Bigg{(}\text{DE }_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},\frac{1}{KH})\log(\frac{KH\mathcal{N }_{[]}((KH|{\mathcal{S}}|)^{-1},\mathcal{P},\|\cdot\|_{\infty})}{\delta})\log(KH)$ $\displaystyle\quad+\sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}\cdot\text{DE}_ {1}(\Psi,{\mathcal{S}}\times\mathcal{A},\frac{1}{KH})\log(\frac{KH\mathcal{N}_ {[]}((KH|{\mathcal{S}}|)^{-1},\mathcal{P},\|\cdot\|_{\infty})}{\delta})\log(KH )}\Bigg{)}\,,$ $$

where $\mathcal{N}_{[]}((KH|{\mathcal{S}}|)^{-1},\mathcal{P},\|\cdot\|_{\infty})$ is the bracketing number defined in Definition 2.

A specific example of the infinite model class is the tabular MDP, where $\mathcal{P}$ is the collection of all the conditional distributions over $\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$. By Corollary 3, we also have a new regret bound for MBRL under the tabular MDP setting, which is nearly horizon-free and second-order.

###### Example 1 (Tabular MDPs) .

When specializing to tabular MDPs, use the fact that tabular MDP has $\ell_{2}$ Eluder dimension being at most $|{\mathcal{S}}||\mathcal{A}|$ (Section D.1 in Russo and Van Roy ()), $\ell_{1}$ dimension is upper bounded by $\ell_{2}$ dimension (Lemma 2), and use the standard $\epsilon$-net argument to show that $\mathcal{N}_{[]}(\epsilon,\mathcal{P},\|\cdot\|_{\infty})$ is upper-bounded by $(c/\epsilon)^{|{\mathcal{S}}|^{2}|\mathcal{A}|}$ (e.g., see Uehara and Sun ()), we can show that Algorithm 1 achieves the following regret bound for tabular MDP: with probability at least $1-\delta$,

$$ $\displaystyle\sum_{k}V^{\pi^{\star}}-V^{\pi^{k}}$ $\displaystyle\leq O\Big{(}|{\mathcal{S}}|^{1.5}|\mathcal{A}|\sqrt{\sum_{k} \mathrm{VaR}_{\pi^{k}}\cdot\log(\frac{KH|{\mathcal{S}}|}{\delta})\log(KH)}+|{ \mathcal{S}}|^{3}|\mathcal{A}|^{2}\log(\frac{KH|{\mathcal{S}}|}{\delta})\log( KH)\Big{)}\,.$ $$

In summary, we have shown that a simple MLE-based MBRL algorithm is enough to achieve nearly horizon-free and second-order regret bounds under non-linear function approximation.

###### Definition 2 (Bracketing Number (Geer, 2000 ) ) .

###### Corollary 3 (Regret bound for Algorithm 1 with infinite model class 𝒫 𝒫 \mathcal{P} caligraphic_P ) .

###### Example 1 (Tabular MDPs) .

### 4.1 Proof Sketch of Theorem 1

Now we are ready to provide a proof sketch of Theorem 1 with the full proof deferred to Appendix D.1. For ease of presentation, we use $d_{\textsf{RL}}$ to denote $\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)$, and ignore some $\log$ terms.

Overall, our analysis follows the general framework of optimism in the face of uncertainty, but with (1) careful analysis in leveraging the MLE generalization bound and (2) more refined proof in the training-to-testing distribution transfer via Eluder dimension.

By standard MLE analysis, we can show w.p. $1-\delta$, for all $k\in[K-1]$, we have $P^{\star}\in\widehat{\mathcal{P}}^{k}$, and

$$ $\displaystyle\sum_{i=0}^{k-1}\sum_{h=0}^{H-1}\mathbb{H}^{2}(P^{\star}(s_{h}^{i },a_{h}^{i})||\widehat{P}^{k}(s_{h}^{i},a_{h}^{i}))\leq O(\log(K\left|\mathcal {P}\right|/\delta))\,.$ (3) $$

From here, trivially applying training-to-testing distribution transfer via the Eluder dimension as previous works (e.g., Wang et al. ()) would cause poly-dependence on $H$. With new techniques detailed in Appendix B, which is one of our technical contributions and may be of independent interest, we can get:
there exists a set $\mathcal{K}\subseteq[K-1]$ such that $|\mathcal{K}|\leq O(d_{\textsf{RL}}\log(K|\mathcal{P}|/\delta))$, and

$$ $\displaystyle\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h}\mathbb{H}^{2}\Big{(} P^{\star}(s_{h}^{k},a_{h}^{k})\mathrel{\|}\widehat{P}^{k}\big{(}s_{h}^{k},a_{h }^{k})\Big{)}\leq O(d_{\textsf{RL}}\cdot\log(K\left|\mathcal{P}\right|/\delta) \log(KH))\,.$ (4) $$

Recall that $(\pi^{k},\widehat{P}^{k})\leftarrow\mathop{\mathrm{argmax}}_{\pi\in\Pi,P\in
\widehat{\mathcal{P}}^{k}}V_{0;P}^{\pi}(s_{0})$, with the above realization guarantee $P^{\star}\in\widehat{\mathcal{P}}^{k}$, we can get the following optimism guarantee: $V^{\star}_{0;P^{\star}}\leq\max_{\pi\in\Pi,P\in\widehat{\mathcal{P}}^{k}}V^{
\pi}_{0;P}=V^{\pi^{k}}_{0;\widehat{P}^{k}}$.

At this stage, one straight-forward way to proceed is to use the standard simulation lemma (Lemma 7):

$$ $\displaystyle\sum_{k=0}^{K-1}V^{\pi^{k}}_{0;\widehat{P}^{k}}-V^{\pi^{k}}_{0;P^ {\star}}$ $\displaystyle\leq\sum_{k=0}^{K-1}\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{k }}_{h}}\left[\left|\mathbb{E}_{s^{\prime}\sim P^{\star}(s,a)}V^{\pi^{k}}_{h+1; \widehat{P}^{k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim\widehat{P}^{k}(s,a)}V^ {\pi^{k}}_{h+1;\widehat{P}^{k}}(s^{\prime})\right|\right].$ (5) $$

However, from here, if we naively bound each term on the RHS via $\mathbb{E}_{s,a\sim d^{\pi^{k}}_{h}}\|P^{\star}(s,a)-\widehat{P}(s,a)\|_{1}$, which is what previous works such as Uehara and Sun () did exactly, we would end up paying a linear horizon dependence $H$ due to the summation over $H$ on the RHS the above expression. Given the mean-to-variance lemma (Lemma 1), we may consider using it to bound the difference between two means $\mathbb{E}_{s^{\prime}\sim P^{\star}(s,a)}V^{\pi^{k}}_{h+1;\widehat{P}^{k}}(s^
{\prime})-\mathbb{E}_{s^{\prime}\sim\widehat{P}^{k}(s,a)}V^{\pi^{k}}_{h+1;
\widehat{P}^{k}}(s^{\prime})$. This still can not work if we start from here, because we would eventually get
$\sum_{k}\sum_{h}\mathbb{E}_{s,a\sim d^{\pi^{k}}_{h}}[\mathbb{H}^{2}(P^{\star}(
s,a)||\widehat{P}^{k}(s,a))]$ terms, which can not be further upper bounded easily with the MLE generalization guarantee.

To achieve horizon-free and second-order bounds, we need a novel and more careful analysis.

First, we carefully decompose and upper bound the regret in $\tilde{\mathcal{K}}:=[K-1]\setminus\mathcal{K}$ w.h.p. as follows using Bernstain’s inequality (for regret in $\mathcal{K}$ we simply upper bound it by $|\mathcal{K}|$)

$$ $\displaystyle\sum_{k\in\tilde{\mathcal{K}}}\left(V^{\pi^{k}}_{0;\widehat{P}^{k }}(s_{h}^{k})-\sum_{h=0}^{H-1}r(s_{h}^{k},a_{h}^{k})\right)+\sum_{k\in\tilde{ \mathcal{K}}}\left(\sum_{h=0}^{H-1}r(s_{h}^{k},a_{h}^{k})-V^{\pi^{k}}_{0;P^{ \star}}\right)\lesssim\sqrt{\sum_{k\in\tilde{\mathcal{K}}}\sum_{h}\big{(} \mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h} ^{k})}$ $\displaystyle+\sum_{k\in\tilde{\mathcal{K}}}\sum_{h}\left|\mathbb{E}_{s^{ \prime}\sim\widehat{P}^{k}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k}}_{h+1;\widehat{P}^{ k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim P^{*}(s_{h}^{k},a_{h}^{k})}V^{\pi^{ k}}_{{h+1};\widehat{P}^{k}}(s^{\prime})\right|+\sqrt{\sum_{k}\mathrm{VaR}_{\pi ^{k}}\log(1/\delta)}\,.$ (6) $$

Then, we bound the difference of two means $\mathbb{E}_{s^{\prime}\sim\widehat{P}^{k}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k}}_{h+
1;\widehat{P}^{k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim P^{*}(s_{h}^{k},a_{h
}^{k})}V^{\pi^{k}}_{{h+1};\widehat{P}^{k}}(s^{\prime})$ using variances and the triangle discrimination (see Lemma 1 for more details), together with the fact that $D_{\triangle}\leq 4\mathbb{H}^{2}$, and information processing inequality on the squared Hellinger distance, we have

$$ $\displaystyle\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{k}(s_{h}^{k},a_{h}^{ k})}V^{\pi^{k}}_{h+1;\widehat{P}^{k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim P ^{*}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k}}_{{h+1};\widehat{P}^{k}}(s^{\prime})\rvert$ $\displaystyle\quad\leq O\Big{(}\sqrt{\big{(}\mathbb{V}_{P^{\star}}V_{h+1; \widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})D_{\triangle}\Big{(}V_{h +1;\widehat{P}^{k}}^{\pi^{k}}\big{(}s^{\prime}\sim P^{\star}(s_{h}^{k},a_{h}^{ k})\big{)}\mathrel{\|}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}(s^{\prime}\sim\widehat {P}^{k}\big{(}s_{h}^{k},a_{h}^{k})\big{)}\Big{)}}$ $\displaystyle\qquad\qquad+D_{\triangle}\Big{(}V_{h+1;\widehat{P}^{k}}^{\pi^{k} }\big{(}s^{\prime}\sim P^{\star}(s_{h}^{k},a_{h}^{k})\big{)}\mathrel{\|}V_{h+1 ;\widehat{P}^{k}}^{\pi^{k}}(s^{\prime}\sim\widehat{P}^{k}\big{(}s_{h}^{k},a_{h }^{k})\big{)}\Big{)}\Big{)}$ $\displaystyle\leq O\Big{(}\sqrt{\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P }^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})\mathbb{H}^{2}\Big{(}P^{\star}(s_{ h}^{k},a_{h}^{k})\mathrel{\|}\widehat{P}^{k}\big{(}s_{h}^{k},a_{h}^{k})\Big{)} }+\mathbb{H}^{2}\Big{(}P^{\star}(s_{h}^{k},a_{h}^{k})\mathrel{\|}\widehat{P}^{ k}\big{(}s_{h}^{k},a_{h}^{k})\Big{)}\Big{)}$ $$

where we denote $V^{\pi^{*}}_{h+1;\widehat{P}}(s^{\prime}\sim P^{\star}(s,a))$ as the distribution of the random variable $V^{\pi^{*}}_{h+1;\widehat{P}}(s^{\prime})$ with $s^{\prime}\sim P^{\star}(s,a)$. This is the key lemma used by Wang et al. () to show distributional RL can achieve second-order bounds. We show that this is also crucial for achieving a horizon-free bound.

Then, summing up over $k,h$, with Cauchy-Schwartz and the MLE generalization bound via Eluder dimension in Equation 4, we have

$$ $\displaystyle\sum_{k\in\tilde{\mathcal{K}}}\sum_{h}\left|\mathbb{E}_{s^{\prime }\sim\widehat{P}^{k}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k}}_{h+1;\widehat{P}^{k}}(s^ {\prime})-\mathbb{E}_{s^{\prime}\sim P^{*}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k}}_{{ h+1};\widehat{P}^{k}}(s^{\prime})\right|\leq O\Big{(}\sum_{k\in\tilde{\mathcal {K}}}\sum_{h}\mathbb{H}^{2}\Big{(}P^{\star}(s_{h}^{k},a_{h}^{k})\mathrel{\|} \widehat{P}^{k}\big{(}s_{h}^{k},a_{h}^{k})\Big{)}$ $\displaystyle+\sqrt{\sum_{k\in\tilde{\mathcal{K}}}\sum_{h}\big{(}\mathbb{V}_{P ^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})\sum_{k \in\tilde{\mathcal{K}}}\sum_{h}\mathbb{H}^{2}\Big{(}P^{\star}(s_{h}^{k},a_{h}^ {k})\mathrel{\|}\widehat{P}^{k}\big{(}s_{h}^{k},a_{h}^{k})\Big{)}}\Big{)}$ $\displaystyle\leq O\Big{(}\sqrt{\sum_{k\in\tilde{\mathcal{K}}}\sum_{h}\big{(} \mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h} ^{k})d_{\textsf{RL}}\log(K\left|\mathcal{P}\right|/\delta)\log(KH)}+d_{\textsf {RL}}\log(K\left|\mathcal{P}\right|/\delta)\log(KH)\Big{)}\,.$ (7) $$

Note that we have $\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k
},a_{h}^{k})$ depending on $\widehat{P}^{k}$. To get a second-order bound, we need to convert it to the variance under ground truth transition $P^{\star}$, and we want to do it without incurring any $H$ dependence. *This is another key difference from Wang et al. ().*

We aim to replace $\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k
},a_{h}^{k})$ by $\big{(}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})$ which is the variance under $P^{\star}$ (recall that $V^{\pi}$ is the value function of $\pi$ under $P^{\star}$), and we want to control the difference $\big{(}\mathbb{V}_{P^{\star}}\left(V_{h+1;\widehat{P}^{k}}^{\pi^{k}}-V_{h+1}^{
\pi^{k}}\right)\big{)}(s_{h}^{k},a_{h}^{k})$.
To do so, we need to bound the $2^{m}$ moment of the difference $V_{h+1;\widehat{P}^{k}}^{\pi^{k}}-V_{h+1}^{\pi^{k}}$ following the strategy in Zhang et al. (); Zhou and Gu (); Zhao et al. (). Let us define the following terms:

$$ $\displaystyle A:=\sum_{k\in\tilde{\mathcal{K}}}\sum_{h}\left[\big{(}\mathbb{V} _{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k}) \right],C_{m}:=\sum_{k\in\tilde{\mathcal{K}}}\sum_{h}\left[\big{(}\mathbb{V}_{ P^{\star}}(V_{h+1;\widehat{P}^{k}}^{\pi^{k}}-V_{h+1}^{\pi^{k}})^{2^{m}}\big{)} (s_{h}^{k},a_{h}^{k})\right],$ $\displaystyle B:=\sum_{k\in\tilde{\mathcal{K}}}\sum_{h}\left[\big{(}\mathbb{V} _{P^{\star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})\right],G:=\sqrt{A \cdot d_{\textsf{RL}}\log(\frac{K\left|\mathcal{P}\right|}{\delta})\log(KH)}+d _{\textsf{RL}}\log(\frac{K\left|\mathcal{P}\right|}{\delta})\log(KH)\,.$ $$

With the fact $\mathbb{V}_{P^{\star}}(a+b)\leq 2\mathbb{V}_{P^{\star}}(a)+2\mathbb{V}_{P^{
\star}}(b)$ we have $A\leq 2B+2C_{0}$. For $C_{m}$, we prove that w.h.p. it has the recursive form $C_{m}\lesssim 2^{m}G+\sqrt{\log(1/\delta)C_{m+1}}+\log(1/\delta)$, during which process we also leverage the above Equation 7 and some careful analysis (detailed in Appendix D.1). Then, with the recursion lemma (Lemma 11), we can get $C_{0}\lesssim G$, which further gives us

$$ $\displaystyle A\lesssim B+d_{\textsf{RL}}\log(\frac{K\left|\mathcal{P}\right|} {\delta})\log(KH)+\sqrt{A\cdot d_{\textsf{RL}}\log(\frac{K\left|\mathcal{P} \right|}{\delta})\log(KH)}\leq O\big{(}B+d_{\textsf{RL}}\log(\frac{K\left| \mathcal{P}\right|}{\delta})\log(KH)\big{)}\,,$ $$

where in the last step we use the fact $x\leq 2a+b^{2}$ if $x\leq a+b\sqrt{x}$.
Finally, we note that $B\leq O(\sum_{k}\mathrm{VaR}_{\pi^{k}}+\log(1/\delta))$ w.h.p.. Plugging the upper bound of $A$ back into Equation 7 and then to Equation 6, we conclude the proof.

## 5 Offline Setting

For the offline setting, we directly analyze the Constrained Pessimism Policy Optimization (CPPO-LR) algorithm (Algorithm 2) proposed by Uehara and Sun (). We first explain the algorithm and then present its performance gap guarantee in finding the comparator policy $\pi^{*}$.

Algorithm 2 splits the offline trajectory data that contains $K$ trajectories into a dataset of $(s,a,s^{\prime})$ tuples (note that in total we have $n:=KH$ many tuples) which is used to perform maximum likelihood estimation $\max_{\tilde{P}\in\mathcal{P}}\sum_{i=1}^{n}\log\tilde{P}(s^{\prime}_{i}|s_{i}
,a_{i})$. It then builds a version space $\widehat{\mathcal{P}}$ which contains models $P\in\mathcal{P}$ whose log data likelihood is not below by too much than that of the MLE estimator. The threshold for the version space is constructed so that with high probability, $P^{\star}\in\widehat{\mathcal{P}}$. Once we build a version space, we perform pessimistic planning to compute $\widehat{\pi}$.

Figure: Algorithm 2 (Uehara and Sun ()) Constrained Pessimistic Policy Optimization with Likelihood-Ratio based constraints (CPPO-LR)

We first define the single policy coverage condition as follows.

###### Definition 3 (Single policy coverage) .

Given any comparator policy $\pi^{*}$, denote the data-dependent single policy concentrability coefficient $C^{\pi^{*}}_{\mathcal{D}}$ as follows:

$$ $\displaystyle C^{\pi^{*}}_{\mathcal{D}}:=\max_{h,P\in\mathcal{P}}\frac{\mathbb {E}_{s,a\sim d^{\pi^{*}}_{h}}\mathbb{H}^{2}\left(P(s,a)\mathrel{\|}P^{\star}(s ,a)\right)}{1/K\sum_{k=1}^{K}\mathbb{H}^{2}\left(P(s_{h}^{k},a_{h}^{k}) \mathrel{\|}P^{\star}(s_{h}^{k},a_{h}^{k})\right)}.$ $$

We assume w.p. at least $1-\delta$ over the randomness of the generation of $\mathcal{D}$, we have $C^{\pi^{*}}_{\mathcal{D}}\leq C^{\pi^{*}}$.

The existence of $C^{\pi^{*}}$ is certainly an assumption. We now give an example in the tabular MDP where we show that if the data is generated from some fixed behavior policy $\pi^{b}$ which has non-trivial probability of visiting every state-action pair, then we can show the existence of $C^{\pi^{*}}$.

###### Example 2 (Tabular MDP with good behavior policy coverage) .

If the $K$ trajectories are collected $i.i.d.$ with a fixed behavior policy $\pi^{b}$, and $d^{\pi^{b}}_{h}(s,a)\geq\rho_{\min},\forall s,a,h$ (similar to Ren et al. ()), then we have: if $K$ is large enough, i.e., $K\geq 2\log(|{\mathcal{S}}||\mathcal{A}|H)/\rho_{\min}^{2}$, w.p. at least $1-\delta$, $C^{\pi^{*}}_{\mathcal{D}}\leq 2/\rho_{\min}$.

Our coverage definition (Definition 3) shares similar spirits as the one in Ye et al. (). It reflects how well the state-action samples in the offline dataset $\mathcal{D}$ cover the state-action pairs induced by the comparator policy $\pi^{\star}$. It is different from the coverage definition in Uehara and Sun () in which the denominator is $\mathbb{E}_{s,a\sim d^{\pi^{b}}_{h}}\mathbb{H}^{2}\left(P(s,a)\mathrel{\|}P^{
\star}(s,a)\right)$ where $\pi^{b}$ is the fixed behavior policy used to collect $\mathcal{D}$. This definition does not apply in our setting since $\mathcal{D}$ is not necessarily generated by some underlying fixed behavior policy. On the other hand, our horizon-free result does not hold in the setting of Uehara and Sun () where $\mathcal{D}$ is collected with a fixed behavior policy $\pi^{b}$ with the concentrability coefficient defined in their way. We leave the derivation of horizon-free results in the setting from Uehara and Sun () as a future work.

Now we are ready to present the main theorem of Algorithm 2, which provides a tighter performance gap than that by Uehara and Sun ().

###### Theorem 2 (Performance gap of Algorithm 2 ) .

For any $\delta\in(0,1)$, let $\beta=4\log(|\mathcal{P}|/\delta)$, w.p. at least $1-\delta$, Algorithm 2 learns a policy $\widehat{\pi}$ that enjoys the following performance gap with respect to any comparator policy $\pi^{*}$:

$$ $V^{\pi^{*}}-V^{\widehat{\pi}}\leq O\left(\sqrt{{C^{\pi^{*}}\mathrm{VaR}_{\pi^{ *}}\log(|\mathcal{P}|/\delta)}/{K}}+{C^{\pi^{*}}\log(|\mathcal{P}|/\delta)}/{K }\right)\,.$ $$

Comparing to the theorem (Theorem 2) of CPPO-LR from Uehara and Sun (), our bound has two improvements. First, our bound is horizon-free (not even any $\log(H)$ dependence), while the bound in Uehara and Sun () has $\text{poly}(H)$ dependence. Second, our bound scales with $\mathrm{VaR}_{\pi^{*}}\in[0,1]$, which can be small when $\mathrm{VaR}_{\pi^{*}}\ll 1$. For deterministic system and policy $\pi^{*}$, we have $\mathrm{VaR}_{\pi^{*}}=0$ which means the sample complexity now scales at a faster rate $C^{\pi^{*}}/K$. The proof is in Appendix E.1.

We show that the same algorithm can achieve $1/K$ rate when $P^{\star}$ is deterministic (but rewards could be random, and the algorithm does not need to know the condition that $P^{\star}$ is deterministic).

###### Corollary 4 ( ${C^{\pi^{*}}}/{K}$ performance gap of Algorithm 2 with deterministic transitions) .

When the ground truth transition $P^{\star}$ of the MDP is deterministic, for any $\delta\in(0,1)$, let $\beta=4\log(|\mathcal{P}|/\delta)$, w.p. at least $1-\delta$, Algorithm 2 learns a policy $\widehat{\pi}$ that enjoys the following performance gap with respect to any comparator policy $\pi^{*}$:

$$ $V^{\pi^{*}}-V^{\widehat{\pi}}\leq O\left({C^{\pi^{*}}\log(|\mathcal{P}|/\delta )}/{K}\right)\,.$ $$

For infinite model class $\mathcal{P}$, we have a similar result in the following corollary.

###### Corollary 5 (Performance gap of Algorithm 2 with infinite model class $\mathcal{P}$ ) .

When the model class $\mathcal{P}$ is infinite, for any $\delta\in(0,1)$, let $\beta=7\log(\mathcal{N}_{[]}((KH|{\mathcal{S}}|)^{-1},\mathcal{P},\|\cdot\|_{
\infty})/\delta)$, w.p. at least $1-\delta$, Algorithm 2 learns a policy $\widehat{\pi}$ that enjoys the following PAC bound w.r.t. any comparator policy $\pi^{*}$:

$$ $\displaystyle V^{\pi^{*}}-V^{\widehat{\pi}}\leq O\left(\sqrt{\frac{C^{\pi^{*}} \mathrm{VaR}_{\pi^{*}}\log(\mathcal{N}_{[]}((KH|{\mathcal{S}}|)^{-1},\mathcal{ P},\|\cdot\|_{\infty})/\delta)}{K}}+\frac{C^{\pi^{*}}\log(\mathcal{N}_{[]}((KH |{\mathcal{S}}|)^{-1},\mathcal{P},\|\cdot\|_{\infty})/\delta)}{K}\right),$ $$

where $\mathcal{N}_{.[]}((KH|{\mathcal{S}}|)^{-1},\mathcal{P},\|\cdot\|_{\infty})$ is the bracketing number defined in Definition 2.

Our next example gives the explicit performance gap bound for tabular MDPs.

###### Example 3 (Tabular MDPs) .

For tabular MDPs, we have $\mathcal{N}_{[]}(\epsilon,\mathcal{P},\|\cdot\|_{\infty})$ upper-bounded by $(c/\epsilon)^{|{\mathcal{S}}|^{2}|\mathcal{A}|}$ (e.g., see Uehara and Sun ()). Then with probability at least $1-\delta$, let $\beta=7\log(\mathcal{N}_{[]}((KH|{\mathcal{S}}|)^{-1},\mathcal{P},\|\cdot\|_{
\infty})/\delta)$, Algorithm 2 learns a policy $\widehat{\pi}$ satisfying the following performance gap with respect to any comparator policy $\pi^{*}$:

$$ $V^{\pi^{*}}-V^{\widehat{\pi}}\leq O\left(|{\mathcal{S}}|\sqrt{{|\mathcal{A}|C^ {\pi^{*}}\mathrm{VaR}_{\pi^{*}}\log(KH|{\mathcal{S}}|/\delta)}/{K}}+{|{ \mathcal{S}}|^{2}|\mathcal{A}|C^{\pi^{*}}\log(KH|{\mathcal{S}}|/\delta)}/{K} \right),$ $$

The closest result to us is from Ren et al. (), which analyzes the MBRL for tabular MDPs and obtains a performance gap $\tilde{O}(\sqrt{\frac{1}{Kd_{m}}}+\frac{|\mathcal{S}|}{Kd_{m}})$, where $d_{m}$ is the minimum visiting probability for the behavior policy to visit each state and action. Note that their result is not instance-dependent, which makes their gap only $\tilde{O}(1/\sqrt{K})$ even when the environment is deterministic and $\pi^{*}$ is deterministic. In a sharp contrast, our analysis shows a better $\tilde{O}(1/K)$ gap under the deterministic environment. Our result would still have the $\log H$ dependence, and we leave getting rid of this logarithmic dependence on the horizon $H$ as an open problem.

###### Definition 3 (Single policy coverage) .

###### Example 2 (Tabular MDP with good behavior policy coverage) .

###### Theorem 2 (Performance gap of Algorithm 2 ) .

###### Corollary 4 ( C π ∗ / K superscript 𝐶 superscript 𝜋 𝐾 {C^{\pi^{*}}}/{K} italic_C start_POSTSUPERSCRIPT italic_π start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT end_POSTSUPERSCRIPT / italic_K performance gap of Algorithm 2 with deterministic transitions) .

###### Corollary 5 (Performance gap of Algorithm 2 with infinite model class 𝒫 𝒫 \mathcal{P} caligraphic_P ) .

###### Example 3 (Tabular MDPs) .

## 6 Conclusion

In this work, we presented a minimalist approach for achieving horizon-free and second-order regret bounds in RL: simply train transition models via Maximum Likelihood Estimation followed by optimistic or pessimistic planning, depending on whether we operate in the online or offline learning mode. Our horizon-free bounds for general function approximation look quite similar to the bounds in Contextual bandits, indicating that the need for long-horizon planning does not make RL harder than CB from a statistical perspective.

Our work has some limitations. First, when extending our result to continuous function class, we pay $\ln(H)$. This $\ln(H)$ is coming from a naive application of the $\epsilon$-net/bracket argument to the generalization bounds of MLE. We conjecture that this $\ln(H)$ can be elimiated by using a more careful analysis that uses techiniques such as peeling/chaining (Dudley, ; Zhang, ). We leave this as an important future direction.
Second, while our model-based framework is quite general, it cannot capture problems that need to be solved via model-free approaches such as linear MDPs (Jin et al., ). An interesting future work is to see if we can develop the corresponding model-free approaches that can achieve horizon-free and instance-dependent bounds for RL with general function approximation. Finally, the algorithms studied in this work are not computationally tractable. This is due to the need of performing optimism/pessimism planning for exploration. Deriving computationally tractacle RL algorithms for the rich function approximation setting is a long-standing question.

## Appendix A Summary of Contents in the Appendix

The Appendix is organized as follows.

In Appendix B, we provide some new analyses for Eluder dimension, which we will use for proving the regret bounds for the online RL setting.

In Appendix C, we provide some other supporting lemmas that will be used in our proofs.

In Appendix D, we provide the detailed proofs for the online RL setting (Section 4). Specifically, in Appendix D.1 we give the proof of Theorem 1; in Appendix D.2, we show the proof of Corollary 2; in Appendix D.3, we give the proof of Corollary 3.

In Appendix E, we provide the detailed proofs for the offline RL setting (Section 5). Specifically, in Appendix E.1 we give the proof of Theorem 2; in Appendix E.2, we show the proof of Corollary 4; in Appendix E.3, we give the proof of Corollary 5; in Appendix E.4, we show the proof of the claim in Example 2.

## Appendix B Analysis regarding the Eluder Dimension

For simplicity, we denote $x_{h}^{k}=(s_{h}^{k},a_{h}^{k})$.

First we have two technical lemma. The first lemma bounds the summation of “self-normalization” terms by the Eluder dimension. Our result generalizes the previous result by Zhao et al. () from the $\ell_{2}$-Eluder dimension to the $\ell_{1}$ case.

###### Lemma 3 .

Suppose for all $g\in\Psi,|g|\leq 1$ and $\lambda>1$, then we have

$$ $\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\min\bigg{\{}1,\sup_{g\in\Psi}\frac{| g(x_{h}^{k})|}{\sum_{k^{\prime}=1}^{k-1}\sum_{h^{\prime}=1}^{H}|g(x_{h^{\prime }}^{k^{\prime}})|+\sum_{h^{\prime}=1}^{h-1}|g(x_{h^{\prime}}^{k})|+\lambda} \bigg{\}}$ $\displaystyle\leq 12\log^{2}(4\lambda KH)\cdot DE_{1}(\Psi,{\mathcal{S}}\times \mathcal{A},1/(8\lambda KH))+\lambda^{-1}.$ $$

###### Proof of Lemma 3 .

We follow the proof steps of Theorem 4.6 in Zhao et al. ().
For simplicity, we use $n=KH$, $i=kH+h$ to denote the indices and denote $x_{h}^{k}$ by $x_{i}$. Then we need to prove

$$ $\displaystyle\sum_{i=1}^{n}\min\bigg{\{}1,\sup_{g\in\Psi}\frac{|g(x_{i})|}{ \sum_{t=1}^{i-1}|g(x_{t})|+\lambda}\bigg{\}}\leq 12\log^{2}(4\lambda n)\cdot DE _{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/(8\lambda n))+\lambda^{-1}$ (8) $$

Let

$$ $\displaystyle g_{i}=\mathop{\mathrm{argmax}}_{g\in\Psi}\frac{|g(x_{i})|}{\sum_ {j=1}^{i-1}|g(x_{j})|+\lambda}$ (9) $$

For any $1/(\lambda n)\leq\rho\leq 1$ and $1\leq j\leq\lceil\log(4\lambda n)\rceil$, we define

$$ $\displaystyle A_{\rho}^{j}=\bigg{\{}i\in[n]:2^{-j}<|g_{i}(x_{i})|\leq 2^{-j+1} ,\frac{|g_{i}(x_{i})|}{\sum_{t=1}^{i-1}|g_{i}(x_{t})|+\lambda}\geq\rho/2\bigg{ \}},\ d_{j}:=DE_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},2^{-j}).$ (10) $$

Next we only consider the set $A_{\rho}^{j}$ where $|A_{\rho}^{j}|>d_{j}$. We denote $A_{\rho}^{j}=\{a_{1},\dots,a_{A}\}$, where $A=|A_{\rho}^{j}|$ and $\{a_{i}\}$ keeps the same order as $\{x_{i}\}$. Next we do the following constructions. We maintain $k=\lfloor(A-1)/d_{j}\rfloor$ number of queues $Q_{1},\dots,Q_{k}$, all of them initialized as emptysets. We put $a_{1}$ into $Q_{1}$. For $a_{i},i\geq 2$, we put $a_{i}$ into $Q_{l}$, where $Q_{l}$ is the first queue where $a_{i}$ is $2^{-j}$-independent of all elements in $Q_{l}$. Let $i_{\max}$ be the smallest $i$ when we can not put $a_{i}$ into any existing queue.

We claim that $i_{\max}$ indeed exists, i.e., our construction will stop before we put all elements in $A^{j}_{\rho}$ into $Q_{1},\dots,Q_{k}$. In fact, note the fact that the length of each $Q_{l}$ is always no more than $d_{j}$, which is due to the fact that any $2^{-j}$-independent sequence’s length is at most $d_{j}$. Meanwhile, since we only have $k=\lfloor(A-1)/d_{j}\rfloor$, then the amount of elements in $Q_{1}\cup\dots\cup Q_{k}$ will be upper bounded by $k\cdot d_{j}<A$. That suggests at least one element in $A_{\rho}^{j}$ is not contained by $Q_{1}\cup\dots\cup Q_{k}$, i.e., $i_{\max}$ exists.

By the definition of $i_{\max}$, we know that $a_{i_{\max}}$ is $2^{-j}$-dependent to each $Q_{l}$. Next we give a bound of $A$. First, note

$$ $\displaystyle\sum_{t=1}^{i_{\max}-1}|g_{i_{\max}}(x_{t})|\geq\sum_{t\in Q_{1} \cup\dots\cup Q_{k}}|g_{i_{\max}}(a_{t})|=\sum_{l=1}^{k}\sum_{t\in Q_{l}}|g_{i _{\max}}(a_{t})|>k\cdot 2^{-j},$ (11) $$

where the first inequality holds since $Q_{l}$ are the elements that appear before $a_{i_{\max}}$, the second one holds due to the following induction of Eluder dimension: since $a_{i_{\max}}$ is $2^{-j}$-dependent to $Q_{l}$, then we have

$$ $\displaystyle\forall g\in\Psi,\ \sum_{t\in Q_{l}}|g(a_{t})|\leq 2^{-j} \Rightarrow|g(a_{i_{\max}})|\leq 2^{-j}.$ (12) $$

Therefore, given the fact $|g_{i_{\max}}(a_{i_{\max}})|>2^{-j}$ (recall the definition of $A^{j}_{\rho}$), we must have $\sum_{t\in Q_{l}}|g_{i_{\max}}(a_{t})|>2^{-j}$ as well, which suggests the second inequality of Equation 11 holds. Second, we have

$$ $\displaystyle\sum_{t=1}^{i_{\max}-1}|g_{i_{\max}}(x_{t})|\leq 2/\rho\cdot|g_{i _{\max}}(a_{i_{\max}})|\leq 4\cdot 2^{-j}/\rho,$ (13) $$

where both inequalities hold due to the definition of $A^{j}_{\rho}$. Combining Equation 11 and Equation 13, we have

$$ $\displaystyle k<4/\rho\Rightarrow A\leq 4d_{j}/\rho+d_{j}\leq 5d_{j}/\rho.$ (14) $$

Therefore, we have that for all $\rho,j$, $|A^{j}_{\rho}|\leq 5d_{j}/\rho$.

Finally we prove Equation 8. $1/(\lambda n)\leq\rho\leq 1$ and $1\leq j\leq\lceil\log(4\lambda n)\rceil=J$. Denote

$$ $\displaystyle A_{\rho}=\bigg{\{}i\in[n]:\frac{|g_{i}(x_{i})|}{\sum_{t=1}^{i-1} |g_{i}(x_{t})|+\lambda}\geq\rho/2\bigg{\}}.$ (15) $$

Then it is easy to notice that $|A_{\rho}|=\sum_{j}|A^{j}_{\rho}|\leq\lceil\log(4\lambda n)\rceil\cdot 5d_{J}/\rho$, where we use the fact that the Eluder dimension $d_{j}$ is increasing. Therefore, by the standard peeling technique, we have

$$ $\displaystyle\sum_{i=1}^{n}\min\bigg{\{}1,\sup_{g\in\Psi}\frac{|g(x_{i})|}{ \sum_{t=1}^{i-1}|g(x_{t})|+\lambda}\bigg{\}}$ $\displaystyle=\sum_{j\in[\lceil\log(\lambda n)\rceil]}\sum_{i\in A_{2^{-j}} \setminus A_{2^{-j+1}}}+\sum_{j=\lceil\log(\lambda n)\rceil}\sum_{i\notin A_{2 ^{-j+1}}}$ $\displaystyle\leq\sum_{j\in[\lceil\log(\lambda n)\rceil]}\sum_{i\in A_{2^{-j}} \setminus A_{2^{-j+1}}}2^{-j-1}+n\cdot 1/(\lambda n)$ $\displaystyle\leq\sum_{j\in[\lceil\log(\lambda n)\rceil]}\sum_{i\in A_{2^{-j}} }2^{-j-1}+n\cdot 1/(\lambda n)$ $\displaystyle\leq\lceil\log(\lambda n)\rceil\cdot\lceil\log(4\lambda n)\rceil \cdot 3d_{J}+\lambda^{-1},$ $$

which concludes our proof.
∎

Next lemma gives a bound to bound the number of episodes where the behavior along these episodes are “bad”. Intuitively speaking, our lemma suggests we only have limited number of bad episodes, therefore won’t affect the final performance of our algorithm.

###### Lemma 4 .

Given $\lambda>1$. There exists at most

$$ $\displaystyle 13\log^{2}(4\lambda KH)\cdot DE_{1}(\Psi,{\mathcal{S}}\times \mathcal{A},1/(8\lambda KH))$ (16) $$

number of $k\in[K]$ satisfying the following claim

$$ $\displaystyle\sup_{g\in\Psi}\frac{\lambda+\sum_{k^{\prime}=1}^{k}\sum_{h^{ \prime}=1}^{H}|g(x_{h^{\prime}}^{k^{\prime}})|}{\lambda+\sum_{k^{\prime}=1}^{k -1}\sum_{h^{\prime}=1}^{H}|g(x_{h^{\prime}}^{k^{\prime}})|}>4.$ (17) $$

###### Proof of Lemma 4 .

Note that

$$ $\displaystyle\sum_{k=1}^{K}\min\bigg{\{}2,\log\sup_{g\in\Psi}\frac{\lambda+ \sum_{k^{\prime}=1}^{k}\sum_{h^{\prime}=1}^{H}|g(x_{h^{\prime}}^{k^{\prime}})| }{\lambda+\sum_{k^{\prime}=1}^{k-1}\sum_{h^{\prime}=1}^{H}|g(x_{h^{\prime}}^{k ^{\prime}})|}\bigg{\}}$ $\displaystyle\leq\sum_{k=1}^{K}\min\bigg{\{}2,\log\prod_{h=1}^{H}\sup_{g\in \Psi}\frac{\lambda+\sum_{k^{\prime}=1}^{k-1}\sum_{h^{\prime}=1}^{H}|g(x_{h^{ \prime}}^{k^{\prime}})|+\sum_{h^{\prime}=1}^{h}|g(x_{h^{\prime}}^{k})|}{ \lambda+\sum_{k^{\prime}=1}^{k-1}\sum_{h^{\prime}=1}^{H}|g(x_{h^{\prime}}^{k^{ \prime}})|+\sum_{h^{\prime}=1}^{h-1}|g(x_{h^{\prime}}^{k})|}\bigg{\}}$ $\displaystyle=\sum_{k=1}^{K}\min\bigg{\{}2,\sum_{h=1}^{H}\log\bigg{(}1+\sup_{g \in\Psi}\frac{|g(x_{h}^{k})|}{\lambda+\sum_{k^{\prime}=1}^{k-1}\sum_{h^{\prime }=1}^{H}|g(x_{h^{\prime}}^{k^{\prime}})|+\sum_{h^{\prime}=1}^{h-1}|g(x_{h^{ \prime}}^{k})|}\bigg{)}\bigg{\}}$ $\displaystyle\leq\sum_{k=1}^{K}\sum_{h=1}^{H}\min\bigg{\{}2,\sup_{g\in\Psi} \frac{|g(x_{h}^{k})|}{\sum_{k^{\prime}=1}^{k-1}\sum_{h^{\prime}=1}^{H}|g(x_{h^ {\prime}}^{k^{\prime}})|+\sum_{h^{\prime}=1}^{h-1}|g(x_{h^{\prime}}^{k})|+ \lambda}\bigg{\}},$ $\displaystyle\leq 2\sum_{k=1}^{K}\sum_{h=1}^{H}\min\bigg{\{}1,\sup_{g\in\Psi} \frac{|g(x_{h}^{k})|}{\sum_{k^{\prime}=1}^{k-1}\sum_{h^{\prime}=1}^{H}|g(x_{h^ {\prime}}^{k^{\prime}})|+\sum_{h^{\prime}=1}^{h-1}|g(x_{h^{\prime}}^{k})|+ \lambda}\bigg{\}}$ $\displaystyle\leq 24\log^{2}(4\lambda KH)\cdot DE_{1}(\Psi,{\mathcal{S}}\times \mathcal{A},1/(8\lambda KH))+2\lambda^{-1}$ $\displaystyle\leq 26\log^{2}(4\lambda KH)\cdot DE_{1}(\Psi,{\mathcal{S}}\times \mathcal{A},1/(8\lambda KH)).$ (18) $$

where the first inequality holds since $\sup_{g}\prod f(g)\leq\prod\sup_{g}f(g)$, the second one holds since $\log(1+x)\leq x$, the fourth one holds due to Lemma 3. Therefore, there are at most

$$ $\displaystyle 26\log^{2}(4\lambda KH)\cdot DE_{1}(\Psi,{\mathcal{S}}\times \mathcal{A},1/(8\lambda KH))/2$ $$

number of $k$ satisfying

$$ $\displaystyle\log\sup_{g\in\Psi}\frac{\lambda+\sum_{k^{\prime}=1}^{k}\sum_{h^{ \prime}=1}^{H}|g(x_{h^{\prime}}^{k^{\prime}})|}{\lambda+\sum_{k^{\prime}=1}^{k -1}\sum_{h^{\prime}=1}^{H}|g(x_{h^{\prime}}^{k^{\prime}})|}>2,$ $$

which concludes the proof.

∎

We next have the following lemma, which bounds the regret by the Eluder dimension.

###### Lemma 5 (Theorem 5.3, Wang et al. 2023 ) .

Let $C:=\sup_{(s,a)\in{\mathcal{S}}\times\mathcal{A},f\in\Psi}\lvert f((s,a))\rvert$ be the envelope.
For any sequences $f^{(1)},\dots,f^{(N)}\subseteq\Psi$, $(s,a)^{(1)},\dots,(s,a)^{(N)}\subseteq{\mathcal{S}}\times\mathcal{A}$, let $\beta$ be a constant such that for all $n\in[N]$ we have,
$\sum_{i=1}^{n-1}\lvert f^{(n)}((s,a)^{i})\rvert\leq\beta.$
Then, for all $n\in[N]$, we have

$$ $\sum_{t=1}^{n}\lvert f^{(t)}((s,a)^{t})\rvert\leq\inf_{0<\epsilon\leq 1}\left \{\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},\epsilon)(2C+\beta\log(C/ \epsilon))+n\epsilon\right\}.$ $$

Given Lemma 4 and Lemma Lemma 5, we are able to prove the following key lemma.

###### Lemma 6 (New Eluder Pigeon Lemma) .

Let the event $\mathcal{E}$ be

$$ $\displaystyle\mathcal{E}:\forall k\in[K],\ \sum_{i=1}^{k-1}\sum_{h=1}^{H} \mathbb{H}^{2}(\widehat{P}^{k}(s_{h}^{i},a_{h}^{i})||P^{*}(s_{h}^{i},a_{h}^{i} ))\leq\eta.$ (19) $$

Then under event $\mathcal{E}$, there exists a set $\mathcal{K}\in[K]$ such that

- •
We have $|\mathcal{K}|\leq 13\log^{2}(4\eta KH)\cdot DE_{1}(\Psi,{\mathcal{S}}\times
\mathcal{A},1/(8\eta KH))$.
- •
We have
$\displaystyle\sum_{k\in[K]\setminus\mathcal{K}}\sum_{h=1}^{H}\mathbb{H}^{2}
\Big{(}P^{\star}(s_{h}^{k},a_{h}^{k})\mathrel{\|}\widehat{P}^{k}\big{(}s_{h}^{
k},a_{h}^{k})\Big{)}$
$\displaystyle\leq\inf_{0<\epsilon\leq 1}\left\{\text{DE}_{1}(\Psi,{\mathcal{S}
}\times\mathcal{A},\epsilon)(2+7\eta\log(1/\epsilon))+KH\epsilon\right\}$
$\displaystyle\leq\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)(2+7
\eta\log(KH))+1\,,$
(20)

where the function class $\Psi=\{(s,a)\mapsto\mathbb{H}^{2}(P^{\star}(s,a)\mathrel{\|}P(s,a)):P\in
\mathcal{P}\}$.

###### Proof of Lemma 6 .

We interchangeably use $n=kH+h$ to denote the indices of $s_{h}^{k},a_{h}^{k}$. We set $f^{(n)}((s,a))$ in Lemma 5 as $H^{2}(P^{k}(s,a)||P^{*}(s,a))$.

First, we prove that the $\beta$ in Lemma 5 can be selected as $7\eta$ under event $\mathcal{E}$. To show that, let $\mathcal{K}$ denote all the $k$ stated in Lemma 4. Then for all $k$ such that $k+1\notin\mathcal{K}$, $h=2,...,H$, let $n=kH+h$, we have

$$ $\displaystyle\sum_{i=0}^{n-1}\lvert f^{(n)}((s,a)^{i})\rvert$ $\displaystyle\leq\sum_{i=0}^{kH+H}\lvert f^{(n)}((s,a)^{i})\rvert$ $\displaystyle=\bigg{(}\lambda+\sum_{i=0}^{kH}\lvert f^{(n)}((s,a)^{i})\rvert \bigg{)}\cdot\frac{\sum_{i=0}^{kH+H}\lvert f^{(n)}((s,a)^{i})\rvert+\lambda}{ \sum_{i=0}^{kH}\lvert f^{(n)}((s,a)^{i})\rvert+\lambda}-\lambda$ $\displaystyle\leq\bigg{(}\lambda+\sum_{i=0}^{kH}\lvert f^{(n)}((s,a)^{i}) \rvert\bigg{)}\cdot 4-\lambda$ $\displaystyle\leq 7\eta,$ (21) $$

where the second inequality holds due to Lemma 4, the last one holds due to the definition of $\mathcal{E}$. Therefore, we prove our lemma by the conclusion of Lemma 5 with $\beta=7\eta$.
∎

###### Lemma 3 .

###### Proof of Lemma 3 .

###### Lemma 4 .

###### Proof of Lemma 4 .

###### Lemma 5 (Theorem 5.3, Wang et al. 2023 ) .

###### Lemma 6 (New Eluder Pigeon Lemma) .

###### Proof of Lemma 6 .

## Appendix C Other Supporting Lemmas

###### Lemma 7 (Simulation Lemma ( Agarwal et al. ( 2019 ) )) .

We have

$$ $\displaystyle V_{0;P^{\star}}^{\pi}-{V}_{0;\hat{P}}^{\pi}\leq\sum_{h=0}^{H-1} \mathbb{E}_{s,a\sim d^{\pi}_{h}}\left[\left|\mathbb{E}_{s^{\prime}\sim P^{ \star}(s,a)}V^{\pi}_{h+1;\widehat{P}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim \widehat{P}(s,a)}V^{\pi}_{h+1;\widehat{P}}(s^{\prime})\right|\right].$ $$

###### Lemma 8 (Change of Variance Lemma (Lemma C.5 in Jin et al. ( 2018 ) )) .

$$ $\displaystyle\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi}_{h}}\left[\big{(} \mathbb{V}_{P^{\star}}V_{h+1;P^{\star}}^{\pi}\big{)}(s,a)\right]=\mathrm{VaR}_ {\pi}.$ $$

###### Lemma 9 (Generalization bounds of MLE for finite model class (Theorem E.4 in Wang et al. ( 2023 ) )) .

Let $\mathcal{X}$ be the context/feature space and $\mathcal{Y}$ be the label space, and we are given a dataset $D=\left\{(x_{i},y_{i})\right\}_{i\in[n]}$ from a martingale process:
for $i=1,2,...,n$, sample $x_{i}\sim\mathcal{D}_{i}(x_{1:i-1},y_{1:i-1})$ and $y_{i}\sim p(\cdot\mid x_{i})$.
Let $f^{\star}(x,y)=p(y\mid x)$ and we are given a realizable, *i.e.*, $f^{\star}\in\mathcal{F}$, function class $\mathcal{F}:\mathcal{X}\times\mathcal{Y}\to\Delta(\mathbb{R})$ of distributions.
Suppose $\mathcal{F}$ is finite.
Fix any $\delta\in(0,1)$, set $\beta=\log(|\mathcal{F}|/\delta)$ and define

$$ $\displaystyle\widehat{\mathcal{F}}=\left\{f\in\mathcal{F}:\sum_{i=1}^{n}\log f (x_{i},y_{i})\geq\max_{\widetilde{f}\in\mathcal{F}}\sum_{i=1}^{n}\log \widetilde{f}(x_{i},y_{i})-4\beta\right\}.$ $$

Then w.p. at least $1-\delta$, the following holds:

- (1)
The true distribution is in the version space, *i.e.*, $f^{\star}\in\widehat{\mathcal{F}}$.
- (2)
Any function in the version space is close to the ground truth data-generating distribution, *i.e.*, for all $f\in\widehat{\mathcal{F}}$
$\displaystyle\sum_{i=1}^{n}\mathbb{E}_{x\sim\mathcal{D}_{i}}\left[\mathbb{H}^{
2}(f(x,\cdot)\mathrel{\|}f^{\star}(x,\cdot))\right]\leq 22\beta.$

###### Lemma 10 (Generalization bounds of MLE for infinite model class (Theorem E.5 in Wang et al. ( 2023 ) )) .

Let $\mathcal{X}$ be the context/feature space and $\mathcal{Y}$ be the label space, and we are given a dataset $D=\left\{(x_{i},y_{i})\right\}_{i\in[n]}$ from a martingale process:
for $i=1,2,...,n$, sample $x_{i}\sim\mathcal{D}_{i}(x_{1:i-1},y_{1:i-1})$ and $y_{i}\sim p(\cdot\mid x_{i})$.
Let $f^{\star}(x,y)=p(y\mid x)$ and we are given a realizable, *i.e.*, $f^{\star}\in\mathcal{F}$, function class $\mathcal{F}:\mathcal{X}\times\mathcal{Y}\to\Delta(\mathbb{R})$ of distributions.
Suppose $\mathcal{F}$ is finite.
Fix any $\delta\in(0,1)$, set $\beta=\log(\mathcal{N}_{[]}((n|\mathcal{Y}|)^{-1},\mathcal{F},\|\cdot\|_{
\infty})/\delta)$ (where $\mathcal{N}_{[]}((n|\mathcal{Y}|)^{-1},\mathcal{F},\|\cdot\|_{\infty})$ is the bracketing number defined in Definition 2) and define

$$ $\displaystyle\widehat{\mathcal{F}}=\left\{f\in\mathcal{F}:\sum_{i=1}^{n}\log f (x_{i},y_{i})\geq\max_{\widetilde{f}\in\mathcal{F}}\sum_{i=1}^{n}\log \widetilde{f}(x_{i},y_{i})-7\beta\right\}.$ $$

Then w.p. at least $1-\delta$, the following holds:

- (1)
The true distribution is in the version space, *i.e.*, $f^{\star}\in\widehat{\mathcal{F}}$.
- (2)
Any function in the version space is close to the ground truth data-generating distribution, *i.e.*, for all $f\in\widehat{\mathcal{F}}$
$\displaystyle\sum_{i=1}^{n}\mathbb{E}_{x\sim\mathcal{D}_{i}}\left[\mathbb{H}^{
2}(f(x,\cdot)\mathrel{\|}f^{\star}(x,\cdot))\right]\leq 28\beta.$

###### Lemma 11 (Recursion Lemma) .

Let $G>0$ be a positive constant, $a<G/2$ is also a positive constant, and let $\{C_{m}\}_{m=0}^{N=\lceil\log_{2}(\frac{KH}{G})\rceil}$ be a sequence of positive real numbers satisfying:

- 1.
$C_{m}\leq 2^{m}G+\sqrt{aC_{m+1}}+a$ for all $m\geq 0$,
- 2.
$C_{m}\leq KH$ for all $m\geq 0$, where $K>0$ and $H>0$ are positive constants.

Then, it holds that:

$$ $C_{0}\leq 4G.$ $$

###### Proof of Lemma 11 .

We will prove by induction that for all $m\geq 0$,

$$ $C_{m}\leq 2^{m+2}G.$ $$

Then, for $m=0$, this would immediately show $C_{0}\leq 4G$.

1. The base case $m=N$:

Since $N=\lceil\log_{2}(\frac{KH}{G})\rceil$, it is obvious that $2^{N+2}G\geq KH$.
Thus, $C_{N}\leq KH\leq 2^{N+2}G$, the inequality holds for $m=N$.

2. The induction step:

Assume that for some $m\geq 0$, for $C_{m+1}$, we have:

$$ $C_{m+1}\leq 2^{m+1+2}G=2^{m+3}G.$ $$

Then, we have

$$ $\displaystyle C_{m}$ $\displaystyle\leq 2^{m}G+\sqrt{aC_{m+1}}+a$ $\displaystyle\leq 2^{m}G+\sqrt{a2^{m+3}G}+a$ $\displaystyle\leq 2^{m}G+\sqrt{\frac{G}{2}\cdot 2^{m+3}G}+\frac{G}{2}$ $\displaystyle=G\cdot(2^{m}+2^{m/2+1}+2^{-1})$ $\displaystyle\leq G\cdot(2^{m}+2^{m+1}+2^{m})$ $\displaystyle=2^{m+2}G\,.$ (22) $$

Therefore, by induction, we have
for all $m\geq 0$,

$$ $C_{m}\leq 2^{m+2}G.$ $$

And the proof follows by setting $m=0$.
∎

###### Lemma 7 (Simulation Lemma ( Agarwal et al. ( 2019 ) )) .

###### Lemma 8 (Change of Variance Lemma (Lemma C.5 in Jin et al. ( 2018 ) )) .

###### Lemma 9 (Generalization bounds of MLE for finite model class (Theorem E.4 in Wang et al. ( 2023 ) )) .

###### Lemma 10 (Generalization bounds of MLE for infinite model class (Theorem E.5 in Wang et al. ( 2023 ) )) .

###### Lemma 11 (Recursion Lemma) .

###### Proof of Lemma 11 .

## Appendix D Detailed Proofs for the online setting in Section 4

### D.1 Proof of Theorem 1

The following is the full proof of Theorem 1.

For notational simplicity, throughout this whole section, we denote

$$ $\displaystyle A$ $\displaystyle:=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\big{ (}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{ h}^{k})\right]$ $\displaystyle B$ $\displaystyle:=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\big{ (}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})\right],$ $\displaystyle C_{m}$ $\displaystyle:=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\big{ (}\mathbb{V}_{P^{\star}}(V_{h+1;\widehat{P}^{k}}^{\pi^{k}}-V_{h+1}^{\pi^{k}})^ {2^{m}}\big{)}(s_{h}^{k},a_{h}^{k})\right]$ $\displaystyle G$ $\displaystyle:=\sqrt{\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left [\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{ k},a_{h}^{k})\right]\cdot\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/ KH)\cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)}$ $\displaystyle\quad+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH) \cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)$ $\displaystyle I_{h}^{k}$ $\displaystyle:=\mathbb{E}_{s^{\prime}\sim P^{*}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k }}_{h+1;\widehat{P}^{k}}(s^{\prime})-V^{\pi^{k}}_{h+1;\widehat{P}^{k}}(s_{h+1} ^{k})$ (23) $$

We use $\mathbb{I}\{\cdot\}$ to denote the indicator function. We define the following events which we will later show that they happen with high probability.

$$ $\displaystyle\mathcal{E}_{1}$ $\displaystyle:=\{\forall k\in[K-1]:P^{\star}\in\widehat{\mathcal{P}}^{k},\text {and}\sum_{i=0}^{k-1}\sum_{h=0}^{H-1}\mathbb{H}^{2}(P^{\star}(s_{h}^{i},a_{h}^ {i})||\widehat{P}^{k}(s_{h}^{i},a_{h}^{i}))\leq 22\log(K\left|\mathcal{P} \right|/\delta).\}\,,$ (24) $\displaystyle\mathcal{E}_{2}$ $\displaystyle:=\Big{\{}\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}I_{ h}^{k}\lesssim\sqrt{\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\big{( }\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h }^{k})\log(1/\delta)}+\log(1/\delta)\Big{\}}\,,$ (25) $\displaystyle\mathcal{E}_{3}$ $\displaystyle:=\mathcal{E}_{1}\cap\{\forall m\in[0,\lceil\log_{2}(\frac{KH}{G} )\rceil]:C_{m}\lesssim 2^{m}G+\sqrt{\log(1/\delta)\cdot C_{m+1}}+\log(1/\delta )\}\,,$ (26) $\displaystyle\mathcal{E}_{4}$ $\displaystyle:=\{\sum_{k=0}^{K-1}\sum_{h=0}^{H-1}\left[\big{(}\mathbb{V}_{P^{ \star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})\right]\lesssim\sum_{k=0}^ {K-1}\mathrm{VaR}_{\pi^{k}}+\log(1/\delta)\}\,,$ (27) $\displaystyle\mathcal{E}_{5}$ $\displaystyle:=\{\sum_{k=0}^{K-1}\sum_{h=1}^{H}r(s_{h}^{k},a_{h}^{k})-\sum_{k= 0}^{K-1}V^{\pi^{k}}_{0;P^{*}}\lesssim\sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{ k}}\log(1/\delta)}+\log(1/\delta)\}\,,$ (28) $\displaystyle\mathcal{E}$ $\displaystyle:=\mathcal{E}_{2}\cap\mathcal{E}_{3}\cap\mathcal{E}_{4}\cap \mathcal{E}_{5}\,.$ (29) $$

First, by the realizability assumption, the standard generalization bound for MLE (Lemma 9) with simply setting $D_{i}$ to be the delta distribution on the realized $(s_{h}^{k},a_{h}^{k})$ pairs, and a union bound over $K$ episodes, we have that w.p. at least $1-\delta$, for any $k\in[0,K-1]$:

- (1)
$P^{\star}\in\widehat{\mathcal{P}}^{k}$;
- (2)
$\sum_{i=0}^{k-1}\sum_{h=0}^{H-1}\mathbb{H}^{2}(P^{\star}(s_{h}^{i},a_{h}^{i})|
|\widehat{P}^{k}(s_{h}^{i},a_{h}^{i}))\leq 22\log(K\left|\mathcal{P}\right|/
\delta).$
(30)

This directly indicates that

$$ $P(\mathbb{I}\{\mathcal{E}_{1}\})\geq 1-\delta\,.$ (31) $$

Under event $\mathcal{E}_{1}$, with the realizability in above (1), and by the optimistic algorithm design
$(\pi^{k},\widehat{P}^{k})\leftarrow\mathop{\mathrm{argmax}}_{\pi\in\Pi,P\in
\widehat{\mathcal{P}}^{k}}V_{0;P}^{\pi}(s_{0})$, for any $k\in[0,K-1]$, we have the following optimism guarantee

$$ $\displaystyle V^{\star}_{0;P^{\star}}$ $\displaystyle\leq\max_{\pi\in\Pi,P\in\widehat{\mathcal{P}}^{k}}V^{\pi}_{0;P}=V ^{\pi^{k}}_{0;\widehat{P}^{k}}.$ $$

Then, under event $\mathcal{E}_{1}$, we use Lemma 6 and Equation 30 to get the following:

There exists a set $\mathcal{K}\subseteq[K-1]$ such that

- •
$|\mathcal{K}|\leq 13\log^{2}(88\log(K\left|\mathcal{P}\right|/\delta)KH)\cdot
DE
_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/(176\log(K\left|\mathcal{P}\right|/
\delta)KH))$
- •
And
$\displaystyle\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\mathbb{H}^{2
}\Big{(}P^{\star}(s_{h}^{k},a_{h}^{k})\mathrel{\|}\widehat{P}^{k}\big{(}s_{h}^
{k},a_{h}^{k})\Big{)}$
$\displaystyle\leq\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)\cdot(
2+154\log(K\left|\mathcal{P}\right|/\delta)\log(KH))+1$
$\displaystyle\lesssim\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)
\cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)\,.$
(32)

We upper bound the regret with optimism, and by dividing $k\in[K-1]$ into $\mathcal{K}$ and $[K-1]\setminus\mathcal{K}$ with the assumption that the trajectory-wise cumulative reward is normalized in [0,1], as follows

$$ $\displaystyle\sum_{k=0}^{K-1}V^{\star}_{0;P^{\star}}-\sum_{k=0}^{K-1}\sum_{h=1 }^{H}r(s_{h}^{k},a_{h}^{k})$ $\displaystyle\leq|\mathcal{K}|+\sum_{k\in[K-1]\setminus\mathcal{K}}\left(V^{ \pi^{k}}_{0;\widehat{P}^{k}}-\sum_{h=0}^{H-1}r(s_{h}^{k},a_{h}^{k})\right)$ $\displaystyle\lesssim\log^{2}(\log(K\left|\mathcal{P}\right|/\delta)KH)\cdot DE _{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/(\log(K\left|\mathcal{P}\right|/ \delta)KH))+\sum_{k\in[K-1]\setminus\mathcal{K}}\left(V^{\pi^{k}}_{0;\widehat{ P}^{k}}-\sum_{h=0}^{H-1}r(s_{h}^{k},a_{h}^{k})\right)\,.$ (33) $$

We then do the following decomposition. Note that for any $k\in[K-1]$, policy $\pi^{k}$ is deterministic. We have that for any $k\in[K-1]$

$$ $\displaystyle V^{\pi^{k}}_{0;\widehat{P}^{k}}(s_{0}^{k})-\sum_{h=0}^{H-1}r(s_{ h}^{k},a_{h}^{k})$ $\displaystyle=Q^{\pi^{k}}_{0;\widehat{P}^{k}}(s_{0}^{k},a_{0}^{k})-\sum_{h=0}^ {H-1}r(s_{h}^{k},a_{h}^{k})$ $\displaystyle=r(s_{0}^{k},a_{0}^{k})+\mathbb{E}_{s^{\prime}\sim\widehat{P}^{k} (s_{0}^{k},a_{0}^{k})}V^{\pi^{k}}_{1;\widehat{P}^{k}}(s^{\prime})-\sum_{h=0}^{ H-1}r(s_{h}^{k},a_{h}^{k})$ $\displaystyle=\mathbb{E}_{s^{\prime}\sim\widehat{P}^{k}(s_{0}^{k},a_{0}^{k})}V ^{\pi^{k}}_{1;\widehat{P}^{k}}(s^{\prime})-\sum_{h=1}^{H}r(s_{h}^{k},a_{h}^{k})$ $\displaystyle=\mathbb{E}_{s^{\prime}\sim P^{*}(s_{0}^{k},a_{0}^{k})}V^{\pi^{k} }_{1;\widehat{P}^{k}}(s^{\prime})-\sum_{h=1}^{H}r(s_{h}^{k},a_{h}^{k})+\mathbb {E}_{s^{\prime}\sim\widehat{P}^{k}(s_{0}^{k},a_{0}^{k})}V^{\pi^{k}}_{1; \widehat{P}^{k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim P^{*}(s_{0}^{k},a_{0}^ {k})}V^{\pi^{k}}_{1;\widehat{P}^{k}}(s^{\prime})$ $\displaystyle=V^{\pi^{k}}_{1;\widehat{P}^{k}}(s_{1}^{k})-\sum_{h=1}^{H-1}r(s_{ h}^{k},a_{h}^{k})+\underbrace{\mathbb{E}_{s^{\prime}\sim P^{*}(s_{0}^{k},a_{0} ^{k})}V^{\pi^{k}}_{1;\widehat{P}^{k}}(s^{\prime})-V^{\pi^{k}}_{1;\widehat{P}^{ k}}(s_{1}^{k})}_{I_{0}^{k}}$ $\displaystyle\quad+\mathbb{E}_{s^{\prime}\sim\widehat{P}^{k}(s_{0}^{k},a_{0}^{ k})}V^{\pi^{k}}_{1;\widehat{P}^{k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim P^{ *}(s_{0}^{k},a_{0}^{k})}V^{\pi^{k}}_{1;\widehat{P}^{k}}(s^{\prime})\,,$ $$

where we use the Bellman equation for several times.

Then, by doing this recursively, we can get for any $k\in[K-1]$

$$ $\displaystyle V^{\pi^{k}}_{0;\widehat{P}^{k}}(s_{h}^{k})-\sum_{h=0}^{H-1}r(s_{ h}^{k},a_{h}^{k})$ $\displaystyle\leq\sum_{h=0}^{H-1}I_{h}^{k}+\sum_{h=0}^{H-1}\left|\mathbb{E}_{s ^{\prime}\sim\widehat{P}^{k}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k}}_{h+1;\widehat{P} ^{k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim P^{*}(s_{h}^{k},a_{h}^{k})}V^{\pi ^{k}}_{{h+1};\widehat{P}^{k}}(s^{\prime})\right|$ (34) $$

Therefore,

$$ $\displaystyle\sum_{k\in[K-1]\setminus\mathcal{K}}(V^{\pi^{k}}_{0;\widehat{P}^{ k}}(s_{h}^{k})-\sum_{h=0}^{H-1}r(s_{h}^{k},a_{h}^{k}))$ $\displaystyle\leq\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}I_{h}^{k} +\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left|\mathbb{E}_{s^{ \prime}\sim\widehat{P}^{k}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k}}_{h+1;\widehat{P}^{ k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim P^{*}(s_{h}^{k},a_{h}^{k})}V^{\pi^{ k}}_{{h+1};\widehat{P}^{k}}(s^{\prime})\right|$ (35) $$

Next we bound $\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}I_{h}^{k}$. Note that by Azuma Bernstein’s inequality, with probability at least $1-\delta$

$$ $\displaystyle\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}I_{h}^{k}\leq \sqrt{2\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\big{(}\mathbb{V}_{ P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})\log(1/ \delta)}+\frac{2}{3}\log(1/\delta)$ (36) $$

This directly indicates that

$$ $P(\mathbb{I}\{\mathcal{E}_{2}\})\geq 1-\delta\,.$ (37) $$

Then, we propose the following lemma.

###### Lemma 12 (Bound of sum of mean value differences for online RL) .

Under event $\mathcal{E}_{1}$, we have

$$ $\displaystyle\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left|\mathbb {E}_{s^{\prime}\sim\widehat{P}^{k}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k}}_{h+1; \widehat{P}^{k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim P^{*}(s_{h}^{k},a_{h}^ {k})}V^{\pi^{k}}_{{h+1};\widehat{P}^{k}}(s^{\prime})\right|$ $\displaystyle\lesssim\sqrt{\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1 }\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s _{h}^{k},a_{h}^{k})\right]\cdot\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{ A},1/KH)\cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)}$ $\displaystyle\quad+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH) \cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH).$ $$

###### Proof of Lemma 12 .

Under event $\mathcal{E}_{1}$, we have

$$ $\displaystyle\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left|\mathbb {E}_{s^{\prime}\sim\widehat{P}^{k}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k}}_{h+1; \widehat{P}^{k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim P^{*}(s_{h}^{k},a_{h}^ {k})}V^{\pi^{k}}_{{h+1};\widehat{P}^{k}}(s^{\prime})\right|$ $\displaystyle\leq 4\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[ \sqrt{\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_ {h}^{k},a_{h}^{k})D_{\triangle}\Big{(}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{(} s^{\prime}\sim P^{\star}(s_{h}^{k},a_{h}^{k})\big{)}\mathrel{\|}V_{h+1; \widehat{P}^{k}}^{\pi^{k}}(s^{\prime}\sim\widehat{P}^{k}\big{(}s_{h}^{k},a_{h} ^{k})\big{)}\Big{)}}\right]$ $\displaystyle\quad+5\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[ D_{\triangle}\Big{(}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{(}s^{\prime}\sim P^{ \star}(s_{h}^{k},a_{h}^{k})\big{)}\mathrel{\|}V_{h+1;\widehat{P}^{k}}^{\pi^{k} }(s^{\prime}\sim\widehat{P}^{k}\big{(}s_{h}^{k},a_{h}^{k})\big{)}\Big{)}\right]$ $\displaystyle\leq 8\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[ \sqrt{\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_ {h}^{k},a_{h}^{k})\mathbb{H}^{2}\Big{(}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{( }s^{\prime}\sim P^{\star}(s_{h}^{k},a_{h}^{k})\big{)}\mathrel{\|}V_{h+1; \widehat{P}^{k}}^{\pi^{k}}(s^{\prime}\sim\widehat{P}^{k}\big{(}s_{h}^{k},a_{h} ^{k})\big{)}\Big{)}}\right]$ $\displaystyle\quad+20\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left [\mathbb{H}^{2}\Big{(}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{(}s^{\prime}\sim P ^{\star}(s_{h}^{k},a_{h}^{k})\big{)}\mathrel{\|}V_{h+1;\widehat{P}^{k}}^{\pi^{ k}}(s^{\prime}\sim\widehat{P}^{k}\big{(}s_{h}^{k},a_{h}^{k})\big{)}\Big{)}\right]$ $\displaystyle\leq 8\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[ \sqrt{\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_ {h}^{k},a_{h}^{k})\mathbb{H}^{2}\Big{(}P^{\star}(s_{h}^{k},a_{h}^{k})\mathrel{ \|}\widehat{P}^{k}\big{(}s_{h}^{k},a_{h}^{k})\Big{)}}\right]$ $\displaystyle\quad+20\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left [\mathbb{H}^{2}\Big{(}P^{\star}(s_{h}^{k},a_{h}^{k})\mathrel{\|}\widehat{P}^{k }\big{(}s_{h}^{k},a_{h}^{k})\Big{)}\right]$ $\displaystyle\leq 8\sqrt{\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1} \left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_ {h}^{k},a_{h}^{k})\right]\cdot\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{ H-1}\left[\mathbb{H}^{2}\Big{(}P^{\star}(s_{h}^{k},a_{h}^{k})\mathrel{\|} \widehat{P}^{k}\big{(}s_{h}^{k},a_{h}^{k})\Big{)}\right]}$ $\displaystyle\quad+20\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left [\mathbb{H}^{2}\Big{(}P^{\star}(s_{h}^{k},a_{h}^{k})\mathrel{\|}\widehat{P}^{k }\big{(}s_{h}^{k},a_{h}^{k})\Big{)}\right]$ $\displaystyle\lesssim\sqrt{\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1 }\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s _{h}^{k},a_{h}^{k})\right]\cdot\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{ A},1/KH)\cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)}$ $\displaystyle\quad+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH) \cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)\,,$ (38) $$

where in the first inequality, we use Lemma 1 to bound the difference of two means $\mathbb{E}_{s^{\prime}\sim P^{\star}(s_{h}^{k},a_{h}^{k})}V^{\pi^{k}}_{h+1;
\widehat{P}^{k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim\widehat{P}^{k}(s_{h}^{
k},a_{h}^{k})}V^{\pi^{*}}_{h+1;\widehat{P}^{k}}(s^{\prime})$ using variances and the triangle discrimination; in the second inequality we use the fact that that triangle discrimination is equivalent to squared Hellinger distance, i.e., $D_{\triangle}\leq 4\mathbb{H}^{2}$; the third inequality is via data processing inequality on the squared Hellinger distance; the fourth inequality is by the Cauchy–Schwarz inequality; the last inequality holds under $\mathcal{E}_{1}$ by Equation 32.
∎

The next lemma shows that the event $\mathcal{E}_{3}$ happens with high probability.

###### Lemma 13 (Recursion Event Lemma) .

Event $\mathcal{E}_{3}$ happens with high probability. Specifically, we have

$$ $P(\mathbb{I}\{\mathcal{E}_{3}\})\geq 1-(1+\lceil\log_{2}(\frac{KH}{G})\rceil)\delta.$ (39) $$

###### Proof of Lemma 13 .

Let $\Delta_{h+1}^{\pi^{k}}:=V_{h+1;\widehat{P}^{k}}^{\pi^{k}}-V_{h+1}^{\pi^{k}}$. First, under event $\mathcal{E}_{1}$, with happens with probability at least $1-\delta$ by Equation 31, and also note that $\pi^{k}$ is deterministic for any $k\in[K-1]$, we can prove the following

$$ $\displaystyle\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\left|( \Delta_{h}^{\pi^{k}})(s_{h}^{k})-\big{(}P^{\star}\Delta_{h+1}^{\pi^{k}}\big{)} (s_{h}^{k},a_{h}^{k})\right|\right]$ (40) $\displaystyle=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\left| ({V}_{h;\widehat{P}^{k}}^{\pi^{k}})(s_{h}^{k})-\big{(}P^{\star}{V}_{h+1; \widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})-\Big{(}({V}_{h}^{\pi^{k }})(s_{h}^{k})-\big{(}P^{\star}{V}_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k}) \Big{)}\right|\right]$ $\displaystyle=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\left| r(s_{h}^{k},a_{h}^{k})+\big{(}\widehat{P}^{k}{V}_{h+1;\widehat{P}^{k}}^{\pi^{k }}\big{)}(s_{h}^{k},a_{h}^{k})-\big{(}P^{\star}{V}_{h+1;\widehat{P}^{k}}^{\pi^ {k}}\big{)}(s_{h}^{k},a_{h}^{k})-r(s_{h}^{k},a_{h}^{k})\right|\right]$ $\displaystyle=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\left| \big{(}\widehat{P}^{k}{V}_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{ h}^{k})-\big{(}P^{\star}{V}_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a _{h}^{k})\right|\right]$ $\displaystyle=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\left| \mathbb{E}_{s^{\prime}\sim P^{\star}(s_{h}^{k},a_{h}^{k})}\left[V^{\pi^{k}}_{h +1;\widehat{P}^{k}}(s^{\prime})\right]-\mathbb{E}_{s^{\prime}\sim\widehat{P}^{ k}(s_{h}^{k},a_{h}^{k})}\left[V^{\pi^{k}}_{h+1;\widehat{P}^{k}}(s^{\prime}) \right]\right|\right]$ $\displaystyle\lesssim\sqrt{\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1 }\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s _{h}^{k},a_{h}^{k})\right]\cdot\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{ A},1/KH)\cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)}$ $\displaystyle\quad+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH) \cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)$ $\displaystyle=G$ (41) $$

where the first equality is by the definition of $\Delta_{h+1}^{\pi^{k}}$, the inequality holds under $\mathcal{E}_{1}$ by Lemma 12, and the last equality is by definition of $A$ and $G$.

Under event $\mathcal{E}_{1}$, with probability at least $1-\lceil\log_{2}(\frac{KH}{G})\rceil\delta$, for any $m\in[0,\lceil\log_{2}(\frac{KH}{G})\rceil]$

$$ $\displaystyle C_{m}$ $\displaystyle=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\big{( }\mathbb{V}_{P^{\star}}(V_{h+1;\widehat{P}^{k}}^{\pi^{k}}-V_{h+1}^{\pi^{k}})^{ 2^{m}}\big{)}(s_{h}^{k},a_{h}^{k})\right]$ $\displaystyle=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\big{( }P^{\star}(\Delta_{h+1}^{\pi^{k}})^{2^{m+1}}\big{)}(s_{h}^{k},a_{h}^{k})-\big{ (}(P^{\star}(\Delta_{h+1}^{\pi^{k}})^{2^{m}})(s_{h}^{k},a_{h}^{k})\big{)}^{2}\right]$ $\displaystyle=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[( \Delta_{h+1}^{\pi^{k}})^{2^{m+1}}(s_{h+1}^{k})\right]-\sum_{k\in[K-1]\setminus \mathcal{K}}\sum_{h=0}^{H-1}\left[\big{(}(P^{\star}(\Delta_{h+1}^{\pi^{k}})^{2 ^{m}})(s_{h}^{k},a_{h}^{k})\big{)}^{2}\right]$ $\displaystyle\quad+\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left( \mathbb{E}_{s\sim P^{*}(s_{h}^{k},a_{h}^{k})}\left[(\Delta_{h+1}^{\pi^{k}})^{2 ^{m+1}}(s)\right]-(\Delta_{h+1}^{\pi^{k}})^{2^{m+1}}(s_{h+1}^{k})\right)$ $\displaystyle\leq\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[( \Delta_{h}^{\pi^{k}})^{2^{m+1}}(s_{h}^{k})-\big{(}(P^{\star}(\Delta_{h+1}^{\pi ^{k}})^{2^{m}})(s_{h}^{k},a_{h}^{k})\big{)}^{2}\right]$ $\displaystyle\quad+\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left( \mathbb{E}_{s\sim P^{*}(s_{h}^{k},a_{h}^{k})}\left[(\Delta_{h+1}^{\pi^{k}})^{2 ^{m+1}}(s)\right]-(\Delta_{h+1}^{\pi^{k}})^{2^{m+1}}(s_{h}^{k})\right)$ $\displaystyle\lesssim\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left [(\Delta_{h}^{\pi^{k}})^{2^{m+1}}(s_{h}^{k})-\big{(}(P^{\star}(\Delta_{h+1}^{ \pi^{k}})^{2^{m}})(s_{h}^{k},a_{h}^{k})\big{)}^{2}\right]+\log(1/\delta)$ $\displaystyle\quad+\sqrt{\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1} \mathbb{V}_{P^{*}}\left((V_{h+1;\widehat{P}^{k}}^{\pi^{k}}-V_{h+1}^{\pi^{k}})^ {2^{m+1}}\right)(s_{h}^{k},a_{h}^{k})\log(1/\delta)}$ $\displaystyle=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\Big{( }(\Delta_{h}^{\pi^{k}})^{2^{m}}(s_{h}^{k})+(P^{\star}(\Delta_{h+1}^{\pi^{k}})^ {2^{m}})(s_{h}^{k},a_{h}^{k})\Big{)}\cdot\Big{(}(\Delta_{h}^{\pi^{k}})^{2^{m}} (s_{h}^{k})-(P^{\star}(\Delta_{h+1}^{\pi^{k}})^{2^{m}})(s_{h}^{k},a_{h}^{k}) \Big{)}\right]$ $\displaystyle\quad+\sqrt{\log(1/\delta)\cdot C_{m+1}}+\log(1/\delta)$ $\displaystyle=\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\Big{( }(\Delta_{h}^{\pi^{k}})^{2^{m}}(s_{h}^{k})+(P^{\star}(\Delta_{h+1}^{\pi^{k}})^ {2^{m}})(s_{h}^{k},a_{h}^{k})\Big{)}\cdot\Big{(}(\Delta_{h}^{\pi^{k}})^{2^{m}} (s_{h}^{k})-(P^{\star}((\Delta_{h+1}^{\pi^{k}})^{2})^{2^{m-1}})(s_{h}^{k},a_{h }^{k})\Big{)}\right]$ $\displaystyle\quad+\sqrt{\log(1/\delta)\cdot C_{m+1}}+\log(1/\delta)$ $\displaystyle\leq\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[ \Big{(}(\Delta_{h}^{\pi^{k}})^{2^{m}}(s_{h}^{k})+(P^{\star}(\Delta_{h+1}^{\pi^ {k}})^{2^{m}})(s_{h}^{k},a_{h}^{k})\Big{)}\cdot\Big{(}(\Delta_{h}^{\pi^{k}})^{ 2^{m}}(s_{h}^{k})-((P^{\star}(\Delta_{h+1}^{\pi^{k}})^{2})(s_{h}^{k},a_{h}^{k} ))^{2^{m-1}}\Big{)}\right]$ $\displaystyle\quad+\sqrt{\log(1/\delta)\cdot C_{m+1}}+\log(1/\delta)$ $\displaystyle\leq 2^{m}\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1} \left[\left|(\Delta_{h}^{\pi^{k}})^{2}(s_{h}^{k})-((P^{\star}\Delta_{h+1}^{\pi ^{k}})(s_{h}^{k},a_{h}^{k}))^{2}\right|\right]+\sqrt{\log(1/\delta)\cdot C_{m+ 1}}+\log(1/\delta)$ $\displaystyle=2^{m}\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[ \left|\big{(}(\Delta_{h}^{\pi^{k}})(s_{h}^{k})+(P^{\star}\Delta_{h+1}^{\pi^{k} })(s_{h}^{k},a_{h}^{k})\big{)}\cdot\big{(}(\Delta_{h}^{\pi^{k}})(s_{h}^{k})-(P ^{\star}\Delta_{h+1}^{\pi^{k}})(s_{h}^{k},a_{h}^{k})\big{)}\right|\right]$ $\displaystyle\quad+\sqrt{\log(1/\delta)\cdot C_{m+1}}+\log(1/\delta)$ $\displaystyle\leq 2\cdot 2^{m}\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{ H-1}\left[\left|(\Delta_{h}^{\pi^{k}})(s_{h}^{k})-\big{(}P^{\star}\Delta_{h+1} ^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})\right|\right]+\sqrt{\log(1/\delta)\cdot C _{m+1}}+\log(1/\delta)$ $\displaystyle\lesssim 2^{m}G+\sqrt{\log(1/\delta)\cdot C_{m+1}}+\log(1/\delta)\,,$ (42) $$

where in the first inequality we change the index, the second inequality holds with probability at least $1-\delta$ by Azuma Bernstain’s inequality, the third inequality holds because that $E[X^{2^{m-1}}]\geq(E[X])^{2^{m-1}}$ for $m\geq 1$ and $X\geq 0$, the fourth inequality holds by keep using $a^{2}-b^{2}=(a+b)(a-b)$, then with $E[X^{2}]\geq E[X]^{2}$, and the assumption that the trajectory-wise total reward is normalized in $[0,1]$, the last inequality holds under $\mathcal{E}_{1}$ by Equation 41, and we take a union bound to get this hold for all $m\in[0,\lceil\log_{2}(\frac{KH}{G})\rceil]$ with probability at least $1-\lceil\log_{2}(\frac{KH}{G})\rceil\delta$ (because for each $m\in[0,\lceil\log_{2}(\frac{KH}{G})\rceil]$ we need to apply the Azuma Bernstain’s inequality once).

The above reasoning directly implies that

$$ $P(\mathbb{I}\{\mathcal{E}_{3}\})\geq 1-(1+\lceil\log_{2}(\frac{KH}{G})\rceil)\delta.$ (43) $$

∎

Under the event $\mathcal{E}_{3}$, we prove the following lemma to bound $\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\big{(}\mathbb{V}_{P
^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})\right]$.

###### Lemma 14 (Variance Conversion Lemma for online RL) .

Under event $\mathcal{E}_{3}$, we have

$$ $\displaystyle\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\big{(} \mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h} ^{k})\right]$ $\displaystyle\leq O\Big{(}\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1} \left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k })\right]+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)\cdot\log(K \left|\mathcal{P}\right|/\delta)\log(KH)\Big{)}.$ $$

###### Proof of Lemma 14 .

Under $\mathcal{E}_{3}$, we have for any $m\in[0,\lceil\log_{2}(\frac{KH}{G})\rceil]$

$$ $C_{m}\lesssim 2^{m}G+\sqrt{\log(1/\delta)\cdot C_{m+1}}+\log(1/\delta)\,.$ (44) $$

Then, by Lemma 11, we have

$$ $C_{0}\lesssim G\,.$ (45) $$

Also note that we have $A\leq 2B+2C_{0}$ since $\mathbb{V}_{P^{\star}}(a+b)\leq 2\mathbb{V}_{P^{\star}}(a)+2\mathbb{V}_{P^{
\star}}(b)$.
Therefore, we have

$$ $\displaystyle A$ $\displaystyle\leq 2B+2C_{0}$ $\displaystyle\lesssim B+G$ $\displaystyle=B+\sqrt{A\cdot\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A}, 1/KH)\cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)}$ $\displaystyle\quad+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH) \cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)$ (46) $$

Then, with the fact that $x\leq 2a+b^{2}$ if $x\leq a+b\sqrt{x}$, we have

$$ $\displaystyle A$ $\displaystyle\leq O\Bigg{(}B+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A} ,1/KH)\cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)\Bigg{)}\,,$ (47) $$

which is

$$ $\displaystyle\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\big{(} \mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h} ^{k})\right]$ $\displaystyle\leq O\bigg{(}\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1 }\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{ k})\right]+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)\cdot\log(K \left|\mathcal{P}\right|/\delta)\log(KH)\bigg{)}$ (48) $$

∎

By the same reasoning in Lemma 26 of Zhou et al. (), we have that with probability at least $1-\delta$

$$ $\displaystyle\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left[\big{(} \mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})\right]$ $\displaystyle\leq\sum_{k=0}^{K-1}\sum_{h=0}^{H-1}\left[\big{(}\mathbb{V}_{P^{ \star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k})\right]$ $\displaystyle\leq O(\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}+\log(1/\delta))\,.$ (49) $$

This indicates that

$$ $P(\mathbb{I}\{\mathcal{E}_{4}\})\geq 1-\delta\,.$ (50) $$

We can use the Azuma Bernstain’s inequality to get that with probability at least $1-\delta$:

$$ $\displaystyle\sum_{k=0}^{K-1}\sum_{h=1}^{H}r(s_{h}^{k},a_{h}^{k})-\sum_{k=0}^{ K-1}V^{\pi^{k}}_{0;P^{*}}\lesssim\sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}} \log(1/\delta)}+\log(1/\delta)\,.$ (51) $$

This indicates that

$$ $P(\mathbb{I}\{\mathcal{E}_{5}\})\geq 1-\delta\,.$ (52) $$

Then, together with Lemma 13, Equation 31 and Equation 37, we have

$$ $P(\mathbb{I}\{\mathcal{E}\})\geq 1-(5+\lceil\log_{2}(\frac{KH}{G})\rceil) \delta\geq 1-5KH\delta\,.$ (53) $$

Finally, under event $\mathcal{E}$, with all the things above (Equation 33, Equation 35, Equation 36,Lemma 12, Lemma 14), we have

$$ $\displaystyle\sum_{k=0}^{K-1}V^{\star}_{0;P^{\star}}-\sum_{k=0}^{K-1}V^{\pi^{k }}_{0;P^{*}}$ $\displaystyle=\sum_{k=0}^{K-1}V^{\star}_{0;P^{\star}}-\sum_{k=0}^{K-1}\sum_{h= 1}^{H}r(s_{h}^{k},a_{h}^{k})+\sum_{k=0}^{K-1}\sum_{h=1}^{H}r(s_{h}^{k},a_{h}^{ k})-\sum_{k=0}^{K-1}V^{\pi^{k}}_{0;P^{*}}$ $\displaystyle\lesssim|\mathcal{K}|+\sum_{k\in[K-1]\setminus\mathcal{K}}\left(V ^{\pi^{k}}_{0;\widehat{P}^{k}}-\sum_{h=0}^{H-1}r(s_{h}^{k},a_{h}^{k})\right)+ \sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}\log(1/\delta)}+\log(1/\delta)$ $\displaystyle\lesssim\log^{2}(\log(K\left|\mathcal{P}\right|/\delta)KH)\cdot DE _{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/(\log(K\left|\mathcal{P}\right|/ \delta)KH))+\sum_{k\in[K-1]\setminus\mathcal{K}}\left(V^{\pi^{k}}_{0;\widehat{ P}^{k}}-\sum_{h=0}^{H-1}r(s_{h}^{k},a_{h}^{k})\right)$ $\displaystyle\quad+\sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}\log(1/\delta)} +\log(1/\delta)$ $\displaystyle\lesssim\log^{2}(\log(K\left|\mathcal{P}\right|/\delta)KH)\cdot DE _{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/(\log(K\left|\mathcal{P}\right|/ \delta)KH))+\log(1/\delta)$ $\displaystyle\quad+\sqrt{\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1} \big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_{h}^{k },a_{h}^{k})\log(1/\delta)}+\sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}\log(1 /\delta)}$ $\displaystyle\quad+\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left| \mathbb{E}_{s^{\prime}\sim\widehat{P}^{k}(s_{1}^{k},A^{k})}V^{\pi^{k}}_{1; \widehat{P}^{k}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim P^{*}(s_{1}^{k},A^{k}) }V^{\pi^{k}}_{1;\widehat{P}^{k}}(s^{\prime})\right|$ $\displaystyle\lesssim\log^{2}(\log(K\left|\mathcal{P}\right|/\delta)KH)\cdot DE _{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/(\log(K\left|\mathcal{P}\right|/ \delta)KH))+\sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}\log(1/\delta)}+\log(1 /\delta)$ $\displaystyle+\sqrt{(\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left [\big{(}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k}) \right]+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)\cdot\log(K \left|\mathcal{P}\right|/\delta)\log(KH))\cdot\log(1/\delta)}$ $\displaystyle\quad+\sqrt{\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1} \left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}^{k}}^{\pi^{k}}\big{)}(s_ {h}^{k},a_{h}^{k})\right]\cdot\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A },1/KH)\cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)}$ $\displaystyle\lesssim\log^{2}(\log(K\left|\mathcal{P}\right|/\delta)KH)\cdot DE _{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/(\log(K\left|\mathcal{P}\right|/ \delta)KH))+\sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}\log(1/\delta)}+\log(1 /\delta)$ $\displaystyle+\sqrt{(\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left [\big{(}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k}) \right]+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)\cdot\log(K \left|\mathcal{P}\right|/\delta)\log(KH))\cdot\log(1/\delta)}$ $\displaystyle+\sqrt{(\sum_{k\in[K-1]\setminus\mathcal{K}}\sum_{h=0}^{H-1}\left [\big{(}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{k}}\big{)}(s_{h}^{k},a_{h}^{k}) \right]+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)\cdot\log(K \left|\mathcal{P}\right|/\delta)\log(KH))}$ $\displaystyle\quad\times\sqrt{\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A },1/KH)\cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH))}$ $\displaystyle\lesssim\log^{2}(\log(K\left|\mathcal{P}\right|/\delta)KH)\cdot DE _{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/(\log(K\left|\mathcal{P}\right|/ \delta)KH))+\sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}\log(1/\delta)}+\log(1 /\delta)$ $\displaystyle+\sqrt{(\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}+\log(1/\delta)+ \text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)\cdot\log(K\left| \mathcal{P}\right|/\delta)\log(KH))\cdot\log(1/\delta)}$ $\displaystyle+\sqrt{\left(\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}+\log\left( \frac{1}{\delta}\right)+\text{DE}_{1}\left(\Psi,{\mathcal{S}}\times\mathcal{A} ,\frac{1}{KH}\right)\cdot\log\left(\frac{K\left|\mathcal{P}\right|}{\delta} \right)\log(KH)\right)}$ $\displaystyle\quad\times\sqrt{\text{DE}_{1}\left(\Psi,{\mathcal{S}}\times \mathcal{A},\frac{1}{KH}\right)\log\left(\frac{K\left|\mathcal{P}\right|}{ \delta}\right)\log(KH)}$ $\displaystyle\leq O\Big{(}\sqrt{\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}\cdot \text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH)\cdot\log(K\left| \mathcal{P}\right|/\delta)\log(KH)}$ $\displaystyle\quad+\text{DE}_{1}(\Psi,{\mathcal{S}}\times\mathcal{A},1/KH) \cdot\log(K\left|\mathcal{P}\right|/\delta)\log(KH)\Big{)}\,.$ (54) $$

The final result follows by replacing $\delta$ to be $\delta/(5KH)$ to make the event $\mathcal{E}$ happen with probability at least $1-\delta$.

###### Lemma 12 (Bound of sum of mean value differences for online RL) .

###### Proof of Lemma 12 .

###### Lemma 13 (Recursion Event Lemma) .

###### Proof of Lemma 13 .

###### Lemma 14 (Variance Conversion Lemma for online RL) .

###### Proof of Lemma 14 .

### D.2 Proof of Corollary 2

###### Proof of Corollary 2 .

By Lemma 8, we have

$$ $\mathrm{VaR}_{\pi^{k}}=\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{k}}_{h}} \left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{k}}\big{)}(s,a)\right]$ (55) $$

Therefore, when $P^{\star}$ is deterministic,
the $\mathbb{E}_{s,a\sim d^{\pi^{k}}_{h}}\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1}
^{\pi^{k}}\big{)}(s,a)\right]$ terms are all 0 for any $k\in[K-1]$ and $h\in[H-1]$, and then the $\sum_{k=0}^{K-1}\mathrm{VaR}_{\pi^{k}}$ term in the higher order term in Theorem 1 is 0.
∎

###### Proof of Corollary 2 .

### D.3 Proof of Corollary 3

###### Proof of Corollary 3 .

We follow the MLE guarantee for the infinite model class in Lemma 10 and the same proof steps in the proof of Theorem 1 in Appendix D.1.
∎

###### Proof of Corollary 3 .

## Appendix E Detailed Proofs for the Offline RL setting in Section 5

### E.1 Proof of Theorem 2

The following is the full proof of Theorem 2.

###### Proof of Theorem 2 .

First, by the realizability assumption, the standard generalization bound for MLE (Lemma 9) with simply setting $D_{i}$ to be the delta distribution on the $(s_{h}^{k},a_{h}^{k})$ pairs in the offline dataset $\mathcal{D}$, we have that w.p. at least $1-\delta$ :

- (1)
$P^{\star}\in\widehat{\mathcal{P}}$;
- (2)
$\frac{1}{K}\sum_{k=1}^{K}\sum_{h=0}^{H-1}\mathbb{H}^{2}(P^{\star}(s_{h}^{k},a_
{h}^{k})||\widehat{P}(s_{h}^{k},a_{h}^{k}))\leq\frac{22\log(\left|\mathcal{P}
\right|/\delta)}{K}.$
(56)

Then, with the above realizability in (1), and by the pessimistic algorithm design $\hat{\pi}\leftarrow\mathop{\mathrm{argmax}}_{\pi\in\Pi}\min_{P\in\widehat{
\mathcal{P}}}V_{0;P}^{\pi}(s_{0})$, $\widehat{P}\leftarrow\mathop{\mathrm{argmin}}_{P\in\widehat{\mathcal{P}}}V_{0;
P}^{\widehat{\pi}}(s_{0})$, we have that for any $\pi^{\star}\in\Pi$

$$ $\displaystyle V_{0;P^{\star}}^{\pi^{\star}}-V_{0;P^{\star}}^{\hat{\pi}}$ $\displaystyle=V_{0;P^{\star}}^{\pi^{\star}}-V_{0;\widehat{P}}^{\pi^{\star}}+V_ {0;\widehat{P}}^{\pi^{\star}}-V_{0;P^{\star}}^{\hat{\pi}}$ $\displaystyle\leq V_{0;P^{\star}}^{\pi^{\star}}-V_{0;\widehat{P}}^{\pi^{\star} }+V_{0;\widehat{P}}^{\hat{\pi}}-V_{0;P^{\star}}^{\hat{\pi}}$ $\displaystyle\leq V_{0;P^{\star}}^{\pi^{\star}}-V_{0;\widehat{P}}^{\pi^{\star} }\,.$ (57) $$

We can then bound $V_{0;P^{\star}}^{\pi^{\star}}-V_{0;\widehat{P}}^{\pi^{\star}}$ using the simulation lemma (Lemma 7):

$$ $\displaystyle V_{0;P^{\star}}^{\pi^{\star}}-V_{0;\widehat{P}}^{\pi^{\star}}$ $\displaystyle\leq\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left [\left|\mathbb{E}_{s^{\prime}\sim P^{\star}(s,a)}V^{\pi^{\star}}_{h+1;\widehat {P}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim\widehat{P}(s,a)}V^{\pi^{\star}}_{h +1;\widehat{P}}(s^{\prime})\right|\right]\,.$ (58) $$

Then, we prove the following lemma to bound the RHS of Equation 58.

###### Lemma 15 (Bound of sum of mean value differences for offline RL) .

With probability at least $1-\delta$, we have

$$ $\displaystyle\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \left|\mathbb{E}_{s^{\prime}\sim P^{\star}(s,a)}V^{\pi^{\star}}_{h+1;\widehat{ P}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim\widehat{P}(s,a)}V^{\pi^{\star}}_{h+ 1;\widehat{P}}(s^{\prime})\right|\right]$ $\displaystyle\leq 8\sqrt{\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{ h}}\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{)} (s,a)\right]\cdot\frac{22C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)} {K}}+\frac{440C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)}{K}.$ $$

###### Proof of Lemma 15 .

We have

$$ $\displaystyle\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \left|\mathbb{E}_{s^{\prime}\sim P^{\star}(s,a)}V^{\pi^{\star}}_{h+1;\widehat{ P}}(s^{\prime})-\mathbb{E}_{s^{\prime}\sim\widehat{P}(s,a)}V^{\pi^{\star}}_{h+ 1;\widehat{P}}(s^{\prime})\right|\right]$ $\displaystyle\leq 4\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}} \left[\sqrt{\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big {)}(s,a)D_{\triangle}\Big{(}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{(}s^{\prime} \sim P^{\star}(s,a)\big{)}\mathrel{\|}V_{h+1;\widehat{P}}^{\pi^{\star}}(s^{ \prime}\sim\widehat{P}\big{(}s,a)\big{)}\Big{)}}\right]$ $\displaystyle\quad+5\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}} \left[D_{\triangle}\Big{(}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{(}s^{\prime} \sim P^{\star}(s,a)\big{)}\mathrel{\|}V_{h+1;\widehat{P}}^{\pi^{\star}}(s^{ \prime}\sim\widehat{P}\big{(}s,a)\big{)}\Big{)}\right]$ $\displaystyle\leq 8\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}} \left[\sqrt{\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big {)}(s,a)\mathbb{H}^{2}\Big{(}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{(}s^{\prime }\sim P^{\star}(s,a)\big{)}\mathrel{\|}V_{h+1;\widehat{P}}^{\pi^{\star}}(s^{ \prime}\sim\widehat{P}\big{(}s,a)\big{)}\Big{)}}\right]$ $\displaystyle\quad+20\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}} \left[\mathbb{H}^{2}\Big{(}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{(}s^{\prime} \sim P^{\star}(s,a)\big{)}\mathrel{\|}V_{h+1;\widehat{P}}^{\pi^{\star}}(s^{ \prime}\sim\widehat{P}\big{(}s,a)\big{)}\Big{)}\right]$ $\displaystyle\leq 8\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}} \left[\sqrt{\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big {)}(s,a)\mathbb{H}^{2}\Big{(}P^{\star}(s,a)\mathrel{\|}\widehat{P}\big{(}s,a) \Big{)}}\right]+20\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}} \left[\mathbb{H}^{2}\Big{(}P^{\star}(s,a)\mathrel{\|}\widehat{P}\big{(}s,a) \Big{)}\right]$ (59) $$

where in the first inequality, we use Lemma 1 to bound the difference of two means $\mathbb{E}_{s^{\prime}\sim P^{\star}(s,a)}V^{\pi^{\star}}_{h+1;\widehat{P}}(s^
{\prime})-\mathbb{E}_{s^{\prime}\sim\widehat{P}(s,a)}V^{\pi^{*}}_{h+1;\widehat
{P}}(s^{\prime})$ using variances and the triangle discrimination; in the second inequality we use the fact that that triangle discrimination is equivalent to squared Hellinger distance, i.e., $D_{\triangle}\leq 4\mathbb{H}^{2}$; the third inequality is via data processing inequality on the squared Hellinger distance. Next, starting from Equation 59, with probability at least $1-\delta$, we have

$$ $\displaystyle 8\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \sqrt{\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{)}(s, a)\mathbb{H}^{2}\Big{(}P^{\star}(s,a)\mathrel{\|}\widehat{P}\big{(}s,a)\Big{)} }\right]+20\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \mathbb{H}^{2}\Big{(}P^{\star}(s,a)\mathrel{\|}\widehat{P}\big{(}s,a)\Big{)}\right]$ $\displaystyle\leq 8\sqrt{\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{ h}}\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{)} (s,a)\right]\cdot\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left [\mathbb{H}^{2}\Big{(}P^{\star}(s,a)\mathrel{\|}\widehat{P}\big{(}s,a)\Big{)} \right]}$ $\displaystyle\quad+20\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}} \left[\mathbb{H}^{2}\Big{(}P^{\star}(s,a)\mathrel{\|}\widehat{P}\big{(}s,a) \Big{)}\right]$ $\displaystyle\leq 8\sqrt{\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{ h}}\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{)} (s,a)\right]\cdot C^{\pi^{\star}}\frac{1}{K}\sum_{k=1}^{K}\sum_{h=0}^{H-1} \mathbb{H}^{2}(P^{\star}(s_{h}^{k},a_{h}^{k})||\widehat{P}(s_{h}^{k},a_{h}^{k} ))}$ $\displaystyle\quad+20C^{\pi^{\star}}\frac{1}{K}\sum_{k=1}^{K}\sum_{h=0}^{H-1} \mathbb{H}^{2}(P^{\star}(s_{h}^{k},a_{h}^{k})||\widehat{P}(s_{h}^{k},a_{h}^{k}))$ $\displaystyle\leq 8\sqrt{\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{ h}}\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{)} (s,a)\right]\cdot\frac{22C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)} {K}}+\frac{440C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)}{K}\,,$ (60) $$

where the first inequality is by the Cauchy–Schwarz inequality; the second inequality is by the definition of single policy coverage (Definition 3); the last inequality holds with probability at least $1-\delta$ with Equation 56. Substituting Equation 60 into Equation 59 ends our proof.
∎

We denote $\mathcal{E}$ as the event that Lemma 15 holds. Under the event $\mathcal{E}$, we prove the following lemma to bound $\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[\big{(}\mathbb{V
}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{)}(s,a)\right]$ with $\widetilde{O}(\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{*}}_{h}}\left[\big{(
}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{*}}\big{)}(s,a)\right]+C^{\pi^{*}}\log(
\left|\mathcal{P}\right|/\delta)/{K}$).

###### Lemma 16 (Variance Conversion Lemma for offline RL) .

Under event $\mathcal{E}$, we have

$$ $\displaystyle\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{)}(s,a) \right]\leq O\Big{(}\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{*}}_{h}}\left[ \big{(}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{*}}\big{)}(s,a)\right]+C^{\pi^{*}} \frac{\log(\left|\mathcal{P}\right|/\delta)}{K}\Big{)}.$ $$

###### Proof of Lemma 16 .

For notational simplicity, we denote $A:=\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[\big{(}
\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{)}(s,a)\right]$, and we denote
$B:=\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[\big{(}
\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{\star}}\big{)}(s,a)\right]$, $C:=\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[\big{(}
\mathbb{V}_{P^{\star}}(V_{h+1;\widehat{P}}^{\pi^{\star}}-V_{h+1}^{\pi^{\star}}
)\big{)}(s,a)\right]$, then we have

$$ $\displaystyle A\leq 2B+2C,$ $$

since $\mathbb{V}_{P^{\star}}(a+b)\leq 2\mathbb{V}_{P^{\star}}(a)+2\mathbb{V}_{P^{
\star}}(b)$.

Let $\Delta_{h+1}^{\pi^{\star}}:=V_{h+1;\widehat{P}}^{\pi^{\star}}-V_{h+1}^{\pi^{
\star}}$. Then, w.p. at least $1-\delta$, we have

$$ $\displaystyle C$ $\displaystyle=\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \big{(}P^{\star}(\Delta_{h+1}^{\pi^{\star}})^{2}\big{)}(s,a)-\big{(}P^{\star} \Delta_{h+1}^{\pi^{\star}}\big{)}^{2}(s,a)\right]$ $\displaystyle=\sum_{h=0}^{H-1}\mathbb{E}_{s\sim d^{\pi^{\star}}_{h+1}}\left[( \Delta_{h+1}^{\pi^{\star}})^{2}(s)\right]-\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d ^{\pi^{\star}}_{h}}\left[\big{(}P^{\star}\Delta_{h+1}^{\pi^{\star}}\big{)}^{2} (s,a)\right]$ $\displaystyle\leq\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left [(\Delta_{h}^{\pi^{\star}})^{2}(s)-\big{(}P^{\star}\Delta_{h+1}^{\pi^{\star}} \big{)}^{2}(s,a)\right]$ $\displaystyle=\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \Big{(}(\Delta_{h}^{\pi^{\star}})(s)+\big{(}P^{\star}\Delta_{h+1}^{\pi^{\star} }\big{)}(s,a)\Big{)}\cdot\Big{(}(\Delta_{h}^{\pi^{\star}})(s)-\big{(}P^{\star} \Delta_{h+1}^{\pi^{\star}}\big{)}(s,a)\Big{)}\right],$ (61) $$

where the first equality is by the definition of variance, the second equality holds as $d^{\pi^{\star}}_{h}$ is the occupancy measure also generated under $P^{\star}$, the first inequality is just changing the index, the third equality holds as $a^{2}-b^{2}=(a+b)\cdot(a-b)$. Starting from Equation 61, we have

$$ $\displaystyle\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \Big{(}(\Delta_{h}^{\pi^{\star}})(s)+\big{(}P^{\star}\Delta_{h+1}^{\pi^{\star} }\big{)}(s,a)\Big{)}\cdot\Big{(}(\Delta_{h}^{\pi^{\star}})(s)-\big{(}P^{\star} \Delta_{h+1}^{\pi^{\star}}\big{)}(s,a)\Big{)}\right]$ $\displaystyle\leq 2\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}} \left[\left|(\Delta_{h}^{\pi^{\star}})(s)-\big{(}P^{\star}\Delta_{h+1}^{\pi^{ \star}}\big{)}(s,a)\right|\right]$ $\displaystyle=2\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \left|({V}_{h;\widehat{P}}^{\pi^{\star}})(s)-\big{(}P^{\star}{V}_{h+1;\widehat {P}}^{\pi^{\star}}\big{)}(s,a)-\Big{(}({V}_{h}^{\pi^{\star}})(s)-\big{(}P^{ \star}{V}_{h+1}^{\pi^{\star}}\big{)}(s,a)\Big{)}\right|\right]$ $\displaystyle=2\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \left|r(s,a)+\big{(}\widehat{P}{V}_{h+1;\widehat{P}}^{\pi^{\star}}\big{)}(s,a) -\big{(}P^{\star}{V}_{h+1;\widehat{P}}^{\pi^{\star}}\big{)}(s,a)-r(s,a)\right|\right]$ $\displaystyle=2\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \left|\big{(}\widehat{P}{V}_{h+1;\widehat{P}}^{\pi^{\star}}\big{)}(s,a)-\big{( }P^{\star}{V}_{h+1;\widehat{P}}^{\pi^{\star}}\big{)}(s,a)\right|\right],$ (62) $$

where the inequality holds as the value functions are all bounded by 1 by the assumption that the total reward over any trajectory is bounded by 1, the first equality is by the definition of $\Delta_{h+1}^{\pi^{\star}}$, the second equality is because $a$ is drawn from $\pi^{\star}$. Starting from Equation 62, we have

$$ $\displaystyle 2\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \left|\big{(}\widehat{P}{V}_{h+1;\widehat{P}}^{\pi^{\star}}\big{)}(s,a)-\big{( }P^{\star}{V}_{h+1;\widehat{P}}^{\pi^{\star}}\big{)}(s,a)\right|\right]$ $\displaystyle=2\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_{h}}\left[ \left|\mathbb{E}_{s^{\prime}\sim P^{\star}(s,a)}\left[V^{\pi^{\star}}_{h+1; \widehat{P}}(s^{\prime})\right]-\mathbb{E}_{s^{\prime}\sim\widehat{P}(\cdot|s, a)}\left[V^{\pi^{\star}}_{h+1;\widehat{P}}(s^{\prime})\right]\right|\right]$ $\displaystyle\leq 16\sqrt{\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star}}_ {h}}\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1;\widehat{P}}^{\pi^{\star}}\big{) }(s,a)\right]\cdot\frac{22C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta) }{K}}+\frac{880C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)}{K}$ $\displaystyle=16\sqrt{A\cdot\frac{22C^{\pi^{\star}}\log(\left|\mathcal{P} \right|/\delta)}{K}}+\frac{880C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/ \delta)}{K}$ (63) $$

where the inequality holds with probability at least $1-\delta$ by Lemma 15, and the second equality is by definition of $A$.

Then combining Equation 61, Equation 62 and Equation 63, we obtain an upper bound for $C$, which suggests

$$ $\displaystyle A$ $\displaystyle\leq 2B+2C$ $\displaystyle\leq 2B+\frac{1760C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/ \delta)}{K}+32\sqrt{\frac{22C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/ \delta)}{K}}\cdot\sqrt{A}.$ $$

Then, with the fact that $x\leq 2a+b^{2}$ if $x\leq a+b\sqrt{x}$, we have

$$ $\displaystyle A\leq 4B+\frac{3520C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/ \delta)}{K}+\frac{22528C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)}{K }\leq O(B+\frac{C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)}{K}).$ $$

∎

With the above lemmas, we can now prove the final results of Theorem 2. We have that w.p. at least $1-\delta$

$$ $\displaystyle V_{0;P^{\star}}^{\pi^{\star}}-V_{0;P^{\star}}^{\hat{\pi}}$ $\displaystyle\leq O\Big{(}\sqrt{A\cdot\frac{C^{\pi^{\star}}\log(\left|\mathcal {P}\right|/\delta)}{K}}+\frac{C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/ \delta)}{K}\Big{)}$ $\displaystyle\leq O\Big{(}\sqrt{(B+\frac{C^{\pi^{\star}}\log(\left|\mathcal{P} \right|/\delta)}{K})\cdot\frac{C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/ \delta)}{K}}+\frac{C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)}{K} \Big{)}$ $\displaystyle\leq O\Big{(}\sqrt{B\cdot\frac{C^{\pi^{\star}}\log(\left|\mathcal {P}\right|/\delta)}{K}}+\sqrt{\frac{C^{\pi^{\star}}\log(\left|\mathcal{P} \right|/\delta)}{K}\cdot\frac{C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/ \delta)}{K}}+\frac{C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)}{K} \Big{)}$ $\displaystyle=O\Big{(}\sqrt{\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{\star} }_{h}}\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{\star}}\big{)}(s,a) \right]\cdot\frac{C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)}{K}}+ \frac{C^{\pi^{\star}}\log(\left|\mathcal{P}\right|/\delta)}{K}\Big{)}$ (64) $\displaystyle=O\Big{(}\sqrt{\frac{\mathrm{VaR}_{\pi^{\star}}C^{\pi^{\star}} \log(\left|\mathcal{P}\right|/\delta)}{K}}+\frac{C^{\pi^{\star}}\log(\left| \mathcal{P}\right|/\delta)}{K}\Big{)}\,,$ $$

where in the last equation we use Lemma 8, and $\mathrm{VaR}_{\pi^{\star}}:=\mathbb{E}\left[\bigg{(}\sum_{h=0}^{H-1}r(s_{h},
\pi^{\star}(s_{h}))-V_{0}^{\pi^{\star}}\bigg{)}^{2}\right]$.
∎

###### Proof of Theorem 2 .

###### Lemma 15 (Bound of sum of mean value differences for offline RL) .

###### Proof of Lemma 15 .

###### Lemma 16 (Variance Conversion Lemma for offline RL) .

###### Proof of Lemma 16 .

### E.2 Proof of Corollary 4

###### Proof of Corollary 4 .

By Lemma 8, we have

$$ $\mathrm{VaR}_{\pi^{*}}=\sum_{h=0}^{H-1}\mathbb{E}_{s,a\sim d^{\pi^{*}}_{h}} \left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1}^{\pi^{*}}\big{)}(s,a)\right]$ (65) $$

Therefore, when $P^{\star}$ is deterministic,
the $\mathbb{E}_{s,a\sim d^{\pi^{*}}_{h}}\left[\big{(}\mathbb{V}_{P^{\star}}V_{h+1}
^{\pi^{*}}\big{)}(s,a)\right]$ terms are all 0 for any $k\in[K-1]$ and $h\in[H-1]$, and then the $\mathrm{VaR}_{\pi^{*}}$ term in the higher order term in Theorem 2 is 0.
∎

###### Proof of Corollary 4 .

### E.3 Proof of Corollary 5

###### Proof of Corollary 5 .

This claim follows the proof of Theorem 2, while we take a different choice of $\beta$ that depends on the bracketing number and follow the MLE guarantee in Lemma 10 for infinite model class.
∎

###### Proof of Corollary 5 .

### E.4 Proof of the claim in Example 2

###### Proof.

Recall that in Definition 3, we have

$$ $\displaystyle C^{\pi^{*}}_{\mathcal{D}}:=\max_{h,P\in\mathcal{P}}\frac{\mathbb {E}_{s,a\sim d^{\pi^{*}}_{h}}\mathbb{H}^{2}\left(P(s,a)\mathrel{\|}P^{\star}(s ,a)\right)}{1/K\sum_{k=1}^{K}\mathbb{H}^{2}\left(P(s_{h}^{k},a_{h}^{k}) \mathrel{\|}P^{\star}(s_{h}^{k},a_{h}^{k})\right)}\,.$ $$

For each step $h$, define two distributions, $p_{h},q_{h}$, where $p_{h}(s,a)=d^{\pi^{*}}(s,a)$, $q_{h}(s,a)=\frac{1}{K}\sum_{k=1}^{K}\mathbb{I}\{(s,a)=(s_{h}^{k},a_{h}^{k})\}$, and we define $f(s,a,P)=\mathbb{H}^{2}(P(s,a)\mathrel{\|}P^{\star}(s,a))$, then we have

$$ $\displaystyle C^{\pi^{*}}_{\mathcal{D}}$ $\displaystyle=\max_{h,P\in\mathcal{P}}\frac{\mathbb{E}_{s,a\sim p_{h}}f(s,a,P) }{\mathbb{E}_{s,a\sim q_{h}}f(s,a,P)}$ $\displaystyle=\max_{h,P\in\mathcal{P}}\frac{\mathbb{E}_{s,a\sim q_{h}}\frac{p_ {h}(s,a)}{q_{h}(s,a)}f(s,a,P)}{\mathbb{E}_{s,a\sim q_{h}}f(s,a,P)}$ $\displaystyle\leq\max_{h,s,a}\frac{p_{h}(s,a)}{q_{h}(s,a)}$ $\displaystyle\leq\max_{h,s,a}\frac{1}{q_{h}(s,a)}\,.$ (66) $$

Note that for all $h$, $\{(s_{h}^{k},a_{h}^{k})\}_{k=1}^{K}$ are i.i.d. samples drawn from $d_{h}^{\pi^{b}}$, therefore, $\mathbb{E}[\mathbb{I}\{(s_{h}^{k},a_{h}^{k})=(s,a)\}]=d^{\pi^{b}}_{h}(s,a)$. By Hoeffding’s inequality and with a union bound over $s,a,h$, and for $K\geq\frac{2\log(\frac{|{\mathcal{S}}||\mathcal{A}|H}{\delta})}{\rho_{\min}^{2}}$, w.p. at least $1-\delta$, we have

$$ $\displaystyle q_{h}(s,a)$ $\displaystyle=\frac{1}{K}\sum_{k=1}^{K}\mathbb{I}\{(s_{h}^{k},a_{h}^{k})=(s,a)\}$ $\displaystyle\geq d^{\pi^{b}}_{h}(s,a)-\sqrt{\frac{\log(\frac{|{\mathcal{S}}|| \mathcal{A}|H}{\delta})}{2K}}$ $\displaystyle\geq\frac{d^{\pi^{b}}_{h}(s,a)}{2}\,,$ (67) $$

where in the last inequality we use the assumption that $d^{\pi^{b}}_{h}(s,a)\geq\rho_{\min},\forall s,a,h$, which gives us $K\geq\frac{2\log(\frac{|{\mathcal{S}}||\mathcal{A}|H}{\delta})}{\rho_{\min}^{2
}}\geq\max_{s,a,h}\frac{2\log(\frac{|{\mathcal{S}}||\mathcal{A}|H}{\delta})}{(
d^{\pi^{b}}_{h}(s,a))^{2}}$, so $K\geq\frac{2\log(\frac{|{\mathcal{S}}||\mathcal{A}|H}{\delta})}{(d^{\pi^{b}}_{
h}(s,a))^{2}}$ for any $s,a,h$.

Therefore, with $K\geq\frac{2\log(\frac{|{\mathcal{S}}||\mathcal{A}|H}{\delta})}{\rho_{\min}^{2}}$, we have that w.p. at least $1-\delta$

$$ $\displaystyle C^{\pi^{*}}_{\mathcal{D}}$ $\displaystyle\leq\max_{h,s,a}\frac{1}{q_{h}(s,a)}\leq\max_{h,s,a}\frac{2}{d^{ \pi^{b}}_{h}(s,a)}\leq\frac{2}{\rho_{min}}\,.$ (68) $$

∎

###### Proof.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. As I have mentioned in (2) in weaknesses, can you compare your horizon-free results with [1,2]?

2. The paper discusses the use of MLE for transition modeling. How does this choice impact the trade-offs between computational efficiency and the accuracy of the learned model in comparison to other model learning techniques (e.g., Bayesian approaches)?

3. How does the use of MLE for model learning affect the sensitivity of the model to noise in the environment, particularly in settings where the transitions are stochastic or partially observable? Can the methodology be adapted to handle such cases without compromising the theoretical bounds?
soundness: 3
strengths: 1. The authors provide solid theoretical analysis.

2. The methodology stands out due to its simplicity. The authors focus on using standard techniques (MLE, version space, optimistic/pessimistic planning) without introducing complex or specialized methods.
summary: This paper proposes a minimalist approach to Model-Based Reinforcement Learning (RL) that leverages Maximum Likelihood Estimation (MLE) for learning transition models and integrates optimistic and pessimistic planning. The proposed scheme achieves strong regret and sample complexity bounds in both online and offline settings. It also provides nearly horizon-free and second-order bounds under certain conditions.
weaknesses: 1. While the paper mentions the simplicity and standard nature of the algorithm, it lacks a direct comparison with other recent state-of-the-art Model-Based RL methods. A more explicit comparison would help highlight the contributions and potential advantages of this approach.

2. While the paper emphasizes it provides a nearly horizon-free result, I do not think it is a novel contribution with the assumption $r(s_h, a_h) \in [0,1 / H]$. I am more interested in approaches of [1,2], which also remove $\log T$ in their regret bound. Can you compare your work with these two papers? 

3. The theoretical conclusions of this article are too dense and lack discussion.

References:

[1] Zhang, Zihan, Xiangyang Ji, and Simon Du. "Horizon-free reinforcement learning in polynomial time: the power of stationary policies." Conference on Learning Theory. PMLR, 2022. 

[2] Li, Shengshi, and Lin Yang. "Horizon-free learning for Markov decision processes and games: stochastically bounded rewards and improved bounds." International Conference on Machine Learning. PMLR, 2023.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Given that the current approach is theoretically sound but may be computationally intense, are there approximate methods that could retain accuracy while reducing computational demands?

2. What are the implications if the assumed model class does not include the true dynamics of the environment? Could the algorithm's performance degrade, and if so, how might this be mitigated?
soundness: 3
strengths: 1. The theoretical results show that performance does not heavily depend on the planning horizon, making this approach comparable to contextual bandits in complexity. The second-order bounds, scaling with policy variance, are particularly advantageous for nearly deterministic systems or policies with low variance.

2. The approach is designed to be versatile, working effectively in online, offline, and hybrid settings.
summary: This paper presents a minimalist model-based RL approach focused on achieving horizon-free and second-order bounds in both online and offline RL contexts. The authors advocate for using MLE for transition model learning, combined with optimistic planning in online RL and pessimistic planning in offline RL. The primary theoretical contribution is demonstrating that this straightforward MLE-based approach, which doesn’t require complex, variance-weighted learning procedures, achieves near-horizon-free sample complexity and second-order regret bounds. The analysis shows that this approach is effective in handling scenarios with either non-linear function approximations or time-homogeneous, low-variance policies, which benefit from the instance-dependent nature of second-order bounds.
weaknesses: 1. While the approach is theoretically sound, its reliance on computationally intensive MLE optimization could hinder scalability for larger or more complex model classes. To address this, it may be valuable to explore specific approximate MLE methods, such as variational inference or stochastic optimization. Alternatively, a discussion of computational complexity trade-offs could provide further clarity and practical guidance.

2. The paper presents strong theoretical contributions, but the lack of empirical validation on challenging RL tasks limits its practical impact. It would be helpful to evaluate the approach to environments such as tabular MDPs. Including such experiments would significantly strengthen the paper’s practical contributions.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Are the assumptions listed on page 4 and in Definition 3 the only ones required for Theorem 2? I’m curious about this, as I would like to gain a better understanding of the factors contributing to the improved results compared to [1].

2. What do you think is the key barrier when attempting to apply a similar analysis to model-free methods? This question is not necessary to be replied.

[1] Uehara, M., & Sun, W. (2021). Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226.
soundness: 3
strengths: This paper explores horizon-free reinforcement learning (RL) within the context of general function approximations, which is a more challenging and generalized setting compared to prior work on tabular or linear MDPs. Theoretical analysis is solid, leveraging triangular discrimination to demonstrate that existing standard model-based algorithms can already achieve horizon-free regret. This analysis could be inspiring for future research in horizon-free RL. Furthermore, the paper provides a second-order instance-dependent upper bound, which can be particularly tight when the variance is low, yielding improved sample complexity in deterministic environments. Finally, the writing is logical, with ideas presented smoothly.
summary: This paper identifies minimalist reinforcement learning (RL) algorithms that can achieve nearly horizon-free and instance-dependent regret and sample complexity bounds,in both online and offline RL with non-linear function approximation. Based on a leverage of triangular discrimination, it demonstrates that existing standard model-based RL algorithms, using maximum likelihood estimation (MLE) for model learning and optimistic or pessimistic planning depending on the setting (online or offline), are sufficient to achieve these performance goals.
weaknesses: It's clear that this paper is purely focused on theoretical contributions. I think the primary weakness is the lack of intuitive insight into how triangular discrimination specifically assists in achieving horizon-free and second-order upper bounds. Although a proof sketch is provided, the underlying intuition remains somewhat unclear. A discussion on this would be appreciated.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. See clarification questions above
2. The bound in Example 1 for tabular MDPs seems to have a worse dependence in SA that existing bounds for the same setting (see eg Jin et al. 2020 or Appendix C in Al-Marjani et al. 2023) despite having a better dependence in H. Any intuition why this happens?

[Jin et al. 2020] Jin, C., Krishnamurthy, A., Simchowitz, M., & Yu, T. (2020, November). Reward-free exploration for reinforcement learning. In International Conference on Machine Learning (pp. 4870-4879). PMLR.
[Al-Marjani et al. 2023] Al-Marjani, A., Tirinzoni, A., & Kaufmann, E. (2023, July). Active coverage for pac reinforcement learning. In The Thirty Sixth Annual Conference on Learning Theory (pp. 5044-5109). PMLR.
soundness: 3
strengths: 1. The paper presents novel and strong results. To my knowledge, the ones studied here are the simplest algorithms to be shown to achieve both horizon-free and second-order bounds (eg, most prior works required specific algorithmic tweaks to this purpose). Due to the popularity of MLE-based approaches, I think this is a relevant result
2. The paper studies both the online and offline RL settings
3. I particularly appreciated the corollaries for MDPs with deterministic transition kernel, which I think is an understudied setting despite its practical relevance
4. Although I only skimmed through the proofs, they do seem sound
5. Relevant literature is properly discussed
summary: The paper studies model-based RL in MDPs with possibly infinite state-action spaces and total returns bounded in [0,1]. The authors show that a simple approach consisting of learning a version space around the MLE of the transition kernel and performing optimistic/pessimistic planning on top of it achieves strong horizon-free and second-order bounds in online/offline RL.
weaknesses: 1. My main concern is that the paper is quite hard to follow, extremely technical, and lacks some clarity in many points. More precisely, the paper is basically a list of theorems/lemmas/corollaries/definitions without too many explanations: several terms that may only be familiar to experts in this line of works are not introduced with sufficient detail and many choices are not motivated. For example,
- it is not clear why the assumption that trajectory returns are in [0,1] is reasonable in practice
- for offline RL, it is not clear why the assumption that the dataset contains trajectories is needed (lines 181-191). Can't you have only transitions?
- the definition of Eluder dimension is not clear (eg what's an epsilon-independent sequence?). It is clearer in prior works
- not clear why the bounds use the function class \Psi defined at lines 258-259. Eg, why not using P itself, which after all is the hypothesis space used for learning?
- In Section 4, it is never explicitly stated that the results before the paragraph "Extension to infinite class P" focus on finite P (the reader has to figure it out from the definition of beta)
- not clear why using bracketing numbers in the analysis. Eg how do they compare to the more standard covering numbers (if there is any difference)? Also, it be great to give examples of what those are for "common" function classes (eg when P is linear)
- not clear how the "single-policy coverage" of Def. 3 compares to the more standard concentrability coefficients defined as ratios between policy visitation distributions used in the offline RL literature
2. The algorithms studied here are both intractable due to the fact that they have to build a version space of transition kernels around the MLE. This is only tractable for simple function classes (eg finite) and limits the practical relevance of this work. Also, I feel this breaks a bit the overall story about the "simplicity" of the approaches. Eg, the conclusions state "we presented a minimalist approach for achieving nearly horizon-free and second-order bounds in online and offline RL: simply train transition models via Maximum Likelihood Estimation followed by optimistic or pessimistic planning", but I don't think this is properly correct: it gives the impression that all we have to do is MLE, but we do have to build version spaces around it, and that's not an easy thing.
3. Lines 171-172: "Without loss of generality, we assume V \in [0,1]". I don't think this is without loss of generality, as the filtering approach proposed in footnote 2 would require doing policy-evaluation for many policies and transition kernels, which is what we want to avoid during training in the first place with an MLE approach
4. [minor] the abstract is very verbose, and I felt many details could have been omitted without altering its quality

Meta-review: Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds 

Summary: The paper introduces a minimalist approach to model-based reinforcement learning (MBRL) that combines Maximum Likelihood Estimation (MLE) for transition modeling with optimistic and pessimistic planning, tailored for online and offline RL settings. It emphasizes achieving nearly horizon-free and second-order regret bounds, offering statistical efficiency akin to contextual bandits. This is achieved without the need for new algorithms but by leveraging triangular discrimination techniques. The work also explores performance improvements under deterministic transitions and proposes bounds for finite and infinite model classes using Eluder dimension and bracketing numbers.

Comments: We received 4 expert reviews, with the scores 6, 6, 8, 8, and the average score is 7.0. The reviewers are positive about the technical contributions of this paper. They appreciated the simplicity of the approach, of leveraging existing model-based RL methods, using Maximum Likelihood Estimation (MLE) and standard planning techniques, to achieve strong theoretical guarantees. I also believe that this is a valuable result for the RL community. The technical contribution in establishing a nearly horizon-free and variance-sensitive regret bound is also original and important. The paper is also well-written. 

The reviewers have also provided multiple comments to strengthen the paper. This includes more comparisons with some specific related works and providing more explanation of the true practicality of implementing the MLE-based approach (line 5 in the algorithm). I recommend the authors update the paper by accommodating these suggestions.

Decision: Accept (Poster)