acceptodds
Under review as a conference paper at ICLR 2027

EX-ANTE ADMISSION WITH STOCHASTIC PRIORITY COMPETITION: LEARNING WHAT MATTERS

Abstract

We study an online ex-ante admission problem in which multiple devices compete for a unit-capacity resource through an unknown priority order and stochastic gating mechanism. At each round, the controller observes demand probabilities and selects an admission set before the actual demands are realized. The active admitted devices then compete according to the latent priority order, while the served device generates a stochastic reward with an unknown mean. This setting creates a coupled learning problem: the controller must simultaneously learn reward parameters and acquire priority information from noisy and randomly occurring competition events. We first characterize the full-information admission oracle through a dynamic program and develop an Exact-Priority Two-Phase algorithm based on a sequential noisy priority comparator. We then show that exact recovery of the entire priority order can lead to substantial over-exploration, since many pairwise ordering errors have only limited influence on the admission value. Motivated by a sensitivity analysis of priority misordering, we propose Relevance-Aware Priority-Upper Confidence Bound (UCB), which probes unresolved priority relations only when their potential decision impact remains significant. We establish regret guarantees that capture both statistical informativeness and decision relevance, and derive a complementary decision-theoretic lower bound. Experiments confirm that the proposed strategy substantially reduces unnecessary priority exploration, particularly in regimes with nearly homogeneous rewards, low effective service probabilities, or rare contextual overlap.

Primary area:
learning theory
Keywords:
Multi-armed bandits, Priority competition, Ex-Ante admission

Reviews

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

The paper studies online admission control where devices compete for a shared resource through an unknown priority ranking, and rewards are unknown. Its main insight is that only the decision-relevant parts of the ranking need to be learned. The authors propose a relevance-aware algorithm (RA) that probes a pair only when its ordering could meaningfully change the decision. They provide regret upper bounds, favorable regimes, and a lower bound.

Critical strengths
  • The paper has a formulation based on a real-world motivating example. It models different aspects of the problem in a justified way.
  • The authors are upfront about stating that their one-round mechanism follows the random consideration set model. They explicitly position their contribution about the learning problem.
  • The paper builds up to its main result step by step. It starts from the oracle and a full-ranking baseline. Then, their sensitivity analysis shows how ordering errors affect the decisions, which motivates the relevance-aware algorithm. This structure makes the paper easy to follow and grounds the main idea.
  • The core idea of the paper is that they need to learn the ranking only among decision-relevant pairs. This idea is very intuitive and clearly explained.
  • A naive baseline sorts all devices, and Theorem 1 charges every comparison at the worst-case pair difficulty, giving O~(Mlog⁡M/(qImin⁡)+MT)\tilde{O}(M \log M/(q I_{\min}) + \sqrt{MT}). The first term comes from learning the priority order and the second from learning the rewards via UCB. Their algorithm replaces the priority term with O~(t0+CRA)\tilde{O}(t_0 + C_{\mathrm{RA}}), where CRAC_{\mathrm{RA}} charges only pairs that cannot be filtered out as decision-irrelevant. This is a natural way to tie learning cost to decision impact, and they obtain meaningful gains when identification is expensive (e.g., low gate probability or rare overlap). However, the extent to which the bound itself improves on the baseline is discussed in the weaknesses.
Critical weaknesses
  • The authors acknowledge that the gains heavily depend on the instance. However, there is no theoretical statement of when RA's bound beats the baseline's. The conclusion claims that the theoretical guarantees support the reduction of unnecessary exploration, but there's no bound-level comparison to Theorem 1. It would be better to state the gains against the naive baseline, which would make their contribution stand out better.
  • The main upper bound result of the paper is given in Theorems 6 and 7. Theorem 6 bounds the regret in terms of E[NTprobe]\mathbb{E}[N_T^{\text{probe}}] (the number of probing rounds). This quantity is instance-dependent, and its behavior isn't characterized in this theorem. The concrete rate relies on Theorem 7 to bound E[NTprobe]\mathbb{E}[N_T^{\text{probe}}], but Theorem 7 has its own gap as described below.
  • Theorem 7 assumes a good event G\mathcal{G} and a burn-in time t0t_0 without constructing them. It assumes that after some t0t_0 the envelopes hold with probability at least 1−δ1-\delta. In general, these envelopes depend on the reward confidence intervals through Gij(t)G_{ij}(t), so they only become tight once the reward confidence intervals have shrunk enough. The paper never says how long that takes, or whether it happens under the algorithm's actions.
  • For Corollary 3 (low gate) and Corollary 4 (rare overlap), the authors rely only on Gij(t)≤Gmax⁡G_{ij}(t) \le G_{\max}, which holds from the start without any reward learning. The corollaries implicitly fix the horizon TT and let gg or ρ→0\rho \to 0. In that setting, screening works once gg or ρ\rho is small enough. But how small depends on TT and MM. Each pair's relevance is about ai,taj,tGmax⁡a_{i,t}a_{j,t}G_{\max}, and the screening condition requires the total over all affected pairs to fall below εT\varepsilon_T. If the condition isn't met, the bound can degrade toward a sum over all (M2)\binom{M}{2} pairs, which can be worse than the baseline's Mlog⁡MM\log M comparisons.
  • For Corollary 2 (near-homogeneous rewards), the authors assume that after t0t_0 the confidence radius satisfies ri(t)≤r0r_i(t) \le r_0, and derive the gain from that. However, there is no result showing this assumption holds by any particular time. For this regime, the claim rests on something they haven't proven.
Questions for authors
  • Can the authors construct G\mathcal{G} and give an explicit bound on t0t_0 more generally? What is the main obstacle here? The authors should discuss this in more detail in the paper.
  • The pairs RA skips are ones that barely affect the reward. RA identifies them online, using its adaptive certificate. In the low-gate and rare-overlap regimes, however, these pairs can be identified from known or observed quantities (pp, γ\gamma), without any reward learning. Couldn't a baseline algorithm simply skip them as well? If so, RA's theoretical advantage would mainly come from the baseline resolving pairs that don't matter, rather than from RA's online skipping. Could the authors clarify whether RA provably improves over such a modified baseline, and in which settings?
  • The paper provides both an upper bound for RA and a lower bound, but doesn't explicitly discuss how they compare. Could the authors discuss how far RA is from optimal, and whether this gap comes from the analysis or from the algorithm's design?
Reviewer_soLnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies an online admission problem where multiple devices compete for a limited resource. The controller must decide which devices to admit before their actual demands are known. The devices have an unknown priority order, and their rewards are also unknown. The authors first develop a DP method for the optimal admission decision when all parameters are known. They propose a two-phase algorithm that learns the full priority order. To reduce unnecessary exploration, the authors introduce a relevance-aware algorithm that focuses on learning priority relations that have a large impact on the final reward. The paper provides regret upper and lower bounds and uses simulations to show that the proposed algorithm can reduce exploration costs and achieve lower regret than the baselines.

Critical strengths
  1. Interesting and meaningful problem setting. The paper studies an online admission problem with unknown priorities, stochastic competition, and uncertain rewards. These factors make the learning problem challenging and relevant to practical resource allocation systems.
  2. Well-motivated algorithm with theoretical support. The paper provides a useful insight that learning the full priority order is not always necessary for decisions. Based on this idea, the authors propose a relevance-aware algorithm that avoids unnecessary exploration. The paper also provides regret bounds and experiments to support this approach.
Critical weaknesses
  1. Limited novelty compared with existing work. The proposed model is closely related to the Random Consideration Set (RCS) model and online assortment optimization. In particular, Lu (2023) already studies learning unknown preference orders in online RCS problems. Although the proposed relevance-aware algorithm is interesting, the paper does not clearly establish how much theoretical improvement it provides over these closely related methods.
  2. Limited theoretical guarantees. The main regret bound still depends on the number of priority-probing rounds, while the instance-dependent bound requires additional conditions. The lower bound is established only for a special two-device setting, leaving a gap between the upper and lower bounds in general cases.
Questions for authors
  1. The regret upper bound depends on the number of priority-probing rounds, while the lower bound considers only a special two-device setting. Can the authors provide a tighter regret bound or extend the lower bound to more general settings?
  2. The algorithm assumes that the gate success probabilities are known. How realistic is this assumption in practical systems? Can the proposed method be extended to unknown gate probabilities?
  3. The algorithm selects priority pairs using the product of decision relevance and information rate. Why is this particular score chosen? Is there any theoretical justification showing that it is better than other selection rules?
Reviewer_kFBKOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary
  • This work studies ex-ante admission under an unknown priority order and stochastic gating, with unknown service rewards. It proposes an algorithm that selectively learns priority relations based on their impact on admission decisions and provides regret upper and lower bounds.
Critical strengths
  • This work proposes a new learning formulation for ex-ante admission and provides theoretical regret guarantees.
Critical weaknesses
  • The presentation is difficult to follow. One example is that the algorithmic details in Section 4 are deferred to the appendix, and key quantities such as IijI_{ij} (lines 202–203) have no definitions in the main text.
  • The proposed setting appears stylized, and its practical motivation is not sufficiently clear. See the question below.
  • The regret upper and lower bounds do not match, leaving the tightness of the theoretical guarantee unclear. See the question below.
  • The additional theoretical contribution over existing RCS work is not sufficiently clear from the current work. See the questions below.
Questions for authors
  • Could you provide a motivating real-world example that satisfies the proposed problem setting?
  • Could you clarify where this gap between the upper and lower bounds arises in the analysis and whether it can be closed?
  • Could you clarify the main technical advance over existing RCS learning works [1, 2], beyond the use of standard analysis of sequential testing, UCB, and perturbation arguments?

References:

[1] Lu, "Online Assortment Optimization for Random Consideration Set Choice Model", SSRN preprint, 2023.

[2] Lu, "Bounds on revenue for the random consideration set choice model", Operations Research Letters, 2024.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.