Displacement-Budgeted Local Steps for Learning in Games Under Limited Communication

When many self-interested learners share a road network, a market, or a training job, they must repeatedly exchange strategies. Each exchange costs bandwidth and time. The usual way to save communication is to let each agent take several local steps between exchanges, holding the other agents' strategies fixed at their last known values. In games this has an effect that is easy to miss. Stale information changes more than the convergence speed. It also changes how much total welfare the agents lose along the way. A striking empirical result shows this clearly. In Combining Car-to-Infrastructure Communication and Multi-Agent Reinforcement Learning in Route Choice, vehicles that query roadside infrastructure with probability $\tau = 0.25$ reach an average travel time of 21.265 minutes on the Sioux Falls network, close to the 20.76-minute equilibrium. Broadcasting to every vehicle ($\tau = 1$) produces herding and pushes the average to 33.941 minutes. The best communication rate there was found by trial and error, and no theory explains it.

We propose a rule for deciding when to communicate. Instead of fixing a number of local steps, each agent keeps stepping on its own until its strategy has moved a set distance from where it stood at the last exchange, and only then synchronizes. That distance is set online from quantities the agent can observe, with no need to know the size of the search space. Bounding how far an agent can move on stale information does two things at once. It bounds the error its opponents incur by using its old strategy, and it caps how far a crowd of agents can jump together in the same direction. The same budget therefore controls both convergence and herding. It applies in unbounded strategy spaces, such as prices, or the scores that a route-choice policy turns into probabilities, which drift toward infinity as agents commit to pure strategies.

Core Claim

Communication period and welfare are coupled. The right control variable is displacement per round, not steps per round. Concretely, player $i$ records its strategy $\bar x_i^r$ at the start of round $r$. It then takes local gradient steps against the frozen opponent profile while

$$\|x_{i,t} - \bar x_i^r\| \le \lambda_i^r, \qquad \lambda_i^r = c \,\frac{\|g_i(\bar x^r)\|}{\hat L_c^r},$$

where $g_i$ is player $i$'s gradient at the synchronized profile, $\hat L_c^r$ is a running estimate of how strongly one player's gradient reacts to others' moves, and $c<1$ is a single constant. The estimate comes from gradient changes observed across past synchronizations. The form follows from a smoothness argument. If cross-player sensitivity is $L_c$, a displacement of $\lambda$ perturbs each opponent's gradient by at most $L_c\lambda$. Choosing $\lambda \propto \|g\|/L_c$ keeps the staleness error a fixed fraction of the true signal.

Local step sizes follow the distance-adaptive rule of DADA: Dual Averaging with Distance Adaptation. That method scales steps by the distance travelled from the initial point and normalizes gradients, which gives optimal rates without a known domain diameter. When gradient noise is heavy-tailed, updates are clipped following clipped-SSTM and its variational-inequality extension (clipping for VIs).

The claim has three parts. First, the rule adapts the effective number of local steps to the coupling strength. It takes many steps when coupling is weak and falls back toward one step per exchange when coupling is strong. This makes it tuning-free where the method in Decoupled SGDA proves convergence only for coupling degree $\kappa_c < 1/4$ with a fixed step count $K$. Second, it lowers the welfare lost during learning, measured against the system optimum, at equal communication. Third, it keeps these properties in unbounded domains.

Research Program

Theory. We first analyze the rule on strongly-monotone games, the setting of Decoupled SGDA. The target result is linear convergence in communication rounds at every coupling strength, with round complexity degrading smoothly in $\kappa_c$ rather than diverging past $1/4$. We state this as a conjecture to prove, not a known fact. We then extend it to monotone games in unbounded domains, using the distance-adaptive analysis of DADA. We flag one known obstacle: DADA is proven for deterministic subgradients. Its stochastic, distributed extension is an open problem that we attack directly, using clipping as the noise-control device.

The welfare quantity. For nonatomic routing, the equilibrium flow is unique. Staleness therefore cannot change where learning ends, only what it costs to get there. We define a trajectory price of anarchy as the time-averaged social cost along the learning trajectory, divided by the system-optimum cost. This is exactly the quantity that herding inflates. For anti-coordination games such as Hawk-Dove and Cournot competition, staleness may also change which equilibrium is selected. We connect this to The Symmetry Trap, which shows that agents with identical architectures stay locked on a symmetric, inefficient manifold. We test whether asynchronous displacement budgets break that symmetry, as architectural diversity does in that work.

Empirical validation as a design constraint. The research file documents repeated cases where methods are proven fast but never measured, for example EMGD. Every claim here will therefore be reported in wall-clock time and bits transmitted, alongside rounds.

Baselines

The naive reference is fully synchronous simultaneous gradient play, with one local step per exchange. It is also run at the other extreme, broadcasting to every agent every step, which is the $\tau=1$ regime. On Sioux Falls, the C2I paper reports average travel times of 33.941 minutes under full broadcast and 21.9 minutes with no communication.

The strongest domain-specific baseline is the intermittent-communication Q-learning of Combining Car-to-Infrastructure Communication and Multi-Agent Reinforcement Learning in Route Choice at its best rate, $\tau=0.25$, with a reported average travel time of 21.265 minutes against a 20.76-minute equilibrium. Beating it means reaching an average within 21.265 minutes at fewer infrastructure queries, or a lower trajectory price of anarchy at an equal query count. We reimplement it on the same demand and cost functions.

The strongest optimization baseline is fixed-$K$ Decoupled SGDA, along with its opponent-predicting Ghost-SGDA variant. It is run on the same games and seeds, with $K$ tuned by grid search at a tuning budget equal to that spent on our constant $c$. The file lists no reported numerical result on Lacuna for Decoupled SGDA's GAN experiments (no FID table), so we will regenerate its numbers ourselves.

Two ablations isolate the key ingredient. The first replaces the displacement trigger with a fixed step count matched to our average steps per round. The second removes distance adaptation, restoring a fixed step size and a projection onto a ball of guessed radius.

Why not just…?

Why not just tune the communication rate or $K$ per instance? This is the real threat, since the C2I Goldilocks result was found exactly this way. Our answer is that the best $K$ depends on coupling, which varies across instances and over time. We will build families of instances with coupling degree swept from about $0.05$ to above $1/4$, and compare our single $c$ against a fixed $K$ tuned once on one instance, and against an oracle $K$ tuned separately per instance. If the per-instance oracle matches us everywhere, the contribution shrinks to "tuning-free," and we will say so.

Why not just lower the step size to damp herding? Damping does reduce oscillation, but it slows every agent in every phase, including phases where coupling is weak. The prediction is more communication rounds for the same final gap. The step-size sweep, reported on the rounds-versus-trajectory-price-of-anarchy curve, decides this directly.

Why not use tolls to remove the inefficiency? Demand-Independent Tolls shows that tolls needing no demand knowledge exist only when every road shares the same congestion exponent. Cyclic networks may even require subsidies. Tolls also shift the equilibrium itself, whereas herding is a transient learning cost. The two approaches are complementary, and we will test ours both with and without marginal-cost tolls.

Proposed Experiments

Sioux Falls (24 nodes, 76 edges, over 360,000 trips). Vehicles use softmax route policies over unconstrained scores. We measure average travel time, the trajectory price of anarchy, the number of queries, and wall-clock time. We add heavy-tailed travel-time noise to test clipping.

Continuous pricing games. Following Decentralized Multi-product Pricing, firms choose unbounded prices, and diagonal dominance gives controllable coupling. This supplies the coupling sweep described above.

Hawk-Dove and Cournot games. These follow the Symmetry Trap setup, which reports that identical-architecture agents converge to suboptimal outcomes in 74% of trials, while architecturally diverse agents reach pure Nash equilibria in 81%. We check whether asynchronous displacement budgets recover the diverse-architecture rate without diversity.

GAN training on CIFAR-10 and SVHN. This follows Decoupled SGDA, measuring FID against communication rounds.

Decisive checks. Three results decide the proposal. First, above $\kappa_c = 1/4$, fixed-$K$ Decoupled SGDA should diverge while our rule converges. Second, on Sioux Falls, ours should reach an average travel time of 21.265 minutes or better at fewer queries than the $\tau = 0.25$ baseline. Third, the fixed-step ablation should lose most of the gain. If the ablation matches the full method, the displacement trigger is not the operative ingredient and the claim fails.