PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, Yu Bai

arXiv:2106.04895v2cs.LGstat.ML

TL;DR

Online and offline RL have largely disconnected theories for sample-efficient near-optimal learning. This paper introduces policy finetuning, analyzes offline reduction and adaptive exploration with a reference policy, and establishes sharp lower and upper bounds plus a beneficial hybrid regime.

  • Problem

    Online and offline RL use different sample-efficient algorithms and theories, motivating a theoretical framework that bridges them.

  • Method

    The paper studies policy finetuning in episodic MDPs, allowing interactive play alongside access to a reference policy and comparing offline reduction, online exploration, and hybrid algorithms.

  • Results

    The paper achieves eO(H^3SC⋆/ε^2) episodes offline, proves an Ω(H^3S min {C⋆, A}/ε^2) lower bound for all finetuning algorithms, and finds hybrid gains under partial concentrability.

  • Takeaways & Limitations

    Under single-policy concentrability, optimal finetuning is either offline reduction or purely online RL, while hybrid designs help when concentrability is only partial.

  • Takeaways & Limitations

    The contributions are mainly theoretical, and extending the algorithms to large state/action spaces with function approximation and evaluating them experimentally remain future directions.

Abstract

from arXiv · show

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 $π_\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 $μ$ 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 $μ$ and $π_\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 $Ω(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 $μ$. 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.

1 Introduction

The paper introduces policy finetuning to connect theoretically disconnected online and offline RL through access to a good reference policy. It establishes sharp offline, lower-bound, and hybrid results for this unified setting.

  • Motivation: Existing online and offline RL algorithms use different strategies: online methods explore unseen states and actions, whereas offline methods optimize value estimators without interactive exploration.The paper frames their theories as rather different and disconnected.
  • Policy finetuning: Policy finetuning gives learners interactive environment access plus a reference policy μ, enabling comparison of offline reduction and online exploration under one sample-complexity metric.The learner may collect data with μ and apply offline optimization, or interactively execute other policies, including adaptive exploration.
  • Contributions: eO(H^3SC⋆/ε^2) episodes suffice for PEVI-Adv to find an ε-optimal policy under single-policy concentrability.This improves the best existing offline result by an H^2 factor, matches the lower bound up to logarithmic factors, and resolves a recent open question.
  • Contributions: Ω(H^3S min {C⋆, A}/ε^2) episodes are necessary for every policy finetuning algorithm, including algorithms that adaptively explore.Under this assumption, the optimal algorithm is either offline reduction or purely online RL, depending on whether C⋆≤A.
  • Contributions: HOOVI combines online exploration with offline data collection and improves on both vanilla offline reduction and purely online algorithms when concentrability holds only partially.This identifies a relaxed setting in which hybrid designs are beneficial.

2 Preliminaries

The paper studies finite-horizon tabular MDPs and defines policy finetuning as learning an ε-near-optimal policy using environment interaction and access to a reference policy. Its main assumption measures reference-policy coverage relative to an optimal policy.

  • MDP model: The environment is an episodic finite-horizon MDP with S states, A actions, horizon H, time-inhomogeneous transitions, and deterministic rewards in [0,1].The initial state is assumed deterministic without loss of generality.
  • Policies and value functions: A policy specifies an action distribution for every time step and state, inducing trajectory expectations, value functions, Q functions, and visitation distributions.Transition and variance operators, together with empirical versions, support estimated-model analysis.
  • Learning objective: The learning goal is to output an ε-near-optimal policy using as few episodes of interaction with the MDP as possible.The optimal policy’s value functions define the benchmark.
  • Policy finetuning setting: Policy finetuning permits either playing any policy interactively or accessing and sampling the reference policy μ arbitrarily during learning.This makes offline reduction and online RL special cases within one setting.
  • Reference-policy assumption: Single-policy concentrability bounds the visitation-distribution distance between μ and some deterministic optimal policy π⋆ using coefficient C⋆≥1.This assumption is more relaxed than requiring bounded supremum concentrability against every policy.

3 Sharp offline learning via reference-advantage decomposition

The paper develops PEVI-Adv, a sharp offline reduction method for policy finetuning that improves horizon dependence under single-policy concentrability and matches the lower bound up to logarithmic factors.

  • Offline reduction: The offline reduction collects trajectories by executing μ and applies offline policy optimization to the resulting dataset.This provides a direct offline-RL interpretation of policy finetuning.
  • Algorithmic ingredients: VI-LCB provides a pessimistic value-iteration warm-up whose value estimates support the later PEVI-Adv procedure.Its finite-horizon guarantee is eO(H^5SC⋆/ε^2).
  • Comparison with VI-LCB: PEVI-Adv improves over VI-LCB by an H^2 factor and is the first method in this setting to match the sample complexity lower bound.The improvement yields cubic horizon dependence under single-policy concentrability.
  • Algorithmic ingredients: PEVI-Adv combines a Bernstein-style bonus with reference-advantage decomposition to reduce the effects of variance and data splitting.The decomposition uses a learned reference value function and separate transition estimates with a new independence structure.
  • Guarantee: Theorem 2 guarantees that, with probability at least 1−δ, PEVI-Adv outputs a policy and value estimate satisfying the stated near-optimality conditions.The theorem assumes that μ satisfies the single-policy concentrability assumption.

4 Lower bound for policy finetuning

The lower-bound analysis shows that, under single-policy concentrability, no policy-finetuning algorithm can generally outperform the better of sharp offline reduction and purely online RL.

  • Consequences: Under single-policy concentrability, combining online exploration with knowledge of μ cannot improve the worst-case sample complexity over these two baselines.The paper describes this as a “no algorithm in between” phenomenon.
  • Lower bound: Ω(H^3S min{C⋆, A}/ε^2) episodes are necessary for any policy-finetuning algorithm to find an ε-near-optimal policy.The lower bound includes algorithms that adaptively explore the environment.
  • Consequences: The lower bound implies that either PEVI-Adv offline reduction or purely online RL is optimal up to logarithmic factors, depending on whether C⋆ is smaller than A.The best baseline is selected according to the relationship between concentrability and action-space size.
  • Relation to prior lower bounds: The lower bound generalizes separate online-RL and offline-RL lower bounds to the policy-finetuning setting.It also directly yields an offline-RL lower bound when 2≤C⋆≤O(A).
  • Hard-instance construction: The hard-instance construction reduces the problem to HS independent A-armed bandit problems while restricting optimal actions to the first K=min{C⋆, A} actions.The reference policy is uniform over those K actions and reveals their range but not the optimal action identities.
  • Hard-instance construction: Because μ identifies only the candidate action set, an algorithm must still try all K actions in each bandit problem, yielding the lower bound.This gives Ω(H^3SK/ε^2)=Ω(H^3S min{C⋆, A}/ε^2).

5 Hybrid offline/online algorithm for policy finetuning

The paper develops HOOVI, a hybrid offline/online algorithm for policy finetuning when the reference policy has concentrability guarantees only through step h⋆. It combines optimistic online exploration for later steps with offline optimization using the reference policy for earlier steps.

  • Partial concentrability: The relaxed setting assumes partial concentrability only through step h⋆, with no bounded concentrability guaranteed afterward.The reference policy may therefore be unreliable for steps h⋆+1:H.
  • Hybrid algorithm: HOOVI first uses UCBVI-UpLow to explore online and estimate values for steps h⋆+1:H.UCBVI-UpLow maintains optimistic and lower value bounds and produces a near-optimal policy for the later steps.
  • Hybrid algorithm: HOOVI then collects data from μ and applies Truncated-PEVI-ADV to optimize the policy for steps 1:h⋆.The second stage uses the lower value estimate from the first stage at step h⋆+1.
  • Guarantee: Theorem 4 guarantees an ε-near-optimal policy with probability at least 1−δ under partial concentrability.The theorem states the hybrid online/offline sample-complexity guarantee for sufficiently small ε.
  • Comparison: Naive offline reduction can fail without later-step concentrability, whereas modifying μ to act uniformly can incur O(A^(H−h⋆)) concentrability and much worse sample complexity.HOOVI instead has polynomial dependence on H, S, and A in the stated comparison.
  • Comparison: The hybrid method can outperform purely online learning when both C_partial and H−h⋆ are small, including the stated asymptotic regime.Purely online exploration from scratch achieves Õ(H^3SA/ε^2), while the hybrid method is advantageous in specified cases.

6 Conclusion & discussions

The paper frames policy finetuning as a bridge between sample-efficient offline and online RL, establishing sharp bounds under different reference-policy assumptions. It also identifies implementation and evaluation beyond tabular theoretical settings as future directions.

  • Main conclusions: The paper establishes sharp upper and lower bounds for policy finetuning under various assumptions on the reference policy.These bounds connect offline reduction, purely online learning, and hybrid methods within one setting.
  • Main conclusions: When the reference policy satisfies single-policy concentrability, the optimal policy-finetuning algorithm is either offline reduction or purely online learning.The purely online alternative does not use the reference policy.
  • Main conclusions: A hybrid online/offline algorithm can be advantageous over both offline reduction and purely online algorithms under more relaxed reference-policy assumptions.The conclusion is limited to the settings characterized by the paper’s bounds.
  • Future directions: The contributions are mainly theoretical, and implementing or extending the algorithms on real-world RL tasks remains a future direction.The tabular algorithms are described as readily implementable, while real-world evaluation is left open.
  • Future directions: For large state or action spaces with function approximation, the paper suggests adapting the algorithms with DQN-type methods and positive or negative bonus functions.Experimental evaluation of such adaptations is identified as a future direction.

B.3 Proof of main theorem

The proof of Theorem 1 uses concentration, monotonicity, and performance-decomposition lemmas for VI-LCB. These ingredients establish the required value and policy guarantees on a high-probability event.

  • Proof ingredients: The monotonicity lemma shows that the VI-LCB output policy satisfies the relevant lower-confidence value relationship on the concentration event.This property is used in the theorem proof to compare the learned policy with the optimistic value estimates.
  • Performance analysis: A performance-decomposition lemma bounds the policy’s suboptimality through confidence-estimation terms along the horizon.The proof applies the decomposition together with the concentration event and Cauchy–Schwarz inequality.
  • Conclusion: At h=1, the resulting bound yields the theorem’s ε guarantee for the initial-state value.The final policy guarantee follows from the lower-confidence value relationship established by monotonicity.

C.2 Proof of the Main Theorem

The proof of Theorem 2 analyzes PEVI-Adv on a high-probability concentration event by decomposing its error into multiple terms. Concentration, Cauchy–Schwarz, and a total-variance bound control these terms before deriving the final policy guarantee.

  • Proof setup: Theorem 2 is proved on a concentration event that holds with probability at least 1−δ.The proof begins by invoking Lemma C.1 and then applies the performance decomposition from Lemma C.3.
  • Term bounds: The leading terms are bounded using concentration and Cauchy–Schwarz, while the total variance lemma controls the variance contribution.The proof explicitly identifies term (I.b) as smaller order than term (I.a).
  • Error decomposition: The main error decomposition separates terms associated with estimation and the reference-value construction.The proof introduces g_h+1 as the difference between the estimated and reference value functions.
  • Term bounds: The reference value function’s guarantee is used to bound the remaining components of the decomposition.The analysis applies Lemma C.5 when controlling term (II.a), then treats terms (II.b) and (II.c) similarly.
  • Conclusion: Substituting the intermediate bounds and using equal data splits yields the final bound and, by monotonicity, the guarantee for the output policy.The proof uses n_ref=n_0=n_1=n/3 before applying the monotonicity property.

D Proof of Theorem 3

The proof constructs hard MDP instances indexed by unknown optimal actions, converts policy identification errors into suboptimality, and derives the policy-finetuning lower bound.

  • Lower-bound conclusion: For ε ≤ 1/12, choosing τ = 12ε/H yields ε suboptimality whenever n ≤ c0·H^3S min{C⋆, A}/ε^2.The construction establishes the desired lower bound for an instance in the family after averaging over a uniform prior on the unknown optimal actions.
  • Hard-instance construction: The hard-instance family uses S bandit states, two absorbing outcome states, A actions, and a 2H+1-step horizon.Bandit states transition among themselves or to good and bad states; rewards later distinguish the two absorbing outcomes.
  • Hard-instance construction: Each MDP M_a⋆ has special optimal actions a⋆_h,i that slightly increase transitions to the good state, while other actions are behaviorally irrelevant elsewhere.The null MDP removes these special actions, creating a family whose distinguishing information is localized to the optimal arms.
  • Reference-policy informativeness: The reference policy μ is identical across the hard MDP family, so it provides no instance-specific information to an online finetuning algorithm.Consequently, algorithms using μ are equivalent here to ordinary online RL algorithms for this class.
  • Reduction to bandit loss: The proof measures failure to identify the best action at each bandit state-time pair through a total bandit loss L.A lemma then links large L to large policy suboptimality, reducing the MDP lower bound to bandit best-arm identification.

D.1 Proof of Lemma D.1

The proof verifies that the constructed reference policy satisfies single-policy concentrability by separately analyzing bandit states and the good/bad absorbing states.

  • Bandit states: For bandit states, the state distribution is policy-independent and the reference and optimal policies both take action 1 deterministically.This directly verifies the concentrability condition on all bandit states.
  • Good and bad states: For the good and bad states, both policies again take action 1, so concentrability reduces to bounding state-distribution ratios.The proof therefore analyzes state occupancy rather than joint state-action occupancy for these states.
  • Good-state occupancy: The constructed transitions assign a slightly higher good-state probability when the optimal action is taken, while otherwise using the baseline transition probability.The transition advantage is localized to the special action at each bandit state-time pair.
  • Concentrability conclusion: The resulting occupancy calculations verify the K-concentrability bound for the good and bad states and for all bandit states.Together with Lemma D.1, this places the hard-instance family inside the assumed concentrability class.

E.1 Algorithm UCBVI-UpLow

UCBVI-UpLow is a single-player optimistic algorithm that combines upper and lower confidence bounds with Bernstein bonuses to produce certified value estimates and a policy.

  • Algorithm design: UCBVI-UpLow specializes Nash-VI to a single-player MDP and modifies its outputs using a certified-policy technique.The algorithm operates from a specified starting step through the horizon.
  • Algorithm design: The algorithm uses a Bernstein bonus in its confidence construction.This bonus is incorporated into the value updates used to obtain upper and lower estimates.
  • Theoretical guarantee: Lemma E.1 guarantees the output lower value estimate with probability at least 1−δ after n_UCB episodes.The guarantee is stated relative to the initial-state distribution at the algorithm’s starting step.
  • Proof strategy: The proof obtains the guarantee by invoking the corresponding Nash-VI theorem and lemma, followed by concentration and union-bound arguments.The analysis controls the relevant state-wise estimates simultaneously.
  • Theoretical guarantee: The resulting value-estimate properties establish both stated parts of the UCBVI-UpLow guarantee.The proof explicitly concludes each part after substituting the concentration bounds.

E.3 Proof of Theorem 4

Theorem 4 analyzes a hybrid procedure that first learns later-horizon values online with UCBVI-UpLow and then applies truncated pessimistic offline updates for earlier steps.

  • Hybrid algorithm: Stage 1 runs UCBVI-UpLow for n/2 episodes using initial states drawn from d^μ at step h⋆+1.Its output lower value estimate supplies the boundary value for the earlier-step procedure.
  • Analysis under partial concentrability: Partial concentrability through steps 1:h⋆ yields bounds on the learned reference values and state-wise concentrability at step h⋆+1.These properties connect the offline early-stage analysis to the online later-stage estimate.
  • Hybrid algorithm: Stage 2 runs Truncated-PEVI-ADV, which estimates a reference value function and performs pessimistic value iteration only through step h⋆.The later-horizon value at h⋆+1 is plugged in and held fixed.
  • Output-policy guarantee: The final policy uses the UCBVI policy from h⋆+1 onward and the truncated offline policy before h⋆+1.The proof propagates the lower-value guarantee backward through the earlier steps.
  • Output-policy guarantee: Theorem 4 concludes that the final output policy is ε-near-optimal when ε satisfies the stated range and the episode count satisfies condition (17).The high-probability argument combines the constituent good events into a 1−δ guarantee.
Loading 2106.04895v2…