Utilitarian Algorithm Configuration for Infinite Parameter Spaces
Authors: Devon R. Graham
Kevin Leyton-Brown
Venue: ICLR 2025 Poster (2025)
Keywords: Algorithm configuration
Utilitarian algorithm configuration
bandits
Primary area: reinforcement learning
TL;DR: The first utilitarian algorithm configuration procedure for searching infinite parameter spaces.

Abstract: Utilitarian algorithm configuration is a general-purpose technique for automatically searching the parameter space of a given algorithm to optimize its performance, as measured by a given utility function, on a given set of inputs. Recently introduced utilitarian configuration procedures offer optimality guarantees about the returned parameterization while provably adapting to the hardness of the underlying problem. However, the applicability of these approaches is severely limited by the fact that they only search a finite, relatively small set of parameters. They cannot effectively search the configuration space of algorithms with continuous or uncountable parameters. In this paper we introduce a new procedure, which we dub COUP (Continuous, Optimistic Utilitarian Procrastination). COUP is designed to search infinite parameter spaces efficiently to find good configurations quickly. Furthermore, COUP maintains the theoretical benefits of previous utilitarian configuration procedures when applied to finite parameter spaces but is significantly faster, both provably and experimentally.

Published as a conference paper at ICLR 2025
UTILITARIAN ALGORITHM CONFIGURATION FOR INFINITE PARAMETER SPACES
Devon R. Graham & Kevin Leyton-Brown
Department of Computer Science University of British Columbia
Vancouver, BC
(drgraham, kevinlbj@cs, wbc. ca
ABSTRACT
Utilitarian algorithm configuration is general-purpose technique for automatically searching the parameter space of a given algorithm to optimize its performance, as measured by a given utility function, on a given set of inputs. Recently intro- duced utilitarian configuration procedures offer optimality guarantees about the returned parameterization while provably adapting to the hardness of the under- lying problem. However, the applicability of these approaches is severely limited by the fact that they only search a finite, relatively small set of parameters. They cannot effectively search the configuration space of algorithms with continuous uncountable parameters. In this paper we introduce a new procedure, which we dub COUP (Continuous, Optimistic Utilitarian Procrastination). COUP is designed to search infinite parameter spaces efficiently to find good configurations quickly. Furthermore, COUP maintains the theoretical benefits of previous utilitarian con- figuration procedures when applied to finite parameter spaces but is significantly faster, both provably and experimentally.
INTRODUCTION
Algorithm configuration is general-purpose technique for optimizing the performance of algorithms by automatically searching over the space of their input parameters. Given set of possible parameter assignments (i.e., a set of "configurations") our objective is to find one that makes the algorithm perform well on average, over a set of inputs of interest. Recently, attention has begun to shift from procedures that define performance in terms of average runtime toward procedures that define performance in terms of more general utility functions over runtime. Graham et al. (2023b) introduced Utilitarian Procrastination (UP), the first non-trivial algorithm configuration procedure that maximizes utility achieved instead of minimizing runtime. Unlike more naive approaches, UP can adapt to the hardness of the problem it faces, requiring provably less time guarantee optimality when many of the configurations it considers are suboptimal. However, UP requires that this set of candidate configurations be discrete and relatively small. This is major limitation; e.g., many algorithms have at least one continuous parameter. UP cannot effectively search over continuous spaces.
In this paper we present COUP (Continuous, Optimistic Utilitarian Procrastination), which designed to handle infinite (e.g., continuous) configuration spaces. Like UP, COUP is utilitarian and takes inspiration from the world of multi-armed bandits. However, COUP based on different bandit procedure that is guided by the principle of "optimism in the face of uncertainty" and is more readily adapted to handle large configuration spaces, including those with continuous parameters. COUP also offers significantly better performance than UP on finite sets of configurations because COUP does not try to explicitly rule bad configurations out, but instead simply ignores them once they no longer appear as promising other alternative configurations.
Section 2 discusses relevant background material. Section B introduces the cittte-oofiiuratinn-nooe version of COUP and shows that this version finds approximately optimal configuration in strictly less total time than UP. We simply call this version OUP since it, like UP, does not actually search over continuous parameter space. Section g introduces COUP, leveraging our understanding of

---

Published as a conference paper at ICLR 2025
the finite case into general-purpose procedure. We discuss empirical evaluations in Section S and conclude with Section 6
2 BACKGROUND
Given parameterizable algorithm and a set of possible parameter assignments, the goal of algorithm configuration is to find a parameter assignment that makes the algorithm perform well across a set of given inputs. If we also require that procedure gives guarantee about the near-optimality of its returned configuration, algorithm configuration can be seen as a multi-armed bandit problem (see e.g.. Lattimore & Szepesvári (2020) called approximate best-arm identification: finding an arm whose mean reward is close to the reward of the best arm available, In this case, it is not the regret of the procedure that concerns us, but the number of samples needed to guarantee the near-optimality of the returned arm. Even-Dar Dar et al. (2002) observe that if we want to find an arm whose value is within of the best with good probability, we could just take Ö( ²) samples of each arm and apply Hoeffding's inequality (Hoefiding I963) to obtain upper and lower confidence bounds on the mean reward of each arm that are sufficient to identify an approximately optimal one (i.e., one within an additive factor of optimal). However, this will be more samples than necessary in all but the worst case; any arm that is significantly worse than the best arm can be ruled out using fewer samples than are required by naively applying Hoeffding's ' inequality. The Successive Elimination (SE) procedure (Even-Dar et al., 2002) is able to identify each arm, where A, is the suboptimality gap for arm i. This can be a significant reduction when many arms are far from optimal. SE achieves this improved, adaptive bound by being anytime: it does not take an e as input. It starts by taking only a few samples of each arm, guaranteeing a relatively large c, and then improves this over time. This allows it to stop sampling bad arms and rule them out before it is finished. Up to logarithmic factors, taking mn min A -2) samples of arm i is not only sufficient, but also necessary for general inputs (Mannor & Tsitsiklis 2004h.
approximately optimal arm with only Omin A -. 2)) samples of
SE is a simple and intuitive procedure with approximately optimal sample complexity, but it can tend to over-investigate bad arms, sampling them repeatedly until it can expressly rule them out. The Upper Confidence Bound (UCB) procedure (Lai 1987p is an alternative to SE that focuses on arms that look promising and/or about which little is known. By repeatedly pulling the arm with largest upper confidence bound, UCB attempts to maximize the information it gains with each pull. For more discussion on the difference between SE and UCB and on their relative performance see the survey by Jamieson & Nowak 2014
There are two key differences between algorithm configuration and most other bandit problems. First, each arm pull imposes a stochastic cost arising from the amount of time it takes for the algorithm run to complete. Second, we have the option of bounding these costs by "capping" algorithm runs at any fixed time of our choice, but when we do so we obtain only censored information about the arm pull (we learn that the run would have taken more than the captime but not how much more). Overall, it is not the total number of samples that we want to control, but the total amount of time spent searching.
Most existing algorithm configuration procedures that offer theoretical guarantees aim to minimize average runtime. These can broadly be seen implementing either SE or UCB. These procedures either run all existing configurations simultaneously (i.e.. round-robin or in parallel), ruling out the ones that can be proved to be suboptimal after each step (Weisz et al. 2018 2019 2020 Brandt et al., 2023). or they iteratively select a particular configuration according to a confidence-bouue and run only this configuration (Kleinberg et al. 2017 2019). In either case, these procedures are significantly complicated by the fact that runtimes are potentially unbounded, and even the notion of optimality that they target requires adjustment to compensate for this. Other theoretically coooretially-mmoivateeed motivated approaches offer performance guarantees based on measures of complexity and guarantee notions of PAC optimality akin to those we present here (Gupta & Roughgarden, 2017 Balcan et al. 201 7] 202Ib. The focus there is not on the time consumed by the configuration process, but on the number of samples required to find a sufficiently good configuration.
index,
Utilitarian algorithm configuration procedures do not try to minimize expected runtime, but instead try to maximize expected utility, as measured by a spe-sppedfied utility function that captures the value associated with solving an input instance as a (weakly decreasing, but not necessarily linear) function of the amount of time spent solving it. For example, if we face daily scheduling problems, then getting solution after waiting 200 days is not 100 times worse than getting it after two days; both too
2

---

Published as a conference paper at ICLR 2025
long to wait. If one algorithm solves most inputs very quickly but occasionally takes an astronomical amount of time, while another algorithm takes a moderate amount of time on every input, determining which algorithm is "better" will likewise depend on our particular setting: How much time do we have? How much better is it to get an answer quickly? In Graham et al. (003a)) we generalized such intuitions, offering detailed argument from first principles that utility maximization is more appropriate objective (c.g., for algorithm configuration) than runtime minimization and showing that such utility functions are guaranteed to exist if our preferences for algorithm runtime distributions follow a certain reasonable structure based on the axioms of Von Neumann & Morgenstern (947).
UP GGahamm et al. 2023b) a utilitarian configuration procedure that can be seen as SE coupled with a doubling mechanism for discovering sufficiently large captimes. UP has several desirable qualities that we would like to incorporate into our own configuration procedure. First, UP maximizes utility instead of minimizing runtime. Second, unlike many runtime-optimizing procedures UP can make simple theoretical guarantees about the near-optimality of the configuration it returns. Third, UP is anytime, meaning that it provides better guarantee the longer it is run, and so requires minimal initial input from the user, who can simply observe the procedure's 's execution and terminate it when they are satisfied with the guarantee being made. Finally, UP's guaranteed performance is adaptive to the inputs it receives; it provably performs better on non-worst-cass inputs (i.e., the associated theoretical guarantees are input-dependent)
However, UP can only be applied to a finite (and relatively small) set of configurations since it cycles through these one by one and runs each of them in turn. This is prohibitive limitation would like to overcome. A natural idea would be to sample a finite set from the infinite configuration space and simply run UP on this set. The optimality guarantee offered by UP would then be made with respect to the best configuration in this subset, and if enough configurations are sampled, we can guarantee that our subset will be likely to contain least one of the top, say, 7-fraction of all configurations. This strategy will work, but since the choice of y potentially limits the quality of the configuration we are likely to find, we would like to make our procedure anytime y as well; we would like our procedure to start with a relatively small set of configurations (i.e., a relatively large 7) and grow this set as time goes on, shrinking the 7 it can guarantee. Of course we still wish to be anytime with respect to the accuracy parameter e, and here we run into a problem with UP. Since UP loops over all remaining configurations, at any point during its execution it will have run all of these configurations on effectively the same number of instances (at most the difference is one). What should we do when we want to expand the set of configurations we are considering? Any newly added configuration will have a large upper confidence bound, since we will know little or nothing about it. This will severely limit the anytime we can guarantee because it remains possible that the new configuration is much better than all the existing ones. So new configurations would need be "caught up" when they are added. How should we do this?
One extreme strategy is completely "catch up" new configurations by running them on all existing instances. This is unnecessarily costly because it fails to leverage what has already been learned about promising configurations. At the other extreme, we could simply refrain from ''aaching up" new configurations at all, just adding them to the existing pool, forever estimating them with fewer samples and thus lower accuracy. This would effectively limit the e we could guarantee to the lower accuracy of these newly introduced configurations. Is there way to balance these two extremes and integrate new configurations into the estimation process smoothly? This Icads us to the UCB procedure. In terms of the runtime cost we incur, we would prefer to take the second extreme approach above and not do anything special with new configurations. However, this would lead to configurations with relatively large upper confidence bounds, which would limit the optimality guarantee we could make. If we choose instead to focus on configurations that have large upper bounds, as UCB does, we will explore new configurations just up to the point where something else looks better, and then stop.
Thus, whereas UP was built around the SE procedure, COUP is built around the UCB procedure. Like UP, COUP utilitarian, adaptive, and anytime with respect to the optimality parameter e. At the same time, COUP can also be applied to infinitely-large sets of configurations, and is also anytime with respect 7, the fraction of unexplored configurations. COUP initially makes guarantees for a small set of configurations, then expands this set while simultaneously improving the optimality guarantee that can make with respect to this (growing) set. What's more, COUP also beats UP at its own game: COUP is significantly faster than UP when the input actually is a fixed, finite set of configurations. Because is built on the SE algorithm, UP runs all suboptimal configurations until they can explicitly be eliminated. For some sets of inputs this can be necessary but in many cases it is
3

---

Published as a conference paper at ICLR 2025
more efficient to rule out poor-perforning configurations by learning more about (i.e., by narrowing the confidence bounds of) other, better-performing configurations. COUP provably stops running sub-optimal configurations well before they would be climinated by UP. Additionally, we re-evaluate a key component of UP-the condition it checks before doubling a configuration's 's captime- and propose an improvement. UP attempts balance the estimation error due sampling with the error due to capping. We argue that this is better achieved with different doubling condition that emerges from a more careful analysis of the confidence bounds.
3 THE CASE OF FEW CONFIGURATIONS, OUP
We begin by presenting and analyzing the finite-oofiiuuration-ppe version of COUP, which we call OUP (Algorithm[]) MD indicate that it does not search over continuous spaces like COUP does. OUP can most easily be understood as a UCB procedure for finding configurations with good capped mean utility, along with a periodic doubling scheme that allows larger and larger captimes to be considered. Like UP, it is adaptive and anytime in the optimality parameter e.
We are given a set of configurations, indexed by i, and a set of instances, indexed by j. We will use bij to denote the true uncapped runtime of configuration i on input j. and 4sj (x) == min(f4j, k) to be the x-capped runtime of on j. When we do a run, we observe tiy (K) rather than 4yy these coincide for any run that completes. The instance distribution D,, along with any randomness of the algorithm or execution environment will together induce a runtime distribution for each configuration i. We will use D; to denote this runtime distribution, and F; to denote its CDF. For each configuration i, the true uncapped expected utility is U, := EA-D. [u( The cumulative distribution function is (x) : Pr,-D, (t S x²). The capped expected utility is U₃(K) == Et-D, [u[ min(t, k))]. Finally, the optimality gaps A, := max, Up. U, partially determine the hardness of the problem; if a configuration has large optimality gap A, then it will be easier to rule out. The notion of optimality that we target is given by the following definition.
Definition 1 (e-optimal). A configuration is e-optimal if A, S.
The error associated with m runtime samples at captime k is axmm, x)) In (1mmaamm 2 x 1) 182
2m chosen to satisfy Hoeffding's inequality and the necessary union bounds. An execution of OUP will be called clean if at all times during its execution we have | F(,s))] S a(m,, Ka) and - (Ra)) I (1 - u(r:)) a(m,, K,) for all configurations i. So during a clean execution, empirical capped average utilities are close to true capped average utilities and empirical CDF values are close to true CDF values at the captime Ki.
Lemma 1. An execution of OUP is clean with probability at least 1 1 ò.
All proofs are deferred to the appendices. The idea behind Lemma I is that the bounds that define a clean run hold initially, they do not change in any round where is not selected, and by Hoeffding 's inequality they hold with high probability in any round where i is selected. The next lemma shows that during a clean execution, the confidence bounds will be valid, and also not too far apart.
Lemma 2. For all at all points during clean execution of OUP we have LCB, S U. < UCB, and UCB, - LCB; I 20(ms, k:)) + u(x))(1 F.(Ra)).
The upper and lower bounds are defined in Algorithm T Each iteration of OUP's main loop corresponds to an iteration of the UCB procedure, with an additional check to see if the captime needs to be doubled. In each iteration the configuration with largest upper bound is selected (Line 7). The doubling condition is then checked (Line 9) and, if necessary, instances that had previously capped are rerun at the newly doubled captime (Line 11). A new runtime sample is drawn, and the sample mean and confidence bounds are recomputed. Finally, we attempt to eliminate provably suboptimal configurations (Lines 20)2 This loop repeats until terminated by the user, at which point it returns the configuration with largest lower confidence bound, which is the configuration we can prove the smallest suboptimality for. We can now state the main theorem of this section.
Theorem With probability at least 1 - 8, OUP eventually returns an optimal configuration and it returns an c-optimal configuration if it is run until 20sore + u(Keprs) )1 Feepe (K )) S c. Furthermore, for any suboptimal configuration i, if m, and K2 ever become large enough that
20(m; K2) + ul u(Ks) (1 F((Ks)) < Ai
(I)
4

---

Published as a conference paper at ICLR 2025
Algorithm 1 OUP
1: Input: configurations i = 1,... instances j = 1,2,... utility function failure probability 8.
2: + {I,...,1) ",.
P candidate configurations
3: for E I do
4:
LCB, t 0; UCBB + 1; t 0; F; + 0; m4 + 0; ni +
initializations
5: end for
6: for r = = 3,2,3,.... do
7:
i arg m UCBp
8:
m, m, +1
9:
if 2a( k2) I u(xx)((1 F.) then
> captime doubling condition
Ki <- 2kg
11:
La (x(4), Lim, (Mi4) c runtime of configuration on instances 1,..., my with timeout K;
else
13:
tim, (Ki) t runtime of configuration on instance m, with timeout Ki
end if
F + [6E(mm) (x)))))
15:
> fraction of runs that completed
16:
0.+ 1 2i uu (k:))
empirical average utility
17:
UCB: +- U; + u(Ki)) aam;; 1s.)
18:
LCB, +ū;
Ü. -- aa R4) w(Ks)(( P.)
19:
i' + arg maxvel LCBB
for 1 do
21:
UCB,, < LCB,- then
b if i' is suboptimal b remove i' from consideration
It IX end if end for
23:
24:
25: if exccution is terminated or [
then
26: return
27: end if
28:
end for
then will never be run again, and will be outright eliminated once mi, Riy Mgose and Kieeet are large enough that
2a 2a(m;, K4) 20(Moo Kepps) ) (1 + u(Kisppe) (1 Fiore (Koppt))
A..
If OUP keeps selecting and running i, then the term 2a(m;, (i00m,;,,,] K.)) + -1x will continue to shrink. So we will eventually have 20(m; K2) rumning i. In either case, we will eventually stop running any suboptimal i. This puts a hard limit on the amount of time will ever dedicate to any suboptimal configuration, and this limit is better than the corresponding guarantee made by UP: compare our Theorem | to Theorem in Graham al. (2023)). UP guarantees that will be eliminated
u1x,)(1 (1x F.(k,)) < A, as long we keep
the bound in Equation
( is satistied.
The bound in Equation M guaranteed by OUP is a necessary condition for this. OUP does not keep running suboptimal configurations until they can be eliminated, as UP does. Instead, simply stops running them, while continuing to tighten the bounds of better configurations instead.
Algorithm D is stated using the old doubling condition introduced in UP. We propose an alternative based on examining the confidence width UCB: - LCB, = 2(1 u((:)) a(m,, Ks)) + u(N;) (1
F, + am,, nz))- The first term is the enror from runs below к; and the second term is the error from runs above K;. Our new doubling condition attempts to balance these two terms. Due to space constraints we discuss this more in Appendix
ultimately Line Algorithm becomes
9:: if 2 u(k)) a(m, m4) < u(Ks)) (1 F amm,, k:)) then captime doubling condition
The change to the continuous-space version COUP is analogous (Line 18 of Algorithm 2. Imple- menting this refined doubling condition improves the performance of both UP and (C)OUP.
5

---

Published as a conference paper at ICLR 2025
4 THE CASE OF MANY CONFIGURATIONS: COUP
We now assume we have a very large, possibly uncountably infinite, set of configurations A, along with an associated distribution D over configurations A from which we sample. It is no longer feasible to target the configuration with maximum utility OPT m&X Ua. It may be arbitrarily unlikely that we ever sample this configuration and, in fact, such a maximum may not even exist. So we must relax our objective. For any Y E (0, 1), let OPT = sup { Pra-DA UUa S pl S 11-7}- The quantity OPT" marks the top [1/r]-que -quantile of expected utilities. That is, OP77 is the utility of the best configuration that remains after we have excluded the top y-fraction of configurations. The notion optimality that we will target is given by the following definition.
Definition 2 ((c, 7) -optimal). A configuration E A is (c, oppptmall Uf 2 OPT -c
We present the general version of COUP in Algorithm 2 The procedure runs in successive phases. Each phase is an execution of the few-configuration version, OUP, with the bounds being chosen carefully that runs can be shared across phases. Each phase of COUP is characterized by two parameters: "pp E (0, 1) determines the tail quantile being targeted in this phase, and cp E (0. 1) determines the level of optimality being targeted. At the start of each phase p, COUP samples enough configurations, where is the 36
new configurations to ensure that has a total of 7p = In a²p²
failure probability and æ is the mathematical constant (Lines 5 and 6). COUP then essentially runs the finite-space version OUP on this set of mp configurations until it can prove "p-optimality (Lines 15-28). However, COUP "maintains state" between phases so that it can build on what it has already learned. Confidence bounds phase p incorporate any runs performed in previous phases (Lines 12 and 13), with the error terms being set carefully that the total failure probability is controlled across all phases.
If % is relatively small and Ep is relatively large, then COUP will sample large number of con- figurations in phase p. but not work too hard to prove that any of them is approximately optimal. On the other hand, if 7/p is relatively large and cp is relatively small, then COUP will sample only few configurations and work very hard to prove one of them is nearly optimal (with respect to this set). Since we are interested in procedures that are anytime in both e and 7, we will be interested in sequences of parameters for which Ep + 0 and - 0 as - oc, We can think of ep as controlling the rate at which we explore new instances, and 7/p as controlling the rate at which we explore new configurations. They are dissimilar in what they quantify though: Ep is in "units" of utility, while "p in "units" of probability.
COUP never eliminates configurations because it needs them in later phases to make statistical guarantees about relative optimality, but we know it will stop running them well before we will
be able to consider them for elimination anyway. Define a (m, k) == nmm" 111/ to be the confidence width, chosen to satisfy Hoeffding's ss inequality and the necessary union bounds. The p-th phase of an execution of COUP will be called clean if |P; Fi(Ks) I ap(m;, Ki) and Ü. - UR:))) s (1 - u(:)) (m,, K2) for all m, and K; for all configurations E Ap- Lemma 3. An execution of COUP is clean for all phases with probability at least 2'
2m
Lemma 4. During a clean execution of COUP we have LCB, S U S UCB, and -UCB-LLCB S
(m,,m,, Kc) + u(ss) F2 (x:)) for all configurations i E Ap in all phases p.
The p-th phase of an execution of COUP will be called characteristic if there exists some ip E Ap with U, ,
Lemma 5. An execution of COUP is characteristic for all phases with probability at least 1 5
Finally, we can state our main theorem about COUP's performmcr............
Theorem 2. If COUP is run with parameters (c,, E2. and (?1,"22...)) .2.). then with with probability at least 8 returns an (cp; "pp) -optimal configuration at the end of every phase p 1, 2,
5 EMPIRICAL EVALUATION
We first compare the performance of OUP with the performance of UP (Section 5.1 and with naive procedure also considered in our previous work (Graham al. 2023b that simply takes

---

Published as a conference paper at ICLR 2025
Algorithm 2 COUP
1: Input: distribution over configurations DA; instances j = 1,2,... utility function failure
parameter 6; phase parameters {Cp, 1,,,p1,,,,,....
2: <- 0
3: Ao
4: for 1,2,3,.. until terminated do
5:
Up + 38
6:
N₂ + sample np - AAp new configurations from DA
7:
Ap Ap UN
b all configurations for this phase
8:
for E No do
initializations for new configurations
9:
LCB; + 0, UCB, + 1; + -0; t 0; m, + 0; K4
end for
11:
for E Ap do
update bounds for existing configurations
UCB; U, (1 u(Ks)) ap(ms; ki) LCB; t Ú. - 0 (m, ki)) u(x))(1 P.)
13:
14:
end for
15:
while A, UCB; maXiEA, LCB; 2 Ep do
phase termination condition
16:
+ arg Ea UCB,
17:
m, < m. +1
18:
if 12ap(mm, Ki) u(k=)(1 F.) then
captime doubling condition
19:
K; t- 2k;
20:
t/ (M44)))..) p...,ii time (Ra) runtime of instances 1,..,,, with timeout Ki
21:
else
22:
lim, (Ki) + runtime of on instance my with timeout Ki
23:
end
F.
(je(mL) cx.]]
> fraction of runs that completed
my
25:
Ü, m. E5 u u((i((Ks))
empirical average utility
26:
UCB, +++,, U, + (1 u(Ks)) appmms; Ki)
27:
LCB; + Ú, ( Rii) - u(xx)(1 F.) end while
28:
29:
end for
return arg maxieA, LCB:
enough runtime samples to satisfy Hoeffding's inequality for each configuration, and takes them at high enough captime that it can still make its guarantee whether they complete or not. We then explore the effects on performance when we expand our search to an infinitely-large set of configurations (Section 5.2). We show that the search of the configuration space does not cost COUP too much in terms of runtime, and we demonstrate COUP's flexibility in the way performs its search. We perform our experiments on three existing datasets from the algorithm configuration literature. The minisat dataset represents the measured execution times of the SAT solver by that name on generated set of instances (see Weisz et al. (2018) for details). The cplex_ron and eplex welle_rreiie. reqion datasets represent the predicted solve times of the CPLEX integer program solver wildlife conservation and combinatorial auction problems, respectively (see Weisz al. (2020) for details). In Section 5.3 we compare COUP and OUP to a variety of other procedures that do not make utilitarian optimality guarantees. We focus the two utility functions considered in our previous work (Graamm et al., 2023b). The "log-Laplace" utility function is defined as (t = - if < Kg and (t = 2 defined as (t) 1- ift < Kg and Uumis (t) = 0 otherwise. The parameter Ko set to 60 in both cases, and the parameter is set to 1. To facilitate the comparison with UP we use the original doubling condition when recreating our previous experiments (Graham et al. 2023b Figures | and 2 For other experiments environment where restarting runs is not possible. Code to reproduce all experiments can found at https: / / thub. com/drgrhn coup
1 (M²)) otherwise. The "uniform" utility function is
use the improved doubling condition. We perform all experiments in
7

---

Published as a conference paper at ICLR 2025
minisat
cplex rcw
cplex region
1.0
1.0
1.0
2000
3aivele-330)
guarantted
guaranceed
guarantaed
0.6
0.6
0.6
0.4
0.4
0.4
0.9 1000
0.90
10
10"
10
066
10'
10'
10'
10"
10
Total time (CPU days)
Total time (CPU days)
Total time (CPU days)
minisat
cplex
cplex region
Narvejxo 63) 601)
Eguaranteed
0.8
Un
Eguaranted
Eguaranteed
OUP
due
OUP
0.6
0.6
0.6
0.1
0.4
0.4
Raa..
10
10 107 Total days)
10'
10
10
10'
10a
20"
10
100"
10
10'
10'
10"
101
Total time (CPU days)
Total time (CPU days)
Figure 1: The guaranteed by each procedure as function of total runtime using the log-Laplace utility function (top row) and uniform utility function (bottom row). OUP consistently outperforms both UP and the naive procedure for reasonable values of e, often by an order of magnitude and even when the the parameter of the naive procedure has been well-chosen.
Time per configuration (s)
minisat
Time per configuration (s)
cplex_rcw rrw
Time per configuration (5)
cplex region
OUP
OUP
DuP
20a
10
10>
10
105
204
02
0.4
0'6
0'8
0.0
0.1
0.2
0.3
0.4
0.0
0.2
0.4
0.6
Uuility configuration
Utility configuration
Utility of configuration
Figure 2: Total time spent by OUP on each configuration (log-Laplace utility function). Configurations are sorted according to average utility. OUP spends less time on all but the very best configurations.
5.1 THE CASE OF FEW CONFIGURATIONS
We first compare the performance of OUP with that of UP by recreating our previously published experiments (Graham et al. 2023b). Figure T shows that OUP consistently proves a meaningful in much less time than UP. OUP is faster by an order of magnitude or more (compare the top row of Figure to Figure 2 in Graham al. 2023b Furthermore, very simple naive approach based on Hoeffding's 's inequality can be faster than UP in some scenarios (i.e. for relatively small values of c) when the captime parameter is chosen appropriately for the given utility function. However, OUP is consistently faster than both UP and this naive approach, regardless of the chosen captime parameter. In Section 3 we argued that OUP will spend less time running bad configurations than UP because can stop devoting attention to them and focus on more promising ones instead. UP, on the other hand, continues to run suboptimal configurations until they are eliminated. Figure 2 shows that OUP does indeed spend considerably less time on suboptimal configurations.
5.2 THE CASE OF MANY CONFIGURATIONS
We now compare the performance of COUP with that of OUP to show that COUP's exploration of the configuration space does not cost too much. The results for the log-Laplace utility function are shown in Figure 3
We set 8 = 0.01 throughout. For each phase p we set 6p = e ep/6 and 7 = e r/3 This schedule allows COUP to sample large fraction of the configurations and the instances in the datasets we consider. When it is finished each phase, it can make an e, -,-optimality guarantee with respect to the set Ap of ny configurations. We compare the total configuration time of COUP at
8

---

Published as a conference paper at ICLR 2025
minisat
cplex
cplex region
1.0
1.0
1.0
ca eteed of phase
COUP
ene of phase
0.8
COUP
<at of phase
0.8
COUP
0.6-
0.6
0.5
0.4
0.2
0.2
0.2-
0.0
10
Total time (CPU days)
Total time (CPU days)
Total time (CPU days)
Time per confiquratioo (s)
OUP
COuP
Time per configuration (s)
OUP
Time per configuration
OUP
COUP
10
102
10"
0.
0.4 0.6
0.9
0.0
0.1 Unility of configuration
0.7
0.3
0.4
0.0
0.2 Utility of configuration
0.4
0.6
Utility of configuration
Figure 3: Performance of COUP compared to OUP, using log- log-Laplace utility function. COUP is anytime, but takes only a small factor more time than OUP. The bottom row shows the final times. OUP backtracks on the eplex_ree ex_region on dataset because COUP sampled a relatively good configuration in phase 5, which OUP is able to capitalize on, proving optimality in less total time than in phase 4.
0.0
1.0
1.0
0.2
suaranteed
'Quarenteed
0.4
0.6
0.6
1oozs
talenced foous
0.6
Flous Othe C
0.2
0.2
telanced
1.0
0.8
0.6
0.4
0.2
0.0
10
10P
10
102
10
10a
16
10a
-gaaratteed
Total time (CPU days)
Total time (CPU days)
Figure 4: Different schedules for exploring new configurations (refining ?) vs. exploring existing configurations (refining e) when running COUP. Results are for the log log-Laplace utility function and the cplex_row dataset.
the end of each phase to the time OUP takes to prove op-tmmaalyyy when applied directly to this set of up configurations. F shows that the total configuration time required by COUP not much different from the time required by OUP, indicating that COUP efficient exploring the configuration space.
COUP is extremely flexible in the way it explores new configurations relative to exploring new instances. The parameter sequences "/1 72, and 61, C2 control the relative rates at which this exploration takes place. We demonstrate this flexibility in Figure g presenting various different exploration strategies. 'hee "y focus" strategy sets <p e -p/0 and 7p e - and so works to explore many configurations, making relatively weak guarantees about their optimality. The "e focus" strategy sets cp = e p/3 and ?pp -9330 and so explores relatively few configurations, but makes strong optimality guarantees with respect to these. The "balanced" strategy sets 6, = 7/p = e -P/5 In too intently until later in the search process. Once we have found
general, it is not wise to focus good configuration (i.c., one with relatively large upper confidence bound), new configurations can be ruled out relatively cheaply, because they quickly look worse than the good one. So it is helpful to find a good configuration quickly, and then later work on proving that it good. The "y then e"
strategy achieves this by setting Ep = e /300 and 7p = e p /3300
5.3 COMPARISON TO PROCEDURES WITH DIFFERENT GUARANTEES
Finally, while we see the main contribution of COUP as being its ability to search infinite parameter spaces and make utilitarian netr-optimality guarantees with respect to them, which other configu- ration procedures have not been able to do, some other procedures do make different but related guarantees. Comparing the performance of these various methods is not always easy since they

---

Published as a conference paper at ICLR 2025
minisat
cplex rcw
cplex region
100
100
100
Percent gap to optimal
75
75
75
50-
50
50-
25-
25-
10"
10"
1.0
10
966
102
10.
10a
10F
10
10"
107
Percent gap to optimal
100
100
100
75
50
25-
25
25
10
10a
10a
100
10 CPU time (days)
1o
10a
1022
CPU time (days)
CPU time (days)
Figure 5: Average configurator performance as measured by the percentage gap to best configuration in the dataset. Top row shows procedures optimizing the log-Laplace utility function. Bottom row shows procedures optimizing an expected runtime. Error regions show maximum and minimum observations.
optimize different metries and offer different guarantees. We compare COUP and OUP to Successive Halving @Jmmieson & Talwalkar 2016), Hyperband eLi al. 2018), AC-Band (Brandt et al, 2023), ImpatientCapsAndRRms (ICAR) (Weisz al. 2020) and Structured Procrastination with Confidence (SPC) (Kleinberg et al. 2019). We describe each of these procedures and their parameter settings in more detail in the appendices. Figure Si the percentage gap to best configuration for each procedure at various amounts of runtime. The top row shows utilitarian procedures optimized for the lag-Laplace utility function, while the bottom row shows procedures that optimize runtime. In the latter case, we optimized OUP and COUP on a uniform utility function, which is equivalent to optimizing capped runtime. For the minisat dataset we set Kig = 100 and for the CPLEX datasets we set Ko 3000. These values are similar to the per-configuration captimes used by ICAR and SPC, which both optimize an expected quantile-capped runtime. Figure 5 shows the results for quantile parameter of d .1. The results for 5 = .2 are essentially the same (see Appendix C To avoid an unfair comparison we report the performance of OUP and COUP with respect to this quantile-capped runtime metric. We observed that AC-Band performed poorly with log-Laplace utility functions, so we additionally report its performance gap with respect to its default metric. We plot the averages and regions over five seeds. OUP, COUP and SPC are anytime so they make recommendations throughout their execution, while the other procedures make point recommendations. Overall, COUP and OUP performed better than many runs of the other procedures and eventually narrowed in on the optimal configuration for every seed. Hyperband also worked well by this percentage-get gap metric in some settings on some seeds. For the RCW dataset it found good configuration more quickly than COUP but still left a gap to the best, whereas COUP and OUP continually improved. COUP and OUP avoided the "luck of the draw" that other non-anytime methods faced in the choice of their budget parameters; our investigation of varying parameterizations for these procedures shows that these hard-to-set parameters substantially impacted performance.
6 CONCLUSION
We have presented COUP, an improved method for utilitarian algorithm configuration. COUP shares the positive qualities of its predecessors, but is truly general purpose, in that it can search over infinite configuration spaces effectively. COUP is also shown to be superior when applied to finite configuration spaces. For the sake of continuity with previous work we have made comparisons on the datasets and utility functions that have been used before. However, this comparison is somewhat limited; a more comprehensive investigation would be a valuable direction for future work. Moreover, while we are convinced that optimizing utility functions is better than optimizing runtime, recognize that coming up with the right utility function is not always easy for end users; establishing tool or guide for doing this is another important future direction.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was funded by an NSERC Discovery Grant, a CIFAR Canada AT Research Chair (Alberta Machine Intelligence Institute), and computational resources provided both by UBC Advanced Research Computing and Digital Research Alliance of Canada RAC Allocation.
REFERENCES
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Lehrning foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pp. 213-274, 2017.
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design. In Symposium on Theory of Computing, pp. 919-932, 2021.
Jasmin Brandt, Elias Schede, Bjöm Haddenhorst, Viktor Bengs, Eyke Hüllermeier, and Kevin Tierney, AC-Band: a combinatorial bandit-based approach algorithm configuration. In AAAI Conference on Artificial Intelligence, pp. 12355-12363, 2023.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi-armed bandit and markov decision processes. In Conference on Computational Learning Theory, pp. 255-270. Springer, 2002.
Devon R Graham, Kevin Leyton-Brown and Tim Roughgarden. Formalizing preferences runtime distributions. In International Conference on Machine Learning, pp. 11659-11688 1162,, 2023a.
Devon R Graham, Kevin Leyton-Browe and Tim Roughgarden. Utilitarian algorithm configuration. In Neural Information Processing Systems, pp. 11659-11688 11622, 2023b.
Rishi Gupta and Tim Roughgarden. PAC approach to application-sper speciffc algorithm selection.
SIAM Journal on Computing, 46(3):992-1017, 2017.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. ISSN 01621459.
Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for the fixed confidence setting. In Conference Information Sciences and Systems, pp. 1-6. IEEE, 2014.
bandits in
Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Artificial intelligence and statistics, pp. 240-248. PMLR, 2016.
Robert Kleinberg, Kevin Leyton-Broot Brown, and Brendan Lucier. Efficiency through procrastination: Approximately optimal algorithm configuration with runtime guarantees. In International Joint Conference on Artificial Intelligence, pp. 2023-2031, 2017.
Robert Kleinberg, Kevin Leyton- Brown, Brendan Lucier, and Devon Graham. Procrastinating with confidence: Near-optimal, anytime, adaptive algorithm configuration. In Neural Information Processing Systems, pp. 8881-8891, 2019.
Tze Leung Lai. Adaptive treatment allocation and the multi-armed bandit problem. The Annals of Statistics, pp. 1091-1114, 1987.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(15)):1-22, 2018.
Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal Machine Learning Research, (JJu)):6336645 2004.

---

Published as a conference paper at ICLR 2025
John Von Neumann and Oskar Morgenstemn. Theory of games and economic behavior. Princeton university press, 2nd edition, 1947.
Gellért Weisz, Andras Gyorgy, and Csaba Szepesvári. LeapsAndBounds: a method for approximately optimal algorithm configuration. In International Conference on Machine Learning, pp. 5257-5265, 2018.
Gellért Weisz, Andras Gyorgy, and Csaba Szepesvári. CapsAndRuns: an improved method for approximately optimal algorithm configuration. In International Conference on Machine Learning. pp. 6707-6715, 2019.
Gellért Weisz, András György, Wei-I Lin, Devon Graham, Kevin Leyton-Brown, Csaba Szepesvari, and Brendan Lucier. ImpatientCapsAndRRum approximately optimal algorithm configuration from infinite pool. In Neural Information Processing Systems, pp. 1 17478-1 17488, 2020.
12


Reviews:
[{"review_id": "2nrVQ9J0eD", "reviewer": "Reviewer_rWFx", "summary": "This paper studies utilitarian algorithm configuration, which is about automatically searching the parameter space of a given algorithm to optimise for its performance.\n\nThe first proposed algorithm is OUP.  It is a UCB style algorithm for finding configurations with good capped mean utility, with the addition of a scheme for periodically doubling the cap time.\n\nThe main algorithm is COUP. It builds on a new notion of optimisation goal called (epsilon, gamma) optimal. Epsilon is about being close to optimality and gamma controls how many configurations to sample. For fixed epsilon and gamma, the inner algorithm is for the most part just OUP. The novelty of the proposed algorithm is that it allows the sharing of trials over different epsilon and gamma.", "questions": "What is delta in OUP? I don't see it being referenced in the description of OUP. Is it only used in one of the subroutines?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed method is general and there are extensive experiments demonstrating its performance.", "weaknesses": "The presentation of this paper is very hard to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QGLyD9Fvbd", "reviewer": "Reviewer_Fgpz", "summary": "An approach for algorithm configuration is presented based on a maximizing the utility of the target algorithm. The approach follows a line of work on \"utilitarian procrastination (UP)\", extending the previous work to function in continuous (infinite) spaces. An interesting aspect of the work is that this extension does not come at the cost of hurting performance on the finite-space case, in fact the performance improves. The resulting method, COUP, has bounds proven indicating essentially how good the configurations it finds are.", "questions": "1. See issues with experiments above.\n2. On line 6 of algorithm 2, COUP samples new configurations at random, which is basically how all of the theoretical approaches to AC work. Is there no way of sampling configurations that might actually be good while maintaining guarantees? It feels like these approaches are all poking around in the dark rather than actually optimizing. (future work, I suppose)", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper moves the theoretical results for algorithm configuration in a very important direction, namely one step closer to real-world settings.\n2. The paper is generally understandable at various levels of detail -- one need not delve into the math to understand the what and why of the paper. The math is clean and well-written, but I note that I could not completely evaluate all of the proofs.\n3. The experimental results are quite good, especially in an area where the gains have been mostly small or just on different areas of the Pareto front of time vs quality. This approach is very competitive.", "weaknesses": "1. There are a few minor clarity issues:\n\t1. The start of the paper is a bit of a slog. It would have been nice to get to the point faster.\n\t2. I do not understand why the notation for Algorithm 1 is introduced after the algorithm is explained. I needed the notation before reading the explanation, so I ended up just being confused until I found the notation, then had to go back and read it again. \n\t3. In Algorithm 1, i is shadowed on line 7. Very minor, but it just seems weird (the same goes for Alg. 2).\n2. I found the visuals in the experiments sometimes hard to read, and was confused by some aspects.\n\t1. Particularly the brown/purple/green combination has very similar shadings on some monitors/printers, another color scheme might be better. \n\t2. In Figure 3, the green line for OUP goes backwards between total time 10^0 and 10^1. Something must be wrong there.\n\t3. The symbols in Figure 5 do not match the legend, and in all honesty I can barely figure out what is going on here. The figures are just too small with too many points crowded in the same spots. \n\nOverall, I have found no major issues with the paper, but I acknowledge that I am not an expert in the math of this paper and could have overlooked something. I am also not convinced of the superiority of the utilitarian approach of AC versus runtime configuration. However, the authors identify valid limitations and I find the use of utilitarian AC plausible for certain users, thus I do not view my disagreement on this point as something to hold against this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bn38vQSZ2h", "reviewer": "Reviewer_67Uh", "summary": "The paper considers the problem of algorithm configuration. There are two key elements that are not handled in combination by previous approaches: (1) infinite (potentially continuous) parameter spaces, and (2) utilitarian reward (which is a function of the running time).\n\nA new algorithm is proposed, COUP, which is based on UCB, using doubling trick for extending cap on the running time, and sampling increasing numbers of arms to deal with the infinite arm's space. A simplified version for finite number of arms, OUP, is also considered. The algorithms are shown to achieve close to optimal configuration. \n\nThe proposed algorithm is compared to another utilitarian algorithm UP, achieving faster convergence for the finite case. The COUP algorithm  seems to perform well empirically for the many configurations case as well.", "questions": "The questions for me are centered around the relation with metric space bandits, and the use of additional baselines.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem considered is important, and the proposed algorithms are sound.\n\nThe theoretical guarantees are valuable.\n\nThe paper is well written.", "weaknesses": "The infinite parametric space problem seems related to me to the bandit problems in continuous/metric spaces. For those problems, the performance of the bandit algorithm is compared to the optimal solution, which is facilitated by Lipschitz or stronger conditions on the reward function. In this work only the top percentile is considered (which is simpler with sampling), but I assume similar conditions on the utility could be considered here as well.\n\nThe experiments use a very limited set of baselines (UP). I think, it would have reasonable to test the algorithm against algorithms that minimize the running time (with the utility coinciding with the running time, or just using the running time as surrogate measure for those algorithms). Testing non-bandit based algorithm configuration approaches would also make sense.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5wX2RMq3hI", "reviewer": "Reviewer_1WyU", "summary": "The paper introduces COUP (Continuous, Optimistic Utilitarian Procrastination) procedure, which explores the parameter space - possibly uncountably infinite - of a given algorithm to optimize its performance on a specified set of inputs, with performance measured through a utility function. The finite (parameter space) verison of the procedure, known as OUP, improves upon the UP (Graham et al., 2023b) by incorporating ideas from the UCB algorithm in bandit literature. Additionally, COUP generalizes the procedure to possibly uncountably infinite parameter space. While doing so, COUP retains the theoretical guarantees of the UP algorithm while being significantly faster, as demonstrated by both theoretical guarantees and empirical results.", "questions": "1) Anonymous repo link seems to be missing?\n\n2) In Figure 1 - second row - third graph - there is a sudden drop in the total runtime (for OUP) around $\\epsilon \\approx 0.19$. Is this due to some specific structure of the problem/algorithm being analyzed?\n\n3) The authors mention that Hyperband also performs well in the percentage-gap metric, but from Figure 5, it’s unclear to me that COUP/OUP actually outperforms it. Is there a reason to expect COUP/OUP would perform better, or is there something I might be overlooking?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1) The finite version (OUP) procedure improves over the previous (UP) procedure using ideas from UCB algorithm in bandit literature.\n\n2) Extensions to the infinite parameter space algorithms.\n\n3) Maintaining the theoretical guarantees provided by the UP procedure.", "weaknesses": "1) The presentation of Section 3 could be improved slightly; introducing the notation before presenting Algorithm 1 might enhance readability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "asabF0xBCM", "reviewer": "Reviewer_rtTp", "summary": "The authors introduced a new procedure, COUP, which claims that 1) it can run on continuous space and 2) it is faster than UP in the case of discrete space. Later experiments confirmed their claims.", "questions": "na", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper appears organized and well-written. The authors effectively emphasized the big picture in Sections 1 and 2, providing a clear understanding of this new and improved algorithm.\n\nThe algorithm is general enough to be applied to many optimization problems. It includes theoretical properties; however, we did not check the appendix for the validity of the proof.", "weaknesses": "na", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8CDQjMbJRf", "reviewer": "Reviewer_a4rf", "summary": "The authors study the problem of utilitarian algorithm configuration with inifinite number of parameters.\nThe key idea is i) to adopt the UCB (upper confidence bound) method rather than the SE (sequential elimination) method in balancing exploration and confirmation of the best parameter to reach the same guarantee with shorter run time, and ii) to relax the reference point of the guarantee from the best to quantiles.", "questions": "Can you address the points I raised in Weakness?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- It is well-motivated, well-executed and well-written.\n- The theoretical analysis looks intuitive and right.", "weaknesses": "- The impact of the extension to continuous space is unclear. I would suggest to compare COUP with OUP + fixed discretization of continuous space.\n- The continuous structure (similarities among neighbor parameters) is not utilized in COUP. So, C in COUP does not describe its nature accurately.  \n\nMinor:\n- In Lemma 2, don’t you need “with probability 1- \\delta”?\n- Why not using log scale for the vertical axes of Figure 1?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)