PaperlayerView exact revision on arXiv

Source-linked AI summary

Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions

Spyros Dragazis, Aldo Pacchiano

arXiv:2608.26755v1cs.LG

TL;DR

Expected-cost safety can fail to prevent unsafe realized outcomes when actions affect outcome variability. The paper introduces High Probability Constrained UCB for continuous-action contextual bandits, combining optimistic reward exploration with conservative safe-set estimation, and reports regret guarantees, substantially fewer violations, and open scope for broader heteroscedasticity and real-world evaluation.

  • Problem

    Expected-cost constraints may not prevent catastrophic individual outcomes in heteroscedastic bandits where actions affect cost variability.

  • Method

    High Probability Constrained UCB controls realized cost stage-wise while exploring optimistically for reward and conservatively estimating the safe action set.

  • Results

    The paper proves tight regret guarantees for linear and nonlinear reward–cost models and empirically validates the approach on synthetic and real-world datasets.

  • Takeaways & Limitations

    Experiments illustrate that accounting for heteroscedasticity matters when safety is imposed on realized rather than expected costs.

  • Takeaways & Limitations

    The analysis is limited to the action-scaled form of heteroscedasticity, and broader safety-critical real-world evaluation remains open.

Abstract

from arXiv · show

Contextual bandits are a standard framework for sequential decision-making under uncertainty, with applications in clinical trials, dosage selection, recommendation systems, and autonomous systems. Safety is central in many of these applications, since a single unsafe decision in settings such as dosage selection or autonomous driving can have catastrophic consequences. A common way to model safety in bandit problems is to associate each action with both a reward signal and a cost signal, and to optimize reward subject to constraints on cost. Most existing safety-constrained bandit models enforce safety by requiring the expected cost of each action to remain below a prescribed threshold. However, this may be insufficient in heteroscedastic settings, where the chosen action affects not only the expected reward and cost, but also the variability of the observed outcomes. We study contextual bandits with one-dimensional continuous actions and stage-wise high-probability constraints on the realized cost. We propose High-Probability Constrained UCB, an optimistic-pessimistic algorithm that explores for reward while conservatively estimating the safe action set. For linear reward and cost models, we prove a tight $\tilde{\mathcal{O}}(d\sqrt{T})$ regret bound, and we extend the analysis to general function classes using the eluder dimension. Experiments show that enforcing realized-cost safety substantially reduces violations compared with expected-cost constrained baselines.

1 Introduction

The paper addresses safety-constrained contextual bandits when actions affect outcome variability, requiring realized-cost control at every round rather than only expected-cost control. It introduces High Probability Constrained UCB and establishes regret guarantees for linear and nonlinear reward–cost models, with empirical validation.

  • Motivation: Expected-cost constraints may be insufficient in heteroscedastic settings because individual realized costs can still be catastrophic.The selected action can affect both the expected cost and the variability of outcomes.
  • Problem: The paper asks whether constrained low-regret algorithms can control realized cost at every round with high probability.
  • Problem: The target guarantee requires P(C_t ≤ τ) ≥ 1 − δ for the realized cost at each time step.The confidence parameter δ controls the tolerated probability of violating the safety threshold.
  • Method: High Probability Constrained UCB explores optimistically for reward while conservatively estimating the safe action set.The method is based on the OFUL principle and does not require prior knowledge of an initial safe action.
  • Theory: The method provides tight regret guarantees for linear and nonlinear reward–cost models.The nonlinear analysis characterizes regret using the eluder dimension.
  • Evaluation: Experiments on synthetic and real-world datasets show the importance of high-probability realized-cost guarantees in heteroscedastic settings.

2 Model and Problem Formulation

The model combines contextual continuous dosage actions with reward and cost signals whose variability depends on the selected action. Safety is imposed through stage-wise high-probability realized-cost constraints, and the algorithm estimates feasible actions conservatively under stated noise and boundedness assumptions.

  • Model and Problem Formulation: Contexts are d-dimensional vectors with no distributional assumptions, allowing stochastic or adversarial context sequences.They may represent structured measurements or embeddings of unstructured information.
  • Model and Problem Formulation: The action α_t lies in [0, 1], and a known increasing response function g scales both reward and cost signals.The function satisfies g(0) = 0 and g(1) = 1.
  • Model and Problem Formulation: The common response function g simplifies the notation, although distinct reward and cost dosage-response functions are a practical extension.The paper states that this extension introduces no additional theoretical difficulty.
  • Model and Problem Formulation: Action-dependent scaling makes the model heteroscedastic because outcome variability depends on the selected dosage.The formulation remains interpretable while capturing monotone dose-response behavior and phenomena such as saturation or instability.
  • 2.1 Assumptions: The model assumes conditionally sub-Gaussian reward and cost noise, bounded unknown parameters, bounded contexts, and a positive toxicity threshold.
  • 2.2 Constraint Formulation: The learner maximizes expected cumulative reward while requiring realized cost to remain below a known threshold with high probability.The confidence parameters distinguish randomness in realized costs from uncertainty in estimating the cost parameter.
  • 2.2 Constraint Formulation: The feasible action set is defined using the realized-cost requirement, whose confidence parameter explicitly controls the probability of an unsafe realization.Because g is strictly increasing, the safe actions can be represented through an interval transformation.
  • 2.2 Constraint Formulation: The algorithm uses optimistic reward estimates and pessimistic cost estimates to explore while ensuring its estimated feasible set is contained in the true feasible set.Performance is measured by constrained pseudo-regret relative to an optimal feasible action.

3 Proposed Algorithm

The algorithm explores optimistically for reward while estimating the feasible action set conservatively from cost uncertainty. It uses regularized least-squares confidence sets and guarantees that the estimated set remains safely contained under the stated event.

  • 3 Proposed Algorithm: The algorithm uses optimism for reward and pessimism for cost to explore while maintaining a conservative safe action set.The cost estimate minimizes the upper endpoint of the estimated safe interval over the cost confidence set.
  • 3 Proposed Algorithm: Two regularized least-squares estimators are constructed for the unknown reward and cost parameters.The regularized covariance matrix uses a fixed λ > 0; experiments set λ = 1.
  • 3 Proposed Algorithm: Rounds with g(αs) = 0 are excluded because they provide no information about the unknown parameters.The transformed observations follow the standard linear regression model whenever g(αs) > 0.
  • 3 Proposed Algorithm: High-probability confidence sets are centered at the least-squares estimates and bound errors relative to the true parameters.The sets follow from self-normalized concentration inequalities and use the number of informative samples collected before round t.
  • 3 Proposed Algorithm: The algorithm computes the estimated feasible set from a pessimistic cost parameter selected within its confidence set.If the feasible-set optimization has no solution, the construction uses the specified fallback; otherwise, the resulting set is defined from the conservative solution.

4 The “Good Event”

The analysis conditions on a good event that combines parameter-concentration guarantees with feasibility containment. This event supplies the high-probability foundation for the subsequent regret analysis.

  • 4 The “Good Event”: The good event is the intersection of concentration events for the reward and cost parameters and an event for feasible-set containment.It is defined as ε = εθ ∩ εµ ∩ εA.
  • 4 The “Good Event”: The first two sub-events ensure that the confidence sets contain the true reward and cost parameters.These guarantees follow from Theorem 1.
  • 4 The “Good Event”: The third sub-event ensures that the estimated feasible action set is contained in the true feasible action set at every round.This provides the algorithm’s conservative feasibility guarantee.

5 Regret Analysis – Linear Case

The linear regret analysis compares the algorithm with the optimal realized-cost-feasible action and decomposes regret into reward-estimation and conservative-feasibility losses. High-probability bounds control both terms.

  • 5 Regret Analysis – Linear Case: The benchmark is the optimal feasible action at each round, while regret compares its feasible reward with the algorithm’s expected reward.The optimal action depends on the sign of ⟨Xt, θ⋆⟩ because g is strictly increasing.
  • 5 Regret Analysis – Linear Case: The regret decomposition introduces an auxiliary feasible action based on the optimistic reward parameter.This separates the reward-optimism contribution from the loss caused by conservative feasibility estimation.
  • 5 Regret Analysis – Linear Case: The first regret term is bounded through the standard optimism argument applied to the transformed action value g(α).The bound holds on the reward-parameter concentration event εθ.
  • 5 Regret Analysis – Linear Case: The second regret term captures and bounds the loss from using a conservative estimate of the feasible action set.This bound holds on the cost-parameter concentration event εµ.
  • 5 Regret Analysis – Linear Case: Theorem 2 combines the two terms to give a high-probability regret bound for High Probability Constrained UCB.The bound is stated with probability at least 1 − δ′.
  • 5 Regret Analysis – Linear Case: The regret bound does not depend on δ because the benchmark satisfies the same realized-cost constraint as the learner.The benchmark is the clairvoyant policy that knows θ⋆ and µ⋆.

6 Non-linear Rewards and Costs

The paper extends the safety-constrained bandit analysis from linear models to general reward and cost function classes. The resulting regret characterization uses confidence widths and eluder dimensions.

  • 6 Non-linear Rewards and Costs: The nonlinear extension replaces linear parameter models with general reward and cost function classes.Its regret bound is expressed in terms of the eluder dimension.
  • 6 Non-linear Rewards and Costs: The model assumes known function classes with bounded functions and conditionally sub-Gaussian noise.The functions are bounded in [−1, 1], relaxing the common normalization to [0, 1].
  • 6 Non-linear Rewards and Costs: The realized-cost feasible action set is defined first, and the learner selects actions from an estimated subset of it.The nonlinear algorithm maintains conservative feasibility while optimizing reward over the estimated set.
  • 6 Non-linear Rewards and Costs: The width of a function class at a context measures uncertainty and plays the role of confidence widths from the linear analysis.The regret analysis uses corresponding confidence radii and eluder dimensions.
  • 6 Non-linear Rewards and Costs: At each round, the algorithm computes least-squares estimates and confidence sets over the reward and cost classes.It then constructs a conservative feasible set and applies optimistic reward selection within that set.
  • 6 Non-linear Rewards and Costs: Theorem 3 gives a high-probability regret guarantee for Non-Linear High Probability Constrained UCB in terms of the reward and cost eluder dimensions.The theorem states the guarantee with probability at least 1 − δ′.

7 Experimental Results

Experiments evaluate HPUCB on synthetic and NASA battery data, emphasizing realized-cost violations, regret, and computational trade-offs under different safety thresholds.

  • Real-world experiments: HPUCB is evaluated on NASA battery data by treating current as dosage, voltage change as reward, and temperature as cost.The experiments use measurements from four battery types across charging and discharging modes.
  • Safety violations: 0.02% violation ratio for HPUCB versus 12%–23% for the expected-cost baseline.The comparison concerns realized-cost violations, whereas the baseline enforces the constraint only in expectation.
  • Synthetic experiments: For synthetic experiments at τ = 0.5, ε = 0.5 provides comparable regret with lower computational cost and no dependence on T in parameter tuning.The ε-Greedy variant plays a safe action with probability ε and otherwise follows Algorithm 1.
  • Real-world experiments: The NASA experiments use approximately half the dataset—about 100k samples with dimension 2048 + 3—to fit ground-truth reward and cost parameters.Performance is evaluated on the remaining data after the least-squares fit.
  • Computational cost: HPUCB takes about 30 minutes on the real-world experiments, compared with about two minutes for the baseline algorithm.The experiments run on an NVIDIA L40 GPU and report cumulative regret for τ ∈ {0.1, 0.2}.
  • Guarantees: The guarantees apply to arbitrary context sequences, including stochastic and adversarial settings, supporting battery-charging and control applications without an explicit dynamical model.The algorithm performs safe decision-making directly from observed data in these settings.

8 Conclusions

The paper studies realized-cost safety in continuous-action contextual bandits and combines conservative feasibility estimation with reward exploration. It establishes regret guarantees while identifying broader heteroscedastic models and clinical evaluation as open directions.

  • 8 Conclusions: The work addresses stage-wise high-probability constraints on realized cost when outcome variability depends on the selected action.The setting uses contextual bandits with continuous actions.
  • 8 Conclusions: An optimistic–pessimistic algorithm balances reward exploration with conservative estimation of the feasible action set.The analysis covers linear and general reward–cost models.
  • 8 Conclusions: The authors identify more general heteroscedasticity beyond the studied action-scaled structure and broader safety-critical empirical evaluation as open directions.They specifically mention adaptive clinical dosage selection for future evaluation.

A.1 Proof of Lemma 1

The proof develops closed-form solutions for the linear optimization programs using KKT conditions, then decomposes regret into reward- and cost-estimation terms.

  • Closed-form optimization: The linear-case solutions to Equations (9) and (10) are derived using KKT conditions, avoiding a convex program at every round.This substantially reduces the computational cost of the algorithm.
  • Closed-form optimization: Maximizing a nonzero linear objective over an ellipsoid places the optimizer on the boundary and yields a unique solution.The feasible ellipsoid is compact and convex, and strict convexity gives uniqueness.
  • Regret decomposition: The regret analysis separates the cost of estimating θ⋆ from the cost of estimating µ⋆ and bounds the two terms separately.These terms correspond to reward and cost estimation, respectively.

D.2 Proof of Lemma 5

The analysis controls feasible-action endpoints using pessimistic cost estimates and confidence sets, then applies concentration and eluder-dimension arguments to obtain regret bounds.

  • Feasible-action comparison: The true and estimated safe sets are represented through upper endpoints, whose comparison controls the action-selection analysis.The endpoint argument is combined with pessimistic cost estimates on the good event.
  • Concentration and regret: Informative samples are collected only when g(αt) > 0, but their number is at most T, so the elliptic potential bound applies.This supports the linear regret analysis.
  • Feasible-action comparison: When the optimistic reward estimate is negative, both selected actions are zero; otherwise, monotonicity reduces selection to choosing the largest feasible effective action.This endpoint comparison is used in the regret proof.

E.3 Proof of Theorem 3

Theorem 3 establishes a high-probability regret guarantee for the Non-Linear High Probability Constrained UCB algorithm. The proof combines earlier lemmas with confidence-class analysis for reward and cost.

  • Theorem 3 states a regret guarantee holding with probability at least 1−δ′ for the Non-Linear High Probability Constrained UCB algorithm.
  • The proof invokes Lemmas 11 and 12 to derive the theorem’s bound.
  • Lemma 13 is applied to both the reward and cost confidence classes.
Loading 2608.26755v1…