REVIEW 2 major objections 6 minor 39 references
This paper claims that upper and lower value bounds learned from an offline batch can be fed into an online exploration algorithm, producing regret bounds that shrink as the offline dataset grows — a provable offline-to-online speedup.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · deepseek-v4-flash
2026-08-04 08:39 UTC pith:RBSUXSCJ
load-bearing objection Offline-learned value envelopes are a real idea with a real regret bound, but the advertised offline-to-online speedup only holds under full state-action coverage, which the main text doesn't actually state. the 2 major comments →
Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approach
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The core discovery is a decoupled upper–lower envelope construction. Unlike earlier shaping-function analyses that require a single sandwich bound supplied in advance, the paper learns both bounds from data and treats them as random variables measurable with respect to the offline dataset. The online algorithm's exploration bonus uses the midpoint and width of the envelope, so that as the width D_h shrinks toward zero the bonus recovers the standard variance-aware bonus. The regret bound decomposes into an Rmax term, inherited from the MDP, and a Dmax term that is controlled by the offline data; Theorem 2 quantifies this control through K and the behavior policy's coverage d_min. The message
What carries the argument
The central object is the value envelope pair (W_h, U_h) with width D_h = U_h − W_h and range R_h = max U_h − min W_h. Algorithm 2 produces these by optimistic and pessimistic offline value iteration with empirical-Bernstein bonuses; Algorithm 1 uses them in the online bonus, which combines the empirical variance of the envelope midpoint with the expected squared width, and clips Q-value estimates to the upper envelope. The width Dmax is the channel through which the offline sample size K enters the online regret: Lemma 3 and Proposition 1 show Dmax shrinks like sqrt(H^5/(K d_min)) + H^3/(K d_min) under full coverage, and this term multiplies the exploration costs in the final bound.
Load-bearing premise
The behavior policy that collected the offline data must visit every state-action pair with at least some small positive probability; otherwise the envelope around the unseen pair never tightens, and the claimed offline-to-online speedup for that pair collapses.
What would settle it
On a fully covered layered tabular MDP, measure the offline envelope width V_1 − V_1 produced by Algorithm 2 as K increases; Proposition 1 predicts decay roughly like H^{5/2}/sqrt(K d_min) plus H^3/(K d_min). If the measured width fails to shrink at this rate, or if online regret fails to drop as K grows under the stated coverage condition, the paper's offline-to-online bridge is falsified.
If this is right
- If Theorem 2 is correct, the online regret bound improves explicitly with K: the Dmax-dependent terms shrink at rates 1/sqrt(K d_min) and 1/(K d_min), so larger offline batches translate into provably less online exploration.
- Because only the envelopes, not the raw offline transitions, are passed to the online phase, the method offers a privacy-conscious way to reuse historical data.
- The Q-shaping version confines the policy's support to 'effective' state-action pairs, concentrating exploration where the upper envelope is at least the optimal value.
- The V-shaping version inherits pseudo-suboptimality set arguments, meaning states reachable only through clearly suboptimal pairs are visited few times, with the visit bound depending on Rmax and Dmax.
- Full coverage by the behavior policy is what makes Dmax shrink; under it, offline pretraining provably accelerates online fine-tuning even though the offline transitions are never reused online.
Where Pith is reading between the lines
- The same argument suggests a transfer-learning extension the paper only sketches: if envelopes were learned on a source MDP and applied to a related target MDP, the regret would need an extra distance term between the two MDPs; this is plausible but not proven here.
- A practical prediction follows: on domains where the behavior policy leaves some state-action pairs uncovered, the promised K-dependent speedup should degrade toward the unshaped rate for those pairs, which could be tested empirically.
- The clipping mechanism could be pushed further: by eliminating actions whose upper bound falls below the best lower bound by a margin, the effective state-action set might shrink beyond PairEff and yield even smaller regret.
- Since Rmax is bounded below by the range of the true optimal value, no amount of offline data can remove the Rmax term; the benefit of better envelopes is largest when the optimal value has a narrow range, as the sliding-window experiments illustrate.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a two-stage framework, 'Envelope Shaping,' for using offline data to accelerate online RL. In the first stage, Algorithm 2 runs an offline model-based value-iteration procedure with Bernstein bonuses on K trajectories to produce upper and lower envelopes (W, U, W̃, Ũ) for the optimal value/Q-function, under an H-split that ensures per-step independence. In the second stage, these envelopes are used to shape the exploration bonus and clip the value estimates of UCBVI, yielding Algorithm 1 (Q-shaping) and Algorithm 3 (V-shaping). The main theoretical results are Theorem 1, a regret bound for Q-shaping in terms of the envelope width Dmax and range Rmax, and Theorem 2, which substitutes an offline width bound from Proposition 1 to obtain a regret bound showing polynomial improvement as the offline dataset size K and coverage d_min grow. The paper also reports numerical experiments on layered tabular MDPs showing regret reductions relative to UCBVI and an upper-only shaping variant.
Significance. If the main results are correct as intended, the paper makes a useful contribution: it formally connects the offline sample size K and the behavior policy's coverage to the online regret, and it extends the shaping-function framework of Gupta et al. (2022) to learned, random value envelopes. The filtration argument for handling GK-measurable envelopes is a genuine technical step, as is the offline H-split width bound. The experiments are reproducible in principle via the provided code link. The central theoretical claim is, however, currently stated under an assumption that is weaker than what the proof actually requires; the advertised offline-to-online speedup only holds under full state-action coverage, not merely state reachability. This is a load-bearing gap that needs to be fixed before the result can be accepted as stated.
major comments (2)
- [§3.3 and Lemma 3 (Appendix A.3)] Section 3.3 assumes only state-level reachability, P^{πb}(s_h=s) ≥ d_min, but Lemma 3, Proposition 1, and hence Theorem 2 require d_min = min_{h,s,a} d^b_h(s,a) > 0, i.e., full state-action coverage by the behavior policy. State reachability does not imply that every action is tried in every reachable state. For any never-visited pair (s,a), the offline bonus in equation (19) is set to H−h, so the upper/lower envelopes for that pair have width Ω(H) and Dmax does not shrink with K. Consequently the K-dependent terms in Theorem 2 do not vanish and the promised offline-to-online speedup fails precisely for the unvisited pairs. The main text's wording 'full coverage of the MDP' is therefore misleading. Please restate the assumption as a lower bound on min_{h,s,a} P^{πb}(s_h=s,a_h=a), and state the required K ≥ 8H/d_min log(HSA/δ) condition in the main text of Theorem 2.
- [Theorem 2 / Appendix D] The proof of Theorem 2 in Appendix D consists of a single sentence: 'Replacing Dmax in Theorem 2's regret with the bound from Proposition 1 gives us the result.' The replacement is not immediate as written: Proposition 1 with equation (27) provides a width bound that is decreasing in h, so the maximum over layers is controlled by the h=1 bound, but the appendix does not say this. Moreover, the appendix labels the Q-shaping result as 'Theorem 7 (Offline Q-Shaping)' while the main-text theorem it proves is Theorem 2, and the phrase 'Theorem 2' is used self-referentially. This makes the main result's proof harder to verify.
minor comments (6)
- [§3.3] The condition is written as d_b_min ≥ 0; the strict inequality d_b_min > 0 is needed for the Chernoff bound and for the sample-complexity condition to be meaningful.
- [§4.1 / PairEff definition] The notation eU_{h(s)}(s,a) uses h(s), but h(s) is only defined informally; please define it explicitly before PairEff.
- [§4.2, Proof sketch] In the bonus-scaling paragraph, the normalization Z_i is written with min_{s'} W_{h+1}(s') and R_{h+1}, but the text does not state that R_{h+1} is positive on the event of interest; adding a one-line justification would help.
- [§5, V-shaping] The statement 'This enters the setting of transfer learning' appears in the conclusion, not in §5; check placement. Minor typographical issues such as 'who's structure' in §6 should be corrected.
- [Appendix D] Theorem 7's statement says 'Replacing Dmax in Theorem 2's regret with the bound from Proposition 1' but the theorem being proved is the offline version of the main Q-shaping theorem; fix the theorem numbering and cross-references.
- [Algorithms 1 and 3] The pseudocode line 'Compute width-based bonus b_t_h(s,a)' refers to b^{t,on}_h, but the symbol is introduced only in the text; use the same notation in the algorithm boxes.
Circularity Check
No circularity: the regret bounds are conditional on the learned envelopes and the offline bound on Dmax is derived from K and d_min, not from the online regret itself.
full rationale
The paper's central derivation is not circular. Theorems 1 and 3 are conditional regret bounds: given Assumption 1 (envelopes W_h ≤ V*_h ≤ U_h and Q-envelope analogues holding with probability 1−δ), the online analysis treats the envelopes as fixed G_K-measurable random variables and bounds online regret in terms of Rmax and Dmax. Theorem 2 then substitutes Dmax with the Proposition 1 bound obtained from the offline algorithm: Proposition 1 derives V_h − Vbar_h ≤ 2H^2[ c1 sqrt(2H L1/(K d_min)) + c2 2H L1/(K d_min) ] from the offline confidence bonuses and the coverage lower bound N_min. This is a genuine offline-to-online transfer argument: the bound scales with K and d_min, and the online phase does not refit the envelopes. No fitted parameter is renamed as a prediction, and no quantity in the regret bound is defined in terms of the regret itself. The paper does rely on external lemmas from Gupta et al. (2022) (Lemmas 6, 7, and Proposition 6 in the appendix), but these are cited with proofs available in that work, they are not self-citations, and they are used as technical tools rather than as the source of the claimed offline-to-online speedup. There is a separate, non-circular correctness concern: Section 3.3 states only state-reachability coverage P^{πb}(s_h=s) ≥ d_min, whereas Lemma 3 requires state-action coverage min_{h,s,a} d_h(s,a) > 0. If some action is never taken offline, N_min may be zero and the K-dependent Dmax bound fails. This affects the validity of the advertised speedup under the stated assumptions, but it does not make the derivation circular. Overall, the regret analysis is self-contained conditional on the stated coverage and envelope-validity assumptions.
Axiom & Free-Parameter Ledger
free parameters (3)
- c1 =
2
- c2 =
14/3
- delta =
user-specified confidence
axioms (5)
- domain assumption Full coverage by behavior policy: P^{πb}(s_h=s) ≥ d^b_min > 0 for all h,s (and d^b_min = min_{h,s,a} d^b_h(s,a) > 0).
- domain assumption Rewards are deterministic and known, r_h(s,a) ∈ [0,1].
- domain assumption Offline dataset D consists of K i.i.d. trajectories from the same MDP under πb, and online dynamics are independent of D.
- standard math Gupta et al. (2022) Corollary B.7 (Lemma 6) and other cited lemmas are valid.
- standard math Layered MDP assumption: state space is partitioned into H layers.
read the original abstract
We investigate the fundamental problem of leveraging offline data to accelerate online reinforcement learning - a direction with strong potential but limited theoretical grounding. Our study centers on how to \emph{learn} and \emph{apply} value envelopes within this context. To this end, we introduce a principled two-stage framework: the first stage uses offline data to derive upper and lower bounds on value functions, while the second incorporates these learned bounds into online algorithms. Our method extends prior work by decoupling the upper and lower bounds, enabling more flexible and tighter approximations. In contrast to approaches that rely on fixed shaping functions, our envelopes are data-driven and explicitly modeled as random variables, with a filtration argument ensuring independence across phases. The analysis establishes high-probability regret bounds determined by two interpretable quantities, thereby providing a formal bridge between offline pre-training and online fine-tuning. Empirical results on tabular MDPs demonstrate substantial regret reductions compared with both UCBVI and prior methods while remaining competitive with related approaches.
Figures
Reference graph
Works this paper leans on
-
[1]
Agarwal, A., Jiang, N., and Kakade, S. M. (2019). Reinforcement learning: Theory and algorithms
2019
-
[2]
Ajay, A., Kumar, A., Agrawal, P., Levine, S., and Nachum, O. (2020). Opal: Offline primitive discovery for accelerating offline reinforcement learning. arXiv preprint arXiv:2010.13611
Pith/arXiv arXiv 2020
-
[3]
G., Osband, I., and Munos, R
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax Regret Bounds for Reinforcement Learning . In Proceedings of the 34th International Conference on Machine Learning , pages 263--272. PMLR. ISSN: 2640-3498
2017
-
[4]
Azuma, K. (1967). Weighted sums of certain dependent random variables. Tohoku Mathematical Journal , 19(3)
1967
-
[5]
B., Chernova, S., Taylor, M
Brys, T., Harutyunyan, A., Suay, H. B., Chernova, S., Taylor, M. E., and Now \'e , A. (2015). Reinforcement learning from demonstration through shaping. In IJCAI , pages 3352--3358
2015
-
[6]
Cheng, C.-A., Kolobov, A., and Swaminathan, A. (2021). Heuristic-guided reinforcement learning. Advances in Neural Information Processing Systems , 34:13550--13563
2021
-
[7]
Chernoff, H. (1952). A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations . The Annals of Mathematical Statistics , 23(4):493--507
1952
-
[8]
V., Mohri, M., and Zimmert, J
Dann, C., Marinov, T. V., Mohri, M., and Zimmert, J. (2021). Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems , 34:1--12
2021
-
[9]
and Moitra, A
Golowich, N. and Moitra, A. (2022). Can q-learning be improved with advice? In Conference on Learning Theory , pages 4548--4619. PMLR
2022
-
[10]
Gupta, A., Kumar, V., Lynch, C., Levine, S., and Hausman, K. (2019). Relay policy learning: Solving long-horizon tasks via imitation and reinforcement learning. arXiv preprint arXiv:1910.11956
Pith/arXiv arXiv 2019
-
[11]
M., and Levine, S
Gupta, A., Pacchiano, A., Zhai, Y., Kakade, S. M., and Levine, S. (2022). Unpacking Reward Shaping : Understanding the Benefits of Reward Engineering on Sample Complexity
2022
-
[12]
Hoeffding, W. (1963). Probability Inequalities for Sums of Bounded Random Variables . Journal of the American Statistical Association , 58(301):13--30
1963
-
[13]
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is q-learning provably efficient? Advances in neural information processing systems , 31
2018
-
[14]
and Langford, J
Kakade, S. and Langford, J. (2002). Approximately optimal approximate reinforcement learning. In Proceedings of the nineteenth international conference on machine learning , pages 267--274
2002
-
[15]
Kang, B., Jie, Z., and Feng, J. (2018). Policy optimization with demonstrations. In International conference on machine learning , pages 2469--2478. PMLR
2018
-
[16]
Kolobov, A. et al. (2012). Planning with Markov decision processes: An AI perspective , volume 17. Morgan & Claypool Publishers
2012
-
[17]
Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2024). Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics , 52(1)
2024
-
[18]
Li, M., Zhang, J., and Bareinboim, E. (2025). Automatic reward shaping from confounded offline data. In Forty-second International Conference on Machine Learning
2025
-
[19]
Lykouris, T., Simchowitz, M., Slivkins, A., and Sun, W. (2021). Corruption-robust exploration in episodic reinforcement learning. In Conference on Learning Theory , pages 3242--3245. PMLR
2021
-
[20]
V., Sima, K., and Leong, T.-Y
Ma, H., Luo, Z., Vo, T. V., Sima, K., and Leong, T.-Y. (2025). Highly efficient self-adaptive reward shaping for reinforcement learning. In The Thirteenth International Conference on Learning Representations
2025
-
[21]
and Pontil, M
Maurer, A. and Pontil, M. (2009). Empirical Bernstein Bounds and Sample Variance Penalization
2009
-
[22]
Nakamoto, M., Zhai, S., Singh, A., Sobol Mark, M., Ma, Y., Finn, C., Kumar, A., and Levine, S. (2023). Cal-ql: Calibrated offline rl pre-training for efficient online fine-tuning. Advances in Neural Information Processing Systems , 36:62244--62269
2023
-
[23]
Y., Harada, D., and Russell, S
Ng, A. Y., Harada, D., and Russell, S. (1999). Policy invariance under reward transformations: Theory and application to reward shaping. In Icml , volume 99, pages 278--287. Citeseer
1999
-
[24]
Pan, S. J. and Yang, Q. (2010). A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering , 22(10):1345--1359
2010
-
[25]
Russo, D. (2019). Worst-case regret bounds for exploration via randomized value functions. Advances in neural information processing systems , 32
2019
-
[26]
Schaal, S. (1996). Learning from demonstration. Advances in neural information processing systems , 9
1996
-
[27]
and Jamieson, K
Simchowitz, M. and Jamieson, K. G. (2019). Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems , 32
2019
-
[28]
A., Krishnamurthy, A., and Sun, W
Song, Y., Zhou, Y., Sekhari, A., Bagnell, J. A., Krishnamurthy, A., and Sun, W. (2022). Hybrid rl: Using both offline and online data can make rl efficient. arXiv preprint arXiv:2210.06718
Pith/arXiv arXiv 2022
-
[29]
Xie, T., Jiang, N., Wang, H., Xiong, C., and Bai, Y. (2021). Policy Finetuning : Bridging Sample - Efficient Offline and Online Reinforcement Learning . In Advances in Neural Information Processing Systems , volume 34, pages 27395--27407. Curran Associates, Inc
2021
-
[30]
Xu, H., Ma, T., and Du, S. (2021). Fine- Grained Gap - Dependent Bounds for Tabular MDPs via Adaptive Multi - Step Bootstrap . In Proceedings of Thirty Fourth Conference on Learning Theory , pages 4438--4472. PMLR. ISSN: 2640-3498
2021
-
[31]
Ye, D., Chen, G., Zhang, W., Chen, S., Yuan, B., Liu, B., Chen, J., Liu, Z., Qiu, F., Yu, H., et al. (2020). Towards playing full moba games with deep reinforcement learning. Advances in Neural Information Processing Systems , 33:621--632
2020
-
[32]
and Brunskill, E
Zanette, A. and Brunskill, E. (2019). Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning , pages 7304--7312. PMLR
2019
-
[33]
Zhai, Y., Baek, C., Zhou, Z., Jiao, J., and Ma, Y. (2022). Computational benefits of intermediate rewards for goal-reaching policy learning. Journal of Artificial Intelligence Research , 73:847--896
2022
-
[34]
and Wang, Z
Zhang, C. and Wang, Z. (2021). Provably efficient multi-task reinforcement learning with model transfer. volume 34, pages 19771--19783. Curran Associates, Inc
2021
-
[35]
D., and Du, S
Zhang, Z., Chen, Y., Lee, J. D., and Du, S. S. (2024). Settling the sample complexity of online reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory , pages 5213--5219. PMLR
2024
-
[36]
Zheng, H., Shen, L., Tang, A., Luo, Y., Hu, H., Du, B., Wen, Y., and Tao, D. (2025). Learning from models beyond fine-tuning. Nature Machine Intelligence , 7(1):6--17
2025
-
[37]
Zhu, H., Gupta, A., Rajeswaran, A., Levine, S., and Kumar, V. (2019). Dexterous manipulation with deep reinforcement learning: Efficient, general, and low-cost. In 2019 International Conference on Robotics and Automation (ICRA) , pages 3651--3657. IEEE
2019
-
[38]
Zhuang, F., Qi, Z., Duan, K., Xi, D., Zhu, Y., Zhu, H., Xiong, H., and He, Q. (2020). A comprehensive survey on transfer learning. Proceedings of the IEEE , 109(1):43--76
2020
-
[39]
Zou, H., Ren, T., Yan, D., Su, H., and Zhu, J. (2019). Reward shaping via meta-learning. arXiv preprint arXiv:1901.09330
Pith/arXiv arXiv 2019
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.