Fast Iterative Combinatorial Auctions via Deep Reinforcement Learning

Luis F. Paul Tosta; Quinn Arnold; Gianluca Brero

cs.GTOct 22, 2026

Fast Iterative Combinatorial Auctions via Deep Reinforcement Learning

Authors: Luis F. Paul Tosta, Quinn Arnold, Gianluca Brero

Organizations: Bryant University

Abstract

Iterative combinatorial auctions are used in spectrum allocation, transportation, and industrial procurement, but rounds are costly. We introduce FastCombo, a deep reinforcement learning approach to sequential price discovery. Bayesian pricing has sharply reduced auction rounds even against subgradient benchmarks tuned with hindsight for each instance, but relies on a one-step objective and repeated online inference and optimization. We prove that greedily maximizing immediate clearing probability can require arbitrarily more rounds in expectation than an informative policy, even with the true valuation distribution known. FastCombo learns price policies offline, assigning credit to queries for the future decisions they enable and producing each online price update with a single neural-network forward pass. We formulate the objective of minimizing expected rounds to clearing in single-minded auctions as a partially observable Markov decision process and train a recurrent bidder-item graph policy over complete auction trajectories. In a one-item experiment, all five trained policies learn an informative opening, reducing expected rounds from 1.85 to 1.65 relative to the tested Bayesian one-step rule. Across four domains from the Combinatorial Auction Test Suite, FastCombo achieves competitive clearing while reducing measured online price-selection time per auction by a factor of roughly 300-900 relative to the standard Bayesian baseline. These results demonstrate the value of learning sequential price policies for both information acquisition and online computational efficiency.

Figures & tables

Figure 1: Measured training curves from all five original conceptual runs. Left: expected capped rounds under exact profile weights

(.25,.35,.40)

, with failures charged three rounds. Right: clearing probability by round three. Thin lines show individual seeds and the thick line their mean. Dashed references show Bayes

\lambda=1

(1.85) and the analytical optimum (1.65). Each seed contributes all ten saved evaluations, including its terminal actor.

	Arbitrary		Paths		Regions		Scheduling
Method	Clear $\uparrow$	Rounds $\downarrow$	Clear $\uparrow$	Rounds $\downarrow$	Clear $\uparrow$	Rounds $\downarrow$	Clear $\uparrow$	Rounds $\downarrow$
FastCombo	68.74	6.59	95.10	7.95	94.23	4.80	97.59	4.64
Bayes-GEN	71.28	3.45	95.46	4.54	95.54	3.32	98.36	4.86
SG-D	42.46	29.78	80.38	16.93	74.86	21.99	88.28	16.32
SG-I	60.12	18.21	96.64	7.25	92.04	13.37	97.92	9.15
Linear-price ceiling	72.28	—	97.48	—	96.22	—	99.90	—

Table 1: CATS mean clearing (%) and rounds. Rounds use, for each FastCombo seed, the instances cleared by all four methods. Standard errors, paired intervals, and subset sizes are in Appendix Tables 4 and 5 .

Domain	Cost ratio	Clearing diff. (pp)	Capped rounds diff.
Arbitrary	624.0 [550.1, 696.1]	-0.90 [-2.30, -0.10]	3.80 [2.68, 5.04]
Paths	304.0 [226.6, 397.2]	-2.10 [-5.00, -0.10]	4.30 [3.20, 5.54]
Regions	571.7 [497.3, 649.4]	-1.80 [-4.20, -0.20]	2.34 [1.41, 3.43]
Scheduling	871.1 [687.1, 1064.7]	-2.80 [-6.10, -0.30]	0.02 [-1.07, 1.29]

Table 2: Default Bayesian comparison on 100 auctions per domain. Entries show paired 95% intervals from 20,000 joint source-file and FastCombo-seed bootstrap draws. Costs are Bayes/FastCombo; differences are FastCombo minus Bayes; failures cost 50 rounds.

	Arbitrary		Paths		Regions		Scheduling
Method	Clear $\uparrow$	Rounds $\downarrow$	Clear $\uparrow$	Rounds $\downarrow$	Clear $\uparrow$	Rounds $\downarrow$	Clear $\uparrow$	Rounds $\downarrow$
FastCombo	68.74	7.38	95.10	7.40	94.23	5.29	97.59	4.65
Recurrent dense control	56.13	20.95	76.58	21.77	87.64	13.47	90.80	12.63
No recurrence	63.80	9.85	89.66	8.01	91.28	6.29	94.92	5.17

Table 3: Architecture controls: mean clearing (%) and rounds. Clearing averages ten seeds, except no-recurrence Paths (nine). Rounds use instances cleared by all three architectures, with nine matched seeds for Paths and ten elsewhere. These success sets differ from the four-method sets in Table 1 , so FastCombo’s round means also differ. Clearing retains the original full-holdout seed counts. Round uncertainty is in Table 7 ; paired clearing intervals are in Appendix Table 6 .

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: FastCombo architecture, following the numbered stages clockwise. Solid arrows show the public actor: per-item recurrence, two graph passes, shared itemwise decoding, and the fixed price map. Dashed arrows show the training-only privileged critic, which embeds normalized private values before a separate call to the same graph encoder; $z_{t}^{\mathrm{crit}}$ denotes its concatenated graph representation. During training, actor locations and learned state-independent log-scales parameterize a product censored Normal law on $[-1,1]^{m}$ ; evaluation uses the clipped location.

Figure 3: Development clearing over CATS training on the fixed 1,000-instance population. The plotted “exact clearing” metric uses the numerical criterion

G<10^{-3}

. Thin lines show all ten training seeds and the thick line their mean. Diamonds mark the selected checkpoints, crosses mark terminal checkpoints, and the dashed line is the development-population linear-price ceiling. Selection uses development clearing only; final results use a separate holdout.

Domain	FastCombo	Bayes-GEN	SG-D	SG-I	Ceiling	FC $-$ Bayes [95% CI]
Arbitrary	68.74 $\pm$ 0.96	71.28 $\pm$ 0.93	42.46 $\pm$ 0.98	60.12 $\pm$ 1.04	72.28	-2.54 [-3.03, -2.10]
Paths	95.10 $\pm$ 0.42	95.46 $\pm$ 0.37	80.38 $\pm$ 0.71	96.64 $\pm$ 0.35	97.48	-0.36 [-0.87, +0.15]
Regions	94.23 $\pm$ 0.40	95.54 $\pm$ 0.34	74.86 $\pm$ 0.81	92.04 $\pm$ 0.46	96.22	-1.31 [-1.68, -0.95]
Scheduling	97.59 $\pm$ 0.24	98.36 $\pm$ 0.20	88.28 $\pm$ 0.52	97.92 $\pm$ 0.22	99.90	-0.77 [-1.16, -0.39]

Appendix

Table 4: CATS clearing (%; mean

\pm

bootstrap standard error) on the 5,000-instance holdout. The last column gives the paired FastCombo–Bayes difference in percentage points with a pointwise 95% confidence interval. FC denotes FastCombo; CI denotes confidence interval.

Domain	FastCombo	Bayes-GEN	SG-D	SG-I	Common set size [range]
Arbitrary	6.59 $\pm$ 0.18	3.45 $\pm$ 0.07	29.78 $\pm$ 0.26	18.21 $\pm$ 0.27	2113.6 [2108–2118]
Paths	7.95 $\pm$ 0.25	4.54 $\pm$ 0.12	16.93 $\pm$ 0.23	7.25 $\pm$ 0.12	3964.8 [3952–3975]
Regions	4.80 $\pm$ 0.10	3.32 $\pm$ 0.05	21.99 $\pm$ 0.20	13.37 $\pm$ 0.17	3735.2 [3727–3740]
Scheduling	4.64 $\pm$ 0.13	4.86 $\pm$ 0.06	16.32 $\pm$ 0.19	9.15 $\pm$ 0.13	4394.5 [4384–4403]

Appendix

Table 5: Mean rounds on seed-specific common-cleared subsets, with one charged demand query per round. For each FastCombo seed, the subset contains instances cleared by that actor and all three baselines; entries average the ten seed-specific means. Entries are means

\pm

bootstrap standard errors. Bayes-GEN denotes Bayes GEN ; SG-D and SG-I use domain-level and instance-level oracle tuning, respectively. Standard errors use 20,000 paired source-file and training-seed bootstrap resamples, recomputing each selected seed’s common-set mean within each resample. Baselines use the same selected seeds and source files; their errors therefore include holdout variation, not only variation in subset membership. The last column reports the mean subset size and its range.

Alternative	Arbitrary	Paths	Regions	Scheduling
No recurrence	-4.94 [-5.74, -4.15]	-5.33 [-6.13, -4.56]	-2.95 [-3.45, -2.49]	-2.68 [-3.19, -2.19]
No bidder bounds	+0.26 [-0.26, +0.80]	+0.36 [+0.03, +0.70]	+0.16 [-0.16, +0.52]	+0.45 [+0.09, +0.82]
Recurrent non-graph encoder	-12.61 [-14.42, -10.96]	-18.52 [-20.56, -16.48]	-6.60 [-7.62, -5.63]	-6.79 [-7.71, -5.89]
One graph pass (depth 1)	-0.94 [-1.45, -0.48]	-0.64 [-1.11, -0.16]	-0.12 [-0.49, +0.23]	+0.31 [+0.00, +0.66]
Three graph passes (depth 3)	-1.06 [-1.54, -0.58]	-0.10 [-0.57, +0.34]	-0.65 [-1.02, -0.27]	-0.46 [-0.77, -0.17]
Public-information critic	-0.61 [-1.19, -0.02]	-0.14 [-0.62, +0.33]	+0.05 [-0.21, +0.33]	+0.18 [-0.09, +0.47]

Appendix

Table 6: Paired change in clearing at raw gap tolerance

10^{-3}

relative to the final depth-2 architecture (alternative minus final, in percentage points), with pointwise 95% paired source-file and training-seed bootstrap intervals. Graph depth is the number of graph passes. Positive values favor the alternative. References and seed accounting follow Section D .

Domain	FastCombo	Dense	No recurrence
Arbitrary	7.38 [7.08, 7.69]	20.95 [19.23, 22.56]	9.85 [9.09, 10.61]
Paths	7.40 [6.97, 7.90]	21.77 [20.01, 23.24]	8.01 [7.59, 8.50]
Regions	5.29 [5.07, 5.51]	13.47 [12.71, 14.23]	6.29 [5.99, 6.58]
Scheduling	4.65 [4.42, 4.91]	12.63 [11.82, 13.51]	5.17 [4.97, 5.36]

Appendix

Table 7: Rounds on seed-specific three-method common-cleared subsets. Entries show mean and paired percentile 95% bootstrap interval, using 20,000 source-file and matched-seed draws.

Domain	FastCombo	Dense	No recurrence
Arbitrary	22.43 [21.54, 23.31]	33.89 [32.43, 35.21]	25.49 [24.48, 26.48]
Paths	11.92 [11.24, 12.65]	28.51 [26.99, 29.91]	14.01 [13.29, 14.76]
Regions	8.90 [8.40, 9.40]	18.24 [17.23, 19.27]	10.73 [10.15, 11.32]
Scheduling	6.77 [6.37, 7.19]	16.25 [15.42, 17.14]	8.12 [7.73, 8.53]

Appendix

Table 8: Capped mean rounds on all matched-seed auctions, charging failures 50 rounds. Entries show mean and paired percentile 95% bootstrap interval; nine Paths seeds, ten elsewhere.

RL for Combinatorial Optimization

Reinforcement learning for combinatorial optimization learns sequential decisions and search strategies for difficult discrete problems.

See all 106 papers

Jun 28, 2026

Learning to Bid in Discriminatory Auctions with Budget Constraints

We study repeated bidding in multi-unit discriminatory (pay-as-bid) auctions for a single bidder with per-round utility equal to value minus

α

times payment, where

α\in[0,1]

is a cost-of-capital parameter. The bidder aims to maximize cumulative utility over

T

rounds subject to a total budget

B

. The problem is challenging even without budgets: the action space is exponential in

M

, the maximum demand of the bidder and the valuation vector (context) varies over time. Exploiting a decomposition of utility across units, we develop polynomial-time learning algorithms based on shortest paths in a directed acyclic graph, obtaining sublinear regret under both full-information and bandit feedback. In the bandit setting, the regret is independent of the number of contexts due to complete cross-learning: observing the utility of the chosen action under the realized context reveals the utility for the same action under all counterfactual contexts. With budget constraints, when the average normalized per-round budget

ρ=\frac{B}{MT}<1

, we design a coupled primal-dual algorithm in which the DAG-based procedure uses dual-adjusted edge weights for primal updates, while online gradient descent updates the dual variable, yielding

ρ

-approximate sublinear regret. Finally, we give implementations whose per-round time and space are independent of the number of contexts, enabling scalability to large or even infinite context spaces.

Negin Golrezaei, Sourav Sahoo

Sloan School of Management, Massachusetts Institute of Technology · Operations Research Center, Massachusetts Institute of Technology

Game Theory Automated Bidding Contextual Bandits Online Resource Allocation

Ask PDF

May 27, 2026

Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback

We study the problem of learning to bid when the bidder's value is dynamic, i.e., when the current value depends on past outcomes. Specifically, we consider a bidder participating in repeated second-price auctions whose value depends on the time elapsed since their last successful bid, with auctions arriving in continuous time and only aggregated feedback revealed at the end of the horizon. Such a bidder must (1) balance the immediate benefit of winning the current auction against its impact on future values and (2) learn unknown environmental parameters. We derive regret bounds for a class of learning methods that combine plug-in estimators with a differential-equation characterization of the optimal policy, and show that a specific confidence bound algorithm learns the optimal policy with a near optimal regret of

\widetilde{O}(\log N)

for piecewise linear primitives, and

\widetilde{O}(N^{1/3})

for general, smooth primitives, achieving these regrets without explicit randomization. These theoretical results are supported by numerical experiments.

Benjamin Heymann, Otmane Sakhi

Criteo AI Lab

Game Theory Automated Bidding

Ask PDF

Jun 27, 2026

A3M: Adaptive, Adversarial and Multi-Objective Learning for Strategic Bidding in Repeated Auctions

Learning to bid in repeated multi-unit auctions with bandit feedback poses a fundamental challenge. Existing methods often rely on rigid explore-then-exploit schedules, assume stationary adversaries, and optimize solely for bidder utility, thereby limiting adaptability and strategic robustness. To address these limitations, we introduce the A3M framework, which integrates adaptive deep reinforcement learning (DRL), explicit adversarial reasoning, and principled multi-objective reward design for online auction strategy optimization. A3M employs an actor-critic DRL backbone to dynamically balance exploration and exploitation, an opponent model for fictitious play against non-stationary adversaries, and a composite reward function to jointly maximize utility, auctioneer revenue, and fairness. We provide the first comprehensive empirical evaluation of this integrated approach against established baselines in both discriminatory and uniform price auctions. Results show that A3M reduces final regret by 30--40% in standard settings, maintains robust performance against adversarial strategy shifts, scales favorably with the number of units

K

, and enables tunable multi-objective trade-offs. An extensive ablation study confirms the necessity of each core component. Our work establishes A3M as a powerful and flexible framework for learning in complex auction environments.

Junhan Li, Yuxin Zhang, Haoran Wang +1

Department of Computer Science Nanjing University

Multi-Objective Reinforcement Learning Game Theory Automated Bidding Reward Design for RL

Ask PDF

Abstract

RL for Combinatorial Optimization

Explore similar work

Learning to Bid in Discriminatory Auctions with Budget Constraints

Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback

A3M: Adaptive, Adversarial and Multi-Objective Learning for Strategic Bidding in Repeated Auctions