Learning under Invariable Bayesian Safety

Gal Bahar, Omer Ben-Porat, Kevin Leyton-Brown, Moshe TennenholtzarXiv 2020 · arXiv

Abstract

In high-stakes decision-making environments such as clinical trials or financial management, the traditional "explore-and-exploit" paradigm of multi-armed bandits faces significant ethical and legal hurdles. This paper introduces a rigorous standard termed Invariable Bayesian Safety, which mandates that the expected reward of an action must exceed a safety threshold in every single round. We present the SEGB (Safe Exploration via GMDP and Bernoulli Trials) algorithm, which treats known safe arms as a "budget" to fund the exploration of risky alternatives. We demonstrate that SEGB is asymptotically optimal and computationally efficient, achieving zero regret relative to an oracle while strictly adhering to safety constraints.

Introduction

Traditional Multi-Armed Bandit (MAB) algorithms prioritize minimizing cumulative regret, often at the cost of taking "risky" actions to gain information. However, in scenarios governed by fiduciary duties, an agent cannot knowingly provide a suboptimal treatment or investment strategy simply to learn. The core challenge is learning the optimal action when every interaction must be expected to be beneficial relative to a baseline.

This research, conducted by teams at the Technion and UBC, shifts the focus from "high probability" or "average" safety to a deterministic expectation-based safety in every round. By utilizing portfolios—randomized distributions over available actions—the agent can blend known safe actions with exploratory ones to maintain the required safety margin.

Methods and Framework

The authors model the environment as a Bayesian problem with static rewards, where the value of an arm is fixed but unknown until it is sampled. The framework relies on three primary components:

  1. Portfolios as Decision Units: Instead of selecting a single arm, the agent selects a portfolio $p$, a probability distribution over arms. A portfolio is safe if its weighted expected reward $\sum a_i p(a_i)$ is non-negative.
  2. Goal Markov Decision Process (GMDP): The exploration process is mapped to a GMDP where states represent sets of unexplored arms. The objective is to reach the terminal state where all arms have been explored.
  3. The SEGB Algorithm: SEGB categorizes arms into "budget" arms (positive prior expectation) and "risky" arms (negative prior expectation). It uses the surplus from budget arms to explore risky ones. Once a high-reward arm is found, it serves as a new, more efficient budget source for further exploration via Bernoulli trials.
The Optimal GMDP Policy (OGP) and its state-transition illustration.

Key Insights

  • Safety as a Budget: Positive expected rewards are viewed as a currency. The agent "spends" the surplus from reliable arms to "buy" information about arms that appear risky but may be optimal.
  • The Equivalence Lemma: A critical theoretical finding is that for specific safe policies, the probability of eventually exploring the entire environment is independent of the exploration order.
  • Deterministic Safety via Randomization: By using portfolios, safety is satisfied deterministically in expectation every round, avoiding the "usually safe" pitfalls of high-probability constraints.

Results and Complexity

The paper proves that the SEGB algorithm is asymptotically optimal, meaning it eventually performs as well as an oracle with full knowledge of the rewards. The convergence rate is instance-dependent, governed by the gap between arm rewards and the safety threshold. Furthermore, the optimal policy is computationally efficient, with linearithmic complexity ($O(n \log n)$), primarily driven by the need to sort arms by their expected values.

Limitations and Future Work

While providing a robust theoretical foundation, the model assumes static rewards, where an arm's value is revealed and remains constant. This does not account for stochastic or non-stationary rewards common in dynamic markets. Additionally, the proofs rely on stochastic dominance between arms, which may not hold for all probability distributions. Future research directions include extending this framework to more complex Markov Decision Processes and incorporating risk-aversion metrics like variance into the safety definition.

Summary updated

Abstract

A recent body of work addresses safety constraints in explore-and-exploit systems. Such constraints arise where, for example, exploration is carried out by individuals whose welfare should be balanced with overall welfare. In this paper, we adopt a model inspired by recent work on a bandit-like setting for recommendations. We contribute to this line of literature by introducing a safety constraint that should be respected in every round and determines that the expected value in each round is above a given threshold. Due to our modeling, the safe explore-and-exploit policy deserves careful planning, or otherwise, it will lead to sub-optimal welfare. We devise an asymptotically optimal algorithm for the setting and analyze its instance-dependent convergence rate.
BibTeX
@misc{bahar2020learning,
  author = {Gal Bahar and Omer Ben-Porat and Kevin Leyton-Brown and Moshe Tennenholtz},
  title = {{Learning under Invariable Bayesian Safety}},
  year = {2020},
  eprint = {2006.04497},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.04497},
}
Figure