Is Pessimism Provably Efficient for Offline RL?

Introduction

The empirical success of online (deep) reinforcement learning (RL) (Mnih et al. 2015; Silver et al. 2016; Silver et al. 2017; Vinyals et al. 2017) relies on two ingredients: (i) expressive function approximators, e.g., deep neural networks (LeCun et al. 2015), which approximate policies and values, and (ii) efficient data generators, e.g., game engines (Bellemare et al. 2013) and physics simulators (Todorov et al. 2012), which serve as environments. In particular, learning the deep neural network in an online manner often necessitates millions to billions of interactions with the environment. Due to such a barrier of sample complexity, it remains notably more challenging to apply online RL in critical domains, e.g., precision medicine (Gottesman et al. 2019) and autonomous driving (Shalev-Shwartz et al. 2016), where interactive data collecting processes can be costly and risky. To this end, we study offline RL in this paper, which aims to learn an optimal policy based on a dataset collected a priori without further interactions with the environment. Such datasets are abundantly available in various domains, e.g., electronic health records for precision medicine (Chakraborty and Murphy 2014) and human driving trajectories for autonomous driving (Sun et al. 2020).

In comparison with online RL (Lattimore and Szepesvári 2020; Agarwal et al. 2020a), offline RL remains even less understood in theory (Lange et al. 2012; Levine et al. 2020), which hinders principled developments of trustworthy algorithms in practice. In particular, as active interactions with the environment are infeasible, it remains unclear how to maximally exploit the dataset without further exploration. Due to such a lack of continuing exploration, which plays a key role in online RL, any algorithm for offline RL possibly suffers from the insufficient coverage of the dataset (Wang et al. 2020a). Specifically, as illustrated in Section 3, two challenges arise:

the intrinsic uncertainty, that is, the dataset possibly fails to cover the trajectory induced by the optimal policy, which however carries the essential information, and

the spurious correlation, that is, the dataset possibly happens to cover a trajectory unrelated to the optimal policy, which by chance induces a large cumulative reward and hence misleads the learned policy.

See Figures 1 and 2 for illustrations. As the dataset is collected a priori, which is often beyond the control of the learner, any assumption on the sufficient coverage of the dataset possibly fails to hold in practice (Fujimoto et al. 2019; Agarwal et al. 2020b; Fu et al. 2020a; Gulcehre et al. 2020).

In this paper, we aim to answer the following question:

Is it possible to design a provably efficient algorithm for offline RL under minimal assumptions on the dataset?

To this end, we propose a pessimistic value iteration algorithm (PEVI), which incorporates a penalty function (pessimism) into the value iteration algorithm (Sutton and Barto 2018; Szepesvári 2010). Here the penalty function simply flips the sign of the bonus function (optimism) for promoting exploration in online RL (Jaksch et al. 2010; Azar et al. 2017), which enables a straightforward implementation of PEVI in practice. Specifically, we study the episodic setting of the Markov decision process (MDP). Our theoretical contribution is fourfold:

We decompose the suboptimality of any algorithm for offline RL into three sources, namely the intrinsic uncertainty, spurious correlation, and optimization error. In particular, we identify the key role of the spurious correlation, even in the multi-armed bandit (MAB), a special case of the MDP.

For any general MDP, we establish the suboptimality of PEVI under a sufficient condition on the penalty function. In particular, we prove as long as the penalty function is an uncertainty quantifier, which is defined in Section 4.1, pessimism allows PEVI to eliminate the spurious correlation from its suboptimality.

For the linear MDP (Yang and Wang 2019; Jin et al. 2020), we instantiate PEVI by specifying the penalty function. In particular, we prove such a penalty function is an uncertainty quantifier, which verifies the sufficient condition imposed in (ii). Correspondingly, we establish the suboptimality of PEVI for the linear MDP.

We prove PEVI is minimax optimal for the linear MDP up to multiplicative factors of the dimension and horizon. In particular, we prove the intrinsic uncertainty identified in (i) is impossible to eliminate, as it arises from the information-theoretic lower bound. Moreover, such a fundamental limit certifies an oracle property of PEVI, which is defined in Section 4.2. Specifically, the suboptimality of PEVI only depends on how well the dataset covers the trajectory induced by the optimal policy, which carries the essential information, rather than any trajectory unrelated to the optimal policy, which causes the spurious correlation.

Throughout our theory, we only require an assumption on the compliance of the dataset, that is, the data collecting process is carried out in the underlying MDP of interest. Such an assumption is minimal. In comparison with existing literature, we require no assumptions on the sufficient coverage of the dataset, e.g., finite concentrability coefficients (Chen and Jiang 2019) and uniformly lower bounded densities of visitation measures (Yin et al. 2020), which often fail to hold in practice. Meanwhile, we impose no restrictions on the affinity between the learned policy and behavior policy (for collecting data) (Liu et al. 2020), which is often employed as a regularizer (or equivalently, a constraint) in existing literature. See Section 1.1 for a detailed discussion.

Our work adds to the vast body of existing literature on offline RL (also known as batch RL) (Lange et al. 2012; Levine et al. 2020), where a learner only has access to a dataset collected a priori. Existing literature studies two tasks: (i) offline policy evaluation, which estimates the expected cumulative reward or (action- and state-) value functions of a target policy, and (ii) offline policy optimization, which learns an optimal policy that maximizes the expected cumulative reward. Note that (i) is also known as off-policy policy evaluation, which can be adapted to handle the online setting. Also, note that the target policy in (i) is known, while the optimal policy in (ii) is unknown. As (ii) is more challenging than (i), various algorithms for solving (ii), especially the value-based approaches, can be adapted to solve (i). Although we focus on (ii), we discuss the existing works on (i) and (ii) together.

A key challenge of offline RL is the insufficient coverage of the dataset (Wang et al. 2020a), which arises from the lack of continuing exploration (Szepesvári 2010). In particular, the trajectories given in the dataset and those induced by the optimal policy (or the target policy) possibly have different distributions, which is also known as distribution shift (Levine et al. 2020). As a result, intertwined with overparameterized function approximators, e.g., deep neural networks, offline RL possibly suffers from the extrapolation error (Fujimoto et al. 2019), which is large on the states and actions that are less covered by the dataset. Such an extrapolation error further propagates through each iteration of the algorithm for offline RL, as it often relies on bootstrapping (Sutton and Barto 2018).

To address such a challenge, the recent works (Fujimoto et al. 2019; Laroche et al. 2019; Jaques et al. 2019; Wu et al. 2019; Kumar et al. 2019; Kumar et al. 2020; Agarwal et al. 2020b; Yu et al. 2020; Kidambi et al. 2020; Wang et al. 2020c; Siegel et al. 2020; Nair et al. 2020; Liu et al. 2020) demonstrate the empirical success of various algorithms, which fall into two (possibly overlapping) categories: (i) regularized policy-based approaches and (ii) pessimistic value-based approaches. Specifically, (i) regularizes (or equivalently, constrains) the policy to avoid visiting the states and actions that are less covered by the dataset, while (ii) penalizes the (action- or state-) value function on such states and actions.

On the other hand, the empirical success of offline RL mostly eludes existing theory. Specifically, the existing works require various assumptions on the sufficient coverage of the dataset, which is also known as data diversity (Levine et al. 2020). For example, offline policy evaluation often requires the visitation measure of the behavior policy to be lower bounded uniformly over the state-action space. An alternative assumption requires the ratio between the visitation measure of the target policy and that of the behavior policy to be upper bounded uniformly over the state-action space. See, e.g., Jiang and Li 2016; Thomas and Brunskill 2016; Farajtabar et al. 2018; Liu et al. 2018; Xie et al. 2019; Nachum et al. 2019a; Nachum et al. 2019b; Tang et al. 2019; Kallus and Uehara 2019; Kallus and Uehara 2020; Jiang and Huang 2020; Uehara et al. 2020; Duan et al. 2020; Yin and Wang 2020; Yin et al. 2020; Nachum and Dai 2020; Yang et al. 2020a; Zhang et al. 2020b and the references therein. As another example, offline policy optimization often requires the concentrability coefficient to be upper bounded, whose definition mostly involves taking the supremum of a similarly defined ratio over the state-action space. See, e.g., Antos et al. 2007; Antos et al. 2008; Munos and Szepesvári 2008; Farahmand et al. 2010; Farahmand et al. 2016; Scherrer et al. 2015; Chen and Jiang 2019; Liu et al. 2019; Wang et al. 2019; Fu et al. 2020b; Fan et al. 2020; Xie and Jiang 2020a; Xie and Jiang 2020b; Liao et al. 2020; Zhang et al. 2020a and the references therein.

In practice, such assumptions on the sufficient coverage of the dataset often fail to hold (Fujimoto et al. 2019; Agarwal et al. 2020b; Fu et al. 2020a; Gulcehre et al. 2020), which possibly invalidates existing theory. For example, even for the MAB, a special case of the MDP, it remains unclear how to maximally exploit the dataset without such assumptions, e.g., when each action (arm) is taken a different number of times. As illustrated in Section 3, assuming there exists a suboptimal action that is less covered by the dataset, it possibly interferes with the learned policy via the spurious correlation. As a result, it remains unclear how to learn a policy whose suboptimality only depends on how well the dataset covers the optimal action instead of the suboptimal ones. In contrast, our work proves that pessimism resolves such a challenge by eliminating the spurious correlation, which enables exploiting the essential information, e.g., the observations of the optimal action in the dataset, in a minimax optimal manner. Although the optimal action is unknown, our algorithm adapts to identify the essential information in the dataset via the oracle property. See Section 4 for a detailed discussion.

Our work adds to the recent works on pessimism (Yu et al. 2020; Kidambi et al. 2020; Kumar et al. 2020; Liu et al. 2020; Buckman et al. 2020). Specifically, Yu et al. 2020; Kidambi et al. 2020 propose a pessimistic model-based approach, while Kumar et al. 2020 propose a pessimistic value-based approach, both of which demonstrate empirical successes. From a theoretical perspective, Liu et al. 2020 propose a regularized (and pessimistic) variant of the fitted Q-iteration algorithm (Antos et al. 2007; Antos et al. 2008; Munos and Szepesvári 2008), which attains the optimal policy within a restricted class of policies without assuming the sufficient coverage of the dataset. In contrast, our work imposes no restrictions on the affinity between the learned policy and behavior policy. In particular, our algorithm attains the information-theoretic lower bound for the linear MDP (Yang and Wang 2019; Jin et al. 2020) (up to multiplicative factors of the dimension and horizon), which implies that given the dataset, the learned policy serves as the “best effort” among all policies since no other can do better. From another theoretical perspective, Buckman et al. 2020 characterize the importance of pessimism, especially when the assumption on the sufficient coverage of the dataset fails to hold. In contrast, we propose a principled framework for achieving pessimism via the notion of uncertainty quantifier, which serves as a sufficient condition for general function approximators. See Section 4 for a detailed discussion. Moreover, we instantiate such a framework for the linear MDP and establish its minimax optimality via the information-theoretic lower bound. In other words, our work complements Buckman et al. 2020 by proving that pessimism is not only “important” but also optimal in the sense of information theory.

Preliminaries

In this section, we first introduce the episodic Markov decision process (MDP) and the corresponding performance metric. Then we introduce the offline setting and the corresponding data collecting process.

and the Bellman operator at each step $h\in[H]$ as

For the episodic MDP $({\mathcal{S}},\mathcal{A},H,\mathcal{P},r)$, we use $\pi^{*}$, $Q_{h}^{*}$, and $V_{h}^{*}$ to denote the optimal policy, optimal Q-function, and optimal value function, respectively. We have $V_{H+1}^{*}=0$ and the Bellman optimality equation

Meanwhile, the optimal policy $\pi^{*}$ is specified by

where the maximum is taken over all functions mapping from ${\mathcal{S}}$ to distributions over $\mathcal{A}$. We aim to learn a policy that maximizes the expected cumulative reward. Correspondingly, we define the performance metric as

which is the suboptimality of the policy $\pi$ given the initial state $s_{1}=x$.

2 Offline Data Collecting Process

We consider the offline setting, that is, a learner only has access to a dataset $\mathcal{D}$ consisting of $K$ trajectories $\{(x_{h}^{\tau},a_{h}^{\tau},r_{h}^{\tau})\}_{\tau,h=1}^{K,H}$, which is collected a priori by an experimenter. In other words, at each step $h\in[H]$ of each trajectory $\tau\in[K]$, the experimenter takes the action $a_{h}^{\tau}$ at the state $x_{h}^{\tau}$, receives the reward $r_{h}^{\tau}=r_{h}(x_{h}^{\tau},a_{h}^{\tau})$, and observes the next state $x_{h+1}^{\tau}\sim\mathcal{P}_{h}(\cdot{\,|\,}s_{h}=x_{h}^{\tau},a_{h}=a_{h}^{\tau})$. Here $a_{h}^{\tau}$ can be arbitrarily chosen, while $r_{h}$ and $\mathcal{P}_{h}$ are the reward function and transition kernel of an underlying MDP. We define the compliance of such a dataset with the underlying MDP as follows.

The dataset $\mathcal{D}$ that the learner has access to is compliant with the underlying MDP $({\mathcal{S}},\mathcal{A},H,\mathcal{P},r)$.

As a special case, Assumption 2.2 holds if the experimenter follows a fixed behavior policy. More generally, Assumption 2.2 allows $a_{h}^{\tau}$ to be arbitrarily chosen, even in an adaptive or adversarial manner, in the sense that the experimenter does not necessarily follow a fixed behavior policy. In particular, $a_{h}^{\tau}$ can be interdependent across each trajectory $\tau\in[K]$. For example, the experimenter can sequentially improve the behavior policy using any algorithm for online RL. Furthermore, Assumption 2.2 does not require the data collecting process to well explore the state space and action space.

What Causes Suboptimality?

In this section, we decompose the suboptimality of any policy into three sources, namely the spurious correlation, intrinsic uncertainty, and optimization error. We first analyze the MDP and then specialize the general analysis to the multi-armed bandit (MAB) for illustration.

Let $\widehat{\pi}=\{\widehat{\pi}_{h}\}_{h=1}^{H}$ be the policy such that $\widehat{V}_{h}(x)=\langle\widehat{Q}_{h}(x,\cdot),\widehat{\pi}_{h}(\cdot{\,|\,}x)\rangle_{\mathcal{A}}$. For any $\widehat{\pi}$ and $x\in{\mathcal{S}}$, we have

2 Illustration via a Special Case: MAB

We consider the MAB, a special case of the MDP, where ${\mathcal{S}}$ is a singleton, $\mathcal{A}$ is discrete, and $H=1$. To simplify the subsequent discussion, we assume without loss of generality

Here $\mu(a)$ is the expected reward of each action $a\in\mathcal{A}$ and $\epsilon$ is independently drawn. For notational simplicity, we omit the dependency on $h\in[H]$ and $x\in{\mathcal{S}}$, as $H=1$ and ${\mathcal{S}}$ is a singleton. Based on the dataset $\mathcal{D}=\{(a^{\tau},r^{\tau})\}_{\tau=1}^{K}$, where $r^{\tau}=r(a^{\tau})$, we consider the sample average estimator

Note that $\widehat{\mu}$ serves as the estimated Q-function. Under Assumption 2.2, we have

In particular, $\{\widehat{\mu}(a)\}_{a\in\mathcal{A}}$ are independent across each action $a\in\mathcal{A}$ conditioning on $\{a^{\tau}\}_{\tau=1}^{K}$. We consider the policy

which is greedy with respect to $\widehat{\mu}$, as it takes the action $\mathop{\text{\rm arg\,max}}_{a\in\mathcal{A}}\widehat{\mu}(a)$ with probability one.

By Equation (3.1), Lemma 3.1, and Equation (3.4), we have

For example, assuming $\mu(a)=0$ for each action $a\in\mathcal{A}$, term (i) is the maximum of $|\mathcal{A}|$ Gaussians $\{\text{N}(0,1/N(a))\}_{a\in\mathcal{A}}$, which can be rather large in expectation, especially when $N(a^{\sharp})$ is relatively small for a certain action $a^{\sharp}\in\mathcal{A}$, e.g., $N(a^{\sharp})=1$. More generally, it is quite possible that $\widehat{\pi}$ takes a certain action $a^{\natural}\in\mathcal{A}$ with probability one only because $N(a^{\natural})$ is relatively small, which allows $\widehat{\mu}(a^{\natural})$ to be rather large, even when $\mu(a^{\natural})$ is relatively small. Due to such a spurious correlation, $\langle\widehat{\mu}(\cdot)-\mu(\cdot),\widehat{\pi}(\cdot)\rangle_{\mathcal{A}}=\widehat{\mu}(a^{\natural})-\mu(a^{\natural})$ in Equation (3.5) can be rather large in expectation, which incurs a significant suboptimality. More importantly, such an undesired situation can be quite common in practice, as $\mathcal{D}$ does not necessarily have a “uniform coverage” over each action $a\in\mathcal{A}$. In other words, $N(a^{\sharp})$ is often relatively small for at least a certain action $a^{\sharp}\in\mathcal{A}$.

Going beyond the MAB, that is, $H\geq 1$, such a spurious correlation is further exacerbated, as it is more challenging to ensure each state $x\in{\mathcal{S}}$ and each action $a\in\mathcal{A}$ are visited sufficiently many times in $\mathcal{D}$. To this end, existing literature (Antos et al. 2007; Antos et al. 2008; Munos and Szepesvári 2008; Farahmand et al. 2010; Farahmand et al. 2016; Scherrer et al. 2015; Liu et al. 2018; Nachum et al. 2019a; Nachum et al. 2019b; Chen and Jiang 2019; Tang et al. 2019; Kallus and Uehara 2019; Kallus and Uehara 2020; Fan et al. 2020; Xie and Jiang 2020a; Xie and Jiang 2020b; Jiang and Huang 2020; Uehara et al. 2020; Duan et al. 2020; Yin et al. 2020; Qu and Wierman 2020; Li et al. 2020; Liao et al. 2020; Nachum and Dai 2020; Yang et al. 2020a; Zhang et al. 2020a; Zhang et al. 2020b) relies on various assumptions on the “uniform coverage” of $\mathcal{D}$, e.g., finite concentrability coefficients and uniformly lower bounded densities of visitation measures, which however often fail to hold in practice.

Pessimism is Provably Efficient

In this section, we present the algorithm and theory. Specifically, we introduce a penalty function to develop a pessimistic value iteration algorithm (PEVI), which simply flips the sign of the bonus function for promoting exploration in online RL (Jaksch et al. 2010; Abbasi-Yadkori et al. 2011; Russo and Van Roy 2013; Osband and Van Roy 2014; Chowdhury and Gopalan 2017; Azar et al. 2017; Jin et al. 2018; Jin et al. 2020; Cai et al. 2020; Yang et al. 2020b; Ayoub et al. 2020; Wang et al. 2020b). In Section 4.1, we provide a sufficient condition for eliminating the spurious correlation from the suboptimality for any general MDP. In Section 4.2, we characterize the suboptimality for the linear MDP (Yang and Wang 2019; Jin et al. 2020) by verifying the sufficient condition in Section 4.1. In Section 4.3, we establish the minimax optimality of PEVI via the information-theoretic lower bound.

The following theorem characterizes the suboptimality of Algorithm 1, which is defined in Equation (2.6).

Theorem 4.2 establishes a sufficient condition for eliminating the spurious correlation, which corresponds to term (i) in Equation (3.2), from the suboptimality for any general MDP. Specifically, $-\Gamma_{h}$ in Algorithm 1 serves as the penalty function, which ensures $-\iota_{h}$ in Equation (3.2) is nonpositive under $\mathcal{E}$ defined in Equation (4.1), that is,

Note that Equation (4.1) holds in a pointwise manner for all $(x,a)\in{\mathcal{S}}\times\mathcal{A}$. In other words, as long as $\Gamma_{h}$ is a $\xi$-uncertainty quantifier, the suboptimality in Equation (4.2) only corresponds to term (ii) in Equation (3.2), which characterizes the intrinsic uncertainty. In any concrete setting, e.g., the linear MDP, it only remains to specify $\Gamma_{h}$ and prove it is a $\xi$-uncertainty quantifier under Assumption 2.2. In particular, we aim to find a $\xi$-uncertainty quantifier that is sufficiently small to establish an adequately tight upper bound of the suboptimality in Equation (4.2). In the sequel, we show it suffices to employ the bonus function for promoting exploration in online RL.

2 Pessimistic Value Iteration: Linear MDP

As a concrete setting, we study the instantiation of PEVI for the linear MDP. We define the linear MDP (Yang and Wang 2019; Jin et al. 2020) as follows, where the transition kernel and expected reward function are linear in a feature map.

at each step $h\in[H]$. Correspondingly, we set

at each step $h\in[H]$. Here $\lambda>0$ is the regularization parameter. Note that $\widehat{w}_{h}$ has the closed form

Meanwhile, we construct $\Gamma_{h}$ based on $\mathcal{D}$ as

at each step $h\in[H]$. Here $\beta>0$ is the scaling parameter. In addition, we construct $\widehat{V}_{h}$ based on $\mathcal{D}$ as

The following theorem characterizes the suboptimality of Algorithm 2, which is defined in Equation (2.6).

Suppose Assumption 2.2 holds and the underlying MDP is a linear MDP. In Algorithm 2, we set As a side note, the factor $d$ in $B$ can be improved with a sample splitting trick; we apply this trick and defer the corresponding discussion to the kernel setting in Section 4.4.

We highlight the following aspects of Theorem 4.4:

“Assumption-Free” Guarantee: Theorem 4.4 only relies on the compliance of $\mathcal{D}$ with the linear MDP. In comparison with existing literature (Antos et al. 2007; Antos et al. 2008; Munos and Szepesvári 2008; Farahmand et al. 2010; Farahmand et al. 2016; Scherrer et al. 2015; Liu et al. 2018; Nachum et al. 2019a; Nachum et al. 2019b; Chen and Jiang 2019; Tang et al. 2019; Kallus and Uehara 2019; Kallus and Uehara 2020; Fan et al. 2020; Xie and Jiang 2020a; Xie and Jiang 2020b; Jiang and Huang 2020; Uehara et al. 2020; Duan et al. 2020; Yin et al. 2020; Qu and Wierman 2020; Li et al. 2020; Liao et al. 2020; Nachum and Dai 2020; Yang et al. 2020a; Zhang et al. 2020a; Zhang et al. 2020b), we require no assumptions on the “uniform coverage” of $\mathcal{D}$, e.g., finite concentrability coefficients and uniformly lower bounded densities of visitation measures, which often fail to hold in practice. Meanwhile, we impose no restrictions on the affinity between $\texttt{Pess}(\mathcal{D})$ and a fixed behavior policy that induces $\mathcal{D}$, which is often employed as a regularizer (or equivalently, a constraint) in existing literature (Fujimoto et al. 2019; Laroche et al. 2019; Jaques et al. 2019; Wu et al. 2019; Kumar et al. 2019; Wang et al. 2020c; Siegel et al. 2020; Nair et al. 2020; Liu et al. 2020).

The following corollary proves as long as the trajectory induced by $\pi^{*}$ is “covered” by $\mathcal{D}$ sufficiently well, the suboptimality of Algorithm 2 decays at a $K^{-1/2}$ rate.

Suppose there exists an absolute constant $c^{\dagger}>0$ such that the event

Here $c>0$ is an absolute constant and $\xi\in(0,1)$ is the confidence parameter. For $\texttt{Pess}(\mathcal{D})$ in Algorithm 2, the event

for $\texttt{Pess}(\mathcal{D})$ in Algorithm 2, the event

where $\widehat{w}_{h}$ and $\Lambda_{h}$ are defined in Equation (4.2). Correspondingly, we have

Here I is the (conditional) mutual information and H is the (conditional) differential entropy. Meanwhile, we have

where the second equality follows from the matrix determinant lemma and the last equality holds when $\phi(s_{h},a_{h})^{\top}\Lambda_{h}^{-1}\phi(s_{h},a_{h})$ is close to zero. Therefore, in Equation (4.8), we have

In other words, the suboptimality in Equation (4.8), which corresponds to the intrinsic uncertainty, can be cast as the mutual information between $w_{h}{\,|\,}\mathcal{D}$ in Equation (4.12) and $\phi(s_{h},a_{h})$ on the trajectory induced by $\pi^{*}$ in the underlying MDP. In particular, such a mutual information can be cast as the information gain (Schmidhuber 1991; Schmidhuber 2010; Sun et al. 2011; Still and Precup 2012; Houthooft et al. 2016; Russo and Van Roy 2016; Russo and Van Roy 2018) for estimating $w_{h}$, which is induced by observing $\phi(s_{h},a_{h})$ in addition to $\mathcal{D}$. In other words, such a mutual information characterizes how much uncertainty in $w_{h}{\,|\,}\mathcal{D}$ can be eliminated when we additionally condition on $\phi(s_{h},a_{h})$.

To simplify the subsequent discussion, we assume $\mathcal{P}_{h}$ is deterministic at each step $h\in[H]$. Let $\{(s_{h}^{*},a_{h}^{*})\}_{h=1}^{H}$ be the trajectory induced by $\pi^{*}$, which is also deterministic. In Equation (4.8), we have

In other words, the suboptimality in Equation (4.8) only depends on how well $\mathcal{D}$ “covers” the trajectory induced by $\pi^{*}$ instead of its “uniform coverage” over ${\mathcal{S}}$ and $\mathcal{A}$. In particular, as long as $(s_{h}^{\diamond},a_{h}^{\diamond})$ lies off the trajectory induced by $\pi^{*}$, how well $\mathcal{D}$ “covers” $(s_{h}^{\diamond},a_{h}^{\diamond})$, that is, $N_{h}(s_{h}^{\diamond},a_{h}^{\diamond})$, does not affect the suboptimality in Equation (4.8). See Figure 2 for an illustration.

Oracle Property: Following existing literature (Donoho and Johnstone 1994; Fan and Li 2001; Zou 2006), we refer to such a phenomenon as the oracle property, that is, the algorithm incurs an “oracle” suboptimality that automatically “adapts” to the support of the trajectory induced by $\pi^{*}$, even though $\pi^{*}$ is unknown a priori. From another perspective, assuming hypothetically $\pi^{*}$ is known a priori, the error that arises from estimating the transition kernel and expected reward function at $(s_{h}^{*},a_{h}^{*})$ scales as $N_{h}(s_{h}^{*},a_{h}^{*})^{-1/2}$, which can not be improved due to the information-theoretic lower bound.

Outperforming Demonstration: Assuming hypothetically $\mathcal{D}$ is induced by a fixed behavior policy $\bar{\pi}$ (namely the demonstration), such an oracle property allows $\texttt{Pess}(\mathcal{D})$ to outperform $\bar{\pi}$ in terms of the suboptimality, which is defined in Equation (2.6). Specifically, it is quite possible that $r_{h}(s_{h}^{\diamond},a_{h}^{\diamond})$ is relatively small and $N_{h}(s_{h}^{\diamond},a_{h}^{\diamond})$ is rather large for a certain $(s_{h}^{\diamond},a_{h}^{\diamond})$, which is “covered” by $\mathcal{D}$ but lies off the trajectory induced by $\pi^{*}$. Correspondingly, the suboptimality of $\bar{\pi}$ can be rather large. On the other hand, as discussed above, $r_{h}(s_{h}^{\diamond},a_{h}^{\diamond})$ and $N_{h}(s_{h}^{\diamond},a_{h}^{\diamond})$ do not affect the suboptimality of $\texttt{Pess}(\mathcal{D})$, which can be relatively small as long as $N_{h}(s_{h}^{*},a_{h}^{*})$ is sufficiently large. Here $(s_{h}^{*},a_{h}^{*})$ is “covered” by $\mathcal{D}$ and lies on the trajectory induced by $\pi^{*}$.

Well-Explored Dataset: To connect existing literature (Duan et al. 2020), the following corollary specializes Theorem 4.4 under the additional assumption that the data collecting process well explores ${\mathcal{S}}$ and $\mathcal{A}$.

Suppose $\mathcal{D}$ consists of $K$ trajectories $\{(x_{h}^{\tau},a_{h}^{\tau},r_{h}^{\tau})\}_{\tau,h=1}^{K,H}$ independently and identically induced by a fixed behavior policy $\bar{\pi}$ in the linear MDP. Meanwhile, suppose there exists an absolute constant $\underline{c}>0$ such that

Here $c>0$ is an absolute constant and $\xi\in(0,1)$ is the confidence parameter. Suppose we have $K\geq C\cdot d\log(4dH/\xi)$, where $C>0$ is a sufficiently large absolute constant that depends on $\underline{c}$. For $\texttt{Pess}(\mathcal{D})$ in Algorithm 2, the event

The suboptimality in Equation (4.13) parallels the policy evaluation error established in Duan et al. 2020, which also scales as $H^{2}K^{-1/2}$ and attains the information-theoretic lower bound for offline policy evaluation. In contrast, we focus on offline policy optimization, which is more challenging. As $K\rightarrow\infty$, the suboptimality in Equation (4.13) goes to zero.

3 Minimax Optimality: Information-Theoretic Lower Bound

For the output $\texttt{Algo}(\mathcal{D})$ of any algorithm, there exist a linear MDP $\mathcal{M}=({\mathcal{S}},\mathcal{A},H,\mathcal{P},r)$, an initial state $x\in{\mathcal{S}}$, and a dataset $\mathcal{D}$, which is compliant with $\mathcal{M}$, such that

See Section 5.3 for a proof sketch and Appendix C.3 for a detailed proof. ∎

Theorem 4.7 matches Theorem 4.4 up to $\beta$ and absolute constants. Although Theorem 4.7 only establishes the minimax optimality, Proposition C.2 further certifies the local optimality on the constructed set of worst-case MDPs via a more refined instantiation of the meta-algorithm (Algorithm 1). See Appendix C.4 for a detailed discussion.

4 Pessimistic Value Iteration: Reproducing Kernel Hilbert Spaces

In this section, we study the Pessimistic Value Iteration in greater generality with kernel function approximation, covering the linear setting of Algorithm 2 as a special case. The algorithm we develop in this part slightly modifies the generic Algorithm 1 with a data splitting trick: we use distinct (and reverse-ordered) subsets of the offline dataset for the value iteration at each time step. Despite a (limited) reduction in the size of available sample, this modification allows us to remove the dependence on the covering number of the kernel function classes in the analysis of suboptimality upper bounds, thereby being particularly favorable if the covering number is large.

Let $\mathcal{L}^{2}(\mathcal{Z})$ be the space of square-integrable functions on $\mathcal{Z}$ with respect to Lebesgue measure and let $\langle\cdot,\cdot\rangle_{\mathcal{L}^{2}}$ be the inner product for $\mathcal{L}^{2}(\mathcal{Z})$. The kernel function $K$ induces an integral operator $T_{K}\colon\mathcal{L}^{2}(\mathcal{Z})\to\mathcal{L}^{2}(\mathcal{Z})$ defined by

Mercer’s Theorem (Steinwart and Christmann 2008) implies that there exists a countable and non-increasing sequence of nonnegative eigenvalues $\{\sigma_{i}\}_{i\geq 1}$ for the integral operator $T_{K}$, and the associated eigenfunctions $\{\psi_{i}\}_{i\geq 1}$ form an orthogonal basis of $\mathcal{L}^{2}(\mathcal{Z})$. Moreover, the kernel function admits a spectral representation $K(z,z^{\prime})=\sum_{i=1}^{\infty}\sigma_{i}\cdot\psi_{i}(z)\cdot\psi_{i}(z^{\prime})$ for all $z,z^{\prime}\in\mathcal{Z}$. The eigenfunctions $\{\psi_{i}\}_{i\geq 1}$ also enables us to write the RKHS $\mathcal{H}$ as a subset of $\mathcal{L}^{2}(\mathcal{Z})$:

such that the $\mathcal{H}$-inner product of any $f,g\in\mathcal{H}$ can be represented as

4.2 Pessimistic Value Iteration for Kernel Function Approximation with Data Splitting

at each step $h\in[H]$ for all $f\in\mathcal{H}$, where only trajectories in fold $\mathcal{D}_{h}$ are involved. The empirical Bellman update is obtained from a kernel ridge regression so that

for some regularization parameter $\lambda>0$. Following the same arguments as in Yang et al. 2020c, we note that $\widehat{f}_{h}$ admits a closed-form solution

where $\beta>0$ is a scaling parameter. Finally, we construct the pessimistic Q-function by

Besides the closeness assumption on the Bellman operator, we also define the maximal information gain (Srinivas et al. 2009) as a characterization of the complexity of $\mathcal{H}$:

Here $K_{\mathcal{C}}$ is the Gram matrix for the set $\mathcal{C}$, defined similarly as Equation (4.17). In particular, when $\mathcal{H}$ has $\gamma$-finite spectrum, $G(n,\lambda)=\mathcal{O}(\gamma\cdot\log n)$ recovers the dimensionality of the linear space up to a logarithmic factor. More importantly, information gain defined in (4.20) offers a characterization of the effective dimension of $\mathcal{H}$ especially when $\mathcal{H}$ is infinite-dimensional.

The suboptimality of the output of Algorithm 3 is characterized by the following theorem.

Suppose Assumption 4.8 holds, and there exists some $\lambda\geq 1+1/K$ and $B>0$ satisfying

Theorem 4.9 expresses the suboptimality upper bound in a generic form consisting of two parts: (i) a parameter $B>0$ that depends on the kernel function class, as well as (ii) an information quantity

that only depends on the optimal policy $\pi^{*}$ and the offline dataset. In the same spirit of our preceding results, pessimism eliminates the spurious correlation (c.f. Equation (3.2)) with a properly constructed uncertainty quantifier $\{\Gamma_{h}\}_{h=1}^{H}$. When the RKHS has $\gamma$-finite spectrum with $\sigma_{j}=0$ for all $j>\gamma$, $\mathcal{I}_{\mathcal{D}}$ reduces to the one in Theorem 4.4 for the linear setting (with data splitting).

In what follows, we interpret the generic bound in Theorem 4.9 under specific conditions on $\mathcal{H}$, focusing on the resulting forms of the two components. We would see the effect of sample splitting in our discussion. Firstly, the parameter $B>0$ depends on the information gain $G(K/H,1+1/K)$, which can be viewed as a characterization of the complexity of $\mathcal{H}$. We provide explicit choices of $B$ under various eigenvalue decay conditions of $\mathcal{H}$ that decide such complexity.

Let $\{\sigma_{j}\}_{j\geq 1}$ be the eigenvalues induced by the integral opretaor $T_{K}$ defined in Equation (4.15) and $\{\psi_{j}\}_{j\geq 1}$ be the associated eigenfunctions. We assume that $\{\sigma_{j}\}_{j\geq 1}$ satisfies one of the following conditions for some constant $\gamma>0$.

$\gamma$-finite spectrum: $\sigma_{j}=0$ for all $j>\gamma$, where $\gamma$ is a positive integer.

$\gamma$-exponential decay: there exists some constants $C_{1},C_{2}>0$, $\tau\in[0,1/2)$ and $C_{\psi}>0$ such that $\sigma_{j}\leq C_{1}\cdot\exp(-C_{2}\cdot j^{\gamma})$ and $\sup_{z\in\mathcal{Z}}\sigma_{j}^{\tau}\cdot|\psi_{j}(z)|\leq C_{\psi}$ for all $j\geq 1$.

$\gamma$-polynomial decay: there exists some constants $C_{1}>0$, $\tau\in[0,1/2)$ and $C_{\psi}>0$ such that $\sigma_{j}\leq C_{1}\cdot j^{-\gamma}$ and $\sup_{z\in\mathcal{Z}}\sigma_{j}^{\tau}\cdot|\psi_{j}(z)|\leq C_{\psi}$ for all $j\geq 1$, where $\gamma>1$.

The $\gamma$-finite spectrum condition is satisfied by the linear MDP (Jin et al. 2020) with feature dimension $\gamma$, and Algorithm 3 reduces to the algorithm for linear MDP established in preceding sections (with data splitting). Also, the exponential and polynomial decay are relatively mild conditions compared to those in the literature. We refer the readers to Section 4.1 of Yang et al. 2020c for a detailed discussion on the eigenvalue decay conditions. Under the conditions in Assumption 4.10, Proposition 4.11 establishes the concrete choices of $B$ for Theorem 4.9.

Under Assumptions 4.8 and 4.10, we set $\lambda\geq 1+1/K$ and $\beta=B$ in Algorithm 3, where

Here $C>0$ is an absolute constant that does not depend on $K$ or $H$. Then with probability at least $1-\xi$ with respect to $\mathcal{D}$, it holds that

for some absolute constant $C>0$ that does not depend on $K$ or $H$.

Under $\gamma$-finite spectrum condition, taking $\lambda=1+1/K$ in Algorithm 3 leads to a variant of Algorithm 2 with sample splitting; setting $\lambda=1+1/K$ instead of $\lambda=1$ does not change the order of upper bounds in Theorem 4.4 for linear MDP. Firstly, comparing $B=\widetilde{\mathcal{O}}(\sqrt{\gamma}H)$ in Proposition 4.11 to $B=\widetilde{\mathcal{O}}(\gamma H)$ for linear MDP where $d=\gamma$ in Theorem 4.4, data splitting improves the upper bound by a factor of $\sqrt{\gamma}$ since it removes the dependence of $B$ on the covering number of the (linear) function class. Here $\widetilde{\mathcal{O}}(\cdot)$ hides logarithmic factors. On the other hand, in ideal settings such as the well-explored case of Corollary 4.6, $\mathcal{I}_{\mathcal{D}}$ is of order $\widetilde{\mathcal{O}}(\sqrt{d}H\cdot|\mathcal{I}_{h}|^{-1/2})$, where the reduction in sample size incurs an additional factor of $\sqrt{H}$. Thus, the data splitting approach is favorable if the horizon $H$ is of a smaller order than $d=\gamma$. In general, the data splitting approach improves sample efficiency if the kernel function class has a covering number that is larger than $\exp(H)$.

To further understand the behavior of $\mathcal{I}_{\mathcal{D}}$ beyond the $\gamma$-finite spectrum setting, we now consider a special case where the offline dataset consists of i.i.d. trajectories induced by some behavior policy. This offers a more clear illustration of the learning performance by certain population quantities that characterzie how close the behavior policy is to $\pi^{*}$.

We study a special case where the offline dataset consist of i.i.d. trajectories from some fixed behavior policy $\pi^{b}$; this enables us to translate $\mathcal{I}_{\mathcal{D}}$ into population quantities with specific choices of $\lambda$. The learning performance would depend on the “coverage” of $\pi^{b}$ for the optimal policy $\pi^{*}$, communicated by the following notion of “effective dimension”.

Moreover, we define the population effective dimension under $\pi^{b}$ as

Suppose $\mathcal{D}$ consists of i.i.d. trajectories sampled from behavior policy $\pi^{b}$, and Assumption 4.10 holds; in case (iii) $\gamma$-polynomial decay, we additionally assume $\gamma(1-2\tau)>1$. In Algorithm 3, we set $B>0$ as in Proposition 4.11 and

where $C>0$ is a sufficiently large absolute constant that does not depend on $K$ or $H$. Then with probability at least $1-\xi$ with respect to $\mathcal{D}$, it holds that

where $C^{\prime}>0$ is an absolute constant that does not depend on $K$ or $H$, and

The same results also apply to $d_{\text{eff}}^{\text{sample}}$.

Parallel to the linear setting, Corollary 4.13 demonstrates the performance of our method in terms of $d_{\text{eff}}^{\text{pop}}$ that depends on the relationship between $\Sigma_{h}$ (from $\pi^{b}$) and $\Sigma_{h}^{*}$ (from $\pi^{*})$. When $\Sigma_{h}$ and $\Sigma_{h}^{*}$ are close (i.e., $\pi^{b}$ covers $\pi^{*}$ well), we have $d_{\text{eff}}^{\text{pop}}\approx\widetilde{\mathcal{O}}(H^{3/2}K^{1/2})$; in this case, the suboptimality is of order $K^{-1/2}$ under $\gamma$-finite spectrum and $\gamma$-exponential decay, while for $\gamma$-polynomial decay we obtain a sublinear rate of $K^{\kappa^{*}-1/2}$.

Proof Sketch

In this section, we sketch the proofs of the main results in Section 4. In Section 5.1, we sketch the proof of Theorem 4.2, which handles any general MDP. In Section 5.2, we specialize it to the linear MDP, which is handled by Theorem 4.4. In Section 5.3, we sketch the proof of Theorem 4.7, which establishes the information-theoretic lower bound.

In Equation (5.1), the nonnegativity of $\{\iota_{h}\}_{h=1}^{H}$ implies the pessimism of $\{\widehat{Q}_{h}\}_{h=1}^{H}$, that is, $\widehat{Q}_{h}\leq Q_{h}^{*}$ in a pointwise manner for all $h\in[H]$. To see this, note that the definition of $\{\iota_{h}\}_{h=1}^{H}$ in Equation (3.1) gives

which together with Equations (2.3) and (2.5) further implies

for all $(x,a)\in{\mathcal{S}}\times\mathcal{A}$ and $h\in[H]$. Also, note that $\widehat{V}_{H+1}=V_{H+1}^{*}=0$. Therefore, Equation (5.2) implies $Q_{H}^{*}\geq\widehat{Q}_{H}$ in a pointwise manner. Moreover, by recursively applying Equation (5.3), we have $Q_{h}^{*}\geq\widehat{Q}_{h}$ in a pointwise manner for all $h\in[H]$. In other words, Lemma 5.1 implies that the pessimism of $\{\widehat{Q}_{h}\}_{h=1}^{H}$ holds with probability at least $1-\xi$ as long as $\{\Gamma_{h}\}_{h=1}^{H}$ in Algorithm 1 are $\xi$-uncertainty quantifiers, which serves as a sufficient condition that can be verified. Meanwhile, the upper bound of $\{\iota_{h}\}_{h=1}^{H}$ in Equation (5.1) controls the underestimation bias of $\{\widehat{Q}_{h}\}_{h=1}^{H}$, which arises from pessimism.

Based on Lemma 5.1, we are ready to prove Theorem 4.2.

We upper bound the three terms on the right-hand side of Equation (3.2) respectively. Specifically, we apply Lemma 3.1 by setting $\widehat{\pi}=\{\widehat{\pi}_{h}\}_{h=1}^{H}$ as the output of Algorithm 1, that is, $\widehat{\pi}=\texttt{Pess}(\mathcal{D})$. As $\widehat{\pi}_{h}$ is greedy with respect to $\widehat{Q}_{h}$ for all $h\in[H]$, term (iii) in Equation (3.2) is nonpositive. Therefore, we have

for all $x\in{\mathcal{S}}$, where terms (i) and (ii) characterize the spurious correlation and intrinsic uncertainty, respectively. To upper bound such two terms, we invoke Lemma 5.1, which implies

2 Suboptimality of PEVI: Linear MDP

Based on Theorem 4.2, we are ready to prove Theorem 4.4, which is specialized to the linear MDP defined in Definition 4.3.

It suffices to show that $\{\Gamma_{h}\}_{h=1}^{H}$ specified in Equation (4.7) are $\xi$-uncertainty quantifiers, which are defined in Definition 4.1. In the following lemma, we prove that such a statement holds when the regularization parameter $\lambda>0$ and scaling parameter $\beta>0$ in Algorithm 2 are properly chosen.

Suppose that Assumption 2.2 holds and the underlying MDP is a linear MDP. In Algorithm 2, we set

Here $c>0$ is an absolute constant and $\xi\in(0,1)$ is the confidence parameter. It holds that $\{\Gamma_{h}\}_{h=1}^{H}$ specified in Equation (4.7) are $\xi$-uncertainty quantifiers, where $\{\widehat{V}_{h+1}\}_{h=1}^{H}$ used in Equation (4.1) are obtained by Algorithm 2.

for all $x\in{\mathcal{S}}$ under $\mathcal{E}$ defined in Equation (4.1). Here the last equality follows from Equation (4.7). Therefore, we conclude the proof of Theorem 4.4. ∎

3 Minimax Optimality of PEVI

In this section, we sketch the proof of Theorem 4.7, which establishes the minimax optimality of Theorem 4.4 for the linear MDP. Specifically, in Section 5.3.1, we construct a class $\mathfrak{M}$ of linear MDPs and a worst-case dataset $\mathcal{D}$, while in Section 5.3.2, we prove Theorem 4.7 via the information-theoretic lower bound.

In the sequel, we construct a class $\mathfrak{M}$ of linear MDPs and a worst-case dataset $\mathcal{D}$, which is compliant with the underlying MDP as defined in Definition 2.1.

Linear MDP: We define the following class of linear MDPs

where $M(p_{1},p_{2},p_{3})$ is an episodic MDP with the horizon $H\geq 2$, state space ${\mathcal{S}}=\{x_{0},x_{1},x_{2}\}$, and action space $\mathcal{A}=\{b_{j}\}_{j=1}^{A}$ with $|\mathcal{A}|=A\geq 3$. In particular, we fix the initial state as $s_{1}=x_{0}$. For the transition kernel, at the first step $h=1$, we set

Meanwhile, at any subsequent step $h\in\{2,\ldots,H\}$, we set

In other words, $x_{1},x_{2}\in{\mathcal{S}}$ are the absorbing states. Here $\mathcal{P}_{1}(x_{1}{\,|\,}x_{0},b_{1})$ abbreviates $\mathcal{P}_{1}(s_{2}=x_{1}{\,|\,}s_{1}=x_{0},a_{1}=b_{1})$. For the reward function, we set

As $x_{1},x_{2}\in{\mathcal{S}}$ are the absorbing states, the optimal policy $\pi_{1}^{*}$ at the first step $h=1$ is a deterministic policy, which by Equation (5.3.1) selects the action $a\in\mathcal{A}$ that induces the largest transition probability into the desired state $x_{1}$. In other words, at the first step $h=1$, we have

Here we assume without loss of generality $p_{1}\neq p_{2}$ in Equation (5.3.1). Meanwhile, at any subsequent step $h\in\{2,\ldots,H\}$, an arbitrary policy $\pi_{h}$ is optimal, as the action $a\in\mathcal{A}$ selected by $\pi_{h}$ does not affect the transition probability. Therefore, for any policy $\pi=\{\pi_{h}\}_{h=1}^{H}$, the suboptimality of $\pi$ for the linear MDP $\mathcal{M}=M(p_{1},p_{2},p_{3})$ takes the form

where for notational simplicity, we define $p_{j}=p_{3}$ for all $j\in\{3,\ldots,A\}$. Here with an abuse of notation, we incorporate the explicit dependency on the underlying MDP $\mathcal{M}\in\mathfrak{M}$ into the suboptimality $\text{SubOpt}(\pi;x_{0})$.

In other words, assuming that $1\leq\tau_{1}<\tau_{2}<\cdots<\tau_{n_{j}}\leq K$ are the episode indices such that $a_{1}^{\tau_{i}}=b_{j}$ for all $i\in[n_{j}]$, we define $\kappa_{j}^{i}=r_{2}^{\tau_{i}}$ for all $j\in[A]$. By such a construction, $\{\kappa_{j}^{i}\}_{i,j=1}^{n_{j},A}$ are the realizations of $K$ independent Bernoulli random variables, which satisfy

Note that knowing the value of the immediate reward $r_{2}^{\tau}$ is sufficient for determining the value of the second state $x_{2}^{\tau}$. Meanwhile, recall that $x_{1},x_{2}\in{\mathcal{S}}$ are the absorbing states. Therefore, for learning the optimal policy $\pi^{*}$, the original dataset $\mathcal{D}$ contains the same information as the reduced dataset $\mathcal{D}_{1}=\{(x_{1}^{\tau},a_{1}^{\tau},x_{2}^{\tau},r_{2}^{\tau})\}_{\tau=1}^{K}$, where the randomness only comes from the state transition at the first step $h=1$ of each trajectory $\tau\in[K]$. Correspondingly, the probability of observing the dataset $\mathcal{D}_{1}$ takes the form

3.2 Information-Theoretic Lower Bound

The proof of Theorem 4.7 is based on the Le Cam method (Le Cam 2012; Yu 1997). Specifically, we construct two linear MDPs $\mathcal{M}_{1},\mathcal{M}_{2}\in\mathfrak{M}$, where the class $\mathfrak{M}$ of linear MDPs is defined in Equation (5.6). Such a construction ensures that (i) the distribution of the dataset $\mathcal{D}$, which is compliant with the underlying MDP, is similar across $\mathcal{M}_{1},\mathcal{M}_{2}\in\mathfrak{M}$, and (ii) the suboptimality of any policy $\pi$, which is constructed based on the dataset, is different across $\mathcal{M}_{1},\mathcal{M}_{2}\in\mathfrak{M}$. In other words, it is hard to distinguish $\mathcal{M}_{1},\mathcal{M}_{2}\in\mathfrak{M}$ based on $\mathcal{D}$, while $\pi$ obtained from $\mathcal{D}$ can not achieve a desired suboptimality for $\mathcal{M}_{1},\mathcal{M}_{2}\in\mathfrak{M}$ simultaneously. Such a construction captures the fundamental hardness of offline RL for the linear MDP.

For any $p,p^{*}\in[1/4,3/4]$, where $p<p^{*}$, we set

For the dataset $\mathcal{D}$ specified in Section 5.3.1, the output $\texttt{Algo}(\mathcal{D})$ of any algorithm satisfies

As specified in Equation (5.10), for the underlying MDP $\mathcal{M}_{1}$, the optimal policy $\pi_{1}^{*}$ takes the initial action $b_{1}$ with probability one at the initial state $x_{0}$, while for $\mathcal{M}_{2}$, $\pi_{1}^{*}$ takes $b_{2}$ with probability one at $x_{0}$. We consider the following hypothesis testing problem

based on the dataset $\mathcal{D}$. For such a problem, any test function $\psi$ is a binary map such that $\psi(\mathcal{D})=0$ means the null hypothesis $H_{0}$ is accepted, while $\psi(\mathcal{D})=1$ means $H_{0}$ is rejected. For the output $\pi=\{\pi_{h}\}_{h=1}^{H}=\texttt{Algo}(\mathcal{D})$ of any algorithm, we define

Correspondingly, the risk of the (randomized) test function $\psi_{\texttt{Algo}}$ takes the form

Therefore, Lemma 5.3 lower bounds the suboptimality of any policy $\pi=\{\pi_{h}\}_{h=1}^{H}=\texttt{Algo}(\mathcal{D})$ by the risk of a (randomized) test function, which is induced by $\pi$, for the corresponding hypothesis testing problem defined in Equation (5.16). Such an approach mirrors the Le Cam method (Le Cam 2012; Yu 1997) for establishing the minimax optimality in statistical estimation. In particular, a careful choice of $p,p^{*}\in[1/4,3/4]$ leads to the information-theoretic lower bound established in Theorem 4.7. See Appendix C.3 for a detailed proof.

References

Appendix A Proofs of Suboptimality Decomposition

By the definition in Equation (2.6), the suboptimality of the policy $\widehat{\pi}$ given any initial state $x\in{\mathcal{S}}$ can be decomposed as

where $\{\widehat{V}_{h}\}_{h=1}^{H}$ are the estimated value functions constructed by the meta-algorithm. Term (i) in Equation (A.1) is the difference between the estimated value function $\widehat{V}_{1}$ and the optimal value function $V_{1}^{\pi^{*}}$, while term (ii) is the difference between $\widehat{V}_{1}$ and the value function $V_{1}^{\widehat{\pi}}$ of $\widehat{\pi}$. To further decompose terms (i) and (ii), we utilize the following lemma, which is obtained from Cai et al. 2020, to characterize the difference between an estimated value function and the value function of a policy.

See Section B.1 in Cai et al. 2020 for a detailed proof. ∎

Applying Lemma A.1 with $\pi=\widehat{\pi}$, $\pi^{\prime}=\pi^{*}$, and $\{\widehat{Q}_{h}\}_{h=1}^{H}$ being the estimated Q-functions constructed by the meta-algorithm, we have

Similarly, applying Lemma A.1 with $\pi=\pi^{\prime}=\widehat{\pi}$ and $\{\widehat{Q}_{h}\}_{h=1}^{H}$ being the estimated Q-functions constructed by the meta-algorithm, we have

Appendix B Proofs of Pessimistic Value Iteration

We first show that on the event $\mathcal{E}$ defined in Equation (4.1), the model evaluation errors $\{\iota_{h}\}_{h=1}^{H}$ are nonnegative. In the sequel, we assume that $\mathcal{E}$ holds. Recall the construction of $\overline{Q}_{h}$ in Line 5 of Algorithm 1 for all $h\in[H]$. For all $h\in[H]$ and all $(x,a)\in{\mathcal{S}}\times\mathcal{A}$, if $\overline{Q}_{h}(x,a)<0$, we have

By the definition of $\iota_{h}$ in Equation (3.1), we have

as $r_{h}$ and $\widehat{V}_{h+1}$ are nonnegative. Otherwise, if $\overline{Q}_{h}(x,a)\geq 0$, we have

As $\{\Gamma_{h}\}_{h=1}^{H}$ are $\xi$-uncertainty quantifiers, which are defined in Definition 4.1, we have

Here the last inequality follows from the definition of $\mathcal{E}$ in Equation (4.1). Therefore, we conclude the proof of $\iota_{h}(x,a)\geq 0$ for all $h\in[H]$ and all $(x,a)\in{\mathcal{S}}\times\mathcal{A}$ on $\mathcal{E}$.

It remains to establish the upper bound in Equation (5.1). For all $h\in[H]$ and all $(x,a)\in{\mathcal{S}}\times\mathcal{A}$, combining the definition of event $\mathcal{E}$ in Equation (4.1) as well as the construction of $\overline{Q}_{h}$ in Line 5 of Algorithm 1 gives

where the first inequality follows from the triangle inequality, while the second inequality follows from the fact that $r_{h}\in$ and $\widehat{V}_{h+1}\in[0,H-h]$. Hence, we have

which by the definition of $\iota_{h}$ in Equation (3.1) implies

Here the last inequality follows from the definition of $\mathcal{E}$ in Equation (4.1). Therefore, we complete the proof of $\iota_{h}(x,a)\leq 2\Gamma_{h}(x,a)$ for all $h\in[H]$ and all $(x,a)\in{\mathcal{S}}\times\mathcal{A}$ on $\mathcal{E}$.

In summary, we conclude that on $\mathcal{E}$,

Therefore, we conclude the proof of Lemma 5.1. ∎

B.2 Proof of Lemma 5.2

Also, Equation (4.4) ensures that the expected reward is linear in $\phi$ for all $h\in[H]$, which implies

Let $V_{\max}>0$ be an absolute constant. For any function $V:{\mathcal{S}}\to[0,V_{\max}]$ and any $h\in[H]$, we have

where $w_{h}$ and $\widehat{w}_{h}$ are defined in Equations (B.2) and (4.2), respectively.

For all $h\in[H]$, Equations (B.1) and (B.2) imply

where the third inequality follows from the fact that $V\in[0,V_{\max}]$.

Meanwhile, by the definition of $\widehat{w}_{h}$ in Equation (4.2) and the triangle inequality, we have

Note that $|r_{h}^{\tau}+\widehat{V}_{h+1}(x_{h+1}^{\tau})|\leq H$, which follows from the fact that $r_{h}^{\tau}\in$ and $\widehat{V}_{h+1}\in[0,H-1]$ by Line 10 of Algorithm 2. Also, note that $\Lambda_{h}\succeq\lambda\cdot I$, which follows from the definition of $\Lambda_{h}$ in Equation (4.2). Hence, we have

where the last inequality follows from the fact that $\|\Lambda_{h}^{-1}\|_{\mathop{\text{op}}}\leq\lambda^{-1}$. Here $\|\cdot\|_{\mathop{\text{op}}}$ denotes the matrix operator norm. By the Cauchy-Schwarz inequality, we have

where the second equality follows from the definition of $\Lambda_{h}$ in Equation (4.2).

Therefore, combining Equations (B.2) and (B.2), we conclude the proof of Lemma B.1. ∎

In the sequel, we upper bound terms (i) and (ii) respectively. By the construction of the estimated value function $\widehat{V}_{h+1}$ in Line 10 of Algorithm 2, we have $\widehat{V}_{h+1}\in[0,H-1]$. By Lemma B.1, we have $\|w_{h}\|\leq H\sqrt{d}$. Hence, term (i) defined in Equation (B.5) is upper bounded by

Here the second equality follows from the definition of $\Lambda_{h}$ in Equation (4.2). Also, the first inequality follows from the Cauchy-Schwarz inequality, while the last inequality follows from the fact that

Here $\|\cdot\|_{\mathop{\text{op}}}$ denotes the matrix operator norm and we use the fact that $\|\Lambda_{h}^{-1}\|_{\mathop{\text{op}}}\leq\lambda^{-1}$.

It remains to upper bound term (ii). For notational simplicity, for any $h\in[H]$, any $\tau\in[K]$, and any function $V\colon{\mathcal{S}}\rightarrow[0,H]$, we define the random variable

By the Cauchy-Schwarz inequality, term (ii) defined in Equation (B.5) is upper bounded by

In the sequel, we upper bound term (iii) via concentration inequalities. An obstacle is that $\widehat{V}_{h+1}$ depends on $\{(x_{h}^{\tau},a_{h}^{\tau})\}_{\tau=1}^{K}$ via $\{(x_{h^{\prime}}^{\tau},a_{h^{\prime}}^{\tau})\}_{\tau\in[K],h^{\prime}>h}$, as it is constructed based on the dataset $\mathcal{D}$. To this end, we resort to uniform concentration inequalities to upper bound

for each $h\in[H]$, where it holds that $\widehat{V}_{h+1}\in\mathcal{V}_{h+1}(R,B,\lambda)$. Here for all $h\in[H]$, we define the function class

For all $\varepsilon>0$ and all $h\in[H]$, let $\mathcal{N}_{h}(\varepsilon;R,B,\lambda)$ be the minimal $\varepsilon$-cover of $\mathcal{V}_{h}(R,B,\lambda)$ with respect to the supremum norm. In other words, for any function $V\in\mathcal{V}_{h}(R,B,\lambda)$, there exists a function $V^{\dagger}\in\mathcal{N}_{h}(\varepsilon;R,B,\lambda)$ such that

Meanwhile, among all $\varepsilon$-covers of $\mathcal{V}_{h}(R,B,\lambda)$ defined by such a property, we choose $\mathcal{N}_{h}(\varepsilon;R,B,\lambda)$ as the one with the minimal cardinality.

By Lemma B.1, we have $\|\widehat{w}_{h}\|\leq H\sqrt{Kd/\lambda}$. Hence, for all $h\in[H]$, we have

Here $\lambda>0$ is the regularization parameter and $\beta>0$ is the scaling parameter, which are specified in Algorithm 2. For notational simplicity, we use $\mathcal{V}_{h+1}$ and $\mathcal{N}_{h+1}(\varepsilon)$ to denote $\mathcal{V}_{h+1}(R_{0},B_{0},\lambda)$ and $\mathcal{N}_{h+1}(\varepsilon;R_{0},B_{0},\lambda)$, respectively. As it holds that $\widehat{V}_{h+1}\in\mathcal{V}_{h+1}$ and $\mathcal{N}_{h+1}(\varepsilon)$ is an $\varepsilon$-cover of $\mathcal{V}_{h+1}$, there exists a function $V^{\dagger}_{h+1}\in\mathcal{N}_{h+1}(\varepsilon)$ such that

Hence, given $V^{\dagger}_{h+1}$ and $\widehat{V}_{h+1}$, the monotonicity of conditional expectations implies

By the triangle inequality, Equations (B.10) and (B.12) imply

for all $h\in[H]$ and all $(x,a,x^{\prime})\in{\mathcal{S}}\times\mathcal{A}\times{\mathcal{S}}$. Setting $(x,a,x^{\prime})=(x_{h}^{\tau},a_{h}^{\tau},x_{h+1}^{\tau})$ in Equation (B.13), we have

The second term on the right-hand side of Equation (B.15) is upper bounded by

where the first inequality follows from Equation (B.14). As it holds that $\Lambda_{h}\succeq\lambda\cdot I$ by the definition of $\Lambda_{h}$ in Equation (4.2) and $\|\phi(x,a)\|\leq 1$ for all $(x,a)\in{\mathcal{S}}\times\mathcal{A}$ by Definition 4.3, for all $h\in[H]$, we have

Combining Equations (B.15) and (B.16), for all $h\in[H]$, we have

Let $V:{\mathcal{S}}\to[0,H-1]$ be any fixed function. Under Assumption 2.2, for any fixed $h\in[H]$ and any $\delta\in(0,1)$, we have

For the fixed $h\in[H]$ and all $\tau\in\{0,\ldots,K\}$, we define the $\sigma$-algebra

where $\sigma(\cdot)$ denotes the $\sigma$-algebra generated by a set of random variables and $(\tau+1)\wedge K$ denotes $\min\{\tau+1,K\}$. For all $\tau\in[K]$, we have $\phi(x_{h}^{\tau},a_{h}^{\tau})\in\mathcal{F}_{h,\tau-1}$, as $(x_{h}^{\tau},a_{h}^{\tau})$ is $\mathcal{F}_{h,\tau-1}$-measurable. Also, for the fixed function $V\colon{\mathcal{S}}\to[0,H-1]$ and all $\tau\in[K]$, we have

as $(r_{h}^{\tau},x_{h+1}^{\tau})$ is $\mathcal{F}_{h,\tau}$-measurable. Hence, $\{\epsilon_{h}^{\tau}(V)\}_{\tau=1}^{K}$ is a stochastic process adapted to the filtration $\{\mathcal{F}_{h,\tau}\}_{\tau=0}^{K}$. By Assumption 2.2, we have

We invoke Lemma E.2 with $M_{0}=\lambda\cdot I$ and $M_{k}=\lambda\cdot I+\sum_{\tau=1}^{k}\phi(x_{h}^{\tau},a_{h}^{\tau})\ \phi(x_{h}^{\tau},a_{h}^{\tau})^{\top}$ for all $k\in[K]$. For the fixed function $V\colon{\mathcal{S}}\to[0,H-1]$ and fixed $h\in[H]$, we have

for all $\delta\in(0,1)$. Here we use the fact that $M_{K}=\Lambda_{h}$. Note that $\|\phi(x,a)\|\leq 1$ for all $(x,a)\in{\mathcal{S}}\times\mathcal{A}$ by Definition 4.3. We have

where $\|\cdot\|_{\mathop{\text{op}}}$ denotes the matrix operator norm. Hence, it holds that $\det(\Lambda_{h})\leq(\lambda+K)^{d}$ and $\det(\lambda\cdot I)=\lambda^{d}$, which implies

Therefore, we conclude the proof of Lemma B.2. ∎

Applying Lemma B.2 and the union bound, for any fixed $h\in[H]$, we have

For all $\xi\in(0,1)$ and all $\varepsilon>0$, we set $\delta=\xi/(H\cdot|\mathcal{N}_{h+1}(\varepsilon)|)$. Hence, for any fixed $h\in[H]$, it holds that

It remains to choose a proper $\varepsilon>0$ and upper bound the $\varepsilon$-covering number $|\mathcal{N}_{h+1}(\varepsilon)|$. In the sequel, we set $\varepsilon=dH/K$ and $\lambda=1$. By Equation (B.19), for all $h\in[H]$, it holds that

For all $h\in[H]$ and all $\varepsilon>0$, we have

See Lemma D.6 in Jin et al. 2020 for a detailed proof. ∎

Here $c>0$ is an absolute constant, $\xi\in(0,1)$ is the confidence parameter, and $\zeta=\log(2dHK/\xi)$ is specified in Algorithm 2. Recall that $\mathcal{N}_{h+1}(\varepsilon)=\mathcal{N}_{h+1}(\varepsilon;R_{0},B_{0},\lambda)$ is the minimal $\varepsilon$-cover of $\mathcal{V}_{h+1}=\mathcal{V}_{h+1}(R_{0},B_{0},\lambda)$ with respect to the supremum norm. Applying Lemma B.3 with $\varepsilon=dH/K$, we have

As it holds that $\zeta>1$, we set $c\geq 1$ to ensure that the second term on the right-hand side of Equation (B.2) is the dominating term, where $32c^{2}\cdot d^{1/2}K^{2}\zeta\geq 1$. Hence, we have

By Equations (B.20) and (B.22), for all $h\in[H]$, it holds that

As it holds that $\zeta>1$ and $\log\zeta\leq\zeta$, Equation (B.2) implies

We set $c\geq 1$ to be sufficiently large, which ensures that $36+8\cdot\log(64c^{2})\leq c^{2}/4$ on the right-hand side of Equation (B.24). By Equations (B.2) and (B.24), for all $h\in[H]$, it holds that

By Equations (4.7), (B.5), (B.2), and (B.25), for all $h\in[H]$ and all $(x,a)\in{\mathcal{S}}\times\mathcal{A}$, it holds that

B.3 Proof of Corollary 4.5

By the Cauchy-Schwarz inequality, we have

for all $x\in{\mathcal{S}}$ and all $h\in[H]$. We define the event

for all $x\in{\mathcal{S}}$ and all $h\in[H]$. On the event $\mathcal{E}^{\dagger}\cap\mathcal{E}^{\ddagger}$, where $\mathcal{E}^{\dagger}$ and $\mathcal{E}^{\ddagger}$ are defined in Equations (4.9) and (B.27), respectively, we have

Here $\{\lambda_{h,j}(x)\}_{j=1}^{d}$ are the eigenvalues of $\Sigma_{h}(x)$ for all $x\in{\mathcal{S}}$ and all $h\in[H]$, the first inequality follows from the definition of $\mathcal{E}^{\ddagger}$ in Equation (B.27), and the second inequality follows from Equation (B.3) and the definition of $\mathcal{E}^{\dagger}$ in Equation (4.9). Meanwhile, by Definition 4.3, we have $\|\phi(s,a)\|\leq 1$ for all $(x,a)\in{\mathcal{S}}\times\mathcal{A}$. By Jensen’s inequality, we have

for all $x\in{\mathcal{S}}$ and all $h\in[H]$. As $\Sigma_{h}(x)$ is positive semidefinite, we have $\lambda_{h,j}(x)\in$ for all $x\in{\mathcal{S}}$, all $h\in[H]$, and all $j\in[d]$. Hence, on $\mathcal{E}^{\dagger}\cap\mathcal{E}^{\ddagger}$, we have