Hierarchical Abstractions for Sequential Decision-Making with Applications to Stochastic Games

Computing an equilibrium in a game with many players, continuous dynamics and limited onboard computation is, in general, out of reach. The cost comes from two directions at once: the number of agents, which makes the joint state and action spaces explode, and the size of the environment, which makes even a single agent’s planning problem expensive. This project attacks both with abstractions — compressed descriptions of the environment and of the population that are small enough to reason about in real time, yet faithful enough that the resulting strategies remain sound. On the environment side, this means information-theoretic tree and graph abstractions that allocate detail where it earns its keep. On the population side, it means replacing a large team of interchangeable agents by its mean field.

When a team is made up of many interchangeable agents, no individual identity matters to the outcome — only the distribution of the team over the state space does. In the infinite-population limit that distribution is the team’s mean field, and a game between two large teams becomes a game between two distributions. We built a proximal-policy-optimization algorithm, MF-MAPPO, on this information structure: each team’s critic sees only commonly available information, namely the two mean fields, while an agent’s private state enters only through its own policy, so the networks scale independently of team size. Because a team rarely observes its opponent’s distribution directly, we added a gradient penalty that enforces Lipschitz continuity in the mean field, so small estimation errors produce only small changes in behavior, together with a decentralized consensus filter that supplies valid estimates under a limited number of communication rounds. On large-population battlefield and epidemic-spread benchmarks the method outperformed every baseline we could find or construct. A further line of work relaxes the usual assumptions that agents are fully rational and that the initial distribution is known, giving risk-averse quantal-response equilibria and their multi-population counterparts, in which each population hedges against ambiguous behavior by the others — at a modest cost in nominal reward, these equilibria degrade far more gracefully when the realized population flows deviate from the nominal ones.

MF-MAPPO. The critics see only the two team mean fields — common information — while each agent’s private state enters only through its own policy, so the networks scale independently of team size.

Abstraction also has a cost that is invisible in single-agent planning and decisive in a game. An agent that groups many states into one superstate must act identically across all of them: that is precisely what makes planning cheap, and precisely what an adversary can exploit once it works out which abstraction the agent is using. We formulated this as an asymmetric-information game and showed that it can be written as a bilinear program whose linear core encodes the Bayesian belief dynamics as flow constraints, rather than iterating between policy optimization and belief propagation. What emerges from the solution is strategic concealment: the agent randomizes between a task-efficient path and a concealing one, hiding its representation only when the benefit outweighs the loss in task performance.

The Attacker holds a private environment representation; the Defender watches its trajectory, infers which representation is in use, and places the barrier that best exploits that representation’s blind spots.

Making any of this useful means solving the resulting games fast enough to close a control loop around them. We developed a family of real-time solvers for constrained dynamic games — a fast Newton solver exploiting the structure of the equilibrium KKT system, an operator-splitting method for games in which the cooperative objectives dominate the competitive ones, and an interior-point method with a curvature correction that steers the iterates away from the spurious saddle points that first-order methods tend to find — together with a numerical certificate that a computed point really is a local generalized Nash equilibrium. A parallel effort addresses games on graphs, where small sub-team games are solved exactly offline and their policies and value functions then steer an online tree search, lifting the usual restriction to a single evader.

Hardware validation on BuzzRacer, the laboratory’s palm-sized autonomous vehicle platform. The solvers compute generalized Nash equilibria at receding-horizon rates for fleets of four to eight cars, producing defensive blocking and coordinated overtaking online under tight physical constraints.

Sponsors

This project is funded by ONR.