Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning

Summary

The authors prove that augmenting an offline dataset with online data collection leads to improved sample complexity compared to online and offline RL in the tabular setting, under the condition of single-policy partial concentrability. This is an extension of previous work on single-policy concentrability, relaxing the requirement that the offline dataset cover the full state-action space of the optimal policy. The authors propose a three step algorithm, given a budget of $K^{on}$ online data collection steps - spend the first third estimating occupancy distributions, the next two thirds on imitating the provided dataset and an exploration focused policy respectively, and finally finding a policy using standard offline RL on the original and collected datasets. This algorithm can be run in polynomial time using a Frank-Wolfe approximation to find the optimal policies in the second step.

Strengths

- The algorithm and proof are both novel to the best of my knowledge, and address an important question in RL theory. - The result is a general improvement over previous work, relaxing the coverage requirements without imposing new constraints or significant additional computation. - The paper is generally well written without many typos or errors.

Weaknesses

- Some of the choices in the algorithm could be better justified in the main text. Without referring to the Appendix the motivation for the imitation and exploration datasets is difficult to understand. - While the Frank-Wolfe updates proposed include a polynomial stopping rule, it's not clear how feasible this bound would be in any realistic task. Minor: - Section 2 (Line 123): noation -> notation

Questions

- What is the definition of $f_{mixed}$ in section 4? - Intuitively, what do the terms $\gamma_1$ and $\gamma_2$ represent?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

The paper proposes a new three step algorithm in the hybrid RL setting for tabular MDPs that improves in terms of sample complexity on the pure online and as well as the pure offline setting. The notion of single-policy partial concentrability is introduced which offers an intuitive concept that connects the sample complexity of pure online and pure offline RL. The algorithm leverages results from reward agnostic exploration to explore the parts of the state-action space that are missing from the offline dataset and then applies an offline learning algorithm to find an $\epsilon$-suboptimal policy. The sample complexity result is compared to existing results and the algorithms advantages and limitations are discussed.

Strengths

The paper is well written and reads itself easily, the algorithm and the sample complexity result are introduced in a digestible manner without loss in rigor. The concept of single-policy partial concentrability captures the two problems with offline datasets well (lack of coverage and mismatch with the state-action distribution of the optimal policy) and provides a neat connection between sample complexity results of pure online and pure offline approaches. For the tabular setting without function approximation the sample complexity result is SOTA. The advantages and limitations of the algorithms are extensively discussed.

Weaknesses

The motivation/intuition why the number of samples coming from the offline dataset distribution needs to be increased with the imitation exploration policy is not clear to me. Why is the offline dataset and the dataset collected with $\pi^{explore}$ not enough ? I find the notation used for the single-policy partial concentrability coefficient slightly confusing: - In equation 10 I would write $\\{G_{h}\\}_{1 \leq h \leq H} \in G(\sigma)$ - in equation 11 I would write $G(\sigma) \coloneqq \\{ \\{ G_{h}\\}_{1 \leq h \leq H} | \forall 1 \leq h \leq H , G_h \subseteq S \times A, ... \\} $

Questions

How does the sample complexity result from "Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient" (Song et al., 2023) compare to the presented result? The mentioned paper looks at bilinear models so similarly to Wagenmaker and Pacchiano is not specifically designed for the tabular case.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The limitations are discussed. An empirical comparison of the presented algorithm with other hybrid RL algorithms would have been interesting but seems out of scope of the presented work. Negative Societal Impact - Not Applicable

Summary

This paper studies hybrid reinforcement learning under tabular MDPs, where the agent has access to both a given offline dataset and online interaction with environment. This paper first proposes an interesting notion of single-policy partial concentrability, which relaxs previous concentrability assumption and accounts for the trade offs between distributional mismatch and partial converage. Then this paper proposes a novel three stage algorithm, which can automatically identify the optiaml trade offs. Then the paper provides a sample complexity upper bound. The sample complexity result shows the benefit of hybrid RL compared with pure online or offline RL.

Strengths

1. The notion of single-policy partial concentrability is interesting and reasonable to me and relaxs previous concentrability assumption. 2. This paper proposes a novel three-stage algorithm for hybrid RL, which can automatically identify the optiaml trade offs between distributional mismatch and partial converage. Intuitively, the agent can imitate the offline dataset to collect partial informative data, and explore the unknown data which is not covered by offline dataset. 3. When compared to pure online or offline results, the samplexity complexity result shows the benefit of hybrid RL.

Weaknesses

1. This paper mentions Frank-Wolfe-type subroutine in introduction and conclusion in main body. However the Frank-Wolfe-type subroutine is even not discussed in main body. Also, pseudocode of algorithm 1 is deferred in Appendix, which make it not easy to read and follow the idea of algorithm. 2. This paper only provides theoretical results without experiment results.

Questions

As listed in weakness.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

There is no negative impact in this work.

Summary

This paper investigates tabular reinforcement learning (RL) in a hybrid setting, where both an offline dataset and online interactions with an unknown environment are available. The main question addressed is how to effectively use online data to enhance and complement the offline dataset for policy fine-tuning. The authors propose a three-stage hybrid RL algorithm that outperforms pure offline RL and pure online RL in terms of sample complexity. The algorithm does not require reward information during data collection.

Strengths

- Innovative approach: The paper introduces a novel three-stage hybrid RL algorithm that combines online and offline data to improve sample complexity in tabular RL. - Theoretical contributions: The authors develop a new notion, single-policy partial concentrability, which captures the trade-off between distribution mismatch and lack of coverage. They provide theoretical results that demonstrate the statistical benefits of hybrid RL compared to pure online and offline RL.

Weaknesses

- The paper provides no empirical evaluations or demonstrations of the proposed algorithm. Neither does it shed light on the design of practical algorithms. - There remain some issues unsolved in the paper. See the questions for details.

Questions

- Empirical estimation of the occupancy distribution in Sec. 3.1 can have high variance. How does the proposed approach handle this issue? - Why do we need to imitate the offline dataset? What if the dataset is collected with random policies? - The analyses are conducted in the tabular case? How to extend them to continuous state/action spaces?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

This paper studies a tabular reinforcement learning setting where the agent tries to learn the optimal policy by both offline data (obtained by exploiting the optimal policy) and online exploration. A three-stage algorithm is proposed to obtain such a policy, which has lower sample complexity compared to pure online and pure offline reinforcement learning algorithms.

Strengths

This paper proposes the first algorithm for the hybrid RL setting that can achieve lower sample complexity than pure online and pure offline algorithms, which is innovative and inspiring. Overall, The writing is clear.

Weaknesses

There are a few crucial technique details that are not clear enough, which should be well justified. Please see my questions below.

Questions

Line 120: what do the authors mean by a "unknown" initial state distribution? Does its value depend on specific applications? Line 126-127: What is the difference between a mixed deterministic policy and a randomized one? Could the author provide a small example to elucidate their difference? Definition 1: I think the definition of $C^\star$ is associated with some policy $\pi^\star$. If so, the authors should specify this. Line 195: How should one decide which samples belong to the first/second half? Or can we divide the two halves arbitrarily? In the "Imitating the offline dataset" step, the authors appear to assume that the offline dataset is obtained by executing an optimal policy. (1) If so, I think the authors should formalize this assumption. (2) Also, this assumption is strong (where the information of the optimality is leaked to the decision maker). Could the authors justify this assumption? It feels fishy that authors claimed that "Towards this end, it suffices to invoke the reward-agnostic online exploration scheme" in line 250, while they assumed that "the reward function is fully revealed upon completion of online data collection" in line 118.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Please see the weaknesses above.

Summary

This paper studies hybrid RL (online RL with offline data) in the specialized setting of tabular MDPs, while providing tighter bounds than prior works. Namely, they seem to propose a novel and weaker concentrability notion called single-policy partial concentrability. The algorithm takes three stages: 1. estimate occupancy distribution, 2. perform online exploration, 3. invoke offline RL for policy learning.

Strengths

1. A weaker notion of partial coverage for hybrid RL is proposed in Def 2. 2. While I'm not familiar with all previous hybrid RL works, this paper seems to be one of the first that obtains better sample complexity in online RL, in the tabular setting.

Weaknesses

1. While the paper is reasonably clear, I think the presentation is a bit incomplete and can be made more succinct. For instance, the main algorithm of the paper is not even in the main paper and requires reading the appendix. 2. The algorithm runs in three stages and is quite complicated for solving the tabular MDP problem. Also, I feel uneasy about Stage 1 of the algorithm, since estimating occupancy distributions is a hard problem in practice, eg. the hardness of DICE algorithms in offline RL is precisely due to this. 3. Can you discuss the computationally complexity of each stage, compared to optimal tabular methods like UCBVI? In Line 340, it says the FW subroutine might be expensive, but can you be more concrete and derive a big-Oh running time? My worry is that this paper, while obtaining better instance-dependent statistical bounds sacrifice the practicality of the algorithm. There are also no experiments to validate the practicality of the new coverage assumption.

Questions

1. How is f_{mixed} is defined in Eq. 26 and 27? I couldn't find a clear definition. 2. For Eq. 27, isn't the minimax-optimal result by Azar supposed to be $H^2 SA/\epsilon^2$ trajectories? 3. Where does the current analysis break when extending to more general MDPs, like linear MDPs?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

See above.

Follow up

Dear Reviewer, We would appreciate if you would you be so kind as to acknowledge and respond to the authors' rebuttal. This is crucial to ensure the reviewing process is conducted adequately. AC

Response

I acknowledge the authors' rebuttal and I remain my rating towards acceptance.