Research map / Reinforcement learning / MDPs and planning
Submodular Reinforcement Learning
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 submodular RL, where rewards are monotone submodular set functions of the visited states, and proposes SubPO, a policy gradient method that greedily maximizes marginal gains.
Problem
Standard RL assumes additive, trajectory-independent rewards, which cannot model diminishing returns from revisiting similar states (coverage, experiment design, informative path planning). Optimizing general submodular history-dependent rewards is intractable in general.
Approach
Model rewards as a monotone submodular set function of the visited (state, time) pairs and optimize them with a policy gradient whose per-step learning signal is the marginal gain of each new state, akin to the greedy algorithm; under an epsilon-bandit MDP the objective is DR-submodular, and bounded curvature gives a 1-c guarantee.
Key results
- Proves a log-factor inapproximability result for submodular RL, even for deterministic MDPs, via reduction from submodular orienteering.
- Under epsilon-bandit MDPs with horizon-dependent policies, J(pi) is monotone DR-submodular, giving a (1-1/e) approximation target for projected gradient methods.
- In experiments, SubPO (Markovian and non-Markovian variants) outperforms modular RL on coverage, item collection, and experiment design, and scales to MuJoCo Ant and car racing.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| maximize marginal gains with SubPOm instead of additive rewards with modular RL | Gorilla nest coverage · Informative path planning | normalized J(π) | Helped |
| use a Markovian policy instead of a history-dependent policy | SubPO · Informative path planning | normalized J(π) | No clear effect |
| maximize marginal gains with SubPOm instead of additive rewards with modular RL | Bayesian D-experimental design · Bayesian D-experimental design | normalized J(π) | Helped |
| use a Markovian policy instead of a history-dependent policy | SubPO · Bayesian D-experimental design | normalized J(π) | No clear effect |
| use a history-dependent policy instead of a Markovian policy | SubPO · Item collection | normalized J(π) | Helped |
| use a history-dependent policy instead of a Markovian policy | SubPO · Building exploration | coverage | Helped |
| maximize marginal gains with SubPO instead of additive rewards with modular RL | Car racing policy · Car racing | normalized progress | Helped |
| maximize marginal gains with SubPO instead of additive rewards with modular RL | MuJoCo Ant policy · MuJoCo Ant | normalized explored area | Helped |
Surprising findings
- Even with a Markovian (time-augmented) state, greedily maximizing marginal gains matches the non-Markovian policy performance in many environments.
Limitations
- General submodular RL is inapproximable beyond log factors, so the constant-factor guarantees rely on restrictive assumptions (epsilon-bandit MDPs or bounded curvature).
- Markovian state representations are insufficient in item collection and building exploration, requiring history-dependent policies.
Experimental setup
Metrics: normalized objective J(pi)
Baselines: modular RL (MRL)
Builds on: REINFORCE submodular orienteering DR-submodular maximization generalized advantage estimation
Closest papers by meaning
- Global Reinforcement Learning : Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods (ICML 2024 · similarity 0.92)
- Multi-Agent Reinforcement Learning with Submodular Reward (ICML 2026 · similarity 0.89)
- Asymmetric REINFORCE for off-Policy Reinforcement Learning: Balancing positive and negative rewards (NeurIPS 2025 · similarity 0.88)
- To the Max: Reinventing Reward in Reinforcement Learning (ICML 2024 · similarity 0.88)
- ContraDiff: Planning Towards High Return States via Contrastive Learning (ICLR 2025 · similarity 0.87)
- Reinforcement Learning with Lookahead Information (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.