TL;DR
The paper introduces Iterated Pareto Referent Optimisation (IPRO), a novel algorithm that uncovers the Pareto front in multi-objective reinforcement learning (MORL) by breaking it down into a sequence of constrained single-objective subproblems. Crucially, IPRO provides mathematical guarantees for convergence and offers a strict upper bound on the distance to undiscovered optimal solutions at any point during its execution, even when dealing with non-convex Pareto fronts and deterministic policies.
What Problem Does This Paper Address?
In many real-world scenarios, reinforcement learning agents must balance multiple conflicting goals—such as maximizing a vehicle's speed while minimizing fuel consumption. Instead of producing a single optimal policy, Multi-Objective Reinforcement Learning (MORL) aims to find a set of optimal trade-offs known as the Pareto front.
When using stochastic policies or assuming a linear utility function, the Pareto front is safely convex, making it relatively easy to compute. However, in safety-critical fields like medicine or robotics, engineers heavily prefer deterministic policies because their behavior is predictable and interpretable. For deterministic policies, the Pareto front often contains concave (non-convex) regions. Existing algorithms either fail to capture these concave regions entirely or rely on restrictive assumptions (like purely deterministic environments).
Methods
The authors propose Iterated Pareto Referent Optimisation (IPRO), an anytime algorithm that systematically carves up the objective space to find the Pareto front.
Instead of searching for the entire front at once, IPRO uses a "divide and conquer" strategy:
- Bounding the Search Space: It defines a bounding box using the ideal point (the best possible score for each objective independently) and the nadir point (the worst expected optimal scores).
- The Pareto Oracle: IPRO repeatedly queries a single-objective solver (the "oracle") with a reference point (referent). The oracle's job is to find a policy that strictly outperforms this referent.
- Trimming the Space: If the oracle succeeds, the new policy's value vector is added to the Pareto front, and the space below it is marked as dominated. If it fails, that region is marked as infeasible.
- Smart Referent Selection: Rather than guessing where to query next, IPRO tracks the "inner corners" of the remaining unexplored space (defined as lower bounds $\mathcal{L}$ and upper bounds $\mathcal{U}$). This allows the algorithm to compute a precise upper bound on the remaining approximation error at any given step.
Dealing with Imperfect Deep RL Oracles
In theory, the oracle must be exact. In practice, deep RL algorithms (like DQN, A2C, or PPO) are heuristic function approximators that make mistakes. To bridge this gap, the authors introduce a backtracking procedure. If IPRO discovers a policy that dominates a region previously declared "infeasible," it backtracks, replays the history, corrects the mistake, and reuses prior computation efficiently.
Datasets
The authors evaluated IPRO across three standard MORL benchmarks:
- Deep Sea Treasure (DST) ($d=2$): A classic deterministic environment where a submarine collects treasure. It is explicitly designed to have a highly non-convex Pareto front, making it a primary testbed for non-convex optimization.
- Minecart ($d=3$): A stochastic environment where an agent collects two types of ore while minimizing fuel consumption. It features a convex Pareto front.
- MO-Reacher ($d=4$): A deterministic robotic arm environment scaled up to four objectives (minimizing distance to four different target balls).
Key Insights and Ideas
- The Power of Inner Corners: By focusing exclusively on the inner corners ($\mathcal{L}$ and $\mathcal{U}$) of the dominated and infeasible boundaries, IPRO reduces an infinite search space into a finite, manageable set of query points.
- Guaranteed Error Bounds: Because the upper bounds ($\mathcal{U}$) strictly enclose all remaining valid solutions, the algorithm can calculate exactly how far its current approximation is from the true Pareto front at any iteration.
- Algorithmic Agnosticism: IPRO treats the single-objective solver as a black box. This means any future breakthrough in standard single-objective RL can be instantly plugged into IPRO to improve multi-objective performance.
Key Results
The authors paired IPRO with deep RL backends (DQN, A2C, and PPO) and compared it against state-of-the-art convex hull methods (GPI-LS, Envelope Q-Learning) and a specialized Pareto front network (PCN).
- Conquering Non-Convexity: On Deep Sea Treasure, IPRO (paired with PPO or DQN) successfully recovered the entire non-convex Pareto front, achieving a minimum shift error ($\epsilon$) of 0.0. In contrast, convex hull methods naturally failed, leaving large portions of the front undiscovered.
- Robustness Across Environments: While specialized baselines like PCN performed well on the deterministic DST, they degraded in the stochastic Minecart environment. IPRO remained highly competitive across all environments without requiring domain-specific modifications.
Limitations and Future Work
The primary trade-off for IPRO's strong theoretical guarantees is sample complexity. Because IPRO is an iterative algorithm that discovers policies sequentially (one per iteration), it generally requires more environment samples than concurrent methods like PCN, which attempt to learn the entire front simultaneously.
Additionally, the authors noted that value-based oracles (like DQN) struggled to align perfectly with the scalarized objective function in higher dimensions ($d=4$).
Future Directions: The authors suggest extending IPRO to learn multiple Pareto-optimal policies concurrently within a single iteration to drastically reduce sample complexity while preserving its foundational convergence guarantees.
Summary updated