Cancellation-Free Constrained SquareCB for Safe Controller Selection

Kartik Pandit, Sourav Ganguly, Arnob GhosharXiv 2026 · arXiv

TL;DR

This paper introduces a new algorithm for constrained contextual bandits that eliminates "cancellation"—the dangerous tendency of traditional algorithms to use past safety "slack" to justify future budget violations. By using a per-round rectified weight instead of a running Lagrange multiplier, the authors achieve 6 to 9 times lower safety violations in quadrotor and building control tasks compared to standard baselines.

What Problem Does This Paper Address?

Contextual bandits (CBs) are a framework for making sequential decisions under uncertainty, widely used in everything from ad placement to medical treatments. In many real-world scenarios, we don't just want to minimize loss; we have to stay within a budget or safety limit (e.g., "don't let the drone overshoot its target by more than 2cm").

The standard way to handle these constraints is through primal-dual methods or virtual queues. These methods learn a weight (a Lagrange multiplier) based on past performance. If the algorithm was very safe in early rounds, it "accumulates slack," which mathematically allows it to violate the budget in later rounds while still appearing "safe" on average.

In safety-critical systems—like the quadrotor drone or building HVAC systems discussed in this paper—this "cancellation" is unacceptable. You want the system to be safe in the current moment, regardless of how much budget it saved yesterday.

Methods

The authors build upon SquareCB, a popular algorithm that reduces contextual bandit problems to online square-loss regression. Their primary innovation is the Rectified SquareCB algorithm.

Key technical components include:

  • Rectified Weight ($\mu_t$): Instead of updating a global Lagrange multiplier via dual ascent, the algorithm calculates a weight for the cost specifically for the current round.
  • Per-Round Complementary Slackness: In each round, the algorithm finds the smallest weight $\mu_t$ such that the estimated cost of the chosen policy meets the budget. If the estimated cost is already under budget, the weight is zero. If it's over, the weight is just large enough to pull it back to the budget line.
  • Bisection Search: Because the relationship between the weight and the resulting policy's cost is well-behaved (non-increasing and right-continuous), the optimal weight can be found efficiently using a simple bisection search.
  • Mixing Policies: If the cost "jumps" over the budget at a specific weight, the algorithm mixes two neighboring distributions to hit the budget exactly.

Datasets

The researchers evaluated their method on two sophisticated control benchmarks:

  1. Safe-Control-Gym (2D Quadrotor): The learner must choose from six LQR controllers to bring a drone to a 1m height. The goal is to minimize tracking error (loss) while keeping the overshoot (cost) below 1.75 cm.
  2. BOPTEST (Building HVAC): The learner selects from eight thermostat schedules for a building zone. The goal is to minimize energy use (loss) while keeping thermal discomfort (cost) below a specific threshold over 180 days of varying weather.

Key Insights and Ideas

  • Memoryless Safety is Better: By making the cost weight a function of current estimates only, the algorithm becomes "cancellation-free." It treats every round as a fresh opportunity to be safe, rather than a chance to spend "safety credits" earned in the past.
  • Theoretical Robustness: The authors prove that their algorithm achieves sub-linear regret and violation bounds. Notably, the violation bound $O(\sqrt{KT \text{Reg}_{Sq}(T)})$ does not depend on the "Slater margin" $\delta$ (how much room there is to be safe), making it theoretically more robust than previous methods.
  • Adversarial Contexts: The paper demonstrates that these safety guarantees hold even if the contexts (like weather or drone payloads) are chosen by an adversary, provided there is a "safe" action available for every possible context.

Key Results

  • Massive Violation Reduction: In both the quadrotor and building experiments, the "cancellation-free violation" was 6 to 9 times lower than that of primal-dual and virtual-queue baselines.
  • Superior Regret: Despite being much safer, the algorithm achieved lower or comparable regret. On the quadrotor task, the final regret was 57, compared to 94 for the primal-dual baseline.
  • Faster Settling: The rectified weight mechanism "settles" on a feasible policy much faster. In the quadrotor task, the proposed method settled within 1,000 episodes, whereas baselines took roughly 10,000 episodes to stabilize.

Limitations and Future Work

  • Single Constraint: The current formulation focuses on a single cost constraint. Real-world systems often have multiple constraints (e.g., battery life, temperature, and physical boundaries), and extending this to multi-constraint settings is a noted direction for future work.
  • Known Slater Margin: The algorithm currently requires a known bound on the optimal multiplier (derived from the Slater margin $\delta$). The authors suggest that removing this requirement without delaying budget enforcement is a key challenge.
  • Beyond Bandits: The authors aim to extend this "rectified" approach to full Reinforcement Learning (RL) settings involving long-horizon control tasks where actions have delayed consequences.

Summary updated

Abstract

We study constrained contextual bandits, in which a learner chooses one of $K$ actions in each round to minimize loss while keeping the expected cost of its play below a budget. Existing reductions to online regression weight the cost by a Lagrange multiplier learned from past constraint residuals, so slack in some rounds can offset violations in others. We instead run SquareCB proposed in \citep{foster2020beyond} with a rectified weight on the cost: it is zero when the estimated cost is within the budget, and otherwise just large enough to bring it back to the budget. Under realizability and Slater's condition with margin $δ$, the algorithm attains regret $O(\sqrt{KT\,\mathrm{Reg}_{\mathsf{Sq}}(T)}/δ)$ and cancellation-free violation $\sum_t(V_c^{p_t}-b)^+=O(\sqrt{KT\,\mathrm{Reg}_{\mathsf{Sq}}(T)})$, where $\mathrm{Reg}_{\mathsf{Sq}}$ is the error of the regression oracle. The same bounds hold when the budget must be met in every context, potentially adversarially chosen contexts. In controller selection for a safe-control-gym quadrotor and a BOPTEST building, the violation is 6 to 9 times lower than that of primal-dual and virtual-queue baselines, with a lower or comparable regret.
BibTeX
@misc{pandit2026cancellation,
  author = {Kartik Pandit and Sourav Ganguly and Arnob Ghosh},
  title = {{Cancellation-Free Constrained SquareCB for Safe Controller Selection}},
  year = {2026},
  eprint = {2611.21880},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21880},
}
Figure