acceptodds
Under review as a conference paper at ICLR 2027

Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm

Abstract

We study contextual queueing bandits, where a learner schedules jobs while learning unknown service rates modeled by logistic functions of job-server features. Performance is measured by queue length regret, the expected excess queue length at round relative to an oracle that knows the service rates. Existing decaying-regret guarantees either have a suboptimal decay rate or require a known fixed horizon. They also assume context-wise slack and a strictly positive minimum eigenvalue of the feature covariance. In this paper, we propose WISE (Widest Interval Selection with Elimination), achieving rate-optimal queue length regret at every sufficiently large time without knowing the horizon. We assume capacity slack, meaning that expected incoming workload under best-server service is below service capacity, and impose no covariance lower bound. Our analysis uses a workload potential measuring the expected service attempts needed by waiting jobs on their best servers. Its drift on nonempty rounds combines a negative term ensured by capacity slack with errors from suboptimal service choices. Then an elliptical potential count bounds how often WISE selects wide confidence intervals, thereby limiting the number of rounds with large service errors. We also sharpen the arrival-rate dependence of an existing lower bound and make its dependence on feature dimension and server count explicit. We prove another lower bound that quantifies the increase in regret as the normalized capacity slack decreases; to our knowledge, this is the first such lower bound for CQB. Simulations show small regret even when context-wise slack fails.

Primary area:
reinforcement learning
Keywords:
scheduling, routing, queueing bandits, contextual bandits, logistic bandits

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_wnq3OpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies a contextual-bandit-based problem in queueing theory. The model is a queue with Bernoulli arrivals and service probabilities that depend on the job's context and the chosen machine through the logistic function. Under a standard stability condition, the authors give an horizon-free algorithm that is minimax optimal up to log-factors, with expected queue-length regret O~(λ/t)\tilde O(\sqrt{\lambda/t}) for all sufficiently large tt. Experiments compare the algorithm to prior work baselines.

Critical strengths
  1. The paper solves an interesting problem at the intersection of online scheduling and online learning: optimal context-dependent scheduling. While the main result is stated in discrete time, it is not hard to imagine an extension to continuous time (e.g., M/M/1 queues with KK modes for each job).
  2. The assumptions used to derive the O(λ/t)O(\sqrt{\lambda/t}) rate are reasonable and a significant improvement over prior work. In particular, the stability condition (Assumption 2) is standard: it essentially requires that the arrival rate be strictly less than the maximal service rate, so that the queue does not have to blow up.
Critical weaknesses

No critical weaknesses to report. Please address minor weaknesses in the questions below.

Questions for authors
  1. Could you strengthen the paper's positioning within online scheduling/learning theory? In particular, [1, 2, 3] seem relevant to the considered scheduling setup. Moreover, the intersection of online learning and scheduling was previously studied in [4] for multi-armed bandits, with a focus on minimizing learning regret while scheduling.
  2. It is a bit misleading to present the problem as having KK servers, which suggests that multiple jobs can be processed in parallel. In this paper, only one job-server pair can be processed per round. A more accurate interpretation is therefore a single server with KK modes of operation.
  3. In Lemma 5, you show that the queue is empty sufficiently often, which effectively controls each job's sojourn time. I think it is very important that no job stays queued indefinitely. Could you derive or conjecture a high-probability upper bound on the maximum number of rounds any job spends in the queue (its sojourn time)?
  4. In Theorem 1, you provide the O~(min⁡(λ,βtλd/t))\tilde O(\min(\lambda, \beta_t\sqrt{\lambda d/t})) upper bound, which holds for sufficiently large tt. However, the second term in the minimum eventually drops below λ\lambda, so the minimum is attained by the second term for all sufficiently large tt. Why keep the first term here?

[1] D. G. Kendall (1953). Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain.

[2] R. M. Loynes (1962). The stability of a queue with non-independent inter-arrival and service times.

[3] Tassiulas and Ephremides (1992). Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks.

[4] A. Ryabchenko, I. Attias, and D. M. Roy (2025). Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs. COLT.

4 comments

[Q1] Could you strengthen the paper's positioning within online scheduling/learning theory? In particular, [1, 2, 3] seem relevant to the considered scheduling setup. Moreover, the intersection of online learning and scheduling was previously studied in [4] for multi-armed bandits, with a focus on minimizing learning regret while scheduling.

We thank the reviewer for pointing out these connections and helping us broaden our perspective on the related literature. We have added comparisons with [1-4] in Appendix A.

  • Queueing theory and stability [1-3]. Kendall [1] analyzes queue-length and waiting-time distributions under given arrival and service models. Loynes [2] shows that a single-server queue is stable under the load condition ρ=λE[B]<1\rho=\lambda\mathbb E[B] < 1, where BB is the time needed to serve one job. Tassiulas and Ephremides [3] consider queueing networks in which only certain servers can operate at the same time. They construct a policy that stabilizes the network whenever the arrival-rate vector lies strictly inside the capacity region.

  • Relation to our work. Our capacity slack assumption is the counterpart of these stability conditions. Under best-server service, a job with context XX needs E[B∣X]=1/p∗(X)\mathbb E[B\mid X]=1/p^{\ast}(X) rounds in expectation, so Loynes' load condition becomes λE[1/p∗(X)]<1\lambda\mathbb E[1/p^{\ast}(X)] < 1, which is Assumption 2. The works in [1-3] do not involve learning unknown service rates. In our setting, the service probabilities must be learned from service outcomes, and we bound Rt=E[Qπ(t)−Q∗(t)]R_t=\mathbb E[Q^\pi(t)-Q^{\ast}(t)], the expected excess queue length relative to an oracle that knows the service rates.

  • Ryabchenko et al. [4]. They study bandits with delayed feedback in which only a limited number of past rounds can be tracked until their feedback arrives. They characterize how this limit and the delays affect cumulative loss regret. Both works combine online learning with scheduling, but the settings and objectives differ. Our scheduler selects a waiting job and a server and observes success or failure immediately after the attempt. We bound the expected excess queue length at each round, instead of cumulative loss regret.

[Q2] It is a bit misleading to present the problem as having KK servers, which suggests that multiple jobs can be processed in parallel. In this paper, only one job-server pair can be processed per round. A more accurate interpretation is therefore a single server with KK modes of operation.

We thank the reviewer for pointing this out and have added a statement in Section 2.1 that only one job-server pair is served per round, corresponding to a single server with KK modes of operation.

[Q3] In Lemma 5, you show that the queue is empty sufficiently often, which effectively controls each job's sojourn time. I think it is very important that no job stays queued indefinitely. Could you derive or conjecture a high-probability upper bound on the maximum number of rounds any job spends in the queue (its sojourn time)?

The reviewer's intuition about jobs' sojourn times is correct. A high-probability bound on the maximum sojourn time follows as a corollary of our existing Lemma 5. We have added this result as Corollary 1 in Appendix F.2.

  • Using Lemma 5, we show that the maximum sojourn time Smax⁡(T)S_{\max}(T) among all jobs that enter the queue in rounds 1,…,T1,\ldots,T satisfies, with probability at least 1−δ1-\delta, Smax⁡(T)≲κ2d2ϵ3p‾3log⁡2!(Tκdϵp‾δ)+1ϵ2p‾2δ.S_{\max}(T)\lesssim\frac{\kappa^2d^2}{\epsilon^3\underline p^3}\log^2\\!\left(\frac{T\kappa d}{\epsilon\underline p\delta}\right)+\frac{1}{\epsilon^2\underline p^2\delta}.

  • Consider a job arriving in round a≤Ta\le T that remains for more than LL rounds. With t=a+Lt=a+L, Lemma 5(i) gives P!(a job arrives in round a and remains for more than L rounds)≤P!(Q(i)>0 for all i∈[t−ℓ0,t,t])≲1ϵ2p‾2t2,\begin{aligned}&\mathbb P\\!\left(\text{a job arrives in round }a\text{ and remains for more than }L\text{ rounds}\right)\\\\&\quad\le\mathbb P\\!\left(Q(i) > 0\text{ for all }i\in[t-\ell_{0,t},t]\right)\lesssim\frac{1}{\epsilon^2\underline p^2t^2},\end{aligned} where the first inequality holds for L>ℓ0,T+LL > \ell_{0,T+L}. Next, if Smax⁡(T)>LS_{\max}(T) > L, at least one job that entered in rounds 1,…,T1,\ldots,T remained for more than LL rounds. A union bound over these arrival rounds gives P(Smax⁡(T)>L)≲1ϵ2p‾2∑a=1T1(a+L)2≲1ϵ2p‾2L.\mathbb P(S_{\max}(T) > L)\lesssim\frac{1}{\epsilon^2\underline p^2}\sum_{a=1}^{T}\frac{1}{(a+L)^2}\lesssim\frac{1}{\epsilon^2\underline p^2L}. Choosing LL such that L≳κ2d2(ϵp‾)3log⁡2(T+L)+1ϵ2p‾2δL\gtrsim\frac{\kappa^2d^2}{(\epsilon\underline p)^3}\log^2(T+L)+\frac{1}{\epsilon^2\underline p^2\delta} ensures that L>ℓ0,T+LL > \ell_{0,T+L} and makes this probability at most δ\delta, giving the result in the first bullet.

[Q4] In Theorem 1, you provide the O~(min⁡(λ,βtλd/t))\widetilde O(\min(\lambda,\beta_t\sqrt{\lambda d/t})) upper bound, which holds for sufficiently large tt. However, the second term in the minimum eventually drops below λ\lambda, so the minimum is attained by the second term for all sufficiently large tt. Why keep the first term here?

We thank the reviewer for pointing this out and have removed the λ\lambda term from the minimum in revised Theorem 1 in Section 5.1.

References

[1] Kendall, "Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain", Ann. Math. Statist., 1953.

[2] Loynes, "The stability of a queue with non-independent inter-arrival and service times", Math. Proc. Cambridge Philos. Soc., 1962.

[3] Tassiulas and Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks", IEEE Trans. Autom. Control, 1992.

[4] Ryabchenko et al., "Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs", COLT, 2025.

Thank you for the detailed response. I maintain my positive score.

Dear Reviewer wnq3,

We thank you again for your valuable comments and positive evaluation of our work!

Thanks, Authors

Reviewer_oi7pOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies contextual queueing bandits while minimizing the queue length regret. The authors propose algorithm name WISE, which does not require the horizon length and achieves O(t^{-1/2}) queue-length regret. Compared with prior work, the analysis requires weaker capacity-slack condition and also removes the feature covariance diversity assumption. The paper also provides lower bounds characterizing the dependence on arrival rate, feature dimension, and capacity slack.

Critical strengths
  1. Strong theoretical results under weaker assumptions. This paper achieves the optimal queue-length regret of order O(t^{-1/2}) without knowing the time horizon. More importantly, it removes two strong assumptions (context-wise slack and covariance lower bound) use in prior work. The writing is easy to follow and this technical contribution makes results more general and useful.

  2. Interesting technical ideas and solid analysis. The paper introduces a workload-based potential function and combines it with elliptical potential counting to control learning errors. These techniques address important challenges in queueing bandits. The paper also provides new lower bounds, making the theoretical results much more complete.

Critical weaknesses
  1. Limited finite-time guarantees. The main regret bound only holds after a sufficiently large time t0t_0, which may depend exponentially on the capacity slack. This makes it unclear how well the theoretical guarantee applies in practical settings, especially when the system is close to its capacity limit.
  2. The experiments only use synthetic data with relatively small problem sizes and ten runs, and the experiments use a fixed confidence radius instead of the theoretical one. However, since this paper mainly focuses on the theory contribution, I think this weakness is minor.
Questions for authors
  1. Finite-time guarantees and capacity slack.

The main regret bound only holds after a sufficiently large time t0t_0, which may depend exponentially on the capacity slack ϵ\epsilon. Can the authors provide a more explicit finite-time bound showing the dependence on ϵ\epsilon? How useful is the current regret bound when ϵ\epsilon is small?

  1. Experimental settings and theoretical consistency.

The experiments use a fixed confidence radius β=100\beta=100 and feature norms that differ from the theoretical assumptions. Can the authors explain these choices and clarify whether the theoretical version of WISE achieves similar performance? How sensitive are the results to the choice of β\beta?

2 comments

[W1] Limited finite-time guarantees. The main regret bound only holds after a sufficiently large time t0t_0, which may depend exponentially on the capacity slack. This makes it unclear how well the theoretical guarantee applies in practical settings, especially when the system is close to its capacity limit.

[Q1] Finite-time guarantees and capacity slack. The main regret bound only holds after a sufficiently large time t0t_0, which may depend exponentially on the capacity slack ϵ\epsilon. Can the authors provide a more explicit finite-time bound showing the dependence on ϵ\epsilon? How useful is the current regret bound when ϵ\epsilon is small?

We thank the reviewer for asking for explicit finite-time guarantees. We have revised the submitted proof to clarify that the exponential condition on t0t_0 is not required. We also added explicit regret bounds before and after t0t_0.

  • As added in equation (83) in Appendix F.1 of the revised manuscript, we choose t0≥3t_0\ge3 as the first integer satisfying t0≳κ14d14λϵ19p‾20log⁡13t0.t_0\gtrsim\frac{\kappa^{14}d^{14}}{\lambda\epsilon^{19}\underline p^{20}}\log^{13}t_0. Thus, t0t_0 depends polynomially on ϵ−1\epsilon^{-1} and p‾−1\underline p^{-1}, up to logarithmic factors. The revised proof is in Appendices B.4 and B.6.

  • To make the transient explicit, for 3≤t<t03\le t < t_0 we have Rt≲κ14d14ϵ19p‾20log⁡13t.R_t\lesssim\frac{\kappa^{14}d^{14}}{\epsilon^{19}\underline p^{20}}\log^{13}t. For t≥t0t\ge t_0, the regret bound in revised Theorem 1 becomes Rt≲κdϵ9/2p‾4log⁡5/2tt.R_t\lesssim\frac{\kappa d}{\epsilon^{9/2}\underline p^4}\frac{\log^{5/2}t}{\sqrt t}. Both bounds are added as equation (84) in Appendix F.1.

[W2] The experiments only use synthetic data with relatively small problem sizes and ten runs, and the experiments use a fixed confidence radius instead of the theoretical one. However, since this paper mainly focuses on the theory contribution, I think this weakness is minor.

[Q2] Experimental settings and theoretical consistency. The experiments use a fixed confidence radius β=100\beta=100 and feature norms that differ from the theoretical assumptions. Can the authors explain these choices and clarify whether the theoretical version of WISE achieves similar performance? How sensitive are the results to the choice of β\beta?

We agree that experiments with larger problem sizes, a comparison of the theoretical and practical versions, and a sensitivity analysis for β\beta are needed. We have added (i) separate sweeps over dd and KK (Appendices H.2 and H.3), (ii) a theoretical and practical comparison (Appendix H.5), and (iii) experiments with different β\beta values (Appendix H.4).

  • For problem size, we vary dd and KK separately over 5,10,20,50\\{5,10,20,50\\}. We also compare the practical and theoretical versions of WISE using the same feature norm 55 and S=10S=10, with the theoretical confidence radius adjusted for this norm (Appendix H.5). Practical WISE with β=100\beta=100 has lower mean regret in all three distributions.

  • For sensitivity to β\beta, we vary β∈0.1,1,10,100,1000\beta\in\\{0.1,1,10,100,1000\\} for all five contextual algorithms (Appendix H.4). Our original β=100\beta=100 and feature norm 55 were practical choices. Fixed confidence coefficients are also used in empirical bandit studies, including Li et al. (2010) [1] and Chapelle and Li (2011) [2]. The table below compares the fixed coefficients and the theoretical radius for WISE.

Algorithmβ\betaq=0q=0q=0.15q=0.15q=0.50q=0.50
WISE0.10.132.162±47.75232.162 \pm 47.75223.771±32.82423.771 \pm 32.82419.665±28.358‾\underline{19.665 \pm 28.358}
WISE118.935±19.611\mathbf{8.935 \pm 19.611}6.495±8.324\mathbf{6.495 \pm 8.324}6.361±13.033\mathbf{6.361 \pm 13.033}
WISE101020.089±18.505‾\underline{20.089 \pm 18.505}20.931±22.279‾\underline{20.931 \pm 22.279}21.900±20.49221.900 \pm 20.492
WISE100100172.608±36.393172.608 \pm 36.393182.066±33.089182.066 \pm 33.089217.544±39.546217.544 \pm 39.546
WISE10001000497.014±29.596497.014 \pm 29.596496.638±29.667496.638 \pm 29.667497.142±29.966497.142 \pm 29.966
WISE (theory)βt\beta_t496.511±30.214496.511 \pm 30.214496.376±29.960496.376 \pm 29.960496.620±30.029496.620 \pm 30.029
  • We acknowledge that WISE is sensitive to β\beta. Nevertheless, WISE performs competitively with the baselines in most tested settings with our default β=100\beta=100, achieving the smallest or second-smallest mean regret in all three distributions and at every tested dd and KK (Figure 6 and Appendices H.2 and H.3).

References

[1] Li et al., "A Contextual-Bandit Approach to Personalized News Article Recommendation", WWW, 2010.

[2] Chapelle and Li, "An Empirical Evaluation of Thompson Sampling", NeurIPS, 2011.

Dear Reviewer oi7p,

Thank you for your careful review. We have addressed each of your comments and questions in our rebuttal and would be grateful if you could take a look when you have a chance.

Thanks, Authors

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

The paper considers a queue of arriving jobs with contextual features and unknown logistic service probabilities. At each round, the learner chooses one waiting job and one server, observes whether service succeeds (if not the job is put back in the queue), and updates its estimates. The objective is the expected excess queue length relative to an oracle that knows the service probabilities. The goal is to minimize this regret.

The operational chain of WISE is as follows: i) estimate the service model using regularized logistic regression; ii) construct confidence intervals and intersect them within the current epoch; iii) retain job–server pairs whose upper bounds exceed the largest lower bound among available pairs; iv) serve the surviving pair with the widest interval and update the estimates; v) restart the intersections at randomly shifted geometric epoch boundaries while retaining the observations.

To my understanding, the authors establish an eventual \widetilde O(t^{-1/2}) regret guarantee under a natural capacity condition, without a covariance lower bound, and derive lower bounds involving arrival rate, dimension, server count, and capacity slack. Experiments compare eight methods across nine synthetic settings.

Critical strengths

i) Meaningful relaxation of existing contextual queueing assumptions. The result combines a horizon-independent algorithm, the optimal time-decay exponent, and weaker assumptions on traffic and feature covariance. To my understanding, earlier rate-optimal CQB results require a known horizon and stronger conditions. The distinction between context-wise slack and aggregate workload slack is thus meaningful: a stable system can contain difficult jobs whose individual service probabilities are below the arrival rate. The removal of the covariance lower bound also allows to accommodate redundant features and distributions supported on lower-dimensional subspaces.

ii) A substantive analysis of the interaction between learning and queue dynamics. The waiting jobs depend on previous scheduling decisions and departures, so standard arguments based on fresh independent action sets cannot simply be transferred. The combination of workload drift, uncertainty counts, and observations following empty rounds seem to address this difficulty.

Critical weaknesses

i) The finite-time significance of the main guarantee remains open/unclear. To my knowledge the optimal decay rate holds only after a threshold t_0 that may depend exponentially on congestion-related parameters. This leaves open whether the improvement becomes informative on relevant timescales, especially near capacity. The result is theoretically meaningful, but a more explicit characterization of the transient is needed to establish the significance of the claimed improvement.

ii) The experiments do not adequately establish the source or robustness of the reported gains. There are no ablations isolating the effects of interval intersections, maximum-uncertainty selection, or epoch resets. Baseline calibration also raises concerns: the prescribed exploration schedule keeps Q-UCB and Q-ThS in pure exploration through round 1,645 of a 2,000-round experiment, while contextual methods use different initial regularization without sufficient justification. This does not invalidate every comparison, but the limited coverage—ten runs per setting with fixed dimension and server count—does not resolve these concerns. Consequently, the experiments provide insufficient evidence that the proposed algorithmic choices deliver a reliable practical advantage.

Questions for authors
  1. Can you make the finite-time dependence on capacity slack and minimum service probability explicit, and clarify whether the potentially exponential threshold is an artifact of the analysis?

  2. Do the empirical gains persist with documented baseline tuning and component ablations, particularly when Q-UCB and Q-ThS are evaluated beyond their forced-exploration period?

2 comments

[W1] The finite-time significance of the main guarantee remains open/unclear. To my knowledge the optimal decay rate holds only after a threshold t0t_0 that may depend exponentially on congestion-related parameters. This leaves open whether the improvement becomes informative on relevant timescales, especially near capacity. The result is theoretically meaningful, but a more explicit characterization of the transient is needed to establish the significance of the claimed improvement.

[Q1] Can you make the finite-time dependence on capacity slack and minimum service probability explicit, and clarify whether the potentially exponential threshold is an artifact of the analysis?

We thank the reviewer for asking for explicit finite-time guarantees. We have revised the submitted proof to clarify that the exponential condition on t0t_0 is not required. We also added explicit regret bounds before and after t0t_0.

  • As added in equation (83) in Appendix F.1 of the revised manuscript, we choose t0≥3t_0\ge3 as the first integer satisfying t0≳κ14d14λϵ19p‾20log⁡13t0.t_0\gtrsim\frac{\kappa^{14}d^{14}}{\lambda\epsilon^{19}\underline p^{20}}\log^{13}t_0. Thus, t0t_0 depends polynomially on ϵ−1\epsilon^{-1} and p‾−1\underline p^{-1}, up to logarithmic factors. The revised proof is in Appendices B.4 and B.6.

  • To make the transient explicit, for 3≤t<t03\le t < t_0 we have Rt≲κ14d14ϵ19p‾20log⁡13t.R_t\lesssim\frac{\kappa^{14}d^{14}}{\epsilon^{19}\underline p^{20}}\log^{13}t. For t≥t0t\ge t_0, the regret bound in revised Theorem 1 becomes Rt≲κdϵ9/2p‾4log⁡5/2tt.R_t\lesssim\frac{\kappa d}{\epsilon^{9/2}\underline p^4}\frac{\log^{5/2}t}{\sqrt t}. Both bounds are added as equation (84) in Appendix F.1.

[W2] The experiments do not adequately establish the source or robustness of the reported gains. There are no ablations isolating the effects of interval intersections, maximum-uncertainty selection, or epoch resets. Baseline calibration also raises concerns: the prescribed exploration schedule keeps Q-UCB and Q-ThS in pure exploration through round 1,645 of a 2,000-round experiment, while contextual methods use different initial regularization without sufficient justification. This does not invalidate every comparison, but the limited coverage—ten runs per setting with fixed dimension and server count—does not resolve these concerns. Consequently, the experiments provide insufficient evidence that the proposed algorithmic choices deliver a reliable practical advantage.

[Q2] Do the empirical gains persist with documented baseline tuning and component ablations, particularly when Q-UCB and Q-ThS are evaluated beyond their forced-exploration period?

We agree that the submitted experiments did not sufficiently isolate the algorithmic components or examine the baseline settings. We have added (i) ablations of WISE's components (Appendix H.1), (ii) comparisons with different exploration coefficients for Q-UCB and Q-ThS (Appendix H.6), and (iii) separate sweeps over dd and KK (Appendices H.2 and H.3).

  • For example, the table below reports mean queue length regret for the β=1\beta=1 ablations (Figure 3 in Appendix H.1).
Algorithmq=0q=0q=0.15q=0.15q=0.50q=0.50
WISE8.935±19.611‾\underline{8.935 \pm 19.611}6.495±8.324‾\underline{6.495 \pm 8.324}6.361±13.033‾\underline{6.361 \pm 13.033}
Latest interval3.151±5.303\mathbf{3.151 \pm 5.303}2.878±3.353\mathbf{2.878 \pm 3.353}2.089±2.954\mathbf{2.089 \pm 2.954}
UCB selection13.217±21.50013.217 \pm 21.50011.715±25.45711.715 \pm 25.45711.765±18.17911.765 \pm 18.179
Greedy selection15.830±25.79615.830 \pm 25.79610.030±15.45410.030 \pm 15.45415.012±33.92215.012 \pm 33.922
No epoch resets487.260±41.199487.260 \pm 41.199488.039±40.348488.039 \pm 40.348483.219±39.547483.219 \pm 39.547
  • With β=1\beta=1, WISE has lower mean regret than UCB and Greedy selection, and removing epoch resets increases regret. Using the latest interval gives the lowest mean regret in all three distributions.

  • For the β=100\beta=100 ablations, UCB and Greedy selection have lower mean regret than WISE, while removing intersections or epoch resets changes mean regret by less than 33 (Figure 2 in Appendix H.1). Thus, the effects of these components depend on β\beta.

  • For Q-UCB and Q-ThS, we compare exploration coefficients c∈0.1,1,2,3c\in\\{0.1,1,2,3\\}, including the original c=3c=3 (Appendix H.6). Exploration has probability one for 00\\%, 16.9516.95\\%, 46.8046.80\\%, and 82.2582.25\\% of the 20002000 rounds, respectively. WISE with β=100\beta=100 has lower mean regret than both baselines at every tested coefficient in all three distributions.

  • For problem size, we vary dd and KK separately over 5,10,20,50\\{5,10,20,50\\} using 2020 runs per setting (Appendices H.2 and H.3). WISE has the smallest or second-smallest mean regret at every tested dd. At every tested KK, WISE has the smallest mean regret for q=0q=0 and 0.150.15, while ACQB has the smallest for q=0.50q=0.50.

Dear Reviewer 4iqX,

Thank you for your careful review. We have addressed each of your comments and questions in our rebuttal and would be grateful if you could take a look when you have a chance.

Thanks, Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.