Dario Fumarola
← Presented workNY-RL 2025

Control under partial information

Broadcast-Gain

Two-byte junction control under partial information

Broadcast-Gain uses sparse reports to schedule competing approaches at a junction. We identify a case where better report delivery postpones service, derive its expected switch time, and replace the conditional fallback with an unconditional deadline.

Expected next-switch timeWith one waiting reporter, original BG rises from 24 to 48 steps as delivery probability increases. A 24-step unconditional deadline stays fixed.4840322400.51Expected next switch · stepsDelivery probability qOriginal BGBG-D · H = 24
Original: 31.38 stepsBG-D: 24 steps

Probability of each original switch time

49.0%24
14.7%30
14.7%36
7.5%42
14.1%48 steps
Exact calculation for one stationary reporter on the unserved axis, with a report every six steps. Clearance follows the switch. Move the slider to change delivery probability.

The single-reporter counterexample

The original rule switches after four reporting cycles when its cache is empty. With a nonempty cache, an evidence test governs early switches and the maximum hold rises to eight cycles. One or two effective reports cannot pass the evidence test, even when all reports favor the unserved axis.

With one stationary agent waiting and no traffic on the served axis, complete loss therefore gives a switch at step 24. Reliable delivery keeps the cache nonempty and delays the switch to step 48. With two-step clearance, the waiting axis first opens at step 26 or 50.

Under independent delivery probability \(q\), an empty cache requires two consecutive lost attempts. Let \(f_n(q)\) be the probability of no adjacent losses in \(n\) attempts. The expected next-switch time is

\[ \begin{aligned} f_0=f_1&=1,\\ f_n&=qf_{n-1}+q(1-q)f_{n-2},\\ \mathbb E[\tau]&=C\left(4+\sum_{n=2}^{5}f_n(q)\right). \end{aligned} \]

The curve above evaluates this recurrence exactly. A delivered report can remove an empty-cache switching opportunity without supplying enough support for an evidence-triggered switch.

Section 3.1 and Appendix B ↗

Reports and the unconditional deadline

Agents within eight cells of the gate send a signed waiting-progress residual in one byte and their axis and distance in another. Sender identity and sequence number are transport fields outside this payload. Cached reports receive freshness weight \(\eta_j=e^{-a_j/C}\), where \(a_j\) is report age.

\[ Q_s=\sum_{j:s_j=s}\eta_j e^{-d_j/8}\frac{1+\widehat x_j}{2}, \qquad n_{\mathrm{eff}}=\sum_j\eta_j. \]

The corrected rule, BG-D, gives each phase a physical-time deadline \(t_0+H\). The deadline is checked every environment step, outside the report-dependent support and minimum-hold tests. Eligible evidence can cause an earlier switch:

\[ \tau=\min\!\left\{t_0+H,\ \inf\{t>t_0:E(t)\}\right\}. \]

For any report sequence, an axis's uninterrupted interval without green is at most \(H+c\), where \(c\) is clearance and \(H>c\). This bounds service interruption; agents can still wait behind a queue.

Algorithm 1 and Proposition 1 ↗

Workload results and timing tradeoffs

In the stress workload, making the 24-step fallback unconditional lowers p95 waiting from 173.4 to 164.9 steps. The paired reduction is 8.5 steps [7.2, 9.8]. Throughput rises from 678.9 to 682.8 crossings per 1,000 steps.

Phase traces show that 46.0% of original phases exceed the 24-step fallback; the corrected rule has no such extension. The narrower weak-cache patch lowers p95 by only 0.7 steps. Most extended phases have more support than the single-reporter example, but inconclusive evidence.

A separately selected 12-step timer has lower waiting in the reference workload. Its advantage changes with clearance cost and demand imbalance.

p95 waiting, in steps. One-factor changes from the stress workload, with greedy movement and fixed controller settings. Table 5.
WorkloadFixed 12Fixed 24Original BGBG-D(24)
Reference156.8184.6173.4164.9
Steady 50:50 demand143.5164.7149.8141.9
Steady 90:10 demand307.2283.0214.5263.7
64-step alternation171.6203.7190.2178.4
One-step clearance139.7167.8154.6146.8
Six-step clearance280.4181.6202.3192.7
80 agents77.691.496.382.9
180 agents211.6244.8237.9222.4

With six-step clearance, a 12-step phase spends half its time closed. Under persistent 90:10 demand, original BG benefits from longer service on the busy axis, and capping it at 24 steps increases waiting. Enforcing the deadline and choosing its duration are separate decisions.

Unequal loss also biases service. With 60% and 80% erasures on the two axes, the higher-loss minus lower-loss p95 gap falls from 37.3 to 17.8 steps under BG-D(24), after exchanging loss labels within each paired realization. The remaining gap reflects report-dependent evidence before the deadline.

Reference: 140 agents, 70% report loss, six-step reporting, two-step clearance, and 75:25 demand alternating every 256 steps. Tables 1, 3, 4 and 5 ↗

Scope and measurements

The tests use one junction with fixed routes. Greedy movement is the main comparison because legal movement carries no energy or risk penalty. Learned PPO movement and the optional report-conditioned logit gain are secondary controls.

Waiting subtracts the 48-step free-flow traversal from each visit's ready-to-completion time. Reported p95 is the mean of realization-level quantiles, not a pooled percentile. The service bound does not establish individual waiting guarantees or network stability; downstream spillback, transport delay, and failure of the reliable status interface are outside the evaluation.

Full paper

Broadcast-Gain: Two-Byte Junction Control under Partial Information

Dario Fumarola · Amazon Web Services