# Risk-Aware Algorithms for Combinatorial Semi-Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 19 references that are in the map.
- First posted on arXiv 2 Dec 2021.

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

- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits](https://mlsanity.com/paper/1401.1123/) (2014)
- [Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards](https://mlsanity.com/paper/1906.00569/) (2019)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem](https://mlsanity.com/paper/1905.03125/) (2019)

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

- [Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2301.13393/) (2023)
- [Risk-Sensitive Agent Compositions](https://mlsanity.com/paper/2506.04632/) (2025)

## Abstract (arXiv)

In this paper, we study the stochastic combinatorial multi-armed bandit problem under semi-bandit feedback. While much work has been done on algorithms that optimize the expected reward for linear as well as some general reward functions, we study a variant of the problem, where the objective is to be risk-aware. More specifically, we consider the problem of maximizing the Conditional Value-at-Risk (CVaR), a risk measure that takes into account only the worst-case rewards. We propose new algorithms that maximize the CVaR of the rewards obtained from the super arms of the combinatorial bandit for the two cases of Gaussian and bounded arm rewards. We further analyze these algorithms and provide regret bounds. We believe that our results provide the first theoretical insights into combinatorial semi-bandit problems in the risk-aware case.