# Satisficing in multi-armed bandit problems

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2015.

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

- [Non-Stationary Representation Learning in Sequential Linear Bandits](https://mlsanity.com/paper/2201.04805/) (2022)
- [Robust Bayesian Satisficing](https://mlsanity.com/paper/2308.08291/) (2023)
- [Contextual Combinatorial Multi-output GP Bandits with Group Constraints](https://mlsanity.com/paper/2111.14778/) (2021)
- [Prescriptive Machine Learning for Automated Decision Making: Challenges and Opportunities](https://mlsanity.com/paper/2112.08268/) (2021)
- [Policy Testing in Markov Decision Processes](https://mlsanity.com/paper/2505.15342/) (2025)
- [Representation Learning for Context-Dependent Decision-Making](https://mlsanity.com/paper/2205.05820/) (2022)
- [Robust Satisficing Gaussian Process Bandits Under Adversarial Attacks](https://mlsanity.com/paper/2506.01625/) (2025)
- [Reciprocal Learning](https://mlsanity.com/paper/2408.06257/) (2024)
- [Maximally Robust Satisficing Bayesian Optimization](https://mlsanity.com/paper/2607.13652/) (2026)

## Abstract (arXiv)

Satisficing is a relaxation of maximizing and allows for less risky decision making in the face of uncertainty. We propose two sets of satisficing objectives for the multi-armed bandit problem, where the objective is to achieve reward-based decision-making performance above a given threshold. We show that these new problems are equivalent to various standard multi-armed bandit problems with maximizing objectives and use the equivalence to find bounds on performance. The different objectives can result in qualitatively different behavior; for example, agents explore their options continually in one case and only a finite number of times in another. For the case of Gaussian rewards we show an additional equivalence between the two sets of satisficing objectives that allows algorithms developed for one set to be applied to the other. We then develop variants of the Upper Credible Limit (UCL) algorithm that solve the problems with satisficing objectives and show that these modified UCL algorithms achieve efficient satisficing performance.