Satisficing in Multi-Armed Bandit Problems

DOI10.1109/TAC.2016.2644380MaRDI QIDQ4589439zbMATH OpenOpenAlexFDO

Authors Paul Reverdy, Vaibhav Srivastava, Naomi Ehrich Leonard

Publication date 10 November 2017

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.07638

Mathematics Subject Classification ID

Sequential statistical analysis (62L10) Probabilistic games; gambling (91A60)

Abstract: 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.

Cited in

(6)

• On Optimal Satisficing: How Simple Policies Can Achieve Excellent Results
• An incentive-compatible multi-armed bandit mechanism
• scientific article; zbMATH DE number 3867090 (Why is no real title available?)
• Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives
• scientific article; zbMATH DE number 7038557 (Why is no real title available?)
• A Structured Multiarmed Bandit Problem and the Greedy Policy

This page was built for publication: Satisficing in Multi-Armed Bandit Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589439)