Reward is enough for convex MDPs
arXiv:2106.00661
Abstract
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.
References in corpus (29)
- Trust Region Policy Optimization
- Generative Adversarial Imitation Learning
- Reward Constrained Policy Optimization
- (More) Efficient Reinforcement Learning via Posterior Sampling
- Maximum a Posteriori Policy Optimisation
- Variational Intrinsic Control
- DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections
- Provably Efficient Maximum Entropy Exploration
- Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
- A Theory of Regularized Markov Decision Processes
- Efficient Exploration via State Marginal Matching
- Variational Option Discovery Algorithms
- Reinforcement Learning with Convex Constraints
- Online Convex Optimization in Adversarial Markov Decision Processes
- Variational Policy Gradient Method for Reinforcement Learning with General Utilities
- Wasserstein Adversarial Imitation Learning
- Behaviour Suite for Reinforcement Learning
- Exploration-Exploitation in Constrained MDPs
- Mirror Descent Policy Optimization
- Off-Policy Evaluation via the Regularized Lagrangian
- Efficiently Solving MDPs with Stochastic Mirror Descent
- Wasserstein Distance guided Adversarial Imitation Learning with Reward Shape Exploration
- Behavior Priors for Efficient Reinforcement Learning
- Variational Bayesian Reinforcement Learning with Regret Bounds
- Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
- Making Sense of Reinforcement Learning and Probabilistic Inference
- Optimistic Policy Optimization with Bandit Feedback
- Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint
- Towards Tight Bounds on the Sample Complexity of Average-reward MDPs