Provable Multi-Party Reinforcement Learning
with Diverse Human Feedback

We start with the contextual bandit (CB) setting. Consider the environment $E=(\mathcal{S},\mathcal{A},\{R_{m}\}_{m=1}^{M},\rho)$, where $\mathcal{S}$ is a state space, $\mathcal{A}$ is an action space, $R_{m}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ for $m\in[M]$ are reward functions from $M$ individuals (or parties), and $\rho$ is an initial state distribution. A deterministic policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$ is a function that maps a state to an action, while a randomized policy $\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ is a function that maps a state to a distribution over the action space.

As in Zhu et al., (2023), we consider an offline setting with a pre-collected dataset $\mathcal{D}$. We are provided with pairwise comparisons $\mathcal{D}=\bigcup_{m=1}^{M}\mathcal{D}_{m}$ from $M$ individuals (or parties), where $\mathcal{D}_{m}=\{(s_{m}^{i},a_{m,1}^{i},a_{m,0}^{i},y_{m}^{i})\}_{i=1}^{n}$ for $m\in[M]$. For the $i$-th sample in $\mathcal{D}_{m}$, a state $s_{m}^{i}$ is first sampled from the initial distribution $\rho$. Given the state $s_{m}^{i}$, an action pair $(a_{m,1}^{i},a_{m,0}^{i})$ is sampled from a distribution $g_{a}(a_{1},a_{0}|s_{m}^{i})$. Thus $(s_{m}^{i},a_{m,1}^{i},a_{m,0}^{i})$ is generated by a generation distribution $g=g_{a}(\cdot|s)\rho(s)$. We then observe a binary outcome $y_{m}^{i}$ from a Bernoulli distribution $\mathbb{P}_{m}(y_{m}^{i}=1|a_{m,1}^{i},a_{m,0}^{i},s_{m}^{i})$. Here $y_{m}^{i}\in\{0,1\}$ indicates the preferred one in $(a_{m,1}^{i},a_{m,0}^{i})$. Primarily, we assume that $\mathbb{P}_{m}$ is reward-based for $m\in[M]$.

As different parties have their own reward functions, in this section, we introduce the social welfare functions to aggregate them such that the trained model aligns with heterogeneous preferences and reflects social welfare. They map individual utilities $u_{1},\cdots,u_{M}$ to collective welfare, where $u_{m}:\mathcal{X}\rightarrow\mathbb{R}$ is the utility of the $m$-th individual for $m\in[M]$ and $\mathcal{X}$ is the possible set of outcomes. A reasonable welfare function should satisfy six axioms: monotonicity, symmetry, continuity, independence of unconcerned agents, independence of common scale, and Pigou-Dalton transfer principle (see, Chapter 3.2, Moulin,, 2004). It has been proved that all functions that satisfy these six desirable properties lie in a one-parameter family of isoelastic social welfare functions $W_{\alpha}$, defined as follows:

Among these functions, we elaborate on three prominent examples: the Utilitarian welfare function $(\alpha=1)$ that calculates the mean expected agreement across parties, the Leximin welfare function $(\alpha\rightarrow-\infty)$ that ensures the utility of the worst individual, and the Nash welfare function $(\alpha=0)$ that maximizes the utility product to attain a proportional-fair (Kelly et al.,, 1998; Zhang et al.,, 2022) solution. These concepts of welfarism are widely used in social choice theory, see more details in Appendix A. We primarily consider Nash welfare function $(\alpha=0)$. In the context of welfarism with bargaining considerations, an objective definition of the zero of individual utility is introduced. This concept is regarded as the worst outcome or minimal utility to be accepted by a specific individual so the arbitrator must consider the utility as a strict lower bound. Thus, Nash bargaining (Nash,, 1953) considers a maximization problem over a feasible set $\{(u_{1}(x),\cdots,u_{M}(x))|x\in\mathcal{X}\}$ under additional normalization of individual zeros $(u_{1}^{0},\cdots,u_{M}^{0})$:

By optimizing the welfare function with such normalizations, the Nash bargaining solution is invariant to affine transformations of $u_{m}$’s and eliminates the dominance of specific individuals, making it a standard solution concept in cooperative games. We begin with the Nash welfare function to aggregate heterogeneous reward functions in the next section and optimize the aggregated function. Additional results of other social welfare functions (e.g., Utilitarian $(\alpha=1)$ and Leximin $(\alpha\rightarrow-\infty)$) are shown in Section 4.4.

The construction of the Nash Bargaining estimator consists of four steps. Step 1 is to estimate the parameters $\theta_{m}^{*}$ from the observations. Step 2 is to construct the confidence sets for these parameters simultaneously. Step 3 involves introducing a pessimistic expected value function using Nash bargaining. Finally, Step 4 is to obtain the pessimistic policy through a maximization problem. We summarize this procedure in Algorithm 1, and discuss each step in detail below.

First, we learn individual reward $R_{m,\theta_{m}}(s,a)=\theta_{m}^{\top}\phi(s,a)$ for $m\in[M]$ through maximum likelihood estimator (MLE). Denote $\alpha=(\alpha_{1},\cdots,\alpha_{M})\in\mathbb{R}^{r\times M}$ as the low-dimensional parameters, and $\Theta=(\theta_{1},\cdots,\theta_{M})\in\mathbb{R}^{d\times M}$ as the original parameters. Define the feature difference as $X_{m,i}=\phi(s_{m}^{i},a_{m,1}^{i})-\phi(s_{m}^{i},a_{m,0}^{i})$ and $X_{m}=(X_{m,1},\cdots,X_{m,n})^{\top}$ for $m\in[M]$. Using the dataset $\mathcal{D}=\bigcup_{m=1}^{M}\mathcal{D}_{m}$ with $\mathcal{D}_{m}=\{(s_{m}^{i},a_{m,1}^{i},a_{m,0}^{i},y_{m}^{i})\}_{i=1}^{n}$, we minimize the negative log-likelihood:

where $l_{\mathcal{D}}(U,\alpha)=-\dfrac{1}{Mn}\sum_{m=1}^{M}\sum_{i=1}^{n}\{\mathbf{1}(y_{m}^{i}=1)\log\left(\Phi(\langle U\alpha_{m},X_{m,i}\rangle)\right)+\mathbf{1}(y_{m}^{i}=0)\log\left(\Phi(\langle U\alpha_{m},X_{m,i}\rangle)\right)\}$. When the minimizer is not unique, we take any of the solutions $(\hat{U},\hat{\alpha}_{m})$ that achieves the minimum. As a result, we obtain the estimators $\hat{\theta}_{m}=\hat{U}\hat{\alpha}_{m}$ for $m\in[M]$. Then define the $d\times d$ data covariance matrices for $m\in[M]$ as

Subsequently, we regard the multi-party alignment problem as a Nash bargaining game involving $M$ reward functions $\{R_{m,\theta_{m}}\}_{m=1}^{M}$. We set the zero utility as $R_{m,\theta_{m}}^{0}(s)=\min_{a}R_{m,\theta_{m}}(s,a)$ and consider the following Nash welfare function to guarantee individual satisfaction,

We emphasize that the introduction of minimal rewards, $R_{m,\theta_{m}}^{0}$, ensures solution invariance and mitigates dominance concerns, as discussed in Section 3.2. Moreover, our specific choice for $R_{m,\theta_{m}}^{0}$ is easy to compute since solving $R_{m,\theta_{m}}^{0}(s)$ is standard in bandit and RL problems (Sutton and Barto,, 2018). Alternatively, we can also consider the reward $R_{m,\theta_{m}}^{\text{ref}}(s)$ under any reference policy. This distinction separates multi-party alignment from single-party alignment.

Next, we introduce the pessimistic technique to learn a policy. We first define the true Nash expected value $J$ of a policy ${\pi}$ and its sub-optimality as:

where $\pi^{*}=\arg\max_{\pi}J(\pi)$ is the optimal policy. This sub-optimality notion measures a performance gap compared to the optimal policy. Given a failure probability $\delta$, we consider the pessimistic estimator obtained from the lower confidence bound of the set of parameters: $\Theta_{B}(\hat{\theta}_{m})=\{\theta\in\Theta_{B}:\|\theta-\hat{\theta}_{m}\|_{\Sigma_{m}}\leq\Gamma(\delta,n,M,d,r)\}$, where $\Gamma$ is defined in the next section. We then construct a pessimistic Nash expected value function:

Finally, we obtain $\hat{\pi}=\arg\max_{\pi}\hat{J}(\pi)$ as the pessimism estimator. The pessimism technique penalizes responses that are less represented in the dataset and thus contributes to finding a more conservative and accurate policy (Xie et al.,, 2021; Zhan et al.,, 2023; Zhu et al.,, 2023). Later, we will demonstrate that $\hat{\pi}$ can approach $\pi^{*}$ in the sense of the true Nash expected value $J$.

In this section, we introduce the sub-optimality bound and the corresponding sample complexity. We begin with the following estimation error between $\hat{\theta}_{m}=\hat{U}\hat{\alpha}_{m}$ and $\theta_{m}^{*}=U^{*}\alpha_{m}^{*}$.

Now we let $\Gamma$ in Algorithm 1 be $\Gamma(\delta,n,M,d,r)=K\sqrt{\dfrac{r^{2}}{n}+\dfrac{dr^{2}\log{d}+r\log(M/\delta)}{Mn}}$, where $K$ is a constant. Theorem 1 implies that with probability at least $1-\delta$, $\theta_{m}^{*}\in\Theta_{B}(\hat{\theta}_{m})$ for any $m\in[M]$. We provide a proof outline here, and defer the details to Appendix C.1. First, we establish an overall bound on $\sum_{m=1}^{M}\|X_{m}\hat{\theta}_{m}-X_{m}\theta_{m}^{*}\|^{2}$ by leveraging the convexity of $l_{\mathcal{D}}(U,\alpha)$, based on second-order Taylor expansion and a careful use of concentration inequalities. Next, we derive a bound on $\|\hat{\theta}_{m}-\theta_{m}^{*}\|_{\Sigma_{m}}$ in terms of $U$ and $\alpha_{m}$ using the Davis-Kahan $\sin\theta$ theorem and Bernstein-type inequality. Theorem 1 is a generalization of the upper bound of Lemma 3.1 in Zhu et al., (2023), which improves the previous bound of $\sqrt{\frac{d}{n}}$ when $r^{2}\ll\min\{M,d\}$. It shows that it is possible to use $O(r^{2})$ samples to learn individual rewards via learning a shared representation with all observations pooled together.

We then consider the induced policy. Denote $\tilde{\theta}_{m}=\arg\min\limits_{\theta_{m}\in\Theta_{B}(\hat{\theta}_{m})}\mathbb{E}_{s\sim\rho}\prod_{m=1}^{M}(R_{m,{\theta}_{m}}(s,\pi^{*}(s))-R_{m,\theta_{m}}^{0}(s))$ as the achieved pessimistic parameter in the lower confidence bound for $\pi^{*}$. Denote $\underline{\pi}_{*m}(s)=\arg\min_{a}R_{m,\theta_{m}^{*}}(s,a)$ and $\underline{\pi}_{m}(s)=\arg\min_{a}R_{m,\tilde{\theta}_{m}}(s,a)$ as the baseline policy to reach $R_{m,\theta_{m}^{*}}^{0}(s)$ and $R_{m,\tilde{\theta}_{m}}^{0}(s)$, respectively. Define the concentratability coefficient as

We have the following guarantee for the pessimistic policy, whose proof is given in Appendix C.2.

The proof sketch is as follows. The sub-optimality can be decomposed as, $J(\pi^{*})-J(\hat{\pi})=(J(\pi^{*})-\hat{J}(\pi^{*}))+(\hat{J}(\pi^{*})-\hat{J}(\hat{\pi}))+(\hat{J}(\hat{\pi})-J(\hat{\pi}))$ and what we truly need to focus on is the first term $J(\pi^{*})-\hat{J}(\pi^{*})$ since the latter two terms are smaller than zero with high probability. We address the multiplicative Nash welfare function by decomposing it into the aggregation of individual errors. Given the normalization inherent in Nash bargaining, we then separately handle the gaps between the true and empirical $R(s,\pi^{*})$ values as well as those between the true and empirical $R^{0}(s)$ values induced by stochasticity, by using the estimation error.

We point out that $C^{*}$ is a concentratability coefficient assumed to be bounded (Zhu et al.,, 2023; Zhan et al.,, 2023). It provides a coverage guarantee of the dataset: the ratio of the state-action occupancy induced by the optimal and baseline policies, to the data distribution, is bounded. This assumption ensures good coverage of the target vector $\mathbb{E}_{s\sim\rho}\phi(s,\pi^{*}(s)),\mathbb{E}_{s\sim\rho}\phi(s,\underline{\pi}(s))$ from the dataset in the feature space, and therefore yields an accurate estimator.

For the problems with bounded concentratability coefficients (defined in (6)), we obtain a lower bound result in the following theorem, whose proof is deferred to Appendix C.3.

The lower bound highlights the complexity challenge in multi-party RLHF. We face the aggregation of individual learning errors and a potentially larger concentratability coefficient $C^{*}$ defined in (6), as it is related to not only the optimal policy $\pi^{*}$ but also the baseline policies $\underline{\pi}_{m}$. This leads to a larger sample complexity than traditional RLHF, where the concentratability coefficient is solely based on a single-party optimal policy as depicted in Theorem 3.10 in Zhu et al., (2023). Obtaining tight dependence of our sub-optimality bound on feature dimensions is challenging. The $\sqrt{r}$ gap between Theorem 2 and Theorem 3 relates to an open problem in classical estimations, see a more detailed discussion on page 8 in Tripuraneni et al., (2020).

We demonstrate the efficiency and fairness guarantees of our method using a Nash welfare function. Theorem 2 implies the above Nash solution is within a small distance (sub-optimality) to the optimal solution $\pi^{*}$ ($\pi^{*}$ is also Pareto efficient, see Lemma 3). This observation motivates us to consider the concept of $\tau$-approximate Pareto efficiency concerning each normalized reward function.

This efficiency guarantees an agreement and balance among multiple parties. It is an adaptation of the definitions by Aumann and Dombb, (2010); Barman et al., (2018) to the CB settings. While previous work considered an efficiency notion that allows a $\tau$ improvement for all individuals, we admit a $\tau$ improvement for only one individual when maintaining others unchanged. Define the state-wise concentratability coefficient as

We formulate the following theorem.

This result is established for every state and the proof is given in Appendix C.4. It confirms that we cannot improve one party significantly without making another party worse, thus leading to a proportional-fair policy. Besides, the pessimistic policy $\hat{\pi}$ follows the approximate Pigou-Dalton principle, ensuring more equitable outcomes (Moulin,, 2004), see Appendix C.4 for details.

Further, we provide a concise introduction of other social welfare functions, including the Utilitarian and Leximin (Egalitarian) welfare functions, and compare their results. We adjust the pessimistic value function $\hat{J}(\pi)$ in Step 3 of Algorithm 1 to accommodate these alternative welfare functions.

We now generalize our results to MDPs where the preference is based on a whole trajectory instead of a single action. Examples of such settings include Atari games and robot locomotion (Christiano et al.,, 2017), where the preference depends on historical behaviors. We consider the environment $E=(\mathcal{S},\mathcal{A},H,\{P_{h}\}_{h=1}^{H-1},\{R_{m}\}_{m=1}^{M},\rho)$, where $\mathcal{S}$ is a state space, $\mathcal{A}$ is an action space, $H$ is the horizon length, $P_{h}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ for $h\in[H-1]$ are known transition kernels, $R_{m}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ for $m\in[M]$ are reward functions from $M$ individuals (or parties), and $\rho$ is an initial state distribution. Define the occupancy measure $d^{\pi}:\mathcal{S}\rightarrow\mathbb{R}$ as $d^{\pi}(s)=\sum_{h=1}^{H}\mathbb{P}_{h}(s_{h}=s|\pi)$, which becomes $\rho(s)$ when $H=1$. We are provided with pairwise comparisons $\mathcal{D}=\bigcup_{m=1}^{M}\mathcal{D}_{m}$, where $\mathcal{D}_{m}=\{(s_{m}^{i},\tau_{m,1}^{i},\tau_{m,0}^{i},y_{m}^{i})\}_{i=1}^{n}$ for $m\in[M]$. For the $i$-th sample in $\mathcal{D}_{m}$, an initial state $s_{m}^{i}$ is sampled from $\rho$ and two trajectories $\tau_{m,1}^{i}=(a_{m,1}^{i},\cdots,s_{m,H}^{i},a_{m,H}^{i}),\tau_{m,0}^{i}=(a_{m,1}^{i^{\prime}},\cdots,s_{m,H}^{i^{\prime}},a_{m,H}^{i^{\prime}})$ are sampled from a distribution $g_{\tau}(\tau_{m,1}^{i};\tau_{m,0}^{i}|s_{m}^{i})$. Thus $(s_{m}^{i},\tau_{m,1}^{i},\tau_{m,0}^{i})$ is generated by a generation distribution $g=g_{\tau}(\cdot|s)\rho(s)$. We then observe a binary outcome $y_{m}^{i}$ from a Bernoulli distribution $\mathbb{P}_{m}(y_{m}^{i}=1|\tau_{m,1}^{i},\tau_{m,0}^{i})$ as follows,

where Assumption 1-4 hold with the feature difference in $\Sigma_{*}$ changed to the cumulative difference over the trajectory, i.e., $\Sigma_{*}=\mathbb{E}_{g}(\sum_{h=1}^{H}(\phi(s_{h},a_{h})-\phi(s_{h}^{\prime},a_{h}^{\prime})))(\sum_{h=1}^{H}(\phi(s_{h},a_{h})-\phi(s_{h}^{\prime},a_{h}^{\prime})))^{\top}$.

The generalized algorithm for MDPs is similar to Algorithm 1. We first construct MLE $\hat{\theta}_{m}=\hat{U}\hat{\alpha}_{m}$, aggregate the reward functions, and then seek a policy to optimize the pessimistic Nash value function $\hat{J}$. However, here we adopt a trajectory-based preference model and thus optimize a trajectory-wise value function. We are going to discuss the differences in detail below.

Denote $X_{m,i}=\sum_{h=1}^{H}\left(\phi(s_{m,h}^{i},a_{m,h}^{i})-\phi(s_{m,h}^{i^{\prime}},a_{m,h}^{i^{\prime}})\right)$ now as the difference between the cumulative feature in two trajectories, $X_{m}=(X_{m,1},\cdots,X_{m,n})^{\top}$. Define the data covariance matrices as $\Sigma_{m}=\dfrac{1}{n}X_{m}^{\top}X_{m}$ for all $m\in[M]$. We again minimize the negative log-likelihood:

where $l_{\mathcal{D}}(U,\alpha)=-\dfrac{1}{Mn}\sum_{m=1}^{M}\sum_{i=1}^{n}\{\mathbf{1}(y_{m}^{i}=1)\log\left(\Phi(\langle U\alpha_{m},X_{m,i}\rangle)\right)+\mathbf{1}(y_{m}^{i}=0)\log\left(\Phi(\langle U\alpha_{m},X_{m,i}\rangle)\right)\}$.

Subsequently, we use Nash bargaining to aggregate individual preferences. Here we point out that the key difference between MDPs and CBs is the inclusion of the trajectory-based measure $d^{\pi}$, which stems from the observation (Zhu et al.,, 2023) that:

where $V^{\pi}(s)=\mathbb{E}[\sum\limits_{h=1}^{H}\prod\limits_{m=1}^{M}(R_{m}(s_{h},a_{h})-R_{m}^{0}(s_{h},a_{h}))|s_{1}=s,\pi]$, and this expectation $\mathbb{E}$ is taken over the trajectory generated according to the transition kernel. Since the transition distribution $P$ is known, we can directly calculate $d^{\pi}$ for any given $\pi$. Define the trajectory-wise true and pessimistic Nash expected value function $J$ and $\hat{J}$ as follows:

where $\Theta_{B}(\hat{\theta}_{m})=\{\theta\in\Theta_{B}:\|\theta-\hat{\theta}_{m}\|_{\Sigma_{m}}\leq K^{\prime}$ $\sqrt{\dfrac{r^{2}}{n}+\dfrac{dr^{2}\log{d}+r\log(M/\delta)}{Mn}}\}$, $K^{\prime}$ is a fixed parameter. Define $\hat{\pi},\pi^{*},\underline{\pi}_{*m},\underline{\pi}_{m},\tilde{\theta}_{m}$ following the same structure as in Section 4.2, $C^{*}=\max_{m}\max_{\pi\in\{\pi^{*},\underline{\pi}_{*m},\underline{\pi}_{m}\}}\|(\Sigma_{m}^{-1/2}\mathbb{E}_{s\sim d^{\pi^{*}}}\phi(s,\pi(s)))\|_{2}$. We have the following result, whose proof is deferred to Appendix C.6.

We can also attain efficiency and fairness guarantees similar to Section 4.3 accordingly.