Deterministic Pareto-Optimal Policy Synthesis for Multi-Objective Reinforcement Learning
June 24, 2026
Abstract
Real-world decision-making often requires balancing multiple conflicting objectives, a challenge that standard Reinforcement Learning (RL) frequently addresses by aggregating rewards into a single scalar signal. While effective for simple tasks, this approach often fails to capture the full spectrum of optimal trade-offs, known as the Pareto frontier. In this paper, we introduce a novel preference-conditioned Bellman operator, motivated from the Chebyshev scalarization, designed to compute deterministic Pareto-optimal policies for Multi-Objective Markov Decision Processes (MOMDPs). We prove that this operator satisfies an enveloping property, where the estimated value functions upper-bound the true Pareto frontier, and demonstrate that it monotonically converges to a coverage set of this frontier. Furthermore, we also show how to extract deterministic policies from these converged Q-estimates. This ensures the agent can recover a policy for any given preference, capturing the entire Pareto-optimal frontier while guaranteeing each synthesized policy remains approximately Pareto-optimal. Experimental results validate that our algorithm successfully recovers complex trade-offs, providing a solution for deterministic Pareto-optimal policy synthesis.
1 Introduction↩︎
Many real-world decision-making problems are inherently multi-objective: practitioners must balance competing criteria rather than optimize a single scalar notion of performance, and the relevant trade-offs vary across users and operating regimes.
This is evident across a wide range of domains, including circuit design (power, performance, area, reliability) [1]–[4]; distributed computing (energy, latency, throughput) [5], [6]; drug and molecule design (efficacy, toxicity, synthesizability) [7]; recommender systems (accuracy, diversity, fairness) [8]; robotics (speed, safety, energy) [9]; satellite communications (throughput, delay, power) [10]; control (tracking, robustness, effort) [11]; and mechanical design (weight, strength, manufacturability) [12]. Reinforcement learning (RL) is increasingly used as a general optimization, control, and exploration mechanism in such settings, but standard RL typically assumes a single reward signal [13]. When multiple objectives are present, practitioners commonly apply scalarisation techniques (e.g., hand-tuned weighted sums) to collapse them into a single objective; while convenient, this can eliminate important trade-offs and may yield policies that perform well on average but fail to satisfy critical preferences in specific scenarios. These limitations motivate a truly multi-objective approach: multi-objective reinforcement learning (MORL), which seeks to learn the full set of Pareto-optimal solutions.
In this work, we introduce a novel Bellman operator parameterized by preference weights. This formulation allows us to obtain a deterministic Pareto-optimal policy corresponding to any desired trade-off. We provide a proof of the operator’s convergence, while guaranteeing that the extracted policies approximately cover the entire Pareto frontier and are individually approximately Pareto-optimal. Further we empirically demonstrate that, our procedure can retrieve the complete Pareto frontier.
The main contributions of this work are as follows:
We introduce a model-based Bellman operator parameterized by preferences, leveraging Chebyshev scalarization. We derive its error bounds and prove that it converges asymptotically to the Pareto-optimal values for deterministic, non-stationary policies in MOMDPs.
From these converged Q-estimates, we demonstrate how to extract deterministic policies requiring only a single-step transition memory. We prove that this approach yields a policy set that covers the Pareto frontier while guaranteeing that each recovered policy is approximately non-dominated within the space of all non-stationary deterministic policies.
We provide empirical evidence demonstrating that our algorithm successfully converges to the Pareto frontier, capturing all trade-offs and recovers a set of deterministic Pareto-optimal policies for all of them.
The remainder of this paper is organized as follows. Section 2 reviews related literature. Section 3 introduces the Multi-Objective Markov Decision Process framework and defines the problem of synthesizing a Pareto coverage set. Section 4 introduces Chebyshev scalarization as our core optimization mechanism, provides geometric intuition for this operator, and proves that a norm-maximization tie-breaking rule yields a necessary and sufficient condition for exactly characterizing the Pareto frontier. Section 5 details our novel, preference-aware Bellman update, while Section 6 outlines the resulting deterministic policy synthesis algorithm. Section 7 validates the convergence and coverage capabilities of our approach through empirical experiments. Finally, Section 8 concludes the paper and outlines directions for future work.
2 Related Work↩︎
We contextualize our contributions within three primary paradigms of Multi-Objective Reinforcement Learning: linear scalarization, preference-based learning, and explicit set maintenance. While comprehensive surveys provide a broader view [14]–[16], we focus on these specific categories to highlight a fundamental challenge: the difficulty of efficiently obtaining deterministic policies that cover the full Pareto frontier while maintaining rigorous convergence guarantees.
Linear Scalarization. A common approach to MORL involves reducing the vector-valued reward to a scalar via a weighted sum. This technique has been applied across diverse domains, including manufacturing [17], hydroelectric control [18], energy management [19], and grid computing [20], alongside the development of specialized algorithms for this setting [21]–[23]. However, linear scalarization is fundamentally restricted to recovering solutions on the convex coverage set of the Pareto frontier, failing to identify optimal trade-offs in non-convex regions common in complex real-world tasks [14], [24], [25].
Preference-Based Approaches. These methods generalize linear scalarization by parameterizing the value function with a vector of weights. The weighted Chebyshev scalarization, originally characterized by Bowman [26], has demonstrated empirical success in multi-objective evolutionary algorithms [27]. In the MORL context, [28] utilize this metric to learn multiple policies, performing weight sweeps (fixing specific weights) to approximate the Pareto curve. Similarly, Reymond et al. [29] extend these concepts using neural network approximations of Pareto-optimal Q-values.
Our work builds upon this foundation by defining a preference space and estimating Q-values parameterized by these preferences. However, unlike methods that fix scalarization weights to learn separate policies, we integrate the preference vector directly into the learning process. This Bellman operator allows the policy to dynamically optimize against varying preferences recursively, resulting in a single succinct representation parameterized by the weights. Furthermore, we provide a proof of asymptotic convergence to deterministic Pareto-optimal policies.
Modern approaches [30]–[33] focus on maintaining explicit sets of Pareto-optimal estimates. However, extracting a policy to achieve a specific Pareto-optimal value from these sets presents a fundamental challenge: alignment consistency. In these settings, the value of a state is represented by a set of vectors, each corresponding to a distinct optimal trade-off. To execute a policy, an agent must effectively select a target trade-off vector from the current state’s set. Crucially, this choice imposes a strict constraint on the subsequent step: to realize the chosen trade-off, the agent must identify and select the specific corresponding vector from the set of estimates at the next state that contributed to the current value. In contrast to scalar RL, where a greedy maximization over a single value suffices, the MORL agent must maintain this specific alignment across the trajectory. If the agent fails to align the next-state selection with the previous state’s trade-off target, the global policy becomes suboptimal. As highlighted in [31] and [34], arbitrarily selecting any trade-off without ensuring this alignment breaks the optimality chain. Consequently, these methods rely on heuristic action selection mechanisms that lack formal guarantees, and thus the executed policy is not guaranteed to realize the target Pareto-optimal value.
Our approach addresses these limitations simultaneously. First, by parameterizing the value function with preferences, we eliminate the need for an explicit set representation, making our method amenable to standard function approximation. Second, we establish asymptotic convergence guarantees for the estimates similar to those of White [35]; however, we obtain policies without the computationally intractable requirement of storing action histories. Instead, we resolve the alignment consistency problem efficiently: our procedure dynamically determines the preference for the subsequent state based on the selected action and current preference. This mechanism allows us to recover non-stationary, deterministic Pareto-optimal policies by simply changing the local preference parameter over the rollout, and we further prove convergence of our policy to the frontier.
Explicit Set-Based Approaches. Works by White [35] established that generating the complete Pareto frontier using deterministic policies requires non-stationary behavior, as stationary policies may be dominated in multi-objective settings. White proposed a Bellman update operating on sets of estimates and established value convergence (a proof later revised by Mifrani [36]). However, retrieving the corresponding policy requires storing the entire history of actions across all updates (\(n\) steps) and may scale exponentially. As noted by [37], this memory requirement is computationally infeasible. To circumvent this, algorithms like CON-MODP [37] restrict the search space to stationary policies, thereby sacrificing the ability to recover the Pareto frontier.
3 Preliminaries and Problem Formulation↩︎
In this section, we formalize the problem of synthesizing a complete and parsimonious set of Pareto-optimal policies. We first introduce the necessary preliminaries and definitions.
Definition 1 (Multi-Objective Markov Decision Process (MOMDP)). A Multi-Objective Markov Decision Process (MOMDP) is a tuple \(\mathcal{M} := (S, A, T, \gamma, s_0, R)\), where \(S\) is a set of states, \(A\) is a set of actions, \(T: S \times A \times S \rightarrow [0,1]\) is a probabilistic transition function, \(\gamma \in [0,1)\) is a discount factor, \(s_0\in S\) is the initial state, and \(R: S \times A \rightarrow \mathbb{R}^d_{\geq 0}\) is a \(\boldsymbol{d}\)-dimensional vector-valued reward.
Example 1.
Consider the MOMDP with 2-dimensional rewards illustrated in Figure 2. As an example, executing action \(a_1\) from the initial state \(s_0\) produces the reward \(\bigl(\begin{smallmatrix} 1.0 \\ 0.5 \end{smallmatrix}\bigr)\in \mathbb{R}^2_{\ge 0}\) and transitions to state \(s_1\).
We focus on deterministic policies \(\pi\) that map a state-action history \(h_t\) and the current state \(s \in S\) to an action \(a \in A\). We denote the action selected at state \(s\) given history \(h_t\) by \(\pi(s \mid h_t)\), and the induced future policy by \(\pi(\cdot \mid h_t)\).
Let \(\Delta(S)\) denote the set of probability distributions over \(S\). For an initial state distribution \(\mathcal{I} \in \Delta(S)\), the Value Function (or value vector) \(\mathbf{V}^\pi(\mathcal{I}) \in \mathbb{R}^d_{\geq 0}\) is the expected discounted return obtained by executing policy \(\pi\): \[\mathbf{V}^\pi(\mathcal{I}) = \mathbb{E}_{s_0 \sim \mathcal{I}, \pi} \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \right]\]
Example 2. In the MOMDP (Figure 2), action choices affect transitions and rewards only at states \(s_0\) and \(s_1\); at states \(s_2\), \(s_3\), and \(s_4\), the outcomes are independent of the action chosen. This results in four distinct deterministic policies, corresponding to the action pairs \(\pi_1=(a_1, a_1)\), \(\pi_2=(a_1, a_2)\), \(\pi_3=(a_2, a_1)\), and \(\pi_4=(a_2, a_2)\), where the first and second components denote the actions taken at states \(s_0\) and \(s_1\) regardless of the history. These policies yield the value vectors \((2,3)\), \((2,1)\), \((3,2)\), and \((3,1)\), respectively (see Figure 3).
Notation. Let \(\Pi\) denote the set of deterministic policies. For vectors \(u, v \in \mathbb{R}^d_{\geq 0}\), \(u\) weakly dominates \(v\) (\(v \preceq u\)) if \(u_i \geq v_i\) for all \(i\), and strictly dominates (\(v \prec u\)) if \(v \preceq u\) and \(u \neq v\). We use the shorthand \(V^\pi(s)\) to denote the value of policy \(\pi\) starting from state \(s\). Let \(\overline{\mathbf{1}}\) denote a \(d\)-dimensional vector of all ones. Assuming a maximum component-wise reward \(R_{\max}\in \mathbb{R}_{\geq 0}\), all value vectors are bounded by \(\mathcal{R} := \frac{R_{\max}}{1-\gamma}\overline{\mathbf{1}}\).
We note that two vectors \(u, v \in \mathbb{R}^d_{\geq 0}\) are incomparable if neither \(u \preceq v\) nor \(v \preceq u\). This occurs if and only if there exist indices \(i\) and \(j\) such that \(u_i < v_i\) and \(u_j > v_j\).
A policy \(\pi \in \Pi\) is Pareto-optimal (PO) if it is not strictly dominated by any other policy; formally, there exists no \(\pi' \in \Pi\) such that \(V^\pi(s_0) \prec V^{\pi'}(s_0)\).1 The set of such policies, denoted \(\Pi^{PO}\), represents the trade-offs where no objective can be improved without sacrificing another.
Example 3. Figure 3 illustrates the value vectors for the four policies: \(\pi_1\) and \(\pi_3\) are Pareto-optimal, whereas \(\pi_2\) is dominated by \(\pi_1\) (\(V^{\pi_2}(s_0) \preceq V^{\pi_1}(s_0)\)) and \(\pi_4\) is dominated by \(\pi_3\) (\(V^{\pi_4}(s_0) \preceq V^{\pi_3}(s_0)\)). Furthermore, policies \(\pi_1\) and \(\pi_3\) are incomparable, as neither of their value vectors dominates the other.
Since multiple policies may yield identical value vectors, \(\Pi^{PO}\) can contain redundant policies. We therefore seek a Pareto Coverage Set \(\mathcal{C}_{PO} \subseteq \Pi^{PO}\) that serves as a representative subset capable of characterizing the entire frontier of optimal values without the redundancy of the full policy space; formally, \(\forall \pi \in \Pi^{PO}, \exists \pi' \in \mathcal{C}_{PO}\) such that \(V^{\pi'}(s_0) = V^{\pi}(s_0)\).
Identifying such a set \(\mathcal{C}_{PO}\) is non-trivial and motivates our problem definition to synthesize a parsimonious policy set that satisfies coverage:
Given a Multi-Objective Markov Decision Process \(M=(S,A,T,\gamma,s_0,R)\), synthesize a Pareto coverage set \(\mathcal{C}_{PO} \subseteq \Pi^{PO}\) that satisfies the following conditions:
Coverage: Every Pareto-optimal policy is represented by a policy in the set \(\mathcal{C}_{PO}\):
\(\forall \pi \in \Pi^{PO}, \exists \pi' \in \mathcal{C}_{PO} \text{ such that }\)
\(V^{\pi}(s_0) = V^{\pi'}(s_0)\)
Parsimony: Every policy in the coverage set is itself Pareto-optimal: \(\forall \pi' \in \mathcal{C}_{PO}, \exists \pi \in \Pi^{PO} \text{ such that }\)
\(V^{\pi'}(s_0) = V^{\pi}(s_0)\)
Since value functions are defined as the limits of infinite sums, evaluating them exactly may not be practically possible without truncating after a finite horizon. To account for the inherent error of this truncation, we relax the exact equality constraints and define the \(\epsilon\)-CAPS problem as follows:
Given a Multi-Objective Markov Decision Process \(M=(S,A,T,\gamma,s_0,R)\) and an \(\epsilon \in \mathbb{R}_{> 0}\), synthesize an approximate Pareto coverage set \(\mathcal{C}^{\epsilon}_{PO}\) that satisfies the following conditions:
Approximate Coverage: Every Pareto-optimal policy is approximately dominated by a policy in the approximate coverage set \(\mathcal{C}^\epsilon_{PO}\):
\(\forall \pi \in \Pi^{PO}, \exists \pi' \in \mathcal{C}^\epsilon_{PO} \text{ such that }\)
\(V^{\pi}(s_0) \preceq V^{\pi'}(s_0) + \epsilon \overline{\mathbf{1}}\)
Approximate Parsimony: Every policy in the approximate coverage set is itself approximately Pareto-optimal: \(\forall \pi' \in \mathcal{C}^\epsilon_{PO}, \exists \pi \in \Pi^{PO} \text{ such that }\)
\(V^{\pi'}(s_0) \preceq V^{\pi}(s_0) + \epsilon \overline{\mathbf{1}}\)
Given a small margin \(\epsilon > 0\), the approximate coverage property ensures that the value of every Pareto-optimal policy is weakly dominated by the value of a policy in \(\mathcal{C}_{PO}^\epsilon\), up to an additive factor of \(\epsilon\) across all components. Similarly, the approximate parsimony property guarantees that every policy in \(\mathcal{C}_{PO}^\epsilon\) is weakly dominated by an actual Pareto-optimal policy, up to the same \(\epsilon\) margin.
To solve the \(\epsilon\)-CAPS problem, we next introduce an additional parameter called a preference. Optimizing for a specific preference yields an approximately Pareto-optimal policy; consequently, systematically varying this preference allows us to construct the full approximate Pareto coverage set \(\mathcal{C}_{PO}^\epsilon\).
Our approach proceeds in two main steps. First, assuming a known probabilistic model of the system, we introduce a Bellman update procedure and prove that the resulting Q-value estimates converge arbitrarily close to the true Pareto-optimal values. Second, we demonstrate how to extract a history-independent policy \(\pi\) from these Q-estimates. This independence relies on a core property we establish regarding greedy Pareto-optimal policies: there exist deterministic, Pareto-optimal policies where, upon taking action \(a\) in state \(s\) and transitioning to \(s'\), the subsequent behavior perfectly matches another deterministic Pareto-optimal policy originating from \(s'\). Consequently, instead of storing the full execution history \(h_t\), we can greedily select actions by dynamically updating the preference parameter based solely on the most recent state transition.
4 Preference-Based Chebyshev Scalarization↩︎
A common approach to solving the Pareto-optimal policy synthesis problem in MOMDPs is via scalarization. In this framework, a non-negative, unit-normalized preference vector encodes the relative importance of the objectives, and a scalarization function maps vector-valued returns to scalar values. For each preference vector, this yields a distinct single-objective optimization problem, whose solution corresponds to a policy tailored to that preference. Solving these problems over a collection of preference vectors produces a set of policies that characterize the Pareto frontier. Our approach builds on this idea; we next formally define the preference space and the Chebyshev scalarization function.
Definition 2 (Preference Space). We define the preference space \(\mathcal{W}\) as the set of all non-negative, unit-normalized weight vectors: \[\mathcal{W} := \Big\{ w \in \mathbb{R}^d_{\geq 0} \;\Big|\; \|w\|_2 = 1,\; w_i \ge 0,\; \forall i = 1,\dots,d \Big\}.\] We refer to any vector \(w \in \mathcal{W}\) as a preference. Conceptually, each component \(w_i\) acts as a weight assigned to the \(i\)-th objective, representing its relative importance.
Definition 3 (Chebyshev Scalarization). Let \(\mathcal{W}\) be the preference space. The Weighted Chebyshev scalarization is a function \(O: \mathcal{W} \times \mathbb{R}^d_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}\) that maps a preference vector \(w\in \mathcal{W}\) and a value vector \(V\in \mathbb{R}^d_{\geq 0}\) to a non-negative scalar score in \(\mathbb{R}_{\geq 0}\). It is defined as: \[O(w, V) := \min_{i : w_i > 0} \left( \frac{V_i}{w_i} \right)\]
For a fixed preference vector \(w \in \mathcal{W}\), we write \(O_w(V) := O(w, V)\) to denote the Chebyshev scalarization induced by the preference \(w\).
Geometric Intuition. Geometrically, the weighted Chebyshev operator \(O(w,V)\) identifies the largest scale factor \(\alpha \geq 0\) such that the vector \(\alpha w\) remains weakly dominated by \(V\). It measures how far a ray originating from the origin in the direction of \(w\) can extend before it is constrained by the components of \(V\) (illustrated in Figure 1). This relationship is formalized by the optimization: \[\max \alpha \quad \text{ subject to } \quad \alpha w \preceq V\] The constraint \(\alpha w \preceq V\) requires that \(\alpha w_i \leq V_i\) for all \(i\). Consequently, the optimization simplifies to \(\alpha \leq \min\limits_{i : w_i > 0} \left( \frac{V_i}{w_i} \right)\). Thus, the resulting scalar value is determined strictly by the \(i\)-th bottleneck component that produces this minimum ratio. This component represents the first coordinate of \(V\) that restricts the scaling along the ray.
We note that for a fixed preference \(w\), multiple distinct value vectors (including those that are strictly dominated) may yield the exact same scalar score. Because the operator is sensitive only to the limiting bottleneck component, increasing any non-bottleneck objective \(V_j\) does not change the resulting value. This phenomenon, where an improvement in one objective is not reflected in the scalarization, is illustrated in Example 4 below.
Example 4. Consider four policies \(\pi_1,\ldots\pi_4\) with value vectors \(V^1=(2,3)\), \(V^2=(2,1)\), \(V^3=(3,2)\), and \(V^4=(3,1)\), as shown in Figure 3. Suppose we have a preference vector \(w=\frac{(3,0.5)}{\|(3,0.5)\|_2}\). For both \(V^3\) and \(V^4\), the first objective is the bottleneck since: \(\frac{V^3_1}{w_1}=\frac{V^4_1}{w_1}=\|(3,0.5)\|_2\). While \(V^3\) strictly dominates \(V^2\) (since \(2>1\) in the second objective), both yield the same scalarized value: \(O_w(V^3)=O_w(V^4)=\|(3,0.5)\|_2\). Consequently, an optimizer using this preference \(w\) would be indifferent between the two. However, for a different preference \(w'=\frac{(2,1)}{\|(2,1)\|}\), the bottleneck shifts, and only \(V^3\) would remain as the maximum.
While Example 4 highlights the operator’s indifference between specific value vectors, it also suggests that for any preference direction \(w\), there exists a limit to how far the ray \(\alpha w\) can extend within the space of achievable outcomes. We formalize this boundary in Definition 4.
Definition 4 (Pareto Performance Frontier (PPF)). Let \(\mathcal{V} \subset \mathbb{R}_{\geq 0}^d\) be the set of all achievable value vectors, such that \(\mathcal{V} \neq \{\boldsymbol{0}\}\). Let \(\mathcal{V}^{PO} \subseteq \mathcal{V}\) denote the subset of Pareto-optimal points in \(\mathcal{V}\). The Pareto Performance Frontier \(\mathrm{PPF}\subset \mathbb{R}_{\geq 0}^d\) is defined as the set of value vectors characterizing the upper boundary of the achievable region. A point \(v\) belongs to the \(\mathrm{PPF}\) if it is weakly dominated by a Pareto-optimal point, yet cannot be strictly improved in all objectives simultaneously by any achievable vector. Formally: \[\begin{align} \mathrm{PPF}= \Big\{ & v \in \mathbb{R}_{\geq 0}^d \;\Big|\; \exists v^* \in \mathcal{V}^{PO} \text{ s.t. } v \preceq v^* \\ & \text{and } \nexists v'\in \mathcal{V} \text{ s.t. } \forall i=1,\ldots, d, \; v_i < v'_i \Big\} \end{align}\]
The frontier separates the achievable performance region from the unachievable region. The achievable region is defined as the set of points weakly dominated by the Pareto set; conversely, the unachievable region comprises values that are strictly unattainable by any policy.
Figure 4 visualizes the \(\mathrm{PPF}\) as a dashed boundary separating the achievable region (weakly dominated by \(\mathcal{V}^{PO}\)) from the strictly unachievable region. By definition, no point on the \(\mathrm{PPF}\) allows simultaneous improvement in all objectives.
Example 5. Figure 4 illustrates \(\mathrm{PPF}\) with a dashed boundary. This frontier demarcates the achievable region, where all feasible points lie on or below the boundary, from the unachievable region located above it. It is easy to see that no point on the \(\mathrm{PPF}\) can be improved in all objectives simultaneously.
Next, we provide an example illustrating a fundamental limitation of linear scalarization: its inability to capture Pareto-optimal points located in non-convex regions of the frontier.
Example 6. Consider the Pareto-optimal points \(A = [2, 3]^\top\), \(B = [2.2, 2.2]^\top\), and \(C = [3, 2]^\top\), as shown in Figure 4. We assert that for any preference vector \(w \in \mathcal{W}\), point \(B\) can never be the maximizer of linear scalarization. Specifically, either \(w^\top B \leq w^\top A\) or \(w^\top B \leq w^\top C\).
We prove this by contradiction. Suppose there exists a preference \(w = [w_1, w_2]^\top \in \mathcal{W}\) (where \(w_1, w_2 \geq 0\)) such that \(w^\top B > w^\top A\) and \(w^\top B > w^\top C\). Expanding and simplifying these inequalities yields: \[\begin{align} 2.2(w_1 + w_2) > 2w_1 + 3w_2 \quad &\implies \quad w_1 > 4w_2 \\ 2.2(w_1 + w_2) > 3w_1 + 2w_2 \quad &\implies \quad w_2 > 4w_1 \end{align}\] Combining these constraints results in \(w_1 > 4w_2 > 16w_1\). Since \(w_1\) and \(w_2\) are non-negative, \(w_1 > 16w_1\) is a clear contradiction. Consequently, varying the preferences and maximizing a linear scalarization will fail to capture the entire Pareto frontier, particularly missing point \(B\).
While the \(\text{PPF}\) defines performance limits, it lacks a mechanism for selecting specific optimal trade-offs. To address this, we use Chebyshev scalarization, which maps preferences to frontier points. Unlike linear weighted sums, which fail on non-convex boundaries, Chebyshev scalarization ensures that every Pareto-optimal point can be recovered. We formalize this in Theorem 1 next:
Theorem 1 (Sufficiency and Necessity of the weighted Chebyshev Scalarization). Let \({\mathcal{V}}\subset \mathbb{R}_{\geq 0}^d\) be a set of achievable value vectors such that \({\mathcal{V}}\subseteq [0,{R_{\max}}]^d\), and let the \(\mathrm{PPF}\) denote the set of Pareto performance frontier for vectors in \({\mathcal{V}}\). For a given preference \(w\in \mathcal{W}\), let \(O_w(v)\) denote the weighted Chebyshev scalarization of \(v\). The following properties hold:
Sufficiency: For any preference \(w\), the maximizer of the Chebyshev scalarization is on the Pareto performance frontier. Formally, if \(V^* \in \arg\max\limits_{v \in \mathcal{V}} O_w(v)\), then \(V^* \in \mathrm{PPF}\).
Necessity: For any Pareto-optimal vector \(V^* \in \mathcal{V}\), there exists a preference \(w \in \mathcal{W}\) such that \(V^*\) is the unique maximizer of the scalarization. Formally if \(V' \in \arg\max\limits_{V \in \mathcal{V}} O_w( V)\) then \(V'=V^*\).
Proof Sketch. The intuition for both properties relies on the geometric constraints of the Chebyshev scalarization:
Sufficiency (Proof by Contradiction): If a maximizer of the Chebyshev objective were not on the Pareto performance frontier (\(\mathrm{PPF}\)), there would exist another achievable vector in \(\mathcal{V}\) that is strictly greater along all dimensions. Because the Chebyshev objective scales strictly with the minimum weighted component, this dominating vector would yield a strictly larger objective value, contradicting the premise that the original vector was a maximizer.
Necessity: For any given Pareto-optimal vector \(V^*\), we can perfectly align the preference vector \(w \in \mathcal{W}\) by setting it proportional to \(V^*\), i.e., \(w:=\frac{V^*}{\|V^*\|_2}\). Therefore, any vector \(V'\in \arg\max\limits_{V\in \mathcal{V}}O_w(V)\) maximizing the objective along this preference must weakly dominate \(V^*\), since \(\min\limits_{w_i>0}\left\{\frac{V'_i}{w_i}\right\} = \min\limits_{V^*_i>0}\left\{\frac{V'_i \|V^*\|_2}{V^*_i}\right\} \geq O_w(V^*)=\|V^*\|_2\), yielding \(V'_i\geq V^*_i\) for all \(i\). Since \(V^*\) is Pareto-optimal by definition, no achievable vector can strictly dominate it, forcing the unique maximizer to be exactly \(V^*\).
A detailed proof is provided in Appendix 6. ◻
Theorem 1 establishes the connection between Chebyshev scalarization and Pareto-optimality. As a consequence, the following Theorem [item:coverage] demonstrates that the set of scalarization maximizers covers all Pareto-optimal points while remaining entirely confined to the Pareto performance frontier.
However, to isolate the Pareto-optimal subset, we must filter out points that lie on the \(\mathrm{PPF}\) but are not Pareto-optimal. To achieve this, we introduce a two-stage optimization procedure in Theorem [item:exactness]. This procedure refines the selection logic: while the first stage uses Chebyshev scalarization to identify candidate solutions, the second stage imposes a maximum \(\ell_2\)-norm tie-breaking rule. By selecting the vector with the largest \(\ell_2\)-norm, we effectively push the solution toward the most distal point on the \(\mathrm{PPF}\), filtering out suboptimal frontier points. This ensures the resulting points are strictly Pareto-optimal, thus exactly capturing the most efficient trade-offs.
Theorem 2 (Coverage and Exact Characterization of Pareto Optimality). Let \(\mathcal{V} \subset \mathbb{R}_{\geq 0}^d\) be a set of achievable value vectors, with \(\mathcal{V}^{PO}\) denoting the Pareto-optimal set and \(\mathrm{PPF}\) the Pareto performance frontier.
The relationship between Chebyshev scalarization and the Pareto set is characterized by the following two properties:
Scalarization-Induced Coverage: Let \(\mathcal{S}\) be the set constructed by selecting, for every preference \(w \in \mathcal{W}\), an arbitrary vector that maximizes the scalarization \(O_w\). Formally: \[\mathcal{S} \;:=\; \bigcup_{w \in \mathcal{W}} \big\{ v_w \big\}, \quad \text{where } v_w \in \arg\max_{v \in \mathcal{V}} O_w(v).\] Then \(\mathcal{S}\) contains all Pareto-optimal points and consists solely of points on the Pareto performance frontier: \[\mathcal{V}^{PO} \subseteq \mathcal{S} \subseteq \mathrm{PPF}.\]
Exact Characterization via Norm-Regularization: Let \(\mathcal{M}\) be the set constructed by selecting, for every preference \(w \in \mathcal{W}\), a vector \(v^*_w\) obtained via a two-stage optimization process: first maximizing the Chebyshev scalarization \(O_w\), and then maximizing the \(\ell_2\)-norm among the resulting candidates for tie-breaking. Formally: \[\mathcal{M} \;:=\; \bigcup_{w \in \mathcal{W}} \big\{ v^*_w \big\},\] where \(v^*_w\) is an arbitrary solution to the nested optimization: \[v^*_w \in \arg\max_{v} \left\{ \|v\|_2 \;\Big|\; v \in \arg\max_{u \in \mathcal{V}} O_w(u) \right\}.\] Then \(\mathcal{M}\) coincides with the Pareto-optimal set: \[\mathcal{M} = \mathcal{V}^{PO}.\]
Proof Sketch.
Scalarization-Induced Coverage: This property is a direct consequence of the Sufficiency and Necessity of the Chebyshev scalarization established in Theorem 1. Sufficiency guarantees that any maximizer chosen for \(\mathcal{S}\) naturally falls on the Pareto performance frontier (\(\mathcal{S}\subseteq \mathrm{PPF})\). Necessity ensures that every true Pareto-optimal point is the unique maximizer for its perfectly aligned preference vector, guaranteeing its inclusion in the coverage set (\(\mathcal{V}^{PO}\subseteq \mathcal{S}\)).
Exact Characterization: To prove \(\mathcal{M} = \mathcal{V}^{PO}\), we must show that the \(\ell_2\)-norm tie-breaker correctly filters out dominated points on the performance frontier. If the two-stage process selected a point that is not Pareto-optimal, a dominating Pareto-optimal point would exist. This dominating point would achieve at least the same scalarization score (passing the first stage) but possess a strictly larger \(\ell_2\)-norm, thereby winning the tie-breaker and contradicting the selection of the inferior point. Conversely, Pareto-optimal points are unique maximizers under their aligned preferences, meaning they trivially pass the tie-breaking phase.
See Appendix 7 for a detailed proof. ◻
5 Bellman Update and Convergence↩︎
Main Idea: Theorem [item:exactness] allows us to characterize the set of Pareto-optimal values via preferences and the two-stage optimization problem involving Chebyshev scalarization in the first stage and norm-maximization in the second stage. By restricting the domain to value vectors achievable by policies, we characterize the set of Pareto-optimal \(Q\)-values obtained by starting from a state \(s\), taking an action \(a\), and subsequently behaving Pareto-optimally with respect to a preference \(w\). We formalize this concept in Definition 5.
To formulate the preference-conditioned Bellman operator, we leverage the coverage guarantee from Theorem [item:coverage]. Crucially, the Bellman update utilizes only the maximization procedure involving the Chebyshev scalarization, since that is sufficient to ensure coverage. Building on this formulation, we prove that the operator satisfies the enveloping property: the estimated value vectors upper-bound the Pareto-optimal values across the preference space. We demonstrate that this property is invariant under the Bellman update: if the initialization envelopes the frontier, subsequent updates maintain this upper bound while monotonically approaching the Pareto performance frontier from above. This monotonic convergence guarantees that the final value estimates cover all Pareto-optimal values.
Finally, to isolate the Pareto-optimal subset, we apply the two-stage optimization procedure to the converged \(Q\)-value vectors. To recover the corresponding Pareto-optimal policies, we rely on Theorem 3, which establishes that Pareto-optimal values are recursive. This recursivity allows us to recover the optimal policies by acting greedily with respect to the converged \(Q\)-values.
Now we define the optimal preference-action-value function as follows.
Definition 5 (Optimal Preference Action-Value Function). For a preference vector \(w \in \mathcal{W}\), the Optimal Preference Action-Value Function \(\mathbf{Q}^* : \mathcal{S} \times \mathcal{A} \times \mathcal{W} \rightarrow \mathbb{R}^d\) maps a state \(s \in \mathcal{S}\), an action \(a \in \mathcal{A}\), and a preference vector \(w\) to the expected vector-valued return obtained by taking action \(a\) in state \(s\) and subsequently following an optimal policy. It is defined as \[\mathbf{Q}^*(s,a,w) := \mathbf{R}(s,a) + \gamma \, \mathbf{V}^*_w\big(p(\cdot \mid s,a)\big),\] where the value function \(\mathbf{V}^*_w\) is determined via a two-stage optimization procedure:
Chebyshev optimization: Identify the policies that maximize the weighted Chebyshev scalarization \(O_w(\cdot)\).
Tie-breaking: Among the resulting optimal value vectors, select one with maximum \(\ell_2\)-norm.
Formally, this is expressed as \[\begin{align} \mathbf{V}^*_w(p(\cdot \mid s,a)) \in \arg\max_{V} \Big\{ \|\mathbf{V}\|_2 \;\big|\; \mathbf{V} = \mathbf{V}^\pi(p(\cdot \mid s,a)), \\ \pi \in \arg\max_{\pi' \in \Pi} O_w(\mathbf{V}^{\pi'}(p(\cdot \mid s,a))) \Big\}. \end{align}\]
As proved in Theorem [item:exactness], this two-stage optimization allows us to characterize the set of Pareto-optimal points via preferences. The following theorem establishes that the preference-conditioned optimal action-value function \(\mathbf{Q}^*\) admits a recursive decomposition.
Theorem 3 (Recursive Decomposition of \(Q^*\)). Let \(\mathbf{Q}^*: S \times A \times \mathcal{W} \to \mathbb{R}^d_{\geq 0}\) be the optimal preference action-value function. For any state \(s \in S\), action \(a \in A\), and preference vector \(w \in \mathcal{W}\), \(\mathbf{Q}^*\) satisfies the recursive relationship:
where the functions \(\hat{A}: S \to A\) and \(\hat{\mathcal{W}}: S \to \mathcal{W}\) map the next-states to actions and preferences, respectively.
Proof Sketch. Let \(\pi\) be a policy achieving \(\mathbf{Q}^*(s,a,w)\). The tail policy induced by \(\pi\) at every next state \(s'\) must be Pareto-optimal. If it were not, there would exist a strictly dominating policy \(\pi'\) at \(s'\). We could then construct a stitched policy \(\pi''\) that follows \(\pi'\) at \(s'\) and \(\pi\) otherwise. This policy \(\pi''\) would strictly dominate \(\pi\) at \((s,a)\) (due to additive nature of expectation), which contradicts the Pareto-optimality of \(\pi\) achieving \(Q^*(s,a,w)\). Thus, the tail value of \(\pi\) at \(s'\) must itself be the Pareto-optimal. Theorem 2 guarantees the existence of a preference \(w'\) recovering this value. By setting \(\hat{A}(s') = \pi(s')\) and \(\hat{\mathcal{W}}(s') = w'\), we recover the recursive form in terms of \(Q^*(s',\hat{A}(s'),\hat{\mathcal{W}}(s'))\). (See Appendix 8 for details.) ◻
This recursive decomposition demonstrates that the Pareto-optimal action-value function \(Q^*\) is greedy with respect to the current preference \(w\). Specifically, after taking an action \(a\) from the current state \(s\), the agent can optimally navigate the environment by greedily selecting the subsequent action \(\hat{\mathcal{A}}(s')\) and preference \(\mathcal{W}(s')\) at each successive state \(s'\). This ensures that the expected vector-valued rewards are maximized along the original preference \(w\) thus capturing the Pareto-optimal trade-offs.
Leveraging the recursive structure established in Theorem 3, we introduce the Preference Bellman Operator \(\mathcal{T}\) (Definition 6) to formalize the iterative update process required to recover the Pareto-optimal values. The relationship between the iterative application of this operator and the Pareto performance frontier is established in Theorem 4. Specifically, we prove that, when initialized with an upper-bounding \(Q\)-function, the sequence of functions generated by the repeated application of \(\mathcal{T}\) monotonically converges to a coverage set of Pareto-optimal values on the \(\mathrm{PPF}\).
Definition 6 (Preference Bellman Optimality Operator). Let \(\mathcal{Q}\) be the space of bounded vector-valued functions mapping \(\mathcal{S} \times \mathcal{A} \times \mathcal{W} \to \mathbb{R}^d_{\geq 0}\). We define the Preference Bellman Optimality Operator \(\mathcal{T}: \mathcal{Q} \to \mathcal{Q}\) as follows.
For any \(Q \in \mathcal{Q}\), state \(s \in \mathcal{S}\), action \(a \in \mathcal{A}\), and preference vector \(w \in \mathcal{W}\):
where the next-state action \(\hat{a}(s')\) and preference \(\hat{w}(s')\) are chosen greedily to maximize the scalarized value at the next state: \[\scalebox{0.95}{ \displaystyle (\hat{a}, \hat{w}) \in \operatorname*{arg\,max}_{\substack{\phi_A:S\rightarrow A \\ \phi_\mathcal{W}: S\rightarrow \mathcal{W}}} O_w\Big( \mathop{\mathrm{\mathbb{E}}}_{s'\sim p(\cdot\mid s,a)} \big[Q(s', \phi_A(s'), \phi_\mathcal{W}(s'))\big]\Big) }\]
The Preference Bellman Operator \(\mathcal{T}\) extends the standard notion of optimality to the multi-objective setting by treating the preference vector as a dynamic component of the decision process. Rather than simply evaluating an action’s immediate reward, the operator performs a preference-conditioned backup.
When evaluating the state-action pair \((s,a)\) under a current preference \(w\), the operator looks ahead to the next state \(s'\) and identifies not only the optimal next action \(\hat{a}\) but also the optimal future preference \(\hat{w}\). This \(\hat{w}\) acts as a steering mechanism: it selects the specific point on the next state’s frontier that contributes most effectively to maximizing the scalarized return for the current preference \(w\).
Next, we prove the convergence of the Bellman operator in Theorem 4.
Theorem 4. Let us define \(Q(s,a,w):= \mathcal{R}\), then for every \(n\in \mathbb{N}\), and each state \(s\), action \(a\), the following three conditions hold:
Upper-bound: Every Pareto-optimal value is upper-bounded by an estimate. Specifically, for every preference \(w\) there exists a preference \(w'\) such that: \[Q^*(s,a,w)\preceq (\mathcal{T}^nQ)(s,a,w')\]
Pareto Envelope: The estimates lie on or above the Pareto performance frontier. Formally, for all preferences \(w\) the estimate is never dominated in all components by a Pareto-optimal value, i.e., \[\begin{gather} \forall w, \nexists w' \text{ such that } \\ (\boldsymbol{\mathcal{T}}^nQ)(s,a,w)_i < Q^*(s,a,w')_i, \quad \forall i=1,\dots,d \end{gather}\]
Asymptotic Convergence: Every estimate converges to the value of a realizable policy. Formally, for all preferences \(w\) there is a policy \(\pi \in \Pi\) such that the gap between the estimate and the policy’s value vanishes: \[\boldsymbol{0}\preceq (\mathcal{T}^nQ)(s,a,w) - V^\pi(s) \preceq \gamma^n \mathcal{R}\]
Proof Sketch. Upper-bound: We proceed by induction. The base case holds by the initialization \(Q \succeq Q^*\). For the inductive step, we invoke the Recursive Decomposition theorem (Theorem 3), which expresses \(Q^*\) as an immediate reward plus a discounted next-state value. By the inductive hypothesis, the next-state \(Q^*\) is upper-bounded by the previous iterate \(\mathcal{T}^{n-1}Q\). Since the operator \(\mathcal{T}\) performs a maximization over potential next-state updates, the update using the upper-bounding estimate yields a value at least as high as \(Q^*\), preserving the inequality \(Q^*(s,a,w)\preceq (\mathcal{T}^nQ)(s,a,w')\).
Pareto Envelope: We argue by contradiction. Suppose there exist preferences \(w\) and \(w'\) such that the estimate is strictly less than an optimal value in all components: \((\mathcal{T}^nQ)(s,a,w)_i < Q^*(s,a,w')_i\) for all \(i=1,\dots,d\). From the Upper-bound property (Theorem [prop:opt95coverage]), we know \(Q^*(s,a,w')\) is itself upper-bounded by some estimate \(\mathcal{T}^nQ(s,a,w'')\). By transitivity, this implies \((\mathcal{T}^nQ)(s,a,w)_i < (\mathcal{T}^nQ)(s,a,w'')_i\) for all \(i\). In other words, the estimate for \(w''\) is strictly greater than the estimate for \(w\) in every component. Subtracting \(R(s,a)\) and dividing by \(\gamma\) implies that the expected continuation value used in the update for \(w''\) is strictly greater component-wise than that for \(w\). Since every component is strictly larger, the resulting Chebyshev scalarization is strictly higher. This contradicts the operator’s maximization step, which would have selected the higher update.
Asymptotic Convergence: The value \(\mathcal{T}^nQ(s,a,w)\) represents the accumulation of rewards from \(n\) steps of optimal updates plus a residual initialization term bounded by \(\gamma^n \mathcal{R}\). We construct a deterministic, non-stationary, history-dependent policy \(\pi\) that exactly mimics the sequence of action updates chosen by the operator \(\mathcal{T}\) for the first \(n\) steps, and acts arbitrarily thereafter. The value of this policy \(V^\pi(s)\) matches the estimate \(\mathcal{T}^nQ(s,a,w)\) exactly in the first \(n\) terms, with the difference arising solely from the tail rewards after step \(n\). Since rewards are bounded, this difference is bounded by \(\gamma^n \mathbb{R}\), which vanishes as \(n \to \infty\).
(See Appendix 12 for the detailed proof.) ◻
Discussion of Theorem 4: The significance of this theorem lies in its guarantee that the preference-conditioned Bellman operator monotonically converges toward the Pareto performance frontier. Unlike standard value iteration, which converges to a single fixed point, our operator converges to a set of values that fully characterizes the frontier.
Condition [prop:opt95coverage] (Upper-bound) acts as a safety guarantee, ensuring that the iterative updates never discard the Pareto-optimal values; the estimates remain sufficiently expressive to cover all optimal trade-offs.
Condition [prop:pareto95envelope] (Pareto Envelope) establishes the geometric relationship of the updates: the estimates approach the frontier strictly from the non-dominated side, creating an “envelope" that tightens with every iteration.
Condition [prop:asymp95real] (Asymptotic Convergence) bridges the gap between estimation and execution. It ensures that as \(n\rightarrow \infty\), the gap between the estimates and achievable values vanishes, guaranteeing that the limiting values of the sequence represent executable policies.
In the next section, we discuss how to obtain Pareto-optimal policies along a preference \(w\).
6 Obtaining Pareto-optimal Policies↩︎
The convergence and recursive properties of the Preference Bellman Operator \(\mathcal{T}\) enable us to recover policies that approximate all Pareto-optimal values. Crucially, as established by the recursive decomposition in Theorem 3, these policies can be executed greedily. Rather than tracking the entire execution history, the agent requires only a constant-size memory consisting of the most recent transition data, namely the previous state \(s_{i-1}\), action \(a_{i-1}\), and reward \(r_{i-1}\), alongside the current guiding preference \(w_i\). At step \(i\), upon observing the current state \(s_i\), the agent greedily selects an action-preference pair \((a_i, w_{i+1})\) based on the Q-estimates. This pair dictates the immediate action to execute and the updated preference parameter required to guide the policy from the subsequent state. The memory is then shifted forward accordingly. Algorithm 5 provides the high-level pseudocode for this execution, starting from an initial state \(s_0\) and initial preference \(w_{init}\) (with the detailed procedure, Algorithm 9, deferred to Appendix 12.1). Next, we establish the theoretical guarantees for the policies generated by this algorithm.
Theorem 5 (Approximate Pareto Coverage). Let \(\mathcal{C}^n_{PO} = \{ \pi_w \mid w \in \mathcal{W} \}\) denote the set of policies generated by all preferences using the \(n\)-th Bellman update by Algorithm 5. This set satisfies the properties of approximate Pareto coverage.
Approximate Coverage: Every Pareto-optimal policy is approximated by some policy in \(\mathcal{C}^n_{PO}\) such that the suboptimality gap is bounded. Formally: \[\begin{align} &\forall \pi \in \Pi, \exists w \in \mathcal{W} \text{ such that } \\ & V^{\pi}(s_0) \preceq V^{\pi_w}(s_0) + \gamma^n \mathcal{R} \end{align}\]
Approximate Parsimony: Every policy in \(\mathcal{C}^n_{PO}\) satisfies \(\boldsymbol{\gamma}^{\boldsymbol{n}}\boldsymbol{\mathcal{R}}\)-Pareto optimality; that is, no other policy can strictly dominate it by a margin larger than the approximation bound. Formally: \[\begin{align} &\forall w \in \mathcal{W}, \forall \pi \in \Pi \quad \text{ we get} \\ &V^{\pi}(s_0) \nsucc V^{\pi_w}(s_0) + \gamma^n \mathcal{R} \end{align}\]
Proof Sketch. The argument depends on bounding the performance gap between the theoretical \(n\)-step Bellman estimate \(\mathcal{T}^n Q(s,a,w)\) and the true expected value \(V^{\pi_w}(s)\) of the policy executing the greedy unrolling procedure starting from preference \(w\).
Recursive Trajectory Bound: At each step of execution, the agent greedily re-plans using the full \(n\)-step horizon aligned with its future expected return. By unrolling the recursive error over the infinite horizon, the maximum performance drop is bounded by the residual term: \[\mathcal{T}^n Q(s,a,w) \preceq V^{\pi_w}(s) + \gamma^n \mathcal{R}\]
Approximate Coverage: We know from the fundamental properties of the scalarized Bellman operator that the value of any true Pareto-optimal policy \(\pi^*\) is weakly dominated by the theoretical \(n\)-th Bellman estimate for some specifically aligned preference \(w'\) added to a small residual term \(\gamma^n\mathcal{R}\). Chaining this bound with our execution bound guarantees that the induced policy \(\pi_{w'}\) approximates the true optimal policy \(\pi^*\) within the residual gap: \[V^{\pi^*}(s) \preceq \mathcal{T}^n Q(s,a,w') \preceq V^{\pi_{w'}}(s) + \gamma^n \mathcal{R}\]
Approximate Parsimony: Since the estimates generated by the Bellman operator cannot be strictly dominated by any policy, and the executed policy \(\pi_w\) successfully recovers this estimate up to the \(\gamma^n \mathcal{R}\) residual margin, no alternative policy exists that can strictly dominate \(V^{\pi_w}(s)\) by a margin larger than \(\gamma^n \mathcal{R}\).
A detailed proof is provided in Appendix 13. ◻
In summary, our framework guarantees that by utilizing the Chebyshev-based Bellman operator to converge to accurate Q-value estimates, and subsequently filtering these estimates to break ties, we can extract an approximate set of Pareto-optimal policies.
7 Experiments↩︎
In this section, we empirically validate the theoretical claims presented in Section 5. Our evaluation addresses three primary questions:
Convergence: Does the recursive application of the preference-aware Bellman operator result in the convergence of value estimates to the Pareto frontier?
Coverage: Do the converged estimates successfully cover the entire set of Pareto-optimal trade-offs?
Policy Extraction: Do the synthesized deterministic policies achieve the estimated Pareto-optimal values (solving the alignment consistency problem)?
To answer these, we evaluate our algorithm on the standard Deep Sea Treasure (convex frontier) and a modified Deep Sea Treasure Concave variant [38]. We note that Pareto-optimal values and policies are known for both the benchmarks [38]. While the Deep-Sea-Treasure has a convex Pareto front, the Deep-Sea-Treasure-Concave has a concave Pareto front.
Q1 Convergence: Figures 6 and 7 illustrate the evolution of the value estimates \(\hat{Q}\) over training iterations \(n=\{1, 100, 1000, 2000\}\). We observe that the estimates (represented by shapes) monotonically advance towards the frontier and stabilize after approximately at 1,000 steps. The negligible shift between the 1,000-step (Green) and 2,000-step (Orange) estimates affirms asymptotic convergence.
Q2 Coverage: The estimates \(\hat{Q}\) for both environments align with the ground truth Pareto optimal values. Notably, in the Concave environment, our method successfully identifies all the trade-offs , which are typically skipped by linear scalarization methods that only recover the convex hull.
Q3 Policy Extraction: To verify consistency, we executed the extracted policies plotted the realized returns as crosses (\(\times\)). The perfect overlap between the predicted estimates (\(\hat{Q}_{2000}\)) and the actual policy returns (\(\pi_{2000}\)) confirms that our policies achieve the estimated Pareto-optimal trade-offs.
Baselines: We benchmark our results against the MORL-Baselines project [39]2. According to these benchmarks, Pareto Q-Learning (PQL) [31] successfully recovers the complete Pareto-optimal frontier in both the convex and concave Deep Sea Treasure environments. In contrast, Multi-Policy Multi-Objective Q-Learning (MP-MOQ) [28] recovers nearly the entire frontier in the convex setting, it fails significantly in the concave environment, identifying only the two points of the concave frontier.
8 Conclusion↩︎
We presented a framework for the Approximate Complete And Parsimonious Synthesis (\(\epsilon\)-CAPS) of deterministic Pareto-optimal policies. By introducing a novel Bellman operator based on Chebyshev scalarization, we established theoretical guarantees for asymptotic convergence to the Pareto performance frontier. Crucially, we demonstrated how to obtain deterministic policies from the converged Q-estimates, ensuring that every recovered policy is approximately non-dominated, and every non-dominated value is approximately recovered. Empirically, our method successfully captures complex, non-convex trade-offs where standard linear scalarizations strictly fail. Future work will focus on scaling this formulation to high-dimensional state spaces via deep reinforcement learning architectures.
9 Principle of Aligned Dominance↩︎
Lemma 1 (The Principle of Aligned Dominance). Let \(\mathcal{V} \subset \mathbb{R}^d_{\geq 0}\) be a compact, non-empty set, such that \(\mathcal{V} \neq \{\mathbf{0}\}\), and let \(v \in \mathcal{V}\) be a non-zero vector. Consider any maximizer \(v^*\) of the Chebyshev scalarization with the preference aligned with \(v\). Then \(v^*\) weakly dominates \(v\).
Formally: \[\text{if } w = \frac{v}{\|v\|_2} \quad \text{and} \quad v^* \in \operatorname*{argmax}_{z \in \mathcal{V}} O_{w}(z), \quad \text{then } v \preceq v^*.\]
Proof. If \(v^* \in \operatorname*{arg\,max}\limits_{z \in \mathcal{V}} O_{w}(z)\) then \(O_w(v^*)\geq O_w(v)\). Therefore \(\min\limits_{i:v_i>0}\Bigl(\frac{v^*_i}{\frac{v_i}{\|v\|_2}}\Bigr)\geq \min\limits_{i:v_i>0}\Bigl(\frac{\cancel{v_i}}{\frac{\cancel{v_i}}{\|v\|_2}}\Bigr) =\|v\|_2\). Therefore for every \(i=1,2\ldots d\), \(v^*_i\geq \frac{v_i}{\cancel{\|v\|_2}}\cancel{\|v\|_2}\geq 0\). Guaranteeing that \(v^*\) dominates \(v\), i.e. \(v^*\succeq v\). ◻
Lemma 1 establishes a mechanism for monotonic improvement in the vector space. Specifically, it guarantees that for any point \(v \in {\mathcal{V}}\), the scalarization objective \(O_w\) parameterized by the direction \(w= \frac{v}{\|v\|_2}\) aligned with \(v\) is maximized by a point \(v^*\) that weakly dominates \(v\). We note that there could be multiple maximizers, possibly incomparable to each other. However, every maximizer would dominate \(v\). Example 7 illustrates this.
Example 7. Consider \(v_1:=(1,1)\), \(v_2=(1.5,2)\), \(v_3=(2,1.5)\), and \({\mathcal{V}}:=\{v_1, v_2, v_3\}\) be three vectors. Then, both \(v_2\) and \(v_3\) are maximizers of the Chebyshev scalarization aligned along \(v_1\), however both \(v_2\) and \(v_3\) are incomparable.
10 Chebyshev Scalarization and Pareto-Optimality↩︎
Theorem 6 (Sufficiency and Necessity of Chebyshev Scalarization). Let \({\mathcal{V}}\subset \mathbb{R}_{\geq 0}^d\) be a set of achievable value vectors such that \({\mathcal{V}}\subseteq [0,{R_{\max}}]^d\), and let the \(\mathrm{PPF}\) denote the set of Pareto performance frontier for vectors in \({\mathcal{V}}\). For a given preference \(w\in \mathcal{W}\), let \(O_w(v)\) denote the weighted Chebyshev scalarization objective. The following properties hold:
Sufficiency: For any preference \(w\), the maximizer of the Chebyshev scalarization is on the Pareto performance frontier. Formally, if \(v^* \in \arg\max\limits_{v \in \mathcal{V}} O_w(v)\), then \(v^* \in \mathrm{PPF}\).
Necessity: For any Pareto-optimal point \(v^* \in \mathcal{V}\), there exists a preference \(w \in \mathcal{W}\) such that \(v^*\) is the unique maximizer of the scalarization. Formally if \({v}' \in \arg\max\limits_{v \in \mathcal{V}} O_w(v)\) then \(v'=v^*\).
Proof. 1. Sufficiency
If \(v^*\in \arg\max\limits_{v\in {\mathcal{V}}} O_w(v)\) then \(v^*\in\mathrm{PPF}\): Suppose for the sake of contradiction \(v^*\) is a maximizer of \(O_w(v)\) but \(v^*\notin \mathrm{PPF}\). Since \(v^*\) is not on the \(\mathrm{PPF}\) there is a Pareto-optimal vector \(v'\in {\mathcal{V}}\) such that \(v'_i > v^*_i\) for all \(i = 1,2 \dots, d\). Then for every \(i\in \{1,2,\ldots d\}\) such that \(w_i>0\), we can divide \(v_i'\) and \(v_i^*\) by the positive weight \(w_i\) to obtain: \[\frac{v'_i}{w_i} > \frac{v^*_i}{w_i}\] Taking the minimum over \(i\): \[\min_{i:w_i>0} \left( \frac{v'_i}{w_i} \right) > \min_{i:w_i>0} \left( \frac{v^*_i}{w_i} \right) \implies O_w( v') > O_w( v^*)\] This contradicts the optimality of \(v^*\). Thus, \(v^*\) must be in \(\mathrm{PPF}\).
2. Necessity
Let \(v^*\in \mathcal{V}\) be a Pareto-optimal point, and let \(w=\frac{v^*}{\|v^*\|_2}\) be the preference aligned with \(v^*\). We invoke Lemma 1 to obtain that for every \(v'\in \arg\max\limits_{v\in \mathcal{V}} O_w(v)\), we have \(v'\succeq v^*\). However, since \(v^*\) is Pareto-optimal, this condition implies \(v^*=v'\). Thus, there is a unique maximizer along the preference aligned with \(v^*\). ◻
Theorem 7 (Coverage and Exact Characterization of Pareto Optimality). Let \(\mathcal{V} \subset \mathbb{R}_{\geq 0}^d\) be a compact set of achievable value vectors, with \(\mathcal{V}^{PO}\) denoting the Pareto-optimal set and \(\mathrm{PPF}\) the Pareto performance frontier.
The relationship between Chebyshev scalarization and the Pareto set is characterized by the following two properties:
Scalarization-Induced Coverage: Let \(\mathcal{S}\) be the set constructed by selecting, for every preference \(w \in \mathcal{W}\), an arbitrary vector that maximizes the scalarization \(O_w\). Formally: \[\mathcal{S} \;:=\; \bigcup_{w \in \mathcal{W}} \big\{ v_w \big\}, \quad \text{where } v_w \in \arg\max_{v \in \mathcal{V}} O_w(v).\] Then \(\mathcal{S}\) contains all Pareto-optimal points and consists solely of points on the Pareto performance frontier: \[\mathcal{V}^{PO} \subseteq \mathcal{S} \subseteq \mathrm{PPF}.\]
Exact Characterization via Norm-Regularization: Let \(\mathcal{M}\) be the set constructed by selecting, for every preference \(w \in \mathcal{W}\), a vector \(v^*_w\) obtained via a two-stage optimization process: first maximizing the Chebyshev scalarization \(O_w\), and then maximizing the \(\ell_2\)-norm among the resulting candidates for tie-breaking. Formally: \[\mathcal{M} \;:=\; \bigcup_{w \in \mathcal{W}} \big\{ v^*_w \big\},\] where \(v^*_w\) is an arbitrary solution to the nested optimization: \[v^*_w \in \arg\max_{v} \left\{ \|v\|_2 \;\Big|\; v \in \arg\max_{u \in \mathcal{V}} O_w(u) \right\}.\] Then \(\mathcal{M}\) coincides with the Pareto-optimal set: \[\mathcal{M} = \mathcal{V}^{PO}.\]
Proof.
Scalarization-Induced Coverage: The proof proceeds in two steps:
1. (\(\mathcal{S} \subseteq \mathrm{PPF}\)): Consider any selected element \(v_w \in \mathcal{S}\). By definition, \(v_w\) is a maximizer of the weighted Chebyshev scalarization \(O_w\). From the Sufficiency property (Theorem [thm:cheb95nece]), any such maximizer must lie on the Pareto performance frontier. Therefore, every element in \(\mathcal{S}\) belongs to \(\mathrm{PPF}\), implying \(\mathcal{S} \subseteq \mathrm{PPF}\).
2. (\(\mathcal{V}^{PO} \subseteq \mathcal{S}\)): Let \(v^* \in \mathcal{V}^{PO}\) be an arbitrary Pareto-optimal vector. From the Necessity property (Theorem [thm:cheb95suff]), there exists a specific preference \(w \in \mathcal{W}\) such that \(v^*\) is the unique maximizer of the scalarization \(O_w\) over \(\mathcal{V}\). Since the maximizer is unique, the arbitrary selection \(v_w\) for this specific weight must be \(v^*\) itself (i.e., \(v_w = v^*\)). Consequently, \(v^*\) is included in \(\mathcal{S}\), implying \(\mathcal{V}^{PO} \subseteq \mathcal{S}\).
Exact Characterization via Norm-Regularization: We prove the equality by showing mutual inclusion: \(\mathcal{M} \subseteq \mathcal{V}^{PO}\) and \(\mathcal{V}^{PO} \subseteq \mathcal{M}\).
1. (\(\mathcal{M} \subseteq \mathcal{V}^{PO}\)): Let \(v_w \in \mathcal{M}\) be a vector selected for some preference \(w\). Suppose for the sake of contradiction that \(v_w \notin \mathcal{V}^{PO}\). This implies there exists a dominating vector \(v^* \in \mathcal{V}^{PO}\) such that \({v_w} \prec v^*\). This means \(v_{w,k} \leq v^*_k\) for all components \(k\), with strict inequality for at least one component.
This dominance implies two properties:
Scalarization: Since every component of \(v^*\) is at least as large as \(v_w\), the weighted minimum ratio cannot decrease, so \(O_w(v_w) \leq O_w(v^*)\).
Norm: Since \(v^*\) strictly dominates \(v_w\) and values are non-negative, the \(\ell_2\)-norm must be strictly larger: \(\|v_w\|_2 < \|v^*\|_2\).
Now we check if \(v_w\) could have been the output of the two-stage process:
If \(O_w(v^*) > O_w(v_w)\), then \(v_w\) failed the first stage (maximizing scalarization), which is a contradiction.
If \(O_w(v^*) = O_w(v_w)\), then \(v_w\) is a valid candidate for the second stage. However, since \(\|v^*\|_2 > \|v_w\|_2\), the second stage would have selected \(v^*\) rather than \(v_w\). This is also a contradiction.
Thus, no such dominating vector \(v^*\) can exist, so \(v_w\) must be Pareto-optimal.
2. (\(\mathcal{V}^{PO} \subseteq \mathcal{M}\)): Let \(v^* \in \mathcal{V}^{PO}\) be an arbitrary Pareto-optimal point. Consider the specific preference aligned with this vector: \(w^* := \frac{v^*}{\|v^*\|_2}\).
We invoke Lemma 1, which states that for aligned preferences, any maximizer \(v'\in \arg\max\limits_{v\in{\mathcal{V}}}O_{w^*}(v)\) of the Chebyshev scalarization \(O_{w^*}\) must weakly dominate the alignment target: \(v' \succeq v^*\). However, since \(v^*\) is Pareto-optimal, it cannot be strictly dominated. Therefore, the weak dominance implies equality: \(v' = v^*\).
This means the set of first-stage maximizers \(\arg\max\limits_{u \in \mathcal{V}} O_{w^*}(u)\) is the singleton set \(\{v^*\}\). Since the set contains only one element, the second-stage norm maximization trivially selects \(v^*\). Consequently, \(v^* \in \mathcal{M}\).
◻
11 Bellman Update↩︎
Theorem 8 (Recursive Decomposition of \(Q^*\)). Let \(\mathbf{Q}^*: S \times A \times \mathcal{W} \to \mathbb{R}^d_{\geq 0}\) be the optimal preference action-value function. For any state \(s \in S\), action \(a \in A\), and preference vector \(w \in \mathcal{W}\), \(\mathbf{Q}^*\) satisfies the recursive relationship:
\[\label{app:thm:eq:rec95q95star} \mathbf{Q}^*(s, a, w) = R(s, a) + \gamma \mathop{\mathrm{\mathbb{E}}}\limits_{s' \sim p(\cdot \mid s, a)} \left[ \mathbf{Q}^*(s', \hat{A}(s'), \hat{\mathcal{W}}(s')) \right]\tag{1}\] where the functions \(\hat{A}: S \to A\) and \(\hat{\mathcal{W}}: S \to \mathcal{W}\) map the next-states to actions and preferences, respectively.
Proof. The proof proceeds by expanding the definition of the optimal preference action-value function and examining the optimality of the induced “tail" policies.
1. Expansion of \(Q^*\): By Definition 5, \(Q^*(s,a,w)\) is the value achieved by a policy \(\pi\) that maximizes the Chebyshev scalarization for the preference \(w\). Let us denote this optimal policy by \(\pi_w\). We can expand the value of this policy recursively: \[\label{eq:proof:rec95expansion} Q^*(s,a,w) = R(s,a) + \gamma \mathop{\mathrm{\mathbb{E}}}_{s' \sim p(\cdot \mid s,a)} \left[ R(s', a') + \gamma V^{\pi_w(\cdot |s',a')}(p(\cdot \mid s', a')) \right]\tag{2}\] where \(a' = \pi_w(s')\) is the action chosen by the policy at the next state, and \(V^{\pi_w(\cdot |s',a')}(p(\cdot \mid s', a'))\) denotes the expected value of following policy \(\pi_w\) from that point onward (i.e., given the history \((s',a')\)).
2. The Claim: To establish the recursive relationship in Equation 1 , we must prove that the tail value term corresponds to an optimal value \(Q^*\) for some configuration of action and preference. Specifically, we claim that for every next state \(s'\), the continuation value vector \(V^{\pi_w(\cdot\mid s',a')}(p(\cdot \mid s', a'))\) is Pareto-optimal. If it is Pareto-optimal, then by Theorem (Theorem [thm:cheb95suff]), it must be the maximizer for some specific preference \(w'\).
**3. Proof by Contradiction (The “Stitching" Argument):** Suppose, for the sake of contradiction, that for the next-state distribution induced by a specific state \(s'\) and action \(a'=\pi_w(s')\), the continuation policy induced by \(\pi_w(\cdot\mid s',a')\) is not Pareto-optimal. This implies there exists an alternative policy \(\pi_{\text{better}}\) that strictly dominates the original”tail" policy from the distribution \(p(\cdot \mid s', a')\). Formally: \[V^{\pi_{\text{better}}}(p(\cdot \mid s', a')) \succ V^{\pi_w(\cdot\mid s',a')}(p(\cdot \mid s', a'))\] We now construct a “stitched" composite policy \(\pi_{\text{new}}\) that switches behavior based on the history. The policy follows \(\pi_{\text{better}}\) if the trajectory passes through the specific history \((s', a')\), and defaults to \(\pi_w\) otherwise: \[\pi_{\text{new}}(h) := \begin{cases} \pi_{\text{better}}(h) & \text{if } h \text{ is rooted at } (s', a') \\ \pi_w(h) & \text{otherwise} \end{cases}\] Since \(\pi_{\text{better}}\) provides strictly higher value on the specific sub-branch starting at \((s', a')\) and \(\pi_{\text{new}}\) behaves identically to \(\pi_w\) everywhere else, the multi-objective value at the root \((s,a)\) must strictly dominate, i.e. \(V^{\pi_w}(p(\cdot\mid s,a))\prec V^{\pi_{\text{better}}}(p(\cdot\mid s,a))\).
Substituting this back into Equation 2 , the value of the new policy satisfies:
\[{!}{ R(s,a) + \gamma \mathbb{E} \Big[ R(s',\pi_w(s'))+\gamma V^{\pi_{\text{better}}(\cdot\mid s',\pi_w(s'))}\big(p(\cdot \mid s',\pi_w(s'))\big) \Big] \succ R(s,a) + \gamma \mathbb{E} \Big[ R(s',\pi_w(s'))+\gamma V^{\pi_w(\cdot\mid s',\pi_w(s'))}\big(p(\cdot \mid s',\pi_w(s'))\big) \Big] = Q^*(s,a,w)}\]
This implies that \(\pi_{\text{new}}\) achieves a strictly dominating value vector than \(\pi_w\). Consequently, from Lemma [item:exactness] the two-stage optimization process involving the Chebyshev scalarization and tie-breaking would never choose \(\pi_w\) since \(\pi_{\text{better}}\) strictly dominates the value \(\pi_w\) obtains from the intial distribution induced by \(p(\cdot\mid s,a)\). That is \(\mathbf{V}^{\pi_w}(p(\cdot \mid s,a)) \notin \arg\max\limits_{V} \Big\{ \|\mathbf{V}\|_2 \;\big|\; \mathbf{V} = \mathbf{V}^\pi(p(\cdot \mid s,a)),\pi \in \arg\max\limits_{\pi' \in \Pi} O_w(\mathbf{V}^{\pi'}(p(\cdot \mid s,a))) \Big\}\).
This contradicts the original assumption that \(\pi_w\) was the maximizer for the preference \(w\).
4. Conclusion: Because the contradiction assumes the tail was not optimal, we conclude that the induced tail policy must be Pareto-optimal. Since the continuation value is Pareto-optimal, there exists a preference \(w'\) (specifically, the one aligned with the continuation value) from Theorem [thm:cheb95suff] such that: \[R(s', a') + \gamma V^{\pi_w}(p(\cdot \mid s', a')) = Q^*(s', a', w')\] Substituting this back into Equation 2 yields the desired recursive relationship: \[Q^*(s, a, w) = R(s, a) + \gamma \mathop{\mathrm{\mathbb{E}}}\limits_{s' \sim p(\cdot \mid s, a)} \left[ Q^*(s', \hat{A}(s'), \hat{\mathcal{W}}(s')) \right]\] ◻
12 Convergence Proof↩︎
Notation: For brevity, we denote the estimate at the \(n\)-th Bellman update \(\mathcal{T}^{ n} Q\) by the shorthand \(\hat{ Q}_{ n}\).
Theorem 9. Let the value function be initialized to an optimistic upper bound \(\hat{{Q}}_0(s,a,w) := \mathcal{R}=\frac{{R}_{\max}}{ 1-\gamma}\Biggl(\begin{smallmatrix} 1\\[-1pt] 1\\[-5pt] \vdots\\[-0.5pt] 1 \end{smallmatrix} \Biggr)\in \mathbb{R}^d_{\geq 0}\). Then for every \(n \in \mathbb{N}\), state \(s\), and action \(a\), the following three conditions hold:
Upper-bound Coverage: The estimated set of values covers the true Pareto front. Formally, for every preference \(w\), there exists a preference \(w'\) such that: \[{Q}^*(s,a,w) \preceq \hat{{Q}}_n(s,a,w')\]
Envelope Property: The estimate is never goes below the Pareto performance frontier. Formally, there is no preference \(w'\) for which a Pareto-optimal value is strictly greater than the estimate in all components: \[\forall w, \nexists w' \quad \text{such that} \quad \hat{Q}_n(s,a,w)_i < Q^*(s,a,w')_i \quad \forall i=1,\dots,d\]
Asymptotic Convergence: Every estimate \(\hat{{Q}}_n\) corresponds to a feasible policy execution up to a residual term. There exists a policy \(\pi \in \Pi\) such that: \[\hat{{Q}}_n(s,a,w) - {V}^\pi(s) \preceq \gamma^n {R}\]
Proof.
Upper-bound Coverage: We prove this by induction on \(n\).
Base Case (\(n=0\)): By initialization, \(\hat{{Q}}_0(s,a,w) = \frac{\mathcal{R}}{1-\gamma}\), which is the maximum possible return. Thus, \({Q}^*(s,a,w) \preceq \hat{{Q}}_0(s,a,w)\) trivially holds.
Induction Step: Assume the hypothesis holds for \(n=k\). That is, for any \(s', a', w_{next}\), there exists some \(\tilde{w}\) such that \(Q^*(s',a',w_{next}) \preceq \hat{Q}_k(s',a',\tilde{w})\). We wish to show that for any \(w\), there exists a \(w'\) such that \(Q^*(s,a,w)\preceq \hat{Q}_{k+1}(s,a,w')\).
From the recursive decomposition (Theorem 3), we know: \[Q^*(s, a, w) = R(s, a) + \gamma \mathop{\mathrm{\mathbb{E}}}_{s' \sim p(\cdot \mid s, a)} \left[ Q^*(s', a'', w'') \right]\] We construct the specific target preference \(w'\) aligned with this optimal continuation expectation: \[w' := \frac{\mathop{\mathrm{\mathbb{E}}}_{s' \sim p(\cdot \mid s, a)} \left[ Q^*(s', a'', w'') \right]}{\big\|\mathop{\mathrm{\mathbb{E}}}_{s' \sim p(\cdot \mid s, a)} \left[ Q^*(s', a'', w'') \right]\big\|_2}\]
By the induction hypothesis, for every optimal continuation value inside the expectation, there exists a preference in our estimate set \(\hat{Q}_k\) that dominates it. Specifically, for any \(s'\), the value \(Q^*(s', a'', w'')\) is dominated by some \(\hat{Q}_k(s', a''', w''')\).
Because the Bellman operator computes the maximizer over all possible actions and preferences, and since the specific preference \(w'\) is perfectly aligned with the optimal continuation vector \(\mathop{\mathrm{\mathbb{E}}}_{s' \sim p(\cdot \mid s, a)} \left[ Q^*(s', a'', w'') \right]\), Lemma 1 (Principle of Aligned Dominance) guarantees: \[\max_{a, \tilde{w}} O_{w'}\Big( \mathop{\mathrm{\mathbb{E}}}\big[ \hat{Q}_k(s', a, \tilde{w}) \big] \Big) \ge O_{w'}\Big( \mathop{\mathrm{\mathbb{E}}}\big[ Q^*(s', a'', w'') \big] \Big)\] This implies component-wise dominance for the updated value: \[\mathop{\mathrm{\mathbb{E}}}_{s'}\big[ \hat{Q}_k(s', \hat{a}, \hat{w}) \big] \succeq \mathop{\mathrm{\mathbb{E}}}_{s'}\big[ Q^*(s', a'', w'') \big]\] Multiplying by \(\gamma\) and adding the reward \(R(s,a)\) to both sides proves that \(Q^*(s,a,w)\preceq \hat{Q}_{k+1}(s,a,w')\).
Envelope Property:
We prove this by contradiction for \(n\geq 1\), if \(n=0\), then \(\hat{Q}_0(s,a,w)=\mathcal{R}\) and the Envelope property holds.
Assume there exist preferences \(w, w'\) such that the estimate is strictly dominated in every component: \[\label{eq:env95assumption} \hat{Q}_n(s,a,w)_i < Q^*(s,a,w')_i \quad \text{for every } i=1,\dots,d\tag{3}\]
Let the update for \(\hat{Q}_n(s,a,w)\) be derived from the specific choice of action \(\hat{a}\) and preference \(\hat{w}\). Similarly, let the optimal value \(Q^*(s,a,w')\) be derived from the optimal action \(a^*\) and preference \(w^*\).
Expanding both sides of Eq. 3 , subtracting \(R(s,a)\), and dividing by \(\gamma\) yields: \[\label{eq:env95strict95ineq} \mathop{\mathrm{\mathbb{E}}}_{s'}\big[ \hat{Q}_{n-1}(s',\hat{a},\hat{w})\big]_i < \mathop{\mathrm{\mathbb{E}}}_{s'}\big[Q^*(s',a^*,w^*)\big]_i \quad \forall i\tag{4}\]
We now apply the Upper-bound Coverage property. For the optimal pair \((a^*, w^*)\), there must exist a preference \(\tilde{w}\) such that: \[\label{eq:env95weak95ineq} Q^*(s',a^*,w^*) \preceq \hat{Q}_{n-1}(s',a^*,\tilde{w})\tag{5}\]
Substituting (5 ) into (4 ) gives the chain of inequalities: \[\mathop{\mathrm{\mathbb{E}}}_{s'}\big[ \hat{Q}_{n-1}(s',\hat{a},\hat{w})\big]_i < \mathop{\mathrm{\mathbb{E}}}_{s'}\big[Q^*(s',a^*,w^*)\big]_i \leq \mathop{\mathrm{\mathbb{E}}}_{s'}\big[\hat{Q}_{n-1}(s',a^*,\tilde{w})\big]_i \quad \forall i\]
This implies that the vector expected from the chosen pair \((\hat{a}, \hat{w})\) is component-wise strictly greater than the vector from the pair \((a^*, \tilde{w})\).
Since any valid scalarization function is strictly increasing with respect to strong dominance, the scalarized score for \((a^*, \tilde{w})\) must be strictly higher than the score for \((\hat{a}, \hat{w})\). That is, for any preference \(w\), the Chebyshev scalarization \(O_{w''}(z) = \min\limits_{i:w''_i>0}\Bigl( \frac{z_i}{{w''}_i}\Big)\) satisfies strict monotonicity with respect to strong dominance. Specifically, since the vector for \((\hat{a}, \hat{w})\) is strictly smaller than the vector for \((a^*, \tilde{w})\) in every component \(i\), it follows that: \[O_{w''}\Big(\mathop{\mathrm{\mathbb{E}}}_{s'}\big[ \hat{Q}_{n-1}(s',\hat{a},\hat{w})\big]\Big) = \min\limits_{i:w''_i>0}\bigg(\frac{\mathop{\mathrm{\mathbb{E}}}[\dots]_{i}}{w''_{i}}\bigg) < \min\limits_{i:w''_i>0}\bigg(\frac{\mathop{\mathrm{\mathbb{E}}}[\dots]_{i}}{w''_{i}}\bigg) = O_{w''}\Big(\mathop{\mathrm{\mathbb{E}}}_{s'}\big[ \hat{Q}_{n-1}(s',a^*,\tilde{w})\big]\Big)\]
This strict inequality violates the optimality of the update rule, as the Bellman operator should have selected the superior configuration \((a^*, \tilde{w})\) (or an even better one) instead of \((\hat{a}, \hat{w})\).
Thus the assumption is not true, and the Envelope property holds.
Asymptotic Convergence: Consider an estimate \(\hat{{Q}}_n(s,a,w)\). We construct a non-stationary deterministic policy \(\pi\) defined by the “backtracking" trace of the Bellman updates.
Let \(\pi\) execute action \(a\) at \(t=0\). For steps \(t=1 \dots n-1\), let \(\pi\) select the actions that were chosen as the maximizers during the recursive computation of \(\hat{{Q}}_n\). The accumulated rewards of this policy match the estimate exactly for the first \(n\) steps.
The difference between the estimate and the true value of \(\pi\) arises only from the tail (after step \(n\)). Since rewards are bounded, the maximum possible value of the tail is bounded by \(\gamma^n\mathcal{R}\). Thus: \[\boldsymbol{0} \preceq \hat{{Q}}_n(s,a,w) - {V}^\pi(s) \preceq \gamma^n \mathcal{R}\]
◻
12.1 Approximate Pareto Coverage↩︎
In this subsection, we provide a detailed algorithmic characterization of the policy execution (or “unrolling”) procedure derived from our Bellman operator, and we prove its convergence properties.
We begin by establishing the necessary notation and definitions. The core intuition is that the computation of the \(n\)-th Bellman update \(\mathcal{T}^n Q(s_1, a_1, w_1)\) naturally relies on the optimal substructure of \(\mathcal{T}^{n-1} Q(s_2, a_2, w_2)\), which in turn relies on \(\mathcal{T}^{n-2} Q\), and so on. This recursive dependency allows us to “unroll” the sequence of actions and preferences \((a_1, w_1), (a_2, w_2), \dots\) originally selected during the computation of \(\mathcal{T}^n Q\). We formally define the policy that performs this unrolling in Definition 8.
Since the value function is initialized with the maximum obtainable rewards, \(\mathcal{R} = \frac{\mathbf{R}_{\max}}{1-\gamma} \mathbf{1}\in \mathbb{R}^d_{\geq 0}\), the Bellman estimate \(\mathcal{T}^n Q(s,a,w)\) can be decomposed into the sum of rewards obtained by this unrolled policy over \(n\) steps plus a residual term \(\gamma^n \mathcal{R}\).
Crucially, because \(\mathcal{T}^n Q\) is simply this finite-horizon sum shifted by the constant residual \(\gamma^n \mathcal{R}\), optimizing the Chebyshev scalarization \(O_w(\mathcal{T}^n Q)\) allows us to identify Pareto-optimal policies for the \(n\)-step horizon. In Theorem 10, we establish a rigorous one-to-one correspondence between the set of Pareto-optimal policies and the Pareto-optimal \(\mathcal{T}^n Q\) values for each state and action.
This correspondence serves as the theoretical foundation for our deployment procedure. Given an \(n\)-step Bellman estimate \(\mathcal{T}^n Q\), our policy selects an action that maximizes this estimate. By greedily optimizing for the \(n\)-step horizon at each step, we ensure that the resulting policy weakly dominates the \((n-1)\)-step policy that was implicitly used to compute the optimal continuation \(\mathcal{T}^{n-1} Q\). This monotonic improvement property allows us to prove the Simulation Lemma (Theorem 12), which confirms that the actual accumulated rewards of our greedy policy satisfy the bounds predicted by the Bellman estimate, thereby concluding the proofs for approximate coverage and parsimony.
Definition 7 (Horizon-Dependent Greedy Selector Functions). For any Bellman update iterate \(k \ge 0\), current state \(s \in S\), action \(a \in A\), and preference \(w \in \mathcal{W}\), let the selector functions \[\hat{A}_k(s, a, w, \cdot): S \to A \quad \text{and} \quad \hat{W}_k(s, a, w, \cdot): S \to \mathcal{W}\] be the mappings that maximize the scalarized expected value of the \((k)\)-th estimate. They are defined as some solution to: \[\big(\hat{A}_k(s,a,w, \cdot), \hat{W}_k(s,a,w, \cdot)\big) \in \operatorname*{arg\,max}_{\substack{\phi_A: S \to A,\\ \phi_W: S \to \mathcal{W}}} O_w\Big( \mathbb{E}_{s' \sim p(\cdot|s,a)} \big[\mathcal{T}^{k}Q(s', \phi_A(s'), \phi_W(s'))\big] \Big)\]
Using the greedy selector functions, we are able to select an action \(\hat{A}_i(s,a,w,s')\) and a preference \(\hat{W}_i(s,a,w,s')\) at each step, allowing us to unroll the rewards \(R(s', \hat{A}_i(s,a,w,s'))\) involved in computing \(\mathcal{T}^n Q(s,a,w)\) up to \(n\) steps.
Definition 8 (Induced Policy Definition). Let \(n \in \mathbb{N}\) be the iterate index of the Bellman update \(\mathcal{T}^n Q\). For a starting configuration of state \(s \in S\), action \(a \in A\), and preference \(w \in \mathcal{W}\), we define the policy \(\pi_{n}^{s,a,w}\) as a mapping from a history \(h\) and a next state \(s'\) to an action.
Let \(H_{s,a}\) denote the set of all histories starting with the pair \((s,a)\). That is, any \(h \in H_{s,a}\) of length \(t\) is a sequence \(h = (s_1, a_1, s_2, a_2, \dots, s_t, a_t)\) where \(s_1 = s\) and \(a_1 = a\).
To define the policy behavior, we first define the notion of history consistency and induced preference sequence:
History Consistency: A history \(h\) is said to be consistent if, for all steps \(1 < i \le t\), the action taken matches the greedy selector for the induced preference: \[a_i = \hat{A}_{n-(i-1)}(s_{i-1}, a_{i-1}, w_{i-1}, s_i)\]
Induced Preference Sequence: For a history \(h\), we construct the sequence of target preferences \((w_1, \dots, w_t)\) recursively: \[w_i = \begin{cases} w & \text{if } i = 1 \\ \hat{W}_{n-(i-1)}(s_{i-1}, a_{i-1}, w_{i-1}, s_i) & \text{if } 1 < i \le t \end{cases}\]
Based on these definitions, the policy \(\pi^{s,a,w}_n(s' \mid h)\) is defined as follows:
Case \(t \ge n\) (Horizon Exceeded): If the history length exhausts the horizon (\(t \ge n\)), the policy behaves arbitrarily.
Case \(t < n\) (Within Horizon):
If the history \(h\) is consistent, the policy selects the greedy action for the next state \(s'\) according to the current preference \(w_t\): \[\pi^{s,a,w}_n(s' \mid h) := \hat{A}_{n-t}(s_t, a_t, w_t, s')\]
If the history \(h\) is inconsistent, the policy behaves arbitrarily.
Having formally defined the induced policy \(\pi^{s,a,w}_m\) which explicitly unrolls the recursive action selection inherent in the Bellman estimate \(\mathcal{T}^n Q\), we now introduce the concept of the \(n\)-step expected return. This definition provides the quantity needed to subsequently prove Lemma 2, demonstrating that the value computed by the operator is realized by the execution of the induced policy upto a residual term \(\gamma^n\mathcal{R}\).
Definition 9 (\(n\)-Step Value). Given a policy \(\pi:(S\times A)^*\times S\rightarrow A\), the \(n\)-step expected return starting from state \(s\) is defined as: \[V^\pi_n(s) := \mathbb{E}\left[ \sum_{t=1}^{n} \gamma^{t-1} R(s_t, a_t) \;\middle|\; s_1 = s, \, a_t = \pi(s_t \mid h_{t-1}) \right]\] where \(h_{t-1} = (s_1, a_1, \dots, s_{t-1}, a_{t-1})\) denotes the history of state-action pairs prior to the current step (with \(h_{0} = \emptyset\)).
Lemma 2 (Bellman Consistency). For any horizon \(n \in \mathbb{N}\), state \(s \in S\), action \(a \in A\), and preference \(w \in \mathcal{W}\), the induced policy \(\pi = \pi^{s,a,w}_n\) satisfies: \[\mathcal{T}^n Q(s,a,w) - \gamma^n \mathcal{R} = V^{\pi}_n(s).\]
Proof Sketch.. The proof follows directly from the construction of the policy. The Bellman operator \(\mathcal{T}^n\) is defined by a sequence of nested maximizations, where at each depth \(t\), the operator selects the optimal strategy (action and preference) to maximize the continuation value.
By Definition 8, the policy \(\pi^{s,a,w}_n\) is explicitly constructed to replicate this optimization path. For every time step \(t \le n\), the policy computes the sequence of greedy selector functions implied by the history and executes the exact action \(\hat{a}_t\) that was chosen to maximize the corresponding stage of the Bellman update.
Since the policy chooses the action \(a_t\) at every step to match the maximizer of the Bellman operator’s \(t\)-th expansion, the distribution of trajectories induced by the policy is identical to those assumed in the calculation of \(\mathcal{T}^nQ\). Consequently, the expected sum of discounted rewards generated by the policy (the value \(V^\pi_n\)) is identical to the value computed by the Bellman update (minus the discounted residual at step \(n\)). ◻
We next establish a one-to-one correspondence between the \(n\)-step values obtained by \(n\)-step Pareto-optimal policies and the \(n\)-step Bellman estimate in Theorem 10. However, prior to this, we prove in Lemma 3 that \(n\)-step Pareto-optimal policies exhibit optimal substructure, ensuring that the induced subpolicy following the first step is itself \((n-1)\)-step Pareto-optimal.
Lemma 3 (Pareto Optimal Subpolicy). Let \(\pi\) be a policy that is Pareto-optimal for the \(n\)-step value \(V^\pi_n(s)\). Let \(s'\) be any state reachable from \(s\) at the second step with non-zero probability.
Then, the continuation policy \(\pi(\cdot \mid s, a)\), which represents the behavior of \(\pi\) for all steps following the history \((s, a)\), must be Pareto-optimal for the remaining \((n-1)\)-step value \(V^{\pi(\cdot\mid s,a)}_{n-1}(s')\) starting from \(s'\).
Proof. Suppose for the sake of contradiction that the continuation policy \(\pi(\cdot \mid s, a)\) is not Pareto-optimal for the state \(s'\).
This implies there exists an alternative continuation policy \(\tilde{\pi}\) such that its value strictly dominates the original continuation value at \(s'\): \[V^{\tilde{\pi}}_{n-1}(s') \succ V^{\pi(\cdot \mid s, a)}_{n-1}(s').\] We can construct a new global policy \(\pi^*\) by “stitching” the original policy behavior at the first step and replacing the behavior for the history \((s, a)\) and state \(s'\) onwards with \(\tilde{\pi}\).
By the linearity of expectation, the total value of this new policy is: \[V^{\pi^*}_n(s) = R(s,a) + \gamma \mathop{\mathrm{\mathbb{E}}}_{\hat{s}} V^{\pi^*}_{n-1}(\hat{s}).\] Since \(\pi^*\) behaves identically to \(\pi\) for all states \(\hat{s} \neq s'\) (and behaves like \(\tilde{\pi}\) at \(s'\)), the difference in value is: \[V^{\pi^*}_n(s) - V^{\pi}_n(s) = \gamma \cdot p(s'|s,a) \cdot \left( V^{\tilde{\pi}}_{n-1}(s') - V^{\pi(\cdot \mid s, a)}_{n-1}(s') \right).\] Since the term in the parentheses is strictly positive (by our assumption of dominance), it follows that \(V^{\pi^*}_n(s) \succ V^{\pi}_n(s)\).
This implies that \(\pi^*\) dominates \(\pi\), which contradicts the initial assumption that \(\pi\) was Pareto-optimal. Therefore, the continuation policy must be Pareto-optimal. ◻
Theorem 10 (Duality of \(n\)-th Pareto-Optimal Estimate and \(n\)-step Pareto-Optimal Policy). Let \(\mathcal{T}^n Q(s,a,w)\) denote the \(n\)-th Bellman estimate. The following relationships hold between the Pareto optimality of the Bellman estimates and the Pareto optimality of the resulting policies:
\(n\)-Step Preference Optimality \(\implies\) \(n\)-Step Policy Optimality
Let \(w \in \mathcal{W}\) be a preference such that the corresponding Bellman estimate is Pareto-optimal. That is, assume: \[\forall w' \in \mathcal{W}, \quad \mathcal{T}^n Q(s,a,w) \nprec \mathcal{T}^n Q(s,a,w').\] Then, the policy \(\pi = \pi_n^{s,a,w}\) is Pareto-optimal with respect to the \(n\)-step return among all policies starting with the same state \(s\) and the same action \(a\). Specifically, for every history-dependent deterministic policy \(\pi' \in \Pi\) such that \(\pi'(s) = \pi(s)=a\): \[V^{\pi}_n(s) \nprec V^{\pi'}_n(s).\]\(n\)-Step Policy Optimality \(\implies\) \(n\)-Step Preference Optimality
Let \(\pi\) be any history-dependent deterministic policy such that \(\pi(s) = a\) and its \(n\)-step value is Pareto-optimal among all such policies (i.e., \(\forall \pi' \in \Pi\) with \(\pi'(s)=a\), \(V^{\pi}_n(s) \nprec V^{\pi'}_n(s)\)).Define the specific preference vector \(w^*\) based on the direction of the future expected return: \[w^* = \frac{V^\pi_n(s) + \gamma^n \mathcal{R} - R(s,a)}{\left\| V^\pi_n(s) + \gamma^n \mathcal{R} - R(s,a) \right\|_2}.\] Then, the Bellman estimate targeting this preference recovers the policy’s value and is itself Pareto-optimal: \[\mathcal{T}^n Q(s, a, w^*) = V^\pi_n(s) + \gamma^n \mathcal{R},\] and \[\forall w' \in \mathcal{W}, \quad \mathcal{T}^n Q(s, a, w^*) \nprec \mathcal{T}^n Q(s, a, w').\]
Proof. We prove both statements by induction on the horizon \(n\).
Base Case (\(n=1\)): For any \(s, a, w\), \(\mathcal{T}^1 Q(s,a,w) = R(s,a) + \gamma \mathcal{R}\) and \(V^\pi_1(s) = R(s,a)\). Since \(R(s,a)\) is constant given \(a\), all estimates and policy values are identical. No value strictly dominates another, so all are Pareto-optimal. Both statements hold vacuously.
Inductive Step: Assume both statements hold for horizon \(n-1\). We prove them for horizon \(n\).
Part 1: Preference Optimality \(\implies\) Policy Optimality Assume \(\mathcal{T}^n Q(s,a,w)\) is Pareto-optimal. Let \(\pi = \pi_n^{s,a,w}\). Suppose for contradiction that \(\pi\) is not Pareto-optimal. Then there exists a policy \(\pi'\) (where \(\pi'(s)=a\)) such that \(V^{\pi'}_n(s) \succ V^{\pi}_n(s)\). Expanding the values: \[R(s,a) + \gamma \mathbb{E}_{s'}\left[ V^{\pi'(\cdot|s,a)}_{n-1}(s') \right] \succ R(s,a) + \gamma \mathbb{E}_{s'}\left[ V^{\pi(\cdot|s,a)}_{n-1}(s') \right].\] By Lemma 3, the continuation of \(\pi'\) must be Pareto-optimal for the \((n-1)\) horizon (otherwise we could improve it to get an even better policy). By the Induction Hypothesis (Part 2), for every state \(s'\), there exists a preference \(w'_{s'}\) such that the Bellman update recovers the value of this continuation policy: \[\mathcal{T}^{n-1}Q(s', \pi'(s'\mid s,a), w'_{s'}) = V^{\pi'(\cdot|s,a)}_{n-1}(s') + \gamma^{n-1}\mathcal{R}.\] Now, consider the global Bellman update \(\mathcal{T}^n\) calculated with a preference \(w_{\text{dom}}\) that is aligned with the expected value vector \(\mathop{\mathrm{\mathbb{E}}}\limits_{s'}V_{n-1}^{\pi'(\cdot \mid s,a)}(s')\) of \(\pi'\) after the first step. By the Principle of Aligned Dominance 1, since the Bellman operator maximizes scalarized expectation over all possible next actions and preferences, the resulting value must be at least as high as that of \(\pi'\) in the direction of \(w_{\text{dom}}\). Consequently, there exists a preference \(w_{\text{dom}}\) such that: \[\mathcal{T}^n Q(s, a, w_{\text{dom}}) \succeq V^{\pi'}_n(s) + \gamma^n\mathcal{R} \succ V^{\pi}_n(s) + \gamma^n\mathcal{R}.\] Using the consistency property (Lemma 2), \(V^{\pi}_n(s) + \gamma^n\mathcal{R} = \mathcal{T}^n Q(s,a,w)\). Thus: \[\mathcal{T}^n Q(s, a, w_{\text{dom}}) \succ \mathcal{T}^n Q(s,a,w).\] This contradicts the assumption that \(\mathcal{T}^n Q(s,a,w)\) was Pareto-optimal. Thus we arrive at a contradiction because of our assumption that \(\pi\) is not \(n\)-step Pareto-optimal starting from the state \(s\). So, \(\pi\) has to be \(n\)-step Pareto-optimal.
Part 2: \(n\)-Step Policy Optimality \(\implies\) \(n\)-Step Preference Optimality
Assume \(\pi\) is a Pareto-optimal policy for the first \(n\)-steps with \(\pi(s)=a\). That is, for any \(\pi' \in \Pi\) such that \(\pi'(s)=\pi(s)\), we have \(V^{\pi}_n(s) \nprec V^{\pi'}_n(s)\).
We define the expected future return vector adjusted for the tail: \[U^* := V^\pi_n(s) - R(s,a) + \gamma^n \mathcal{R}.\] We define the target preference \(w^*\) to be aligned with this return: \[w^* := \frac{U^*}{\|U^*\|_2}.\] We now analyze the Bellman update \(\mathcal{T}^n Q(s,a,w^*)\). By Definition 7, this operator computes the expectation over the optimal next-step greedy selectors: \[\mathcal{T}^n Q(s,a,w^*) = R(s,a) + \gamma \mathbb{E}_{s'} \left[ \mathcal{T}^{n-1}Q\Big(s', \hat{A}_{n-1}(s,a,w^*,s'), \hat{W}_{n-1}(s,a,w^*,s')\Big) \right].\]
Step 2.1: Feasibility (Lower Bound)
By Lemma 3, the continuation policy \(\pi(\cdot|s,a)\) is Pareto-optimal for the \((n-1)\) horizon. By the Inductive Hypothesis (Part 2), for every next state \(s'\), there exists a preference \(w_{s'}\) such that the
\((n-1)\)-th estimate recovers this continuation value: \[\mathcal{T}^{n-1}Q(s', \pi(s'|s,a), w_{s'}) = V^{\pi(\cdot|s,a)}_{n-1}(s') + \gamma^{n-1}\mathcal{R}.\] The Bellman
operator maximizes the scalarized objective over all possible next-step actions and preferences. Since the specific action chosen by the policy, \(a'_{s'} = \pi(s' \mid s, a)\), and the preference \(w_{s'}\) constitute a valid candidate pair \((a'_{s'}, w_{s'})\) in this search space, the scalar value achieved by the optimal selectors \(\hat{A}_{n-1}, \hat{W}_{n-1}\) must be at least that of the configuration used by \(\pi\): \[O_{w^*}(\mathcal{T}^n Q(s,a,w^*) - R(s,a)) \ge O_{w^*}(U^*).\]
Step 2.2: Contradiction (Equality)
Suppose for the sake of contradiction that the inequality is strict. That is, the Bellman operator finds a configuration of greedy selectors \(\hat{A}_{n-1}\) and \(\hat{W}_{n-1}\) that
yields a strictly higher scalarized value: \[O_{w^*}\left( \gamma \mathbb{E}_{s'} \left[ \mathcal{T}^{n-1}Q(s', \hat{A}_{n-1}(\dots), \hat{W}_{n-1}(\dots)) \right] \right) > O_{w^*}(U^*).\] Let \(V_{new}\) denote this superior expected value found by the operator. By the Inductive Hypothesis (Part 1), for each next state \(s'\), the term \(\mathcal{T}^{n-1}Q(s', \hat{A}_{n-1}(\dots), \hat{W}_{n-1}(\dots))\) corresponds to the value of some valid Pareto-optimal policy \(\pi'_{s'}\) starting at \(s'\).
We can “stitch" these policies together to form a new global policy \(\pi_{stitch}\). We define \(\pi_{stitch}\) such that it executes action \(a\) at the root state \(s\), and for any subsequent state \(s'\) reached, it adopts the behavior of the corresponding sub-policy \(\pi'_{s'}\). Formally, for a history \(h\): \[\pi_{stitch}(h) = \begin{cases} a & \text{if } h = (s) \\ \pi'_{s'}(h') & \text{if } h = (s, a ) \circ h' \end{cases}\] where \(h'\) denotes the local history suffix starting from \(s'\).
The value of this new policy is precisely the value found by the operator: \[V^{\pi_{stitch}}_n(s) - R(s,a) + \gamma^n \mathcal{R}= \gamma \mathbb{E}_{s'} \left[ \mathcal{T}^{n-1}Q(s', \hat{A}_{n-1}(\dots), \hat{W}_{n-1}(\dots)) \right]\] Substituting this back into our inequality: \[O_{w^*}(V^{\pi_{stitch}}_n(s) - R(s,a) + \gamma^n \mathcal{R}) > O_{w^*}(V^{\pi}_n(s) - R(s,a) + \gamma^n \mathcal{R}).\] By Lemma 1 (Principle of Aligned Dominance), since \(w^*\) is the unit vector strictly aligned with the direction of the RHS vector, a strictly higher scalarization score implies strict vector dominance: \[V^{\pi_{stitch}}_n(s) \succ V^{\pi}_n(s).\] This contradicts the assumption that \(\pi\) is Pareto-optimal for the \(n\)-step discounted rewards. Therefore, strict inequality is impossible, and we must have equality: \[\mathcal{T}^n Q(s,a,w^*) = V^\pi_n(s) + \gamma^n \mathcal{R}.\]
Step 2.3: Pareto Optimality of the Estimate
Finally, we prove that the estimate \(\mathcal{T}^n Q(s,a,w^*)\) is itself Pareto-optimal. Suppose not; then there would exist a preference vector \(w'\) such that: \[\mathcal{T}^n Q(s,a,w') \succ \mathcal{T}^n Q(s,a,w^*).\] Without loss of generality, we assume that the estimate \(\mathcal{T}^n Q(s,a,w')\) is itself Pareto-optimal (otherwise, we
could simply select a further dominating estimate).
We expand the term on the left-hand side using the definition of the Bellman operator: \[\mathcal{T}^n Q(s,a,w') = R(s,a) + \gamma \mathbb{E}_{s' \sim p(\cdot \mid s,a)}\left[ \mathcal{T}^{n-1}Q\big(s', \hat{A}_{n-1}(s,a,w',s'), \hat{W}_{n-1}(s,a,w',s')\big) \right].\] Let \(\hat{a}_{s'} = \hat{A}_{n-1}(s,a,w',s')\) and \(\hat{w}_{s'} = \hat{W}_{n-1}(s,a,w',s')\). Since \(\mathcal{T}^nQ(s,a,w')\) is Pareto-optimal, each inner term \(\mathcal{T}^{n-1}Q(s', \hat{a}_{s'}, \hat{w}_{s'})\) must be a Pareto-optimal estimate for the \((n-1)\) horizon (otherwise, we could replace it with a dominating term to obtain a quantity strictly more than \(\mathcal{T}^nQ(s,a,w')\) leading to a contradiction of \(\mathcal{T}^nQ(s,a,w')\) being Pareto-optimal).
By the Inductive Hypothesis (Part 1), for each \(s'\), there exists a Pareto-optimal policy \(\pi'_{s'}\) starting at \(s'\) such that its value matches this estimate: \[V^{\pi'_{s'}}_{n-1}(s') + \gamma^{n-1}\mathcal{R} = \mathcal{T}^{n-1}Q(s', \hat{a}_{s'}, \hat{w}_{s'}).\] We can now construct a new global policy \(\pi_{new}\) that takes action \(a\) at state \(s\), and for any subsequent history \(h = ((s, a) , h')\), follows the policy \(\pi'_{s'}(h')\). The value of this stitched policy is: \[V^{\pi_{new}}_n(s) + \gamma^n \mathcal{R} = R(s,a) + \gamma \mathbb{E}_{s'} \left[ V^{\pi'_{s'}}_{n-1}(s') + \gamma^{n-1}\mathcal{R} \right] = \mathcal{T}^n Q(s,a,w').\] Combining this with our initial dominance assumption: \[V^{\pi_{new}}_n(s) + \gamma^n \mathcal{R} \succ \mathcal{T}^n Q(s,a,w^*) = V^\pi_n(s) + \gamma^n \mathcal{R}.\] Simplifying, we get \(V^{\pi_{new}}_n(s) \succ V^\pi_n(s)\). This contradicts the assumption that \(\pi\) is Pareto-optimal. Thus, no such dominating preference \(w'\) can exist. ◻
In the next theorem, we establish the transformation in the preference required to obtain a one-to-one correspondence between Pareto-optimal policies and Bellman estimates.
Theorem 11 (Bellman-Policy Pareto Equivalence and Scalarization Alignment). Combining the Bellman Consistency (Lemma 2) and the Pareto Duality (Theorem 10), we establish the following equivalence:
Estimates generate optimal policies aligned with future returns:
If the Bellman estimate \(\mathcal{T}^n Q(s,a,w)\) is Pareto-optimal (i.e., \(\forall w' \in \mathcal{W}, \mathcal{T}^nQ(s,a,w) \nprec \mathcal{T}^nQ(s,a,w')\)), then the resulting policy \(\pi = \pi_n^{s,a,w}\) is Pareto-optimal for the \(n\)-step return among all policies starting with action \(a\) (i.e., \(\forall \pi' \in \Pi \text{ s.t. } \pi'(s)=a, V^\pi_n(s) \nprec V^{\pi'}_n(s)\)).Furthermore, this policy maximizes the scalarized expected return for the specific preference direction \(w_{\text{eff}}\) aligned with the estimated value adjusted for the tail: \[w_{\text{eff}} = \frac{\mathcal{T}^n Q(s,a,w) - \gamma^n \mathcal{R}}{\left\| \mathcal{T}^n Q(s,a,w) - \gamma^n \mathcal{R} \right\|_2}.\] That is, \(\forall \pi' \in \Pi \text{ s.t. } \pi'(s)=a, \quad O_{w_{\text{eff}}}(V^\pi_n(s)) \geq O_{w_{\text{eff}}}(V^{\pi'}_n(s))\).
Optimal policies correspond to specific Bellman estimates:
Conversely, let \(\pi\) be a history-dependent policy that takes action \(a\) at state \(s\) and is Pareto-optimal for the \(n\)-step horizon among all such policies (i.e., \(\forall \pi' \in \Pi \text{ s.t. } \pi'(s)=\pi(s)=a, V^{\pi}_n(s) \nprec V^{\pi'}_n(s)\)).Then, its value is exactly recovered by the Bellman operator targeting the preference \(w^*\) aligned with the policy’s actual future return: \[w^* = \frac{V^\pi_n(s) - R(s,a) + \gamma^n \mathcal{R}}{\left\| V^\pi_n(s) - R(s,a) + \gamma^n \mathcal{R} \right\|_2}.\] Specifically, the Bellman estimate recovers the policy value: \[\mathcal{T}^n Q(s, a, w^*) = V^\pi_n(s) + \gamma^n \mathcal{R},\] and this estimate is itself Pareto-optimal (i.e., \(\forall w' \in \mathcal{W}, \mathcal{T}^n Q(s, a, w^*) \nprec \mathcal{T}^n Q(s, a, w')\)).
Next we give the exact algorithm for greedy policy based on the \(n^{th}\)-Bellman estimate.
Description: The execution procedure is detailed in Algorithm 9. The process begins (Lines 2–5) by identifying the optimal action and next-preference pair \((\hat{a}_0, \hat{w}_1)\) for the initial state \(s_0\).
The core of the execution loop relies on dynamic preference alignment. By Lemma 2 the current estimate \(\mathcal{T}^n Q(s_t, a_t, w_{\text{target}})\) corresponds to the value of an \(n\)-step policy (\(\pi^{s,a,w}_n\)), specifically \(\mathcal{T}^n Q - R - \gamma^n \mathcal{R}\). In Line 12 and 13, we explicitly calculate the preference direction \(\hat{w}_{t+1}\) that aligns with this future value component.
In Line 15, the algorithm performs a search to find the action and preference maps \((\hat{A}, \hat{W})\) that greedily maximize the scalarized expected return with respect to the aligned preference \(\hat{w}_{t+1}\). By the Principle of Aligned Dominance (Lemma 1), maximizing this specific scalarization guarantees that the resulting policy choice dominates the future component of the previous estimate. Finally, in Lines 19–20, the agent instantiates this policy for the actually observed state \(s_{t+1}\) to determine the next action \(a_{t+1}\) and target preference \(w_{\text{next}}\).
It is important to note that while the recursive calculation of the Bellman operator typically utilizes the \((n-1)\)-th estimate, our execution policy consistently utilizes the full \(n\)-th estimate \(\mathcal{T}^n Q\) for the lookahead optimization at every step, ensuring the highest available lookahead in action selection.
Theorem 12 (Recursive Trajectory Error Bound). Let \(\{(s_t, a_t, w_{t+1})\}_{t \ge 0}\) be the trajectory generated by the execution policy, where \(\hat{w}_{t+1}\) is the preference target aligned for the next step. Let \(V^\pi(s)\) denote the true value of the executed policy starting from state \(s\).
The following recursive inequality holds: \[\mathcal{T}^n Q(s_t, a_t, w_{t+1}) - V^\pi(s_t) \preceq \gamma \mathbb{E}_{s_{t+1} \sim p(\cdot|s_t, a_t)} \left[ \mathcal{T}^n Q(s_{t+1}, a_{t+1}, w_{t+2}) - V^\pi(s_{t+1}) \right] + \gamma^n(1-\gamma)\mathcal{R}\]
Proof. Let \(\Delta_t = \mathcal{T}^n Q(s_t, a_t, w_{t+1}) - V^\pi(s_t)\) denote the vector error at time step \(t\). We expand both terms using their respective Bellman definitions.
First, we expand the true policy value \(V^\pi(s_t)\) using the standard Bellman equation: \[V^\pi(s_t) = R(s_t, a_t) + \gamma \mathbb{E}_{s_{t+1} \sim p(\cdot|s_t, a_t)}\left[ V^{\pi(\cdot\mid s_t,a_t)}(s_{t+1}) \right]. \label{eq:true95val95expansion}\tag{6}\]
Next, we expand the \(n\)-step estimate \(\mathcal{T}^n Q(s_t, a_t, w_{t+1})\). From Lemma 2 we obtain that this estimate is composed of the immediate reward plus the discounted value of the tail policy plus a residual value: \[\mathcal{T}^n Q(s_t, a_t, w_{t+1}) = R(s_t, a_t) + \gamma \mathbb{E}_{s_{t+1} \sim p(\cdot|s_t, a_t)}\left[ V^{\text{tail}}_{n-1}(s_{t+1}) + \gamma^{n-1}\mathcal{R} \right]. \label{eq:est95val95expansion}\tag{7}\]
Subtracting 6 from 7 , the immediate reward \(R(s_t, a_t)\) cancels out: \[\Delta_t = \gamma \mathbb{E}_{s_{t+1}} \left[ \left( V^{\text{tail}}_{n-1}(s_{t+1}) + \gamma^{n-1}\mathcal{R} \right) - V^{\pi(\cdot\mid s_t,a_t)}(s_{t+1}) \right].\]
At step \(t+1\), the agent re-computes the estimate \(\mathcal{T}^n Q(s_{t+1}, a_{t+1}, w_{t+2})\) using a full \(n\)-step horizon and an updated preference \(\hat{w}_{t+1}\) explicitly aligned with \(\mathop{\mathrm{\mathbb{E}}}_{s_{t+1}}V^{\text{tail}}_n(s_{t+1})\). This fresh estimate is guaranteed to weakly dominate the residual value of the previous plan (the stale tail) by the Principle of Aligned Dominance (Lemma 1): \[V^{\text{tail}}_{n-1}(s_{t+1}) \;\preceq\; \mathcal{T}^n Q(s_{t+1}, a_{t+1}, w_{t+2})-\gamma^n\mathcal{R}\]
Substituting this inequality back into the expression for \(\Delta_t\), we obtain: \[\begin{align} \Delta_t &\preceq \gamma \mathbb{E}_{s_{t+1}} \left[ \mathcal{T}^n Q(s_{t+1}, a_{t+1}, w_{t+1}) - V^{\pi(\cdot\mid s_t,a_t)}(s_{t+1}) \right] + \gamma^n(1-\gamma)\mathcal{R}\\ &\preceq \gamma \mathbb{E}_{s_{t+1}} \left[ \Delta_{t+1} \right] + \gamma^n(1-\gamma)\mathcal{R} \end{align}\]
Thus, the error at time \(t\) is bounded by the discounted expected error at time \(t+1\). ◻
Theorem 13 (Approximate Pareto Coverage). Let \(\mathcal{C}^n_{PO} = \{ \pi_w \mid w \in \mathcal{W} \}\) denote the set of policies generated by all preferences using the \(n\)-th Bellman update by Algorithm 5. This set satisfies the properties of approximate Pareto coverage.
Approximate Coverage: Every Pareto-optimal policy is approximated by some policy in \(\mathcal{C}^n_{PO}\) such that the suboptimality gap is bounded. Formally: \[\begin{align} &\forall \pi \in \Pi, \exists w \in \mathcal{W} \text{ such that } \\ & V^{\pi}(s_0) \preceq V^{\pi_w}(s_0) + \gamma^n \mathcal{R} \end{align}\]
Approximate Parsimony: Every policy in \(\mathcal{C}^n_{PO}\) satisfies \(\boldsymbol{\gamma}^{\boldsymbol{n}}\boldsymbol{\mathcal{R}}\)-Pareto optimality; that is, no other policy can strictly dominate it by a margin larger than the approximation bound. Formally: \[\begin{align} &\forall w \in \mathcal{W}, \forall \pi \in \Pi \quad \text{ we get} \\ &V^{\pi}(s_0) \nsucc V^{\pi_w}(s_0) + \gamma^n \mathcal{R} \end{align}\]
Proof. Using Theorem 12, we obtain \(\Delta_t\preceq \gamma \mathop{\mathrm{\mathbb{E}}}_{s_{t+1}}[\Delta_{t+1}] + \gamma^n(1-\gamma)\mathcal{R}\), therefore taking a max for each component allows us to prove \(\Delta_{max}\preceq \gamma^n\mathcal{R}\). Therefore starting with any \(n^{th}\) estimate \(\mathcal{T}^nQ(s,a,w)\) the procedure obtains a value \(V^\pi(s)\), such that \(\mathcal{T}^nQ(s,a,w)\preceq V^\pi(s)+\gamma^n\mathcal{R}\).
Approximate Coverage: Since we prove in Theorem [prop:opt95coverage] that every Pareto-optimal policy \(\pi^*\) is dominated by an estimate \(V^{\pi^*}(s)\preceq \mathcal{T}^nQ(s,a,w')\preceq V^{\pi_{w'}}(s)+\gamma^n\mathcal{R}\).
Approximate Parsimony: Since there is no policy that dominates an estimate \(\mathcal{T}^nQ(s,a,w)\) we obtain that there is no policy that dominates \(V^{\pi_w}(s_0)+\gamma^n\mathcal{R}\).
◻
References↩︎
While dominance is defined here with respect to the initial state \(s_0\), the concept naturally extends to any initial state distribution \(\mathcal{I} \in \Delta(S)\) by substituting \(V^\pi(s_0)\) with \({V}^\pi(\mathcal{I})\).↩︎