Provably Efficient and Practical Self-Play for Better LLM Alignment

Thank you for your constructive comment. We will address your questions point by point in the following responses. If there are any aspects we may have misunderstood or if you have further questions, we would be grateful for the opportunity to clarify and address them further.

Q1: Why is $\mathcal{R}$ defined on two actions instead of one action as in Equation (3)?

We appreciate the reviewer's question. The use of two different action spaces in defining $\mathcal{R}$ is primarily motivated by the theoretical analysis in our main theorem, which is based on the algorithm framework presented in Section 3. While our practical algorithm TANPO is equivalent to this framework when using the value function defined in Equation (3), the framework itself is more general. It is designed to apply not only to the specific value function in Equation (3) but also to any two-agent zero-sum game, including those that are not necessarily symmetric.

Defining $\mathcal{R}$ with respect to two different actions allows us to accommodate this generality and ensures consistency with our theoretical proofs. However, we acknowledge that this choice might appear confusing in the current presentation. We thank the reviewer for pointing this out, and we will revise this section to make the explanation clearer and more intuitive.

Q2: Is the final step of Equation (7) $V_r(\pi_t,\mu)$ instead of $V_r(\pi_t,\dagger)$?

We thank the reviewer for pointing out this typo. You are absolutely correct—the final step of Equation (7) should indeed be $V_r(\pi_t,\mu)$ instead of $V_r(\pi_t,\dagger)$. We will revise this in the manuscript to ensure accuracy. We sincerely appreciate your careful review and attention to detail.

Q3: What is the sampling strategy of online DPO?

We thank the reviewer for the question. The sampling strategy in our online DPO is designed to align as closely as possible with that used in TANPO. In TANPO, to encourage more diverse response pairs, we apply different temperature values for the max-player and min-player. Specifically, we use a temperature of 0.7 for the max-player and 0.5 for the min-player. Similarly, in the online DPO setting, the responses for the two players are sampled using these respective temperatures: 0.7 for the max-player and 0.5 for the min-player. This sampling strategy is consistent with prior work, where such temperature-based methods have been shown to promote diversity in response generation [1].

Q4: Regarding data diversity: Why does larger $|\log \pi_\text{ref}(a^1) - \log \pi_\text{ref}(a^2)|$ reflect higher data diversity?

We appreciate the reviewer's insightful question regarding data diversity and its measurement. One of the motivations for exploring data diversity in our work stems from the observation that, despite the max-player in TANPO and online DPO optimizing the exact same objective, TANPO empirically outperforms online DPO. We hypothesize that this difference arises from the disparity in the training data between the two algorithms.

In TANPO, the response pairs in the training data for the max-player consist of one response generated by the max-player and another generated by the min-player. In contrast, in online DPO, both responses in the pair are generated by the current policy. As a result, TANPO inherently has greater diversity within each local pair, as supported by the empirical evidence in Figure 1. To capture this, we use $|\log \pi_\text{ref}(a^1) - \log \pi_\text{ref}(a^2)|$ as a metric to quantify the diversity within local pairs. This local pair diversity directly affects the information learned by the agent and consequently impacts model performance.

Furthermore, this emphasis on increasing local pair differences is consistent with exploration techniques used in RLHF literature, such as ensemble methods [2], where a central idea is to maximize the diversity between the two responses within a pair through sampling. Additionally, increasing local pair differences has been shown to be effective in practical applications, as a commonly used technique leverages a similar approach to deliberately maximize the difference between two responses in a pair through choosing large-margin pairs based on the win-rate rank [3].

Regarding the reviewer's suggestion of using $D_{KL}(\pi_\text{ref}(\cdot | \text{TANPO}) || \pi_\text{ref}(\cdot | \text{online DPO}))$, we acknowledge its potential to measure overall distributional differences. However, if "TANPO" and "online DPO" in $\pi_\text{ref}(\cdot | \text{TANPO})$ and $\pi_\text{ref}(\cdot | \text{online DPO})$ refer to the prompts, the two distributions will be identical, as both TANPO and online DPO are trained on the exactly same dataset. Thus, in our work, we focus on the differences in local pairs, as they better capture the essential distinctions between the two algorithms.

Regarding Q4, I basically mean for some prompt $x$, we measure the diversity of responses generated by TANPO and DPO by some divergence measure between the distribution $\pi_{TANPO}(\cdot|x)$ and $\pi_{DPO}(\cdot|x)$.

We thank the reviewer for the insightful suggestion regarding the use of divergence measures between $\pi_{TANPO}(\cdot|x)$ and $\pi_{DPO}(\cdot|x)$ to assess the differences between TANPO and DPO.Our study primarily aims to understand and compare the unique characteristics of TANPO and DPO as individual algorithms, particularly focusing on why TANPO outperforms DPO. To achieve this, we use metrics that directly evaluate specific properties within each algorithm, rather than relying on divergence measures that only quantify the differences between the two. Measuring divergence alone provides limited explanatory power for understanding the underlying causes of TANPO's better performance, such as enhanced diversity or robustness.

Moreover, we avoided using KL-divergence to measure the diversity within response pairs generated by DPO in the online setting because the two responses are drawn from the same policy. In such cases, KL-divergence becomes meaningless as it fails to reflect the diversity of outputs within a single distribution.

Regarding Q6, it seems weird to me that to model a non-transitive reward requires approximation as previous papers do not assume this. Can you elaborate more on the tabular matrix game setting?

We thank the reviewer for the question regarding the modeling of non-transitive rewards and the need for approximations in our algorithm. Below, we provide a detailed explanation of the tabular matrix game setting and highlight the differences from previous works.

In some previous papers, such as [1][2], the proposed algorithms do not require approximations because the policy update at each step is defined as:

which has a closed-form solution:

and can be directly solved using standard methods. This simplicity arises because these algorithms do not explicitly account for exploration during policy updates.

For the transitive reward model, we leverage a reparameterization trick to transform the exploration term in the optimization problem into a simpler and practical objective, as shown in Equation (13) of our paper. This reformulation aligns perfectly with our theoretical algorithm and does not introduce any gap. However, for the non-transitive reward model, additional approximations are needed to transform the optimization into a practical form that can be effectively applied in LLM alignment tasks. Our algorithm introduces exploration by modifying the optimization objective. Specifically, if we define $V(\pi, \mu) = \mathbb{P}(\pi \succeq \mu)$, the optimization problem for the min-player in our setting takes the following form:

where $\mathcal{L}(\mu | \mathcal{D})$ is a loss function based on historical data, and $\hat{\mathbb{P}}$ represents an estimated probability learned by the agent. Unlike the transitive setting, the exploration term $\hat{\mathbb{P}}(\mu \succeq \pi_t)$ cannot be easily reparameterized into a function of $\mu_t$, making it difficult to directly optimize. To address this, approximations may be necessary to make the optimization problem tractable and applicable in practice.

In conclusion, previous works do not consider exploration in their algorithms and primarily rely on methods that avoid estimating value functions. In our case, to enable active exploration, we require an algorithm capable of effectively estimating value functions, which is inherently more challenging, especially in the non-transitive setting. We appreciate the reviewer for raising this point, as it opens up avenues for future research to improve the design of such algorithms.

[1] Munos R, Valko M, Calandriello D, et al. Nash learning from human feedback[J]. arXiv preprint arXiv:2312.00886, 2023.

[2] Wu Y, Sun Z, Yuan H, et al. Self-play preference optimization for language model alignment[J]. arXiv preprint arXiv:2405.00675, 2024.

Regarding Q7, I do not mean to plot a $\Theta(T)$ curve. It is okay if it is way better than $O(T)$ in some instances. For toy environments, you should be able to afford more training steps by using a small action space, say $100$ actions.

We thank the reviewer for the insightful suggestion. We agree that using a smaller action space could allow for more training steps, and we appreciate this direction. We will consider this approach in future work.

Thank you for your constructive comment. We will address your questions point by point in the following responses. If there are any aspects we may have misunderstood or if you have further questions, we would be grateful for the opportunity to clarify and address them further.

Q1: Policies $\pi$ and $\mu$ are fully decoupled in the value function (3).

We thank the reviewer for raising this insightful question regarding our choice of using a value function that can be fully decoupled while employing Nash equilibrium as a solution concept. Below, we explain our reasoning in detail:

Our proposed algorithm framework in Section 3 is designed for a general two-agent zero-sum game and is not restricted to fully decoupled value functions. It is applicable to all kinds of value functions. However, for the specific case studied in this work, we chose to use a value function that can be fully decoupled for the following reasons.

As demonstrated in Section 4, when using the additive value function described in Equation (3), our general algorithm framework aligns perfectly with a simple and practical algorithm. This close alignment ensures that the theoretical guarantees of the framework carry over seamlessly to the practical algorithm, which also demonstrates superior empirical performance. This highlights both the robustness and practicality of our approach in real-world scenarios.

Besides, the choice of a fully decoupled value function is also motivated by our goal to find the KL-regularized optimal policy, in line with other works based on BT-model like DPO. Specifically, we still aim to solve

$

\max_{\pi} \mathbb{E}[r(x, a)] - \alpha D_{\text{KL}}(\pi | \pi_{\text{ref}}).

$

By employing a fully decoupled value function within our algorithm, achieving the Nash equilibrium directly translates to obtaining the KL-regularized optimal policy. This equivalence enables us to fairly compare our results to other works based on the BT-model.

The use of Nash equilibrium as the solution is necessitated by the self-play nature of RLHF problem and our algorithm. Due to the nature of the RLHF problem, the data used for agent learning always consists of a prompt, two responses, and a preference. This structure inherently differs from standard contextual bandit problems, where a single objective can be directly maximized. While many works employ certain tricks to reformulate the RLHF problem into a contextual bandit framework, this approach often introduces practical inefficiencies. In our framework, the max-player and min-player both learn from historical data consisting of response pairs, where one response is generated by the max-player and the other by the min-player. This self-play setup inherently aligns with the Nash equilibrium concept, ensuring that both players’ strategies evolve in response to each other.

Many works that model online RLHF as a single-agent optimization problem instead of a two-player zero-sum game rely on one response being generated from a fixed policy to align with the contextual bandit setting. However, in our practical implementation, both responses are generated dynamically through self-play. While theoretically, both our algorithm and single-agent optimization approaches (where one response is generated from a fixed policy) can effectively find the same optimal policy, the latter approach is impractical in real-world applications. In practice, the vast majority of algorithms adopt a self-play style, where both responses are generated dynamically from updating policies. This is also the case in our algorithm, which avoids the limitations of relying on responses generated from fixed policies. Moreover, as demonstrated empirically in Section 6, our self-play-style algorithm achieves better performance compared to single-agent approaches, further highlighting its practical advantages.

We hope this explanation clarifies our design choices and demonstrates how they contribute to the robustness and effectiveness of our framework. Thank you again for the opportunity to elaborate on these points.

Thank you for your constructive comment. We will address your questions point by point in the following responses. If there are any aspects we may have misunderstood or if you have further questions, we would be grateful for the opportunity to clarify and address them further.

Q1: Value functions are already expected values.

We thank the reviewer for pointing out the redundancy in the term "expected Nash equilibrium value function." As the reviewer correctly noted, value functions in this context are already defined as expected values. We will revise the manuscript to remove this redundant phrasing and now refer to it simply as the "Nash equilibrium value function." Thank you for helping us improve the clarity of the manuscript.

Q2: Both the Nash equilibrium value function and the best response value function are a unique functions mapping from decision points to values. They are not an objective that a player can maximize.

We thank the reviewer for raising this important point. In our work, as well as in the majority of RLHF literature, a model-based learning approach is employed. Specifically, the max-player and min-player do not have access to the true reward function $r(x, a)$; instead, they estimate reward functions $\hat{r}_t^1$ and $\hat{r}_t^2$ based on historical data. These estimated reward functions are then used to compute the Nash equilibrium value function and the best response value function. Consequently, if the estimated reward functions differ, the resulting Nash equilibrium value function and best response value function will also differ. In this way, the agents can optimize the corresponding Nash equilibrium value function and the best response value function by changing the estimated reward function.

Our optimization variables are the parameters of the estimated reward function. The objective of our framework is to find a reward function that not only minimizes the loss on the historical data but also achieves high Nash equilibrium value function and best response value function based on the estimated reward functions. This approach encourages agents to explore more effectively by guiding them towards reward functions that balance exploitation and exploration.

We hope this clarifies the rationale behind our method and its objectives.

Q3: There is no such previously mentioned reward function.

We thank the reviewer for pointing out the lack of clarity regarding the reference to "that reward function." In Section 2, Equation (1), we define $r(x, a)$ as the human-provided score or a score predicted by a reward model that reflects the quality or suitability of response $a$ given the prompt $x$. However, we acknowledge that we did not explicitly refer to $r(x, a)$ as the "reward function", which might have caused confusion. While this is a common terminology in the RLHF literature, we agree that clearer terminology would improve the readability of the manuscript. To address this, we will revise the relevant sections to explicitly define $r(x, a)$ as the reward function. Thank you for your helpful suggestion.

Q4: TANPO is a tasteless name.

We appreciate the reviewer's comment on the name "Two-Agent Nash Policy Optimization." We chose this name to reflect the algorithm's focus on Nash equilibrium in two-agent zero-sum games. However, we understand that there is a large body of work on policy-based algorithms for computing Nash equilibria, and we are open to reconsidering the name to avoid any potential confusion. We will revise the manuscript accordingly. Thank you for your suggestion.

Q5: Refinements in language and presentation.

We thank the reviewer for this suggestion. We will revise the manuscript to replace "given the strategy of the other" with "given the other" as recommended. We believe this makes the statement more concise while retaining its intended meaning.

We also thank the reviewer for pointing out that the term "general" is superfluous in this context. We will remove it from the manuscript to make the statement more concise. Thank you for this helpful suggestion.