Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
Year: 2021

Abstract:
Recent theoretical work studies sample-efficient reinforcement learning (RL) extensively in two settings: learning interactively in the environment (online RL), or learning from an offline dataset (offline RL). However, existing algorithms and theories for learning near-optimal policies in these two settings are rather different and disconnected. Towards bridging this gap, this paper initiates the theoretical study of policy finetuning, that is, online RL where the learner has additional access to a “reference policy” μ close to the optimal policy π? in a certain sense. We consider the policy finetuning problem in episodic Markov Decision Processes (MDPs) with S states, A actions, and horizon length H . We first design a sharp offline reduction algorithm—which simply executes μ and runs offline policy optimization on the collected dataset—that finds an ε near-optimal policy within Õ(HSC/ε) episodes, where C is the single-policy concentrability coefficient between μ and π?. This offline result is the first that matches the sample complexity lower bound in this setting, and resolves a recent open question in offline RL. We then establish an Ω(HSmin{C, A}/ε) sample complexity lower bound for any policy finetuning algorithm, including those that can adaptively explore the environment. This implies that—perhaps surprisingly—the optimal policy finetuning algorithm is either offline reduction or a purely online RL algorithm that does not use μ. Finally, we design a new hybrid offline/online algorithm for policy finetuning that achieves better sample complexity than both vanilla offline reduction and purely online RL algorithms, in a relaxed setting where μ only satisfies concentrability partially up to a certain time step. Overall, our results offer a quantitative understanding on the benefit of a good reference policy, and make a step towards bridging offline and online RL.

text: Recent theoretical work studies sample-efficient reinforcement learning (RL) extensively in two settings: learning interactively in the environment (online RL), or learning from an offline dataset (offline RL). However, existing algorithms and theories for learning near-optimal policies in these two settings are rather different and disconnected. Towards bridging this gap, this paper initiates the theoretical study of policy finetuning, that is, online RL where the learner has additional access to a “reference policy” µ close to the optimal policy π? in a certain sense. We consider the policy finetuning problem in episodic Markov Decision Processes (MDPs) with S states, A actions, and horizon length H . We first design a sharp offline reduction algorithm—which simply executes µ and runs offline policy optimization on the collected dataset—that finds an ε near-optimal policy within Õ(H3SC?/ε2) episodes, where C? is the single-policy concentrability coefficient between µ and π?. This offline result is the first that matches the sample complexity lower bound in this setting, and resolves a recent open question in offline RL. We then establish an Ω(H3Smin{C?, A}/ε2) sample complexity lower bound for any policy finetuning algorithm, including those that can adaptively explore the environment. This implies that—perhaps surprisingly—the optimal policy finetuning algorithm is either offline reduction or a purely online RL algorithm that does not use µ. Finally, we design a new hybrid offline/online algorithm for policy finetuning that achieves better sample complexity than both vanilla offline reduction and purely online RL algorithms, in a relaxed setting where µ only satisfies concentrability partially up to a certain time step. Overall, our results offer a quantitative understanding on the benefit of a good reference policy, and make a step towards bridging offline and online RL.

heading: 1 Introduction
text: Reinforcement learning (RL)—where agents learn to play sequentially in an environment to maximize a cumulative reward function—has achieved great recent success in many artificial intelligence challenges such as video games playing [38, 52], large-scale strategy games (e.g. GO) [44, 45], robotic manipulation [3, 32], behavior learning in social scenarios [8], and more. In many such challenging domains, achieving human-like or superhuman performance requires training the RL agent with millions of samples (steps of acting or game playing) or more. Understanding and improving the sample efficiency of RL algorithms has been a central topic of research.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Sample-efficient RL has been studied in a rich body of theoretical work in two main settings: online RL, in which the learner has interactive access to the environment and can execute any policy; and offline RL, in which the learner only has access to an “offline” dataset collected by executing some (one or many) policies within the environment, and is not allowed to further access the environment. These two settings share some common learning goals such as the sample complexity (number of episodes of playing) for finding the optimal policy. However, existing algorithms and theories in the online and offline setting seem rather different and disconnected—In online RL, state-of-the-art sample-efficient algorithms typically explore the entire environment, e.g. by using optimism to encourage visitation to unseen states and actions [9, 27, 19, 41, 21, 5, 22, 12, 23, 53]. In contrast, offline RL does not allow interactive exploration, and sample-efficient policy optimization algorithms typically focus on optimizing an unbiased (or downward biased) estimator of the value function [39, 48, 4, 40, 10, 56, 35, 58, 25, 42]. It is therefore of interest to ask whether these two types of algorithms and theories can be connected in any way.
Further, on the empirical end, insights and patterns from offline RL often help as well in designing online RL algorithms and improving the sample efficiency in the real world. For example, there are online RL algorithms that alternate between data collection steps using a fixed policy, and policy improvement steps by learning on the collected dataset [20]. The replay buffer in value-based algorithms can also be seen as a local form of offline (off-policy) policy optimization and are often be used in conjunction with optimistic exploration techniques [38, 18, 49]. The prevalence of these algorithms also offers practical motivations for us to look for a more unified understanding of online and offline RL in theory. These reasonings motivate us to ask the following question:
Can we bridge sample-efficient offline and online RL from a theoretical perspective?
This paper proposes policy finetuning, a new RL setting that investigates the benefit of a good initial policy in reinforcement learning, and encapsulates challenges of both online and offline RL. In the policy finetuning problem, the learner is given interactive access to the environment and asked to learn a near-optimal policy, but in addition has access to a reference policy µ that is good in certain aspects. This setting offers great flexibility for the algorithm design: For example, the algorithm is allowed to either simply collect data from µ and run any offline policy optimization algorithm on the collected dataset. It is also allowed to play any other policy interactively, including those that adaptively explores the environment. The policy finetuning problem offers a common playground for both offline and online types of algorithms, and has a unified performance metric (sample complexity for finding the near-optimal policy) for comparing their performance.
We study the policy finetuning problem theoretically in finite-horizon Markov Decision Processes (MDPs) with H time steps, S states, and A actions. We summarize our contributions as follows.
• We begin by considering offline reduction algorithms which simply collect data using the reference policy µ and run an offline policy optimization algorithm on the collected dataset. This setting equivalent to offline RL with behavior policy µ, and thus our result translates to a same result for offline RL as well. We design an algorithm PEVI-ADV that is able to find an ε-optimal policy (for small ε) within Õ(H3SC?/ε2) episodes of play, where C? is the single-policy concentrability coefficient between µ and some optimal policy π? (Section 3). This improves over the best existing offline result by anH2 factor in the same setting and matches the lower bound (up to log factors), thereby resolving the recent open question of [42] on tight offline RL under single-policy concentrability.
• Under the same assumption on µ, we establish an Ω(H3Smin {C?, A}/ε2) sample complexity lower bound for any policy finetuning algorithm, including those that adaptively explores the environment (Section 4). This implies that the optimal policy finetuning algorithm is either offline reduction via PEVI-ADV, or a “purely” online RL algorithm from scratch (such as UCBVI), depending on whether C? ≤ A. This comes rather surprising, as it rules out possibilities of combining online exploration and knowledge of µ to further improve the sample complexity over the aforementioned two baselines.
• Finally, we consider policy finetuning in a more challenging setting where µ only satisfies concentrability up to a certain time step. We design a “hybrid offline/online” algorithm HOOVI that combines online exploration and offline data collection, and show that it achieves better sample complexity than both vanilla offline reduction and purely online algorithms in certain cases (Section 5). This gives a positive example on when such hybrid algorithm designs are beneficial.

heading: 1.1 Related work
text: Sample-efficient online RL There is a long line of work on establishing provably sample-efficient online RL algorithms. A major portion of these works is concerned with the tabular setting with finitely many states and actions [9, 27, 19, 5, 11, 2, 22, 63]. For episodic MDPs with inhomogeneous transition functions with S states, andA actions, and horizon lengthH , the optimal sample complexity for finding the ε near-optimal policy is Õ(H3SA/ε2), achieved by various algorithms such as UCBVI of Azar et al. [5] and UCB-Advantage of Zhang et al. [63]. Our paper adapts the reference-advantage decomposition technique of Zhang et al. [63] to designing sharp offline algorithms. Online RL with with large state/action spaces are also studied by using function approximation in conjunction with structural assumptions on the MDP [23, 61, 62, 1, 41, 21, 47, 53, 57, 14, 24].
Offline RL Offline/batch RL studies the case where the agent only has access to an offline dataset obtained by executing a behavior policy in the environment. Sample-efficient learning results in offline RL typically work by assuming either sup-concentrability assumptions [39, 48, 4, 40, 15, 51, 10, 56]) or lower bounded exploration constants [58, 59] to ensure the sufficient coverage of offline data over all (relevant) states and actions. However, such strong coverage assumptions can often fail to hold in practice [16]. More recent works address this by using either policy constraint/regularization [16, 35, 29, 55], or the pessimism principle to optimize conservatively on the offline data [30, 60, 28, 25, 59, 42]. The policy-constraint/regularization-based approaches prevent the policy to visit states and actions that has no or low coverage from the offline data. Our proposed offline RL algorithm PEVI-ADV (Algorithm 1) is inspired by the pessimistic value iteration algorithms of [25, 42] and achieves an improved sample complexity over these work under the same single-policy concentrability assumption on the behavior policy.
Bridging online and offline RL Kalashnikov et al. [26] observed empirically that the performance of policies trained purely from offline data can be improved considerably by a small amount of additional online fine-tuning. A recent line of work studied low switching cost RL [6, 63, 17, 54]— which forbits online RL algorithms from switching its policy too often—as an interpolation between the online and offline settings. The same problem is also studied empirically as deployment-efficient RL [36, 46]. While we also attempt to bridge online and offline RL, our work differs from this line in that our policy finetuning setting allows a direct comparison between “fully offline” and “fully online” algorithms, whereas the low switching cost setting prohibits fully online algorithms.

heading: 2 Preliminaries
text: Markov Decision Processes In this paper, we consider episodic Markov decision processes (MDPs) with time-inhomogeneous transitions, specified by M = (S,A, H,P, r), where S is the state space, A is the action space, H is the horizon length, P = {Ph}Hh=1 where Ph(·|s, a) ∈ ∆S is the transition probabilities at step h, and r = {rh : S ×A → [0, 1]}Hh=1 are the deterministic1 reward functions at time step h ∈ [H]. Without loss of generality, we assume that the initial state s1 is deterministic2.
Policies, value functions, visitation distributions A policy π = {πh(·|s)}h∈[H],s∈S consists of distributions πh(·|s) ∈ ∆A. We use Eπ[·] to denote the expectation with respect to the random trajectory induced by π in the MDP M , that is, (s1, a1, r1, s2, a2, r2, . . . , sH , aH , rH), where ah = πh(sh), rh = rh(sh, ah), sh+1 ∼ Ph(·|sh, ah). For each policy π, let V πh : S → R and Qπh : S ×A → R denote its value functions and Q functions at each time step h ∈ [H], that is,
V πh (s) := Eπ [ H∑ h′=h rh′(sh′ , ah′) ∣∣∣∣sh = s], Qπh(s, a) := Eπ[ H∑ h′=h rh′(sh′ , ah′) ∣∣∣∣sh = s, ah = a]. The operators Ph and Vh are defined as [PhVh+1](s, a) := E[Vh+1(s′)|sh = s, ah = a] and [VhVh+1](s, a) := Var[Vh+1(s′)|sh = s, ah = a] for any value function Vh+1 at time step h + 1.
1While we assume deterministic rewards for simplicity, our results can be straightforwardly generalized to stochastic rewards, as the major difficulty is in learning the transitions rather than learning the rewards.
2Any MDP with stochastic s1 is equivalent to an MDP with deterministic by creating a dummy initial state s0 and increasing the horizon by 1.
We also use P̂h and V̂h to denote empirical versions of these operators building on estimated models (which will be clear in the context).
We use π? := arg maxπ V π 1 (s1) to denote any optimal policy, and V ? h := V π? h and Q ? h := Q π? h to denote the value function and Q function of π? at all h ∈ [H]. Throughout this paper, our learning goal is to find an near-optimal policy π̂ such that V ?1 (s1)− V π̂1 (s1) ≤ ε.
Finally, we let dπh denote the state(-action) visitation distributions of π at time step h ∈ [H]:
dπh(s) := P(sh = s|π), and dπh(s, a) := P(sh = s, ah = a|π).
Miscellaneous We use standard O(·) and Ω(·) notation: A = O(B) is defined as A ≤ CB for some absolute constant C > 0 (and similarly for Ω). The tilded notation A = Õ(B) denotes A ≤ CL ·B where L is a poly-logarithmic factor of problem parameters.

heading: 2.1 Policy Finetuning
text: We now introduce the setting of policy finetuning. A policy finetuning problem consists of an MDP M and a reference policy µ. During the learning stage, the learner can perform the following two types of moves:
(a) Play an episode in the MDP M using any policy (i.e. learner has online interactive access to M ).
(b) Access the values of the reference policy µh(a|s) for all (h, s, a). For example, the learner can use it to sample actions a ∼ µh(·|s) for any h, s for arbitrarily many times during learning.
The goal of the learner is to output ε near-optimal policy π̂ within as few episodes of play (within the MDP) as possible.
A unique feature about the policy finetuning setting is that it allows both online interactive plays via any online RL algorithm (not necessarily using µ), as well as offline reduction which simply collects data by executing the reference policy µ and do anything with the collected dataset. In particular, this means that any algorithm for offline policy optimization (based on offline datasets) also gives an algorithm for policy finetuning via this offline reduction. Therefore, policy finetuning offers a common playground for both online and offline type algorithms with a unified learning goal.
Assumption on reference policy Throughout most of this paper (except for Section 5), we consider the following assumption on the reference policy µ.
Assumption A (Single-policy concentrability). The reference policy µ satisfies that
max h∈[H],(s,a)∈S×A
dπ?h (s, a) dµh(s, a) ≤ C?
(with the convention 0/0 = 0) for some deterministic optimal policy π? and constant C? ≥ 1.
The single-policy concentrability characterizes the distance between the visitation distributions of the reference policy µ and some optimal policy π?. This assumption is considered in the recent work of Rashidinejad et al. [42] on offline RL and is more relaxed than previously assumed concentrability assumptions which typically requires the supremum concentrability against all possible π’s to be bounded [10]. We consider this assumption as it both allows efficient offline RL algorithms [42], and is perhaps also a sensible measure of quality for the reference policy in policy finetuning.

heading: 3 Sharp offline learning via reference-advantage decomposition
text: We begin by investigating the sharpest sample complexity for policy finetuning via the offline reduction approach. This requires us to design sharp offline RL algorithms that run on the dataset D collected by executing µ. We emphasize that this is both an interesting offline RL question on its own right, and also important for our later discussions on lower bounds and other algorithms for policy finetuning, as the sharpest sample complexity via offline reduction provides a solid baseline.
Warm-up: VI-LCB As a warm-up, we first show that a finite-horizon variant of the VILCB (Value Iteration with Lower Confidence Bounds) algorithm of Rashidinejad et al. [42] achieves sample complexity Õ(H5SC?/ε2) for finding an ε near-optimal policy. This result is similar to the Õ(SC?/(1− γ)5ε2) guarantee3 for the original VI-LCB in infinite-horizon discounted MDPs [42, Theorem 6]. The main ingredients of our VI-LCB algorithm is a pessimistic value iteration procedure in which we perform value iteration on the empirical model estimated from the dataset D, along with a negative Hoeffding bonus term to impose pessimism. Due to space constraints, the algorithm description (Algorithm 3) and the proof of Theorem 1 are deferred to Appendix B. Theorem 1 (VI-LCB for finite-horizon MDPs). Suppose the reference policy µ satisfies the singlepolicy concentrability (Assumption A). Then with probability at least 1− δ, VI-LCB (Algorithm 3) outputs a policy π̂ and value estimate V̂ such that
(a) maxh∈[H] ∑ s∈S d π? h (s)(V ? h (s)− V̂h(s)) ≤ ε,
(b) V ?1 (s1)− V π̂1 (s1) ≤ ε, within n = Õ ( H5SC?/ε2 ) episodes.
Theorem 1 serves two main purposes. First, the Õ(H5SC?/ε2) sample complexity asserted in Theorem 1(b) provides a first result for offline RL (and offline reduction for policy finetuning) under single-policy concentrability in finite-horizon MDPs. Second, the value estimation bound in Theorem 1(a) shows that the estimated value function V̂h(s) provided by VI-LCB is close to the optimal value V ?h (s) at every step h ∈ [H], in terms of the weighted average with d π? h (s). Our next algorithm PEVI-ADV builds on this property so that VI-LCB can be used as a “warm-up” learning procedure that provides a high-quality value estimate.
Sharp offline learning via reference-advantage decomposition We now design a new sharp algorithm PEVI-ADV which achieves an improved Õ(H3SC?/ε2) sample complexity (for small enough ε). This improves over VI-LCB by Õ(H2) and is the first algorithm that matches the sample complexity lower bound. PEVI-ADV adds two new ingredients over VI-LCB in order to achieve the Õ(H2) improvement:
1. We replace the Hoeffding-style bonus in VI-LCB with a Bernstein-style bonus. This shaves off one H factor in the sample complexity via the total variance property (Lemma C.4).
2. Both VI-LCB and our PEVI-ADV use data splitting to make sure that the estimated value V̂h+1 and empirical transitions P̂h are estimated using different subsets of D, this yields conditional independence that is required in bounding concentration terms of the form (P̂h − Ph)V̂h+1. However, applied naively, this data splitting induces one undesired H factor in the sample complexity as we need to split D into H folds and thus each Ph is estimated using only n/H episodes of data. As a technical crux of this algorithm, we overcome this issue by adapting the reference-advantage decomposition technique of Zhang et al. [63]. This technique proposes to learn an initial reference value function V̂ ref of good quality in a certain sense, and then performing the following type of approximate value iteration (using the right-hand side as the algorithm update):
PhV̂h+1 ≈ P̂h,0V̂ refh+1 + P̂h,1 ( V̂h+1 − V̂ refh+1 ) .
Above, V̂h+1, P̂h,0, and P̂h,1 are estimated on three disjoint subsets of the data. The advantage of this approach is that, due to this new independence structure, P̂h,0 for different h ∈ [H] can be estimated on the same set of trajectories without H-fold splitting, which shaves off the H factor within this part. On the other hand, estimating P̂h,1 still requires H-fold splitting, yet this would not hurt the sample complexity if the magnitude of (V̂h+1 − V̂ refh+1) is much smaller than its naive upper bound O(H)—we show this can be achieved by using VI-LCB to learn V̂ ref .
3[42] can achieve a faster rate in case C? ≤ 1 + Õ(1/N). However, we focus on the case C? = 1 + Θ(1) where the guarantee of Rashidinejad et al. [42] is Õ(SC?/(1− γ)5ε2).
Algorithm 1 Pessimistic Value Iteration with Reference-Advantage Decomposition (PEVI-ADV) Require: Dataset D = {
(s (i) 1 , a (i) 1 , r (i) 1 , . . . , s (i) H , a (i) H , r (i) H ) }n i=1 collected by executing µ in M .
1: Split the dataset D into Dref , D0 and {Dh,1}Hh=1 uniformly at random:
nref := |Dref | = n/3, n0 := |D0| = n/3, n1,h := |Dh,1| := n/(3H) (n1 := n/3).
2: Learn a reference value function V̂ ref ← VI-LCB(Dref) via VI-LCB (Algorithm 3). 3: Let Nh,0(s, a) and Nh,0(s, a, s′) denote the visitation count of (s, a) and (s, a, s′) at step h
within dataset D0. Construct empirical model estimates:
P̂h,0(s′|s, a)← Nh,0(s, a, s
′)
Nh,0(s, a) ∨ 1 , and r̂h,0(s, a)← rh(s, a)1 {Nh,0(s, a) ≥ 1} .
Similarly define Nh,1(s, a), Nh,1(s, a, s′), (r̂h,1, P̂h,1) for all h ∈ [H] based on dataset Dh,1. 4: Set bh,0(s, a)← c· (√ [V̂h,0V̂ refh+1](s,a)ι Nh,0(s,a)∨1 + Hι Nh,0(s,a)∨1 ) for all (h, s, a), where ι := log(HSA/δ).
5: Set V̂H+1(s)← 0 for all s ∈ S. 6: for h = H, . . . , 1 do 7: Set bh,1(s, a)← c · (√ [V̂h,1(V̂h+1−V̂ refh+1)](s,a)ι Nh,1(s,a)∨1 + Hι Nh,1(s,a)∨1 ) .
8: Perform pessimistic value update for all (s, a): Q̂h(s, a)← r̂h,0(s, a) + [ P̂h,0V̂ refh+1 ] (s, a)− bh,0(s, a) + [ P̂h,1(V̂h+1 − V̂ refh+1) ] (s, a)− bh,1(s, a);
V̂h(s)← [ max a Q̂h(s, a) ] ∨ 0.
9: Set π̂h(s)← arg maxa Q̂h(s, a) for all s ∈ S. 10: end for 11: return Policy π̂ = {π̂h}h∈[H].
We instantiate this plan by carefully using VI-LCB to learn the reference value function V̂ ref , combined with tight Bernstein bonuses, to shave off another H factor in the sample complexity. The full PEVI-ADV algorithm is provided in Algorithm 1. We now present its guarantee in the following theorem. The proof can be found in Appendix C.
Theorem 2 (Sharp offline learning via PEVI-ADV). Suppose the reference policy µ satisfies the single-policy concentrability (Assumption A). Then with probability at least 1− δ, PEVI-ADV (Algorithm 1) outputs a policy π̂ and value estimate V̂ such that
(a) maxh∈[H] ∑ s∈S d π? h (s)(V ? h (s)− V̂h(s)) ≤ ε,
(b) V ?1 (s1)− V π̂1 (s1) ≤ ε,
within n = Õ ( H3SC?/ε2 +H5.5SC?/ε ) episodes.
Near-optimal offline RL under single-policy concentrability For small enough ε ≤ H−2.5, Theorem 2 achieves Õ(H3SC?/ε2) sample complexity for finding the ε near-optimal policy from the offlien dataset D. This is the first cubic horizon dependence for offline RL under single-policy concentrability, which improves over recent works [25, 42] in this setting and resolves the open question of [42]. For C? ≥ 2, our sample complexity further matches the information-theoretical lower bound Ω(H3SC?/ε2) up to log factors4. We remark that tight hoziron dependence has also been achieved in several recent works offline RL [58, 59, 43] which are however quite different from (and do not imply) ours in both the assumptions (on the behavior policy) and the analyses.
4This lower bound can be adapted directly from a Ω(SC?/(1− γ)3ε2) lower bound of [42, Theorem 7].

heading: 4 Lower bound for policy finetuning
text: We now switch gears to considering the policy finetuning problem with any algorithm, not necessarily restricted to the offline reduction approach.
Two baselines: offline reduction & purely online RL A first observation is that naive offline reduction is already a strong baseline for policy finetuning, by our Theorem 2: Our PEVI-ADV algorithm only collects data with µ and does not do any online exploration, yet achieves a sharp Õ(H3SC?/ε2) sample complexity for finding a near-optimal policy.
On the other hand, as the policy finetuning setting allows online interaction, purely online RL is another baseline algorithm: Simply run any sample-efficient online RL algorithm (which typically uses optimism to encourage exploration) from scratch, and disregard the reference policy µ. Using any sharp online RL algorithm such as UCBVI [5], this approach can find an ε near-optimal policy within Õ(H3SA/ε2) episodes of play. Note that whether this is advantageous over the offline reduction boils down to the comparison between C? and A, which makes sense intuitively. For example, C? ≤ o(A) means that µ is perhaps close enough to π? so that collecting data from µ and run offline policy optimization is a stronger algorithm than exploring from scratch.
Given these two baselines, it is natural to ask whether there exists an algorithm that improves over both — Can we design an algorithm that performs some amount of optimistic exploration, yet also utilizes the knowledge of µ, so as to achieve a better rate than both offline reduction and purely online RL? In this section, we provide an information-theoretic lower bound showing that, perhaps surprisingly, the answer is negative: there is an Ω(H3Smin {C?, A}/ε2) sample complexity lower bound for any policy finetuning algorithm, if we still assume that µ satisfies C? single-policy concentrability.
Lower bound To formally state our lower bound, we define the class of problems
MC? := { (M,µ) : Exists deterministic π? of M such that sup
h,s,a
dπ?h (s, a) dµh(s, a) ≤ C?
} . (1)
We recall that a policy finetuning algorithm for problem (M,µ) is defined as any algorithm that can play in the MDP M for n episodes, has full knowledge of the reference policy µ, and outputs a policy π̂ after playing in the MDP.
With these definitions ready, we now state our lower bound for policy finetuning. The proof of Theorem 3 can be found in Appendix D.
Theorem 3 (Lower bound for policy finetuning). Suppose S,H ≥ 3, A ≥ 2, C? ≥ 2. Then, there exists an absolute constant c0 > 0 such that for any ε ≤ 1/12 and any online finetuning algorithm that outputs a policy π̂, if the number of episodes
n ≤ c0 ·H3Smin {C?, A}/ε2,
then there exists a problem instance (M,µ) ∈ MC? on which the algorithm suffers from εsuboptimality:
EM [ V ?1,M − V π̂1,M ] ≥ ε,
where the expectation EM is w.r.t. the randomness during the algorithm execution within MDP M .
Either offline reduction or purely online is optimal Theroem 3 shows that any policy finetuning algorithm needs to play at least Ω(H3Smin{C?, A}/ε2) episodes in order to find an ε near-optimal policy. Crucially, this implies that either a sharp offline reduction (e.g. our PEVI-ADV algorithm) or purely online RL matches the lower bound (up to log), depending on whether C? . A. In other words, if we have the knowledge of whether C? ≤ A, choosing the right one of these two baseline algorithms will yield the optimal sample complexity. Perhaps surprisingly, this rules out the possibility of designing any algorithm “in between” that combines online exploration and knowledge of µ to improve the sample complexity, at least in the worst-case over all problems inMC? . We argue that this “no algorithm in between” phenomenon may be due to the single-policy concentrability assumption being too strong such that offline reduction already achieves a rather competitive sample
Algorithm 2 Hybrid Offline/Online Value Iteration (HOOVI) Require: MDP M , reference policy µ.
1: # Stage 1: Learn step h? + 1 : H via optimistic online exploration 2: for Episode k = 1, . . . , nUCB = n/2 do 3: Receive initial state s1 and play with policy µ up to step h?. Arrive at state sh?+1. 4: Play step h? + 1 to H using the UCBVI-UPLOW algorithm (Algorithm 4). 5: end for 6: Denote the final output of UCBVI-UPLOW as
(V h?+1, V h?+1, π̂ UCB (h?+1):H )← UCBVI-UPLOW(nUCB).
7: # Stage 2: Learn step 1 : h? via executing µ + pessimistic offline policy optimization 8: Collect D ← {n− nUCB episodes of data using policy µ up to step h?}. 9: Learn policy π̂PEVI1:h? via the TRUNCATED-PEVI-ADV(Algorithm 5):
π̂PEVI1:h? ← TRUNCATED-PEVI-ADV(D, h?, V h?+1).
10: return Policy π̂ = (π̂PEVI1:h? , π̂ UCB (h?+1):H ).
complexity Õ(H3SC?/ε2). We investigate policy finetuning beyond the single-policy concentrability assumption in Section 5.
We also remark that Theorem 3 generalizes both the Ω(H3SA/ε2) lower bound for online RL [11, 58, 13] into the policy finetuning problem, as well as the Ω(H3SC?/ε2) lower bound for offline RL under single-policy concentrability with C? ≥ 2 [42]5. Further, Theorem 3 directly implies an Ω(H3SC?/ε2) lower bound for offline RL with 2 ≤ C? ≤ O(A), as any algorithm for offline policy optimization is also an algorithm for policy finetuning via the offline reduction.
Proof intuition; Construction of hard instance The proof of Theorem 3 constructs a family of hard MDPs that requires solving HS “independent” bandit problems with A arms, similar as in existing Ω(H3SA/ε2) lower bounds for online RL [11, 58]. However, our key modification is that we let the optimal arms to be always within the first K := min {C?, A} actions instead of all A actions, and we define our reference policy µ to play uniformly within [K]. This µ has the following properties:
• µ satisfies C? single-policy concentrability for any MDP in this family (Lemma D.1).
• µ provides the knowledge that the optimal actions are within [K], but no other knowledge about the optimal actions.
Therefore, with µ at hand, any policy finetuning algorithm can “gain the knowledge” that the optimal actions are within [K], but still needs to try all K actions in order to solve each bandit problem— rigorizing this information-theoretically gives the Ω(H3SK/ε2) = Ω(H3Smin {C?, A}/ε2) lower bound.

heading: 5 Hybrid offline/online algorithm for policy finetuning
text: Towards circumventing the lower bound in Theorem 3, in this section, we study policy finetuning under more relaxed assumptions on the reference policy µ. A weaker µ will induce a higher sample complexity for naive offline reduction approaches, and thus yields opportunities for designing new algorithms that can potentially better utilize µ.
More concretely, we consider the following relaxation: We assume µ satisfies partial concentrability only up to a certain time-step h? ≤ H , and may not have any bounded concentrability at steps h > h?. We formalize this in the following
5The lower bound in [42] is Ω(SC?/ε2(1 − γ)3) for the infinite-horizon γ-discounted setting, which corresponds to an Ω(H3SC?/ε2) lower bound for our finite-horizon setting.
Assumption B (h?-partial concentrability). The reference policy µ satisfies the single-policy concentrability with respect to π? up to step h? only:
max h≤h? max s,a∈S×A
dπ?h (s, a) dµh(s, a) ≤ Cpartial
(with the convention 0/0 = 0), where π? is some deterministic optimal policy of the MDP, and constant Cpartial ≥ 1.
Algorithm description We design a hybrid offline/online algorithm HOOVI (presented in Algorithm 2) for policy finetuning under the partial concentrability assumption. At a high-level, the algorithm consists of two main stages:
• In the first stage, it runs an online algorithm UCBVI-UPLOW which uses optimistic exploration to find a near-optimal policy π̂UCB and an accurate value estimate for steps (h? + 1) : H .
• In the second stage, we run a TRUNCATED-PEVI-ADV algorithm, which collects data from µ and runs offline policy optimization to find a near-optimal policy π̂PEVI for steps 1 : h?, building on the lower value estimate V h?+1 from the first stage.
This strategy makes sense intuitively as the reference policy µ does not have guarantees for steps h? + 1 : H and thus the algorithm is required to perform optimistic exploration first to get a good policy. However, additional technical cares are needed in order to make the above algorithm provably sample-efficient. The analysis of the second stage requires the online algorithm in the first stage to not only perform fast exploration (e.g. by using upper confidence bounds), but also output a lower value estimate for step h? + 1, and in addition output a final output policy that achieves at least the value of the lower value estimate at every state s ∈ S. Such lower bounds are not directly available in standard online RL algorithms such as UCBVI [5]. We resolve this by designing the UCBVI-UPLOW algorithm (detailed description in Algorithm 4), which is a modification of the Nash-VI Algorithm of Liu et al. [34] (for two-player Markov games) into the single-player case. This algorithm is particularly suitable for our purpose since it maintains both upper bounds of V ? and lower bounds for the value function of the deployed policies. Our UCBVI-UPLOW further integrates the certified policy technique of Bai et al. [7] to make sure that its output policy achieves value greater or equal than the lower bound at every state (similar guarantees can also be obtained by the policy certificate technique of Dann et al. [12]). We now state our main theoretical guarantee for the HOOVI algorithm. The proof can be found in Appendix E. Theorem 4 (Hybrid online / offline learning for policy finetuning). Suppose the reference policy µ satisfies the partial concentrability (Assumption B) up to some step h? ≤ H . Then for small enough ε ≤ min { h−2.5? , C partial/S }
, HOOVI (Algorithm 2) outputs a policy π̂ such that V ?1 (s1)− V π̂1 (s1) ≤ ε with probability at least 1− δ, within
n = Õ
( H2h?SC partial + (H − h?)3SA(Cpartial)2
ε2 ) episodes of play.
Comparison against offline reduction and purely online algorithms The sample complexity in Theorem 4 compares favorably against both naive offline reduction as well as purely online algorithms in certain situations. First, naive offline reduction with µ does not have any guarantee since µ is not assumed to have a finite single-policy concentrability at h ≥ h? + 1. We can modify µ into µ′ that plays uniformly within A at steps h ≥ h? + 1; the single-policy concentrability coefficient of µ′ is guaranteed to be finite but scales exponentially as O(AH−h?) in the worst case, leading to a sample complexity much worse than ours (which is polynomial in H,S,A).
On the other hand, a sharp online algorithm can still achieve Õ(H3SA/ε2) in this setting (by optimistic exploration from scratch). Our Theorem 4 is in general incomparable with this, but can be better in cases when both Cpartial and H − h? are small, e.g., if Cpartial = o(A) and (H−h?)/H = o((Cpartial)−2/3). This makes sense intuitively as our hybrid offline/online algorithm benefits the most if the length requiring exploration (H − h?) is small, and the partial concentrability Cpartial is small so that µ still has a high-quality for the first h? steps. To best of our knowledge, this is first result that characterizes when the sample complexity of such hybrid algorithms can be beneficial over purely online or offline algorithms.

heading: 6 Conclusion & discussions
text: This paper studies policy finetuning, a new reinforcement learning setting that allows us to compare and connect sample-efficient online and offline reinforcement learning. We establish sharp upper and lower bounds for policy finetuning under various assumptions on the reference policy. Our bounds show that the optimal policy finetuning algorithm is either offline reduction or a purely online algorithm in the specific setting where the reference policy satisfies single-policy concentrability, and we also show that a hybrid online/offline algorithm can be advantageous over both in more relaxed settings. Many directions could be of interest for future research, such as alternative assumptions on the reference policy, or policy finetuning with function approximation.
Also, while our contributions are mainly theoretical, implementing or extending our policy finetuning algorithms on real-world RL tasks would be a compelling future direction. When the environment is a tabular MDP, our Algorithm 1 (offline reduction) and Algorithm 2 (hybrid offline / online RL) are readily implementable. When there is large state/action space and potentially function approximation, we believe our algorithm can be adapted, for example, by replacing all the optimistic/pessimistic value iteration steps by DQN-type algorithms [38] with positive/negative bonus functions [50]. Experimental evaluation of such algorithms would be a good direction for future work.

heading: Acknowledgment
text: The authors would like to thank Ming Yin, Chi Jin and David Forsyth for the many insightful discussions. NJ acknowledges funding support from the ARL Cooperative Agreement W911NF17-2-0196, NSF IIS-2112471, and Adobe Data Science Research Award. HW, CX, YB are funded through employment with Salesforce.

Review summaries:
This paper provides a theoretical framework for policy finetuning in episodic finite-horizon MDPs, where the agent can interact with the environment online and also has access to offline data from a reference policy. The authors develop/provides three main results:  (1) A fully offline algorithm based on finite-horizon VI-LCB (Rashidinejad et al.'21) and improving its near-optimal sample complexity by the order of O(H^2) in polylogarithmic time (H being the horizon length). This is done by (a) replacing Hoeffding bonus in VI-LCB with Bernstein bonus and (b) adopting the reference-advantage decomposition technique of (Zhang et al'20)  (2) Under concentrability assumption (boundedness of state-action importance weights w.r.t some optimal policy), the authors argue that there is no finetuning algorithm with better sample complexity than the extreme cases(purely online or the proposed offline algorithm) for some MDP and reference policy. This establishes a lower bound for finetuning.  (3) A partial concentrability assumption (reference policy is only guaranteed to satisfy concentrability up to a certain step) and a two-satge hybrid algorithm based on Nash-VI algorithm(Liu, et.al'20) and truncated version of their proposed offline algorithm.

The paper attempts to bridge the gap in theory for online and offline RL. The paper introduces a theoretical study of policy fine-tuning, an online RL setup where the learner has access to policy close to the optimal policy in a certain metric. Then the authors introduce a shart offline reduction algorithm that collects data using this policy and then runs offline RL training on the collected data and prove a converge bound for this algorithm. Then authors establish a lower bound on any policy fine-tuning method. Finally, the authors design a new hybrid offline/online algorithm.

This paper studies policy finetuning, a new reinforcement learning setting that allows us to compare and connect sample-efficient online and offline reinforcement learning. We establish sharp upper and lower bounds for policy finetuning under various assumptions on the reference policy. Our bounds show that the optimal policy finetuning algorithm is either offline reduction or a purely online algorithm in the specific setting where the reference policy satisfies single-policy concentrability, and we also show that a hybrid online/offline algorithm can be advantageous over both in more relaxed settings. Many directions could be of interest for future research, such as alternative assumptions on the reference policy, or policy finetuning with function approximation.  This paper investigates theoretical aspects of policy fine tuning where the goal is to find a near optimal policy when a reference policy is given. They study this problem under two assumptions:  1- Reference policy \mu satisfies single-policy concentrability. 2- Reference policy \mu satisfies concentrability up to a certain time step which is a more relaxed than the first assumption.  Under these assumptions for the first time sharp upper and lower bounds for policy finetuning is stablished.