# Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods

arXiv: https://arxiv.org/abs/2407.09905 · HTML: https://mlsanity.com/paper/2407.09905/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 27 of its 53 references that are in the map.
- First posted on arXiv 13 Jul 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 27 of 27)

- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [A Divergence Minimization Perspective on Imitation Learning Methods](https://mlsanity.com/paper/1911.02256/) (2019)
- [Efficient Exploration via State Marginal Matching](https://mlsanity.com/paper/1906.05274/) (2019)
- [Behavior From the Void: Unsupervised Active Pre-Training](https://mlsanity.com/paper/2103.04551/) (2021)
- [Explore, Discover and Learn: Unsupervised Discovery of State-Covering Skills](https://mlsanity.com/paper/2002.03647/) (2020)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [The Importance of Non-Markovianity in Maximum State Entropy Exploration](https://mlsanity.com/paper/2202.03060/) (2022)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [Challenging Common Assumptions in Convex Reinforcement Learning](https://mlsanity.com/paper/2202.01511/) (2022)
- [Active Exploration in Markov Decision Processes](https://mlsanity.com/paper/1902.11199/) (2019)
- [Density Constrained Reinforcement Learning](https://mlsanity.com/paper/2106.12764/) (2021)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Wasserstein Unsupervised Reinforcement Learning](https://mlsanity.com/paper/2110.07940/) (2021)
- [Active Model Estimation in Markov Decision Processes](https://mlsanity.com/paper/2003.03297/) (2020)
- [Active Exploration via Experiment Design in Markov Chains](https://mlsanity.com/paper/2206.14332/) (2022)
- [Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space](https://mlsanity.com/paper/2306.01854/) (2023)
- [Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications](https://mlsanity.com/paper/1408.2051/) (2014)
- [Curiosity in exploring chemical space: Intrinsic rewards for deep molecular reinforcement learning](https://mlsanity.com/paper/2012.11293/) (2020)
- [Near-Optimal Multi-Agent Learning for Safe Coverage Control](https://mlsanity.com/paper/2210.06380/) (2022)
- [Polyhedral aspects of Submodularity, Convexity and Concavity](https://mlsanity.com/paper/1506.07329/) (2015)
- [Fast Semidifferential-based Submodular Function Optimization](https://mlsanity.com/paper/1308.1006/) (2013)
- [Planning with Submodular Objective Functions](https://mlsanity.com/paper/2010.11863/) (2020)

## Built on by (most cited first, 15 of 15)

- [Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuning](https://mlsanity.com/paper/2511.22640/) (2025)
- [Provable Maximum Entropy Manifold Exploration via Diffusion Models](https://mlsanity.com/paper/2506.15385/) (2025)
- [Efficient Tail-Aware Generative Optimization via Flow Model Fine-Tuning](https://mlsanity.com/paper/2602.16796/) (2026)
- [Verifier-Constrained Flow Expansion for Discovery Beyond the Data](https://mlsanity.com/paper/2602.15984/) (2026)
- [On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning](https://mlsanity.com/paper/2410.04108/) (2024)
- [Efficient Reinforcement Learning in Probabilistic Reward Machines](https://mlsanity.com/paper/2408.10381/) (2024)
- [Zero-Shot Offline Imitation Learning via Optimal Transport](https://mlsanity.com/paper/2410.08751/) (2024)
- [Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.16600/) (2024)
- [Soft Forward-Backward Representations for Zero-shot Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2602.06769/) (2026)
- [A Unified Density Operator View of Flow Control and Merging](https://mlsanity.com/paper/2602.08012/) (2026)
- [From Relative Entropy to Minimax: A Unified Framework for Coverage in MDPs](https://mlsanity.com/paper/2601.11890/) (2026)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [kappa-Explorer: A Unified Framework for Active Model Estimation in MDPs](https://mlsanity.com/paper/2602.20404/) (2026)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)
- [Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering](https://mlsanity.com/paper/2609.15539/) (2026)

## Abstract (arXiv)

In classic Reinforcement Learning (RL), the agent maximizes an additive objective of the visited states, e.g., a value function. Unfortunately, objectives of this type cannot model many real-world applications such as experiment design, exploration, imitation learning, and risk-averse RL to name a few. This is due to the fact that additive objectives disregard interactions between states that are crucial for certain tasks. To tackle this problem, we introduce Global RL (GRL), where rewards are globally defined over trajectories instead of locally over states. Global rewards can capture negative interactions among states, e.g., in exploration, via submodularity, positive interactions, e.g., synergetic effects, via supermodularity, while mixed interactions via combinations of them. By exploiting ideas from submodular optimization, we propose a novel algorithmic scheme that converts any GRL problem to a sequence of classic RL problems and solves it efficiently with curvature-dependent approximation guarantees. We also provide hardness of approximation results and empirically demonstrate the effectiveness of our method on several GRL instances.