Constrained Online Optimization Beyond Slater Conditions

173 concepts143 papers1 proposal

In sequential decision-making—whether a bandit algorithm is allocating an ad budget or a reinforcement learning (RL) agent is navigating an autonomous vehicle—maximizing rewards is only half the battle. The agent must also satisfy real-world constraints, such as safety limits or resource budgets.

To balance these competing goals, algorithms traditionally rely on primal-dual optimization. This framework treats constraints as penalties: if the agent violates a constraint, a dual variable (acting like a mathematical spring) tightens and pulls the agent back into the feasible region.

However, for this spring mechanism to remain stable, classical optimization relies on a crucial assumption known as Slater's condition (or strict feasibility). Slater's condition assumes that there exists a baseline policy capable of strictly satisfying all constraints with a positive safety margin.

But what happens when this safety buffer is unknown, vanishingly small, or entirely absent? Recent research has shifted toward eliminating this dependency, unlocking algorithms that remain robust even when operating on the absolute edge of feasibility.


The Intuition and Failure of the Safety Buffer

To understand why Slater's condition is so deeply embedded in classical algorithms, we must look at how dual variables behave. The size of the safety margin—often called the Slater constant ($\delta$)—dictates the maximum possible value of the optimal dual variables. Intuitively, if a system has a large safety buffer ($\large \delta$), a small penalty is enough to steer the agent back to safety. If the safety buffer is tiny, the dual variables must scale aggressively to enforce constraints. Mathematically, the bounds on these dual variables scale with $1/\delta$.

This dependency introduces three severe failure modes in practical applications:

  1. Exploding Sample Complexity: As the safe action space shrinks, finding a valid policy becomes drastically harder. As shown by Tian et al. and Vaswani et al., the sample complexity required to guarantee strict constraint satisfaction scales inversely with the Slater constant. When the margin approaches zero, the data requirements explode.
  2. Hyperparameter Sensitivity: Traditional primal-dual methods require prior knowledge of $\delta$ to properly tune the learning rates of the dual updates. As Stradi et al. and Bernasconi point out, this parameter is almost always unknown in practice. Guessing incorrectly can cause the dual variables to under-correct (leading to catastrophic violations) or over-correct (causing algorithmic instability), a vulnerability highlighted by Iosifidis et al. and Sharma et al..
  3. Boundary Infeasibility: In many optimized systems, the most efficient or profitable strategy lies exactly on the constraint boundary. In these edge cases, the interior of the feasible region is empty, completely violating Slater's condition and causing traditional multi-objective or primal-dual frameworks to fail entirely, as observed by Mahdavi et al. and Bernasconi et al..

Bypassing Strict Feasibility: Modern Mechanisms

To liberate constrained optimization from the constraints of Slater's condition, researchers have developed several core algorithmic mechanisms. Rather than assuming a global safety buffer exists, these approaches adaptively construct safety guarantees from data.

1. Confidence-Bound Frameworks

Instead of using a dual variable to penalize violations after they happen, some modern methods enforce constraints directly in the primal decision space using uncertainty quantification. For example, in online advertising markets where return-on-spend constraints are exceptionally tight, Vijayan et al. replaced standard primal-dual updates with a confidence-bound framework. By maintaining upper and lower confidence bounds on both rewards and constraint costs, the algorithm can safely navigate narrow feasible regions without ever needing an interior point.

2. Multi-Layered Optimism

In standard online learning, algorithms are "optimistic face of uncertainty" regarding rewards. To handle constraints without a Slater margin, Guo et al. introduced the $\text{Optimistic}^3$ framework. This approach applies optimism simultaneously across three distinct layers: parameter learning, primal decisions, and dual updates. This balanced optimism ensures that the algorithm aggressively explores the environment's boundaries while preventing the dual updates from collapsing when the safety margin is unknown.

Standard Primal-Dual:   [Optimistic Reward Exploration] ──> [Rigid Dual Penalty (Requires Margin)]
                                                                     │
                                                                     ▼ Breaks if margin = 0

Optimistic³ Framework:  [Optimistic Reward] ──> [Optimistic Primal] ──> [Optimistic Dual Update]
                                                                     │
                                                                     ▼ Stable on the boundary

3. Lyapunov Optimization and Adaptive Tracking

Another powerful alternative involves borrowing tools from control theory. Rather than performing gradient descent-ascent on a standard Lagrangian, Sinha et al. combined adaptive online convex optimization (AdaGrad) with Lyapunov optimization. The Lyapunov function tracks the "drift" of constraint violations over time. By minimizing this drift alongside the objective function, the algorithm achieves optimal sublinear regret and constraint violations against adaptive adversaries without requiring any strict feasibility assumptions.

4. Rectified Penalties and Regularization

In Constrained MDPs (CMDPs), algorithms often suffer from "error cancellations"—a loophole where a severe constraint violation in an early training episode is mathematically offset by overly safe behavior in a later episode. To eliminate this, Müller et al. introduced a novel regularization framework that forces the agent to learn safety step-by-step, removing the need to estimate or know the Slater gap. Similarly, Guo et al. utilized rectified penalties to achieve constant cumulative constraint violations for fixed constraints, proving that strict feasibility is not a prerequisite for zero-violation bounds.


Why It Works: The Intuition of Boundary-Safe Learning

The fundamental reason these modern methods succeed where classical primal-dual methods fail comes down to a shift from global assumptions to local adaptation.

Traditional algorithms treat the dual variable as a global property of the optimization landscape. If you do not know the global landscape (the Slater constant $\delta$), you cannot bound the dual variable's growth.

Modern algorithms, by contrast, treat safety as a local tracking problem. By utilizing adaptive step sizes (like those in AdaGrad) or tracking constraint drifts (via Lyapunov functions), the algorithm dynamically scales its penalties based on the actual history of violations rather than a theoretical worst-case margin. If the agent finds itself hugging a tight constraint boundary, the adaptive penalties stabilize the dual space locally.

By pairing this local adaptation with optimism, the agent can safely explore right up to the edge of a constraint. It no longer needs a map showing where the "safe center" of the room is; it can feel its way along the walls without breaking them.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 146 papers
  2. Version 1 · 2026-10-04 · 197 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_slater_condition_dependency_f7ecbd49,
  title = {Slater condition dependency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/slater-condition-dependency/rdr_f7ecbd49e7d14e3987ea8c44f46aa5ff},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_slater_condition_dependency_f7ecbd49_v2,
  title = {Slater condition dependency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/slater-condition-dependency/rdr_f7ecbd49e7d14e3987ea8c44f46aa5ff/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake