Research map / Reinforcement learning / Policy gradient and actor-critic

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

ICML 2024 · Reinforcement learning › Policy gradient and actor-critic · approach: Policy gradients for special settings · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Global RL, where rewards are set functions over trajectories, and proposes submodular/supermodular semi-gradient meta-algorithms (GTO, GPO) that reduce each step to a classic MDP with curvature-based approximation guarantees.

Problem

Reinforcement learning with non-additive, trajectory-level rewards (capturing negative/positive interactions among states) is intractable in general; existing convex RL lacks efficient approximate algorithms for finite-sample objectives.

Approach

Treat trajectory rewards as set functions over state-time pairs, decompose them into submodular and supermodular parts, and iteratively optimize tight modular lower bounds (discrete semi-gradients), so each iteration is a standard MDP planning problem with curvature-dependent guarantees.

Key results

• On D-optimal experimental design, GTO performs significantly better than the optimal policy for the modularized objective and competitively with SubPO, and nearly optimally relative to the optimal non-Markovian policy.
• For diverse synergies (BP reward) in a stochastic environment, GPO performs significantly better than the optimal policy for the modular surrogate; in deterministic settings GTO matches the optimal non-Markovian policy.
• Theory gives first-iterate guarantees: R(pi_1) <= k_F J* for submodular rewards, and a hardness result shows no poly-time algorithm beats 1-k^G+eps for BP rewards unless P=NP.

Surprising findings

• Maximizing a fully-curved supermodular component can perform arbitrarily poorly, yet GPO still performs well on the BP diverse-synergy task.
• Greedy submodular lower bounds outperform the standard lower bound on certain horizons.

Limitations

• GPO with stochastic dynamics does not guarantee monotonic improvement and needs many sampled trajectories.
• Known transition model assumed; extension to unknown dynamics left as future work.
• Guarantees are first-iterate and depend on curvature; fully-curved supermodular rewards have poor worst-case bounds.

Experimental setup

Benchmarks: grid environment with 400 states (D-optimal experimental design, diverse synergies, safe state coverage)

Metrics: objective value under global reward non-additive suboptimality gap

Baselines: SubPO optimal policy for modular objective optimal non-Markovian policy

Builds on: Convex RL SubPO submodular function maximization BP function maximization

Closest papers by meaning

• Submodular Reinforcement Learning (ICLR 2024 · similarity 0.92)
• On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning (NeurIPS 2025 · similarity 0.89)
• To the Max: Reinventing Reward in Reinforcement Learning (ICML 2024 · similarity 0.89)
• Beyond Optimism: Exploration With Partially Observable Rewards (NeurIPS 2024 · similarity 0.88)
• Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL (NeurIPS 2025 · similarity 0.87)
• Inverting the Bellman Equation: From $Q$-Values to World Models (NeurIPS 2026 · similarity 0.87)