- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies an interesting problem regarding hyperparameter tuning for online reinforcement learning.
The authors briefly reviewed the statistical error for PAC learners in supervised learning, and subsequently discussed the counterpart in online RL, comparing logarithmic versus linear overhead in . Thm. 3.6 then formally established a constant-probability hardness result that supports the central claim of the paper.
In Sec. 4, the authors further proposed two metrics: effective sample complexity and effective area under the curve, used to estimate the hparam-tuning cost of a practical deep RL implementation.
Finally, Sec. 5 focused specifically on GRPO and PPO, including the latter’s GAE/ADVN variants. The authors presented –SC/AUC curves in Fig. 3 and compared SC/AUC across the base algorithms in Fig. 4.
Critical strengths
To conclude my overall assessment, I highlight the paper's key strengths below.
- The cost of hyperparameter tuning, is indeed a crucial aspect during the performance evaluation of a given online RL algorithm. I appreciate the paper’s central argument, as it highlights an important concern that is often overlooked by the community. In fact, the importance of hyperparameter tuning is also seen in offline RL literature (e.g., [1] and [2]).
- The paper is exceptionally clear in its writing, presentation of the mathematical arguments, and interpretation of the results.
[1] Zhang, S., & Jiang, N. (2021). Towards Hyperparameter-free Policy Selection for Offline Reinforcement Learning. arXiv [Cs.LG]. http://arxiv.org/abs/2110.14000.
[2] Liu, P., Zhao, L., Agarwal, S., Liu, J., Huang, A., Amortila, P., & Jiang, N. (2025). Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocol. arXiv [Cs.LG]. http://arxiv.org/abs/2502.08021
Critical weaknesses
In addition to the strengths, I also have concerns about potential gaps in the theoretical analysis. As requested by the reviewer guidelines, I summarize these concerns in the following paragraphs.
First, Cor. 3.7 is stated for an arbitrary base agent, whereas App. D only establishes the lower bound for a specifically constructed base-agent family. The universal quantifier in the statement is therefore not justified by the proof.
Second, in accordance with Def. 3.5 and Thm. 3.6, consider an HPO setup as follows.
(i) Let . For each , the episodic reward , where .
(ii) Consider a familiy of online RL algorithms constructed so that, a base learner executes for , and performs for , where .
(iii) Prescribe a deterministic HPO instance that first executes for episodes. If a reward of is observed, it allocates all remaining episodes to and returns its output policy. Otherwise, it executes for episodes. If a reward of is observed during these episodes, it allocates all remaining episodes to and returns its output policy. Otherwise, it allocates the remaining episodes to and returns the output policy of . No episodes are allocated to or . This procedure satisfies Definition 3.5: it uses exactly episodes, adaptively allocates them based on observed rewards, shares no data across agents, and returns a policy produced by an instantiated base agent.
And the resulting learner allocation is seen in the table below.
\\hline \text{The MDP index $i$} & \text{The budgets }(N_1, N_2, \cdots, N_6) & \text{The resulting }S \\\\ \\hline 1 & (120, 0, 0, 0, 0 ,0) & \set{1} \\\\ 2 & (41, 79, 0, 0, 0, 0) & \set{1, 2} \\\\ i\in\set{3,4,5,6} & (41, 41, 38, 0, 0, 0) & \set{1, 2} \\\\ \\hline \end{array}$$ (iv) We also follow the uniform MDP sampling protocol in L803-804. From this instance, one can see that: **(a) the conditional estimation in L806-807, i.e., $\Pr(I\in S|S)=\frac{|S|}{M}$, does not hold.** For example, when $S=\set{1}$, $\Pr(I\in S|S)=1$, which is no less than $\frac{1}{2}+\frac{1}{M}$. **(b)** The same applies to L864-869. **(c)** Also a typo found in L199: "*A**n*** algorithm-agnostic HPO...".Questions for authors
See the weaknesses above. I would consider raising my score if the authors convincingly address the identified gaps in their proofs.
2 comments
Thank you to the authors for addressing my concerns. I am willing to raise my assessment to a score of 3.
Thank you for the careful reading of our paper and the very careful check of our proofs. Your concrete example was extremely helpful in pinpointing where the argument needed to be strengthened.
Example on Step 6 (L806–807) and L864–869.
Please see the General Response, which gives the updated Step 6 for both Theorem 3.6 and Corollary 3.7 and checks it on your instance: the reference run gives S0={1,2}, consistent with your table.
Corollary 3.7 quantifier. Thank you for this point. Corollary 3.7 relies on the construction in App. D, so we have restated it in the same existential form as Theorem 3.6:
Typo (L199). Fixed: "An algorithm-agnostic HPO meta-algorithm...".
We hope the updated proofs address your concerns. If you have any other comments or feedback, please let us know. We look forward to hearing from you, and thank you again for the review!