Offline Equilibrium Finding in Extensive-form Games: Datasets, Methods, and Analysis

Thank you for your valuable feedback. Below is our response to your question:

---

Curated Datasets

• Thank you for raising this important point. Indeed, the datasets used in our experiments are sampled from game simulators and may not fully capture the practical setting. However, these datasets were chosen intentionally to provide a controlled environment for evaluating algorithmic performance, allowing us to isolate and analyze specific factors influencing the performance of the proposed algorithm.

• We agree that using datasets collected from human gameplay could offer valuable insights and strengthen the application of our methods. Unfortunately, to the best of our knowledge, publicly available datasets of human gameplay for these or similar games are currently limited. We are eager to explore real-world gameplay data in future work, should such datasets become available. Additionally, we hope that our work motivates the creation of more realistic datasets to advance Offline EF research.

---

Theoretical Results

• Thank you for your thoughtful feedback regarding the theoretical results in Section 4. We recognize that the assumptions underlying Theorems 4.4, 4.5, and 4.6 may appear strong. However, these assumptions are intended to provide a foundation base for understanding the theoretical guarantees of our method. Specifically, Theorem 4.5 demonstrates that with sufficient data and a low-error function approximator, it is possible to recover an approximate equilibrium strategy.

• We agree that further relaxing these assumptions would significantly enhance the contribution, and we are actively exploring potential extensions to our theoretical framework to address more practical settings with weaker assumptions. Additionally, our empirical results aim to complement the theoretical analysis by demonstrating the effectiveness of the proposed method in scenarios where the assumptions are not strictly satisfied.

---

Results of Leduc

• We acknowledge that the NashConv values reported for Leduc Poker in our experiments are relatively high compared to the low exploitability achieved by CFR+ in the OpenSpiel implementation. This discrepancy is likely due to two key factors: the high dynamism of Leduc Poker and the poor quality of the offline dataset. Notably, even when conducting the experiments on the expert dataset, the performance of the BC algorithm is suboptimal, further indicating the low quality of the offline dataset. Additionally, the high dynamism of Leduc Poker makes it challenging to train an accurate environment model, leading to discrepancies between the trained model and the original game dynamics. These discrepancies negatively impact overall performance.

---

Small Tested Domain

• Thank you for your valuable feedback. We acknowledge that the tested domains, while effective for initial evaluation, are relatively small and may not fully capture the complexity of realistic offline scenarios. However, these domains were intentionally chosen to provide a controlled environment for understanding and validating the core principles of our approach.

• We agree that evaluating our method on larger and more complex games, such as Limit Hold’em, would significantly increase the relevance and impact of our work. However, applying BOMB to larger games presents substantial computational and data-related challenges, particularly in ensuring the availability of high-quality offline datasets. Nonetheless, we are actively working toward scaling up our experiments and exploring adaptations of BOMB for larger-scale games, as we discussed in the Future Work section.

---

Reply to Q1

• In definition 2.1, we seek to minimize the gap over all joint strategies in the original game, as $\sigma^*$ in the definition represents the equilibrium strategy of the original game.

---

Reply to Q2

• The x-axis represents the proportion of data from the random dataset within the hybrid dataset. Specifically, when the proportion is 0, the hybrid dataset is equivalent to the expert dataset; conversely, when the proportion is 1, the hybrid dataset consists entirely of the random dataset. This description is provided in our paper, but we will ensure it is highlighted more explicitly for clarity.

---

Reply to Q3

• In multi-player scenarios, while these equilibrium-finding algorithms do not guarantee convergence to Nash equilibrium strategies, we report these results as part of our experiments to explore the factors influencing the performance of our model-based algorithm. Additionally, for correlated equilibrium (CCE) solutions in multi-player cases, we also report the corresponding results in RQ4 for a more comprehensive analysis.

---

We hope our response can address your concerns, and we deeply appreciate that if you could reconsider the evaluation of our paper.

Dear Reviewer H5em,

Thank you once again for your valuable review and reply.

As the author-reviewer discussion period is nearing its end, we would like to kindly ask if our responses have addressed your concerns. We have put a lot of effort into preparing detailed responses to your questions. We are eager to address any additional feedback or unresolved concerns you may have before the discussion period concludes.

We look forward to hearing from you. Thank you for your time and consideration.

Sincerely,

Authors of Submission 8885

Thank you for your valuable feedback. Below is our response to your question:

---

Theoretical Results and Assumptions

• Thank you for your valuable feedback. We acknowledge that the theoretical results in the paper make strong assumptions, such as the dataset size, its coverage, and the learning algorithm’s ability. These assumptions were made to establish baseline guarantees for offline equilibrium finding (Offline EF) and provide a foundational understanding of the problem.

• At this stage, such assumptions are an unavoidable compromise, as Offline EF introduces significant additional challenges compared to online settings, including reliance on static datasets with potentially limited coverage and imperfect learning models. By working within these assumptions, we aim to provide initial insights and a clear framework for evaluating offline methods, acknowledging their limitations.

• We agree that providing bounds on the effectiveness of offline methods with randomly sampled datasets or analyzing how learning errors impact the equilibrium distance would significantly strengthen the theoretical contributions. This is a compelling suggestion and a promising direction for future work.

---

BOMB Algorithm and Abstraction

• Thank you for your insightful feedback. The BOMB algorithm combines BC and MB approaches with a predictor to determine their optimal weighting. While the overall framework may appear straightforward, its strength lies in its ability to effectively balance the strengths of BC and MB to adapt to diverse offline datasets and scenarios.

• We appreciate your observation about using abstractions to scale from smaller to larger games. This is indeed an interesting direction, and we agree that creating abstractions directly from the offline dataset could fit well into the Offline EF framework. Such an approach could help address challenges related to dataset incompleteness or scalability in larger games, where direct computation might be infeasible. By extracting a meaningful abstraction from the dataset, we could potentially improve the accuracy of the environment model and the overall performance of the algorithm.

• In our current work, we have not explicitly incorporated abstraction-based techniques, but we recognize their potential in the offline setting and view this as a promising avenue for future research. We appreciate your suggestion and will consider exploring how abstractions can be integrated into the BOMB framework to further enhance its applicability to large-scale games.

---

Truly Offline Setting in Experiments

• In our current experiments, we relied on datasets generated through random, expert, and hybrid policies to create controlled scenarios for evaluation. These allow for a systematic comparison of different methods and an understanding of how dataset quality affects performance, although they may not fully represent the challenges posed by real-world offline datasets, such as those generated from human play. As we discussed in Limitations and Future Work, we take applying the offline EF to human-play datasets as future work.

---

General Sum Games and NE

• While these equilibrium-finding algorithms do not guarantee convergence to Nash equilibrium strategies in general-sum games, we report these results as part of our experiments to explore the factors influencing the performance of our model-based algorithm. Additionally, for correlated equilibrium (CCE) solutions in multi-player cases, we also report the corresponding results in RQ4 for a more comprehensive analysis. We appreciate your observation regarding the statements in lines 506-507. Upon review, we realize that the wording may be overly strong and could lead to confusion. We revise this section in the revision to clarify that our experimental results do not imply a general solution to approximating NE in polynomial time but rather highlight the practical effectiveness of BOMB in the specific datasets and settings tested.

---

Typo Issue

• Thanks for pointing out this. We have revised it in the revision.

---

Reply to Q1

• The current predictor design in BOMB relies on the similarity between the BC and MB policies as input, which we acknowledge may have limitations. This simplified design was chosen to provide a practical solution in a fully offline scenario.

• Before finalizing this design, we also considered incorporating more contextual information into the predictor, such as the quality of the dataset or features of the environment model. However, these approaches often require additional data or computational resources, which may introduce higher demands on offline application settings. Considering these trade-offs, we opted for the similarity-based predictor as it balances feasibility and effectiveness under current resource and technical limitations. Despite its simplicity, it has shown efficacy in our experiments.

• We agree that exploring more sophisticated and context-aware predictor designs is a valuable direction for future work. Such improvements could enhance the predictor’s accuracy and further expand the robustness of the BOMB framework in more complex scenarios.

---

Reply to Q2

• The purpose of using grid search in our experiments is to provide an upper-bound evaluation of the BOMB framework’s potential performance by identifying the optimal combination of BC and MB policies. We acknowledge that grid search may not reflect a fully practical offline scenario, as it requires validation data or an environment for evaluation. To address this limitation, we also proposed and evaluated a learning-based method to estimate \alpha without requiring online interactions after training. While the learning-based method performs slightly worse than grid search in some cases, it demonstrates promising results and better aligns with the fully offline setting.

---

Reply to Q3

• To answer this question, we can transfer this extensive form game into the following normal form game.

  actions	$b_1$	$b_2$
  $a_1$	(0, 0)	(0, 0)
  $a_2$	(1, -1)	(-2, 2)

  We can see that action $b_2$ weakly dominates action $b_1$. When player 2 chooses action $b_2$, then player 1’s best response would be action $a_1$. Clearly, strategy profile ($a_1$, $b_2$) would be the NE strategy.

---

Reply to Q4

• Indeed, the grid search method used in BOMB allows it to explore a range of $\alpha$ values, naturally providing BOMB with the flexibility to outperform either component individually. However, the key strength of BOMB lies in its ability to effectively balance the advantages of the BC and MB approaches, as neither single method can handle all diverse cases on its own. By combining these two methods, BOMB leverages their complementary strengths, as demonstrated by the performance gains observed in our experiments. While the grid search method provides a straightforward way to optimize $\alpha$, it is the combination of BC and MB that enables BOMB to consistently achieve superior results across diverse datasets and game scenarios.

Dear Reviewer KpQq,

Thank you once again for your valuable review.

As the author-reviewer discussion period is nearing its end, we would like to kindly ask if our responses have addressed your concerns. We have put a lot of effort into preparing detailed responses to your questions. We are eager to address any additional feedback or unresolved concerns you may have before the discussion period concludes.

We look forward to hearing from you. Thank you for your time and consideration.

Sincerely,

Authors of Submission 8885

Thank you for your valuable feedback. Below is our response to your question:

---

Reply to Q1

• We agree that offline MARL faces similar issues as offline RL, with these challenges being further amplified due to the added complexity of inter-agent dependencies and interactions. For instance, to mitigate the distribution shift issue, our MB approach leverages a learned environment model to simulate inter-agent dynamics and explore strategies that may not be directly represented in the dataset. To further address this, the environment model is shared among all agents, ensuring consistency and reducing potential discrepancies in the simulated interactions.

---

Reply to Q2

• In our model-based algorithm, the trained environment model replaces the original game simulator in the equilibrium-finding algorithms. As a result, our MB method does not exacerbate the inherent non-uniqueness problem of equilibria in these games and algorithms. While it is true that the state-action pairs in the dataset influence the training of the environment model, the primary factor affecting performance is the gap between the learned environment model and the actual game model, rather than the non-uniqueness of equilibria.

• Regarding the equilibrium-finding algorithms, we intentionally use their vanilla versions in this paper to demonstrate that our MB method can seamlessly integrate online equilibrium-finding algorithms into the offline setting with minimal modifications. This approach highlights the flexibility of our framework while leaving room for future improvements to address offline-specific challenges.

---

Reply to Q3

• We acknowledge that the theoretical results rely on strong assumptions, including sufficient dataset coverage to ensure that every relevant state is visited. As you pointed out, in complex games such as chess or Go, it is practically impossible to achieve full coverage of all states due to the immense size of their state spaces.

• Our theoretical framework is intended to establish a baseline understanding of the conditions under which Offline EF can succeed, even if these assumptions are idealized. In the experimental section, we demonstrate the practical performance of our approach under different offline datasets, showcasing its ability to address challenges arising from limited state coverage to some extent.

---

Reply to Q4

• We combine the two policies in the policy space. Specifically, for each state, both policies produce their respective distributions over actions. These distributions are then combined using a weighted interpolation based on the given weight, resulting in a single distribution that represents the final strategy.

---

Reply to Q5

• For the offline RL baselines, the problem is treated as an independent offline RL task for each player to compute their optimal strategy. We run the offline RL algorithms separately for each player to derive their respective optimal strategies. Once these strategies are obtained, we evaluate the gap between the resulting strategy profile and the equilibrium strategy to assess performance.

---

Relevant papers

• Thank you for pointing out these relevant papers. Both papers address challenges in offline multi-agent settings and propose approaches tailored to specific aspects of equilibrium finding.

• Our BOMB explicitly combines behavior cloning (BC) and model-based (MB) approaches, leveraging their complementary strengths. This hybrid approach contrasts with the purely policy optimization-based frameworks in [1] and [2].

• While both [1] and [2] emphasize specific response oracle and policy evaluation techniques, our work investigates the balance between BC and MB approaches to produce effective approximate equilibria.

---

We hope our response can address your concerns, and we deeply appreciate that if you could reconsider the evaluation of our paper.

Dear Reviewer rVFL,

Thank you once again for your valuable review and reply.

As the author-reviewer discussion period is nearing its end, we would like to kindly ask if our responses have addressed your concerns. We have dedicated significant effort to preparing detailed, point-by-point responses to your questions. If our responses have adequately addressed your concerns, we would be grateful if you could reconsider the evaluation of our paper. However, if there are remaining issues or concerns that you feel we have not sufficiently addressed, we kindly ask for further clarification so that we can work on resolving them before the discussion period concludes.

We look forward to hearing from you. Thank you for your time and consideration.

Sincerely,

Authors of Submission 8885

Thank you for your valuable feedback. Below is our response to your concern:

---

Sample Complexity

• We appreciate your comments on the need for more explicit theoretical analysis. In Appendix D.2, we provide a generalization bound for the training error as a function of the dataset size $m$. Based on these results, it is possible to derive a lower bound for $m$ by setting the training error to a target value $\epsilon$. This analysis offers a quantification of the sample complexity within the scope of our theoretical framework.

---

We hope our response can address your concerns, and we deeply appreciate that if you could reconsider the evaluation of our paper.

Dear Reviewer PKQc,

Thank you once again for your valuable review.

As the author-reviewer discussion period is nearing its end, we would like to kindly ask if our responses have addressed your concerns. We are eager to address any additional feedback or unresolved concerns you may have before the discussion period concludes.

We look forward to hearing from you. Thank you for your time and consideration.

Sincerely,

Authors of Submission 8885