Intersectional Fairness in Reinforcement Learning with Large State and Constraint Spaces

Dear Reviewer Gqfm,

Thank you for your positive assessment of our work.

Empirical Scope As we highlight in Section 5 on Future Work, we completely agree that moving towards more realistic scenarios with these algorithms poses an interesting future direction for our work. However, the current manuscript is largely a theoretical contribution and we believe that moving to more complex oracle settings will come with its own challenges and open questions. These include studying the effects of potentially sub-optimal oracles in practice, which will likely warrant a different type of publication. Our experiments primarily aim to verify the effectiveness of our FairFictRL algorithm. This algorithm is easy to implement but it does not come with with polynomial-time guarantees. Thus, our experiments validate that this easy version of the algorithm might be a feasible alternative in practice.

Optimization Oracle Assumption Our optimization oracle assumption is mainly stating that we are able to do linear optimization efficiently in practice. Algorithms to achieve this exist in practice. For example, in the case of continuous space, interior point methods or barrier methods work well and in the case of conjunctions, integer linear programs and mixed integer programs, etc. work effectively in practice. For best response oracles one may hope to resort to deep reinforcement learning algorithms that may return policies close to optimal. We are happy to extend the discussion on this by adding text akin to the previous sentences to the paper.

Computational Complexity and Scaling Since we provide oracle efficient algorithms, the run time (which we bound in our lemmas) is the core component of our computational complexity. Our algorithms mainly make O(T) oracle calls total, comprising the majority of the computation within each round; the only other computation is the sampling of noise vectors of size $O(d)$ or $O(|S|)$ at each round for the Follow the Perturbed Leader base algorithms. We will update our paper to include a statement highlighting the computational complexity of our algorithms. Lemma $3.3$ shows that the computational complexity of our algorithm for tabular MDPs scales logarithmically in $|\mathcal{G}|$ and polynomially in $|S|$. Lemma $3.6$ shows that the computational complexity of our algorithm for continuous spaces and groups with separator structor scales with the size of the separator set $d$ and $\ln(|\mathcal{G}|)$. We believe that the impact of the number of groups on scaling to larger settings in practice would be negligible.

Baseline Methods We appreciate the question. We have not implemented any baselines in this setting and we are not aware of any baselines that would be suitable. We view the main claim of the experimental section as validating that our proposed FairFictRL algorithm works. We do not believe that the addition of baselines would strengthen this claim substantially.

Dear Reviewer zwEM,

Thank you for acknowledging the significant theoretical contribution of our work and the detailed feedback on our submission.

Individual Fairness The notion of fairness we consider represents a middle ground between fully statistical notions of fairness and fully individual notions. By considering a sufficiently rich set of subgroups (rather than just the $d$ individual attributes or all individuals), we are able to provide algorithms that are tractable even for large state spaces while having meaningful guarantees for more fine-grained portions of the population. We believe this to be a valuable step towards methods that deal with the great variety of preferences and characteristics that individuals can exhibit, reflecting the vast diversity found within human sub-populations.

Pareto Optimal Fairness This is a great point. You are correct in that the minimax optimization does not imply pareto optimality. However, what we can claim is that the minimax solution Pareto-dominates the solution that tries to equalize rewards across groups. We will clarify this in the text. We also do agree (as Figure 3 shows) that overall efficiency or optimality may be sacrificed when trying to optimize with fairness constraints in mind. This may unfortunately be unavoidable in many settings.

Empirical Scope As we highlight in Section 5, we completely agree that more realistic scenarios pose an interesting future direction. However, the current manuscript is largely a theoretical contribution and we believe that moving to more complex oracle settings will come with its own challenges and open questions. These include studying the effects of potentially sub-optimal oracles, which will likely warrant a different type of publication. Our experiments primarily aim to verify the effectiveness of our FairFictRL algorithm. This algorithm is easy to implement but it does not come with polynomial-time guarantees. Thus, our experiments validate that this algorithm is a feasible alternative in practice.

Baseline methods We appreciate the feedback on this. We view the main claim of the experimental section to be that our proposed FairFictRL algorithm is practical and we do not believe that the addition of baselines would strengthen this claim substantially.

Other Notions of Fairness This is a great point. We agree that other notions like leximin fairness are very interesting. In fact, an idea for future work might be to adapt our method to iteratively solve for leximin fairness as in [1]. However, even in this classification setting, leximin fairness is a very subtle and technically unstable concept. In addition, it can become computationally challenging when the number of groups is large as one may have to iterate over all groups. Instead, our method is able to handle a broad class of linear/convex fairness constraints or objectives and can be implemented efficiently. That being said, there are still many other interesting fairness notions that one could explore and we are excited about doing so in the future.

Group/Objective Scaling Our proposed method scales with the log of the number of groups as can be seen in Lemma $3.3$ for tabular MDPs and Lemma $3.6$ for large state spaces. This is one of the key strengths of our contribution as it allows us to handle exponentially many groups.

Approximate Lin-OPT Our optimization oracle assumption is mainly stating that we are able to do linear optimization efficiently in practice. For this, interior point methods or barrier methods work well in the case of continuous spaces and in the case of conjunctions, integer linear programs and mixed integer programs work effectively. We are happy to extend the discussion on this by adding text akin to the previous sentences to the paper.

Large and continuous state-action spaces Our methods already give provable guarantees for large spaces as we are able to make use of Algorithm $3$, which gives poly-time guarantees when we have group separator structure, or Algorithm $4$ for spaces without any group structure assumptions, but with an asymptotic guarantee. Here, one challenge would be to implement the policy oracle as mentioned before. One could hope to approximate solutions via standard deep RL techniques, which in many settings may be feasible. Yet, in various problems these algorithms may not return optimal policies in every execution [2]. As stated before we believe that moving to more complex oracle settings will come with its own challenges that lie beyond the scope of this manuscript.

[1] Lexicographically Fair Learning: Algorithms and Generalization. Emily Diana et al. FORC 2021.

[2] Deep Reinforcement Learning that Matters. Peter Henderson et al. AAAI 2018.

Dear Reviewer sNea,

Thank you for your positive assessment of our work and your feedback.

Additional Experimental Simulations The experimental study that we provide is used to highlight the applicability of our FairFictRL algorithm. Fictitious Play is easy to implement in practice because it only relies on Follow the Leader for both players and does not require noise generation that scales with the dimension of the action space. However it does not come with polynomial-time guarantees and our experiments aim to verify that it is still a good choice in practice. The Follow the Perturbed Leader-based algorithms themselves already have provable guarantees to converge, and we believe that adding additional experiments here may distract from the main message of the experimental section.

Optimization Oracles and Experiments In our experiments we consider a tabular MDP, for which the best response oracle is implemented via value iteration. The regulator can select the group that minimizes the past cumulative cost by iterating over the groups, because the number of groups is small in this experiment; in practice would need to use a stronger optimization oracle that is able to do linear optimization efficiently. In the case of conjunctions, this might also involve Integer Linear Programs or Mixed Integer Programs. Regarding MDP access, none of our algorithms require direct access to the MDPs. We only assume access to the MDP in our experimental section, in which we use value iteration to implement our best response oracle. We will update the wording in the manuscript to make this more clear. Note that to implement the best response oracle, we simply need to be able to optimize a given specified reward function within an MDP, which can be done with standard RL methods. These do not need to depend on access to the MDP. We simply choose value iteration because the goal of the experimental section is not to evaluate different oracles but rather to evaluate our FairFictRL algorithm under the proposed assumptions.

Separator sets The separator assumption directly affects our computational efficiency via the dependence of d in the bound given in Lemma 3.6. Since we are providing oracle-efficient algorithms, our primary computational- complexity analysis comes from the number of rounds our algorithm runs for given that we make O(T) oracle calls.

Dear Reviewer xri7,

We appreciate the positive assessment of our work.

Deep RL experiments As we highlight in Section 5 on Future Work, we completely agree that deep learning poses an interesting future direction for this type of work. However, the current manuscript is largely a theoretical contribution and we believe that moving to deep learning will come with its own challenges and open questions such as studying the effects of potentially sub-optimal oracles in practice, which will likely warrant a different type of publication. Our experiments primarily aim to verify the effectiveness of our FairFictRL algorithm. This algorithm is very easy to implement but, unlike our other algorithms, it does not come with with polynomial-time guarantees. Yet, our experiments validate that this easy version of the algorithm might be a feasible alternative in practice.

Applications Fairness in Reinforcement learning plays a large role in various applications such as healthcare or loan approval. However, we believe that one of the most interesting applications in our current timeline is the application to Reinforcement Learning from Human Feedback (RLHF). Our technique could be a step towards preventing LLMs from outputting discriminatory or toxic prompts to various (intersectional) groups. We will update the paper to include additional discussion of this application.