Overview

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

69 papers16 papers in the last four weeks, down 6% on the four weeks before. 0.1% of all new papers.

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.
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.
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 O~(SA Var+lower-order terms)\tilde{O}( \sqrt{SA\,\text{Var}} + \text{lower-order terms}), where S,AS,A are the state and action space sizes, and Var\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 ∥h⋆∥sp\Vert h^\star\Vert_\text{sp}, our algorithm obtains lower-order terms scaling as ∥h⋆∥spS2A\Vert h^\star\Vert_\text{sp} S^2 A, which we prove is optimal in both ∥h⋆∥sp\Vert h^\star\Vert_\text{sp} and AA. Without prior knowledge, we prove that no algorithm can have lower-order terms smaller than ∥h⋆∥sp2SA\Vert h^\star \Vert_\text{sp}^2 S A, and we provide a prior-free algorithm whose lower-order terms scale as ∥h⋆∥sp2S3A\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 ∥h⋆∥sp\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.
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 BB batches and has only WW bits of persistent memory. Prior work shows that each constraint alone is surprisingly mild: near-minimax regret O~(KT)\widetilde{O}(\sqrt{KT}) is achievable with O(log⁡T)O(\log T) bits of memory under fully adaptive interaction, and with a KK-independent O(log⁡log⁡T)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 WW-bit memory constraint must use at least Ω(K/W)Ω(K/W) batches to achieve near-minimax regret O~(KT)\widetilde{O}(\sqrt{KT}), even under adaptive grids. In particular, logarithmic memory rules out O(K1−ε)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)Ω(K) bits of information about the hidden set of good arms under a suitable hard prior, whereas an algorithm with BB batches and WW bits of memory allows only O(BW)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 WW with Ω(log⁡T)≤W≤O(Klog⁡T)Ω(\log T) \le W \le O(K\log T), uses at most WW bits of memory and O~(K/W)\widetilde{O}(K/W) batches while achieving regret O~(KT)\widetilde{O}(\sqrt{KT}), nearly matching our lower bound up to polylogarithmic factors.
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 TT-exponents up to logarithmic factors, with no knowledge of the moment order p∈(1,2)p \in (1,2) or its scale σpσ_p, and -- in the nonparametric case -- none of the effective Hölder smoothness β∈(0,1]β\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 pp-th moments for some p∈(1,2)p \in (1,2), with possibly infinite variance. An epoch-based algorithm with truncated means achieves regret O~(T(2−p)/p)\widetilde{O}(T^{(2-p)/p}) in the parametric model and O~(T1−2β(p−1)/(βp+d(p−1)))\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 TT up to logarithmic factors over the effective smoothness range β∈(0,1]β\in (0,1], interpolating between the classical nonparametric rate at p=2p{=}2 and the trivial linear rate as p→1+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 E[g(m,V,W)−g(π,V,W)]≤L∣m−π∣2\mathbb{E}[g(m,V,W) - g(π,V,W)] \le L|m-π|^2 -- no second moment is needed.
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.
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 Ω(T(ln⁡T)d(ln⁡ln⁡T)−d)Ω(\sqrt{T (\ln T)^{d} (\ln \ln T)^{-d}}) cumulative regret, where TT and dd 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⁡1ε)d(ln⁡ln⁡1ε)−d)Ω(ε^{-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)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.
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%.
Feb 24, 2025

Linear Bandits on Ellipsoids: Minimax Optimal Algorithms

We consider linear stochastic bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. We first derive a novel information-theoretic lower bound on the regret of any algorithm, which must be at least Ω(min⁡(dσT+d∥θ∥A,∥θ∥AT))Ω(\min(d σ\sqrt{T} + d \|θ\|_{A}, \|θ\|_{A} T)) where dd is the dimension, TT the time horizon, σ2σ^2 the noise variance, AA a matrix defining the set of actions and θθ the vector of unknown parameters. We then provide an algorithm whose regret matches this bound to a multiplicative universal constant. The algorithm is non-classical in the sense that it is not optimistic, and it is not a sampling algorithm. The main idea is to combine a novel sequential procedure to estimate ∥θ∥\|θ\|, followed by an explore-and-commit strategy informed by this estimate. The algorithm is highly computationally efficient, and a run requires only time O(dT+d2log⁡(T/d)+d3)O(dT + d^2 \log(T/d) + d^3) and memory O(d2)O(d^2), in contrast with known optimistic algorithms, which are not implementable in polynomial time. We go beyond minimax optimality and show that our algorithm is locally asymptotically minimax optimal, a much stronger notion of optimality. We further provide numerical experiments to illustrate our theoretical findings.