Best of both worlds: Stochastic & adversarial best-arm identification

• URL: http://arxiv.org/abs/2604.14860v1
• Date: Thu, 16 Apr 2026 10:47:50 GMT
• Title: Best of both worlds: Stochastic & adversarial best-arm identification
• Abstract summary: We study bandit best-arm identification with arbitrary and potentially adversarial rewards.<n>A simple random uniform learner obtains the optimal rate of error in the adversarial scenario.<n>We show that designing such a learner is impossible in general.
• Score: 37.84473422648414
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.

Related papers

• Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness [13.802167452101909]
  Prior work established that the optimal error under such instance-targeted poisoning attacks scales as $Theta(deta)$.<n>We show that the optimal excess error is $tildeTheta(sqrtdeta)$, answering one of the main open problems left by Hanneke et al.
  arXiv  Detail & Related papers  (2025-06-03T16:53:20Z)
• Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs [32.29254118429081]
  We show that the optimal mistake bound under bandit feedback is at most $O(k)$ times higher than the optimal mistake bound in the full information case. We also present nearly optimal bounds of $tildeTheta(k)$ on the gap between randomized and deterministic learners.
  arXiv  Detail & Related papers  (2024-02-12T07:20:05Z)
• Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
  dominance models risk-averse preferences for decision making with uncertain outcomes. Despite theoretically appealing, the application of dominance in machine learning has been scarce. We first generalize the dominance concept to enable feasible comparisons between any arbitrary pair of random variables. We then develop a simple and efficient approach for finding the optimal solution in terms of dominance.
  arXiv  Detail & Related papers  (2024-02-05T03:21:23Z)
• A Minimaximalist Approach to Reinforcement Learning from Human Feedback [49.45285664482369]
  We present Self-Play Preference Optimization (SPO), an algorithm for reinforcement learning from human feedback. Our approach is minimalist in that it does not require training a reward model nor unstable adversarial training. We demonstrate that on a suite of continuous control tasks, we are able to learn significantly more efficiently than reward-model based approaches.
  arXiv  Detail & Related papers  (2024-01-08T17:55:02Z)
• Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances [10.470114319701576]
  We propose a strategy that estimates variances during an adaptive experiment and draws arms with a ratio of the estimated standard deviations. Our results suggest that under the worst-case scenario characterized by the small-gap regime, our strategy, which employs estimated variance, is optimalally even when the variances are unknown.
  arXiv  Detail & Related papers  (2023-12-20T03:28:49Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  Multi-armed bandits are a sequential-decision-making framework, where, at each interaction step, the learner selects an arm and observes a reward. We consider the scenario in which the learner has access to a set of mediators, each of which selects the arms on the agent's behalf according to a and possibly unknown policy. We propose a sequential decision-making strategy for discovering the best arm under the assumption that the mediators' policies are known to the learner.
  arXiv  Detail & Related papers  (2023-08-29T18:18:21Z)
• Best of Both Worlds Model Selection [39.211071446838474]
  We study the problem of model selection in bandit scenarios in the presence of nested policy classes. Our approach requires that each base learner comes with a candidate regret bound that may or may not hold. These are the first theoretical results that achieve best of both world (stochastic and adversarial) guarantees while performing model selection in (linear) bandit scenarios.
  arXiv  Detail & Related papers  (2022-06-29T20:57:30Z)
• Optimal Fixed-Budget Best Arm Identification using the Augmented Inverse Probability Estimator in Two-Armed Gaussian Bandits with Unknown Variances [27.122181278234617]
  We consider the fixed-budget best arm identification problem in two-armed Gaussian bandits with unknown variances. We propose a strategy comprising a sampling rule with randomized sampling (RS) following the estimated target allocation probabilities of arm draws. We show that the proposed strategy is agnostically optimal when the sample size becomes infinitely large and the gap between the two arms goes to zero.
  arXiv  Detail & Related papers  (2022-01-12T13:38:33Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  We introduce a theory for multi-armed bandits where the values are the modes of the reward distributions instead of the mean. We show in simulations that our algorithms are robust to perturbation of the arms by adversarial noise sequences.
  arXiv  Detail & Related papers  (2020-03-05T21:29:27Z)
• Attacks Which Do Not Kill Training Make Adversarial Learning Stronger [85.96849265039619]
  Adversarial training based on the minimax formulation is necessary for obtaining adversarial robustness of trained models. We argue that adversarial training is to employ confident adversarial data for updating the current model.
  arXiv  Detail & Related papers  (2020-02-26T01:04:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.