mlsanityData to 7 Oct 2026

Conservative Bandits

arXiv 1602.04282 ↗First posted 13 Feb 2016stat.ML cs.LGcited by 58

Not on the map. Why?

Abstract (arXiv)

We study a novel multi-armed bandit problem that models the challenge faced by a company wishing to explore new strategies to maximize revenue whilst simultaneously maintaining their revenue above a fixed baseline, uniformly over time. While previous work addressed the problem under the weaker requirement of maintaining the revenue constraint only at a given fixed time in the future, the algorithms previously proposed are unsuitable due to their design under the more stringent constraints. We consider both the stochastic and the adversarial settings, where we propose, natural, yet novel strategies and analyze the price for maintaining the constraints. Amongst other things, we prove both high probability and expectation bounds on the regret, while we also consider both the problem of maintaining the constraints with high probability or expectation. For the adversarial setting the price of maintaining the constraint appears to be higher, at least for the algorithm considered. A lower bound is given showing that the algorithm for the stochastic setting is almost optimal. Empirical results obtained in synthetic environments complement our theoretical findings.

Key facts. Cited by 58 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Feb 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 11; 2023: 14; 2024: 4; 2025: 6; 2026: 11.

58 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  2. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  3. 2023Performative Prediction: Past and Futurecited by 52
  4. 2022Regret Minimization with Performative Feedbackcited by 40
  5. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  6. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  7. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  8. 2021Online certification of preference-based fairness for personalized recommender systemscited by 22
  9. 2022Almost Optimal Variance-Constrained Best Arm Identificationcited by 16
  10. 2022Safe Exploration for Efficient Policy Evaluation and Comparisoncited by 15
  11. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 15
  12. 2024On Safety in Safe Bayesian Optimizationcited by 15
38 more
  1. 2022Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Riskcited by 14
  2. 2022Safe Linear Bandits over Unknown Polytopescited by 13
  3. 2021Bandit Algorithms for Precision Medicinecited by 12
  4. 2021A Reduction-Based Framework for Conservative Bandits and Reinforcement Learningcited by 9
  5. 2021Robust Bandit Learning with Imperfect Contextcited by 8
  6. 2023Directional Optimism for Safe Linear Banditscited by 8
  7. 2022Leveraging Initial Hints for Free in Stochastic Linear Banditscited by 7
  8. 2021Robust Generalization and Safe Query-Specialization in Counterfactual Learning to Rankcited by 6
  9. 2022Stochastic Conservative Contextual Linear Banditscited by 6
  10. 2021ESCADA: Efficient Safety and Context Aware Dose Allocation for Precision Medicinecited by 5
  11. 2023Learning for Edge-Weighted Online Bipartite Matching with Robustness Guaranteescited by 5
  12. 2021Safe Data Collection for Offline and Online Policy Learningcited by 4
  13. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 4
  14. 2023Price of Safety in Linear Best Arm Identificationcited by 4
  15. 2025Balancing optimism and pessimism in offline-to-online learningcited by 4
  16. 2021Conservative Contextual Combinatorial Cascading Banditcited by 3
  17. 2022Safety Aware Changepoint Detection for Piecewise i.i.d. Banditscited by 2
  18. 2024Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraintscited by 2
  19. 2021Conservative Policy Construction Using Variational Autoencoders for Logged Data with Missing Valuescited by 1
  20. 2023Probably Anytime-Safe Stochastic Combinatorial Semi-Banditscited by 1
  21. 2023Learning-Augmented Decentralized Online Convex Optimization in Networkscited by 1
  22. 2023Anytime-Competitive Reinforcement Learning with Policy Priorcited by 1
  23. 2024SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDPcited by 1
  24. 2025Best of Both Worlds: Regret Minimization versus Minimax Playcited by 1
  25. 2025Multi-Agent Stage-wise Conservative Linear Banditscited by 1
  26. 2021Conservative Optimistic Policy Optimization via Multiple Importance Samplingcited by 0
  27. 2022Keeping Minimal Experience to Achieve Efficient Interpretable Policy Distillationcited by 0
  28. 2023Leveraging User-Triggered Supervision in Contextual Banditscited by 0
  29. 2023Exploration of Unranked Items in Safe Online Learning to Re-Rankcited by 0
  30. 2023Disincentivizing Polarization in Social Networkscited by 0
  31. 2023Conservative Exploration for Policy Optimization via Off-Policy Policy Evaluationcited by 0
  32. 2023Zero-Inflated Banditscited by 0
  33. 2025Bandits with Anytime Knapsackscited by 0
  34. 2025Multi-Armed Bandits with Minimum Aggregated Revenue Constraintscited by 0
  35. 2025Learning When Not to Learn: Risk-Sensitive Abstention in Bandits with Unbounded Rewardscited by 0
  36. 2026Learning Safely Without Knowing the World:COMPASS-Hedgecited by 0
  37. 2026Quality-preserving Model for Electronics Production Quality Tests Reductioncited by 0
  38. 2026Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidycited by 0

50 most cited of 58 All 58 (JSON)