Source-linked AI summary
The BAR-SOT Method: Long-term Average Cost Control as Stochastic Optimal Self-Transport
Sharan Srinivasan, Berke M. Turkay, Harsha Honnappa
TL;DR
Average-cost control couples the policy to its invariant law, making the optimal rate and relative value interdependent. BAR-SOT recasts the problem as a finite-horizon controlled self-transport loop; at ρ = 0.9, its workload dual attains 14.04 average holding cost, comparable to work-conserving PPO (14.10) and below LBFS (14.32).
Problem
Average-cost control couples the optimal cost rate, relative value, and policy, while the invariant law depends on the policy being chosen.
Source: §1.1 · p. 1Method
BAR-SOT jointly optimizes a controlled finite-horizon marginal flow and its common endpoint law, with the flow constrained by the basic adjoint relationship.
Source: §8 · p. 45Results
At ρ = 0.9, the workload dual attains an average holding cost of 14.04, comparable to work-conserving PPO (14.10) and below LBFS (14.32).
Source: §7.1.4 · p. 34Takeaways & Limitations
The BAR-SOT value equals T times the ergodic rate when the Poisson equation has a relative value solution and the optimal control meets the stated recurrence and integrability conditions.
Source: §8 · p. 45For partially controlled scheduling dynamics, the conditioned cost-tilted reference path law is generally unattainable, so the classical guarantee is not claimed.
Source: §5.5 · p. 26
Abstract
from arXiv · showhide
We reformulate average-cost (ergodic) control of a Markov jump process as a finite-horizon stochastic optimal transport (SOT) problem that jointly optimizes over the controlled evolution and the marginal law from which it starts and returns to (i.e., a self-transport). The constraint relating the marginal flow to the controlled generator is the basic adjoint relationship (BAR), so we call the resulting problem BAR-SOT. For any time horizon T>0, its optimal value is a constant scaling of the long-run average-cost rate. We give three equivalent formulations (through controlled processes, a Fokker--Planck constraint, and relaxed marginal measures) and show that the optimal dual is a stationary potential plus a term linear in time, with slope equal to the rate. A relative-entropy penalty on the control yields a cost-tilted Schrodinger bridge problem, computable by a Sinkhorn-type iteration when every transition rate is controlled, whose value converges to the unregularized optimum as the penalty vanishes. We develop the theory for finite Markov decision processes and then for general controlled Markov jump processes. A neural parametrization of the dual, trained as a physics-informed neural network (PINN), that encodes Harrison's equivalent-workload formulation (see Harrison 2000) matches the strong reinforcement-learning baseline of Dai and Gluzman (2022); numerically conditioning the fit of a sub-dominant transverse correction then improves on both that baseline and the best priority heuristic. On the input-queued switch, a graph-attention parametrization of the dual improves on the strongest matching heuristic we are aware of, with a parameter count that does not grow with the switch size.
1. Introduction
Average-cost control couples policy choice to the invariant law it induces, making its gain and relative value mutually dependent. BAR-SOT recasts this problem as a finite-horizon self-transport loop and uses its periodic dual to support an entropically regularized computational approach.
1.1. Background and Motivation.
- The average-cost optimality equation links the cost rate, relative value, and policy, while the invariant law is determined only after a policy is fixed.Classical relative value and policy iteration depend on the controlled chain’s mixing rate.Source: §1.1 · p. 1
- BAR-SOT optimizes a controlled finite-horizon flow that returns to its starting marginal, then optimizes over that common endpoint law.The flow is constrained by the basic adjoint relationship, and the resulting meta-SOT value is T times the ergodic rate.Source: §1.1 · p. 2
- The optimal dual is a time-periodic boundary-value problem whose additive constant equals the meta-SOT value, retaining the self-consistency of the average-cost problem.A consistent dual exists only at the meta-SOT value because the rate enters a non-coercive Poisson equation.Source: §1.1 · p. 2
- Entropic regularization replaces hard control maximization with a log-sum-exp and a smooth randomized Gibbs control, making the BAR-SOT formulation computationally tractable.It does not remove the intrinsic eigenvalue problem or its self-consistency.Source: §1.1 · pp. 2–3
1.2. Literature Survey.
- The transport lift differs from steady-state occupation-measure LPs by exposing a time-periodic dual and leaving the invariant law free.The LP formulations optimize a single stationary occupation measure subject to a balance constraint.Source: §1.2 · p. 3
- The framework draws on stochastic optimal transport and Schrödinger bridges, while optimizing a common endpoint law under controlled dynamics rather than steering between prescribed marginals.Its entropy-regularized control problem is related to Sinkhorn or iterative proportional fitting methods.Source: §1.2 · p. 4
2. Finite Markov Decision Processes as a Self-Transport Problem
The finite-state, discrete-time development turns average-cost control into an N-step loop of controlled state-action marginals with a shared endpoint law. The basic adjoint relationship identifies its value with the ergodic rate, while entropy regularization gives a cost-tilted bridge formulation.
2.1. The Ergodic Problem as a Linear Program.
- For a finite MDP, randomized state-action marginals describe the controlled flow, and under the unichain assumption the optimal average cost agrees with the stationary occupation-measure LP.That LP has an optimum at a deterministic stationary policy, so admitting randomized rules does not change its value.Source: §2.1 · p. 5, §2 · p. 5
2.2. The N-Step Self-Transport Problem.
- The N-step self-transport problem seeks the cheapest controlled flow that leaves and returns to a common endpoint law, then minimizes over that law.Randomization lets the flow match the prescribed endpoint marginal; the formulation is the discrete-time finite-state BAR-SOT instance.Source: §2.2 · p. 6
2.3. The Discrete Basic Adjoint Relationship and the Ergodic Value.
- Time-averaging any feasible N-step flow yields a stationary BAR-feasible occupation measure, and the stationary BAR is equivalent to the LP balance constraint.The proof pairs this lower bound with a constant optimal occupation-measure flow to attain the ergodic value.Source: §2.3 · pp. 7–8
- Unlike the stationary LP’s single measure, self-transport uses stepwise state-action measures and the endpoint law, enabling a route through entropic regularization.The loop requires stationarity only of the time average.Source: §2.3 · p. 8
- Optimizing over the endpoint law makes the self-transport value equal to the ergodic value for every horizon, not only asymptotically.The matched endpoints cancel the telescoped flow’s endpoint contribution exactly, including at N = 1.Source: §2.3 · p. 8
2.4. Entropic Regularization and Schrödinger Bridge Form.
- With a fixed endpoint law, entropy-regularized self-transport is a Schrödinger bridge for a cost-tilted reference, with Sinkhorn-type computation under the stated identification’s scope.The cost tilts the reference control by its Gibbs factor; the paper names this the cost-tilted bridge.Source: §2.4 · pp. 8–9
- Uniformization carries the discrete BAR and endpoint condition to bounded-rate jump processes, but state-dependent intensities without a finite bound require the general continuous-time treatment.That treatment replaces boundedness with natural Lyapunov conditions.Source: §2.4 · p. 9
3. Long-term Average Cost Control as a Stochastic Optimal Transport Problem
This section recasts long-run average-cost control as finite-horizon stochastic self-transport, with the controlled flow constrained by the BAR and its initial and terminal marginal laws equal. It establishes equivalence between flow and relaxed-measure formulations and, using duality and a Poisson equation, connects their values to ergodic control: under the stated hypotheses, the finite-horizon optimum is T times the rate and the ergodic self-transport and control values agree.
3.1. Process Formulation of Self-Transport Problem.
- The process formulation requires a controlled process to begin and end with a prescribed law; with time-independent cost, its finite-horizon value matches the ergodic problem.The control may vary over time, as a loop returning to its initial law need not be generated by a stationary control.Source: §3.1 · p. 11
3.2. Weak Basic Adjoint Relationship (BAR) Formulation of Self-Transport Problem.
- The weak-BAR formulation optimizes a loop of probability measures and controls subject to the weak forward equation, which becomes the loop BAR constraint at the terminal time.The flow satisfies ρ_0 = ρ_1 = π̃.Source: §3.2 · p. 11
3.3. Relaxed Marginal Measure Formulation of Self-Transport Problem.
- The relaxed marginal formulation optimizes over joint state-time-control measures, allowing randomized controls; this relaxation matters on the switching set where maximizing actions are nonunique.In the two-class queue example, maximizing controls are bang-bang away from the switching set, while the relaxed kernel may split mass on it.Source: §3.3 · pp. 12–13
3.4. Equivalence of the Three Formulations.
- Under a convex action set, control-affine generator, lower-semicontinuous convex cost, and bounded jump intensity, the process, weak-BAR, and relaxed-marginal formulations have equal values.The jump intensity must satisfy q(x, S; u) ≤ κ_V(1 + V(x)).Source: §3.4 · pp. 13–14
- The controlled-process and relaxed-measure formulations correspond through the BAR constraint, with the loop condition and finite-energy requirements preserved.Disintegrating the relaxed measure and taking its barycentric control yields a controlled process with the same marginal flow and no greater cost.Source: §3.4 · p. 15
3.5. The Dual Problem and Weak Duality.
- Weak duality bounds the primal value below by the dual value, with equality at the optimizing marginal under the Poisson-equation ansatz.The dual optimizer has the form h(x) + (t − T)g*, where h is the Poisson potential.Source: §3.5 · p. 15, §3.6 · p. 17
3.6. The Ergodic Problem.
- Under coercive cost, a suitable Poisson solution, and irreducibility of its maximizing control, that process is positive Harris recurrent with a unique invariant law and finite cost.The recurrence conclusion uses the condition that −h is bounded below with relatively compact sublevel sets.Source: §3.6 · p. 17
- For every T > 0, the optimized self-transport value is Tg*, and under additional admissibility and moment conditions the ergodic control value also equals g*.The common value is attained at the invariant law of the pointwise maximizing control.Source: §3.6 · pp. 18–19
- Reflected dynamics fit the framework, but charging boundary local time requires singular-control BAR and duality extensions left for future work.The boundary cost introduces an expected boundary occupation measure in the BAR identity and a gradient constraint in the dual.Source: §3.6 · p. 19
4. The Optimality System and the Difficulty of a Direct Solve
The section formulates the self-transport optimum as a coupled HJB–Kolmogorov system with a periodic endpoint condition. It explains that unknown ergodic cost, nonlinear switching, and self-consistent boundary data make direct solution difficult, motivating entropic regularization.
4.1. The optimality system.
- The optimality system couples a backward HJB, a forward Kolmogorov equation for the induced marginal flow, and the closure ρ0 = ρT = π̃.Because the running cost is independent of ρ, the flow is a passive readout once the dual potential determines the control.Source: §4.1 · pp. 19–20
4.2. Why a direct solve is hard.
- The ergodic rate g* must be found with the solution: periodic closure makes the lifted potential solve a nonlinear Poisson eigenvalue problem.The potential is determined only up to constants, and the periodic problem has no prescribed terminal data to make the operator invertible.Source: §4.2 · p. 20
- The HJB is fully nonlinear, and control-affine scheduling can produce abrupt bang-bang switches and a nonsmooth relative value along an unknown switching surface.For continuum state spaces, a classical solution need not exist; on lattices the unknown switching surface remains difficult.Source: §4.2 · p. 20
- The periodic boundary law is self-consistent rather than given: it is the stationary law generated by the optimal control, so the flow cannot start from known endpoints.The outer problem also optimizes over that endpoint law.Source: §4.2 · p. 20
- The state space can be large and unbounded, adding a scale challenge that the paper addresses separately through a neural representation of the dual.The section distinguishes this scale issue from the structural obstacles in the optimality system.Source: §4.2 · p. 20
- Entropic regularization replaces the hard control supremum with a smooth soft Hamiltonian, addressing bang-bang discontinuity but not the unknown ergodic rate directly.The endpoint gap Tg* can instead be imposed as a periodic boundary condition on the soft HJB.Source: §4.2 · pp. 20–21
5. Iterative Resolution via Entropy Regularization
Entropy regularization smooths BAR-SOT control selection and supports an endpoint-scaling iteration for the self-transport bridge. Its classical convergence guarantee applies in the fully controlled case, not generally to partially controlled scheduling.
5.1. Entropy Regularization.
- The KL penalty regularizes the control kernel relative to a reference while leaving the endpoint and BAR constraints unchanged.The endpoint law is fixed for this inner problem; optimization over it is deferred.Source: §5.1 · p. 21
5.2. BAR Dual and Gibbs Kernel.
- The dual BAR multiplier induces a local Gibbs control law by exponentially tilting the reference kernel, but this alone does not determine state-marginal evolution.A forward transition-rate kernel is needed to convert local control randomization into probability flow.Source: §5.2 · p. 22
5.3. Forward Self-Transport Under the Gibbs Kernel.
- The Gibbs kernel induces forward state flow, and the bridge condition requires that flow to return to its initial endpoint law.The coupled system combines a backward soft Hamilton–Jacobi equation, a forward equation, and the endpoint identity.Source: §5.3 · p. 23
5.4. Iterative Endpoint Scaling.
- Endpoint scaling updates the terminal dual potential according to the mismatch between the generated terminal marginal and the target law.This is the BAR-SOT analog of Sinkhorn scaling; the update can be damped.Source: §5.4 · p. 24
5.5. Convergence of Endpoint Scaling.
- With fully controlled rates and the stated hypotheses, endpoint scaling converges to the unique minimizer; the classical guarantee is not claimed for partially controlled scheduling.Under two-sided kernel bounds the convergence is linear in the Hilbert projective metric; in scheduling, endpoint conditioning can alter uncontrolled arrival rates.Source: §5.5 · pp. 25–26
6. The Outer Problem as a Periodic Boundary-Value Problem: Untruncated Solution at Scale
The outer optimization is recast as a periodic boundary-value problem for the BAR dual, removing the endpoint law as an optimization variable. The entropy-regularized value converges to the unregularized value, with a finite-action estimate for single-server scheduling.
6.1. The Optimal Dual is Time-Periodic.
- The optimal dual is time-periodic up to an additive constant, whose value is Tg* and is independent of the endpoint law.The state-dependent Poisson potential returns to itself over the horizon, and the constant endpoint gap resolves the outer optimization.Source: §6.1 · pp. 26–27
6.2. Consistency of the Regularized Value.
- The entropy-regularized dual value converges to the unregularized value as ε → 0, with an O(Tε log 1/ε) upper-gap bound; convergence of maximizers is not claimed.The regularized value over-estimates the unregularized value.Source: §6.2 · pp. 27–28
- The finite-action Hamiltonian gap is O(ε); Figure 2 reports slope E˜π[log n] = 0.196, below the uniform bound ε log k.The estimate is for the single-server finite-action setting, and the figure reports the gap over three orders of ε.Source: Figure 2 · p. 30, §6.2 · p. 30
6. The Outer Problem as a Periodic Boundary-Value Problem: Untruncated Solution at Scale
- The outer problem is solved numerically by collocation of the soft-HJB residual under a neural parametrization of the dual.The reported applications are scheduling multiclass reentrant networks and input-queued switches.Source: §6.2 · p. 30
7. Numerical Examples
The numerical examples apply the periodic dual to a reentrant network and an input-queued switch, using different neural parametrizations for their respective scaling challenges.
7. Numerical Examples
- For a six-class reentrant network, the dual's action-separating component becomes a vanishing fraction of its magnitude near full load, motivating a Harrison equivalent-workload architecture.The network is presented as a standard heavy-traffic benchmark.Source: §7 · p. 30
- For the input-queued switch, graph attention parametrizes the dual on the bipartite structure despite a super-exponentially sized matching control set.The switch state is the full matrix of queue lengths.Source: §7 · p. 30
- Both problems use the periodic dual's entropy-regularized Gibbs control, evaluated by long-run average holding cost in one validated simulator against available baselines.The passage states the evaluation setup but does not report the comparison outcomes.Source: §7 · p. 30
7.1. Heavy Traffic and the Equivalent-Workload Architecture.
In the six-class reentrant network, heavy traffic makes the action-relevant differences in the dual small relative to the value being fitted. Encoding workload structure in the dual makes it resolvable at high load, and conditioning the fit of its transverse correction improves the resulting policy beyond LBFS.
7.1.1. Benchmark and the heavy-traffic obstruction.
- As ρ approaches 1, the action-relevant advantage is only about (1 − ρ)^2 of the dual’s magnitude, making direct queue-coordinate fitting ill-conditioned.At ρ = 0.9, this ratio is about 1%.Source: §7.1.1 · p. 31
7.1.2. The equivalent-workload architecture.
- The workload architecture splits the queue into W = Mx and z ∈ ker M, assigning the diverging value to W and the finite-load correction to z.This confines the heavy-traffic conditioning obstruction to the sub-dominant transverse term.Source: §7.1.2 · p. 32
7.1.3. An architecture-agnostic baseline.
- A network-agnostic pooling model diverges for ρ ≳ 0.85, whereas the workload architecture tracks LBFS through ρ = 0.9.The dimension scan finds that m ≈ 4–8 approaches the workload architecture and LBFS; m = 1 is insufficient.Source: §7.1.4 · p. 34, Figure 7 · p. 35, Figure 8 · p. 36
7.1.4. Numerical results.
- At ρ = 0.9, the standard workload dual’s average holding cost is 14.04, versus 14.10 for PPO and 14.32 for LBFS.The dual is fit by collocation with a load homotopy, warm-starting from light load and annealing ε at each stage.Source: §7.1.4 · p. 34, Table 1 · p. 35
7.1.5. Improving the transverse correction.
- 13.64: at ρ = 0.9, the residual-conditioned dual falls below LBFS, improving on the standard-fit dual’s parity with PPO.The improvement requires both freezing the leading workload value and normalizing the residual; neither ingredient alone suffices.Source: §7.1.4 · p. 34, Figure 7 · p. 35, Table 2 · p. 38
- The residual-conditioned fit resolves the transverse correction by freezing the workload value and normalizing the residual together.The correction provides the lower-order allocation through which a policy may improve on LBFS; its fit remains variance-limited at heavier loads.Source: §7.1.5 · pp. 36, 38, 39
7.2. Scheduling the input-queued switch.
The switch experiments test whether a learned BAR-SOT dual can improve scheduling beyond strong matching heuristics, including under heavy traffic and increasing switch size. The learned policy’s advantage depends on the regime: it improves on Algorithm 2 at moderate sizes, while the advantage shrinks to parity by N = 50.
7.2.1. The switch and the comparison policies.
- The switch has N² queues and matching actions, and Algorithm 2 is the strongest general-N competitor identified by the authors.MaxWeight is throughput-optimal but myopic; weighted MaxWeight accounts for costs but remains a one-slot rule.Source: §7.2.1 · pp. 39–40
7.2.2. The dual and the induced schedule.
- The learned dual ranks matchings by expected future cost, providing lookahead beyond the one-slot backlog ranking of MaxWeight.Its entropy-regularized control is a Gibbs kernel; the reference control anchors stability by retaining support on work-conserving matchings for ε > 0.Source: §7.2.2 · pp. 40–41, §7.2.3 · p. 41
7.2.3. The construction of the learned dual.
- The dual is fitted on states visited in steady state, using exact arrival-distribution targets rather than squared residuals from single sampled arrivals.The latter would add arrival variance to the squared error and bias the fit.Source: §7.2.3 · p. 41
7.2.4. Performance at moderate load.
- For the weighted 2 × 2 switch, the tabular BAR-SOT dual matches the known optimum at +0.0%, while weighted MaxWeight is about 20% above it.The dual also reproduces the optimum on the symmetric unit-cost instance within simulation error.Source: §7.2.4 · p. 41
- On the weighted 3 × 3 switch, the learned dual’s schedule costs 5.3% less than Algorithm 2 across five training seeds, with every seed improving.The paired comparison uses common random numbers; Table 4 reports average weighted backlog at ρ = 0.85.Source: §7.2.4 · p. 41, Table 4 · p. 42
7.2.5. Deep heavy traffic.
- At ε = 0.5, the control beats Algorithm 2 by 5.0% at ρ = 0.9 and 3.3% at ρ = 0.95; setting ε to zero produces instability at both loads.The reported positive-ε improvements average five seeds, with every seed beating Algorithm 2.Source: §7.2.5 · p. 42, Table 5 · p. 42
7.2.6. Scaling to large switches.
- For large switches, a shared bipartite graph-attention dual seeds port embeddings with workloads and edge embeddings with local queue information, keeping parameter count independent of N.Shared maps give port-relabeling equivariance, while message passing supplies per-cell corrections beyond workloads.Source: §7.2.6 · pp. 43–44, Figure 11 · p. 43
- At ρ = 0.85, the dual beats Algorithm 2 through moderate switch sizes and reaches parity by N = 50, as cost-weighted MaxWeight also closes its gap.The narrowing margin reflects the scheduling problem becoming easier as switch size grows, rather than degradation of the dual.Source: §7.2.6 · pp. 44–45, Table 7 · p. 45
8. Discussion and Conclusion
The discussion characterizes BAR-SOT as a periodic self-transport reformulation of average-cost control and describes entropy-regularized computation and structured neural dual approximations. Experiments support effective state-dependent control in tested finite-load settings, with stated boundaries and directions for further work.
8. Discussion and Conclusion
- When the average-cost Poisson equation has a relative value solution and the induced optimal control meets recurrence and integrability conditions, BAR-SOT has value Tg* for every horizon T > 0.The optimal dual combines the relative value function with a linear time term of slope g*, and its endpoint gap is Tg*.Source: §8 · p. 45
- Entropy regularization yields a smooth soft-Hamiltonian and state-dependent Gibbs kernel; a Sinkhorn-type endpoint-scaling relation converges when endpoint-conditioned tilted dynamics remain admissible.The numerical experiments approximate the periodic soft dual directly rather than using the endpoint-scaling iteration.Source: §8 · p. 46
- The experiments show effective state-dependent control in tested finite-load configurations, but input-switch experiments found empirical instability at ε = 0 and reentrant estimates became more sensitive to initialization and training variability near critical load.The authors therefore characterize the comparisons as finite-load results.Source: §8 · p. 46
- Future directions include learning across workload maps and models, and extending the BAR framework to boundary control with a local-time occupation measure and a dual gradient constraint.The boundary-control question is whether the primal optimum and state-independent dual endpoint gap still equal Tg*.Source: §8 · p. 46
AI Statement
The authors report that generative AI tools assisted with language refinement and aspects of code development, while the authors retain responsibility for the research and conclusions.
AI Statement
- Generative AI assisted with language refinement and some code development; the authors say they reviewed and verified AI-assisted content.The authors attribute the research questions, theory, methodology, analysis, and conclusions to themselves.Source: AI Statement · p. 47