# Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 34 of its 95 references that are in the map.
- First posted on arXiv 24 Jul 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

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

- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Multi-Task Learning as Multi-Objective Optimization](https://mlsanity.com/paper/1810.04650/) (2018)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Conflict-Averse Gradient Descent for Multi-task Learning](https://mlsanity.com/paper/2110.14048/) (2021)
- [Just Pick a Sign: Optimizing Deep Multitask Models with Gradient Sign Dropout](https://mlsanity.com/paper/2010.06808/) (2020)
- [A Generalized Algorithm for Multi-Objective Reinforcement Learning and Policy Adaptation](https://mlsanity.com/paper/1908.08342/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Rewards-in-Context: Multi-objective Alignment of Foundation Models with Dynamic Preference Adjustment](https://mlsanity.com/paper/2402.10207/) (2024)
- [Arithmetic Control of LLMs for Diverse User Preferences: Directional Preference Alignment with Multi-Objective Rewards](https://mlsanity.com/paper/2402.18571/) (2024)
- [Beyond One-Preference-Fits-All Alignment: Multi-Objective Direct Preference Optimization](https://mlsanity.com/paper/2310.03708/) (2023)
- [Controllable Preference Optimization: Toward Controllable Multi-Objective Alignment](https://mlsanity.com/paper/2402.19085/) (2024)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Panacea: Pareto Alignment via Preference Adaptation for LLMs](https://mlsanity.com/paper/2402.02030/) (2024)
- [Conservative Data Sharing for Multi-Task Offline Reinforcement Learning](https://mlsanity.com/paper/2109.08128/) (2021)
- [Smooth Tchebycheff Scalarization for Multi-Objective Optimization](https://mlsanity.com/paper/2402.19078/) (2024)
- [Revisiting Scalarization in Multi-Task Learning: A Theoretical Perspective](https://mlsanity.com/paper/2308.13985/) (2023)
- [Scaling Pareto-Efficient Decision Making Via Offline Multi-Objective RL](https://mlsanity.com/paper/2305.00567/) (2023)
- [Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance](https://mlsanity.com/paper/2305.20057/) (2023)
- [Direction-oriented Multi-objective Learning: Simple and Provable Stochastic Algorithms](https://mlsanity.com/paper/2305.18409/) (2023)
- [Online Primal-Dual Mirror Descent under Stochastic Constraints](https://mlsanity.com/paper/1908.00305/) (2019)
- [A Simple Reward-free Approach to Constrained Reinforcement Learning](https://mlsanity.com/paper/2107.05216/) (2021)
- [On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL](https://mlsanity.com/paper/2206.10770/) (2022)
- [Promptable Behaviors: Personalizing Multi-Objective Rewards from Human Preferences](https://mlsanity.com/paper/2312.09337/) (2023)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Multi-objective Contextual Bandit Problem with Similarity Information](https://mlsanity.com/paper/1803.04015/) (2018)
- [Multi-Objective Generalized Linear Bandits](https://mlsanity.com/paper/1905.12879/) (2019)
- [Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2206.05357/) (2022)
- [Choosing the Best of Both Worlds: Diverse and Novel Recommendations through Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2110.15097/) (2021)
- [Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs](https://mlsanity.com/paper/2303.10859/) (2023)
- [Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2210.00701/) (2022)

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

- [Multi-objective Large Language Model Alignment with Hierarchical Experts](https://mlsanity.com/paper/2505.20925/) (2025)
- [Rethinking Diverse Human Preference Learning through Principal Component Analysis](https://mlsanity.com/paper/2502.13131/) (2025)
- [How to Find the Exact Pareto Front for Multi-Objective MDPs?](https://mlsanity.com/paper/2410.15557/) (2024)
- [Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation](https://mlsanity.com/paper/2608.04333/) (2026)
- [A Reward-Free Viewpoint on Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2604.24532/) (2026)
- [Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits](https://mlsanity.com/paper/2608.04324/) (2026)
- [A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization](https://mlsanity.com/paper/2605.09094/) (2026)
- [Enabling Pareto-Stationarity Exploration in Multi-Objective Reinforcement Learning: A Multi-Objective Weighted-Chebyshev Actor-Critic Approach](https://mlsanity.com/paper/2507.21397/) (2025)
- [Quality-Diversity Optimization as Multi-Objective Optimization](https://mlsanity.com/paper/2602.00478/) (2026)
- [Pareto-Optimal Offline Reinforcement Learning via Smooth Tchebycheff Scalarization](https://mlsanity.com/paper/2604.13175/) (2026)
- [Contextual Multi-Objective Optimization: Rethinking Objectives in Frontier AI Systems](https://mlsanity.com/paper/2605.03900/) (2026)
- [Adaptive Smooth Tchebycheff Attention for Multi-Objective Policy Optimization](https://mlsanity.com/paper/2605.12771/) (2026)
- [SURF: Steering the Scalarization Weight to Uniformly Traverse the Pareto Front](https://mlsanity.com/paper/2605.20619/) (2026)
- [On Generalizing Preference-based Reinforcement Learning to Multi-Objective Problems](https://mlsanity.com/paper/2607.11432/) (2026)
- [Few-for-Many Best-Arm Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2610.16840/) (2026)

## Abstract (arXiv)

This paper investigates multi-objective reinforcement learning (MORL), which focuses on learning Pareto optimal policies in the presence of multiple reward functions. Despite MORL's significant empirical success, there is still a lack of satisfactory understanding of various MORL optimization targets and efficient learning algorithms. Our work offers a systematic analysis of several optimization targets to assess their abilities to find all Pareto optimal policies and controllability over learned policies by the preferences for different objectives. We then identify Tchebycheff scalarization as a favorable scalarization method for MORL. Considering the non-smoothness of Tchebycheff scalarization, we reformulate its minimization problem into a new min-max-max optimization problem. Then, for the stochastic policy class, we propose efficient algorithms using this reformulation to learn Pareto optimal policies. We first propose an online UCB-based algorithm to achieve an varepsilon learning error with an tildeO(varepsilon-2) sample complexity for a single given preference. To further reduce the cost of environment exploration under different preferences, we propose a preference-free framework that first explores the environment without pre-defined preferences and then generates solutions for any number of preferences. We prove that it only requires an tildeO(varepsilon-2) exploration complexity in the exploration phase and demands no additional exploration afterward. Lastly, we analyze the smooth Tchebycheff scalarization, an extension of Tchebycheff scalarization, which is proved to be more advantageous in distinguishing the Pareto optimal policies from other weakly Pareto optimal policies based on entry values of preference vectors. Furthermore, we extend our algorithms and theoretical analysis to accommodate this optimization target.