acceptodds
Under review as a conference paper at ICLR 2027

The Cost of Hyperparameter Tuning in Online Reinforcement Learning

Abstract

The performance of reinforcement learning (RL) algorithms is often benchmarked without accounting for the cost of hyperparameter tuning, despite its significant practical impact. In this paper, we show that such practices can misrepresent the perceived efficiency of RL methods and impede meaningful algorithmic progress. We formalize this concern by proving a lower bound showing that tuning hyperparameters in RL can induce an exponential blow-up in the sample complexity or regret, in stark contrast to the linear overhead observed in supervised learning. This highlights a fundamental inefficiency specific to the online learning setting. In light of this, we propose evaluation protocols that account for the number and cost of tuned hyperparameters, enabling fairer comparisons across algorithms. Surprisingly, we find that once tuning cost is accounted for, elementary algorithms can outperform their successors with more sophisticated design. These findings suggest the value of a tuning-aware evaluation perspective in how RL algorithms are benchmarked and compared, especially in settings where efficiency and scalability are critical.

Primary area:
reinforcement learning
Keywords:
hyperparameter tuning, reinforcement learning, evaluation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_FcW8OpenReview ↗
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 ∣Θ∣|\Theta|. 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 log⁡∣Θ∣\log |\Theta|–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.


  1. 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]).

  1. 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 M=6,T=120,L=⌊2T/M⌋=40M=6, T=120, L=\lfloor 2T/M\rfloor=40. For each 1≤i≤61\leq i\leq 6, the episodic reward Ri(aj)=1j=iR_i(a_j)=\mathbf{1}_{j=i}, where j∈{ 0,1,⋯ ,6 }j\in\set{0, 1, \cdots, 6}.

(ii) Consider a familiy of online RL algorithms constructed so that, a base learner AθA_\theta executes a0a_0 for t∈{ 1,⋯ ,40 }t\in\set{1, \cdots, 40}, and performs aθa_\theta for t≥41t\geq 41, where θ∈{ 1,⋯6 }\theta\in\set{1, \cdots 6}.

(iii) Prescribe a deterministic HPO instance that first executes A1A_1 for 4141 episodes. If a reward of 11 is observed, it allocates all remaining 7979 episodes to A1A_1 and returns its output policy. Otherwise, it executes A2A_2 for 4141 episodes. If a reward of 11 is observed during these episodes, it allocates all remaining 3838 episodes to A2A_2 and returns its output policy. Otherwise, it allocates the remaining 3838 episodes to A3A_3 and returns the output policy of A1A_1. No episodes are allocated to A4,A5,A_4,A_5, or A6A_6. This procedure satisfies Definition 3.5: it uses exactly 120120 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 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}S_0=\lbrace 1,2\rbrace, 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:

Corollary 3.7 (Regret Lower Bound). For a base agent Aθ\mathcal A_\theta, let Regθ(n,δ)\mathrm{Reg_{\mathit{\theta}}}(n,\delta) denote the smallest value that its regret ∑t=1n(max⁡πVπ−Vπt)\sum_{t=1}^{n}\big(\max_\pi V^\pi-V^{\pi_t}\big) does not exceed with probability at least 1−δ1-\delta, where πt\pi_t is the policy executed in episode tt. For any TT with 2T/∣Θ∣∈N2T/|\Theta|\in\mathbb{N}, there exist a set of base agents {Aθ}θ∈Θ\lbrace \mathcal A_\theta\rbrace_{\theta\in\Theta} and a family of episodic MDPs MΘ\mathcal M_\Theta such that no algorithm-agnostic HPO procedure can achieve, with probability greater than 1/21/2 on all M∈MΘ\mathcal M\in\mathcal M_\Theta, regret smaller than min⁡θ∈Θ∣Θ∣2Regθ(2T/∣Θ∣,1/2).\min_{\theta\in\Theta}\frac{|\Theta|}{2}\mathrm{Reg_{\mathit{\theta}}}(2T/|\Theta|,1/2).

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!

Thank you to the authors for addressing my concerns. I am willing to raise my assessment to a score of 3.

Reviewer_WbiWOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper addresses the pervasive issue of hyperparameter tuning in online RL and supports the common knowledge in the community that misreporting the tuning costs can impede algorithmic progress by causing unfair comparisons of new complex algorithms to their simpler baselines. Indeed, the authors show that in light of their evaluation protocol, simpler or “elementary” algorithms outperform the more sophisticated ones.The paper also proves a lower bound to show that tuning hyperparameters in RL can lead to a sample complexity blow-up.

Critical strengths
  1. The issue is timely and deserves ongoing attention

  2. This is useful to practitioners

  3. Evaluation protocols are always helpful if they challenge the existing hierarchy of algorithms and inspire new angles of research

Critical weaknesses

Major

  1. The conclusion to develop more Hyperparameter-Free RL does not necessarily follow from the paper. An HP-robust algorithm that is more computationally efficient than an HP-free one will always be preferable.

  2. Since the proposed evaluation metrics (Effective SC and Effective AUC) penalize algorithms exponentially in the number of tuned hyperparameters, the empirical rankings in Section 5 are dictated by seemingly arbitrary choices of which parameters are swept versus held fixed (e.g., penalizing PPO+GAE with M=81 for tuning λ, while treating Vanilla PPO as M=27 by fixing λ=1 and holding GRPO’s group size and ~20 shared PPO parameters constant). Assigning different post-hoc grid ranges to shared parameters in Table 1 and truncating training horizons by T/(M/3²) in Section 5.2 conflate an algorithm's intrinsic sample efficiency with the design choices of the hyperparameter grid.

  3. Previous protocols are left completely unmentioned. The omissions of Jackson et al. and Kurenkov et al. are highly relevant despite focusing on offline RL, and Agarwal et al. is the de facto most widely used evaluation protocol in the community.

Minor

  1. The AUC illustration does not seem necessary.

  2. The black mean lines in Figures 3 and 4 are very confusing and do not add much to the story, as the spread is really different across experiments. Please consider violin plots or other ways of capturing spread.

Jackson, Matthew, et al. "A clean slate for offline reinforcement learning." Advances in Neural Information Processing Systems 38 (2026): 161052-161083.

Kurenkov, Vladislav, and Sergey Kolesnikov. "Showing your offline reinforcement learning work: Online evaluation budget matters." International Conference on Machine Learning. PMLR, 2022.

Agarwal, Rishabh, et al. "Deep reinforcement learning at the edge of the statistical precipice." Advances in neural information processing systems 34 (2021): 29304-29320.

Questions for authors

How do the rankings in Section 5 change if all four algorithms are evaluated under a matched tuning budget (e.g., tuning only the top m=2 parameters or drawing a fixed number of K random configurations from identical, pre-specified ranges) over the exact same episode horizon?

Please address the weaknesses above. My main concerns are omitted related work, limited novelty and the aforementioned design choices.

2 comments

Thank you for the review and for the pointers to related protocols.

W1. "HP-free" does not necessarily follow; an HP-robust algorithm may be preferable.

The message our results support is to reduce the number of hyperparameters that must be tuned per task. Both hyperparameter-free algorithms and HP-robust algorithms with reliable defaults achieve this. Our framework treats the two alike: an algorithm whose defaults transfer has effective M=1M=1, which is exactly the m=0m=0 point in Use Case I.

W2. Rankings depend on which parameters are swept versus held fixed.

  • What the metric measures. Effective SC/AUC evaluate an algorithm together with its tuning protocol: given the hyperparameters that must be tuned, how much interaction is needed? Making this protocol, and in particular MM, explicit is the purpose of the metric. Standard reporting omits it, even though it changes conclusions.
  • Vanilla PPO vs. PPO+GAE. Fixing λ=1\lambda=1 is what defines vanilla PPO. The §5.2 comparison between the two therefore asks whether tuning λ\lambda is worth its cost, which is exactly the question our metric is designed to answer.
  • Other fixed hyperparameters. As in any tuning study, all hyperparameters outside the tuned set (including GRPO's group size) are held fixed across all configurations. Which hyperparameters are tuned is part of the protocol that the metric makes explicit.
  • Grid ranges in §5.2. As shown in Table 1, the three algorithms compared in §5.2 (GRPO, vanilla PPO, PPO+GAE) use identical grids for every hyperparameter they share: actor LR {10−5,3⋅10−5,10−4}\lbrace 10^{-5},3\cdot10^{-5},10^{-4}\rbrace, entropy {10−3,10−2,10−1}\lbrace 10^{-3},10^{-2},10^{-1}\rbrace, critic LR {10−4,3⋅10−4,10−3}\lbrace 10^{-4},3\cdot10^{-4},10^{-3}\rbrace. PPO+ADVN, which is used in §5.1 and not in the §5.2 ranking, is the only algorithm whose ranges differ.
  • The T/(M/32)T/(M/3^2) truncation. It is applied uniformly: every algorithm receives the same total budget 9T9T (GRPO trains each configuration for TT episodes, vanilla PPO for T/3T/3, PPO+GAE for T/9T/9).

W3. Prior evaluation protocols.

Thank you for the references. We have added the following to Related Work (§2):

Closest to our motivation, Kurenkov & Kolesnikov (2022) showed that in offline RL, algorithm comparisons depend on the online budget used to select among trained policies, and proposed reporting performance across such budgets; Jackson et al. (2026) refined this by measuring the budget in online evaluation episodes. In online RL, candidate configurations are trained with separate interaction, so tuning multiplies the training cost itself; our lower bound in Section 3 formalizes this for algorithm-agnostic tuning. Agarwal et al. (2021) recommended interval estimates, performance profiles and the interquartile mean to account for statistical uncertainty in RL evaluation; these tools are complementary to ours and can be used together with our metrics.

Minor. Thank you for the suggestion. In the revision, we have redrawn Figs. 3 and 4 as box plots with the per-environment points overlaid, replacing the mean lines.

Question: rankings under a matched tuning budget (related to W2).

Matched m=2m=2 would require fixing the remaining hyperparameters, whose values themselves need tuning, so we ran the matched-KK variant for the three algorithms ranked in §5.2 (PPO+ADVN is used only in §5.1). Each algorithm draws K∈{1,3,9}K\in\lbrace 1,3,9\rbrace configurations uniformly from its Table 1 grid (identical ranges for shared hyperparameters), and every configuration is trained for the same horizon TT, so M=KM=K for all (10,000 draws). GRPO ranks last in every draw. The gap between vanilla PPO and PPO+GAE closes or reverses (fraction of draws in which vanilla PPO ranks first):

KKEffective AUCEffective SC
161%46%
355%36%
949%18%

Hence GRPO's position does not change under this protocol either, while vanilla PPO's advantage in §5.2 comes from not having to tune λ\lambda, which is the cost our metric is designed to expose.

On novelty: our main contribution relative to the protocols in W3 is the metrics themselves. Effective SC/AUC charge each algorithm for the online interaction its tuning requires, with the multiplicative ∣Θ∣|\Theta| cost derived from our lower bound for algorithm-agnostic HPO in online RL (vs. log⁡∣Θ∣\log|\Theta| in SL), and they change the conclusion of the algorithm comparison in §5.2.

[Agarwal et al., 2021] Deep Reinforcement Learning at the Edge of the Statistical Precipice

[Kurenkov & Kolesnikov, 2022] Showing Your Offline Reinforcement Learning Work: Online Evaluation Budget Matters

[Jackson et al., 2026] A Clean Slate for Offline Reinforcement Learning

We hope these responses 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!

Thank you for responses. I think this alleviates most of my concerns.

I am still puzzled by the fact that this work requires deciding which HP to freeze and which ones to sweep. A huge part of PPO tuning is the outer loop HPs like the number of minibatches and update epochs [1].

There are other loss term coefficients that are clearly treated as HP in a lot of PPO implementations like the CleanRL or PureJaxRL ones on github.

Writing a paper on a widely accepted observation that HP tuning is costly and freezing a lot of the relevant HP seems incomplete. A positive interpretation is that this inclusion can only strengthen the paper, but its absence makes it complete nonetheless.

On a more cautious notes, adding the other HP to both the PPO variants could change the reported advantages.

My score now reflects both the authors' answers and my concerns that go beyond this review round.

[1] Beukman, Michael, et al. "Preventing Learning Stagnation in PPO by Scaling to 1 Million Parallel Environments." arXiv preprint arXiv:2603.06009 (2026).

Reviewer_VBTDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper the authors investigates the cost of hyperparm tuning and optimization problem, in the online Reinforcement Learning (RL) setting. Compared with the supervised learning case, hyperparam optimization in RL is more challenging, as revealed by the authors, linear vs. logarithmic dependence on the number of candidate configurations. As a popular setting, hyperparams as configurations form a Cartesian grid, the hyperparams optimization can even become exponential in the number of tuned hyperparameters.

Based on these findings, this paper proposes two new evaluation metrics, Effective Sample Complexity and Effective AUC, to incorporate tuning costs into algorithm comparisons. Experiments on MuJoCo environments, and use GRPO + several PPO variants, and illustrate that these metrics can favour search spaces and change algorithm rankings.

Critical strengths

The paper addresses a consequential evaluation problem. Reporting only the best configuration’s learning curve can conceal substantial interaction costs. Explicitly examining this issue is valuable for applications where environment interaction is expensive and could improve the interpretation of RL benchmark results.

The paper makes the tuning–performance tradeoff concrete. The proposed metrics and controlled comparisons across related policy-gradient methods provide an interpretable case study of how algorithm rankings depend on the evaluation objective. The use of multiple environments and repeated trials provides useful material for further analysis.

Critical weaknesses

On theoretical part

While the majority theoretical analysis is sound, here are a few things to check and gaps may affect its central guarantees.

  • The Theorem 3.6 proof, which is in Appendix C. Here in Step 6, the equation Pr(I∈S∣S)=∣S∣/MPr(I\in S\mid S)=|S|/M (line 806), may not hold.
    • Although the set SS of sufficiently trained learners can depend on the environment index II, independence of II from the tuner's initial randomness does not justify this identity, because the allocation is adaptive and thus SS can depend on the environment index II through observed rewards.
    • Also found this in Appendix D, Page 17, line 868.
    • Notably, an indistinguishability argument may repair the construction, but the current proofs leave the adaptive case unjustified.
  • Theorem 3.4, the proof on page 14, lines 710–713.
    • Here the proof considers the selected policy as the best policy among the trained configurations.
    • But, the procedure was described as selecting the empirically best configuration. They are different:
\quad\not\Rightarrow\quad V^{\pi_{\hat\theta}}=\max_\theta V^{\pi_\theta}.$$ ## On Experiment side Overall I think experiment looks good, with the following issues to improve the quality: * No actual tuner comparison; metric penalties partly drive trends. * Defaults selected and evaluated on the same tasks. * Episode-versus-timestep budget accounting unclear. * Ninefold budget adjustment; no budget-sensitivity analysis. * No uncertainty intervals for reported rankings.
Questions for authors
  • How is adaptive dependence handled in Appendices C–D?
  • Where are evaluation error and cost included in Theorem 3.4?
  • What justifies dropping validation error in Theorem 3.2?
  • Algorithm 2: shared or per-environment configuration selection?
  • A few about experiments:
    • Does Figure 3’s SC trend follow mechanically from 3m3^m?
    • Do rankings survive held-out tasks and different interaction budgets?
    • Do the metrics predict actual tuner performance?
3 comments

Thank you for the detailed and constructive review, and for checking both the proofs and the experiments so carefully.

Q1. How is adaptive dependence handled in Appendices C–D?

Thank you for pointing this out. Please see the General Response, which gives the updated Step 6 for App. C and the same step in App. D using the indistinguishability argument you mentioned.

Q2. Where are evaluation error and cost included in Theorem 3.4? (also: empirically best vs. best policy, L710–713)

Thank you for this question; we now include both explicitly. The naive RL HPO procedure allocates T/(2∣Θ∣)T/(2|\Theta|) episodes to training each base agent AθA_\theta, which returns a policy πθ\pi_\theta, and then evaluates each πθ\pi_\theta with n=T/(2∣Θ∣)n=T/(2|\Theta|) fresh rollouts with returns in [0,Vmax⁡][0,V_{\max}]. Let V^θ\hat V_\theta be the average return of these rollouts. The procedure outputs π^=πθ^\hat\pi=\pi_{\hat\theta} with θ^∈arg⁡max⁡θ∈ΘV^θ\hat\theta\in\arg\max_{\theta\in\Theta}\hat V_\theta. For a fixed θ∈Θ\theta\in\Theta, since AθA_\theta is a PAC agent, with probability at least 1−δ/(2∣Θ∣)1-\delta/(2|\Theta|), max⁡πVπ−Vπθ≤ϵθ(T2∣Θ∣,δ2∣Θ∣)\max_\pi V^\pi-V^{\pi_\theta}\le\epsilon_\theta\big(\tfrac{T}{2|\Theta|},\tfrac{\delta}{2|\Theta|}\big). Applying a union bound over all θ∈Θ\theta\in\Theta, with probability at least 1−δ/21-\delta/2 this holds simultaneously for every θ∈Θ\theta\in\Theta. Conditionally on training, the evaluation rollouts of each πθ\pi_\theta are i.i.d. with mean VπθV^{\pi_\theta}. By Hoeffding's inequality and a union bound over Θ\Theta, with probability at least 1−δ/21-\delta/2, ∣V^θ−Vπθ∣≤β:=Vmax⁡∣Θ∣log⁡(4∣Θ∣/δ)/T|\hat V_\theta-V^{\pi_\theta}|\le\beta:=V_{\max}\sqrt{|\Theta|\log(4|\Theta|/\delta)/T} for all θ∈Θ\theta\in\Theta. Let θ⋆∈arg⁡min⁡θ∈Θϵθ(T2∣Θ∣,δ2∣Θ∣)\theta^\star\in\arg\min_{\theta\in\Theta}\epsilon_\theta\big(\tfrac{T}{2|\Theta|},\tfrac{\delta}{2|\Theta|}\big). On both events, which hold simultaneously with probability at least 1−δ1-\delta, Vπ^≥V^θ^−β≥V^θ⋆−β≥Vπθ⋆−2βV^{\hat\pi}\ge\hat V_{\hat\theta}-\beta\ge\hat V_{\theta^\star}-\beta\ge V^{\pi_{\theta^\star}}-2\beta. Hence, max⁡πVπ−Vπ^≤min⁡θ∈Θϵθ(T2∣Θ∣,δ2∣Θ∣)+2Vmax⁡∣Θ∣log⁡(4∣Θ∣/δ)T.\max_\pi V^\pi-V^{\hat\pi}\le\min_{\theta\in\Theta}\epsilon_\theta\Big(\tfrac{T}{2|\Theta|},\tfrac{\delta}{2|\Theta|}\Big)+2V_{\max}\sqrt{\tfrac{|\Theta|\log(4|\Theta|/\delta)}{T}}. The evaluation term has the same order ∣Θ∣/T\sqrt{|\Theta|/T} as the leading term. The O~(min⁡θ∣Θ∣CFθ/T)\tilde O(\min_\theta\sqrt{|\Theta|C_{\mathcal F_\theta}/T}) rate and the matching lower bound in Thm 3.6 are therefore unchanged (up to constant and logarithmic factors). In the revision, this procedure is described just before Theorem 3.4, which now states:

Theorem 3.4. Suppose the returns of each evaluation rollout lie in [0,Vmax⁡][0,V_{\max}]. With probability at least 1−δ1-\delta, this procedure returns π^\hat\pi satisfying: max⁡πVπ−Vπ^≤min⁡θ∈Θϵθ(T2∣Θ∣,δ2∣Θ∣)+2Vmax⁡∣Θ∣log⁡(4∣Θ∣/δ)T≈O~(min⁡θ∈Θ∣Θ∣CFθT).\max_\pi V^\pi-V^{\hat\pi}\le\min_{\theta\in\Theta}\epsilon_\theta\Big(\tfrac{T}{2|\Theta|},\tfrac{\delta}{2|\Theta|}\Big)+2V_{\max}\sqrt{\tfrac{|\Theta|\log(4|\Theta|/\delta)}{T}}\approx\tilde O\Big(\min_{\theta\in\Theta}\sqrt{\tfrac{|\Theta|C_{\mathcal F_\theta}}{T}}\Big).

The proof in App. B has been replaced by the argument above.

Q3. What justifies dropping validation error in Theorem 3.2?

The validation error is absorbed into the leading term rather than dropped. The proof (App. A) carries the uniform validation deviation α=O((log⁡∣Θ∣+log⁡(1/δ))/N)\alpha=O(\sqrt{(\log|\Theta|+\log(1/\delta))/N}) (for bounded losses) explicitly. Under the standard rate in equation 2, the leading term is ϵθ(N/2,δ/(2∣Θ∣))=O(CFθlog⁡(∣Θ∣/δ)/N)\epsilon_\theta(N/2,\delta/(2|\Theta|))=O(\sqrt{C_{\mathcal F_\theta}\log(|\Theta|/\delta)/N}), so α\alpha is of no larger order whenever CFθ≥1C_{\mathcal F_\theta}\ge 1. In the revision, Theorem 3.2 now states the validation term explicitly:

Theorem 3.2. Suppose the loss takes values in [0,B][0,B]. With probability at least 1−δ1-\delta, Algorithm 1 returns f^\hat f satisfying: E[(f^(x)−y)2]−min⁡f∈FE[(f(x)−y)2]≤min⁡θ∈Θϵθ(N2,δ2∣Θ∣)+2Blog⁡(4∣Θ∣/δ)N≈O~(min⁡θ∈Θlog⁡∣Θ∣ CFθN).\mathbb{E}[(\hat f(x)-y)^2]-\min_{f\in \mathcal F}\mathbb{E}[(f(x)-y)^2]\le\min_{\theta\in\Theta}\epsilon_\theta\Big(\tfrac N2,\tfrac{\delta}{2|\Theta|}\Big)+2B\sqrt{\tfrac{\log(4|\Theta|/\delta)}{N}}\approx\tilde O\Big(\min_{\theta\in\Theta}\sqrt{\tfrac{\log|\Theta|\thinspace C_{\mathcal F_\theta}}{N}}\Big).

Here 2Blog⁡(4∣Θ∣/δ)/N=2α2B\sqrt{\log(4|\Theta|/\delta)/N}=2\alpha, with α\alpha obtained from Hoeffding's inequality over the N/2N/2 validation samples and a union bound over Θ\Theta. This also makes eq. 4 consistent with the proof in App. A.

Q4. Algorithm 2: shared or per-environment configuration selection?

Thank you for the question. Both, depending on the role of the hyperparameter:

  • Fixed (unreleased) hyperparameters take a single value shared across all environments: the reference configuration θref\theta_{\text{ref}}, chosen as the best configuration on average over environments.
  • Released hyperparameters are tuned per environment: in each environment, the effective metric is the best (max AUC / min SC) over the candidate set Γm\Gamma_m. Each point in Figure 3 is this per-environment optimum.

We have revised the last loop of Algorithm 2 to state this per-environment selection explicitly, as follows:

for m=0,1,2,3,4 do\textbf{for } m=0,1,2,3,4 \textbf{ do}

for e∈E do\quad\textbf{for } e\in\mathcal E \textbf{ do}

if Metric=AUC then\qquad\textbf{if } \mathrm{Metric}=\mathrm{AUC} \textbf{ then}

θm,e⋆←arg⁡max⁡θ∈ΓmNormMetricm(e,θ)\qquad\quad\theta^\star_{m,e}\leftarrow\arg\max_{\theta\in\Gamma_m}\mathrm{NormMetric_{\mathit{m}}}(e,\theta)

else\qquad\textbf{else}

θm,e⋆←arg⁡min⁡θ∈ΓmNormMetricm(e,θ)\qquad\quad\theta^\star_{m,e}\leftarrow\arg\min_{\theta\in\Gamma_m}\mathrm{NormMetric_{\mathit{m}}}(e,\theta)

end if\qquad\textbf{end if}

vm(e)←NormMetricm(e,θm,e⋆)▹ one point in Figure 3\qquad v_m(e)\leftarrow\mathrm{NormMetric_{\mathit{m}}}(e,\theta^\star_{m,e})\qquad\triangleright\ \text{one point in Figure 3}

end for\quad\textbf{end for}

vˉm←1∣E∣∑e∈Evm(e)▹ average over environments\quad\bar v_m\leftarrow\frac{1}{|\mathcal E|}\sum_{e\in\mathcal E}v_m(e)\qquad\triangleright\ \text{average over environments}

end for\textbf{end for}

Return: released sets {Um}m=04, candidate spaces {Γm}m=04, selected setups {θm,e⋆}m,e, and values {vm(e)}m,e, {vˉm}m=04\textbf{Return: }\text{released sets }\lbrace U_m\rbrace_{m=0}^{4},\ \text{candidate spaces }\lbrace\Gamma_m\rbrace_{m=0}^{4},\ \text{selected setups }\lbrace\theta^\star_{m,e}\rbrace_{m,e},\ \text{and values }\lbrace v_m(e)\rbrace_{m,e},\ \lbrace\bar v_m\rbrace_{m=0}^{4}

Here NormMetricm(e,θ)\mathrm{NormMetric_{\mathit{m}}}(e,\theta) is the normalized effective metric of θ\theta in environment ee at release level mm, i.e., with ∣Γm∣=3m|\Gamma_m|=3^m candidate configurations: for AUC, the learning curve is truncated at T/3mT/3^m episodes and its AUC is scaled by 3m3^m; for SC, the number of episodes to reach the threshold is scaled by 3m3^m. Both are normalized with the full-grid anchors p5,AUC(e)p_{5,\mathrm{AUC}}(e), p95,AUC(e)p_{95,\mathrm{AUC}}(e) and p5,SC(e)p_{5,\mathrm{SC}}(e) (lines 2–3; eqs. 13/14), which do not depend on mm. In Use Case I, this protocol matches Definitions 4.1/4.2: tuning is paid for, and done, separately in each deployment environment.

Q5(a). Does Figure 3's SC trend follow mechanically from 3m3^m? (also: metric penalties partly drive trends)

Partly. Effective SC is 3m⋅min⁡θ∈ΓmTθ(ϵ)3^m\cdot\min_{\theta\in\Gamma_m}T_\theta(\epsilon). The factor 3m3^m is mechanical, but min⁡θTθ(ϵ)\min_\theta T_\theta(\epsilon) is non-increasing in mm because Γm\Gamma_m grows. The trend is therefore not forced: releasing a hyperparameter pays off whenever it lowers the best-case number of episodes to reach the threshold by more than 3×3\times. We checked this directly on the Use Case I runs (Table 1 grids). The unscaled best SC does improve as hyperparameters are released (averaged over environments: PPO+GAE 1.02→0.611.02\to0.61, PPO+ADVN 1.21→0.731.21\to0.73 from m=0m=0 to m=4m=4). However, none of the 40 release steps (2 algorithms ×\times 5 environments ×\times 4 steps) improves it by more than 3×3\times; the largest improvement is 2.0×2.0\times. The trend thus reflects a real but insufficient benefit of tuning, rather than the 3m3^m factor alone.

Q5(b). Do rankings survive held-out tasks and different interaction budgets? (also: defaults selected and evaluated on the same tasks; ninefold budget adjustment)

  • Held-out tasks. We repeated Use Case I with a leave-one-environment-out protocol: the reference configuration is selected on four environments and evaluated on the held-out fifth. Across all 20 algorithm–metric–environment cases, m=0m=0 remains best in 19 of them (compared with 20 of 20 under the original protocol of Fig. 3, where the defaults are selected on all five environments). The single exception is PPO+GAE's Effective SC on Swimmer, where defaults selected on the other four environments transfer poorly and tuning two hyperparameters is best. Tuning all four hyperparameters is never optimal.
  • Budget. The "T/(M/32)T/(M/3^2)" adjustment in §5.2 is applied uniformly: it is equivalent to giving every algorithm the same total budget 9T9T (GRPO has M=9M=9 configurations, each trained for TT episodes; vanilla PPO has M=27M=27, each trained for T/3T/3; PPO+GAE has M=81M=81, each trained for T/9T/9), so it does not favor any algorithm. We repeated the §5.2 Effective-AUC comparison with total budgets kTkT, k∈{1,3,9}k\in\lbrace 1,3,9\rbrace (k=1k=1 is the standard T/MT/M split; k=9k=9 is the paper's setting):
kkGRPOvanilla PPOPPO+GAEbest in # envs (GRPO / vanilla PPO / PPO+GAE)
10.140.270.301 / 1 / 3
30.270.400.300 / 4 / 1
90.390.620.430 / 4 / 1

(Entries: Effective AUC divided by the total budget kTkT, i.e., the average normalized return over the whole budget, averaged over the five environments. This normalization makes different kk comparable; it differs from the AUC-quantile normalization of Fig. 4a, but the ranking within each environment is the same, and at k=9k=9 it matches Fig. 4a.) Vanilla PPO ranks first for k=3k=3 and k=9k=9, and GRPO ranks last on average for every kk. At k=1k=1 each PPO+GAE configuration receives only T/81T/81 episodes (35–46 episodes on Swimmer, HalfCheetah and Hopper), and on Hopper, HalfCheetah and Walker2d the average normalized return of every algorithm is below 0.130.13 (returns are normalized so that the 5th and 95th percentiles map to 0 and 1), i.e., none of the algorithms learns a reasonable policy within this budget. This is why §5.2 uses the 9T9T budget.

Q5(c). Do the metrics predict actual tuner performance? (also: no actual tuner comparison)

Our metrics are modeled on worst-case bounds. Effective SC mirrors the matching PAC bounds (Theorems 3.4/3.6), under which uniform allocation is optimal up to constant and logarithmic factors among algorithm-agnostic procedures. Effective AUC corresponds to the regret lower bound (Corollary 3.7) and is therefore optimistic. Practical tuners such as successive halving can still do better on benign instances. Effective SC/AUC therefore quantify the tuning cost that no algorithm-agnostic tuner can avoid in the worst case, rather than predict the realized performance of a specific tuner on a specific instance.

Episode vs. timestep accounting.

Budgets in §5 are measured in episodes, consistent with the episodic PAC formulation of §3. Each run is capped at 3 million environment steps. Because episode lengths differ across configurations, we truncate all curves to the common minimum number of episodes per environment, and this common length defines TT. We now state this explicitly in §5.

Uncertainty intervals. We performed a stratified bootstrap over seeds: in each of 1,000 bootstrap samples, the 10 seeds of every configuration are resampled with replacement, and all rankings and the choice of the best configurations are recomputed from the resampled seed averages. The reported rankings are stable. In Use Case I, the environment-averaged Effective AUC and SC degrade monotonically with mm in at least 99% of samples, for both PPO+GAE and PPO+ADVN. In Use Case II, the ranking vanilla PPO > PPO+GAE > GRPO is unchanged in 99.0% (Effective AUC) and 99.9% (Effective SC) of samples, and GRPO fails to reach the threshold in the same two environments in 99.9% of samples. We have added these results to the appendix (App. F). The top-ranked algorithm for each budget in Q5(b) is also unchanged in all samples.

We hope these responses 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!

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank all reviewers for their careful reading and constructive feedback. Reviewers VBTD and FcW8 both raised the same point about Step 6 in the proofs of Theorem 3.6 and Corollary 3.7, so we address it here. All other points are answered in the individual responses. We have uploaded a revised PDF in which changes are marked in red.

Step 6 of Theorem 3.6 / Corollary 3.7 under adaptive allocation

We thank both reviewers for this observation. Under adaptive allocation, SS may depend on II, so Step 6 (App. C, and the same step in App. D) needs an additional step, which we give below using the indistinguishability ("reference run") argument suggested by Reviewer VBTD. The bounds in Theorem 3.6 and Corollary 3.7 remain unchanged.

Updated Step 6. Fix the internal randomness ω\omega of HPO. Define the reference run h0(ω)h_0(\omega) as the interaction that HPO produces when every observed reward is 00; it depends only on ω\omega and not on ii. Let Nθ0(ω)N^0_\theta(\omega) be the number of episodes allocated to θ\theta in the reference run, and S0(ω):={θ∈Θ: Nθ0(ω)≥L}.S_0(\omega):=\lbrace\theta\in\Theta:\ N^0_\theta(\omega)\ge L\rbrace. The reference run also uses exactly TT episodes, so the argument of Step 4 gives ∣S0(ω)∣≤⌊M/2⌋+1|S_0(\omega)|\le\lfloor M/2\rfloor+1 for every ω\omega.

Claim: on MiM_i, if i∉S0(ω)i\notin S_0(\omega), then the run of HPO coincides with the reference run. We argue by induction over episodes. The decisions of HPO depend only on ω\omega and the observed history, and all MDPs share the same single state, so the two runs can differ only through observed rewards. By construction, AθA_\theta plays action 00, which yields reward 00 on every MiM_i, during its first LL executions, and then plays θ\theta, which yields reward 11 on MiM_i only if θ=i\theta=i. Hence the run on MiM_i can diverge from h0(ω)h_0(\omega) only at the first episode in which AiA_i is executed for the (L+1)(L+1)-th time. As long as the two runs agree, the execution count of AiA_i is at most Ni0(ω)<LN^0_i(\omega)\lt L, so this event never occurs and the two runs are identical.

Consequently, if i∉S0(ω)i\notin S_0(\omega), then Ni<LN_i\lt L on MiM_i, and by Step 5 the output of HPO is not optimal on MiM_i. Therefore {π^ is optimal on Mi}⊆{i∈S0(ω)}.\lbrace\hat\pi\ \text{is optimal on }M_i\rbrace\subseteq\lbrace i\in S_0(\omega)\rbrace. Now sample the environment index II uniformly from {1,…,M}\lbrace 1,\dots,M\rbrace, independent of ω\omega. Since S0(ω)S_0(\omega) is a function of ω\omega alone, Pr⁡(π^ is optimal on MI)≤Eω[Pr⁡(I∈S0(ω)∣ω)]=Eω[∣S0(ω)∣M]≤⌊M/2⌋+1M≤12+1M,\Pr\big(\hat\pi\ \text{is optimal on }M_I\big)\le\mathop{\mathbb{E}}\nolimits_\omega\big[\Pr(I\in S_0(\omega)\mid\omega)\big]=\mathop{\mathbb{E}}\nolimits_\omega\Big[\frac{|S_0(\omega)|}{M}\Big]\le\frac{\lfloor M/2\rfloor+1}{M}\le\frac12+\frac1M, and the rest of the proof is unchanged.

Check on Reviewer FcW8's example. The reference run of the reviewer's HPO allocates (41,41,38,0,0,0)(41,41,38,0,0,0), so S0={1,2}S_0=\lbrace 1,2\rbrace. The updated argument allows success only on M1M_1 and M2M_2, which is consistent with the reviewer's table (the allocations for i∈{3,…,6}i\in\lbrace 3,\dots,6\rbrace never fully train AiA_i). The realized set SS may still vary with ii (e.g., S={1}S=\lbrace 1\rbrace on M1M_1), but success on MiM_i always requires i∈S0i\in S_0, and S0S_0 does not depend on ii.

Same step in the proof of Corollary 3.7 (App. D). Here L=2T/ML=2T/M. Now consider any algorithm-agnostic HPO meta-algorithm with total budget TT, and fix its internal randomness ω\omega. Define the reference run h0(ω)h_0(\omega), its allocation Nθ0(ω)N^0_\theta(\omega) and S0(ω):={θ∈Θ:Nθ0(ω)≥L}S_0(\omega):=\lbrace\theta\in\Theta: N^0_\theta(\omega)\ge L\rbrace as in Step 6 of the proof of Theorem 3.6. Since the reference run uses exactly TT episodes, we have ∣S0(ω)∣ L≤T|S_0(\omega)|\thinspace L\le T, so ∣S0(ω)∣≤T/L=M/2|S_0(\omega)|\le T/L=M/2. Fix an instance MiM_i with i∉S0(ω)i\notin S_0(\omega). By the claim in Step 6 of the proof of Theorem 3.6, the run on MiM_i coincides with the reference run. In this run, AiA_i is executed fewer than LL times and therefore only plays action 00, while every other agent AθA_\theta plays action 00 or θ≠i\theta\neq i. Therefore, throughout all TT episodes, the meta-algorithm never executes the optimal action ii, and thus incurs unit gap in every episode. Hence RegHPO(T)=T\mathrm{Reg_{\mathit{HPO}}}(T)=T whenever i∉S0(ω)i\notin S_0(\omega). Now sample II uniformly from [M][M], independent of ω\omega. Since S0(ω)S_0(\omega) is a function of ω\omega alone, Pr⁡(RegHPO(T)<T on MI)≤Eω[Pr⁡(I∈S0(ω)∣ω)]=Eω[∣S0(ω)∣/M]≤1/2\Pr(\mathrm{Reg_{\mathit{HPO}}}(T)\lt T \text{ on } M_I)\le\mathop{\mathbb{E}}\nolimits_\omega[\Pr(I\in S_0(\omega)\mid\omega)]=\mathop{\mathbb{E}}\nolimits_\omega[|S_0(\omega)|/M]\le 1/2, and the rest of the proof is unchanged.

In the revision, we have replaced Step 6 in App. C, and the same step in App. D, with the argument above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.