betaFeedback

WorksComputer Science

Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions

Abstract

We study adversarial linear bandits with strong corruption, in which an adaptive adversary chooses the reward vectors and a strong adversary corrupts each observed reward after seeing the learner's action, subject to a known total corruption budget CC. Strong corruption breaks the importance-weighted reward estimates used by adversarial bandit algorithms: by corrupting only the rounds in which a rarely sampled action is drawn, the adversary amplifies each unit of corruption by the inverse of its sampling probability. The best known bound for this problem, O~(d3T+dC)\tilde O(\sqrt{d^3T} + dC) by Liu et al. (2024), is a factor d\sqrt{d} above the corruption-free rate in its leading term, and whether O~(dT+dC)\tilde O(d\sqrt{T} + dC) regret is achievable was left open. We propose CRW-FTRL, which runs follow-the-regularized-leader with a radius-weighted entropy regularizer and estimates rewards with a normalized kernel estimator whose sensitivity to corruption is governed by per-action radii instead of inverse sampling probabilities. The radii are nondecreasing and are chosen jointly with the sampling distribution through a monotone log-determinant barrier problem, so that a negative linear term in the regularizer cancels both the corruption bias and the estimation error of every comparator. For KK actions in Rd\mathbb{R}^d, CRW-FTRL achieves O~(dTlog⁡K+dC)\tilde O(\sqrt{dT\log K} + dC) regret with high probability against an adaptive adversary, which matches the best known corruption-free rate and the Ω(dC)Ω(dC) lower bound up to logarithmic factors. Applied to a discretization of a general compact action set, it yields O~(dT+dC)\tilde O(d\sqrt{T} + dC) regret, which settles the statistical rate of corrupted adversarial linear bandits under strong corruption.

Introduction

Adversarial linear bandits ([4, 39, 16, 1, 12]) are a basic model of sequential decision making with structured actions and nonstationary rewards. In each round, the learner picks an action a∈A⊂Rd\mathbf{a} \in\mathcal{A} \subset\mathbb{R}^d, an adversary picks a reward vector θt∈Rd\boldsymbol{\theta}_t \in\mathbb{R}^d, and the learner observes only the reward aTθt\mathbf{a}^{\mathsf{T}}\boldsymbol{\theta}_t of the action it played, possibly with noise. The regret of this problem is well understood. For a finite action set of size KK, exponential weights with a suitable exploration distribution achieves O(dTlog⁡K)O(\sqrt{dT\log K}) regret ([12]), which is minimax optimal up to logarithmic factors on the hypercube ([16]), and a rate of the same order holds with high probability against an adaptive adversary ([46]). These guarantees all assume, however, that the observed reward equals the linear reward of the chosen action plus zero-mean noise. In many applications, this assumption fails because the feedback itself is manipulated. Click fraud in online advertising, fake ratings in recommender systems, and malicious users who poison the feedback of an online learner all inject corruptions into the observed rewards, and even a small corruption budget suffices to mislead standard bandit algorithms [37, 25, 35, 20]. Corruption-robust bandit algorithms address this issue by allowing an adversary to perturb the observed rewards subject to a total budget CC, and they aim for regret that degrades gracefully with CC. For stochastic linear bandits, this goal is largely achieved: He et al. (2022) obtain O~(dT+dC)\widetilde{O}(d\sqrt{T}+dC) regret, which matches the Ω(dT+dC)\Omega(d\sqrt{T}+dC) lower bound [29, 11] up to logarithmic factors. When the rewards are themselves adversarial, the corruption cannot be absorbed into the reward vectors θt\theta_t, because it may depend on the realized action and is not linear in the action [36]. Corrupted adversarial linear bandits are therefore a genuinely different problem, and they were studied only recently.

Liu et al. [36] initiated the study of corrupted adversarial linear bandits and distinguished two types of adversaries. A weak adversary fixes the corruption of every action before the learner draws its action, whereas a strong adversary chooses the corruption after observing the drawn action. Against a weak adversary, Liu et al. [36] obtain O~(dT+dC∞)\widetilde{O}(d\sqrt{T}+\sqrt{d}C_\infty) regret, matching the stochastic case. Against a strong adversary, their bound is O(d3T+dC)O(\sqrt{d^3T}+dC), whose leading term is a factor d\sqrt{d} larger than the corruption-free rate, and they leave open whether dT+dCd\sqrt{T}+dC regret is achievable [36 Section 7]. The difficulty lies in the reward estimator. Adversarial bandit algorithms rely on importance-weighted estimates of the rewards, and the weight placed on the observed reward can be as large as 1/pt,It1/p_{t,I_t} when the drawn action ItI_t has small sampling probability pt,Itp_{t,I_t}. A weak adversary cannot exploit this, because the large weight is drawn with probability pt,Itp_{t,I_t} and cancels in expectation. A strong adversary, by contrast, can stay silent in most rounds and spend its budget only in rounds where a rarely sampled action is drawn, so that each unit of corruption shifts the reward estimates by 1/pt,It1/p_{t,I_t} instead of O(1)O(1). Liu et al. [36] avoid this problem by running continuous exponential weights over a lifted action space, whose concentrated sampling keeps the weights bounded by poly⁡(d)\operatorname{poly}(d), and their analysis of this approach incurs the additional d\sqrt{d} factor in the leading term.

In this paper, we resolve this open question in the affirmative. We study adversarial linear bandits with KK actions, where an adaptive adversary chooses the reward vectors and a strong adversary chooses the corruptions after observing both the drawn action and its clean reward, subject to a known budget CC. Our contributions are summarized as follows.

  • We propose CRW-FTRL, an FTRL algorithm that combines a radius-weighted entropy regularizer with normalized kernel reward estimates. In each round, the algorithm assigns each action a nondecreasing radius via a monotone log-determinant barrier problem and constructs a reweighted, normalized kernel reward estimator. Controlling the estimator’s sensitivity through these radii rather than inverse sampling probabilities prevents a strong adversary from amplifying its corruption on rarely sampled actions, while the radius-weighted entropy regularizer with a linear bonus offsets both the cumulative corruption bias and the estimation variance.

  • We prove that, with probability at least 1−δ1-\delta, CRW-FTRL achieves realized regret O(dClog⁡(dT)+dTlog⁡(dT)log⁡(KT/δ))=O~(dTlog⁡K+dC)O(dC\log(dT)+\sqrt{dT\log(dT)\log(KT/\delta)})=\widetilde{O}(\sqrt{dT\log K}+dC) against an adaptive adversary with strong corruption (Theorem Theorem 5.1 and Corollary Corollary 5.2). The corruption-free term matches the best known high-probability rate O~(dTlog⁡K)\widetilde{O}(\sqrt{dT\log K}) for finite action sets [12 Zimmert and]

Lattimore, 2022), and the corruption term matches the Ω(dC)\Omega(dC) lower bound of Bogunovic et al. [11] (which holds already for O(d)O(d) actions; adjoining the zero action to their dd standard-basis arms gives K=d+1K=d+1 actions with full affine span in Rd\mathbb{R}^{d}), both up to logarithmic factors.

  • Because KK enters our bound only through log⁡K\log K, running CRW-FTRL on a fine discretization of a compact action set yields O~(dT+dC)\widetilde{O}(d\sqrt{T}+dC) regret for general action sets with bounded reward vectors (Remark 5.3). This answers the question of Liu et al. [36] on the statistical rate and improves the leading term of their bound from d3T\sqrt{d^{3}T} to dTd\sqrt{T}. Together with their result for weak adversaries, it shows that corrupted adversarial linear bandits attain the same minimax rates as corrupted stochastic linear bandits under both corruption models. Since the discretization has exponentially many actions in dd, this reduction is not computationally efficient, and achieving the same rate with a computationally efficient algorithm remains open.

Notation. For nonnegative sequences {xn}\{x_n\} and {yn}\{y_n\}, we write xn=O(yn)x_n=O(y_n) if lim sup⁡n→∞xn/yn<∞\limsup_{n\to\infty}x_n/y_n<\infty, yn=Ω(xn)y_n=\Omega(x_n) if xn=O(yn)x_n=O(y_n), and yn=Θ(xn)y_n=\Theta(x_n) if xn=O(yn)x_n=O(y_n) and xn=Ω(yn)x_n=\Omega(y_n). We further employ O~(⋅)\widetilde{O}(\cdot), Ω~(⋅)\widetilde{\Omega}(\cdot), and Θ~(⋅)\widetilde{\Theta}(\cdot) to hide polylogarithmic factors. We denote [N]:={1,⋯ ,N}[N]:=\{1,\cdots,N\} for any positive integer NN, and write ΔK:={p∈RK:pi≥0, ∑i=1Kpi=1}\Delta_K:=\{p\in\mathbb{R}^{K}:p_i\ge0,\ \sum_{i=1}^{K}p_i=1\} for the probability simplex over [K][K]. Boldfaced lowercase and uppercase letters are reserved for vectors and matrices, respectively. We denote by ei\mathbf{e}_i the ii-th standard basis vector, by 0\mathbf{0} and 1\mathbf{1} the all-zeros and all-ones vectors, by ∥⋅∥\|\cdot\| the Euclidean norm, and by ⟨x,y⟩:=x⊤y\langle\mathbf{x},\mathbf{y}\rangle:=\mathbf{x}^{\top}\mathbf{y} the standard inner product for vectors x,y\mathbf{x},\mathbf{y} of the same dimension. For symmetric matrices A\mathbf{A} and B\mathbf{B}, we write A⪰B\mathbf{A}\succeq\mathbf{B} (resp. A≻B\mathbf{A}\succ\mathbf{B}) if A−B\mathbf{A}-\mathbf{B} is positive semidefinite (resp. positive definite), and use λmax⁡(⋅)\lambda_{\max}(\cdot), tr⁡(⋅)\operatorname{tr}(\cdot), and det⁡(⋅)\det(\cdot) to denote the largest eigenvalue, trace, and determinant.

Related Work

Adversarial Linear Bandits. Adversarial linear bandits were introduced by Awerbuch and Kleinberg [4] and McMahan and Blum [39]. Dani et al. [16] proposed GeometricHedge, which runs exponential weights over the action set and explores with a barycentric spanner, and proved an Ω(dT)\Omega(d\sqrt{T}) lower bound on the hypercube with i.i.d. losses. Abernethy et al. [1] gave a computationally efficient algorithm with O(dϑTlog⁡T)O(d\sqrt{\vartheta T}\log T) regret by running FTRL with a ϑ\vartheta-self-concordant barrier (yielding O~(dT)\widetilde{O}(d\sqrt{T}) when ϑ=O(1)\vartheta=O(1) and O~(d3/2T)\widetilde{O}(d^{3/2}\sqrt{T}) for a general ϑ=O(d)\vartheta=O(d) barrier). Cesa-Bianchi and Lugosi [13] and Bubeck et al. [12] refined the exploration distribution of exponential weights, and Bubeck et al. [12] obtained O(dTlog⁡K)O(\sqrt{dT\log K}) regret for KK actions by exploring according to John’s theorem. High-probability bounds against adaptive adversaries are more delicate, and existing approaches control the variance of importance weighting either through biased reward estimates and bonuses ([6, 46]) or by combining unbiased estimators with an increasing learning rate schedule (Lee et al. [31]). Zimmert and Lattimore [46] obtained almost minimax optimal high-probability bounds, using exponential weights for finite action sets and, for general action sets, FTRL with a log-determinant potential over lifted covariance matrices of the action distribution. In the presence of corruptions, Liu et al. [36] extended this lifted log-determinant FTRL approach to weak adversaries and used continuous exponential weights against strong adversaries, while Cheng et al. [14] studied adversarial bandit linear optimization over convex action sets with globally bounded perturbations against an oblivious adversary. Building on the principle of inducing a negative comparator-dependent FTRL penalty to cancel estimation or corruption errors ([19, 46, 36] and the monotone matrix envelope of Liu et al. [36], CRW-FTRL runs FTRL over the KK-dimensional simplex with a radius-weighted entropy regularizer, while using a log-determinant barrier in an inner problem that selects the per-action radii for a normalized kernel estimator.

Multi-Armed Bandits with Adversarial Corruptions. Lykouris et al. [37] introduced stochastic multi-armed bandits with adversarial corruptions and proposed a corruption-agnostic algorithm whose regret incurs a multiplicative O~(KC)\widetilde{O}(KC) factor on top of the corruption-free regret. Gupta et al. [21] improved this to a bound in which the corruption enters additively as O(KC)O(KC). In both works, the adversary corrupts the rewards of all arms before the learner draws its arm, which corresponds to the weak adversary in our terminology. For adversarial multi-armed bandits, Yang et al. [42] studied oblivious clean rewards with corruptions chosen after observing the pulled arm and obtained O(KTlog⁡K+KClog⁡T)O(\sqrt{KT\log K}+KC\log T) regret for a known corruption budget CC, whereas Zimmert and Seldin [47] developed a best-of-both-worlds algorithm that is simultaneously optimal for stochastic and adversarial rewards and remains robust in corrupted stochastic environments. Corruption robustness has also been studied in episodic reinforcement learning ([38, 41]). From the attacker’s perspective, Jun et al. [25] and Liu and Shroff [35] showed that a small corruption budget suffices to steer standard multi-armed bandit algorithms toward a target arm.

Stochastic Linear Bandits with Adversarial Corruptions. In the linear setting, Garcelon et al. [20] showed that standard linear contextual bandit algorithms are similarly vulnerable to targeted data poisoning attacks. On the defense side, Li et al. (2019) obtained gap-dependent bounds for stochastic linear bandits against a weak adversary, measuring the corruption by its per-round maximum over actions. Bogunovic et al. [11] considered a strong adversary that observes the pulled arm and the noise before corrupting, proposed a robust phased elimination algorithm with O~(dTlog⁡K+d3/2/C)\widetilde{O}(\sqrt{dT}\log K+d^{3/2}/C) regret for known CC, and proved that any algorithm must incur Ω(dC)\Omega(dC) regret even on an instance with K=dK=d orthogonal arms; see also Bogunovic et al. [10] for Gaussian process bandits. Best-of-both-worlds algorithms for linear and linear contextual bandits that remain robust to corrupted stochastic rewards were developed by Lee et al. [32] and Kuroki et al. [28]. For linear contextual bandits, Zhao et al. [45] (under weak corruption) and Ding et al. [18] (under strong corruption) obtained corruption terms with a polynomial dependence on TT, and He et al. (2022) achieved the nearly optimal O~(dT+dC)\widetilde{O}(d\sqrt{T}+dC) regret against a strong adversary by weighting each observation according to its uncertainty. This uncertainty-weighting idea has since been extended to nonlinear function classes (Ye et al., 2023), variance-aware bounds (Yu et al., 2025), and dueling bandits ([17]). A closely related line of work studies misspecified linear bandits, where the reward deviates from a linear function by a bounded amount in every round ([30, 19, 40]), and Liu et al. [36] unified the weak (C∞C_{\infty}) and strong (CC) corruption measures across stochastic and adversarial linear bandits. Table 1 compares our result with the most related work on linear bandits with corruptions.

References

  1. [1]Abernethy, J., Hazan, E. and Rakhlin, A. (2008). Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the 21st Annual Conference on Learning Theory (COLT).
  2. [2]Aliprantis, C. D. and Border, K. C. (2006). Infinite Dimensional Analysis: A Hitchhiker’s Guide. 3rd ed. Springer.
  3. [3]Auer, P., Cesa-Bianchi, N., Freund, Y. and Schapire, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM Journal on Computing 32 48–77.DOI
  4. [4]Awerbuch, B. and Kleinberg, R. D. (2004). Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC). ACM.
  5. [5]Azuma, K. (1967). Weighted sums of certain dependent random variables. Tohoku Mathematical Journal 19 357–367.DOI
  6. [6]Bartlett, P. L., Dani, V., Hayes, T. P., Kakade, S. M., Rakhlin, A. and Tewari, A. (2008). High-probability regret bounds for bandit online linear optimization. In Proceedings of the 21st Annual Conference on Learning Theory (COLT).
  7. [7]Berge, C. (1963). Topological Spaces: Including a Treatment of Multi-Valued Functions, Vector Spaces, and Convexity. Macmillan.
  8. [8]Beygelzimer, A., Langford, J., Li, L., Reyzin, L. and Schapire, R. (2011). Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS).
  9. [9]Bhatia, R. (2007). Positive Definite Matrices. Princeton University Press.
  10. [10]Bogunovic, I., Krause, A. and Scarlett, J. (2020). Corruption-tolerant Gaussian process bandit optimization. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 108 of Proceedings of Machine Learning Research.arxiv.org/abs/2003.01971
  11. [11]Bogunovic, I., Losalka, A., Krause, A. and Scarlett, J. (2021). Stochastic linear bandits robust to adversarial attacks. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 130 of Proceedings of Machine Learning Research.arxiv.org/abs/2007.03285
  12. [12]Bubeck, S., Cesa-Bianchi, N. and Kakade, S. M. (2012). Towards minimax policies for online linear optimization with bandit feedback. In Proceedings of the 25th Annual Conference on Learning Theory (COLT), vol. 23 of Proceedings of Machine Learning Research. PMLR.arxiv.org/abs/1202.3079
  13. [13]Cesa-Bianchi, N. and Lugosi, G. (2012). Combinatorial bandits. Journal of Computer and System Sciences 78 1404–1422.
  14. [14]Cheng, Z., Hatano, K. and Takimoto, E. (2026). Adversarial bandit optimization with globally bounded perturbations to linear losses. arXiv preprint arXiv:2603.26066 .arxiv.org/abs/2603.26066
  15. [15]Cohen, M. B. and Peng, R. (2015). Lₚ row sampling by Lewis weights. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC).
  16. [16]Dani, V., Hayes, T. P. and Kakade, S. M. (2007). The price of bandit information for online optimization. In Advances in Neural Information Processing Systems (NIPS), vol. 20. Curran Associates, Inc.
  17. [17]Di, Q., He, J. and Gu, Q. (2025). Nearly optimal algorithms for contextual dueling bandits from adversarial feedback. In Proceedings of the 42nd International Conference on Machine Learning (ICML), vol. 267 of Proceedings of Machine Learning Research.arxiv.org/abs/2404.10776
  18. [18]Ding, Q., Hsieh, C.-J. and Sharpnack, J. (2022). Robust stochastic linear contextual bandits under adversarial attacks. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 151 of Proceedings of Machine Learning Research.arxiv.org/abs/2106.02978
  19. [19]Foster, D. J., Gentile, C., Mohri, M. and Zimmert, J. (2020). Adapting to misspecification in contextual bandits. In Advances in Neural Information Processing Systems (NeurIPS), vol. 33. Curran Associates, Inc.arxiv.org/abs/2107.05745
  20. [20]Garcelon, E., Rozière, B., Meunier, L., Tarbouriech, J., Teytaud, O., Lazaric, A. and Pirotta, M. (2020). Adversarial attacks on linear contextual bandits. In Advances in Neural Information Processing Systems (NeurIPS), vol. 33.arxiv.org/abs/2002.03839
  21. [21]Gupta, A., Koren, T. and Talwar, K. (2019). Better algorithms for stochastic bandits with adversarial corruptions. In Proceedings of the 32nd Conference on Learning Theory (COLT), vol. 99 of Proceedings of Machine Learning Research.arxiv.org/abs/1902.08647
  22. [23]Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58 13–30.
  23. [24]Horn, R. A. and Johnson, C. R. (2012). Matrix Analysis. 2nd ed. Cambridge University Press.
  24. [25]Jun, K.-S., Li, L., Ma, Y. and Zhu, X. (2018). Adversarial attacks on stochastic bandits. In Advances in Neural Information Processing Systems (NeurIPS), vol. 31.arxiv.org/abs/1810.12188
  25. [26]Kiefer, J. and Wolfowitz, J. (1960). The equivalence of two extremum problems. Canadian Journal of Mathematics 12 363–366.
  26. [27]Kubo, F. and Ando, T. (1980). Means of positive linear operators. Mathematische Annalen 246 205–224.DOI
  27. [28]Kuroki, Y., Rumi, A., Tsuchiya, T., Vitale, F. and Cesa-Bianchi, N. (2024). Best-of-both-worlds algorithms for linear contextual bandits. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 238 of Proceedings of Machine Learning Research. PMLR.
  28. [29]Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.
  29. [30]Lattimore, T., Szepesvári, C. and Weisz, G. (2020). Learning with good feature representations in bandits and in RL with a generative model. In Proceedings of the 37th International Conference on Machine Learning (ICML), vol. 119 of Proceedings of Machine Learning Research.
  30. [31]Lee, C.-W., Luo, H., Wei, C.-Y. and Zhang, M. (2020). Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs. In Advances in Neural Information Processing Systems (NeurIPS), vol. 33. Curran Associates, Inc.arxiv.org/abs/2006.08040
  31. [32]Lee, C.-W., Luo, H., Wei, C.-Y., Zhang, M. and Zhang, X. (2021). Achieving near instance-optimality and minimax-optimality in stochastic and adversarial linear bandits simultaneously. In Proceedings of the 38th International Conference on Machine Learning (ICML), vol. 139 of Proceedings of Machine Learning Research. PMLR.arxiv.org/abs/2102.05858
  32. [33]Lewis, D. R. (1978). Finite dimensional subspaces of Lₚ. Studia Mathematica 63 207–212.
  33. [35]Liu, F. and Shroff, N. (2019). Data poisoning attacks on stochastic bandits. In Proceedings of the 36th International Conference on Machine Learning (ICML), vol. 97 of Proceedings of Machine Learning Research.arxiv.org/abs/1905.06494
  34. [36]Liu, H., Tajdini, A., Wagenmaker, A. and Wei, C.-Y. (2024). Corruption-robust linear bandits: Minimax optimality and gap-dependent misspecification. In Advances in Neural Information Processing Systems (NeurIPS), vol. 37.arxiv.org/abs/2410.07533
  35. [37]Lykouris, T., Mirrokni, V. and Leme, R. P. (2018). Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM.arxiv.org/abs/1803.09353
  36. [38]Lykouris, T., Simchowitz, M., Slivkins, A. and Sun, W. (2021). Corruption-robust exploration in episodic reinforcement learning. In Proceedings of the 34th Conference on Learning Theory (COLT), vol. 134 of Proceedings of Machine Learning Research.
  37. [39]McMahan, H. B. and Blum, A. (2004). Online geometric optimization in the bandit setting against an adaptive adversary. In Proceedings of the 17th Annual Conference on Learning Theory (COLT). Lecture Notes in Computer Science, Springer.
  38. [40]Neu, G. and Olkhovskaya, J. (2020). Efficient and robust algorithms for adversarial linear contextual bandits. In Proceedings of the 33rd Conference on Learning Theory (COLT), vol. 125 of Proceedings of Machine Learning Research. PMLR.arxiv.org/abs/2002.00287
  39. [41]Wei, C.-Y., Dann, C. and Zimmert, J. (2022). A model selection approach for corruption robust reinforcement learning. In Proceedings of the 33rd International Conference on Algorithmic Learning Theory (ALT), vol. 167 of Proceedings of Machine Learning Research.arxiv.org/abs/2110.03580
  40. [42]Yang, L., Hajiesmaili, M., Talebi, M. S., Lui, J. C. S. and Wong, W. S. (2020). Adversarial bandits with corruptions. In Advances in Neural Information Processing Systems (NeurIPS), vol. 33.
  41. [45]Zhao, H., Zhou, D. and Gu, Q. (2021). Linear contextual bandits with adversarial corruptions. arXiv preprint arXiv:2110.12615.arxiv.org/abs/2110.12615
  42. [46]Zimmert, J. and Lattimore, T. (2022). Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Proceedings of the 35th Conference on Learning Theory (COLT), vol. 178 of Proceedings of Machine Learning Research. PMLR.
  43. [47]Zimmert, J. and Seldin, Y. (2021). Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research 22 1–49.

Paper details

vlnc:W_5d5kqa9q
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Gemini 4 Argon, Claude Opus 5.5

View statement
Looking for related papers…
Contents