What Slack Costs: Memory Requirements of Lexicographic Long-Run Control

Many controllers must rank goals rather than trade them off. A delivery robot should first keep its battery-and-dock routine alive, then maximize throughput, then save energy. Lexicographic optimization handles this by maximizing the top goal, then the next goal among the options that remain. Practical versions add slack: the controller may give up a small amount, δ, of a higher goal to gain on lower ones. Deep lexicographic reinforcement learning methods implement slack as a constraint on expected return, and they use memoryless policies, which map the current state to an action with no internal record of the past. This note argues that the definition of slack, rather than the number of objectives, determines how much memory the controller needs. The same definition decides whether the slack is safe at all.

The core observation is short. If slack is measured in expectation, the optimal controller can be a lottery: at the start of a run it flips a weighted coin and commits forever to one of a few fixed policies. Some fraction of runs then gives up the top-priority goal entirely, while the average still looks within tolerance. If slack must hold on every run, lotteries are forbidden. The controller must instead share time between behaviors within a single run. Time-sharing has different memory needs, and the formal-methods literature shows those needs can become infinite when the top goal is a recurring obligation. We propose to map these regimes exactly. We will build learners whose memory matches each regime, and we will test whether current lexicographic reinforcement learning (RL) methods quietly learn lotteries.

Core Claim

Fix an MDP (Markov decision process: a state machine with random transitions and actions chosen by the controller) with long-run average rewards $r_1 \succ r_2 \succ \dots \succ r_n$, ordered by priority. Let $\mathrm{MP}(r)=\liminf_{T\to\infty}\frac1T\sum_{t<T} r_t$ be the long-run average of reward $r$ along one run, and let $v_1^*$ be the best achievable value of the top objective. There are two definitions of slack on the top objective:

$$\text{expectation slack: } \mathbb{E}^\sigma[\mathrm{MP}(r_1)] \ge v_1^*-\delta, \qquad \text{per-run slack: } \Pr^\sigma[\mathrm{MP}(r_1)\ge v_1^*-\delta]=1,$$

where $\sigma$ is the controller's strategy. Lower objectives are then maximized subject to the chosen constraint, in the same way at each level. We conjecture, and plan to prove, three statements.

The first concerns expectation slack. A start-of-run random choice among at most $a+1$ memoryless deterministic policies suffices, where $a$ is the number of slack constraints that are binding. That is about $\log_2(a+1)$ bits, set once, and the size does not depend on the number of states. The bound should follow from writing the achievable expectation vectors as a polytope, as in Markov Decision Processes with Multiple Long-run Average Objectives, and applying Carathéodory's theorem: a point on a face of dimension $a$ is a convex combination of at most $a+1$ vertices. Strict lexicography ($\delta=0$) should need no memory, because the lexicographic optimum of a linear program is a vertex. Slack therefore creates the memory requirement.

The second concerns per-run slack, where the top objective is a recurring qualitative obligation such as "visit the dock infinitely often" (a parity or Büchi condition) and the second is average throughput. Exact optimality needs infinite memory, as shown in Energy and Mean-Payoff Parity Markov Decision Processes. We conjecture that any δ>0 lowers this to no memory at all for randomized controllers: leave the high-reward cycle with a fixed small probability per step. The ergodic theorem within an end component (a set of states the controller can stay in forever) then gives the per-run average almost surely.

The third concerns deterministic controllers under per-run slack. These need a counter, and we conjecture its size is $\Theta(L\Delta/\delta)$. Here $L$ is the expected length of a detour away from the high-reward cycle, and $\Delta$ is the reward lost per detour step. The form comes from the time-sharing arithmetic: the fraction of time spent on detours must be at most $\delta/\Delta$, so the counter must hold roughly $L\Delta/\delta$ steps on the high-reward cycle between detours.

The practical consequence is that a memoryless stochastic policy trained against an expectation constraint can satisfy the constraint "on average" by sacrificing whole runs. Nothing in standard reporting would reveal this.

Relation to Prior Work

Two formal results supply the method and the anchors. Stochastic games with lexicographic objectives proves that strict lexicographic reachability and safety games need only memory that scales with the number of objectives, not the state space. That paper explicitly leaves mean-payoff objectives and slack open, and our first conjecture is the slack analogue of its result. The 2-memory stochastic-update strategies of Markov Decision Processes with Multiple Long-run Average Objectives, together with the unified linear program of Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, give us the polytope and the exact solver used as an oracle. Neither paper imposes a priority order. The mean-payoff-parity infinite-memory result constrains the design, since it rules out exact per-run optimality with any finite controller. We treat δ as the quantity that makes the problem realizable.

Four lexicographic-with-slack methods motivate the gap, because all of them assume memoryless policies. Multi-Objective MDPs with Conditional Lexicographic Reward Preferences applies slack separately at each state inside value iteration (LVI). Prioritized Soft Q-Decomposition for Lexicographic Reinforcement Learning (PSQD) restricts each state's actions to an "indifference set" of near-optimal actions. Both of these are per-state, per-run notions, and we expect them to be conservative. Lexicographic Multi-Objective Reinforcement Learning applies tolerance to expected values through Lagrangian actor-critics, called LPPO (lexicographic proximal policy optimization) and LA2C (lexicographic advantage actor-critic). This is exactly the expectation-slack regime where lotteries appear. Multi-objective Linear Reinforcement Learning with Lexicographic Rewards proves regret bounds only for episodic linear MDPs, where memory across episodes plays no role. Model-Free Reinforcement Learning for Lexicographic Omega-Regular Objectives shows that the structure of a memory automaton matters a great deal in learning. On its 108-node chain, satisfaction probability was 1.0 with an optimized automaton and 0.50 with a logically equivalent one. That paper handles only qualitative objectives.

Research Program

The theory part proves or refutes the three conjectures. It also gives matching lower bounds through small gadget MDPs, such as a fork into two irreversible end components for the first claim and a cycle with a stochastic detour for the third. For n priority levels, we will characterize how slack constraints compound: we expect the mode count to grow with the number of binding constraints, not with n.

The algorithm part builds two learners. The first is a committed-mode learner for the expectation regime. It samples a discrete mode from a learned distribution with support of size $a+1$ at the start of each run, then runs a mode-conditioned memoryless policy. Mixture weights are fit by a small linear program over the estimated value vectors of the modes. This makes the lottery explicit and auditable instead of hidden. The second is a per-run learner. It enforces the constraint on each run's empirical average through a chance-style constraint on the distribution of run-level returns. It adds a bounded deficit counter of size set by the $L\Delta/\delta$ formula when the controller must be deterministic.

Baselines

The naive reference point is strict lexicographic action pruning with δ=0, as in the reduction of Stochastic games with lexicographic objectives. It needs no memory and gives the floor on secondary performance. Beating it means higher secondary return at equal per-run primary guarantees.

The strongest deep competitor is LPPO from Lexicographic Multi-Objective Reinforcement Learning. It is the most direct implementation of expectation slack in deep RL. The file gives no reported LPPO numbers: no reported result found on Lacuna for LPPO returns or violation rates on CartSafe, GridNav or IntersectionEnv. The only reported claim is that LPPO and its deep Q-network counterpart matched or outperformed two earlier constrained-RL methods (RCPO and AproPO). We will run the authors' tolerance settings and equalize sample budget and hyperparameter search (same number of seeds and trials) across all methods. Beating LPPO means matching its expected primary and secondary returns while reducing the fraction of runs that violate $v_1^*-\delta$. In the per-run regime, it means beating LPPO's secondary return at zero violations.

PSQD and LVI represent per-state slack. Beating them means higher secondary return under the same per-run guarantee, which would show that per-state slack is overly conservative. The only reported figure for LVI is a runtime: under nine minutes on GPU for the New York City network, versus over 4.5 hours on CPU. For PSQD the file reports only qualitative results, namely zero collisions in 2D Navigation.

Linear scalarization with $w_1 \gg w_2$ is included as the reviewer's default. A GRU (gated recurrent unit) recurrent version of LPPO, in the spirit of DCRAC, tests whether generic learned memory finds the right structure. On tabular instances, the exact linear program of Unifying Two Views gives the true optimum for both slack semantics, and all learners are scored as a gap to it.

Two ablations isolate the key ingredients. The first removes commitment from the committed-mode learner by resampling the mode every step. The second removes randomization from the per-run learner, which forces it to rely on the counter alone.

Why not just…?

Why not just use a stochastic memoryless policy, since deep RL already randomizes? In the per-run regime our second conjecture says this is exactly right, and the experiments are designed to confirm it rather than argue against it. In the expectation regime, randomizing at a fork between two places the controller can never leave already acts as a lottery. In general, Markov Decision Processes with Multiple Long-run Average Objectives proves that memoryless strategies cannot even approximate some trade-off points. Our gadget MDPs will place the slack optimum at such points.

Why not just let a recurrent network learn whatever memory it needs? It may well work for expected return. The risk is that it learns the lottery without anyone noticing. The chain result in Model-Free Reinforcement Learning for Lexicographic Omega-Regular Objectives, 1.0 versus 0.50 satisfaction depending on memory structure, warns that memory structure strongly affects learning. We will report the GRU baseline's per-run violation distribution and probe whether its hidden state encodes a fixed mode.

Why not just use per-state slack (LVI or PSQD), which is memoryless and already safe on every run? This is a real competitor. If its secondary-return gap to the per-run linear-program optimum is negligible on our benchmarks, our per-run learner adds little, and we will say so. We expect per-state slack to compound across states and to lose measurably in environments with long detours.

Why not just use a chance-constrained or risk-sensitive constrained MDP? It is the natural way to implement per-run slack, and our per-run learner borrows from it. What it does not give is the memory characterization: which policy class is sufficient, and what counter size a deterministic controller needs.

Proposed Experiments

On tabular gadgets and long-run versions of the Hallway and CleaningRobot games from Stochastic games with lexicographic objectives, built in PRISM and Mungojerrie, we will compute exact optima under both semantics. For each δ, we will measure the minimal memory a verified strategy needs, using the linear program to find the optimum and gadget-specific counting to find the memory. This directly tests the $a+1$ mode bound and the $L\Delta/\delta$ counter scaling.

For deep RL, we will use CartSafe, GridNav and IntersectionEnv from Lexicographic Multi-Objective Reinforcement Learning, and minecart, four-room and deep-sea-treasure from MO-Gymnasium. Each is run with and without a recurring checkpoint obligation, and we will add irreversible branches so that multiple end components exist. The metrics are expected primary and secondary return, the fraction of runs below $v_1^*-\delta$, the conditional value-at-risk of the primary objective (its average over the worst runs), the gap to the linear-program optimum where it can be computed, and controller memory in bits.

The decisive check is whether LPPO's per-run primary returns are bimodal in the multichain variants, which would mean it learned a lottery, while its mean satisfies the tolerance. If they are not bimodal, the safety half of the argument fails and the work reduces to the memory characterization. A second check is whether the committed-mode learner with $a+1$ modes matches the exact expectation optimum while resampling the mode every step does not. A third is whether randomized memoryless exits attain the per-run optimum on the mean-payoff-parity gadgets, as conjectured, while deterministic controllers need counters that grow as $1/\delta$.