Distributed Policy Learning for Online Submodular Maximization over Time-Varying Directed Graphs

This paper investigates the online submodular maximization problem for multi-agent systems over time-varying directed communication networks. At each round, multiple agents collaboratively maximize a time-varying monotone submodular utility function using only local information, and without prior knowledge of future objectives. This setting has wide applications including multi-robot target tracking, client selection in federated learning, and distributed information fusion in the dynamic environment. Existing approaches, such as OSG and MA-OSMA, typically rely on fixed and connected graphs, which limits their applicability to networks with asymmetric communication and intermittent connectivity arising from packet losses and communication link failures. To address these limitations, we propose a Push-Sum Online Surrogate Mirror Ascent (POSMA) algorithm which utilizes a multilinear extension to transform the original discrete problem into a continuous optimization problem. A push-sum mechanism is further incorporated to compensate for the aggregation bias. Under the B-strongly connected communication, we theoretically confirm that the algorithm achieves an approximation ratio of $\frac{1-e^{-\bar{c}}}{\bar{c}}$ with an average dynamic regret, where $\bar{c}$ bounds the curvature of all objective functions. Moreover, we quantitatively characterize how network connectivity degradation slows the agreement rate and therefore increases online submodular regret by establishing the regret bound $\mathcal{O}\left(\frac{1}{\sqrt{\lambda (1-\lambda )}}\sqrt{\frac{1+C_T}{T}}\right)$, where $C_T$ represents the cumulative variation of the optimal action sets, and $\lambda ={\left(1-\frac{1}{N^{NB}}\right)}^{1/B}$ characterizes the rate of agreement related to the jointly connected bound $B$. Finally, we conduct simulations of multi-target tracking to demonstrate the effectiveness of the proposed algorithm and show the benefits compared with the baseline algorithm under fixed and time-varying communication graphs.