A defender who schedules patrols against human attackers faces a problem with three parts. The attackers are not perfect optimizers: they choose noisily, and how noisily changes over time as they tire, learn, or are replaced by new people. The defender must keep expected losses under a hard budget every round, not only on average in the long run. And computing a good patrol schedule against a noisy attacker is expensive: in sequential games a single solve can take hours. We propose a rule that tells the defender when it must re-solve and when it can safely keep its current schedule. The rule rests on an asymmetry. Checking how a fixed schedule performs against a noisy attacker of a given noise level is cheap, while finding the best schedule is expensive. So the defender tracks a widening band of plausible attacker noise levels and re-solves only when the worst case inside that band would break the loss budget.
The attacker model we use is quantal response, a standard model of noisy choice in which the attacker picks each target with probability proportional to $e^{\lambda U}$, where $U$ is the attacker's expected payoff and $\lambda$ measures how rational the attacker is. Human-subject studies such as Improving Resource Allocation Strategy against Human Adversaries in Security Games and Beyond Equilibrium: Predicting Human Behavior in Normal-Form Games show that this model predicts real attackers better than perfect rationality. These studies treat $\lambda$ as fixed and known. The claim of this note is that treating $\lambda$ as a slowly drifting quantity, and certifying the current schedule against a drift-aware band of $\lambda$ values, keeps round-by-round loss-budget violations near a target rate. It should do so with a small fraction of the solver calls that periodic re-solving or surprise-triggered re-solving would need at the same violation rate.
Core Claim
Let $x$ be the defender's mixed patrol strategy, and let $L(x,\lambda)$ be the defender's expected loss against a quantal-response attacker with rationality $\lambda$. The defender must keep $L(x,\lambda_t) \le \varepsilon$ in each round $t$. A Bayesian filter over $\log\lambda$ uses a random-walk prior, so its credible interval $[\lambda^-_t,\lambda^+_t]$ widens between informative attacks and does not collapse under slow drift. The defender holds its current strategy as long as
$$\max_{\lambda\in[\lambda^-_t,\lambda^+_t]} L(x,\lambda)\le\varepsilon .$$
Evaluating this condition is a one-dimensional scan. Each point on the scan costs one pass of the attacker's response against a fixed $x$: a softmax over targets in normal-form games, or a single tree traversal in extensive-form games. When the condition fails, the defender calls the expensive solver. That solver returns a strategy that satisfies the budget over a padded interval $[\lambda^-_t - m, \lambda^+_t + m]$ and has the best nominal utility among such strategies. The margin $m$ is the single knob. It trades conservativeness, meaning utility given up, against expected hold time, meaning solver calls saved. The trade has a predictable shape: under a random walk with per-round step size $\sigma$, the credible interval widens roughly as $\sigma\sqrt{t}$, a standard diffusion result, so expected hold time should scale like $(m/\sigma)^2$.
The same certificate governs exploration. The defender needs informative attacks to learn $\lambda$, but it only ever deploys strategies whose worst case over the current band meets the budget. Learning about the attacker therefore never buys information with budget violations.
Relation to Prior Work
Two strands supply the method. Computing Quantal Stackelberg Equilibrium in Extensive-Form Games gives the expensive inner solver: a Dinkelbach-type reformulation solved as a mixed-integer linear program. It solved a 6-step search game in about 3.5 hours where a baseline failed within 3 days. We reuse this solver unchanged and add budget constraints at a finite grid of $\lambda$ values. BRQR from Improving Resource Allocation Strategy against Human Adversaries in Security Games is the normal-form counterpart. The same paper constrains the design: prospect-theory parameterizations sometimes did worse than the perfect-rationality baseline because they over-protected some targets. We therefore start with the quantal response model and treat richer behavioral models as a later extension, not the core. The nested-choice model of Choices Are Not Independent and the belief-updating attacker of Security Games with Limited Surveillance supply stress-test attackers whose parameters we also drift.
Four papers motivate the gap and differ in specific ways. Pausing Policy Learning in Non-stationary Reinforcement Learning shows that holding a policy fixed beats continuous updating. It uses a fixed update-to-hold ratio and has no safety constraint; our hold length is set by a safety certificate instead. A Surprise Triggered Adaptive and Reactive (STAR) Framework re-models only when prediction error is surprising, and reports 94% fewer model operations against switching Rock-Paper-Scissors opponents. Its trigger measures how wrong the model is, not whether the current action is still safe. Under slow drift those two questions come apart. Towards Safe Policy Improvement for Non-Stationary MDPs argues that slow drift is more dangerous than abrupt change because it looks like noise. That is exactly why our filter widens between observations. SPIN also relies on importance sampling and assumes the change is exogenous. We avoid importance sampling by exploiting the known structure of how the attacker responds to $x$, which confines the non-stationarity to a low-dimensional parameter. Provably Efficient Model-Free Algorithms for Non-stationary CMDPs achieves zero violations through periodic hard restarts. We keep the model and restart nothing.
The closest bounded-rationality work, Robust Adversarial Reinforcement Learning via Bounded Rationality Curricula and Dynamic Obstacle Avoidance with Bounded Rationality Adversarial Reinforcement Learning, uses $\lambda$ as a training curriculum that the designer controls. It handles collisions with reward penalties. In our setting the adversary's rationality drifts outside the defender's control at deployment time, and safety is a hard per-round constraint. Context-Aware Safe Reinforcement Learning for Non-Stationary Environments infers hidden parameters online and runs risk-averse model predictive control at every step. Our design is the opposite in cost: the defender re-optimizes rarely and verifies cheaply.
On the computational-overhead direction, the file's material concerns large-model RL, including rollout latency and memory for multiple models. We borrow only its central lesson: when the inner optimization loop dominates cost, reduce how often you run it. We do not claim anything about language models.
Research Program
We will build the filter, the certificate, and the padded constrained solver for two game families. The first is normal-form security games with 10 to 100 targets, using payoff structures modeled on the human-subject study. The second is the extensive-form search and network games from the quantal Stackelberg equilibrium paper, where each solve takes minutes to hours.
On the analysis side, we will first show the conditions under which a filter with a random-walk prior yields calibrated intervals when the true drift is slower or faster than the prior assumes. We will then derive the hold-time scaling in $m/\sigma$ and a bound on the violation probability per round in terms of the interval's coverage. Finally, we will handle the part of drift the defender causes itself. Under the limited-surveillance attacker, a change in $x$ shifts attacker behavior only after the attacker has observed the new schedule. The certificate must therefore evaluate $L$ against the attacker's lagged belief about $x$, not against $x$ itself, and we will implement that variant.
One scoping point is honest to state up front. In small normal-form games BRQR solves in under a minute, so re-solving every round is affordable and our method's advantage there is only robustness. The compute argument lives in the extensive-form regime.
Baselines
The naive reference is a single strong Stackelberg equilibrium solve, assuming a perfectly rational attacker, held forever. It anchors the claim that bounded rationality matters. A second static reference solves the quantal Stackelberg equilibrium once at the initial $\lambda$ estimate and never updates.
The strongest competitors are compute-matched adaptive schemes that use the same filter and the same solver. The first is periodic re-solving in the style of the pausing paper, with its period tuned on held-out drift seeds and then fixed so that its total solver calls equal ours. The second is a STAR-style trigger that re-solves when the cumulative negative log-likelihood of observed attacks crosses a threshold, with the threshold tuned the same way. The third is the "fully robust once" scheme: a single padded solve over a wide prior range of $\lambda$, never revisited.
Every-round re-solving serves as the compute-unlimited upper reference. It is not a competitor to beat on utility. It measures how much utility the certificate gives up.
Two ablations isolate the key ingredient. The first uses a static posterior with no random-walk widening, which tests the slow-drift argument. The second sets the margin $m=0$, which tests whether the pad is what buys long holds.
We found no reported result on Lacuna for any defender against a drifting quantal-response attacker, so no published number exists for these baselines in this setting. The nearest reported figures are STAR's 94% fewer model operations, SPIN keeping unsafe deployments below its 5% threshold where stationary baselines reached 40%, and DTA's roughly 3.5-hour solve. They set expectations but are not directly comparable.
Beating the baselines means one of two things. At equal solver calls, our method must have a lower per-round violation rate with no loss of cumulative utility. Or at a matched violation rate, it must use substantially fewer calls. We pre-register the target that the certificate stays at or below a 5% per-round violation rate while using at most one fifth of the every-round solver calls, in regimes where both compute-matched adaptive baselines exceed that rate.
Why not just…?
Why not just re-solve on a fixed schedule? A fixed period is tuned to one drift speed. When drift is slow it wastes calls, and during fast phases it lets violations accumulate. The pausing paper itself leaves adaptive hold lengths open. Our mixed-speed drift experiments, which alternate slow drift with abrupt jumps, test this directly. If periodic re-solving matches us at equal compute under stationary-speed drift, we will report that and restrict the claim to variable-speed drift.
Why not just trigger on surprise? Surprise measures how poorly the model fits recent attacks. It says nothing about whether the current schedule still meets the budget. A large misfit in the attacker's behavior on low-value targets can trigger costly solves that are unnecessary, while a small, steady drift on high-value targets can breach the budget without ever looking surprising. That second case is the slow-drift failure the SPIN paper warns about. The STAR baseline at matched compute settles this. This is the most serious threat, and if it ties us we would conclude that the certificate adds interpretability but not performance.
Why not just solve one maximally robust strategy and never update? If the plausible range of $\lambda$ is narrow, this may be enough, and it is a real threat in that regime. We will sweep the prior range. We expect the fixed robust strategy to give up large utility when the range spans nearly random to nearly rational attackers, because protecting against both extremes forces coverage onto targets that only one attacker type would hit. The utility gap measured against every-round re-solving quantifies this.
Why not just assume a perfectly rational attacker? The human-subject evidence already shows that quantal-response defenders outperform perfect-rationality defenders against people, and the limited-surveillance work finds the same for attackers with limited information. We include the strong Stackelberg equilibrium baseline mainly to confirm that result in our simulated regime.
Proposed Experiments
Simulated attackers follow a quantal-response model whose $\log\lambda$ drifts in one of three ways: a slow random walk, piecewise-constant jumps, or a sinusoid. Stress-test attackers use nested-logit and limited-surveillance models whose nesting strengths and observation counts $\tau$ drift in the same ways. Each run lasts several thousand rounds, and we report 20 seeds per condition.
We measure three things: the per-round budget-violation rate, cumulative defender utility, and the number of solver calls and wall-clock solver time. The decisive check has three parts. On the extensive-form search game under slow drift, the certificate must meet the 5% violation target at a fraction of every-round compute where compute-matched periodic and surprise triggers do not. The static-posterior ablation must fail that same test, which would confirm that drift-aware widening does the work. The measured hold time must grow roughly quadratically in $m/\sigma$.
If the 40-subject game data from the human-subject study are obtainable, we will replay the attack sequences in their recorded order as a sanity check on whether real $\lambda$ estimates drift at all. If they show no drift, that would itself narrow the proposal's relevance.
References
- Improving Resource Allocation Strategy against Human Adversaries in Security Games
- Beyond Equilibrium: Predicting Human Behavior in Normal-Form Games
- Computing Quantal Stackelberg Equilibrium in Extensive-Form Games
- Choices Are Not Independent: Stackelberg Security Games with Nested Quantal Response Models
- Security Games with Limited Surveillance
- Pausing Policy Learning in Non-stationary Reinforcement Learning
- A Surprise Triggered Adaptive and Reactive (STAR) Framework for Online Adaptation in Non-stationary Environments
- Towards Safe Policy Improvement for Non-Stationary MDPs
- Provably Efficient Model-Free Algorithms for Non-stationary CMDPs
- Robust Adversarial Reinforcement Learning via Bounded Rationality Curricula
- Dynamic Obstacle Avoidance with Bounded Rationality Adversarial Reinforcement Learning
- Context-Aware Safe Reinforcement Learning for Non-Stationary Environments