Recognition: unknown
Provably Efficient Offline-to-Online Value Adaptation with General Function Approximation
Pith reviewed 2026-05-10 12:51 UTC · model grok-4.3
The pith
A structural condition on offline-pretrained value functions allows an algorithm to adapt them to the target environment with fewer samples than pure online reinforcement learning.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Under a novel structural condition on the offline-pretrained value functions, O2O-LSVI achieves a problem-dependent sample complexity that provably improves over pure online RL for value adaptation in the offline-to-online setting with general function approximation.
What carries the argument
O2O-LSVI, an adaptation procedure built on least-squares value iteration that exploits the structural condition to reduce online sample needs.
Load-bearing premise
The offline-pretrained value functions satisfy a novel structural condition whose precise form enables the adaptation procedure to achieve better sample complexity than learning from scratch.
What would settle it
A concrete MDP instance and pretrained Q-function obeying the structural condition in which O2O-LSVI nevertheless requires as many online samples as pure online LSVI to reach the same accuracy.
read the original abstract
We study value adaptation in offline-to-online reinforcement learning under general function approximation. Starting from an imperfect offline pretrained $Q$-function, the learner aims to adapt it to the target environment using only a limited amount of online interaction. We first characterize the difficulty of this setting by establishing a minimax lower bound, showing that even when the pretrained $Q$-function is close to optimal $Q^\star$, online adaptation can be no more efficient than pure online RL on certain hard instances. On the positive side, under a novel structural condition on the offline-pretrained value functions, we propose O2O-LSVI, an adaptation algorithm with problem-dependent sample complexity that provably improves over pure online RL. Finally, we complement our theory with neural-network experiments that demonstrate the practical effectiveness of the proposed method.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies offline-to-online value adaptation in RL under general function approximation. It first proves a minimax lower bound showing that, even when the offline-pretrained Q-function is close to optimal, online adaptation can require as many samples as pure online RL on certain hard instances. On the positive side, under a novel structural condition on the pretrained value functions, the authors propose the O2O-LSVI algorithm whose problem-dependent sample complexity provably improves over pure online RL; the theory is complemented by neural-network experiments demonstrating practical effectiveness.
Significance. If the structural condition holds for realistic pretrained Q-functions, the result provides the first provable improvement in sample complexity for offline-to-online adaptation under general function approximation, bridging offline and online RL. The lower bound clarifies when adaptation cannot help, while the positive result and experiments suggest a concrete algorithmic path forward. The work is strengthened by its use of general FA and explicit problem-dependent bounds rather than worst-case rates.
major comments (3)
- [§3.2] §3.2, Definition 3.1 (structural condition): the condition is load-bearing for the entire positive result (Theorems 4.1 and 4.2), yet the manuscript provides no argument or example showing that it is satisfied by Q-functions returned by standard offline methods (e.g., pessimistic VI, CQL, or BC). Without such verification the claim that O2O-LSVI “provably improves over pure online RL” remains conditional on an untested assumption.
- [Theorem 4.2] Theorem 4.2 (sample-complexity bound): the stated improvement over online RL is expressed in terms of a problem-dependent quantity that appears only after invoking the structural condition; the manuscript does not quantify how large this quantity must be relative to the online RL baseline (e.g., the covering number or eluder dimension) to guarantee a strict sample saving, making it difficult to assess the practical magnitude of the improvement.
- [§5] §5 (experiments): the neural-network results are presented without an ablation that isolates the contribution of the structural condition (e.g., by comparing O2O-LSVI against a version that ignores the condition or against pure online LSVI). Consequently it is unclear whether the observed gains are due to the proposed algorithm or to generic benefits of warm-starting.
minor comments (2)
- [§4] Notation: the symbol for the structural condition (e.g., “C”) is introduced in Definition 3.1 but then used without re-statement in the proof sketches of §4; a short reminder or reference to the definition in each theorem statement would improve readability.
- [§2] Related work: the discussion of prior offline-to-online results (e.g., works on policy adaptation or value transfer) is brief; adding one or two sentences contrasting the new structural condition with existing “coverage” or “realizability” assumptions would help situate the contribution.
Simulated Author's Rebuttal
We thank the referee for the constructive and detailed feedback. The comments help clarify the presentation of our structural condition, the practical implications of our sample-complexity bounds, and the interpretation of our experiments. We address each major comment below and describe the revisions we will make to strengthen the manuscript.
read point-by-point responses
-
Referee: [§3.2] §3.2, Definition 3.1 (structural condition): the condition is load-bearing for the entire positive result (Theorems 4.1 and 4.2), yet the manuscript provides no argument or example showing that it is satisfied by Q-functions returned by standard offline methods (e.g., pessimistic VI, CQL, or BC). Without such verification the claim that O2O-LSVI “provably improves over pure online RL” remains conditional on an untested assumption.
Authors: We agree that verifying the structural condition for standard offline algorithms is important for the applicability of our positive results. The condition is intentionally formulated to capture a broad class of pretrained Q-functions that are close to optimal in a structured manner, but the original manuscript indeed focuses on the algorithmic consequences rather than explicit verification. In the revised manuscript we will add a dedicated discussion subsection (new §3.3) that (i) provides a simple analytic example in which a Q-function obtained by behavior cloning satisfies the condition with a small structural parameter, and (ii) argues why the condition is expected to hold for pessimistic value iteration and CQL under mild coverage assumptions on the offline data. This addition will make the practical relevance of Theorems 4.1 and 4.2 more concrete while preserving the original theoretical claims. revision: yes
-
Referee: [Theorem 4.2] Theorem 4.2 (sample-complexity bound): the stated improvement over online RL is expressed in terms of a problem-dependent quantity that appears only after invoking the structural condition; the manuscript does not quantify how large this quantity must be relative to the online RL baseline (e.g., the covering number or eluder dimension) to guarantee a strict sample saving, making it difficult to assess the practical magnitude of the improvement.
Authors: We thank the referee for pointing out the need for clearer quantification. Theorem 4.2 already expresses the sample complexity in terms of a problem-dependent term that is strictly smaller than the corresponding term in pure online LSVI whenever the structural parameter is positive. To make the improvement explicit, we will insert a new remark immediately after Theorem 4.2 that states sufficient conditions for a strict asymptotic saving: specifically, when the structural parameter is o(1) relative to the eluder dimension (or covering number) of the function class, the leading term in our bound is asymptotically smaller than the pure-online baseline. We will also include a short numerical illustration comparing the two bounds for representative values of the structural parameter. These additions will allow readers to assess the magnitude of the improvement directly from problem parameters. revision: yes
-
Referee: [§5] §5 (experiments): the neural-network results are presented without an ablation that isolates the contribution of the structural condition (e.g., by comparing O2O-LSVI against a version that ignores the condition or against pure online LSVI). Consequently it is unclear whether the observed gains are due to the proposed algorithm or to generic benefits of warm-starting.
Authors: We acknowledge that the current experimental section does not contain ablations that isolate the role of the structural condition. In the revised manuscript we will expand §5 with two additional sets of experiments on the same neural-network environments: (1) a direct comparison of O2O-LSVI against standard online LSVI (both starting from the same random initialization), and (2) a controlled variant of O2O-LSVI that performs the online update without exploiting the structural condition (i.e., by reverting to the standard least-squares update). These ablations will be presented alongside the existing results and will include statistical significance tests. We believe the new figures will clarify that the observed gains are attributable to the proposed adaptation mechanism rather than generic warm-starting. revision: yes
Circularity Check
No circularity: positive result conditioned on explicit novel assumption with independent lower bound
full rationale
The paper establishes a minimax lower bound showing that adaptation cannot improve over pure online RL without additional structure, then introduces a novel structural condition on pretrained Q-functions as the assumption enabling the O2O-LSVI algorithm and its problem-dependent sample complexity bound. This is standard conditional analysis under general function approximation; the derivation does not reduce any claimed prediction or result to a fitted parameter, self-definition, or self-citation chain. The condition is stated as an external assumption rather than derived from the algorithm's outputs, and no load-bearing step equates the improvement to its own inputs by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- ad hoc to paper Novel structural condition on the offline-pretrained value functions
Reference graph
Works this paper leans on
-
[1]
Zixiang Chen, Chris Junchi Li, Angela Yuan, Quanquan Gu, and Michael I Jordan. A general framework for sample-efficient function approximation in reinforcement learning.arXiv preprint arXiv:2209.15634,
-
[2]
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang
ISSN 0933-3657. Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is a good representation sufficient for sample efficient reinforcement learning?arXiv preprint arXiv:1910.03016,
-
[3]
arXiv preprint arXiv:2112.13487 , year=
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making.arXiv preprint arXiv:2112.13487,
-
[4]
An empirical study of implicit regularization in deep offline rl.arXiv preprint arXiv:2207.02099,
Caglar Gulcehre, Srivatsan Srinivasan, Jakub Sygnowski, Georg Ostrovski, Mehrdad Farajtabar, Matt Hoffman, Razvan Pascanu, and Arnaud Doucet. An empirical study of implicit regularization in deep offline rl.arXiv preprint arXiv:2207.02099,
-
[5]
Xiao Huang, Xu Liu, Enze Zhang, Tong Yu, and Shuai Li. Offline-to-online reinforcement learning with classifier-free diffusion generation.arXiv preprint arXiv:2508.06806,
-
[6]
Offline Reinforcement Learning with Implicit Q-Learning
Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit q-learning. arXiv preprint arXiv:2110.06169,
work page internal anchor Pith review arXiv
-
[7]
Chengrui Qu, Laixi Shi, Kishan Panaganti, Pengcheng You, and Adam Wierman. Hybrid transfer reinforcement learning: Provable sample efficiency from shifted-dynamics data.arXiv preprint arXiv:2411.03810,
-
[8]
Hybrid rl: Using both offline and online data can make rl efficient.arXiv preprint arXiv:2210.06718,
Yuda Song, Yifei Zhou, Ayush Sekhari, J Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make rl efficient.arXiv preprint arXiv:2210.06718,
-
[9]
Chen Tang, Ben Abbatematteo, Jiaheng Hu, Rohan Chandra, Roberto Martín-Martín, and Peter Stone
doi: 10.52202/079017-3815. Chen Tang, Ben Abbatematteo, Jiaheng Hu, Rohan Chandra, Roberto Martín-Martín, and Peter Stone. Deep reinforcement learning for robotics: A survey of real-world successes.Annual Review of Control, Robotics, and Autonomous Systems, 8(1):153–188,
-
[10]
arXiv preprint arXiv:2107.06226 , year=
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage.arXiv preprint arXiv:2107.06226,
-
[11]
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism.arXiv preprint arXiv:2203.05804,
-
[12]
A posterior sampling framework for interactive decision making,
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond.arXiv preprint arXiv:2211.01962,
-
[13]
Yifei Zhou, Ayush Sekhari, Yuda Song, and Wen Sun. Offline data enhanced on-policy policy gradient with provable guarantees.arXiv preprint arXiv:2311.08384,
-
[14]
17 Zhiyuan Zhou, Andy Peng, Qiyang Li, Sergey Levine, and Aviral Kumar. Efficient online reinforcement learning fine-tuning need not retain offline data.arXiv preprint arXiv:2412.07762,
-
[15]
B.2 Proof Sketch of Theorem 6.2 In this subsection, we highlight a few key points as the proof sketch of Theorem 6.2. The first key technical lemma suggests that through the online interactions, the number of the algorithm visiting Line 11 of Algorithm 1 is bounded: Lemma B.1(Informal statement of Lemma B.11).For eachh∈ [H], the set of|Mh| is bounded by ˜...
2023
-
[16]
With probability at least1−5δ, we can bound the regret step-by-step
21 B.6 Detailed Proof Proof of Theorem 6.2.Under the eventsE ˆf and E ˇf, and by Lemmas B.9, E.2, B.12, and B.14, we take a union bound. With probability at least1−5δ, we can bound the regret step-by-step. First, leveraging Lemma B.9, we expand and bound the initial regret: Regret(K) = KX k=1 h V ⋆ 1 (s1)−V πk 1 (s1) i ≤ KX k=1 h V k 1 (s1)−V πk 1 (s1) i ...
2024
-
[17]
Since ζH≥ϵ , we have thatmaxs,a |Qref;h(s, a) −Q ⋆ h(s, a)| ≤ζH , which implies thatM ∈ M ζ
Unrolling this recursion over the horizonHand applyingγ≤6ϵyield the final upper bound on the Q-value difference: max s,a |Qref;h(s,a)−Q ⋆ h(s,a)| ≤ HX i=h γHmax a |a⊤µi| ≤γH 2 max a |a⊤µh| ≤ 1 6 γ≤ϵ, where maxa |a⊤µh| ≤ 1 6 H −2. Since ζH≥ϵ , we have thatmaxs,a |Qref;h(s, a) −Q ⋆ h(s, a)| ≤ζH , which implies thatM ∈ M ζ. Lemma D.2(Decomposition).Suppose H...
2021
-
[18]
1 K KX k=1 V ⋆ 1 (s1)−V πk 1 (s1) # ≥ϵ. Since µ is a parameter ofM, it suggests that it requires at leastΩ(H 3d2 ϵ2 )online episodes to achieve ϵ-suboptimal average regret: Es1,M
To lower boundT1 −S 1, first note that Si = (H−i)(a i + 1 2H ) +S i+1(1−a i − 1 2H ), Ti = (H−i)(γ(d−1)∆ + 1 2H ) +T i+1(1−γ(d−1)∆− 1 2H ), 40 which gives that Ti −S i = (H−i−T i+1)(γ(d−1)∆−a i) + (1−a i − 1 2H )(Ti+1 −S i+1).(27) Therefore by induction, we get that T1 −S 1 = H−1X h=1 (γ(d−1)∆−a h)(H−h−T h+1) h−1Y j=1 (1−a j − 1 2H ).(28) To further bound...
2020
-
[19]
We implement our method based on the CORL repository [Tarasov et al., 2023], which also serves as the codebase for the offline RL baselines CQL [Kumar et al., 2020], IQL [Kostrikov et al., 2021], and Cal-QL [Nakamoto et al., 2023]. Hyperparameter Value Ensemble Size 5 β 50 CQL Conservative Coefficientα(Offline & Online) 5.0 Discount factor 0.99 Q Network ...
2023
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.