Policy Aggregation

Summary

This paper joins a long list of recent work that studies how to aggregate the preferences of several agents (e.g., humans) in a reinforcement learning framework inspired by social choice theory. The problem is modeled as a multi-objective MDP with $n$ different reward functions. The authors propose to use the state-action occupancy measure instead of each agent's most preferred policy or reward function directly. Popular concepts from social choice theory, such as the Borda count rule and approval voting, are then studied from this perspective.

Strengths

- The paper is well-written and easy to read. - It appears that considering the state-action occupancy measure has some advantages over working directly with each agent's optimal policy or reward function when attempting to introduce social choice rules, which---even though a standard approach in RL---is interesting.

Weaknesses

- In my opinion, the contributions of this work are limited. E.g., only the full information case is studied - The primary justification of this work (which is repeatedly mentioned in the paper) is that prior work on policy aggregation and fair RL is not invariant to affine transformations of the reward function. Essentially, agents can have differently scaled reward functions, which makes, e.g., maximizing for social welfare a bad objective. However, I don't understand why we cannot simply normalize the reward function of each agent, so that the reward functions are directly "comparable". I find the concern about affine transformations quite weak.

Questions

- I'm a bit surprised about the title of the paper since you're not aggregating policies, but reward functions. In fact, the policies play a minor role in the paper, since you look at the preference relation induced by the reward function (which you then express in term of occupancy measures). Could you explain why what you're doing is policy aggregation and not just preference aggregation? Typo: "Policy Aggergation" in title of Section 5

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Limitations are adequately addressed in my opinion.

Summary

The paper solves the problem which arises in preference aggregation of individual policies to a collective policy – (1) summation based aggregation are sensitive to affine transformations and (2) voting rule based aggregation faces problem of policies being exponential in S. Towards solving this, the paper proposes voting over continuous space of alternatives (which eliminates affine sensitivity) and a volumetric definition of preference ordering. The paper next proposes efficient algorithms to (1) find approximate volumetric veto core and (2) approximate q-Quantile Fairness. They also show complexity of existing voting rules, notably plurality voting and borda count. They show that problem is computationally hard for plurality and open for broad count. I am inclined towards accepting the paper.

Strengths

The paper solves a well-motivated problem of policy aggregation. Their proposal of achieving different notions of approximate fairness through efficient algorithms both novel and appears to be sound. Their theoretical analysis of the complexity of using plurality and borda count based voting is also significant and allows scope for future work in the direction. Their algorithms have been validated through experiments.

Weaknesses

In the experimental section, using a common metric to quantify the “level of fairness” guaranteed by different algorithms would be beneficial for a more learned comparison. In Def. 4 should the expression be vol(O’)/vol(O) >= 1 – veto(S) + epsilon instead of vol(O’) >= 1 – veto(S) + epsilon as currently stated?

Questions

see weakness. Why can't yours be a special case of Noothigattu et al. [27]?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Authors adequately address the problem statement and discussed limitations/candidate improvements of their work which is left to future work.

Summary

This paper studies aggregating multiple policies–which can be seen as a formalization of the task of aligning an AI system to the values of multiple individuals. When the number of states is small (such as, when multiple individuals have to select one out of a few candidates), this problem has been widely studied in voting and social choice theory, and there are many efficient aggregation rules (such as the Borda count). This paper, however, considers the other extreme: where the state-action space is huge, and it is not obvious how to design efficient methods to aggregate policies. The main insight of this paper is that preferences over policies have a volumetric interpretation in the state-action policy space that, in some cases, leads to efficient aggregation algorithms. Concretely, the authors examine two types of aggregation rules: (1) two aggregation rules that are known to have desirable fairness properties (namely, proportional veto code and, the recently introduced, quantile fairness) and (2) voting or score-based rules such as Borda count and $\alpha$-approval voting rule. Building on their insight the authors prove several results, including 1. an algorithm which finds the policy wrt an $\epsilon$-approximation of the proportional veto core using $O(log(1/\epsilon))$ queries to a volume computation oracle, 2. the existence of $q$-quantile fair policies for all $q\geq 1/e$ (which is tight and stronger than the best possible bound in the discrete case), 3. NP-hardness and inapproximability results for $\alpha$-approval score.

Strengths

The paper is well-written and easy to read. I believe that the problem proposed in the paper is well-motivated from alignin AI systems, and is of significant interest to research on voting rules and social choice theory. The theoretical results are solid and the proofs and/or approach are well outlined. Finally, I did not check the proofs in detail, but they appear sound. One caveat is that I am not familiar with the closely related prior work (e.g., [6]) and, so, cannot comment on the novelty of the proofs and results from prior work.

Weaknesses

I am not sure if the empirical results section is adding any value to this paper: it evaluates different aggregation rules, but I think this is not the focus of this work–I think the focus is to design efficient algorithms and/or prove existential results. If other reviews and the area chairs agree, my suggestion is to drop the empirical results section and use the additional space to add more exposition on the proofs. To be clear, this is no a significant concern for me.

Questions

I do not have any specific questions for the authors.

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

I do not see significant limitations.

Response to authors

I thank the authors for their response. I will keep my previous score and think this paper should be accepted.