Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data
Authors: Ruiqi Zhang
Andrea Zanette
Venue: NeurIPS 2023 poster (2023)
Keywords: offline RL
online RL
exploration
non-reactive
fine-tuning
TL;DR: Policy finetuning using a non-reactive exploration policy with theoretical guarantees

Abstract: In some applications of reinforcement learning, 
a dataset of pre-collected experience is already available
but it is also possible to acquire some additional online data to help improve the quality of the policy.
However, it may be preferable to gather additional data with a single, non-reactive exploration policy
and avoid the engineering costs associated with switching policies. 

In this paper we propose an algorithm with provable guarantees 
that can leverage an offline dataset to design a single non-reactive policy for exploration. 
We theoretically analyze the algorithm and measure the quality of the final policy 
as a function of the local coverage of the original dataset and the amount of additional data collected.

Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data
Ruiqi Zhang
Department of Statistics
University of California, Berkeley rgzhang@brrkaley edu
Andrea Zanette
Department of EECS
University of California, Berkeley zanette@berkeley.c edu
Abstract
In some applications of reinforcement learning, dataset of pre-collected experi- ence is already available but it also possible to acquire some additional online data help improve the quality of the policy. However, it may be preferable gather additional data with a single, non-rcactive exploration policy and avoid the engineering costs associated with switching policies.
In this paper we propose an algorithm with provable guarantees that can leverage offline dataset to design single non-reactive policy for exploration. We the- oretically analyze the algorithm and measure the quality of the final policy as a function of the local coverage of the original dataset and the amount of additional data collected.
Introduction
Reinforcement learning (RL) is a general framework for data-driven, sequential decision making [Puterman 1994 Suttonn and Barto 2018 In RL, common goal is to identify near-optimal policy, and there exist two main paradigms: online and offline RL.
Online RI. is effective when the practical cost of a bad decision is low, such in simulated environ- ments (c.g., [Mnih et al. [2015] Silver et al., (2166). In online RL, a well designed learning algorithm starts from tabula rasa and implements sequence of policies with value that should approach that of an optimal policy. When the cost of making a mistake is high, such as in healthcare [Gottesman et al. [2018) and in self-driving [Kiran et al. 202T], offline approach is preferred. In offline RL, the agent uses a dataset pre-collected experience to extract policy that is as good as possible. In this latter case, the quality of the policy that be extracted from the dataset is limited by the quality of the dataset.
Many applications, however, fall between these two opposite settings: for example, company that sells products online has most likely recorded the feedback that has received from its customers, but also collect small amount of additional strategic data in order to improve its recommendation engine. While in principle an online exploration algorithm can be used to collect fresh data, in practice there are number of practical engineering considerations that require the policy to be
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

deployed to be non-reactive. We say that policy is non-reactive, (or passive, memoryless) if it chooses actions only according to the current state of the system. Most online algorithms are, by design, reactive to the data being acquired.
An example of situation where non-reactive policies may be preferred are those where a human in the loop is required to validate each exploratory policy before they are deployed. to ensure they are of high quality [Dann et al., 2019] and safe [Yang et al.) 2021], as well as free of discriminatory content Koenecke et al. 2020]. Other situations that may warrant non-reactive exploration are those where the interaction with the user occurs through a distributed system with delayed feedback. In recommendation systems, data collection may only take minutes, but policy deployment and updates can span weeks [Afsar et al.) 2022]. Similar considerations apply across various RL application domains, including heal thcare Yu et al. [02T], computer networks (Xu et al. [2018]. and new material design (Raccuglia et al., [016]] In all such cases, the engineering effort required to implement a
system that handles real-time policy switches may be prohibitive: deploying single, non-reactive
policy is much preferred.
Non-reactive exploration from offline data Most exploration algorithms that we are aware of incorporate policy switches when they interact with the environment (Dann and Brunskill 2013
Dann et al.
2017 Azar et al. 2017 Jin et al., 2018 Dann et al., 2019 Zanette and Brunskill 2019
Zhang et al. 2020b]. Implementing sequence of non non-reactive policies is necessary in order to achieve
near-optimal regret: the number of policy switches must be at least Ô (H [S] |A| log log K) where S,A, H, K are the state space, action space, horizon and the total number of episodes, respectively [Qiao et al. 2022]. With no switches, i.e., when a fully non-reactive data collection strategy is implemented, it is information theoretically impossible (Xiao et al. 2022] to identify good policy using a number of samples polynomial in the size of the state and action space.
However, these fundamental limits apply to the case where the agent learns from tabula rasa. In the more common case where offline data is available, we demonstrate that it possible to leverage the dataset to design an effective non-reactive exploratory policy. More precisely, an available offline dataset contains information (e.g., transitions) about certain area of the state-action space, a concept known as partial coverage. A dataset with partial coverage naturally identifies a 'sub-region' of the original
more precisely, a sub-graph- that is relatively well explored. We demonstrate that it is possible to use the dataset to design a non-reactive policy that further explores such sub-region. The additional data collected can be used to learn a near-optimal policy in such sub-region.
In other words, exploration with no policy switches can collect additional information and compete with the best policy that is restricted to an area where the original dataset has sufficient information. The value of such policy can be much higher than the one that can be computed using only the offline dataset, and does not directly depend on a concentrability coefficient [Munos and Szepesvári 2008 Chen and Jiang] 2019
Perhaps surprisingly, addressing the problem of reactive exploration in reinforcement learning requires an approach that combines both optimism and pessimism in the face of uncertainty to explore efficiently. While optimism drives exploration, pessimism ensures that the agent explores conservatively, in way that restricts its exploration effort to a region that it knows how to navigate, and so our paper makes a technical contribution which can be of independent interest.
Contributions To the best of our knowledge, this is the first paper with theoretical rigor that considers the problem of designing an experiment in reinforcement learning for online, passive exploration, using a dataset of pre-collected experience. More precisely, our contributions are as follows:
We introduce an algorithm that takes as input a dataset, uses to design and deploy a non-reactive exploratory policy, and then outputs a locally near-optimal policy.
We introduce the concept of sparsified MDP, which is actively used by our algorithm to design the exploratory policy, as well as to theoretically analyze the quality of the final policy that it finds.
We rigorously establish a nearly tinimax-optimal upper bound for the sample complexity needed learn local s-optimal policy using our algorithm.
1 MMore rigorously, our sample complexity matches the minimax lower bound when we have some degree of knowledge for the full MDP, see the discussion in Section section The lower bound for the samples needed in reward-free case is proved in [Jin et al. (2020b). but their result applies to the non- non-honogen hon-hongesssuu MDP. The sample complexity homogeneous MDP should be shaved off by an H factor.

---

2 Related Work
In this section we discuss some related literature. Our work related to lww-shitching algorithms, but unlike those, we focus on the limit case where no-switiches are allowed. For more related work about low-switching algorithms, offline RI., task-agnostic RI,, and reward-free RL we refer to Appendix F
Low-switching RL In reinforcement learning, [Bai et al. 2019 first proposed Q-learning with UCB2 exploration, proving an O(1**1] | log K) switching cost. This was later improved by a factor of H by the UCBadvantage algorithm in (Zhang et a 2020b]. Recently, (Qiao et al., 2022] generalized the policy elimination algorithm from [Cesa-Bianchi et al. 2013] and introduced APEVE, which attains an optimal O(H [S] |A] log log K) switching cost. The reward-frie wwward-free version of their algorithm (which is not regret minimizing) has an O(H [S] [Al) switching cost.
Similar ideas were soon applied in RL with linear function approximation |aoo ct al. 2021 Wang al. 202T Qiao and Wang 2022 and general function approximation [Qiao et al. 2023]. Addition- ally, numerous research efforts have focused on low-adaptivity in other learning domains, such as batched dueling bandits [Agarwal et al. 2022], batched convex optimization (Duchi et al. (0188).
linear contextual bandits [Ruan et al. 202 I.. and deployment-efficient RL (Huang et al. 2022]
Our work was inspired by the problem of non-reactive policy design in linear contextual bandits. Given access to an offline dataset, [Zanette et al. 202 proposed an algorithm to output a single exploratory policy, which generates dataset from which a near-optimal policy can be extracted. However, there are number of additional challenges which arise in reinforcement learning, including the fact that the state space is only partially explored in the offline dataset. In fact, in reinforcement learning, [Xiao et al.) 2022) established an exponential lower bound for any non-adaptive policy learning algorithm starting from tabula rasa.
Setup
Throughout this paper, we let [n]
21,,...,, We adopt the big-O notation, where Ō(-) suppresses poly-log factors of the input parameters. We indicate the cardinality of a set X' with |
Markov decision process We consider hime-homogeneous episodic Markov decision processes (MDPs). They are defined by a finite state space S, a finite action space .A, a trasition kernel P., a reward function and the episodic length H. The transition probability PP (s' s, a), which does not depend on the current time-step E [H]. denotes the probability of transitioning to state E S when taking action E A in the current state S. Typically we denote with s1 the initial state. For simplicity, we consider deterministic reward functions r S x A - [0, 1]. A deterministic non-reactive (or memoryless, or passive) policy
{*x [=]])] maps given state to action.
The value function is defined as the expected cumulated reward. It depends on the state under consideration, the transition IP and reward r that define the MDP as well as on the policy æ being implemented. defined as Vn (s; IP, r. x) = Bp, r(s,, a,) s%, = s]. where Ep, denotes the expectation generated by IP and policy π. A closely related quantity is the state-action value function, or Q-function, defined as Qn (s, a; IP, r, x) Ex r(s;, a;) Sh 5, ag a]. When it is clear from the context, we sometimes omit (IP r) and simply write them as VT((s and QT (s, a). We denote an MDP defined by S, A and the transition matrix IP M (S, A,
3.1 Interaction protocol
Algorithm Design of experiments in reinforcement learning
Input: Offline dataset D
1: Offline phase: use D to compute the exploratory policy Ter
2: Online phase: deploy Ter to collect the online dataset D'
3: Planning phase: receive the reward function and use D U D' extract /f
Output: Return π final
3

---

In this paper we assume access to an offtine dataset D = {(s. a, s')} where every state-action (s. a) sampled in an i..dd fashion from some distribution μ and s' P(- s, a). which common in the offline RI. literature [iie et al. 2021a Zhan et al. 2022 Rashidinejad et al. 2021 Uehara and Sun 2021]. We denote N(8, a) and (s, a, 8') as the number (s, a) and (8, a, 8' samples the offline dataset D, respectively. The interaction protocol considered in this paper consists of three distinct phases, which are displayed in algorithm [
They are:
the offline phase, where the learner uses an offline dataset 'D of pre-collected experience to design the non-reactive exploratory policy Teni
the online phase where Tex is deployed to generate the online dataset D';
the planning phase where the learner receives a reward function and uses all the data collected to extract good policy π final with respect to that reward function.
The objective is to minimize the number of online episodic interactions needed to find a policy т final whose value is as high as possible. Moreover, we focus on the reward-free RL setting [Jin et al. 2020a Kaufmann et al. 2021 Li et al. 2023b], which is more general than reward- aware RL. In the offline and online phase, the data are generated without specific reward signals, and the entire reward information is then given in the planning phase. One of the primary advantages of using reward- -wree-frree offline data is that it allows for the collection of data without the need for explicit reward signals. This can be particularly beneficial in environments where obtaining reward signals is costly, risky, ethically challenging, or where the reward functions are human- human-designed.
4 Algorithm: balancing optimism and pessimism for experimental design
In this section we outline our algorithm Reward-Free Non-reactive Policy Design (RF-NPD), which follows the high-level protocol described in algorithm | The technical novelty lies almost entirely in the design of the exploratory policy Wez- In order to prepare the reader for the discussion of the algorithm, we first give some intuition in section 4. followed by the definition of sparsified MDP in section 4.2 a central concept of this paper, and then describe the implementation of line iin the protocol in algorithm in section 4.3 We conclude by presenting the implementation of lines 2 and
the protocol in algorithm]]
4.1 Intuition
In order to present the main intuition for this paper, in this section we assume that enough transitions are available in the dataset for every edge (s,a) + s', namely that the critical condition
N(s, a, s²) 2 4 = -(H²)
(4.1)
holds for all tuples (s,a, S x A x S (the precise value for t will be given later in eq. (5.1)
Such condition is hardly satisfied everywhere in the state-action-state space, but assuming it in this section simplifies the presentation of one of the key ideas of this paper.
The key observation is that when eq. 4.1 holds for all (s, s'), can use the empirical transition kernel to design an exploration policy Tez to eventually extract a opar-optimal policy Tiinal for any desired level of sub-optimality E, despite eq. (4.1) being independent of e. More precisely, let fP be the empirical transition kernel defined in the usual way PP(s' a) N(s, a, s') a) for any tuple (s, a, 8'). The intuition-which will be verified rigorously in the analysis of the algorithm-is the following:
If eq. 4.1 holds for every (s, a, a's) then P can be used to design a non-reactive exploration policy Nea which can be deployed on M to find an e-optimal policy Jininal using + samples.
We remark that even if the condition 4.1 holds for all tuples (s, a, s'), the empirical kernel P is not accurate enough to extract an e-optimal policy from the dataset D without collecting further data. Indeed, the threshold $- = @(H²) on the number of samples is independent of the desired sub-optimality & > O, while it is well known that at least z offline samples are needed to find an e-optimal policy. Therefore, directly implementing offline RL algorithm to use the available

---

offline dataset D does not yield an E-optimal policy, However, the threshold + = ((H)) is sufficient to design a non-reactive exploratory policy Ter that can discover an e-optimal policy x final after collecting 22 online data.
4.2 Sparsified MDP
The intuition in the prior section must be modified to work with heterogeneous datasets and dynamics where (ss, a, s') 2 db may fail to hold everywhere. For example, if P(s' s,a) is very small for a certain tuple (s, a, s'), it is unlikely that the dataset contains ((s, a, s') 2 & samples for that particular tuple. In more extreme setting, if the dataset is empty, the critical condition in eq. (4.1) is violated for all tuples (s, a, s'), and in fact the lower bound of Xiao et al. [2022) states that finding e-optimal policies by exploring with non-reactive policy is not feasible with 2 sample complexity. This suggests that in general it is not possible to output an e-optimal policy using the protocol in algorithm|
However, a real-world dataset generally covers at least a portion of the state-action space, and so we expect the condition ((s, a, s') 4 to hold somewhere; the sub-region of the MDP where it holds represents the connectivity graph of the sparsified MDP. This is the region that the agent knows how to navigate using the offline dataset D, and so it is the one that the agent explore further using Tez- More precisely, the sparsified MDP is defined to have identical dynamics as the original MDP on the edges (s, a) -> s' that satisfy the critical condition 4.1 When instead the edge (s, a) -> s' fails to satisfy the critical condition 4.1 it replaced with transition (s, - af to an absorbing state s!.
Definition 4.1 (Sparsified MDP). Let st be an absorbing state, iee. such that P (s" st,,a) = 1 and r(st,a) 0 for all A. The state space in the sparsified MDP Mt is defined as that of the original MDP with the addition of st. The dynamics TPt of the sparsified MDP are defined as
IP(s'| s,)))
if (s, +
Pt s,a)
10 0
Pi(s (s,)s
E 8'40'
P(s' |s,a).
((, < 4.
N(sas"))
(4.2)
For any deterministic reward function r .Sx A + +10, 1], the reward function on the sparsified MDP is defined as r' (ss a) r(s, a); for simplicity we only consider deterministic reward functions.
The empirical sparsified MDP Mt (S
is defined in the same way but by using the empirical transition kernel in eq. (42)). The empirical sparsified MDP is used by our algorithm to design the exploratory policy, while the (population) sparsified MDP is used for its theoretical analysis. They are two fundamental concepts in this paper. By formulating the sparsified MDP, we restrict the transitions and rewards within the area where we know how to navigate, embodying the principle of pessimism. Various forms of pessimistic regularization have been introduced to address the challenges of partially covered offline data. Examples include a pessimistic MDP KKidambi et al., 2020 and limiting policies to those covered by offline data [Liu et al. 2020
4.3
Offline design of experiments
In this section we deseribe the main sub-component of the algorithm, namely the sub-routine that uses the offline dataset 'D to compute the exploratory policy Tex- The exploratory policy Tex is a mixture of the policies π T1, 72 .... ... produced by variant of the reward-free exploration algorithm of Kaufmann et al. 2021 Ménard et al. 20221). Unlike prior literature, the reward-free algorithm is not interfaced with the real MDP M, but rather simulated on the empirical sparsified MDP M This avoids interacting with M with a reactive policy, but introduces some bias that must be controlled. The overall procedure is detailed in algorithm? 2 To be clear, real- world samples are collected by algorithm instead we use the word 'virtual samples' refer to those generated from Mt.
At high level, algorithm 2 implements value iteration using the empirical transition kernel Pt, with the exploration bonus defined in eq. (4.3) that replaces the reward function. The exploration bonus can be seen implementing the principle of optimism in the face of uncertainty; however, the possibility of transitioning to an absorbing state with zero reward (due to the use of the absorbing state in the definition of pPt) implements the principle of pessimism.
5

---

Algorithm 2 RF-UCB (M', Kuchi E,
Input: d E (0,1), O, number of episode Kucb; MDP Mi
1: Initialize Counter n² (8,a) a) = ( (8,,,,, a, 80) = 0 for any (s,a,8) ESx
2: for == 1,, K do
for h = H.HH- 1,1-1,... .......... ,, do for any (h, s,, E [H] 8 A. 5: for (s E S x A do
3:
4:
Set (s,
6:
Calculate the empirical uncertainty U a) using eq. (.4 where @ is from eq. (4.3
7:
end for (8) = arg max (s, Vs E and (T()") =- any action.
8:
9:
end for
10:
Set initial state sf = S1.
for h 1, 1,2, 2.., .... H do Sample a ( ship1 Pl Pi af)
11:
12:
end for
13:
n n++1(s (s,a) n² (s) EnEmh I[(s,, a) = (5 af]]-
14: n n (s,a, = as, - Ene(m L((s,a, = (s at s(+2))
15: end for
Output: Ter Uniform " kk((K
This delicate interplay between optimism and pessimism is critical to the success of the overall procedure: while optimism encourages exploration, pessimism ensures that the exploration efforts are directed to the region of the state space that the agent actually knows how to navigate, and prevents the agent from getting 'trapped' in unknown regions. In fact, these latter regions could have combinatorial structures Xiao et al., 2022] which cannot be explored with non-reactive policies.
n² n a) and n" s') denote the counters for the number of virtual samples simulated from M at each (s, a) and (s, a, s') tuple. We define the bonus function
More precisely, at the beginning of the k-th virtual episode in algorithm 2
H [log(GH (S) |A| /8) + |S] 21)))) I
δ (z, 6)
(4.3)
which is used to construct the empirical uncertainty function U a quantity that serves as a proxy for the uncertainty of the value of any policy æ on the spasified MDP. Specifically, for the k-th virtual episode, we set U/ 11+1 (8, a) = 0 and & E S, a E A. For / E [H]. we further define:
(s) = H min o(n (s. a))} + (t Tmax (
(4.4)
Note that, the above bonus function takes a similar form of the bonus function in [Menard et al. 2021] This order of O(1/z:) is set to achieve the optimal sample complexity. and other works have also investigated into other forms of bonus function [Kaufmann et al.] 2021]. Finally, in line TT through line 12 the current policy which is the greedy policy with respect ii-iis simulated on the empirical reference MDP Mi, and the virtual counters are updated. It crucial to note that the simulation takes place entirely offline, by generating virtual transitions from M Upon termination of algorithm 2 the uniform mixture of policies n' 7 .... form the non-reactive exploration policy Tez, ensuring that the latter has wide 'coverage' over M!
4.4 Online and planning phase
Algorithm 2
implleenns line of the procedure in algorithm by finding the exploratory policy Tex- After that, in line of the interaction protocol the online dataset D' is generated by deploying Tez on the real MDP M to generate Kat trajectories. Conceptually, the online dataset D' and the offline dataset D identify an updated empirical transition kernel and its sparsified version
iP. Finally, in
For any (e, a, e') E S A x S. we define (o' a, m(s.c.aa) if (,,,,,' 2 1 and (a a, O otherwise. mEc.0)
Finally, any (s, E AA, we have (tt a, m E/'s (o...") ms a, s') any a A, we have Piet a..a) 1. Here (e, e') the counter initial offline data and m(..,)) -) the counter online data.

---

B reward function is received, and the value iteration algorithm (See Appendix E is invoked with reward function and IP as dynamics, and the near-optimal policy finel is produced. The use of the (updated) empirical sparsified dynamies IPt can be seen as incorporating the principle of pessimism under uncertainty due to the presence of the absorbing state.
Our complete algorithm reported in algorithm 3 and can be seen as implementing the interaction protocol described in algorithm [
Algorithm 3 Reward-Free Non-reactive Policy Design (RF-NPD)
Input: Offline dataset D, target suboptimality ε >> O, failure tolerance å (0,
1: Construct the empirical sparsified MDP .M
2: Offfine phase: run RF-UCB(MM Kucb, E. 6) obtain the exploratory policy Tex-
3: Online phase: deploy Texr the MDP M for Kde episodes to get the online dataset D'
4: Planning phase: receive the reward function r, construct M from the online dataset D', compute
TI final (which the optimal policy on M') using value iteration (Appendix)
Output: final-
Main Result
In this section, we present performance bound on our algorithm, namely bound on the sub- optimality of the value of the final policy x final when measured on the sparsified MDP M The sparsified MDP arises because it is generally not possible to directly compete with the optimal policy using a non-reactive data collection strategy and a polynomial number of samples due to the lower bound of Xiao et al. [022]; more details are given in Appendix C
In order to state the main result, we let of episodes for the offline simulation and online interaction, respectively. Let C' be some universal constant, and choose the threshold in the definition of sparsified MDP
ucb = Kee where Kueb and K are the number
6H²² log(1211 |s? /8).
(5.1)
Theorem 5.1. For any > and < 1, if we les the number of online episodes be
CH2 S |A|
polylog (1S1. (A, 11
K
then with probability at least 1 - 8, for any reward function the final policy final returned by Algorithm saatisies the bound
max Vı (s:;Ptt,((,)) Vi (s1;Pt, ( S e. aell
(5.2)
The theorem gives a performance guarantee on the value of the policy Tinals which depends both on the initial coverage the offline dataset D as well as on the number of samples collected in the online phase. The dependence on the coverage of the offline dataset is implicit through the definition of the (population) sparsified M which is determined by the counts N(..))
In order to gain some intuition, we examine some special cases as a function of the coverage of the offline dataset.
Empty dataset Suppose that the offline datasct D is empty. Then the sparsified MDP identifies a multi-armed bandit at the initial state $1, where any action a taken from such state gives back the reward r(31, a) and leads to the absorbing state sf. In this case, our algorithm essentially designs an allocation strategy Tex that is uniform across all actions at the starting state 51. Given enough online samples, T final converges to the action with the highest instantaneous reward on the multi-armed bandit induced by the start state. With coverage from the offline dataset, the lower bound of Xiao et al. 2022] for non-reactive policies precludes finding an e-optimal policy on the original MDP M unless exponentially many samples collected.
Known connectivity graph On the other extreme, assume that the offline dataset contains enough information everywhere in the state-action space such that the critical condition 4.1 is satisfied for
7

---

all (s.a, a, tuples. Then the sparsified MDP and the real MDP coincide, i.e., M _M" and so the final policy T final directly competes with the optimal policy x* for any given reward function in eq. (52)). More precisely, the policy Tfnnal is e-suboptimal on .M (11² | /E2 trajectories collected in the online phase, result that matches the lower bound for reward-free exploration of Jin et al. [2000b] up to log factors. However, we achieve such result with a data collection strategy that is completely passive, one that is computed with the help of an initial offline dataset whose size [D] ~ || = (( need not depend on final accuracy E.
Partial coverage In more typical cases, the offline dataset has only partial coverage over the state- action space and the critical condition may be violated in certain state-action -scceeso states. In this case, the connectivity graph of the sparsified MDP M is sub- wub-graph of the original MDP M augmented with edges towards the absorbing state. The lack of coverage of the original dataset arises through the sparsified MDP in the guarantees that we present in theorem 5.1 In this section, we 'translate" such guarantees into guarantees on M, which case the 'lack of coverage" naturally represented by the concentrability coefficient
C sup d (s, a)/aa/////s ((8,a),
8,0
see for examples the papers MMnoos and Szepesvári, 2008 Chen and Jiang 2019 for background
material on the concentrability factor. More precisely, we compute the sample complexity in terms for final to be e-suboptimal with respect to any comparator policy æ, and in particular with respect to the optimal policy म. on the "real" MDP M. The next corollary is proved in appendix B.3
of online as well as offline cumples-requiee
Corollary 5.2. Suppose that the offline dataset contains
S
|A|C
C
samples and that additional
H S IA
22
online samples are collected during the online phase. Then with probability at least 1 1- for any reward function the policy IT final is e-suboptimal with respect to any comparator policy
V1 (sr: V1 (s1; P, r, T finat) S
(5.3)
The online sample size equivalent the one that arises the statement of theorem 5.1 (expressed as number of online trajectories), and does not depend on the concentrability coefficient. The dependence on the offline dataset in theorem 5. is implicit in the definition of sparsified MDP; here we have made it explicit using the notion of concentrability.
Corollary 5.2 can be used to compare the achievable guarantees of our procedure with that of an offline algorithm, such as the canimmxx-otiima procedure detailed in [Xie et al., 2021b]. The proceedure described in [ii al. 2021b achieves
(5.3) with probability least 1 by using
H S H5.5 S
(5.4)
E2
E
offline s In terms of offline data, our procedure has a similar dependence on various factors, but it depends on the desired accuracy through (1) as opposed to Ō(1/²2) which is typical for an offline algorithm. This implies that in the small-s regime, if sufficient online samples are collected, one can improve upon fully offline procedure by collecting a number of additional online samples in non-reactive way.
Finally, notice that one may improve upon an offline dataset by collecting more data from the distribution μ., i.e., without performing experimental design. Compared to this latter case, notice that our online sample complexity does not depend on the concentrabiliry coefficient. Further discussion can be found in appendix B
TTechnically, Zhan al. 2022 considers the non-hommgeneous setting, and expresses their result in terms of number of trajectories. In obtaining eq. (5.4p. we 'removed' H factor due to our dynamics being homogeneous, and add it back to express the result in terms of number of samples. However, notice that [Zhan et al. 2022 consider the reward-awe aware setting, which is simpler than reward-free RL setting that we consider. This should add additional |S] factor that is not accounted for eq. 5.4). see the paper Jin et al. 2020b for more details.
8

---

6 Proof
In this section we prove theorem 5.1 and defer the proofs of the supporting statements to the Appendix
Let us define the comparator policy त. used for the comparison in eq. (5.2 to be the (deterministic) policy with the highest value function the sparsified MDP:
arg max V1 (s1: rr, T).
*EIl
We can bound the suboptimality using the triangle inequality as
Vi (81: Pt, (rr,m()))) - V1 (81; pt,rt, TT finat) S Vi (815 Pr, xx!] - Vi 8815 Ptt ,r,, m²)
+ 1/ $1; ,r,t Ví (s1:Pt, r Fénaal
+ V/2 (sl:Pt,ri T - V (81: 1pt, rt, TT/aaa)))
50
Vi (si:Pi, ,|, - (s;
2 sup r
The middle term after the first inequality negative due to the optimality of final on Pt and rt. suffices to prove that for any arbitrary policy and reward function the following statement holds with probability at least 8
V1 (s1;Pt popt,rt, (r1; Vi (s1; r
(6.1)
2
Estimation erroe
Bounding the estimation error using the population uncertainty function In order to prove eq. (6.I). we first define the population uncertainty function X, which a scalar function over the state-action space. It represents the maximum estimation error the value of any policy when it evaluated on Mt instead of M. For any (s, a) E S A, the uncertainty function is defined as XH+1(8,00 a) == O and for h E (H),
(s,s,, a) == min { H +1; (H) (1 1 11 H
Σ Pel (s' s,
max (Xu+z (8', (x (d, }
a'
We extend the definition to the absorbing state by letting Xn(st, a) 0 for any h E [H] E A. The summation Σ. used above is over s' S [s]], but since Xx(st, = 0 for any h E [M] E A, it is equivalent that over s' E S. Intuitively, (s, a) takes similar form as Bellman optimality equation. The additional (1 +++ H/H) factor and additional term 9/l óm a)) quantify the uncertainty of the true function on the sparsifed MDP and 9/1 ((m(s, a)) will converge to zero when the sample size goes to infinity. This definition of uncertainty function and the following lemma follow closely from the uncertainty function defined in [Ménadd al. 202T).
The next lemma highlights the key property of the uncertainty function X, namely that for any reward function and any policy म, can upper bound the estimation error via the uncertainty function the initial times-step: it is proved in appendix A.2.
Lemma 6.1. With probability 1 - 8, for any reward function r and any deterministic policy n, it holds that
(1 - Pi max (i + C max (81,
(6.2)
The uncertainty function X contains the inverse number of online samples 1/m(s, a) through dim(s, a)), and so lemma 6.1 expresses the estimation error in eq. (6.1) as the maximum expected size the confidence intervals sup, Epi (s,)(s / 11/m(s, a), a quantity that directly depends on the number m(:..) of samples collected during the online phase.

---

Leveraging the exploration mechanics Throughout this section, C' denotes some universal con- stant and may vary from line to line. Recall that the agent greedily minimizes the empirical uncer- tuinty function U to compute the exploratory policy Tex- The empirical uncertainty is defined as for any k. 8 E S, a E and
Uk (841(8,0)
U a) H min ((n (s, a))} PT (max U (
(6.3)
where n (s,, a) is the counter of the times encounter (s, a) until the beginning of the k-the virtual episode in the simulation phase. Note that, (s, a) takes similar form Xx(s,, a), except that (s, a) depends on the empirical transition probability pt while (s a) depends transition probability on the sparsified MDP. For the exploration scheme to be effective, X and U should be close in value, concept which is the core of this work and which we formally state below and prove in appendix A.2.2
the true
Lemma 6.2 (Bounding uncertainty function with empirical uncertainty functions). With prohability at least 6, we have for any 8,,8,a) a) E [H] S x A,
C K
an(s,a) S
E (s,
Notice that XA is the population uncertainty after the online samples have been collected, while U/ the corresponding empirical uncertainty which varies during the planning phase.
Rate of decrease of the estimation error Combining lemmas 6. and 6.2 shows that (a function of) the agent's uncertainty estimate U upper bounds the estimation error eq. 1). In order to conclude, we need to show that U decreases on average at the rate 1/K, statement that we present below and prove in appendix A.2.3
Lemma 6.3. With probability at least 1 - 8. we have
11
Σ
(s)
polylog
(6.4)
K
k=1
Then, for any E > 0, we lake
K CH [S] IA|
1 1 (+118) polyyog (181,141, H1
ē 8
then with probability at least 1 - 8, it holds that
1
K
After combining lemmas 6.1 to 6.3
we see that the estimation error can be bounded as
Vi (s1; .r.,)) T) - Vi ( s1 Pl rl ④T)
< max X2 (81, a) + C,
max X1 (s1,
K
K
C max
Ut a) + K
Σ k=1
(
K
k=1
< 0 (c+
$ Ce
(for 0 < < const)
Here, the constant may vary between lines. Rescaling the universal constant C and the failure probability 6, we complete the upper bound in equation 6. and hence the proof for the main result.
10

---

References
M Mchddi Afsar, Trafford Crump, and Behrouz Far. Reinforcement learning based recommender systems: A survey. ACM Computing Surveys, 55(7):1-38, 2022.
Arpit Agarwal, Rohan Ghuge, and Viswanath Nagarajan. Batched dueling bandits. In International Conference on Machine Learning, pages 89-110. PMLR, 2022.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019.
Nicolo Cesa-Bianche Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems, 26, 2013.
Jinglin Chen and Nan Jiang. Information-theoretic considerations batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051. PMLR, 2019.
Jinglin Chen, Aditya Modi, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. On the statistical efficiency of reward-free exploration in non-linear rl. arXiv preprint arXiv:2206. 10770, 2022.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. In Advances in Neural Information Processing Systems (NIPS), 2015.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507-1516, 2019.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674. PMLR, 2019.
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. In International Conference Machine Learning, pages 2892-2902. PMLR, 2021.
John Duchi, Feng Ruan, and Chulhee Yun. Minimax bounds stochastic batched convex optimiza- tion. In Conference On Learning Theory, pages 3065-3162. PMLR, 2018
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:21 2021.
Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00494 2021.
Zijun Gao. Yanjun Han, Zhimei Ren, and Zhengging Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Omer Gottesman, Fredrik Johansson, Joshua Meier, Jack Dent, Donghun Lee, Srivatsan Srinivasan, Linying Zhang, Yi Ding, David Wihl, Xuefeng Peng, Jiayu Yao, Isaac Lage, Christopher Mosch, Li wei H. Lehman, Matthieu Komorowski, Matthieu Komorowski, Aldo Faisal, Leo Anthony Celi, David Sontag, and Finale Doshi-Vethe Evaluating reinforcement learning algorithms in observational health settings, 2018

---

Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. International Conference on Machine Learning, pages 2681-2691. PMLR, 2019.
Jiawei Huang. Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie- Yan Liu. Towards deployment- efficient reinforcement learning: Lower bound and optimality. arXiv preprint arXiv:2202.0664 06450, 2022.
Nan Jiang and Jiawei Huang. Minimax value interval for ofllcy evaluation and policy optimization. Advances in Neural Information Processing Systems, 33:2747-2777 2020.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4877 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870-4879.
PMLR, 2020a.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning (ICML), 2020b.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? arXiv preprint 20/2::20//22.0885 2020c.
Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 33:1253-1263, 2020.
Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon in off- foff-policy evaluation with double reinforcement learning. Operations Research, 2022.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pages 865-891. PMLR, 2021.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model- based offline reinforcement learning. arXiv preprint arXiv:2005.05951, 2020.
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 23(6):4909-499 2021.
Allison Koenecke, Andrew Nam, Emily Lake, Joe Nudell, Minnie Quartey, Zion Mengesha, Connor Toups, John R Rickford, Dan Jurafsky, and Sharad Goel. Racial disparities in automated speech recognition. Proceedings of the National Academy of Sciences, 1 177(14)7684-7689 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Gen Li, Yuling Yan, Yuxin Chen, and Jianqing Fan. Optimal reward -cward-agnostic exploration rein- forcement learning. 2023a.
Gen Li, Wenhao Zhan, Jason D Lee, Yuejie Chi, and Yuxin Chen. Reward-agnostic fine-tuning: Provable statistical benefits of hybrid reinforcement learning. arXiv preprint 2305 2023b.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.08202, 2020.
Jihao Long, Jiequn Han, and Weinan. An 12 analysis of reinforcement learning high dimensions with kernel and neural network approximation. arXiv preprint arXiv:2/04.07794, 3, 2021.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza-
tion. arXiv preprint arXiv:0907.37700, 2009.
12

---

Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration reinforcement learning. In Interna- lional Conference on Machine Learning, pages 7599-7608. PMIR, 2021.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient tich-observation reinforcement learning. In International conference on machine learning, pages 0961-6971. PMLR, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):52-533, 2015.
Rémi Munos and Csaba Szepesvári. Finete-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprint
2019.
Thanh Nguyen- Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance- dependent bounds for offline reinforcement learning with linear function approximation. arXiv preprint (tt:::2//1.132000 2022.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1994. ISBN 0471619779.
Dan Qiao and Yu- Yu-Xiang Wang. Near-optimal deployment efficiency in reward- reinforcement learning with linear function approximation. arXiv preprint arXiv:2210.0070) 2022.
Dan Qiao, Ming Yin, Ming Min, and Yu- Yu-Xiang Wang. Sample-efficien reinforcemnnt learning with loglog (t) switching cost. In International Conference on Machine Learning, pages 18031-18061. PMLR, 2022.
Dan Qiao, Ming Yin, and Yu-Xiang Wang. Logarithmic switching cost in reinforcement learning beyond linear mdps arXiv preprint 230.. 2023.
Shuang Qiu, Jieping Ye, Zhaoran Wang. and Zhuoran Yang. On reward free rl with kernel and neural function approximations: Single-agent mdp and markov game. In International Conference on Machine Learning, pages 8737-8747. PMLR, 2021.
Paul Raccuglia, Katherine C Elbert, Philip DF Adler, Casey Falk, Malia B Wenny, Aurelio Mollo, Matthias Zeller, Sorelle A Friedler, Joshua Schrier, and Alexander J Norquist. Machine- learning- assisted materials discovery using failed experiments. Nature, 533(7601):73-76, 2016.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. arXiv preprint arXiv:2103. 12021, 2021.
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang. Stuart Russell, and Jiantao Jiao. Optimal conser- vative offline rl with general function approximation via augmented lagrangian. arXiv preprint arXiv:2211.00 100116 2022.
Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 74, 2021.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT Press, 2018.
Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-aware regret bounds for undis- counted reinforcement learning mdps. In Algorithmic Learning Theory, pages 770-805. PMLR, 2018.
13

---

Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage, 2021.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward- free rl is no harder than award-aware rl in linear markov decision processes. In International PMLR, 2022.
Conference on Machine Learning, pages
Martin J Wainwright. High-dimensions statistics: non-asymptotic viewpoint, volume 48, Cam- bridge university press, 2019.
Ruosong Wang, Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances neural information processing systems, 178266 2020a.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010. 1000000/1199 1895, 2020b.
Tianhao Wang. Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances in Neural Information Processing Systems, 34:13524-13536, 2021.
Chenjun Xiao, Ilbin Lee, Bo Dai, Dale Schuurmans, and Csaba Szepesvari. The curse of passive data collection in batch reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 8413-8438. PMLR, 2022.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. arXiv preprint arXiv:2008. 000,99000..09990 2020a.
Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, pages 550-559. PMLR, 2020b.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Dellman--onsisten pessimism for offline reinforcement learning. arXiv preprint arXiv:2 06926, 202
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg-
ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395-27407, 2021b.
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint arXiv:2205.155122 2022.
Zhiyuan Xu, Jian Tang, Jingsong Meng, Weiyi Zhang. Yanzhi Wang, Chi Harold Liu, and Dejun Yang. Experience-driven networking: A deep reinforcement learning based approach. In IEEE INFOCOM 2018-1EE2 conference on computer communications, pages 1871-1879. IEEE, 2018.
Tsung-Yee Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J. Ramadge. Accelerating safe reinforcement learning with constraint-mismatceed policies, 2021.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off off-policy evaluation for tabular rein- forcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3948-3958. PMLR, 2020.
Ming Yin, Yu-Xiang Wang, Yaqi Duan, and Mengdi Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism.
Ming Yin, Bai, and Yu-Xiang Wang. Near optimal provable uniform convergence off-policy evaluation for reinforcement learning, arXiv preprini arXiv:2007.03760, 2020.
Ming Yin, Mengdi Wang, and Yu-Xiang Wang. Offline reinforcement learning with differentiable function approximation is provably efficient. arXiv preprint arXiv:2210.00750, 2022.
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: survey, ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
14

---

Andrea Zanette. When is realizability sufficient for off off-policy reinforcement learning? ICML 2023, 2023.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312 7312. PMLR, 2019.
Andrea Zanette and Martin J. Wainwright. Bellman residual orthogonalizztion for offline reinforce- ment learning. 2022. URL https: //rxpi wrg. 2abb//203.. 12786
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33:11756-11766 2020.
Andrea Zanette, Kefan Dong, Jonathan Lee, and Emma Brunskill. Design of experiments for stochastic contextual linear bandits. Advances in Neural Information Processing Systems, 34: 22720-22731, 2021a.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 34:13626- 13640, 2021b.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason D Lee. Offline reinforcement learning with realizability and single-policy concentrability. arXiv preprint arXiv:220.004634 2022.
Ruiqi Zhang, Xuezhou Zhang, Chengzhuo Ni, and Mengdi Wang. Off-policy fitted q-evaluation with differentiable function approximators: Z-estimation and inference theory. In International Conference on Machine Leurning, pages 26713-26744 PMLR, 2022.
Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems, 33:1 1734-173111111 1743, 2020a.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantaee decomposition. Advances in Neural Information Processing Systems, 33: 15198-15200 2020b.
Zihan Zhang, Simon Du and Xiangyang Ji. Near optimal reward-free reinforcement learning. In International Conference on Machine Learning, pages 12402-12412, PMLR, 2021.
15

---

Contents
Introduction
2
Related Work
3
Setup
3.1
Interaction protocol
A Algorith:: balancing optimism and pessimism for experimental design
Intuition
4.2
Sparsified MDP
Offline design of experiments
4.4
Online and planning phase
5
Main Result
6
Proof
Proof of the main result
18
A.I
Definitions).
18
A.1.I
Sparsified MDP
18
A. 1.22
High probability events
19
A.1.3
Uncertainty function and empirical uncertainty function
20
A.2
Proof of the key theorems and lemmas
21
A.2.1
Uncertainty Functions upper bounds the estimation error
21
A.2.
Proof of lemma16.2
22
A.2.3
Upper bounding the empirical uncertainty function (Jemma 6.3
23
A.3
Omitted proofs
25
A.3.1
Proof for lemma A.4 4 (high probability event)
25
A.3.2
Proof for lemma
14 (property of intermediate uncertainty function)
26
A.3.3
Proof for lemma A. 15 and lemma A. 16 (properties of uncertainty function)
28
A.3.4
Proof for lemma 7 lemmal A.18 18 lemma A.19 lemma A. 20 properties of bonus function)
29
A.3.5
Proof for lemma
A.21 and lemma A.22 properties of empirical sparsified
MDP)
Additional comparisons
33
Comparison with other comparator policy
33
B.2
Comparison with offline reinforcement learning
33
B.3
Proof of corollary 5.2
35
Proof for lemma B. and lemma B.2
38
Lower bound
39
16

---

D Technical lemmas and proofs
40
Details of the planning phase
42
More related works
42
17

---

A Proof of the main result
A.1 Definitions
In this section, we define some crucial concepts that will be used in the proof of the main result.
A.1.1 Sparsified MDP
First, restate the definition 4.1 in the main text.
Definition A.1 (Sparsified MDP). Let 8 be absorbing state, i.e., such that IP [st| aa) -1 and rstt a) 0 for all A. The state space in the sparsified MDP M is defined as that of the original MDP with the addition of st. The dynamics TPt of the sparsified MDP are defined as
IP(s' s,
if (s, 2 +
Pt(s' s,
1
Pi(s
Σ S'S N(sa,,))
P(s' ss,)).
if N(8,a,8)) Φ;
(A.1)
For any deterministic reward function r: S A - [0, 11, the reward function on the sparsified MDP defined as (x, a) = r(8, a); for simplicity we only consider deterministic reward functions.
In the offline phase of our algorithm. we simulate the virtual episodes from the empirical version of sparsified MDP (See Algorithm 2 Now we formally this MDP.
Definition A.2 (Emprical sparsified MDP). Let st be the absorbing state defined in the sparsified MDP. The state space in the empirical sparsified MDP M is defined as that of the original MDP with the addition of st. The dynamics Pst of the sparsified MDP are defined
Nis.a.e)) N(s,a)
N 5) + if ())
N(8,a,8))
PP'('' 18,0)
PT 18,0)= =
E s'
N(s,
N(s.,s')co
(A.2)
For any deterministic reward function S A [0, 1), the reward function on the empirical sparsified MDP is defined (s, r(s, a): for simplicity only consider deterministic reward functions. Here, the counters N(s,a) and (s,, a, s') are the number of (8, a) and (s, a, s') in the offline data, respectively.
Finally, in the planning phase, after we interact with the true environment for many online episodes, construct fine-estimated sparsified MDP, which used to extract optmal policy of given reward functions. We formally define it below.
Definition A.3 (Fine-estimated sparsified MDP). Let s be the absorbing state defined in the sparsified MDP. The state space in the fine-estimated sparsified MDP M is defined as that of the original MDP with the addition of st. The dynamics jpt of the sparsified MDP are defined as
mis.a.5') m(s,a)
if N a, s') + N(s,a,
m(s, a, s²)
(s' s,
Pt(s s,,)=
Σ s'
m(s 0.)
N(s.a,E")<
(A.3)
For any deterministic reward function : A- 10, 1), the reward function on the fine-sstmaaed sparsified MDP is defined r' (s, r(s, a): for simplicity we only consider deterministic reward functions. Here, the counters (s, and N(8 8') are the number of (8, a) and (8, a, s') in the offline data, respectively, while m(s,a) a) and m(s, s, a, s') are the counters of (s, a) and (s, a, s') in online episodes.
18

---

A.1.2 High probability events
In this section, we define all high-probability events we need in order to make our theorem to hold. Specifically, we define
: a's,a,s') s.t. N(s,a,s) 2, Pt(s' s,
Pt('' s.
27 8,a) a(s,a)
12|5| |A]
14
12 12 AA
log
log
(N(s,a)
8
66 |||
8² VscEN
Σ
Σ
d (s, HIn
2
icc kE[H]
611 |S |||
89 (
22
Σ
Z as, Hin
8
scc KE
: ((s,a) xx A,KL (BB
6 665 |A|
) +|S| e (c(1+ m(s, a)
$ m(s,a)
log
[s]
6H (||AAA
80 = V(s.a) [H] x Sx A, 2 7 Kde
Σ hE(H]
white (s, a) H In
8
where
Kuch
wh miz (s, a)
= Kucb
d (s,a).
Here, ( denotes the Kullback Leibler divergence between two distributions. Kusb is the number of episodes of the sub-routine RF-UCB and N is the policy executed at the i-th episode of RF-UCB (See algorithm
2). Kae is the number of episodes executed in the online phase. n (s, a) is the counter of (s, a) before the beginning of the k-th episode in the offline phase and m(s, a) is the number of (s, a) samples in the online data (See definitions in section A. We denote dz (8, a), (s. (s, a) and d' (s, a) as the occupancy measure of (s, at stage h under policy n, on P (the
(s. true transition dynamics), pf (the transition dynamics in the sparsfied MDP) and (the transition dynamics in the empirical sparsified MDP) respectively.
For the event defined above, we have the following guarantee, which is proved in appendix A.3.
Lemma A.4. For 8 > 0, we have
:= U U8 UELu8T
happens with probability least 1 5- 6,
19

---

A.1.3 Uncertainty function and empirical uncertainty function
In this section, we restate the definition of uncertainty function and empirical uncertainty functions, as well as some intermediate uncertainty functions which will be often used in the proof. First, we restate the definition of bonus function.
Definition A.5 (Bonus Function), We define
H
)) 6H [S] ( + |S| log (c(1+ 2. 5)
(xx)
log
(A.4)
Further, we define
((x) = min {1. Ho(r)}
(A.5)
Next, we restate the definition of uncertainty function and empirical uncertainty function. Notice that the uncertainty function does not depend on reward function or specific policy æ. Definition A.6 (Uncertainty function). We define for any (h, s, a) E [H] x and any deterministic policy
Xu+1(8, a) = 0,
(x( == min - h 1, + 1+ H
=min
Pi (-18,a)T (max Xa+1 (..d))
where we specify
Pt(. (,))) (max (Xn+1
--Pi Pi' (s' s, max (Xu+1 (5', d')))
In addition, we define (a a) for any h E [H] A. Here, the notation E. above means summation over s' S {st] st.. But since (n a) 0 for any h [H] A, this is equivalent to the summation over 8 E S. Pt is the transition probubility of fine-estimated sparsified MDP defined in section A.I.I
Then, for the reader to better understand the proof, we define some intermediate quantity, which also measure the uncertainty of value estimation, but they may be reward or policy dependent.
Definition A.7 (Intermediate uncertainty function). We define for any (h,8,0 [H] S A and any deterministe policy
W (
8 (m(s, a)) Var (1F(0a)) (Veta (st:Pt,
(7,,,, = min
:mmin
H h + 1, V H²
-9H0 (HH, + 1 4)
( ( W Wi
where
( ( (s,) = ΣΣ
P (s' 5. (a' 1s')
(d'ls')) Wht (s',d'r))
In addition, we define WT a,r) 0 any [H) a A and any reward function r. Here, 1l is the transition probability of fitte-estimated sparsified MDP defined in section A.1.1
The intermediate function W is reward and policy dependent and can be used to upper bound the value estimation error. Further, we need to define some -deeedede version of the uncertainty function, denoted as X (s, a), as well as another quantity Y (s, a, r) Definition A.8. We define X (3, a) (
as a.r) r) = for any n, r, 8, a and
X (8, a) = min H + 1,9H (m(s,))) + 1+ :
( ( Xh Xh+r(0,a)
20

---

8 (s, = /
(Vati (st; (1+ H #)
(Fiznts) Viti
H2 (m(s, Var (InF)(aa)
where
(1 X Xh-1 = ΣΣ
pi 3,0) (a' ss) Xh+1 (s',a';;
5'
(flTAT)) Yhe (s,
ΣΣ ss,) Th+1 (a' s') Yht1 (s'.a',r))
a²
a,,) for any A, E [H] and any reward r, any policy n. Here, pi is the transition probability of entemmettdated sparsified MDP defined in section A.I
In addition, we define -
Finally, we define the empirical uncertainty functions.
Definition A.9. We define U (8, a) = 0.for any k E [Kuch] and E S,a a E A. Further, we define
Us a) H min {1, (s, + as) (max Uh+1 (::a)))
(A.6)
where & is the bonus fanction defined in eq. (A.4) and ne (s, a) is the counter of the times we encounter (s, a) until the beginning of the k-the episode when running the sub-routine RF-UCB in the offline phase.
A.2
Proof of the key theorems and lemmas
A.2.1 Uncertainty Functions upper bounds the estimation error
Proof. This proof follows closely from the techniques in [Ménard et al. 2021 but here we consider the homogeneous MDP. We let d (s, a) be the probability of encountering (s, a) at stage / when running policy on Pt, starting from Now we assume & happens and fix a reward function r and policy и. From lemma 14 we know
Vi 91; Pr rt, (T) Vi (s1; Pt, (tt,tt (t)
S Qn (s1, (a1): -Qn (51, (I S (5 (s))).)),
where WT (s, a, is the intermediate uncertainty function defined in definition A.7 Here, we use the policy-dependen version of uncertainty function W a) which will then upper bounded using another two policy-dependent quantities X7 (s. a) and (s, a, r). We define these policy- dependent uncertainty functions upper bound the estimation error of specific policy, but since are considering reward-free setting, which entails a low estimation eπrоr for any policy and reward, these quantities cannot be directly used in the algorithm update the policy. Next, we claim
WX (7, (s,a. r) & (s, a) + Y (s,a,r) a)
where (s, a) and (7, a, r) are defined definition A.8 Actually, this is easy from the definition of X2 (s, a). Y, (s, a, and WT (s, a, r). For h = H I, this is trivial. Assume this is true for + 1, then the case is given by the definition and the fact that min {z, y 2 S min {x, y) + for any x, y, 0. Therefore, we have
Vi (s:
Vi (sn: rt. (i,, Y (81, (s)).))
(A.7)
Next, we eliminate the dependency to policy and obtain an upper bound of estimation error using the policy-independen uncertainty function X,, (s, a). This is done by bounding Y;" (s1, ग (31). by X (s. a) and then upper bounding X (s, a) by X₁, (s, a). From definition A.8 the Cauchy- Schwarz inequality and the fact that E [0. 1]. we have for any reward function and any deterministic policy t.
(5L, (()).))
21

---

H
(s,a)
1+
1 H
h-1
H o (m((, a)) Var Va (s.a)
(Vh+1 (s;1111,1 rl ,
x))
8.0 h=1
(Induction by successively using the definition of Y)
8
7 (3, Var ( (Vo+t (s::Pi, (st:Pirl,z))
ΣΣ h=1
(s, (s) a) (m(s, a))
H
h=1
(Cauchy- Schwarz Inequality)
H
N
e H
8
A.h (s,a).
ΣΣ (1,
5,a h=1
8,a h=1
Se
8
J (s, (s, aa (m(s,a)).
1=1
We notice that the right hand side of the last inequality above the policy value of some spe- cific reward function when running π on P. Concretely, if the transition probability is I and the reward function at (s, a) is & (m(ssa) a)), then the state value function at the initial state $1 is E., Σ L (s, a) (m(s, a)). This specific reward function is non-negative and uniformly bounded by one, holds that E,, Σ (s, a)o (m(s,a) a)) H - h 1. Moreover, from the definition of & and (eq. (A.4)) ), we know ø (m(s, a)) & Hő (m(s, a)) Then, from the definition
of Xx(s, a) in definition A.6 we apply an inductive argument to obtain
H a (s, a) (m) a)) s (s)
ΣΣ 8,0 h=1
(
for any deterministic policy æ. So have
( (1 2VV2
Therefore, combining the last inequality with (A.7). we have
Vi (s1; 1 ạ Vi (81; Pl, rr,, m)
S X1 (81, (I))) 2/2e (s mi (s1)).
From the definition (n,s,, a) (definition A.6 and Xx (s, a) (definition A.8 we can see ( a) $ as,
for any (h, s, a) and any deterministic policy क. Therefore, we conclude that
vi (s.: rl.T) Vi (s1: m) $ Xi क. (s +222 (1s),
< max (1( 2/22, max X1(s1,
A.2.2 Proof of lemma 6.2
Proof. It suffices to prove that for any i E [K], h E [H) E S, S, E A, it holds that
1 3(H-N)
(s < 1
(s,
H
since the theorem comes from average of the inequalities above and the fact that (1 1 Se. For any fixed k; we prove by induction on When H 1, both sides are zero by definition. Suppose the claim holds for h + 1; we will prove that it also holds for h. We denote Kues as the
22

---

number of virtual episodes in the offline phase. From lemma A.16 the decreasing property of have
6-)mmm A.17 and lemma A.21
(n(8,a) a) s CHo (n (8, + 1+ H
max (Xnti(+e))) (Lemma A. 16 Pt( (1,8)
a'
2
(s,
+
1+
[max (oxx((((())))) P (- (,1,,a)'
(Lemma A.17
H
o'
3
1
1
maxx Pt (-18,a)
(Xo+1(;,d))
a'
(Lemma A.21 and 2/H S (1+1/H))
The inductive hypothesis gives us for any s',
max (Xnti(s(,a()) sc (1 1
3(H 3(H-h-1)
max U (
H
which implies
3(H-h)
Xn(s,a) & CHO (n* + 1
Pt ssa) max {u (
H
3(H-N)
<c
1 H
HH (n))aa)) Pt( (8,a)
mmax { (Uk=)()aa))]] (A.8)
Again, by definition of X,, a). have
1 3(H-h) (1+
(x S -
H.
(A.9)
H
Combining A.88 and (A.9), well the definition of Uă (definition stage h and we conclude the theorem by induction.
A.9
prove the case of
A.2.3 Upper bounding the empirical uncertainty function (lemma 6.3
Proof. First, are going prove
K
| K
(H|S||AA 8
(c(1+
KH [S]
)) log 1
HK [S||A] (A.10)
Σ (s)
log
+ +|s|
K
From the definition (see algorithm 2}. we know an important property of uncertainty function is that Th is greedy with respect to U So we have
(s, H min (1, øb (n a))) + (s, (max Uk (,,')) H min (1, Φb (n (s, a))} + Σ Tpt(s' 18, (a' 1s') Uh (8' a').
Therefore, we have
Kuch
Σ a))
Kuch
km
Kueb
max Uit (s),a)
Kuch
Kueh
H
L (8, min (1, (s)
(definition A.9
K uuch
1= (2,0)
23

---

6H (HAS)A
+ +S| log (o (c(1+ Kuoh H
11 K Kuch
c (s,a)
log
Σ
Kuch
[
(s,a) max 1, - ii-1 2 kee [ xi (8,a)
(lemma A.20
We apply Lemma D.7 and Jensen's Inequality obtain
Kueb
a (s,
max {1, Ei -i Eneim a (s.a)
ME[H]
(s,a)
Kues
<4
log
1
i (8,0)
(lemma D.7
(8,0)
iml
NE(H]
Kubb
<4 |4 |4| log
1+
Σ
S |A|
he(H] (a,0)
H. K ueb
14|8||A||oo
|S] |A|
Inserting the last display to the upper bound, we conclude the proof of the upper bound on U. Then, to prove the sample complexity, we use lemma
D.8 We take
64H²
LA
6H|S||A 5
+ |S| and Kucb [8]
B
log
82
in Lemma D.8.
From lemma D.8 we know there exists a universal constant C₁ such that when
x 2
it holds that B log(1 + I) (1 + log(1 + x)) I I, which implies whenever
64/1² [8] |A|
6// S) (
Kuch
log
+ |
6²
5
it holds that
64H2|S||A4
(HAS|A
Kueb S
Kub
)]
log
+15|
log
1 +
+ log
1
SEa (A.11)
Knob
[|
For notation simplicity, we define
(GHSSAA)
L= 16 [S] [A|
log
|S|
8
Comparing the left hand side of (A.II and the right hand side of AA.0 we know
Right hand side of (A.10)
16// |
HK ueb
(HHSSIAA)
1+ Kueb
)
log 1+
log
+ +1S1 + S) log
Kneb
[S] [A|
6
[S]
16/1² |S|||
Kucb
6/H S||A
1 Kuoslll } )
log(H) + log
1
log
+ [S|
+ |S| log
Kucb
[S]
5
[S]
16H² |S||A|] log(H) + log
Kuets
6.H (SIA
ncch
1+
log
+ |S|
1 + (1) + log
11
Kneb
[S|
5
[
Kuet
)]{
Kuch
log(H) H) + log 1+
1 + log( H) + log
1+
Kueb
[S]
|
It is easy to see that (f)( < log (1 + Kues/ (SI), so the right hand side of last inequality is upper bounded by
4L log
Kueb
Kueb )]
1+
1 1ogo log
11
K Kwob
[S]
[
24

---

From (.III we know this is upper bounded by =² as long as Kueb 2 4L/s². From the definition of L and equations (A.10) A.III. we have when Kach 2 4L/E², it holds that
Kuch
U (s1, a) I right hand side of A.10 I left hand side of A.11 S
K
In conclusion, this admits a sample complexity of polylog (15), |A|, H. = 8
Kuch = CH2 |A|
1 -12 (15).1A),H,,
++ |S|
62
A.3
Omitted proofs
A.3.1
Proof for lemma A.4 (high probability event)
The lemma A.4 is proved by combining all the lemmas below via a union bound. Below, we always denote N 0, 8') as the number of (s, s') in the offline dataset.
Lemma A.10. ed holds with probability at least 1 - 6/6.
Proof. For any fixed (s, a, s') such that a(s.a, 2 4 we denote n, a) as the index of the i-th time when we visit (s, a). For notation simplicity, we fix the state-action pair (s, a) here and write n,(s,o) a) as simply for = 1, ..., (s,, a). Notice that the total visiting time (s,, a) is random, so our argument is based on conditional probability. We denote X; = 1 (s', = =s) as the indicator of whether the next state is s' when we visited (s, a) at the i-th time. From the data generating mechanism and the definition for the reference MDP, we know conditional on the total number of visiting (s, a) and all the indexes 7, S S (N((s.)): it holds that X1, X2,,, independent Bernoulli random variable with successful probability being Pt (s' s, s, We denote X as their arithmetic average, Using Empirical Bernstein Inequality (Lemma D.3), and the fact that N(sa))
are
(X: x)² N(s.a)
N(sa)) X²
X; Pi a), we have ==== E i=1
((.aa)
[(s.0)
N[s.aa
F (E n. (1 ((s5s N(s, a) = 1-666. 8/6.
((s
Taking integral of the conditional probability, we conclude that the unconditional probability of the event& E is at least 8/6. Therefore, we conclude.
Lemma A.11. For 8 0, it holds that P (E*) 2 -866.
Proof. Consider for fixed triple (s, a) E x A. Let m(s a) denote the number of times the tuple (s,a) was encountered in total during the online interaction phase. We define X, follows. For < m(s, a), we let X; be the subsequent state when (s, a) was encountered the i-th time in the whole run of the algorithm. Otherwise, we let X; be an independent sample from Pt (s, a). By construction, (X,) is a sequence of i.i.d. categorical random variables from S with distribution IPf (. 8, 8,a). We denote Ptt = Σ = ōx, as the empirical probability mass and P as the probability mass of X,, Then, from Lemma D.4 we have with probability at least 1 - 5/6, it holds that for any i E N,
KL (P - log (9)
+ |S| log (e (1+ [8]
(5) )
which implies
KL (P):
1 a) log
6 |S] log (e ((1 m(s.a) a)
[
Using union bound for (s,a) E S x A, we conclude.
25

---

Lemma A.12 (Lower Bound on Counters). For 8 > O, it holds that IP (E²) 2 1 - 5/6 and P (EE5) 2 1 8-666. 8/6.
Proof. We denote nř, as the number of times we encounter (s, a) at stage before the beginning of episode k. Concretely speaking, define n (s, a) for any (h, 8, s, Then, define
(s, a) = (s, a) (s,, a) = (5 ax)
We fixed an (s, a, h)) E [H] x S x A and denote F& as the sigma field generated by the first k: - episodes when running RF-UCB and X 11 [( a = (s, a)] Then, we know X Fk+1 measurable and E [Xx F&] = d. a (s,a) a) is F2 meaasuabae... Taking W In (6/6) in Lemma D.1 and applying a union bound, we know with probability 8/6, the following event happens:
Ak E N, sh) E [H] x. (s a) 2 Σ 2 (s, - In (6 (6H|S) IA ick
|SH|S|
2
To finish the proof, it remains to note that the event above implies the event we want by summing over & [H] for each & E N and each (s, a) E S x A. For the E the proof is almost the same. L
Lemma A.13 (Upper Bound on Counters). For > 0, it holds that IP (E3) 2 1 5/6.
Proof. We denote nf, as the number of times we encounter (s, a) at stage before the beginning of episode k. Concretely speaking, we define n) (s, a) = for any (h, s, a). Then, we define
(s, a) (s, + [(8, a) (5 a
We fixed an (s, a, fi) E [/]] x 8 x A and denote Fg the sigma field generated by the first k 1 episodes when running RF-UCB and X T [( at) (s. w)] Then, we know X5 is Fk++1
measurable and E [X Fi] = Th a (s,a) a) is meeasuuuable.. Taking W = (6/5) in Lemma D.2 and applying union bound, we know with probability 5/66, the following event happens:
Vk E N, 8, E x ()) $ IT - In 6/H SIIA!
8
i<k
To finish the proof, it remains note that the event above implies the event want by summing over h E [H] for each E N and each (s, a) E x A.
A.3.2 Proof for lemma A.14 (property of intermediate uncertainty function)
Lemma A.14 (Intermediate Uncertainty Function). We define for any (h, 8, [H] S and any deterministc policy
W (7,)(s,u,r):== :=
(Z, = min h + 1, 1122
=minn
a)(s,a)) Var (a((,a)))) (Vita (s:.Pr,
( ( W Witr(s,
19H0 + 1+
H
where
(Pl Th+1
WT (s, == ΣΣ S (s' (s Aht1 (a' (s') W (s',d)r).
In addition, define WT (st r) 0 for any h [H) A and any reward function r. Then, under for any (h, s, a) E [H] x A, any deterministic policy n, and any deterministic reward function r (with its augmentation r(), holds that
|Qn (s. a, Pr (rt,, Qn (8, ptt pt.rtttttt. (.,,,,,))) m) (g
26

---

Proof. We prove by induction. For h = H + 1, we know WH+1(s.a.1) left hand side of the inequality we want also vanishes. Suppose the claim holds for h and for any The Bellman equation gives us
(s. r) = 0 by definition and the
A = Qb Clo;;PPrrt, Qu (s, a. .t..P,,,.) = E PP (s' (, - Ipt (s' | s. s.a)) Vh+1 (s'; (tt,,,, ,r,,x)
PT
Pl (8' (8'1 Vi+z ( (8:Pt,rt, m)
Va+1
11
Under E, we know that KL (tt: S H o (miss a)) for any (s, a), so from Lemma D.5 we have
5 V " o (m((s,)) a)) (arg.-Pr(s.)) (Vh+1 (s'; rl, x)) + " (1I - 11) -H1
2
(m(s,a))
H
2 s V 1 / (m(ss, (m(ss a)) Varg:>P((aa) (Ve+1 (Pt rt. m)) + 3 (m(s, a)),
where @ is the bonus defined as (A.4p. Here, let f in Lemma D.5 be Vh+1 (s'; Pt, (t';Pt,ri,,) range will be H h and the upper bound for KL divergence is given by high-probability event E. We further apply Lemma t to get
.). So the
Var, (ot,,)) (Vu+1 (s':P), rl, m)) s Var (ar())))() (Va+1 (s': ,r m)) + 4H0 (m(s, a))
and
Var, (atrr))())))) (Vh-1 (s/: ,t,,)) S 2 Var Var (((a)) (Votz (:IP,,(,x))
+2H Σ 1 (s' s))) Vn+i (s: .)) Vn+i
Therefore, have
| s 3 (m(ss
8
o a)) Var (e,,)) (Vati (s::B,rl, + 86 (m((s))) a))²
H
1/2
+80(mms a))
Σ pt (s') a, Vi+1 S'.pt.rt, Vi+1 (s': x)
Using the fact that vx + US V + Vi and yay I 2 we obtain
=tv for positive x, y, and the definition of II,
MI V V (m(s, Var (s. (Vats (t: + 6H0 (m(s, a)) + H |111
which implies
A S v
f
8 o (m)s,a)) Var (rt(sa) (Vit2 (s::P,,r,,)) m)) ( (m((s a))+ 11 (1+
1 H) I.I.
If H (m(s, a)) S 1, then we have by definition
8 H
Hの (m(s,a)) Var (ar (Vits (c: (HT + (1+ H mM
A S
V
H2 o (m(s,a), Var (o.)) (Vnti .))) + (mH + 1+ HH
1
[II]
by definition. Otherwise, H (m(s, a)) 2 1, we have
H ( a)) Var Varswnt(ss,)) Vi+t (8 St .T) < (8Ho(m(s,a)) a)) S 3H0 (m(mm a)).
8
27

---

Therefore, we have in either case
| S V H² ã (m(s,a)) Var (saa) (Vitz sr;Pt,
8
ri,,,r,,, (st +9HH (9H (1+ H
The induction hypothesis gives us that
| S ΣΣ pt (s' s. Ta (a' I 80) Qutz (s', - Qu+1 (s','; ,,,,,
< <(PTTan)) W Wh+1(s,ar))
Inserting this into the upper bound of An, we prove the case of h by the definition of W (8, a,r) and the simple fact that A H h +1
A.3.3 Proof for lemma A.15 and lemma A. 16 (properties of uncertainty function)
In this section, we prove some lemmas for upper bounding the uncertainty functions (s, a). We first provide basic upper bound for (s, a). The uncertainty function is defined in definition A.6
Lemma A.15. Under the high probability event & (defined in appendix A.1.2 for all sh, [H] x S x A, holds that
(n S 11H min (1,((m()))))) + (1+ 2 pt (.),,a) (max Xn+i(;
In addition, for = 8t, from definition, we know the above upper bound naturally holds.
For any fixed (h, a) E [W]] 8 x A, from the definition of the uncertainty function, we know
Proof.
(s, - 9H6 (m)) + (1+ P (-18,a) max Xx+1(+,a))
H
To prove the lemma, it suffices to bound the difference between PP (. s, a)) (maxa (++1(,,a) and Itt (- a, (max. a')) Under E(which happens with probability at least - 5), it holds that KL (PA. (- (,)s)))PPP) (- (a) S # (m(s, a)). Applying Lemma D.5 and a simple bound for variance gives us
Ptt (. s,a) mmax Xntzl(,a)) - pt (,) (naxXx+i(:a))
Vargwwtt(aa)
(maxXn+ (6' & (m((,
2 (m(s,a))
H
2 pt (. (.18,a)" Xn+ (
30 (m(s,a))
(m((s
3
H
2 2 plt (. (1))a) (aax (maxX (nxxx HÓ (m)
3 o (m(s,a))
H1
1
$ pt s,
(max (n+xl:aa)) + 2H (m(s,a)).
The last line comes from Vab 2th for any positive a, b, and the fact that 1 HHo(m(s, a)) 2n (o(m(s,a) a)) < 2H 2Ho(m(s, a)). Insert this bound into the definition of (n a) to obtain
2t) pt (.)s,a) (maxxx++1(,d))) Xn a) & 11 (m(ss + 1+ и
Noticing that (s, < h +11 11H, we conclude.
28

---

Lemma A.16. There exists a universal constant C 2 1 such that under the high probability event E, when 3K Ke we have for any (h, s, a) [H] S A, holds that
(n) CH Kuch @ (n + (1 H
2
Pl (.(.1s.))
(max (X
Kde
In addition, for = from definition, we know the above upper bound naturally holds.
Proof. Here, the universal constant may vary from line line. Under &, have ())
CCHo(m(s,o)) + (1 1 H
pt s,a)
max Xnx)(.a))
(definition)
2
SCH min (1, (m(s, +
1+ pt( s,a) (max (Tax(((nt(( (Lemma A.I5
SCHól Kde
Σ
wh
whith (s, (8,
2 pi (.1s.a)T mmax (Xutzl;,a)))
he[H]
(Lemma A.18
Kucb
-CHo
Kie
Σ
d deanlral) + (1+
2 H
pl P1(118,))
s,a) maxx (Xn+s(:
Kweb
k= hE(M)
(definition)
Kues
Kie
<CHó
Σ
d x" (e
+
1+ H
P1( (-|ssa) (max (X
3Ruch
k=1 hE(l)
(Lemma A.22 and A.17
Kuch
SCH
Kucb Σ
Σ
d 2 2aal + +(+
2 H
Pl (=)))a)T
(max (xn+1(,aa)))
Kde
k=1 NE(M)
(Lemma A.17
Since Xn(s,a) S (H- S CH CHH.uch Kic
Kuch
we can modify the last display as
K
(era ) (1 2 pt( ((:1),a)T (max (Xn+i(sdd)))
Kuch Kdc.
an(s,a) s CHl
min
Σ
Σ
Jie Jr
k=1
hE(m
< CH Kde
Kucb
@ (n Kude (s) + (1+ H
2
pe( (())), (max (Xati(sa'))
(Lemma A.19
Therefore, we conclude.
A.3.4 Proof for lemma A.17 lemma A.18 lemma A.19. lemma A.20 (properties of bonus function)
For our bonus function, we have the following basic property.
Lemma A.17. Φ(x) is non-increasing when x > 0. For any a S 1, we have Φ(ax) < oz()).
Proof. We define f(x) = z [C Dlog (e (1+ + F))] where C, D2 1. Then, for x > 0,
fxx)= = C'
D log (e (1+ + )
D
< C Dog (1 x <
z²
D + x)
x2
Taking log (GH [S] |A| 8) and D |S], we conclude thee first claim. For the second claim, trivial since the logarithm function is increasing.
29

---

Lemma A.18. Under E, we have for any (s,a) E ES x A,
H
min min I 40
Kee Σn whe (s, (s,
Proof. For fixed (s,a) E A, when In (6H (A1/0)) S de Ene [m] wh w (s. we
know that E implies m(s, a) 2 E Enelnn Ke wa (s, a), From Lemma A.17
we know
(m(ss, a)) 5
1
Σ
Kae wh mii
(s, (o
S 40
Σ
Kdewn mazz (s.
4
hE(H)
hE[H]
When H In (6H S) |A| /6) > 1 (Kde Ene(h) w
(s. (s) simple algebra shows that
min (1, a)) 4H In (6H S S||A|/8 /8)
Kd Ene(h wh (s) S 46
Kde Σ
wh (s,
hE(H)
Therefore, we conclude.
Lemma A.19. Under E, we have for any (8, ES A.
Kucb
H
min 1. Φ
Σ
s 46 (s,
A=1
Proof.
We consider under the event E3, it holds that for any (s,a) E SSSx A,
1
6H S
S|
*h n (8. a)
5n n Kuch (s, (s,
Hin
8
If H In (6H [S] |A] /8) s Kuco (s, then we have Kuch ΣH which implics
En=1 xh (s, 2 in Kuc
dl
Kueb 1f
ΣΣ
(5, S 2 (n < 40 (n (ack
Otherwise, if In (6H [S] 18) > (ankuct then we have
min { 1,
Knch
Σ (aal
2H In (6H |S] |S||||| [A]/5)
S 46 (u
n Keeb (s, a.)
Combining the two cases above, we conclude.
Lemma A.20. Under E, we have for any (Kuct) and any (8, E S x A,
min {1,
4H
log (HA181AA
+18| [8] (e (e(1+
Eick Eneren oi (s,
max 1, Eick Eneim T (o,10
[
30

---

Proof.
Under E? it holds that
6H|S||A)
n (s,
Σ
T (s, 11
8
ick hE[H]
If Hn (6H1/)))110)) - Lick E Ene( and hence,
d at (8, a), then n n* 2 1 2
Eicc Ene(m o (8,
min (s, & (n s
- $4
ΣΣ P-c hE|M)
This result equals to the right hand side in the lemma, because Σisk Enelhn 4H In (6H 2 (so taking maximum does change anything). Otherwise, H (6118)))11))) > Eic Enetn (5, a), then
a 1 2
(H
min {1, (n² (s, a))) SIS
Eieh Ene(h) C (s,
Since 1 $ 4H In (6H (6H|S]|A|/6)) we have
4H In (1111111/8))
min (1, (n a))} S15
$ RHS
max 1, [, Ene( (e..((sa)))
The last inequality comes from simple algebra. Therefore, we conclude.
A.3.5 Proof for lemma A.2I and lemma A.22 (properties of empirical sparsified MDP)
In this section, we state two important properties of the empirical sparsified MDP and prove them. We remark that we do not include P (st a) in these two lemmas, since by definition sf S.
Lemma A.21 (Multiplicative Accuracy). We set
12 12|5|211 A
Φ 2 2 log
8
Then, when H 2 2, under g", we have for any (s, s') E x A S,
1
1 H
(s' PP s.a) s
Pt s,a).
+
H
Proof. For N(s, a, s') < 4, both sides are zero. For as, > o recall Pt(' s,a) = N(s.0.s). then from lemma A.10 with probability at least 8,
N(a.)
(t's' s,a) - (ss' s,a)
(s' s,a) log
12|5| [4]
14 3N(s, a)
12 12|8| |A] 5
log
a(s,a)
(lemma A.10 and definition of E
2
/2|8/2 2 IA 8
14
12|S| [A|
log
log
1t ss
((s, a,
3. a.
P (s' s,a)
N(c.o.e)) N(3.0)
<
V
3H +
(8
9H²
H
where the second line comes from the lower bound 4. We conclude.
31

---

Lemma A.22 (Bound on Ratios of Visitation Probability). For any deterministic policy т and any 8,, [H] x S x A, holds that
H ( Se (8, S 3d (s,
Here, recall that we denote d (s, a) and dr (s, as the occupancy measure of (s, a) at stage under policy on P (the transition dynamics in the sparsfied MDP) and Pt (the transition dynamics in the empirical sparsified MDP) respectively.
We remark that for s² & S the inequality does not necessarily hold.
Proof. We denote Th as all truncated trajectories ($1, 01 $2, 02 .... 8/, a4.) up to stage such that (sh, an) (s, a). Notice that if Th ($1, 01 $2, 02, Sh, ai.) E The then it holds that s; * st
for 1 S. S h 1. We denote IP (-: IP,, T) as the probability under specific transition dynamics IP
and policy æT. For any fixed (h, s, a) [H] S x A and any fixed Thasas we apply Lemma A.21
to get
T:
PT
Tee
(a:
8;)
ptt
(s1+1 S4 a,)
i=1
1
H
h-1
+
II me (a: s;) II
Pl ($#+1 1/s 0;) s 3P [T: x
H
and
h
P T:
Pt
=
me
(a;
84)
Pt (s s/ a4)
1=1
1=1
II m.s (a, st) II pt (8141 st,a))
P P|r:Pt,
H
4
We conclude by rewriting the visiting probability
df (8,0)
Σ P[r:Pi,m]; TETh.A.
(s, E
PP PT:
TETh.n.
32

---

B Additional comparisons
B.1 Comparison with other comparator policy
Our main result compares the sub-optimality of the policy Finat against the optimal policy on the sparsified MDP. We can further derive the sub-optimality of our output with respect to any comparator policy the original MDP M. If we denote T,, T. and finat as the global optimal policy, the optimal policy on the sparsified MDP and the policy output by our algorithm, respectively, and denote the comparator policy, have
V1 (s1, - V1 (81, fTT.aa))
VV1 (s,, - V1 (s1, ,,, + V1 (s1, ,,, - V1 (51, Pt ,.,
50
+ Vi (s1, Pl, ,r, - Vi (s1, Pl. finat) + Vi (81, Pi, final
- Vi Pr, T final
50
< 1/2 Ps,, 1/2 (s n..) tE.
(B.1)
Approsimation Error
Here, the second term is non-positive from the definition of n., the third term is upper bounded by due to our main theorem (Theorem (. and the last term is non-positive from the definition of the sparsified MDP. Since the connectivity graph of the sparsified MDP is sub-graph of the original MDP, for any policy, the policy value on the sparsified MDP must be no higher than that on the original MDP.
At a high level, the e term in the last line of (B.I) represents the error from the finite online episodes, measures the policy value
while the approximation eгror term V1 ($1, p.r,T) V12 (s1. Pf, difference of on the original MDP and the sparsified one, representing the coverage quality of the offtine dataset. If the dataset covers most of what covers, then this gap should be small. When is the global optimal policy オ., this means the data should cover the state-actions pairs where optimal policy covers. The approximation error here plays similar role as the concentrability coefficient in the offline reinforcement learning.
B.2 Comparison with offline reinforcement learning
Our algorithm leverages some information from the offline dataset, so it is natural to ask how we expect that offline dataset to be, compared traditional offline reinforcement learning does. In offline RL, we typically require the concentrablity condition, namely good coverage for the offline dataset, in order achieve a polynomial sample complexity. Specifically. if we assume the offline data are sampled by first sampling (s, a) i.i.d. from and then sampling the subsequent state from the transition dynamics, then the concentrability condition says the following constant C** is well-defined and finite.
d (s, a) < 0o.
C = sup
(s.a)
(18800 a)
The concentrability coefficient can be defined in several alternative ways. either for a set of policies or with respect to a single policy [Chen and Jiang 2019 Zhan et al. 2022 Xie et al.) [021b]] Zanette al., 2021b). Here, follow the definition in [Xie al.) 202 This means, the sampling distribution must covers the region where the global optimal policy covers, which a very similar intuition obtained from setting.
[Xic et al. 2021b) also gave optimal sample complexity (in terms of statc-action pairs) for an offline RL algorithm is
N - (
C* 555 |
62
which is minimax optimal up to logarithm terms and higher order terms. Similar sample complexity were also given in several literature Yin and Wang 2020 Yin al. 2020 Xie and Jiang 2020b).
33

---

Uniform data distribution For simplicity, we first assume to be uniform on all state-action pairs and the reward function be given. Consider we have N state-action pairs the offline data, which are sampled i.i.d. from the distribution μ.. Notice that here, the global optimal policy n, still differs from the optimum on the sparsified MDP T!, since even if we get enough samples from each (s, a) pairs, we might not get enough samples for every (s, a, s') and hence, not all (s, a, s') will be included in the set of known tuples.
Concretely, we consider the case when we sample each state-action pair for N/([S] A|) times and simply treat the transition frequency as the true probability, then for any (s, a, 8 < + it
holds that IP (s' 8, s, N(s.a.s)) "=..a.'')SSllA
LiS|AAl So for any any (s, a, s') 2 4 we
N(s,0)
N
know P(s' 8, a) = =s' 8, a); while for any N(8, a, 8)) D, we have PP (8' (8,0) & *|S|AA| and (f 8, a) = 0. Therefore, we have
N
+ |S|
P(s' s,a) -s s. =
N
From the value difference lemma (lemma D.11 we can upper bound the approximation error by V1 (81, Pr,, V1 (s,,
Ep,r.
Σ Σ
(P'
Ss. an) ap)
P(SN+1 18h Vn (8h41,P,r,,) 8h.
h=1 86+1
(lemma D.11
H
|
< Ep,r
H Sh =8
(the value function is upper bounded by H)
N
hm
& 2
|8|2
[A|
(summation over h E [H] and 8/+11 S)
N
H |
IA]
(definition of O in (5.1)
Therefore, to get an e-optimal policy compared to the global optimal one, we need the number of state-action pairs in the initial offline dataset 2 to be
H | LA
N
From the theorem 5.1 the offline data size we need here actually significantly smaller than what we need for an offline algorithm. As long suP()..) d= (s, a) is not too small, for instance, larger than H 11115 then we shave off the whole 1/e² term. The order of offline sample complexity here is actually ((1/s) instead of ((1/=²) typical in offline RL, and this is significantly smaller in small e regime. To compensate the smaller offline sample size, actually we need more online sample to obtain an globally e-optimal policy, and we summarize the general requirement for offline and online sample size in corollary 5.2
Non-uniform data distribution Assume the data generating distribution μ is not uniform but still supported all (s, a) pairs such that dd (8, a) > so that the concentrability coefficient in offline RI is still well defined. We simply consider the case when each state-action pair (s, a) is sampled by N p(s, a) times and treat the transition frequency as the true underlying probability. Then, following a very similar argument as in the last paragraph, the number of state-action pairs needed in the initial offline dataset order extract e-globally optimal policy is
H I
d= (s,
N ==Ö δ
u(s,a)
Here, the quantity
d (8,a) pls,o)
c1 cl Σ
34

---

plays a similar role of classical concentrability coefficient and also measures the distribution shift between two policies. the worst case. this coefficient can be | resulting in an extra [S] |A| factor compared to the optimal offline sample complexity. However, we still shave off the entire 1/e² term and also shave off H1. in the 1/e term.
Partial coverage data Under partial coverage, we expect the output policy finol to be competitive with the value of the best policy supported in the region covered by the offline dataset. In such case, theorem 5.1 provides guarantees with the best comparator policy on the sparsified MDP .M! In order to gain further intuition, it is best to 'translate' such guarantees into guarantees on M.
In the worst case, the data distribution i at a certain (s, a) pair can be zero when d' (s a) > 0, which implies the concentrability coefficient C co. Here, is arbitrary comparator policy. In this case, either classical offline RL algorithm or our policy finetuning algorithm cannot guarantee an e-optimal policy compared to the global optimal policy. However, we can still output a locally e-optimal policy, compared to the optimal policy on the sparsified MDP.
In order to compare T Final to any policy the original MDP, we have the corollary 5.2 which will be proved in appendix B.3
The statement in corollary 5.2 is quite direct consequence of theorem 5.1 and it expresses the sub-optimality gap of iI fénal with respect to any comparator policy π on the original MDP M. It can also be written in terms of the sub-optimality: If we fix comparator policy then with probability least 1 8, for any reward function r, the policy x ffinal returned by algorithm 2 satisfies:
11 [S] VIA Vi (s1;Prr, Vi (fmat) 5
1 IS N
d" (TT a)
=
Vdde
p1s, a)
Online error
Oflline error
H HSSI
H
| sa u(s,a)
|A sup
d (s.
=
Viáe
N
where Kae is the number of online episodes and N the number of state-action pairs offline data. Here, the sub-optimality depends on online error well as on offline error. The online error is the one that also arises in the statement of theorem 5.1 is an error that can be reduced by collecting more online samples, i.e., by increasing K, with the typical inverse square-root depedence 1/vK.
However, the upper bound suggests that even in the limit of infinite online data, the value of π final will not approach that of π. because of residual error due to the offline dataset D. Such residual d (=.a))
pls.a) < |S||A sup,.a (u(,,a) whose presence is intuitive: if a comparator policy is not covered well, our algorithm does not have enough information to navigate to the area that π tends visit, and so unable refine
error depends on certain concentrability factor expressed as Σ., d'
its estimates there. However the dependence on the number of offline samples N = [D] is through its inverse, i.e., 1/N as opposed the more typical 1/VN: such gap represents the improvable performance when additional online data are collected non-reactively.
is useful to compare corollary 5.2 with what is achievable by using a minimax-optimal online algorithm Xie et al. 2021b). In this latter case, one can bound the sub-optimality gap for any comparator policy with high probability as
H3 ( N
dt (8.a) a) u1s
Vi (st: - Vi (r):P, Timaaa) S 5
{6(
sup s,
(B.2)
B.3 Proof of corollary 5.2
Let's denote D [(st, a,, sE)EEN jEIN the offline dataset, where N as the total number of tuples. We keep the notation the same in the main text. We use N(s, a) and N (ssa, a, s') to denote the counter of (s. a) and (s, s') in the offline data D. The state-action pairs are sampled i.i.d. from μl(s, a) and the subsequent states are sampled from the transition dynamics. We fix a comparator policy æ and assume ju(s,0 a) > 0 for any (8, such that d= (s. a) > 0, which implies a finite concentrability constant C*. Here, dd (8, a) the occupancy probability of (s, a) when executing policy म, averaged over all stages h [H].
35

---

Similar to the Section B. we have
V1 (s,,P.r,, - V1 (s,,P,r Prr,
VVi (,,, V1 (s1, Ptt, r, V1 (s1, n, Ví (s1, Ptt ,r,
50
+V1 (51, Pt ,r, V1 (s1, Pt T. sinat) + V1 (81, IPt minaa))
V1 (81, P, J f
20 Vi (s1, r, x!) Vi (s1, P r, x Ffiatt) V (81, P,,,) Vi (s1, p n, ,r,
(B.3)
Approximation Error
Estimation Frmor
where o. and final are the optimal policy on the sparsified MDP and the policy output by our algorithm, respectively. and и is the fixed comparator policy. Here, the second term is non non-positive from the definition of πh, the last term is non non-positive from the definition of the sparsified MDP. This is because, for any state-action pair (s, a) and any fixed policy म, the probability of reaching (s, a) under P will not exceed that under the true transition probability If we denote the visiting probability under x and P (or Tpi resp.) as ( a) (s, a) resp.), then we have
(s, a) S (s,
for any E [H] E S,a E A. Note that, for = st, this does not hold necessarily, Them, for any policy n, we have
"
Vi (1 (l.
,r,))
Σ
Σ
dl (s,
(definition of policy value)
h=1 s,a
Σ (s)
(r(s), a) 0 for any a)
Σ
d (s.(ss)))(ss))) V1 Pr,,
1 a
Therefore, we get V1 (s1, r, final) - V1 ($1, P. finat) S 0 when we take ग = final-
From the main result (Theorem 5.1 we know the estimation error is bounded as
H|SIvIA Vide
Vi (s1, Pt r, m!) Vi (s1, IPt Minat) S Sō
(B.4)
Estimation Erar
where Kde is the number of online episodes. Therefore, to make the right hand side of (.4) less than e/2, one needs at least H
HSSSIA
online episodes. This is exactly what the main result shows.
So it suffices to bound the approximation error term. From the value difference lemma (Lemma D.I.p. we have
Vi (81, Fr,,,) Vi (s1, P(.;;))
(P S/ a:) - PP- st, a:)) T Vi+1 (:IPt, ,, 91 =
Ep,,
H
d (n, (Pi ( - P(- ss, ss)) T Vi+1 (: (: m.
:=1 si.a;
(by expanding the expectation)
<H |S|
Σ Σ dxn( suu |Pt (s') | (ss
IP(s s/ a:)]
(Vi+1 S Hl and the inner product has |S] terms)
36

---

We define
dx (s, a)
d n (s
(B.5)
as the average visiting probability. Then, we have
(s1, V1 (s1, Pt Pr,,, r, m)
|8 H
sup IPt 88,a) IP(8 s. d (8.
(B.6)
So suffices to upper bound [Pt('' 8, s,a) - P(s' | s. a) Notice here we only consider 8 + st and s' * s", since the value function starting from sf is always zero.
For (s, 8'), if ((s, o, s') Φ it holds that (st s,a) P(s' s,a). Otherwise, from the definition, we know (1 s, 0, so it suffices to bound IP(s' 1,, a) in this case. From lemma B.1 we know that with probability at least 6622, for any (s, a, 8') such that ((s, a, 8') + it holds that
2N(s, 2 log (2|8)² [A|/8]
P(s' s,a) S
N a)
Then deal with cases. When Nu(s, a) 2 64, from lemma B.2 have
4N(8, s') 2 log 4 1 (8
4+ 2 2og 4 [||)) |A| /6
P(s ss < Nu(s, a) 2 log (2 S [A] /6)
Np(s, 2 log (2 S| [A] /8)
From the definition of $ we know that 2og which implies
(4|8) [A]
s + and 2 2oo (2 |S| |A| /8) s $
5Φ
6$
P(s' s.a) I
Nu(s, a) 4b S Nu(s,a)
The last inequality comes from our assumption for N)(ss,) 2 6Φ. In the other case, when Nu(s,,) a) 66, it holds that
6Φ
Nu(s,a)
for any (s, a, Therefore, for any for any (s, a, s') such that N(s, a,s,,,5)) < 2 we have
6$
PPs' 8, 8,
(B.7)
Np(s,a)
Combining equations (B.7 and (B.6),
we know for any comparator policy क, holds that
H |S|
Σ dr(s,a) p(s,a)
Sō Ht S Σ
ds(s,
Vi (s1, Vı (s1, P r, (,
S
m(s,a)
Approsimation Erroe
where N is the total number of transitions in the offline data. In order to make the right hand side of last display less than s/2, one needs at least
(s)))) ((s,a)
< 2ō H HS 1S
offline transitions. Combining the proof for estimation error and approximation error, we conclude.
37

---

B.4
Proof for lemma B.1 and lemma B.2
Lemma B.1. With probability least 8/2, any (s, A S, it holds that
1 N(s.a,5)) a)) s, log [2| [A]
Proof. We fixed (s,, a, s') and denote as the index set where (8;, a;) (s, a) for E I. We range the indexes in I as 1 < i2 < < (((o)) For S N(s a), we denote X; = 8/ = =s' which is the indicator of whether the next state is s' when we encounter (s, a) the j-th time. When j 2 (s, a), we denote Xj as independent Bernoulli random variables with successful rate [P s, a). Then, know X, for all j E N are i.i.d sequence of Bernoulli random variables. From Lemma D. with probability at least 8/2, for any positive integer n, holds that
we know
Σx
X
P(s s, log (3)
2
We take n = (s, a) (although ((s, a) random, we can still take it because for any n the inequality above holds) to get
N(sa)
a(s,a, = Σ
X,
aPs (8,0) log (
j=1
Applying a union bound for all (s, a, s'), we conclude.
Lemma B.2, With probability at least - - any (s) E S x A, it holds that
N(s a) 2 ()(s,a) log (2
Proof. If (((, a) this is trivial. We fixed an (s, a) such that yass, a) > 0. For j S N, we denote X, [s, s, a2 a). which is the indicator of whether the j-th state-action pair we encounter in the offline dataset is (s, a). When j 2 N,, we denote X, as independent Bernoulli random variables with successful rate u(s.a) a). Then, we know Xj for all j E N are i.i.d. sequence of Bernoulli random variables. From Lemma D.1 we know with probability at least 5/2, for any positive integer n, holds that
X, Σ 1=1
u(s, a) - log
We take N to get
2 2 Np(s,a) log
N(s,a) Σ
Xj
1=1
Applying a union bound for all (s,a) such that p(s, a) > 0, we conclude.
38

---

C Lower bound
In this section we briefly discuss the optimality of the algorithm. Although the following consid- erations are also mentioned in the main text, here we mention how they naturally lead to a lower bound.
Lower bound for reward-free exploration Consider the MDP class M defined in the proof of the lower bound of Theorem 4.1 in [Jin et al. 2020b]. Assume that the dataset arises from a logging policy Wlog which induces the condition (x, a, x)) 2 + for all (s,a,& x') x A for every instance of the class. In this case, every MDP instance M E M and its sparsified version M coincide. Then the concatenation of the logging policy Woog and of the policy ffinal produced by our algorithm (i.e., algorithm 3) can be interpreted as a reactive policy, which must comply with the reward free lower bound established in Theorem 4.1 of [Jin et al. [020b]. More precisely, the reward-free sample complexity lower bound established in Theorem 4.1 in [Jin et al. 2020b] is
|8| |1
22
(C.1)
c2
trajectories. This matches the sample complexity of theorem 5.1 originally present in the dataset can be
Notice that the number of samples
|S| -(H2)= 0(1))()111))
(C.2)
a term independent of the accuracy c. Given that when c I 1 we have
Õ(H (8(111)))111 + 2 |S
H22 1
= 22 |5
8²
e²
our algorithm is unimprovable beyond constant terms and logarithmic terms in a minimax sense.
Lower bound for non-reactive exploration Consider the MDP class M defined in the proof of the lower bound in Theorem 1 of [Xiao et al.] [022]. It establishes exponential sample complexity for non-reactive exploration when no prior knowledge is available. In other words, in absence of any data about the MDP, non-reactive exploration must suffer exponential sample complexity. In such case, our theorem 5. (correctly) provides vacuous guarantees, because the sparsified MDP M is degenerate (all edges lead to the absorbing state).
Combining the two constructions It is possible to combine the MDP class M₁ from the paper (Xiao et al. 2022] with the MDP class M2 from the paper (Jin et al. 2020b). In lieu of a formal proof, here we provide only a sketch of the construction that would induce a lower bound. More precisely, consider a starting state $1 where only two actions-4e
available. Taking a = 1 leads to the start state of an instance of the class M1, while taking a = 2 leads to the start state of an instance of the class M2; in both cases the transition occurs with probability one and zero reward is collected.
1 and = 2
Furthermore, assume that the reward function given over the MDPs in Mi is shifted such that the value of a policy that takes a = 81 and then plays optimally 1 and that the reward functions on M2 is shifted such that the value of policy which takes initially and then playes optimally is 2e.
In addition, assume that the dataset arises from a logging policy Tlog which takes 2 initially and then visits all (s, a, s') uniformly.
Such construction and dataset identify a sparsified MDP which coincide with M2 with the addition of 81 (and its transition to M2 with zero reward). Intuitively, a policy with value arbitrarily close to I must take action a = which leads to MI, which is the portion of the MDP that is unexplored in the dataset. In this case, unless the agent collects exponentially many trajectories in the online phase, the lower bound from [Xiao et al. 2022 implies that it is not possible to discover a policy with value close (e.g.. larger than 1/2). On the other hand, our theorem 5.1 guarantees that fn has a value at least e, because ग final is e-optimal on the sparsified MDP i.c., e-optimal when restricted trajectories. This value
to an instance on M2 with high probability using at most ~ H is unimprovable given the lower bound Ji al. [2020b]. which applies to the class M2.
For completeness, in the next sub-section we refine the lower bound of (iiao al. 2022 to handle mixture policies.
39

---

D Technical lemmas and proofs
Lemma D.1 (Lemma E.4 in Dann et al. 2017). Let F; for 1... ... be a flltation and X1,.. S1,...X, Xx be sequence of Bernoulli random variables with (X; Fi-1) P. with P. being Fi-1- measurable and X₃ being Fi measurable. It holds that
P
E
X1
P./2-1W sc"..
Lemma D.2. Let Fi Fororr i- 1... be a filtration and XI.... Xn be a sequence of Bernoulli random P. with P. being 1-eemaaaurbbll and X, being Fi measurable.
variables with IP (X, F(-1) holds that
n
En
X
2P. + W se-w
1] is non-decreasing R, where extend this function. For any t E N,, since X; - P: S 1, we have exp (Xx - Pt) - (X, - Pt) (X, P3)² (e 2) < (X, P.)² Taking expectation conditional on Fi and noticing that P: Xt a Martingale difference sequence w.r.t. the filtration Fx, we have
Proof. Notice that - (exp(u)
continuously
E [exp (X; P.) F--1] 1+E [x, - P.)2 [i-1] 1 S exp E (X. - P.)2 PI) [
exp (Pi),
where the last inequality comes from the fact that conditional on Fi-1, X, is Bernoulli random variable. We define M,. :- exp 1-t=1 (X, 2P:)]. which is supermartingale from our deriva- tion above. We define now the stopping time
min { N: M, > ew) and the sequence Tn min e N M, > w V 2 n). Applying the convergence theorem for nonnegative super- martingales (Theorem 4.2.12 12 in [Durrett 2019)). we get that lim, M, is well-defined almost surely. Therefore, M, is well-defined even when oc. By the optional stopping theorem for non- negative supermartingales (Theorem 4.8.4 in [Durrett 2019]. we have E [M,.] < E [Ma] < 1 for all and applying Fatou's lemma, obtain E [M-] E [limn-soc Mr,] S lim inf E [M Using Markov's 's inequality, we can finally bound
3n
X
Σ
P.+W
W
P(( < SP, >e)>>ee)= se se E[M
Lemma D.3 (Empirical Bernstein Inequality, Theorem 11 in [Maurer and Pontil 2009 ). Let > and T1, ... Tn be i.i.d random variables such that |> < A with probability 1. Let v 1 -.=1 Ty.
and V, Dim (Ia +) then with probability 1 we have
2 log(2/8)
14A
J
B[x]
log(2/8)
3n
Lemma D.4 (Concentration for KL Divergence, Proposition 1 in Jonsson et al. 2020)). ). Let X1, X2,..., .,, Xn.... be i.i.d. samples from a distribution supported over {1,... m. of proba- bilities given by P E Em, where Emp the probability simplex of dimension m 1. We denote by P. the empirical vector of probabilities. Then, for any E [0, 1). with probability at least 1 - 6, it holds that
Vn KL (P...P))
( log +
m "lo
(e(1
We remark that there is slight difference between it and the original version. In Jonsson et al. 2020y they use m instead of m. But since the second term of the right hand side above is increasing with m. our version also holds.
40

---

Lemma D.5 (Bernstein Transportation, Lemma 11 in Talebi and Maillard and any two probability measure Q2 IP which satisfy Q < F. we denote r Varx-r(f(XX and (()) == 2 x f()) inf,, [(x)) We assume Vr(s) and S(f) are finite, then we have
2018 ). For any function
12q [ʃ] [ & V2 P) (())TT(Q,))
Ep & 2VP[FIKL((),))
Lemma D.6 (Difference of Variance, Lemma 12 in Ménard et al. 2021)) Let P. Q be two probability measure on discrete sample space of cardinality S. Let f.g 9 be two functions defined S such that 0 S f(s) < for all S. we have that
Vare(f) S 2 Varp(g) 2bEp gl
and
Vara()) & VJro(J) + 312 Q
Further, KL (P; Q) S ax it holds that
Vara()) < 2 Varp(S) + 4b
Lemma D.7. For any sequence of numbers . 2n with S 26 S 1, we have
< 4 4lgg
Σ 24 +1
max
1;
kー
21
Proof.
7
*k
--1
2k
2i
21==1 Zj
max
1: 3 1=
k=
2 +
:=1
k-1
24
-i= Zi
1==1
+ 2i=1 2i
k=1
2121 2t
< 4
dx S 4log
Σe+11
Σ 24 22
1
kml
Lemma D.8. For 2 16 and 2 3, there exists a universal constant C1 2 4, such that when
x z C (o)(B)3
it holds that
B Blog(1 + +z) (1 log(1 +x)) S
Proof. We have
B log(1 1 + x)) (1+ (1 + x)) S B (1 + x))² -. B (1 + log(2x))² s B [log(6x))².
We define f(x) ;= x B [log(6x))² then have f((x) 2B (Gg)
Since 20, log(B),
x
we have
f(x) 2 log (gg1 log(B))
C log(( B)
We take C1 2 such that C1 log( B3) log 12C log (B)) whenever B 2 16. Therefore, we know fxx is increasing when æ 2 C log( B) Then, it suffices to prove
[log (og) < C₁ 2
Since [log (6C]Blog(D))]] lB)(B)2
llog (6C, lo)(B)))] it suffices prove Ci -
log (6C1 lBg(
V 2 log(
When C₁ 2 4, the difference of right hand side and left hand side s always increasing w.r.t. for
fixed C₁. Therefore, it suffices to prove the case when B 16. Noticing that we can always take a sufficiently large uniform constant C₁ such that the inequality above holds when B 16, we conclude.
41

---

Lemma D.9 (Chain rule of Kullback- divergence, Exercise 3.2 in Wainwright 2019 Given two n-variate distributions Q and P. show that the Kullback Leiblec Leibler divergence can be decomposed
as
"
Σ
( (1xx-1))
1=2
where Q (-1x denotes the conditional distribution of X, given (I, under Q
with similar definition for P3 (-1x;-)).
Lemma D.10 (Bretagnolle-Hubes Inequality, Theorem 14.1 in [Lattimore and Szepesvári 2020
Let P and Q be probability measures on the same measurable space (9,, and let A E F be an arbitrary event. Then,
P(A) + Q(4) 2 exp(-D((::Q)
where A = A is the complement of A.
Lemma D.11 (Value Difference Lemma, Lemma E.15 [Dann et al. 2017). ). For any two MDPs
M' and M" with rewards r' and r" and transition probabilities P' and P", the difference in values with respect to the same policy ı can be written as
Vi(s) (s) EE
(r' (st. a2, ae, s; =
F1
+ E"
Σ
(P' (st, at,t) PP" 1P'"(s (sL, t)) Vi+1 |s =
where V (8) = v = 0 for any state s and the expectation E' taken with respect to F and x and E" with respect Td and w.
E Details of the planning phase
In this section, provide some details of the planning phase in algorithm 3 In the planning phase, we are given a reward function r: S x A + [0, 1] and we compute an estimate of sparsified transition dynamics 1t, which is formally defined appendix A.1.1 The goal of the plamning phase is to compute the optimal policy Timal the MDP specified by the transition dynamics Pr and reward function r!, where r is the sparsified version of r r'(s, r(s, a) and r (s1, a) 0 for any E A. To compute the optimal policy, we iteratively apply the Bellman optimality equation. First, we define (8 = (ss a) for any (s, a) and solve
Final, (8) = arg max r (s.a). aeAA
Then, for h = - 1, -2, 2, we iteratively define
= : + Σ Pt (s' |1, @n a ft i (s'))
for any (s, a), and then solve
final, (8) arg max (s, a) aeAA
for any 8 S. For sf and any h E [H]], ffimat, can arbitrary action. Then, from the property of Bellman optimality equation, we know finat is the optimal policy on Ptt and rt.
F
More related works
Other low-switching algorithms Low-switching learning algorithms were initially studied in the context of bandits, with the UCB2 algorithm [Auer al. 2002 achieving an O(Alog K) switching
42

---

cost. Gao et al. [019 demonstrated a sufficient and necessary (AA log K) switching cost for attaining the mimimax optimal regret multi-armed bandits. In both adversarial and stochastic online learning, [Cesa-Bianchi et al. 2013 designed an algorithm that achieves an (log log K) switching cost.
Reward- reinforcement learning In reward-free reinforcement learning (RFRL) the goal is to find a near-optimal policy for any given reward function. (Jin al. 2020a] proposed an algorithm
based on EULER Zanette and Brunskill 2019) that can find a e policy with O(H |s [A| /sa) trajectories. Subsequently, [Kaufmann et al. 202T reduces the sample complexity by factor H by using uncertainty functions to upper bound the value estimation error. The sample complexity was further improved by another H factor by [Ménard et al. 2021].
A lower bound of Ö(H² | |Al/ was established for homogeneous MDPs by [Jin et al. 2020a
while an additional factor conjectured for non-homogeneous cases. (Zhang 2021 proposed the first algorithm with matching sample complexity in the homogeneous case. Similar results are
available with linear [Wang et al. [020a] Wagenmaker al. 2022 Zanette al. 2020 and general
function approximation [Chen al. 2022 Qiu et al. 2021]]
Offinne reinforcement learning In offline reinforcement learning the goal learn near-optimal policy from an existing dataset which is generated from a (possibly very different) logging policy, Offline RL in tabular domains has been investigated extensively (Yin and Wang [020 Jin al.
2020c Nachum et al., 2019 [Rashidinejad et al., [021]] Kallus and Uehara [2022] Xie and Jiang
2020a Similar results were shown using linear Yin al.) Xiong et al. [202]] Nguyen- Tang et al.
|022, Zanette et al., 2021b) and general function approximation Xie et al., al.]2222aa] J et al. [2021
Zhang et al.] 2022 Duan et al. [021 Jiang and Huang 2020 Uehara and Sun | Zanette and Wainwright 2022 Rashidinejad et al.) [022] Yin et al. 2022]. Offline RI. is effective when the dataset "covers' a near optimal policy, as measured by certain concentrabiluty factor. In the function approximation setting additional conditions, such as Bellman completeness, may need to be
approximately satisfied [Munos and Szepesvári 2008 Chen and Jiang 2019 Zanette 2023 Wang
al. 2020b Foster et al., (021][Zha et al.) 2022]
Task-agnostic reinforcement learning Another related line of work is task-agnostic RL, where N tasks are considered during the planning phase, and the reward functions is collected from the environment instead of being provided directly. (Zhang et al., 2020a] presented the first task-agnostic algorithm, UBEZero, with a sample complexity of ((H S| |A| log(N)/=²)) Recently, [Li et al. 2023a proposed algorithm that leverages offline RL techniques
estimate well-behaved behavior policy in the reward-agnostic phase, achieving minimax sample complexity. Other works exploring effective exploration schemes in RL include (Hazan et al. 2019 Du al.) 2011 MMirra eet al. 2020]. (Li et al. 2023b) also considered an offline-to-olline reinforcement learning algorithm which explores the environment using mixed policies reward-free mode.
43


Reviews:
[{"review_id": "HnwM2IRXnI", "reviewer": "Reviewer_CnHc", "summary": "The paper considers the setting where it is possible to leverage a dataset of transitions, together with the possibility of deploying a policy to collect additional information. The question then lies into what kind of policy should be deployed and what kind of data should be gathered. The authors argue that deploying an exploratory policy that switches, e.g. a policy that learns and adapts from its experience, leads a great engineering costs. As such, they propose to follow the principle of pessimism together with a non reactive policy that would be constrained to a sub-region of the MDP with enough transitions. They also make use of the principle of optimism to derive the exploratory actions taken within the subMDP. The authors provide a near optimal minimax-optimal upper bound for learning an epsilon-optimal policy.", "questions": "How good of a policy (trained from scratch) could be obtained with the number of additional samples required in Corollary 5.2?\n\nAlthough the dependence on the desired accuracy is reduced in Corollary 5.2, how much of a difference can this make given the concentrability coefficient?", "limitations": "The limitations are not clearly stated throughout the work. Some of the questions above try to probe into this.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The contributions and assumptions are made clear in the introduction (however, the concept of reactive policy is only clearly explained in plain a words a bit late). An intuition section is also provided which helps the reader follow the paper.\n\nThe authors provide theoretical guarantees both for the sparsified MDP together with the full MDP. In particular for the results on the full MDP it seems like a reduction in the epsilon coefficient is an important contribution.\n\nThe paper emphasizes a hybrid approach, exploring a setting that combines elements of both offline and online methods, hence offering a more practical and adaptable framework for various real-world applications.", "weaknesses": "Although the setting of interest is important (mix of online and offline) the paper doesn’t stress enough the importance of a non-reactive policy. Why is learning from the generated experience such a bad idea in practice? It seems like a slowly changing deployed policy (where changes perhaps happen through a trust region) would be a better choice.\n\nI understand the paper is essentially a theoretical one, however it would be interesting to present some empirical evidence as to the practicability of the proposed algorithm. Indeed, it is not clear if the current dependencies on state, action, epsilon and such quantities in the bounds would provide a meaningful difference.\n\nThe paper misses an opportunity to provide a comprehensive conclusion, one that effectively synthesizes the results, giving the reader a clear understanding of the study's overall implications and potential future directions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions on our paper! We will try to answer your questions below.  \n\n1. Q: Why is learning from the generated experience such a bad idea in practice? It seems like a slowly changing deployed policy (where changes perhaps happen through a trust region) would be a better choice.\n\nA: We agree with the reviewer that a slowly changing policy would be the preferred choice (and the approach that we would recommend) if it can be implemented easily. \n\nHowever, an interactive system that adaptively changes interventions in response to outcomes may be impractical in some settings due to the expertise and infrastructure needed.  An example is (1) when multiple agents collect data asynchronously and real-time communication to update their policy is difficult (such as in a large organization that is selling ads) and (2) whenever there is a significant overhead in the engineering infrastructure to implement an adaptive policy (such as in an organization with a complex production code).  \n\nRunning an experiment with a fixed decision policy is much simpler logistically, (since such organizations may already design decision policies by hand) and appealing, since many areas (education, healthcare, social sciences) commonly deploy experiments to find the best approach.  In these settings there is a key opportunity to design a sample efficient non-reactive policy that can be used to gather additional data to later identify better decision rules.\n\nAlthough some of these considerations are mentioned in Lines 30-40, we will expand them with additional discussion. \n\n\n2. Q: It would be interesting to present some empirical evidence as to the practicability of the proposed algorithm. Indeed, it is not clear if the current dependencies on state, action, epsilon and such quantities in the bounds would provide a meaningful difference.\n\nA: We thank reviewers for the suggestion that the paper could be made stronger with the addition of numerical experiments. \n\nAlthough we agree with the reviewers’ suggestions, a practically useful RL algorithm for this setting would need to leverage function approximation such as neural networks. Designing an effective algorithm for such a setting requires making several critical design choices that are specific to the function approximation setting, and overcoming the challenges that likely arise. This is beyond the scope of the paper, which is a first step towards understanding how offline data can be used for non-reactive exploration. We will highlight in the conclusion of the paper that the creation of a practical algorithm with function approximation is an important future direction.\n\n**We improved the sample complexity compared to a purely offline approach.** The best tabular offline algorithm requires O(H^3 S^2 C^* / \\eps^2 + H^{5.5} S^2 C^* / \\eps) samples to find an eps-optimal policy [4] (when ‘translated’ to the time-homogeneous and reward-free setting). Our sample complexity is O(H^3 S^2 A / \\eps^2 + H^4 S^2 A C^* / \\eps). We shave off the concentrability coefficient C^* in the leading term and also shave off H^1.5 in the O(1/\\eps) term. Since the concentrability coefficient can be extremely large, our approach offers a significant  improvement over purely offline algorithms.\n\nMore precisely, the current dependencies on the S,A,H and \\eps are minimax optimal up to the log factors in the reward-free setting [3]. This means that in the worst case one can not obtain an eps-optimal policy using less samples than our bounds. \n\n\n3. Q: How good of a policy (trained from scratch) could be obtained with the number of additional samples required in Corollary 5.2?\n\nA: Generally it is not possible to obtain meaningful guarantees when training *from scratch* with a single non-reactive policy. In fact, in the absence of any information about the MDP the best one can do is just to deploy a uniformly random policy, which commands an exponential O(exp(H)) sample complexity in hard-to-explore settings [1]. When exploring from scratch it is essential to use *reactive* policies; a well designed algorithm can find \\eps-optimal policies with O(H^3 S^2 A / \\eps^2) samples in the reward-free setting [3].\n\n\n4. Q: Although the dependence on the desired accuracy is reduced in Corollary 5.2, how much of a difference can this make given the concentrability coefficient?\n\nA: In practice, this concentrability coefficient is unknown and can be large. Since we remove C^* from the main term (the one with O(1/\\eps^2) dependence), the sample complexity now only depends on the concentrability  C^* through a lower-order term ( the one with O(1/\\eps) dependence ). That is, the smaller the target accuracy \\eps, the smaller the effect of a large concentrability C^*.\n\n\n5. Q: The paper misses an opportunity to provide a comprehensive conclusion, and the limitations are not clearly stated throughout the work. \n\nA: Thanks for your suggestion and we will add an additional conclusion section in the future version.\n\nTo summarize, in this paper we leverage offline data to conduct exploration using non-reactive policies. The key contributions lie in the originality of the setup and in the mathematical work to describe the conditions that need to be met for sub-optimality guarantees. Algorithmically, this is achieved by a novel blending of the principle of optimism and pessimism to design the exploration policy in a way that is probably efficient. Extending these algorithmic and theoretical insights to derive a practical reinforcement learning algorithm with function approximation is an important next step. \n\n[1]. Xiao et al, The curse of passive data collection in batch reinforcement learning.\n[2]. Qiao et al. Sample-efficient reinforcement learning with loglog (t) switching cost.\n[3]. Jin et al. Reward-free exploration for reinforcement learning.\n[4]. Xie et al. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning.\n"}, {"review_id": "6EqDWG6Jql", "reviewer": "Reviewer_gUtm", "summary": "The work proposes a method to create a non-reactive exploratory policy from an initial input dataset. Then, leveraging the new data, the algorithm generates a locally near-optimal policy.\n\nThe relevance of the algorithm is in the low-switching algorithms, where it is assumed there is a cost to changing a deployed policy.\n\nThe proposed algorithm uses the initial data to build a sparsified MDP, an approximation of the original MDP that keeps only the transitions (s, a, s') for which there are at least Φ transitions.\n\nThe next part of the algorithm is building the exploratory policy using the sparsified MPD using a value iteration iterative strategy with an exploration bonus instead of actual rewards. The exploration bonus balances optimism and pessimism, boosting exploration towards less explored states while avoiding spending too much time in unknown parts of the MDP.\n\nFinally, additional data is collected from the environment using this exploring policy, and a value iteration algorithm is employed on the combined datasets of experiences to build the final policy.\n\nThe authors provide optimality bounds, describing the conditions for the algorithm to discover an epsilon-suboptimal policy.", "questions": "Could some experiments be added to see the performance of the algorithm in practice, maybe compared to other offline RL methods?", "limitations": "no", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The strengths of this paper lie in the originality of the setup and in the mathematical work to describe the conditions that need to be met for sub-optimality guarantees.", "weaknesses": "The weakness of the paper is the need for empirical. For example, it would be helpful to see how well the algorithm performs given initial data sets of different sizes and coverage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions on the paper! We will try to answer your questions below. \n\n1. Q: The weakness of the paper is the need for empirical. For example, it would be helpful to see how well the algorithm performs given initial data sets of different sizes and coverage.\n\nA: We thank reviewers for the suggestion that the paper could be made stronger with the addition of numerical experiments. Although we agree with the reviewers’ suggestions, a practically useful RL algorithm for this setting would need to leverage function approximation such as neural networks. Designing an effective algorithm for such a setting requires making several critical design choices that are specific to the function approximation setting, and overcoming the challenges that likely arise. This is beyond the scope of the paper, which is a first step towards understanding how offline data can be used for non-reactive exploration. We will highlight in the conclusion of the paper that the creation of a practical algorithm with function approximation is an important future direction.\n"}, {"review_id": "KraQ3dYlwl", "reviewer": "Reviewer_rHsz", "summary": "The paper proposes an algorithm that, given a previously collected dataset of transitions from an MDP, produces a non-reactive policy that can effectively collect additional data that enables a near-optimal policy to be obtained for any possible reward function. The algorithm is model-based and combines elements of optimism (exploration bonuses) and pessimism (early termination at OOD states/actions). Suboptimality is bounded relative to the optimal policy that stays within the “sparsified MDP” which is the subset of the original MDP that is sufficiently covered by the data.", "questions": "I’m curious if it is known that better sample complexity can be obtained if you allow the policy to be adaptive? (Although I understand the engineering-related reasons for not doing so.) If so, it could be useful context to briefly comment on in the paper.", "limitations": "No, limitations are not addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The paper presents positive, novel (to my knowledge) theoretical results in a well-motivated setting of practical interest.\n* The interaction protocol is new AFAIK, but closely related to existing areas such as reward-free RL. It may inspire more work in the future.\n* The paper is clear and not hard to follow, despite its technicality.", "weaknesses": "* No experiments, despite having “Design of Experiments” in the title :) (But this is a theory paper so I think it is okay)\n* IMO the Related Work should cite the MOReL paper [1], which uses a pessimistic MDP construction similar to your sparsified MDP, in which low-density states/actions lead to a special absorbing state. Of course, they are tackling a different setting (offline RL with a particular reward function) and use a somewhat different termination criterion, but the idea is the same.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions on our paper! We will try to answer your questions below. \n\n1. Q: I’m curious if it is known that better sample complexity can be obtained if you allow the policy to be adaptive? (Although I understand the engineering-related reasons for not doing so.) If so, it could be useful context to briefly comment on in the paper.\n\nA: This is a very good question and we will stress this point in the next version of our paper. Yes, one can do better if you use reactive exploration policy. By using reactive policies, you can achieve eps-optimal policy on the entire MDP with O(H^2 S^2 A / \\eps^2) trajectories[1,2], while the non-reactive exploring policies can only yield an eps-optimal policy on the sparsified MDP. This difference is natural since we can only effectively explore the region where we have some knowledge about (i.e., the sparsified MDP). \n\n\n2. Q: No experiments, despite having “Design of Experiments” in the title :) (But this is a theory paper so I think it is okay)\n\nA: We thank reviewers for the suggestion that the paper could be made stronger with the addition of numerical experiments. Although we agree with the reviewers’ suggestions, a practically useful RL algorithm for this setting would need to leverage function approximation such as neural networks. Designing an effective algorithm for such a setting requires making several critical design choices that are specific to the function approximation setting, and overcoming the challenges that likely arise. This is beyond the scope of the paper, which is a first step towards understanding how offline data can be used for non-reactive exploration. We will highlight in the conclusion of the paper that the creation of a practical algorithm with function approximation is an important future direction.\n\n3. IMO the Related Work should cite the MOReL paper, which uses a pessimistic MDP construction similar to your sparsified MDP, in which low-density states/actions lead to a special absorbing state. Of course, they are tackling a different setting (offline RL with a particular reward function) and use a somewhat different termination criterion, but the idea is the same.\n\nA: We thank the reviewer for pointing out a connection with MOReL; the paper is indeed relevant and we will cite it. As the reviewer notices, MOReL also constructs a sub-MDP using the principle of pessimism; a key algorithmic difference is that we combine such pessimistic construction with the principle of optimism to explore within the sub-MDP instead of directly using the dataset to output a policy.\n\n[1]. Ménard et al. Fast active learning for pure exploration in reinforcement learning.\n[2]. Jin et al. Reward-free exploration for reinforcement learning."}, {"review_id": "1z9OLrbGVI", "reviewer": "Reviewer_TPkj", "summary": "This paper proposes an algorithm for policy fine-tuning in reinforcement learning using a dataset of pre-collected experience. The algorithm leverages the dataset to design a non-reactive exploratory policy and outputs a locally near-optimal policy. The paper makes theoretical contributions in analyzing the quality of the policy and establishing sample complexity bounds. The work is motivated by the practical need for non-reactive exploration in domains where switching policies is costly and impractical. The paper presents innovative ideas and provides a novel solution to the problem.", "questions": "- Can you give more details on the non-reactive property of a policy? It seems that most RL policies in an MDP will be non-reactive, as long as they take only the current state $s_t$ as input. How is the example in line 30-32 related to the non-reactive property?\n- Online exploration may lead to safety violations. How safe will the online phase be in the original MDP?\n- It seems contradictory to be both optimistic and pessimistic at the same time. How to determine the region that the agent knows how to navigate?\n- Can you provide some empirical evaluations of the proposed algorithm, compared with fully offline or fully online algorithms?\n", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces an algorithm that addresses the problem of non-reactive policy design in reinforcement learning and provides provable guarantees for the quality of the resulting policy.\n- The concept of sparsiﬁed MDP is introduced and effectively used in the algorithm and theoretical analysis.\n- The paper rigorously establishes a nearly minimax-optimal upper bound for the sample complexity needed to learn a local ε-optimal policy using the proposed algorithm.\n- The paper addresses a practical need for non-reactive exploration in domains where policy switches are costly and provides a solution that can be valuable in such scenarios.\n", "weaknesses": "- The paper only considers discrete state and action spaces. \n- The paper provides no empirical evaluations or demonstrations of the proposed algorithm. Neither does it shed light on the design of practical algorithms.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions on our paper! We will try to answer your questions below. \n\n1. Q: Can you give more details on the non-reactive property of a policy? It seems that most RL policies in an MDP will be non-reactive, as long as they take only the current state s_t as input. How is the example in line 30-32 related to the non-reactive property?\n\nA: Thank you for your question and we will try to make it clearer in the next version. **A non-reactive policy is a policy that is not updated during the whole interaction process.**\n\nAs the reviewer notices, RL algorithms typically employ a sequence of non-reactive policies as they explore the environment. **These algorithms are reactive to the data they acquire, because such data is used to update the currently deployed policy.** The sequence of non-reactive policies that they deploy could be interpreted as a **single reactive** policy, namely one that changes during the interaction.\n\nIn contrast our work examines the setting where exploration must be done with a **single non-reactive** policy: in our case, no updates are possible during the entire exploration phase.\n\nWhile deploying a sequence of policies is the better approach from a theoretical point of view, **doing so is not always practically feasible**. In line 30-32 we give an example with a human in the loop. The human may need significant time to validate each policy that a reactive algorithm produces, and this may make real-time deployment of a reactive algorithm impractical. However, such a problem disappears if the algorithm only deploys a static policy for exploration, because this policy only needs to be checked once before deployment.\n\n2. Q: Online exploration may lead to safety violations. How safe will the online phase be in the original MDP?\n\nA: Although safety is an important concern in the application of reinforcement learning,  it is not the main motivation of our paper. Nonetheless, there are two ways to incorporate safety.\n\nThe first is to incorporate some techniques from safe RL [4,5,6] into the design of the algorithm, and also to the procedure of collecting the offline dataset. The second is before deployment: non-reactive exploration produces a single policy, and so safety can be checked quite easily before deployment.\n\n3. Q: It seems contradictory to be both optimistic and pessimistic at the same time. How to determine the region that the agent knows how to navigate?\n\nA: One of our contributions is that our algorithm combines the principle of optimism and pessimism in a subtle way: they are applied to different regions of the MDP and so there is no contradiction between these two principles. We will clarify this in the introduction.\n\nAt a high level, pessimism excludes the region where we have little to no knowledge about the transition dynamics, and it identifies a sub-MDP where approximate planning is possible. Within the sub-MDP, we explore using the principle of optimism. In summary, pessimism defines the MDP sub-region where we can leverage optimism to conduct exploration.\n\n4. Q: Can you provide some empirical evaluations of the proposed algorithm, compared with fully offline or fully online algorithms?\n\nA: We thank reviewers for the suggestion that the paper could be made stronger with the addition of numerical experiments. Although we agree with the reviewers’ suggestions, a practically useful RL algorithm for this setting would need to leverage function approximation such as neural networks. Designing an effective algorithm for such a setting requires making several critical design choices that are specific to the function approximation setting, and overcoming the challenges that likely arise. This is beyond the scope of the paper, which is a first step towards understanding how offline data can be used for non-reactive exploration. We will highlight in the conclusion of the paper that the creation of a practical algorithm with function approximation is an important future direction.\n\n5. Q: The paper only considers discrete state and action spaces.\n\nIndeed our paper is a first step for exploration with a non-reactive policy which is computed with the help of offline data.\n\nAlthough we could have tackled the setting of function approximation, doing so would have involved a number of technical considerations that might have made the result more cluttered and less clear for a first paper on such topics. We do agree with the reviewer that the extensions to the function approximation setting are important future directions, and we will mention this in the conclusion.\n\n[1]. Jin et al. Is q-learning provably effi394 cient?\n[2]. Kaufmann et al. Adaptive reward-free exploration.\n[3]. Ménard et al. Fast active learning for pure exploration in reinforcement learning.\n[4]. Gu et al. A review of safe reinforcement learning: Methods, theory and applications.\n[5]. Ding et al. Provably efficient safe exploration via primal-dual policy optimization.\n[6]. Cheng et al. End-to-end safe reinforcement learning through barrier functions for safety-critical continuous control tasks.\n\n"}, {"review_id": "2vn7CTJHXL", "reviewer": "Reviewer_wsu5", "summary": "The paper explores reinforcement learning applications where a pre-existing dataset of collected experience is available, and suggests the possibility of obtaining additional online data to enhance policy quality. To avoid the costs associated with switching policies, the authors propose utilizing a single non-reactive exploration policy for gathering supplementary data. They present an algorithm with provable guarantees that leverages an offline dataset to design such a policy. The algorithm is analyzed theoretically, and the authors evaluate the final policy's quality based on the local coverage of the original dataset and the amount of additional data collected. Overall, the research contributes to improving reinforcement learning by optimizing data acquisition and policy design.", "questions": "See weakness.", "limitations": "The authors didn't discuss the limitation of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The advantages of this paper are as follows: \n1. Although I haven't carefully derived each equation, the proofs in this paper are expected to be accurate, with complete steps and rigorous derivations.\n2. This paper represents the pioneering effort in terms of theoretical rigor, addressing the challenge of designing an experiment in reinforcement learning for online passive exploration, leveraging a dataset comprising pre-collected experiences. The setting is novel and has some practical significance.\n3. The proof method presented in this paper is innovative and the sample complexity mentioned in the conclusion is also tight. It will introduce new approaches to the theoretical research of RL. Additionally, the conclusions of this paper also reveal some interesting insights that will enrich the existing theoretical achievements in the offline-to-online field.\n", "weaknesses": "1. The basic assumption of this article is that the offline-trained policy cannot be switched during the online phase, and it allows for the collection of an unlimited number of samples using this policy. I have two concerns. Firstly, from a theoretical research perspective, this assumption narrows down the problem to a very specific setting, so even with rigorous mathematical proofs, the generalizability of the conclusions may be compromised. Secondly, from a practical application standpoint, if the offline-trained policy itself is poor but cannot be switched during the online phase, and a large number of online samples need to be collected using this policy, there will be even greater security issues. As a result, the advocated security considerations in this paper will no longer exist. I appreciate the mathematical methods used in this paper, but the lack of persuasive motivation will impact the significance of this paper.\n2. The proof process in this paper is too lengthy and difficult to understand. Although the main text provides some introduction to the overall proof logic, there are too many specific terms involved in the proof without providing intuitive explanations for their generation, which increases the difficulty of understanding. I suggest that the author can provide a more concise version, even if the resulting sample complexity is not optimal, but it can be used to understand the overall proof framework.\n3. Another limitation is that it currently only applies to smaller S and A. When S and A are larger, the application will become difficult and the sample complexity will be significant. So I'm curious to know if this approach can be extended to scenarios involving function approximation. If it is possible, what additional considerations or processing steps would be required? If it is not feasible, what challenges exist?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions on our paper! We will try to answer your questions below. \n\n1. Q: Firstly, from a theoretical research perspective, this assumption narrows down the problem to a very specific setting, so even with rigorous mathematical proofs, the generalizability of the conclusions may be compromised.\n\nA: Thanks for your question! Our study on non-reactive exploration arise from the need for low deployment and switching costs in the real-world applications across various domains such as recommendation systems and healthcare. By necessity, we formalized such general research questions in a specific setting where we could obtain concrete results, but we believe that some of the insights and algorithmic design principles extend more broadly.\n\n2. Q: Secondly, from a practical application standpoint, if the offline-trained policy itself is poor but cannot be switched during the online phase, and a large number of online samples need to be collected using this policy, there will be even greater security issues. As a result, the advocated security considerations in this paper will no longer exist. I appreciate the mathematical methods used in this paper, but the lack of persuasive motivation will impact the significance of this paper.\n\nA: Although safety is an important concern in the application of reinforcement learning,  it is largely orthogonal to the issues investigated in our paper. As the reviewer noticed, the safety of the online phase can partially depend on the pre-collected dataset, so if we want to take more safety factors into consideration, we can of course apply some additional techniques.\n\nGenerally speaking, there are two ways to incorporate safety. The first is to incorporate some techniques from safe RL [1,2,3] into the design of the algorithm, and also to the procedure of collecting the offline dataset. The second is before deployment: non-reactive exploration produces a single policy, and so safety can be checked quite easily before deployment.\n\n3. Q: The proof process in this paper is too lengthy and difficult to understand. Although the main text provides some introduction to the overall proof logic, there are too many specific terms involved in the proof without providing intuitive explanations for their generation, which increases the difficulty of understanding. I suggest that the author can provide a more concise version, even if the resulting sample complexity is not optimal, but it can be used to understand the overall proof framework.\n\nA: We understand that the proof can be long, but this is often a necessary compromise for the sake of rigor, and we will try our best to make it as clear as we can by adding some descriptions about the overall proof strategy.\n\n4. Q: Another limitation is that it currently only applies to smaller S and A. When S and A are larger, the application will become difficult and the sample complexity will be significant. So I'm curious to know if this approach can be extended to scenarios involving function approximation. If it is possible, what additional considerations or processing steps would be required? If it is not feasible, what challenges exist?\n\nA: Thanks for your question! As the first paper working on the non-reactive exploring policy in offline-to-online RL, we considered the tabular case. \n\nIt is an interesting next step to extend these insights to the function approximation setting. In the function approximation setting, one probably needs to overcome additional challenges, starting from defining of sparsified MDP in a way that takes into account function approximation. The method of adding positive bonus in the offline simulation phase can also be applied with slight change to the concrete form of bonus functions in the function approximation setting.\n\n5. The authors didn't discuss the limitations of their work.\n\nA: Thanks for your advice on the writing! We will definitely add a conclusion with emphasis on the significance as well as the limitations of our works. \n\nTo summarize, in this paper we leverage offline data to conduct exploration using non-reactive policies. The key contributions lie in the originality of the setup and in the mathematical work to describe the conditions that need to be met for sub-optimality guarantees. Algorithmically, this is achieved by a novel blending of the principle of optimism and pessimism to design the exploration policy in a way that is probably efficient. Extending these algorithmic and theoretical insights to derive a practical reinforcement learning algorithm with function approximation is an important next step. \n\n[1]. Gu et al. A review of safe reinforcement learning: Methods, theory and applications.\n[2]. Ding et al. Provably efficient safe exploration via primal-dual policy optimization.\n[3]. Cheng. End-to-end safe reinforcement learning through barrier functions for safety-critical continuous control tasks.\n"}, {"review_id": "D0ek1AFTWB", "reviewer": "Reviewer_s51D", "summary": "The authors introduced the concept of sparsified MDP. Based on this concept, they proposed a new algorithm that takes as input a dataset, uses it to design and deploy a non-reactive exploratory policy, and then outputs a locally near-optimal policy. A nearly minimax-optimal upper bound for the sample complexity is also established to learn a local ε-optimal policy using this algorithm.", "questions": "- Is it possible for the exploratory policy to explore out of the coverage of offline dataset? I know it is impossible if there is no data at all, but   it seems that using the information of the dropped transitions may help.", "limitations": "Limitations are not explicitly discussed by the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper proposed a new setting where the agent is access to an offline dataset and can further explore the environment online with a non-reactive policy. In this way, the agent can utilize the offline dataset while avoid the engineering costs associated with switching policies.\n- Sparsified MDP provides an perspective on combining both optimism and pessimism principle, which is interesting.\n- The authors obtain the sample complexity bound of the new approach, and the bound is tighter than previous method.\n- The paper is well-written and easy to follow.\n", "weaknesses": "- The algorithm is based on tabular setting, which limits its application.\n- The exploratory policy only explore in the sparsified MDP. In this way, the final policy is strictly limited by the offline dataset even if the budget for online interaction is large.\n- The transitions that cannot achieve the threshold is dropped directly, even though they contain some information of the environment. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions on our paper! We will try to answer your questions below. \n\n1. Q: The algorithm is based on tabular setting, which limits its application. \n\nA: Indeed our paper is a first step for exploration with a non-reactive policy which is computed with the help of offline data.\n\nAlthough we could have tackled the setting of function approximation, doing so would have involved a number of technical considerations that might have made the result more cluttered and less clear for a first paper on such topics. We do agree with the reviewer that the extensions to the function approximation setting are important future directions, and we will mention this in the conclusion.\n\n2. Q: The exploratory policy only explores in the sparsified MDP. In this way, the final policy is strictly limited by the offline dataset even if the budget for online interaction is large. \n\nA: The reviewer’s observation is correct, and this is a limitation of exploration with non-reactive policies. In the worst case, one cannot explore the regions not covered by the offline dataset because they may contain hard-to-explore combinatorial structures which command an exponential sample complexity[1]. More practical problems often do not have such worst-case structure; however what can be achieved in those cases is problem dependent and can be an interesting direction for future research.\n\n3. Q: The transitions that cannot achieve the threshold are dropped directly, even though they contain some information about the environment. Is it possible for the exploratory policy to explore out of the coverage of offline dataset? I know it is impossible if there is no data at all, but it seems that using the information of the dropped transitions may help.\n\n[1] Xiao et al, The curse of passive data collection in batch reinforcement learning.\n\nA: The reviewer is correct that some transitions are dropped even if in certain cases they may contain enough data about the environment. For example, some environments are nearly deterministic, and so even a few samples (below the value of our threshold) would suffice to explore. However, how to explore the regions that do not have enough data, and whether it is even possible to do so, depends on the particular structure of the problem. Including these considerations would have made the algorithm more complex and the analysis more cluttered and so we settled for a ‘hard’ threshold which is simpler but still very effective.\n\n4.  Limitations are not explicitly discussed by the paper.\n\nA: Thanks for your advice on the writing! We will definitely add a conclusion with emphasis on the significance as well as the limitations of our works to the next version of paper.\n\nTo summarize, in this paper we leverage offline data to conduct exploration using non-reactive policies. The key contributions lie in the originality of the setup and in the mathematical work to describe the conditions that need to be met for sub-optimality guarantees. Algorithmically, this is achieved by a novel blending of the principle of optimism and pessimism to design the exploration policy in a way that is probably efficient. Extending these algorithmic and theoretical insights to derive a practical reinforcement learning algorithm with function approximation is an important next step. \n"}]

Author rebuttal:

Meta-review: This paper rigorously characterizes the problem of learning from offline data without reward, followed by a fine-tuning phase using a non-reactive policy. All the reviewers voted for acceptance, some strongly so, and the authors responded well to the reviews. Reviewer CnHc was confident the work was correct and well executed but questioned if the results are particularly useful or will have any impact on practice. The AC had similar concerns and in consultation with the SAC determined some of this stems from missing justifications and explanations in the text, that would go a long way to improve the paper. In particular, we strongly recommend the authors address the following:

1. More justification for reward-free offline data
2. Main result Theorem 5.1 shows the performance bound for the sparsified MDP, not the original MDP. Do we care about the performance in the sparsified MDP? It might be possible to get some results like the performance loss compared to the best covered policy used in [1]. It is well worth extra text detailing why this bound is relevant
3. Explain why, in line 3 of algorithm 1, we receive the entire reward information.
4. "We rigorously establish a nearly minimax-optimal upper bound”. There is only an upper bound. Where is the minimax optimality from?
5. The paper should motivate why considering this particular separation of offline and online phase is useful. Corollary 5.2 shows the bound for the original MDP by assuming the standard concentrability coefficient. If we make the assumption that data is sampled i.i.d and the standard concentrability coefficient, offline data is sufficient to get a nearly optimal policy like Eq (5.4).
6. Line 49 is a bit misleading. The paper cites Xiao et. al., 2020 to show that using only data from a non-reactive policy cannot be sample efficient. However, the paper considered the setting where the offline data is sampled in an i.i.d. fashion from some distribution, only in the online phase the data is collected from a policy. 

This work is correct and well executed (ignoring the writing issues highlighted above). Even if limited, there is a community of researchers that will find this work interesting and build on it, therefore this paper should be accepted.

[1] Provably Good Batch Reinforcement Learning Without Great Exploration
Decision: Accept (poster)