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.
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
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.
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~(SAVar+lower-order terms), where S,A are the state and action space sizes, and 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, our algorithm obtains lower-order terms scaling as ∥h⋆∥spS2A, which we prove is optimal in both ∥h⋆∥sp and A. Without prior knowledge, we prove that no algorithm can have lower-order terms smaller than ∥h⋆∥sp2SA, and we provide a prior-free algorithm whose lower-order terms scale as ∥h⋆∥sp2S3A, nearly matching this lower bound. Taken together, these results completely characterize the optimal dependence on ∥h⋆∥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
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 O(KT) is achievable with O(logT) bits of memory under fully adaptive interaction, and with a K-independent O(loglogT)-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 O(KT), even under adaptive grids. In particular, logarithmic memory rules out O(K1−ε) 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 Ω(logT)≤W≤O(KlogT), uses at most W bits of memory and O(K/W) batches while achieving regret O(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
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∈(1,2) or its scale σp, and -- in the nonparametric case -- none of the effective Hölder smoothness β∈(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∈(1,2), with possibly infinite variance. An epoch-based algorithm with truncated means achieves regret O(T(2−p)/p) in the parametric model and O(T1−2β(p−1)/(βp+d(p−1))) when the market value function is β-Hölder, with matching Ω(⋅) 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 β∈(0,1], interpolating between the classical nonparametric rate at p=2 and the trivial linear rate as p→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 -- no second moment is needed.
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.
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(lnT)d(lnlnT)−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ε1)d(lnlnε1)−d) time steps to find an ε-optimal point. We also provide the improved O((lnT)d+1(lnlnT)−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.
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%.
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)) where d is the dimension, T the time horizon, σ2 the noise variance, A 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) and memory O(d2), 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.
Raymond Zhang, Hedi Hadiji, Richard Combes
Laboratoire des signaux et systèmes, Univ. Paris-Saclay, CNRS, CentraleSupélec