acceptodds
Under review as a conference paper at ICLR 2027

Off-Policy Learning of Capacity-Constrained Allocations

Abstract

We study off-policy learning of capacity-constrained allocations from individual logged rewards under a shared linear model and an unknown logger that may assign zero probability to available actions. Capacity constraints determine which unresolved reward directions matter, captured by a source-radius modulus. We characterize the exact infinite-data identification threshold for a fixed source law and propose a minimax-regret allocation rule with high-probability worst-batch guarantees without overlap or minimum-eigenvalue assumptions. Marginal and integral outputs can have fundamentally different sample complexity. A constructed family requires samples for marginal outputs but for integral outputs. Experiments recover the predicted finite-sample behavior, and a semi-synthetic study on real LLM query contexts shows lower empirical failure and regret under source ambiguity for MRA than regression and robust baselines.

Primary area:
learning theory
Keywords:
Off-policy learning, Capacity-constrained allocation, Partial identification

Reviews

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

This paper studies capacity-constrained resource allocation learned from logged data, where the logging policy may never select some actions. To satisfy the capacity constraints, the paper outputs a randomized combination of feasible integral assignments, so that every realized assignment satisfies the constraints, while the allocation minimizes the worst-case regret over the reward models consistent with the data. To compute this, the paper proposes an algorithm based on the double-oracle method, which determines whether the current pool of assignments is sufficient or whether additional assignments are needed. Theoretically, the paper characterizes the infinite-data identification threshold and shows that randomized (marginal) outputs can require substantially fewer samples than integral assignments.

Critical strengths

Allocation without information on unlogged actions: Under the assumption that the reward is linear in known features, the method can choose allocations with small regret even for actions that the logger never selects, for which no direct information is available.

Lower regret than existing approaches under the same information: In the source-fiber experiment, it achieves lower regret than existing approaches that use the same logged information and the same linear model, since it optimizes the worst-case regret over all reward models consistent with the data and outputs randomized allocations. This advantage, however, holds only when the linearity assumption is correct.

Certified stopping: The double-oracle procedure computes an upper bound U, the exact worst-case regret of the current allocation, and a lower bound L on the best worst-case regret achievable with the current data. Comparing the two determines whether the current pool of assignments suffices or whether additional assignments are needed, and the resulting certificate directly yields the worst-batch PAC guarantee (Theorem 5).

Critical weaknesses

Small problem size and untested scalability: The experiments use batches of five units and five actions, with only 120 feasible assignments. In this setting, the model best response explicitly enumerates all 120 assignments, and the authors note that the experiments do not establish a computational advantage from avoiding enumeration. As a result, the applicability to large allocation problems, such as those motivating the paper, remains unclear. In particular, the setting is far from one where the algorithm identifies which additional assignments are needed and improves the allocation by adding them, which is the central role of the double-oracle procedure.

Reliance on the linearity assumption: The guarantees rely on the reward being exactly linear in known features, and the paper does not quantify how much the performance degrades when this assumption is violated. I suspect that synthetic linear Bernoulli rewards are used in the LLM experiment because the benchmark scores do not satisfy this assumption.

Fairness of the comparison: In the source-fiber experiment, one action is never logged, and the evaluation criterion, the worst-case regret over models consistent with the data, coincides with the objective that MRA directly optimizes. Moreover, with five units and five unit-capacity actions, every feasible assignment must use the unlogged action. The comparators, which optimize different objectives, are therefore expected to fail under this criterion, and their uniform failure (20/20 in every setting) appears to stem from this design rather than from a general limitation.

Questions for authors

Q1. Could the authors evaluate MRA using the actual benchmark scores of LLMRouterBench instead of synthetic linear rewards? Even though these scores may violate the linearity assumption, such an evaluation would show how much performance is lost when linearity does not hold.

Q2. Are there existing approaches that explicitly handle actions absent from the logged data, such as methods for deficient support or pessimism without overlap, and how does MRA compare with them? If this is the first work, could you let me know?

6 comments
AuthorsOpenReview ↗

Response to Reviewer jaCg (1/4)

We appreciate the reviewer's positive assessment of MRA's ability to learn with unlogged actions, its source-fiber performance, and its certified stopping guarantees. Below, we address the concerns about computational scalability, model misspecification, baseline comparisons, and related experimental and theoretical questions.


Computational Scalability and Double-Oracle Execution

To further assess the scalability of the double-oracle procedure, we conducted experiments with larger batches using a structured certified best-response oracle. This procedure avoids exhaustive enumeration while preserving the full confidence set and hard capacity constraints.

Batch sizeFeasible assignmentsMedian final pool sizeCertified casesMedian learner runtime
m=5m=512015.540/400.73 s
m=10m=10113,4001940/401.90 s
m=20m=203.06×10113.06\times10^{11}2140/4017.32 s

All 120 cases terminate with valid full-confidence target or minimax-gap certificates, without fallback. For m=10,20m=10,20, all cases satisfy the minimax-gap stopping condition rather than the absolute ϵ\epsilon target.

Double-oracle execution. The complete iteration traces show 2,115 assignment-column additions to the restricted pools across the 120 runs. At m=20m=20, the final pool contains only 21 assignments at the median and at most 28, despite approximately 3.06×10113.06\times10^{11} feasible assignments. The certified gap U−LU-L reaches the prescribed stopping tolerance as the restricted pools expand, although the gap need not decrease monotonically.

These results directly demonstrate the role of the double-oracle procedure in selecting additional assignments and achieving certified convergence without enumerating the feasible allocation space. The computational improvements are established for the evaluated structured allocation family, rather than arbitrary confidence-set and allocation geometries.


Evaluation on Actual Benchmark Rewards

We thank the reviewer for suggesting an evaluation using actual LLMRouterBench reward scores. To address this concern, we conducted additional experiments using the benchmark's recorded binary model scores instead of synthetic linear Bernoulli rewards. We retain the original logging setup, including an action with zero logging probability, and evaluate MRA against four baselines.

The experiments cover four fixed environments, with 20 independent source logs per environment and 32 held-out batches per log. In addition to the original saturated-capacity setting (1,1,1,1,1)(1,1,1,1,1), we consider four one-seat slack-capacity configurations, each increasing the capacity of one logged action by one. Since the fifth action is never logged, these configurations allow feasible allocations that avoid the unlogged action. The resulting evaluation comprises 64,000 policy–batch instances.

The table reports mean fixed-score hindsight regret (lower is better).

CapacityMRAOLS-flowConstrained-flowMaximinReference-pessimistic
Saturated0.25580.25400.25400.25500.2540
Mild 00.22460.23590.23590.23620.2359
Mild 10.24550.25220.25220.25560.2522
Mild 20.25900.26910.26910.27280.2691
Mild 30.22020.23060.23060.23280.2306

MRA achieves the lowest mean regret in all four slack-capacity configurations, while OLS-based methods perform slightly better under saturated capacities. Against OLS-flow, all 16 environment-specific slack-capacity mean differences favor MRA, with nine paired 95% confidence intervals entirely below zero. The remaining seven intervals include zero.

None of the methods meets the empirical log-level ϵ=0.1\epsilon=0.1 target in these settings. Since this evaluation uses recorded binary outcomes and a fixed-score hindsight oracle, it provides complementary empirical evidence rather than a direct test of the conditional-mean PAC guarantees.

AuthorsOpenReview ↗

Response to Reviewer jaCg (2/4)

Fairness of Baseline Comparisons

To assess baseline fairness beyond the original source-fiber evaluation, we conducted additional controlled experiments with four slack-capacity configurations in which using the unlogged action is optional. We evaluate both true-parameter regret and regret under six prespecified source-compatible reward completions, using the same logged information and capacity constraints.

Controlled comparisons. We retain the same logging distribution, historical data, reward model, features, and evaluation batches across MRA and the four baselines. All methods operate under the same capacity constraints and feasible assignment set within each configuration, although their optimization objectives and returned policies differ. In each slack-capacity configuration, 60 of the 360 feasible integral assignments avoid the unlogged action entirely.

Evaluation at the true parameter. Rather than relying solely on source-fiber worst-case regret, we evaluate expected regret under the true generating parameter of the synthetic linear-reward model. The table reports mean true-parameter expected regret across four environments and 20 independent source logs per environment (lower is better).

CapacityMRAOLS-flowConstrained-flowMaximinReference-pessimistic
Saturated0.01570.00680.00680.00720.0068
Mild 00.02130.04830.04830.04880.0483
Mild 10.02150.03720.03720.03770.0372
Mild 20.02060.03580.03580.03630.0358
Mild 30.02270.04600.04600.04640.0460

Under saturated capacities, OLS-based methods achieve lower true-parameter regret than MRA. However, MRA achieves the lowest mean true regret in all four slack-capacity configurations, where the unlogged action is no longer mandatory. At ϵ=0.1\epsilon=0.1, MRA has no empirical true-parameter log-level failures across the 80 logs in each slack configuration, compared with 23–35 failures for OLS-flow. These failures are evaluated using the maximum expected regret over 32 held-out batches per log.

We also evaluate robustness against six prespecified source-compatible reward completions. For each log, we take the maximum expected regret over these completions and the 32 held-out batches, then average across logs. Under saturated capacities, MRA reduces this mean worst-completion regret from 0.15593 for OLS-flow to 0.09225. Under Mild 0, the corresponding values are 0.14638 and 0.09268. In the two reported worst-completion comparisons, MRA achieves lower mean regret than OLS-flow under both saturated and Mild 0 capacities. These finite stress tests do not establish worst-case regret guarantees over the entire source fiber.

Together, these results show that MRA's observed advantage is not solely attributable to forced use of the unlogged action or evaluation under its own robust objective. They also clarify the trade-off between true-parameter performance and robustness, rather than suggesting that MRA uniformly outperforms the baselines under every criterion.

AuthorsOpenReview ↗

Response to Reviewer jaCg (3/4)

Robustness to Reward Model Misspecification

We have extended our theoretical analysis to quantify the effect of deviations from the shared-linear reward assumption. Specifically, suppose the true conditional mean satisfies

\qquad |\xi(x,a)|\le\kappa.$$ We assume $\boldsymbol\theta\in\Theta$, bounded conditional means $0\le\mu(x,a)\le B$, and the same conditional mean function for logged and deployment rewards. **Robustness of the original MRA.** When the observed logged features span all decision-relevant allocation contrasts, we establish that the original MRA satisfies $$\Delta_\mu(I,\widehat{\mathbf Q}) \le 2s_I+\kappa\Gamma_I$$ simultaneously for all batches satisfying this coverage condition, on an event of probability at least $1-\delta/2$. Here $s_I$ measures statistical uncertainty in allocation comparisons, while $\Gamma_I$ measures how residual model errors in the source data affect deployment comparisons. Both quantities are determined by the observed design and deployment features. This bound applies **without modifying MRA, its OLS confidence set, or its allocation rule**, and without providing $\kappa$ to the learner. It also accounts for the bias introduced into OLS estimation by model misspecification, rather than treating the approximation error as an additional deployment error alone. This is a conditional decision-relevant robustness guarantee requiring realized coverage of the allocation comparison space. It does not extend the original worst-batch PAC theorem to arbitrary misspecification. Appendix A.12 also gives a counterexample in which the source covariance is full rank but increasingly ill-conditioned, and $\kappa$ approaches zero while a positive unavoidable regret remains. **Controlled nonlinear experiment.** We further evaluate MRA under a controlled nonlinear conditional-mean perturbation involving an interaction between the observed features, with strengths $\gamma\in \\{0,0.25,0.5 \\}$. Using one fixed environment, three independent source logs, and 32 held-out batches per log, we compare saturated capacities with one slack-capacity configuration (Mild 0). Regret is evaluated against the true conditional-mean oracle. | $\gamma$ | Held-out best-linear RMSE | MRA regret (Saturated) | MRA regret (Mild 0) | Failed logs (Sat.; Mild 0) | |:---:|---:|---:|---:|:---:| | 0 | 0.0000 | 0.0095 | 0.0216 | 0/3; 0/3 | | 0.25 | 0.0291 | 0.0145 | 0.0259 | 0/3; 1/3 | | 0.5 | 0.0583 | 0.0157 | 0.0277 | 1/3; 1/3 | A log is counted as a failure if the maximum true conditional-mean expected regret over its 32 held-out batches exceeds $\epsilon=0.1$. As the best-linear approximation error increases, MRA's mean true conditional-mean regret also increases in both capacity settings. We additionally identify eight batch-level cases where the nonlinear regret exceeds the original linear-model certificate. This pilot quantifies sensitivity to misspecification, although the perturbation also attenuates the original linear signal. We have incorporated these results and their precise conditions into the revised manuscript.
Reviewer_YM7YOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies off-policy learning for capacity-constrained resource allocations under a shared linear reward model when the logging policy lacks full support. Because the reward parameter is only partially identified from the logged data, the authors characterize the exact infinite-data identification floor using a source-radius modulus and propose Minimax-Regret Allocation (MRA). MRA uses a double-oracle procedure to find a feasible marginal distribution over integral assignments that minimizes worst-case regret over a source confidence set. A core theoretical result is a sharp sample complexity separation showing that outputting marginal distributions can bypass rare-observation dependencies (ρ⁻¹) that are unavoidable for deterministic integral assignments. A key result is that marginal outputs need Θ(log 1/δ) samples while integral outputs need Θ(ρ⁻¹ log 1/δ). The theory is validated on synthetic setups matching the lower-bound constructions and a semi-synthetic routing task using LLMRouterBench contexts.

Critical strengths

The main strength of this paper is the theoretical characterization of how randomization over feasible integral assignments changes the statistical information required from offline logs, showing a Θ(log⁡(1/δ))\Theta(\log(1/\delta)) vs. Θ(ρ−1log⁡(1/δ))\Theta(\rho^{-1}\log(1/\delta)) sample complexity gap between marginal and integral allocations. Moreover, the analysis avoids standard overlap assumptions and connects finite-sample confidence sets directly to the partial identification via the source-radius modulus, with tight lower bounds.

Critical weaknesses

My main concern is the computational scalability of the model best-response step in MRA and the somewhat toy nature of the semi-synthetic evaluation. Computing the exact adversarial model response requires solving a bilinear/MIP program over Cn×Z(I)\mathcal{C}_n \times \mathcal{Z}(I) or evaluating against all vertices of the reduced comparison polytope. In the LLMRouterBench experiment, batches are tiny (m=5m=5 queries, 5!=1205!=120 assignments), allowing brute-force enumeration of all comparators. Furthermore, the LLM experiment replaces actual benchmark performance scores with synthetic linear Bernoulli rewards, which leaves open how MRA behaves under model misspecification or larger batch sizes where exact best-response certification defaults to the OLS plug-in. Some relevant previous work is not cited, e.g., Stoye (2009), Kitagawa & Tetenov (2018), and Manski (2009, IER). Manski's work shows that, with two treatments, minimax-regret allocations are fractional under ambiguity, including under capacity constraints on the treated fraction, and discusses ex ante vs. ex post equal treatment of such allocations. This is a close conceptual precedent for the mixing-helps message.

Questions for authors
  • What is new relative to Manski (2009) beyond the finite-sample combinatorial setting?
  • Why is expected regret the right criterion when each unit receives one realized assignment? What is the realized regret of sampled assignments?
  • In the LLM study, what are the regret at the true parameter and the failure rate as a function of ε?
  • In Algorithm 1, if the best-response optimization reaches a computation limit, the algorithm falls back to the integral plug-in z0z_0. In larger batch settings (m≫5m \gg 5) where enumerating Z(I)\mathcal{Z}(I) is impossible and the MIP formulation in Proposition 25 is solved approximately, how often does MRA fall back to z0z_0, and can approximate best responses still yield valid regret certificates?
  • In the LLMRouterBench experiment, why not evaluate on the actual benchmark reward scores in addition to the synthetic linear Bernoulli rewards?
4 comments
AuthorsOpenReview ↗

Response to Reviewer YM7Y (1/4)

We thank the reviewer for the thoughtful assessment and for recognizing the sharp marginal–integral sample-complexity separation and our theoretical guarantees without overlap assumptions. We also appreciate the constructive feedback on computational scalability, empirical evaluation, related work, and the interpretation of randomized allocations, which we address below.


Computational Scalability and Certified Approximate Optimization

We have extended our computational evaluation beyond the original m=5m=5 setting and clarified how approximate best responses can retain valid regret certificates.

Computational scalability. We evaluate MRA on batches of m=5,10,20m=5,10,20 individuals with five resources, balanced capacities, and n=512n=512 logged observations. Each size includes 20 independent source logs and two deployment batches per log. We retain the original full correlated confidence set and verify the returned policies against that entire set.

Batch sizeCertified casesTarget / gap stopsFallbacksMedian runtime
m=5m=540/405 / 3500.73 s
m=10m=1040/400 / 4001.90 s
m=20m=2040/400 / 40017.32 s

At m=20m=20, the problem has approximately 3.06×10113.06\times10^{11} feasible integral assignments, which are handled without enumeration using a structured certified best-response procedure. The median learner runtime is 17.32 seconds, excluding independent certificate verification. The median independent verification time is 49.97 seconds, and the median normal end-to-end runtime is 86.83 seconds. All 40 cases at this size obtain valid minimax-gap certificates, rather than certificates of absolute regret at most ϵ\epsilon. No integral plug-in fallback occurs in these tested cases.

In a separate experiment using a time-limited general-purpose MIP solver, none of the 40 runs across m=10,20m=10,20 and time limits of 30 or 120 seconds obtained a final certificate, resulting in fallback. These results illustrate the practical value of exploiting allocation structure for certified response computation in the evaluated instances.

Certified approximate best responses. Exact optimization is not necessary for a valid certificate if the solver provides rigorous global bounds satisfying

L≤vn,I≤gn,I(Q)≤U,L\le v_{n,I}\le g_{n,I}(\mathbf Q)\le U,

where vn,Iv_{n,I} is the minimum achievable worst-case regret over the confidence set, and gn,I(Q)g_{n,I}(\mathbf Q) is the returned policy's worst-case regret. The original stopping rules remain valid. The condition U≤ϵU\le\epsilon certifies the target regret, while U−L≤ζnU-L\le\zeta_n certifies approximate minimax optimality. A feasible solver incumbent alone is insufficient without the required global bounds.

These certified stopping conditions preserve the original worst-batch PAC analysis without modifying the confidence set. If computation remains uncertified and the algorithm returns the integral OLS plug-in, feasibility is preserved but the PAC bound must account for the probability of unresolved computation.

The structured experiment demonstrates certified execution in the evaluated allocation family, while the separate MIP experiment reports fallback behavior under the tested solver and time limits. Neither establishes a general computational complexity guarantee.

AuthorsOpenReview ↗

Response to Reviewer YM7Y (2/4)

True-Parameter Regret and Failure Rates

We have extended the synthetic linear-reward experiment on LLMRouterBench contexts to report regret at the true generating parameter and empirical failure rates across evaluation thresholds. At n=131,072n=131{,}072, we evaluate four fixed environments with 20 independent source logs per environment and 32 held-out batches per log. A log is counted as a failure when the maximum true-parameter expected regret across its 32 batches exceeds the evaluation threshold ϵ\epsilon.

The five-resource setting has saturated capacities (1,1,1,1,1)(1,1,1,1,1) and four one-seat slack configurations, each increasing the capacity of one logged action by one. The fifth action is never logged.

CapacityMean batch-level true regret (MRA / OLS-flow)Failures at ϵ=0.05\epsilon=0.05Failures at ϵ=0.075\epsilon=0.075Failures at ϵ=0.1\epsilon=0.1
Saturated0.01574 / 0.0068023 / 202 / 30 / 0
Slack 00.02134 / 0.0483534 / 774 / 480 / 35
Slack 10.02148 / 0.0372223 / 562 / 400 / 23
Slack 20.02058 / 0.0357925 / 612 / 430 / 24
Slack 30.02268 / 0.0459841 / 734 / 430 / 33

All failure-count entries are MRA / OLS-flow, out of 80 logs per capacity setting, pooled descriptively across the four fixed environments. Under saturated capacities, OLS-flow has lower mean true-parameter regret, whereas MRA reduces the mean log-level maximum regret over six prespecified source-compatible reward completions from 0.15593 to 0.09225. Under all four one-seat slack configurations, MRA achieves lower mean true-parameter regret and fewer empirical failures.

The table evaluates the same saved policies, trained with ϵ=0.1\epsilon=0.1, at evaluation thresholds 0.050.05, 0.0750.075, and 0.10.1 without retraining. The first two thresholds provide additional rebuttal-level summaries, while the revised manuscript reports the ϵ=0.1\epsilon=0.1 failure counts. These empirical failures concern 32 held-out batches per log, not the supremum over all admissible batches required by our theoretical PAC criterion.


Evaluation on Actual Benchmark Rewards

We have extended the LLMRouterBench evaluation to use the recorded binary reward scores rather than synthetic linear Bernoulli rewards. At n=131,072n=131{,}072, we evaluate four fixed environments with 20 independent source logs per environment and 32 held-out batches per log, across five capacity configurations and five allocation methods.

The table reports mean fixed-score hindsight regret, averaged descriptively across the four environments.

CapacityMRAOLS-flow
Saturated0.25580.2540
One-seat slack 00.22460.2359
One-seat slack 10.24550.2522
One-seat slack 20.25900.2691
One-seat slack 30.22020.2306

MRA achieves lower mean regret in all four slack-capacity configurations, while OLS-flow performs slightly better under saturated capacities. Across the 16 environment-specific slack-capacity comparisons, all paired mean differences favor MRA, with 9 having pointwise 95% confidence intervals entirely below zero. These intervals use independent source logs as the sampling units and are not adjusted for multiple comparisons.

Nevertheless, all methods fail the empirical log-level ϵ=0.1\epsilon=0.1 criterion in every evaluated environment and capacity configuration. The recorded scores need not satisfy the assumed shared-linear conditional-mean model, and the fixed-score hindsight oracle differs from the theoretical conditional-mean oracle. Thus, these results provide additional evidence of MRA's empirical behavior beyond synthetic rewards, rather than a guarantee of robustness to model misspecification.

The revised manuscript reports the pooled comparisons and summarizes the environment-specific paired confidence intervals in Appendix E.7.

AuthorsOpenReview ↗

Response to Reviewer YM7Y (3/4)

Relation to Prior Minimax-Regret Treatment Choice

We thank the reviewer for highlighting these relevant connections. We have expanded the Related Work to discuss Manski (2009), Stoye (2009), and Kitagawa and Tetenov (2018). Manski establishes fractional minimax-regret treatment allocation under ambiguity, including capacity restrictions. Stoye studies exact finite-sample minimax-regret treatment choice, while Kitagawa and Tetenov analyze empirical welfare maximization and finite-sample welfare guarantees, including treatment-share constraints.

Our main contribution goes beyond finite-sample combinatorial optimization. We develop a source-specific statistical theory of off-policy allocation learning under an unknown logging distribution that may assign zero probability to some actions. In this setting, the reward parameter need not be identifiable. We characterize the exact identification floor induced by the logging source and introduce a source-radius modulus that connects finite-sample uncertainty to allocation regret. MRA uses the logged data, the observed deployment batch, and the known allocation constraints without requiring knowledge of the logging distribution. It provides simultaneous worst-batch PAC guarantees rather than controlling only sample-averaged welfare regret.

Moreover, our analysis establishes sharp information-theoretic separations between marginal and integral outputs. Theorem 9 shows that marginal allocations can achieve a target accuracy with Θ(log⁡(1/δ))\Theta(\log(1/\delta)) samples, whereas integral outputs require Θ(ρ−1log⁡(1/δ))\Theta(\rho^{-1}\log(1/\delta)) samples under the same logging experiment. Theorem 10 further establishes matching sample complexity above a positive identification floor, with the upper bound attained by MRA.

We have also strengthened these results with controlled capacity comparisons. Holding the reward model, features, logging distribution, and deployment contexts fixed, changing only the capacities can create a marginal–integral sample-complexity separation or change the exact identification floor from 00 to B/12B/12. These results clarify how capacity constraints affect the statistical information required for allocation, beyond the classical principle of fractional minimax-regret treatment choice.

AuthorsOpenReview ↗

Response to Reviewer YM7Y (4/4)

Expected Regret and Realized Assignments

Our policy randomizes over feasible integral assignments rather than implementing fractional assignments. Every sampled assignment satisfies the eligibility and hard capacity constraints.

Let Q=π^n(I)\mathbf Q=\widehat\pi_n(I) be the learned marginal, conditional on any learner-level randomization, and let Z\mathbf Z be sampled from a feasible integral mixture representing Q\mathbf Q. By linearity of welfare,

\Delta_\theta(I,\mathbf Z) \mid\mathcal D_n,I,\mathbf Q \right] = \Delta_\theta(I,\mathbf Q).$$ Thus, our expected-regret criterion exactly measures the conditional expected regret of the implemented randomized allocation policy. It is appropriate for evaluating the policy's expected welfare while ensuring feasibility in every realization. The PAC guarantee controls this expected regret uniformly over deployment batches with high probability over the learning process. It does not guarantee that every sampled assignment achieves the same regret. For any $t>0$, $\Pr(\Delta_\theta(I,\mathbf Z)>t\mid\mathcal D_n,I,\mathbf Q)\le\min(1,\frac{\Delta_\theta(I,\mathbf Q)}{t})$ This distinction is fundamental. For the base batch $L=1$ under the larger capacity in Appendix B.9, consider the three source-indistinguishable models at $h=0$. A feasible marginal achieves expected regret $B/12$ under all three models, whereas every integral assignment incurs regret at least $B/8$ under at least two of them. Since this base batch belongs to the declared domain, every integral-output learner satisfies $\max_{j\in[3]}\Pr_{\theta_j}(R_{\theta_j}(\widehat{\pi}_n)>t)\ge\frac{2}{3}$ $\frac{B}{12}<t<\frac{B}{8}$ for every sample size, including learner-level randomization. Hence an analogous high-probability guarantee for individual realizations does not follow from the expected-regret guarantee. We additionally evaluate realized-assignment regret using the saved policy mixtures in the saturated synthetic LLMRouterBench-context experiment. Across 80 source logs, the mean log-maximum true-parameter expected regret is 0.0464, whereas the mean conditional expected maximum regret over 32 independently sampled feasible assignments is 0.0901. The mean conditional probability that at least one sampled assignment incurs regret exceeding 0.1 is 0.3747. These quantities are computed from the exact finite-mixture distributions under the true generating parameter, rather than from fresh deployment reward observations. We have clarified the interpretation of expected regret, the feasibility of sampled assignments, and the distinction between policy-level PAC guarantees and realized-assignment regret in the revised manuscript.
Reviewer_UqRUOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies how to allocate limited resources using historical data when some available actions may never have been chosen. It examines which gaps in the data affect allocation decisions and characterizes the best accuracy achievable even with unlimited data. The authors propose a method that accounts for the remaining uncertainty and provides guarantees on how much worse its decisions can be than the best feasible allocation. They also show that, in certain settings, randomizing among feasible allocations requires substantially less data than committing to a single allocation.

Critical strengths

The paper addresses an interesting question that I believe is well motivated by practical applications. Furthermore, it establishes tight theoretical bounds for specific problem settings. The paper also includes experiments that illustrate the theoretical findings and compare the proposed method with several baselines.

Critical weaknesses

In its current form, I do not find the paper sufficiently clear to recommend acceptance at ICLR. For example, the "Problem Formulation" section introduces definitions without first explaining how they fit together. I suggest beginning this section with a high-level description of the problem. What information the learner observes, what decisions it must make, and what objective it seeks to achieve. A concrete running example would help connect these elements before introducing the formal notation. In addition, Assumption 1 refers to I∈II \in \mathcal I before this quantity is defined, making it difficult to follow.

Questions for authors

The paper demonstrates the benefit of randomization in a specific construction. Could the authors discuss when a similar benefit should be expected in practical allocation problems?

4 comments
AuthorsOpenReview ↗

Response to Reviewer UqRU

We thank the reviewer for the thoughtful assessment and for recognizing the significance of our problem and theoretical contributions. We also appreciate the constructive feedback on the clarity of the presentation and the practical benefits of randomization, which we address below.


Clarifying the Problem Formulation and Notation

We have reorganized Section 3 to first explain the learner's observations, feasible allocation decisions, and simultaneous worst-batch PAC objective before introducing the formal notation. We have also added an illustrative example to explain how randomized policies operate over hard-feasible assignments. In addition, we have moved the definitions of the deployment batch II and batch domain I\mathcal I before Assumption 1. These changes clarify how the components of the problem formulation fit together without altering the model or theoretical results.


When Randomization Is Beneficial in Practical Allocations

The benefit of randomization arises from the interaction between decision-relevant uncertainty and the discrete structure of feasible allocations. In particular, randomization can improve worst-case expected regret when plausible reward models favor different allocations and no single integral assignment achieves the optimal balance across these models.

A concrete example arises when the uncertain reward differences depend on how many individuals use a scarce resource. If plausible models favor opposite changes in resource usage, the regret-minimizing balance may lie between two feasible integer counts. Randomizing between the corresponding feasible assignments can then strictly improve worst-case expected regret while respecting hard capacities in every realized assignment. In this resource-count setting, the benefit can be characterized through feasible usage counts and reward contrasts.

In the resource-count setting of Proposition 28, let ℓ<u\ell<u be the minimum and maximum feasible integer usage counts. When the opposing regret slopes α,β\alpha,\beta are both positive, the minimax-balancing expected count is

k∗=ℓ+(u−ℓ)βα+β.k^*=\ell+(u-\ell)\frac{\beta}{\alpha+\beta}.

Randomization strictly improves worst-case expected regret over every integral allocation if and only if k∗k^* is nonintegral. This is an exact criterion for the specified resource-count structure, not a universal condition for all allocation problems.

Importantly, incomplete logging or competing resource demands alone do not guarantee an advantage. Randomization may provide no improvement when an integral assignment already achieves the minimax balance or when the remaining uncertainty does not affect the optimal allocation. We have added this structural interpretation and the corresponding conditions to the revised manuscript.

We also evaluate this benefit across 1,200 matched allocation instances spanning five capacity configurations. The returned randomized MRA policy achieves strictly lower certified full-confidence expected regret than the minimax-optimal integral allocation in 905 instances, and in 635 instances MRA alone certifies the robust ϵ=0.1\epsilon=0.1 target. These results provide empirical evidence of the benefits of randomization beyond the original theoretical constructions.

The benefit concerns worst-case expected regret over plausible reward models, rather than a guarantee that every sampled assignment outperforms an integral alternative.

I thank the authors for their response. However, I still believe that this paper falls below the ICLR threshold in terms of presentation and clarity. At a time when AI tools are increasingly capable of developing mathematical results, I believe that the quality of presentation and the clarity of exposition play an especially important role. Therefore, although I remain slightly positive overall, I am not willing to champion or strongly endorse this paper for acceptance.

We appreciate the reviewer's additional feedback. We have also revised Section 3 to provide a clearer overview of the learning problem and added an illustrative example. We corrected the order of definitions as well. If there are other parts of the manuscript that could be clearer, we would appreciate any further suggestions and would be happy to improve the presentation.

We thank the reviewer again for emphasizing the importance of presentation and clarity. Following this feedback, we have further revised the exposition throughout the manuscript, beyond the changes to Section 3 described in our previous response.

In addition to clarifying the problem formulation and adding an illustrative example in Section 3, we have made the following improvements.

  • Sections 4–6: We strengthened the intuition behind source-fiber ambiguity and the source-radius modulus, clarified the distinction between minimax regret and maximin value, explained the roles of the two stopping certificates, and improved the connections between confidence sets, PAC guarantees, and information lower bounds.
  • Section 7 and Related Work: We clarified the interpretations of the sharpness results and capacity-only interventions, including a resource-count criterion for beneficial randomization, and expanded the discussion of relevant prior literature.
  • Section 8 and Appendices: We clarified the experimental protocols, evaluation criteria, and limitations, including the trade-off between saturated and relaxed capacities. We also provided additional theoretical and computational details in response to the other reviewers' questions.
  • Figures 1–6: We improved the readability of all figures, including their text, labels, and legends.

Taken together, these changes make the connections between the problem formulation, theoretical analysis, algorithmic design, and empirical evaluation more explicit. We hope these revisions address the reviewer's concerns about presentation and clarity.

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

My understanding is that the authors are investigating how to select a subsequent allocation strategy under hard capacity constraints, given only the offline context-action-reward data left by the behavioral policy—and with the possibility that certain actions may never have appeared in the log. MRA uses the worst-case regret of candidate reward models to select an executable randomized allocation strategy, and employs the source-radius modulus to describe the remaining decision uncertainty when data is insufficient. I believe this problem is closely related to offline policy learning, logs with finite support, and partial identification.

Critical strengths

S1: I appreciate that the authors do not require the behavioral policy to cover all actions, nor do they impose the assumption of a minimum eigenvalue for the source covariance. Under these conditions, proving the PAC regret guarantees for each deployment batch and distinguishing between the information required for a probabilistic policy and that for a single deterministic assignment holds theoretical significance.

Critical weaknesses

W1: My initial main concern was that certain sample complexity separations in Theorems 9–10 appear to be reducible to examples where a single decision-maker selects three actions, without necessarily requiring multiple decision-makers competing for capacity. If the capacity constraint is removed and the core effect persists, what exactly does the paper reveal about the new learning difficulty introduced by capacity itself?

W2: I am also concerned about whether the results are computable. The source-radius modulus already contains a min–max decision problem; if knowledge of the unknown log distribution is required to estimate it, the theoretical thresholds would be difficult to apply directly. Another issue is that the rewards in the LLM context-querying experiments are synthetically constructed and cannot be described as off-policy benefit guarantees for real LLM routing.

Questions for authors

Q1: I would like to see a set of experiments or constructs that vary only capacity, while keeping other reward models, log distributions, and contexts constant.

Q2: I hope there are verifiable structural conditions that ensure the source-radius modulus and sample complexity bounds are more than just formal expressions.

5 comments
AuthorsOpenReview ↗

Response to Reviewer deyN (1/2)

We thank the reviewer for the thoughtful assessment and for recognizing our theoretical guarantees under unknown and potentially singular logging distributions and the information-theoretic benefits of randomization. We also appreciate the constructive feedback on capacity constraints, operational significance, and experimental evidence, which we address below.


The Role of Capacity Constraints in Statistical Separations

The three-action reduction noted by the reviewer preserves the statistical separations in Theorems 9 and 10. These results address broader statistical questions under partial identification: Theorem 9 establishes a sharp marginal–integral information separation, while Theorem 10 provides matching sample-complexity bounds above a positive identification floor. To clarify the additional role of capacity constraints, we have added Section 7.3 and Appendices B.8–B.9, establishing two controlled capacity interventions. Both comparisons hold the reward model, feature map, logging distribution, and deployment contexts fixed while changing only the capacity vector. These new results show that capacity constraints themselves can alter the statistical information required for accurate allocation.

One-seat capacity intervention. Consider a cyclic allocation problem with an even number m≥4m\ge 4 of individuals and resources. Changing only the capacities from b=1\mathbf b=\mathbf 1 to c=1+e1\mathbf c=\mathbf 1+\mathbf e_1 yields, for ϵ0=3B/16\epsilon_0=3B/16, 0<ρ≤1/20<\rho\le 1/2, and 0<δ≤1/80<\delta\le 1/8,

Nb∗(ϵ0,δ)≍Nb(1)(ϵ0,δ)≍Nc∗(ϵ0,δ)≍log⁡(1/δ)N_{\mathbf b}^{\ast}(\epsilon_0,\delta) \asymp N_{\mathbf b}^{(1)}(\epsilon_0,\delta) \asymp N_{\mathbf c}^{\ast}(\epsilon_0,\delta) \asymp \log(1/\delta)

Nc(1)(ϵ0,δ)≍ρ−1log⁡(1/δ)N_{\mathbf c}^{(1)}(\epsilon_0,\delta) \asymp \rho^{-1}\log(1/\delta)

Here N(1)N^{(1)} denotes the minimax sample complexity restricted to integral outputs, and ρ\rho is the rare-observation probability. Thus, increasing the capacity of a single resource creates a marginal–integral sample-complexity separation that is absent under the original capacities. Under the original capacities, feasibility restricts the problem to two assignments, and unobserved resource-specific effects cancel from their comparison. Increasing one capacity admits additional threshold assignments whose relative values depend on rarely observed resource effects. Randomized allocations can hedge against this uncertainty without identifying those effects, whereas integral outputs require the rare observations to achieve the same target accuracy. The dimension-independent upper bounds in this construction are achieved by a specialized learner.

Capacity-induced identification floor. In a separate fixed-dimensional shared-linear model, changing only the capacities from bL=(L,L,L)\mathbf b_L=(L,L,L) to cL=(2L,L,L)\mathbf c_L=(2L,L,L) changes the exact identification floor from

\qquad\text{to}\qquad F_{\mathbf c_L}=B/12.$$ For $0<\rho\le1/2$, $0<\tau\le B/2304$, and $0<\delta\le1/32$, the matching PAC sample complexities at the same excess accuracy $\tau$ above the respective floors satisfy $N_{\mathbf b_L}^{\ast}(\tau,\delta) \asymp \frac{B^2}{(1-\rho)\tau^2}\log\frac1\delta$ $N_{\mathbf c_L}^{\ast}(B/12+\tau,\delta) \asymp \frac{B^2}{\rho\tau^2}\log\frac1\delta$ Both upper bounds are attained by the original MRA with its unchanged OLS confidence set and completed exact best responses (Theorem 27, Appendix B.9). The common mechanism is that resource-specific reward components cancel from allocation comparisons when all capacities are saturated. Relaxing capacities can make resource counts vary, rendering previously irrelevant reward components decision-relevant. These results demonstrate that capacity constraints can directly alter both the statistical benefit of randomization and the information needed for accurate allocation.
AuthorsOpenReview ↗

Response to Reviewer deyN (2/2)

Computability and Statistical Sharpness of the Source Modulus

We have added Appendix A.11 (Theorem 15 and Proposition 16) to establish verifiable conditions for computing the source-radius modulus and matching PAC bounds.

Computability (Theorem 15, Appendix A.11). Suppose the source identifies all feasible allocation comparisons and the squared norms of source-whitened integral assignment features are affine in the assignment indicators. Under these conditions, the relevant geometric radius can be computed by a convex quadratic program over feasible marginal allocations. For explicitly specified finite feature and batch families and a given population source covariance, a sufficient certificate for the affine-energy condition can be obtained from a linear feasibility system using allocation equalities and incompatible edge pairs. An additional assignment-flow optimization certifies the optimization gap.

Matching sample complexity (Proposition 16, Appendix A.11). Suppose a common parameter makes all feasible assignments tie and the bounded-reward parameter set permits decision-relevant perturbations up to radius t0t_0. Then

\qquad (0\le t\le t_0),$$ where $\gamma$ is the maximum geometric radius over the declared batches. If $\gamma>0$ and the source rank is bounded, we further obtain $$N^*(\epsilon,\delta;\mathcal E_\lambda) \asymp \frac{B^2\gamma^2}{\epsilon^2} \log\frac1\delta$$ for $0<\epsilon\le B\gamma t_0/16$ and $0<\delta\le 1/8$, with a fixed positive reward-interiority margin. The upper bound is attained by the original MRA with its unchanged OLS confidence set and completed exact best responses, without knowing the logging distribution. Separately, when the observed Gram matrix covers the allocation contrasts of a given batch and an enclosing ball is certified, we obtain a valid regret certificate for that batch. This optional computation is not part of the original MRA. For the capacity-induced identification-floor construction, we separately establish that changing only the capacities shifts the exact source-fiber identification floor from $0$ to $B/12$ and yields matching PAC sample-complexity rates above the respective floors (Theorem 27, Appendix B.9). --- ### Additional Experimental Evidence To address the concerns about empirical generality and computational scalability, we have substantially expanded the evaluation in the revised manuscript (Appendices E.7, E.9, and E.10), including recorded benchmark scores, certified computation on larger batches, and randomized-versus-integral comparisons. **Evaluation with actual benchmark scores.** We additionally evaluate MRA using recorded binary reward scores from LLMRouterBench rather than synthetic linear Bernoulli rewards. Across four environments, with 20 independent source logs per environment and 32 held-out batches per log, we consider the original saturated-capacity setting and four slack-capacity configurations. The fifth action is never logged. Saturated capacities are $(1,1,1,1,1)$, while each slack configuration increases the capacity of one logged action by one, making it possible to avoid the unlogged action. The mean fixed-score hindsight regrets are reported below (lower is better). | Capacity configuration | MRA | OLS-flow | |:---|---:|---:| | Saturated | 0.2558 | **0.2540** | | Mild 0 | **0.2246** | 0.2359 | | Mild 1 | **0.2455** | 0.2522 | | Mild 2 | **0.2590** | 0.2691 | | Mild 3 | **0.2202** | 0.2306 | MRA achieves lower mean regret than OLS-flow in all four slack-capacity configurations, while OLS-flow performs slightly better under saturated capacities. Nevertheless, all methods fail the empirical log-level $\epsilon=0.1$ criterion. Since the recorded scores need not satisfy the assumed linear conditional-mean model, this evaluation does not directly test the theoretical PAC guarantee. **Computational scalability.** We extend the linear-reward experiment to batch sizes $m=5,10,20$, with five resources and balanced capacities. MRA obtains valid full-confidence target or minimax-gap certificates in all 40 tested cases at each size, without fallback. At $m=20$, approximately $3.06\times10^{11}$ feasible integral assignments are handled without enumeration, with a median learner runtime of 17.3 seconds. All $m=20$ cases achieve minimax-gap certification rather than the absolute $\epsilon$ target. **Benefit of randomized allocations.** Across 1,200 matched comparisons spanning five capacity configurations, the returned randomized MRA policy achieves strictly lower certified full-confidence expected regret than the minimax-optimal integral allocation in 905 cases. In 635 cases, MRA alone satisfies the robust $\epsilon=0.1$ target. These results provide further evidence of the benefits of randomization and certified computation in the evaluated settings. The scalability experiment exploits structured allocation geometry and does not establish general computational superiority.
Reviewer_deyNOpenReview ↗

Revised assessment

I am raising my score from 2 to 3. The added capacity interventions address the main issue in my review: with the reward model, logger and deployment contexts fixed, changing capacities can create the rare-observation separation and move the identification floor from 0 to B/12. This is stronger evidence for the role of capacities than Theorems 9–10 alone. Appendix A.11 also gives concrete conditions under which the geometric radius is computable and the local modulus yields matching rates, so I no longer regard this question as unanswered.

I now lean toward acceptance on the strength of these theoretical results. Their scope should remain explicit: the dimension-independent bound in Theorem 26 uses a specialized learner, and Appendix A.11 requires coverage of the allocation comparison space and additional geometric conditions. The computational results likewise support the structured implementation: all 40 cases at m=20 obtain minimax-gap certificates, while the general-purpose MIP falls back in all 40 budgeted attempts. These limits constrain the practical interpretation, but they do not negate the new capacity-dependent results.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.