# Multi-Step Alignment as Markov Games: An Optimistic Online Gradient Descent Approach with Convergence Guarantees

arXiv: https://arxiv.org/abs/2502.12678 · HTML: https://mlsanity.com/paper/2502.12678/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 46 of its 73 references that are in the map.
- First posted on arXiv 18 Feb 2025.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 30 of 46)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [SimPO: Simple Preference Optimization with a Reference-Free Reward](https://mlsanity.com/paper/2405.14734/) (2024)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [MetaMath: Bootstrap Your Own Mathematical Questions for Large Language Models](https://mlsanity.com/paper/2309.12284/) (2023)
- [ORPO: Monolithic Preference Optimization without Reference Model](https://mlsanity.com/paper/2403.07691/) (2024)
- [Step-DPO: Step-wise Preference Optimization for Long-chain Reasoning of LLMs](https://mlsanity.com/paper/2406.18629/) (2024)
- [RLHF Workflow: From Reward Modeling to Online RLHF](https://mlsanity.com/paper/2405.07863/) (2024)
- [MT-Bench-101: A Fine-Grained Benchmark for Evaluating Large Language Models in Multi-Turn Dialogues](https://mlsanity.com/paper/2402.14762/) (2024)
- [From r to Q^*: Your Language Model is Secretly a Q-Function](https://mlsanity.com/paper/2404.12358/) (2024)
- [Self-Play Preference Optimization for Language Model Alignment](https://mlsanity.com/paper/2405.00675/) (2024)
- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences](https://mlsanity.com/paper/2404.03715/) (2024)
- [Generalized Preference Optimization: A Unified Approach to Offline Alignment](https://mlsanity.com/paper/2402.05749/) (2024)
- [A Minimaximalist Approach to Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2401.04056/) (2024)
- [Token-level Direct Preference Optimization](https://mlsanity.com/paper/2404.11999/) (2024)
- [Taming the Noise in Reinforcement Learning via Soft Updates](https://mlsanity.com/paper/1512.08562/) (2015)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)

## Built on by (most cited first, 3 of 3)

- [Improving LLM General Preference Alignment via Optimistic Online Mirror Descent](https://mlsanity.com/paper/2502.16852/) (2025)
- [Proximal Point Nash Learning from Human Feedback](https://mlsanity.com/paper/2505.19731/) (2025)
- [Asymptotic Universal Alignment: A New Alignment Framework via Test-Time Scaling](https://mlsanity.com/paper/2601.08777/) (2026)

## Abstract (arXiv)

Reinforcement Learning from Human Feedback (RLHF) has been highly successful in aligning large language models with human preferences. While prevalent methods like DPO have demonstrated strong performance, they frame interactions with the language model as a bandit problem, which limits their applicability in real-world scenarios where multi-turn conversations are common. Additionally, DPO relies on the Bradley-Terry model assumption, which does not adequately capture the non-transitive nature of human preferences. In this paper, we address these challenges by modeling the alignment problem as a two-player constant-sum Markov game, where each player seeks to maximize their winning rate against the other across all steps of the conversation. Our approach Optimistic Multi-step Preference Optimization (OMPO) is built upon the optimistic online mirror descent algorithm~citeprakhlin2013online,joulani17a. Theoretically, we provide a rigorous analysis for the convergence of OMPO and show that OMPO requires O(ε-1) policy updates to converge to an ε-approximate Nash equilibrium. We also validate the effectiveness of our method on multi-turn conversations dataset and math reasoning dataset.