mlsanityData to 7 Oct 2026

Robust Lipschitz Bandits to Adversarial Corruptions

arXiv 2305.18543 ↗First posted 29 May 2023cs.LG stat.MLcited by 15

Not on the map. Why?

Abstract (arXiv)

Lipschitz bandit is a variant of stochastic bandits that deals with a continuous arm set defined on a metric space, where the reward function is subject to a Lipschitz constraint. In this paper, we introduce a new problem of Lipschitz bandits in the presence of adversarial corruptions where an adaptive adversary corrupts the stochastic rewards up to a total budget C. The budget is measured by the sum of corruption levels across the time horizon T. We consider both weak and strong adversaries, where the weak adversary is unaware of the current action before the attack, while the strong one can observe it. Our work presents the first line of robust Lipschitz bandit algorithms that can achieve sub-linear regret under both types of adversary, even when the total budget of corruption C is unrevealed to the agent. We provide a lower bound under each type of adversary, and show that our algorithm is optimal under the strong case. Finally, we conduct experiments to illustrate the effectiveness of our algorithms against two classic kinds of attacks.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 24 of its 42 references that are in the map. First posted on arXiv 29 May 2023.

Builds on

24 of 42 references.

References · 24

  1. 2019Introduction to Multi-Armed Banditscited by 475
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  3. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  4. 2018Learning to Optimize under Non-Stationaritycited by 85
  5. 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
  6. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  7. 2013Bandits and Experts in Metric Spacescited by 63
  8. 2014Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithmscited by 59
  9. 2018Adversarial Attacks on Stochastic Banditscited by 56
  10. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  11. 2018Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Banditcited by 49
  12. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
12 more
  1. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  2. 2020Adversarial Attacks on Linear Contextual Banditscited by 34
  3. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  4. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  5. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 23
  6. 2021Lipschitz Bandits with Batched Feedbackcited by 21
  7. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  8. 2020A Fast and Robust Method for Global Topological Functional Optimizationcited by 15
  9. 2021Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithmscited by 10
  10. 2020Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuningcited by 6
  11. 2023PyXAB -- A Python Library for X-Armed Bandit and Online Blackbox Optimization Algorithmscited by 4
  12. 2023Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Banditscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 4; 2025: 3; 2026: 6.

15 papers.

Sort:

By area:

  1. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  2. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  3. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  4. 2024Statistical Guarantees for Lifelong Reinforcement Learning using PAC-Bayes Theorycited by 7
  5. 2024Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximationcited by 6
  6. 2025Quantum Lipschitz Banditscited by 4
  7. 2025Non-Stationary Lipschitz Banditscited by 3
  8. 2024Stochastic Bandits Robust to Adversarial Attackscited by 1
  9. 2025Lipschitz Bandits with Stochastic Delayed Feedbackcited by 1
  10. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  11. 2026Lipschitz Dueling Bandits over Continuous Action Spacescited by 1
  12. 2026Instance-dependent Stochastic Lipschitz banditcited by 0
3 more
  1. 2026Leveraging Similarities in Multi-Armed Banditscited by 0
  2. 2026Lipschitz Bandits with Arbitrary Feedback Delayscited by 0
  3. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochscited by 0