A Learning-Augmented Approach to Online Allocation Problems

We thank the reviewer for the careful review. Below, we address each question in detail.

Q: The paper could benefit from another round of polishing and it current form at is less ready for publication, since the current structure is a bit hard to follow with respect to the logic connections. For example, the introduction part focuses on heavily on the applications, but the applications mentioned in Section 5 do not match these applications exactly. One can get easily lost in the last two paragraphs before the Organization in Introduction. These two paragraphs do not help introducing this paper and its main theme. Also, merging the problem formulation with the contributions is somewhat confusing. Having a separate section of the problem formulation would make things clearer.

The last two paragraphs before the organization in the introduction are integral to the paper.

The penultimate paragraph motivates the maximization problems (MaxMin, Nash Social Welfare, $p$‑means, etc.): it explains the “value to agents” viewpoint and asserts that our vector framework yields $(1-\varepsilon)$ guarantees there, contrasting with strong lower bounds without learning. This constitutes one half of the results in this paper, complementing the results for the minimization problems. Due to space limitations, the maximization proofs are in Appendix F. One of the two applications in Section 5, Nash Social Welfare, falls in the maximization category.

The final paragraph describes the learnability core: we prove the existence of bounded, robust parameters—scaling with the number of coordinates and $\varepsilon$—and use this to obtain PAC learnability and stability to small estimation noise. Again, these are key contributions of the paper. The detailed proofs for learnability are in Appendix C.

Q: The proof of Lemma 4.4 is missing, or I may miss something. It would be helpful if the authors could point to the place.

After the statement of Lemma 4.4, the entire remaining part of Section 4 is dedicated to the proof of Lemma 4.4. The sentence “The remainder of this section gives a proof of Lemma 4.4” opens a proof sketch, and the proof is concluded at the end of the section (bottom of page 8, lines 311–314).

Q: MaxMin and MinMax are not defined with mathematic rigor.

MaxMin and MinMax are formally defined in lines 211–214. MinMax is the minimization of $f(v)=\max_{i\in[d]} v_i$, and MaxMin is the maximization of $f(v)=\min_{i\in[d]} v_i$.

Q: I assume that the balanced instance is $\tilde{I}$ instead of $I$ in the statements of the theorems.

We use the notation $I(\tilde{v},\tilde{k})$ for the transformed (balanced) instance, i.e., it is the instance with inputs $\tilde{v},\tilde{k}$.

Q: The paper seems to over claim the contributions in the introduction, since essentially the results hold for balanced instances, instead of all the instances in the online resource allocation problems. It would be helpful to clarify these, to avoid ambiguity.

We believe there is a misunderstanding of the result. We emphasize that our algorithm applies to all instances and not just balanced instances. The preprocessing that converts a general instance to a balanced instance is a part of our overall online algorithm. Conceptually, it removes options that should not be considered by the allocation. Subsequently, the algorithm for balanced instances is applied to the transformed instance and this constitutes the final solution for the original instance. Once again, we emphasize that the conversion to balanced instances is an algorithmic technique and not a restriction on the input, and the final solution and bounds are for the original instance, not the transformed (balanced) instance.

In fact, this idea of preprocessing is also used in prior work such as [25]. To see why this is necessary, consider an instance of a makespan minimization problem where one option has $p_{i_1,j}=1$ and $p_{i_2,j}\to\infty$. Then, without preprocessing, we must have $\alpha_{i_1}/\alpha_{i_2}\to\infty$, making the parameter space unbounded.

Q: the concept of agents do not seem to appear in the general problem formulation. This necessitates further clarifications.

Our general formulation is stated in terms of resource coordinates. The familiar notion of agents is simply a special case: in maximization or fairness settings (e.g., Nash social welfare) we identify each coordinate with one agent, so the cumulative value of coordinate $i$ is exactly agent $i$’s utility. We already introduce this agent view in the Introduction and use it again in Section 5; in the revision we will add a brief sentence in the formal problem‑formulation section to make this mapping explicit and avoid any ambiguity.

We are glad the reviewer liked the paper and appreciate the insightful comments. Below, we address each question in detail.

Q: Can you be more precise on the consistency robustness trade-off? Specifically, how is the confidence parameter $\lambda$ chosen and what is the dependence on the error of the learned parameter vector? Is there an adaptive mechanism to set the confidence parameter dynamically based on the perceived accuracy of predictions, rather than a fixed value?

The use of a confidence parameter follows standard practice in learning-augmented algorithms, see e.g. [11], [31], and other papers such as

Gollapudi, S., & Panigrahi, D. (2019). Online algorithms for rent-or-buy with expert advice. ICML 2019.

As in prior work, the confidence parameter is application-dependent and typically tuned from data—for example, based on the number of prior samples or the discrepancy between predicted and actual performance on a validation window. It balances consistency (staying close to the learned policy) with robustness (falling back to a worst-case baseline). Fully automatic, near-optimal tuning is precluded by lower bounds without further assumptions. In practice, adaptive schemes work well: by tracking prediction error over time, the confidence level can be adjusted dynamically.

Q: Could the convex programming formulation be adapted to handle different types of constraints or other settings beyond allocation problems?

Yes, we believe our techniques can extend to broader classes of problems. Our max‑entropy template should extend cleanly to additional linear side constraints, and with appropriate smoothing or convex conjugates it may also handle certain separable concave terms (e.g., diminishing‑returns utilities). Formal guarantees would need a careful re‑derivation of the dual sensitivity bounds, so this is a good follow‑up direction for future work.

W: On the other hand, I would like to see more justification for the “small items assumption”, which is required both for learnability of the predictions and the rounding of the fractional solutions.

Q: For problems requiring integral solutions, how significant is the "small items assumption" in practice, and what are the implications if it doesn't hold perfectly?

In real systems, “small items” are the norm or can be achieved with light batching. The atomic units—packets or flowlets in networks, requests or shards in services, impressions in online advertising—individually have small impact relative to total capacity. So, splitting traffic or budget across options already operates at fine granularity. Operators also aggregate over short time windows to smooth variability; this makes each decision step small enough that averages are stable, learning from samples is reliable, and randomized implementation (hashing, probabilistic routing, paced spending) stays close to targets.

If the small items assumption doesn't hold perfectly, then the approximation factor of our algorithm degrades gracefully with increase in size of the largest item. Furthermore, when there’s a light tail of large items, those few can be handled separately, e.g. by reserving capacity, while the vast majority remain small, preserving both learnability and concentration in practice.

Indeed, the small items assumption is quite standard in the literature for allocation problems, see e.g.,

Mehta, A., Saberi, A., Vazirani, U., & Vazirani, V. (2007). Adwords and generalized online matching. Journal of the ACM.

Devanur, N. R. & Hayes, T. P. (2009). The adwords problem: online keyword matching with budgeted bidders under random permutations. EC 2009.

Gollapudi, S., & Panigrahi, D. (2014). Fair Allocation in Online Markets. CIKM 2014.

Agrawal, S., & Devanur, N. R. (2014). Fast algorithms for online stochastic convex programming. SODA 2014.

We thank the reviewer for their careful reading of our manuscript and for the insightful feedback. Below, we address each question and weakness raised by the reviewer in detail.

Q: Can you provide concrete examples where fractional solutions are directly applicable without rounding? The paper's main guarantees are for fractional solutions, yet most applications (routing, scheduling) require integral decisions.

We give examples of applications where fractional solutions are directly applicable:

• Traffic engineering / SDN: requests (or flows) are commonly split across multiple paths; fractional solutions translate directly to per‑path splitting ratios, see e.g.,

Salimifard, K., & Bigharaz, S. (2022). The multicommodity network flow problem: state of the art classification, applications, and solution methods.

Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., & Naor, J. (2006). A general approach to online network optimization problems. ACM Transactions on Algorithms.

• Cloud and datacenter load balancing: tasks/data shards are shared across machines or queues using probabilistic routing; fractional rates are implemented by hashing or randomized assignment, see e.g., [17], [23].

• Online advertising / budget pacing: budgets are split fractionally across channels/segments; the objective is smooth (Nash welfare or $\ell_p$) over aggregate spends, see e.g., [24] and

Buchbinder, N., Jain, K., & Naor, J. (2007). Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms.

Moreover, there has been prior work on learning-augmented algorithms that obtain fractional solutions, see e.g.,

Anand, K., Ge, R., Kumar, A., & Panigrahi, D. (2022). Online algorithms with multiple predictions. In International Conference on Machine Learning.

W: The paper solves fractional problems, with integral solutions in the appendix. The (1±ε) guarantees are relative to fractional problems, not integral ones.

We have already discussed applications where fractional solutions can be directly applied. For applications that require integral solutions, we provide a rounding algorithm in Appendix D. We emphasize that after rounding, we get a $(1\pm \varepsilon)$ approximation for integral solutions as well under the standard small items assumption. In real systems, “small items” are typical or can be enforced through light batching. The atomic units—packets or flowlets in networks, requests or shards in services, impressions in online advertising—each have negligible impact relative to total capacity. Consequently, traffic or budget is already split across options at fine granularity. In practice, operators also aggregate decisions over short time windows to smooth variability; this keeps each step small enough that averages remain stable, sampling‑based learning is reliable, and randomized implementations (hashing, probabilistic routing, paced spending) track their targets closely. If a light tail of large items exists, those few can be handled explicitly—either by reserving capacity or by routing them individually—while the vast majority stay small, preserving both learnability and concentration guarantees.

Q: The three-step preprocessing appears quite aggressive, potentially changing the instance structure significantly. For example, provide an example where the algorithm fails without preprocessing? Also, it's helpful to quantify how much the preprocessing changes typical instances (what fraction of options are removed in Step 2)?

W: There seems to be a mismatch of what the paper claims to contribute. The three-step balanced instance transformation also requires better motivation. It is essential to bound the exponential terms but deviate from reality it claims to model.

We believe there is a misunderstanding of the result. We emphasize that our algorithm applies to all instances and not just balanced instances. The preprocessing that converts a general instance to a balanced instance is a part of our overall online algorithm. Conceptually, it removes options that should not be considered by the allocation. Subsequently, the algorithm for balanced instances is applied to the transformed instance and this constitutes the final solution for the original instance. Once again, we emphasize that the conversion to balanced instances is an algorithmic technique and not a restriction on the input, and the final solution and bounds are for the original instance, not the transformed (balanced) instance.

In fact, this idea of preprocessing is also used in prior work such as [25]. To see why this is necessary, consider an instance of a makespan minimization problem where one option has $p_{i_1,j}=1$ and $p_{i_2,j}\to\infty$. Then, without preprocessing, we must have $\alpha_{i_1}/\alpha_{i_2}\to\infty$, making the parameter space unbounded.

Q: Provide the explicit algorithm for learning α from samples?

In the appendix (lines 591–594), we present the learning algorithm: an ERM procedure that outputs the parameter values on the discrete net with minimum empirical loss.

W: The convex program requires knowing the entire instance, making the "learning" aspect somewhat artificial.

Finally, the convex program is used in the analysis to establish the existence of suitable parameters and to derive tight, coordinate-wise sensitivity bounds. It is not part of the online algorithm, which simply applies a fixed exponential rule using a learned vector $\alpha$. As shown in the paper, $\alpha$ can be estimated from data via finite-class empirical risk minimization (ERM) over a bounded net constructed from the sensitivity bounds. So, the learning is via the use of ERM on data as usual, but learnability of the parameters and the fact that the learned parameters yield a near-optimal solution are established via the convex program.

We are glad that the reviewer liked the paper and appreciate the insightful comments. Below, we address each question in detail and conclude with a concise summary of the main differences between our work and [17] as requested by the reviewer.

Q: What is the difference between the PAC learnability proof (Theorem 2.2) from the learnability bounds in [17]?

Both works establish PAC learnability by restricting to a finite hypothesis class and applying standard finite‑class generalization bounds. The crux in both settings is to bound the parameter space. In prior work [17, 22, 25], a simple rescaling of the learned parameters yields an equivalent (or near‑equivalent) allocation, so one can cap parameter magnitudes with only a negligible loss. In our vector setting, this rescaling trick fails. Instead, we bound the parameters via a max‑entropy dual and a coordinate‑wise sensitivity analysis.

Q: What is the main technical difference between the problems that cannot be handled by the framework in [17] vs the current paper? The description that [17] cannot handle general vector needs explanation: one way to interpret the divisible weights p_{i, j} in [17] is to view it as a d-dimensional vector (one per agent) that is received each time an item j appears.

In [17], for each arriving item $j$, each option assigns it to a single agent $i$ with value/cost $p_{i,j}$. Our paper is more general. Here, for each arriving item $j$, each option $k$ corresponds to an entire vector $v_{j,k}\in\mathbb{R}^d_{\ge 0}$ that adds value/cost for multiple agents simultaneously. This captures coupled, multi‑coordinate effects within a single choice. So, [17] is a special case of our setting where each vector has a single non-zero entry. In comparison, we allow “general vectors”. Such a coupled choice is necessary in applications like online routing. Here, each option is a path which adds load on each edge of the path. This can be modeled in our framework by encoding edges as coordinates. For example, suppose there are three edges $e_1,e_2,e_3$ and the feasible path vectors (i.e., the options) are $v_1=(1,1,0)$ and $v_2=(0,0,1)$. (So, one path comprises the first two edges and the second path comprises only the third edge.) Our model can choose between $v_1, v_2$ or a convex combination of these two options. For instance, if one chooses fraction $\tau$ for the first option and fraction $1-\tau$ for the second option, then the load on the edges increases by $(\tau,\tau,1-\tau)$. The model in [17] can only capture the situation where every path is a single edge. If a path has multiple edges, then the options correspond to vectors with multiple non-zero entries, which cannot be captured by the model in [17]. In terms of techniques, [17] uses a form of proportional allocation. Unfortunately, proportional allocation cannot handle coupled, multi-coordinate effects due to general vectors in our setting.

Q: On line 177, the paper says in comparison to [17] "we simplify the previous approaches as well by requiring only a single variable per dimension": it appears that [17] also requires one learned-parameter per dimension d so this needs further clarification.

In our framework, there is a single learned vector over resource coordinates which is also there in [17], but we do not have any global exponent or auxiliary scaling vector which are both present in [17].

Q: Is the fair allocation problem with Nash Social welfare objective already covered by the framework in [17]? What does "matching previous results in [17]" mean on line 154 in the paper.

[17] provides a near‑optimal fractional guarantee for online Nash Social Welfare (NSW) where every option allocates the item to a single agent and adds value to the agent. Our result matches the bounds for this case, but we also generalize it further to options having vector utilities, i.e., where an option can add (possibly different amounts of) value to multiple agents simultaneously. In other words, choosing an option adds a utility vector to the agents. This coupled, multi‑beneficiary setting is captured by our vector framework but is not handled in [17]. We will clarify this in the paper.

In summary, the following are the key differences between our paper and [17]:

1. Scope of the model: [17] is an assignment model in which each item has to be split across agents; our framework handles general vector options that update many coordinates jointly, enabling coupled applications such as online routing and vector‑utility NSW that [17] does not encode.

2. Parameterization: We use a single learned vector over resource coordinates without any auxiliary global exponent or per‑agent scaling, both of the latter being present in [17].

3. Techniques: The rescaling trick used in [17, 22, 25] does not work for vectors; we instead derive parameters from a max‑entropy dual with a coordinate‑wise sensitivity bound giving an explicit box $0 \le \alpha_i \le \tfrac{d^2}{\varepsilon}\log(d/\varepsilon)$, which yields a robust finite net and PAC guarantees. Indeed, the connection that we draw to the max-entropy convex program and the subsequent use of convex programming duality is a novel contribution that we believe does not appear in this line of work prior to our paper.

To highlight these differences, we will add a focused comparison paragraph and a routing example to make the distinction clear.