- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies the problem of online refinement of an imperfect Q-function pretrained offline. The authors first establish a minimax sample complexity lower bound for this problem. They then propose the O2O-LSVI algorithm and show that it achieves better sample complexity than purely online reinforcement learning methods under additional structural assumptions.
Critical strengths
-
The lower bound provides a meaningful insight: even when the pretrained Q-function is sufficiently close to the optimal Q-function, online interactions are still required in the worst case for a certain range of accuracy levels.
-
The proposed algorithm establishes a regret bound under general function approximation that depends on the complexity of the function class. The paper also analyzes the additional regret caused by bounded misspecification of the reference function, making the theoretical analysis more comprehensive.
Critical weaknesses
- The -separable condition in Definition 5.1 and the bounded accuracy coverage assumption in Assumption 5.3 seem rather strong and may limit the applicability of the theoretical results under function approximation. Definition 5.1 requires the error of each reference Q-value to be either exactly zero or at least . Assumption 5.3 further requires that, at every stage, the probability of visiting the inaccurate region under any policy is at most . Together, these assumptions imply when , provided that is continuous and the state-action space is connected. In Remark 6.6, the authors emphasize that the tabular setting can be extended to continuous state-action spaces, where assuming continuity of is natural.
Appendix A allows the observed reference function to have a uniform perturbation of at most , which appears to relax the assumptions. However, it is not clear whether this extension fully addresses the applicability of the results to continuous state-action spaces. I remain concerned that these two assumptions may limit the relevance of the theoretical results to smooth continuous-control tasks.
- [1] has already studied how to leverage given predictions of optimal Q-values to improve regret in online RL. The current paper does not cite this directly relevant work, and its novelty relative to prior work needs to be further clarified.
[1] Golowich, N., & Moitra, A. (2022, June). Can Q-learning be improved with advice?. In Conference on Learning Theory (pp. 4548-4619). PMLR.
Questions for authors
-
Regarding Weakness 1, could the authors further clarify the applicability of this assumption to continuous-control tasks, or discuss whether the relaxed assumption in Appendix A fully addresses this concern?
-
Could the authors provide a more detailed comparison between the proposed work and [1]? Which part of the analysis is new beyond the extension to general function approximation?
5 comments
W2&Q2. Can you provde more detailed comparison with [1]?
A. We thank the reviewer for pointing out this closely related work. We agree that [1] is directly relevant and will include it in the related work. While both papers investigate how prior Q-value predictions can improve online RL, the key distinction lies in the structural assumptions under which pretrained Q-values provide improved sample efficiency.
Specifically, [1] introduces an approximate distillation condition, requiring that at every state and stage, there exists a nearly optimal action whose predicted Q-value does not significantly underestimate its true value:
where . In contrast, our -separable value-gap condition and bounded inaccuracy coverage assumption do not require accurate predictions of near-optimal actions at every state. Instead, they characterize pretrained Q-functions that are accurate in some regions but substantially inaccurate in others, with the visitation probability of inaccurate regions bounded by under any policy.
For example, our Example 5.6 considers missing offline coverage, where on covered state-action pairs but on uncovered pairs. At a completely uncovered state , assuming rewards are bounded below by , we have where
Therefore, the approximate distillation condition of [1] fails for , whereas our -separable condition holds with , and our bounded inaccuracy coverage condition can hold with . This demonstrates that our framework provides improved sample-complexity guarantees for pretrained Q-functions that do not satisfy the distillation condition required for the improved guarantees in [1].
Conversely, the distillation condition in [1] permits substantial errors on suboptimal actions, without requiring bounded inaccuracy coverage. Thus, the two conditions characterize different regimes rather than one strictly generalizing the other.
Beyond this structural distinction, our work extends the analysis to general function approximation and establishes a minimax lower bound demonstrating that uniform closeness of pretrained Q-values alone is insufficient to guarantee improved online sample efficiency.
We have revised the related work to acknowledge [1] and explicitly clarify these differences.
[1] Golowich, N., & Moitra, A. (2022, June). Can Q-learning be improved with advice?. In Conference on Learning Theory (pp. 4548-4619). PMLR.
Dear Reviewer Du8F,
Thank you again for your detailed and constructive review and your support for our work. As we are about halfway through the discussion period, we would like to kindly follow up.
We would like to briefly summarize our main clarifications and revisions:
-
Applicability to continuous control (W1 & Q1). We provide an explicit continuous-state, continuous-action MDP construction satisfying the -separable value-gap and bounded inaccuracy coverage conditions, with and arbitrarily small positive . The construction also admits a finite-dimensional Bellman-complete function class, demonstrating compatibility with continuous function approximation. We have added this example to Appendix B.
-
Comparison with prior Q-value advice methods (W2 & Q2). We expand the related work discussion to compare our assumptions with Golowich and Moitra (2022). Unlike their approximate distillation condition, which requires accurate predictions for a near-optimal action at every state, our conditions allow substantial inaccuracies in regions with bounded visitation probability. We provide an example where our assumptions hold while their condition fails, and clarify that the two frameworks characterize distinct regimes rather than one strictly generalizing the other. We additionally highlight our general function approximation results and minimax lower bound.
We would greatly appreciate it if you could let us know whether our responses address your concerns, and we would be happy to clarify any remaining questions.
We thank the reviewer for the constructive feedback and support for acceptance. We address the reviewer's concerns below:
W1&Q1 How will structural condition be applied to continuous control setitng**
A. We thank the reviewer for raising this important point. We agree that the β-separable condition and bounded inaccuracy coverage impose additional structure on the pretrained Q-function. However, we would like to clarify that these assumptions do not require discrete state-action spaces and can hold nontrivially in continuous-state, continuous-action MDPs. We provide an explicit construction motivated by Example 5.6.
1. Example: Continuous control with accurate and inaccurate trajectory regions.
Consider an episodic MDP with continuous action space A=[−1,1] and state space S=0,1×[0,1]. Each state is represented by s=(z,x), where z∈0,1 identifies one of two disconnected regions and x∈[0,1] is a continuous state variable.
At the beginning of each episode, let z∼Bernoulli(ρ). The region indicator remains unchanged throughout the trajectory, i.e., zh+1=zh. Within each region, consider the smooth reward function
\in\left[\frac14,\frac34\right],$$ and action-dependent transition dynamics $$P(x_{h+1}\in du\mid z_h,x_h,a_h) =\left[1+\eta a_h(2u-1)\right]du,$$ where $0<\eta<1$. These dynamics are continuous in the state-action variables and have full support over $u\in[0,1]$. Suppose the offline dataset contains trajectories only from region $z=0$, with sufficient coverage of its continuous state-action space. Following the pessimistic construction in Example 5.6, define $$Q_{\mathrm{ref},h}(z,x,a)= \begin{cases} Q_h^\star(z,x,a), & z=0,\newline 0, & z=1. \end{cases}$$ Since the reward is uniformly lower bounded by $1/4$, we have $$Q_h^\star(z,x,a)\geq\frac{H-h+1}{4}.$$ Consequently, $$|Q_{\mathrm{ref},h}-Q_h^\star|= \begin{cases} 0, & z=0,\newline Q_h^\star\geq 1/4, & z=1. \end{cases}$$ Thus, Definition 5.1 is satisfied with $\beta=1/4$. Moreover, since the region indicator is preserved under every policy, $$\begin{aligned} &\sup_{\pi} \Pr_{(s,a)\sim d_h^\pi} \left(Q_{\mathrm{ref},h}(s,a)\neq Q_h^\star(s,a)\right)\\ &=\sup_\pi\Pr_\pi(z_h=1) =\rho,\qquad \forall h\in[H]. \end{aligned}$$ Therefore, Assumption 5.3 is satisfied for any $\rho\in[0,1]$, including arbitrarily small positive $\rho$. This example has a natural trajectory-level interpretation: with probability $1-\rho$, the entire trajectory lies in the accurately pretrained region, and $Q_{\mathrm{ref}}=Q^\star$ at every step. With probability $\rho$, the entire trajectory lies in the uncovered region, and the pretrained Q-function is inaccurate at every step. **2. Compatibility with continuous function approximation.** Importantly, this example is not restricted to tabular value functions. Both $Q^\star$ and $Q_{\mathrm{ref}}$ are continuous within each region and continuous on the disconnected state-action domain. Furthermore, the construction admits a finite-dimensional, Bellman-complete function class. For example, consider the feature map $$\phi(z,x,a)= \begin{bmatrix} \mathbf 1_{\\{z=0\\}}^\top r(x,a) & \mathbf 1_{\\{z=1\\}}^\top r(x,a)& \mathbf 1_{\\{z=0\\}}^\top & \mathbf 1_{\\{z=1\\}}^\top & a\mathbf 1_{\\{z=0\\}}^\top & a\mathbf 1_{\\{z=1\\}}^\top \end{bmatrix}^\top.$$ For any bounded continuation value function $V$, its Bellman backup satisfies $$(\mathcal T_hV)(z,x,a)=r(x,a)+c_{z,0}(V)+a \cdot c_{z,1}(V),$$ where $$c_{z,0}(V)=\int_0^1V(z,u)\,du,\qquad c_{z,1}(V)=\eta\int_0^1(2u-1)V(z,u)\,du.$$ Therefore, $\mathcal T_hV$ belongs to the linear span of $\phi$, verifying Bellman completeness. Both $Q^\star$ and $Q_{\mathrm{ref}}$ also belong to this finite-dimensional function class. Hence, the example demonstrates that our structural conditions can hold under continuous states, continuous actions, and general function approximation. We have added this example in Appendix B of our revised manuscript.