Large fleets such as taxis, patrol cars and ships leave behind enormous logs of how their drivers moved. Two properties make these logs awkward to learn from. The drivers are often mediocre: many chase the same busy zone, idle in the wrong place, or react late. And the logs that can be shared at scale usually record only counts, such as how many vehicles moved from zone A to zone B in each interval, with individual identities removed. We propose to learn a fleet policy from such logs by treating control as inference, meaning we compute which flows of vehicles would be probable if the fleet were known to succeed. The model reweights whole configurations of collective movement by how well they serve the fleet's goal. It does not reweight individual drivers' actions one at a time.
The central observation is mathematical and simple. When the probability of a count table is written down exactly, it contains a multinomial coefficient, the number of ways to assign anonymous agents to the observed counts. That coefficient is, to first order, the population-weighted entropy of how agents spread across choices. Conditioning such a model on success therefore produces an anti-herding pressure on its own. Online anonymous-fleet learners had to add this pressure by hand as a density-entropy bonus. Reweighting agents one at a time, the natural offline fix for mediocre demonstrators, lacks it. That approach sends every agent toward the currently best-looking zone. When returns diminish, which is the normal case, this reproduces the herding that makes the demonstrators suboptimal in the first place.
Core Claim
The setting has three ingredients. There is an offline log of state-action count tables from a population of exchangeable agents, most of whom are not experts. A collective reward can be computed from the logs, such as served demand or incidents answered on time. And a simulator or fitted transition model exists for evaluation only. In this setting, a policy fit to the success-conditioned posterior over flows will beat per-agent advantage-weighted imitation. The margin should grow with how strongly the reward saturates in agent counts and should vanish when the reward is linear in counts.
To make this concrete, let $n_t(s)$ be the number of agents in zone $s$ at time $t$. Let $m_t(s,a)$ be how many of them take action $a$ (for example, drive to zone $a$). Let $\beta(a \mid s, n_t)$ be the demonstrators' behavior policy estimated from the logs. Let $R_t(m_t)$ be the collective reward, and let $\alpha$ be a temperature. The object we sample is
$$p(m_{1:T} \mid O = 1) \propto \prod_t \exp\!\big(R_t(m_t)/\alpha\big) \prod_s \frac{n_t(s)!}{\prod_a m_t(s,a)!} \prod_a \beta(a \mid s, n_t)^{m_t(s,a)},$$
subject to flow conservation between consecutive count tables. By Stirling's approximation, the log of the middle factor is approximately $\sum_s n_t(s)\,H\big(m_t(s,\cdot)/n_t(s)\big)$, where $H$ is Shannon entropy. This is a count-weighted spreading term whose strength is tied to $\alpha$ rather than tuned separately. Per-agent weighting such as $\exp(\beta \hat A(s,a))$ applied to each logged action matches this posterior only when $R_t$ is linear in $m_t$. With saturating rewards such as served demand $=\min(\text{supply},\text{demand})$, the two differ exactly where herding happens.
Relation to Prior Work
Methods we reuse. Collective Graphical Models showed how to do inference directly on anonymous transition counts. It uses Markov-basis cycle moves whose step distribution is log-concave, so the sampler's cost does not depend on population size. That work only estimates passive flows (for example bird migration) and leaves learning to future work. We add the success conditioning and a policy-fitting step. Collective Multiagent Sequential Decision Making Under Uncertainty introduced Fictitious EM, which alternates sampling count trajectories with fitting a count-conditioned policy $\pi(a \mid s, n)$. It requires online simulator rollouts and a known reward, and it uses no demonstrations. We keep its EM shape but make the E-step a posterior over logged flows anchored to the demonstrators' behavior. The general recipe of inferring a reward-tilted trajectory posterior and then regressing the policy onto it comes from Matthew Hoffman et al. and the control-as-inference formulation of Sergey Levine et al.. Both are single-agent.
Work that motivates the gap. Offline imitation methods that tolerate bad demonstrators all assume individual trajectories or identities. Exponentially Weighted Imitation Learning for Batched Historical Data (MARWIL) reweights each logged action by exponentiated advantage. Imitation Learning by Estimating Expertise of Demonstrators (ILEED) learns a per-demonstrator skill embedding. Revisiting Distribution Correction Estimation for Offline Imitation Learning with Suboptimal Dataset (ReDICE) was run on the multi-ship ShipNaviSim, but only as an ego-centric single agent. Collective imitation such as CBIL matches swarm distributions adversarially and so assumes the swarm is optimal. The team method BTIL handles suboptimality but tracks each agent's latent state, which it applies only to two-agent domains.
Work that constrains the design. Entropy Based Independent Learning in Anonymous Multi-Agent Settings found that independent learners in taxi fleets herd into hot spots, and fixed this with a hand-added density-entropy reward. We claim to derive a version of that bonus rather than invent it, and we test whether the derivation matters in practice. Credit Assignment For Collective Multiagent RL With Global Rewards shows that per-agent advantages are too noisy under non-decomposable global rewards. That is the regime where we expect per-agent weighting to fail.
A known pitfall. Control-as-inference with stochastic dynamics lets the posterior "wish" for lucky transitions. Here that would mean tilting the customer demand itself toward favorable values. We therefore tilt only the action counts $m_t$ and hold demand and travel outcomes at their fitted model distribution. This is a structured variational choice that we will ablate.
Research Program
We will build one algorithm, which we call collective posterior imitation. It has three stages.
The first stage estimates the behavior prior $\beta(a \mid s, n)$ and a zone-level transition and demand model from the count logs alone.
The second stage is the E-step. It runs cycle-move MCMC over flow tables consistent with conservation, targeting the tilted posterior above. The CGM sampler handles the combinatorial moves. The reward tilt is added as a Metropolis correction. For large fleets, a Gaussian approximation in the style of Gaussian Approximation of Collective Graphical Models serves as a fallback.
The third stage is the M-step. It fits a neural policy $\pi_\theta(a \mid s, n)$ by maximum likelihood on the posterior flow samples. The policy becomes the next iteration's proposal, while $\beta$ stays fixed as the anchor.
The temperature $\alpha$ absorbs the known reward-scale problem. We select it on held-out log days by off-policy return estimates, with the same budget given to every baseline's weighting parameter.
On the analysis side, we will make the Stirling-based spreading term precise, including its error for small zone counts. We will also prove that the posterior reduces to per-agent exponential weighting exactly when $R_t$ is affine in $m_t$. This gives the falsifiable prediction that drives the experiments.
Baselines
The naive reference is replaying the demonstrators themselves. We score the logged fleet behavior, or $\beta$ run in the simulator, which tells us how much room for improvement the logs leave. Next is count behavioral cloning, which fits $\pi(a \mid s, n)$ to the empirical flow proportions. This amounts to FEM's M-step fed with logs instead of posterior samples.
The strongest competitor is count-conditioned MARWIL. It uses the loss from Exponentially Weighted Imitation Learning for Batched Historical Data, with a critic $Q(s,a,n)$ that sees current crowding, and it weights each logged count $m_t(s,a)$ by $\exp(\beta \hat A)$. It is strongest because it already handles bad demonstrators, it already sees counts, and it scales. The only thing it lacks is joint reasoning about simultaneous moves by others. The file reports no offline-imitation number for any method on the taxi or patrol benchmarks, so we will establish MARWIL's number ourselves. Its single-agent evidence is strong, with a TORCS score of 9492 against 2710 for plain imitation, reported in that paper.
We will also run count-MARWIL with a tuned density-entropy bonus as in Entropy Based Independent Learning in Anonymous Multi-Agent Settings. This is the hand-built version of our mechanism. On synthetic data where trajectories are available, we will add ReDICE run ego-centrically per agent with count features. All offline methods get identical logs, the same policy network, the same critic architecture, and an equal hyperparameter search of 30 configurations each, selected on the same validation days.
The key ablation removes the multinomial coefficient and the joint reward, leaving a per-agent tilt inside otherwise identical EM machinery. This isolates the collective-conditioning ingredient. A second ablation lets the tilt act on demand as well, to measure how much the optimistic-dynamics fix matters.
As online upper bounds that need a simulator, we will run FEM and MCAC. Their published figures set the ceiling. Closed-loop FEM achieved over 20% higher solution quality than prior methods on robot congestion (Collective Multiagent Sequential Decision Making Under Uncertainty). MCAC reached a 7.8% failure rate on police patrolling against 9.32% for static allocation, and reduced unserved taxi demand by 32% (Credit Assignment For Collective Multiagent RL With Global Rewards).
Beating the field means outperforming count-MARWIL and count-MARWIL with the entropy bonus on served demand or failure rate, with non-overlapping 95% intervals across seeds, while staying offline.
Why not just…?
Why not just use count-conditioned MARWIL? Each agent's weight comes from a critic evaluated at the current crowding. The critic cannot account for the fact that other agents in the same zone are being pushed toward the same high-advantage action at the same moment. Under a saturating reward, the tenth taxi sent to a hot zone gets the same weight as the first. Entropy Based Independent Learning in Anonymous Multi-Agent Settings documents exactly this herding in anonymous fleets. This is a genuine threat when rewards are nearly linear. Our affine-reward theorem predicts a tie there, and the concavity sweep below tests whether the gap actually opens as rewards saturate.
Why not just add the density-entropy bonus to MARWIL? This is the most serious alternative, because it may recover most of the gain. What we offer instead is a spreading strength tied to the same temperature as the reward, with no extra knob, and a spreading term that is joint over the flow rather than a per-zone heuristic. If tuned MARWIL plus the bonus matches us at equal tuning budget, we will report the contribution as an explanation of why the bonus works rather than a better method. The equal-budget comparison is designed to settle this.
Why not just run MCAC or FEM in a simulator? The target regime is logs without a trusted simulator. Online methods also need a hand-specified reward and discard what human drivers know about the city. We include them as upper bounds. A fair secondary test is whether our policy is a better warm start for FEM than behavioral cloning.
Why not just recover identities and use ILEED or BTIL? Count logs do not contain identities, and BTIL is demonstrated only on two-agent teams. In the synthetic setting we can hand ILEED the true identities as an oracle. If it wins there, the lesson is that identities are worth collecting, which is itself informative.
Proposed Experiments
The decisive experiment is synthetic. We use the 81-zone and 111-zone taxi simulators from the anonymous-fleet papers above. Populations are mixtures in which a fraction $\rho \in \{0.05, 0.2, 0.5\}$ of agents follow a FEM-trained expert and the rest follow greedy or noisy policies. The logs keep only count tables. We sweep a reward-concavity parameter from linear revenue to hard min-capacity service. The prediction is that our method ties count-MARWIL at the linear end and pulls ahead as concavity increases, with the no-multinomial ablation tracking MARWIL throughout. If there is no gap at high concavity, the core claim is wrong.
Second, on the real Singapore taxi GPS traces aggregated to counts, we measure served demand, revenue and earnings variance across zones. On police patrolling (16 cars, 24 zones), we measure the failure rate against the 7.8% online MCAC figure and the 9.32% static-allocation figure.
Third, a scaling check varies fleet size from 500 to 8,000 and confirms that E-step wall-clock time per sweep stays roughly flat. The CGM sampler's population-independent cost predicts this.
Finally, a transfer check converts ShipNaviSim traffic into lane-segment counts. We then compare near-miss counts against ego-centric ReDICE. The file gives no reported numbers for ReDICE on ShipNaviSim, so we will measure that baseline ourselves.
References
- Collective Graphical Models
- Collective Multiagent Sequential Decision Making Under Uncertainty
- An Expectation Maximization Algorithm for Continuous Markov Decision Processes with Arbitrary Reward
- Variational Policy Search via Trajectory Optimization
- Exponentially Weighted Imitation Learning for Batched Historical Data
- Imitation Learning by Estimating Expertise of Demonstrators
- Revisiting Distribution Correction Estimation for Offline Imitation Learning with Suboptimal Dataset
- ShipNaviSim: Data-Driven Simulation for Real-World Maritime Navigation
- CBIL: Collective Behavior Imitation Learning for Fish from Real Videos
- Semi-Supervised Imitation Learning of Team Policies from Suboptimal Demonstrations
- Entropy Based Independent Learning in Anonymous Multi-Agent Settings
- Credit Assignment For Collective Multiagent RL With Global Rewards
- Gaussian Approximation of Collective Graphical Models