A Novel Multi-Agent Reinforcement Learning Method Under Submodular Trajectory Rewards

Multi-agent reinforcement learning (MARL) faces optimization challenges in cooperative tasks due to non-additive rewards. A recent paper proposes using submodular curvature to control history dependence and designs a greedy algorithm that balances theoretical guarantees with computational efficiency.

Problem Background: Non-Additive Rewards Lead to Exponential Complexity

In multi-agent systems, when the reward function is monotone submodular with respect to the joint trajectory (i.e., there are diminishing marginal returns but always non-negative), the optimal policy often needs to depend on the entire history of all agents. This is because the non-additivity of submodular rewards means that the contributions among agents are coupled, and the value of the current action depends on the behavioral trajectories of all previous agents.

This history dependence causes exact optimization to grow exponentially in both time horizon and number of agents—for each agent, the policy space expands exponentially with history length, and joint multi-agent optimization is even worse. Traditional methods either sacrifice theoretical guarantees (e.g., heuristic approximations) or can only handle small-scale problems with extremely short horizons.

Submodular functions are real-valued functions defined on sets that satisfy the diminishing marginal returns property: for any sets A ⊆ B and element x ∉ B, we have f(A ∪ {x}) - f(A) ≥ f(B ∪ {x}) - f(B). In the context of this paper, "sets" correspond to joint trajectories (sequences of historical states and actions for each agent), and submodularity characterizes how the reward increment from adding a segment of trajectory decreases as more of the trajectory is already covered. Monotonicity requires that marginal returns are always non-negative. Maximizing submodular functions is a classic NP-hard problem, but greedy algorithms with approximation guarantees can be designed using parameters such as curvature. This paper transfers this combinatorial optimization framework to multi-agent reinforcement learning, using submodular curvature to constrain the policy's dependence on history length.

Core Innovation: Pre-window Curvature Quantifies Historical Influence

The paper introduces a key metric—pre-window curvature c_m—to quantify "the degree to which states visited more than m steps ago reduce the current marginal gain." Intuitively, if the influence of early states on current decisions decays rapidly, then each agent only needs to depend on the most recent m+1 states to approximate the optimal policy.

The smaller c_m is, the weaker the historical influence, and the more myopic the policy can be; the larger c_m is, the longer the history window that must be retained. This curvature parameter controls the error of history dependence within a provable range, providing a theoretical handle for subsequent algorithm design.

In the submodular maximization literature, total curvature is typically defined as 1 minus the minimum ratio of "marginal return of the full set to the marginal return of a single element," a global measure of how far the function deviates from additivity. In contrast, the pre-window curvature c_m in this paper is a more fine-grained localized measure: it only focuses on the proportion by which states more than m steps ago reduce the current marginal gain, rather than the global worst case. This design allows c_m to directly control the length of the policy truncation window—when c_m is small, the truncation error has an upper bound, allowing the algorithm to retain only the most recent m+1 states. Compared with total curvature, pre-window curvature better captures the intuition of "decaying influence of distant states" in reinforcement learning, and also provides an adjustable parameter for approximation ratio analysis.

Greedy Algorithm: Sequential Optimization of Local Policies

Leveraging decoupled dynamics (independent state transitions for each agent) and pre-window curvature, the authors propose a greedy algorithm: optimize each agent's local policy sequentially, with each policy depending only on its most recent m+1 states.

• Approximation guarantee: For a fixed m, the algorithm achieves an approximation ratio of (1-c_m)/(2-c_m) (ignoring estimation error), and this factor approaches 1/2 as c_m decreases.
• Computational efficiency: Computation time grows polynomially in the number of agents and the horizon, rather than exponentially.
• Theoretical compatibility: When the reward degenerates to time-additive, the classic 1/2 approximation factor is recovered; for the single-agent setting, the approximation factor is no worse than the known total curvature bound.

This result combines the concept of curvature from submodular optimization with multi-agent reinforcement learning, providing provable approximation quality while maintaining polynomial time complexity.

Decoupled dynamics assumes that the state transitions of each agent are independent of one another, i.e., each agent's next state is determined solely by its current state and its own action, and is not directly affected by other agents' states or actions. This assumption greatly simplifies the optimization of joint policies: coupling among agents is reflected only through the reward function (submodular reward), not through state evolution. Under decoupled dynamics, sequential optimization of local policies becomes possible—when optimizing the i-th agent, the policies of previously optimized agents are fixed, and only the marginal contribution to the reward needs to be considered. If state transitions are coupled, then a change in a single agent's policy would alter the state distributions of other agents, and the theoretical guarantees of sequential optimization would no longer directly hold, which is why the paper identifies this assumption as a limitation.

Application Example: Multi-Agent Traffic Monitoring

The paper models multi-agent traffic monitoring as an instance of this framework: multiple cameras (agents) collaborate to monitor a road network, and the reward function is submodular with respect to the joint trajectory—covering more areas yields diminishing marginal returns. Experimental evaluations show that the greedy algorithm is effective in traffic monitoring scenarios, validating the practical feasibility of the theoretical analysis.

Significance and Limitations

This work provides a path for cooperative multi-agent reinforcement learning that balances theoretical rigor and computational feasibility. The pre-window curvature c_m, as a computable measure of historical influence, provides a basis for policy truncation. However, estimation error in c_m affects practical performance, and the algorithm assumes decoupled dynamics—how to extend it to scenarios with coupled agent state transitions remains an open problem.

Overall, this study demonstrates the potential of submodular optimization tools in MARL, offering a new theoretical perspective and a practical algorithm for handling cooperative tasks with non-additive rewards.

One-line Summary

Using submodular curvature to control history dependence, a polynomial-time greedy algorithm is designed to solve cooperative multi-agent reinforcement learning.

Paragraph Summary

This paper addresses the problem in cooperative multi-agent reinforcement learning where submodular trajectory rewards cause the optimal policy to depend on the entire history and exact optimization to be exponentially complex. It proposes pre-window curvature c_m to quantify the degree to which early states reduce the current marginal gain. Based on the decoupled dynamics assumption, the authors design a greedy algorithm that sequentially optimizes each agent's local policy, with each policy depending only on the most recent m+1 states. Theoretical analysis shows that the algorithm achieves an approximation ratio of (1-c_m)/(2-c_m), and computation time grows polynomially in the number of agents and the horizon; when the reward degenerates to time-additive, the classic 1/2 approximation factor is recovered. Experiments on multi-agent traffic monitoring validate the practical effectiveness of the algorithm.