Abstract
In Reinforcement Learning (RL), an agent interacts with an environment to maximize a reward generated from an unknown distribution. Traditional RL frameworks assume that rewards are additive over time. However, many real-world applications—such as path planning and coverage control—exhibit the "law of diminishing returns," where the marginal utility of an action decreases as more actions are taken. This property is formally defined as submodularity. In this paper, we study a variant of the RL problem where the reward function is submodular. We propose Submodularity Graph-based Policy Optimization (SGPO), a pruned graph-based approach that provides a provably approximate solution within feasible computation time. Our analysis covers the algorithm's time and space complexity as well as its performance guarantees. Experimental results on benchmark environments demonstrate that SGPO achieves higher rewards and greater stability compared to existing baseline methods.
Introduction
Standard Reinforcement Learning (RL) algorithms rely on the assumption that the total reward of a trajectory is the sum of individual step-wise rewards. This additive structure allows for the application of Bellman’s optimality principle, enabling efficient dynamic programming and temporal difference learning. However, this assumption fails in scenarios like informative path planning, document summarization, or area coverage, where the value of a state depends on the history of states already visited.
In these contexts, the reward function is submodular. Because the reward depends on the entire trajectory rather than just the current state-action pair, the state space effectively explodes, making standard RL approaches computationally intractable. While recent "Submodular RL" methods have attempted to address this, they often struggle with high-dimensional spaces due to the intensive computational cost of calculating marginal gains. SGPO aims to bridge this gap by introducing a scalable, graph-based sparsification technique.
Methodology: Submodularity Graph-based Policy Optimization (SGPO)
The core innovation of SGPO lies in its ability to manage the complexity of the state space through a pruned submodularity graph. The algorithm follows a four-step process:
- Submodularity Graph Construction: The algorithm builds a weighted directed graph where nodes represent states. The edge weights represent the "divergence" between states, measuring the unique information or reward a state provides relative to others in the trajectory.
- Graph Pruning (Sparsification): To maintain computational efficiency, SGPO iteratively samples a subset of states and prunes those with low divergence weights. This pruning ensures that the algorithm only focuses on the most "informative" states, significantly reducing the number of marginal gain computations required.
- Policy Gradient Estimation: The authors derive a specific gradient estimator (Theorem 3) tailored for submodular rewards. This allows the policy—represented by a neural network—to be updated using regularized gradient ascent.
- Complexity Management: By utilizing the pruned graph, the algorithm maintains a logarithmic iteration complexity ($O(\log n)$), making it significantly more scalable than exhaustive greedy search methods.
Theoretical Insights
The paper provides a rigorous theoretical foundation for the necessity of approximation heuristics:
- Hardness of Submodular RL: Theorem 2 proves that Submodular RL is fundamentally hard. Unless $NP \subseteq ZTIME(n^{polylog(n)})$, no polynomial-time algorithm can guarantee better than a logarithmic approximation. This justifies the use of the proposed graph-pruning heuristic.
- Variance Reduction: The "Divergence of a state" metric identifies redundant states. By pruning these, the algorithm reduces noise during training. Experiments confirmed that SGPO’s loss curves were smoother than baselines, suggesting that focusing on high-divergence states acts as a form of variance reduction.
Experimental Evaluation
SGPO was evaluated across four environments featuring both continuous and discrete state-action spaces:
- MuJoCo Ant (Continuous): A quadruped robot task where the objective is to maximize the unique 2D area covered. SGPO achieved a coverage of 2636 units, outperforming the SubPO baseline (2612 units).
- Car Racing (Continuous): A high-dimensional task where a car must complete a lap. SGPO demonstrated faster learning, requiring fewer horizon steps to complete the lap as training progressed.
- Entropy-Based Environment (Discrete): This environment focuses on exploration using entropy as the objective. SGPO achieved an objective value of 237.8, a significant improvement over SubPO’s 171.2.
- Graph-Based Environment (Discrete): Evaluated in both M Mode (unique node weights) and SRL Mode (repeated coverage), SGPO consistently outperformed baselines in reward accumulation and convergence stability.
Conclusion and Future Work
SGPO offers a scalable solution for RL problems with non-additive, submodular rewards. By leveraging a pruned submodularity graph, the method identifies and prioritizes informative states, leading to superior performance and training stability compared to state-of-the-art baselines.
While SGPO reduces computational overhead, the theoretical complexity ($O(N \cdot n^4 s^2 m^2)$) remains a challenge for massive-scale industrial applications. Future research may focus on further optimizing these bounds or extending the framework to broader classes of non-additive reward functions beyond submodularity.
Summary updated