Virtual Queues Under Performative Feedback: When Long-Term Constraints Destabilize Retraining

Many deployed models must satisfy promises that hold on average over time rather than at every step. A lender keeps its default rate under a budget across a quarter. A city keeps parking occupancy near a target across a month. A platform keeps approval rates for two groups within a set gap over a year. The standard engineering tool for such promises comes from network control and is called drift-plus-penalty. It keeps a running tally of how far over budget the system has gone, a "virtual queue," and at each step it weighs current cost against that tally. The tool is cheap and needs no forecast of the future, but its guarantees assume the environment is exogenous: tomorrow's traffic does not depend on today's decision. In lending, pricing, and screening the opposite holds. The population reacts to the deployed model, which is the setting of performative prediction, and these reactions often unfold gradually.

This note argues that the two mechanisms interact in a specific way that nobody has analyzed. A virtual queue acts as a time-varying weight on the constraint. When that constraint is itself computed on a population that reacts to the model, a growing queue raises the effective sensitivity of the retraining loop to distribution shift. A loop that is stable when the constraint is slack can therefore begin to oscillate once the constraint binds. We propose to derive this stability condition, to test whether it predicts oscillation in real reactive-population benchmarks, and to build a drift-plus-penalty variant with an adaptive damping term that restores convergence. Because the queue bounds realized violations along the actual trajectory, the variant also controls violations during the transient adaptation phase that steady-state methods leave unaddressed.

Core Claim

Consider a deployed parameter $\theta_t$, a population state that responds to it, a loss $\ell$, and a long-term constraint function $g$ whose time average must be nonpositive. Naive performative drift-plus-penalty solves at each step

$$\theta_{t+1} = \arg\min_{\theta}\; V\,\mathbb{E}_{z\sim\mathcal{D}_t}[\ell(\theta;z)] + Q_t\,\mathbb{E}_{z\sim\mathcal{D}_t}[g(\theta;z)] + \tfrac{\alpha_t}{2}\|\theta-\theta_t\|^2,$$

and then updates the queue as $Q_{t+1}=\max[Q_t+\hat g_t,0]$. Here $\mathcal{D}_t$ is the distribution observed after deploying $\theta_t$, $V$ is the cost-versus-constraint trade-off knob, $\hat g_t$ is the realized constraint value, and $\alpha_t$ is a proximal damping weight. With $\alpha_t=0$ this is repeated risk minimization (retraining on whatever data the last model induced) applied to a queue-weighted Lagrangian.

The contraction argument of Performative Prediction shows that retraining converges when the population's sensitivity $\epsilon$ satisfies $\epsilon<\gamma/\beta$. Here $\epsilon$ is a Lipschitz bound on how far the distribution moves in Wasserstein distance per unit change of the model, $\gamma$ is the strong convexity of the objective, and $\beta$ is its smoothness in the data. Applied to the queue-weighted objective, the condition becomes roughly

$$\epsilon\,(V\beta_\ell + Q_t\beta_g) < V\gamma_\ell + Q_t\gamma_g + \alpha_t .$$

Constraints such as default-rate budgets or approval-rate gaps are often nearly linear in the score, so $\gamma_g\approx 0$ and the right side does not grow with $Q_t$ while the left side does. In standard drift-plus-penalty the steady-state queue scales as $O(V)$, so the ratio $Q/V$ settles at a level set by how tight the constraint is, not by $V$. Our prediction is that instability depends on constraint tightness. Making the budget stricter can push a previously convergent loop past the threshold into limit cycles, and no choice of $V$ fixes this. The remedy we propose is to set $\alpha_t$ in proportion to $\hat\epsilon\,Q_t\beta_g$ using an online estimate $\hat\epsilon$, which keeps the loop contractive at every queue level. The cost is slower tracking, which we quantify.

This is an analysis-plus-algorithm claim, and we state its scope honestly. The proposed method converges to a constrained performatively stable point, meaning a point that is optimal for the distribution it itself induces. It does not converge to the constrained performative optimum. Closing that gap is a separate add-on, discussed below.

Where This Sits

Two strands motivate the gap. Constrained Optimization With Decision-Dependent Distributions defines a Constrained Equilibrium Point in which both objective and linear constraints shift with the decision. It proves linear convergence of Repeated Constrained Minimization and Repeated Dual Ascent under joint contraction conditions. Its constraints are instantaneous, its analysis uses exact expectations, and it explicitly leaves stochastic streams and time-averaged constraints open. Zero-Regret Performative Prediction Under Inequality Constraints targets the performative optimum with an adaptive primal-dual method. That method achieves $O(\sqrt{T})$ regret and violation, but it requires location families (shifts affine in $\theta$), exploration noise injected into live deployments, and constraints that do not themselves shift. Neither work sees the queue-sensitivity coupling, because neither has a dual variable that grows with accumulated violation while the constraint is evaluated on a reacting population.

Two further papers supply ingredients we reuse. How to Learn when Data Gradually Reacts to Your Model models populations with memory and estimates response Jacobians by finite differences. It optimizes only the steady-state loss and names cumulative transient loss as open. Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments handles memory by holding decisions fixed over epochs; we use it as a damping alternative. On the drift-plus-penalty side, Lyapunov Drift Plus Penalty Optimization gives the $[O(1/V),O(V)]$ cost-versus-backlog trade-off under exogenous randomness. Delay-Tolerant Constrained OCO with Application to Network Resource Allocation adds proximal regularization to virtual-queue updates to survive stale feedback. A slowly reacting population behaves like delayed feedback, and our adaptive $\alpha_t$ is a performativity-aware version of that regularizer.

A Lyapunov Drift-Plus-Penalty Method Tailored for Reinforcement Learning with Queue Stability argues that per-step drift-plus-penalty is myopic and replaces it with a queue-aligned reward for PPO. It supplies our strongest learning-based competitor, though it was only tested with exogenous Poisson arrivals.

Two constraint-side papers explain why the target constraints matter. Fair When Trained, Unfair When Deployed proves that error-rate fairness metrics drift after deployment under performative concept shift. A one-shot fairness constraint is therefore insufficient, and a running tally is the natural object. Achieving Long-Term Fairness in Sequential Decision Making and Long Term Fairness via Performative Distributionally Robust Optimization both stop at stable points and enforce fairness step by step or through robustness, without any tracked budget.

Research Program

The theoretical part has three pieces. First, we derive a drift bound for the queue-weighted loop under an $\epsilon$-sensitive map with geometric memory. The standard bound acquires an extra term of order $\epsilon\,Q_t\|\theta_{t+1}-\theta_t\|$ plus a lag term from population memory. We then show that the adaptive damping rule cancels the extra term, recovering an $O(1/V)$ cost gap and $O(V)$ backlog relative to the constrained equilibrium point. Second, we exploit a property of the queue update that does not depend on the environment. With $Q_0=0$, the cumulative realized violation $\sum_{t<T}\hat g_t$ never exceeds $Q_T$. Bounded queues therefore guarantee bounded violation along the actual trajectory, including the transient, for any population dynamics. What the performative setting breaks is queue stability itself. We identify the condition that restores it: a performative Slater condition, meaning some decision keeps the constraint strictly negative after the population has responded to it. Third, we characterize the instability boundary in closed form for a location-family credit model, where the response is affine and every constant is computable. This gives an exact prediction of the constraint tightness at which oscillation begins.

The algorithmic part builds the damped method, with $\hat\epsilon$ estimated online from consecutive deployments using the finite-difference approach of the stateful PerfGD work. We also build an optional "anticipatory" extension. It evaluates $g$ on a one-step-ahead prediction of the population state rather than the current one, which partially restores the performative gradient. This extension is treated as a separate ablation so that the stability claim does not depend on it.

Baselines

The naive reference point is unconstrained repeated retraining: deploy, collect, retrain on the induced data, and ignore the budget. It shows how badly the long-term constraint is violated when nothing tracks it. Next to it we run repeated retraining with a fixed Lagrange penalty $\lambda$, tuned by grid search on a held-out simulator seed. This is what a practitioner would do first.

The strongest stability-seeking competitor is Repeated Dual Ascent from Constrained Optimization With Decision-Dependent Distributions. It is the closest existing method: a primal step on the induced distribution followed by a dual step, which is structurally our undamped loop with a tuned dual step size. We run its stochastic variant on the same sample streams, with step sizes tuned over the same budget of configurations as our $V$ and damping constant. That paper's experiments on SFpark and its synthetic market do not report a number in the file, so there is no reported result on Lacuna for this baseline's performance on SFpark. Beating it means one of two outcomes. Either it shows the predicted limit cycles at tight budgets where our method converges, or it reaches lower time-average cost at matched cumulative violation.

The strongest optimality-seeking competitor is APDA from Zero-Regret Performative Prediction Under Inequality Constraints. Its guarantee is theoretical: $O(\sqrt{T})$ regret and $O(\sqrt{T})$ violation in location families. The file contains no reported numerical value on our benchmarks. We run it with its exploration noise and also report the extra loss that noise causes, since deploying perturbed models has a real cost. We do not expect to beat APDA on steady-state cost in pure location families. Beating it means lower cumulative violation during transients, and equal or better cost once responses are nonlinear or stateful.

For the learning-based alternative we train a PPO agent with the queue-aligned reward of LDPTRLQ A Lyapunov Drift-Plus-Penalty Method Tailored for Reinforcement Learning with Queue Stability inside the same simulators. It receives the same number of environment interactions that our method uses for deployment and tuning combined.

The key ablation removes adaptive damping. We compare the undamped queue loop, a fixed $\alpha$ tuned for the slack-constraint regime, and epoch-holding in the style of the geometric-decay paper. This isolates whether damping in proportion to the queue, rather than damping in general, is what matters.

Why not just…?

Why not just use a fixed Lagrange penalty and retrain? A fixed $\lambda$ is a constant queue, so it removes the instability mechanism. That is exactly why it is a real threat. Its weakness is that the right $\lambda$ depends on where the population settles, and that location shifts as the model shifts. Under performative concept drift, which Fair When Trained, Unfair When Deployed proves occurs for error-rate fairness metrics, a $\lambda$ tuned on one deployment under- or over-enforces on the next. Our experiments sweep $\lambda$ and report the best member of the grid in hindsight. If that best fixed $\lambda$ matches our method on both cost and violation across budgets, the queue adds nothing and we will say so. We expect it to lose when budgets or population responses change mid-run.

Why not just use Repeated Dual Ascent, since a virtual queue is a dual variable? That is correct: the queue update is projected dual ascent with unit step, scaled by $1/V$. We do not claim a new update rule for the dual variable. Our claim is about what happens when that dual variable grows with accumulated violation while the constraint is computed on a reacting population. The contraction conditions of Constrained Optimization With Decision-Dependent Distributions are stated for instantaneous constraints with a step size tuned per problem. They do not predict that the stability margin shrinks as the budget tightens. The decisive test is a budget sweep at fixed sensitivity. If Repeated Dual Ascent stays convergent wherever our derived threshold predicts oscillation, our analysis is wrong.

Why not just learn a long-horizon policy with constrained RL? Reinforcement learning can in principle learn to anticipate the population's response. Its costs are sample appetite and exploratory deployments, which are exactly the externalities flagged for high-stakes domains. The LDPTRLQ result shows that queue-aligned rewards help on non-convex costs, but only with exogenous arrivals. We include it at a matched interaction budget. If it wins on cumulative violation at that budget, that would argue the real bottleneck is foresight rather than damping, and we would refocus on the anticipatory extension.

Proposed Experiments

We use three environments taken from the file. The first is SFpark hourly parking data, used by both the constrained-equilibrium paper and the geometric-decay paper. Here prices set occupancy through demand that reacts with memory, and the long-term constraint is a time-average occupancy ceiling. The second is a strategic-response credit simulator on the Give Me Some Credit data used in Long Term Fairness via Performative Distributionally Robust Optimization. Its constraints are a long-run default-rate budget and a long-run approval-rate gap between groups. That paper reports minority-group accuracy falling to 54.0% at the stable point reached by ordinary retraining, a useful reference for how stable points can fail a group. The third is the Taiwan Credit Card semi-synthetic setup from Achieving Long-Term Fairness in Sequential Decision Making. There, fairness enforced through retraining costs accuracy, about 0.68 against about 0.82 unconstrained, and that figure gives our cost-of-constraint reference. We add the location-family synthetic market, where the instability threshold is computable exactly.

The metrics are time-average loss, cumulative constraint violation over the full trajectory (reported separately for the transient window and the steady state), the queue trajectory, and an oscillation index: the amplitude of $\|\theta_{t+1}-\theta_t\|$ over the last quarter of the run.

The decisive check runs in the synthetic market. We fix the sensitivity and sweep the constraint budget from slack to tight. We then ask whether undamped queue retraining and Repeated Dual Ascent begin to oscillate at the budget our closed-form condition predicts, and whether the damped variant stays convergent past it. A second check on SFpark and credit asks whether damped drift-plus-penalty achieves lower transient cumulative violation than APDA, without exploration noise, at comparable steady-state cost. A third check varies population memory to test whether the damping rule, rather than epoch-holding, carries the gains when the population adapts slowly.

If the predicted threshold fails to appear, the central claim is refuted. If the threshold appears but the best fixed-$\lambda$ baseline matches the damped queue everywhere, the practical case for queues in performative systems is refuted. Either outcome is informative.