mlsanityData to 7 Oct 2026

A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning

arXiv 2106.11692 ↗First posted 22 Jun 2021cs.LG stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

In this paper, we present a reduction-based framework for conservative bandits and RL, in which our core technique is to calculate the necessary and sufficient budget obtained from running the baseline policy. For lower bounds, we improve the existing lower bound for conservative multi-armed bandits and obtain new lower bounds for conservative linear bandits, tabular RL and low-rank MDP, through a black-box reduction that turns a certain lower bound in the nonconservative setting into a new lower bound in the conservative setting. For upper bounds, in multi-armed bandits, linear bandits and tabular RL, our new upper bounds tighten or match existing ones with significantly simpler analyses. We also obtain a new upper bound for conservative low-rank MDP.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 24 of its 32 references that are in the map. First posted on arXiv 22 Jun 2021.

Builds on

24 of 32 references.

References · 24

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  4. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  6. 2020Exploration-Exploitation in Constrained MDPscited by 146
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  8. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  9. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  10. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  11. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  12. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
12 more
  1. 2020Stochastic Bandits with Linear Constraintscited by 68
  2. 2016Conservative Banditscited by 58
  3. 2016Conservative Contextual Linear Banditscited by 56
  4. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  5. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 33
  6. 2020Conservative Exploration in Reinforcement Learningcited by 20
  7. 2020Improved Algorithms for Conservative Exploration in Banditscited by 16
  8. 2020Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RLcited by 16
  9. 2020A One-Size-Fits-All Solution to Conservative Bandit Problemscited by 5
  10. 2018Conservative Exploration using Interleavingcited by 4
  11. 2019Contextual Combinatorial Conservative Banditscited by 4
  12. 2021Conservative Contextual Combinatorial Cascading Banditcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 7; 2024: 1; 2025: 0; 2026: 1.

9 papers.

  1. 2023Pairwise Proximal Policy Optimization: Harnessing Relative Feedback for LLM Alignmentcited by 57
  2. 2023Learning for Edge-Weighted Online Bipartite Matching with Robustness Guaranteescited by 5
  3. 2023Robustified Learning for Online Optimization with Memory Costscited by 4
  4. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 4
  5. 2023Robust Learning for Smoothed Online Convex Optimization with Feedback Delaycited by 3
  6. 2023Learning-Augmented Decentralized Online Convex Optimization in Networkscited by 1
  7. 2023Anytime-Competitive Reinforcement Learning with Policy Priorcited by 1
  8. 2024SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDPcited by 1
  9. 2026Reserve-Aware Contrast Certificates for Conservative Bandits with Uncertain Baselinescited by 0