# Safe Linear Bandits over Unknown Polytopes

arXiv: https://arxiv.org/abs/2209.13694 · HTML: https://mlsanity.com/paper/2209.13694/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 31 references that are in the map.
- First posted on arXiv 27 Sep 2022.

## Builds on (most cited first, 20 of 20)

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Safe Exploration in Finite Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/1606.04753/) (2016)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [Safe Linear Thompson Sampling with Side Information](https://mlsanity.com/paper/1911.02156/) (2019)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/1810.10895/) (2018)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk](https://mlsanity.com/paper/2204.00706/) (2022)
- [Norm-Agnostic Linear Bandits](https://mlsanity.com/paper/2205.01257/) (2022)
- [On the Complexity of Bandit Linear Optimization](https://mlsanity.com/paper/1408.2368/) (2014)

## Built on by (most cited first, 14 of 14)

- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [Online Bidding under RoS Constraints without Knowing the Value](https://mlsanity.com/paper/2503.03195/) (2025)
- [Data-Dependent Regret Bounds for Constrained MABs](https://mlsanity.com/paper/2505.20010/) (2025)
- [Replicable Constrained Bandits](https://mlsanity.com/paper/2602.14580/) (2026)
- [Learning Decision-Sufficient Representations for Linear Optimization](https://mlsanity.com/paper/2603.18551/) (2026)
- [Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs](https://mlsanity.com/paper/2309.15395/) (2023)
- [Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback](https://mlsanity.com/paper/2412.03983/) (2024)
- [Constrained Linear Thompson Sampling](https://mlsanity.com/paper/2503.02043/) (2025)
- [The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification](https://mlsanity.com/paper/2510.01020/) (2025)
- [Multi-Armed Bandits with Minimum Aggregated Revenue Constraints](https://mlsanity.com/paper/2510.12523/) (2025)
- [A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression](https://mlsanity.com/paper/2602.05019/) (2026)
- [Truly Adapting to Adversarial Constraints in Constrained MABs](https://mlsanity.com/paper/2602.14543/) (2026)
- [When Can Safe Controllers Adapt? Information before Commitment](https://mlsanity.com/paper/2607.16895/) (2026)
- [Instance-Dependent Regret for CMDPs with Step-Wise Constraints](https://mlsanity.com/paper/2610.02520/) (2026)

## Abstract (arXiv)

The safe linear bandit problem (SLB) is an online approach to linear programming with unknown objective and unknown roundwise constraints, under stochastic bandit feedback of rewards and safety risks of actions. We study the tradeoffs between efficacy and smooth safety costs of SLBs over polytopes, and the role of aggressive doubly-optimistic play in avoiding the strong assumptions made by extant pessimistic-optimistic approaches. We first elucidate an inherent hardness in SLBs due the lack of knowledge of constraints: there exist `easy' instances, for which suboptimal extreme points have large `gaps', but on which SLB methods must still incur Omega(√T) regret or safety violations, due to an inability to resolve unknown optima to arbitrary precision. We then analyse a natural doubly-optimistic strategy for the safe linear bandit problem, DOSS, which uses optimistic estimates of both reward and safety risks to select actions, and show that despite the lack of knowledge of constraints or feasible points, DOSS simultaneously obtains tight instance-dependent O(log2 T) bounds on efficacy regret, and tilde O(√T) bounds on safety violations. Further, when safety is demanded to a finite precision, violations improve to O(log2 T). These results rely on a novel dual analysis of linear bandits: we argue that algoname proceeds by activating noisy versions of at least d constraints in each round, which allows us to separately analyse rounds where a `poor' set of constraints is activated, and rounds where `good' sets of constraints are activated. The costs in the former are controlled to O(log2 T) by developing new dual notions of gaps, based on global sensitivity analyses of linear programs, that quantify the suboptimality of each such set of constraints. The latter costs are controlled to O(1) by explicitly analysing the solutions of optimistic play.