- 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
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).
| Capacity | MRA | OLS-flow | Constrained-flow | Maximin | Reference-pessimistic |
|---|---|---|---|---|---|
| Saturated | 0.0157 | 0.0068 | 0.0068 | 0.0072 | 0.0068 |
| Mild 0 | 0.0213 | 0.0483 | 0.0483 | 0.0488 | 0.0483 |
| Mild 1 | 0.0215 | 0.0372 | 0.0372 | 0.0377 | 0.0372 |
| Mild 2 | 0.0206 | 0.0358 | 0.0358 | 0.0363 | 0.0358 |
| Mild 3 | 0.0227 | 0.0460 | 0.0460 | 0.0464 | 0.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 , 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.
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.
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.
All 120 cases terminate with valid full-confidence target or minimax-gap certificates, without fallback. For m=10,20, all cases satisfy the minimax-gap stopping condition rather than the absolute ϵ target.
Double-oracle execution. The complete iteration traces show 2,115 assignment-column additions to the restricted pools across the 120 runs. At m=20, the final pool contains only 21 assignments at the median and at most 28, despite approximately 3.06×1011 feasible assignments. The certified gap U−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), 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).
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 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.