acceptodds
Under review as a conference paper at ICLR 2027

Learning to Assign Prediction Tasks to Agents with Capacity Constraints

Abstract

We address the problem of learning to assign prediction tasks to one agent from a set of available agents, including human decision-makers and AI models. We focus on sequential learning of agent expertise and assignment policies where each agent is constrained to handle a fraction of tasks. We provide a general theoretical characterization of this problem in terms of agent capacities, differences in agent expertise, and task context. We then develop a framework of sequential explore-exploit policy-learning algorithms that seek to maximize overall performance. Experimental results over a variety of tabular, image, and text prediction tasks demonstrate systematic gains from our policy-learning algorithms relative to non-contextual baselines across different types of agents, including LLMs and humans.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Human-AI collaboration, Assignment policy, Online learning

Reviews

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

The paper studies the problem of sequentially assigning online prediction tasks to an agent (human or AI) subject to specific capacity constraints. An ideal routing policy is defined which demonstrates the best strategy assigns tasks based on how much better one agent is than another on a given task, adjusted by a penalty that prevents any single agent from being overworked. An online algorithm is proposed for this task. They demonstrate good results against selected baselines on different tasks.

Critical strengths

The "critical" strength of the paper is the rigorous mathematics. The authors are exhaustive in their proofs, backing up pretty much every claim that they make, and working around edge-cases (like when one agent dominates vs. when they disagree). Whilst it's quite a theoretical paper, they try make it as "realistic" as possible.

Critical weaknesses

My primary "critical" weaknesses is that the paper misses quite a few related works, of which may narrow the novelty claims.

Firstly, the paper writes: "Our work differs from prior work in two primary aspects. First, we jointly learn assignment policies and agent expertise online (useful, for example, under distribution shift), unlike prior work on learning to defer or LLM routing, which learns agent expertise offline (Mozannar & Sontag, 2020; Claure et al., 2020; Chen et al., 2023)." I believe the existing "population-adaptive" L2D works of L2D-Pop [1] and IFD [2] (whilst not marketed as online-learning L2D) can do this. Whilst these papers meta-train their architectures (classifier and rejector) offline, at inference they utilize a set of data (similar to an online stream?) to learn and update agent expertise online under bandit feedback. I think it's especially relevant to IFD's Bayesian expert competence updating, as they update the expert's competence posterior as new data comes in. It's quite similar to the paper's Bayesian logistic/tree reward model in Sec. 3. Additionally, there seems to be many other works not cited/discussed within the paper which seem quite relevant. I have not read these papers in detail, though. See [3] and [4].

Next, the authors claim their work differs from prior work because they study "capacity constraints on the agents, unlike fairness-constrained bandits, which enforce a shared minimum-rate constraint across arms (Chen et al., 2020), and cost-constrained LLM routing, which enforces a global budget rather than agent-specific capacity limits." There are a few issues with this. On page 1, when introducing the author to related works and noting how theirs is different, the authors do not discuss capacity constraints L2D work. But, in Sec. 5, they cite five L2D works which explicitly enforce agent-specific workload/capacity constraints. This is important because I believe the theoretical characterization in Sec 2.3, Thm 2.1 is already established in L2D -- see [5].

Unrelated, the authors do not release the code. In my opinion, in the modern era where ICLR receives 66K submissions and there is a reproducibility crisis, I think this severely hampers the ability to accept a paper if the reviewers cannot audit the results.

[1] Tailor, D., et al. (2024). Learning to Defer to a Population: A Meta-Learning Approach. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics (AISTATS 2024), PMLR 238:3475–3483.

[2] Strong, J., et al. (2026). Identity-Free Deferral For Unseen Experts. Proceedings of The Fourteenth International Conference on Learning Representations (ICLR 2026).

[3] To Defer or Not to Defer? Online Learning with LLMs and Congested Experts. https://arxiv.org/html/2610.15128v1

[4] Online Decision Deferral under Budget Constraints. https://arxiv.org/abs/2409.20489

[5] Post-hoc Estimators for Learning to Defer to an Expert, NeurIPS 2022

Questions for authors

The only question which would materially effect my assessment are those pertaining the related works (see critical weaknesses). Can the authors please address these?

4 comments

We thank Reviewer UYem for the careful reading and for these references, and we are glad the reviewer found our theoretical analysis rigorous, including the treatment of edge cases such as agent dominance and disagreement. We have read each suggested paper and revised the introduction and related work accordingly. They help us position our work more precisely, and we address each below.

Population-adaptive L2D [1, 2].

Thank you for pointing us to L2D-Pop [1] and IFD [2], which we now cite in the introduction and related work. Both meta-train offline so that, at test time, the rejector can adapt to an unseen expert from a small context set of that expert’s past predictions with true labels. IFD’s Beta–Binomial competence posterior is indeed close in spirit to our Bayesian reward models. The key difference is the source of the data. In both papers, the context set is a labeled sample collected before deployment and independent of the system’s own decisions, for example “a few ‘warm-up’ diagnoses (on historical data)” in L2D-Pop (see their Section 4). IFD studies larger context sets by re-evaluating a fixed, pre-trained model with larger random draws from a labeled pool (see their App. G.3–G.4). In this sense, their expertise estimation happens at test time but is offline with respect to the decision stream, and it is not bandit feedback, since the expert’s prediction and the true label are available for every context example. In our setting, tasks arrive sequentially and we observe only the outcome of the selected agent, so what we learn depends on our own assignments. In addition, IFD models competence per class rather than as a function of the input (see their Section 4.1), whereas we model context-dependent expertise μa(x)μ_a(x). Neither method enforces agent-specific capacities. IFD’s deferral budget is a quantile threshold over the evaluation set (see their Section 5), while we enforce each agent’s capacity online.

Online deferral [3, 4].

Reid et al. (2024) [4] was already cited. We have revised our description to state that it studies online deferral between a model and a single human as a contextual bandit with a budget on deferral costs, under both bandit and full-information feedback. Our setting differs in that tasks are assigned among multiple agents, each with its own capacity target, rather than limiting a budget on a single costly expert with the model as a free fallback.

Saketos et al. [3] appeared on arXiv on 10 October 2026, after the ICLR submission deadline, and we now cite it as concurrent work. It is close in spirit, with online learning, selective feedback, and limited expert capacity. However, it learns the reliability of a single LLM from a discrete confidence signal and defers to a shared queue of experts who are assumed to be always correct, with capacity entering as a congestion cost. In contrast, we learn the context-dependent expertise of every agent and enforce agent-specific capacity targets.

Capacity-constrained L2D and Theorem 2.1 [5].

Thank you for pointing out that our introduction did not discuss learning-to-defer methods with workload constraints, although our Related Work (Section 5) cites them. We have revised the introduction to discuss workload-constrained learning to defer directly. It now states that workload constraints have been studied in learning to defer (Alves et al., 2024; Nguyen et al., 2025; Zhang et al., 2026, in our paper), where agent expertise is learned offline. Our setting differs in combining these constraints with online learning of agent expertise from bandit feedback, where capacities must be enforced as tasks arrive.

We also agree on Theorem 2.1. Its general form is a known result from semi-discrete optimal transport [6], and the two-agent threshold rule (Proposition 2.1) matches the constrained deferral rules in learning to defer [5]. We now cite both after the theorem and present it as a foundation of our analysis rather than as contributions. Our contribution in Section 2 is to characterize when and by how much context-dependent assignment improves on non-contextual assignment under capacity constraints, in terms of the size of the disagreement regions and the contextual reward gap (Propositions 2.2–2.3), and when it outperforms both individual agents (App. D.3).


[6] Peyré, G., & Cuturi, M. (2019). Computational optimal transport: With applications to data science. Foundations and Trends® in Machine Learning, 11(5–6), 355–607.

Summary

With these works now cited, our contribution is stated more precisely. Each prior line covers part of the problem: population-adaptive L2D [1,2] estimates expertise from labeled data supplied before routing; workload-constrained L2D (Alves et al., 2024; Nguyen et al., 2025; Zhang et al., 2026, in our paper) enforces per-agent capacities but learns expertise offline; and online deferral methods [3, 4] learn from their own decisions, but with a single expert or expert pool under a congestion or cost budget. Combining these changes the problem: under bandit feedback, agent-specific capacity constraints themselves determine which agents' outcomes are observed. We address this directly: our capacity guarantee holds for any reward model (App. G), and our new ablation shows that the constraints supply the exploration a greedy learner otherwise lacks (App. H.9).

Code

Thank you; we agree that reviewers should be able to audit the results. Our code is now available at https://anonymous.4open.science/r/learning_to_assign/ We will release it publicly with the final version.


[6] Peyré, G., & Cuturi, M. (2019). Computational optimal transport: With applications to data science. Foundations and Trends® in Machine Learning, 11(5–6), 355–607.

Thanks for the rebuttal.

My remaining concern is the limited novelty of the revised contribution. Theorem 2.1 is now acknowledged as known, Appendix H.12 establishes the equivalence between the queue update and Euclidean dual mirror descent under rescaling, and Propositions 2.2 & 2.3 appear to follow fairly directly from the established threshold characterization.

The additional capacity analysis and empirical comparisons do indeed strengthen the paper, but I remain unconvinced that they establish a sufficiently substantial advance beyond existing constrained contextual-bandit and primal-dual approaches. I therefore maintain my weak rejection recommendation, with my remaining reservation focused on novelty and significance.

We thank Reviewer UYem for the reply and for acknowledging that the additional capacity analysis and empirical comparisons strengthen the paper.

Queue update and DMD. We respectfully disagree that App. H.12 establishes an equivalence between our method and DMD. It shows only that the two share a price update, which we do not claim as a contribution. As detailed in our response to Reviewer MRow (W1 & Q1), DMD solves a different problem: it has upper budgets and a void action, whereas our capacities are exact and every task must be assigned. To run DMD in our setting, we had to modify it in two ways: learn rewards from bandit feedback, and, since there is no void action, send all remaining tasks to the other agent once an agent’s budget is spent. Our soft queue keeps correcting throughout the stream, so each agent’s share stays close to its target at every point, for any reward model (Theorem G.1(a)). DMD’s budget stop instead meets the capacities only as totals at the end of the horizon, and its window deviation is up to 10 times ours on Bank, with no gain in accuracy. We have revised App. H.12 to state this difference explicitly, replacing the earlier wording that could be read as equivalence.

Propositions 2.2–2.3. We agree that these follow directly from the threshold characterization, and we present them as new direct corollaries as opposed to new technical results. Their role is to express the gain from contextual assignment in measurable quantities: the size of the disagreement regions and the average reward gap within them. Our experiments match these predictions. On Camelyon17, the gain is largest at α1=0.5\alpha_1=0.5, the capacity closest to full exploitation of disagreement (Prop. 2.2), and shrinks as the capacity moves away from it. On the tabular datasets, where one agent dominates, the gain comes from choosing which tasks the weaker agent receives (Prop. 2.3).

Significance. Our contribution is the problem and what we learn about it, not a new update rule. We study learning multiple agents’ context-dependent expertise from bandit feedback while enforcing exact per-agent capacities. In this setting, the capacities determine which agents’ outcomes are observed, and we show that they supply the exploration a greedy learner otherwise lacks (App. H.9). In constrained contextual bandits such as CBwK (Agrawal & Devanur, 2016) and DMD (Balseiro et al., 2020), budgets only cap consumption, a null action is available, and exploration has to come from the learner. We validate this across eight datasets with ML, LLM, and human agents.

The initial review noted that related work was the main issue affecting the assessment, and we have addressed each of the five suggested papers. To our knowledge, no existing constrained-bandit or primal–dual method addresses this realistic setting, where every task must be assigned under exact per-agent capacities and agents learn expertise online. We would be glad to compare against it if the reviewer could point us to one.

Reviewer_8ic5OpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors present an approach for learning to assign prediction tasks to agents with varied expertise and capacity constraints. The novelty of the approach is that agents' context-dependent expertise and an assignment policy are learned jointly online through repeated interactions, under known, agent-specific capacity limits. The approach is operationalized by building on the contextual multi-armed bandit framework, where tasks arrive sequentially and the assignment policy is updated online based on the assigned task outcomes.

Critical strengths

The study maintains strong scientific rigor through a thorough evaluation process with eight tabular, text, and image datasets. All four contextual policies evaluated here reduce error relative to an ablated non-contextual baseline.

The manuscript is well written, and the formalization is clearly articulated.

Critical weaknesses

The authors hypothesize that the similar performance of Thompson sampling and greedy approaches (discussed in line 396 of pg 8) is 'likely a result of the implicit exploration induced by the capacity constraints', but do not test the hypothesis with experiments. Appendix H.8 already runs tree-based greedy at η=0\eta = 0 (no capacity penalty); adding Thompson sampling there would test the hypothesis, since greedy should fall behind Thompson sampling if the constraints supply the exploration.

I am also curious how the authors would place the current work in the context of: Liu, X., Li, B., Shi, P., & Ying, L. (2021). An efficient pessimistic-optimistic algorithm for stochastic linear bandits with general constraints. Advances in Neural Information Processing Systems, 34, 24075-24086. I would recommend including this citation and relating it to the current work since it seems highly relevant here.

Questions for authors

See weaknesses

2 comments

We thank the reviewer 8ic5 for recognizing the scientific rigor and thorough evaluation across tabular, text, and image datasets, and the clear writing and formalization. We also appreciate the two suggestions, which have strengthened the paper. Below, we test the implicit-exploration hypothesis directly with the suggested greedy vs. Thompson sampling ablation at η=0\eta = 0, and we position our work relative to Liu et al. (2021), which we now cite.

W1 Greedy vs. Thompson sampling at η=0\eta = 0

We agree and directly tested this hypothesis by running Thompson Sampling (TS) and Greedy on Camelyon17 without capacity constraints (η=0\eta = 0) across 10 randomized streams.

  • Logistic model: Removing capacity pressure makes Greedy clearly worse than TS (error rate 0.226±0.0230.226 \pm 0.023 vs. 0.166±0.0010.166 \pm 0.001. Without capacity constraints to force routing, Greedy locks onto a single agent in 4 of 10 streams and incurs that agent's standalone error (about 0.31). This supports the hypothesis that capacity constraints supply the exploration Greedy otherwise lacks.

  • Tree-based model: Greedy slightly outperforms TS (0.178 vs. 0.189). We view this as inconclusive, since tree-based Greedy already includes randomization through bootstrap refits.

  • Broader Evaluation: Runs on CivilComments, ImageNet-16H, and MMLU show a similar pattern for the logistic model.

We have added these results to App. H.9 and referenced them in Section 4.1.

W2 Relation to Liu et al., 2021

Thank you for the pointer. Liu et al. (2021) is indeed relevant, and we now cite it in Section 3.2 and in the Related Work section. Both works combine a reward estimate with virtual queues that act as dynamic Lagrange multipliers, and our capacity constraints can be written in their formulation. The key difference is that their guarantees require the constraints to be satisfiable with slack (Slater’s condition). In our setting, every task must be assigned and the capacities sum to one, so no slack exists and their bounds do not apply. We instead exploit the specific form of the capacity costs (i.e., each task goes to exactly one agent and the capacities sum to one). In Appendix G (Theorem G.1(a)), we prove that, for any η>0\eta>0, each agent's realized assignment share is deterministically within (A−1)Cη/T(A-1)C_\eta/T of its target at every horizon TT, i.e., O(1/T)O(1/T) for fixed η\eta, for any reward estimate in [0,1][0,1], including the greedy and tree-based policies we deploy.

In short, Liu et al. guarantee that constraints hold in expectation or with high probability for linear rewards when every constraint has slack, whereas our capacities sum to one and so have no slack, and we still guarantee that the realized assignment share of every agent stays within O(1/T)O(1/T) of its target on every sample path, for any reward model we deploy. The two works also differ in focus. Liu et al. develop regret and constraint-violation guarantees for linear rewards with LinUCB. Our work studies context-dependent agent expertise empirically, using logistic and tree-based models across image, tabular, and text tasks with ML classifiers, LLMs, and human annotators.

We thank Reviewer 8ic5 for your constructive feedback, which has helped us substantially improve the paper.

As the author–reviewer discussion period ends soon, we wanted to ask whether you have any remaining questions or concerns. We would be happy to provide further clarification.

We hope our responses have addressed your concerns. If so, we would be grateful if you would consider updating your rating.

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

The paper studies how to route incoming prediction tasks to one of several agents (human experts, classifiers or LLMs) when each agent must handle a fixed share of the workload. It first shows that, if each agent’s accuracy were known, the best policy assigns each task to the agent with the highest accuracy after subtracting an agent-specific “price” that enforces its workload share, and that the benefit over random assignment depends on how much, and where, the agents disagree. For the realistic case where accuracies are unknown, it learns them online with logistic or tree-based models (using greedy or Thompson-sampling selection) and enforces the workload shares with a queue-based mechanism, with bounds on capacity violation and regret. Experiments on eight datasets (four tabular, two image and two text), image and text datasets show that context-aware routing consistently beats capacity-matched random assignment, and that greedy selection performs as well as Thompson sampling.

Critical strengths
  1. A relevant, well-posed problem with an interpretable solution. Routing tasks under per-agent workload quotas while learning context-dependent expertise online is a realistic human–AI setting. The shadow-price view and queue controller give a simple rule, and capacity tracking is verified carefully.
  2. Breadth and transparency. Eight datasets with human, ML and LLM agents, several extensions, and a candid discussion of where the theory does not cover the deployed algorithms.
Critical weaknesses
  1. Positioning and baselines (main reason for my score). Theorem 2.1 is the known solution of semi-discrete optimal transport, which is not cited, and the online problem is an instance of contextual bandits with knapsacks and online primal–dual allocation (Agrawal & Devanur, 2016; Balseiro et al., 2020), which Sec. 5 mislabels as fair-bandit work. Yet the only online baseline is random assignment, which the theory already guarantees is worse. Without a constrained-bandit or plug-in baseline and an offline capacity-constrained benchmark, the experiments show that context helps, not that this method is a good way to use it.

  2. The experiments limit the complementarity claim. Contexts are one-dimensional on three of the four non-tabular datasets, and ImageNet16H repeats the same 200 images ten times. On the tabular datasets, the unconstrained oracle barely beats Agent 1 alone, so the gains mostly come from choosing which tasks a weaker, forced agent receives. Agent construction also mixes model family, class weighting and feature split, and the claim that capacity constraints let greedy match Thompson sampling is not ablated.

Questions for authors

Questions

  1. How does the method compare with a constrained-bandit baseline and a simple plug-in policy that learns accuracies and thresholds at the capacity quantile? Adding the offline capacity-constrained curve would also help. Convincing results here would raise my score.
  2. On Bank, why does the XGBoost agent reach only 0.53 accuracy, well below the majority-class rate? Which seed is shown in Fig. 3a, given that other seeds in Table 3 show much smaller gains?

Clarifications(Will not affect score) 3. Was PCA fitted on the evaluation stream, and does the logistic model include an intercept? 4. Does greedy fall behind Thompson sampling without capacity pressure (η = 0)?

6 comments
AuthorsOpenReview ↗

Positioning and Additional Comparisons

We thank Reviewer MRow for recognizing the relevance of the problem, the interpretable shadow-price solution with carefully verified capacity tracking, and the breadth and transparency of our evaluation. We also appreciate the constructive points raised, which have improved the paper. In summary, we now position Theorem 2.1 and the online problem within the semi-discrete optimal-transport and constrained-bandit literature, and we add three comparisons: a plug-in policy, dual mirror descent, and an offline capacity-constrained router. We also clarify the source of the gains and the experimental setup, correct the agent-labeling typo, and add the greedy vs. Thompson sampling ablation. We address each point below.

W1 & Q1 Positioning and baselines

We thank the reviewer for pointing out connections to related methods that we had not made in the paper. In short, we now cite this literature (details below) and we added the three comparisons requested (full details in App. H.12): a plug-in policy, dual mirror descent (DMD), and an offline capacity-constrained router. The plug-in and DMD are boundary cases of capacity enforcement: the plug-in never corrects for realized assignments, while DMD enforces hard budgets that bind only at the end of the horizon. Across all comparisons, our method meets the capacities most closely in every setting without giving up accuracy. Where DMD has lower error, the difference is not statistically significant. Where the plug-in has lower error, its capacity deviation is much higher than ours. Learning expertise online costs at most 1.7 percentage points relative to the offline router, which is given both agents' labels in advance. We give details on each point below.

Positioning

Theorem 2.1. Thank you for pointing out that Theorem 2.1 is a known result. We now cite it as the solution of semi-discrete optimal transport [1], note related threshold rules in learning to defer [2], and keep the proof for completeness. Our contribution in Section 2 is Propositions 2.2–2.3, which characterize when and by how much context-dependent assignment improves on the individual agents under capacity constraints.

Section 5. We agree that the online problem is closely related to contextual bandits with knapsacks and online primal–dual allocation. We removed the fair-bandit label and now cite Agrawal & Devanur (2016) [3] and Balseiro et al. (2020) [4] in Related Work. One key difference is that our capacities are exact targets and every task must be assigned, whereas [3] and [4] impose upper budgets and allow a null action in which the task is not assigned to any agent. We adapted dual mirror descent from [4] to our setting and added it as a comparison.

Additional comparisons (App. H.12).

We first describe how we interpreted each of your suggestions; please let us know if we misread any of them.

Simple plug-in policy. We read this as an online version of the threshold rule in Theorem 2.1. It estimates the accuracy gap Δ^t(xt)=μ^2,t(xt)−μ^1,t(xt)\hat\Delta_t(x_t)=\hat\mu_{2,t}(x_t)-\hat\mu_{1,t}(x_t) and assigns Agent 2 if Δ^t(xt)\hat\Delta_t(x_t) exceeds the empirical (1−α2)(1-\alpha_2)-quantile of {Δ^s(xs)}s≤t\{\hat\Delta_s(x_s)\}_{s\le t}. It targets the capacities only through this threshold and has no queue or other correction based on realized assignments, so it does not enforce the capacity constraints.

Constrained-bandit comparison. We use DMD [4] with both its Euclidean and entropic updates and step size 1/T1/\sqrt{T}. With known capacity consumption, as here, it has the same primal–dual structure as the algorithm of [3]: each task goes to the agent with the highest estimated accuracy minus a capacity price, and the prices are updated by online mirror descent on realized assignments relative to the capacities. We made two adaptations: (1) rewards are learned from bandit feedback, and (2) since there is no null action, once an agent has received its budget of αaT\alpha_a T tasks, it is masked, and all remaining tasks go to the other agent.

Offline capacity-constrained benchmark. We read this as a router that knows agent expertise before deployment. We fit it on half of the held-out tasks using both agents' labels, then freeze it and run it on the other half under the same capacities and queue.

We ran comparisons on Bank and Camelyon17, using the same 10 task streams and the same online reward models (logistic and tree, learned from bandit feedback) for all online methods, so differences come only from the allocation rule.

Results. Tables R1–R3 show Bank with the logistic reward model; results with the tree model and on Camelyon17 are similar (App. H.12).

Table R1 (Bank, logistic). Error rate, % (standard error), over 10 paired task streams. Bold: lowest error per column.

Methodα1=0.2\alpha_1=0.20.40.40.50.50.60.60.80.8
Ours, η=A/T\eta=\sqrt{A/T}28.27 (0.05)14.70 (0.08)12.57 (0.07)11.60 (0.09)10.00 (0.07)
DMD, Euclidean28.83 (0.05)14.72 (0.08)12.65 (0.07)11.75 (0.07)10.03 (0.07)
DMD, entropic29.55 (0.06)14.62 (0.09)12.58 (0.11)11.90 (0.14)10.22 (0.07)
Online plug-in27.60 (0.14)16.22 (0.18)13.41 (0.11)12.01 (0.08)10.45 (0.11)

Table R2 (Bank, logistic). Maximum window deviation from the target capacity: the largest gap between the share of tasks assigned to Agent 1 within any 200 consecutive tasks and α1\alpha_1, excluding windows that end within the first 1,000 tasks, maximized over the 10 streams. Bold: lowest deviation per column.

Methodα1=0.2\alpha_1=0.20.40.40.50.50.60.60.80.8
Ours, η=A/T\eta=\sqrt{A/T}0.0550.0550.0450.0550.045
DMD, Euclidean0.2000.2900.2100.2000.140
DMD, entropic0.2000.4000.3650.5450.220
Online plug-in0.1500.2100.2550.2700.210
  1. Our method meets the capacities most closely without giving up accuracy. At η=A/T\eta=\sqrt{A/T} (the same 1/T1/\sqrt{T} order as DMD's step size), our error is lower than or statistically indistinguishable from both DMD variants at every capacity (Table R1), and no other method has a smaller capacity deviation than ours at any capacity (Table R2). In Table R2, DMD's deviation is 3-10 times ours because it enforces capacity only as a total budget: once an agent's budget is exhausted, every remaining task goes to the other agent regardless of context, affecting up to 9% of the stream at α1=0.2\alpha_1=0.2. The plug-in has lower error at α1=0.2\alpha_1=0.2, but its threshold receives no feedback on realized assignments, so its capacity deviation is much higher than ours and it does not meet the capacities.

Table R3 (Bank, logistic). Our online policy vs. the offline capacity-constrained router, both with η=0.5\eta=0.5 (the main-text setting, which prioritizes capacity tracking, so errors are higher than for η=A/T\eta=\sqrt{A/T} in Table R1), over 10 paired task streams. The router is fit on one half of the held-out tasks using both agents' labels and then frozen; both methods are evaluated on the other half. Error rate, % (standard error).

Methodα1=0.2\alpha_1=0.20.40.40.50.50.60.60.80.8
Ours (online)32.13 (0.09)22.80 (0.17)19.62 (0.07)16.45 (0.07)11.89 (0.09)
Offline router31.81 (0.05)21.85 (0.13)18.14 (0.11)14.77 (0.03)10.35 (0.02)
  1. Learning expertise online costs little. An offline capacity-constrained router that knows agent expertise before deployment is at most 1.7 percentage points more accurate than our policy, which learns from bandit feedback alone (Table R3).

Together with the comparison to random assignment, which isolates the value of context, these comparisons show that our method is a competitive way to use it.


[1] Peyré, G., & Cuturi, M. (2019). Computational optimal transport: With applications to data science. Foundations and Trends® in Machine Learning, 11(5–6), 355–607.

[2] Narasimhan, H., Jitkrittum, W., Menon, A. K., Rawat, A., & Kumar, S. (2022). Post-hoc estimators for learning to defer to an expert. Advances in Neural Information Processing Systems, 35, 29292–29304.

[3] Agrawal, S., & Devanur, N. (2016). Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 29.

[4] Balseiro, S., Lu, H., & Mirrokni, V. (2020). Dual mirror descent for online allocation problems. In Proceedings of the 37th International Conference on Machine Learning, PMLR 119, 613–623.

Comments on the paper

1 comment

We thank the reviewers for their constructive feedback and are glad they recognized the well-posed problem (MRow), the breadth of the evaluation (MRow, 8ic5), the clear writing (8ic5), and the rigorous mathematics (UYem). The main points we addressed are:

  • Positioning [MRow, UYem, 8ic5]. We now cite Theorem 2.1 as a known optimal-transport result and add more constrained-bandit and learning-to-defer work. Note that none of this other work learns multiple agents' expertise online while enforcing agent-specific capacities.

  • Comparisons [MRow]. We added three new comparisons: a plug-in policy, dual mirror descent, and an offline router (App. H.12). Our method meets the capacities most closely in all settings while matching or beating DMD's error. The plug-in is more accurate at some capacities, but misses the target capacities significantly more often than our methods, and hence, it does not solve the constrained problem we study. We show that learning expertise online costs little relative to the offline router, which is given both agents' labels in advance.

  • Greedy vs. Thompson sampling [MRow, 8ic5]. Without capacity constraints, greedy falls behind Thompson sampling, supporting our hypothesis that capacities supply exploration (App. H.9).

  • Robustness [MRow]. Gains hold across all seeds and feature splits (App. H.4, H.11).

  • Code [UYem]. Code to reproduce all our results, figures and tables is now available: https://anonymous.4open.science/r/learning_to_assign/.

Details are in the revised paper, where new and revised content is marked in blue.

We hope these revisions address the reviewers' concerns and would be grateful if they are taken into account in the final assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.