Regret Minimization

Follow this topic Ask about this topic

Momentum

12 papers in the last four weeks, up 71% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 81

All topics

Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy
Jul 2, 2026Jiawei ZhangRegret Minimization Online Resource Allocation
Stern School of Business New York University
Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates
Jul 2, 2026Jiawei ZhangRegret Minimization Online Resource Allocation
Department of Technologies, Operations, and Statistics Stern School of Business, New York University
Improved Multi-Dimensional Forecasting for Swap Regret
Jun 28, 2026Joey Rivkin, Ramiro N. Deo-Campo Vuong, Robert Kleinberg +3Regret Minimization Online Learning
Cornell University
Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes
Jun 26, 2026Luis LealNash Equilibrium Imperfect-Information Games
The Decision Geometry of Covariance Estimation for the Global Minimum-Variance Portfolio under Heavy Tails
Jun 25, 2026Xavier FonsecaRegret Minimization Portfolio Optimization
Academy for AI, Games and Media, Breda University of Applied Sciences, Breda, The Netherlands.
YUKTI: From Natural-Language Situations to Robust, Verifiable Decisions An Uncertainty-Typed Proposition IR, Assumption-Robust Pareto Frontiers, and a Regret Certificate
Jun 22, 2026Suyash MishraLarge Language Model-Guided Optimization Robust Optimization
AI Researcher
Toward Simultaneously Optimal Regret in U-Calibration
Jun 16, 2026Rafael Frongillo, Haipeng Luo, Nishant A. Mehta +1Probabilistic Forecasting Proper Scoring Rules
University of Colorado Boulder · University of Southern California and Google Research · University of Victoria +1
Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret
Jun 15, 2026Madhulatha Mandarapu, Sandeep KunkunuruRegret Minimization Dense Retrieval
VaidhyaMegha Private Limited, India
Bellman-sufficient Information Complexity
Jun 9, 2026Yunbei XuMulti-Armed Bandits Minimax Regret
National University of Singapore
Phi-Actor-Critic: Steering General-Sum Games to Pareto-Efficient Correlated Equilibria
Jun 9, 2026Wongyu Lee, Francesco Lelli, Omran Ayoub +1Multi-Agent Coordination Regret Minimization
Politecnico di Milano · Tilburg University · University of Applied Sciences and Arts of Southern Switzerland
Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret
Jun 8, 2026Seoungbin Bae, Dabeen LeeExploration-Exploitation Tradeoff Regret Minimization
Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University
Regret Minimization with Adaptive Opponents in Repeated Games
Jun 4, 2026Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu +1Game-Playing Agents Game Theory
Massachusetts Institute of Technology · OpenAI · University of Maryland, College Park
Mean-based algorithms: A lower bound and regret
Jun 3, 2026Julius Durmann, Amelie KleberMulti-Armed Bandits Regret Minimization
Technical University of Munich
Streaming Knowledge Compilation: Proactive Materiality-Scored Pinning for Time-Evolving LLM Wikis
Jun 3, 2026Juan M. HuertaMemory-Augmented Language Models Knowledge Augmentation for Language Models
Zinnia Tech Solutions 600 Steamboat Road Greenwich, CT 06830, USA
Two-Action Apple Tasting with Switching Costs
Jun 2, 2026Tommaso Cesari, Roberto ColomboniMulti-Armed Bandits Minimax Regret
School of Electrical Engineering and Computer Science University of Ottawa Ottawa, Canada · School of Mathematics University of Bristol Bristol, United Kingdom
A No-Regret Framework for Adaptive Incentive Design
Jun 1, 2026Georgios Vasileiou, Lantian Zhang, Silun ZhangMechanism Design Game Theory
Department of Mathematics, KTH Royal Institute of Technology, Stockholm, 10044, Sweden.
Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits
Jun 1, 2026Pu Wang, Yao-Xiang DingMulti-Armed Bandits Best-Arm Identification
State Key Lab of CAD&CG, Zhejiang University
Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization
May 31, 2026Shion TakenoBayesian Optimization Regret Minimization
Nagoya University
TRACER: Turn-level Regret Matching with Inner Reinforcement Credit for Cooperative Multi-LLM Reasoning
May 27, 2026Chusen Li, Zhou Liu, Shuigeng Zhou +1Regret Minimization Multi-Agent Reasoning
1Fudan University · 2Zhongguancun Academy · 3Academy for Advanced Interdisciplinary Studies, Peking University
On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits
May 25, 2026Yunlong Hou, Zixin Zhong, Vincent Y. F. TanMulti-Armed Bandits Regret Minimization
Department of Mathematics, National University of Singapore · Data Science and Analytics Thrust, Hong Kong University of Science and Technology (Guangzhou) · Department of Electrical and Computer Engineering, National University of Singapore
Regret Analysis of Retry-Based Bandits
May 20, 2026Bingkui Tong, Junpei Komiyama, Soichiro Nishimori +1Multi-Armed Bandits Regret Minimization
Mohamed bin Zayed University of Artificial Intelligence · RIKEN AIP · The University of Tokyo
Active Context Selection Improves Simple Regret in Contextual Bandits
May 19, 2026Mohammad Shahverdikondori, Jalal Etesami, Negar KiyavashMulti-Armed Bandits Best-Arm Identification
College of Management of Technology, EPFL · Department of Computer Science, TU Munich
Real-Time Parallel Counterfactual Regret Minimization
May 19, 2026Boning Li, Longbo HuangGame-Playing Agents GPU Acceleration
IIIS, Tsinghua University
Calibeating for general proper losses: A Bregman divergence approach
May 17, 2026Maximilian Fichtl, Cristóbal Guzmán, Nishant A. MehtaFunctional Bregman Divergences Proper Scoring Rules
Independent researcher · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile · Department of Computer Science, University of Victoria
Parallelizing Counterfactual Regret Minimization
May 14, 2026Juho Kim, Tuomas SandholmGPU Acceleration Imperfect-Information Games
Computer Science Department Carnegie Mellon University · Computer Science Department, CMU · Strategic Machine, Inc. +2
Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
May 13, 2026Irene AldridgeStochastic Optimization Regret Minimization
A Regret Perspective on Online Multiple Testing
May 13, 2026Qingyang Hao, Kongchang Zhou, Fang Kong +1FDR Control Regret Minimization
Southern University of Science and Technology
Profit Maximization in Bilateral Trade against a Smooth Adversary
May 12, 2026Simone Di Gregorio, Paul Dütting, Federico Fusco +1Mechanism Design Minimax Regret
Department of Computer, Control and Management Engineering Sapienza University of Rome · Google Research · Department of Computer Science Aarhus University
Regret Minimization in Bilateral Trade With Perturbed Markets
May 11, 2026Anna Lunghi, Matteo Castiglioni, Alberto MarchesiMechanism Design Automated Negotiation
Politecnico di Milano
Learning from Acceptance: Cumulative Regret in the Game of Coding
May 10, 2026Hanzaleh Akbari Nodehi, Parsa Moradi, Mohammad Ali Maddah-AliImperfect-Information Games Game Theory
University of Minnesota, Twin Cities, Minneapolis, MN, USA

Jul 2, 2026, cs.LGJ/K move · Enter open · S save

Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy

Jiawei Zhang

Stern School of Business New York University

Regret Minimization Online Resource Allocation

Open paper AskPDF arXiv

We study online resource allocation when both rewards and consumption sizes may be continuously distributed. Requests arrive sequentially and must be accepted or rejected irrevocably under fixed resource capacities. Each request belongs to one of finitely many observable types; conditional on an observable request type, both the reward and the scalar size are random, and the realized size scales a fixed type-specific resource-consumption vector. The model allows the deterministic fluid relaxation to be degenerate. We show that additive regret is governed by the size-weighted mass of requests whose value-to-size ratios lie near the active acceptance cutoffs. We formalize this quantity through an active weighted-mass exponent p. When p > 1, this cutoff mass is thin, and the problem is genuinely hard: every online policy must incur regret of order at least

T^{1/2 - 1/(2p)}

, and this holds for every p > 1. A sample-path marginal policy matches this lower bound up to polylogarithmic factors; and when p = 1, so that the mass grows linearly near the cutoff, it attains

O((\log T)^2)

regret. For example, if the size and the value-to-size ratio are independent and uniformly distributed, then p = 1; if instead the size and the reward are independent and uniformly distributed, then p = 2. Thus the policy achieves

o(\sqrt{T})

regret throughout this regularity class without any fluid non-degeneracy assumption, allowing both primal degeneracy and dual non-uniqueness.

Momentum

Related topics

Latest papers 81