Minimax Regret

Follow this topic Ask about this topic

Minimax regret asks how well a decision-maker can perform, in the worst case, compared with a benchmark that knew the outcomes or model in advance. It studies settings from bandits and reinforcement learning to online prediction, pricing, and resource allocation, using methods such as UCB, elimination, mirror descent, and robust optimization. Researchers pair algorithmic regret guarantees with information-theoretic lower bounds to determine which rates are achievable. A central tension is that feedback, dimension, heavy-tailed noise, and constraints such as fairness or safety can sharply change those rates, while algorithms must often adapt without knowing which conditions apply.

Latest papers

55 papers15 papers in the last four weeks, up 67% on the four weeks before. 0.1% of all new papers.

Jul 29, 2026

Parameter-Free Dynamic Regret under Heavy-Tailed Noise

We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite

p

-th central moment, where

p\in(1,2]

is unknown. For a bounded convex domain of diameter

D

, subgradients bounded by

G

, noise scale

σ

, and comparator path length

P_T

, let

Λ_T=1+P_T/D

. A single algorithm, using none of

G,σ,p,P_T

, attains expected dynamic regret

O_p\left(\min\{GD\sqrt{TΛ_T}+σDT^{1/p}Λ_T^{(p-1)/p},\,GDT\}\right)

against every fixed comparator sequence. Restarted AdaGrad experts produce the noise-path exponent

(p-1)/p

, and a prior favoring longer restart intervals removes horizon-dependent logarithmic overhead. We give an explicit bound uniform in

p

; its logarithm-free form has noise coefficient

O(1+\log(p/(p-1)))

, while the static-regret constant is universal. The analysis requires only marginal noise moments and permits dependent errors. Complete pathwise proofs retain both the expert-loss range and the gradient energies preceding comparator movement. Matching lower bounds hold on every bounded convex domain of positive diameter, under the same gradient-only information model. Together with a path-budget-tuned upper bound, they characterize the minimax rate with universal constants, including its linear-regret saturation.

Vaneet Aggarwal

Purdue University

Online Convex Optimization Dynamic Regret Minimization Minimax Regret Heavy-Tailed Noise Adaptive Gradient Methods Heavy-Tailed Stochastic Optimization

Ask PDF

Jul 26, 2026

Experimentation and Commitment under Reward Shifts

Decision-makers in learning environments face a dilemma when their short-term optimal actions may not favor their long-term benefits the most. To understand the fundamental tradeoff behind the dilemma, we study adaptive experimentation with post-commitment reward shifts. During an experiment phase, the decision-maker may adaptively test multiple options; during a subsequent commitment phase, the decision-maker must commit to a single option, whose reward may differ from its pre-commitment reward. We propose the Reserved Arm Eliminations for Commitment (RAEC) algorithm, which reserves a predetermined portion of the experiment phase to identify the best post-shift option while using the remaining rounds to minimize short-run regret. We establish regret upper bounds for RAEC across all parameter regimes and matching minimax lower bounds, providing a tight characterization of the cost of balancing short-term performance and long-term commitment. A key implication is that deciding in advance how much of the experiment phase to reserve for the commitment decision is sufficient to achieve the best possible worst-case regret rate; adapting this amount as more data are observed does not improve the rate. We further study extensions with structural knowledge of reward shifts and with concave commitment rewards and portfolio choice. Numerical experiments confirm that our proposed algorithms achieve the regret predicted by our theory and outperform other baselines.

Puping Jiang, Wei Tang, Renyu +1

Philip

Multi-Armed Bandits Exploration-Exploitation Tradeoff Minimax Regret Non-Stationary Bandits

Ask PDF

Jul 21, 2026

The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization

We establish a

\widetildeΩ(d^{5/4}\sqrt T)

lower bound on the minimax expected regret of stochastic bandit convex optimization of

1

-Lipschitz functions on the Euclidean ball. This presents the first nontrivial regret lower bound that grows faster than

d\sqrt{T}

for this problem, establishing that stochastic bandit convex optimization is fundamentally harder than linear bandits. The hard class of convex functions we construct takes the following form in dimension

2d

: for an action

a = (a^1,a^2) \in \mathbb{B}^{2d}_2

, each function is the scaled soft maximum of a "tube",

r^{-1} \| W^\star a^1 - \frac{r}{8\varepsilon} a^2 \|_2

(hyperparameterized by

\varepsilon,r

), and a squared distance function,

\frac12 \| a^1 - u^\star \|_2^2 - \frac12 \| u^\star \|_2^2

. Here,

W^\star \in \mathbb{R}^{d \times d}

is an unknown linear transformation, and

u^\star \in \mathbb{R}^{d}

is an unknown vector which must be learned to minimize the function. Observations are informative about

u^\star

only when the learner's action lies near the tube determined by

W^\star

, satisfying

a^2 \approx \frac{8\varepsilon}{r} W^\star a^1

: thus the learner must either find this tube without knowing

W^\star

, or spend observations learning useful directions of

W^\star

. Formally, our regret analysis exploits this tradeoff by bounding the posterior spread of Fisher information matrices obtained under an adaptive sequence of actions. Together, these ingredients give a sample complexity lower bound of

\widetildeΩ(d^{5/2}/\varepsilon^2)

to find an

\varepsilon

-optimal action, which translates to an

\widetildeΩ (d^{5/4} \sqrt{T})

regret lower bound. We also extend this lower bound to the unconstrained setting where the action space is

\mathbb{R}^d

Nived Rajaraman

Microsoft Research

Online Convex Optimization Minimax Regret Bandit Convex Optimization Information-Theoretic Lower Bounds

Ask PDF

Jul 15, 2026

Min-Max Regret Task Allocation and Planning of Heterogeneous Multi-Robot System in Partially Known Environments

Efficient task allocation for large-scale Heterogeneous Multi-Robot Systems (HMRS) is critical, yet dealing with complex temporal logic tasks in partially known environment (PKE) remains a computational bottleneck. Existing approaches often struggle to balance exploring uncertain regions and exploiting known resources, while also suffering from exponential computational complexity. To address these issues, this paper presents a robust planning framework that simultaneously handles high-level logical constraints and environmental uncertainty without sacrificing scalability. We formulate the problem as a min-max regret optimization, proposing a Region-Binding Atomic Proposition (RbAP) to capture resource uncertainty within the automaton structure. To solve this, we propose the Extended Planning Decision Tree (E-PDT) equipped with a novel Regret-based Branch-and-Bound (BnB) strategy. Unlike traditional methods that rely on prior probabilities or worst-case analysis, our approach dynamically prunes suboptimal policies, effectively balancing the need for information gathering (exploration) and task completion (exploitation). Theoretical analysis confirms the feasibility and completeness of our approach. Extensive numerical and physical experiments demonstrate that the proposed framework achieves near-linear scalability with respect to the number of robots and types, significantly outperforming MILP-based baselines in both solution quality and computational efficiency.

Xinkai Liang, Huixuan Chan, Ying Liu +2

Minimax Regret Multi-Robot Exploration Robot Task Planning Multi-Robot Task Allocation

Ask PDF

Jul 15, 2026

Price of Fairness in Bandits: A Tight Minimax Characterization

In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized

p

-mean, interpolating between utilitarian welfare (

p=1

), Nash welfare (

p\to0

), and Rawlsian fairness (

p\to-\infty

). Although tight guarantees are known for

p\ge0

, the strictly fair regime

q=-p>0

remains unresolved because negative-power means are dominated by the smallest per-round rewards. For

σ

-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret

O(k^{(q+1)/2}/\sqrt{T})

, while the only general lower bound was the classical

Ω(σ\sqrt{k/T})

. Thus it was unclear whether the extra dependence on

k

was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound

Ω(σ\sqrt{k^{\max(1,q)}/T})

; for

q>1

, this shows that the penalty

k^{q/2}

is information-theoretically unavoidable. We then introduce UCB-HARE (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is

\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T})

, matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that UCB-HARE improves over uniform-exploration baselines, with gains increasing as

q

grows.

Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury

1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Indian Institute of Technology Kanpur

Multi-Armed Bandits Minimax Regret Fair Resource Allocation Algorithmic Fairness UCB Algorithms Information-Theoretic Lower Bounds

Ask PDF

Jul 12, 2026

Bandit PCA with Minimax Optimal Regret

We study the bandit-feedback version of online principal component analysis (Bandit PCA): in each round

t = 1,\dots,T

, the adversary selects a

d \times d

symmetric gain matrix

G_t

with spectrum in

[0,1]

and rank at most

r

; the learner simultaneously selects a unit vector

w_t \in S^{d-1}

and receives the reward

w_t^\top G_t w_t

. The learner receives no other feedback, and aims to minimize the regret against the best unit vector in hindsight. This problem was introduced by Kotlowski and Neu (2019), who gave an algorithm with regret

O(d\sqrt{rT \log T})

and showed the lower bound of

Ω(r\sqrt{T/\log T})

. We improve upon both of these bounds and essentially bridge the gap between them, establishing the minimax regret of order

r\sqrt{dT}

up to polylogarithmic factors in

d

and

T

. The upper bound is attained by a novel algorithm, which combines online mirror descent on the spectrahedron of (real) density matrices with a multiscale exploration scheme in which the eigenspaces with different spectral magnitudes are updated at different rates. For the lower bound, we construct an adaptive adversary that refines a hidden large-reward subspace based on the learner's actions, in such a way that low regret is impossible without estimating the subspace; as a result, lower-bounding the regret reduces to studying the arising subspace estimation problem. Finally, we discuss connections of Bandit PCA with adaptive-measurement quantum tomography.

Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa Saha

Georgia Tech · University of Illinois, Chicago

Principal Component Analysis Minimax Regret Online Mirror Descent Regret Minimization Adversarial Bandits

Ask PDF

Jul 10, 2026

Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information

Adversarial team games (ATGs) with asymmetric information, such as adversarial path-finding, goal search, and reachability games on graphs, require strategies that are robust to hidden opponent types, such as a hidden goal flag, and to deception. Under asymmetric information, deception is seen as strategic shifts in the type distribution such that the omniscient opponent can collude with Nature and condition its play on the observed type. Existing risk-neutral solution concepts, such as Bayesian Nash equilibrium (BNE), are sensitive to distribution shifts, while distributionally robust approaches provide guarantees only within a prescribed ambiguity set. To address these limitations, we introduce Probabilistically Robust Minimax-Regret Equilibrium (PR-MRE), a novel equilibrium concept that combines the distribution-free robustness of minimax-regret reasoning with probabilistic information from a nominal type distribution. PR-MRE minimizes worst-case regret over a high-confidence subset of the type space, providing protection against strategic redistribution of probability mass while avoiding the conservatism of fully distribution-free approaches. We show that, for normal-form Bayesian games, PR-MRE can be formulated as a robust bilinear program and derive a tractable semidefinite relaxation. We then adapt this relaxation into a novel meta-solver within a robust double-oracle framework, PRMRE-PSRO, enabling population-based learning of approximate PR-MRE strategies via deep reinforcement learning best responses. Experiments on graph-structured adversarial team games demonstrate that PR-MRE discovers strategies with substantially improved worst-case performance across hidden types compared to risk-neutral equilibrium solutions, resulting in more robust behavior under strategic distribution shifts.

Naman Aggarwal, Jonathan P. How

Aerospace Control Laboratory Laboratory of Information and Decision Systems Massachusetts Institute of Technology

Imperfect-Information Games Game Theory Minimax Regret Nash Equilibrium Computation

Ask PDF

Jun 9, 2026

Bellman-sufficient Information Complexity

We introduce Bellman-sufficient information complexity for minimax analysis of sequential decision problems. A Bellman-sufficient state retains enough of the history to close the controlled recursion, while an index

Y=χ(Ω)

specifies the decision-relevant information being charged. The upper bound is a log-penalized Bellman program; the lower bound is a Bellman--Fano comparison along an algorithm-dependent reference trajectory. If the two values match at a common localization scale and the stated admissibility, calibration, and growth conditions hold, they form an information-risk sandwich. UCB, E2D, and AMS/EBO control or relax the upper Bellman bracket in different ways. For the main application, we give a negative answer to a widely studied form of the GP--UCB minimax-optimality question. For every

0<α<1/4

, we construct one bounded continuous kernel whose minimax regret is

Θ(T^{1-α})

along an infinite sequence of horizons, while two globally calibrated GP--UCB rules incur linear regret under one fixed truth. An epochwise finite-marginal action-index AIR Bellman policy, implemented through robust AIR/AMS/EBO control, attains the minimax order. The construction separates realized information from the cost of uniform optimism: many low-value directions inflate the exploration multiplier and change the trajectory. Through the canonical RKHS feature map, it also yields a finite-horizon polynomial minimax separation for the specified maximal-information-calibrated LinUCB rule. A reproducible experiment illustrates the mechanism.

Yunbei Xu

National University of Singapore

Multi-Armed Bandits Minimax Regret Gaussian Process Bandits Regret Minimization UCB Algorithms Information-Theoretic Lower Bounds

Ask PDF

Jun 2, 2026

Two-Action Apple Tasting with Switching Costs

We study the two-action apple-tasting problem with switching costs against an oblivious adversary. In an equivalent normalized formulation, at each round the learner chooses between a revealing action and a blind action: the revealing action gives reward

0

and reveals the hidden value

x_t\in[-1,1]

of the blind action; the blind action gives reward

x_t

but reveals nothing. The learner pays one unit whenever they switches actions, and regret is measured against the best fixed action in hindsight. General feedback-graph algorithms with switching costs give

\widetilde O(T^{2/3})

regret guarantees for this problem. The two-action apple-tasting graph was the natural candidate for the missing

Ω(T^{2/3})

obstruction in the switching-cost classification: such a lower bound would have transferred to a large family of still-unclassified feedback graphs. We prove that this obstruction is not there: the oblivious minimax expected regret for this problem satisfies

\frac{1}{2\sqrt3}\cdot\sqrt T \le R_T^\star \le 2\sqrt{3}\cdot \sqrt{T}.

Tommaso Cesari, Roberto Colomboni

School of Electrical Engineering and Computer Science University of Ottawa Ottawa, Canada · School of Mathematics University of Bristol Bristol, United Kingdom

Multi-Armed Bandits Minimax Regret Regret Minimization Adversarial Bandits

Ask PDF

Jun 1, 2026

Minimax-Optimal Policy Regret in Partially Observable Markov Games

We study sequential decision-making in partially observable environments against strategic, adaptive opponents, modeled as partially observable Markov games (POMGs). The central challenge is to learn latent dynamics from partial observations while facing an adversary whose behavior depends on the learner's strategy, making standard regret notions inadequate. We prove that an epoch-based optimistic maximum-likelihood algorithm achieves

\tilde{O}(\sqrt{T})

policy regret for fixed problem parameters, with explicit dependence on the horizon, adversary memory, confidence radius, and the aggregate Eluder dimension of the observable-operator class. The algorithm selects one policy per geometrically growing epoch using confidence sets built cumulatively from past data, which keeps the cost of comparing adversary responses across policies logarithmic in

T

. We also prove a lower bound matching the

\sqrt{T}

and aggregate-Eluder-dimension dependence, up to problem-dependent and logarithmic factors. Finally, we extend the framework to horizon-adaptive guarantees and adversaries with geometric fading memory.

Raman Arora

Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA.

Regret Minimization in RL Imperfect-Information Games Partially Observable RL Minimax Regret Model-Based RL Partially Observable Stochastic Games

Ask PDF

May 29, 2026

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size

B

, and during each batch the learner sends

B

requested arm pulls to an agent, who then observes the corresponding

B

rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only or total bit budgets only. We establish a minimax lower bound showing that

Ω(B\min\{d,\log\lvert \mathcal{A} \rvert\})

regret is unavoidable due to the 1-bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of

\widetildeΩ(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}})

. We develop two phased-elimination algorithms based on

G

-optimal designs and 1-bit mean estimation. The first achieves

\widetilde{O}(dB + d\sqrt{T})

regret, matching the lower bound up to logarithmic factors when

\lvert \mathcal{A} \rvert = \exp(Ω(d))

, and the second incorporates a safe-arm identification and warm-start procedure to obtain

\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})

regret, which is near-optimal in broad scaling regimes of

(\lvert \mathcal{A} \rvert, B, d, T)

. Together, our results demonstrate that a single bit of feedback per batch suffices to nearly match the minimax regret of unconstrained linear bandits in broad scaling regimes, even for batch sizes as large as

Θ(\sqrt{T})

Ivan Lau, Daniel McMorrow, Kevin Jamieson +1

National University of Singapore · University of Washington

Multi-Armed Bandits Batched Bandits Minimax Regret Communication Complexity Low-Bit Quantization Bandit Learning

Ask PDF

May 22, 2026

Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays

We study adversarial multi-armed bandits with and without delayed feedback under a safety-aware goal: achieving minimax-optimal worst-case regret while keeping nearly constant regret relative to a designated "safe" baseline policy. Existing approaches can balance this trade-off with immediate feedback for smooth comparators, but arbitrary delays can mistime transitions between conservatism and exploration, endangering the safety guarantee. To bridge this gap, we propose Prudent-Banker, a novel algorithm that combines a delay-adapted variant of Online Mirror Descent with a modified phased-aggression mechanism. Its key technical contribution is a delay-calibrated restart threshold that rigorously accounts for the worst-case distortion induced by unobserved feedback and reliably detects comparator suboptimality. We also establish new lower bounds for safety-constrained adversarial delayed bandits, showing that the regret guarantees of Prudent-Banker are unimprovable, up to logarithmic factors, under the baseline-safety requirement. To the best of our knowledge, Prudent-Banker is the first algorithm to achieve the optimal safety--robustness trade-off: pseudo-regret

\widetilde{O}(\sqrt{T}+\sqrt{D})

together with

\widetilde{O}(1)

regret against the safe comparator, both with and without delays. Experiments across diverse delay distributions show that, unlike standard delay-robust baselines, Prudent-Banker effectively balances safety and learning.

Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis

Department of Finance University of Wisconsin–Madison · Department of Computer Sciences University of Wisconsin–Madison

Multi-Armed Bandits Minimax Regret Online Mirror Descent Bandits with Delayed Feedback Adversarial Bandits Bandit Learning

Ask PDF

May 19, 2026

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs

We study reinforcement learning for episodic Markov Decision Processes (MDPs) whose transitions are modelled by a multinomial logistic (MNL) model. Existing algorithms for MNL mixture MDPs yield a regret of

\smash{\tilde{O}(dH^2\sqrt{T})}

(Li et al., 2024), where

d

is the feature dimension,

H

the episode length, and

T

the number of episodes. Inspired by the logistic bandit literature (Abeille et al., 2021; Faury et al., 2022; Boudart et al., 2026), we introduce a problem-dependent constant

\barσ\_T \leq 1/2

, measuring the normalised average variance of the optimal downstream value function along the learner's trajectory. We propose an algorithm achieving a regret of

\smash{\tilde{O}(dH^2\barσ\_T\sqrt{T})}

, which recovers the existing bound in the worst case and improves upon it for structured MDPs. For instance, for KL-constrained robust MDPs,

\barσ\_T = O(H^{-1})

, reducing the horizon dependence by a factor

H

. We further establish a matching

\smash{Ω(dH^2\barσ\_T\sqrt{T})}

lower bound, proving minimax optimality (up to logarithmic factors) and fully characterising the regret complexity of MNL mixture MDPs for the first time.

Pierre Boudart, Pierre Gaillard, Alessandro Rudi

SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth +3

Regret Minimization in RL Markov Decision Processes Reinforcement Learning Minimax Regret

Ask PDF

May 15, 2026

Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning

We study episodic reinforcement learning with fixed reward and transition functions, but with episode-dependent admissible action sets that are observed at the start of each episode. Performance is measured by cumulative regret against the episode-wise optimal value,

\sum_{k=1}^K [V^{*,M^k} - V^{π^k,M^k}]

, where

M^k

represents the action context in the

k

-th episode. We show that the MVP algorithm naturally extends to this framework and enjoys strong theoretical guarantees. In particular, we establish a minimax regret bound of

\widetilde{O}(\sqrt{SAH^3K\log L})

for adversarial contexts, where

L

denotes the number of possible contexts. This result implies a regret bound of

\widetilde{O}(\sqrt{SAH^3K})

for stochastic contexts. We further translate the stochastic regret guarantee into a sample complexity bound of

\widetilde{O}(SAH^3/ε^2)

for a fixed context distribution. In addition, we derive a gap-dependent regret bound of

\widetilde O\left( \inf_{p\in [0,1)} \left( \frac{1}{Δ_{\min}^{p}} + pKΔ_{\min}^{p} \right)\log K \cdot \mathrm{poly}(S,A,H) \right),

where

Δ_{\min}^{p}

is the global

p

-trimmed positive-gap floor over suboptimal

(h,s,a)

triples. This bound can substantially improve upon the minimax rate when the relevant suboptimality gaps are large.

Zijun Chen, Zihan Zhang

Department of Computer Science and Engineering Hong Kong University of Science and Technology

Regret Minimization in RL Reinforcement Learning Minimax Regret Contextual RL

Ask PDF

May 12, 2026

Profit Maximization in Bilateral Trade against a Smooth Adversary

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good. We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents' valuations are generated by a smooth adversary. We devise a learning algorithm that guarantees a

\tilde{O}(\sqrt{T})

regret bound, which is tight in the time horizon

T

up to poly-logarithmic factors. This matches the minimax rate for the stochastic i.i.d. case, and is also well separated from the adversarial setting, where sublinear-regret is unattainable. By extending the strong regret guarantees from the i.i.d. case to the smooth adversary, we significantly broaden the scope of settings where such fast rate is achievable, while closing an important gap in the regret landscape of this fundamental economic problem. To overcome the challenges posed by this adversary, we leverage a continuity property of smooth instances and combines this with a hierarchical net-construction of the broker's action space, which is analyzed via algorithmic chaining. We showcase the applicability of these techniques by deriving a similarly tight

\tilde{O}(\sqrt{T})

regret bound for a related mechanism design model: the joint ads problem.

Simone Di Gregorio, Paul Dütting, Federico Fusco +1

Department of Computer, Control and Management Engineering Sapienza University of Rome · Google Research · Department of Computer Science Aarhus University

Mechanism Design Minimax Regret Regret Minimization

Ask PDF

May 10, 2026

Optimal Regret for Single Index Bandits

We study the

\textit{single-index bandit}

problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts through an unknown reward function. This model extends linear and generalized linear bandits to a nonparametric setting, and is particularly relevant when the reward function is not known in advance. While optimal regret guarantees are known for monotone reward functions, the general non-monotone case remains poorly understood, with the best known bound being

\tilde{\mathcal{O}}(T^{3/4})

(under standard boundedness and Lipschitz assumptions on the reward function [Kang et al., 2025]). We close this gap by establishing the optimal regret for general single-index bandits. We propose a simple two-phase algorithm, namely, Zoomed Single Index Bandit with Upper Confidence Bound (

\texttt{ZoomSIB-UCB}

), that first estimates the projection direction via a normalized Stein estimator, and then reduces the problem to a one-dimensional bandit using discretization and finally use UCB. This approach achieves a regret of

\tilde{\mathcal{O}}(T^{2/3})

, and improves significantly upon prior work without any additional assumptions. We also prove a matching minimax lower bound of

\tildeΩ(T^{2/3})

, showing that the upper bound is essentially tight. Our upper and lower bounds together provide a sharp characterization of the regret in single-index bandits. Moreover, the empirical results further demonstrate the effectiveness and robustness of our approach.

Devdan Dey, Sujoy Bhore, Avishek Ghosh

Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

Multi-Armed Bandits Single-Index Models Minimax Regret Regret Minimization Contextual Bandits

Ask PDF

Apr 27, 2026

Prior-Agnostic Robust Forecast Aggregation

Robust forecast aggregation combines the predictions of multiple information sources to perform well in the worst case across all possible information structures. Previous work largely focuses on settings with a known binary state space, where the state is either 0 or 1. We study prior-agnostic robust forecast aggregation in which the aggregator observes only experts' reports, yet is ignorant of both the underlying joint information structure and the full prior, including the underlying state space. Unlike the standard model that fixes the binary state space {0, 1}, we allow the (binary) unknown state values to be arbitrary numbers in [0, 1], so the same reported probability may correspond to very different realized outcome frequencies across environments. Our main contribution is a simple, explicit, closed-form log-odds aggregator that linearly pools forecasts in logit space, together with (nearly-)tight minimax-regret guarantees across three knowledge regimes. We first show that under conditionally independent (CI) signals, robust aggregation with an unknown state space is strictly harder than in the known-state setting by establishing a larger lower bound, and our aggregation rule can achieve a worst-case regret of 0.0255. Along the way, we also characterize tight regret bounds for Blackwell-ordered structures and for general information structures. In the classical setting with known state space {0,1}, our aggregator achieves regret strictly below 0.0226 for CI structures. To the best of our knowledge, this is the first explicit closed-form aggregator that achieves a regret upper bound strictly less than 0.0226. Finally, we extend the model where the aggregator additionally knows each expert's marginal forecast distribution; in this setting, with the CI structures, we show that a generalized log-odds rule achieves regret of 0.0228, complementing with a lower bound of 0.0225.

Zhi Chen, Cheng Peng, Wei Tang

Chinese University of Hong Kong

Minimax Regret Probabilistic Forecasting Regret Minimization

Ask PDF

Mar 27, 2026

Water-Filling is Universally Minimax Optimal

Allocation of dynamically-arriving (i.e., online) divisible resources among a set of offline agents is a fundamental problem, with applications to online marketplaces, scheduling, portfolio selection, signal processing, and many other areas. The water-filling algorithm, which allocates an incoming resource to maximize the minimum load of compatible agents, is ubiquitous in many of these applications whenever the underlying objectives prefer more balanced solutions; however, the analysis and guarantees differ across settings. We provide a justification for the widespread use of water-filling by showing that it is a universally minimax optimal policy in a strong sense. Formally, our main result implies that water-filling is minimax optimal for a large class of objectives -- including both Schur-concave maximization and Schur-convex minimization -- under

α

-regret and competitive ratio measures. This optimality holds for every fixed tuple of agents and resource counts. Remarkably, water-filling achieves these guarantees as a myopic policy, remaining entirely agnostic to the objective function, agent count, and resource availability. Our techniques notably depart from the popular primal-dual analysis of online algorithms, and instead develop a novel way to apply the theory of majorization in online settings to achieve universality guarantees.

Siddhartha Banerjee, Ramiro N. Deo-Campo Vuong, Robert Kleinberg

Cornell University.

Online Resource Allocation Multi-Agent Resource Allocation Fair Resource Allocation Minimax Regret

Ask PDF

Mar 26, 2026

Globalized Adversarial Regret Optimization: Robust Decisions with Uncalibrated Predictions

Optimization problems routinely depend on uncertain parameters that must be predicted before a decision is made. Classical robust and regret formulations are designed to handle erroneous predictions and can provide statistical error bounds in simple settings. However, when predictions lack rigorous error bounds (as is typical of modern machine learning methods) classical robust models often yield vacuous guarantees, while regret formulations can paradoxically produce decisions that are more optimistic than even a nominal solution. We introduce Globalized Adversarial Regret Optimization (GARO), a decision framework that controls adversarial regret, defined as the gap between the worst-case cost and the oracle robust cost, uniformly across all possible uncertainty set sizes. By design, GARO delivers absolute or relative performance guarantees against an oracle with full knowledge of the prediction error, without requiring any probabilistic calibration of the uncertainty set. We show that GARO equipped with a relative rate function generalizes the classical adaptation method of Lepski to downstream decision problems. We derive exact tractable reformulations for problems with affine worst-case cost functions and polyhedral norm uncertainty sets, and provide a discretization and a constraint-generation algorithm with convergence guarantees for general settings. Finally, experiments demonstrate that GARO yields solutions with a more favorable trade-off between worst-case and mean out-of-sample performance, as well as stronger global performance guarantees.

Jannis Kurtz, Bart P. G. van Parys

University of Amsterdam · CWI Amsterdam

Robust Optimization Predict-Then-Optimize Minimax Regret

Ask PDF

Mar 25, 2026

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

Online reinforcement learning in infinite-horizon Markov decision processes (MDPs) remains less theoretically and algorithmically developed than its episodic counterpart, with many algorithms suffering from high ``burn-in'' costs and failing to adapt to benign instance-specific complexity. In this work, we address these shortcomings for two infinite-horizon objectives: the classical average-reward regret and the

γ

-regret. We develop a single tractable UCB-style algorithm applicable to both settings, which achieves the first optimal variance-dependent regret guarantees. Our regret bounds in both settings take the form

\tilde{O}( \sqrt{SA\,\text{Var}} + \text{lower-order terms})

, where

S,A

are the state and action space sizes, and

\text{Var}

captures cumulative transition variance. This implies minimax-optimal average-reward and

γ

-regret bounds in the worst case but also adapts to easier problem instances, for example yielding nearly constant regret in deterministic MDPs. Furthermore, our algorithm enjoys significantly improved lower-order terms for the average-reward setting. With prior knowledge of the optimal bias span

\Vert h^\star\Vert_\text{sp}

, our algorithm obtains lower-order terms scaling as

\Vert h^\star\Vert_\text{sp} S^2 A

, which we prove is optimal in both

\Vert h^\star\Vert_\text{sp}

and

A

. Without prior knowledge, we prove that no algorithm can have lower-order terms smaller than

\Vert h^\star \Vert_\text{sp}^2 S A

, and we provide a prior-free algorithm whose lower-order terms scale as

\Vert h^\star\Vert_\text{sp}^2 S^3 A

, nearly matching this lower bound. Taken together, these results completely characterize the optimal dependence on

\Vert h^\star\Vert_\text{sp}

in both leading and lower-order terms, and reveal a fundamental gap in what is achievable with and without prior knowledge.

Guy Zamir, Matthew Zurek, Yudong Chen

Department of Computer Sciences, University of Wisconsin–Madison

Regret Minimization in RL Average-Reward RL Minimax Regret

Ask PDF

Mar 14, 2026

Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits

We study stochastic multi-armed bandits under simultaneous constraints on space and adaptivity: the learner interacts with the environment in

B

batches and has only

W

bits of persistent memory. Prior work shows that each constraint alone is surprisingly mild: near-minimax regret

\widetilde{O}(\sqrt{KT})

is achievable with

O(\log T)

bits of memory under fully adaptive interaction, and with a

K

-independent

O(\log\log T)

-type number of batches when memory is unrestricted. We show that this picture breaks down in the simultaneously constrained regime. We prove that any algorithm with a

W

-bit memory constraint must use at least

Ω(K/W)

batches to achieve near-minimax regret

\widetilde{O}(\sqrt{KT})

, even under adaptive grids. In particular, logarithmic memory rules out

O(K^{1-\varepsilon})

batch complexity. Our proof is based on an information bottleneck. We show that near-minimax regret forces the learner to acquire

Ω(K)

bits of information about the hidden set of good arms under a suitable hard prior, whereas an algorithm with

B

batches and

W

bits of memory allows only

O(BW)

bits of information. A key ingredient is a localized change-of-measure lemma that yields probability-level arm exploration guarantees, which is of independent interest. We also give an algorithm that, for any bit budget

W

with

Ω(\log T) \le W \le O(K\log T)

, uses at most

W

bits of memory and

\widetilde{O}(K/W)

batches while achieving regret

\widetilde{O}(\sqrt{KT})

, nearly matching our lower bound up to polylogarithmic factors.

Ruiyuan Huang, Zicheng Lyu, Xiaoyi Zhu +1

School of Data Science, Fudan University · School of Data Science, Fudan University Shanghai Innovation Institute

Batched Bandits Multi-Armed Bandits Minimax Regret

Ask PDF

Mar 6, 2026

Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound

In contextual bilateral trade under full feedback, the posted price does not affect which valuations are observed. We show that in this model such action-independent feedback removes the polynomial adaptation penalty familiar from heavy-tailed bandits: fully parameter-free algorithms attain the oracle minimax

T

-exponents up to logarithmic factors, with no knowledge of the moment order

p \in (1,2)

or its scale

σ_p

, and -- in the nonparametric case -- none of the effective Hölder smoothness

β\in (0,1]

. The statistic that makes model selection possible is a paired squared-loss difference, whose noise-square term cancels exactly, leaving noise damped by the candidate gap. The resulting bilateral-trade regret rates are new. Trader valuations have bounded conditional densities and heavy tails -- finite

p

-th moments for some

p \in (1,2)

, with possibly infinite variance. An epoch-based algorithm with truncated means achieves regret

\widetilde{O}(T^{(2-p)/p})

in the parametric model and

\widetilde{O}(T^{1-2β(p-1)/(βp + d(p-1))})

when the market value function is

β

-Hölder, with matching

Ω(\cdot)

lower bounds -- under a mild nondegeneracy condition -- via Assouad's method and a fixed-support mixture construction -- characterizing the minimax rate in

T

up to logarithmic factors over the effective smoothness range

β\in (0,1]

, interpolating between the classical nonparametric rate at

p{=}2

and the trivial linear rate as

p \to 1^+

. The enabling structural step extends the self-bounding property of Bachoc et al. (ICML 2025) from bounded to real-valued valuations: within our conditionally independent, conditionally centered noise model, bounded conditional densities and finite first moments suffice for the expected regret of any price

π

to satisfy

\mathbb{E}[g(m,V,W) - g(π,V,W)] \le L|m-π|^2

-- no second moment is needed.

Hangyi Zhao

Minimax Regret Regret Minimization Contextual Bandits

Ask PDF

Mar 2, 2026

Learning Optimal Search Strategies

We explore the question of how to learn an optimal search strategy within the example of a parking problem where parking opportunities arrive according to an unknown inhomogeneous Poisson process. The optimal policy is a threshold-type stopping rule characterized by an indifference position. We propose an algorithm that learns this threshold by estimating the integrated jump intensity rather than the intensity function itself. We show that our algorithm achieves a logarithmic regret growth, uniformly over a broad class of environments. Moreover, we prove a logarithmic minimax regret lower bound, establishing the growth optimality of the proposed approach.

Stefan Ankirchner, Maximilian Philipp Thiel

Institute for Mathematics, University of Jena, Inselplatz 5, 07743 Jena, Germany.

Optimal Stopping Minimax Regret

Ask PDF

Feb 20, 2026

Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere

We study an algorithm-independent, worst-case lower bound for the Gaussian process (GP) bandit problem in the frequentist setting, where the reward function is fixed and has a bounded norm in the known reproducing kernel Hilbert space (RKHS). Specifically, we focus on the squared exponential (SE) kernel, one of the most widely used kernel functions in GP bandits. One of the remaining open questions for this problem is the gap in the dimension-dependent logarithmic factors between upper and lower bounds. This paper partially resolves this open question under a hyperspherical input domain. We show that any algorithm suffers

Ω(\sqrt{T (\ln T)^{d} (\ln \ln T)^{-d}})

cumulative regret, where

T

and

d

represent the total number of steps and the dimension of the hyperspherical domain, respectively. Regarding the simple regret, we show that any algorithm requires

Ω(ε^{-2}(\ln \frac{1}ε)^d (\ln \ln \frac{1}ε)^{-d})

time steps to find an

ε

-optimal point. We also provide the improved

O((\ln T)^{d+1}(\ln \ln T)^{-d})

upper bound on the maximum information gain for the SE kernel. Our results guarantee the optimality of the existing best algorithm up to dimension-independent logarithmic factors under a hyperspherical input domain.

Shogo Iwazaki

LY Corporation, Tokyo, Japan

Gaussian Process Bandits Minimax Regret Multi-Armed Bandits Information-Theoretic Lower Bounds Kernel Methods

Ask PDF

Feb 18, 2026

What is the Value of Censored Data? An Exact Analysis for the Data-driven Newsvendor

We study the offline data-driven newsvendor problem when historical demand is censored by past inventory levels. We introduce a class of policies for which worst-case expected regret over all bounded demand distributions admits an exact finite-dimensional characterization, valid for any sample size and historical inventory design. The dimension depends on the number of distinct inventory levels, rather than the number of observations. This framework yields exact analyses of the sales-as-demand heuristic, the Kaplan-Meier policy, and recent policies from the censored-newsvendor literature. We leverage this reduction to derive sharp insights on the achievable performance of standard inventory policies under demand censoring. In particular, our analysis of the Kaplan-Meier policy shows that while demand censoring fundamentally limits what can be learned from passive sales data, just a small amount of targeted exploration at high inventory levels can substantially improve worst-case guarantees. Finally, we further leverage our reduction to design new policies that push the frontier and substantially improve upon the worst-case regret of known policies, reducing it by up to 40%.

Rachitesh Kumar, Omar Mouchtaki

Carnegie Mellon University · New York University

Inventory Control Minimax Regret Learning with Missing Data

Ask PDF