Background and Motivation
Many real-world systems involve a large number of interacting agents whose states evolve over time based on local interactions. Examples include epidemics, biological signaling networks, and distributed robotic systems. These interactions are often structured by sparse networks: each agent typically communicates or interacts with only a small subset of other agents. Designing scalable control strategies in such settings, while respecting locality and privacy constraints, is an important challenge in modern systems engineering.
Research Objectives
This project aims to develop a rigorous framework for the optimal control of stochastic interacting agents connected by large sparse random graphs. We focus on two fundamental questions:

1. Does the optimal control strategy for a finite network converge to a limiting policy as the number of agents grows?
2. Can we exploit structural symmetries of the limiting graph (e.g., infinite trees) to characterize this policy via recursive equations?

Approach and Preliminary Insights
We consider a population of stochastic agents evolving on a random graph, where each agent’s dynamics depend on its state, the empirical distribution of its neighbors’ states, and a control action drawn from a common, state-dependent policy. The central objective is to minimize the expected long-term cost incurred by a uniformly chosen agent. To analyze the large-population limit, we model the network as a sequence of sparse random graphs (e.g., uniform k-regular graphs) and study their convergence in the local weak sense to an infinite rooted tree. We have formally defined the control problem on this limiting tree and expressed the cost functional in terms of the marginal law at the root. We also proved a symmetry property of local distributions, showing that under i.i.d. initial states and a shared policy, the distribution of the local neighborhood is invariant across nodes. Inspired by earlier results for uncontrolled dynamics, we have proposed a strategy to lift the controlled process into trajectory space. This involves using the second-order Markov random field (MRF) property to recover a Markov structure at the root and its neighbors

Planned Work
Next, we aim to:

• Rigorously prove that the trajectory process forms a second-order MRF under shared control policies.
• Use this to demonstrate that the process over the root and its neighbors is Markovian in the lifted (trajectory-valued) state space.
• Formulate a Bellman-type recursion on this lifted space to characterize the optimal control.
• Analyze convergence of optimal value functions and policies from the finite-agent system to the infinite-tree limit.
• Extend the formulation to limits of more general sparse graphs, such as Unimodular Galton–Watson trees.