Drift Budgets as Occupancy Regularizers

When a system plans for a person, it usually assumes the person's preferences stay fixed while the plan runs out. In practice they drift. A recommender's user tires of a genre partway through a session. A delivery robot's operator shifts priority from speed to energy. A treatment plan's patient changes what they care about. A planner that must commit before it sees how the preferences move needs a notion of robustness that is honest about the drift. The worst case should be a person whose preferences change by a bounded total amount over the horizon, not an adversary who rewrites the objective arbitrarily at every step.

This note proposes to model preference drift as a drift budget, meaning a cap on the total distance the reward function can travel over the episode. The central observation is that this budget couples reward uncertainty across time steps, so it is a non-rectangular uncertainty set. The worst case is nonetheless exact and cheap. It equals the nominal return minus a penalty on the size of the policy's tail occupancy: how much future state-action visitation the policy still has left at the moment the preference could shift. Planning robustly against drift then becomes a convex program over occupancy measures, solvable in polynomial time. It yields policies that behave differently from both recency-weighted learning and step-wise adversarial games.

Core Claim

Some background first. A robust Markov decision process (MDP) optimizes a policy against the worst environment in an uncertainty set. Most tractable methods assume the set is rectangular, meaning nature perturbs each state-action pair independently. Dropping that assumption for transitions is NP-hard in general (Non-rectangular Robust MDPs with Normed Uncertainty Sets).

For rewards, Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization showed that a coupled $L_p$ ball of rewards is dual to penalizing the $L_q$ norm of the policy's state-action visitation frequencies, where $q$ is the Hölder conjugate satisfying $1/p+1/q=1$. That set is static, however: one perturbed reward holds for the whole episode. We extend the duality to reward sequences that drift.

Fix a finite horizon $H$ and let $d_t(s,a)$ be the probability that the policy is at state $s$ taking action $a$ at step $t$. Nature picks rewards $r_1,\dots,r_H$ from

$$\mathcal{U}=\Big\{\|r_1-R_0\|_p\le\alpha,\ \ \textstyle\sum_{t=1}^{H-1}\|r_{t+1}-r_t\|_p\le V\Big\},$$

where $R_0$ is the nominal reward, $\alpha$ bounds the initial misspecification, and $V$ is the total drift budget. Write each increment $r_{k+1}-r_k$ as $u_k$ and define the tail occupancy $D_{>k}=\sum_{t>k}d_t$. The return $\sum_t\langle d_t,r_t\rangle$ is linear in the increments, with $D_{>k}$ multiplying $u_k$. Minimizing over the budget puts all of it on the single most damaging change point, which gives

$$\min_{\mathcal{U}} \sum_{t}\langle d_t,r_t\rangle=\sum_t\langle d_t,R_0\rangle-\alpha\,\|D_{\ge 1}\|_q-V\max_{1\le k<H}\|D_{>k}\|_q .$$

The objective is concave in the time-indexed occupancies, and those occupancies range over a polytope defined by flow-conservation constraints. The robust problem is therefore a convex program with $SAH$ variables.

Two consequences matter.

  1. Time coupling is what makes it tractable. If the same total drift is split into per-step allowances that nature spends independently (drift that is "rectangular in time"), the penalty becomes an average over all $k$ rather than a maximum. That version charges the policy for $H$ simultaneous worst-case changes that a bounded-drift human cannot produce. This is the temporal analogue of the "lightning doesn't strike twice" argument in Non-rectangular Robust MDPs with Normed Uncertainty Sets.
  2. The regularizer has a behavioral meaning. A drift-robust policy spreads its future visitation across states and actions, so that any single mid-episode shift in preference hurts less. A policy that ignores drift instead concentrates late-episode visitation on whatever the nominal reward favors.

Research Program

The first component is theoretical.

  • Tabular results. We will prove the duality above for general $p>1$. We will also give the discounted infinite-horizon version, where tail occupancies carry geometric weights, and characterize when the optimal robust policy must be non-stationary.
  • Policy gradient. We will derive a robust policy-gradient theorem in the style of the one in Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization. The gradient of $\|D_{>k^\ast}\|_q$ at the active change point $k^\ast$ is an ordinary policy gradient on a pseudo-reward. That pseudo-reward equals the signed power of the tail occupancy and is switched on only after step $k^\ast$. This gives a scalable actor-critic that needs only a learned occupancy estimate and a critic for the pseudo-reward.
  • Multi-objective case. When the reward is $w_t^\top r(s,a)$ with drifting weights $w_t$, the same argument applies with occupancies projected onto reward vectors. This produces a $d$-dimensional penalty that avoids the per-step inner minimization in Time-Consistent Robust Multi-Objective Reinforcement Learning via a Bellman–Isaacs Weight-Adversary Recursion.

The second component addresses the parameter-dependency problem that NS-DPO (Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift) and the COLLABORATIVE bandit (Learning User Preferences in Non-Stationary Environments) both leave open. Both need the variation budget in advance. In our formulation, $V$ is a physical quantity: the total reward distance travelled per horizon. It can be estimated from timestamped preference data by fitting a time-varying reward model and measuring its path length. We will do this on the longitudinal New Yorker Caption Ranking Dataset, which contains eight years of human ratings, and on the drift variant of MovieLens 25m. This gives realistic budgets rather than hand-tuned ones.

Scope. We model drift that is exogenous in time. Satiation that responds to the agent's own actions, as in Ads that Stick, makes nature's reward depend on the trajectory. That behaves more like coupled transition uncertainty, which the frequency-regularization paper flags as not reducible to occupancy norms. We treat it only as a stress test, not as a claim.

Baselines

Nominal planning (naive reference point). This is the plan that maximizes return under $R_0$, or under the most recent reward estimate. It uses the same occupancy-LP solver and the same data. Any drift-robust method must beat it on worst-case return while losing little nominal return. Otherwise robustness is not worth its cost.

Bellman–Isaacs weight adversary (strongest existing method). This is the recursion of Time-Consistent Robust Multi-Objective Reinforcement Learning via a Bellman–Isaacs Weight-Adversary Recursion. It is the only method in the file that plans against drifting preferences in a sequential problem. Its authors report a Weighted Reward Return of −68.56 on MO-Gymnasium Timemove against −76.30 for the next-best baseline.

We will run their tabular and deep variants on the same MO-Gymnasium environments with a matched budget:

  • equal environment steps,
  • equal hyperparameter-search trials for their switching cost $\lambda$ and our $V$,
  • the same number of seeds.

Evaluation uses two adversary classes. The first is their reactive best-response protocol (BR-$K$, where $K$ best-response adversaries are trained against a frozen agent). The second is a budget-constrained open-loop drift adversary. Beating the baseline means matching its BR-$K$ Weighted Reward Return within seed variance while being strictly better under budgeted drift. A further win would be wall-clock savings that grow with objective dimension, on 4D Lunar-Lander and 6D Fruit-Tree. If it loses clearly on BR-$K$, we report that our set is the wrong model for reactive adversaries.

Static frequency regularization. This is the method of Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization, with its radius tuned over the same grid. It is our $V=0$ special case with $\alpha$ free, so it is the natural ablation of the temporal term.

Rectangular-in-time drift. This is the per-step-budget ablation described in the Core Claim. It isolates whether time coupling, rather than extra pessimism, produces the gains.

Rectangular robust dynamic programming. Standard robust value iteration with per-state-action reward boxes serves as the conventional robust baseline.

Replanning with recency weighting. This baseline estimates the reward with NS-DPO-style exponential weights and replans every $m$ steps, where $m$ is swept.

Why not just…?

Why not just recency-weight the preference data, as NS-DPO does? NS-DPO (Right Now, Wrong Then) raised length-controlled win rate from 7.29 to 8.93 on UltraFeedback-LM. That is a result about estimating the current reward from past data. It says nothing about how a committed multi-step plan should hedge against future drift. Recency weighting and our method solve different halves of the problem and compose naturally: estimate $R_0$ with NS-DPO weights, then plan with the drift penalty. The replanning baseline tests whether estimation alone suffices.

Why not just replan frequently, or restart as COLLABORATIVE does? This is the real threat. If the agent observes drift within the episode and can replan cheaply, robust commitment may add little. Restarts at $\Delta_T=100$ already beat static windows on MovieLens (Learning User Preferences in Non-Stationary Environments). We therefore sweep feedback delay and replanning interval, and we report the crossover point where replanning matches the robust plan. The claim is restricted to regimes on the far side of that crossover: delayed feedback, committed schedules, or costly plan changes.

Why not just inflate the static robustness radius? A larger $\alpha$ penalizes total occupancy $\|D_{\ge1}\|_q$. It cannot distinguish a policy that front-loads reward from one that back-loads it, whereas the tail term can. We will construct Garnet MDPs, which are randomly generated benchmark MDPs, where the two penalties rank policies differently. We then check whether the best tuned static radius can reach our worst-case and nominal return frontier. If it can, the temporal term is unnecessary and we will say so.

Why not just use the Bellman–Isaacs game? That game handles reactive adversaries that we do not model. Its per-step inner minimization, however, scales poorly with objective dimension. Its step-wise switching cost also never caps total drift, so it may be over-pessimistic against humans whose drift is budgeted. The two-adversary evaluation above settles which modeling assumption pays off where.

Proposed Experiments

Garnet MDPs. We start with randomly generated Garnet MDPs and the machine-replacement problem used in Policy Gradient Algorithms for Robust MDPs with Nonrectangular Uncertainty Sets. Here the exact worst case over $\mathcal{U}$ can be verified by brute-force linear programming against our closed form. We measure worst-case return, nominal return, return under sampled drift paths, and solve time as $S$, $H$, and $V$ grow. The first decisive check is exactness: the dual penalty must match the brute-force inner minimum to solver tolerance.

MO-Gymnasium. We move to Timemove, Timespeed, DeepSeaTreasure, Lunar-Lander, and Fruit-Tree, against the Bellman–Isaacs baseline under both adversary classes. The second decisive check is whether the time-coupled penalty beats the rectangular-in-time ablation at equal nominal return. If it does not, coupling is not doing the work.

MovieLens 25m. We then use the MovieLens 25m Action/Romance drift variant, cast as a session-level recommendation MDP, with $V$ estimated from the 15 time windows. The third decisive check is calibration. A $V$ estimated from held-out historical drift should give lower out-of-sample regret than $V$ chosen by validation on the test period's own drift. If it does not, the "budget is estimable" claim fails.

Deep actor-critic. The deep actor-critic version is evaluated on the Mountain Car and Ant-v3 settings from the frequency-regularization paper, with a scheduled reward drift. We report cumulative return, CVaR (the mean return over the worst fraction of episodes), and the replanning crossover.

Satiation stress test. Finally, a synthetic ad-scheduling simulation with the convex annoyance loss of Ads that Stick measures how much is lost when drift is actually action-dependent. This bounds the scope of the method rather than claiming to cover it.