Summary
This paper studies hybrid RL in linear MDPs, aiming to address the problem of whether hybrid RL can improve upon the existing lower bounds established in purely offline and purely online settings, without relying on the single-policy concentrability assumption. By combining offline dataset with online interaction, authors introduce computationally efficient algorithms which achieve sharper error bound and regret bound in offline and online settings.
Strengths
Existing theoretical works of hybrid RL under function approximation mainly focus on PAC guarantees which are not tight and require stringent concentrability assumptions on the quality of the behavior policy. Motivated by the question of whether hybrid RL is useful (i.e. improving upon the existing lower bounds established in purely offline and purely online RL without relying on the single-policy concentrability assumption, which is raised by Xie et al. (2022b)), authors provide computationally efficient algorithms for both PAC and regret-minimizing RL for linear MDPs, without relying on single-policy concentrability.
In particular, this work exhibits several interesting findings:
1. Algorithmically, two types of hybrid RL algorithms are introduced: an online-to-offline algorithm, which involves reward-agnostic online exploration followed by a pessimistic offline algorithm to learn an optimal policy; and additionally, an offline-to-online method that utilizes offline data to warm start an online algorithm.
2. Theoretically, authors show both algorithms improve upon existing sample complexity, which is measured with respect to either the PAC framework or the regret.
This work demonstrates clear rationale and compelling motivation, while clearly articulates its main ideas throughout the draft. Thorough discussion of related works have been provided. It develops a better theoretical understanding of hybrid RL in linear MDPs, which potentially benefits future works for hybrid RL with functional approximation in this context.
Weaknesses
Below are several potential improvements that authors are suggested to consider:
1. It is better to summarize and highlight the main technical novelties in the main text. There exist extensive theoretical studies in either linear MDPs or in hybrid RL. It is still not quite clear throughout the main text what the main technical challenges are in achieving the optimal policy in the studied context and what the technical novelties are in improving existing theoretical results. It seems to me that the proofs closely follow Xiong et al. (2023) in offline RL, Wagenmaker and Pacchiano (2023) in reward-agnostic exploration and He et al. (2023) in linear MDPs. As a result, it is important to point out how the studied settings can be technically challenging, and what novel arguments are developed compared to existing works.
Questions
1. Could you highlight the main technical techniques / reason why Alg. 2 can achieve better regret compared to Tan and Xu, 2024 and Amortila et al., 2024 for the linear MDP case?
2. In the studied setting, if we consider general function approximation or a more general class of MDPs with linear structure, do you envision the current analysis and results can be utilized to improve existing bounds?
3. Could you comment on the optimality of the provided bounds, whether dependence on the parameters involved can be further improved?
4. Could you provide an intuitive explanation of concentrability coefficient? And what is the range that indicates good concentrability? In line 135, does $d^*$ represent the occupancy measure of the optimal policy?
Limitations
This is a theoretical work, no negative social impact.