mlsanityData to 7 Oct 2026

Discovering a set of policies for the worst case reward

arXiv 2102.04323 ↗First posted 8 Feb 2021cs.AI cs.LGcited by 21

Not on the map. Why?

Abstract (arXiv)

We study the problem of how to construct a set of policies that can be composed together to solve a collection of reinforcement learning tasks. Each task is a different reward function defined as a linear combination of known features. We consider a specific class of policy compositions which we call set improving policies (SIPs): given a set of policies and a set of tasks, a SIP is any composition of the former whose performance is at least as good as that of its constituents across all the tasks. We focus on the most conservative instantiation of SIPs, set-max policies (SMPs), so our analysis extends to any SIP. This includes known policy-composition operators like generalized policy improvement. Our main contribution is a policy iteration algorithm that builds a set of policies in order to maximize the worst-case performance of the resulting SMP on the set of tasks. The algorithm works by successively adding new policies to the set. We show that the worst-case performance of the resulting SMP strictly improves at each iteration, and the algorithm only stops when there does not exist a policy that leads to improved performance. We empirically evaluate our algorithm on a grid world and also on a set of domains from the DeepMind control suite. We confirm our theoretical results regarding the monotonically improving performance of our algorithm. Interestingly, we also show empirically that the sets of policies computed by the algorithm are diverse, leading to different trajectories in the grid world and very distinct locomotion skills in the control suite.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 12 of its 32 references that are in the map. First posted on arXiv 8 Feb 2021.

Builds on

12 of 32 references.

References · 12

  1. 2018DeepMind Control Suitecited by 935
  2. 2018Diversity is All You Need: Learning Skills without a Reward Functioncited by 734
  3. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 633
  4. 2016Successor Features for Transfer in Reinforcement Learningcited by 331
  5. 2016Variational Intrinsic Controlcited by 262
  6. 2019Fast Task Inference with Variational Intrinsic Successor Featurescited by 131
  7. 2019Transfer in Deep Reinforcement Learning Using Successor Features and Generalised Policy Improvementcited by 88
  8. 2013A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimizationcited by 18
  9. 2019Apprenticeship Learning via Frank-Wolfecited by 13
  10. 2019Disentangled Cumulants Help Successor Representations Transfer to New Taskscited by 11
  11. 2019Unknown mixing times in apprenticeship and reinforcement learningcited by 7
  12. 2019Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local Policiescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 8; 2023: 3; 2024: 3; 2025: 1; 2026: 1.

21 papers.

Sort:

By area:

  1. 2021Reward is enough for convex MDPscited by 82
  2. 2022CIC: Contrastive Intrinsic Control for Unsupervised Skill Discoverycited by 66
  3. 2022Discovering Policies with DOMiNO: Diversity Optimization Maintaining Near Optimalitycited by 35
  4. 2022Neuroevolution is a Competitive Alternative to Reinforcement Learning for Skill Discoverycited by 23
  5. 2022Optimistic Linear Support and Successor Features as a Basis for Optimal Policy Transfercited by 22
  6. 2021Discovering Diverse Nearly Optimal Policies with Successor Featurescited by 20
  7. 2022Robust Policy Learning over Multiple Uncertainty Setscited by 16
  8. 2023Diversifying AI: Towards Creative Chess with AlphaZerocited by 15
  9. 2021A First-Occupancy Representation for Reinforcement Learningcited by 14
  10. 2021Constructing a Good Behavior Basis for Transfer using Generalized Policy Updatescited by 14
  11. 2022Generalised Policy Improvement with Geometric Policy Compositioncited by 11
  12. 2024Beyond Worst-case Attacks: Robust RL with Adaptive Defense via Non-dominated Policiescited by 8
9 more
  1. 2022Reward-Free Policy Space Compression for Reinforcement Learningcited by 6
  2. 2024Planning with a Learned Policy Basis to Optimally Solve Complex Taskscited by 4
  3. 2024C-MORL: Multi-Objective Reinforcement Learning through Efficient Discovery of Pareto Frontcited by 4
  4. 2021Learning to Be Cautiouscited by 3
  5. 2023Robust Reinforcement Learning through Efficient Adversarial Herdingcited by 2
  6. 2025Constructing an Optimal Behavior Basis for the Option Keyboardcited by 2
  7. 2023Diverse Policy Optimization for Structured Action Spacecited by 1
  8. 2022Minimum Description Length Controlcited by 0
  9. 2026The Laplacian Keyboard: Beyond the Linear Spancited by 0