No-Regret is Not No-Harm: Bandits with Consumable Action Sets
Abstract
Sublinear regret is the standard justification for deploying sequential decision-making systems. We show that this justification is vacuous when actions consume the action set. We study bandits in which pulling an arm may destroy it, and in which each destroyed arm imposes a permanent negative externality on every subsequent reward. We prove a two-sided separation: a policy achieving \emph{exactly zero} regret against the best-available-arm benchmark can incur value loss mδ E, unbounded in both the pool size m and the externality magnitude δ E, and can drive total value negative while the optimal policy remains positive; conversely, any policy near the system optimum is \emph{forced} to report private regret mϵ. The metric does not merely fail to separate good from destructive policies---it orders them backwards. The mechanism is that regret is measured against an optimum the learner has itself degraded. We further establish that the parameter governing optimal play, the expected marginal externality κa = pa ea, determines whether greedy is optimal: constant κ is proven sufficient for universal optimality---via an adjacent- interchange lemma and backward induction, holding at every horizon without qualification, verified independently across 450 adversarial instances---and non-constant κ is proven to admit a counterexample instance, not universal failure. The parameter is also (ii) subject to a consumption-induced estimation floor SE ≥ 2σ/√(min(T,∑j 1/pj)) that \emph{does not decrease with the horizon}, because each arm supplies exactly one before/after transition and the sample budget is capped by consumption rather than time. The quantity that matters most cannot be estimated arbitrarily accurately, and its attainable precision degrades exactly as it becomes more important. We give a closed-form correction (ECI, exact under constant κ, with a proven though loose bound on its general approximation gap), characterise an exactly-solvable special case, and show that sequential multi-agent consumption on a shared pool reduces exactly to the single-agent case, so no price-of-anarchy separately arises there. We further stress-test the independence assumption underlying every result: under correlated, cluster-level destruction the core characterisation appears to survive exactly (verified, not proven) while the correction requires an explicit adjustment, which we derive and validate against exact and scaled ground truth. We release an open-source testbed, \textsc{Attrition}, with a regression test for every claim.
Related
- Follow the Perturbed Leader for Linear Bandits: √T Regret over General Action Sets
- A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets
- Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
- Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
- Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
BibTeX
@misc{modi2026noregret,
title = {{No-Regret is Not No-Harm: Bandits with Consumable Action Sets}},
author = {Navikkumar Modi},
howpublished = {HAL},
year = {2026},
month = sep,
url = {https://hal.science/hal-05767940v1},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - No-Regret is Not No-Harm: Bandits with Consumable Action Sets
AU - Navikkumar Modi
PY - 2026
DA - 2026/09/28
PB - HAL
UR - https://hal.science/hal-05767940v1
AB - Sublinear regret is the standard justification for deploying sequential decision-making systems. We show that this justification is vacuous when actions consume the action set. We study bandits in which pulling an arm may destroy it, and in which each destroyed arm imposes a permanent negative externality on every subsequent reward. We prove a two-sided separation: a policy achieving \emph{exactly zero} regret against the best-available-arm benchmark can incur value loss mδ E, unbounded in both the pool size m and the externality magnitude δ E, and can drive total value negative while the optimal policy remains positive; conversely, any policy near the system optimum is \emph{forced} to report private regret mϵ. The metric does not merely fail to separate good from destructive policies---it orders them backwards. The mechanism is that regret is measured against an optimum the learner has itself degraded. We further establish that the parameter governing optimal play, the expected marginal externality κ_a = p_a e_a, determines whether greedy is optimal: constant κ is proven sufficient for universal optimality---via an adjacent- interchange lemma and backward induction, holding at every horizon without qualification, verified independently across 450 adversarial instances---and non-constant κ is proven to admit a counterexample instance, not universal failure. The parameter is also (ii) subject to a consumption-induced estimation floor SE ≥ 2σ/√(min(T,∑_j 1/p_j)) that \emph{does not decrease with the horizon}, because each arm supplies exactly one before/after transition and the sample budget is capped by consumption rather than time. The quantity that matters most cannot be estimated arbitrarily accurately, and its attainable precision degrades exactly as it becomes more important. We give a closed-form correction (ECI, exact under constant κ, with a proven though loose bound on its general approximation gap), characterise an exactly-solvable special case, and show that sequential multi-agent consumption on a shared pool reduces exactly to the single-agent case, so no price-of-anarchy separately arises there. We further stress-test the independence assumption underlying every result: under correlated, cluster-level destruction the core characterisation appears to survive exactly (verified, not proven) while the correction requires an explicit adjustment, which we derive and validate against exact and scaled ground truth. We release an open-source testbed, \textsc{Attrition}, with a regression test for every claim.
ER -