CS Paper Radar

Fast Iterative Combinatorial Auctions via Deep Reinforcement Learning

Luis F. Paul Tosta, Quinn Arnold, Gianluca Brero

cs.GT cs.LG ·submitted 2026-10-22 03:32 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Reinforcement Learning with Hawkes-Structured Networks for Market Making

cs.LG q-fin.CP ·2026-10-12 ·Fernando Acero, Philipp Plank, Yufei Zhang
published similarity 0.68
Abstract · Accepted to ACM ICAIF 2026

Market making under realistic order-flow dynamics is challenging due to the clustered, self-exciting nature of order arrivals, which are naturally modeled by non-Markovian Hawkes processes. We propose a model-free reinforcement learning (RL) framework for market making with general Hawkes order-flow dynamics. We first establish non-asymptotic performance bounds that quantify the loss incurred by approximating the infinite-dimensional Hawkes state using a finite collection of exponentially weighted features. Guided by this analysis, we introduce the Hawkes-Structured Network (HSN), a novel neural architecture that encodes historical order flow through a learnable mixture-of-exponentials filter. HSN is trained end-to-end using model-free RL, jointly optimizing the feature representation and quoting policy directly from reward feedback. Experiments on single- and multi-asset market-making problems with mixture-of-exponentials, power-law, and regime-switching kernels demonstrate that HSN outperforms general-purpose neural architectures, achieving higher trading rewards while implicitly recovering the underlying order-flow intensities.

0.16

Fine-Tuning Autobidders with Group Relative Policy Optimization

cs.GT ·2026-08-28 ·Anton Safin, Alexandra Khirianova, Andrey Pudovikov, Aleksandr Katrutsa, Egor Samosvat
similarity 0.66
Abstract

Automated bidding (autobidding) is a core component of modern online advertising systems. Within this component, advertisers delegate sequential bid decisions to algorithms that must maximize campaign value while adhering to constraints such as a limited budget and a target cost-per-click (CPC). One of the approaches to resolve the autobidding problem is to formulate it as a Markov decision process and use reinforcement learning (RL) to train a bid generation function. The standard RL framework is actor-critic, which consists of an actor network that generates actions and a critic network that estimates the value of those actions. In our setting, the action is typically a bid or related pacing multiplier, and the value is the expected return from the auction given the bid. However, the alternating training of actor-critic RL models leads to instability and reduced robustness to noise. To address these issues, we adapt the Group Relative Policy Optimization (GRPO) framework to the autobidding setting. This framework is a \emph{critic-free} policy-gradient method originally developed for large language model post-training, where the ground-truth target is unknown. The autobidding setting shares this property, since the optimal bid is unknown in advance. Moreover, GRPO in the LLM domain is used to fine-tune the pre-trained model, and we use the same technique to enhance the performance of the strong heuristic baseline. We empirically compare Autobidding GRPO with actor-critic models, simple heuristics, and controller-based methods on the BAT, iPinYou, and AuctionNet benchmarks. Extensive experiments show that Autobidding GRPO consistently outperforms baselines in clicks and is the best or second-best method in conversion volume.

0.20

Learning to Sell: Reinforcement Learning for Strategic Large Language Model Agents in Multi-Product Markets

cs.AI ·2026-09-27 ·Shuze Daniel Liu, Claire Chen, Jiuqi Wang, David Simchi-Levi, Thorsten Joachims
similarity 0.65
Abstract

Autonomous large language model (LLM) agents operating in multi-product markets must make sequential decisions under information asymmetry and resource constraints. We develop a machine learning approach for training such agents to act effectively as sellers in a multi-item bargaining environment, where a seller concurrently negotiates a catalog of substitutable assets across a pool of independent buyers. Buyers hold private, heterogeneous valuations across products, and each can purchase at most one item. Facing limits on total communication turns, the seller must dynamically match buyers with the most profitable products considering their private valuations, while strategically allocating its limited interaction budget toward combinations of greater potential value. We formalize this problem as a Partially Observable Markov Decision Process using a structured, four-part message protocol that maps natural language into a parsable and regulated decision space. Using this formalization, we design a post-training method using Reinforcement Learning from Verifiable Rewards (RLVR). To evaluate this framework, we construct a multidimensional metric suite that quantifies constraint adherence, seller surplus extraction, and allocation quality. Our trained seller agent learns to match limited inventory to buyers more effectively, matching or outperforming trillion-parameter frontier models in both seller surplus extraction and buyer-product allocation quality. Finally, these learned strategies generalize robustly to unseen market structures, correlated valuation distributions, and price ranges not encountered during training.

0.35

Extending Myerson's Optimal Auctions to Correlated Bidders via Neural Network Interpolation

cs.GT cs.LGecon.TH ·2026-10-16 ·Mingyu Guo, Jiayuan Liu, Vincent Conitzer
top venuetheory similarity 0.65
Abstract · Accepted at NeurIPS 2026

We aim to design revenue-maximizing single-item auctions that are deterministic, strategy-proof, and ex post individually rational --- the quintessential fundamental model for optimal mechanism design. While Myerson's seminal work solved this model for independent bidders, straightforward extensions to correlated settings often result in non-monotonic, and therefore non-strategy-proof allocations. Critically, optimal allocation design for correlated bidders is NP-hard to approximate, rendering theoretical optimality guarantees in this domain computationally intractable. We establish a new standard of empirical rigor for this theoretically hard model by proposing an empirical pipeline. We synthesize neural interpolation of Myerson's greedy allocation based on marginal profits (the correlated variant of virtual valuation), formal neural verification to enforce exact strategy-proofness, and a constructive repair procedure. Empirically, our method is highly effective, consistently achieves near-optimal revenue across a wide range of distributions, including synthetic, adversarial, and real-world (consumer, financial, and industrial) datasets. Compared to existing manual and neural baselines, our approach shows substantial improvement, often reducing the revenue gap by an order of magnitude. Our study is also the first to introduce (unattainable) greedy revenue as a rigorous upper bound for empirical benchmarking, providing a definitive quantitative performance measure where true optima remain theoretically elusive. We demonstrate the generality of our approach by extending it to multi-unit auctions with unit demand and integrating our verification techniques into RegretNet to achieve exact strategy-proofness.

0.55

Cooperative Multi-Agent Reinforcement Learning for Market Making on Prediction-Market Order Books

cs.LG stat.MLcs.MAq-fin.TR ·2026-10-19 ·Skander Lejmi
similarity 0.65
Abstract · 50 pages, 8 figures, 7 tables. Extended version of a paper accepted at ICAIF 2026 Workshop on AI-Driven Market Microstructure. MSc dissertat…

A market maker provides liquidity by quoting prices to buy and sell an asset, earning the spread while managing inventory risk. We study market makers trained with multi-agent reinforcement learning on prediction markets, specifically Polymarket, whose thin order books pose distinct challenges. Three challenges underpin this research: adverse selection may cause a policy trained on real data to stop quoting; the consequences of a quote can arrive many steps after the action; and prediction-market L2 data does not identify individual orders needed for simulation. We address these challenges by reconstructing order-level LOBSTER-format data from Polymarket and training agents in JaxMARL-HFT on 417 real markets. We enrich the baseline market maker's observation space with the book and recent flow, redesign its actions and inventory controls, and propose a cooperative multi-agent decomposition into a quoter and a risk manager trained using recurrent Independent Proximal Policy Optimisation (IPPO) with RNN policies. We investigate reward shaping, particularly reward blending and post-fill markout, to mitigate credit-assignment difficulties between the agents. Our redesigned single-agent market maker quotes more frequently and incurs smaller held-out losses than the retrained JaxMARL-HFT baseline, although the contributions of jointly changed observations, actions and risk constraints are not separately identified. Decomposition alone performs poorly; careful reward design substantially improves the desk relative to the unshaped split and yields our best result. Models are evaluated on realised end-of-episode portfolio value on held-out markets. None establishes positive average portfolio value in periodic held-out evaluation, and each configuration was trained with one seed. The environment, data and protocol lay a foundation for makers that quote many linked markets at once.

0.21

PowerMarketJax: A JAX Benchmark Suite for Multi-Agent Reinforcement Learning in Power Markets

cs.MA cs.AIeess.SY ·2026-09-29 ·Zhanhua Pan, Xin Qin, Xiao Liu, Zhilong Cao, Jianhong Wang +1 more
benchmarkcode/data similarity 0.64
Abstract · 69 pages

Power markets are a natural testbed for multi-agent reinforcement learning (MARL), where multiple self-interested participants repeatedly submit bids. A market-clearing mechanism then determines dispatch and prices subject to power grid constraints and market settlement rules. However, existing MARL environments typically focus on a single market setting, implement simplified clearing mechanisms, or rely on CPU-based optimization solvers that slow large-scale training and limit the systematic study of bidding strategies and market behavior. We introduce PowerMarketJax, a benchmark suite for MARL across five power markets: day-ahead wholesale, real-time balancing, ancillary services, peer-to-peer double auctions, and local flexibility. Each environment implements its own clearing, pricing, and settlement rules while providing a common framework for learning and evaluation. We find that learned bidding behavior depends strongly on the market design: independent learners can miss better strategies when gains require many agents to change together, when more profitable strategies lie beyond a region of lower profit, or when profits disappear as more agents adopt the same strategy. PowerMarketJax implements both market simulation and policy training in JAX, allowing the entire pipeline to run on the GPU with 1,024 X 1,200 parallelisms across both environments and market participants, achieving up to 33X speedup over CPU-based baselines. Our open-source benchmark is available at: https://github.com/powermarketjax/PowerMarketJax.

0.23

MARL-Based Sequential RIS Auctions: A Physical-Layer Security Analysis

cs.CR ·2026-08-23 ·Yuanyu Zhang, Yu Zhang, Jialu He, Zhixin Huang, Shuangrui Zhao +1 more
theory similarity 0.63
Abstract

Reconfigurable intelligent surfaces (RISs) hold great potential to enhance coverage, spectral efficiency, and communication security by intelligently configuring their reflecting elements. When owned by a neutral RIS operator, these elements can be offered as resources for which legitimate receivers and eavesdroppers compete. This paper investigates such competition and evaluates its impact on the physical-layer security performance of legitimate receivers. To model the competition, we develop a sequential RIS auction (SRA) framework, in which a bundle of RIS elements is auctioned in each round through a first-price sealed-bid mechanism, with each bidder submitting its bid based on the achievable rate gain and remaining budget. We then formulate the sequential bidding process as a Markov game by specifying its states, actions, rewards, and state transitions. To solve the game, we propose a multi-bidder deep deterministic policy gradient (MADDPG)-based multi-bidder reinforcement learning (MARL) approach under centralized training and decentralized execution (CTDE), enabling legitimate receivers and eavesdroppers to learn bidding strategies that maximize their long-term economic surplus. Numerical results show that, under the considered eavesdropper bidding strategies, the RL-based strategy enables legitimate receivers to achieve the highest secrecy rate per unit cost, outperforming random and fixed strategies and approaching the ideal physical-layer upper bound.

0.26

Decision-Focused Reinforcement Learning for LLM Post-Training

cs.LG cs.AI ·2026-11-19 ·Haotian Zhai, Leqi Liu
similarity 0.63
Abstract

Large language models (LLMs) have shown promise as predictors across various tasks, benefiting from their ability to use information from unstructured context. However, when predictions serve as parameters of downstream optimization problems, higher prediction accuracy does not necessarily translate into lower decision costs. We propose decision-focused reinforcement learning (DFRL), a framework for post-training LLMs to predict optimization parameters using negative downstream decision regret as reward. DFRL trains LLM predictors to minimize the costs of the decisions induced by their predictions, without requiring downstream convexity or differentiability, and integrates readily into existing RL post-training frameworks. To address expensive reward evaluation, we develop two approaches. Heuristic warm-starting uses inexpensive approximate rewards during an initial phase before switching to refinement with exact rewards. Reward correction combines inexpensive estimates with randomized exact evaluations, preserving the expected policy gradient while reducing the expected number of exact solves per update. Experiments on three synthetic optimization problems demonstrate improvements over prediction-loss baselines, while a larger knapsack experiment shows faster early improvement under short training budgets. On inventory planning with H&M transactions and product descriptions, our best configuration, in which the LLM reasons before predicting, reduces regret by 31.4% relative to the SFT baseline and 12.4% relative to the strongest evaluated conventional forecasting baseline.

0.17