mlsanityData to 7 Oct 2026

Reward is enough for convex MDPs

arXiv 2106.00661 ↗First posted 1 Jun 2021cs.AI cs.LG stat.MLcited by 82

Not on the map. Why?

Abstract (arXiv)

Maximising a cumulative reward function that is Markov and stationary, i.e., defined over state-action pairs and independent of time, is sufficient to capture many kinds of goals in a Markov decision process (MDP). However, not all goals can be captured in this manner. In this paper we study convex MDPs in which goals are expressed as convex functions of the stationary distribution and show that they cannot be formulated using stationary reward functions. Convex MDPs generalize the standard reinforcement learning (RL) problem formulation to a larger framework that includes many supervised and unsupervised RL problems, such as apprenticeship learning, constrained MDPs, and so-called `pure exploration'. Our approach is to reformulate the convex MDP problem as a min-max game involving policy and cost (negative reward) `players', using Fenchel duality. We propose a meta-algorithm for solving this problem and show that it unifies many existing algorithms in the literature.

Key facts. Cited by 82 papers in the map (data through 7 Oct 2026). Builds on 45 of its 84 references that are in the map. First posted on arXiv 1 Jun 2021.

Builds on

45 of 84 references.

References · 45

  1. 2015Trust Region Policy Optimizationcited by 2,503
  2. 2016Generative Adversarial Imitation Learningcited by 1,576
  3. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 866
  4. 2019Introduction to Online Convex Optimizationcited by 793
  5. 2018Diversity is All You Need: Learning Skills without a Reward Functioncited by 734
  6. 2016Deep Exploration via Bootstrapped DQNcited by 518
  7. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  8. 2018Reward Constrained Policy Optimizationcited by 397
  9. 2018Maximum a Posteriori Policy Optimisationcited by 318
  10. 2019A Theory of Regularized Markov Decision Processescited by 279
  11. 2016Variational Intrinsic Controlcited by 262
  12. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
33 more
  1. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  2. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  3. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  4. 2019Efficient Exploration via State Marginal Matchingcited by 186
  5. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  6. 2020Exploration-Exploitation in Constrained MDPscited by 146
  7. 2019Behaviour Suite for Reinforcement Learningcited by 129
  8. 2017Stochastic Neural Networks for Hierarchical Reinforcement Learningcited by 124
  9. 2018Variational Option Discovery Algorithmscited by 121
  10. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  11. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  12. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  13. 2020Mirror Descent Policy Optimizationcited by 102
  14. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  15. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  16. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  17. 2020Adaptive Reward-Free Explorationcited by 77
  18. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 76
  19. 2019Wasserstein Adversarial Imitation Learningcited by 59
  20. 2019Reinforcement Learning with Convex Constraintscited by 57
  21. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  22. 2020Behavior Priors for Efficient Reinforcement Learningcited by 40
  23. 2014Fast Algorithms for Online Stochastic Convex Programmingcited by 36
  24. 2018Variational Bayesian Reinforcement Learning with Regret Boundscited by 31
  25. 2020Making Sense of Reinforcement Learning and Probabilistic Inferencecited by 30
  26. 2021Online Apprenticeship Learningcited by 28
  27. 2021Discovering a set of policies for the worst case rewardcited by 21
  28. 2020Balancing Constraints and Rewards with Meta-Gradient D4PGcited by 18
  29. 2019Apprenticeship Learning via Frank-Wolfecited by 13
  30. 2020Wasserstein Distance guided Adversarial Imitation Learning with Reward Shape Explorationcited by 13
  31. 2019Inverse Reinforcement Learning in Contextual MDPscited by 12
  32. 2017Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularitiescited by 11
  33. 2019Unknown mixing times in apprenticeship and reinforcement learningcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 12; 2023: 21; 2024: 21; 2025: 12; 2026: 13.

82 papers.

Sort:

By area:

  1. 2023Generative Flow Networks as Entropy-Regularized RLcited by 60
  2. 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 54
  3. 2022Discovering Policies with DOMiNO: Diversity Optimization Maintaining Near Optimalitycited by 35
  4. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  5. 2023Fast Rates for Maximum Entropy Explorationcited by 32
  6. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 29
  7. 2022Simplifying Model-based RL: Learning Representations, Latent-space Models, and Policies with One Objectivecited by 28
  8. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  9. 2023Submodular Reinforcement Learningcited by 23
  10. 2022Your Policy Regularizer is Secretly an Adversarycited by 21
  11. 2022Active Exploration via Experiment Design in Markov Chainscited by 19
  12. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 19
38 more
  1. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  2. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  3. 2023Optimal Exploration for Model-Based RL in Nonlinear Systemscited by 17
  4. 2023Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilitiescited by 15
  5. 2023Diversifying AI: Towards Creative Chess with AlphaZerocited by 15
  6. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methodscited by 15
  7. 2025Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuningcited by 15
  8. 2021On Covariate Shift of Latent Confounders in Imitation and Reinforcement Learningcited by 14
  9. 2024Three Dogmas of Reinforcement Learningcited by 14
  10. 2022Versatile Skill Control via Self-supervised Adversarial Imitation of Unlabeled Mixed Motionscited by 13
  11. 2022Geometry and convergence of natural policy gradient methodscited by 12
  12. 2023A Coupled Flow Approach to Imitation Learningcited by 12
  13. 2024Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inferencecited by 12
  14. 2024Optimizing Backward Policies in GFlowNets via Trajectory Likelihood Maximizationcited by 12
  15. 2023Probabilistic Inference in Reinforcement Learning Done Rightcited by 11
  16. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  17. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  18. 2021The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPscited by 9
  19. 2024On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Taskscited by 9
  20. 2022Towards Painless Policy Optimization for Constrained MDPscited by 8
  21. 2023Inverse Reinforcement Learning with the Average Reward Criterioncited by 8
  22. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  23. 2024Policy Aggregationcited by 8
  24. 2025The impact of intrinsic rewards on exploration in Reinforcement Learningcited by 8
  25. 2023Learning Diverse Skills for Local Navigation under Multi-constraint Optimalitycited by 7
  26. 2024Transition Constrained Bayesian Optimization via Markov Decision Processescited by 7
  27. 2024Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPscited by 7
  28. 2022Improved Policy Optimization for Online Imitation Learningcited by 6
  29. 2022Policy Gradient for Reinforcement Learning with General Utilitiescited by 6
  30. 2024The Limits of Pure Exploration in POMDPs: When the Observation Entropy is Enoughcited by 6
  31. 2024Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstractioncited by 6
  32. 2024On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learningcited by 6
  33. 2026Efficient Tail-Aware Generative Optimization via Flow Model Fine-Tuningcited by 6
  34. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5
  35. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  36. 2023Offline Diversity Maximization Under Imitation Constraintscited by 4
  37. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  38. 2024Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysiscited by 4

50 most cited of 82 All 82 (JSON)