In traditional reinforcement learning (RL), the learner aims to solve a single objective optimization problem: find the policy that maximizes expected reward. However, in many real-world settings, it is important to optimize over multiple objectives simultaneously. For example, when we are interested in fairness, states might have feature annotations corresponding to multiple (intersecting) demographic groups to whom reward accrues, and our goal might be to maximize the reward of the group receiving the minimal reward. In this work, we consider a multi-objective optimization problem in which each objective is defined by a state-based reweighting of a single scalar reward function. This generalizes the problem of maximizing the reward of the minimum reward group. We provide oracle-efficient algorithms to solve these multi-objective RL problems even when the number of objectives is very large --- for tabular MDPs, as well as for large MDPs when the group functions have additional structure. The contribution of this paper is that we are able to solve this class of multi-objective RL problems with a possibly exponentially large class of constraints over intersecting groups in both tabular and large state space MDPs in an oracle-efficient manner. Finally, we experimentally validate our theoretical results and demonstrate applications on a preferential attachment graph MDP.

There are many decision-making problems in the real-world where multiple different demographic groups are affected by the outcome (i.e. disaster relief). Therefore, it is vital to ensure that when decision-making models are deployed to the real-world they are fair to the people they are meant to serve. In particular, one such challenge faced by models that aim to be fair is that of fairness gerrymandering, where models can be marginally fair over some sets of attributes, but systematically unfair to certain subgroups of the population. Therefore it is important to have models that are fair with respect to a sufficiently rich class of subgroups (intersectional fairness). In this paper, we address this problem by introducing a set of Reinforcement Learning algorithms that are able to provide certain types of fairness guarantees to a very large number of groups. We do this by formulating a zero-sum game between a learner that is trying to learn various policies or decision-making rules and a regulator who is choosing subgroups which loosely speaking are treated the least fairly. This approach enables us to extend Reinforcement Learning algorithms to settings where we want to ensure fairness to a large number of groups and we hope that some of this toolkit will be used beyond for other classes of problems where there are multiple objectives to consider.