We show upper and lower bounds on the regret of m-set adversarial bandits for different utilities (winner reward or sum of rewards) and feedback models (winner index, winner reward, sum of rewards, and their combinations). By comparing to standard bounds for combinatorial and MNL bandits, our results reveal how subtle changes in the setting can have a dramatic impact on the learning rates. Our main technical contributions are the information-theoretic lower bounds on the regret. Experiments on synthetic data confirm our theoretical analyses.
Nicolò Cesa-Bianchi, Matteo Papini
Universit`a degli Studi di Milano · Politecnico di Milano
We study causal logistic bandits with counterfactual fairness constraints. The causal structure is given through known factual and counterfactual feature maps that share an unknown logistic reward parameter, but the learner observes only factual rewards. Consequently, the directions determining counterfactual feasibility need not be identifiable from the available feedback. The closest prior analyses either omit a coverage condition or impose a comparatively strong one, and do not establish matching lower bounds. We first show that some coverage condition is necessary: without a coverage-type restriction, factually indistinguishable environments with different optimal fair actions force Ω(T) expected joint loss. Under a weaker full-rank condition on the factual covariance pooled across actions, we identify a target-specific information scale V⋆ that measures the difficulty of estimating rewards and counterfactual effects from factual feedback. We construct worst-case families satisfying this condition on which every policy incurs expected joint loss Ω([V⋆min{logK,d}]1/3T2/3). We also give an explore--then--exploit procedure tuned using V⋆ and an adaptive algorithm that does not require its value. Both algorithms achieve max{RT,VT}=O([V⋆min{logK,d}]1/3T2/3+κd/σ02), where RT is regret relative to the best fair action and VT denotes the cumulative stage-wise positive violations. Thus the upper and lower bounds match in their leading dependence on T, V⋆, and min{logK,d}, up to logarithmic factors.
Junhyuk Huh, Seoungbin Bae, Dabeen Lee
Faculty of Mathematics, University of Cambridge · Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University
We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For K-armed bandits with A optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a O~(KAK−AT) minimax regret, where T is the total number of interactions and O~(⋅) drops all constant and logarithmic factors, improving the previous O~(KT/A) regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of A up to O~(1) factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of K-armed bandits with A over the entire range of 1≤A≤K−1.
Kaixuan Ji, Qiwei Di, Qingyue Zhao +2
Department of Computer Science, University of California, Los Angeles, CA 90095, USA
Prediction with expert advice is a fundamental problem in online learning. When the time horizon T is known in advance, the minimax cumulative regret over n experts is asymptotically 2Tlnn. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to T, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time t, the best known guarantee has been tlnn---a factor of 2 worse---and it has remained unknown whether this factor of 2 is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies Rt≤(1+O(lnlnn/lnn))tlnn/2 simultaneously for every t≥1.
Yang Cai, Vineet Gupta, Yanchen Jiang +4
Google Research · Yale University · Google DeepMind
We study repeated contract design when a principal observes outcomes but not the actions that generate them. The principal may use any bounded outcome-contingent payment vector, and the agent's best response can make expected profit discontinuous in those payments. For every fixed number m≥2 of outcomes, the minimax regret over T rounds is of order Tm/(m+1), up to logarithmic factors. The upper bound allows arbitrary action spaces and agent heterogeneity, without smoothness or monotone-surplus assumptions. Its key is an effective-dimension reduction that the benchmark can be normalized even when fixed tie-breaking is not shift invariant, after which revealed preference yields a monotone response map in payment-difference coordinates. A learning policy built on a Lipschitz parametrization of this map attains the rate using only observed outcome categories. The lower-bound construction accounts for how incentive losses accumulate across outcome dimensions. It shows that each additional contractible outcome creates a precise and unavoidable increase in the worst-case cost of learning.
Rui Ai, David Simchi-Levi, Han Zhong
Massachusetts Institute of Technology · Shanghai Jiao Tong University
A learner probes at most k of n arms each round, receives the maximum of their rewards in [0,1], and competes with the best fixed arm. When does the probing advantage pay for learning? We determine two minimax laws. Under independent stochastic rewards with winner feedback (the maximum and a winning label), or on arbitrary fixed sequences given a single signed contrast between block maxima, the minimax regret has order Φn,k(T)=min{nn−kT,kn−k}, 2≤k<n. Under winner feedback, both arbitrary joint i.i.d. rewards and fixed sequences have minimax regret of order Rn,k(T)=nn−kmin{T,kn+T,knT}. Both laws have universal constants and anytime upper bounds. The first reduces regret to a pure coverage cost: same-round contrasts absorb the stability cost, and independence permits exact resampling whose gains fund sample advancement. The second adds a learning cost that becomes comparable to coverage at horizon n; beyond nk, numerical maxima improve over labels alone. The lower bound allows every adaptive action size.
We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let d be the dimension, K be the menu size, and T the time horizon. For 2≤K≤d, we prove an upper bound O(K1/4dT). When T≥d2, we further prove a lower bound Ω(K1/4dT). Thus, for T≥d2 and 2≤K≤d, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on K is optimal. Compared with the previous O(dKT) bound, our upper bound improves the dependence on K by a factor of K1/4. For K≥d, we prove an upper bound Od,T(dTmin{d,(dlogK)1/4}) and a lower bound Ω(dTmin{d,(log(2d)dlogK)1/4}). Here, Od,T omits logarithmic factors only in d and T. In particular, for polynomially large K≥d, the upper and lower bounds both scale as d3/4T up to logarithmic factors, improving the standard O(dT) rate by a factor of d1/4. As K grows further, the regret smoothly recovers the dT scale once logK reaches order d.
Tianyuan Jin
Data Science and Analytics Thrust The Hong Kong University of Science and Technology (Guangzhou)
We determine the minimax cumulative log-loss regret of a finite-alphabet, exogenously driven source with genuinely infinite input memory: independent Rademacher inputs (Ut) are observed sequentially and the next binary mark has logit ∑j≥1θjUt+1−j, the unknown coefficients obeying a summable envelope ∣θj∣≤rj, ∑jrj≤B. At horizon T, lag j can move the logit by at most rj and is exercised in only nT,j=(T−j+1)+ rounds, and the two limitations combine into the sum ΓT(r)=∑j≤Tlog(1+nT,jrj2). One coordinate-localised Bayesian mixture achieves RT(r)≤CΓT(r) for \emph{every} summable envelope with C universal. Our main result is a matching nonasymptotic converse for the canonical exponential and polynomial envelopes; its new ingredients are a modular finite-sample information bound for logistic experiments with an exogenous random design, and a conditioning estimate for the overlapping Toeplitz lag matrix obtained by exhibiting each off-diagonal Gram sum as a sum of independent Rademacher variables indexed by the edges of a forest, needing neither local asymptotic normality nor any spectral theorem for random Toeplitz matrices. So ΓT(r) is the minimax regret scale here, giving Θ(α−1log2T) for rj=Ae−αj and Θ(T1/(2s)) for rj=Aj−s, s>1 --- the latter without the extra (logT)1−1/(2s) factor any window-truncation analysis pays. We also show memory decay cannot determine regret, and that a profile-scaled online Newton predictor attains OB(ΓT(r)) in polynomial time per round.
Sequential decision-making in real-world applications often involves uncertainty about the environment's model. Uncertain Markov decision processes (UMDPs) represent the possible environments as a set of MDPs with shared states and actions but potentially different transition probabilities and rewards. Optimizing a single policy across all possible MDPs may sacrifice performance, while preparing an individually optimized policy for every MDP may violate operational, regulatory, or interpretability constraints on the number of policies that can be prepared and deployed. We consider settings in which model uncertainty is resolved shortly before execution, allowing the most suitable policy to be selected from a limited set prepared in advance. We introduce k-adaptable policy synthesis, which optimizes such a set of k policies under a minimax-regret objective. We prove that the problem is NP-hard and develop KAPS, an exact nested branch-and-bound algorithm with problem-specific bounds and heuristics. KAPS jointly optimizes which MDPs share a policy and the policies themselves. Experiments across various UMDP benchmarks show that the largest reduction in regret consistently occurs when increasing from one to two policies. In the single-policy setting, KAPS is competitive with existing methods in solution quality and proves optimality substantially more often.
We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite p-th central moment, where p∈(1,2] is unknown. For a bounded convex domain of diameter D, subgradients bounded by G, noise scale σ, and comparator path length PT, let ΛT=1+PT/D. A single algorithm, using none of G,σ,p,PT, attains expected dynamic regret Op(min{GDTΛT+σDT1/pΛT(p−1)/p,GDT}) 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.
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.
We establish a Ω(d5/4T) 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 dT 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=(a1,a2)∈B22d, each function is the scaled soft maximum of a "tube", r−1∥W⋆a1−8εra2∥2 (hyperparameterized by ε,r), and a squared distance function, 21∥a1−u⋆∥22−21∥u⋆∥22. Here, W⋆∈Rd×d is an unknown linear transformation, and u⋆∈Rd is an unknown vector which must be learned to minimize the function. Observations are informative about u⋆ only when the learner's action lies near the tube determined by W⋆, satisfying a2≈r8εW⋆a1: thus the learner must either find this tube without knowing W⋆, or spend observations learning useful directions of W⋆. 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 Ω(d5/2/ε2) to find an ε-optimal action, which translates to an Ω(d5/4T) regret lower bound. We also extend this lower bound to the unconstrained setting where the action space is Rd.
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.
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→0), and Rawlsian fairness (p→−∞). Although tight guarantees are known for p≥0, 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/T), while the only general lower bound was the classical Ω(σ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 Ω(σkmax(1,q)/T); for q>1, this shows that the penalty kq/2 is information-theoretically unavoidable. We then introduce \textsf{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 O(σkmax(1,q)/T), matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that \textsf{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
We study the bandit-feedback version of online principal component analysis (Bandit PCA): in each round t=1,…,T, the adversary selects a d×d symmetric gain matrix Gt with spectrum in [0,1] and rank at most r; the learner simultaneously selects a unit vector wt∈Sd−1 and receives the reward wt⊤Gtwt. 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(drTlogT) and showed the lower bound of Ω(rT/logT). We improve upon both of these bounds and essentially bridge the gap between them, establishing the minimax regret of order rdT 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
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
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 Θ(T1−α) 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.
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 xt∈[−1,1] of the blind action; the blind action gives reward xt 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 O(T2/3) regret guarantees for this problem. The two-action apple-tasting graph was the natural candidate for the missing Ω(T2/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
231⋅T≤RT⋆≤23⋅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
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 O~(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 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.
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 Ω(Bmin{d,log∣A∣}) 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 Ω(Bmin{d,log∣A∣}+dTmin{d,log∣A∣}). We develop two phased-elimination algorithms based on G-optimal designs and 1-bit mean estimation. The first achieves O(dB+dT) regret, matching the lower bound up to logarithmic factors when ∣A∣=exp(Ω(d)), and the second incorporates a safe-arm identification and warm-start procedure to obtain O(Blog∣A∣+d3/2B+dTlog∣A∣) regret, which is near-optimal in broad scaling regimes of (∣A∣,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 Θ(T).
Ivan Lau, Daniel McMorrow, Kevin Jamieson +1
National University of Singapore · University of Washington
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 O(T+D) together with 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.
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 O~(dH2T) (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 σˉ_T≤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 O~(dH2σˉ_TT), which recovers the existing bound in the worst case and improves upon it for structured MDPs. For instance, for KL-constrained robust MDPs, σˉ_T=O(H−1), reducing the horizon dependence by a factor H. We further establish a matching Ω(dH2σˉ_TT) 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
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, ∑k=1K[V∗,Mk−Vπk,Mk], where Mk 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 O(SAH3KlogL) for adversarial contexts, where L denotes the number of possible contexts. This result implies a regret bound of O(SAH3K) for stochastic contexts. We further translate the stochastic regret guarantee into a sample complexity bound of O(SAH3/ε2) for a fixed context distribution. In addition, we derive a gap-dependent regret bound of
O(p∈[0,1)inf(Δminp1+pKΔminp)logK⋅poly(S,A,H)),
where Δminp 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
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 O~(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 O~(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
We study the 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 O~(T3/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 (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 O~(T2/3), and improves significantly upon prior work without any additional assumptions. We also prove a matching minimax lower bound of Ω~(T2/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.
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.
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.