# Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 27 references that are in the map.
- First posted on arXiv 31 Jan 2023.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (2016)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2010.00081/) (2020)
- [Safe Linear Stochastic Bandits](https://mlsanity.com/paper/1911.09501/) (2019)
- [Thompson Sampling Algorithms for Mean-Variance Bandits](https://mlsanity.com/paper/2002.00232/) (2020)
- [Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measure](https://mlsanity.com/paper/1604.05257/) (2016)
- [Improved Algorithms for Conservative Exploration in Bandits](https://mlsanity.com/paper/2002.03221/) (2020)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Thompson Sampling Algorithms for Cascading Bandits](https://mlsanity.com/paper/1810.01187/) (2018)
- [A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits](https://mlsanity.com/paper/2108.11345/) (2021)
- [Constrained regret minimization for multi-criterion multi-armed bandits](https://mlsanity.com/paper/2006.09649/) (2020)
- [Risk-Aware Algorithms for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2112.01141/) (2021)

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

- [Bandits with Anytime Knapsacks](https://mlsanity.com/paper/2501.18560/) (2025)

## Abstract (arXiv)

Motivated by concerns about making online decisions that incur undue amount of risk at each time step, in this paper, we formulate the probably anytime-safe stochastic combinatorial semi-bandits problem. In this problem, the agent is given the option to select a subset of size at most K from a set of L ground items. Each item is associated to a certain mean reward as well as a variance that represents its risk. To mitigate the risk that the agent incurs, we require that with probability at least 1-δ, over the entire horizon of time T, each of the choices that the agent makes should contain items whose sum of variances does not exceed a certain variance budget. We call this probably anytime-safe constraint. Under this constraint, we design and analyze an algorithm sc PASCombUCB that minimizes the regret over the horizon of time T. By developing accompanying information-theoretic lower bounds, we show that under both the problem-dependent and problem-independent paradigms, sc PASCombUCB is almost asymptotically optimal. Experiments are conducted to corroborate our theoretical findings. Our problem setup, the proposed sc PASCombUCB algorithm, and novel analyses are applicable to domains such as recommendation systems and transportation in which an agent is allowed to choose multiple items at a single time step and wishes to control the risk over the whole time horizon.