Elamur Research⌕
☰
home / papers / 2023 / Nash Learning from Human Feedback

Nash Learning from Human Feedback

Paper · 2023 · Remi Munos, Michal Valko, Daniele Calandriello et al.

Summary

Standard RLHF reduces pairwise human judgments to a scalar reward, typically through a Bradley-Terry model, and then optimizes the LLM against that score. The authors argue that this Elo-like scoring cannot express every kind of preference and depends heavily on the training data distribution. They propose Nash learning from human feedback (NLHF). It learns a preference model that scores a pair of responses to a prompt, then searches for the policy whose outputs win against any rival policy. This is the Nash equilibrium of a KL-regularized game, which they prove exists and is unique. For tabular policies they derive Nash-MD, a mirror-descent method whose final iterate reaches that equilibrium. It plays only against a geometric blend of the current and initial policies, so no stored checkpoint history is needed. Deep variants were tested on TL;DR summarization, with PaLM 2 Large judging pairwise comparisons that included an RLHF baseline. The experiments are framed as a feasibility demonstration rather than evidence of superiority. The work offers a principled alternative to reward-based alignment that makes fewer assumptions.

Key points

  • The preference model takes two responses plus a prompt and outputs the probability that one is preferred. It can be bootstrapped from LLM-generated (AI) feedback and refined on human data without any Bradley-Terry assumption.
  • Nash-MD has a last-iterate convergence guarantee in the tabular case. Regret-minimization approaches instead converge only as an average of past policies.
  • Nash-EMA is a fictitious-play-inspired variant that uses an exponential moving average of past parameters. Nash-MD-PG and Nash-EMA-PG are the policy-gradient versions for deep networks.
  • In the deep setting, the mixing coefficient β moves between pure self-play (β = 0) and playing against a fixed policy (β = 1). All NLHF runs shared the same hyperparameters, with no per-method tuning.
  • The work comes from Google DeepMind and was published at ICML 2024 (PMLR 235). It is related to IPO, whose online form approximates a special case of Nash-MD.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🔬Institut national de recherche en sciences et technologies du numériqueLe Chesnay-Rocquencourt · France90 works · 26,097 citations🔬Institut de Recherche en Informatique et Systèmes AléatoiresRennes · France9 works · 2,021 citations

Also on the byline: ENSAE Paris.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

Cite

Cite as Remi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, Marco Selvi, Sertan Girgin, Nikola Momchev, Olivier Bachem, Daniel J. Mankowitz, Doina Precup and Bilal Piot. 2023. Nash Learning from Human Feedback. arXiv:2312.00886.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2312.00886 · arXiv 2312.00886

@misc{munos2023nash,
  title = {{Nash Learning from Human Feedback}},
  author = {Remi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, Marco Selvi, Sertan Girgin, Nikola Momchev, Olivier Bachem, Daniel J. Mankowitz, Doina Precup and Bilal Piot},
  year = {2023},
  doi = {10.48550/arxiv.2312.00886},
  eprint = {2312.00886},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2312.00886}
}

References

84 references, 15 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Abernethy, J., Lai, K. A., Levy, K. Y., and Wang, J.-K. Faster rates for convex-concave games. In Proceedings of the Annual Conference on Learning Theory, 2018. find
  2. Bertrand, Q., Czarnecki, W. M., and Gidel, G. On the limitations of the Elo: Real-world games are transitive, not additive. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023. find
  3. Akrour, R., Schoenauer, M., and Sebag, M. Preference-based policy learning. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2011. find
  4. Bradley, R. A. and Terry, M. E. Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika, 39(3/4):324–345, 1952. find
  5. Amodei, D., Olah, C., Steinhardt, J., Christiano, P., Schulman, J., and Mané, D. Concrete problems in AI safety. arXiv, 2016.
  6. Brown, G. W. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374, 1951. find
  7. Bubeck, S. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4): 231–357, 2015. find
  8. Anil, R., Dai, A. M., Firat, O., Johnson, M., Lepikhin, D., Passos, A., Shakeri, S., Taropa, E., Bailey, P., Chen, Z., Chu, E., Clark, J. H., Shafey, L. E., Huang, Y., Meier-Hellstern, K., Mishra, G., Moreira, E., Omernick, M., Robinson, K., Ruder, S., Tay, Y., Xiao, K., Xu, Y., Zhang, Y., Abrego, G… find
  9. Busa-Fekete, R., Szörényi, B., Weng, P., Cheng, W., and Hüllermeier, E. Preference-based reinforcement learning: Evolutionary direct policy search using a preference-based racing algorithm. Machine Learning, 97(3):327– 351, 2014. find
  10. Busbridge, D., Ramapuram, J., Ablin, P., Likhomanenko, T., Dhekane, E. G., Suau, X., and Webb, R. How to scale your EMA. In Advances in Neural Information Processing Systems, 2023. find
  11. Calandriello, D., Guo, D., Munos, R., Rowland, M., Tang, Y., Pires, B. A., Richemond, P. H., Lan, C. L., Valko, M., Liu, T., Joshi, R., Zheng, Z., and Piot, B. Human alignment of large language models through online preference optimisation. arXiv, 2024. find
  12. Farina, G., Kroer, C., and Sandholm, T. Optimistic regret minimization for extensive-form games via dilated distance-generating functions. In Advances in Neural Information Processing Systems, 2019. find
  13. Fudenberg, D. and Levine, D. K. The Theory of Learning in Games. MIT Press, 1998. find
  14. Cesa-Biachi, N. and Lugosi, G. Predition, Learning, and Games. Cambridge University Press, 2006. find
  15. Gardner, M. The paradox of the nontransitive dice. Scientific American, (223):110–111, 1970. find
  16. Chen, X., Zhong, H., Yang, Z., Wang, Z., and Wang, L. Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation. In Proceedings of the International Conference on Machine Learning, 2022. find
  17. Geist, M., Scherrer, B., and Pietquin, O. A theory of regularized Markov decision processes. In Proceedings of the International Conference on Machine Learning, 2019. find
  18. Gidel, G., Jebara, T., and Lacoste-Julien, S. Frank-Wolfe algorithms for saddle point problems. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2016. find
  19. Cheng, W., Fürnkranz, J., Hüllermeier, E., and Park, S.-H. Preference-based policy iteration: Leveraging preference learning for reinforcement learning. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2011. find
  20. Glaese, A., McAleese, N., Trebacz, M., Aslanides, J., Firoiu, V., Ewalds, T., Rauh, M., Weidinger, L., Chadwick, M., Thacker, P., Campbell-Gillingham, L., Uesato, J., Huang, P.-S., Comanescu, R., Yang, F., See, A., Dathathri, S., Greig, R., Chen, C., Fritz, D., Elias, J. S., Green, R., Mokrá, S., F… — Improving alignment of dialogue agents via targeted human judgements
  21. Christiano, P., Leike, J., Brown, T. B., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, 2017. find
  22. Clopper, C. J. and Pearson, E. S. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404–413, 1934. find
  23. Grill, J.-B., Strub, F., Altché, F., Tallec, C., Richemond, P. H., Buchatskaya, E., Doersch, C., Pires, B. A., Guo, Z. D., Azar, M. G., Piot, B., Kavukcuoglu, K., Munos, R., and Valko, M. Bootstrap your own latent: A new approach to self-supervised learning. In Advances in Neural Information Proces… find
  24. Csiszar, I. and Korner, J. Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic Press, Inc., 1982. find
  25. Daskalakis, C. and Panageas, I. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In Proceedings of the Conference on Innovations in Theoretical Computer Science, 2019. find
  26. Gulcehre, C., Paine, T. L., Srinivasan, S., Konyushkova, K., Weerts, L., Sharma, A., Siddhant, A., Ahern, A., Wang, M., Gu, C., Macherey, W., Doucet, A., Firat, O., and de Freitas, N. Reinforced self-training (ReST) for language modeling, 2023.
  27. Daskalakis, C., Deckelbaum, A., and Kim, A. Near-optimal no-regret algorithms for zero-sum games. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2011. find
  28. Heinrich, J. and Silver, D. Deep reinforcement learning from self-play in imperfect-information games. arXiv, 2016. find
  29. Dong, H., Xiong, W., Goyal, D., Zhang, Y., Chow, W., Pan, R., Diao, S., Zhang, J., SHUM, K., and Zhang, T. RAFT: Reward rAnked FineTuning for generative foundation model alignment. Transactions on Machine Learning Research, 2023.
  30. Heinrich, J., Lanctot, M., and Silver, D. Fictitious self-play in extensive-form games. In Proceedings of the International Conference on Machine Learning, 2015. find
  31. Hennes, D., Morrill, D., Omidshafiei, S., Munos, R., Perolat, J., Lanctot, M., Gruslys, A., Lespiau, J. B., Parmas, P., Duéñez-Guzmán, E., and Tuyls, K. Neural replicator dynamics: Multiagent learning via hedging policy gradients. In Proceedings of the International Joint Conference on Autonomous… find
  32. Efroni, Y., Merlis, N., and Mannor, S. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021. find
  33. Elo, A. E. The Rating of Chessplayers, Past and Present. Arco Pub., 1978. find
  34. Hoda, S., Gilpin, A., Peña, J., and Sandholm, T. Smoothing techniques for computing Nash equilibria of sequential games. Mathematics of Operations Research, 35(2):494– 512, 2010. find
  35. Mokhtari, A., Ozdaglar, A., and Pattathil, S. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2020. find
  36. Hofbauer, J. and Sorin, S. Best response dynamics for continuous zero-sum games. Discrete and Continuous Dynamical Systems Series B, 6(1):215, 2006. find
  37. Moskovitz, T., Singh, A. K., Strouse, D., Sandholm, T., Salakhutdinov, R., Dragan, A. D., and McAleer, S. Confronting reward model overoptimization with constrained RLHF. arXiv, 2023. find
  38. Jacob, A. P., Farina, G., and Andreas, J. Regularized conventions: Equilibrium computation as a model of pragmatic reasoning. arXiv, 2023a.
  39. Munos, R., Perolat, J., Lespiau, J.-B., Rowland, M., De Vylder, B., Lanctot, M., Timbers, F., Hennes, D., Omidshafiei, S., Gruslys, A., Azar, M. G., Lockhart, E., and Tuyls, K. Fast computation of Nash equilibria in imperfect information games. In Proceedings of the International Conference on Machi… find
  40. Jacob, A. P., Shen, Y., Farina, G., and Andreas, J. The consensus game: Language model generation via equilibrium search, 2023b. find
  41. Jaques, N., Ghandeharioun, A., Shen, J. H., Ferguson, C., Lapedriza, A., Jones, N., Gu, S., and Picard, R. Way off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv, 2019. find
  42. Nakano, R., Hilton, J., Balaji, S., Wu, J., Ouyang, L., Kim, C., Hesse, C., Jain, S., Kosaraju, V., Saunders, W., Jiang, X., Cobbe, K., Eloundou, T., Krueger, G., Button, K., Knight, M., Chess, B., and Schulman, J. WebGPT: Browser-assisted question-answering with human feedback. arXiv, 2021.
  43. Kangarshahi, E. A., Hsieh, Y.-P., Sahin, M. F., and Cevher, V. Let’s be honest: An optimal no-regret framework for zero-sum games. In Proceedings of the International Conference on Machine Learning, 2018. find
  44. Nemirovski, A. and Yudin, D. Problem complexity and method efficiency in optimization. Wiley-Interscience Series in Discrete Mathematics, 1983. find
  45. Klimenko, A. Y. Intransitivity in theory and in the real world. Entropy, 17(6):4364–4412, 2015. find
  46. Nesterov, Y. Excessive gap technique in nonsmooth convex minimization. SIAM Journal on Optimization, 16(1): 235–249, 2005. find
  47. Korpelevich, G. The extragradient method for finding saddle points and other problems. Matecon, 12:747–756, 1976. find
  48. Novoseller, E., Wei, Y., Sui, Y., Yue, Y., and Burdick, J. Dueling posterior sampling for preference-based reinforcement learning. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2020. find
  49. Lattimore, T. and Szepesvári, C. Bandit Algorithms. Cambridge University Press, 2020. find
  50. Lee, H., Phatale, S., Mansoor, H., Lu, K., Mesnard, T., Bishop, C., Carbune, V., and Rastogi, A. RLAIF: Scaling reinforcement learning from human feedback with AI feedback. arXiv, 2023. find
  51. OpenAI. Introducing ChatGPT, 2022. URL https://openai.com/blog/chatgpt. ↗
  52. OpenAI. GPT-4 technical report. arXiv, 2023.
  53. Menick, J., Trebacz, M., Mikulik, V., Aslanides, J., Song, F., Chadwick, M., Glaese, M., Young, S., Campbell-Gillingham, L., Irving, G., and McAleese, N. Teaching language models to support answers with verified quotes. arXiv, 2022.
  54. Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. Training language models to follow instructions with… — Training language models to follow instructions with human feedback
  55. Mertikopoulos, P., Papadimitriou, C., and Piliouras, G. Cycles in adversarial regularized learning. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2018. find
  56. Pacchiano, A., Saha, A., and Lee, J. Dueling RL: Reinforcement learning with trajectory preferences. arXiv, 2023. find
  57. Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C., Chandrasekhar, V., and Piliouras, G. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In Proceedings of the International Conference on Learning Representations, 2019. find
  58. Perolat, J., Munos, R., Lespiau, J.-B., Omidshafiei, S., Rowland, M., Ortega, P., Burch, N., Anthony, T., Balduzzi, D., De Vylder, B., Piliouras, G., Lanctot, M., and Tuyls, K. From Poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In Proceed… — Factually Consistent Summarization via Reinforcement Learning with Textual Entailment Feedback
  59. Perolat, J., Vylder, B. D., Hennes, D., Tarassov, E., Strub, F., de Boer, V., Muller, P., Connor, J. T., Burch, N., Anthony, T., McAleer, S., Elie, R., Cen, S. H., Wang, Z., Gruslys, A., Malysheva, A., Khan, M., Ozair, S., Timbers, F., Pohlen, T., Eccles, T., Rowland, M., Lanctot, M., Lespiau, J.-B.… find
  60. Rosen, J. B. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica: Journal of the Econometric Society, pp. 520–534, 1965. find
  61. Ruppert, D. Efficient estimations from a slowly convergent Robbins–Monro process. Technical report, Cornell University Operations Research and Industrial Engineering, 1988. find
  62. Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv, 2017. find
  63. Polyak, B. T. New stochastic approximation type procedures. Automat. i Telemekh, 7(98-107):2, 1990. find
  64. Shani, L., Rosenberg, A., Cassel, A., Lang, O., Calandriello, D., Zipori, A., Noga, H., Keller, O., Piot, B., Szpektor, I., Hassidim, A., Matias, Y., and Munos, R. Multi-turn reinforcement learning from preference human feedback. arXiv, 2024. find
  65. Polyak, B. T. and Juditsky, A. B. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, 1992. find
  66. Rafailov, R., Sharma, A., Mitchell, E., Ermon, S., Manning, C. D., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. In Advances in Neural Information Processing Systems, 2023.
  67. Sion, M. On general minimax theorems. Pacific Journal of mathematics, 8(1):171–176, 1958. find
  68. Sokota, S., D’Orazio, R., Kolter, J. Z., Loizou, N., Lanctot, M., Mitliagkas, I., Brown, N., and Kroer, C. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. In Proceedings of the International Conference on Learning Representations, 2023. find
  69. Rakhlin, S. and Sridharan, K. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, 2013. find
  70. Rame, A., Couairon, G., Shukor, M., Dancette, C., Gaya, J.-B., Soulier, L., and Cord, M. Rewarded soups: Towards Pareto-optimal alignment by interpolating weights fine-tuned on diverse rewards. In Advances in Neural Information Processing Systems, 2023.
  71. Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F. Learning to summarize with human feedback. In Advances in Neural Information Processing Systems, 2020. find
  72. Roberts, A., Chung, H. W., Levskaya, A., Mishra, G., Bradbury, J., Andor, D., Narang, S., Lester, B., Gaffney, C., Mohiuddin, A., Hawthorne, C., Lewkowycz, A., Salcianu, A., van Zee, M., Austin, J., Goodman, S., Soares, L. B., Hu, H., Tsvyashchenko, S., Chowdhery, A., Bastings, J., Bulian, J., Garci… find
  73. Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems, 2015. find
  74. Tang, Y., Guo, Z. D., Zheng, Z., Calandriello, D., Munos, R., Rowland, M., Richemond, P. H., Valko, M., Ávila Pires, B., and Piot, B. Generalized preference optimization: A unified approach to offline alignment, 2024. find
  75. Tversky, A. Intransitivity of preferences. Psychological Review, 76(1):31–48, 1969. find
  76. Völske, M., Potthast, M., Syed, S., and Stein, B. TL;DR: Mining Reddit to learn automatic summarization. In Proceedings of the Workshop on New Frontiers in Summarization. Association for Computational Linguistics, 2017.
  77. Robinson, J. An iterative method of solving a game. Annals of Mathematics, 54(2):296–301, 1951. find
  78. Roit, P., Ferret, J., Shani, L., Aharoni, R., Cideron, G., Dadashi, R., Geist, M., Girgin, S., Hussenot, L., Keller, O., Momchev, N., Ramos, S., Stanczyk, P., Vieillard, N., Bachem, O., Elidan, G., Hassidim, A., Pietquin, O., von Neumann, J. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen… find
  79. Wang, Y., Liu, Q., and Jin, C. Is RLHF more difficult than standard RL? In Advances in Neural Information Processing Systems, 2023. find
  80. Wilson, A., Fern, A., and Tadepalli, P. A Bayesian approach for policy learning from trajectory preference queries. In Advances in Neural Information Processing Systems, 2012. find
  81. Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, J. A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(136): 1–46, 2017. find
  82. Wortsman, M., Ilharco, G., Gadre, S. Y., Roelofs, R., Gontijo-Lopes, R., Morcos, A. S., Namkoong, H., Farhadi, A., Carmon, Y., Kornblith, S., and Schmidt, L. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. In Proceedings of the Intern…
  83. Zhao, Y., Joshi, R., Liu, T., Khalman, M., Saleh, M., and Liu, P. J. SLiC-HF: Sequence likelihood calibration with human feedback. In Proceedings of the International Conference on Learning Representations, 2023.
  84. Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. Regret minimization in games with incomplete information. In Advances in Neural Information Processing Systems, 2007. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/munos-2023-nash-learning-human-feedback/