Conservative Bandits

By Yifan Wu, R. Shariff, Tor Lattimore, Csaba Szepesvari. 2016

110 citations recorded by the source corpus.

We study a novel multi-armed bandit problem that models the challenge faced by a company wishing to explore new strategies to maximize revenue whilst simultaneously maintaining their revenue above a fixed baseline, uniformly over time. While previous work addressed the problem under the weaker requirement of maintaining the revenue constraint only at a given fixed time in the future, the design of those algorithms makes them unsuitable under the more stringent constraints. We consider both the stochastic and the adversarial settings, where we propose natural yet novel strategies and analyze the price for maintaining the constraints. Amongst other things, we prove both high probability and expectation bounds on the regret, while we also consider both the problem of maintaining the constraints with high probability or expectation. For the adversarial setting the price of maintaining the constraint appears to be higher, at least for the algorithm considered. A lower bound is given showing that the algorithm for the stochastic setting is almost optimal. Empirical results obtained in synthetic environments complement our theoretical findings.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Exploiting the Natural Exploration In Contextual Bandits (2017, result): “tasets. This study provides strong empirical validation of our theoretical ndings. Conservative Bandits. Our approach is also related to recent literature on designing conservative bandit algorithms (Wu et al. 2016, Kazerouni et al. 2016) that operate within a safety margin, i.e., the regret is cons”
Recent advances in reinforcement learning in finance (2021, result): “For more details about these variants and solutions, see Xiao et al. (2020). In addition to the mean–variance framework, other major paradigms in portfolio optimization are the Kelly Criterion and Risk Parity.”
Bandit Algorithms (2020, background): “Like partial monitoring this problem exhibits many challenges and is not yet well understood [Wu et al., 2015].”
Constrained Efficient Global Optimization of Expensive Black-box Functions (2022, methodology): “For the setting where no constraint violations are tolerated, a group of safe optimization methods has been developed (Sui et al., 2015; Wu et al., 2016; Sui et al., 2018; Turchetta et al., 2020; Moradipari et al., 2020; Amani et al., 2020).”