Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
Authors: Tengyang Xie
Nan Jiang
Huan Wang
Caiming Xiong
Yu Bai
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning theory
offline RL
online RL
policy finetuning

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" $\mu$ close to the optimal policy $\pi_\star$ 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 $\mu$ and runs offline policy optimization on the collected dataset---that finds an $\varepsilon$ near-optimal policy within $\widetilde{O}(H^3SC^\star/\varepsilon^2)$ episodes, where $C^\star$ is the single-policy concentrability coefficient between $\mu$ and $\pi_\star$. 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 $\Omega(H^3S\min\{C^\star, A\}/\varepsilon^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 $\mu$. 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 $\mu$ 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. 

Policy Finetuning: Bridging Sample-Eficcien Offline and Online Reinforcement Learning
Tengyang Xie UICC tx1001llinois.eed edu
Nan Jiang UICC nanjiang@illinoss.ddu
Huan Wang Salesforce Research huan. www.eaaleseorre.ecoomm
Caiming Xiong
Yu Bai
Salesforce Research cxiong@salesforcee com
Salesforce Research yu. www.ba@s@eeeffore..com com
Abstract
Recent theoretical work studies sample-efficient reinforcement learning (RL) ex- tensively 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" μr close to the optimal policy T. a certain sense. We con- sider the policy finetuning problem in episodic Markov Decision Processes (MDPs) with S states, actions, and horizon length H. We first design a sharp offtine reduction algorithm- which simply executes μ and runs offline policy optimization the collected dataset- that finds near-optimal policy within O(H episodes, where C* is the single-policy concentrability coefficient between and m. 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 Q(H m EE") sample complexity lower bound for any policy fine- tuning algorithm, including those that can adaptively explore the environment. This implies that Stat-perhapee surprisingly the optimal policy finetuning algorithm is either offline reduction or purely online RL algorithm that does not use μ.. Finally, we design new hybrid offline/online algorithm for policy finetuning that achieves better sample complexity than both vanilla offline reduction and purely online RL algorithms, relaxed setting where l only satisfies concentrability partially up to a certain time step. Overall, our results offer a quantitative understanding the benefit of a good reference policy, and make a step towards bridging offline and online RL.
Introduction
Reinforcement learning (RL) wher- agents learn to play sequentially in an environment to maximize cumulative reward function hasooon-hasss 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 game playing) more. Understanding and improving the sample efficiency of RI. algorithms has been a central topic of research.
35th Conference on Neural Information Processing Systems (NcurIPS 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 RI., in which the learner only has access to an "offline" dataset collected by executing some (one or many) policies within the environment, and 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-efficien 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- pooicooooyy 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 offiie RL in theory. These reasonings motivate us to ask the following question:
Can we bridge sample-efficient offline and online flom a theoretical perspective?
This paper proposes policy finetuming, a new RL setting that investigates the benefit of good initial policy 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 near-optimal policy, but in addition has access to a reference policy l that is good certain aspects. This setting offers great flexibility for the algorithm design: For example, the algorithm is allowed to either simply collect data from j 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 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 Jr, 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 c-optimal policy (for small E) within SC* /=²) episodes of play, where C* is the ungle-policy concentrability coefficient between μ and some optimal policy R,, (Section 3). This improves over the best cxisting offline result by an 2² factor in the same setting and matches the lower bound (up to log factors), thereby resolving the recent open question of [42] tight offline RL under single-policy concentrability.
Under the same assumption on μt, we establish an S min (C*, A)/s²) sample complexity lower bound for any policy finetuning algorithm, including those that adaptively explores the environment (Section 4). This implies that the optimal policy finetuming algorithm is either offline reduction via PEVI-ADV, or a "purely" online RL algorithm from scratch (such as UCBVI), depending 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 con- centrability 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 positive example on when such hybrid algorithm designs are beneficial.
2

---

1.1 Related work
Sample-efficient online RL There 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, and A actions, and horizon length H, the optimal sample complexity for finding the near-optimal policy is SA/" achieved by various algorithms such UCBVI of Azar et al. [5] and UCB-Advantage of Zhang et al. [63]. Our paper adapts the reference-advantagge decomposition technique of Zhang et al. [63] 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, 41, 21, 47, 53, 57, 14, 24].
Offinn RL Offline/batch RL studies the case where the agent only has access to an offline dataset obtained by executing behavior policy in the environment. Sample-effccient 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/regulaizzttioo [16, 35, 29, 55]. or the pessimism principle to optimize conservatively wtwpri//rrrgguariiittooonaasees 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
on the offline data [30, 60, 28, 25, 59, 42]. The polieyy-oonttaiinrrgullaiiizzi
inspired by the pessimistic value iteration algorithms of [25, 42] and achieves an improved sample complexity over these work under the same single-pole pogll--polcyyooo 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-efficienn 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 direct comparison between "fully offline" and "fully online" algorithms, whereas the low switching cost setting prohibits fully online algorithms.
2 Preliminaries
Markov Decision Processes In this paper, we consider episodic Markov decision processes (MDPs) with time-inhomogeneous transitions, specified by M = AS H, P. r), where S is the state space, A is the action space, H is the horizon length, probabilities at step and r (rn S A + [0, _]} are the deterministic' reward functions at time step h E [H). Without loss of generality, we assume that the initial state i is deterministic".
(PP 1 h=1 where [- (-Is, a) As is the transition
Policies, value functions, visitation distributions A policy म = =m (-1))) he(ul,ee consists of distributions TA (-[s) E A.A. We use [-]] to denote the expectation with respect to the random trajectory induced by i in the MDP M, that is, (81, (11, ri, 82, (22 .2, 851 an, rw), where On. = Th (8)), FA [s(S,, (n), 81+1 ~ IPa (2(-118.. ax). ). For each policy let V : :S + R and Q x A R denote its value functions and Q functions at each time step h E [H]. that is,
H (se an) (a((ssww))))))
H
V (s) = E,
s (% = E,
Σ A h
Th (SNr and = 8, s,a,
The operators Pj and Vn defined as [PA Vh+1 ()s a) == E (8') 8, an a) and WAVe+1l(s, a) = Var = 8, az a) for any value function Va+1 at time step + 1.
'While 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.
2 "Ayy MDP with stochastic sı is equivalent to an MDP with deterministic by creating a dummy initial state so and increasing the horizon by 1.
3

---

We also use PA and V% to denote empirical versions of these operators building on estimated models (which will be clear in the context).
We use n. = arg m VT" (81) to denote any optimal policy, and V = V and Q == 0% to denote the value function and Q function of I" all [H]. Throughout this paper, our learning goal is to find an near-optimal policy such that Vi (s1) (s1) S.
Finally, we let d% denote the state(-action) visitation distributions of x at time step h E [H]:
(s) = (s, s/T), and (s. P(ss) 8, a/)r).
Miscellaneous We use standard O()) and S2-)) notation: A = O(B) is defined as S CB for some absolute constant C > (and similarly for Q). The tilded notation A = ((B) denotes A S CL B where L is a poly-logarilmmic factor of problem parameters.
2.1 Policy Finetuning
We now introduce the setting of policy finetuning. A policy finetuning problem consists of an MDP M and reference policy μ. During the learning stage, the learner can perform the following two types 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 na, (a]s) for all (h, 8, a). For example, the learner can it to sample actions a (-1s)) for any h, for arbitrarily many times during learning.
The goal of the learner is to output near-optimal policy â within few episodes of play (within the MDP) as possible.
unique feature about the policy finetuning setting is that allows both online interactive plays via any online RL algorithm (not necessarily using μ)) as well as offfine 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 common playground for both online and offline type algorithms with unified learning goal.
Assumption reference policy Throughout most of this paper (except for Section 5), consider the following assumption on the reference policy μ.
Assumption A (Single-policy concentrability). The reference policy μ satisfies that
(s, (s,a)
max (E()),,
S C*
(with the convention 0/0- for some deterministic optimal policy n, and constant C* 2
The single-policy concentrability characterizes the distance between the visitation distributions the reference policy and some optimal policy n². This assumption is considered in the recent work of Rashidineeja et al. [42] on offline RL and more relaxed than previously assumed concentrability assumptions which typically requires the supremum concentrability against all possible x' to be bounded [10]. We consider this assumption as both allows efficient offline RL algorithms [42]. and is perhaps also a sensible measure of quality for the reference policy in policy finetuning.
3 Sharp offline learning via reference-advantage decomposition
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 RI question on its own right, and also important for our later discussions on lower bounds and other algorithms for policy finetuning, the sharpest sample complexity via offline reduction provides solid bascline.

---

Warm-up: VI-LCB As warm-up, we first show that finite-horizon variant of the VI- LCB (Value Iteration with Lower Confidence Bounds) algorithm of Rashidinejad al. [42] achieves sample complexity O(H SC* /E") for finding an e near-optimal policy. This result similar to the Ó(SC*/(L (11 - = guarantee" for the original VI-LCB in anfiiie-horizon discounted MDPs [42, Theorem 6]. The main ingredients of our VI-LCB algorithm a pessimistic value iteration procedure in which we perform value iteration on the empirical model estimated from the dataset D, along with negative Hoeffding bonus term to impose pessimism. Due to space constraints, the algorithm description (Algorithm 3) and the proof of Theorem I are deferred to Appendix B.
Theorem (VI-LCB for kmite-horizon MDPs). Suppose the reference policy μa satisfies the single- policy concentrabillty (Assumption A). Then with probability at least 1 - 6, VI-LCB (Algorithum 3)
outputs policy ãे and value estimate V such that
(a) [M Exes (s)( (()(()s))V((()) SE.
(b) - S..
within Ö(H* /2)) episodes.
Theorem serves two main purposes. First, the Ö(HSSC* 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 horte-horizon MDPs. Second, the value estimation bound in Theorem (() shows that the estimated value function (s) provided by VI-LCB is close to the optimal value Vř (s) at every step h [H], in terms of the weighted average with d% (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 high-quality value estimate.
Sharp offline learning via reference-advantagg decomposition We now design new sharp algorithm PEVI-ADV which achieves an improved Ö(H ((HSSCC/E2 /E?) sample complexity (for small enough E). This improves over VI-LCB by Ö(H²) 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(H²) improvement:
We replace the Hoeffding-style bonus 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 Ve+1 and empirical transitions IP, are estimated using different subsets of D, this yields conditional independence that is required in bounding concentration terms of the form (P,, PA PA) V 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 IF,, is estimated using only n/H episodes of data.
As a technical crux of this algorithm, we overcome this issue by adapting the -avrenntaedd decomposition technique of Zhang et al. [63]. This technique proposes to learn initial reference value function Freef 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):
Ph Pr z Pref + Ph.1 (Vi+1
Free 1++1
Above, Dr+1, Pr.. and h, are estimated on three disjoint subsets the data. The advantage of this approach is that, due to this new independence structure, Ph.D for different h E [H] can be estimated on the same set of trajectories without //fold splitting, which shaves off the H factor within this part. On the other hand, estimating iPr, still requires H-fold splitting, yet this would not hurt the sample complexity if the magnitude of (Vr+1 Viref ) is much smaller than its naive upper bound O(H) we show this can be achieved by using VI-LCB to learn Peeff
1422 can achieve faster rate in case C* < 1 Ō(1NN). However, we focus the C' 1 0(1) where the guarantee of Rashidinejad al. [42] is Ö(SC* /(1 (111111--50 =2)
5

---

Algorithm 1 Pessimistic Value Iteration with Reference-Advantaae Decomposition (PEVI-ADV)
Require: Dataset D = { (() (+) (8)
(5) (()
} collected by executing μ in M.
1 .....
i=1
1:
Split the dataset into Dref, Do and (DA, 1 uniformly at random:
Thref == /eerl n//3, no (Pol n/3, 11, [Pr,1 n2(3H) (M1 == n/3).
2: Learn a reference value function Vreef + (I-LC via VI-LCB (Algorithm 3).
3: Let No, a) and Ns, a, s') denote the visitation count of (s, a) and (s, a,s') at step h within dataset Do. Construct empirical model estimates:
Fn.o(d' an,o(s,a.s) and Fn,0(8,a) rn(s,))1 (Mu,(ss 2 13. an)o(s,a)VI VT
Similarly define (s,1 a), (8, (s, 8'), (Fa,1, PA.1) for all [H] based dataset Dr.1-
4: Set (8, t c. (V Con
He for all (h, 8, a), where c. == log(HSA/6).
Maaaaaiiii Na.oss.jvi
5: Set (1s) + 0 for all s E.
6: for h H...... do
(v [B.. ( ([s,a)) + Na.(enoyv)
7: Set bn, (s, a) c..
He
Nai(s.o/Vi
8: Perform pessimistic value update for all as)
(8, a) <- Fn,o(s. a) + iPnoo N+1 (8, un,00, + [PPL - -Dnti) (s, (s,
[a(s)) - max Qu a) vo.
9: Set 7. (8) &- arg max, a)) for all 8 E.
10: end for
11: return Policy के (a))e((H]
We instantiate this plan by carefully using VI-LCB to learn the reference value function Pree 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 (Sharp offline learning via PEVI-ADV). Suppose the reference policy μ satisfies the single-policy concentrability (Assumption A). Then with probability least 6, PEVI-ADV (Algo- rithm 1) outputs a policy के and value estimate V such that
(a) maNNe(M] Eees di (s) vh(s)) SE.
- ( S (b)
within = Ō0 H5.5 episodes.
Near-optimal offline RL under single-policy concentrability For small enough ε H H22 Theorem 2 achieves 3C* sample complexity for finding the E near-optimal policy from the offlien dataset D. This is the first cubic horizon dependence for offline RL under singlc-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 informatioo-thhoretiie lower bound 2 SC' /e2) up to log factors*. 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.
'This lower bound can be adapted directly from ((SC' /(1 =)) lower bound of [42, Theorem 7].

---

4 Lower bound for policy finetuning
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 strong baseline for policy finetuning, by our Theorem 2: Our PEVI-ADV al- gorithm only collects data with and does not do any online exploration, yet achieves a sharp Ó(H SC* /E²) sample complexity for finding a near-optimal policy.
On the other hand, the policy finetuning setting allows online interaction, purely online RL is another baseline algorithm: Simply run any sample-efficient online RI. 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 SA/E) 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 y is perhaps close enough to so that collecting data from f and run offline policy optimization 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 μu, so as to achieve a better rate than both offline reduction and purely online RL? In this section, we provide an information ceeematto--thooeticc lower bound showing that, perhaps surprisingly. the answer is negative: there is an Q H S min {C*, AA//E²) 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
t (s.a) h,e.a (s.a)
Mc- == (M, (M, p): Exists deterministic π. of M such that sup
(I)
We recall that a policy finetuning algorithm for problem (M, μ1) is defined any algorithm that can play in the MDP M for episodes, has full knowledge of the reference policy p. and outputs a policy î after playing the MDP.
With these definitions ready, we now state our lower bound for policy finetuning. The proof of Theorem can be found in Appendix D.
Theorem 3 (Lower bound for policy finetuning). Suppose 8, H > 3, A 2, C* > 2. Then, there exists an absolute constant co > 0 such that for any E S 1/12 and any online finetuning algorithm that outputs policy ft, if the number of episodes
n S S min (C", A//s"'
then there exists a problem instance (M,μ) E MMc on which the algorithm suffers from suboptimality:
EM Vi.Ms VilMM 2e,
where the expectation Ey is w.r. 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 2(H2 m A}/e²) episodes in order to find an near-optimal policy. Crucially, this implies that either 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 in Mc.. 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
7

---

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, . RUCB nn/2 do
3: Receive initial state $, and play with policy i up to step h, Arrive at state $h,
4: Play step /, + H using the UCBVI-UPLOW algorithm (Algorithm 4).
5: end for
6: Denote the final output of UCBVI-UPLOW
UCB (V +I+ Vn, +1 (b++1):H) + UCBVI-UPLOW(MUcs))
7: # Stage 2: Learn step 1 h4 via executing pessimistic offline policy optimization
8: Collect D +- {n RUCB episodes of data using policy μl up step h,
9: Learn policy PPVV via the DEAIICATEE--EVI-AAVVAAAAOO #1:h,
5);
PEVI TRUNCATED- h,, V +1,+1)-
lsh,
UCB return Policy मे 111hh " (b++1):))
complexity Ö(H² DCHSSC//E) /E") We investigate policy finetuning beyond the single-policy concentrability assumption in Section 5.
We also remark that Theorem 3 generalizes both the Q(H* lower bound for online RL [1 58, 13] into the policy finetuning problem, as well the Q(H /²²) lower bound for offline RL under single-policy concentrability with C* 2 2 [42] Further, Theorem 3 directly implies an Q(H /e²) lower bound for offline RI. with 2 S C s ((), 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 Theorem 3 constructs a family of hard MDPs that requires solving HS "independent" bandit problems with A arms, similar as in existing ((H$SA/ SA/²") lower bounds for online RL [11, 58). However, our key modification 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).
fi 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 anformation-theoreticalll gives the (2(HSSK/e" 2 min (C),)) lower bound.
5 Hybrid offline/online algorithm for policy finetuning
Towards cireumventing the lower bound in Theorem 3, in this section, 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 ht < H, and may not have any bounded concentrability steps h. We formalize this the following
'The lower bound in [42] is Q(SC* /e² )) for the infinite horizon y-discounted setting, which corresponds to 2 SC*
/e²) SC"/""
lower bound for our finite-horizon setting.

---

Assumption B -partal concentrability), The reference policy satisfies the single-policy concen- trability with respect to n, up to step h2 only:
dh (s,a) hgh, 8.EEXA 0% (s,
I &CPartial
max max
(with the convention 0/0 = 0), where n. is some deterministic optimal policy of the MDP, and constant Opartial
L.
Algorithm description We design a hybrid offline/online algorithm HOOVI (presented in Al- gorithm 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 CEUUNCAEE--EVIIIIE and runs offline policy optimization to find near-optimal policy PPEVI for steps h,, building on the lower value estimate Vn, +1 from the first stage.
algorithm, which collects data from
This strategy makes sense intuitivelyy as the reference policy 1 does not have guarantees for steps h4 - 1: H and thus the algorithm is required to perform optimistic exploration first to get a good policy. However, additional technical cares needed in order to make the above algorithm provably sample-efficiet. 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 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 E Such lower bounds are not directly available in standard online RL algorithms such as UCBVI [5].
We resolve this by designing the VI-VIL algorithm (detailed description in Algorithm 4), which is modification of the Nash-VI Algorithm of Liu et al. [34] (for two-player Markov games) into the single-plag 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 UCB UCBVI-UPLOW further integrates the certified policy technique of Bai et al. [7] to make sure that its output policy achieves value greater equal than the lower bound 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 ht S H. Then for small enough S min { Cpartial /S). HOOVI (Algorithm 2) outputs a policy ā such that Vi (81) V (s1) S e with probability at least 1 8, within
n = Ō Hhh (H h())SA(Crarraaa))
g2
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 f does not have any guarantee since μ is not assumed to have finite single-policy concentrability at h > h2 + 1. We can modify μ into μ' that plays uniformly within A at steps h Z h4 + 1; the single-policy concentrability coefficient u' is guaranteed to be finite but scales exponentially as O(A#-h.) in the worst case, leading to a sample complexity much worse than ours (which is polynomial in H, A).
On the other hand, a sharp online algorithm can still achieve O(H*S//²²) in this setting (by optimistic exploration from scratch). Our Theorem is in general incomparable with this, but can be better in cases when both O'arttial and H h4 are small, e.g., if Opartiill o(A) and (H HH-hh ) H- ([[CPartial-=2/) benefits the most if the length requiring exploration (H It..) small, and the partial concentrability Caartial 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 offline algorithms.
This makes sense intuitively as our hybrid offline/online algorithm

---

Conclusion & discussions
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 offiine reduction 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, policy finetuning with function approximation.
Also, while our contributions are mainly theoretical, implementing or extending our policy finetuning algorithms real- world RL tasks would be compelling future direction. When the environment is a tabular MDP, our Algorithm (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/pessimisiic 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.
Acknowledgment
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 W91 17-2-0196, NSF I1S-21 and Adobe Data Science Research Award. HW, CX, YB are funded through employment with Salesforce.
References
[1] A. Agarwal, S. Kakade, A. Krishnamurthy, and W. Sun. Flambe: Structural complexity and representation learning of low rank mdps. arXiv preprint 2xXiv:2006.10814 2020.
[2] S. Agrawal and R. Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 1184-1 194, 2017.
[3] Akkaya, M. Andrychowicz, M. Chociej, M. Litwin, B. McGrew, A. Petron, A. Paino, M. Plappert, G. Powell, R. Ribas, et al. Solving rubik's 's cube with a robot hand. arXiv preprini 1rXiv:1900007111 2019.
[4] A. Antos, C. Szepesvári, and R. Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1): 89-129, 2008.
[5] M. G. Azar, Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[6] Y. Bai, T. Xie, N. Jiang, and Y.-X. Wang. Provably efficient q-learning with low switching cost. arXiv preprint arXiv: /905. 2249, 2019.
[7] Y. Bai, C. Jin, and T. Yu. Near-optimal reinforcement learning with self-play. Advances in Neural Information Processing Systems, 33, 2020.
[8] B. Baker, I. Kanitscheider, Markov, Y. Wu, G. Powell, B. McGrew, and Mordatch. Emergent tool use from multi-agent autocurricula. arXiv preprint arXiv: 090000759990 2019.
[9] R. I. Brafman and M. Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213-23) 2002.
[10] Chen and N. Jiang. Information-theorett considerations in batch reinforcement learning. In International Conference Machine Learning, pages 1052-1051. PMLR, 2019.
10

---

[1]] C. Dann, T. Lattimore, and E. Brunskill. Unifying pac and regret: uniform pac bounds for episodic reinforcement learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 5717-5727, 2017.
[12] C. Dann, L. Li, W. Wei, and E. Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507-1516. PMLR, 2019,
[13] O. D. Domingues, P. Ménard, E. Kaufmann, and M. Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021.
[14] S. S. Du, S. M. Kakade, J. D. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: A structural framework for provable generalization in rl. arXiv preprint arXhv:2103.1089) 2021.
[15] A. M. Farahmand, R. Munos, and C. Szepesvári. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, 2010.
[16] S. Fujimoto, D. Meger, and D. Precup. Off Off-policy deep reinforcement learning without explo- ration. In International Conference on Machine Learning, pages 2052-2062. PMLR, 2019.
[17] M. Gao, T. Xie, S. S. Du, and L. F. Yang. A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint urXiv:2101.00494 2021.
[18] M. Hessel, J. Modayil, H. Van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar, and D. Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[19] T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
[20] M. Janner, J. Fu, M. Zhang, and S. Levine. When to trust your model: Model- based policy 2019.
optimization. arXiv preprint
[21] N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. Contextual decision processes with low bellman rank are pac-learnable In International Conference on Machine Learning, pages 1713. PMLR, 2017.
[22] C. Jin, Z. Allen-Zhu, Bubeck, and M. I. Jordan. Is q-learning provably efficient? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4868-48 4878, 2018
[23] C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement leaaffr with linear function approximation. In Conference Learning Theory, pages 2137-2143. PMLR, 2020.
[24] C. Jin, Q. Liu, and S. Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.00815 2021.
[25] Y. Jin, Z. Yang. and Z. Wang. Is pessimism provably efficient for offline rl? arXiv preprint arXiv:20/2.15083 /5085, 2020.
[26] D. Kalashnikov. A. Irpan, P. Pastor, Ibarz, Herzog, E. Jang, D. Quillen, Holly, M. Kalakr- ishnan, V. Vanhoucke, et al. Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robot Learning, pages 651-673, PMLR, 2018.
[27] M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 2922)2209-23,, 2002.
[28] R. Kidambi, A. Rajeswaran, P. Netrapalli, and T. Joachims. Morel: Model-based offline reinforcement learning. arXiv preprint arXiv:2005.05551, 2020.
[29] A. Kumar, Fu, G. Tucker, and Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. arXiv preprint arXiv:1906.0000 00949, 2019.

---

[30] A. Kumar, A. Zhou, G. Tucker, and S. Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint AXXv:22006004799 2020.
[31] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[32] Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter. Learning quadrupedal locomotion over challenging terrain. Science robotics, 5(47), 2020.
[33] E. L. Lehmann and G. Casella. Theory of point estimation. Springer Science & Business Media, 2006.
[34] Q Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis of model-based reinforcement learning with self-play, arXiv preprint arXiv:2010.01604, 2020.
[35] Y. Liu, A. Swaminathan, A. Agarwal, and E. Brunskill. Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202, 2020.
[36] T. Matsushima, H. Furuta, Y. Matsuo, O. Nachum, and S. Gu. Deployment-efficien rein- forcement learning via model-based offline optimization. arXiv preprint arXiv:2006.0366 2020.
[37] A. Maurer and M. Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.37440, 2009.
[38] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. nature, 518(7540):529-533, 2015.
[39] R. Munos. Error bounds for approximate policy iteration. In ICML,, volume 3, pages 560-567, 2003.
[40] R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
[41] I. Osband and B. V. Roy. Model-based reinforcement learning and the eluder dimension. In Proceedings of the 27th International Conference on Neural Information Processing Systems- Volume 1, pages 1666,1174, 2014.
[42] P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. arXiv preprint arXiv:2103./2022 2021.
[43] T. Ren, J. Li, B. Dai, S. S. Du, and S. Sanghavi. Nearly horizon-free offline reinforcement learning, arXiv preprint 1XXi::2003.1477 2021.
[44] D. Silver, A. Huang, C. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanetot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[45] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature, 550 (7676):354-359, 2017.
[46] D. Su, D. Lee, J. M. Mulvey, and H. V. Poor. Musbo: Model-based uncertainty regularized and sample efficient batch optimization for deployment constrained reinforcement learning. arXiv preprint arXiv:2102.11445 2021.
[47] W. Sun, N. Jiang, A. Krishnamurthy, A. Agarwal, and J. Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pages 2898-2933. PMLR, 2019.
[48] C. Szepesvári and R. Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference Machine learning, pages 880-887, 2005.
12

---

[49] A. A. Taiga, W. Fedus, M. C. Machado, A. Courville, and M. G. Bellemare. Benchmark- ing bonus-based exploration methods on the arcade learning environment. arXiv preprint arXiv: 1908 02388, 2019.
[50] A. A. Taiga, W. Fedus, M. C. Machado, A. Courville, and M. G. Bellemare. On bonus based exploration methods in the arcade learning environment. In International Conference on Learning Representations, 2020. URL attpp:://ppereet
[51] S. Tosatto, M. Pirotta, C. d' d'Eramo, and M. Restelli. Boosted fitted q-iteration. In International Conference on Machine Learning, pages 3434-3443. PMLR, 2017.
[52] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)350-3344 2019.
[53] R. Wang, R. R. Salakhutdinov, and L. Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances Neural Information Processing Systems, $3:6123-6133 2020.
[54] T. Wang, D. Zhou, and Q. Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. arXiv preprint arXiv:2101.02195, 2021.
[55] Y. Wu, G. Tucker, and O. Nachum. Behavior regularized offline reinforcement learning. arXiv preprint arXiv: 19.1.11111111 11361, 2019.
[56] Xie and N. Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, pages 550-559, PMLR, 2020.
[57] Z. Yang, Jin, Z. Wang. M. Wang, and M. Jordan. Bridging exploration and general function approximation in reinforcement learning: Provably efficient kernel and neural value iterations. arXiv preprint MxXiv:2011.04222 2020.
[58] M. Yin, Y. Bai, and Y.-.. Wang. Near optimal provable uniform convergence in off-policy evaluation for reinforcement learning. arXiv preprint arXiv:2007.03766, 2020.
[59] M. Yin, Y. Bai, and Y.-X. Wang. Near-optimal offline reinforcement learning via double variance reduction. arXiv preprint arXiv:2102.01748 2021.
[60] T. Yu, G. Thomas, L. Yu, S. Ermon, J. Zou, S. Levine, C. Finn, and T. Ma. Mopo: Model-based offline policy optimization. arXiv preprint 3333, 2020.
[61] A. Zanette, A. Lazaric, M. Kochenderfer, and E. Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10989. PMLR, 2020.
[62] A. Zanette, A. Lazaric, M. J. Kochenderfer, and E. Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. arXiv preprint arXiv:2008.07737, 2020.
[63] Z. Zhang, Y. Zhou, and X. Ji. Almost optimal model-free reinforcement learningvia reference- advantage decomposition. Advances in Neural Information Processing Systems, 33, 2020.
13


Reviews:
[{"review_id": "wgyp2xWJNLy", "reviewer": "Reviewer_rtpe", "summary": "The paper proposes a theoretical analysis of off-policy and on-policy RL algorithms, and proposes a new hybrid algorithm that learns a policy in the following way:\n\n- The beginning of episodes, time-steps 1 to h*, is used to learn offline, from samples collected by a behavior policy.\n- The end of episodes, time-steps h* to the horizon, is used to learn online by exploring in the environment\n\nThe paper proves that there are families of environments and behavior policies for which the proposed algorithm has a better sample-efficiency than either purely online or purely offline approaches.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very dense, but well written, easy to understand, and does a great job at citing and discussing related work. The proposed algorithm seems quite original, as it is unusual to consider \"halves\" of episodes, with the early time-steps used for something, and the later time-steps used differently. The theoretical approach and the proofs look sound, and the paper is overall well motivated.\n\nA minor question I have is whether Step 1 of Algorithm 2 (the step that executes the behavior policy for some time-steps, before starting to explore with UCB) could store the transitions acquired by the behavior policy in the experience buffer D, later used for offline learning. The idea would be to be a bit more data efficient, and not to throw away the samples generated by $\\mu$ in Step 1.\n\nThe paper is overall already very dense, and I don't see how more information could be added to it. I would however suggest (maybe for future work) to also have, linked to the research presented in this paper:\n\n- A numerical evaluation of the proposed algorithm, compared to the baselines, in several environments (that can be simple). The objective is to see how the change in theoretical sample-efficiency influences real-world performance.\n- A brief description, maybe a paragraph, of how to implement the equations as part of a practical algorithm. Ideas on how to implement the algorithm with function approximation would have high value, even if the resulting implementation would be incompatible with the proofs given in the paper.\n\nI think that the algorithm proposed in this paper, with its splitting of episodes, is truly novel. I would feel bad if this algorithm were to remain un-implemented for decades, because it never leaves the field of theoretical reinforcement learning.\n\nAuthor response: The authors say that they will discuss avenues for implementing their contribution. I think that it is absolutely crucial to do so, as the authors are the only people in the world truly expert in their contribution. Finding how to implement it may be a bit more challenging than originally expected, and the authors are usually the only people who may eventually be able to do it. I recommend accepting this paper, as it is novel and well-presented, but I also personally recommend that the authors spend a bit of time producing at least a work-in-progress implementation of the algorithm (a fork of stable-baselines3 on Github for instance). I think that if this paper were to be presented at NeurIPS, having a nice QR-Code in the slides, that points to ready-to-use code, would lead to many citations of this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There was no societal impact to evaluate, as the paper is purely theoretical, and uses equations that introduce no human bias.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ULA50xriaX", "reviewer": "Reviewer_gXvU", "summary": "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:\n\n(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)\n\n(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.\n\n(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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written. Assumptions and discussions are fairly easy to read.  The authors do a good job motivating the problem and provide a nice formulation of policy finetunning. The hybrid algorithm and partial concentrability assumption are also interesting.\n\n-In the hybrid case(theorem 4), how much the sample complexity depends on the choice of algorithm in the first stage? I was wondering if there is any other choice other than UCBVI-UPLOW that could be used in the algorithm?\n\nline 69: setting *is* equivalent\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have addressed theoretical limitations to some extent", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "To6CsLXGXz5", "reviewer": "Reviewer_eRNE", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies a relevant setup of policy fine-tuning. The fine-tuning setup is really useful for certain RL applications. The proofs seem to be correct but I didn't check the theory thoroughly. The paper is well written and easy to follow.\n\nI have some concerns regarding a lack of any experimental evaluation. But, in general, the paper is well written and studies the problems that are relevant to the RL community. I will be curious to see a follow-up work that addresses similar questions for the function approximation case.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "2i9IclPNmvF", "reviewer": "Reviewer_TVkX", "summary": "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.\n\nThis 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:\n\n1- Reference policy \\mu satisfies single-policy concentrability.\n2- Reference policy \\mu satisfies concentrability up to a certain time step which is a more relaxed than the first assumption.\n\nUnder these assumptions for the first time sharp upper and lower bounds for policy finetuning is stablished.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n1-This paper studies an increasingly important setting for reinforcement learning that can pave the path for solving real world problems via RL. \n2-Contributions seems to be original and are the first step towards algorithms for policy finetuning with provably near optimal solutions. Derivations sounds correct as much as i could check. \n3-Paper is well written.\n\nCons: \nPaper does not have any experimental results.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors have not discussed the societal Impact of this work. As with any machine learning algorithm, there are potential societal impacts in how their proposed insights/algorithms is applied.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all agreed that this paper provides important theoretical contributions to an important area: sample efficient online learning (fine-tuning), using first offline training. The primary concern is about the practicality of the algorithm and the lack of empirical validation. As a paper focused on theory, however, this is not a concern; such work can naturally be done as a follow-up. As suggested by a reviewer, I highly encourage the authors to use the additional space in the final version to discuss how such an algorithm could be implemented, to make it easier to follow-up on this work. 
Decision: Accept (Poster)