CS Paper Radar

On the Computational Tractability of Robust Bandits

Vanessa Kosoy, Vinayak Pathak

cs.LG ·submitted 2026-10-06 17:38 UTC · v1

Abstract

Learning when the environment does not belong to the learner's hypothesis class is typically handled using agnostic learning guarantees. However, for anything beyond supervised learning, agnostic guarantees are difficult to come by. Recently, imprecise bandits (Kosoy, 2025) (later renamed to robust bandits in Appel and Kosoy, 2025) were introduced as another approach to unrealizable learning in the bandits setting and a $Θ(\sqrt{T})$ regret learner was shown for a large class. However, no computational guarantees were provided. In this paper we identify a special case that admits a polynomial-time learner with $\tilde{O}(\sqrt{T})$ regret. We also show that several small generalizations of this special case are NP-hard thus indicating that the special case is at the boundary of what is tractable. It has been recently suggested (Kosoy, 2018) that computationally efficient learners for unrealizable learning problems are crucial for solving the AI alignment problem. This work is a small step in that direction.

Closest papers

Nearest neighbours by meaning across the whole index.

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary

cs.LG stat.ML ·2026-09-11 ·Mengxiao Zhang
similarity 0.79
Abstract

We study switching regret in adversarial multi-armed bandits, where the learner competes with an arm sequence that changes at most $S$ times. When $S$ is known, an optimal expected regret of $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ is obtainable [Auer et al., 2002]. However, when $S$ is unknown, Marinov and Zimmert [2021] show that this guarantee is impossible under an adaptive adversary. In this paper, we show that a single algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ expected regret for every $S$ against an oblivious adversary, resolving an open problem of Auer et al. [2019b]. Our algorithm combines a fixed-share learner initialized with a small learning rate and dyadic-interval subroutines that search for local improvements using randomized learning rates and implicit exploration. Importantly, a non-uniform prior favors following the main learner, keeping the cost of maintaining many subroutines small. When the subroutines accumulate sufficient improvement over the main learner, its learning rate doubles, allowing adaptation to the unknown number of comparator switches $S$.

0.17

Adversarially Batched Online Learning

cs.LG cs.DS ·2026-11-12 ·Mingda Qiao, Kerui Wu
theory similarity 0.77
Abstract

We introduce adversarially batched online learning, where the learner may update its decision rule only at a restricted set of time steps. Equivalently, the time horizon is partitioned into batches, within which the learner must use a fixed policy. We study this model for four canonical problems: stochastic bandits, online convex optimization, prediction with expert advice, and adversarial bandits. For stochastic bandits, we identify a universal complexity measure based on relative batch growth and establish both gap-dependent and gap-independent regret bounds. We show that the multiplicative penalty relative to the standard gap-dependent complexity can grow superlinearly in batch hardness. For the remaining three, we show that the optimal regret is tightly characterized by the 2-norm of the batch-length sequence. The upper bound is achieved by a batch-oblivious learner who does not know the batch structure, via a generic adaptive doubling trick tailored to this complexity measure. In contrast, the lower bound holds even for batch-aware learners.

0.11

Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

cs.LG stat.ML ·2026-09-27 ·Gon Buzaglo, Elad Hazan
highly cited similarity 0.77
Abstract

We consider binary prediction with i.i.d. contexts from an unknown distribution and adaptively chosen losses. We show that a simple Follow-the-Perturbed-Leader algorithm using a Gaussian perturbation for each observed context achieves $\widetilde O(\sqrt{T\log N})$ regret for a class of $N$ experts, while requiring one optimization-oracle call per round and no explicit enumeration of the class. For an infinite hypothesis class $\mathcal H$, the same algorithm achieves $\widetilde O(\sqrt{T\operatorname{VC}(\mathcal H)})$ regret. This resolves an open problem posed by Lazaric and Munos (2012), showing that hybrid classification is computationally as easy as statistical learning. As an application, we reduce the problem of contextual bandits with $K$ actions to classification through uniform exploration, achieving $\widetilde O(K^{2/3}T^{2/3}(\log N)^{1/3})$ regret. This matches the best known dependence on the horizon while removing the context-distribution access required by prior oracle-efficient methods.

0.39

Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry

cs.LG ·2026-10-31 ·Canzhe Zhao, Vincent Y. F. Tan
similarity 0.77
Abstract

We study \textit{best-of-both-worlds} (BOBW) algorithms for linear bandits, which aim to simultaneously guarantee $\gO(\sqrt T)$ regret in the adversarial regime and $\gO(\log T)$ regret in the stochastic regime over $T$ rounds. For finite action sets, we introduce \emph{information-acquisition follow-the-regularized-leader} (\IAFTRL{}), the first BOBW algorithm based purely on the follow-the-regularized-leader (FTRL) framework that attains an $\gO(\cstar\log T)$-type regret in the stochastic regime, where $\cstar$ is the information-acquisition complexity that characterizes instance-dependent optimality in linear bandits, while retaining the $\gO(\sqrt{T})$ regret guarantee in the adversarial regime. This resolves the open problem posed in~\cite{LeeEtAl2021,KongZ023,ItoT23,ZhaoItoLi2025}.

0.15

Generalized Linear Bandits with Memory

cs.LG stat.ML ·2026-08-16 ·Heesang Ann, Hyunjun Choi, Taehyun Hwang, Younghoon Shin, Haeju Cheong +1 more
top venue similarity 0.73
Abstract · Accepted at ICML 2026

We study generalized linear bandits with memory, an endogenous non-stationary setting in which rewards depend on past actions through a finite memory matrix. Building on prior work for linear models (Clerici et al., 2024), we show that the previously known $\tilde{O}(T^{3/4})$ regret bound stems from a loose analysis, and we provide a sharpened analysis that recovers a $\tilde{O}(\sqrt{T})$ regret rate in the linear case. We then extend this improvement to generalized linear models and propose a block-wise algorithm based on shrunken confidence bounds. Our algorithm achieves a regret bound of $\tilde{O}\left(\sqrt{mT} + d\sqrt{T} + \sqrtκ\, d^{2} m^{1/4} T^{1/4} + κd^{2} \right)$, where $d$ denotes the feature dimension, $m$ the memory length, and $κ$ a curvature parameter of the link function. This attains a $\sqrt{T}$-type rate despite nonlinear rewards and memory effects. To the best of our knowledge, this analysis provides a unified treatment of memory-induced non-stationarity and nonlinear link functions, while ensuring that the leading regret term is independent of the curvature of the link function. We conduct numerical experiments that are consistent with our theoretical findings.

0.61

Accelerating Linear Bandits with Persistent Candidate Sets

cs.LG ·2026-10-09 ·Bingkui Tong, Daria Korovaitceva, Marina Sheshukova, Sergey Samsonov, Junpei Komiyama
theory similarity 0.73
Abstract

Exhaustive optimistic scoring can make action selection costly in linear bandits with a large fixed set of $K$ actions, requiring $\mathcal{O}(K)$ score evaluations per round. We introduce Persistent Candidate LinUCB (\textsc{PC-LinUCB}), which maintains $k$ active actions and samples $q$ challengers uniformly from the remaining $K-k$ actions at each round. By scoring only these $k+q$ candidates, \textsc{PC-LinUCB} reduces the number of score evaluations per round to $\mathcal{O}(k+q)$. We establish problem-independent and problem-dependent high-probability regret bounds consisting of a standard linear-bandit learning term and an additive discovery cost of order $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ at fixed confidence. Notably, this additional cost does not grow with the horizon. For fixed gaps and sufficiently long horizons, we establish an $Ω\left((K-k)/q\right)$ regret lower bound under uniform challenger sampling, showing that partial candidate access itself imposes an unavoidable regret cost. Experiments show that \textsc{PC-LinUCB} substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.

0.20

An Efficient Minimax-Optimal Algorithm for Adversarial $m$-Set Bandits

cs.LG ·2026-08-12 ·Francesco Bacchiocchi, Tommaso Cesari, Roberto Colomboni
theory similarity 0.72
Abstract

We study adversarial combinatorial bandits with $m$-set actions, where at each round the learner selects $m$ out of $d$ items and observes only the aggregate loss of the selected items. The resulting action set contains $K=\binom{d}{m}$ elements and can therefore be exponentially large. We propose a computationally efficient algorithm that exploits this structure without explicitly enumerating the action set. Against adaptive non-anticipating adversaries, it guarantees, with probability at least $1-δ$, regret against the best action in hindsight of $R_T =O(\sqrt{dT\log(K/δ)}). $ This matches the high-probability regret bound of the finite-action EXP3 with Kiefer-Wolfowitz exploration algorithm of Zimmert and Lattimore, whose direct implementation may require exponential space. Our algorithm instead represents each sampling distribution with $d$ parameters and runs in polynomial time without enumerating the action set. This resolves an open problem posed by Maiti et al. We complement this upper bound with a matching high-probability lower bound. For all sufficiently small $δ$ and all sufficiently large horizons, every randomized algorithm admits an adaptive non-anticipating adversary for which, with probability at least $δ$, $R_T=Ω( \sqrt{dT\log(K/δ)}). $ Thus, the rate is minimax optimal up to universal constants in this regime. In particular, setting $m=1$ shows that the $\log K$ factor in the high-probability regret bound for ordinary $K$-armed bandits against adaptive non-anticipating adversaries is unavoidable. This strengthens the lower bound of Gerchinovitz and Lattimore, closing the remaining $\sqrt{\log K}$ gap between high-probability upper and lower regret bounds.

0.34

Expected Sample Complexity in Multi-Armed Bandits

cs.LG stat.ML ·2026-10-07 ·Nadav Sukenik, Nadav Merlis
hot direction similarity 0.72
Abstract

Sample complexity is a widely used metric in sequential decision-making problems, defined as the number of suboptimal decisions during the interaction between the agent and an environment. We study the sample complexity of stochastic multi-armed bandit problems and introduce the expected sample complexity performance measure, analyzing it in a novel framework called approximately correct in expectation (ACE). We show that ACE guarantees imply almost sure convergence to the optimal expected reward, in contrast to high-probability guarantees found in other frameworks, and also show how to convert ACE guarantees into explicit expected regret bounds. We further show that, in contrast to existing measures, deterministic algorithms cannot obtain favorable ACE bounds, and analyze stochastic algorithms in two settings: when the allowed suboptimality level $ε$ is known to the algorithm and when it is unknown. In the former, we devise an explore-then-$ε$-greedy algorithm, and in the latter, we analyze the expected sample complexity of Thompson sampling. Finally, we establish nearly matching lower bounds for both settings, showing that the algorithms are tight in $ε$ and proving a performance separation between the two regimes.

0.23