# Discovering a set of policies for the worst case reward

arXiv: https://arxiv.org/abs/2102.04323 · HTML: https://mlsanity.com/paper/2102.04323/

## Key facts

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

## Builds on (most cited first, 12 of 12)

- [DeepMind Control Suite](https://mlsanity.com/paper/1801.00690/) (2018)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Successor Features for Transfer in Reinforcement Learning](https://mlsanity.com/paper/1606.05312/) (2016)
- [Variational Intrinsic Control](https://mlsanity.com/paper/1611.07507/) (2016)
- [Fast Task Inference with Variational Intrinsic Successor Features](https://mlsanity.com/paper/1906.05030/) (2019)
- [Transfer in Deep Reinforcement Learning Using Successor Features and Generalised Policy Improvement](https://mlsanity.com/paper/1901.10964/) (2019)
- [A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization](https://mlsanity.com/paper/1301.4666/) (2013)
- [Apprenticeship Learning via Frank-Wolfe](https://mlsanity.com/paper/1911.01679/) (2019)
- [Disentangled Cumulants Help Successor Representations Transfer to New Tasks](https://mlsanity.com/paper/1911.10866/) (2019)
- [Unknown mixing times in apprenticeship and reinforcement learning](https://mlsanity.com/paper/1905.09704/) (2019)
- [Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local Policies](https://mlsanity.com/paper/1902.10140/) (2019)

## Built on by (most cited first, 21 of 21)

- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [CIC: Contrastive Intrinsic Control for Unsupervised Skill Discovery](https://mlsanity.com/paper/2202.00161/) (2022)
- [Discovering Policies with DOMiNO: Diversity Optimization Maintaining Near Optimality](https://mlsanity.com/paper/2205.13521/) (2022)
- [Neuroevolution is a Competitive Alternative to Reinforcement Learning for Skill Discovery](https://mlsanity.com/paper/2210.03516/) (2022)
- [Optimistic Linear Support and Successor Features as a Basis for Optimal Policy Transfer](https://mlsanity.com/paper/2206.11326/) (2022)
- [Discovering Diverse Nearly Optimal Policies with Successor Features](https://mlsanity.com/paper/2106.00669/) (2021)
- [Robust Policy Learning over Multiple Uncertainty Sets](https://mlsanity.com/paper/2202.07013/) (2022)
- [Diversifying AI: Towards Creative Chess with AlphaZero](https://mlsanity.com/paper/2308.09175/) (2023)
- [A First-Occupancy Representation for Reinforcement Learning](https://mlsanity.com/paper/2109.13863/) (2021)
- [Constructing a Good Behavior Basis for Transfer using Generalized Policy Updates](https://mlsanity.com/paper/2112.15025/) (2021)
- [Generalised Policy Improvement with Geometric Policy Composition](https://mlsanity.com/paper/2206.08736/) (2022)
- [Beyond Worst-case Attacks: Robust RL with Adaptive Defense via Non-dominated Policies](https://mlsanity.com/paper/2402.12673/) (2024)
- [Reward-Free Policy Space Compression for Reinforcement Learning](https://mlsanity.com/paper/2202.11079/) (2022)
- [Planning with a Learned Policy Basis to Optimally Solve Complex Tasks](https://mlsanity.com/paper/2403.15301/) (2024)
- [C-MORL: Multi-Objective Reinforcement Learning through Efficient Discovery of Pareto Front](https://mlsanity.com/paper/2410.02236/) (2024)
- [Learning to Be Cautious](https://mlsanity.com/paper/2110.15907/) (2021)
- [Robust Reinforcement Learning through Efficient Adversarial Herding](https://mlsanity.com/paper/2306.07408/) (2023)
- [Constructing an Optimal Behavior Basis for the Option Keyboard](https://mlsanity.com/paper/2505.00787/) (2025)
- [Diverse Policy Optimization for Structured Action Space](https://mlsanity.com/paper/2302.11917/) (2023)
- [The Laplacian Keyboard: Beyond the Linear Span](https://mlsanity.com/paper/2602.07730/) (2026)
- [Minimum Description Length Control](https://mlsanity.com/paper/2207.08258/) (2022)

## 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.