Learning When Not to Learn: Risk-Sensitive Abstention in Bandits with Unbounded Rewards

AI summary

Overview

Research area: Machine learning theory, specifically safe exploration, risk-sensitive contextual bandits, and sequential decision-making with unbounded rewards.

Technical level: Advanced. The paper is a theory contribution built around impossibility theorems, Lipschitz continuity assumptions, a discretization-based algorithm, and regret bounds stated in big-O notation with explicit dependence on dimension, horizon, and input-distribution tail behavior.

Scope: The paper formalizes a mentor-free model of learning with irreparable costs as a two-action contextual bandit with an abstain option, proves two impossibility results, and analyzes a caution-based algorithm that only commits where evidence does not already certify harm.

What This Paper Is About

Most sequential decision-making theory assumes errors are recoverable, typically by bounding rewards. In high-stakes settings such as autonomous driving or surgical robotics, a single action can cause damage that no later good behavior can undo. The authors ask whether an agent can avoid such irreparable errors on its own, without a human mentor, by learning when not to act: at each round it observes an input and either abstains (reward 0) or commits to a preexisting baseline policy whose reward is upper-bounded by 1 but can be arbitrarily negative.

Key Contributions

1. A formal model of learning with irreparable costs and no external mentor. The agent faces a two-action contextual bandit with an abstain option, i.i.d. inputs from an unknown distribution ν on R^n, a commit reward that is L-Lipschitz and bounded above by 1 but unbounded below, and abstention that deterministically yields 0. The origin is treated as fully in-distribution with r(0,1) > 0, and ||x|| measures how out-of-distribution an input is.

2. Two impossibility results that delineate the necessity and limits of caution. Theorem 4.1 shows that an algorithm which always commits on the first round can suffer infinite expected regret when E_{x~ν}[||x||] = ∞. Theorem 4.2 shows that when all inputs lie on the sphere of radius T, no algorithm can guarantee sublinear expected regret.

3. A caution-based algorithm achieving sublinear regret for any fixed input distribution. Algorithm 1 restricts committing to a trusted ball of radius m(T), discretizes it into bins of side w(T), and permanently abstains in any bin whose pessimistic reward bound is negative. With w(T) = T^{-1/(n+2)} and m(T) = ln T, expected regret is O((L+σ²) T^{(n+1)/(n+2)} (ln T)^{n+1} + T ν̄(ln T)).

4. A regret decomposition that separates geometric/statistical error from tail risk. The bound splits into a discretization-and-concentration term inside the trusted region and a term T ν̄(ln T) that grows with how often the agent encounters far out-of-distribution inputs, where ν̄ is the radial survival function ν̄(R) = Pr_{x~ν}[||x|| ≥ R].

Main Findings

• Caution is necessary (Theorem 4.1). If ν satisfies E_{x~ν}[||x||] = ∞ and inputs are i.i.d., there exists a reward function (specifically r(x,1) = 1 − L||x||) such that any algorithm committing on the first time step has E[Reg(T)] = ∞. The proof modifies to cover a first commit taken with constant probability, or a constant number of initial abstention rounds.

• Caution has limits (Theorem 4.2). If ν_T is supported on {x : ||x|| = T} and inputs are i.i.d. from ν_T, no algorithm can guarantee E[Reg(T)] ∈ o(T). The proof compares two reward functions, r⁻(x,1) = 1 − L||x|| and r⁺(x,1) = 1, and shows the max over them of E[Reg(T)] is Ω(T) by conditioning on whether the agent ever commits.

• Sublinear regret under a fixed distribution (Theorem 5.2). Algorithm 1 with w(T) = T^{-1/(n+2)} and m(T) = ln T achieves E[Reg(T)] ∈ O((L+σ²) T^{(n+1)/(n+2)} (ln T)^{n+1} + T ν̄(ln T)).

• The bound degrades gracefully with tail mass. For any fixed ν, ν̄(ln T) → 0, so T ν̄(ln T) = o(T). Under subgaussian tails with ν̄(r) ≤ e^{−cr²}, T ν̄(ln T) ≤ T e^{−c(ln T)²} = o(1). Under subexponential tails with ν̄(r) ≤ e^{−cr}, it is at most T^{1−c} = o(T). Under polynomial tails with ν̄(r) ≍ r^{−α}, it is ≍ T/(ln T)^α = o(T).

• The impossibility result is matched. The Theorem 4.2 construction sets x_t = T for all t, so ν̄(ln T) = 1 and the Theorem 5.2 bound becomes linear, matching the Ω(T) lower bound.

• Dimensional dependence is exponential. As in standard Lipschitz contextual bandits, the bound has exponential dependence on the dimension n, making it most meaningful in low-dimensional settings.

• Prior knowledge of ν helps. If ν has polynomial tails and the agent knows this, choosing m(T) = T^c for small c > 0 improves the bound to O(T^{1−cα}).

Methodology in Plain English

The authors first set up a stripped-down decision problem: each round the agent sees an input and chooses between a safe no-op and running a baseline policy. They assume nothing about how bad the baseline policy can be — its reward has no lower bound — but do assume similar inputs produce similar commit rewards (Lipschitz continuity), and that the baseline policy is genuinely useful at the origin.

They then show why naive exploration fails. A standard bandit algorithm tries each option at least once; if inputs can be arbitrarily far from the origin where the baseline policy is arbitrarily bad, that single try can cost infinitely much in expectation. Conversely, they show that if every input is very far out-of-distribution, no amount of cleverness helps and the agent should simply abstain forever.

Given those two results, they design an algorithm around the middle ground. It carves out a ball of radius m(T) around the origin — treated as "close enough to trust" — and tiles it into small hypercubes. Inside each cube it estimates the average commit reward and inflates that estimate by a confidence radius that shrinks as it gathers more data, plus a term accounting for how much the true reward can vary within the cube. If even the inflated, pessimistically adjusted estimate is below zero, the algorithm concludes that committing in that cube is harmful and stops trying there forever. Outside the ball, it never commits at all.

The regret analysis splits into two pieces: how much is lost while committing inside the trusted region (bounded using the number of cubes, the size of the region, and the confidence radii), and how much is lost from inputs so far out-of-distribution that the algorithm simply refuses to act on them (bounded using the probability that inputs fall outside the ball, i.e., the radial survival function).

Why This Matters

Impact on research. The paper removes the boundedness assumption that underpins almost all bandit and reinforcement learning regret theory, and replaces it with a Lipschitz smoothness condition plus a safe fallback action. It also introduces a model that differs from the typical fallback-action literature: rather than assuming globally bounded constraint violation and a known Slater's gap, the bounds depend on the input distribution instead.

Real-world applications (as listed in the paper):

• Process control and manufacturing robotics
• Autonomous driving — the paper gives the example of a self-driving car that cannot compensate for a deadly crash by later driving more safely
• Surgical assistance — a medical robot cannot undo a fatal mistake during surgery
• Any deployed learning system that needs to behave safely without a human supervisor available

Industry relevance. As the number of deployed AI systems grows, the paper argues it may be impractical for each one to have a human supervisor. Even where external help eventually arrives, an agent may need to act safely on its own in the short term. This makes mentor-free cautious abstention directly relevant to deployment.

Future Directions

• Handling high-dimensional inputs. The regret bound has exponential dependence on the dimension n, so the results are most meaningful in low-dimensional settings. Extending to structured high-dimensional input spaces is a natural open problem.

• Tighter distribution-dependent radius choices. The paper notes that with prior knowledge of ν, the choice m(T) = T^c for polynomial-tailed distributions improves the bound to O(T^{1−cα}) over the generic m(T) = ln T. Adaptive selection of m(T) without prior knowledge of ν is left implicit.

• Relaxing the Lipschitz assumption. The analysis assumes commit rewards are L-Lipschitz in Euclidean norm. Whether similar guarantees hold under weaker smoothness or under a more general metric space (the paper notes ‖·‖ could be replaced by a general metric) is not addressed.

• Empirical comparison with related algorithms. The paper states that simulations appear in Appendix B, but the truncated content does not report their results. It also notes that apples-to-apples comparisons to risk-sensitive linear bandit algorithms would be difficult because those methods are non-contextual or use linear rather than Lipschitz structure.

Target Audience

Researchers working on bandit theory, safe exploration, and safe reinforcement learning, particularly those interested in irrecoverable errors, abstention, and settings where reward boundedness cannot be assumed. Also relevant to practitioners in safety-critical domains (autonomy, robotics, surgical systems, industrial control) who need formal grounding for when a learned policy should decline to act, and to readers familiar with regret analysis who want an introduction to how standard optimism-under-uncertainty breaks down when rewards are unbounded below.

Authors’ abstract

In high-stakes AI applications, even a single action can cause irreparable damage. However, nearly all of sequential decision-making theory assumes that all errors are recoverable (e.g., by bounding rewards). Standard bandit algorithms that explore aggressively may cause irreparable damage when this assumption fails. Some prior work avoids irreparable errors by asking for help from a mentor, but a mentor may not always be available. In this work, we formalize a model of learning with unbounded rewards without a mentor as a two-action contextual bandit with an abstain option: at each round the agent observes an input and chooses either to abstain (always 0 reward) or to commit (execute a preexisting task policy). Committing yields rewards that are upper-bounded but can be arbitrarily negative, and the commit reward is assumed Lipschitz in the input. We propose a caution-based algorithm that learns when not to learn: it chooses a trusted region and commits only where the available evidence does not already certify harm. Under these conditions and i.i.d. inputs, we establish sublinear regret guarantees, theoretically demonstrating the effectiveness of cautious exploration for deploying learning agents safely in high-stakes environments.